操作系统复习

1、操作系统复习 1、 P25 复习题 1.11.81 计算机的 4 个主要组成部分 处理器 控制计算机的操作，执行数据处理功能 内存 存储数据和程序 输入 / 输出模块 在计算机和外部环境之间移动数据 系统总线 为处理器、内存和输入 / 输出模块提供通信的设施2 处理器寄存器的两张主要类别 用户可见寄存器 可以由机器语言应用，一般对所有程序都可用 控制和状态寄存器 用于控制处理器操作的寄存器，大部分此类寄存器对用户不可见 一条机器指令能够指定的四种不同操作 处理器 - 存储器 处理器 -I/O 数据处理 控制 中断的定义 处理器接收到内部或外部的信号之后，放下手头正在做的工作，处理一些其他工作，

2、之后再回来继续做之前的工作的行为。 多中断的处理方式是 第一种方式是当正在处理一个中断时，禁止再发生中断 第二种方法是定义中断优先级，允许高优先级中断打断低优先级中断处理程序的运行内存层次的各个元素间的特征是神马 定义寄存器 - 高速缓存 - 主存 - 外存的级别由高到低，则从上往下 每一位价格递减、容量递增、存取时间递增、处理器访问存储器的频率递减神马是高速缓存 为了解决处理器和内存之间速度不匹配，利用局部性原理，在处理器和内存之间提供一个容量小而速度快的存储器，称作高速缓存。 I/0 操作的三种技术 可编程 I/O 当处理器执行程序并遇到一个与 I/0 相关指令时，它通过给相应的 I/0

3、模块发命令来执行这个指令。可编程 I/0 要求处理器在执行 I/0 指令后，还要定期检查 I/O 模块的状态，以确定 I/O 操作是否完成。 中断驱动 I/O 处理器给模块发 I/O 命令，然后继续做一些其他有用的工作，当 I/O 模块准备好与处理器交换数据时，它打断处理器的执行并请求服务。处理器和前面一些执行数据传送，再恢复正常的执行。 DMA 直接内存存取 当处理器要读写一块数据时，它给 DMA 模块产生一条命令，之后处理器继续其他工作。 DMA 负责存储器与 I/0 之间数据传送。直到整个传送完成后， DMA 再发一个中断信号给处理器，表明传送已完成。2、 操作系统概述1 实地址和虚地址

4、的区别虚地址就是虚拟存储器中的地址，而虚拟存储器是允许程序从逻辑的角度访问存储器，而不考虑物理内存上可用的空间数量。实地址就是实际的内存中的地址。使用中，虚地址和实地址之间存在着动态的映射，当虚地址中内容在实际内存中不存在时，由存储管理硬件载入这块内容到内存。2 单体内核和微内核的区别单体内核指操作系统应提供的功能由一个大内核提供（这些功能包括调度、文件系统、网络、设备驱动器、存储管理），典型情况下，这个大内核作为一个进程实现，所有元素共享相同的地址空间。微内核体系下则只给内核分配一些最基本的功能（包括地址空间、进程间通信、基本的调度），其他操作系统的服务都是由运行在用户态下与其他应用程序类似

5、的进程提供。3 执行上下文又称进程状态，是操作系统用来管理和控制进程所需的内部数据，包括了操作系统管理进程以及处理器正确执行进程所需要的全部信息。 4 时间片轮转在固定时间间隔内，当前用户被剥夺处理器的使用权，另一用户被载入。5 特权指令只能在内核态下由操作系统执行的指令，用户程序希望执行特权指令时应请求操作系统为自己执行。3 、进程描述和控制 五状态进程图形 P79 五种状态 新建 就绪 运行 阻塞 退出 六种转换 新建 就绪 操作系统准备好接纳一个进程时 就绪 运行 调度器选择一个处于就绪态的进程运行 运行 退出 进程完成 取消 运行 就绪 到“允许不中断的最大时间段” / 被其他进程抢占

6、 / 自愿释放 运行 阻塞 进程请求一个它必须等待的事件 阻塞 就绪 进程等待的事件发生 有挂起的进程状态转换图 七种状态 新建 就绪 运行 阻塞 就绪 / 挂起 阻塞 / 挂起 退出 十三种转换 新建 就绪 允许进入：同上 新建 就绪 / 挂起 允许进入：内存不足 就绪 / 挂起 就绪 激活：内存中没有处于就绪态的进程 / 就绪 / 挂起态的进程比所有就绪态进程优先级都高 就绪 就绪 / 挂起 挂起：为了释放内存 / 处于阻塞态的高优先级进程即将就绪 就绪 运行 分派：同上 运行 退出 释放：同上 运行 就绪 超时（不是很准确）：同上 运行 阻塞 事件等待：同上 阻塞 就绪 事件发生：同上

7、阻塞 阻塞 / 挂起 挂起 内存中没有就绪进程，换出以让出空间 阻塞 / 挂起 阻塞 激活：最高优先级即将就绪进程被优先激活 阻塞 / 挂起 就绪 / 挂起 事件发生：同上 运行 就绪 / 挂起 挂起：挂起队列中高优先级就绪，直接换入抢占 哪些事件会导致创建一个进程 a) 新的批处理作业 b) 交互登陆 c) 操作系统因为提供一项服务而创建 d) 由现有进程派生 什么是交换，其目的是 交换：当内存中没有处于就绪态的进程时，操作系统就把被阻塞的进程换出到磁盘中的挂起队列，此后，操作系统取出挂起队列中的另一个进程，或者接受一个新进程的请求，将其纳入到内存中运行。 为了应对内存中所有进程都在阻塞的情

8、况（考虑 I/O 速度比处理器慢很多），在这种情况下提升处理器运行效率。 操作系统创建一个新进程的步骤 a) 给新进程分配一个唯一的进程标识符 b) 给进程分配空间 c) 初始化 PCB d) 设置正确的连接 e) 创建或扩充其他数据解雇 进程切换的步骤 a) 保存处理器上下文环境 b) 更新 PCB c) 将 PCB 移至相应的队列 d) 选择一个进程执行 e) 更新所选进程的 PCB f) 更新内存管理的数据结构、 g) 恢复所选进程最近一次被切出时的上下文环境 习题 3.2 灰常有歧义的一道题目 能确认的就是 运行态最大值是 B ，就绪挂起、阻塞挂起的最大值都没有限制 各个状态的最小值都

9、为 0 有歧义的是内存中的两个状态 就绪态和阻塞态 个人倾向于理解为题目中没有涉及虚拟内存（毕竟它根本没提到操作系统），而我们要考虑虚拟内存，这样答案就是没有限制 ( 这个和 ” 官方答案“一致，强调虚拟内存意义，即使一个进程整个内存都放不下，它也可以就绪的，即 C 无约束作用 ) 不过说到底，“在任何时候内存最多容纳 C 个进程”这句话就很有歧义，进程又不是一样大的。 4 、线程、对称多处理和微内核 两种线程 用户级线程 ULT 所有有关线程的管理工作都是由应用程序实现，内核意识不到线程的存在 内核级线程 KLT 有关线程的管理工作都是由内核实现，应用程序中没有管理线程的代码，只有一个到内核

10、线程设施的 API 列举使用线程相对于使用进程的好处 i) 时间花费少，具体包括创建新线程、线程切换、终止线程都少。 Ii) 通信便利高效，进程间通信需要内核介入，而一个进程内的线程共享内存和文件，直接可以通信 列举微内核操作系统和单体内核操作系统 7 个优点和可能存在的缺点 优点： i) 一致接口 ii) 可扩展性 iii) 灵活性 iv) 可移植性 v) 可靠性 vi) 分布式系统支持 vii) 适用于面向对象操作系统环境 可能存在的缺点： 性能问题 通过微内核构造和发送消息，接受应答并解码所花费的时间比进行一次系统调用的时间要多。5 、并发性：互斥和同步 名词解释 临界区 要被多个进程访

11、问的一个不可共享资源称为临界资源，使用临界资源的那一部分程序称为程序的临界区。 死锁 一组进程，当其中每一进程都因等待某一事件而被阻塞，而这事件仅可能由其他进程促发，则发生死锁。 互斥 一次只允许一个程序在临界区中，即一个进程在使用不可共享资源过程中一直拥有资源的控制权。 竞争条件 竞争条件发生在多个进程或线程读写数据时，其最终结果依赖于多个进程的指令执行顺序。2 生产者、消费者问题 图 5.11基本：有一个活多个生产者生产某种类型的数据，并放置在缓冲区中，有一个消费者从缓冲区中取数据，每次取一项。要避免对缓冲区的重复操作，并保证缓冲区已满时，生产者不向中加入数据（这个 MS 暂时不考虑， 5

12、.11 么）；缓冲区为空时，消费者不会移走数据。个人思考：i) 为什么要使用两个信号量，主要是要完成两个功能，即不重复操作 信号量 s 是做一个临界区保护；缓冲区为空时，消费者不移走数据 信号量 delay + 计数量 n 实现。（这必须要用两个信号量才够！）ii) Delay + n 的实现方法之所以错了， 就是由于这两个之间存在“间隙”， n 存在的目的是作为不能多次计数的二元信号量 delay 的补充，而它的变化与 delay 变化的不同步导致了错误。（生产者程序插在了消费者 n 和 if(n = 0) semWaitB(delay) 之间）iii) 5.11 中用一般信号量 n 取代了

13、 delay + n 的组合，自然消除了这个问题iv) 在 P153 中也提到了， wait 的顺序很重要。鉴于顺序的随机性，其实直接看 wait signal 的位置关系既可以发现会不会有死锁3 读者写者问题 图 5.22 5.23 基本：有一个多个进程共享的数据区，这个数据区可以是一个文件或一块内存，甚至是一组寄存器，有一些进程只读取这个数据区中的数据，有一些只写。条件如下： i) 任意多进程可以同时读 ii) 一次只有一个可以写 iii) 写时禁止读个人思考：i) 对于读者优先，比较简单 , wsem 用于所有进程之间互斥， readcount 则避免读进程之间互斥， x 用于对 rea

14、dcount 相关操作进行临界区保护。ii) 写者优先比较实际一点，但复杂度。其实也不是很复杂x 、 readcount 、 wsem 用途不变y 用于保护 writecount, writecount 用于在有写进程等待（至少一个即可 ）的情况下禁止读z 则保证 rsem 上永远只有一个读进程在等待这么看真的不复杂，但这些信号量放置的位置 (wait signal) 要很小心4 习题 5.4 不管这是神马语言了，直接 C 语言写了 ( 这里认为通用的信号量 = 二元信号量 )信号量声明Semaphore sa = 1, sb = 0 ， b_end_flg = 0;A 部分：semWait(

15、sa);if (b_end_flg = 0) semSignal(sb); Else semSignal(sa); B 部分：semWait(sb);b_end_flg = 1;semSignal(sa);. MS 所有 pv 就是 .p(sa) .v(sa) 这样进行上锁和解锁。6 、死锁和饥饿 死锁发生的 4 个条件 :互斥 一个资源一次只能被一个进程使用持有并等待 一个进程持有已分配资源的同时，等待分配其他资源不可剥夺 资源在被进程持有时不可被强制剥夺循环等待 存在一个进程链，使得每一个进程至少占有一个此链中下一个进程所等待的资源如何预防占有并等待条件 进程一次性请求所有需要资源，并阻塞

16、直至所有请求都被满足。如何防止不可抢占 当进程的资源请求被拒绝时，它必须释放它最初占有的资源，如有必要，可再次一次请求这些资源；一个进程请求当前被另一进程占有的一个资源，操作系统可以抢占另一进程，要求它释放资源（要求任意两进程优先级不同）。如何防止循环等待 定义资源类型的线性顺序，如果一个进程已分配到 R 类型资源，则它后面请求的资源只能是 R 类型之后的。2 习题 6.5 画资源分配图 a) 暂时理解为随便算b) 资源分配图是对多线程中运行的一个时间点状态的描述，所以要说明死锁的可能性只需要构造一个这样的时间点并画图（内含闭环）即可。针对本题，其实只要画 T1 、 T2 、 T3时间点为 T

17、1 拥有 s1 请求 s2 T2 拥有 s2 、 s4( 可不画 ) 请求 s5 T3 拥有 s5 、 s6( 可不画 ) 请求 s1 习题 6.6 死锁检测就是 189 页的算法1） 标记 Aij 中全零行 这样的进程不可能导致死锁，直接标记2） 初始化 A 的计数变量 W3） 后面类似银行家算法，就是找一个 Ri 小于 W 的，走掉（标记），释放资源（将 Ai 加到 W 中去），回头继续找满足条件 Ri最后没有满足条件 Ri 了，就看是不是所有进程都标记了，都标记了，就没有问题；所有没标记的都是要死锁的。习题 6.11 银行家算法总需求量 Cij 一定，总可用量 R 一定，银行家算法的目的

18、在于规范过程中每次申请资源请求（申请资源后会导致 Aij ，即剩余请求量 Rij = Cij - Aij 和剩余资源量 A ，如存在这个 A 可以完全消化 Rij, 则为安全状态，否则，不安全 这次的自愿申请无效）a) 基本的 b ） c) d) ( a) 中先算出 A 和 Rij 可以减少一点计算量 ) 注意题目中给出的是 R B 可以 c 不行 d 显然不行 7 、内存管理1 重定位，为什么要重定位进程的能力 程序被传出到磁盘之后，重新载入内存时可以放置在与之前不同的一个位置。（也可以说还包括压缩） 为什么 交换的需求实际存在，而如果要求进程换入时放置的位置必须和换出前一致，会对内存的使用

19、造成很大的限制。2 内部碎片和外部碎片由于被装入的数据块小于分区的大小，导致分区内部存在空间的浪费，这种现象称为内部碎片。动态分区随着时间推移，导致内存中出现越来越多的空洞，内存利用率随之下降，这种现象称为外部碎片。3 逻辑地址、相对地址、物理地址 逻辑地址 与当前数据在内存中物理分配地址无关的访问地址，在执行内存访问前必须将它转换成物理地址。 相对地址 逻辑地址的一个特例，是相对于某些已知点的存储单元。 物理地址（绝对地址） 数据在内存中的实际位置4 页、段、帧（页框） 帧（页框） 内存中一个固定长度的块 页 一个固定长度的数据块，储存在二级存储器中。数据页可以临时复制入内存的页框中 段 一

20、个变长的数据块，储存在二级存储器中。整个段可以临时复制到内存的一个可用区域内（分段）或者将一个段分为许多页，将每页单独复制到内存中（分页 + 分段）5 习题 7.2 固定分区方案 最佳适应分配 最佳可得分配 （照着它说的做就行了）a) 最佳适应分配1-p0 10ms 3-p0 20ms 5-p0 15ms2-p1 5ms4-p3 15ms 6-p3 10ms 显见需要 10+20+15 = 45ms 完成 b) 最佳可得分配1-p0 10ms 2-p1 5ms 5-p1 15ms 3-p2 20ms 4-p3 15ms 6-p3 10ms 总共需要 15+10 = 25ms 习题 7.6 动态

21、分区方案 首次适配 最佳适配 下次适配（ P215 动态分区的放置算法，很简单） a) 首次适配80MB 20MB 120MBb) 最佳适配230MB 20MB 160MBc) 下次适配80MB 120MB 160MB习题 7.7 伙伴系统 （ P217 的实例很容易理解） 1MBA 请求 25K A=32K 32K 64K 128K 256K 512KB 请求 500K A=32K 32K 64K 128K 256K B=512KC 请求 60K A=32K 32K C=64K 128K 256K B=512KD 请求 100K A=32K 32K C=64K D=128K 256K B=5

22、12KE 请求 30K A=32K E=32K C= 64K D=128K 256K B= 512K 释放 A 32K E=32K C=64K D= 128K 256K B= 512KF 申请 20K F=32K E=32K C= 64K D= 128K 256K B=512K 5 个内部碎片，分别 F 12K E 2K C 4K D 28K B 12K 习题 7.12 3 级页表 （ P219P221 关于分页 页号 偏移量 页框号）a) 页大小 212 = 4KBb)2(32-12) = 1MBc)232 = 4GBd) 这个同意 syz 观点，“ 6 位表示页号”应该是页框号，否则物理内

23、存大小不可知2(6+12) = 256KB习题 7.14 (P222 分段 和分页不同只是进程维护的映射信息不一样，分页 - 页框号 分段 - 段长 + 段起始物理地址）a) 660 + 198b) 222 + 156c) 530 > 442 段错误d) 996+444e) 660 + 222 8、 虚拟内存1 驻留集 进程执行中的任何时候都在内存中的部分定义为进程的驻留集2 抖动处理器的大部分时间都用于交换块，而不是执行指令的情况3 转换检测缓冲区（ TLB ） 虚拟内存的方案中为页表项使用的一个特殊的高速缓存。4 习题 8.2 多级页表设计（ P236 的实例） 这里的页表项不用考虑

24、神马控制位之类的 页表项 32 位 偏移量为 10 （页大小 1KB ），则页表项总数为 222 需要限制页表大小为 1 个页，即 210 ，而页表项为 22(32 字节 ) ，所以页表中页表项的数目限制为 28 总页表项数位 222 ，所以需要三级页表， 8 ， 8, 6 按照第三问，要使总的页数最小的话，数据页数固定，即使页表数目最少，这时候显然将大页放下，小页放上效果最好。（数学说明的话，就假设数据 X 页，三级页表从上往下一次 x,y,z, 则有总页表数目 X/2 z + X/2 z +y +X/2 z+y+x , 要使这个求和结果最小（在 x+y+z 结果一定情况下），显然要保证 z

25、 >= y >= x ）所以应该 6,8,8 习题 8.4 置换算法 FIFO LRU 时钟算法 （ P246249 的基本算法，也不复杂，注意时钟算法要求了解到用两位 访问位、修改位的实现） a) 置换页框 3 3 加载时间最早，根据 FIFO ，优先被换出 b) 置换页框 1 1 访问时间最早，即上一次访问距现在时间最长，根据 LRU ，换出 c) 对于时钟算法的个人理解就是 FIFO （用循环指针扫描、置 0 访问位，仍然有优先换出早加载的页的倾向） + 弱 LRU （只具备短期的记忆） 简单模拟是时钟算法过程的话可以用书上得 * 符号表示访问位 如果在访问位的基础上引入了修

26、改位，则基本思想是最优先换出没有被修改的（节省写回的成本）不过这个的细节需要了解一下（第一遍循环不置 0 访问位，第二遍才置 0 ，第三遍指针重置，全部置 0 ） 置换页框 1 R= 0 M = 0 最优先 d) 置换页框 3 即换出页 3 ，因为在 03 四个页中，从下面访问串看，页 3 最后被再次访问到e) MS 算不要求？关于这部分要涉及工作集，稍微有点难理解，题目本身也有点问题，毕竟工作集主要用作评估，而不是直接替换 ( 那样的话就是 FIFO 了 )习题 8.6 FIFO LRU OPT 计算缺页次数（同上）1) 页面大小为 100 字节，则总共有 04 五个页引用串 0 0 1 1

27、 0 3 1 2 2 4 4 32) 200 字节，即两个页框 0 1 仿照书上写法来LRU 0 0 01 01 01 F03 F13 F12 12 F42 42 F43 共 5 次缺页FIFO 0 0 01 01 01 F31 31 F32 32 F42 42 F43 共 4 次缺页OPT 0 0 01 01 01 F31 31 F32 32 F34 34 34 共 3 次缺页习题 8.8 64 位系统，一级页表需要多少地址a) 264 b) 252c) 页表变得非常大（页表项非常多），使用一级页表成本很高（不可能在内存中维护这么大的表）。解决：多级页表。9 、单处理器调度 周转时间 指一个

28、进程从提交到完成之间的时间间隔，包括实际执行时间加上等待资源（包括处理器资源）的时间。2 各种调度策略基本： 吞吐量 每个时间单位完成的进程数目 响应时间 对于交互进程，从提交一个请求到开始接受响应之间的事件间隔w 进程到目前为止在系统中停留的时间 E 进程自创建已经执行的时间 s 进程所需要的总的服务时间（必须估计或用户给出）选择函数，如 max(w)决策模式 抢占 / 非抢占下面就是各种调度策略：（关于其中不强调是神马意思不明，是不是很确定？不以这个为卖点 / 缺陷？） P277 表格FCFS frist-come-first-served 先来先得 / 严格排队Max(w) 非抢占 不强

29、调吞吐量 响应可能很慢，毕竟排队 开销最小 对短进程不利，对 I/0 密集进程不利RR round robin 轮转常数（到一定时间即可） 抢占（时间片完时） 时间片小，吞吐量低（切换开销大） 短进程响应快 开销最小 对各进程公平（不过公平而非照顾就会产生问题） 个人理解：就是有时限的排队，当时限非常大时直接退化为排队SPN shortest process next 最短进程优先Min(s) 非抢占 吞吐量高 短进程响应快 开销可能比较高（要得到 s ） 对长进程不利，甚至可能导致长进程饥饿个人理解：允许短进程插队的排队SRT shortest remaining time 最短剩余时间Mi

30、n(s e) 抢占 吞吐量高时间响应快 开销可能比较高（同样要 s ） 对长进程不利，可能饥饿个人理解：允许剩余时间最短的进程直接踢开队首的人，很凶残HRRN highest response rate nextmax(w+s)/s) 非抢占 吞吐量高 时间响应好 开销可能比较高（理由同上） 很好平衡（等的多了，机会也大了）个人理解：同样大家一起等（不算排队了），不过用了一个科学的指标衡量等的时间的长短，以此决定谁先反馈 可以说没有选择函数吧 抢占（结合了时间片） 不强调吞吐量不强调响应时间 开销可能比较高（要维护一串队列） 可能对 I/0 密集型进程有利（因为反馈是歧视老进程和长进程的 ,I

31、/0 多就一直是“新”进程） 可能会导致长进程的饥饿，这个有一个解决方法就是增大下层队列的时间片的长度，时间片长 = 2I i = 队列号3 习题 9.1 9.2 给定进程的到达时间、处理时间表格，画出调度图（看来考试那天要带尺 = = ， P279 ） ( 表格 MS 没要求，不过看一下也很简单，进程、到达时间、服务时间 Ts ， 针对每一种调度策略：完成时间，周转时间 Tr ， Tr/Ts) 对于 9.1FCFS A3 B5 C2 D5 E5RR(q = 1) 有一个问题，就是在一个时间点一个进程超时回到队列尾，同时一个新进程加入队列尾，这两者之间前后关系该怎么定 从书上看应该是新的在前，

32、超时的在后 A1 B1 A1 B1 C1 A1 B1 C1 B1 D1 B1 D1 .RR(q =4) 类似上面SPN A3 C2 B5 D5 E 5SRT A3 C2 B5 D5 E5HRRN A3 B5 C2 D5 E5反馈 (q = 1) 也有一些问题，从例子 p279 看：降级只发生在被“别的进程”抢占时，时间片到了然后还是自己执行不算 ( 更完整说的话， 同级或下级 队列中有进程时 ，尽管没有进程来抢占当前进程， 都需要降级 ) 认为级数无限制这个画几张状态图会很清楚A1 B1 A1 C1 B1 A1 C1 B2 D2 B1 E2 D1 E1 D1 E1 D1 E1根据标准答案（第五

33、版），这道题目上面这样是不对的，所以，目前认为反馈的基本原则如下： 新来的永远最优先 所有进程在同一级队列时不降级，其余降级A1 B1 A1 C1 B1 A1 C1 B2 D1 B1 D1 E1 D1 E1 D1 E1 D1 E2反馈（ q=2i ）类似上面10 、多处理器和实时调度 习题 10.1 具有完成 deadline 的周期任务，画出 固定优先级调度图 最早最后期限调度图 （ P317 例子，一章只看两页，清楚明了 = = ） 个人觉得调度就是要用合理的执行顺序安排达到并行的效果。 这道题目并不复杂，注意这个和例题的第一个是对应的 周期性任务、完成最后期限， 比较的是固定优先级 和 最早最后期限 固定优先级：有 6 种方法，保证第一次 A 不丢，只有 ABC ACB BAC ABC C 丢 ACB B 丢 BAC C 丢 所以都是不行的（其实从 10 * 50/20 + 10 +15 = 50 满满的可以大致猜出是不行的），这样的话应该画一个图意思一下就行 最早最后期限 在这里要设定一下，最后期限相同时，进程的执行顺序是 ABC A1 10 B1 10 A2 10 C1 15 A3 10 B2 5 A4 10 B2 5 C2 5 A5 10 C5 10 100 个时间单位可以认为是一个周期，用最早最后期限调度可以完成三个周期任务的调度。 习题