操作系统操作系统习题课2PPT.ppt

《操作系统操作系统习题课2PPT.ppt》由会员分享，可在线阅读，更多相关《操作系统操作系统习题课2PPT.ppt（94页珍藏版）》请在课桌文档上搜索。

1、第一章,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设备利用率。,画出三个作业并行工作图如下(图中着色部分为作业等

2、待时间)：,Job1：I2(30ms)、CPU(10ms)、I1(30ms)、CPU(10ms)Job2：I1(20ms)、CPU(20ms)、I2(40ms)Job3：CPU(30ms)、I1(20ms),Job1从投入到运行完成需80ms，Job2从投入到运行完成需90ms，Job3从投入到运行完成需90ms。CPU空闲时间段为：60ms至70ms，80ms至90ms。所以CPU利用率为(90-20)/90=77.78%。设备I1空闲时间段为：20ms至40ms，故I1的利用率为(90-20)/90=77.78%。设备I2空闲时间段为：30ms至50ms，故I2的利用率为(90-20)/9

3、0=77.78%。,8、若主存中有3道程序A、B、C，优先级从高到低为A、B和C，它们单独运行时的CPU和I/O占用时间为：若3道程序并发执行，调度开销忽略不计，但优先级高的程序可中断优先级低的程序，优先级与I/O设备无关。试画出多道运行的时间关系图，并问最早与最迟结束的程序是哪个？每道程序执行到结束分别用了多少时间？计算3个程序全部运算结束时的CPU利用率?,最早结束的程序为B，最后结束的程序为C。程序A为250ms。程序B为220ms。程序C为310ms。CPU利用率为(310-120)/310=61.3%,第二章,11 有5个批处理作业A到E均已到达计算中心，其运行时间分别2、4、6、8

4、和10分钟；各自的优先级分别被规定为1、2、3、4和5，这里5为最高级。对于(1）时间片轮转算法、(2）优先数法、(3）短作业优先算法、(4）先来先服务调度算法(按到达次序C、D、B、E、A)，在忽略进程切换时间的前提下，计算出平均作业周转时间。（对(1）每个作业获得相同的2分钟长的时间片；对(2）到(4）采用单道运行，直到结束。）,调度算法准则的计算(P123),(1)资源利用率(CPU、I/O操作利用率)(2)吞吐率(3)公平性(4)响应时间(5)周转时间(平均作业周转时间、平均带权作业周转时间),(1)FCFS调度算法,(2)优先级调度算法,(3)时间片轮转法,按次序A B C D E

5、B C D EC D E D E E轮转执行。,(4)SJF调度算法,20，有一个四道作业的操作系统，若在一段时间内先后到达6个作业，它们的提交和估计运行时间由下表给出：作业 提交时间 估计运行时间(分钟)1 8：00 60 2 8：20 35 3 8：25 20 4 8：30 25 5 8：35 5 6 8：40 10,系统采用剩余SJF调度算法，作业被调度进入系统后中途不会退出，但作业运行时可被剩余时间更短作业抢占。(1)分别给出6个作业的执行时间序列、即开始执行时间、作业完成时间、作业周转时间。(2)计算平均作业周转时间。,作业 提交 需运行 开始运行 被抢占还 完成 周转号 时间 时间

6、 时间 需运行时间 时间 时间J1 8:00 60 8:00 40 10:35 155J2 8:20 35 8:20 30 9:55 95J3 8:25 20 8:25 8:45 20 J4 8:30 25 9:00 25 9:25 55 J5 8:35 5 8:45 8:50 15J6 8:40 10 8:50 9:00 20,说明:(1)J2到达时抢占J1；J3到达时抢占J2。(2)但J4到达时，因不满足SJF，故J4不能被运行，J3继续执行5分钟。(3)由于是4道的作业系统，故后面作业不能进入主存而在后备队列等待，直到有作业结束。(4)根据进程调度可抢占原则，J3第一个做完。而这时J5、

7、J6均己进入后备队列，而J5可进入主存。(5)因J5最短，故它第二个完成。这时J6方可进入主存。因J6最短，故它第三个完成。(6)然后是:J4、J2和J1(7)T=(155+95+20+55+15+20)/6=60,27，某多道程序系统供用户使用的主存为100K，磁带机2台，打印机1台。采用可变分区主存管理，采用静态方式分配外围设备，忽略用户作业I/O时间。现有作业序列如下：作业调度采用FCFS策略，优先分配为多少?主存低地址区且不准移动已在主存的作业，在主存中的各作业平分CPU时间。现求：(1)作业被调度的先后次序?(2)全部作业运行结束的时间?(3)作业平均周转时间为多少?(4)最大作业周

8、转时间,参照P238的可变分区管理的定义,本题综合测试了作业调度、进程调度、及对外设的竞争、主存的竞争。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的主存及打印机均可满足，投入运行。

9、作业5到达时间晚，只能等待。9:10 作业4运行结束，作业5因分不到打印机，只能在后备队列继续等待。9:15 作业2运行结束，作业5投入运行。9:30 作业全部执行结束。,答：(1)作业调度选择的作业次序为：作业1、作业3、作业4、作业2和作业5。(2)全部作业运行结束的时间9:30。(3)周转时间：作业1为30分钟、作业2为55分钟、作业3为40分钟、作业4为40分钟和作业5为55分钟。(4)平均作业周转时间=44分钟。(5)最大作业周转时间为55分钟。,28，某多道程序设计系统采用可变分区主存管理，供用户使用的主存为200K，磁带机5台。采用静态方式分配外围设备，且不能移动在主存中的作业，

10、进程调度采用FCFS，忽略用户作业I/O时间。现有作业序列如下：现求：(1)FIFO算法选中作业执行的次序及作业平均周转时间。(2)SJF算法选中作业执行的次序及作业平均周转时间。,几个注意问题：,1，这里还需要考虑进程调度（FCFS).2,需要搞清楚几个关键时刻点内存和磁带机的状态，以确定是否需要装入相应的作业，以及是否需要可以占用处理机。,1、先来先服务算法：,1.先来先服务算法。说明：(1)8:30 作业A到达并投入运行。注意它所占用的资源。(2)8:50 作业B到达，资源满足进主存就绪队列等CPU。(3)9:00 作业C到达，主存和磁带机均不够，进后备作业队列等待。(4)9:05 作业

11、D到达，磁带机不够，进后备作业队列等待。后备作业队列有C、D。(5)9:10 作业A运行结束，归还资源磁带，但注意主存不能移动(即不能紧缩)。作业B投入运行。作业C仍因主存不够而等在后备队列。这时作业E也到达了，也由于主存不够进入后备作业队列。此时作业D因资源满足(主存/磁带均满足)，进主存就绪队列等待。后备作业队列还有C、E。(6)9:35 作业B运行结束，作业D投入运行。这时作业C因资源满足而调入主存进就绪队列等CPU。而作业E因磁带机不够继续在后备作业队列等待。(7)9:55 作业D运行结束，作业C投入运行。这时作业E因资源满足而调入主存进就绪队列等CPU。(8)10:30 作业C运行结

12、束，作业E投入运行。(9)10:40 作业E运行结束。,2.短作业优先算法。,(1)8:30 作业A到达并投入运行。注意它所占用的资源。(2)8:50 作业B到达，资源满足进主存就绪队列等CPU。(3)9:00 作业C到达，主存和磁带机均不够，进后备作业队列等待。(4)9:05 作业D到达，磁带机不够，进后备作业队列等待。后备作业队列有C、D。(5)9:10 作业A运行结束，归还资源磁带，但注意主存不能移动(即不能紧缩)。作业B投入运行。作业C仍因主存不够而等在后备队列。这时作业E也到达了，虽然该作业最短，也由于主存不够进入后备作业队列。此时作业D因资源满足(主存/磁带均满足)，进主存就绪队列

13、等待。后备作业队列还有C、E。(6)9:35 作业B运行结束，作业D投入运行。这时作业C和E资源均满足，但按SJF应把作业E调入主存进就绪队列等CPU。而作业C因磁带机不够继续在后备作业队列等待。(7)9:55 作业D运行结束，作业C调入主存进就绪队列等CPU。(8)10:05 作业E运行结束，作业C投入运行。(9)10:40 作业C运行结束。,第三章,77 试利用test&set指令实现单处理器上的信号量机制。(P229),typedef struct int flag;/标志 int value;/信号量值struct pcb*list;/信号量队列指针semaphore;void P(s

14、)while(!test_set(s.flag)s.value-;if(s.value0)W(s.list);s.flag=1;s.flag=1;void V(s)while(!test_set(!s.flag)s.value+;if(s.value=0)R(s.list);s.flag=1;,19，四个进程Pi（i=03）和四个信箱Mj（j=03），进程间借助相邻信箱传递消息，即Pi每次从Mi中取一条消息，经加工后送入M(i+1)mod4，其中M0、M1、M2、M3分别可存放3、3、2、2个消息。初始状态下，M0装了三条消息，其余为空。试以P、V操作为工具，写出Pi（i=03）的同步工作算法

15、。,semaphore mutex1,mutex2,mutex3,mutex0;mutex1=mutex2=mutex3=mutex0=1;semaphore empty0,empty1,empty2,empty3;empty=0;empty1=3;empty=2;empty3=2;semaphore full0,full1,full2,full3;full0=3;full1=full2=full3=0;int in0,in1,in2,in3,out0,out1,out2,out3;in0=in1=in2=in3=out0=out1=out2=out3=0;cobeginprocess P0(

16、)while(true)P(full0);P(mutex0);从M0out0取一条消息;out0=(out0+1)%3;V(mutex0);V(empty0);加工消息;P(empty1);P(mutex1);消息存M1in1;in1=(in1+1)%3;V(mutex1);V(full1);,process P1()while(true)P(full1);P(mutex1);从M1out1取一条消息;out1=(out1+1)%3;V(mutex1);V(empty1);加工消息;P(empty2);P(mutex2);消息存M2in2;in2=(in2+1)%2;V(mutex2);V(f

17、ull2);,process P2()while(true)P(full2);P(mutex2);从M2out2取一条消息;out2=(out2+1)%2;V(mutex2);V(empty2);加工消息;P(empty3);P(mutex3);消息存M3in3;in3=(in3+1)%2;V(mutex3);V(full3);process P3()while(true)P(full3);P(mutex3);从M3out3取一条消息;out3=(out3+1)%2;V(mutex3);V(empty3);加工消息;P(empty0);P(mutex0);消息存M0in0;in0=(in0+1

18、)%3;V(mutex0);V(full0);coend,25，一条公路两次横跨运河，两个运河桥相距100米，均带有闸门，以供船只通过运河桥。运河和公路的交通均是单方向的。运河上的运输由驳船担负。在一驳船接近吊桥A时就拉汽笛警告，若桥上无车辆，吊桥就吊起，直到驳船尾P通过此桥为止。对吊桥B也按同样次序处理。一般典型的驳船长度为200米，当它在河上航行时是否会产生死锁?若会，说明理由，请提出一个防止死锁的办法，并用信号量来实现驳船的同步。,有些类似于读者写者问题,分析：当汽车或驳船未同时到达桥A时，以任何次序前进不会产生死锁。但假设汽车驶过了桥A，它在继续前进，并且在驶过桥B之前，此时有驳船并快

19、速地通过了桥A，驳船头到达桥B，这时会发生死锁。因为若吊起吊桥B让驳船通过，则汽车无法通过桥B；若不吊起吊桥B让汽车通过，则驳船无法通过桥B。可用两个信号量同步车、船通过两座桥的动作。,semaphore ship_mutex=1;semaphore car_mutex=0;semaphore sbridge=1;int ship_count=0;in car_count=0;cobeginprocess ship()P(ship_mutex);if(ship_count=0)p(sbridge);ship_count+;V(ship_mutex);ship_go_on();P(ship_mu

20、tex);ship_count-;if(ship_count=0)V(sbridge);V(car_mutex);process car()P(car_mutex);if(car_count=0)p(sbridge);car_count+;V(ship_mutex);car_go_on();P(car_mutex);car_count-;if(car_count=0)V(sbridge);V(ship_mutex);coend,30，把死锁检测算法用于下面的数据，并请问：Available=(1，0，2，0)(1)此时系统处于安全状态吗？(2)若第二个进程提出资源请求request2(0，0，

21、1，0)，系统能分配资源给它吗？(3)执行(2)之后，若第五个进程提出资源请求request5(0，0，1，0)，系统能分配资源给它吗？,31，考虑一个共有150个存储单元的系统，如下分配给三个进程，P1最大需求70,已占有25；P2最大需求60,已占有40；P3最大需求60,已占有45。使用银行家算法，以确定下面的任何一个请求是否安全。(1)P4进程到达，P4最大需求60,最初请求25个。(2)P4进程到达，P4最大需求60,最初请求35。如果安全，找出安全序列；如果不安全，给出结果分配情况。,(1)由于系统目前还有150-25-40-45=40个单元，P4进程到达，把25个单元分给它。这时

22、系统还余15个单元，可把15个单元分给P3，它执行完后会释放60个单元。于是可供P1(还要45个单元)，P2(还要20个单元)，P4(还要35个单元)任何一个执行。安全序列为：P1，P2，P3，P4，P3，P1，P2，P4 P1，P2，P3，P4，P3，P1，P4，P2 P1，P2，P3，P4，P3，P2，P1，P4 P1，P2，P3，P4，P3，P2，P4，P1 P1，P2，P3，P4，P3，P4，P1，P2 P1，P2，P3，P4，P3，P4，P2，P1(2)P4进程到达，P4最大需求60,最初请求35。如果把35个单元分给P4，系统还余5个单元，不再能满足任何一个进程的需求，系统进入不安

23、全状态。,32,有一个仓库，可存放X、Y两种产品，仓库的存储空间足够大，但要求：(1)每次只能存入一种产品X或Y，(2)满足-NX产品数量-Y 产品数量M。其中，N和M是正整数，试用信号量与P、V操作实现产品X与Y的入库过程。,本题最有意思的部分在于信号量的设置上,本题给出的表达式可分解为制约条件：NX产品数量Y产品数量 X产品数量Y产品数量M也就是说，X产品的数量不能比Y产品的数量少N个以上，X产品的数量不能比Y产品的数量多M个以上。可以设置两个信号量来控制X、Y产品的存放数量：sx表示当前允许X产品比Y产品多入库的数量，即在当前库存量和Y产品不入库的情况下，还可以允许sx个X产品入库；初始

24、时，若不放Y而仅放X产品，则sx最多为M1个。sy表示当前允许Y产品比X产品多入库的数量，即在当前库存量和X产品不入库的情况下，还可以允许sy个Y产品入库。初始时，若不放X而仅放Y产品，则sy最多为N1个。当往库中存放入一个X产品时，则允许存入Y产品的数量也增加1，故信号量sy应加1；当往库中存放入一个Y产品时，则允许存入X产品的数量也增加1，故信号量sx应加1。semaphore mutex=1;/*互斥信号量*/semaphore sx，sy；sx=M-1;sy=N-1;,cobegin process storeX()while(true)P(sx);P(mutex);将X产品入库；V(

25、mutex);V(sy);process storeY()while(true)P(sy);P(mutex);将Y产品入库；V(mutex);V(sx);coend,管程(不会重点考察）,66，在一个分页存储管理系统中，用freeindex数组记录每个页框状态，共有n个页框(index=0，n-1)。当freeindex=true时，表示第index个页框空闲，freeindex=false时，表示第index个页框被占用。试设计一个管程，它有两个过程acquire和return分别负责分配和回收一个页框。,管程的实现方法（OS第三版）,1,Hoare方法（霍尔方法）2,Hanson方法（汉森

26、方法）3,需要注意管程与进程的比较,TYPE framemanagement=monitor bool freen;semaphore waitcondition;int i,waitcondition_count;for(int index=0;index n;index+)freeindex=true;InterfaceModule IM;DEFINE acquire,release;USE enter,wait,signal,leave;void acquire(int index)enter(IM);for(int i=0;in;i+)if(freei)freei=false;inde

27、x=i;else wait(waitcondition,waitcondition_count,IM);leave(IM);void return(int index)enter(IM);freeindex=true;signal(waitcondition,waitcondition_count,IM);leave(IM);,第四章,47，假设一个物理存储器，有4个页框，对下面每种策略，给出引用串：P1、p2、p3、p1、p4、p5、p1、p2、p1、p4、p5、p3、p4、p5的缺页数目（所有页框最初都是空的）。试用下列算法求出缺页中断次数，(a)OPT，(b)FIFO，(c)SCR，(d

28、)改进的CLOCK，(e)LRU，(f)MIN，(g)WS。,（a）最优置换算法OPT：1 2 3 1 4 5 1 2 1 4 5 3 4 5缺页6次。,（b）先进先出算法FIFO1 2 3 1 4 5 1 2 1 4 5 3 4 5,缺页10次。,（c）第二次机会算法SCR1 2 3 1 4 5 1 2 1 4 5 3 4 5,缺页10次。,（d）改进的时钟算法clock（假设所有对页面p2的访问都是写请求）1 2 3 1 4 5 1 2 1 4 5 3 4 5(具体的算法：参见P267倒数第3行）,（e）最近最少使用算法（LRU）1 2 3 1 4 5 1 2 1 4 5 3 4 5,缺页

29、7次,（f）局部最优页面置换算法（MIN）1 2 3 1 4 5 1 2 1 4 5 3 4 5,设滑动窗口3,缺页9次。在这里由于3，内存最多需要4块。,（g）工作集算法（WS），21 2 3 1 4 5 1 2 1 4 5 3 4 5,缺页8次。,3 一个页式存储管理系统使用FIFO、OPT和LRU页面替换算法，如果一个作业的页面走向为：(1)2、3、2、1、5、2、4、5、3、2、5、2。(2)4、3、2、1、4、3、5、4、3、2、1、5。(3)1、2、3、4、1、2、5、1、2、3、4、5。当分配给该作业的物理块数分别为3和4时，试计算访问过程中发生的缺页中断次数和缺页中断率。,答：

30、(1)作业的物理块数为3块，使用FIFO为9次，9/12=75%。使用LRU为7次，7/12=58%。使用OPT为6次，6/12=50%。作业的物理块数为4块，使用FIFO为6次，6/12=50%。使用LRU为6次，6/12=50%。使用OPT为5次，5/12=42%。(2)作业的物理块数为3块，使用FIFO为9次，9/12=75%。使用LRU为10次，10/12=83%。使用OPT为7次，7/12=58%。作业的物理块数为4块，使用FIFO为10次，10/12=83%。使用LRU为8次，8/12=66%。使用OPT为6次，6/12=50%。其中，出现了Belady现象，增加分给作业的主存块数

31、，反使缺页中断率上升。,4，在可变分区存储管理下，按地址排列的主存空闲区为：10K、4K、20K、18K、7K、9K、12K和15K。对于下列的连续存储区的请求：(1)12K、10K、9K，(2)12K、10K、15K、18K试问：使用首次适应算法、最佳适应算法、最差适应算法和下次适应算法，哪个空闲区被使用？,1)首次适应算法 12KB选中分区3，这时分区3还剩8KB。10KB选中分区1，恰好分配故应删去分区1。9KB选中分区4，这时分区4还剩9KB。2)最佳适应算法 12KB选中分区7，恰好分配故应删去分区7。10KB选中分区1，恰好分配故应删去分区1。9KB选中分区6，恰好分配故应删去分区

32、6。3)最差适应算法 12KB选中分区3，这时分区3还剩8KB。10KB选中分区4，这时分区4还剩8KB。9KB选中分区8，这时分区8还剩6KB。4)下次适应算法12KB选中分区3，这时分区3还剩8KB。10KB选中分区4，这时分区4还剩8KB。9KB选中分区6，恰好分配故应删去分区6。,(2)1)首次适应算法 12KB选中分区3，这时分区3还剩8KB。10KB选中分区1，恰好分配故应删去分区1。15KB选中分区4，这时分区4还剩3KB。最后无法满否18KB的申请，应该等待。2)最佳适应算法 12KB选中分区7，恰好分配故应删去分区7。10KB选中分区1，恰好分配故应删去分区1。15KB选中分

33、区8，恰好分配故应删去分区8。18KB选中分区4，恰好分配故应删去分区4。3)最差适应算法 12KB选中分区3，这时分区3还剩8KB。10KB选中分区4，这时分区4还剩8KB。15KB选中分区8，恰好分配故应删去分区8。最后无法满否18KB的申请，应该等待。4)下次适应算法12KB选中分区3，这时分区3还剩8KB。10KB选中分区4，这时分区4还剩8KB。15KB选中分区8，恰好分配故应删去分区8。最后无法满否18KB的申请，应该等待。,51 设进程分得三个页框，其执行访问序列为：0 1 2 3 0 1 2 3 0 1 2 3 4 5 6 7，试采用(1)Belady(即OPT)，(2)LRU

34、，(3)LFU，(4)FIFO算法来分别计算缺页中断次数，并给出缺页时加进主存的页号。,(1)Belady算法共10次，缺页时加进主存的页面见表中带星的页号。,(2)LRU算法共16次，缺页时加进主存的页面见表中带星的页号。,(3)LFU算法共12次，缺页时加进主存的页面见表中带星的页号。,注意，如果一个页过去没有被经常使用，它就会被选替换，当有多个页满足条件时，系统可任选一个进行替换。LFU(Least Frequently Used,(4)FIFO算法共16次，缺页时加进主存的页面见表中带星的页号。,第五章,7、假定磁盘有200个柱面，编号0199，当前存取臂的位置在143号柱面上，并刚刚

35、完成了125号柱面的服务请求(告诉了运动方向），如果请求队列的先后顺序是：86，147，91，177，94，150，102，175，130；试问：为完成上述请求，下列算法存取臂移动的总量是多少？并算出存取臂移动的顺序。(1)先来先服务算法FCFS；(2)最短查找时间优先算法SSTF；(3)扫描算法SCAN。(4)电梯调度。,注意区别：P327,电梯调度算法:每次总是选择沿着移动臂的移动方向最近的那个柱面；若当前移动方向上没有访问请求，则改变移动臂的移动方向，去处理所遇到的最近I/O请求。“扫描”算法：移动臂每次沿一个方向移动，扫过所有柱面，遇到在最近的I/O请求，直到最后一个柱面后，在反向移动

36、过来。“循环扫描”算法：移动臂总是从0号柱面到最大号柱面顺序扫描。,(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。,25 磁盘组共有n个柱面，编号顺序为0、1、

37、2、n-1；共有m个磁头，编号顺序为0、1、2、m1；每个磁道内的k个信息块从1开始编号，依次为1、2、k。现用x表示逻辑磁盘块号，用a,b,c分别表示任一逻辑磁盘块的柱面号、磁头号、磁道内块号，则x与a,b,c可通过如下公式进行转换：x=kma+kb+ca=(x-1)DIV(km)b=(x-1)%(km)DIV kc=(x-1)%(km)%(k+1)若某磁盘组为n200，m20，k10，问：(1)柱面号为185，磁头号为12，道内块号为5的磁盘块的逻辑磁盘块号为多少？(2)逻辑磁盘块号为1200，它所对应的柱面号、磁头号及磁道内块号为多少？(3)若每一磁道内的信息块从0开始编号，依次为0、1

38、、k-1，其余均同题设，试写出x与a、b、c之间的转换公式。,参看P325磁盘结构图,(1)由上述公式可知，逻辑磁盘块号x为：x=kma+kbc=102018510205=37125所以，柱面号为185，磁头号为12，道内块号为5的磁盘块的逻辑磁盘块号为：37125。(2)由上述公式可知，a=(x-1)DIV(km)=(1200-1)DIV(1020)=1199 DIV 200=5 b=(x-1)%(km)DIV k=(1200-1)%(1020)DIV 10=(1199%200)DIV 10=199 DIV 10=10 c=(x-1)%(km)MOD k+1=(1200-1)%(1020)%

39、(10+1)=(1199%200)%(10+1)=199%(10+1)=9+1=10所以，逻辑磁盘块号为1200，它所对应的柱面号是5、磁头号是19及磁道内块号为10。(3)转换公式为：x=kma+kb+c+1a=(x-1)DIV(km)b=(x-1)%(km)DIV kc=(x-1)%(km)%k,12、某磁盘共有200个柱面，每个柱面有20个磁道，每个磁道有8个扇区，每个扇区为1024B。如果驱动程序接到访求是读出606块，计算该信息块的物理位置。,（1）每个柱面的物理块数为208=160块（2）606/160得到商为3，余数为126。访求的物理位置在：第3个柱面(柱面号、磁道号与扇区号均

40、从0开始编号)的126物理块中(即3柱面、16磁道、5扇区)。,15、一个软盘有40个柱面，查找移过每个柱面花6ms。若文件信息块零乱存放，则相邻逻辑块平均间隔13个柱面。但优化存放，相邻逻辑块平均间隔为2个柱面。如果搜索延迟为100ms，传输速度为每块25ms，现问在两种情况下传输100块文件信息各需多长时间。,答：非优化存放，读一块数据需要时间为：136+100+25=203ms因而，传输100块文件需：20300ms。优化存放，读一块数据需要时间为：26+100+25=137ms因而，传输100块文件需：13700ms。,第六章,5 在UNIX 中，如果一个盘块的大小为1KB，每个盘块号

41、占4个字节，即每块可放256个地址。请转换下列文件的字节偏移量为物理地址：(1)9999；(2)18000；(3)420000。(对比P374，这里每个盘块大小为1KB,而书上是512B。所以每次间接索引所指向的那个盘块实际上就会有256个子索引项。）,答：步1 将逻辑文件的字节偏移量转换为文件的逻辑块号和块内偏移。方法是：将逻辑文件的字节偏移量/盘块大小，商为文件的逻辑块号，余数是块内偏移。步2将文件的逻辑块号转换为物理块号。使用多重索引结构，在索引节点中根据逻辑块号通过直接索引或间接索引找到对应物理块号。9000 L1=INT(9999，1024)=9 B1=MOD(9999，1024)=

42、783其逻辑块号为9，故直接索引addr9中可找到物理块号。18000 L2=INT(18000，1024)=17 B1=MOD(18000，1024)=592其逻辑块号为17，通过一次间接索引addr10中可找到物理块号。420000 L1=INT(420000，1024)=410 B1=MOD(9000，1024)=160其逻辑块号为410，通过二次间接索引addr11中可找到物理块号。,9，一个UNIX/Linux文件，如果一个盘块的大小为1KB，每个盘块号占4个字节，那么，若进程欲访问偏移为263168字节处的数据，需经过几次间接？(对比P374，这里每个盘块大小为1KB,而书上是51

43、2B。所以每次间接索引所指向的那个盘块实际上就会有256个子索引项。）,UNIX/Linux文件系统中，直接寻址为10块，一次间接寻址为256块，二次间接寻址为2562块，三次间接寻址为2563块。偏移为263168字节的逻辑块号是：263168/1024=257。块内偏移量=263168-2571024=0。由于10257256+10，故263168字节在一次间接寻址内。,15 某磁盘共有100个柱面，每个柱面有8个磁头，每个盘面分4个扇区。若逻辑记录与扇区等长，柱面、磁道、扇区均从0起编号。现用16位的200个字(0-199)来组成位示图来管理盘空间。现问：(1)位示图第15个字的第7位为

44、0而准备分配给某一记录，该块的柱面号、磁道号、扇区号是多少?(2)现回收第56柱面第6磁道第3扇区，这时位示图的第几个字的第几位应清0?,磁盘块的物理地址描述 采用三个参数,要在磁盘上访问一个扇区，必须给出其柱面号、磁头号和扇区号，这称为扇区的物理地址，即物理扇区号。由物理扇区号表示的扇区称为绝对扇区。为了方便，操作系统通常将其转变为连续的逻辑扇区号加以管理。编址方式为：对整个磁盘从柱面0到最后一个柱面增加，在柱面上按磁道号增加，在磁道上按扇区号增加。,设一块为一扇，则磁盘块号及其物理三地址之间可按以下式子转换:(1)已知块号，则磁盘驱动用的三地址：柱面号块号/（磁头数扇区数）磁头号(块号mo

45、d(磁头数扇区数)/扇区数 扇区号(块号mod(磁头数扇区数)mod 扇区数(2)已知磁盘块物理地址，则磁盘块号：块号柱面号(磁头数扇区数)磁头号扇区数扇区号,(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。,