四、P，V操作题（15分）
有n个进程将字符读入到一个容量为80的缓冲区中（n>1），当缓冲区满后，由另一个进程Pb负责一次取走这80个字符。这种过程循环往复，请写出n个读入进程（P1， P2，…Pn）和Pb的动作序列。（可以用文字或表达式来描述动作序列，并假设Pi每次读一个字符到缓冲区中。）
解：
var mutex,empty，full:semaphore;
count,in:integer
buffer:array[0..79] of char;
mutex:=1;empty:=80;full:=0;
count:=0;in:=0;
cobegin
process P i(i=1,...,n))
begin
L: 读入一字符到x;
P(empty);
P(mutex);
Buffer[in]:=x;
in:=(in+1) mod 80;
count++;
if (count==80) then
{count:=0;V(mutex);V(full);}
else V(mutex);
goto L;
end;
process Pb
begin
P(full);
P(mutex);
读出字符从buffer[0];
…
读出字符从buffer[79];
in:=0;
V(mutex);
for j:=1 to 80 do
V(empty);
end;
coend.
东南大学操作系统试题（2001）参考答案
一、判断题——指出下面的叙述是否正确（20分）
1．因为分时系统一定是多道系统，所以多道系统也一定是分时系统。(错)
2．批处理系统不允许用户随时干预自己作业的运行。(对)
3．进程是提交给计算机系统的用户程序。 (错)
4．在单处理机系统中最多允许两个进程处于运行状态。 (错)
5．OS允许用户创建自己的子进程，所以创建子进程的原语是在用户态下完成的。(错)
6．原语是一种特殊的系统调用，它的执行过程必须是不可中断的。(对)
7．因为临界资源一次只允许一个进程使用，所以临界资源不能共享。(错)
8．独占设备一次只允许一个用户使用，所以独占设备不能共享。(对)
9．使用P，V操作后，可以防止系统出现死锁。(错)
10．信号量的初值不能是负数。 (错)
11．线程是调度的基本单位，但不是资源分配的基本单位。(对)
12．在分时系统中，响应时间=时间片×用户数，因此为缩短响应时间，简单的方法就是使时间片越小越好。(错)
13．存储空间是指内存中的物理存储单元的集合，这些单元的编号称为绝对地址。(对)
14．覆盖和对换都需要从外存读入信息，所以覆盖是对换的别名。(错)
15．虚拟存储器是一个假想的存储空间，因而这个地址的大小是没有限制的。(错) 16．采用快表后分页系统访问主存时既要访问快表，又要访问页表，因此与没有快表的分页系统相比，降低了对主存的存取速度。(错)
17．公共过程段必须赋以相同的段号才能被各作业所共享。(对)
18．操作系统提供文件系统服务后，用户可按名存取文件，故用户使用的文件必须有不同的名字。 (错)
19．文件的逻辑组织是指文件在外存的存放形式。(错)
20．磁盘的先来先服务调度算法虽然平均的服务效率不高，但它是公平合理的。(对)
二、选择题——选择可以与指定位置的符号互换的最确切的答案（20分）
1．（A）是一种只能进行P操作和V操作的特殊变量。（A）可以用来实现异步并行进程之间的（B）和（C），（B）是指排他地访问共享资源，（C）则是指进程间在逻辑上的相互制约关系。（D）是可以用来实现异步并行进程的（B）和（C）的特殊程序结构。（D）中的（E）用来实现进程间的（C）。
供选择的答案：
A，B，C，D，E：（1）调度 （2）类程 （3）进程 （4）互斥 （5）信号量 （6）控制变量 （7）条件变量 （8）管程 （9）同步
（10）共享变量 （11）规程 （12）分配
A=（5）信号量 B=（4）互斥 C=（9）同步 D=（8）管程 E=（7）条件变量
2．批处理系统在作业运行的过程中，（A）的内容反映了作业的运行情况，并且是作业存在的惟一标志。在多道批处理系统中，为充分利用各种资源，运行的程序应具备的条件是（B），在批处理系统中，用户的作业是由（C）组成的。
供选择的答案：
A：（1）作业状态 （2）作业类型 （3）作业控制块 （4）作业优先
B：（1）适用于内存分配的 （2）计算量大的
（3）I/O量大的 （4）计算型和I/O型均衡的
C：（1）程序 （2）程序+数据
（3）程序+作业说明书 （4）程序+数据+作业说明书
A=(3) 作业控制块 B=（4）计算型和I/O型均衡的 C=（4）程序+数据+作业说明书
3．当为多道程序所提供的共享的系统资源不能满足要求时可能出现死锁。此外，
不适当的（A）也可能产生死锁。死锁产生的必要条件是（B），（C），不剥夺和环路等待。当出现死锁时，可以采用剥夺资源的方法。此外还可以采用（D）来解除死锁，采取措施预防死锁的发生（E）。
供选择的答案：
A：（1）程序并行操作 （2）资源的线性分配
（3）分配队列优先权 （4）进程推进顺序
B，C：（1）独占资源 （2）时间片过长 （3）信号量S=0
（4）执行P,V操作 （5）因请求资源而被阻塞的进程仍保持资源
（6）每种资源只有一个
D：（1）停止并行操作 （2）撤销进程
（3）拒绝分配新资源 （4）修改信号量
E：（1）是可能的 （2）是不可能的 （3）是否可能还未有定论
A=（4）进程推进顺序 B=（1）独占资源 C=（5）因请求资源而被阻塞的进程仍保持资源 D=（2）撤销进程 E=（1）是可能的
4．通过硬件和软件的功能扩充，把原来独占的设备改造成若干个用户共享的设备，这种设备称为（A）。与设备分配策略有关的因素有：设备的固有属性，设备分配算法，（B）和设备的独立性。CPU输出数据的速度远远高于打印机的打印速度，为解决这一矛盾，可采用（C）。
供选择的答案：
A：（1）存储设备 （2）系统设备 （3）虚拟设备 （4）用户设备
B：（1）设备使用的周期性 （2）设备的使用频度
（3）设备的配套性 （4）设备分配中的安全性
C：（1）并行技术 （2）通道技术 （3）缓冲技术 （4）虚存技术
A=（3）虚拟设备 B=（4）设备分配中的安全性 C=（3）缓冲技术
5．选择与下面各条叙述关系最密切的答案。
（a）作业调度中使用的平均等待时间最短的调度算法是（A）；
（b）为了保证数据的安全性而采取的一种措施是（B）；
（c）系统接通电源后自动从磁盘上引入操作系统的过程是（C）：
（d）进程之间在逻辑上的相互制约关系是（D）。
供选择的答案：
A：（1）先来先服务 （2）优先级 （3）短作业优先 （4）长作业优先
B：（1）数据校验 （2）授权控制 （3）记账系统 （4）系统管理员
C：（1）系统自举 （2）初始化 （3）系统生成 （4）系统自检
D：（1）同步 （2）组合 （3）连接 （4）唤醒
A=（3）短作业优先 B=（2）授权控制 C= （1）系统自举 D= （1）同步
三、简答题（每题5分）
1．假定有一个请求分页管理系统，在某时刻测得各相关成分的利用率为，CPU：20％，磁盘交换区：99％，其他I/O设备：10％，下面哪些措施将（可能），改进CPU的利用率，为什么?
（1）增加一个更快速的CPU：
（2）增加磁盘交换区的大小；
（3）增加多道程序的度数；
（4）减少多道程序的度数：
（5）增加其他更快速的I/O设备。
解：答：(1) CPU还有潜力，不必增加。(2) 磁盘容量己成瓶颈，更换更大的分页磁盘。(3) 因交换区己满，不宜增加多道程序道数。(4) 适当挂起一些用户进程，减少对交换区的压力。(5)由于其他I/O设备利用率很低，增加其他更快速的I/O设备是不必要的。
2．文件系统是如何利用访问控制表和访问权限表来控制进程对文件的访问的?
解：
访问控制用于防止文件主和其他用户有意或无意的非法操作所造成的文件不安全性，其基本思想是建立如下的三元组：
（用户、对象、存取权限）
用户：是指每一个操作系统使用者的标识。
对象：在操作系统中一般都是文件，因为，操作系统把设备资源也统一到文件层次，如通过设备文件使用设备、通过socket关联文件使用进程通信等。
存取权限：定义了用户对文件的访问权，如：读、写、删除、执行等等。一个安全性较高的系统权限划分得较多较细。
每当用户对文件访问时，根据访问控制表验证合法性和权限，以定该用户能否访问。
由于访问控制三元组规模大，对该矩阵按列分解(以文件为单位)，用户可分若干组，规定每组权限，所有用户组对文件权限的集合形成文件访问控制表。对该矩阵按行分解(以用户为单位)，构成了用户对文件的访问权限表(又叫权能表)。
3。分布式进程同步的常用算法有：Lamport算法，Richart和Agrawala算法以及令牌传送法，请按表对它们进行比较。
解：见教材第八章。
4．利用通道传送数据具有那些特点？它与DMA方式有何不同?
解：DMA方式虽比程序中断方式有了进步，但是，每发出一次I/O指令，只能读写一个数据块，如果希望一次读写多个离散的数据块，并能把它们传送到不同的主存区域，或相反时，则需要由CPU分别发出多条启动I/O指令及进行多次I/O中断处理才能完成。通道方式是DMA方式的发展，它进一步减少了CPU对I/O操作的干预，减少为对多个不连续的数据块，而不是仅仅一个数据块的传输，及有关管理和控制的干预。同时，为了获得中央处理器和外围设备之间更高的并行工作能力，也为了让种类繁多，物理特性各异的外围设备能以标准的接口连接到系统中，计算机系统引入了自成独立体系的通道结构。
5．在UNIX系统中把设备也进行“文件化”，即把设备看成文件。请问这样做有什么好处？
解：把设备统一在文件系统下，系统实现方便，也为用户使用设备及文件提供了一致性的接口。
|
算法名称 |
进程使用一次临界资源所需发送的消息数 |
发送的信息是否需要打上时间戳 |
可能存在的问题 |
|
Lamport |
|
|
|
|
R&A |
|
|
|
|
令牌传送 |
|
|
|
四、计算题（每题5分）
1．假设一个单CPU系统，以单道方式处理一个作业流，作业流中有两道作业，其占用CPU时间、输入卡片数、打印输出行数如表所示。
|
作业号 |
占用CPU计算时间（min） |
输入卡片张数 |
输出行数 |
|
1 |
3 |
100 |
2000 |
|
2 |
2 |
200 |
600 |
其中，卡片输入机速度为1000张/min（平均），打印机速度为1000行/min（平均），忽略读写盘时间。试计算：
（1）不采用SPOOLing技术，计算这两道作业的总运行时间（从第一个作业输入开始，到最后一个作业输出完毕）；
（2）如果采用SPOOLing技术，计算这两道作业的总运行时间。
解：(1)
作业1 输入100张卡片花6秒，计算花3分，打印2000行花2分。故合计花5分6秒。
作业2 输入200张卡片花12秒，计算花2分，打印600行花36秒。故合计花2分48秒。
不采用SPOOLing技术，两道作业的总运行时间=7分54秒。
(2) 如果采用SPOOLing技术，由于预输入和缓输出时间与其他任务重迭进行，这两道作业的总运行时间应=5分。
2．假设一个可移动磁头的磁盘具有200个磁道，其编号为0～199，当它刚结束了125道的存取，正在处理143道的服务请求，假设系统当前I/O请求队列如下： 86，147，91，177，94，150，102，175，130
试对以下磁盘I/O调度算法而言，满足以上请求队列，磁头将如何移动？
（1）先来先服务算法（FCFS）；
（2）最短查找时间优先调度（SSTF）；
（3）扫描法（SCAN）；
（4）单项扫描（循环扫描）（C-SCAN）；
（5）按移动距离大小排队，从小到大的顺序排列上述算法。
解：由题意知目前的磁头位于143道，且方向是向大的方向(对SCAN和C-SCAN有用)。FCFS---143,86，147，91,177，94，150，102，175，130。
SSTF---143,147,150,130,102,94,91,86,175,177。
SCAN---143,147,150,175,177,130,102,94,91,86。
C-SCAN—143,147,150,175,177,86,91,94,102,130。
从小到大的顺序排列SCAN，SSTF，C-SCAN，FCFS。
五、回答下列问题（每题5分）
1．给定一组作业J1，J2…Jn，它们的运行时间分别为T1，T2，…，Tn，假定这些作业是同时到达，并且将在一台CPU上按单道方式运行。
（1）试证明：若按最短作业优先调度算法运行这些作业，则平均周转时间最短；
（2）采用最短作业优先调度算法会产生什么问题？
答：首先，对n个作业按执行时间从小到大重新进行排序，则对n个作业：J1’，…，Jn’，它们的运行时间满足：T1’≤ T2’≤… ≤T(n-1)’≤Tn’。那么有：
T=[T1’ +( T1’+T2’)+ (T1’ + T2’+ T3’)+…+(T1’ + T2’+ T3’+…+ Tn’)]/n
=[n×T1’ +( n-1)×T2’+ (n-3)×T3’]+…+ Tn’]]/n
=(T1’ + T2’+ T3’+…+ Tn’)-[0×T1’+1×t2 ’ +2×T3’ +…+(n-1) Tn’]/n
由于任何调度方式下，T1’ + T2’+ T3’+…+ Tn’为一个确定的数，而当T1’≤ T2’≤… ≤T(n-1)’≤Tn’ 时才有：0×T1’+1×T2 ’ +2×T3’ +…+(n-1) Tn’的值最大，也就是说，此时T值最小。所以，按短作业优先调度算法调度时，使得平均作业周转时间最短。
采用最短作业优先调度算法会产长作业出现饥饿现象。
2．UNIX文件系统中有关盘块的分配与释放，是借助于超级块中的栈进行的。假定某时刻有图4-2-8情况。
假设此时某进程要删除文件A，并归还它所占据的盘块134#，220#，367#，389#和575#，请说明过程并给出删除完毕后有关数据及表目的更改情况。
 |
答：
见教材p515算法。
内存结果如图左。而367块号内容如图右。
 |
