作业J1进入内存时间为10：00； 作业名 提交时刻 运行时间SJF 作业J2进入内存时间为12：30； （小时） IN OUT 作业J3进入内存时间为13：30； J1 10：00 2 10：00 12：00 作业J4进入内存时间为12：00； J2 10：30 1 12：30 13：30
J3 10：50 13：30 15：00 平均周转时间为：(2+3++/4= J4 11：20 12：00 12：30
2．一个请求分页系统中，若系统分配给一个作业的物理块数为2块，且作业的页面走向为2，3，2，1，5，2，4，5，3，2，5，2。试用FIFO和LRU两种算法分别计算出程序访问过程中所发生的缺页次数，并计算它们各自的缺页率。（假设初始作业装入时已经依次装入了页号为1和2的两个页面） (1) FIFO：（5分） 1 2 2 2 1 3 3 2 × 2 3 2 1 1 3 × 5 5 1 × 2 2 5 × 4 4 2 × 5 5 4 × 3 3 5 × 2 2 3 × 5 5 2 × 2 5 2 F=9/12=75% (2) LRU：（5分） 1 2 2 2 1 3 3 2 × 2 2 3 1 1 2 × 5 5 1 × 2 2 5 × 4 4 2 × 5 5 4 × 3 3 5 × 2 2 3 × 5 5 2 × 2 2 5 F=9/12=75%
3．假定某移动磁盘上，处理了访问56号柱面的请求后，现在正在70号柱面上读信息，目前有下面的请求访问磁盘柱面的序列：73,68,100,120,60,108,8，50。请写出： （1）用最短查找时间优先算法，列出响应的次序。 （2）用电梯调度算法，列出响应的次序。 (1)
用最短查找时间优先算法，响应的次序为68、73、60、50、8、100、108、120。 （2）
用电梯调度算法，响应的次序为73、100、108、120、68、60、50、8。
得 分 评分人 一、
1、设系统中有五个并发进程（P1，P2，P3，P4，P5）共享系统中的三类资源（R1，R2，R3），它们的资源总数量分别为（16，5，19），在T0时刻系统状态如下图所示，系统采用银行家算法实施死锁避免策略。
进程 P1 P2 P3 P4 P5 最大资源需求量 R1 5 5 4 4 3 R2 5 3 0 2 2 R3 9 6 11 5 4 已分配资源数量 R1 2 4 4 2 3 R2 1 0 0 0 1 R3 2 2 5 4 4 综合分析题（每题10分，共20分）
问题1：判断在T0时刻是否处于安全状态，为什么
A＝(1,3,2)；N5=(0,1,0) N4=(2,2,1) 问题2：在T0时刻若进程P2提出（1，0，1）的资源请求，是否实施分配为什么 A＝(1,3,2)；R2=(1,0,1) N4=(2,2,1) 2、有一只最多能装2只兔子的铁笼子，猎人仅能向笼子中放入兔子（每次只能放入1只），若笼子是满的，则猎人必须等待；饭店老板仅能从笼子中取兔子（每次只能取出1只），若笼子是空的则他也必须等待。假设初始时笼子是空的。定义信号量并初始化，使用P、V操作模拟猎人和饭店老板进程之间的同步与互斥。 mutex,empty,fullsemaphore; 1分 mutex=1,empty=2;full=0; 2分 以下内容7分 cobegin pcocedure Hunter(x) begin： P（empty）； P（mutex）； 1. 1:1000＋6*3 1:1000＋6*3 2. 4:1000 +6*3 4:1000＋6*3 3. 5:1000 +6*3 5:1000＋6*3 4. 1:10+1 1:10＋1 5. 7:1000 +6*3 7:1000＋6*3 6. 6: 1000+6*3 6: 1000＋6*3 7. 4:1000+ 6*3 4: 1000＋6*3 8. 1:1000+ 6*3 1: 1000＋6*3 7次缺页中断 7次缺页中断 OPT 1. 1:1000＋6*3 2. 4:1000 +6*3 3. 5:1000 +6*3 4. 1:10+1 5. 7:1000 +6*3 6. 6:1000 + 6*3 7. 4:10+1 8. 1:10+1 5次缺页中断 3、在请求调页的动态分页系统中，一个程序的页面访问次序为：2，4，8，3，2，4，5， 2，4，8，3，5。如果分配给此程序的页帧数为4，分别分析采用FIFO、LRU和OPT算法时的置换过程并计算页面缺页次数。（9分） 解：请在单元格填写正确的页面号，并在发生缺页的列打勾 √（每个算法3分） 访问次序 2 2 FIFO 页面缺页（10）次 访问次序 2 2 LRU 页面缺页（8）次 4 4 2 √ 4 4 2 √ 8 8 4 2 √ 8 8 4 2 √ 3 3 8 4 2 √ 3 3 8 4 2 √ 2 3 8 4 2 2 2 3 8 4 4 3 8 4 2 4 4 2 3 8 5 5 3 8 4 √ 5 5 4 2 3 √ 2 2 5 3 8 √ 2 2 5 4 3 4 4 2 5 3 √ 4 4 2 5 3 8 8 4 2 5 √ 8 8 4 2 5 √ 3 3 8 4 2 √ 3 3 8 4 2 √ 5 5 3 8 4 √ 5 5 3 8 4 √ √ √ 访问次序 2 2 √ 4 4 2 √ 8 8 4 2 √ 3 3 8 4 2 √ 2 3 8 4 2 4 3 8 4 2 5 5 8 4 2 √ 2 5 8 4 2 4 5 8 4 2 8 5 8 4 2 3 3 5 4 2 √ 5 3 5 4 2 OPT 页面缺页（6）次 4、有哪几种I/O控制方式各适用于何种场合（8分） 答：1、程序I/O方式，适用于低速字节设备；2、中断方式，适用于中低速字节设备；3、DMA方式，适用于中高速块设备；4、通道方式，适用于各种类型的设备，尤其是高速块设备 5、系统中有一组如右表所示的磁盘I/O请求等待服务，假设当前磁道为88，刚完成对100道的操作，分别计算先来先服务、最短寻找时间优先、电梯调度方法下的磁头移动的总道数。（9分） 被访问的磁道 ======= 90 189 130 16 45 解：先来先服务调度：2＋99＋59＋114＋29＝303（3分） 最短寻找时间优先调度：2＋40＋59＋144＋29＝274（3分） 电梯调度：43＋29＋74＋40＋59＝245（3分） 1、某虚拟存储器的用户编程空间共32个页面，每页为1KB，内存为16KB。假定某时刻一用户页表中已调入内存的页面的页号和物理块号的对照表如下： 页号 0 1 2 3 物理块号 5 10 4 7 则逻辑地址0A5D（H）所对应的物理地址是什么（6分） 0A5D（H）=0000 1010 0101 1101 2号页对应4号块，所以物理地址是0001 0010 0101 1101 即125D（H）。 2、设有三道作业，它们的提交时间及执行时间由下表给出: 作业号 提交时间 执行时间 1 2 3 试计算在单道程序环境下，采用先来先服务调度算法和最短作业优先调度算法时的平均周转时间 (时间单位:小时，以十进制进行计算；要求写出计算过程)（10分） FCFS: 作业号 提交时间 执行时间 开始时间 完成时间 周转时间 1 2 3 平均周转时间=++/3=(小时) SJF: 作业号 提交时间 执行时间 开始时间 完成时间 周转时间 1 2 3 平均周转时间=++/3=(小时) 3、假定当前磁头位于100号磁道，进程对磁道的请求序列依次为55，58，39，18，90，160，150，38，180。当采用先来先服务和最短寻道时间优先算法时，总的移动的磁道数分别是多少（请给出寻道次序和每步移动磁道数）（8分） FCFS: 服务序列依次为:55，58，39，18，90，160，150，38，180 移动的磁道数分别是: 45, 3, 19, 21, 72, 70, 10, 112,142 总的移动的磁道数是:494 SSTF: 服务序列依次为:90，58，55，39，38，18，150，160，180 移动的磁道数分别是: 10, 32, 3, 16, 1, 20, 132, 10, 20 总的移动的磁道数是:244 11．在一个请求分页系统中，有一个长度为 5 页的进程，假如系统为它分配 3 个物理块 ，并且此进程的页面走向为 2，3，2，1，5，2，4，5，3，2，5，2。试用 FIFO 和 LRU 两种算法分别计算出程序访问过程中所发生的缺页次数。（10分） 解：FIFO： 2 3 2 1 5 2 4 5 3 2 5 2 第1页 2 2 2 5 5 5 3 3 3 第2页 3 3 3 2 2 2 5 5 第3页 1 1 1 4 4 4 2 缺页中断次数 = 6 LUR： 2 3 2 1 5 2 4 5 3 2 5 2 第1页 2 2 2 2 5 5 5 3 第2页 3 3 5 2 3 3 5 第3页 1 1 4 4 2 2 缺页中断次数 = 5 18、若干个等待访问磁盘者依次要访问的磁道为20，44，40，4，80，12，76，假设每移动一个磁道需要3毫秒时间，移动臂当前位于40号柱面，请按下列算法分别写出访问序列并计算为完成上述各次访问总共花费的寻道时间。 （1）先来先服务算法； （2）最短寻道时间优先算法。 （3）扫描算法（当前磁头移动的方向为磁道递增）（10分） 解： （1）磁道访问顺序为：20，44，40，4，80，12，76 寻道时间=（20+24+4+36+76+68+64）*3=292*3=876 （2）磁道访问顺序为：40，44，20，12，4，76，80 寻道时间=（0+4+24+8+8+72+4）*3=120*3=360 （3）磁道访问顺序为：40，44，76，80，20，12，4 寻道时间=（0+4+32+4+60+8+8）*3=116*3=348
操作系统综合题
