操作系统大题全集.docx
《操作系统大题全集.docx》由会员分享，可在线阅读，更多相关《操作系统大题全集.docx（28页珍藏版）》请在冰点文库上搜索。
操作系统大题全集
2．进程A1，A2，．．．，Anl通过m个缓冲区向进程B1，B2，．．．，Bn2不断地发送消息，发送和接收工作遵循如下规则：
（1）每个发送进程一次发送一个信息，写入一个缓冲区，缓冲区大小与消息长度一样；
（2）对每一个消息，B1，B2，．．．，Bn2都需各接收一次，读入各自的数据区；
（3）m个缓冲区都满时，发送进程等待，没有可读的消息时，接收进程等待。
试用P、V操作组织正确的发送和接收操作。
解答：
这是一个变形的生产和消费问题。
每个缓冲区只需写一次，但需读n2次。
可以把一组缓冲区看做n2组缓冲区，这样，每个生产者需要同时写n2个缓冲区组中相应的n2个缓冲区，而每一个消费者只需读它自己对应的那组缓冲区中的单元。
生产者须在n2个缓冲区都为空闲是方可写入，这时，就可以用n2组信息量（avail,free）来实现这一流程，具体流程如下：
BEGIN
integermutex,avail[n2],full[n2];
integerI;
mutex:
=1;
forI:
=1ton2do
begin
avail[I]:
=m;
full[I]:
=0;
end;
proceduresend[M]
integerI;
begin
forI:
=1ton2do
begin
P（avail[I]）;
end;
P（metux）;
将消息放入缓冲区;
forI:
=1ton2do
begin
V（full[I]）;
end;
V（metux）
end;
procedurereceive（M,I）
begin
P（full[I]）;
P（metux）;
从缓冲区中取消息;
V（avail[I]）;
V（mutex）;
end;
Cobegin
Ai:
begin
……..
send[M]
………
end
Bi;begin
…….
Receive（M,i）;
………
end;
Coend;
end;
3．设系统中仅有一类数量为M的独占型资源，系统中有N个进程竞争该类资源，其中各进程对该类资源的最大需求数为W，当M，N，W分别取下列值时，试判断哪些情况会发生死锁，为什么？
（1）M=2，N=2，W=1
（2）M=3，N=2W=2
（3）M=3，N=2，W=3
（4）M=5N=3W=2
（5）M=6N=3W=3
解答：
（1）不会发生死锁。
因为系统中只有两个进程，每个进程的最大需求量为1，
且系统中资源总数为2，系统能够满足两个进程的最大资源需求量，故不会发生死锁。
（2）不会发生死锁。
因为系统中有两个进程，每个进程的最大资源需求量为2，
且系统中资源总数为3，无论如何分配，两个进程中必有一个进程可以获得两个资源，该进程将顺利完成，从而可以将分配给它的资源归还给系统，使另一个进程也能顺利执行完成，故不会发生死锁。
（3）可能发生死锁。
因为系统中有两个进程，每个进程的最大资源需求量为3，
且系统中资源总量为3，若系统先将全部资源分配给其中一个过程，则该进程将顺利完成，从而可将分配给它的资源归还给系统，使另一进程也能顺利完成，以这种方式分配资源时不会发生死锁；若系统将两个资源分配给一个过程，而剩余的一个资源分配给另一个进程，则系统中没有空闲资源，而每个进程都需要等待资源，此时发生死锁。
（4）不会发生死锁。
因为系统中有3个过程，每个进程的最大资源需求量为2，
且系统中资源总量为5，无论如何分配，3个进程中必有一个进程可以获得2个资源，该进程将顺利完成，从而可以将分配给它的资源归还给系统，使其他进程也能顺利执行完成，故不会发生死锁
（5）可能会发生死锁。
因为系统中有3个进程，每个进程的最大资源需求量为
3，且系统中资源总数为6，若系统先将3个资源分配给其中一个过程，则该进程将顺利完成，从而可将分配给它的资源归还给系统，使其他进程也能顺利完成，以这种方式分配资源时不会发生死锁；若系统给每个进程分配两个资源，则系统中没有空间资源，而每个进程都需要等待一个资源，此时发生死锁。
4．设某作业占有7个页面，如果在主存中只允许装入4个工作页面（即工作集为4），作业运行时，实际访问页面的顺序是1，2，3，6，4，7，3，2，1，4，7，5，6，5，2，1。
试用FIFO与LRU页面调度算法，列出各自的页面淘汰顺序和缺页中断次数，以及最后留驻主存4页的顺序（假设开始的4个页面已装入主存）。
解答：
对ＦＩＦO算法 ：
页面淘汰顺序为１，２，３，６，４，７；
缺页中断６次；
最后留驻主存４页的顺序为：
２，１，５，6。
对ＬＲＵ 的算法；
页面淘汰顺序为１，２，６，４，７，３，２，１，４，７
缺页中断１０次；
最后留驻主存４页的概率：
６，５，２，１
注：
假定前面四页１，２，３，６ 已在主存
5．在某请求分页管理系统中，一个作业共５页，作业执行时依次访问如下页面：
１，４，３，１，２，５，１，４，２，１，４，５ 若分配给该作业的主存块数为３，分别采用ＦＩＦＯ，ＬＲＵ页面置换算法，试求出缺页中断的次数及缺页率。
解答：
（1）采用ＦＩＦＯ页面置换算法，
缺页中断的次数为９，缺页率9/１２＝７５％
（２）采用ＬＲＵ页面置换短法
缺页中断的次数为８，缺页率８／１２＝６７％
6．设存中有三道程序A，B，C，它们按A/B/C的优先次序执行，它们的计算和I/O操作的时间如表所1-1示（单位；MS）
表1-13道程序的操作时间
A
B
C
计算
20
40
10
I/O
30
20
30
计算
10
10
20
假设3道程序使用相同设备进行I/O操作，即程序以串行方式使用设备，试画出单道运行和多道运行的时间关系图（调度程序执行时间忽略不计）在两种情况下，完成这三道程序各要花多少时间？
解答：
若采用单道方式运行三道程序，则运行次序为A，B，C，即程序A先执行20MS的计算，再完成30MS的I/O操作。
最后在进行10MS的计算。
接下来程序B先执行40MS的计算，再完成20MS的I/O操作。
最后在进行10MS的计算。
然后程序C先执行10MS的计算，再完成30MS的I/O操作。
最后在进行20MS的计算。
至此，三到程序全部运行完毕，其程序运行的时间关系如图1-1所示总的运行时间为
20+30+10+40+20+10+10+30+20=190ms
I/O
计算
时间ms
0205060100120130140170190
A
A
A
B
B
B
C
C
C
若采用都道方式运行三道程序，因系统按照A，B，C的优先次序执行，则在运行
过程中，无论使用CPU还是I/O设备，A的优先级最高，B的优先级次之，C的优先级最低，即程序A先执行20MS的计算，再完成30MS的I/O操作（与此同时，程序B进行30MS的计算），最后在进行10MS的计算（此时程序B等待，因还继续10MS计算）：
接下来程序B先执行10MS的计算，再完成20MS的I/O操作（与此同时，程序C进行10MS的计算，然后等待I/O的设备），最后在进行10MS的计算（此时程序C执行I/O操作10MS）。
然后程序C先执行20MS的I/O操作，最后在进行20MS的计算。
至此，三到程序全部运行完毕，
其程序运行的时间关系如图1-2所示总的运行时间为
20+30+10+10+20+10+10+20+30=140ms
7．在大学和天津大学的之间有一条弯曲的小路，其中从S到T一段路每次只允许一辆自行车通过，但中间有一个小的安全岛M（同时允许两辆自行车停留），可供两辆自行车在以从两端进入小路情况下错车使用，如下图所示，试设计一个算法，使来往的自行车辆均靠顺利通过。
解答：
对于这一类问题，关键在于正确分析所需控制的对象、工作流程以及控制关系。
在这一问题中，根据从S到T路段的特点，可以把它分为3个小段：
从S到K，驶进安全岛M，从L到T。
路段S到K及L到T，只允许一辆自行车通过（即一个进程使用），而安全岛M允许两辆自行车通过（即两个进程使用）。
对它们分别用3个信号量来管理。
再注意到同时最多只能由一个方向的一辆自行车通过，因此每个方向的自行车还要用一个信号量来控制。
用bikeT_to_N和bikeN_to_T分别表示从天津大学到南开大学和从南开大学到天津大学两个方向的自行车。
控制流程如下：
Begin
Integer:
N_to_T,T_to_N,L,M,K;
N_to_T:
=1;T_to_N:
=1;L:
=1;M:
=2;K:
=1;
ProcedurebikeT_to_N（）
Begin
P（T_to_N）;
P（L）;
GothroughTtoL;
P（M）；
GointoM；
V（L）;
P（K）;
GothroughKtoS;
V（M）;
V（K）;
V（T_to_N）;
End;
ProcedurebikeN_to_T（）
Begin
P（N_to_T）;
P（K）;
GothroughStoK;
P（M）；
GointoM；
V（K）;
P（L）;
GothroughLtoT;
V（M）;
V（L）;
V（N_to_T）;
End;
End;
8．例：
在银行家算法中，若出现表2-4所示的资源分配情况，试问：
1．该状态是否安全？
2．如果进程P2提出请求Request2（1,2,2,2）后，系统能否将资源分配给它。
表2-4资源分配表
Allocation
Need
Available
ABCD
ABCD
ABCD
P0
0032
0012
1622
P1
1000
1750
P2
1354
2356
P3
0332
0652
P4
0014
0656
解答：
（1）利用银行家算法对此时刻的资源分配情况进行分析，可得表2-5所示的安全性分析情况。
表2-5安全性检查表
Work
Need
Allocation
Work+Allocation
Finish
ABCD
ABCD
ABCD
ABCD
P0
1622
0012
0032
1654
true
true
true
true
true
P3
1654
0652
0332
1986
P4
1986
1750
0014
19910
P1
19910
0656
1000
29910
P2
29910
2356
1354
3121414
从以上情况分析可以看出，此时存在一个安全序列{p0,p3,p4,p1,p2},故该状态是安全的。
（2）P2提出请求Request2（1,2,2,2）。
按银行家算法进行检查：
Request2（1,2,2,2）<=need（2,3,5,6）
Request2（1,2,2,2）<=available（1,6,2,2）
试分配并修改相应数据结构，资源分配情况如表2-6所示。
表2-6P2申请资源后的资源分配表
Allocation
Need
Available
ABCD
ABCD
ABCD
P0
0032
0012
0400
P1
1000
1750
P2
1354
1134
P3
0332
0652
P4
0014
0656
再利用安全性检查算法检查系统是否安全，可用资源available（0,4,0,0）已不能满足任何进程的需要，此时系统不能将资源分配给P2。
9．有桥如图2-7所示。
车流如箭头所示，桥上不允许两车交会，但允许同方向多辆车依次通行（即桥上可以有多个同方向的车）。
用P、V操作实现交通管理以防止桥上阻塞。
解答：
由于桥上不允许两车相会，故桥应该互斥访问，而同一方向上允许多辆车一次通过，即临界区允许多个实例访问。
用同一信号量来互斥访问临界区。
由于不能允许某一方向的车完全“控制桥”，应保证最多某一方向上连续通过一定数量的车后，必须让另一方向的车通过，可以通过3个信号量来控制。
具体程序如下：
Begin
Integer:
mutex,availn,abails;
Mutes:
=0;avialn:
=m;avails:
=m;
Cobegin
South:
begin
P（avails）;
P（mutex）;
过桥；
V（mutex）;
V（avails）;
End;
North:
begin
P（availn）;
P（mutex）;
过桥；
V（mutex）;
V（availn）;
End;
Coend;
End;
10．设系统中有三类资源A、B和C，又设系统中有5个进程P1，P2，P3，P4和P5.在T0时刻系统状态如下：
最大需求量已分配资源量剩余资源量
ABCABCABC
P1864121211
P2433311
P31013413
P4333322
P5546113
（1）系统是否处于安全状态？
如是，则给出进程安全序列.
（2）如果进程P5申请1个资源类A、1个资源类B和1个资源类C，能否实施分配？
为什么？
答案：
（1）
最大需求量已分配资源量剩余资源量尚需要量
ABCABCABCABC
P1864121211743
P2433311122
P31013413600
P4333322011
P5546113433
系统是处于安全状态，安全序列为：
P4，P2，P1，P3，P5
（2）P5申请（1，1，1）
最大需求量已分配资源量剩余资源量尚需要量
ABCABCABCABC
P1864121100743
P2433311122
P31013413600
P4333322011
P5546224322
不能实施分配，因为分配后找不到安全序列，系统将处于不安全状态.
31．有三个进程PA，PB和PC合作解决文件打印问题：
PA将文件记录从磁盘读入主存的缓冲区1，每执行一次读一个记录；PB将缓冲区1的容复制到缓冲区2，每执行一次复制一个记录；PC将缓冲区2的容打印出来，每执行一次打印一个记录。
缓冲区的大小等于一个记录大小。
请用P，V操作来保证文件的正确打印。
解答：
在本题中，进程PA，PB和PC之间的关系为：
PA与PB共用一个单缓冲区，而PB又与PC共用一个单缓冲区，其合作方式可用图2-10表示，当缓冲区1为空时，进程PA可将一个记录读入其中；若缓冲区1中有一个数据且缓冲区2为空，则进程PB可将记录从缓冲区1复制到缓冲区2中；若缓冲区2中有数据，则进程PC可以打印记录，在其他条件下，相应进程必须等待。
事实上，这是一个生产者—消费者的问题
打印
缓冲区1
缓冲区2
PA
从磁盘读入
PB
PC
复制
图2-10进程间的合作方式
为遵循这一同步规则。
应设置四个信号量empty1，empty2，full1，full2，信号量empty1及empty2分别表示缓冲区1及缓冲区2是否为空，其初值为1；信号量full1，full2分别表示缓冲区1及缓冲区2是否有记录可供处理，其初值为0。
其同步描述如下：
intempty1=1；
intempty2=1；
intfull1=0;
intfull2=0;
main（）
{
cobegin
PA（）;
PB（）;
PC（）;
coend
}
PA（）
{
while
（1）
{从磁盘读一个记录;
P（empty1）;
将记录存入缓冲区1；
V（full1）;
}
}
PB（）
{
while
（1）
{
P（full1）;
从缓冲区1中取出记录;
V（empty1）;
P（empty2）;
将记录存入缓冲区2；
V（full2）;
}
}
PC（）
{
while
（1）
{
P（full2）;
从缓冲区2中取出记录;
V（empty2）;
打印记录;
}
}
本题也是一个典型生产者—消费者的问题，其中的难点在于PB既是一个生产者又是一个消费者。
11．有一个虚拟存储系统,每个进程在存占有3页数据区、1页程序区.刚开始时数据区为空.有以下访页序列:
1、5、4、1、2、3、2、1、5、4、2、4、6、5、1
试给出下列情形下的缺页次数:
（1）系统采用先进先出（FIFO）淘汰算法.
（2）系统采用最近最少使用（LRU）淘汰算法.
12．有个一虚拟存储系统,每个进程在存占有3页数据区,刚开始时数据区为空.有以下访页序列:
2、3、4、5、3、4、1、2、3、5、1、4、2、4、5、1、3、2、1、3
试给出下列情形下的缺页次数:
（1）系统采用先进先出（FIFO）淘汰算法.
（2）系统采用最近最少使用（LRU）淘汰算法.
用PV操作解决读者写者问题的正确程序如下：
beginS,Sr:
Semaphore;rc:
integer;
S:
=1;Sr:
=1;rc:
=0;
cobeginPROCESSReaderi（i=1,2…）
beginP（Sr）
rc:
=rc+1;
ifrc=1thenP（S）;
V（Sr）;
readfile;
P（Sr）;
rc:
=rc-1
ifrc=0thenV（S）;
V（Sr）;
end;
PROCESSWriterj（j=1,2…）
beginP（S）;
Writefile;
V（S）
end;
coend;
end;
请回答：
（1）信号量Sr的作用；
（2）程序中什么语句用于读写互斥，写写互斥；（3）若规定仅允许5个进程同时读怎样修改程序？
答：
（1）Sr用于读者计数rc的互斥信号量；
（2）ifrc=1thenP（S）中的P（S）用于读写互斥，写者进程中的P（S）用于写写互斥，读写互斥。
（3）程序中增加一个信号量S5，初值为5，P（S5）语句加在读者进程P（Sr）之前，V（S5）语句加在读者进程第2个V（Sr）之后。
2．考虑一个由8个页面、每页有1024个字节组成的逻辑空间，把它装入到有32个物理
块的存储器中，问：
（1）逻辑地址需要多少二进制位表示?
（2）物理地址需要多少二进制位表示?
因为页面数为8＝23，故需要3位二进制数表示。
每页有1024个字节，1024＝210，于是页地址需要10位二进制数表示。
32个物理块，需要5位二进制数表示（32＝25）
（1）页的逻辑地址由页号和页地址组成，所以需要3+10=13位二进制数表示。
（2）页的物理地址由块号和页地址的拼接，所以需要5+10=15位二进制数表示。
1.某虚拟存储器的用户编程空间共32个页面，每页为1KB，存为16KB。
假定某时刻一用户页表中已调入存的页面的页号和物理块号的对照表如下：
页号
物理块号
0
5
1
10
2
4
3
7
计算逻辑地址0A5C（H）所对应的物理地址（要求写出分析过程）。
1．解：
页式存储管理的逻辑地址分为两部分：
页号和页地址。
由已知条件“用户编程空间共32个页面”，可知页号部分占5位；由“每页为1KB”，1K=210，可知页地址占10位。
由“存为16KB”，可知有16块，块号为4位。
逻辑地址0A5C（H）所对应的二进制表示形式是：
000101001011100，根据上面的分析，下划线部分为页地址，编码“00010”为页号，表示该逻辑地址对应的页号为2。
查页表，得到物理块号是4（十进制），即物理块地址为：
0100，拼接块地址1001011100，得01001001011100，即125C（H）。
2. 假设一个磁盘有200个磁道，编号从0～199。
当前磁头正在143道上服务，并且刚刚完成了125道的请求。
如果寻道请求队列的顺序是：
86,147,91,177,94,150,102,175,130
问：
为完成上述请求，使用最短寻道时间优先磁盘调度算法SSTF时，磁头移动的总量是多少？
（要求写出分析过程）
采用最短寻道时间优先磁盘调度算法SSTF，进行调度的情况为：
从143道开始
下一磁道
移动磁道数
147
150
130
102
94
91
86
175
177
4
3
20
28
8
3
5
89
2
磁头移动总量为162。
一、设某文件的物理存储方式采用方式，该文件由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个磁盘块。
37.当磁头处于100号磁道时，有9个进程先后提出读写请求涉及的柱面号为63、57、34、88、91、103、76、18和128。
要求：
（1）写出按最短寻找时间优先算法SSTF时的调度次
升级会员 