(考研复试)操作系统笔记

1 操作系统的目标 提高资源利用率 提高系统吞吐量 使用户使用更方便 兼容新的计算机硬件和软件 2 操作系统的作用 用户和计算机硬件之间的接口 使用 户方便的操纵硬件 计算机系统的管理者 对计算机资源 进行抽象 3 计算机系统的发展 人工操作方式 穿孔卡片 单道 批处理系统 每次只从磁盘中调入一个程序进内存 多道 批处理系统 调入多个程序 CPU 可以切换 分时操作系 统 将一台主机给多个用户使用 实时操作系统 响应快 同时面对大量的远程终端 4 操作系统特点 并发 共享 虚拟 空分 时分 异 步 5 操作系统的功能 CPU 管理 进程控制 同步 通信 调度 存储器管理 内存分配 内存保护 地址映射 内 存扩充 设备管理 缓冲管理 设备分配 设备处理 文 件管理 存储管理 目录管理 读写保护管理 接口 用 户接口管理 程序接口管理 6 操作系统结构 模块化操作系统 分层式操作系统 C S 操作系统 分布式 微内核结构 建立在前三者的基 础上 微内核只提高 最基本 的服务 进程调度 进程 间通信 存储管理 处理 I O 设备 其他服务 如文件管 理 网络支持等通过接口连到微内核 微内核具有良好的 移植性 7 传统操作系统中 进程是资源分配和独立运行的基本单 位 8 为了并发才引入进程 9 进程控制块 PCB 是一个记录型数据结构 记录了操作 系统所需的用户描述进程的当前状况和控制进程运行的全 部信息 使一个在多道环境环境下不能独立运行的程序成 为一个可以独立运行的基本单位 系统创建一个进程的时 候就要顺带着创建 PCB OS 要调用一个进程的时候就要先 查看 PCB 系统将 PCB 组织成若干个链队列或索引表 PCB 中有进程标识符 处理机状态 进程调度信息 进程 控制信息等 10 进程的特性 动态 并发 独立 独立运行 独立分 配资源 独立接受调度 异步 不可预知的速度前进 11 进程的三种基本状态 就绪 阻塞 执行 就绪到执行 到阻塞再回到就绪 执行可以直接回到就绪 此外还有挂 起 创建 终止 12 进程的创建 申请 PCB 为新进程分配资源 子进程 可以继承父进程 比如父进程打开的文件 和父进程的缓 冲区等 初始化 PCB 把新的进程插入队列 13 进程的终止 找出 PCB 读出进程状态 若进程在执 行 就终止进程 若进程有子孙进程 还要把子进程终止 收回资源 移出 PCB 14 进程的阻塞 停止执行 PCB 插入阻塞队列 CPU 给 另外一个就绪进程 15 进程的唤醒 从阻塞队列中移出 PCB 插入就绪列队 中 16 临界资源是指每次仅允许一个进程访问的资源 每个 进程中访问临界资源的那段代码叫做临界区 17 整形信号量 用 S 表示资源数目 一个 wait 就资源减 一 一个 signal 就资源加一 其中执行 wait 前 如果资源数 小于 0 就要一直等待下去 用 while 循环 18 记录型信号量 防止进程一直 while 而等待 记录型信 号量先 S 1 然后判断 S 如果小于 0 了就调用 block 阻塞 于是就会有很多进程被阻塞 于是创建一个进程链表指针 链接阻塞进程 19 AND 型信号量 一个进程需要多个临界资源 AND 信 号量控制多个临界资源 只有当所有的临界资源的 S 都大于 1 的时候 才允许执行并所有的 S 都减一 20 信号量集 一个进程需要多个临界资源 而又有多个 进程 信号量集就是为多个进程服务 只有这些进程都可 以启动的时候才一起启动 每个资源都有不同的数量 所 以有资源数目 需求数目 下限数目 si ti di 21 计算机把各种硬件和软件都用数据结构抽象的描述其 资源特性 用少量信息和对资源所执行的操作来表征该资 源 而忽略内部结构和细节特性 同样 共享资源也用数 据结构来表示 代表共享资源的数据结构 以及由对共享 数据结构实施操作的一组过程所组成的资源管理程序 就 是管程 管程把数据结构包起来 只允许自己访问它 所 有进程要访问临界资源都要通过管程 而管程每次只允许 一个进程进入管程 从而实现进程互斥 22 生产者消费者问题 用一个数组代表 n 个缓冲区构成 一个缓冲池 用 mutex 实现互斥 empty 表示缓冲池中空 缓冲区的数量 full 表示满缓冲区的数量 生产者方面 先 wait empty 一定要等到 empty 0 了 才执行 empty 才能执行下一句 wait mutex 当缓冲池中没人 mutex 1 于是通过 生产者把货物放进缓冲池 缓冲区 数组下标加 1 然后释放 signal mutex 然后 signal full 加 1 消费者就是先 wait full 然后 wait mutex 然后数组下标 然后释放 mutex 和 empty 23 哲学家进餐 第 i 位哲学家要用到第 i 个筷子和第 i 1 个筷子 有多少个筷子就会有多少个信号量 用信号量数 组来表示 第 i 个哲学家 要 wait s i wait s i 1 然 后吃 然后释放两个信号量 24 读者写者问题 只要有一个 reader writer 就不允许 设置两个信号量 rmutex 表示有 rmutex 个人可以同时读 和 wmutex 和 readcount readcount 等于 0 的时候才允 许写 读者方面 首先 wait rmutex 通过后要做一个判 断 readcount 0 如果等于 0 说明可能有进程在写 那么 再 wait wmutex 也就是说 如果有进程在写 就会导 致 wmutext 等于 0 那么这个 wait 就会阻塞 一直到没 有进程在写了 然后 readcount 并释放 rmutex 然后 执行读操作 因为允许多个进程读 所以要释放 rmutex 前面对于 rmutex 的执行仅仅是保证只有一个读进程对 wmutex 进行操作 此时 wmutex 是临界资源 执行完了读操作以后 又要对 wmutex 进行判断 先 readcount 如果 readcount 0 说明允许写了 于是就 释放写进程 siganl wmutex 这一步的前后依然要加上 wait rmutex 和 signal rmutex 写者很简单 就是先 wait wmutex 然后执行写操作 然后 signal wmutex 25 进程通信 共享存储器系统 基于共享数据结构 基 于共享存储区 通过关键字 消息传递系统 进程间的数 据交换以格式化的消息为单位来传递 分为直接通信方式 直接发给目标进程 和间接通信方式 类似邮箱 管 道通信 直接连接读进程和一个写进程 把数据流入管道 即可 26 处理机调度层次 高级调度 作业级调度 把外存作 业调入内存 作业进入系统后 就分配一个 JCB 系统对 JCB 进行控制 低级调度 进程调度 保存处理机现场信 息 选取进程 把处理机分配给进程 有抢占和非抢占两 种 中级调度 把不能运行的进程调到外存去 27 调度算法要求 周转时间短 响应时间快 截止时间 有保证 优先权 系统吞吐量高 处理利用率高 各资源 平衡利用 28 调度算法 先来先服务 短作业调度算法 优先权调 度算法 抢占和非抢占 响应比优先调度算法 动态优先 权 等待时间 要求服务时间 等待时间 时间片轮转法 多级反馈队列调度 按照每个优先级划分队列 程序一来 就是最高优先级队列 然后执行一个时间片 执行完以后 放入下一个优先级队列 每个优先级队列的对应的时间片 长度不一样优先级越高 就时间片越小 29 实时调度算法 要求系统处理能力强 大部分采用抢 占式 具有快速切换机制 最早截止时间优先 EDF 最低 松弛度优先级 LLF least laxity first 紧急程度越高 就优 先级越高 比如人物要在 200ms 内完成且自身时间就要 100ms 这就是紧急程度 30 产生死锁的必要条件 互斥 请求和保持 不剥夺 环路等到 31 预防死锁 摒弃 请求和保持 条件 运行之前申请 到所有资源 摒弃不剥夺条件 当进程提出的资源请求得 不到满足的时候 就放弃手上的所有资源 摒弃环路等待 条件 所有进程都必须按照一定的顺序申请资源 比如打 印进程必须先申请输入机 再申请打印机 再 32 银行家算法 维护 6 种数据结构 1 available j K 表示系统中现在有空闲的 J 类资源 K 个 2 MAX i j K 表示进程 i 需要 j 类资源最多 k 个 3 allocation i j k 表示进程 i 已经得到 j 类资源 k 个 4 need i j k 表示进程 i 还需要 j 类资源 k 个 5 work j k 表示整个系统含有可用的 j 资源的数目 k 和 available 类似 只不过 work 用于安全性算法中 6 finish i true 表示系统是否有足够多的资源分配给 进程 i 执行时 进程 i 发出 request j k 表示要 j 资源 k 个 然 后判断是不是 request j need i j 如果不是就出错 如果是就判断 request j available j 如果不是就等待 如果是就试探分配资源 并修改 available allocation need 然后执行安全性算法 如果 安全 就分配资源 如果不是 就恢复被修改的 available allocation need 进程等待 安全性算法 在所有进程中 找到一个进程 finish false 并且 need i j work i 如果没找到 if 所 有的 finish 都是 true 就都处于安全状态 if need i j work i 说明系统不安全 如果找到了 就 work i work i allocation i j finish i true 比如现在有 01234 五个进程 ABC 三种资源 维护 max allocation need available 4 张表 首先对现在进行安 全性算法 一开始 work available finish 都是 false 然后 看 work 是不是大于 0 的 need 发现小于 那么看 1 work 大于 1 的 need 于是执行 1 不是真正的执行 然后收回 1 的资源 work 变多了 然后判断是不是大于 2 的 need 不大于 然后判断是不是大于 3 的 need 大于 再收回 3 的 allocation 然后判断是不是大于 4 的 大于 收回 再判断是不是大于 0 的 大于 收回 再判断是不 是大于 2 的 大于 每次收回以后都要把 finish true 最 后全部的 finish 都是 true 这样就得到一个安全序列 13420 下面就开始真正的执行 进程 1 发出 request 1 0 2 小于 need 也小于 available 说明可以分配 然后修改四个 表 再判断分配给进程 1 后的安全性算法 得到一个安全序 列 进程 4 发出 request 3 3 0 request 3 3 0 小于 need 但是大于 available 由于 1 进程占据资源 于是进程 4 等待 0 发出 request request need 也 available 那么假 定为 0 分配资源 修改四张表 但是如果满足了 0 的要求 以后 可用资源也就是 available 已经无法满足所有进程的 need 进入不安全状态 备注 所谓不安全就是没有进程可以运行 可能导致 死锁 所谓安全序列就是至少按我和这个序列是安全的 但是不一定会按我这个序列执行 每个进程的 request 是不 定的 33 死锁的解除 剥夺资源 从其他进程中剥夺足够多的 资源 撤销进程 存储器管理 34 存储器由高到低 寄存器 主存 高速缓存 主存 磁盘缓存 磁盘 可移动存储介质 35 程序装入内存 先把源代码编译成多个目标模块 然 后把模块链接起来形成装入模块 然后装入内存 有绝对 装入 装入程序按照模块中的地址讲程序和数据装入内存 程序的逻辑地址和实际内存地址完全相同 可重定位装入 程序中的地址都是以 0 开始的 装入内存以后也用相对 地址来改变程序中的地址成绝对地址 动态运行时装入 在程序执行的时候再把相对地址改变成绝对地址 36 程序的链接 静态链接 装入时动态链接 运行时动 态链接 37 连续分配方式 一个用户程序分配一个连续的内存空 间 单一连续分配 内存分为系统区和用户区 用于单用 户 固定分区分配 用户空间划分成若干个固定的大小区 域 每个分区只装入一道作业 这样划分成几个分区就有 几个用户并行作业 动态分区分配 根据进程的实际需要 动态为之分配内存空间 每个分区的大小不一样 比如伙 伴系统 可重定位分区分配 内存中有很多碎片 为了移 动碎片 就必须移动文件 就是重定位文件 38 进程的换入换出 首先选择处于阻塞且优先级最低的 进程换出 然后启动磁盘 把该进程的程序和数据传送到 磁盘的对换区上 39 分页存储 连续分配会有很多碎片 如果整合随便开 销巨大 那么我们希望一个程序不要连续分配 于是引入 页 内存被划分成大小相等的页面 进程分配空间的时候 就把进程放在若干个可以不相邻的页面中 只有最后一个 页面允许空位 分页地址的地址结构 低 12 位为页内位移 高 20 位为页号 地址变换机构只是变化页号 页内位移是 不变的 有三种 基本地址变换 从页表寄存器读出页表 起始地址 然后页号加上起始地址就是页在页表中对应页 表项 然后从页表项中读出物理地址 加上页内位移 快 表 页表示在内存中的 CPU 存取一个数据要两次访问内 存 不爽 加入缓存 多级页表 40 分段存储 页面使固定分区到动态分区 目的是提高 内存利用率 段的大小不固定 那么引入分段是为了方便 程序员并且容易实现共享 如果是页 或许一个程序的代 码有 20 页 那么每个共享的程序都要维护一个 20 个页表 项的页表 段内位移 16 位 段号 16 位 用户可以按照自 己作业的逻辑关系划分成若干个段 也有段表和地址变换 机构 41 段页存储 集合二者所长先通过段号在段表中找到段 并提取段表项的页表起始地址 然后通过页号找到页表项 42 虚拟存储器 有的作业很大 要求的内存超过了内存 总量 每次只能调一部分进去 但是用户看到的大容量是 一种假象 所以叫虚拟存储器 可以用分页和分段来实现 43 虚拟存储器的分页 也是页表 但是有一部分还在硬 盘上 于是页表有所不同 还要指出所调的块在外存上的 地址 缺页中断 地址变换流程 程序请求访问一页 页 号如果正确 检索快表 如果在快表中 就形成物理地址 直接访问 如果不在就访问页表 如果页在内存 就修改 快表 然后访问物理地址 如果不在 就产生缺页中断 保留 CPU 现场 在外存中找到缺页 如果内存满了 就要 换页 如果被换出的页被修改了还要写回外存 如果内存 没满 启动 I O 直接调页 放入内存 修改页表 然后程 序重新请求访问该页 44 虚拟存储器的内存分配策略 固定分配局部置换 系 统给程序分配一定数目的物理块 就这么多数目 不能改 变 如果发现缺页就在该进程的页面中选一个调出 可变 分配全局置换 OS 保持一个空闲物理块队列 如果缺页 就从空闲物理块队列拿出一个装入一个页面 当没空闲的 了 在从任意进程中选择一块调出 可变分配局部置换 系统给程序分配一定数目的物理块 如果发现缺页就在该 进程的页面中选一个调出 如果频繁的发生缺页中断 就 多分配几个物理块 物理块分配算法 平均分配 进程大 小分配 进程优先级分配 45 调页策略 预调页 一次调入相邻的若干页 请求调 页 要什么页给什么页 46 页面置换算法 最佳置换法 被淘汰的页面是未来长 时间不会使用的 最近最久未使用 LRU 可以用寄存器 和栈实现 clock 置换算法 每个页面设置一个访问位 访 问某页的时候 访问位置 1 淘汰某页的时候访问为置 0 如果再淘汰这页 真的淘汰了 设备管理 47 I O 设备的分类 存储设备和输入输出设备 低中高速 设备 块设备和字符设备 独占共享虚拟设备 48 设备和控制器之间的接口 数据信号线 控制信号线 状态信号线 49 设备控制器 由处理机接口和设备接口 I O 逻辑三部 分组成 接受和识别命令 数据交换 标识和报告设备状 态 地址识别 数据缓冲 差错控制 50 I O 通道是一种特殊的处理机 51 总线系统 ISA EISA VESA PCI 52 程序 I O 处理机向控制器发送一个 I O 指令 把状态 寄存器设 busy 然后不断的循环测试 busy 如果 busy 为 1 表示输入机还没输完 如果为 0 处理机把数据寄存器 的数据取出 送到指定内存单元 这样完成了一个字符的 I O 中断驱动的 I O CPU 向设备控制器发一个 I O 命令 然后立即返回执行原来的任务 设备控制器自动控制 I O 设备 控制输入设备读数据 一旦数据进入数据寄存器 控制器就发送中断信号 CPU 取走数据信号 写入内存 直接存储器访问 DMA 不再以字节为单位 开始以数据块 为单位 直接由设备输入内存 仅完成一个数据块的传送 的开始和结束的时候才需要 CPU 干预 I O 通道 DMA 随 便可以完成一个数据块的传送 且只能传到一个内存区域 而通道可以传送一组数据块到不同的内存区域 CPU 要完 成一组相关的读写操作 只需向通道发送一个 I O 指令 给出所要执行的通道程序的首地址和 I O 设备 通道接受 到指令以后 执行通道程序完成 I O 任务 53 缓冲 缓冲是为了缓和 CPU 和 I O 速度不匹配的问题 减少对 CPU 的中断频率 放宽 CPU 中断响应时间要求 有 单缓冲和双缓冲 双缓冲可以同时双向通信 循环缓冲 缓冲池 循环缓冲只适用于某种特定的进程 当系统较大 时候 就会有许多这样的循环缓冲 于是有了可供多个进 程共享的缓冲池 54 中断处理程序 进程上下文切换 处理中断信号 读 取设备状态修改进程状态等 55 设备驱动程序 接受上层软件发来的抽象 I O 命令 转化为具体要求后发送给设备控制器 此外也接受设备控 制器发来的信号传给上层软件 56 为了实现设备分配 必须在系统中设置相应的数据结 构 设备控制表 系统为每一个设备分配一个设备控制表 记录本设备情况 包括设备队列队首指针 设备状态 设 备控制器表指针 重传次数 类似的还有控制器控制表 通道控制表 系统设备控制表 57 设备分配流程 首先根绝 I O 请求的物理设备名 找 到系统设备表 找出设备的设备控制表 找到设备状态字 段 找出与该设备连接的控制器的控制器控制表 在控制 器控制表中找到通道控制表 根据通道控制表知道是不是 忙碌等等 只有在设备 控制器 通道都分配成功的时候 才算分配成功 才可以启动 I O 设备传输数据 58 spooling 技术 假脱机技术 spooling 技术可以将 一台物理 I O 设备虚拟为多台逻辑 I O 设备 允许多个用 户共享一台物理 I O 设备 输入输出井 输入输出缓冲区 输入输出进程构成 井在磁盘上 缓冲区在内存上 比如 要共享一个打印机 用户要求打印的时候 SPOOLING 同 意打印 但是不真正的打印 而是输出井之中申请一个空 闲磁盘块 将要打印的数据输入其中 输出进程为用户进 程申请一张用户请求打印表 把用户打印要求写入表中 再把表挂到打印队列上 打印机空闲的时候 就取出表 把井中的传送到缓冲区 再打印 SPOOLING 提高了 I O 速度 实现了虚拟设备的功能 59 磁盘调度 先来先服务 最短寻道时间优先 选择要 求访问的磁道与当前磁道最近的进程 扫描算法 引入方 向的概念 选择是磁头移动方向上最近的进程 循环扫描 算法 扫描算法是磁道由左到右再由右到左 而这个是由 左到右 由左到右 由左到右 60 磁盘高速缓存 为了提高磁盘的 I O 速度 利用内存 中的存储空间来暂存磁盘中读出的盘块信息 逻辑上属于 磁盘 物理上属于内存 磁盘高速缓存有两种形式 一个 是在内存上固定分配一小块空间 另一个是内存上所有的 未分配空间都可以用 当有一个进程请求某个盘块的时候 就先查看磁盘高速缓存 如果高速缓存装满了 就要使用 置换算法 而且高速缓存里的还要周期性的写回磁盘 61 提高磁盘 I O 的方法 提前读 延迟写 本来要把某 个缓冲区的数据写回磁盘 但是考虑到可能等会还要用 于是就把这个缓冲区放到空闲缓冲区队列的最后 一直等 到这个空闲缓冲区需要被占用的时候 才写回去 优化物 理块分布 虚拟盘 RAM 利用内存仿真磁盘 文件管理 62 现代计算机是通过文件系统来组织和管理计算机所存 储的大量程序和数据的 数据分成数据项 记录 文件三 个等级 63 文件的逻辑结构 有结构文件 由一个以上的记录构 成 有顺序文件 索引文件 索引顺序文件 无结构文件 大量的源程序 可执行文件 库函数 就是无结构文件 64 文件的物理结构 顺序文件 串结构 按关键字排列 的顺序结构 索引文件 要查找第 i 个记录 根据一个 i 为参数的函数就可以获知记录的物理位置 索引顺序文件 只把诸多记录中抽取几个来做索引 查找的时候就先找 到这几个 然后以这几个为基址来顺序 直接文件 记录 键值本身就决定了物理地址 哈希文件 通过键值找到目 录表中的一项 这一项的内容可以指向相应的物理块 65 外存分配方式 连续分配方式 链接分配