操作系统复习应用题.doc

1、1若程序 A 和 B 单独执行时分别需要 1 小时和 1.5 小时，其中 CPU 工作时间分别为 18 分钟和 27 分钟。若采用多道程序设计方法，让 A 和 B 并行工作，假定 CPU 利用率达到50，另加 15 分钟系统开销，请问系统效率能提高多少?解：在多道系统中，程序 A 和 B 共用的 CPU 时间为：(18 十 27)5090 分钟系统效率提高(A 和 B 单独执行的时间总和多道方式下总时间)A 和 B 单独执行的时间总和，即(60 十 90)(90 十 15)(60 十 90)45150301. 假定在单 CPU 条件下有下列要执行的作业：作业 运行时间 优先级1 10 22 4

2、 33 3 0作业到来的时间是按作业编号顺序进行的(即后面作业依次比前一个作业迟到一个时间单位)。(1)用一个执行时间图描述在采用非抢占式优先级算法时执行这些作业的情况。(2)对于上述算法，各个作业的周转时间是多少?平均周转时间是多少?(3)对于上述算法，各个作业的带权周转时间是多少?平均带权周转时间是多少?解： (1)非抢占式优先级算法作业的执行情况如下：作业 到达时间 运行时间 完成时间 周转时间 带权周转时间1 0 10 10 10 1.02 1 4 17 16 4.03 2 3 13 11 3.7平均周转时间 12.3平均带权周转时间 2.92若在后备作业队列中等待运行的同时有三个作业

3、 1、2、3，已知它们各自的运行时间为a、b、c，且满足关系 abc，试证明采用短作业优先调度算法能获得最小平均周转时间。证明：由于短作业优先调度算法总是在后备作业队列中选择运行时间最短的作业作为调度对象，因此对短作业优先调度算法而言，这三个作业的总周转时间为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-a0由此可见，短作业优先调度算法能获得最小平均周转时间。3设有 4 道作业，它们

4、的提交时间及执行时间如下：试计算在单道程序环境下，采用先来先服务调度算法和最短作业优先调度算法时的平均周转时间和平均带权周转时间，并指出它们的调度顺序。(时间单位：小时，以十进制进行计算。)解：若采用先来先服务调度算法，则其调度顺序为 1、2、3、4。平均周转时间 T=(2.0 十 2.8 十 3.1 十 3.3)/42.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.854

5、假设有四个作业，它们的提交、运行时间如下表所示。若采用高响应比优先调度算法，试问平均周转时间和平均带权周转时间为多少？ (时间单位小时，以十进制进行计算。)解：根据响应比的定义每次调度前计算出各作业的响应比，得到四个作业的调度次序为：作业 1、作业 3、作业 2、作业 4。平均周转时间为 T=(2.0 十 2.3 十 1.6 十 2.O)/4=1.975平均带权周转时间 W=(1 十 4.6 十 16 十 5)/4=6.655有一个具有两道作业的批处理系统，作业调度采用短作业优先的调度算法，进程调度采用以优先数为基础的抢占式调度算法。在下表所示的作业序列，作业优先数即为进程优先数，且优先数越小

6、优先级越高。(1)列出所有作业进入内存时间及结束时间(2)计算平均周转时间。分析: 在本题中，每个作业的运行将经历两级调度：作业调度和进程调度。作业调度采用短作业优先调度算法，进程调度采用基于优先数的抢占式调度算法，高优先级的进程可以抢占系统处理机。只有当作业调度程序将作业装入内存后，方能参与进程调度。本题中的批处理系统是两道作业系统，因此每次只能有两道作业进入系统内存。本题中的作业和进程推进顺序如下：10：00 时，A 作业到达。因系统的后备作业队列中没有其他作业，进程就绪队列中也没有进程，故作业调度程序将作业 A 调入内存并将它排在就绪队列上，进程调度程序调度它运行。10：20 时，B 作

7、业到达。因系统的后备作业队列中没有其他作业，故作业调度程序将作业 B 调入内存并将它排在就绪队列上。而作业 B 的优先级高于作业 A 的优先级，进程调度程序停止作业 A 的运行，将作业 A 放入就绪队列，调度作业 B 运行。此时，系统中已有两道作业在内存中运行，作业 A 已运行 20 分钟，还需运行 20 分钟才能完成。10：30 时，C 作业到达。因系统中已有两道作业在内存中运行，故作业 C 只能在后备作业队列中等待作业调度。此时，作业 B 已运行了 10 分针并将继续运行，还需运行 20 分钟才能完成，作业 A 已等待 10 分针并将继续等待、还需运行 20 分钟才能完成。10：50 时，

8、B 作业运行 30 分钟结束运行，D 作业到达。因系统中只有作业 A 在内存中运行，作业后备队列中有 C、D 两道作业，按短作业优先的作业调度策略，作业 D 被作业调度程序选中，装入内存运行，作业 C 仍在后备作业队列中等待作业调度。在内存中，作业A 的优先级高于作业 D，进程调度程序调度作业 A 运行，作业 D 在就绪队列中等待进程调度。此时，作业 A 已运行了 20 分钟，在就绪队列中等待了 30 分钟，还需运行 20 分钟才能完成；作业 C 已在后备队列中等待了 20 分钟并将继续等待11：10 时，A 作业运行 40 分针结束运行。因系统中只有作业 D 在内存中运行，作业后备队列中只有

9、作业 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 十 9

10、0 十 90)470 分钟。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 的作业运行情况

11、表(2)调度算法 1 是按照作业到达的先后次序执行的，所以它是先来先服务调度算法。调度算法 2 满足短作业优先的调度原则，所以它属于短作业优先调度算法。此外，从响应比高者优先调度算法来看，当作业 1 在 12.0 完成时，作业 2 和作业 3 的响应比如下：作业 2 的响应比1+1.9/12.9，作业 3 的响应比1+1.5/0.54 也即，调度算法 2 也可能是响应比高者优先调度算法。7有三个进程 P1，P2 和 P3 并发工作。进程 P1 需用资源 S3 和 S1；进程 P2 需用资源 S1和 S2；进程 P3 需用资源 S2 和 S3。回答：(1)若对资源分配不加限制，会发生什么情况?为

12、什么?(2)为保证进程正确工作，应采用怎样的资源分配策略?为什么?答：(1)可能会发生死锁 例如：进程 P1，P2 和 P3 分别获得资源 S3，S1 和 S2 后再继续申请资源时都要等待，这是循环等待。(或进程在等待新源时均不释放已占资源)(2)可有几种答案： A采用静态分配 由于执行前已获得所需的全部资源，故不会出现占有资源又等待别的资源的现象(或不会出现循环等待资源现象)。 或 B.采用按序分配 不会出现循环等待资源现象。或 C.采用银行家算法 因为在分配时，保证了系统处于安全状态。8设系统有三种类型的资源，数量为(4，2，2)，系统中有进程 A，B，C 按如下顺序请求资源： 进程 A

13、申请(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)(

14、不满足)(3，2，1)，A 的所有资源被剥夺，A 处于等待，C，B 完成之后，A 可完成。 9某系统中有 10 台打印机，有三个进程 P1，P 2，P 3分别需要 8 台，7 台和 4 台。若P1，P 2，P 3已申请到 4 台，2 台和 2 台。试问：按银行家算法能安全分配吗？请说明分配过程。答：系统能为进程 P3分配二台打印机。因为尽管此时 10 台打印机已分配给进程 P14台，P 22 台和 P34 台，全部分配完，但 P3已分配到所需要的全部 4 台打印机，它不会对打印机再提出申请，所以它能顺利运行下去，能释放占用的 4 台打印机，使进程 P1，P 2均可能获得乘余的要求 4 台和 5

15、 台，按银行家算法是安全的。10在生产者消费者问题中，如果对调生产者进程中的两个 P 操作和两个 V 操作，则可能发生什么情况?解：如果对调生产者进程中的两个 P 操作和两个 v 操作，则生产者消费者问题的同步描述为：int full=0;int empty =n;int mutex=1;main ( )cobeginproducer ( );consumer ( );coendproducer ( )while (生产未完成)生产一个产品；p(mutex);p(empty);送一个产品到有界缓冲区；v(full);v(mutex);consumer ( )while(还要继续消费)p(ful

16、l);p(mutex);从有界缓冲区中取产品；v(mutex);v(empty);消费一个产品；由于 V 操作是释放资源，因此对调 V 操作的次序无关紧要。而对调 P 操作的次序则可能导致死锁。这是因为对调 P 操作后，有可能出现这样一种特殊情况：在某一时刻缓冲区中己装满了产品且缓冲区中无进程工作(这时信号量 full 的值为 n，信号量 empty 的值为0，信号量 mutex 的值为 1)，若系统此时调度生产者进程运行，生产者进程又生产了一个产品，它执行 P(mutex)并顺利进入临界区(这时 mutex 值为 0)，随后它执行 p(empty)时因没有空闲缓冲单元而受阻等待，等待消费者进

17、程进入缓冲区取走产品以释放出缓冲单元；消费者进程执行 p(full)后再执行 p(mutex)时，因缓冲区被生产者进程占据而无法进入。这样就形成了生产者进程在占有临界资源的情况下，等待消费者进程取走产品，而消费者进程又无法进入临界区取走产品的僵局，此时两进程陷入死锁。11n 个进程共享某种资源 R，该资源共有 m 个可分配单位，每个进程一次一个地申请或释放资源单位。假设每个进程对该资源的最大需求量均小于 m，且各进程最大需求量之和小于 m 十 n，试证明在这个系统中不可能发生死锁。解：设 max(i)表示第 i 个进程的最大资源需求量，need(i)表示第 i 个进程还需要的资源量，alloc

18、(i)表示第 i 个进程己分配的资源量。由题中所给条件可知：max(1)+max(2)+max(n)=(need(1)+need(n)+(alloc(1)+alloc(n)m+n如果在这个系统中发生了死锁，那么一方面 m 个资源应该全部分配出去，即alloc(1)+alloc(n)=m另一方面所有进程将陷入无限等待状态。由上述两式可得：need(1)+need(n)n上式表示死锁发生后，n 个进程还需要的资源量之和小于 n，这意味着此刻至少存在一个进程 i，need(i)0，即它己获得了所需要的全部资源。既然该进程已获得了它所需要的全部资源，那么它就能执行完成并释放它占有的资源，这与前面的假设

19、矛盾，从而证明在这个系统中不可能发生死锁。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,

20、2, 2)试分配并修改相应的数据结构，资源分配情况如下：再利用安全性算法检查系统是否安全，可用资源 Available (0，4，0，0)己不能满足任何进程的需要，故系统进入不安全状态，此时系统不能将资源分配给 P2。13有相同类型的 5 个资源被 4 个进程所共享，且每个进程最多需要 2 个这样的资源就可以运行完毕。试问该系统是否会由于对这种资源的竞争而产生死锁。 答：该系统不会由于对这种资源的竞争而产生死锁。因为在最坏情况下，每个进程都需要 2 个这样的资源，且每个进程都已申请到了 1 个资源，那么系统中还剩下 1 个可用资源。无论系统为了满足哪个进程的资源申请而将资源分配给该进程，都会因

21、为该进程已获得了它所需要的全部资源而确保它运行完毕，从而可将它占有的 2 个资源归还给系统，这就保证了其余三个进程能顺利运行。由此可知，该系统不会由于对这种资源的竞争而产生死锁。14考虑下列资源分配策略：对资源的申请和释放可以在任何时候进行。如果一个进程提出资源请求时得不到满足，若此时无由于等待资源而被阻塞的进程，则自己就被阻塞；若此时已有等待资源而被阻塞的进程，则检查所有由于等待资源而被阻塞的进程。如果它们有申请进程所需要的资源，则将这些资源取出分配给申请进程。例如，考虑一个有 3 类资源的系统，系统所有可用资源为(4，2，2)，进程 A 申请(2，2，1)，可满足；进程 B 申请(1，0，

22、1)，可满足；若 A 再申请(0，0，1)，则被阻塞。此时，若 C 请求(2，0，0)，它可以分到剩余资源(1，0，0)，并从 A 已分到的资源中获得一个资源，于是进程 A 的分配向量变成(1，2，1)而需求向量变成(1，0，1)。这种分配策略会导致死锁吗?如果会，请举一个例子；如果不会，请说明产生死锁的哪一个必要条件不成立。这种分配方式会导致某些进程的无限等待吗?为什么?解：本题所给的资源分配策略不会产生死锁。因为本题给出的分配策略规定若一进程的资源得不到满足，则检查所有由于等待资源而被阻塞的进程，如果它们有申请进程所需要的资源，则将这些资源取出分配给申请进程。从而破坏了产生死锁必要条件中的

23、不剥夺条件，这样系统就不会产生死锁。这种方法会导致某些进程无限期的等待。因为被阻塞进程的资源可以被剥夺，所以被阻塞进程所拥有的资源数量在其被唤醒之前只可能减少。若系统中不断出现其他进程申请资源，这些进程申请的资源与被阻塞进程申请或拥有的资源类型相同且不被阻塞，则系统无法保证被阻塞进程一定能获得所需要的全部资源。例如，本题中的进程 A 申请(2，2，1)后再申请(0，0，1)被阻塞。此后，进程 C 又剥夺了进程 A 的一个资源，使得进程 A 拥有的资源变为(1，2，1)，其需求向量为(1，0，1)。之后，若再创建的进程总是只申请第 1和第 3 类资源，总是占有系统所剩下的第 1 和第 3 类资源

24、的全部且不阻塞，那么进程 A 将会无限期地等待。15一台计算机有 8 台磁带机。它们由 N 个进程竞争使用，每个进程可能需要 3 台磁带机。请问 N 为多少时，系统没有死锁危险，并说明原因。解：当 N 为 1，2，3 时，系统没有产生死锁的危险。因为，当系统中只有 1 个进程时，它最多需要 3 台磁带机，而系统有 8 台磁带机，其资源数目足够系统内的 1 个进程使用，因此绝不可能发生死锁：当系统中有 2 个进程时，最多需要 6 台磁带机，而系统有 8 台磁带机，其资源数目也足够系统内的 2 个进程使用，因此也不可能发生死锁；当系统中有 3个进程时，在最坏情况下，每个进程都需要 3 个这样的资源

25、，且假定每个进程都已申请到了 2 个资源，那么系统中还剩下 2 个可用资源，无论系统为了满足哪个进程的资源申请而将资源分配给该进程，都会因为该进程已获得了它所需要的全部资源而确保它运行完毕，从而可将它占有的 3 个资源归还给系统，这就保证了其余进程能顺利运行完毕。由此可知，当 N 为 1，2，3 时，该系统不会由于对这种资源的竞争而产生死锁。16假设就绪队列中有 10 个进程，系统将时间片设为 200ms，CPU 进行进程切换要花费10ms，试问系统开销所占的比率约为多少?解：因就绪队列中有 10 个进程，它们以时间片轮转的方式使用 CPU，时间片长度为200ms。当一个时间片用完时调度进程将

26、当前运行进程设置为就绪状态并放入就绪队列尾，再从就绪队列队首选择进程投入运行，这一过程(进程切换)要花费时间 l0ms。因此系统开销所占比率为：10/(200+10)=4.8%17.如果 P、V 操作设计不当，则有可能产生死锁。假如系统中有输入机和打印机两类资源各一台，有两个进程 P1 和 P2 都要求使用输入机和打印机。我们可以利用 P、V 操作来实现互斥：定义 s1、s2 分别为代表输入机和打印机能否被使用的信号量，初值均为 1，并且按如下方法请求使用和归还资源：Process P1beginP(s1)；使用输入机；P(s2)；使用打印机；V(s2)；V(s1)；End;Process P

27、2Begin P(s2)；使用打印机；P(s1)；使用输入机；V(s2)；V(s1)；End；结合死锁产生的必要条件，分析此种方法是否会造成死锁，若不会，给出理由；若会产生死锁，则修改上面程序，使 P1、P2 两进程能够互斥的使用资源，并且能够顺利完成。解：此种方法可能会出现 P1 得到输入机而 P2 得到打印机，双方在不释放已有资源的情况下，又去申请新的资源，从而造成死锁。可以采用为资源编号的方法，让进程按序申请资源，来避免死锁。程序可修改如下：Process P2Begin P(s2)；使用输入机；P(s1)；使用打印机； V(s2)；V(s1)；End；18假定某计算机系统有 R1 和

28、R2 两类可再使用资源(其中 R1 有两个单位，R2 有一个单位)它们被进程 P1 和 P2 所共享，且已知两个进程均以申请 R1 申请 R2 申请 R1 释放 R1 释放 R2 释放 R所示的顺序使用两类资源。试求出系统运行过程中可能到达的死锁点并画出死锁点的资源分配图(或称进程一资源图)。解：该题答案不惟一。从已知条件可知，P1、P2 两进程都是各自按顺序申请系统中所有资源，并在全部得到满足之后才会依次释放；由此可得，只要让 Pl、P2 分别占有其中某个资源，即不把全部资源都交给一个进程，则会发生死锁。进程一资源图如下：19某系统有 R1、R2 和 R3 共 3 种资源在 T0 时刻 P1

29、、P2、P3 和 P4 这 4 个进程对资源的占用和需求情况见下表，此刻系统的可用资源向量为(2，1，2)，问题：(1)将系统中各种资源总数和此刻各进程对各资源的需求数目用向量或矩阵表示出来；(2)如果此时 P1 和 P2 均发出资源请求向量 Request(1，0，1)，为了保持系统安全性，应该如何分配资源给这两个进程?说明你所采用策略的原因；(3)如果(2)中两个请求立刻得到满足后，系统此刻是否处于死锁状态?解：（1）系统资源总数为(9，3，6)。各进程对资源需求矩阵为： 2 2 22 0 21 0 34 2 0(2)采用银行家算法进行计算得：系统不可以将资源分配给进程 P1，虽然剩余资源

30、还可以满足进程 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)根据所给页面走向，使用最佳页面置换算法时，页面置换情况如下：(略)