操作系统经典算法题汇总-分章节

操作系统计算题汇总2013.12谨以此献给计科11级JAVA同学：学习不是为了考试内容进程管理涉及到计算题内存管理涉及到计算题外设管理涉及到计算题文件系统涉及到计算题（一）、进程管理涉及到计算题进程同步问题理发店里有一位理发师、一把理发椅子和五把供等候理发的顾客坐的椅子。如果没有顾客，理发师便在理发椅上睡觉。当一个顾客到来时，他必须先叫醒理发师，如果理发师正在理发时又有顾客来到，而如果有空椅子可坐，他们就坐下来等，如果没有空椅子，他就离开。这里的问题是为理发师和顾客各编写一段程序来描述他们行为，并用wait和signal原语操作实现其同步。睡眠理发师问题Processcustomer{

P(seat);

V(customers);//向理发师发信号wait_for_haircut();

}睡眠理发师问题方法1Varcustomers,seat:Semaphore:=0,5Processbarber{While(1){P(customers);//接收顾客信号Cut_hair();V(seat);}}Processcustomer{

P(seat);

V(customers);//向理发师发信号P(barbers);//接收理发师信号

V(seat);Get_haircut();}睡眠理发师问题方法2Varcustomers,barbers,seat:Semaphore:=0,0,5Processbarber{While(1){P(customers);//接收顾客信号V(barbers);//向顾客发信号Cut_hair();}}Processcustomer{P(mutex);If(waiting<CHAIRS)then{waiting=waiting+1;V(customers);//向理发师发信号V(mutex);P(barbers);//接收理发师信号Get_haircut();}else{V(mutex);}}睡眠理发师问题方法3#defineCHAIRS=5Varcustomers,barbers,mutex:Semaphore:=0,0,1intwaiting=0;Processbarber{While(1){P(customers);//接收顾客信号P(mutex);waiting=waiting-1;V(barbers);//向顾客发信号V(mutex);Cuthair();}}类似问题：吸烟者问题（1971,Patil）：在一个房间内有三位吸烟者、一位材料供应者。其中：

a)吸烟者：需要拥有三种材料“烟草（Tobacco）、卷烟纸（Cigarette-paper）、火柴（Match）”才能吸烟：

第一位吸烟者有丰富的烟草；

第二位吸烟者有丰富的卷烟纸；

第三位吸烟者有丰富的火柴；

;当吸烟者拿到所需要的材料后，唤醒供应者进行下一次投放；

b)材料供应者：不吸烟，且有丰富的Tobacco、Cigarette-paper、Match三种材料；

每次随机地将三种材料中的两种投放到桌子上；

允许拥有另一种材料的吸烟者吸烟。

【要求】编写算法用信号量和P、V操作实现它们之间的同步关系。用信号灯及P、V操作来描述右图1、说明进程的同步关系：2、设置信号灯，说明含义、初值。3、写出程序描述（用P、V操作描述P1、P2、P3）。主函数如下：main(){ints13=0,s23=0;cobeginp1;p2;p3;coend}两个并发执行的进程A和B的程序如下：

进程A

Repeat

N=N+5;

Untilfalse;

进程B

Repeat

打印N的值；

N=0；

Untilfalse;

其中N为整数，初值为4。若进程A先执行了三个循环后，进程A和进程B又并发执行了一个循环，写出可能出现的打印值。正确的打印值应该是多少？请用P、V操作进行管理，使进程A和B并发执行时不会出现与时间有关的错误。答：因为N初值为4，若进程A先执行了三个循环，此时N的值为19。当进程A和进程B并发执行时可能会有如下两种执行次序，即进程A先执行一次循环，然后再进程B执行一次循环，此时打印的是正确值24，执行后N中的值为0。但若进程B先执行一次循环，然后再进程A执行一次循环，则打印的值是19，执行后N中的值是5。这是错误的，即发生了与时间有关的错误。用P、V操作进行管理，使进程A和B并发时不会出现与时间有关的错误的程序如下：（S为互斥信号量，初值为1），

进程A

Repeat

P(S);

N=N+5;

V(S);

Untilfalse;

进程B

Repeat

P(S);

打印N的值；

N=0；

V(S);

Untilfalse;假定在单道批处理环境下有5个作业，各作业进入系统的时间和估计运行时间如下表所示：（1）如果应用先来先服务的作业调度算法，试将下面表格填写完整。（2）如果应用最短作业优先的作业调度算法，试将下面表格填写完整。

作业

进入系统时间

估计运行时间/分钟

开始时间

结束时间

周转时间/分钟1

8:00

402

8:20

303

8:30

124

9:00

18

5

9:10

5作业

进入系统时间

估计运行时间/分钟

开始时间

结束时间

周转时间/分钟

1

8:00

40

8：00

8：40

40

2

8:20

30

8：40

9：10

50

3

8:30

12

9：10

9：22

52

4

9:00

18

9：22

9：40

40

5

9:10

5

9：40

9：45

35作业平均周转时间T=43.4

217作业

进入系统时间

估计运行时间/分钟

开始时间

结束时间

周转时间/分钟

1

8:00

40

8：00

8：40

40

2

8:20

30

8：52

9：22

62

3

8:30

12

8：40

8：52

22

4

9:00

18

9：27

9：45

45

5

9:10

5

9：22

9：27

17作业平均周转时间T=37.2

186进程调度问题：就绪队列中有4个进程P1，P2，P3，P4同时进入就绪队列，它们进入就绪队列10秒之后开始进程调度，它们需要的处理器时间如表所示。进程处理器时间（秒）进程处理器时间（秒）P1P21015P3P445忽略进行调度等所花费的时间，且进程执行过程中不会发生阻塞，请回答下列问题：分别写出采用时间片轮转调度算法（时间片为4秒）、响应比高者优先调度算法选中进程执行的次序。在单机系统中，系统中各个进程到达就绪队列的时刻、执行时间和优先级如下表所示。假设进程的调度时间忽略不计。请分别给出采用下面不同的进程调度算法时各个进程的调度次序，画出执行时间图，并计算平均周转时间、平均带权周转时间。进程到达就绪队列的时刻执行时间（ms）优先级P1033P2265P3441（高）P4652P5824（1）先来先服务调度算法；（2）时间片轮换调度算法（时间片为1ms）；（3）抢占式短进程优先调度算法；（4）抢占式优先级调度算法；（5）非抢占式优先级调度算法。

例1：系统中有五个进程P1、P2、P3、P4、P5，有三种类型的资源：R1、R2、和R3。在T0时刻系统状态如表所示。若采用银行家算法实施死锁避免策略，回答下列问题：（1）T0时刻是否为安全状态？为什么？（2）若这时P4请求资源（1，2，0），是否能实施资源分配？为什么？（3）在上面的基础上，若进程P3请求资源（0，1，0），是否能实施资源分配？为什么？

T0时刻系统状态如下所示：已分配资源数量最大资源需求量

R1R2R3R1R2R3P1001001P2200275P3003665P4115435P5033065

R1R2R3剩余资源数330解：（1）T0时刻是安全的，安全序列为：P1，P4，P5，P2，P3（2）P4请求资源（1，2，0），根据银行家算法，预分配后系统是安全的，安全序列为：P1，P4，P5，P2，P3（3）P3请求资源（1，1，0），根据银行家算法，预分配后系统不安全，所以不能实施资源分配。

设系统中有3种类型的资源A、B、C和5个进程P0、P1、P2、P3、P4，A资源的数量为10，B资源的数量为5，C资源的数量为7。在T0时刻系统状态如下表所示。系统采用银行家算法实施死锁避免策略。 MaxAllocationNeedAvailableABCABCABCABCP0P1P2P3P4753010743332322200122902302600222211011433002431（1）T0时刻是否为安全状态？若是，请给出安全序列。（2）在T0时刻若进程P1发出资源请求Request（1，0，2），是否能够实施资源分配？（3）在②的基础上P4发出资源请求Request（3，3，0），是否能够实施资源分配？（4）在③的基础上P0发出资源请求Request（0，2，0），是否能够实施资源分配?（二）、内存管理计算一个进程的大小占5个页面，每页的大小为1K，系统为它分配了3个物理块。当前进程的页表如图所示：块号 存在位P访问位R修改位M0x1C1100x3F111-0000x5D100-000（1）有那些页面不在内存？（2分）（2）请分别计算进程中虚地址为0x3B7、0x12A5、0x1432单元的物理地址（用十六进制表示），并说明理由。（6分）解：（1）不在内存的是2和4页（按页号），或第3和5页（按序号）。（2）0x3B7的物理地址=0x73B70x12A5的物理地址=0x176A5，缺页，换出第三页。0x1432地址越界，出错。在一分页存储管理系统中，逻辑地址长度为16位，页面大小为4096字节，现有一逻辑地址为2F6AH，且第0、1、2页依次存放在物理块5、10、11中，问相应的物理地址为多少？根据如下段表：

段号

基地址

长度

合法（0）/非法（1）

0

300

200

1

7500

540

2

3000

1010

3

2000

100（1）求出逻辑地址为0，100的物理地址并将其的合法性填入上表适当位置；（2）求出逻辑地址为3，100的物理地址并将其的合法性填入上表适当位置；(1)答：物理地址为：300+100=400(2)答：物理地址为：2000+100=2100

段号

基地址

长度

合法（0）/非法（1）

0

300

200

0

1

7500

540

2

3000

1010

3

2000

100

1给定下面的段表，已知下面的逻辑地址(其中方括号中的第一个元素为段号，第二个元素为段内地址)求其对应的物理地址：(1)[0,430]；(2)[3,400]；(3)[l,10]；(4)[2,2500]；(5)[4,42]；(6)[1,11]。段号段长段首地址06002191142300210090358013274961954在一个请求分页系统中，采用LRU页面置换算法时，假如一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5，当分配给该作业的物理内存块数M分别为3和4时，分别计算在访问过程中所发生的缺页次数和缺页率，并画出页面置换图。

当M=3时，缺页次数为10次，缺页率为10/12=0.83=83%。当M=4时，缺页次数为8次，缺页率为8/12=0.66=66%。某程序在逻辑地址100处有一条取数指令LOADl，500，而500单元内存放数据51888。假设程序被分配到内存起始地址5000单元时，试用图示意，采用下述各种方式下的该指令及数据地址的物理地址及相应地址的变换过程。(1)静态重定位。(2)采用重定位寄存器实现动态重定位。(3)采用页表映像(映射)方式，假定页面大小为100单元，其负表各页映射到50，51、52，53，54，55，…，59物理页上。对于一个使用快表的页式虚存，设快表的命中率为70%，内存的存取周期为1ns；缺页处理时，若内存有可用空间或被置换的页面在内存未被修改过，则处理一个缺页中断需8000ns，否则需20000ns。假定被置换的页面60%是属于后一种情况，为了保证有效存取时间不超过2ns，问可接受的最大缺页率是多少？答：设可接受的最大缺页率位p，则有1ns×0.7+2ns×(1-0.7-p)+0.4p×8000ns+0.6p×20000ns=2ns即

0.7+0.6-2p+3200p+12000p=2

15198p=0.7

P=0.000046在分页存储管理系统中，存取一次内存的时间是8ns，查询一次快表的时间是1ns，缺页中断的时间是20ns。假设页表的查询与快表的查询同时进行，当查询页表时，如果该页在内存但快表中没有页表项，系统将自动把该页页表项送入快表。一个作业最多可保留3个页面在内存。现在开始执行一作业，系统连续对作业的2，4，5，2，7，6，4，8页面的数据进行一次存取，如分别采用FIFO算法和最优页面置换算法，求每种上存取这些数据需要的总时间。答：（1）FIFO

第2页面：20＋8×3

第4页面：20＋8×3

第5页面：20＋8×3

第2页面：8＋1

第7页面：20＋8×3

第6页面：20＋8×3

第4页面：20＋8×3

第8页面：20＋8×3

因此总的时间是（20＋8×3）×7＋（8＋1）ns(2)最优页面置换

第2页面：20＋8×3

第4页面：20＋8×3

第5页面：20＋8×3

第2页面：8＋1

第7页面：20＋8×3

第6页面：20＋8×3

第4页面：8＋1

第8页面：8＋1

因此总的时间是（20＋8×3）×5＋（8＋1）×3ns在某分页系统中，测得CPU和磁盘的利用率如下，试指出每种情况下的问题和措施。（1）CPU的利用率为15%，磁盘利用率为95%。（2）CPU的利用率为88%，磁盘利用率为3%。（3）CPU的利用率为13%，磁盘利用率为5%。答：在某分页虚存系统中，在题中的CPU和磁盘的利用率的情况下，出现的问题和应采取的措施如下：（1）可能已出现了抖动现象，应减少系统的进程数。（2）系统比较正常，可考虑适当增加进程数以提高资源利用率。（3）CPU和磁盘的利用率都较低，必须增加并发进程数。考虑一个有快表的请求分页系统，设内存的读写周期为1ns，内外存之间传送一个页面的平均时间为5000ns，快表的命中率为80%，页面失效率为10%，求内存的有效存取时间。答：内存的有效存取时间EAT(EfficentAccessTime)也叫平均存取时间AAT(AverageAccessTime)，其计算公式如下：EAT＝1ns×80%+2ns×10%+(5000ns+2ns)×10%=0.8ns+0.2ns+500.2ns=501.2ns一台计算机有一个Cache、内存储器和用作虚拟存储器的磁盘，假设访问Cache中的字需要20ns的定位时间；如果该字在内存储器中而不在Cache中，则需要60ns的时间载入Cache，然后在重新开始定位；如果该字不在内存储器中，则需要12ms的时间从磁盘中提取，然后需要60ns复制到Cache中，然后在定位。Cahce的命中率为0.9，内存储器的命中率为0.6，在该系统中访问一个被定位的字需要的平均时间是多少ns？（三）、外设管理计算三、磁盘访问时间：1.寻道时间：TS=m*n+sm：常量，n：磁道数，s：磁盘启动时间。2.旋转延时间Tr（平均旋转延迟时间）：指定扇区旋转到磁头下所需时间。设每秒r转，则Tr＝1/(2r)（均值）3.数据传输时间:Tt＝b/(rN)b：每次读/写字节数N：每道上的字节数访问时间：Ta=Ts+1/(2r)+b/(rN)可见，由于特定磁盘，只有集中放数据，集中读写（b的值大）才能更好提高传输效率。寻道时间:20ms，磁盘通道传输速率:1MB/s，转速r=3600rpm，每扇区512字节，每磁道32扇区。目标：读128k数据，问：访问时间为多少？因为：60*16kB=960kB/s<1MB/s顺序组织(20＋8.33＋16.67)＋(8.33＋16.67)×7＝220(ms)随机组织(20＋8.33＋0.52)×256＝7385.6(ms)其中：3600转/分=60转/秒，0.5KB*32=16KB/道其中：1/r=1/60≈16.67ms/转，均值=1/(2r)≈8.33ms/转；128KB/16KB=8其中：Tt＝b/(rN)=0.5KB/(60*16KB)≈0.52(ms),128KB/0.5KB=256某磁盘组有6片盘片，每片有两个记录面，存储区域内径为22cm，外径为33cm，道存储密度为40道/cm，内层位存储密度为400b/cm，转速为3000r/min（转/分），问共有多少柱面？盘组总存储量为多少？平均等待时间为多少？假定磁盘转速为6000r/min（转/分），磁盘格式化时每个盘面被分为9个扇区，现有一个文件共有 A，B，C，D，E，F，G，H，I九个逻辑记录要存放在同一磁道上供处理程序使用，假设每个记录的大小与扇区的大小相同，处理程序每次从磁盘读出一个记录后要花2.5ms处理时间。若忽略其他辅助时间，请回答下列问题：（1）现在假设已经顺序存放好这9个记录，那么读出该文件需要多少时间？（2）为了使读出文件需要的时间最短，请重新调整各个记录的存放位置，画出各个记录的存放位置，计算该文件的读出时间，并与（1）进行比较说明。假设计算机系统采用CSCAN(循环扫描)磁盘调度策略,使用2KB的内存空间记录16384个磁盘的空闲状态(1)、请说明在上述条件如何进行磁盘块空闲状态的管理。

(2)、设某单面磁盘的旋转速度为每分钟6000转，每个磁道有100个扇区，相临磁道间的平均移动的时间为1ms。若在某时刻，磁头位于100号磁道处，并沿着磁道号增大的方向移动，磁道号的请求队列为50，90，30，120对请求队列中的每个磁道需读取1个随机分布的扇区，则读完这个扇区点共需要多少时间？需要给出计算过程。假设一个可移动磁头的磁盘具有200个磁道，其编号为0～199，当它刚刚结束了125道的存取后，现正在处理143道的服务请求，假设系统当前I/O请求序列以FIFO顺序排列如下：86，147，91，177，94，150，102，175，130。试问对以下几种磁盘I/O请求调度算法而言，满足以上请求序列，磁头将分别如何移动，请列出磁道访问次序，并计算出移动距离？假设有一个磁盘组共有100个柱面，每个柱面上有8个磁道，每个盘面被分成8个扇区。现有一个含有6400逻辑记录的文件，逻辑记录的大小与扇区一致，该文件以顺序结构的形式被存储到磁盘上。柱面、磁道、扇区的编号从“0”开始，逻辑记录的编号也从“0”开始。文件信息从0柱面、0磁道、0扇区开始存放，试问：（1）该文件的3680个逻辑记录应该存放在什么位置？（2）78柱面