名校操作系统历年考研试题(含解答)资料.pdf

《名校操作系统历年考研试题(含解答)资料.pdf》由会员分享，可在线阅读，更多相关《名校操作系统历年考研试题(含解答)资料.pdf（70页珍藏版）》请在三一文库上搜索。

1、名校操作系统考研试题与解答 10.1 北京大学1997 年考研操作系统试题 ( 一) 名词术语解释 ( 每小题 5 分 , 共 30 分) 1. 进程状态 2.快表 3.目录项 4. 系统调用 5.设备驱动程序 6.微内核 ( 二) 填空 ( 每小题 1 分,共 10 分 ) 1. 如果系统中有n 个进程 , 则在等待队列中进程的个数最多为_个。 2. 在操作系统中 , 不可中断执行的操作称为_。 3. 如 果 系 统 中的 所 有 作业 是 同 时 到 达的 , 则 使作 业 平 均 周 转时 间 最 短的 作 业 调 度是 _。 4. 如果信号量的当前值为-4, 则表示系统中在该信号量上有

2、_个等待进程。 5. 在有 m个进程的系统中出现死锁时, 死锁进程的个数k 应该满足的条件是_。 6. 不让死锁发生的策略可以分为静态和动态两种, 死锁 避免 属于 _。 7. 在操作系统中 , 一种用空间换取时间的资源转换技术是_。 8. 为实现 CPU与外部设备的并行工作, 系统引入了 _硬件机制。 9. 中断优先级是由硬件规定的, 若要调整中断的响应次序可通过_。 10. 若使当前运行的进程总是优先级最高的进程, 应选择 _进程调度算法。 ( 三) 问答题 ( 每小题 15 分, 共 30 分) 1. 消息缓冲通信技术是一种高级通信机制, 由 Hansen首先提出。 (1) 试述高级通信

3、机制与低级通信机制P、V原语操作的主要区别。 (2) 请给出消息缓冲机制( 有界缓冲 ) 的基本原理。 (3) 消息缓冲通信机制( 有界缓冲 ) 中提供发送原语Send(receiver,a),调用参数 a表示发送 消息的内存区首地址, 试设计相应的数据结构, 并用 P、V原语操作实现Send 原语。 2. 在虚拟段式存储系统中, 引入了段的动态链接。 (1) 试说明为什么引入段的动态链接。 (2) 请给出动态链接的一种实现方法。 ( 四)( 共 10 分) 在实现文件系统时, 为加快文件目录的检索速度, 可利用 “文件控制块分解法“ 。假设目录文件 存放在磁盘上,每个盘块为512 字节。文件

4、控制块占64 字节 , 其中文件名占8 字节。通常将文 件控制块分解成两个部分, 第一部分占10 字节 ( 包括文件名和文件内部号), 第二部分占56 字 节( 包括文件内部号和文件其他描述信息) 。 (1) 假设某一目录文件共有254 个文件控制块 , 试分别给出采用分解法前和分解法后, 查找该 目录文件的某一个文件控制块的平均访问磁盘次数。 (2) 一般地 , 若目录文件分解前占用n个盘块 ,分解后改用m个盘块存放文件名和文件内部号部 分, 请给出访问磁盘次数减少的条件。 ( 五)( 共 10 分 设系统中有三种类型的资源(A、B、C)和五个进程 (P1、P2、P3、P4、P5),A 资源

5、的数量为17,B 资源的数量为5,C 资源的数量为20。在 T0时刻系统状态如表1 和表 2 所示。系统采用银行家 算法实施死锁避免策略。 T0时刻是否为安全状态? 若是 , 请给出安全序列。 在 T0时刻若进程P2请求资源 (0,3,4),是否能实施资源分配? 为什么 ? 在的基础上, 若进程 P4请求资源 (2,0,1),是否能实施资源分配? 为什么 ? 在的基础上, 若进程请求资源(0,2,0),是否能实施资源分配? 为什么 ? 表 1 T0时刻系统状态 进程 最大资源需求量已分配资源数量 A B C A B C P1 P2 P3 P4 P5 5 5 9 5 3 6 4 0 11 4 2

6、 5 4 2 4 2 1 2 4 0 2 4 0 5 2 0 4 3 1 4 表 2 T0时刻系统状态 A B C 剩余资源数 2 3 3 ( 六)( 共 10 分)某高校计算机系开设有网络课并安排了上机实习, 假设机房共有2m台机 器, 有 2n 名学生选该课,规定 : 每两个学生组成一组, 各占一台机器 , 协同完成上机实习； 只有一组两个学生到齐, 并且此时机房有空闲机器时, 该组学生才能进入机房； 上机实习由一名教师检查, 检查完毕 , 一组学生同时离开机房。 试用 P 、V操作模拟上机实习过程。 北京大学 1997 年级研操作系统试题解答 ( 一) 名词术语解释 ( 每小题 5 分

7、, 共 30 分) 1. 进程在其存在过程中,由于各进程并发执行及相互制约, 使得它们的状态不断发生变化。一 般来说进程主要有三种基本状态, 这三种基本状态是: 就绪状态、运行状态和阻塞状态。 2. 在页式存储管理系统中的地址变换过程中, 由于页表是存放在内存中的,CPU 每访问一个数 据( 或一条指令 ) 至少要访问内存两次, 一次是访问页表, 确定所取数据( 或指令 ) 的物理地址 , 第二次才根据该地址访问数据( 或指令 ) 。 为了提高查表速度, 在地址变换机构中加入了一个高 速、小容量的联想寄存器, 构成一张快表。如果快表被命中, 只要访问内存一次即可存取一个 数据。 3. 在文件系

8、统中 , 文件目录记录文件的管理信息, 每个文件在目录表中都有一个目录项。文件 目录项主要包含下列信息: (1) 有关文件的标识信息, 例如文件的名称符号。 (2) 有关文件结构的信息, 例如文件长度、文件存放在外存中的物理地址等。 (3) 有关文件的存取控制信息, 例如文件属性、文件主及共享用户的标识、存取权限等。 (4) 有关文件的管理信息, 例如文件建立的时间、保留时间、最新修改时间等。 4. 系统调用是用户在程序中能用“ 访管指令 “调用的由操作系统提供的子功能的集合。每一个 子功能称为一条系统调用命令( 或广义指令 ) 。系统调用是操作系统在程序级给用户提供的接 口。系统调用与一般过

9、程调用不同, 其主要区别是: 运行的状态不同: 进入的方式不同: 代码层次不同。 5 设备驱动程序也称为I/O 处理程序 , 是一种低级的系统例程, 它向上与高级I/0操作原语相 对应 , 向下与 I/0硬设备相对应,完成两者间的相互通信。它们一般是用汇编语言编写, 针对具 体的 I/0设备控制器 , 进行控制编码或微程序操作。设备驱动程序早期是操作系统的一部分, 后来将其中的公共部分作为高级I/O操作原语留在操作系统中, 而把与物理设备有直接关系 的部分脱离操作系统, 交给设备厂商和软硬件开发商编制。因此, 设备驱动程序己成为系统的 选件 , 系统和用户可以根据需要选择配置设备, 灵活地装载

10、、 卸载驱动程序 , 从而极大地增强了 系统的开放性和可扩展性。 6. 操作系统有两种内核组织形式: 强内核 (Monolithic kernel)和微内核 (Micro kernel)。 微 内核结构是一种新的结构组织形式, 它体现了操作系统结构设计的新思想。其设计目标是使操 作系统的内核尽可能小,使其它所有操作系统服务都放在核外用户级完成。微内核仅仅提供以 下四种服务: 进程间通信机制: 某些存储管理: 有限的低级进程管理和调度: 低级 I/0 。微内核的基本思想是良好的结构化、模块化, 最小的公共服务。具有微内核的操作系统 称为微内核操作系统。 ( 二) 填空 ( 每小题 1 分,共 1

11、0 分 ) 1.n-1 2.原语 3.短作业优先算法 4.四 5.km 6. 动态策略 7.缓冲区技术 8.中断和通道 9.软件实现 10.剥夺式优先级 ( 三) 问答题 ( 每小题 15 分, 共 30 分) 1.( 见西安交大2000 年考题中第五题的解答) 2.(1)在作业装入内存运行前, 应将各个目标程序定位后装入作业的地址空间, 形成可执行程 序的链接 , 称为静态链接。静态链接常常因为目标程序个数多而花费大量的CPU时间 , 而实际 运行时又常常只用到其中的部分模块, 因而也造成了存储空间的浪费。动态链接是作业运行时 先装入主程序, 运行过程中需要某模块时, 再将该模块的目标程序调

12、入内存并进行链接, 它克 服了静态链接的不足。 (2) 分段存储管理就是最典型的动态链接。分段管理允许用户将作业按逻辑关系进行自然分段, 各段的大小可以不同。逻辑段内的地址是由两部分组成的(s: 段号 ,d ：段内位移量 ), 即分段 地址空间是用户定义的二维空间。内存分配以段为单位, 段可以在作业运行过程中根据请求而 动态链接和装入。 ( 四)( 共 10 分)利用 “文件控制块分解法“加快文件目录的检索速度, 其原理是减少因查找文件 内部号而产生的访问磁盘次数。因为在进行查找文件内部号的过程中不需要把文件控制块的 所用内容都读入内存, 所以在查找过程中减少所需读入的存储块就有可自色减少访问

13、磁盘的 次数。但是 , 采用这种方法访问文件, 当找到匹配的文件控制块后, 还需要访问一次磁盘, 才能 读出全部的文件控制块信息。这就是为何采用这种方法在一定条件下并不能减少访问磁盘的 次数的原因。 (1) 采用分解法前 , 查找该目录文件的某一个文件控制块的平均访问磁盘次数为: 64(254/2)/512=16 采用分解法后,查找该目录文件的某一个文件控制块的平均访问磁盘次数为: 10(254/2)/512+1=4 (2) 访问磁盘次数减少的条件为 64 (x/2)/512 10(x/2)/512+1，解不等式得x=19 时访 问磁盘的次数减少。 ( 五)( 共 10 分) T0时刻是安全状

14、态, 因为可以找到一个安全的序列(P4,P5,Pl,P2,P3) 。 不能分配。因为所剩余的资源数量不够。 可以分配。 当分配完成后 , 系统剩余的资源向量为(0,3,2),这时仍可找到一个安全的序列队, (P4,P5,Pl,P2,P3) 。 不能分配。若分配完成后, 系统剩余的资源向量为(0,3,匀, 这时无法找到一个安全的序列。 ( 六)( 共 10 分)在本题中 , 为了保证系统的控制流程, 增加了 Monitor进程 , 用于控制学生的进 入和计算机分配。 从题目本身来看, 虽然没有明确写出这一进程, 但实际上这一进程是存在的。 因此 , 在解决这类问题时, 需要对题目加以认真分析,

15、找出其隐蔽的控制机制。 上机实习过程可描述如下: BEGIN student,computer,enter,finish,check:semaaphore; studen:=0; computer:=2m; mter:=0; finish :=O; check :=0; COBEGIN Process Procedure Student: begin V(student); 表示有学生到达 P(computer); 获取一台计算机 P(enter); 等待允许进入 DO it with partner; V(finish); 表示实习完成 P(check); 等待教师检查 V(computer

16、); 释放计算机资源 end Process Procedure Teacher: begin L1:P(finished); 等待学生实习完成 P(finished); 等待另一学生实习完成 check the work; V(check); 表示检查完成 V(check); 表示检查完成 goto L1; end Process Procedure Monitor begin L2: P(student); 等待学生到达 P(student); 等待另一学生到达 V(enter); 允许学生进入 V(enter); 允许学生进入 end Coend END 10.2 西安交通大学1999

17、年考研操作系统试题 ( 一) 名词解释 (30 分, 每小题 5 分) 1. 多道程序设计 2.工作目录 3. 线程与进程 4.地址空间与存储空间 5. 通道 6.系统调用 ( 二) 判断、选择与填空题( 每题 1 分, 共 15 分) 1. 程序的并发执行是指同一时刻有两个以上的程序, 它们的指令在同一处理器上执行。() 2. 对于请求分页式存储管理系统, 若把页面的大小增加一倍, 则缺页中断次数会减少一半。() 3. 三个用户在同一系统上同时对他们的C 语言源程序进行编译, 此时系统应分别为各用户创 建一个 C编译进程及保留一份C编译程序副本。() 4. 可顺序存取的文件不一定能随机存取,

18、 但是 , 凡可随机存取的文件都可以顺序存取。() 5. 缓冲技术是借用外存储器的一部分区域作为缓冲池。() 6. 在操作系统中 ,P、V操作是一种 _。 (A) 机器指令 (B)系统调用命令 (C) 作业控制命令 (D)低级进程通讯原语 7. 最佳适应算法的空白区是_。 (A) 按大小递减顺序排列的 (B)按大小递增顺序排列的 (C) 按地址由小到大排列的 (D)按地址由大到小排列的 8. 把作业地址空间中使用的逻辑地址变成内存中的物理地址称为_。 (A) 加载 (B)重定位 (C)物理化 (D)逻辑化 9. 文件系统用 _组织文件。 (A) 堆核 (B)指针 (C)目录 (D)路径 10.

19、 磁盘是设备 ,磁带是设备 , 显示器是 _设备。 (A) 输入 (B)输出 (C)输入输出 (D)虚拟 11. 并发进程中涉及相同变量的程序段叫做_, 对这些程序段要执行_。 12. 分区存储管理方案不能实现虚拟的原因是_。 13. 目前认为逻辑文件有两种类型, 即_式文件与 _式文件。 14. 进程调度算法采用等时间片轮转法, 时间片过大 , 就会使轮转法转化为_调度算法。 15. 采用交换技术获得的好处是以牺牲_为代价的。 ( 三) 简答题 ( 每题 10 分 ,共 50 分) 1. 试述分时系统与实时系统, 并比较它们的区别。 2. 何谓虚拟存储器?举一例说明操作系统是如何实现虚拟内存

20、的。 3. 什么是 P、 V操作 ? 试用 P、V操作描述读者一写者问题。要求允许儿个阅读者可以同时读 该数据集 , 而一个写者不能与其他进程( 不管是写者还是读者)同时访问该数据集。 4. 磁盘请求的柱面按10,22,20,2,40,6,38的次序到达磁盘的驱动器, 寻道时每个柱面移动需 要 6ms 。计算按以下算法调度时的寻道时间: (1) 先来先服务 ; (2)下一个最邻近的柱面; (3)电梯算法。 以上所有情况磁头臂均起始于柱面20。 5. 对 3种不同的保护机制, 即权限 , 存取控制表以及UNIX操作系统的RWX 位, 简述下面的情况 分别适用于哪些机制。 (1) 甲用户希望除他的

21、同事以外,任何人都能读取他的文件; (2) 乙用户和丙用户希望共享某些秘密文件; (3) 丁用户希望公开他的一些文件。 西安交通大学1999 年考研操作系统试题解答 ( 一) 名词解释 (每小题 5 分, 共 30 分) 1. 多道程序设计是指在主存中同时存放多道用户作业, 它们都处于执行的开始点和结束点之 间。多道程序设计的特点如下: (1) 多道。主存中有多道程序, 它们在任一时刻必须处于就绪、运行、阻塞三种状态之一。 (2) 宏观上并行。从宏观上看, 它们在同时执行。 (3) 微观上串行。从微观上看, 它们在交替、穿插地执行。 采用多道程序设计后, 减少了 CPU时间的浪费。 尤其对计算

22、题的作业, 由于 I/O 操作较少 ,CPIJ 浪费的时间很少。 2. 文件系统如果采用多级树型目录, 那么使用完整的路径名来查找文件会感到很不方便, 因此 引入了 “ 工作目录 “。 考虑到通常一个进程在一段时间内所访问的文件具有局部性, 即在某一范 围之内 , 所以可在这一段时间内指定某一目录为工作目录或值班目录。以后的操作一般都是针 对以工作目录(也称为当前目录)为根的子目录树进行的。 3. 所谓线程 (thread),从操作系统的管理角度看, 就是指 “ 进程的一个可调度实体“, 是处理机 调度的基本单位: 从编程逻辑看,线程是指 “程序内部的一个单一的顺序控制流“ 。 线程是进程的一

23、个组成部分, 每个进程在创建时通常只有一个线程, 由这个线程再创建其它进 程。通常一个进程都有若干个线程, 至少会有一个线程。 进程和线程是构造操作系统的两个基本元素, 两者之间的主要区别是: (1) 调度方面 : 线程作为调度分派的基本单位。 (2) 并发性方面 : 进程之间可以并发执行。 (3) 拥有资源方面: 进程是拥有资源的基本单位, 线程除少量必不可少的资源外, 基本上不拥 有资源 , 但它可以访问其隶属进程的资源。 (4) 系统开销 : 进程间切换时要涉及到进程环境的切换, 开销比较大。而线程间的切换只需保 存和设置少量的寄存器内容。因此进程问切换的系统开销远大于线程问切换的系统开

24、销。 4. 程序经编译和连接以后转变为相对地址编址形式, 它是以 0 为基址的。相对地址也叫逻辑地 址或虚地址。地址空间是逻辑地址的集合。 计算机系统实际的内存地址是绝对地址。绝对地址又叫物理地址或实地址。存储空间是 物理地址的集合。 5. 通道又称 I/O 处理机 , 它使主机摆脱了管理I/O 的工作 , 彻底实现了主机和外设的并行操作。 具有通道结构的计算机系统, 主存、通道、控制器和设备之间采用四级连接, 实施三级控制。 这样 ,I/O系统就由通道、控制器、设备三级构成。一个CPU可以连接多个通道, 一个通道可 以连接多个控制器, 一个控制器可以连接同类型的多台设各。另一方面, 也允许将

25、一台设备连 接到几个控制器上, 或一个控制器连接到几个通道上。按信息交换方式和连接的设备类型不同, 可以将通道分为三种类型: (1) 字节多路通道；(2) 选择通道； (3) 数组多路通道 6. 系统调用是用户在程序中能用“ 访管指令 “调用的由操作系统提供的子功能的集合。 每一个子功能称为一条系统调用命令或广义指令 。 系统调用是操作系统在程序级给用户提 供的接口。 ( 二) 判断、选择与填空题( 每题 1 分, 共 15 分) 1. 错 2.错 3.错 4.对 5.错 6.(D) 7.(B) 8.(B) 9.(C) 10.(C)和(D),(C),(B) 11. 临界区互斥 12. 作业的地

26、址空间不能超过存储空间 13. 有结构的记录无结构的流 14. 先来先服务 (FCFS) 15.CPU时间 ( 三) 简答题 ( 每题 10 分 ,共 50 分) 1. 所谓分时系统, 就是在一台计算机上, 连接多个终端, 用户通过各自的终端和终端命令把作 业送入计算机,计算机又通过终端向各用户报告其作业的运行情况, 这种计算机能分时轮流地 为各终端用户服务并能及时对用户服务请求予以响应, 这就构成了分时系统。 分时系统设计的 主要目标是使用户能与系统交互作用, 对用户的请求及时响应, 并在可能的条件下尽量提高系 统资源的利用率。 实时系统是为了能对特定输入做出及时响应, 并在规定的时间内完成

27、对该事件的处理而 引入的。实时系统分为两大类z 实时控制系统和实时信息处理系统。 (1) 实时控制系统 : 在这类应用中要求计算机系统实时采集测量系统的数据, 对被测量的数据 及时进行加工处理及输出。它主要用于军事和生产过程中的自动控制领域。 (2) 实时信息处理系统：在这类应用中要求计算机系统能对用户的服务请求及时作出回答, 并 能及时修改、处理系统中的数据。它主要用于像飞机票的预定、银行储蓄的财务管理等大量 数据处理的实时系统中。 实时系统与分时系统的主要区别如下: 系统的设计目标不同。分时系统的设计目标是提供一种随时可供多个用户使用的通用性很 强的系统 : 而实时系统则大多数都是具有某种

28、特殊用途的专用系统。 响应时间的长短不同。分时系统的响应时间通常为秒级: 而实时系统的响应时间通常为毫秒 级甚至是微秒级。 交互性的强弱不同。分时系统的交互性强, 而实时系统的交互性相对较弱。 2. 在操作系统中, 通过一些硬件和软件的措施为用户提供了一个其容量比实际主存大得多的 存储器 , 称为虚拟存储器。 操作系统要实现虚拟内存, 必须把主存和辅存统一管理起来, 即大作业程序在执行时, 有一部 分地址空间在主存, 另一部分在辅存, 当访问的信息不在主存时, 由操作系统将其调入主存并 实现自动覆盖功能, 使用户在编写程序时不再受主存容量的限制。 例如在请求分页存储管理系统中, 用户作业的所有

29、页面并不一定都在实存, 在作业运行过 程中再请求调入所用的虚页。为了实现从逻辑地址空间到物理地址空间的变换, 在硬件上必须 提供一套地址变换机构, 动态地址变换机构自动地将所有的逻辑地址划分为页号和页内地址 两部分 , 并利用页表将页号代之以块号, 把块号和页内地址拼接就得到了内存的物理地址, 从 而实现了虚拟存储器。 3. 读者一写者问题是经常出现的一种同步问题。计算机系统中的数据( 文件、记录 ) 常被多个 进程共享 , 但其中某些进程可能只要求读数据( 称为Reader): 另一些进程则要求修改数据( 称 为 Writer)。就共享数据而言,Reader 和 Writer是两种不同类型的

30、进程。一般地 , 两个或两个 以上的Reader 进程同时访问共享数据时不会产生副作用, 但若某个Writer和其它进程 (Reader 或 Writer)同时访问共享数据时, 则可能产生错误。 为了避免错误 , 同时尽可能地让读 者进程和写者进程并发运行, 只要保证任何一个写者进程能与其它进程互斥访问共享数据即 可。这个问题称为读者一写者问题。下面使用信号量机构来描述这一问题。 P、V操作是定义在信号量s 上的两条原语, 它是解决进程同步与互斥的有效手段。 定义下列信号量: 互斥信号量rmutex, 初值为1, 用于使读者互斥地访问读者计数器, 共享 变量 rcount: 互斥信号量wmut

31、ex, 初值为 1, 用于实现写者之间以及写者与读者之间互斥地访 问共享数据集。则用信号量和P、V操作描述读者一写者问题如下: Begin rmutex wmutex:semaphore; rcount:Integer; rmutex=wmutex=1; rcount=0; Cobegin Process procedure Reader begin repeat , P(rmutex); rcount:=rcount+1 if rcount=l then P(rmutex); V(rmutex); perfonn read operations; P(rmutex); rcount:=rco

32、unt-1; if rcount=O then V(rmutex); V(rmutex); , until fa1se; end Process procedure Writer begin repeat , P(wmutex); perform write operations; V(wmutex); , until false; end Coend End 4. 该题的解题方法是先计算出每种算法的柱面移动总量。因为每个柱面移动需要6ms,所以 , 寻道时间 =柱面移动总量6ms。 (1) 先到先服务算法的调度顺序为:10,22,20,2,40,6,38 柱面移动总量为:146 寻道时间为

33、:146 6ms=876ms (2) 下一个最邻近柱面算法调度顺序为:20,22,10,6,2,38,40 柱面移动总量为:60 寻道时间为 :60 6ms=360ms (3) 电梯算法调度顺序为:20,22,38,40,10,6,2 柱面移动总量为:58 寻道时间为586ms=348ms 5. 第(1) 种情况只适合用存取控制表实现保护机制。 第(2) 种情况适合用权限或存取控制表实现保护机制。 第(3) 种情况适合用存取控制表或RWX 位或权限实现保护机制。 10.3 西安交通大学2000 年考研操作系统试题 ( 一) 名词解释 (15 分) 1. 线程 2.分时系统 3.系统调用 4.

34、地址再定位 5.多道程序设计 ( 二) 简答题 (32 分) 1. 覆盖技术与虚拟存储技术有何本质不同?交换技术与虚存中使用的调入/ 调出技术有何相同 与不同之处 ? 2. 文件顺序存取与随机存取的主要区别是什么?它们对有结构文件与无结构文件的操作有何 不同 ? 3. 死锁和竞争有何关系? 4. 何请虚拟设备 ? 请说明 SPOOLing系统是如何实现虚拟设备的。 ( 三 )(10分 ) 有5 个 任 务A,B,C,D,E,它 们 几 乎 同 时 到 达 , 预 计 它 们 的 运 行 时 间 为 10,6,2,4,8mn。其优先级分别为3,5,2,1和 4, 这里 5 为最高优先级。 对于下

35、列每一种调度算 法, 计算其平均进程周转时间( 进程切换开销可不考虑) 。 (1) 先来先服务 (按 A,B,c,D,E)算法。 (2) 优先级调度算法。 (3) 时间片轮转算法。 ( 四)(10 分) 在虚拟页式存储系统中引入了缺页中断。 1. 试说明为什么引入缺页中断。 2. 缺页中断的实现由哪几部分组成?并分别给出其实现方法。 ( 五)(13 分) 消息缓冲通信技术是一种高级通信机制, 由 HANSEN 首先提出。 1. 试叙述高级通信机制与低级通信机制P、 V原语操作的区别。 2. 请给出消息缓冲通信机制( 有界缓冲 ) 的基本工作原理。 3. 试设计相应的数据结构, 并用 P 、 V

36、原语操作实现Send和 Receive 原语。 西安交通大学2000 年考研操作系统试题解答 ( 一) 名词解释 (15 分) 1. 所谓线程 (thread),从操作系统管理角度看线程是指“ 进程的一个可调度实体“, 是处理机调 度的基本单位: 从编程逻辑看线程是指“程序内部的一个单一的顺序控制流“ 。线程是进程的 一个组成部分。 2. 所谓分时系统, 就是指在一台计算机上, 连接多个终端, 用户通过各自的终端和终端命令把 作业送入计算机, 计算机又通过终端向各用户报告其作业的运行情况。这种计算机能分时轮流 地为各终端用户服务并能及时对用户服务请求予以响应, 这就构成了分时系统。 分时系统设

37、计 的主要目标是使用户能与系统交互作用, 对用户的请求及时响应, 并在可能的条件下尽量提高 系统资源的利用率。分时系统的主要特征是: 同时性 : 若干个终端用户按照系统提供的各种服务, 在各自终端进行操作, 同时使用一台计 算机资源。宏观上看是各用户在并行工作, 微观上看是各用户轮流使用计算机。 独立性 : 用户间可以相互独立地操作, 互不干涉 , 系统保证各用户程序运行的完整性, 不会发 生相互混淆或破坏现象。 及时性 : 系统可对用户的输入及时作出响应。分时系统性能的主要指标之一是响应时间, 它 是指从终端发出命令到系统予以应答所需的时间。 交互性 : 用户可根据系统对请求的响应结果, 进

38、一步向系统提出新的请求, 即能使用户和系 统进行人一机对话的工作方式, 所以分时系统也被称之为交互式系统。 3. 系统调用是指用户在程序中能用“ 访管指令 “ 调用的由操作系统提供的子功能的集合。每一 个子功能称为一条系统调用命令( 或广义指令 ) 。系统调用是操作系统在程序级给用户提供的 接口。 4. 所谓地址再定位, 就是当一个程序装入到与其地址空间不一致的存储空间而进行的地址变 换过程 , 即将地址空间给出的逻辑地址映射到内存的物理地址。地址重定位有静态重定位和动 态重定位两种方式。 5. 多道程序设计是指在主存中同时存放多道用户作业, 它们都处于执行的开始点和结束点之 间。多道程序设计

39、的特点如下: (1) 多道。主存中有多道程序, 它们在任一时刻必须处于就绪、运行、阻塞三种状态之一。 (2) 宏观上并行。从宏观上看, 它们在同时执行。 (3) 微观上串行。从微观上看, 它们在交替、穿插地执行。 采用多道程序设计后, 减少了 CPU时间的浪费。尤其对计算题的作业, 由于 I/O 操作较少 ,CPU 浪费的时间很少。 ( 二) 简答题 (32 分) 1. 覆盖技术与虚拟存储技术最本质的不同在于覆盖的程序段的最大长度要受到物理内存 容量的限制, 而虚拟存储器的最大长度不受物理内存容量的限制, 只受计算机地址结构的限 制。另外 , 使用覆盖技术要求程序员必须精心地设计程序及其数据结

40、构, 使得要覆盖的段具有 相对独立性 , 不存在直接联系或相互交叉访问。而虚拟存储技术对用户的程序段之间没有此要 求。 交换技术与虚存中使用的调入/ 调出技术的主要相同点是都要在内存与外存之间交换信 息。交换技术与虚存中使用的调入/ 调出技术的主要区别在于: 交换技术换进换出整个进程 (proc结构和共享正文段除外, 因此一个进程的大小受物理存储器的限制: 而虚存中使用的 调入 / 调出技术在内存和外存之间来回传递的是存储页或存储段, 而不是整个进程, 从而使得 进程的地址映射具有了更大的灵活性, 且允许进程的大小比可用的物理存储空间大得多。 2. 顺序存取法就是严格按物理记录排列的顺序依次存

41、取: 随机存取法允许随意存取文件 中的任何一个物理记录,而不管上次存取了哪一个记录。 顺序存取法对有结构文件的操作是设置一个访问指针ptr, 令它总是指向“ 下一次 “ 要访 问的记录首址。 每访问完一个记录后, 对 ptr 住进行相应的修改。对于定长记录:ptr=ptr+L(L 为文件的物理记录长度): 对于变长记录:Ptr=ptr+Li+1(其中 1是存放记录长度Li 的字节数 ) 。 顺序存取法对无结构文件的操作是按读写位移(offset)从当前位置开始读写, 即每读写完一 段信息后 , 读写位移自动力日上这段的长度, 然后再根据该位移读写下面的信息。 随机存取法对有结构文件的操作也是设

42、置一个访问指针pt, 对于定长记录文件, 欲访问 第 I 个记录。 (I=0,1,2,) 的首址为 : ptr=offset+I*L(其中 ,offest是该文件的首址,L 为记 录长度 ): 对于变长记录,随机存取法是十分低效的。随机存取法对无结构文件的操作必须事先 用有关的命令把读写位移移到欲读写的信息开始处, 然后再进行读写。 3. 死锁是指多个进程因竞争资源而造成的一种僵局, 若无外力的作用, 这些进程都将永远 不能再向前推进。所以,死锁是由于系统中多个进程所共享的资源不足以同时满足需要时, 引 起对资源的竞争而产生的。但竞争资源不定都会产生死锁, 因为只要进程推进顺序合法, 就 不会

43、产生死锁。 4. 所谓虚拟设备, 是指利用SPOOLing 系统把低速的独占设备改造成为共享的设备, 或利 用软件方法把共享的设备分割为若干台虚拟设备。 SPOOLing系统的核心思想是利用一台可共享的、高速大容量的块设备( 磁盘 )来模拟独占 设各的操作 , 使一台独占设备变成多台可并行使用的虚拟设备。SPOOLing 系统主要由输入井 和输出井、输入缓冲区和输出缓冲区、输入进程和输出进程三部分组成。它的特点是提高了 I/O 操作的速度 : 将独占设备改造为共享设备; 实现了虚拟设备功能。 ( 三)(10 分) (1) 采用 FCFS的调度算法时 , 各任务在系统中的执行情况如下表所示: 执

44、行次序运行时间优先数等待时间周转时间 A 10 3 0 10 B 6 5 10 16 C 2 2 16 18 D 4 1 18 22 E 8 4 22 30 所以 , 进程的平均周转时间为: T=(10+16+18+22+3O)/5=19.2 min (2) 采用优先级调度算法时, 各任务在系统中的执行情况如下表所示: 执行次序运行时间优先数等待时间周转时间 B 6 5 0 6 E 8 4 6 14 A 10 3 14 24 C 2 2 24 26 D 1 1 26 27 所以 , 进程的平均周转时间为: T=(6+14+24+26+27)/5=19.4 min (3)采 用 时 间 片 轮

45、转 算 法 时 , 假 定 时 间 片 为2min,各 任 务 的 执 行 情 况 是:(A,B,C,D,E),(A,B,D,E),(A,B,E),(A,E),(A)。设 A E五个进程的周转时间依次为T1 T5, 显然 , T1=3Omin, T2=22min, T3=6min,T4=16min,T5=28min 所以 , 进程的平均周转时间为: T=(30+22+6+16+28)/5=20.4min ( 四)(10 分) 1. 因为虚拟页式存储系统中允许作业的一部分页面在内存, 只有引入缺页中断, 才能将不 在内存的信息页从外存调入内存, 中断恢复后可以继续执行。 2. 缺页中断的实现由硬

46、件和软件两部分组成。其实现方法如下: 每当CPU要执行一条指令时, 首先形成操作数的有效地址, 在计算页号和页内地址, 检查 页表看该页在实存吗。 如在 , 则进行地址变换, 按变换后的地址取出操作数, 完成该指令的功能, 然后继续进行下一条指令; 如不在 , 则引起缺页中断, 进入缺页中断处理程序。 在中断处理程序中,首先利用存储器分块表(MBT)检查实存是否有空闲页面, 如无 , 则选择 某页淘汰。若该页被修改过还需写入辅存, 并修改 PMT和 MBT,此时便出现了空闲实页。如有 空闲实页 , 则根据辅助页表提供的磁盘地址调入所需的页面, 修改 PMT和 MBT 。最后再重新执 行被中断的

47、指令。 ( 五)(13 分) 1. 高级通信机制与低级通信机制P、V原语操作的主要区别是: (1) 交换信息量方面: 利用 p、v 原语操作作为进程间的同步互斥工具是理想的, 但进程间只能 交换一些信息,基本上只能是控制信息, 缺乏传输消息的能力。而高级通信不仅能较好地解决 进程间的同步互斥问题,且能很好交换大量消息, 是理想的进程通信工具。 (2) 通信对用户透明方面: 用户要用P、V原语进行进程间的通信必须在程序中增加p、V编程 , 这样做不但增加了编程的复杂性, 不便对程序有直观的理解, 同时由于编程不当, 有可能出现 死锁 , 难以查找其原因。而高级通信机制不但能高效传输大量信息, 且

48、操作系统隐藏了进程通 信的实现细节,即通信过程对用户是透明的。这样就大大地简化了通信程序编制上的复杂性。 2. 所谓消息 (Message), 是指一组信息 , 消息缓冲区是含有如下信息的缓冲区: 指向发送进程的指针:Sptr 指向下一信息缓冲区的指针:Nptr; 消息长度 : Size; 消息正文 : Text; 消息缓冲通信机制的基本工作原理是: 把消息缓冲区作为进程通讯的一个基本单位, 为了 实现进程之间的通讯, 系统提供了发送原语Send(A) 和接收原语Receive(B) 。 每当发送进程欲 发送消息时 , 发送进程用Send(A) 原语把欲发送的消息从发送区复制到消息缓冲区, 并将它挂 在接收进程的消息队列末尾。如果该接收进程因等待消息而处于阻塞状态, 则将其换醒。 而每 当接收进程欲读取消息时, 就用接收原语Receive(B) 从消息队列头取走一个消息放到自己的 接收区。 3. 消息缓冲通信机制中, 消息队列属于临界资源, 故在PCB 中设置了一个用于互斥的信号量 mute