算法题

算法题（共32个题目）200348.在信号量机制中，若P（S）操作是可中断的，则会有什么问题？此题答案为：答：P（S）的操作如下：BeginS.Value:=S.Value-1;①IfS.Value0Then②BeginInsert(*,S.L);Block(*)③EndEnd.若P（S）可中断的，例如进程A在执行了语句①之后从CPU上退下了，假定此时S.Value＝0；这时换另一进程B，B又将S.Value的值减1使之为－1，在执行语句③时，B被阻塞；然后又换回A执行，由于A的断点是语句①之后，当它执行语句②时，由于这时S.Value已经是－1，故进程继续执行而被阻塞。这就出现了错误：本来A操作P（S）操作后，S.Value＝0，是不应该被阻塞的，现在却被阻塞了。200350.何谓临界区？下面给出的两个进程互斥的算法是安全的吗？为什么？＃definetrue;#definefalse;Intflag[2];flag[1]=flag[2]=false;enter-crtsec(i)inti;{While(flag[1-i])flag[i]=true;}feave-crtsec(i)Inti;{flag[i]=false;}processI;…Enter-crtsec(i);Incriticalsection;Leave-crtsec(i);此题答案为：答：一次仅允许一个进程使用的资源称为临界资源，在进程中对临界资源访问的程序段称为临界区。从概念上讲，系统中各进程在逻辑上是独立的，它们可以按各自的速度向前推进。但由于它们共享某些临界资源，因而产生了临界区问题。对于具有临界区问题的并发进程，它们之间必须互斥，以保证不会同时进入临界区。这种算法不是安全的。因为，在进入临界区的enter-crtsec（）不是一个原语操作，如果两个进程同时执行完其循环（此前两个flag均为false），则这两个进程可同时进入临界区。53.某车站售票厅，任何时刻最多可容纳20名购票者进入，当售票少于20名购票者时，则厅外的购票者可立即进入，否则需在外面等待。若把一个购票者看作一个进程，请回答下列问题：（1）用P、V操作管理这些并发进程时，应怎样定义信号量？写出信号量的初值以及信号量各种取值的含义。（2）根据所定义的信号量，把应执行的P、V操作填入下述程序中，以保证进程能够正确地并发执行。CobeginPROCESSPi(i=1,2,…)Begin进入售票厅；购票；退出；End;Coend(3)若欲购票者最多为n个人，写出信号量可能的变化范围（最大值和最小值）。此题答案为：售票厅问题解答如下：（1）定义一信号量S，初始值为20。S0S的值表示可继续进入售票厅的人数；S=0表示售票厅中已有20名购票者；S0|S|的值为等待进入售票厅中的人数。（2）上框为P(S)，下框为V(S)。（3）S的最大值为20，S的最小值为20－N，N为某一时刻需要进入售票厅的最多人数。200362.在批处理系统、分时系统和实时系统中，各采用哪几个进程（作业）调度算法？此题答案为：答：（1）批处理系统中的作业调度算法有：先来先服务算法（FCFS）短作业优先算法（SJF）优先级调度算法（HPF）高响应比优先算法（RF）。批处理系统的进程调度算法有：先进先出算法（FIFO）短进程优先算法（SPF）优先级调度算法（HPF）高响应比优先算法（RF）。（2）分时系统中只设有进程调度（不设作业调度），其进程调度算法只有轮转法（RR）一种。（3）实时系统中只设有进程（不设作业调度），其进程调度算法调度有：轮转法、优先级调度算法。前者适用于时间要求不严格的实时系统；后者用于时间要求严格的实时系统。后者又可细分为：非抢占式优先级调度、抢占式优先级调度、基于时钟中断的抢占式优先级调度。注意，一个纯粹的实时系统是针对特定应用领域设计的专用系统。作业提交的数量不会超过系统规定的多道程序的道数，因而可全部进入内存。若将实时系统与批处理系统结合的话，就可以让作业量超过多道程序道数，使优先级低的作业呆在外存的后备队列上。200372.假设系统中有5个进程，它们的到达时间和服务时间见下表1，忽略I/O以及其他开销时间，若按先来先服务（FCFS）、非抢占的短作业优先和抢占的短作业优先三种调度算法进行CPU调度，请给出各个进程的完成时间、周转时间、带权周转时间、平均周转时间和平均带权周转时间，完成表2。表1进程到达和需要服务时间进程到达时间服务时间A03B26C44D65E82此题答案为：表2进程的完成时间和周转时间进程ABCDE平均FCFS完成时间39131820周转时间37912128.6带权周转时间1.001.172.252.406.002.56SPF(非抢占)完成时间39152011周转时间37111437.6带权周转时间1.001.171.752.801.501.84SPF(抢占)完成时间31582010周转时间31341427.2带权周转时间1.002.161.002.801.001.59200377.一个逻辑空间最多可有64个页，每页1KB字节。若把它映射到由32个物理块组成的存储器。问：（1）有效的逻辑地址由多少位？（2）有效的物理地址由多少位？此题答案为：答：一个逻辑空间有64个页，每页1KB字节。若把它映射到由32个物理块组成的存储嚣。64＝26，则：（1）逻辑地址有16位。（2）物理地址有15位。说明：解此题的关键是要知道在分页管理中，页和块是一样大小的，这样才知道物理存储器是32KB。200380.在某分页系统中，测得CPU和磁盘的利用率如下，试指出每种情况下的问题和措施。（1）CPU的利用率为15%，磁盘利用率为95%。（2）CPU的利用率为88%，磁盘利用率为3%。（3）CPU的利用率为13%，磁盘利用率为5%。此题答案为：答：在某分页虚存系统中，在题中的CPU和磁盘的利用率的情况下，出现的问题和应采取的措施如下：（1）可能已出现了抖动现象，应减少系统的进程数。（2）系统比较正常，可考虑适当增加进程数以提高资源利用率。（3）CPU和磁盘的利用率都较低，必须增加并发进程数。200381.对访问串：1，2，3，4，1，2，5，1，2，3，4，5，指出在驻留集大小分别为3，4时，使用FIFO和LRU替换算法的缺页次数。结果说明了什么？此题答案为：答：首先采用FIFO，当m=3时，缺页次数＝9，当m=4时，缺页次数＝10。采用LRU算法，当m=3时，缺页次数＝10；当m=4时，缺页次数＝8。结果说明：FIFO有Belady奇异现象，即不满足驻留集增大，缺页次数一定减小的规律；另外在m=3时，LRU的缺页次数比FIFO要多，所以LRU算法并不总优于FIFO，还要看当前访问串的特点。200389.一个分页存储器的页表存放在内存。（1）若内存的存取周期为0.6ms，则CPU从内存取一条指令（或一个操作数）需多少时间？（2）若使用快表且快表的命中率为75%，则内存的平均存取周期为多少？此题答案为：答：一个分页存储器的页表存放在内存（1）因为页表放在内存，故取一条指令（或一个操作数）须访问两次内存，所以需0.6ms×2=1.2ms的时间。（2）这里家假设访问快表的时间忽略不计，命中快表时，取数只要一次访问，故此时的平均存取周期为0.6ms×0.75+1.2ms×(1-0.75)=0.75ms200392.在一个请求分页系统中，采用LRU页面置换算法时，假如一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5，当分配给该作业的物理内存块数M分别为3和4时，分别计算在访问过程中所发生的缺页次数和缺页率，并画出页面置换图。此题答案为：当M=3时，缺页次数为10次，缺页率为10/12=0.83=83%。当M=4时，缺页次数为8次，缺页率为8/12=0.66=66%。可见，增加分配给作业的内存块数可以减少缺页次数，从而降低缺页率。200394.对于一个使用快表的页式虚存，设快表的命中率为70%，内存的存取周期为1ns；缺页处理时，若内存有可用空间或被置换的页面在内存未被修改过，则处理一个缺页中断需8000ns，否则需20000ns。假定被置换的页面60%是属于后一种情况，为了保证有效存取时间不超过2ns，问可接受的最大缺页率是多少？此题答案为：答：设可接受的最大缺页率位p，则有1ns×0.7+2ns×(1-0.7-p)+0.4p×8000ns+0.6p×20000ns=2ns即0.7+0.6-2p+3200p+12000p=215198p=0.7P=0.000046200396.在分页存储管理系统中，存取一次内存的时间是8ns，查询一次快表的时间是1ns，缺页中断的时间是20ns。假设页表的查询与快表的查询同时进行，当查询页表时，如果该页在内存但快表中没有页表项，系统将自动把该页页表项送入快表。一个作业最多可保留3个页面在内存。现在开始执行一作业，系统连续对作业的2，4，5，2，7，6，4，8页面的数据进行一次存取，如分别采用FIFO算法和最优页面置换算法，求每种上存取这些数据需要的总时间。此题答案为：答：（1）FIFO第2页面：20＋8×3第4页面：20＋8×3第5页面：20＋8×3第2页面：8＋1第7页面：20＋8×3第6页面：20＋8×3第4页面：20＋8×3第8页面：20＋8×3因此总的时间是（20＋8×3）×7＋（8＋1）ns(2)OPT第2页面：20＋8×3第4页面：20＋8×3第5页面：20＋8×3第2页面：8＋1第7页面：20＋8×3第6页面：20＋8×3第4页面：8＋1第8页面：8＋1因此总的时间是（20＋8×3）×5＋（8＋1）×3ns200532.在一个请求分页系统中，采用LRU页面置换算法时，假如一个作业的页面走向为1、3、2、1、1、3、5、1、3、2、1、5，当分配给该作业的物理内存块数M分别为3和4时，分别计算在访问过程中所发生的缺页次数和缺页率，并画出页面置换图。此题答案为：当M=3时，缺页次数为6次，缺页率为6/12=0.5=50%。当M=4时，缺页次数为4次，缺页率为4/12=0.33=33%。可见，增加分配给作业的内存块数可以减少缺页次数，从而降低缺页率。200592.在一个请求分页系统中，采用OPT页面置换算法时，假如一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5，当分配给该作业的物理内存块数M分别为3和4时，分别计算在访问过程中所发生的缺页次数和缺页率，并画出页面置换图。此题答案为：当M=3时，缺页次数为7次，缺页率为7/12=0.583=58.3%。当M=4时，缺页次数为8次，缺页率为6/12=0.5=50%。可见，增加分配给作业的内存块数可以减少缺页次数，从而降低缺页率。200601.试证明：如果系统作业几乎同时到达，则使系统平均作业周转时间最短的算法是短作业优先。此题答案为解：设有n个作业j1,j2,j3,...,jn，其运行时间分别为t1,t2,t3,...,tn。不妨假设t1=t2=t3=...=tn，则短作业优先的作业调度算法的平均周转时间为：T=(t1+(t1+t2)+(t1+t2+t3)+....(t1+t2+t3+...+tn))/n=(n*t1+(n-1)*t2+...+tn)/n考虑其他不同调度算法，设在此调度算法下的作业调度次序为ji1,ji2,...jin,其中（i1,i2,...,in）是（1,2,3,...,n）的一个排列，则类似上面可以得出：T1=((n*ti1+(n-1)*ti2+...+tin)/n)根据不等式结论：如果有a1=a2=...=an且b1=b2=...=bn，则a1bn+a2bn-1+...+anb1=a1bi1+a2bi2+...+anbn=a1b1+a2b2+...+anbn其中（i1,i2,...,in）是（1,2,3,...,n）的一个排列，不难得出T=T1。200602.采用银行家算法防止死锁，用Pi→n表示Pi进程申请n个资源，用Pi