进程等题

8.假设系统中有5个进程，它们的到达时间和服务时间见下表1，忽略I/O以及其他开销时间，若按先来先服务（FCFS）、非抢占的短作业优先和抢占的短作业优先三种调度算法进行CPU调度，请给出各个进程的完成时间、周转时间、带权周转时间、平均周转时间和平均带权周转时间，完成表2。表1进程到达和需要服务时间进程到达时间服务时间A03B26C44D65E82表2进程的完成时间和周转时间进程ABCDE平均FCFS完成时间周转时间带权周转时间SPF(非抢占)完成时间周转时间带权周转时间SPF(抢占)完成时间周转时间带权周转时间此题答案为：表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.599.一个逻辑空间最多可有64个页，每页1KB字节。若把它映射到由32个物理块组成的存储器。问：（1）有效的逻辑地址由多少位？（2）有效的物理地址由多少位？答：一个逻辑空间有64个页，每页1KB字节。若把它映射到由32个物理块组成的存储嚣。64＝26，则：（1）逻辑地址有16位。（2）物理地址有15位。说明：解此题的关键是要知道在分页管理中，页和块是一样大小的，这样才知道物理存储器是32KB。10.在某分页系统中，测得CPU和磁盘的利用率如下，试指出每种情况下的问题和措施。（1）CPU的利用率为15%，磁盘利用率为95%。（2）CPU的利用率为88%，磁盘利用率为3%。（3）CPU的利用率为13%，磁盘利用率为5%。答：在某分页虚存系统中，在题中的CPU和磁盘的利用率的情况下，出现的问题和应采取的措施如下：（1）可能已出现了抖动现象，应减少系统的进程数。（2）系统比较正常，可考虑适当增加进程数以提高资源利用率。（3）CPU和磁盘的利用率都较低，必须增加并发进程数。11.对访问串：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，还要看当前访问串的特点。19.一个分页存储器的页表存放在内存。（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）页面走向432143543215最近最长时间未使用的页面433243543243214354321最近刚使用过的页面432143543215缺页√√√√√√√√√√当M=3时，缺页次数为10次，缺页率为10/12=0.83=83%。访问过程中缺页情况（M=4）页面走向432143543215最近最长时间未使用的页面432111543432143543243214354321最近刚使用过的页面432143543215缺页√√√√√√√当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）页面走向132113513215最近最长时间未使用的页面133213513213221351321最近刚使用过的页面132113513215缺页√√√√√√当M=3时，缺页次数为6次，缺页率为6/12=0.5=50%。访问过程中缺页情况（M=4）页面走向132113513215最近最长时间未使用的页面222553133213513213221351321最近刚使用过的页面132113513215缺页√√√√当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）页面走向432143543215最近最长时间未使用的页面2111544/33/21/23334335最近刚使用过的页面44443443555缺页√√√√√√√当M=3时，缺页次数为7次，缺页率为7/12=0.583=58.3%。访问过程中缺页情况（M=4）页面走向432143543215最近最长时间未使用的页面111544/34/3/21/3/222222533343325最近刚使用过的页面44443443255缺页√√√√√√当M=4时，缺页次数为8次，缺页率为6/12=0.5=50%。可见，增加分配给作业的内存块数可以减少缺页次数，从而降低缺页率。200593.在一个请求分页系统中，采用FIFO页面置换算法时，假如一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5，当分配给该作业的物理内存块数M分别为3和4时，分别计算在访问过程中所发生的缺页次数和缺页率，并画出页面置换图。此题答案为：解：访问过程中缺页情况（M=3）页面走向432143543215最近最长时间未使用的页面432144435543214333522最近刚使用过的页面432143555211缺页√√√√√√√√√当M=3时，缺页次数为9次，缺页率为9/12=0.75=75%。访问过程中缺页情况（M=4）页面走向432143543215最近最长时间未使用的页面444321543433321543243222154321最近刚使用过的页面432111543215缺页√√√√√√√√√当M=4时，缺页次数为10次，缺页率为10/12=0.86=83%。可见，增加分配给作业的内存块数并不能减少缺页次数，降低缺页率，这种现象叫抖动现象（Belady）。200594.利用信号量机制描述前趋关系：S={S1,S2,S3,S4,S5,S6,S7}={(S1,S2),(S1,S3),(S2,S4),(S2,S5),(S3,S5),(S3,S6),(S4,S7),(S5,S7),(S6,S7)}解：Vara,b,c,d,e,f,g,h,i,:semaphore:=0,0,0,0,0,0,0,0,0,0;BeginParbeginBeginS1;signal(a);signal(b);end;Beginwait(a);S2;signal(c);signal(d);end;Beginwait(b);S3;signal(e);signal(f);end;Beginwait(c);S4;signal(g);end;Beginwait(d);wait(e);S5;signal(h);end;Beginwait(f);S6;signal(i);end;Beginwait(g);wait(h);wait(i);S7;end;Parendend200601.试证明：如果系统作业几乎同时到达，则使系统平均作业周转时间最短的算法是短作业优先。解：设有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←n表示Pi进程占有n个资源。如果占有n个资源的进程被阻塞，可以用Pi*←n来表示，假设系统中有某类资源10个，进程P1,P2,P3各自的最大需求量为3,7,10个,各进程T0时刻开始运行:T1时刻发生:P1→2,P2→3,P3→3T2时刻发生:P2→1,P3→2T3时刻发生:P1→1,P2→1根据银行家算法,填写三个时刻的进行占有和阻塞情况.进程T0T1T2T3P1P2P3P2P3解：进程T0T1T2T3P1P1←0P1←2P1←2