操作系统大题总结解答

处理机的执行模式与执行状态处理机的执行模式与执行状态 大多数处理器都至少支持两种执行模式 一种是同操作系统有关的模式 另一种则是同用户程序有关的模 式 较低特权的模式称为用户模式 较高特权的模式称系统模式 控制模式或内核模式 内核模式能执行所有的指令 访问所有的内存 用户模式则只能执行有限的指令 访问规定的内存 处理器往往有一个或多个寄存器来保存处理器模式信息 程序状态字 PSW 为了防止操作系统及其关键数据 如 PCB 遭到用户程序有意或无意的破坏 通常将处理机的执行状态分 为两种 核心态与用户态 核心态又称管态 系统态 是操作系统管理程序执行时机器所处的状态 它具有较高的特权 能执行一切指令 能访问所有的寄存器和存储区 用户态又称目态 是用户程序执行时机器所处的状态 它具有较低的特权 只能执行规定的指令和只能访问指定的寄存器和存储区 信号量信号量练习 2 某电话亭每一时刻最多只能容纳一个人打电话 来打电话的人 如果看到电话亭空闲 则 直接进入电话亭打电话 如果看到电话亭里正有人在打电话 则在外面排队等候 直到轮到自己 再进入 电话亭打电话 请用信号量来表达打电话的进程对电话机的互斥使用逻辑 该电话亭每次只能容纳一个人打电话 进程 使用 所以是一个临界资源 资源量为 1 各进程要互斥使 用 用信号量来表达资源的数量 semaphore mutex 1 或 empty 1 main Cobegin Pi i 1 2 3 4 Coend 练习 3 某电话亭共有 3 台电话机 即能容纳 3 个人 3 个进程 同时打电话 来打电话的人 如果看到电 话亭有空闲机子 则直接进入电话亭打电话 如果看到电话亭人满 则在外面排队等候 直到轮到自己再 进入电话亭打电话 请用信号量机制表达打电话的进程对电话机资源的使用限制 用信号量来表达空闲的电话机数 资源量的初值为 3 表示开始时有 3 台空机子可用 semaphore empty 3 main Cobegin Pi i 1 2 3 Coend 4 生产者 消费者问题 一个说明空缓冲单元的数目 用 empty 表示 其初值为有界缓冲区的大小 n 另一个说明满缓冲单元的数 目 用 full 表示 其初值为 0 而有界缓冲区是一个临界资源 必须互斥使用 因此还需要另外设置一 个互斥信号量 mutex 其初值为 1 semaphore full 0 第一步 定义信号量 semaphore empty n 并为信号量赋初值 semaphore mutex 1 main 第二步 编写主函数 cobegin 在其中调用各个进程 produceri i 1 2 m P i i 1 2 3 P mutex 打电话 打完电话 走出电话亭 V mutex Pi i 1 2 3 P empty 打电话 打电话完毕 出电话亭 V empty consumerj j 1 2 k coend 例例 有三个作业按下表的时间提交给系统 按照先来先服务的调度算法计算它们的平均周转时间 T 和平均 带权周转时间 W 先来先服务先来先服务 T 2 00 2 90 3 00 3 2 63 W 2 2 2 90 1 3 00 0 25 3 5 30 短作业优先 T 2 00 3 15 2 00 3 2 38 W 2 2 3 15 1 2 00 0 25 3 4 05 表中有 4 个作业提交给系统 按响应比高者优先算法调度 计算它们的平均周转时间和平均带权周转时间 producer i while 1 生产一个产品 p empty p mutex 将一个产品送入有界 缓冲区 V mutex V full consumer j while 1 p full p mutex 从缓冲区中取出一个 产品 V mutex V empty 消费一个产品 作业 1 做完后 其它三个作业的响应比为 R2p 1 等待时间 估计运行时间 1 1 5 0 5 4 R3p 1 1 0 0 1 11 R4p 1 0 5 0 2 3 5 故作业 3 的响应比最大 作业 1 完成后要运行作业 3 作业 3 运行结束时 时间为 10 06 这时候再看作 业 2 4 的响应比哪个高 R2p 1 等待时间 估计运行时间 1 1 6 0 5 4 2 R4p 1 0 6 0 2 4 R2p R4p 所以先调度作业 2 到内存中 作业 2 运行完毕 结束时间为 10 36 T 2 2 1 1 1 1 3 4 1 625 W 2 00 2 2 1 0 5 1 1 0 1 1 3 0 2 4 5 7 银行家算法 例 1 若系统运行中出现如下所示的资源分配情况 该系统是否安全 如果进程 P2 此时提出资源申请 1 2 2 2 系统能否将资源分配给它 为什么 解 1 利用安全性算法对此刻的资源分配情况进行分析 可得到如下安全性检测表 从上表中可以看出 此时存在一个安全序列 P0 P3 P4 P1 P2 故该系统是安全的 请问还有其它的安全序列吗 如 P0 P3 P1 P4 P2 解 2 P2 提出请求 1 2 2 2 按银行家算法进行检查 Request 1 2 2 2 Need 2 3 5 6 Request 1 2 2 2 Available 1 6 2 2 试着把资源分配给 P2 资源分配表中 P2 的项目改变的有 Allocation Allocation 1 2 2 2 Need Need 1 2 2 2 Available Available 1 2 2 2 由此得到新的资源分配表 经检查发现可用的资源 Available 0 4 0 0 已不能再满足任何进程的需要 所以 系统处于不安全状态 系统不能把资源分配给 P2 内存的分配与回收内存的分配与回收 在多道程序设计的环境中 当有作业进入计算机系统时 存储管理模块应能根据当时的内存分配情况 按 作业要求 分配给它适当的内存 当某个作业完成之后不再使用内存时 应回收其占用的内存空间 按照分配时机的不同 有两种内存分配形式 静态存储分配和动态存储分配静态存储分配和动态存储分配 1 静态存储分配 指内存分配是在作业运行之前 各目标模块连接后 把整个作业一次性全部装入内存 并规定在作业 的整个运行过程中 不允许再申请其它内存或在内存中移动位置 也就是说 内存分配是在作业运行前一 次性完成的 2 动态存储分配 作业要求的基本内存空间是在目标模块装入内存时分配的 但在作业运行过程中 允许作业再申请 附加的内存空间或者在内存中移动 即分配工作可以在作业运行前及运行过程中逐步完成 显然 动态存储分配具有较大的灵活性 它不要求一个作业把全部信息装入内存才开始运行 而是在作业 运行期间需要某些信息时 系统才将其调入内存 作业中暂不使用的信息可放在辅存中 不必进入内存 从而大大提高了内存的利用率 因此 内存中所有的空闲区和已分配的区域应当被合理地组织起来 通常可用分区说明表 空闲区链表 存储分块表等组织内存区域 地址重定位地址重定位 1 内存空间 物理空间 内存是由若干个存储单元组成的 每个存储单元都有一个编号 该编号能唯一地确定一个存储单元 称为内存地址 物理地址 内存地址的集合称为内存地址 物理地址 空间 简称内存空间 它是一个线性空间 其编址顺序为 0 1 2 3 n 1 n 的大小由实际组成存储器的存储单元的个数 决定 如 某个系统有 64KB 内存 则其内存空间为集合 0 1 2 65535 2 逻辑地址空间 在多道程序环境中 内存中可同时驻留多个相互独立的进程 这些进程在内存中的地址 用户事先并不知道 且应用程序装入内存是随机的 每次装入内存时所占用的 内存空间可能都不一样 因此 用户不能直接使用内存的物理地址来编程 为了方便用户编程 用户使用高级语言或汇编语言编程时 使用的是符号地址 即用符号名来访问某一单 元 把程序中由符号名组成的程序空间称为符号名空间 简称名空间 用户编写的源程序经过编译后 会形成若干个目标程序 每个目标程序的首地址都为 0 即每个目标程序都是以 0 为基址顺序进行编址的 原来用符号名访问的单元被具体的数据 单元号取代 这些地址 或相对于基址的单元号 称为逻辑地址 或虚地址 相对地址 由逻辑地址组成的集合称为逻辑地址空间或程序地址空间 3 地址重定位 目标程序只有经过链接 装入内存后才能运行 当程序装入内存的时候 每道程序不可能都从内存空间的 0 地址开始装入 因此程序的逻辑地址与所分到 的内存地址会不一致 为使程序能正确运行 必须将逻辑地址空间中的逻辑地址转换为内存空间中的物理地址 这一过程称为地 址重定位或地址映射 换句话说 地址重定位就是建立用户程序的逻辑地址和物理地址之间的对应关系 按重定位的时机不同 地址重定位又分为静态地址重定位和动态地址重定位 1 静态地址重定位 静态地址重定位是在程序执行之前由操作系统的重定位装入程序完成的 它根据要装入的内存起始地址 直接修改所有涉及到的逻辑地址 一次性完成逻辑地址到物理地址的转换 在程序运行中 不再进行任何地址转换 例如 有一个目标程序 其逻辑地址空间是 0 1 60 把它装入内存的首地址为 100 若采用静态重定位的方式 应根据 物理地址 逻辑地址 100 对程序中所有逻辑地址进行转换 静态地址重定位的优点是只需通过重定位装入程序 即可实现逻辑地址向物理地址的转化 不需要硬件的 支持 可以在任何机器上实现 早期的操作系统大多采用这种方法 缺点是程序必须占据连续的内存空间 且一旦装入内存后 就不能被移动 不利于内存空间的利用 所以静态重定位只适用于静态内存分配方式 动态地址重定位的优点是不要求程序装入连续的内存空间 在内存中允许程序再次移动位置 而且还可以部分地装入程序运行 便于作业共享同一程序的副本 因此现代计算机系统广泛采用动态地址重定位技术 动态地址重定位的缺点是需要硬件的支持 而且实现存储管理的软件算法也比较复杂 存储保护存储保护 界限寄存器保护的技术有界限寄存器保护的技术有 2 2 种 种 上下界存储保护 是一种简单的存储保护技术 系统为每个作业设置一对上 下界寄存器 分别用来存放当前运行作业在内 存空间上的上 下界地址 用它们来限制用户程序的活动范围 在作业运行中 每当要访问内存某单元的时候 就检查经过重定位以后产生的内存地址是否在上 下界寄 存器规定的范围内 若在规定的范围内 访问合法 否则产生越界中断 通知系统进行越界处理 基址 限长存储保护 是上 下界保护的一个变种 系统为每个作业设置一个基址寄存器和一个限长寄存器 基址寄存器存放该作业在内存中的首地址 限长寄存器存放该作业的长度 基址 限长存储保护通常可结合动态地址重定位实现 基址寄存器相当于重定位寄存器 对于存储保护 除了防止越界外 还可对某一区域指定专门的保护机制 常用的保护方式有 禁止做任何操作 只能执行 只能读 能读 写 如对许多用户可共享的程序 一般设为只能执行 而对用户可共享的数据 则设为只能读 一般的用户作业则是可读 写的 虚拟存储器虚拟存储器 虚拟存储管理技术 虚拟存储管理技术的基本思想是把有限的内存空间与大容量的外存统一管理起来 构成一个远大于实际内 存的 虚拟的存储器 此时外存是作为内存的直接延伸 用户并不会感觉到内外存的区别 即把两级存储器当作一级存储器来看 待 一个作业运行时其全部作业装入虚存 实际上可能只有当前运行必须的一部分信息被装入了内存 其它则 存在于外存上 当所访问的信息不在内存中时 系统自动将其从外存调入内存 当然操作系统也可以把暂时不用的信息调致外存 以腾出内存空间供必须之用 这些都由存储管理系统自动实现 不须用户干预 对用户而言 感觉到系统提供了一个大容量的内存 供用户使用 而实际上这样大的内存并不存在 是一种虚拟的存储器 把具有这种功能的存储管理技术叫做虚拟存储管理 请求分页存储管理和请求分段存储管理都是利用虚拟存储管理技术实现内存扩充的实例 为了实现存储管理的诸功能 人们研究总结出多种存储管理方案 根据能否实现虚拟存储 我们把存储方案分为两类 实存管理和虚存管理 实存管理实存管理 实存管理的特点是作业运行时整个作业的逻辑地址空间必须全部装入内存 当作业尺寸大于主存可用空间时 该作业就无法运行 即实存管理无法实现虚拟存储技术 常用的实存管理技术有单一连续分区 固定分区存储管理 可变式分区存储管理和纯分页式存储管理 纯 分段式存储管理 段页式存储管理 单一连续分区单一连续分区 这是最简单的内存分配管理方法 内存只被分为两个区域 一个是操作系统所占据的内存区域 另一个是用户区域 用户程序在运行的时候 必须全部调入内存的用户区 可以看出 这样的内存管理不能支持多道程序并发 因为所有程序只能使用同一个内存区域 CPU 效率太低 内存也没有得到充分利用 固定分区存储管理固定分区存储管理 固定分区是实现多道程序设计的一种最简单的存储管理技术 基本思想是 作业未进入内存之前就由操作员或操作系统 把内存可用空间划分成若干个固定大小 每一 区域大小都固定不变 但各个区域的大小一般不等 的存储区 除操作系统占据一个区域外 其余物理内存区域为系统中多个用户共享 因为在系统运行期间 各个内存 分区的大小 数目都不改变 所以固定分区管理也称为静态分区内存管理 固定分区存储管理固定分区存储管理 假定系统有 256K 内存 系统被划分为 5 个大小不等的的分区 除了操作系统占据低地址部分的 40K 外 假定其它 4 个分区按区域从小到大排列 第 1 个分区 8K 第 2 个分区 32K 第 3 个分区 64K 第 4 个 112K 为了进行分区的分配和回收 在固定分区管理中应该有一个说明表 用来记录各个内存分区的使用情况 固定式分区说明表 固定分区内存的分配与回收固定分区内存的分配与回收 当某个作业要求装入内存运行时 系统首先查询分区说明表 找到一个满足条件的空闲分区 将相应表目的状态位置 1 为什么 然后向用户返回分区号或分区起始地址 完成内存的分配工作 当一个作业完成后 释放其内存分区 系统根据分区号或起始地址找到分区说明表相应表目 将其状态置 0 表示该分区空闲 固定分区存储管理的最大优点是简单 要求的硬件支持少 软件算法简单 缺点是容易产生内部碎片 主存利用率不高 可变式分区存储管理可变式分区存储管理 可变式分区是指在作业 程序 装入时 依据它对内存空间的实际需求来划分主存的分区 因此 每个分 区的大小与进入它的作业 程序 大小相同 它能有效解决固定分区的内碎片问题 是一种较为实用的存 储管理方法 因为在系统运行过程中 内存中分区的大小和数目都是可变的 所以这种可变式分区也称为 动态分区 纯分页存储管理纯分页存储管理 如果把一个作业的所有页面一次全部装入到内存块中 这种分页称为纯分页存储管理 如果作业的所有页面并不是一次性全部装入 而是根据作业运行时的实际要求装入 则把这种分页称为请 求式分页存储管理 存储块的分配与回收存储块的分配与回收 当有作业请求分配内存时 可根据逻辑地址的大小计算出需要多少存储块 然后将空闲块分配给它们使用 通常有两种记录空闲块的方法 位图法和链表法 例 4 有一个页式系统 其页表存放在内存中 1 对内存的一次存取需要 1 5 微妙 问实现一次页面访问 其存取时间是多少 2 若系统中增加了快表 联想寄存器 平均命中率为 85 且当页表项在快表中时 其查找时间忽略 不计 问此时的存取时间是多少 解 1 由于页表放在内存中 若要存取内存中的信息 必须 2 次访问内存 第一次到内存查页表 找到该页对应的内存块号 求出信息在内存的地址 第二次真正到内存里取信息 所以实现一次页面访问的存取时间为 1 5 微秒 2 3 0 微秒 2 增加快表后 在快表中查到的比率为 85 0 1 5 85 1 5 1 5 1 85 1 725 微妙 例 5 在一个分段存储管理系统中 其段表如表 1 所示 求表 2 中逻辑地址对应的物理地址 表 1 段表 表 2 逻辑地址 解答 1 由表 1 知 段号为 0 的段内存起始地址为 210 段长为 500 由表 2 知 逻辑地址的段内位移为 430 因 430 500 所以该逻辑地址是合法的 其对应的物理地址为 210 430 640 2 因 1090 即逻辑地址的段内位移 500 已经超过了段长 90 所以该逻辑地址是非法的 段页式存储管理与动态地址重定位段页式存储管理与动态地址重定位 段页式存储管理是目前使用较多的一种存储管理方式 它主要涉及以下概念 1 作业地址空间进行段式管理 也就是说 将作业地址空间分成若干个逻辑分段 每段都有自己的段 名 或段号 2 每段内再分成若干大小固定的页 每段都从 0 开始 为自己的各页依次编写连续的页号 3 对内存空间的管理仍然和分页存储管理一样 将其分成若干个和页面大小相同的物理块 对内存空间 的分配是以物理块为单位的 4 那么作业的逻辑地址就应该包括三个部分 段号 页号和页内位移 5 为实现地址变换 段页式系统建立了段表和页表 系统为每一个作业建立一张段表 并为每一段建 立一张页表 段表表项中至少包含段号 页表起始地址和页表长度等信息 页表表项中至少包括页号和块 号等信息 段 1 号段对应的页表 假定页尺寸 1024B 再根据地址 1 210 中的段内位移 获得页号和页内地址 210 1024 0 210 所以 在第 0 页开始的第 210 个存储单元 所以内存的物理地址为 22 1024 210 22528 从上述过程可看出 若段表 页表存放在内存中 则为了访问内存中的某一条指令或数据 需要访问内存 三次 第一次 查找段表 获得该段对应页表的起始地址 第二次 查找页表 获得该页所对应的物理块号 形成所需的物理地址 第三次 根据所得的物理地址 到内存中去访问该地址中的指