二、应用题
（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
8：00
2.0
2
9：00
1.2
3
9.50
0.5
4
10.2
0.3
解：
● 先来先服务：
● [2+(10-9+1.2)+(11.2-9.5+0.5)+(11.7-10.2+0.3)]/4=2.05(小时）
● 短作业优先：
● [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个进程最大资源需求量<M+N,也就是说，进程与资源组成的有向图的边小于M+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
7
14
14
4
4
10
10
0
解：
⏹ 要访问文件1574字节，先求它在文件中的相对块：
⏹ 相对块号＝1574/(256*2)=3  块内位置为38。
⏹ 由3查链表得：相对块号3对应得物理块号为4。
⏹ 因此，应该访问4次磁盘才能把物理块读出，再从块内38的位置读即可。
（10）参考教材P122  5-10
文件系统的执行速度依赖于缓冲池中到盘块的比率。假设盘块从缓冲池读出用1毫秒，从盘上读出用40毫秒。从缓冲池到盘块的比率为n，请给出一个公式计算读盘块的平均时间，并画出n从0到1.0的函数图像。
解：
：读一个盘块的平均时间=(n*1)ms+40(1-n)ms
            =(40-39n)ms
画出n从0到1.0的函数图像如下：
（11）参考教材P68  3-21
● （1） 当前系统是安全的。这是因为：
●         剩余资源向量：1502
●       剩余请求矩阵为：      已分配矩阵：
●         0  0  0  0                        0  0  1  2
●         0  7  5  0                        1  0  0  0
●         1  0  0  2                        1  3  5  4
●         0  0  2  0                        0  6  3  2
●         0  6  4  2                        0  0  1  4
●     判断系统是否安全，只要检查系统剩余向量能否对各进程的剩余请求向量中能否到一个进程完成序列，当按照这个序列为各进程分配资源时，各进程都能成功完成，若能到，则系统是安全的，否则，为不安全。
● 先到p0,  因为p0已满足最大资源请求，它可以完成，释放其占有的资源，使系统剩余资源向量为：1514
● 之后，系统剩余资源向量（1514），可满足进程p2,  使p2 可以完成，释放其占有的资源，使系统剩余资源向量为：    2868
●    
● 之后无论选哪一个进程都可成功完成,故到的进程序列可为：p0,p2,p4,p3,p1;    或p0, p2,p3,p1,p4  等，故系统是安全的。
● （2）当p2提出（1001）请求时，因系统剩余可用向量为1502，同样应该按照要求，顺序检查，看能否到一个进程完成序列。首先进行假分配，1502-1001=0501。由于p0不再申请资源，它最终释放资源，使系统变为0513。之后满足P2，。。。，故系统是安全的。
（12）参考教材P68  3-20
同类资源10个，进程3个，分别申请的资源数量8，6，7。
（1）第5次分配后的各进程状态：
● ①p1申请3，可以满足，系统剩余7个；②p2申请2，可以满足，系统还剩5个；
● ③P3申请4个，不能满足，让其阻塞。因为如果满足它，就使系统处于不安全状态；
● ④P1申请2个，可以满足，系统还剩3个；⑤P2申请2个，不能满足，让其阻塞。