1、1 部分高校操作系统硕士研究生入学试题参考答案 北京大学 2000 操作系统硕士入学试参考答案 一、回答下列问题 （15 分） 1对某系统进行检测后表明平均每个进程在 I/O 阻塞之前的运行时间为 T，一 次进程的切换时间为 S，这里 S 实际上就是开销。对于时间为 Q 秒的轮转法进 程调度，分别就下列条件给出 CPU 的利用率的计算公式。 （1）Q=； （2）QT； （3）S0 表 示 还 有 共 享 资 源 可 供 使 用 。 S=0 表 示 共 享 资 源 正 被 进 程 使 用 但 没 有 进 程 等 待 使 用 资 源 。 S0 then z:=x+y: x:=x+a else z:
2、=x*y: b:=a+x print z; c:=b*b end. print c; end z 可能值=(3，-2，)，c 可能值=(9，81，25)。 3段页式系统中，其中作业的段表、页表格式如所示，页的大小为 1K，现有 逻辑地址为2|，其对应的物理地址为（页 2 对应 105，位移不变 ） 。 （5 分） 答： 段号 页表长 页表始址 0 1 1 2 2 3 页号 页面号 0 100 0 118 1 120 2 116 0 111 2 117 2 105 root A B C D E F1 11 4一个文件系统目录结构如图所示，文件采用的物理结构是串联结构，文件 F1 由 500 个逻
3、辑记录组成，每个磁盘块可存放 20 个逻辑记录。现在欲读取 F1 中的第 406#记录，文件系统的根目录现存放在内存，则最少需要读（23 ）个 磁盘块，才能取出 F1 的第 406#记录。 （5 分） 四、P，V 操作题（15 分） 有 n 个进程将字符读入到一个容量为 80 的缓冲区中（n1） ，当缓冲区满后，由 另一个进程 Pb 负责一次取走这 80 个字符。这种过程循环往复，请写出 n 个读 入进程（P1， P2，Pn）和 Pb 的动作序列。 （可以用文字或表达式来描述动作 序列，并假设 Pi 每次读一个字符到缓冲区中。 ） 解： var mutex,empty，full:semapho
4、re; count,in:integer buffer:array079 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); Bufferin:=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(
5、mutex); 读出字符从 buffer0; 读出字符从 buffer79; in:=0; V(mutex); for j:=1 to 80 do V(empty); end; coend. 12 东南大学操作系统试题（2001）参考答案 一、判断题指出下面的叙述是否正确（20 分） 1因为分时系统一定是多道系统，所以多道系统也一定是分时系统。(错) 2批处理系统不允许用户随时干预自己作业的运行。(对) 3进程是提交给计算机系统的用户程序。 (错) 4在单处理机系统中最多允许两个进程处于运行状态。 (错) 5OS 允许用户创建自己的子进程，所以创建子进程的原语是在用户态下完成 的。(错) 6原
6、语是一种特殊的系统调用，它的执行过程必须是不可中断的。(对) 7因为临界资源一次只允许一个进程使用，所以临界资源不能共享。(错) 8独占设备一次只允许一个用户使用，所以独占设备不能共享。(对) 9使用 P，V 操作后，可以防止系统出现死锁。(错) 10信号量的初值不能是负数。 (错) 11线程是调度的基本单位，但不是资源分配的基本单位。(对) 12在分时系统中，响应时间=时间片用户数，因此为缩短响应时间，简单的 方法就是使时间片越小越好。(错) 13存储空间是指内存中的物理存储单元的集合，这些单元的编号称为绝对地 址。(对) 14覆盖和对换都需要从外存读入信息，所以覆盖是对换的别名。(错) 1
7、5虚拟存储器是一个假想的存储空间，因而这个地址的大小是没有限制的。 (错) 16采用快表后分页系统访问主存时既要访问快表，又要访问页表，因 此与没有快表的分页系统相比，降低了对主存的存取速度。(错) 17公共过程段必须赋以相同的段号才能被各作业所共享。(对) 18操作系统提供文件系统服务后，用户可按名存取文件，故用户使用的文件 必须有不同的名字。 (错) 19文件的逻辑组织是指文件在外存的存放形式。(错) 20磁盘的先来先服务调度算法虽然平均的服务效率不高，但它是公平合理的。 (对) 二、选择题选择可以与指定位置的符号互换的最确切的答案（20 分） 1 （A）是一种只能进行 P 操作和 V 操
8、作的特殊变量。 （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）分配 13 A=（5）信号量 B=（4）互斥 C=（9）同步 D=（8）管程 E=（7）条件变 量 2批处理系统在作业运行的过程中， （A）
9、的内容反映了作业的运行情况，并且 是作业存在的惟一标志。在多道批处理系统中，为充分利用各种资源，运行的 程序应具备的条件是（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当为多道程序所提供的共享的系统资源不能满足要
10、求时可能出现死锁。此外， 不适当的（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）是不可能
11、的 （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）设备分配中的安
12、全性 14 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）系统自
13、举 （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 还有潜力，不必增
14、加。(2) 磁盘容量己成瓶颈，更换更大的分页磁盘。(3) 因交换区己满，不宜增加多道程序道数。(4) 适当挂起一些用户进程，减少对交换区的压 力。(5)由于其他 I/O 设备利用率很低，增加其他更快速的 I/O 设备是不必要的。 2文件系统是如何利用访问控制表和访问权限表来控制进程对文件的访问 的? 解： 访 问 控 制 用 于 防 止 文 件 主 和 其 他 用 户 有 意 或 无 意 的 非 法 操 作 所 造 成 的 文 件 不 安 全 性 ， 其 基 本 思 想 是 建 立 如 下 的 三 元 组 ： （用户、对象、存取权限） 用 户 ： 是 指 每 一 个 操 作 系 统 使 用 者
15、 的 标 识 。 对 象 ： 在 操 作 系 统 中 一 般 都 是 文 件 ， 因 为 ， 操 作 系 统 把 设 备 资 源 也 统 一 到 文 件 层 次 ， 如 通 过 设 备 文 件 使 用 设 备 、 通 过 socket 关 联 文 件 使 用 进 程 通 信 等 。 存 取 权 限 ： 定 义 了 用 户 对 文 件 的 访 问 权 ， 如 ： 读 、 写 、 删 除 、 执 行 等 等 。 一 个 安 全 15 性 较 高 的 系 统 权 限 划 分 得 较 多 较 细 。 每当用户对文件访问时，根据访问控制表验证合法性和权限，以定该用户 能否访问。 由于访问控制三元组规模大
16、，对该矩阵按列分解(以文件为单位)，用户可 分若干组，规定每组权限，所有用户组对文件权限的集合形成文件访问控制表。 对该矩阵按行分解(以用户为单位)，构成了用户对文件的访问权限表(又叫权能 表)。 3。分布式进程同步的常用算法有：Lamport 算法，Richart 和 Agrawala 算 法以及令牌传送法，请按表对它们进行比较。 解 ： 见 教 材 第 八 章 。 4利用通道传送数据具有那些特点？它与 DMA 方式有何不同? 解：DMA 方式虽比程序中断方式有了进步，但是，每发出一次 I/O 指令，只能读写一 个数据块，如果希望一次读写多个离散的数据块，并能把它们传送到不同的主存区域，或
17、相反时，则需要由 CPU 分别发出多条启动 I/O 指令及进行多次 I/O 中断处理才能完成。通 道方式是 DMA 方式的发展，它进一步减少了 CPU 对 I/O 操作的干预，减少为对多个不连续 的数据块，而不是仅仅一个数据块的传输，及有关管理和控制的干预。同时，为了获得中 央处理器和外围设备之间更高的并行工作能力，也为了让种类繁多，物理特性各异的外围 设备能以标准的接口连接到系统中，计算机系统引入了自成独立体系的通道结构。 5在 UNIX 系统中把设备也进行“文件化” ，即把设备看成文件。请问这样 做有什么好处？ 解：把设备统一在文件系统下，系统实现方便，也为用户使用设备及文件 提供了一致性
18、的接口。 算法名称 进程使用一次临界资源所 需发送的消息数 发送的信息是否 需要打上时间戳 可能存在的问题 Lamport R direction(up,down); busy:boolean; S:array099 of condition; DEFINE request,return; USE wait,signal,check,release; procedure request(var dest:integer); begin check(IM); if busy then wait(Sdest,IM); busy:=true; if (headpos1，即系统还有一个资源可以使用，就
19、可 以使这几个进程中的一个进程获得所需的全部资源，该进程可以运行结束，释 放出所占有的资源，供其他进程使用，从而每一个进程都可以执行结束。 因而，当：m-n（x-1）1 时，即 n（x-1）+1m 时，系统不会发生死锁。 3用 P，V 操作实现这些进程间的同步算法如下： BEGIN S1，S2，S3，S4：semaphore； S1：=S2：=S3：=S4：=0 Cobegin Process P1： Begin do all work； V（S1） ； F1(100K) F2(50K) B(70K) F1(30K) A(30K) F2(20K) A(30K) B(70K) C(50K) 61
20、 V（S1） ； End Process P2： Begin P（s1） do all work； V（s2） ； End Process P3： Begin P（s1） ； do a11 work； V（s3） ； End Process P4： Begin P（s2） ； do a11 work； V（s4） ； End Prorcess P5： Begin P（s3） ； Do all work； V（34） ； End Prorcess P6： Begin P（s4） ； P（s4） ； do a11 work； End Coend END 4 （1）一个作业最多可以有 28=256 段。 （2）每段的最大长度为 216=64KB=65 536 字节。 （3）逻辑地址0，430的主存地址为：2100+430=2530； 逻辑地址1，50无法进行地址变换，因为产生了越界中断； 逻辑地址2，30无法进行地址变换，因为产生了缺段中断； 逻辑地址3，70的主存地址为：4000+70=4070。 5文件 A 在磁盘上占用 5 簇，簇号依次是 002，004，009，005，007。文 件 B 在磁盘上占用 3 簇，簇号依次是 003，008，006。
