操作系统应用题2(解答)

解：

①系统可设三个进程来完成这个任务：R进程负责从卡片输入机上读入卡片信息，输入到缓冲区B1中；C进程负责从缓冲区B1中取出信息，进行加工处理，之后将结果送到缓冲区B2中；P进程负责从缓冲区B2中取出信息，并在打印机上印出。

②R进程受C进程影响，B1放满信息后R进程要等待——等C进程将其中信息全部取走，才能继续读入信息；C进程受R进程和P进程的约束：B1中信息放满后C进程才可从中取出它们，且B2被取空后C进程才可将加工结果送入其中；P进程受C进程的约束：B2中信息放满后P进程才可从中取出它们,进行打印。 ③信号量含义及初值：

B1full—— 缓冲区B1满，初值为0；（B1full＝1表示B1满） B1empty——缓冲区B1空，初值为1；（B1empty＝1表示B1空） B2full—— 缓冲区B2满，初值为0；（B2full＝1表示B21满） B2empty——缓冲区B2空，初值为1；（B2empty＝1表示B2空）

R进程 C进程 P进程 P( B1empty) 输入信息写入B1 V(B1full)

2、现有一个作业，在段式存储管理的系统中已为其主存分配，建立的段表内容如下： 段号 0 1 2 3 主存起始地址（段基址） 120 760 480 370 段长度 40 30 20 20 P(B1full) P(B2empty) 取B1送入B2 V(B1empty) V(B2full) P(B2full) 从B2中取出信息进行打印 V(B2empty) 计算逻辑地址（2，15），（0，60），（3，18）的绝对地址是多少？ 注：括号中第一个元素为段号，第二个元素为段内地址。

解：

段式存储管理的地址转换过程为：（1）根据逻辑地址中的段号查段表的相应栏目；（2）根据段内地址<段长度，检查地址是否越界；（3）若不越界，则绝对地址=该段的主存起始地址+段内地址。

逻辑地址（2，15）查段表得段长度为20，段内地址15<20，地址不越界，段号2查表得段首地址为480，于是绝对地址为480+15=495。

逻辑地址（0，60）查段表得段长度为40，段内地址60>40，地址越界，系统发出“地址越界”中断。

逻辑地址（3，18）查段表得段长度为20，段内地址18<20，地址不越界，段号3查表得段首地址为370，于是绝对地址=370+18=388。

3．若干个等待访问磁盘者依次要访问的柱面为20，44，40，4，80，12，76，假设每移动一个柱面需要3毫秒时间，移动臂当前位于40号柱面，请按下列算法分别计算为完成上述各次访问总共花费的寻找时间。 （1）先来先服务算法； （2）最短寻找时间优先算法。

解（1）3毫秒×292=876毫秒 （2）3毫秒×120=360毫秒 （注：各算法使移动臂的移动次序和移动的柱面数如下： （1）40 → 20 → 44 → 40 → 4 → 80 → 12 → 76

（20） （24）（4） （36） （76）（68） （） 共移动292柱面 （2）40 → 44 → 20 → 12 → 4 → 76 → 80

（4） （24）（8） （8） （72）（4） 共移动120柱面

4．某系统中有10台打印机，有三个进程P1，P2，P3分别需要8台，7台和4台。若P1，P2，P3已申请到4台，2台和2台。试问：按银行家算法能安全分配吗？请说明分配过程。

解：系统能为进程P3分配二台打印机。因为尽管此时10台打印机已分配给进程P1 4台，P22台和P34台，全部分配完，但P3已分配到所需要的全部4台打印机，它不会对打印机再提出申请，所以它能顺利运行下去，能释放占用的4台打印机，使进程P1，P2均可能获得乘余的要求4台和5台，按银行家算法是安全的。

5．用PV操作解决读者写者问题的正确程序如下： begin S, Sr: Semaphore; rc: integer; S:=1; Sr:=1; rc:=0;

cobegin PROCESS Reader i ( i=1,2…) begin P(Sr) rc:=rc+1;

if rc=1 then P(S); V(Sr); read file; P(Sr); rc:=rc-1

if rc=0 thenV(S); V(Sr); end ;

PROCESS Writer j (j=1,2…) begin P(S);

Write file; V(S)

end; coend ; end;

请回答：（1）信号量 Sr的作用；（2）程序中什么语句用于读写互斥，写写互斥；（3）若规定仅允许5个进程同时读怎样修改程序？

解（1）Sr用于读者计数rc的互斥信号量；

（2）if rc=1 then P（S）中的P（S）用于读写互斥，写者进程中的P（S）用于写写互斥，读写互斥。

（3）程序中增加一个信号量S5，初值为5，P（S5）语句加在读者进程P（Sr）之前，V（S5）语句加在读者进程第2个V（Sr）之后。

6. 判断下面的同步问题的算法是否正确？若有错，请指出错误原因并予以改正。

设A、B两进程共用一个缓冲区Q，A向Q写入信息，B则从Q读出信息，算法框图如图所示。

进程A 进程B

向Q写入信息 P(S) V(S) 从Q读出信息

注：信号量S的初值为0

解：这个算法不对。

因为A、B两进程共用一个缓冲区Q，如果A先运行，且信息数量足够多，那么缓冲区Q中的信息就会发生后面的冲掉前面的，造成信息丢失，B就不能从Q中读出完整的信息。 进行改正：

A、 B两进程要同步使用缓冲区Q。为此，设立两个信号量： empty表示缓冲区Q为空，初值为1； full表示缓冲区Q为满，初值为0。 算法框图如图所示。

A进程 B进程

P(empty) P(full) 向Q写入信息 从Q中读出信息 V(full) V(empty)

7.有三个用户进程A、B和C，在运行过程中都要使用系统中的一台打印机输出计算结果。 (1) 试说明A、B、C进程之间存在什么样的制约关系？

(2) 为保证这三个进程能正确地打印出各自的结果，请用信号量和P、V操作写出各自的有关申请、使用打印机的代码。要求给出信号量的含义和初值。 解：

(1) A、B、C三个进程之间存在互斥的制约关系。因为打印机属于临界资源，必须一个进程使用完之后另

一个进程才能使用。

（2）mutex：用于互斥的信号量，初值为1。 各进程的代码如下 ：

进程A 进程B 进程C ... … ... ... … ... P(mutex) P(mutex) P(mutex) 申请打印机 申请打印机 申请打印机 使用打印机 使用打印机 使用打印机 V(mutex) V(mutex) V(mutex) … … …

8. 假定在某移动臂磁盘上，刚刚处理了访问75号柱面的请求，目前正在80号柱面读信息，并且有下述请求序列等待访问磁盘：

请求序列： 1 2 3 4 5 6 7 8 欲访问柱面号： 160 40 190 188 90 58 32 102

试用：(1)电梯调度算法

(2)最短寻找时间优先算法 分别列出实际处理上述请求的次序。

解(1)电梯调度算法:由”刚刚处理了访问75号柱面的请求，目前正在80号柱面读信息”可知:初始磁头前进的方向是:”从小到大”

所以:处理次序为：

5 8 1 4 3 6 2 7 90 102 160 188 190 58 40 32 (2)最短寻找时间优先算法:

处理次序为：

5 8 6 2 7 1 4 3

90 102 58 40 32 160 188 190

9. 有三个进程P1，P2和P3并发工作。进程P1需用资源S3和S1；进程P2需用资源S1和S2；进程P3需用资源S2和S3。回答：

(1)若对资源分配不加，会发生什么情况?为什么?

(2)为保证进程正确工作，应采用怎样的资源分配策略?为什么? 解：

(1)可能会发生死锁

例如：进程P1，P2和P3分别获得资源S3，S1和S2后再继续申请资源时都要等待，这是循环等待。 (或进程在等待新源时均不释放已占资源) (2)可有几种答案： A.采用静态分配

由于执行前已获得所需的全部资源，故不会出现占有资源又等待别的资源的现象(或不会出现循环等待资源现象)。

或B.采用按序分配 不会出现循环等待资源现象。

或C.采用银行家算法 因为在分配时，保证了系统处于安全状态。

10. 某车站售票厅，任何时刻最多可容纳20名购票者进入，当售票厅中少于20名购票者时，则厅外的购票者可立即进入，否则需在外面等待。若把一个购票者看作一个进程，请回答下列问题：

(1)用PV操作管理这些并发进程时，应怎样定义信号量，写出信号量的初值以及信号量各种取值的含义。 (2)根据所定义的信号量，把应执行的PV操作填入下述方框中，以保证进程能够正确地并发执行。 COBEGIN PROCESS PI(I=1，2，……) begin ； 进入售票厅；

购票； 退出；

end；

COEND

(3)若欲购票者最多为n个人，写出信号量可能的变化范围(最大值和最小值)。

解(1)定义一信号量S，初始值为20。 意义：

S>0 S的值表示可继续进入售票厅的人数 S=0 表示售票厅中已有20名顾客(购票者) S<0 |S|的值为等待进入售票厅的人数 (2)上框为P(S) 下框为V(S)

(3)S的最大值为20 S的最小值为20－n

注：信号量的符号可不同(如写成t)，但使用时应一致(即上述的s全应改成t)。

11． 有两个进程P1和P2，它们执行的过程如下：

P1: 10秒CPU操作、20秒I/O操作（设备1）、5秒CPU操作、10秒I/O操作（设备2）、5秒CPU操作、结束

P1: 15秒I/O操作（设备1）、10秒CPU操作、15秒I/O操作（设备2）、10秒CPU操作、结束 （1） 如果进程P1和P2顺序执行，请画出进程P1和P2执行情况图； （2） 如果进程P1和P2并发执行，请画出进程P1和P2执行情况图；

（3） 分别计算在（1）和（2）情况下，CPU的利用率、设备1和设备2的利用率。 解：

(1) P1和P2顺序执行 P1: ` CPU I/O(DEV1) CPU I/O(DEV2) CPU 0 10 30 35 45 50 P2: I/O(DEV1) CPU I/O(DEV2) CPU 50 65 75 90 100

(2) P1和P2并发执行 CPU(P1) CPU(P2) CPU(P1)CPU(P2) CPU(P1) I/O(DEV1)(P2) I/O(DEV1)(P1) I/O(DEV2)(P2) I/O(DEV2) 0 10 15 25 35 40 50 55 (3) 在情况（1）下，CPU的利用率=40/100=40% 设备1的利用率=35/100=35% 设备2的利用率=25/100=25%

在情况（2）下，CPU的利用率=40/55=73% 设备1的利用率=35/55=% 设备2的利用率=25/55=45%

12．一个程序P的用户空间为16K,存储管理采用请求式分页系统，每个页面大小为2K，存在以下的页表：

页框号 12 3 0 0 2 15 0 8 有效位 1 1 1 0 1 1 0 1 其中，有效位＝1表示页面在内存；0表示页面不在内存。

请将虚地址0x060C，0x1502，0x1d71，0x2c27，0x4000转换为物理地址。

答：用户地址空间共用14bit表示.范围为:0x0000~0x3FFF.超过这个范围即为”越界”

0x060C：1548+12*2048=0x660C 0x1502：0x6502 0x1d71：缺页 0x2c27：0x1427 0x4000：越界

13．有一个文件系统，根目录常驻内存，目录文件采用链接式，每个磁盘块存放10个下级文件的描述，最多存放40个下级文件(最多涉及到4个盘块)，若下级文件为目录文件，则上级目录指向该目录文件的第一块，否则指向普通文件的文件控制块。普通文件采用二级索引形式，文件控制块中给出12个磁盘块地址，前10个磁盘块地址指出前10页的物理地址，第11个磁盘块地址指向一级索引表，一级索引表给出256个磁盘块地址，即指出该文件第10页至第256页的地址，第12个磁盘块地址指向二级索引表，二级索引表中指出256个一级索引表的地址。(1) 该文件系统中的普通文件最大可有多少页?

(2) 若要读文件/A/D/K/Q中的某一页, 最少要启动磁盘几次? 最多要启动磁盘几次? 答：（1）一个文件的所有块可以通过下面三种途径找到：直接通过FCB找到前10块，通过一级索引找到256块，通过二级索引找到256*256块，所以一个文件最大可以有10+256+2562块

最坏情况是：每次读取目录描述信息的时候都在最后一个块找到下级的目录或文件

，所以要找到Q文件的

FCB至少要读取A的第一块，D、G、二个目录项的所有四个块，再读取Q的FCB，总共要1+4*2+1＝10次启动硬盘。找到FCB后再读取该文件页所在的块，如果这一块在前10块之列，那么在启动一次硬盘就可以找到这一块，如果这一块在最后一块，则可能需要通过二级索引找到这一块，这总共需要读取二级索引和最后一块共2+1次读取硬盘。

14.一个系统中存在某类资源m个，被n个进程共享。资源的分配和释放必须一个一个进行，请证明在以下两个条件下不会发生死锁：

 每个进程需要资源的最大数在1~m之间；  所有进程需要的资源总数小于m+n；

证明：

假设进程Pi(0假设进程已经分配到的资源为Ai(0假设当前发生了死锁，则 A1+A2+….+An=m AiAi+1<=Ri 则

A1+A2+….+An+n<=R1+R2+….+Rn 即

m+n<=R1+R2+….+Rn

和（1）矛盾，死锁不成立。

15．一个请求式分页存储系统，页表存放在内存：  访问一次内存需要100ns

 如果仅调入一个页面，需要花费8ms（内存有空页面，或需要进行页面置换，单被置换的页面没有修改过）；  如果调入一个页面同时需要进行被置换页面的写出，则需要20ms;  假设页面被修改的比例是60%;

请问，缺页率必须控制在多少以下，才能使得EAT<200ns? 解：

假设缺页率为f_rate,

则，

EAT=(1-f_rate)*100+f_rate*(40%*8000+60%*20000) 如EAT<200, 则，

(1- f_rate)*100+f_rate*(40%*8000+60%*20000)<200 100-100*f_rate+15200*f_rate<200 151*f_rate<1 f_rate<1/151 即缺页率小于0.66%。

16．一个文件有100个磁盘块，假设文件控制块在内存（如果文件采用索引分配(indexed allocation)，索引表也在内存）。在下列情况下，请计算在contiguous, linked, indexed(single-level)三种分配方式下，分别需要多少次磁盘I/O操作？（每读出或写入一个磁盘块都需要一次磁盘I/O操作）(10%)

假设在contiguous分配方式下，文件头部无空闲的磁盘块，但文件尾部有空闲的磁盘块。假设要增加的块信息存放在内存中。

 在文件开始处添加一个磁盘块；  在文件结尾处添加一个磁盘块；  在文件中间删除第50块磁盘块；（假设磁盘块编号从0—99）

 在文件第50块前添加一个磁盘块； （假设磁盘块编号从0—99） 解：

 在文件开始处添加一个磁盘块：连续：201/链接：1/索引：1  在文件结尾处添加一个磁盘块：连续：1/链接：101/索引：1

 在文件中间删除一个磁盘块：连续：48*2＋1＋1=98/链接：52/索引：0  在文件中间添加一个磁盘块：连续：101/链接：52/索引：1

17.一个操作系统有20个进程，竞争使用30个同类资源，申请方式是逐个进行，一旦某个进程获得了它的全部资源，就马上归还所有的资源，每个进程最多使用30，最少使用一个资源。20个进程需要的资源总数小于50。如果仅考虑这类资源，系统会产生死锁吗？请说明理由。

答：

设max(i)表示第i个进程的最大资源需求量，

need(i)表示第i个进程还需要的资源量， alloc(i)表示第i个进程已分配的资源量。 由题中所给条件可知：

max(1)+…+max(20)=(need(1)+…need(20))+(alloc(1)+…+alloc(20))<50

如果在这个系统中发生了死锁，那么一方面30个资源R应该全部分配出去，即（反证法）alloc(1)+…+alloc(20)=30

另一方面所有进程将陷入无限等待状态。

由上述两式可得：need(1)+…+need(20)<20（关键）

上式表示死锁发生后，20个进程还需要的资源量之和小于20，这意味着此刻至少存在一个进程i，need(i)=0，即它已获得了所需要的全部资源。既然该进程已获得了它所需要的全部资源，那么它就能执行完成并释放它占有的资源，这与前面的假设矛盾，从而证明在这个系统中不可能发生死锁。

18. 一个分页存储系统，页表存放在内存：

 如果访问一次内存需要200ns，则访问一个内存单元需要多少时间？  如果系统采用三级页表，则访问一个内存单元需要多少时间？

 如果系统引入联想寄存器，90％的页表项可以在快表中命中，则访问一个内存单元需要多少时间？（假设访

问一次快表需要10ns） 解：

1、 400 ns(200ns+200ns)(访问页表＋访问具体内存单元)

2、 800 ns（3×200ns+200ns）(访问3级页表＋访问具体内存单元)

3、 229 ns[（90%×10+10%×200）+200ns] (访问页表的平均时间＋访问具体内存单元)

18. 设某文件的物理存储方式采用链接方式，该文件由5个逻辑记录组成，每个逻辑记录的大小与磁盘块大小相等，均为512字节，并依次存放在50、121、75、80、63号磁盘块上。（10分）  文件的第1569逻辑字节的信息存放在哪一个磁盘块上？

 要访问第1569逻辑字节的信息，需要访问多少个磁盘块？（假如该文件的FCB在内存） 答：

因为：1569=512×3+33

所以要访问字节的逻辑记录号为3，对应的物理磁盘块号为80。故应访问第80号磁盘块。

由于采用链接方式，所以要访问第3个逻辑记录的信息，必须访问逻辑记录第0、1、2后，才能访问第3个逻辑记录，所以要访问第1569逻辑字节的信息，需要访问4个磁盘块。