南京大学计算机科学与技术系 操作系统期末试卷（ 2003 年 12 月 28）一、简答题1、列出 I/O 控制方式。2、列出文件的共享方式。3、列出几种实时调度算法。4、列举系统发生死锁的必要条件。5、虚拟存储器的容量与什么有关 ?6、列出可变分区搜索分配算法。7、列出影响缺页中断率的主要因素。8、 列出管程的主要特性。二、问答题1、假设有一个操作系统采用层次结构组成，它运行在裸机上，并有以下层次组 成：作业管理、设备管理、内存管理、命令管理、文件管理、进程调度及内核支 撑功能，试给出一种由底向上的正确层次。2、试从资源管理的观点，叙 .述操作系统的功能和任务。3、叙述操作系统中引入 ”进程”和”线程 ”的主要目的。4、叙述进程通信及其分类。5、叙述 SPOOLING 系统的技术特点、组成和数据结构。6、叙述内存映射文件的基本原理和优点。7、解释微内核与单内核操作系统，说明微内核结构设计的主要优点。8、来自处理器和主存内部的中断称“异常” ，列举它的分类及主要区别 ?三、计算题1、如果一个操作系统采用 LFU 页面置换算法的一个变种： 每个页框对应一个计数器，用来 计数曾经装入过一个页框的页面个数， 当有多个候选淘汰页面所在的页框计数器具有相同的 最小值时，按 FIFO 进行。现在有一个进程分到了 4 个页框，则对如下页面走向求出缺页中 断次数及淘汰的页号。 1 , 2 , 3 ,4 , 5 ,3 , 4, 1, 6,7, 8, 7, 8, 9, 7, 8, 9, 5, 4, 5, 7, 22、假定在某移动臂磁盘上，刚刚处理了访问 38 号柱面的请求，目前正在 40号 柱面读信息， 并且有下述请求序列等待访问磁盘。 试分别使用电梯调度算法和最 短寻找时间优先算法列出实际处理上述请求的次序。请求次序12345678欲访问的柱面号77209594452916583、某多道程序设计系统供用户使用的主存为100K，磁带机 2 台，打印机 1 台。采用可变分区内存管理，采用静态方式分配外围设备，忽略用户作业 I/O 时间。现有作业序 列如下：作业号进入输入井时间运行时间主存需求量磁带需求打印机需求18:0025 分钟15K1128:2010 分钟30K0138:2020 分钟60K1048:3020 分钟20K1058:3515 分钟10K11作业调度采用 FCFS 策略，优先分配主存低地址区且不准移动已在主存的作业，在主 存中的各作业平分 CPU 时间。现求： (1)作业被调度的先后次序 ?(2) 全部作业运行结 束的时间 ?(3) 作业平均周转时间 ?(4) 最大作业周转时间 ?四、信号量、 P-V 题1、桌上有一只盘子，最多可以容纳两个水果，每次仅能放入或取出一个水果。爸爸向 盘子中放苹果 (apple) ，妈妈向盘子中放桔子 (orange)，两个儿子专等吃盘子中的桔子，两个 女儿专等吃盘子中的苹果。试用：信号量和P、 V 操作编写实现爸爸、妈妈、儿子、女儿间正确工作的程序。2、在一个盒子里有数量相等的黑、白两种棋子，现有两个进程 P1 和 P2，其 中 P1专拣白子， P2 专拣黑子；规定每个进程每次只拣一个子；一个进程拣子时， 另一个进程不能去拣； P1和 P2必须交替拣子；按黑先白后次序拣子。请用 Monitor 写出实现该自动分拣系统和进程 P1、 P2 的调用程序。南京大学计算机科学与技术系操作系统期末试卷( 2004年 12月 28)一、解释题1. 解释操作系统为用户提供了虚拟机。2. 解释并发与并行，并说明两者关系。3. 解释多道程序与多重处理，并说明两者关系。4. 解释模式切换与进程切换，并说明两者关系。5. 解释死锁与“饥饿” 。6. 解释管程及其组成 。7. 解释中断及异常。8. 解释硬中断和软中断。二、问答题1. 叙述 LRU 、NRU 和 LFU 三种页面置换算法的思想， 并各给出一种可能的 实现方案。2. 叙述操作系统的安全策略、安全模型和安全机制。3. 在一个分布式系统中，如何对系统中的事件进行一致性排序 ?4. 试解释多级页表与反置页表。5. 简述操作系统虚拟性在设备管理中的应用。6. 用垫脚石过河， 每块垫脚石仅允许一个人使用， 当两人在河中相遇且都互 不退让时，则出现了死锁。试写出产生死锁的 4 个必要条件，并就“过河问 题”给出破坏死锁的 4 个必要条件的方法。三、计算题1. 使用位示图： 0 行开始共 20 行、0 列开始共 30列来表示空闲盘块状态， 设首盘块号为 1。假如当分配一个盘块号为 140 时，其在位示图中的行、 列数应为多少 ?当释放一个盘块号为 301 时，其所在位示图中的行、列 数为多少?2. 在一个操作系统中， 如果一个盘块的大小为 1KB ，每个盘块号占 4 个字 节，采用直接地址 （为 10 块）、一次间接、二次间接及三次间接的成组链 接法保存文件。那么，一个进程要访问偏移量为 287744B 处的数据时， 需要经过几次间接 ?3. 在一个请求分页存储管理系统中，某程序的页面走向为： 7，0，1，2，0， 3，0，4，2，3，0，3，2，1，2，0，1，7，0，1。假设分得的页框数是 3，并且开始时页框中是空的，则分别采用最佳替换算法和LRU 页面替换算法，在访问过程中发生缺页中断率各为多少 ?4. 磁盘调度采用 SCAN 调度算法，设任务队列欲访问的柱面号为 66、 65、 124、14、122、37、183、98。试计算服务结束时，磁头总共移动了多少 个柱面。假设磁盘共有 200 个柱面 （编号 0-199），开始服务时，磁头刚 从 60 移到 66 柱面。四、综合题1有 5个作业依次进入系统， 到达时间、运行时间、所需内存容量列于下表。 设内存容量为 100KB ，采用可变分区存储管理，且作业在主存不能移动。作业 调度采用先来先服务算法， 作业对应的进程调度采用内存中的就绪进程平分 CPU 时间，不计作业对换及其他系统开销。试求各作业 （进程 ）开始执行时间、完成时 间、周转时间填入表中。 （可直接填入下表。 ）作业提交时间需运行时间作业长度开始执行时间完成时间周转时间J110:002515J210:203060J310:202540J410:301520J510:3510302 请用信号量编程解决以下的“过独木桥”问题：同一方向的行人可连续过 桥，当某一方向有人过桥时， 另一方向的行人必须等待； 当某一方向无人过桥时， 另 一方向的行人可以过桥。3 假设有如右图所示的工作模型，有三个并发进程 P1、 P2 和 P3，两个单缓冲 B1 和 B2。进程 P1负责不断从输入设备读数据， 若读入的数据为正数，则直接送入 B2，否则应先将数据送入 B1， 经 P2 取出加工后再送入 B2，P3 从 B2 中取信息输出。请用信号 量操作描述进程 P1、P2、P3 实现同步的算法。 许昌学院 2008-2009 学年第一学期期末考试试题一、选择题 1、在现代操作系统中引入了（），从而使并发和共享成为可能A. 单道程序 B. 磁盘 C. 对象 D. 多道程序2、（ ） 操作系统允许在一台主机上同时连接多台终端， 多个用户可以通过各自的终端同时交互地使用计算机A. 网络 B. 分布式 C.分时D. 实时3、从用户的观点看，操作系统是（）。A. 用户与计算机硬件之间的接口B.控制和管理计算机资源的软件C. 合理组织计算机工作流程的软件D.计算机资源的的管理者4、当 CPU 处于管态时，它可以执行的指令是（）。A. 计算机系统中的全部指令 访管指令 D. 仅限于特权指令5、用户在程序中试图读取某文件的第 （ ）接口。A. 系统调用B.图形用户接口B. 仅限于非特权指令 C. 仅限于100 个逻辑块时，使用操作系统提供的C. 原语D.键盘命令6、下列几种关于进程的叙述， （）最不符合操作系统对进程的理解？A. 进程是在多程序并行环境中的完整的程序。B. 进程可以由程序、数 据和进程控制块描述。C.线程是一种特殊的进程。D. 进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。7、当一个进程处于（）状态时，称其为等待（或阻塞）状态。A. 它正等待中央处理机 B. 它正等待合作进程的一个消息 C. 它正 等待分给它一个时间片D. 它正等待进入内存8、一个进程释放一种资源将有可能导致一个或几个进程（）。A. 由就绪变运行 B. 由运行变就绪 C. 由阻塞变运行 D. 由阻塞变就 绪9、下面关于线程的叙述中，正确的是（）。A. 不论是系统支持线程还是用户级线程，其切换都需要内核的支持。 B. 线 程是资源的分配单位，进程是调度和分配的单位。C. 不管系统中是否有线程， 进程都是拥有资源的独立单位。 D. 在引入线程 的系统中，进程仍是资源分配和调度分派的基本单位。10、设有 3个作业，它们同时到达，运行时间分别为 T1、T2和 T3,且 T1T2 T3，若它们在单处理机系统中按单道运行， 采用短作业优先调度算法， 则平均周 转时间为（ ）。A. T1+T2+T3D. T3/3+2*T2/3+T1B. (T1+T2+T3)/3C. T1+T2/3+2*T3/311、在下面的 I/O 控制方式中，需要 CPU 干预最少的方式是（）A程序 I/O 方式 B中断驱动 I/O 控制方式 C直接存储器访问 DMA 控 制方式 D I/O 通道控制方式12、有 m个进程共享同一临界资源， 若使用信号量机制实现对一临界资源的互斥 访问，则信号量的变化范围是（ ）。A. 1 至 （m-1） B.1至 m-1 C.1 至 m D.1 至 m13、对资源编号， 要求进程按照序号顺序申请资源， 是破坏了死锁必要条件中的 哪一条？（ ）A. 互斥 B. 请求与保持 C. 不可剥夺 D. 循环等待14、某系统采用了银行家算法，则下列叙述正确的是（）B.系统处于不安全状态D.系统处于安全状态时A. 系统处于不安全状态时一定会发生死锁 时可能会发生死锁C.系统处于安全状态时可能会发生死锁定会发生死锁15、CPU 输出数据的速度远远高于打印机的打印速度，为解决这一矛盾，可采用（ ）A 并行技术B缓冲技术C虚拟存储器技术D覆盖技术16、下面最有可能使得高地址空间成为大的空闲区的分配算法是（）。A.首次适应法B.最佳适应法C.最坏适应法D. 循环首次适应法17、在下面关于虚拟存储器的叙述中，正确的是（）。A.要求程序运行前必须全部装入内存且在运行过程中一直驻留在内存B. 要求程序运行前不必全部装入内存且在运行过程中不必一直驻留在内存C. 要求程序运行前不必全部装入内存但是在运行过程中必须一直驻留在内 存D. 要求程序运行前必须全部装入内存但在运行过程中不必一直驻留在内存18、采用段式存储管理的系统中，若地址用 24位