二、应用题
（1）参考教材P23 1-19
在批处理系统中，有两个程序参与运行，其中A程序要做的工作依次为：计算10分钟，使用I/O1工作5分钟，计算5分钟，10分钟I/O2，计算10分钟。B程序要做的工作依次是：10分钟I/O1，计算10分钟，5分钟I/O2，计算5分钟，10分钟I/O2。假定多道运行时候是A先运行。计算运行时，两个程序的周转时间，和CPU利用率。
解：
（2）参考教材P40 2-12
假定系统有四道作业，它们的提交时间和运行时间（以小时为单位）如下表所示。在单道批处理系统中，采用先来先服务、最短作业优先的调度算法。分别计算下表作业的平均周转时间。 作业编号 提交时间（小时） 估计运行时间（小时） 1 2 3 4 解：
? 先来先服务：
? [2+(10-9+1.2)+(11.2-9.5+0.5)+(11.7-10.2+0.3)]/4=2.05(小时）
8：00 9：00 9.50 10.2 2.0 1.2 0.5 0.3 ? 短作业优先：
? [2+(0.5+0.5)+(0.3+0.3)+(10.8-9+1.2)]/4=1.65
（3）
有一个为数组清零的程序。系统为其分配两页，一页放程序，一页放被清零的数据。 假定程序已装入内存，且常驻。另外数据页页为空； 每页页面大小为128个整数； 假定矩阵A[128*128]按行存放。程序中i代表行，j代表列。 程序编制方法1： 程序编制方法2： For j:=1 to 128 For i:=1 to 128
For i:=1 to 128 For j:=1 to 128 A[i,j]:=0; A[i,j]:=0;
求：对于两种程序编制方法，分别产生多少次缺页中断？ 解
对于第一种方法：
产生的缺页中断次数为128*128次； 对于第二种方法：产生的缺页中断次数为128次.
（4）参考教材P100 4-20
? 有一个虚存系统，按行存储矩阵元素，一个进程要为矩阵进行清零操作，系统为该进程分配物理主存3页，系统用其中一页存储程序，且已经调入，其他两页空闲。按需调入矩阵数据。若进程按下列两种方式编程： ? Var A:arry[1..100, 1..100]of integer; ? 程序A:
? { for i:=1 to 100 do ? for j:=1 to 100 do ? A[I,j]:=0; ? } ? 程序B:
? { for j:=1 to 100 do ? for i:=1 to 100 do ? A[I,j]:=0; ? }
? (1)若每页存放200个整数，问采用A程序和B程序方式时，个执行过程分别会发生多少次缺页？
? （2）若每页只能存放100个整数时，会是什么情况？
解：
? 若每页存放200个整数，即每两行产生一次中断，程序A会发生50次缺页中断。程序B运行时，每页存放两列元素，内层循环每两次产生一次中断，共50次。外循环类似产生100次中断，共产生5000次中断。
? 若每页只能放100个整数，A程序产生100次中断：B程序产生10000次中断。
（5）参考教材P67 3-9
? 有一个阅览室，共100个座位。为了很好的利用它，读者进入时必须先在登记表上登记，该表设有座位号和读者姓名；读者离开时将其登记擦除。试问： ? （1）.为描写读者的动作应编写几个程序，应设几个进程，它们之间的关系是什么？
? （2）.试用P,V操作描述进程之间的同步算法。 解：
? 为描述阅览室，用一个登记表来记录使用情况。表中共有100项。每当有读者进入阅
览室时，为了正确地登记，各读者应互斥使用。为此设两个信号量。Mutex:互斥信号量，用来制约各读者互斥地进行登记，其初值为1；empty同步的信号量，用来制约各读者能同时进入阅览室的数量，初值为100。
? 下面用两个过程描述对表格应执行的动作： Mutex=1; empty=100; ? 登记过程： 擦除过程：
? begin begin ? p(empty) p(mutex)
? p(mutex) 找到自己的登记项 ? 找到一个登记项登记 v(mutex)
? v(mutex) v(empty) ? end end
（6）参考教材P67 3-15
设有8个进程M1,M2…M8,他们有如图3.6所示的优先关系，试用P,V操作实现这些进程的同步。
解：
? ? ? ? ? ? ? ? ? ?
设有信号量, S2, ,S26,S3,S36,…S38,S78; 并且初值均为0；
进程M1: M1,V(S2), V(S3),V( S4) 进程M2: P(S2), M2,V(S26)
进程M3: P(S3),M3,V(S36), V(S38) 进程M4: P(S4),M4, V(S47) 进程M5：M5, V(S57)
进程M6: P(S26), P(S36),M6
进程M7: P(S47), P(S57), M7,V(S78) 进程M8: P(S38), P(S78),M8
（7）参考教材P67 3-14
假定系统有n个进程，共享m个单位资源。规定进程对资源的申请和释放每次只申请或释放一个资源。每个进程最大需求不超过m个所有进程的需求资源总和小于m+n。为什么这种情况不会发生死锁。证明之。
解：
假定系统是死锁的，这时M个资源都已分配给进程。由进程资源图可知，系统死锁时，进程和资源节点组成的有向图形成环路。因此，有M+N条边。由题意可知，N个进程最大资源需求量 （8）用数学方法分析只考虑页表和碎片时，每一页的最佳尺寸为多少？ 答：用数学方法分析页面大小的影响： 假设进程大小的平均尺寸为S字节，每页大小为p字节，每个页表项占e个字节，每个进程所需页数近似s/p,则页表空间为es/p,进程由于内部碎片浪费的存储空间为平p/2.因此碎片和页表引起的系统总开销为 es/p+p/2 第一项是页表开销，页面越小，开销越大，第二项是碎片开销，页面越大，开销也越大。对上面的式子优化，对p求导。得方程： -se/p2+1/2=0 解方程得 因此在只考虑页表和碎片是页面的最佳尺寸为： （9）参考教材P123 5-13 磁盘上有一链接文件A。它有10个记录，每个记录长256B，存放在5个磁盘块中，如图所示。若要访问文件的第1574字节数据，应访问哪个盘快？要访问几次磁盘才能将该字节的内容读出。 物理块号 5 7 14 4 10 解： 2se链接指针 7 14 4 10 0 ? 要访问文件1574字节，先求它在文件中的相对块： ? 相对块号＝1574/(256*2)=3 块内位置为38。 ? 由3查链表得：相对块号3对应得物理块号为4。 ? 因此，应该访问4次磁盘才能把物理块读出，再从块内38的位置读即可。