操作系统部分习题参考答案孙钟秀版.doc

操作系统部分习题参考答案第一章2.一个计算机系统，有一台输入机和一台打印机，现有两道程序投入运行，且程序A先开始做，程序B后开始运行。程序A的运行轨迹为：计算50ms、打印100ms、再计算50ms、打印100ms，结束。程序B的运行轨迹为：计算50ms、输入80ms、再计算100ms，结束。试说明(1)两道程序运行时，CPU有无空闲等待？若有，在哪段时间内等待？为什么会等待？(2)程序A、B有无等待CPU的情况？若有，指出发生等待的时刻。答：画出两道程序并发执行图如下：(1)两道程序运行期间，CPU存在空闲等待，时间为100至150ms之间(见图中有色部分)。(2)程序A无等待现象，但程序B有等待。程序B有等待时间段为180ms至200ms间(见图中有色部分)。5.在单CPU和两台I/O(I1,I2)设备的多道程序设计环境下，同时投入三个作业运行。它们的执行轨迹如下：Job1：I2(30ms)、CPU(10ms)、I1(30ms)、CPU(10ms)Job2：I1(20ms)、CPU(20ms)、I2(40ms)Job3：CPU(30ms)、I1(20ms)如果CPU、I1和I2都能并行工作，优先级从高到低为Job1、Job2和Job3，优先级高的作业可以抢占优先级低的作业的CPU。试求：(1)每个作业从投入到完成分别所需的时间。(2) 从作业的投入到完成CPU的利用率。(3)I/O设备利用率。答：画出三个作业并行工作图如下(图中着色部分为作业等待时间)：(1) Job1从投入到运行完成需80ms，Job2从投入到运行完成需90ms，Job3从投入到运行完成需90ms。(2)CPU空闲时间段为：60ms至70ms，80ms至90ms。所以CPU利用率为(90-20)/80=77.78%。(3)设备I1空闲时间段为：20ms至40ms，故I1的利用率为(90-20)/90=77.78%。设备I2空闲时间段为：30ms至50ms，故I2的利用率为(90-20)/90=77.78%。第二章7假定执行作业Job1Job5，作业号即为其到达顺序，依次在时刻0按照序号1、2、3、4、5进入单处理器系统。作业号 执行时间/ms 优先权Job1 10 3Job2 1 1Job3 2 3Job4 1 4Job5 5 2（1）分别采用先来先服务调度算法、时间片轮转算法（时间片为1ms）、短作业优先算法及非抢占式优先权调度算法，计算出各作业的执行次序（注意：优先权越高，其数值越小）（2）计算每种情况下作业的平均周转时间和平均带权周转时间。答：（1）采用先来先服务调度算法执行次序执行时间等待时间开始时间完成时间周转时间带权周转时间Job1Job2Job3Job4Job5101215010111314010111314101113141910111314191116.5143.8作业平均周转时间作业平均带权周转时间13.47.26（2）采用时间片轮转算法，令时间片=1，各作业执行情况为：1234513515151511111执行次序执行时间完成时间周转时间带权周转时间Job1Job2Job3Job4Job5101215192741419274141.923.542.8作业平均周转时间作业平均带权周转时间9.22.84（3）短作业优先算法执行次序执行时间等待时间开始时间完成时间周转时间带权周转时间Job2Job4Job3Job5Job111251001249012491249191249191221.81.9作业平均周转时间作业平均带权周转时间71.74（4）非抢占式优先权调度算法执行次序优先数执行时间等待时间周转时间带权周转时间Job2Job5Job1Job3Job41233415102101616181616181911.21.6919作业平均周转时间作业平均带权周转时间126.3611. 5个批处理作业A到E均已到达计算中心，其运行时间分别2、4、6、8和10分钟；各自的优先级分别被规定为1、2、3、4和5，这里5为最高级。对于1）时间片轮转算法、2）优先数法、3）短作业优先算法、4）先来先服务调度算法(按到达次序C、D、B、E、A)，在忽略进程切换时间的前提下，计算出平均作业周转时间。（对1）每个作业获得相同的2分钟长的时间片；对2）到4）采用单道运行，直到结束。）答： (1) 时间片轮转法按次序A B C D E B C D EC D E D E E轮转执行。(2) 优先级调度算法(3)SJF调度算法(4)FCFS调度算法15在单道批处理系统中，下列三个作业采用先来先服务调度算法和最高响应比优先算法进行调度，哪种算法性能较好？请完成下表。作业提交时间运行时间开始时间完成时间周转时间带权周转时间12310: 0010：1010: 252:001:000:25作业平均周转时间=作业平均带权周转时间=答：（1）FIFO算法作业提交时间运行时间开始时间完成时间周转时间带权周转时间12310: 0010：1010: 252:001:000:2510:0012:0013:0012:0013:0013:2522:503120/120170/60180/25作业平均周转时间=2.61作业平均带权周转时间=3.68（2）HRRF算法作业提交时间运行时间开始时间完成时间周转时间带权周转时间12310: 0010：1010: 252:001:000:2510:0012:2512:0012:0013:2512:2523:152120/120195/60120/25作业平均周转时间=2.41作业平均带权周转时间=3.02可见HRRF比FIFO要好。27. 某多道程序设计系统供用户使用的主存为100K，磁带机2台，打印机1台。采用可变分区内存管理，采用静态方式分配外围设备，忽略用户作业I/O时间。现有作业序列如下：作业号 进入输入井时间 运行时间 主存需求量 磁带需求 打印机需求 1 8:00 25分钟 15K 1 1 2 8:20 10分钟 30K 0 1 3 8:20 20分钟 60K 1 0 4 8:30 20分钟 20K 1 0 5 8:35 15分钟 10K 1 1 作业调度采用FCFS策略，优先分配主存低地址区且不准移动已在主存的作业，在主存中的各作业平分CPU时间。现求：(1)作业被调度的先后次序?(2)全部作业运行结束的时间?(3)作业平均周转时间为多少?(4)最大作业周转时间为多少?答：(1)作业调度选择的作业次序为：作业1、作业3、作业4、作业2和作业5。 (2)全部作业运行结束的时间9:30。 (3)周转时间：作业1为30分钟、作业2为55分钟、作业3为40分钟、作业4为40分钟和作业5为55分钟。 (4)平均作业周转时间=44分钟。 (5) 最大作业周转时间为55分钟。分析：本题综合测试了作业调度、进程调度、及对外设的竞争、主存的竞争。8:00 作业1到达，占有资源并调入主存运行。8:20 作业2和3同时到达，但作业2因分不到打印机，只能在后备队列等待。作业3资源满足，可进主存运行，并与作业1平分CPU时间。8:30 作业1在8:30结束，释放磁带与打印机。但作业2仍不能执行，因不能移动而没有30KB的空闲区，继续等待。作业4在8:30到达，并进入主存执行，与作业3分享CPU。8:35 作业5到达，因分不到磁带机/打印机，只能在后备队列等待。9:00 作业3运行结束，释放磁带机。此时作业2的主存及打印机均可满足，投入运行。作业5到达时间晚，只能等待。9:10 作业4运行结束，作业5因分不到打印机，只能在后备队列继续等待。9:15 作业2运行结束，作业5投入运行。9:30 作业全部执行结束。第三章（思考题）42某系统有m个同类资源供n个进程共享，若每个进程最多申请x个资源（1xm）,推导出系统不发生死锁（n、m和x）的关系式。答：最坏：每个（x-1）个资源，申请最后一个，剩m-n(x-1)若还有一个资源可用，则可使所有进程执行结束。m-n(x-1)1，即n(x-1)+1m系统不会死锁。3.有两个优先级相同的进程P1和P2，各自执行的操作如下，信号量S1和S2初值均为0。试问P1、P2并发执行后，x、y、z的值各为多少？P1： P2：begin begin y:=1; x:=1; y:=y+3; x:=x+5; V(S1); P(S1); z:=y+1; x:=x+y; P(S2); V(S2); y:=z+y z:=z+x; end. end.答：现对进程语句进行编号，以方便描述。P1： P2：begin begin y:=1; x:=1; y:=y+3; x:=x+5; V(S1); P(S1); z:=y+1; x:=x+y; P(S2); V(S2); y:=z+y z:=z+x; end. end.、和是不相交语句，可以任何次序交错执行，而结果是唯一的。接着无论系统如何调度进程并发执行，当执行到语句时，可以得到x=10，y=4。按Bernstein条件，语句的执行结果不受语句的影响，故语句执行后得到z=5。最后，语句和并发执行，这时得到了两种结果为：语句先执行：x=10，y=9，z=15。语句先执行：x=10，y=19，z=15。此外，还有第三种情况，语句被推迟，直至语句后再执行，于是依次执行以下三个语句：z:=z+x；z:=y+1; y:=z+y;这时z的值只可能是y+1=5，故y=z+y=5+4=9，而x=10。第三种情况为：x=10，y=9，z=5。（注：第28和30题请参考书上的例题，使用表格给出求解安全序列的过程。正式考试中，如果没有求解过程，一律扣分！）28、（1）2 2 2 1 0 2 1 0 3 4 2 0 （2）存在安全序列2,1,3,4，所以安全 （3）存在安全序列2,1,3,4，所以安全 （4）不可以分配，资源不足 （5）不可以分配，处于不安全状态30、（1）存在安全序列4,1,5,2,3，所以系统安全 （2）可以分配，存在安全序列4,1,5,2,3 （3）不可以分配，因为系统进入不安全状态第四章1在一个请求分页虚拟存储管理系统中，一个程序运行的页面走向是： 1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6分别使用FIFO、OPT和LRU算法，对于分配给程序四个页框的情况，求出缺页中断次数和缺页中断率。答：FIFO12342156212376321236F(1)F(2)F(3)F(4)F(5)F(6)F(2)F(1)F(3)F(7)11111123455621137766222223456621337662233334562213776221144456211376621133缺页中断次数：14，缺页中断率：14/20OPT12342156212376321236F(4)F(5)F(1)F(7)11111111111177771111222222222222222222233333333333333333344456666666666666缺页中断次数：8，缺页中断率：8/20LRU12342156212376321236F(3)F(4)F(5)F(6)F(1)F(7)11111342155612276661222342156612376331233421562123763212342156212376321236缺页中断次数：10，缺页中断率：10/204.在可变分区存储管理下，按地址排列的主存空闲区为：10KB、4KB、20KB、18KB、7KB、9KB、12KB和15KB。对于下列连续存储区的请求：（1）12KB、10KB、9KB；（2）12KB、10KB、15KB、18KB；试问：使用首次适应算法、最佳适应算法、最差适应算法和下次适应算法，哪个空闲区将被使用？答：（1）空闲分区如图所示分区号分区长1234567810KB4KB20KB18KB7KB9KB12KB15KB首次适应算法：12KB选中分区3，此时分区3还剩8KB。10KB选中分区1，恰好分配完，所以删去分区1。9KB选中分区4，这时分区4还剩9KB。最佳适应算法：12KB选中分区7，恰好分配完，所以删去分区7。10KB选中分区1，恰好分配完，所以删去分区1。9KB选中分区6，恰好分配完，所以删去分区6。最差适应算法：12KB选中分区3，此时分区3还剩8KB。10KB选中分区4，此时分区4还剩8KB。9KB选中分区8，此时分区8还剩6KB。下次适应算法：12KB选中分区3，此时分区3还剩8KB。10KB选中分区4，此时分区4还剩8KB。9KB选中分区6，恰好分配完，所以删去分区6。 （2）略第五章7假定磁盘有200个柱面，编号0199，当前存取臂的位置在143号柱面上，并刚刚完成了125号柱面的服务请求，如果请求队列的先后顺序是：86，147，91，177，94，150，102，175，130；试问：为完成上述请求，下列算法存取臂移动的总量是多少？并算出存取臂移动的顺序。(1)先来先服务算法FCFS；(2)最短查找时间优先算法SSTF；(3)扫描算法SCAN。(4)电梯调度。答：(1)先来先服务算法FCFS为565，依次为143-86-147-91-177-94-150-102-175-130。(2)最短查找时间优先算法SSTF为162，依次为143-147-150-130-102-94-91-86-175-177。(3)扫描算法SCAN为169，依次为143-147-150-175-177-199-130-102-94-91-86。(4)电梯调度为125(先向地址大的方向)，依次为143-147-150-175-177-130-102-94-91-86。9、若磁头的当前位置为100柱面，磁头正向磁道号减小方向移动。现有磁盘读写请求队列，柱面号依次为：190,10,160,80,90,125,30,20,29,140,25。若采用最短寻道时间优先算法和电梯调度算法，试计算出各种算法的移臂所经过的柱面数。答：SSTF:100-90-80-125-140-160-190-30-29-25-20-10，总柱面数为310。 电梯调度：100-90-80-30-29-25-20-10-125-140-160-190，总柱面数为270补充习题：从100号磁道开始，向磁道号增加的方向访问，则有9个进程分别按下述四种方法调度，顺序及平均寻道长度分别为：请求的下一磁道号FCFS的移动距离（磁道数）SSTF的移动距离（磁道数）电梯算法循环扫描算法555545901015050150505858358321601016010393919553184241842418182139169094181669090723815832382016016070182055339115015010150132391655163838112160103815831841841461842418209032平均寻道长55.327.527.835.8第六章3 某操作系统的磁盘文件空间共有500块，若用字长为32位的位示图管理盘空间，试问：(1)位示图需多少个字? (2)第i字第j位对应的块号是多少? (3)并给出申请/归还一块的工作流程。答： (1) 位示图占用字数为500/32=16(向上取整)个字。(2) 第i字第j位对应的块号N=32i+j。(3)申请时自上至下、自左至有扫描位示图跳过为1的位，找到第一个迁到的0位，根据它是第i字第j位算出对应块号，并分配出去。归还时已知块号，块号/32算出第i字第j位并把位示图相应位清0。15磁盘共有100个柱面，每个柱面有8个磁头，每个盘面分4个扇区。若逻辑记录与扇区等长，柱面、磁道、扇区均从0起编号。现用16位的200个字(0-199)来组成位示图来管理盘空间。现问：(1)位示图第15个字的第7位为0而准备分配给某一记录，该块的柱面号、磁道号、扇区号是多少?(2)现回收第56柱面第6磁道第3扇区，这时位示图的第几个字的第几位应清0?答：(1)位示图第15个字的第7位对应的块号=1516(字长)+7=247，而块号247对应的：柱面号=247/(84)=7(从0编号，向下取整)磁头号=(247 MOD 32)/4=5扇区号=247 MOD 32 MOD 4=3(2)块号=柱面号柱面扇区数+磁道号盘扇区+盘扇区=56(84)+64+3=1819字号=1819/16=113位号=1819 MOD 16 =11所以，回收第56柱面第6磁道第3扇区时，位示图的第113字的第11位应清0。 1一 月二 月三 月产品名称数量金额利润产品名称数量金额利润产品名称数量金额利润合 计合 计合 计四 月五 月六 月产品名称数量金额利润产品名称数量金额利润产品名称数量金额利润合 计合 计合 计下午13：0017：00B实行不定时工作制的员工，在保证完成甲方工作任务情况下，经公司同意,可自行安排工作和休息时间。312打卡制度3.1.2.1公司实行上、下班指纹录入打卡制度。全体员工都必须自觉遵守工作时间，实行不定时工作制的员工不必打卡。3.1.2.2打卡次数：一日两次，即早上上班打卡一次，下午下班打卡一次。3.1.2.3打卡时间：打卡时间为上班到岗时间和下班离岗时间； 3.1.2.4因公外出不能打卡：因公外出不能打卡应填写外勤登记表,注明外出日期、事由、外勤起止时间。因公外出需事先申请，如因特殊情况不能事先申请，应在事毕到岗当日完成申请、审批手续，否则按旷工处理。因停电、卡钟（工卡）故障未打卡的员工，上班前、下班后要及时到部门考勤员处填写未打卡补签申请表，由直接主管签字证明当日的出勤状况，报部门经理、人力资源部批准后，月底由部门考勤员据此上报考勤。上述情况考勤由各部门或分公司和项目文员协助人力资源部进行管理。3.1.2.5手工考勤制度3.1.2.6手工考勤制申请：由于工作性质，员工无法正常打卡（如外围人员、出差），可由各部门提出人员名单，经主管副总批准后，报人力资源部审批备案。3.1.2.7参与手工考勤的员工，需由其主管部门的部门考勤员(文员)或部门指定人员进行考勤管理，并于每月26日前向人力资源部递交考勤报表。3.1.2.8参与手工考勤的员工如有请假情况发生，应遵守相关请、休假制度，如实填报相关表单。3.1.2.9 外派员工在外派工作期间的考勤,需在外派公司打卡记录;如遇中途出差,持出差证明,出差期间的考勤在出差地所在公司打卡记录;3.2加班管理3.2.1定义加班是指员工在节假日或公司规定的休息日仍照常工作的情况。A现场管理人员和劳务人员的加班应严格控制，各部门应按月工时标准，合理安排工作班次。部门经理要严格审批员工排班表，保证员工有效工时达到要求。凡是达到月工时标准的，应扣减员工本人的存休或工资；对超出月工时标准的，应说明理由，报主管副总和人力资源部审批。 B因员工月薪工资中的补贴已包括延时工作补贴，所以延时工作在4小时（不含）以下的，不再另计加班工资。因工作需要，一般员工延时工作4小时至8小时可申报加班半天，超过8小时可申报加班1天。对主管(含)以上管理人员，一般情况下延时工作不计加班，因特殊情况经总经理以上领导批准的延时工作，可按以上标准计加班。3.2.2.2员工加班应提前申请，事先填写加班申请表，因无法确定加班工时的，应在本次加班完成后3个工作日内补填加班申请表。加班申请表经部门经理同意，主管副总经理审核报总经理批准后有效。加班申请表必须事前当月内上报有效，如遇特殊情况，也必须在一周内上报至总经理批准。如未履行上述程序，视为乙方自愿加班。3.2.2.3员工加班，也应按规定打卡，没有打卡记录的加班，公司不予承认；有打卡记录但无公司总经理批准的加班，公司不予承认加班。3.2.2.4原则上，参加公司组织的各种培训、集体活动不计加班。3.2.2.5加班工资的补偿：员工在排班休息日的加班，可以以倒休形式安排补休。原则上，员工加班以倒休形式补休的，公司将根据工作需要统一安排在春节前后补休。加班可按1：1的比例冲抵病、事假。3.2.3加班的申请、审批、确认流程3.2.3.1加班申请表在各部门文员处领取，加班统计周期为上月26日至本月25日。3.2.3.2员工加班也要按规定打卡，没有打卡记录的加班，公司不予承认。各部门的考勤员(文员)负责加班申请表的保管及加班申报。员工加班应提前申请，事先填写加班申请表加班前到部门考勤员(文员)处领取加班申请表，加班申请表经项目管理中心或部门经理同意，主管副总审核，总经理签字批准后有效。填写并履行完审批手续后交由部门考勤员(文员)保管。3.2.3.3部门考勤员（文员）负责检查、复核确认考勤记录的真实有效性并在每月27日汇总交人力资源部，逾期未交的加班记录公司不予承认。15