搜索
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条件下有下列要执行的作业：作业运行时间优先级1102243330作业到来的时间是按作业编号顺序进行的(即后面作业依次比前一个作业迟到一个时间单位)。(1)用一个执行时间图描述在采用非抢占式优先级算法时执行这些作业的情况。(2)对于上述算法，各个作业的周转时间是多少?平均周转时间是多少?(3)对于上述算法，各个作业的带权周转时间是多少?平均带权周转时间是多少?解：(1)非抢占式优先级算法作业的执行情况如下：作业到达时间运行时间完成时间周转时间带权周转时间101010101.021417164.032313113.7平均周转时间12.3平均带权周转时间2.92．若在后备作业队列中等待运行的同时有三个作业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-a0由此可见，短作业优先调度算法能获得最小平均周转时间。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.854．假设有四个作业，它们的提交、运行时间如下表所示。若采用高响应比优先调度算法，试问平均周转时间和平均带权周转时间为多少？(时间单位小时，以十进制进行计算。)解：根据响应比的定义每次调度前计算出各作业的响应比，得到四个作业的调度次序为：作业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．有一个具有两道作业的批处理系统，作业调度采用短作业优先的调度算法，进程调度采用以优先数为基础的抢占式调度算法。在下表所示的作业序列，作业优先数即为进程优先数，且优先数越小优先级越高。(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(){cobeginproducer();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+n如果在这个系统中发生了死锁，那么一方面m个资源应该全部分配出去，即alloc(1)+…+alloc(n)=m另一方面所有进程将陷入无限等待状态。由上述两式可得：need(1)+…+need(n)n上式表示死锁发生后，n个进程还需要的资源量之和小于n，这意味着此刻至少存在一个进程i，need(i)＝0，即它己获得了所需要的全部资源。既然该进程已获得了它所需要的全部资源，那么它就能执行完成并释放它占有的资源，这与前面的假设矛盾，从而证明在这个系统中不可