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

精品文档 1欢迎下载 名校操作系统考研试题与解答名校操作系统考研试题与解答 10 110 1 北京大学北京大学 19971997 年考研操作系统试题年考研操作系统试题 一 名词术语解释 每小题 5 分 共 30 分 1 进程状态 2 快表 3 目录项 4 系统调用 5 设备驱动程序 6 微内核 二 填空 每小题 1 分 共 10 分 1 如果系统中有 n 个进程 则在等待队列中进程的个数最多为 个 2 在操作系统中 不可中断执行的操作称为 3 如果系统中的所有作业是同时到达的 则使作业平均周转时间最短的作业调度是 4 如果信号量的当前值为 4 则表示系统中在该信号量上有 个等待进程 5 在有 m 个进程的系统中出现死锁时 死锁进程的个数 k 应该满足的条件是 6 不让死锁发生的策略可以分为静态和动态两种 死锁避免避免属于 7 在操作系统中 一种用空间换取时间的资源转换技术是 8 为实现 CPU 与外部设备的并行工作 系统引入了 硬件机制 9 中断优先级是由硬件规定的 若要调整中断的响应次序可通过 10 若使当前运行的进程总是优先级最高的进程 应选择 进程调度算法 三 问答题 每小题 15 分 共 30 分 1 消息缓冲通信技术是一种高级通信机制 由 Hansen 首先提出 1 试述高级通信机制与低级通信机制 P V 原语操作的主要区别 2 请给出消息缓冲机制 有界缓冲 的基本原理 3 消息缓冲通信机制 有界缓冲 中提供发送原语 Send receiver a 调用参数 a 表示发 送消息的内存区首地址 试设计相应的数据结构 并用 P V 原语操作实现 Send 原语 2 在虚拟段式存储系统中 引入了段的动态链接 1 试说明为什么引入段的动态链接 2 请给出动态链接的一种实现方法 四 共 10 分 在实现文件系统时 为加快文件目录的检索速度 可利用 文件控制块分解法 假设目录文件 存放在磁盘上 每个盘块为 512 字节 文件控制块占 64 字节 其中文件名占 8 字节 通常将 文件控制块分解成两个部分 第一部分占 10 字节 包括文件名和文件内部号 第二部分占 56 字节 包括文件内部号和文件其他描述信息 1 假设某一目录文件共有 254 个文件控制块 试分别给出采用分解法前和分解法后 查找该 目录文件的某一个文件控制块的平均访问磁盘次数 2 一般地 若目录文件分解前占用 n 个盘块 分解后改用 m 个盘块存放文件名和文件内部号 部分 请给出访问磁盘次数减少的条件 五 共 10 分 设系统中有三种类型的资源 A B C 和五个进程 P1 P2 P3 P4 P5 A 资源的数量为 17 B 资源的数量为 5 C 资源的数量为 20 在 T0时刻系统状态如表 1 和表 2 所示 系统采用 银行家算法实施死锁避免策略 T0时刻是否为安全状态 若是 请给出安全序列 在 T0时刻若进程 P2请求资源 0 3 4 是否能实施资源分配 为什么 在 的基础上 若进程 P4请求资源 2 0 1 是否能实施资源分配 为什么 精品文档 2欢迎下载 在 的基础上 若进程请求资源 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 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 操作模拟上机实习过程 北京大学北京大学 19971997 年级研操作系统试题解答年级研操作系统试题解答 一 名词术语解释 每小题 5 分 共 30 分 1 进程在其存在过程中 由于各进程并发执行及相互制约 使得它们的状态不断发生变化 一 般来说进程主要有三种基本状态 这三种基本状态是 就绪状态 运行状态和阻塞状态 2 在页式存储管理系统中的地址变换过程中 由于页表是存放在内存中的 CPU 每访问一个数 据 或一条指令 至少要访问内存两次 一次是访问页表 确定所取数据 或指令 的物理地址 第二次才根据该地址访问数据 或指令 为了提高查表速度 在地址变换机构中加入了一个 高速 小容量的联想寄存器 构成一张快表 如果快表被命中 只要访问内存一次即可存取一 个数据 3 在文件系统中 文件目录记录文件的管理信息 每个文件在目录表中都有一个目录项 文件 目录项主要包含下列信息 1 有关文件的标识信息 例如文件的名称符号 2 有关文件结构的信息 例如文件长度 文件存放在外存中的物理地址等 3 有关文件的存取控制信息 例如文件属性 文件主及共享用户的标识 存取权限等 4 有关文件的管理信息 例如文件建立的时间 保留时间 最新修改时间等 4 系统调用是用户在程序中能用 访管指令 调用的由操作系统提供的子功能的集合 每一个 子功能称为一条系统调用命令 或广义指令 系统调用是操作系统在程序级给用户提供的接 口 系统调用与一般过程调用不同 其主要区别是 运行的状态不同 进入的方式不同 代码层次不同 5 设备驱动程序也称为 I O 处理程序 是一种低级的系统例程 它向上与高级 I 0 操作原语 相对应 向下与 I 0 硬设备相对应 完成两者间的相互通信 它们一般是用汇编语言编写 针 对具体的 I 0 设备控制器 进行控制编码或微程序操作 设备驱动程序早期是操作系统的一 部分 后来将其中的公共部分作为高级 I O 操作原语留在操作系统中 而把与物理设备有直接 关系的部分脱离操作系统 交给设备厂商和软硬件开发商编制 因此 设备驱动程序己成为系 统的选件 系统和用户可以根据需要选择配置设备 灵活地装载 卸载驱动程序 从而极大地 精品文档 3欢迎下载 增强了系统的开放性和可扩展性 6 操作系统有两种内核组织形式 强内核 Monolithic kernel 和微内核 Micro kernel 微内核结构是一种新的结构组织形式 它体现了操作系统结构设计的新思想 其设计目标是 使操作系统的内核尽可能小 使其它所有操作系统服务都放在核外用户级完成 微内核仅仅 提供以下四种服务 进程间通信机制 某些存储管理 有限的低级进程管理和调度 低 级 I 0 微内核的基本思想是良好的结构化 模块化 最小的公共服务 具有微内核的操作 系统称为微内核操作系统 二 填空 每小题 1 分 共 10 分 1 n 1 2 原语 3 短作业优先算法 4 四 5 k m 6 动态策略 7 缓冲区技术 8 中断和通道 9 软件实现 10 剥夺式优先级 三 问答题 每小题 15 分 共 30 分 1 见西安交大 2000 年考题中第五题的解答 2 1 在作业装入内存运行前 应将各个目标程序定位后装入作业的地址空间 形成可执行程 序的链接 称为静态链接 静态链接常常因为目标程序个数多而花费大量的 CPU 时间 而实际 运行时又常常只用到其中的部分模块 因而也造成了存储空间的浪费 动态链接是作业运行 时先装入主程序 运行过程中需要某模块时 再将该模块的目标程序调入内存并进行链接 它 克服了静态链接的不足 2 分段存储管理就是最典型的动态链接 分段管理允许用户将作业按逻辑关系进行自然分 段 各段的大小可以不同 逻辑段内的地址是由两部分组成的 s 段号 d 段内位移量 即 分段地址空间是用户定义的二维空间 内存分配以段为单位 段可以在作业运行过程中根据 请求而动态链接和装入 四 共 10 分 利用 文件控制块分解法 加快文件目录的检索速度 其原理是减少因查找文件 内部号而产生的访问磁盘次数 因为在进行查找文件内部号的过程中不需要把文件控制块的 所用内容都读入内存 所以在查找过程中减少所需读入的存储块就有可自色减少访问磁盘的 次数 但是 采用这种方法访问文件 当找到匹配的文件控制块后 还需要访问一次磁盘 才能 读出全部的文件控制块信息 这就是为何采用这种方法在一定条件下并不能减少访问磁盘的 次数的原因 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时刻是安全状态 因为可以找到一个安全的序列 P4 P5 Pl P2 P3 不能分配 因为所剩余的资源数量不够 可以分配 当分配完成后 系统剩余的资源向量为 0 3 2 这时仍可找到一个安全的序列 队 P4 P5 Pl P2 P3 不能分配 若分配完成后 系统剩余的资源向量为 0 3 匀 这时无法找到一个安全的序列 六 共 10 分 在本题中 为了保证系统的控制流程 增加了 Monitor 进程 用于控制学生的进 入和计算机分配 从题目本身来看 虽然没有明确写出这一进程 但实际上这一进程是存在的 因此 在解决这类问题时 需要对题目加以认真分析 找出其隐蔽的控制机制 上机实习过程可描述如下 精品文档 4欢迎下载 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 释放计算机资源 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 210 2 西安交通大学西安交通大学 19991999 年考研操作系统试题年考研操作系统试题 一 名词解释 30 分 每小题 5 分 1 多道程序设计 2 工作目录 3 线程与进程 4 地址空间与存储空间 5 通道 6 系统调用 二 判断 选择与填空题 每题 1 分 共 15 分 1 程序的并发执行是指同一时刻有两个以上的程序 它们的指令在同一处理器上执行 精品文档 5欢迎下载 2 对于请求分页式存储管理系统 若把页面的大小增加一倍 则缺页中断次数会减少一半 3 三个用户在同一系统上同时对他们的 C 语言源程序进行编译 此时系统应分别为各用户创 建一个 C 编译进程及保留一份 C 编译程序副本 4 可顺序存取的文件不一定能随机存取 但是 凡可随机存取的文件都可以顺序存取 5 缓冲技术是借用外存储器的一部分区域作为缓冲池 6 在操作系统中 P V 操作是一种 A 机器指令 B 系统调用命令 C 作业控制命令 D 低级进程通讯原语 7 最佳适应算法的空白区是 A 按大小递减顺序排列的 B 按大小递增顺序排列的 C 按地址由小到大排列的 D 按地址由大到小排列的 8 把作业地址空间中使用的逻辑地址变成内存中的物理地址称为 A 加载 B 重定位 C 物理化 D 逻辑化 9 文件系统用 组织文件 A 堆核 B 指针 C 目录 D 路径 10 磁盘是设备 磁带是设备 显示器是 设备 A 输入 B 输出 C 输入输出 D 虚拟 11 并发进程中涉及相同变量的程序段叫做 对这些程序段要执行 12 分区存储管理方案不能实现虚拟的原因是 13 目前认为逻辑文件有两种类型 即 式文件与 式文件 14 进程调度算法采用等时间片轮转法 时间片过大 就会使轮转法转化为 调度算法 15 采用交换技术获得的好处是以牺牲 为代价的 三 简答题 每题 10 分 共 50 分 1 试述分时系统与实时系统 并比较它们的区别 2 何谓虚拟存储器 举一例说明操作系统是如何实现虚拟内存的 3 什么是 P V 操作 试用 P V 操作描述读者一写者问题 要求允许儿个阅读者可以同时读 该数据集 而一个写者不能与其他进程 不管是写者还是读者 同时访问该数据集 4 磁盘请求的柱面按 10 22 20 2 40 6 38 的次序到达磁盘的驱动器 寻道时每个柱面移动需 要 6ms 计算按以下算法调度时的寻道时间 1 先来先服务 2 下一个最邻近的柱面 3 电梯算法 以上所有情况磁头臂均起始于柱面 20 5 对 3 种不同的保护机制 即权限 存取控制表以及 UNIX 操作系统的 RWX 位 简述下面的情况 分别适用于哪些机制 1 甲用户希望除他的同事以外 任何人都能读取他的文件 2 乙用户和丙用户希望共享某些秘密文件 3 丁用户希望公开他的一些文件 西安交通大学西安交通大学 19991999 年考研操作系统试题解答年考研操作系统试题解答 一 名词解释 每小题 5 分 共 30 分 1 多道程序设计是指在主存中同时存放多道用户作业 它们都处于执行的开始点和结束点之 间 多道程序设计的特点如下 1 多道 主存中有多道程序 它们在任一时刻必须处于就绪 运行 阻塞三种状态之一 2 宏观上并行 从宏观上看 它们在同时执行 3 微观上串行 从微观上看 它们在交替 穿插地执行 精品文档 6欢迎下载 采用多道程序设计后 减少了 CPU 时间的浪费 尤其对计算题的作业 由于 I O 操作较少 CPIJ 浪费的时间很少 2 文件系统如果采用多级树型目录 那么使用完整的路径名来查找文件会感到很不方便 因此 引入了 工作目录 考虑到通常一个进程在一段时间内所访问的文件具有局部性 即在某一 范围之内 所以可在这一段时间内指定某一目录为工作目录或值班目录 以后的操作一般都 是针对以工作目录 也称为当前目录 为根的子目录树进行的 3 所谓线程 thread 从操作系统的管理角度看 就是指 进程的一个可调度实体 是处理机 调度的基本单位 从编程逻辑看 线程是指 程序内部的一个单一的顺序控制流 线程是进程的一个组成部分 每个进程在创建时通常只有一个线程 由这个线程再创建其它进 程 通常一个进程都有若干个线程 至少会有一个线程 进程和线程是构造操作系统的两个基本元素 两者之间的主要区别是 1 调度方面 线程作为调度分派的基本单位 2 并发性方面 进程之间可以并发执行 3 拥有资源方面 进程是拥有资源的基本单位 线程除少量必不可少的资源外 基本上不拥 有资源 但它可以访问其隶属进程的资源 4 系统开销 进程间切换时要涉及到进程环境的切换 开销比较大 而线程间的切换只需保 存和设置少量的寄存器内容 因此进程问切换的系统开销远大于线程问切换的系统开销 4 程序经编译和连接以后转变为相对地址编址形式 它是以 0 为基址的 相对地址也叫逻辑 地址或虚地址 地址空间是逻辑地址的集合 计算机系统实际的内存地址是绝对地址 绝对地址又叫物理地址或实地址 存储空间是 物理地址的集合 5 通道又称 I O 处理机 它使主机摆脱了管理 I O 的工作 彻底实现了主机和外设的并行操作 具有通道结构的计算机系统 主存 通道 控制器和设备之间采用四级连接 实施三级控制 这样 I O 系统就由通道 控制器 设备三级构成 一个 CPU 可以连接多个通道 一个通道可 以连接多个控制器 一个控制器可以连接同类型的多台设各 另一方面 也允许将一台设备连 接到几个控制器上 或一个控制器连接到几个通道上 按信息交换方式和连接的设备类型不 同 可以将通道分为三种类型 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 作业的地址空间不能超过存储空间 13 有结构的记录 无结构的流 14 先来先服务 FCFS 15 CPU 时间 三 简答题 每题 10 分 共 50 分 1 所谓分时系统 就是在一台计算机上 连接多个终端 用户通过各自的终端和终端命令把作 业送入计算机 计算机又通过终端向各用户报告其作业的运行情况 这种计算机能分时轮流地 为各终端用户服务并能及时对用户服务请求予以响应 这就构成了分时系统 分时系统设计 的主要目标是使用户能与系统交互作用 对用户的请求及时响应 并在可能的条件下尽量提高 精品文档 7欢迎下载 系统资源的利用率 实时系统是为了能对特定输入做出及时响应 并在规定的时间内完成对该事件的处理而 引入的 实时系统分为两大类 z 实时控制系统和实时信息处理系统 1 实时控制系统 在这类应用中要求计算机系统实时采集测量系统的数据 对被测量的数据 及时进行加工处理及输出 它主要用于军事和生产过程中的自动控制领域 2 实时信息处理系统 在这类应用中要求计算机系统能对用户的服务请求及时作出回答 并 能及时修改 处理系统中的数据 它主要用于像飞机票的预定 银行储蓄的财务管理等大量 数据处理的实时系统中 实时系统与分时系统的主要区别如下 系统的设计目标不同 分时系统的设计目标是提供一种随时可供多个用户使用的通用性很 强的系统 而实时系统则大多数都是具有某种特殊用途的专用系统 响应时间的长短不同 分时系统的响应时间通常为秒级 而实时系统的响应时间通常为毫 秒级甚至是微秒级 交互性的强弱不同 分时系统的交互性强 而实时系统的交互性相对较弱 2 在操作系统中 通过一些硬件和软件的措施为用户提供了一个其容量比实际主存大得多的 存储器 称为虚拟存储器 操作系统要实现虚拟内存 必须把主存和辅存统一管理起来 即大作业程序在执行时 有一部 分地址空间在主存 另一部分在辅存 当访问的信息不在主存时 由操作系统将其调入主存并 实现自动覆盖功能 使用户在编写程序时不再受主存容量的限制 例如在请求分页存储管理系统中 用户作业的所有页面并不一定都在实存 在作业运行过 程中再请求调入所用的虚页 为了实现从逻辑地址空间到物理地址空间的变换 在硬件上必 须提供一套地址变换机构 动态地址变换机构自动地将所有的逻辑地址划分为页号和页内地 址两部分 并利用页表将页号代之以块号 把块号和页内地址拼接就得到了内存的物理地址 从而实现了虚拟存储器 3 读者一写者问题是经常出现的一种同步问题 计算机系统中的数据 文件 记录 常被多个 进程共享 但其中某些进程可能只要求读数据 称为 Reader 另一些进程则要求修改数据 称 为 Writer 就共享数据而言 Reader 和 Writer 是两种不同类型的进程 一般地 两个或两 个以上的 Reader 进程同时访问共享数据时不会产生副作用 但若某个 Writer 和其它进程 Reader 或 Writer 同时访问共享数据时 则可能产生错误 为了避免错误 同时尽可能地让 读者进程和写者进程并发运行 只要保证任何一个写者进程能与其它进程互斥访问共享数据 即可 这个问题称为读者一写者问题 下面使用信号量机构来描述这一问题 P V 操作是定义在信号量 s 上的两条原语 它是解决进程同步与互斥的有效手段 定义下列信号量 互斥信号量 rmutex 初值为 1 用于使读者互斥地访问读者计数器 共享 变量 rcount 互斥信号量 wmutex 初值为 1 用于实现写者之间以及写者与读者之间互斥地 访问共享数据集 则用信号量和 P V 操作描述读者一写者问题如下 Begin rmutex wmutex semaphore rcount Integer rmutex wmutex 1 rcount 0 Cobegin Process procedure Reader begin repeat 精品文档 8欢迎下载 P rmutex rcount rcount 1 if rcount l then P rmutex V rmutex perfonn read operations P rmutex rcount rcount 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 寻道时间为 146 6ms 876ms 2 下一个最邻近柱面算法调度顺序为 20 22 10 6 2 38 40 柱面移动总量为 60 寻道时间为 60 6ms 360ms 3 电梯算法调度顺序为 20 22 38 40 10 6 2 柱面移动总量为 58 寻道时间为 58 6ms 348ms 5 第 1 种情况只适合用存取控制表实现保护机制 第 2 种情况适合用权限或存取控制表实现保护机制 第 3 种情况适合用存取控制表或 RWX 位或权限实现保护机制 10 310 3 西安交通大学西安交通大学 20002000 年考研操作系统试题年考研操作系统试题 一 名词解释 15 分 1 线程 2 分时系统 3 系统调用 4 地址再定位 5 多道程序设计 精品文档 9欢迎下载 二 简答题 32 分 1 覆盖技术与虚拟存储技术有何本质不同 交换技术与虚存中使用的调入 调出技术有何相同 与不同之处 2 文件顺序存取与随机存取的主要区别是什么 它们对有结构文件与无结构文件的操作有何 不同 3 死锁和竞争有何关系 4 何请虚拟设备 请说明 SPOOLing 系统是如何实现虚拟设备的 三 10 分 有 5 个任务 A B C D E 它们几乎同时到达 预计它们的运行时间为 10 6 2 4 8mn 其优先级分别为 3 5 2 1 和 4 这里 5 为最高优先级 对于下列每一种调度 算法 计算其平均进程周转时间 进程切换开销可不考虑 1 先来先服务 按 A B c D E 算法 2 优先级调度算法 3 时间片轮转算法 四 10 分 在虚拟页式存储系统中引入了缺页中断 1 试说明为什么引入缺页中断 2 缺页中断的实现由哪几部分组成 并分别给出其实现方法 五 13 分 消息缓冲通信技术是一种高级通信机制 由 HANSEN 首先提出 1 试叙述高级通信机制与低级通信机制 P V 原语操作的区别 2 请给出消息缓冲通信机制 有界缓冲 的基本工作原理 3 试设计相应的数据结构 并用 P V 原语操作实现 Send 和 Receive 原语 西安交通大学西安交通大学 20002000 年考研操作系统试题解答年考研操作系统试题解答 一 名词解释 15 分 1 所谓线程 thread 从操作系统管理角度看线程是指 进程的一个可调度实体 是处理机调 度的基本单位 从编程逻辑看线程是指 程序内部的一个单一的顺序控制流 线程是进程的 一个组成部分 2 所谓分时系统 就是指在一台计算机上 连接多个终端 用户通过各自的终端和终端命令把 作业送入计算机 计算机又通过终端向各用户报告其作业的运行情况 这种计算机能分时轮 流地为各终端用户服务并能及时对用户服务请求予以响应 这就构成了分时系统 分时系统 设计的主要目标是使用户能与系统交互作用 对用户的请求及时响应 并在可能的条件下尽量 提高系统资源的利用率 分时系统的主要特征是 同时性 若干个终端用户按照系统提供的各种服务 在各自终端进行操作 同时使用一台计 算机资源 宏观上看是各用户在并行工作 微观上看是各用户轮流使用计算机 独立性 用户间可以相互独立地操作 互不干涉 系统保证各用户程序运行的完整性 不会发 生相互混淆或破坏现象 及时性 系统可对用户的输入及时作出响应 分时系统性能的主要指标之一是响应时间 它 是指从终端发出命令到系统予以应答所需的时间 交互性 用户可根据系统对请求的响应结果 进一步向系统提出新的请求 即能使用户和系 统进行人一机对话的工作方式 所以分时系统也被称之为交互式系统 3 系统调用是指用户在程序中能用 访管指令 调用的由操作系统提供的子功能的集合 每一 个子功能称为一条系统调用命令 或广义指令 系统调用是操作系统在程序级给用户提供的 接口 4 所谓地址再定位 就是当一个程序装入到与其地址空间不一致的存储空间而进行的地址变 换过程 即将地址空间给出的逻辑地址映射到内存的物理地址 地址重定位有静态重定位和 精品文档 10欢迎下载 动态重定位两种方式 5 多道程序设计是指在主存中同时存放多道用户作业 它们都处于执行的开始点和结束点之 间 多道程序设计的特点如下 1 多道 主存中有多道程序 它们在任一时刻必须处于就绪 运行 阻塞三种状态之一 2 宏观上并行 从宏观上看 它们在同时执行 3 微观上串行 从微观上看 它们在交替 穿插地执行 采用多道程序设计后 减少了 CPU 时间的浪费 尤其对计算题的作业 由于 I O 操作较少 CPU 浪费的时间很少 二 简答题 32 分 1 覆盖技术与虚拟存储技术最本质的不同在于覆盖的程序段的最大长度要受到物理内存 容量的限制 而虚拟存储器的最大长度不受物理内存容量的限制 只受计算机地址结构的限制 另外 使用覆盖技术要求程序员必须精心地设计程序及其数据结构 使得要覆盖的段具有相对 独立性 不存在直接联系或相互交叉访问 而虚拟存储技术对用户的程序段之间没有此要求 交换技术与虚存中使用的调入 调出技术的主要相同点是都要在内存与外存之间交换信 息 交换技术与虚存中使用的调入 调出技术的主要区别在于 交换技术换进换出整个进程 proc 结构和共享正文段除外 因此一个进程的大小受物理存储器的限制 而虚存中使用的 调入 调出技术在内存和外存之间来回传递的是存储页或存储段 而不是整个进程 从而使得 进程的地址映射具有了更大的灵活性 且允许进程的大小比可用的物理存储空间大得多 2 顺序存取法就是严格按物理记录排列的顺序依次存取 随机存取法允许随意存取文件 中的任何一个物理记录 而不管上次存取了哪一个记录 顺序存取法对有结构文件的操作是设置一个访问指针 ptr 令它总是指向 下一次 要访 问的记录首址 每访问完一个记录后 对 ptr 住进行相应的修改 对于定长记录 ptr ptr L L 为文件的物理记录长度 对于变长记录 Ptr ptr Li 1 其中 1 是存放记录长度 Li 的字节数 顺序存取法对无结构文件的操作是按读写位移 offset 从当前位置开始读写 即 每读写完一段信息后 读写位移自动力日上这段的长度 然后再根据该位移读写下面的信息 随机存取法对有结构文件的操作也是设置一个访问指针 pt 对于定长记录文件 欲访问 第 I 个记录 I 0 1 2 的首址为 ptr offset I L 其中 offest 是该文件的首址 L 为 记录长度 对于变长记录 随机存取法是十分低效的 随机存取法对无结构文件的操作必须 事先用有关的命令把读写位移移到欲读写的信息开始处 然后再进行读写 3 死锁是指多个进程因竞争资源而造成的一种僵局 若无外力的作用 这些进程都将永远 不能再向前推进 所以 死锁是由于系统中多个进程所共享的资源不足以同时满足需要时 引 起对资源的竞争而产生的 但竞争资源不 定都会产生死锁 因为只要进程推进顺序合法 就 不会产生死锁 4 所谓虚拟设备 是指利用 SPOOLing 系统把低速的独占设备改造成为共享的设备 或利 用软件方法把共享的设备分割为若干台虚拟设备 SPOOLing 系统的核心思想是利用一台可共享的 高速大容量的块设备 磁盘 来模拟独 占设各的操作 使一台独占设备变成多台可并行使用的虚拟设备 SPOOLing 系统主要由输入 井和输出井 输入缓冲区和输出缓冲区 输入进程和输出进程三部分组成 它的特点是提高 了 I O 操作的速度 将独占设备改造为共享设备 实现了虚拟设备功能 三 10 分 1 采用 FCFS 的调度算法时 各任务在系统中的执行情况如下表所示 执行次序运行时间优先数等待时间周转时间 精品文档 11欢迎下载 A103010 B651016 C221618 D411822 E842230 所以 进程的平均周转时间为 T 10 16 18 22 3O 5 19 2 min 2 采用优先级调度算法时 各任务在系统中的执行情况如下表所示 执行次序运行时间优先数等待时间周转时间 B6506 E84614 A1031424 C222426 D112627 所以 进程的平均周转时间为 T 6 14 24 26 27 5 19 4 min 3 采用时间片轮转算法时 假定时间片为 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 缺页中断的实现由硬件和软件两部分组成 其实现方法如下 每当 CPU 要执行一条指令时 首先形成操作数的有效地址 在计算页号和页内地址 检查 页表看该页在实存吗 如在 则进行地址变换 按变换后的地址取出操作数 完成该指令的功 能 然后继续进行下一条指令 如不在 则引起缺页中断 进入缺页中断处理程序 在中断处理程序中 首先利用存储器分块表 MBT 检查实存是否有空闲页面 如无 则选择 某页淘汰 若该页被修改过还需写入辅存 并修改 PMT 和 MBT 此时便出现了空闲实页 如有 空闲实页 则根据辅助页表提供的磁盘地址调入所需的页面 修改 PMT 和 MBT 最后再重新执 行被中断的指令 五 13 分 1 高级通信机制与低级通信机制 P V 原语操作的主要区别是 1 交换信息量方面 利用 p v 原语操作作为进程间的同步互斥工具是理想的 但进程间只能 交换一些信息 基本上只能是控制信息 缺乏传输消息的能力 而高级通信不仅能较好地解决 进程间的同步互斥问题 且能很好交换大量消息 是理想的进程通信工具 2 通信对用户透明方面 用户要用 P V 原语进行进程间的通信必须在程序中增加 p V 编程 这 样做不但增加了编程的复杂性 不便对程序有直观的理解 同时由于编程不当 有可能出现死 锁 难以查找其原因 而高级通信机制不但能高效传输大量信息 且操作系统隐藏了进程通信 的实现细节 即通信过程对用户是透明的 这样就大大地简化了通信程序编制上的复杂性 2 所谓消息 Message 是指一组信息 消息缓冲区是含有如下信息的缓冲区 指向发送进程的指针 Sptr 指向下一信息缓冲区的指针 Nptr 精品文档 12欢迎下载 消息长度 Size 消息正文 Text 消息缓冲通信机制的基本工作原理是 把消息缓冲区作为进程通讯的一个基本单位 为了 实现进程之间的通讯 系统提供了发送原语 Send A 和接收原语 Receive B 每当发送进程 欲发送消息时 发送进程用 Send A 原语把欲发送的消息从发送区复制到消息缓冲区 并将它 挂在接收进程的消息队列末尾 如果该接收进程因等待消息而处于阻塞状态 则将其换醒 而每当接收进程欲读取消息时 就用接收原语 Receive B 从消息队列头取走一个消息放到自 己的接收区 3 消息缓冲通信机制中 消息队列属于临界资源 故在 PCB 中设置了一个用于互斥的信号量 mutex 而每当有进程要进入消息队列时 应对信号量 mutex 施行 P 操作 退出消息队列后 应 对信号量 mutex 施行 V 操作 由于接受进程可能会收到几个进程发来的消息 故应将所有的 消息缓冲区链成一个队列 其队头由接收进程 PCB 中的队列头指针 Hptr 指出 为了表示队列中的消息的数目 在 PCB 中设置了信号量旬 每当发送进程发来一个消息 并将 它挂在接收进程的消息队列上时 便在 Sn 上执行 V 操作 而每当接收进程从消息队列上读取 一个消息时 先对 Sn 执行 P 操作 再从队列上移出要读取的消息 用 P V 原语操作实现 Send 原语和 Receive 原语的处理流程如下 Procedure Send receiver Ma 发送原语 begin getbuf Ma size i 申请消息缓冲区 i sender Ma Sender 将发送区的信息发送到消息缓冲区 i size Ma Size i text Ms text i next 0 getid PCB set receive j 获得接收进程的内部标识符 P j mutex insert j Hptr i 消息缓冲区插入到消息队列首 V j Sn V j mutex end Procedure Receive Mb 接收原语 begin j internal name 接收进程内部标识符 P j Sn P j mutex remove j Hptr i 从消息队列中移出第一个消息 V j mutex Mb Sender i Sender 将消息缓冲区中的信息复制到接收区 Mb Size i Size Mb text i text End 10 410 4 西安电子科技大学西安电子科技大学 20002000 年考研操作系统试题年考研操作系统试题 一 单项选择题 10 分 1 分页式虚拟存储管理系统中 一般来说页面的大小与可能产生缺页中断的次数 A 成正比 B 成反比 C 无关 D 成固定比值 精品文档 13欢迎下载 2 实时操作系统必须在 内完成来自外部的事件 A 响应时间 B 周转时间 C 规定时间 D 调度时间 3 早期 UNIX 操作系统的存储管理采用 方案 A 段式管理 B 请求分页 C 可变式分区管理 D 固定式分区管理 4 在下列语言中属于脱机作业控制语言的是 A 作业控制语言 B 汇编语言 C 会话式程序设计语言 D 解释 BASIC 语言 5 MS DOS 中的文件物理结构采用 A 连续结构 B 链接结构 C 索引结构 D 哈希表 6 在请求分页存储管理方案中 如果所需的页面不在内存中 则产生缺页中断 它属于 中断 A 硬件故障 B I O C 外 D 程序中断 7 设有四个作业同时到达 每个作业的执行时间均为 2 小时 它们在一台处理机上按单道方式 运行 则平均周转时间为 A 1 小时 B 5 小时 C 2 5 小时 D 8 小时 8 在关于 SPOOLING 的叙述中 描述是不正确的 A SPOOLING 系统中不需要独占设备 B SPOOLING 系统加快了作业执行的速度 C SPOOLING 系统使独占设备变成共享设备 D SPOOLBNG 系统利用了处理器与通道并行工作的能力 9 页式虚拟存储管理的主要特点是 A 不要求将作业装入到主存的连续区域 B 不要求将作业同时全部装入到主存的连续区域 C 不要求进行缺页中断处理 D 不要求进行页面置换 10 下列文件中属于逻辑结构的文件是 A 连续文件 B 系统文件 C 散列文件 D 流式文件 二 改错题 对错误的命题 请说明原因 10 分 1 采用多道程序设计的系统中 系统的程序道数越多 系统的效率就越高 2 特权指令只能在管态下执行 而不能在算态下执行 3 采用资源的静态分配算法可以预防死锁的发生 4 一个虚拟的存储器 其地址空间的大小等于辅存的容量加上主存的容量 5 一个作业由若干个作业步组成 在多道程序设计的系统中这些作业步可以并发执行 6 作业调度是处理机的高级调度 进程调度是处理机的低级调度 7 I O 交通管理程序的主要功能是管理主存 控制器和通道 8 移臂调度的目标是使磁盘旋转周数最小 9 进程是一个独立的运行单位 也是系统进行资源分配和调度的基本单位 10 作业的联机控制方式适用于终端作业 三 填空题 9 分 1 UNIX 操作系统在结构上分为两个部分 和 2 把作业装入内存中随即进行地址变换的方式称为 而在作业执行期间 当访问到指 令或数据时才进行地址变换的方式称为 3 死锁产生的四个必要条件是 互斥控制 精品文档 14欢迎下载 4 多道程序设计的引入给存储管理提出了新的课题 应考虑的三个问题是 5 在存储管理方案中 可用上下限地址寄存器存储保护的是 6 在 UNIX 文件管理系统中 为了对磁盘空间的空闲块进行有效的管理 采用的方法 7 为了记录设备的分配情况 操作系统应设置一张 和三个控制块 设备控制块 8 I O 设备处理进程平时处于 状态 当 和 出现时被唤醒 四 综合题 21 分 1 什么叫 可再入 程序 它有什么特征 2 简述 UNIX 的进程调度的公式和算法 3 给出 UNDE 进程的调度状态 当子进程终止时 处于什么状态 4 假设有 4 个记录 A B C D 存放在磁盘的某个磁道上 该磁道划分为 4 块 每块存放一个 记录 安排如下表所示 块号 1 2 3 4 记录号 A B C D 现在要顺序处理这些记录 如果磁盘旋转速度为 2Oms 转一周 处理程序每读出一个记录 后花 5ms 的时间进行处理 试问处理完这 4 个记录的总时间是多少 为了缩短处理时间应进 行优化分布 试问应如何安排这些记录 并计算处理的总时间 5 有一个理发师 一把理发椅和 n 把供等候理发的顾客坐的椅子 如果没有顾客 则理发师便 在理发椅子上睡觉 当一个顾客到来时 必须唤醒理发师 进行理发 如果理发师正在理发时 又有顾客来到 则如果有空椅子可坐 他就坐下来等 如果没有空椅子 他就离开 为理发师和 顾客各编一段程序描述他们的行为 要求不能带有竞争条件 西安电子科技大学西安电子科技大学 20002000 考研操作系统试题答案考研操作系统试题答案 一 单项选择题 10 分 1 B 2 C 3 C 4 A 5 B 6 D 7 B 8 C 9 B 10 D 二 改错题 对错误的命题 请说明原因 10 分 1 错 系统的程序道数越多 并不能说明效率就越高 2 对 3 对 4 错 虚存大小与地址总线的位数有关 5 错 作业之间并发执行 6 对 7 错 I 0 交通管理程序管理设备 控制器 通道的全部状态信息等 但它不管理主存 8 错 移臂调度以减少移臂时间为目的 9 对 10 对 三 填空题 9 分 1 外壳 内核 2 静态地址再定位 动态地址再定位 3 非剥夺控制 零散请求 环路条件 4 存储器分配 虚存管理 存储保护 5 分区分配 精品文档 15欢迎下载 6 成组连接法 7 系统设备表控 制器控制块 通道控制块 8 睡眠 IIO 中断 I O 请求 四 综合题 21 分 1 可再入程序是能够被多个进程共享的程序段 代码不因程序的执行而改变 又称为可再入码 纯代码的主要作用就是可被多个程序共享 其特点如下 1 可再入程序必须是纯代码的 在执行中不变化 2 一个可再入程序要求调用者提供工作区 以保证程序以同样的方式为用户服务 3 编译程序和操作系统程序通常是可再入程序 能同时被不同用户调用而形成不同进程 2 UNIX 采用动态优先数调度算法 优先数的计算公式为 p pri min 127 p cpu 16 PUSER p ice UNIX 第 6 版 p pri p cpu 2 PUSER NZERO UNIX System 优先数越大 优先级越低 3 在 UNIX 系统中 进程状态有 运行状态 就绪状态 睡眠状态 创建状态 僵尸状态 当 进程终止时处于僵尸状态 4 优化前处理总时间 5 5 5 3 5 5 5 3 5 5 5 3 5 5 85ms 优化后记录顺序为 A C B D 优化后处理总时间 20 4 5 4 5 45ms 5 define CHAIRS 6 为等候的顾客准备的椅子数 semphore customers 0 semphore barbers O semaphore S 1 用于互斥 int waiting 0 void barber while T P customers P S waiting waiting 1 V bMbers V S 理发 void customerO P S if wait CHAIRS waiting waiting I V customers V S P barbers 精品文档 16欢迎下载 坐下等待 else V S 2 4 32 4 3 睡睡 着着 的的 理发理发 师师 问问 题题 The The SleepingSleeping BarberBarber Problem Problem 睡睡 着着 的的 理理 发发 师师 问问 题题 又又 是是 一一 个个 有有 趣趣 的的 进进 程程 同同 步步 问问 题 题 在在 理理 发发 馆馆 中 中 有有 一一 个个 理理 发发 师师 一一 张张 理理 发发 椅椅 和和 n n 个个 为为 等等 待待 顾顾 客客 所所 设设 的的 椅椅 子 子 如如 果果 没没 有有 顾顾 客客 来 来 理理 发发 师师 就就 会会 坐坐 在在 理理 发发 椅椅 上上 睡睡 觉 觉 当当 一一 个个 顾顾 客客 来来 到到 时 时 他他 必必 须须 唤唤 醒醒 睡睡 着着 了了 的的 理理 发发 师师 如如 果果 在在 理理 发发 师师 理理 发发 时 时 又又 有有 别别 的的 顾顾 客客 到到 达 达 他他 们们 要要 么么 坐坐 下下 如如 果果 有有 空空 的的 椅椅 子子 要要 么么 离离 开开 如如 果果 所所 有有 的的 椅椅 子子 都都 被被 坐坐 满满 解解 决决 方方 法法 是是 使使 用用 三三 个个 信信 号号 量量 1 customerscustomers 用用 于于 记记 录录 等等 候候 的的 顾顾 客客 的的 数数 量 量 2 barbersbarbers 用用 于于 记记 录录 空空 闲闲 理理 发发 师师 的的 数数 量 量 3 mutex mutex 用用 于于 进进 程程 之之 间间 的的 互互 斥 斥 另另 外外 还还 需需 使使 用用 一一 个个 变变 量量 w