操作系统复习应用题.docx
《操作系统复习应用题.docx》由会员分享，可在线阅读，更多相关《操作系统复习应用题.docx（31页珍藏版）》请在冰点文库上搜索。
操作系统复习应用题
1．若程序A和B单独执行时分别需要1小时和1.5小时，其中CPU工作时间分别为18分钟和27分钟。
若采用多道程序设计方法，让A和B并行工作，假定CPU利用率达到50％，另加15分钟系统开销，请问系统效率能提高多少?
解：
在多道系统中，程序A和B共用的CPU时间为：
（18十27）／50％＝90分钟
系统效率提高＝（A和B单独执行的时间总和－多道方式下总时间）／A和B单独执行的时间总和，即（（60十90）－（90十15））／（60十90）＝45／150＝30％
1.假定在单CPU条件下有下列要执行的作业：
作业
运行时间
优先级
1
10
2
2
4
3
3
3
0
作业到来的时间是按作业编号顺序进行的（即后面作业依次比前一个作业迟到一个时间单位）。
（1）用一个执行时间图描述在采用非抢占式优先级算法时执行这些作业的情况。
（2）对于上述算法，各个作业的周转时间是多少?
平均周转时间是多少?
（3）对于上述算法，各个作业的带权周转时间是多少?
平均带权周转时间是多少?
解：
（1）非抢占式优先级算法作业的执行情况如下：
作业
到达时间
运行时间
完成时间
周转时间
带权周转时间
1
0
10
10
10
1.0
2
1
4
17
16
4.0
3
2
3
13
11
3.7
平均周转时间
12.3
平均带权周转时间
2.9
2．若在后备作业队列中等待运行的同时有三个作业1、2、3，已知它们各自的运行时间为
a、b、c，且满足关系a＜b＜c，试证明采用短作业优先调度算法能获得最小平均周转时间。
证明：
由于短作业优先调度算法总是在后备作业队列中选择运行时间最短的作业作为调
度对象，因此对短作业优先调度算法而言，这三个作业的总周转时间为
T1=a+（a+b）+（a+b+c）=3a+2b+c……
（1）
若不按短作业优先调度算法来调度这三个作业，不失一般性，假定调度顺序为2、l、3，则其周转时间为T2=b+（b+a）+（b+a+c）=3b+2a+c……
（2）
由
（1）、
（2）两式可得：
T2-T1=b-a>0
由此可见，短作业优先调度算法能获得最小平均周转时间。
3．设有4道作业，它们的提交时间及执行时间如下：
试计算在单道程序环境下，采用先来先服务调度算法和最短作业优先调度算法时的平均周转时间和平均带权周转时间，并指出它们的调度顺序。
（时间单位：
小时，以十进制进行计算。
）
解：
若采用先来先服务调度算法，则其调度顺序为1、2、3、4。
平均周转时间T=（2.0十2.8十3.1十3.3）/4＝2.8
平均带权周转时间W=（1十2.8十6.2十11）／4=5.25
若采用短作业优先调度算法，则其调度顺序为1、4、3、2
平均周转时间为T=（2.0+1.8+2.4+3.6）/4=2.45
平均带权周转时间W=（1十6十4.8十3.6）/4=3.85
4．假设有四个作业，它们的提交、运行时间如下表所示。
若采用高响应比优先调度算法，试问平均周转时间和平均带权周转时间为多少？
（时间单位小时，以十进制进行计算。
）
解：
根据响应比的定义每次调度前计算出各作业的响应比，得到四个作业的调度次序为：
作业1、作业3、作业2、作业4。
平均周转时间为T=（2.0十2.3十1.6十2.O）/4=1.975
平均带权周转时间W=（1十4.6十16十5）/4=6.65
5．有一个具有两道作业的批处理系统，作业调度采用短作业优先的调度算法，进程调度采
用以优先数为基础的抢占式调度算法。
在下表所示的作业序列，作业优先数即为进程优先
数，且优先数越小优先级越高。
（1）列出所有作业进入内存时间及结束时间
（2）计算平均周转时间。
分析:
在本题中，每个作业的运行将经历两级调度：
作业调度和进程调度。
作业调度采用短作业优先调度算法，进程调度采用基于优先数的抢占式调度算法，高优先级的进程可以抢占系统处理机。
只有当作业调度程序将作业装入内存后，方能参与进程调度。
本题中的批处理系统是两道作业系统，因此每次只能有两道作业进入系统内存。
本题中的作业和进程推进顺序如下：
10：
00时，A作业到达。
因系统的后备作业队列中没有其他作业，进程就绪队列中也没有进程，故作业调度程序将作业A调入内存并将它排在就绪队列上，进程调度程序调度它运行。
10：
20时，B作业到达。
因系统的后备作业队列中没有其他作业，故作业调度程序将作业B调入内存并将它排在就绪队列上。
而作业B的优先级高于作业A的优先级，进程调度程序停止作业A的运行，将作业A放入就绪队列，调度作业B运行。
此时，系统中已有两道作业在内存中运行，作业A已运行20分钟，还需运行20分钟才能完成。
10：
30时，C作业到达。
因系统中已有两道作业在内存中运行，故作业C只能在后备作业队列中等待作业调度。
此时，作业B已运行了10分针并将继续运行，还需运行20分钟才能完成，作业A已等待10分针并将继续等待、还需运行20分钟才能完成。
10：
50时，B作业运行30分钟结束运行，D作业到达。
因系统中只有作业A在内存中运行，作业后备队列中有C、D两道作业，按短作业优先的作业调度策略，作业D被作业调度程序选中，装入内存运行，作业C仍在后备作业队列中等待作业调度。
在内存中，作业A的优先级高于作业D，进程调度程序调度作业A运行，作业D在就绪队列中等待进程调度。
此时，作业A已运行了20分钟，在就绪队列中等待了30分钟，还需运行20分钟才能完成；作业C已在后备队列中等待了20分钟并将继续等待．
11：
10时，A作业运行40分针结束运行。
因系统中只有作业D在内存中运行，作业后备队列中只有作业C在等待，作业调度程序将作业C装入内存运行。
因作业C的优先级高于作业D，进程调度程序调度作业C运行，作业D仍在就绪队列中等待进程调度。
此时作业D已在就绪队列中等待了20分钟并将继续等待。
12：
00时，C作业运行50分针结束运行。
因系统中只有作业D在内存，进程调度程序调度作业D运行。
12：
20时，D作业运行20分钟结束运行。
解：
（1）由上述分析可得出所有作业的进入内存时间和结束时间：
（2）各作业执行时的周转时间为：
作业A：
70分钟
作业B：
30分钟
作业c：
90分钟
作业D：
90分钟
作业的平均周转时间为：
（70十30十90十90）／4＝70分钟。
6.已知3个批处理作业中：
第一个作业10.00时到达，需要执行2小时；第二个作业在10.1时到达，需要执行1小时；第三个作业在10.5小时到达，需要执行0.5小时。
如果分别采用如下的表1和表2所示的两种作业调度算法。
（1）计算各调度算法下的作业平均周转时间：
（2）这两种调度算法各可能是什么作业调度算法?
表1调度算法1
表2调度算法2
解：
（1）采用调度算法1的作业运行情况如下表3所示：
表3采用调度算法1的作业运行情况表
采用调度算法2的作业运行情况如下表4所示：
表4采用调度算法2的作业运行情况表
（2）调度算法1是按照作业到达的先后次序执行的，所以它是先来先服务调度算法。
调度算
法2满足短作业优先的调度原则，所以它属于短作业优先调度算法。
此外，从响应比高者优先调度算法来看，当作业1在12.0完成时，作业2和作业3的响应比如下：
作业2的响应比＝1+1.9/1＝2.9，作业3的响应比＝1+1.5/0.5＝4也即，调度算法2也可能是响应比高者优先调度算法。
7．有三个进程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.采用银行家算法因为在分配时，保证了系统处于安全状态。
8．设系统有三种类型的资源，数量为（4，2，2），系统中有进程A，B，C按如下顺序请求资源：
进程A申请（3，2，1）
进程B申请（1，0，1）
进程A申请（0，1，0）
进程C申请（2，0，0）
请你给出一种防止死锁的资源剥夺分配策略，完成上述请求序列，并列出资源分配过程，指明哪些进程需要等待，哪些资源被剥夺。
解：
①分配策略为：
当进程Pi申请ri类资源时，检查ri中有无可分配的资源，有则分配给Pi；否则将Pi占有的资源全部释放而进入等待状态。
（Pi等待原占有的所有资源和新申请的资源）
②资源分配过程：
剩余资源
进程A：
（3，2，1）（1，0，1）
进程B：
（1，0，1）（0，0，0）
进程C：
（2，0，0）（1，2，1）
进程A：
（0，1，0）（不满足）（3，2，1），A的所有资源被剥夺，A处于等待，C，B完成之后，A可完成。
9．某系统中有10台打印机，有三个进程P1，P2，P3分别需要8台，7台和4台。
若P1，P2，P3已申请到4台，2台和2台。
试问：
按银行家算法能安全分配吗？
请说明分配过程。
答：
系统能为进程P3分配二台打印机。
因为尽管此时10台打印机已分配给进程P14台，P22台和P34台，全部分配完，但P3已分配到所需要的全部4台打印机，它不会对打印机再提出申请，所以它能顺利运行下去，能释放占用的4台打印机，使进程P1，P2均可能获得乘余的要求4台和5台，按银行家算法是安全的。
10．在生产者—消费者问题中，如果对调生产者进程中的两个P操作和两个V操作，则可能发生什么情况?
解：
如果对调生产者进程中的两个P操作和两个v操作，则生产者—消费者问题的同步描述为：
intfull=0;
intempty=n;
intmutex=1;
main（）
{
cobegin
producer（）;
consumer（）;
coend
}
producer（）
{
while（生产未完成）
{
生产一个产品；
p（mutex）;
p（empty）;
送一个产品到有界缓冲区；
v（full）;
v（mutex）;
}
}
consumer（）
{
while（还要继续消费）
{
p（full）;
p（mutex）;
从有界缓冲区中取产品；
v（mutex）;
v（empty）;
消费一个产品；
}
}
由于V操作是释放资源，因此对调V操作的次序无关紧要。
而对调P操作的次序则可能导致死锁。
这是因为对调P操作后，有可能出现这样一种特殊情况：
在某一时刻缓冲区中己装满了产品且缓冲区中无进程工作（这时信号量full的值为n，信号量empty的值为0，信号量mutex的值为1），若系统此时调度生产者进程运行，生产者进程又生产了一个产品，
它执行P（mutex）并顺利进入临界区（这时mutex值为0），随后它执行p（empty）时因没有空闲缓冲单元而受阻等待，等待消费者进程进入缓冲区取走产品以释放出缓冲单元；消费者进程执行p（full）后再执行p（mutex）时，因缓冲区被生产者进程占据而无法进入。
这样就形成了生产者进程在占有临界资源的情况下，等待消费者进程取走产品，而消费者进程又无法进入临界区取走产品的僵局，此时两进程陷入死锁。
11．n个进程共享某种资源R，该资源共有m个可分配单位，每个进程一次一个地申请或释放资源单位。
假设每个进程对该资源的最大需求量均小于m，且各进程最大需求量之和小于m十n，试证明在这个系统中不可能发生死锁。
解：
设max（i）表示第i个进程的最大资源需求量，need（i）表示第i个进程还需要的资源量，alloc（i）表示第i个进程己分配的资源量。
由题中所给条件可知：
max
（1）+max
（2）+…＋max（n）=（need
（1）+…+need（n））+（alloc
（1）+…+alloc（n））如果在这个系统中发生了死锁，那么一方面m个资源应该全部分配出去，即
alloc
（1）+…+alloc（n）=m
另一方面所有进程将陷入无限等待状态。
由上述两式可得：
need
（1）+…+need（n）上式表示死锁发生后，n个进程还需要的资源量之和小于n，这意味着此刻至少存在一
个进程i，need（i）＝0，即它己获得了所需要的全部资源。
既然该进程已获得了它所需要的全部资源，那么它就能执行完成并释放它占有的资源，这与前面的假设矛盾，从而证明在这个系统中不可能发生死锁。
12．在银行家算法中，若出现下述资源分配情况：
试问：
（1）该状态是否安全?
（2）如果进程P2提出请求Request2（1，2，2，2）后，系统能否将资源分配给它?
解：
（1）利用银行家算法对此时刻的资源分配情况进行分析，可得此时刻的安全性分析情况：
从上述分析中可以看出，此时存在一个安全序列{P0，P3，P4，P1，P2}，故该状态是
安全的。
（2）P2提出请求Request2（1，2，2，2），按银行家算法进行检查：
Request2（1，2，2，2）≤Need2（2,3,5,6）
Request2（1，2，2，2）≤Available（1,6,2,2）
试分配并修改相应的数据结构，资源分配情况如下：
再利用安全性算法检查系统是否安全，可用资源Available（0，4，0，0）己不能满足任何进程的需要，故系统进入不安全状态，此时系统不能将资源分配给P2。
13．有相同类型的5个资源被4个进程所共享，且每个进程最多需要2个这样的资源就可以运行完毕。
试问该系统是否会由于对这种资源的竞争而产生死锁。
答：
该系统不会由于对这种资源的竞争而产生死锁。
因为在最坏情况下，每个进程都
需要2个这样的资源，且每个进程都已申请到了1个资源，那么系统中还剩下1个可用资
源。
无论系统为了满足哪个进程的资源申请而将资源分配给该进程，都会因为该进程已获
得了它所需要的全部资源而确保它运行完毕，从而可将它占有的2个资源归还给系统，这
就保证了其余三个进程能顺利运行。
由此可知，该系统不会由于对这种资源的竞争而产生
死锁。
14．考虑下列资源分配策略：
对资源的申请和释放可以在任何时候进行。
如果一个进程提出资源请求时得不到满足，若此时无由于等待资源而被阻塞的进程，则自己就被阻塞；若此时已有等待资源而被阻塞的进程，则检查所有由于等待资源而被阻塞的进程。
如果它们有申请进程所需要的资源，则将这些资源取出分配给申请进程。
例如，考虑一个有3类资源的系统，系统所有可用资源为（4，2，2），进程A申请（2，2，1），可满足；进程B申请（1，0，1），可满足；若A再申请（0，0，1），则被阻塞。
此时，若C请求（2，0，0），它可以分到剩余资源（1，0，0），并从A已分到的资源中获得一个资源，于是进程A的分配向量变成（1，2，1）而需求向量变成（1，0，1）。
①这种分配策略会导致死锁吗?
如果会，请举一个例子；如果不会，请说明产生死锁的哪一个必要条件不成立。
②这种分配方式会导致某些进程的无限等待吗?
为什么?
解：
①本题所给的资源分配策略不会产生死锁。
因为本题给出的分配策略规定若一进程的资源得不到满足，则检查所有由于等待资源而被阻塞的进程，如果它们有申请进程所需要的资源，则将这些资源取出分配给申请进程。
从而破坏了产生死锁必要条件中的不剥夺条件，这样系统就不会产生死锁。
②这种方法会导致某些进程无限期的等待。
因为被阻塞进程的资源可以被剥夺，所以
被阻塞进程所拥有的资源数量在其被唤醒之前只可能减少。
若系统中不断出现其他进程申
请资源，这些进程申请的资源与被阻塞进程申请或拥有的资源类型相同且不被阻塞，则系
统无法保证被阻塞进程一定能获得所需要的全部资源。
例如，本题中的进程A申请（2，2，
1）后再申请（0，0，1）被阻塞。
此后，进程C又剥夺了进程A的一个资源，使得进程A拥有的资源变为（1，2，1），其需求向量为（1，0，1）。
之后，若再创建的进程总是只申请第1和第3类资源，总是占有系统所剩下的第1和第3类资源的全部且不阻塞，那么进程A将会无限期地等待。
15．一台计算机有8台磁带机。
它们由N个进程竞争使用，每个进程可能需要3台磁带机。
请问N为多少时，系统没有死锁危险，并说明原因。
解：
当N为1，2，3时，系统没有产生死锁的危险。
因为，当系统中只有1个进程时，
它最多需要3台磁带机，而系统有8台磁带机，其资源数目足够系统内的1个进程使用，因此绝不可能发生死锁：
当系统中有2个进程时，最多需要6台磁带机，而系统有8台磁带机，其资源数目也足够系统内的2个进程使用，因此也不可能发生死锁；当系统中有3个进程时，在最坏情况下，每个进程都需要3个这样的资源，且假定每个进程都已申请到了2个资源，那么系统中还剩下2个可用资源，无论系统为了满足哪个进程的资源申请而将资源分配给该进程，都会因为该进程已获得了它所需要的全部资源而确保它运行完毕，从而可将它占有的3个资源归还给系统，这就保证了其余进程能顺利运行完毕。
由此可知，当N为1，2，3时，该系统不会由于对这种资源的竞争而产生死锁。
16．假设就绪队列中有10个进程，系统将时间片设为200ms，CPU进行进程切换要花费10ms，试问系统开销所占的比率约为多少?
解：
因就绪队列中有10个进程，它们以时间片轮转的方式使用CPU，时间片长度为200ms。
当一个时间片用完时．调度进程将当前运行进程设置为就绪状态并放入就绪队列尾，再从就绪队列队首选择进程投入运行，这一过程（进程切换）要花费时间l0ms。
因此系统开销所占比率为：
10/（200+10）=4.8%
17.如果P、V操作设计不当，则有可能产生死锁。
假如系统中有输入机和打印机两类资源各一台，有两个进程P1和P2都要求使用输入机和打印机。
我们可以利用P、V操作来实现互斥：
定义s1、s2分别为代表输入机和打印机能否被使用的信号量，初值均为1，并且按如下方法请求使用和归还资源：
ProcessP1
begin
P（s1）；
使用输入机；
P（s2）；
使用打印机；
V（s2）；
V（s1）；
End;
ProcessP2
Begin
P（s2）；
使用打印机；
P（s1）；
使用输入机；
V（s2）；
V（s1）；
End；
结合死锁产生的必要条件，分析此种方法是否会造成死锁，若不会，给出理由；若会产生死锁，则修改上面程序，使P1、P2两进程能够互斥的使用资源，并且能够顺利完成。
解：
此种方法可能会出现P1得到输入机而P2得到打印机，双方在不释放已有资源的情况下，又去申请新的资源，从而造成死锁。
可以采用为资源编号的方法，让进程按序申请资源，来避免死锁。
程序可修改如下：
ProcessP2
Begin
P（s2）；
使用输入机；
P（s1）；
使用打印机；
V（s2）；
V（s1）；
End；
18．假定某计算机系统有R1和R2两类可再使用资源（其中R1有两个单位，R2有一个单位）．它们被进程P1和P2所共享，且已知两个进程均以
申请R1申请R2申请R1释放R1释放R2释放R
所示的顺序使用两类资源。
试求出系统运行过程中可能到达的死锁点．并画出死锁点的资源分配图（或称进程一资源图）。
解：
该题答案不惟一。
从已知条件可知，P1、P2两进程都是各自按顺序申请系统中所有资源，并在全部得到满足之后才会依次释放；由此可得，只要让Pl、P2分别占有其中某个资源，即不把全部资源都交给一个进程，则会发生死锁。
进程一资源图如下：
19．某系统有R1、R2和R3共3种资源．在T0时刻P1、P2、P3和P4这4个进程对资源的占用和需求情况见下表，此刻系统的可用资源向量为（2，1，2），问题：
（1）将系统中各种资源总数和此刻各进程对各资源的需求数目用向量或矩阵表示出来；
（2）如果此时P1和P2均发出资源请求向量Request（1，0，1），为了保持系统安全性，应该如何分配资源给这两个进程?
说明你所采用策略的原因；
（3）如果
（2）中两个请求立刻得到满足后，系统此刻是否处于死锁状态?
解：
（1）系统资源总数为（9，3，6）。
各进程对资源需求矩阵为：
222
202
103
420
（2）采用银行家算法进行计算得：
系统不可以将资源分配给进程P1，虽然剩余资源还可以满足进程P1现在的需求，但是一旦分配给进程P1后，就找不到一个安全执行的序列保证各个进程能够正常运行下去。
因此进程P1进入等待状态。
系统可以满足P2的请求，因为分配完成后，至少还可以找到一个安全序列，如（P2P1P3P4），使各进程可以运行至结束。
（3）系统满足进程P1和P2的请求后，没有立即进入死锁状态，因为此时所有进程还处于运行状态，没有被阻塞；只有等到进程继续申请资源井因得不到满足而全部进人阻塞状态，死锁才真正发生了。
1．在一个请求分页存储管理系统中，一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5，当分配给该作业的物理块数分别为3、4时，试计算采用下述页面淘汰算法时的缺页次数（假设开始执行时主存中没有页面），并比较所得结果。
（1）最佳置换法（OPT）
（2）先进先出法（FIFO）
解：
（1）根据所给页面走向，使用最佳页面置换算法时，页面置换情况如下：
（略）
物理块为3时，缺页次数为7；
物理块为4时，缺页次数为6。
由上述结果可以看出，增加分配给作业的内存块数可以降低缺页次数。
（2）根据所给页面走向，使用先进先出页面置换算法时，页面置换情况如下：
（略）
物理块为3时，缺页次数为9；
物理块为4时，缺页次数为10。
由上述结果可以看出，对先进先出算法而言，增加分配给作业的内存块数反而出现缺页次数增加的异常现象。
2．某采用页式存储管理的系统，接收了一个共7页的作业，作业执行时依次访问的页为：
1、2、3、4、2、1、5、6、2、1、2、3、7。
当内存块数量为4时，请分别用先进先出（FIFO）调度算法和最近最少使用（LRU）调度算法，计算作业执行过程中会产生多少次缺页中断?
写出依次产生缺页中断后应淘汰的页。
（所有内存开始时都是空的，凡第一次用到的页面都产生一次缺页中断。
要求写出计算过程）
答：
采用先进先出（FIFO）调度算法，共产生10次缺页中断，依次淘汰的页是1、2、3、4、5、6，（页面调度过程略）；
采用最近最少使用（LRU）调度算法，共产生8次缺页中断，依次淘汰的页是3、4、5、6，（页面调度过程略）。
3．在一个多道程序系统中，设用户空间为200K，主存空间管理采用最先适应分配算法，并采用先来先服务算法管理作业。
今有如下所示的作业序列，请列出各个作业开始执行时间、完成时间和周转时间。
（注意：
忽略系统开销，时间用10进制。
）
作为名
进入输入井时间
需计算时间
主存需求量
JOB1
8.0时
1小时
20K
JOB2
8.2时
0.6小时
60K
JOB3
8.4时
0.5小时
25K
JOB4
8.6时
1小时
20K
答：
作业
开始时间
完成时间
周转时间
J
升级会员 