北方工业大学《操作系统》课程考试计算简答题复习材料.pdf

操作系统课程考试 计算 （简答） 题复习材料 2015-2016 学年版本 （根据宋 丽 华老师讲义整理） 北方工业大学 计算机学院 2015 年 12 月 30 日 北方工业大学 操作系统课程考试计算题复习材料 目 录 一、同步与互斥问题 .1 3.6.4 生产者 消费者问题 .1 二、作业调度 .2 作业调度算法 FCFS（ First come first serve） .2 短作业优先算法 SJF （ shortest job first） .2 最高响应比优先 HRN（ highest response-ratio next） .2 三 地址映射 .3 5.4.1 页式管理的基本原理 .3 四、页面置换 .4 5.4.4 请求页式管理的置换算法 .4 先进先出算法 (FIFO- First Input First Output） , .4 最优淘汰算法（ OPT-Optimal replacement algorithm）： .4 五 死锁避免 .5 银行家算法实例 .5 验证 T0 时刻的安全性 .5 P2 请求资源 1， 0， 1 .6 验证 P2 分配资源后的安全性 .6 P1 请求资源 1， 0， 1 .6 P3 请求资源 0， 0， 1 .6 P3 分配资源后的安全性 .7 P2 请求资源 1， 0， 1 .7 六 磁盘调度算法 .7 5.6.2 磁盘调度 .8 先来先服务 FCFS(First Come First Served) .8 最短寻道时间优先 SSTF(Shortest Seek Time First) .8 扫描 (SCAN)算法 (又称电梯算法 ) .8 循环扫描 (CSCAN)算法（也称单向扫描算法） .9 （适用于：计算机科学与技术专业、信息安全专业、数字媒体专业） 北方工业大学 操作系统课程考试计算题复习材料 1 / 9 一、 同步与互斥问题 分析题意，确定同步、互斥或同步与互斥问题。 设信号量，给出信号量表示的含义（公用，私用）和初始值。 描述算法，注意死锁问题。 3.6.4 生产者 消费者问题 把一个长度为 n 的有界缓冲区 (n 0)与一群生产者进程 P1， P2， ， Pm和一群消费者进 程 C1， C2， ， Ck联系起来 设生产者进程和消费者进程是互相等效的，其中，各生产者进程使用的过程 deposit(data)和各消费者使用的过程 remove(data)可描述如下： 1. 首先生产者 消费者问题是一个同步问题。即生产者和消费者之间满足如下条件： 1)消费者想接收数据时，有界缓冲区中至少有一个单元是满的 2)生产者想发送数据时，有界缓冲区中至少有一个单元是空的 2. 由于有界缓冲区是临界资源，因此，各生产者进程和各消费者进程之间必须互斥执 行。 公用信号量 mutex，保证生产者进程和消费者进程之间的互斥，表示可用有界缓冲 区的个数，初值为 1； 信号量 avail 为生产者进程的私用信号量，表示有界缓冲区中的空单元个数，初值为 n； 信号量 full 为消费者进程的私用信号量，表示有界缓冲区中非空单元个数，初值为 0。 从而有： deposit(data)： begin P(avail) P(mutex) 送数据入缓冲区某单元 V(full) V(mutex) End remove(data)： begin P(full) P(mutex) 取缓冲区中某单元数据 V(avail) V(mutex) end 北方工业大学 操作系统课程考试计算题复习材料 2 / 9 二、 作业调度 画表格计算周转时间和带权周转时间 给出作业（进程）调度序列 计算平均周转时间和平均带权周转时间 作业调度算法 FCFS（ First come first serve） 思想：按作业和就绪进程来到的次序进行调度。这种算法优先考虑在系统中等待 时间最长的作业，而不管它要求运行时间的长短。 优点：算法简单，公平，容易实现 缺点：对于短作业或短进程，等待时间长 下面是 4 个作业在系统中从提交、运行的信息。 平均周转时间： T=1.725 平均带权周转时间 W=6.875 短作业优先算法 SJF （ shortest job first） 思想：比较作业缓冲区中的作业预计的运行时间，选择预计时间最短的作业进入运行 状态。 优点：算法简单，可得到最大系统吞吐率，效率高。 缺点：主要问题是对长作业不利，如果系统不断地接收短作业，就会使长作业长时间 等待。 平均周转时间： T=1.55 平均带权周转时间 W=5.15 最高响应比优先 HRN（ highest response-ratio next） 响应比 =响应时间 /预计执行时间 -响应时间 =等待时间 +预计执行时间 -所以响应比为： 1+作业等待时间 /预计执行时间 思想：当需要从就绪队列中选择进程投入运行时，先计算每个进程的响应比，选 北方工业大学 操作系统课程考试计算题复习材料 3 / 9 择响应比最高的进程运行 优点：短作业响应比高，执行时间短；长作业响应比随着等待时间增加而提高， 不会过长等待。既照顾了短作业、也考虑到了长作业。 缺点：每次调度前计算响应比增加了系统开销。 平均周转时间： T=1.625 W=5.675 三、 地址映射 根据公式计算逻辑地址的页号和页内地址 p=intA/L d=A mod L 根据页表查找页面号。 页面号乘以页长，加上位移量（ d）计算逻辑地址 多次计算直到找到数据、指令为止。 5.4.1 页式管理的基本原理 逻辑空间上的地址为：页号 +页内地址，页内的地址空间是连续的，页之间不必连 续。 如果给定的逻辑地址是 A，页面大小是 L，则 页号 p 和 页内地址 d 可以按以下公式 求得： p=intA/L d=A mod L 例：逻辑地址 100 页面大小 1k 地址变换： 根据逻辑空间的页号，查找页表对应项找到 对应的物理页面号，页面号乘以页 长，加上位移量（页内地址）就是物理地址。每个作业的逻辑地址是连续的，重 定位到内存空间后就不一定连续了。 变换过程全部由硬件地址变换机构自动完成。 北方工业大学 操作系统课程考试计算题复习材料 4 / 9 四、 页面置换 根据引用页面序列画出页面置换图 给出被置换页面序列，调入内存页面序列 计算缺页次数，缺页率，命中率 5.4.4 请求页式管理的置换算法 先进先出算法 (FIFO- First Input First Output） , 先进入内存的页面先淘汰。 优点：实现简单。 缺点：常用的页会被淘汰。 Belady 现象：分配给一个进程的页面增加，反而出现缺页增加的现象 . 最优淘汰算法（ OPT-Optimal replacement algorithm）： 是理想算法。系统预测作业将要访问的页面。淘汰预测不被访问或长时间后才被访问 中的页面。 北方工业大学 操作系统课程考试计算题复习材料 5 / 9 最近 最久未使用页面淘汰法（ LRU - Least Recently Used）： 淘汰最近一段时间最久没访问的页面。 缺点：每页设访问记录，每次更新，系统开销大。 五、 死锁避免 先验证系统初始状态的安全性，找出安全序列。 根据申请资源情况，结合剩余资源检 查申请合理性。 验证分配后系统安全性，给出安全序列，否则不能分配资源给相应进程。 银行家算法实例 假定系统有四个进程 P1,P2,P3,P4,三种类型的资源 R1,R2,R3,数量分别为 9， 3， 6，在 T0 时刻的资源分配情况如下： 验证 T0 时刻的安全性 分析： 1. 四进程执行状态都是未完成， Finish=false 2. 找 Pi，其需要的资源 need<=有效资源 work 3. 当前的 work=1/1/2， need P1 P2 P3 P4 (2/2/2), (1/0/2), (1/0/3), (4/2/0) 4. 找到 P2 满足条件，如果让 P2 运行结束 存在运行序列： P2,P1,P3,P4 北方工业大学 操作系统课程考试计算题复习材料 6 / 9 P2 请求资源 1， 0， 1 现在 P2 请求资源 1/0/1，按照银行家算法检查： Request21/0/1<=Need21/0/2 Request21/0/1<=Available21/1/2 假定可以分配，修改 Available, Allocation, Need 进行安全性检查 验证 P2 分配资源后的安全性 存在运行序列： P2,P1,P3,P4 P1 请求资源 1， 0， 1 P1 请求资源 1/0/1，按照银行家算法检查： Request11/0/1 Available10/1/1 条件不满足，不能分配，让 P1 等待。 P3 请求资源 0， 0， 1 现在 P3 请求资源 0/0/1，按照银行家算法检查： Request30/0/1<=Need31/0/3 Request30/0/1<=Available30/1/1 假定可以分配，修改 Available, Allocation, Need 北方工业大学 操作系统课程考试计算题复习材料 7 / 9 进行安全性检查 P3 分配资源后的安全性 分析：四进程执行状态都是未完成， Finish=false 找 Pi，其需要的资源 need<=当前的 work=0/1/0 进程的 need P1 P2 P3 P4 (2/2/2), (0/0/1), (1/0/2), (4/2/0) 找不到满足条件的 Pi,因此资源 P3 不能分配本次资源，回退。 P2 请求资源 1， 0， 1 现在 P2 请求资源 1/0/1，按照银行家算法检查： Request21/0/1<=Need21/0/2 Request21/0/1<=Available21/1/2 假定可以分配，修改 Available, Allocation, Need 六、 磁盘调度算法 看清调度算法 给出寻道次序 计算移动 磁道数，平均寻道长度。 北方工业大学 操作系统课程考试计算题复习材料 8 / 9 5.6.2 磁盘调度 先来先服务 FCFS(First Come First Served) 假定磁盘共有 40 个柱面，当前磁头正在第 11 道服务，等待服务的进程有 6 个，它们 请求的磁道号分别是： 1， 36， 16， 34， 9 和 12 (以请求时间先后为序 )。 移动为： 11 1 36 16 34 9 12 总移动磁道数 :10+35+20+18+25+3 = 111 最短寻道时间优先 SSTF(Shortest Seek Time First) 假定磁盘共有 40 个柱面，当前磁头正在第 11 道服务，等待服务的进程有 6 个，它们 请求的柱面分别是： 1， 36， 16， 34， 9 和 12 (以请求时间先后为序 )。 移动为： 11 12 9 16 1 34 36 总移动磁道数： 1+3+7+15+33+2 = 61 由此可知总的磁道移动数为 61，而 FCFS 为 111 扫描 (SCAN)算法 (又称电梯算法 ) 具体做法：当有访问请求时，磁头按一个方向移动，在移动过程中对遇到的访问请求 进行服务，然后判断该方向上是否还有访问请求，如果有则继续扫描；否则改变移动方 向，如此反复 北方工业大学 操作系统课程考试计算题复习材料 9 / 9 假定磁盘共有 40 个柱面，当前磁头正在第 11 道自里向外服务，等待服务的进程有 6 个，它们请求的柱面分别是： 1， 36， 16， 34， 9 和 12 (以请求时间先后为序 )。 移动为： 11 12 16 34 36 9 1 总移动磁道数： 1+4+18+2+27+8 = 60 循环扫描 (CSCAN)算法 （ 也称单向扫描算法 ） 总是从外面柱面开始向里扫描。移动臂到达最后个一个请求磁道柱面后，立即带动读 写磁头快速返回。返回时不为任何的等待访问者服务。返回后可再次进行扫描。 假定磁盘共有 40 个柱面，当前磁头正在第 11 道自里向外服务，等待服务的进程有 6 个，它们请求的柱面分别是： 1， 36， 16， 34， 9 和 12 (以请求时间先后为序 )。 移动为： 11 12 16 34 36 1 9 总移动磁道数： 1+4+18+2+35+8 = 68