操作系统习题参考答案第二版.pdf

第第 1 章章 操作系统概述操作系统概述 习题参考答案习题参考答案 1. 选择题 (1) C (2) C (3) C CP/M 和 MS-DOS 都是单用户单任务操作系统。Windows NT 是单用户多任 务操作系统。UNIX 和 Linux 是多用户多任务操作系统 (4) B (5) C (6) B (7) C (8) B (9) A 批处理系统没有交互能力，所以 A 对。 2. 填空题 (1) 存储管理 设备管理 (2) 软硬件资源 (3) 批处理操作系统 分时操作系统 实时操作系统 (4) 20ms 3. 问答题 (1) 简述操作系统的概念 答： 操作系统是一组能控制和管理计算机系统的硬件和软件资源， 合理地组织计算机工 作流程并为用户使用计算机提供方便的程序和数据的集合。 (2) 什么是批处理系统？为什么要引入批处理系统？ 答：批处理系统指用户的作业成批的处理，作业建立、过渡、完成都自动由系统成批完 成。因为 19581964 年，晶体管时代，计算机速度、容量、外设品种和数量等方面和第一代 计算机相比都有了很大发展，计算机速度有几十倍、上百倍的提高，故使手工操作的慢速度 和计算机运算的高速度之间形成一对矛盾。只有设法去掉人工干预，实现作业自动过渡，这 样就出现了成批处理。 (3) 什么叫多道程序？试述多道程序涉及技术的基本思想及特征，为什么对作业进行多 道批处理可以提高系统效率？ 答： 多道程序设计技术是在计算机内存中同时存放几道相互独立的程序， 使它们在管理 程序控制下，相互穿插交替运行。当某道程序因某种原因不能继续运行下去时，管理程序就 将另一道程序投入运行， 这样使几道程序在系统内并行工作， 可使中央处理机及外设尽量处 于忙碌状态， 从而大大提高计算机使用效率。 在批处理系统中采用多道程序设计技术形成多 道批处理系统，多个作业成批送入计算机，由作业调度程序自动选择作业运行，这样提高了 系统效率。 (4) 何为分时系统？简述其特点。 答：分时系统采用时间片轮转法，使一台计算机同时为多个终端服务。特点： 多路性。若干个终端连接到计算机上，系统按分时原则为每个用户服务。宏观上多用户 同时工作，共享系统资源。微观上，每个用户作业轮流在 CPU 上运行。 独立性。各用户独立地使用一台终端工作，彼此互不干扰。用户感觉自己在独占使用计 算机。 及时性。 用户的请求能在较短时间内得到响应。 分时系统的响应时间指用户发出终端命 令到系统响应，做出应答所需要的时间。此时间需要在用户能接受的范围之内，通常为 2 至 3 秒。 交互性。在分时系统中，用户能与计算机进行对话，以交互的方式进行工作。用户可联 机对文件进行编辑，对源程序进行编译、链接，对程序进行调试，运行程序等活动。 (5) 分时系统和实时系统有何不同？ 答：分时系统控制的主动权在计算机，计算机按一定时间间隔，以固定时间片或不固定 时间片去轮流完成多个提交的任务，只是在用户反应相对较慢时，不感到机器“走开” 。而 实时系统控制的主动权在用户，用户规定什么时间要计算机干什么，计算机不能“走开” 。 分时系统通用性强，交互性强，及时响应性要求一般（通常数量级为秒） ；实时系统往 往是专用的，系统与应用很难分离，常常紧密结合在一起，实时系统并不强调资源利用率， 而更关心及时响应性（通常数量级为毫秒或微秒） 、可靠性等。 (6) 实现多道程序解决哪些问题？ 答：首先包括分时使用硬件的硬件设计技术： CPU 和通道分时使用内存、只读存储器 和数据通道等；通道与通道分时使用 CPU、内存、通道的公用控制部分等；同一通道中的 I/O 又分时使用内存、通道等。其次包括共享硬件和软件资源的软件设计技术：包括引入“进 程”“线程”等技术。 第第 2 章章 操作系统用户界面操作系统用户界面习题参考习题参考答案答案 1. 选择题 (1) D (2)A (3)A (4)B (5)A (6) D (7) D (8) B 2. 填空题 (1) 命令控制接口 程序接口（系统调用） (2) 目（用户） 管（核心） (3) 用户程序 (4) 编程 bash (5) drw-r-r- 3. 问答题 (1) 什么是核心态与用户态？为什么需要区别出这两种状态？系统是如何区分的？ 核心态是计算机的特权态，当执行操作系统程序时，处理机处于核心态。在核心态下 CPU可以执行所有的指令，包括一般用户程序中不能使用的特权指令，从而能对所有寄存器 和内存进行访问、启动I/O操作等。用户态是非特权态，用户程序是在用户态下执行，它的 的权限最低，只能执行指令集中非特权指令。 设置这两种不同状态的目的是保护计算机资源的合理分配与使用， 防止用户程序干扰操 作系统执行，提高计算机的可靠性。 通常在PSW中有一个控制位控制这两种状态。 (2) 什么是系统调用？系统调用是通过什么指令实现的？ 系统调用是操作系统提供给用户程序调用的一组“特殊”接口。用户程序可以通过这组 “特殊”接口来获得操作系统内核提供的服务，是进入系统内核空间的一种方法。在用户程序 中通过执行一条访管指令使得系统进入核心态，调用相应的系统调用功能。 (3) (4) 系统调用与过程调用在功能及实现上有什么相同点和不同点？ 答：相同点：两者都由程序代码构成，可直接用高级程序设计语言（如C,C+和Perl语 言）来编制；使用方式相同以函数调用的形式出现，调用时传送参数。 不同点：代码层次不同，过程调用不属于操作系统的一部分，而系统调用是操作系统 的一部分。运行状态不同。过程调用只能在用户态下运行，不能进入核心态，而系统调用 是在核心态下运行的。进入方式不同。过程调用在用户程序中调用，并直接在用户空间内 执行；而系统调用可以在用户程序中调用，但是在用户程序中执行到系统调用时，会产生异 常事件。 实现处理机状态从用户态到核心态的转变， 从而进入操作系统核心空间去执行系统 调用的代码。 (5) 试说明特权指令和系统调用之间的区别与联系。 答：特权指令是一类只能在核心态下执行的机器指令。而系统调用不是机器指令，它往 往以函数调用的形式出现， 实现操作系统提供的子功能， 它是操作系统与用户的编程接口 。 在用户程序中可以使用系统调用来获得操作系统服务， 在系统调用代码中可以使用特权指令 第第 3 章章 进程与进程通信习题参考答案进程与进程通信习题参考答案 1. 选择题 (1) B (2) D (3) B (4)D (5)D (6) A (7) C (8) D (9) D (10) D (11) C (12)D (13) A (14) B (15)B 共需要 260ms (16) C (17) B (18) C (19) (20) (21) (22) (23) (24) (25) (26) (27) B 2. 填空题 (1) 数据段 PCB (2) 并行 并发 (3) 资源分配 调度 (4) 阻塞 (5) 共享存储 (6) 运行时间短 等待时间长 (7) 阻塞状态 (8) 后备 (9) 可剥夺 非剥夺 (10) 1.5 3. 问答题 (1) 简述进程和程序之间的区别和联系。 答：进程和程序是既有区别又有联系的两个概念。 1) 进程是动态的，程序是静态的。程序是一组有序的指令集合，是一个静态的概念； 进程则是程序及其数据在计算机上的一次执行，是一个动态的集合。离开了程序，进程就失 去了存在的意义， 但同一程序在计算机上的每次运行将构成不同的进程。 程序可看作是电影 的胶片，进程可以看作电影院放电影的过程。 2) 一个进程可以执行多个程序，如同一个电影院的一场电影可放映多部影片。 3) 一个程序可被多个进程执行，如同多个影院同时利用一个电影的胶片放映同一部 电影。 4) 程序可以长期保存，进程只能存在于一段时间。程序是永久存在的，而进程有从被 创建到消亡的生命周期。 (2) 为什么将进程划分成运行、就绪和阻塞三个基本状态？ 答: 根据多道程序执行的特点，进程的运行是走走停停的。因此进程的初级状态应该是 执行和等待状态。 处于执行状态的进程占用处理机执行程序， 处于等待状态的进程正在等待 处理机或者等待其它某种事件的发生。但是，当处理机空闲时，并不是所有处于等待状态的 进程都能放到处理机上执行，有的进程即使分配给它处理机，它也不能执行，因为它的执行 的条件没有得到满足。因此，将等待状态的进程分成两部分，一部分是放在处理机上就能立 即执行，这就是就绪的进程；另一部分是仍需等某种事件发生的进程，即使放在处理机上也 不能执行的进程，这就是阻塞进程。 (3) PCB的作用是什么？它主要包含哪些内容？ 答: 操作系统管理的进程是多种多样的，要对这些进程实施有效的管理，必须对进程进 行抽象。 为了便于系统控制和描述进程的活动， 在操作系统核心为进程定义了一个进程控制 块PCB。PCB用于描述进程的基本情况以及进程运行和变化的过程，它与进程一一对应。当 系统创建进程时，为进程分配一个PCB；在进程运行过程中，系统通过PCB对进程实施管理 和控制；进程结束时，系统将收回PCB。 PCB中的内容主要包括调度信息和现场信息两大部分。调度信息包括进程名、进程号、 优先级、当前状态、资源信息、程序和数据的位置信息、隶属关系和各种队列指针信息等。 现场信息主要包括程序状态字、时钟寄存器和界限寄存器等描述进程运行情况的信息。 (4) 简述创建进程的大致过程 解 创建一个进程大体分以下几步： 1) 申请一个空白的PCB和唯一的进程标识号pid 2) 为新进程分配除CPU以外的资源，包括内存空间； 3) 初始化PCB中的数据项，包括标志信息、状态信息、控制信息等； 4) 将新进程的PCB插入系统的就绪队列。 (5) 为何引入线程？线程与进程的关系是什么？ 答：在操作系统中引入进程的目的，是为了使多个程序并发执行，以改善资源利用率及 提高系统的吞吐量； 那么， 在操作系统中再引入线程则是为了减少程序并发执行时所付出的 时空开销，使操作系统具有更好的并发性。 线程具有许多传统进程所具有的特征，故又称为轻型进程(Light-Weight Process)或进程 元；而把传统的进程称为重型进程(Heavy-Weight Process)，它相当于只有一个线程的任务。 在引入了线程的操作系统中，通常一个进程都有若干个线程，至少需要有一个线程。 (6) 何谓进程通信？试列举几种进程通信方式。 答：进程之间的信息交换，就是进程通信。进程同步与互斥，就实现了进程之间交换信 息，但由于交换的信息量少，可以看作是低级通信。并发执行的进程，有交换信息的各种需 要，除同步与互斥外，还可采用其它的通信方式。介绍几种常用的通信方式：共享存储、消 息传递、管道。 (7)进程的三个基本的转换如下图所示，图中1、2、3、4分别代表某种类型状态变迁， 请分别回答： 2 运行 就绪 阻塞 1 3 4 1）什么事件引起各状态之间的变迁？ 2）系统中常常由于某一进程的状态变迁引起另一进程也产生状态变迁，试判断变迁 3 1、21、32、41、34 是否存在因果关系？ 答答: 1) 引起各变迁的事件如下： 变迁 1：正在执行的进程从处理机上退下，导致进程调度程序从就绪状态的进程中选取 一个进程。 变迁 2：正在执行的进程所分配的时间片用完，导致进程从处理机上退到就绪状态；或 者在可抢占优先级的进程调度中， 有更高有先级的进程进入就绪状态， 导致正在执行的进程 从执行状态退到就绪状态。 变迁 3：进程需要等待事件的发生； 变迁 4：进程所等待的某事件发生了（如 I/O 完成） ； 2) 可能发生的因果变迁 31：由于处于运行状态的进程转入阻塞状态，进程调度程序根据调度算法，又从 就绪队列中选择一个进程投入运行； 21：由于处于运行状态的进程时间片用完，重新转入就绪状态，从而使进程调度程 序又从就绪队列中选择一个进程投入运行； 32：此种变化不存在； 41：4 的发生与 1 的发生没有必然关系； 34：3 的发生和 4 的发生没有必然关系。 (8) 设在内存中有三道程序A、B和C，并按A、B、C的优先次序运行，其在CPU上运行 时间以及I/O时间分别为： A：计算30ms，I/O 40ms，计算10ms B：计算30ms，I/O 50ms，计算10ms C：计算20ms，I/O 40ms，计算20ms 试画出按多道程序运行的时间关系图(调度程序的执行时间忽略不计)，完成这三道程序 共花多少时间？比单道运行节省多少时间?(假定运行环境为单CPU，每个程序所用的I/O设 备相同，比如打印机) 答：三道程序共花180ms，比单道（80+90+80）ms=250ms节省了70ms。 CPU I/O 0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 t/ms A B C A 空闲 B 空闲 C 图1 三道作业并发运行情况 (9) 下表给出了4个作业J1、J2、J3、J4的提交时间、运行时间，试分别采用FCFS、SJF 和HRRF调度算法，求出在各种作业调度算法下作业的平均周转时间。 表1 4个作业的提交时间和运行时间表 作业名 提交时间 运行时间/h J1 10:00 2 J2 10:18 1 J3 10:48 0.5 J4 11:00 0.8 解：采用FCFS作业调度算法时，根据这4个作业提交作业的先后顺序依次运行，每个作 业的周转时间如表2所示。 表 2 FCFS调度算法性能表 作业名 提交时间 运行时间/h 开始时间 完成时间 周转时间/h J1 10:00 2 10:00 12:00 2 J2 10:18 1 12:00 13:00 2.7 J3 10:48 0.5 13:00 13:30 2.7 J4 11:00 0.8 13:30 14:18 3.3 作业的平均周转时间 = （2+2.7+2.7+3.3）h/4=2.675h 采用SJF作业调度算法时，每个作业的周转时间如表3所示。 表3 SJF调度算法性能表 作业名 提交时间 运行时间/h 开始时间 完成时间 周转时间/h J1 10:00 2 10:00 12:00 2 J2 10:18 1 13:18 14:18 4 J3 10:48 0.5 12:00 12:30 1.7 J4 11:00 0.8 12:30 13:18 2.3 作业的平均周转时间 = （2+4+1.7+2.3）h/4=2.5h 采用HRRF作业调度算法时，每个作业的周转时间如表4所示。当时间为10:00时，仅有 作业J1，J1先运行。当作业J1结束后，此时系统中存在3个作业，计算这3个作业J2、J3、J4 的响应比，分别为2.7、3.4、2.25。作业J3的响应比高，作业J3运行。当作业J3结束后，系 统中剩下2个作业，计算这2个作业J2、 J4的响应比， 分别为3.2、 2.875。作业J2的响应比高， 运行作业J2。作业J2运行结束后，运行作业J4。 表 4 HRRF调度算法性能表 作业名 提交时间 运行时间/h 开始时间 完成时间 周转时间/h J1 10:00 2 10:00 12:00 2 J2 10:18 1 12:30 13:30 3.2 J3 10:48 0.5 12:00 12:30 1.7 J4 11:00 0.8 13:30 14:18 3.3 作业的平均周转时间 = （2+3.2+1.7+3.3）h/4=2.55h (10) 引起进程调度的主要因素主要有哪些？ 答： 1) 一个进程运行完毕； 2) 一个正在运行的进程被阻塞； 3) 在抢占式调度中，一个高优先级的进程被创建； 4) 在抢占式调度中，一个高优先级进程由阻塞被唤醒； 5) 在轮转式调度中，正在运行的进程运行完一个时间片。 (11)【答案要点】 (1)由于采用了静态优先数，当就绪队列中总有优先数较小的进程时，优先数较大的进 程一直没有机会运行，因而会出现饥饿现象。 (2)优先数priority的计算公式为： priority=nice+k1*cpuTime-k2*waitTime，其中k10, k20, 用来分别调整cpuTime和 waitTime在priority中所占的比例。waitTime可使长时间等待的进程优先数减小，从而避 免出现饥饿现象。 第第 4 章章 进程进程互斥互斥、同步与死锁同步与死锁 思考与练习题参考答案思考与练习题参考答案 1. 选择题 (1) D (2)D (3) C (4) A (5) B, A (6) B,D (7) A (8) A (9) B (10) C (11) D (12) A (13) D (14) D (15) A (16) B (17) C (18) C (19) B (20) D (21) D (22) C (23) D (24) B (25) B (26) B (27) B (28)A (29)B (30) C 2. 填空题 (1)环路等待条件。 (2)临界资源。 (3) P、V 等待 (4) 可用资源数目 等待该资源的进程数。 (5) 等待 (6) P V (7) 进程 (8) 安全 不安全 3. 问答题与同步题 (1) 在多道程序系统中程序的执行失去了封闭性和再现性，因此多道程序的执行不需要 这些特性，这种说法是否正确 ？ 答：答：这种说法不正确。可以想象，如果一个程序在多道程序系统中，在相同的输入的情 况下，多次执行所得结果是不同的，有谁还敢使用这个程序？因此，多道程序的执行也需要 封闭性和再现性， 只不过单道程序系统的封闭性和再现性是先天固有的， 多道程序系统的程 序执行要想获得封闭性和再现性， 需通过程序员的精心设计才能得到。 所使用的方法就是同 步和互斥的方法。 (2) 多个进程对信号量S进行了5次 P操作，2次V操作后，现在信号量的值是 -3，与信 号量S相关的处于阻塞状态的进程有几个？信号量的初值是多少？ 解：解： 因为 S 的当前值是-3，因此因为 S 处于阻塞状态的进程有 3 个； 因为每进行一次 P(S)操作，S 的值都减 1，每执行 1 次 V 操作 S 的值加 1，故信号量的 初值为-3+5-2=0; (3)解解: 在这个问题中，司机与售票员间是并行操作的，司机和售票员各自的操作是顺 序进行的。因此司机是一个进程，售票员是一个进程，它们之间是合作关系，即同步关系。 根据一般常识，司机和售票员在车上的操作规则如下： 售票员操作的规则是只有司机停车后，售票员才能开门让乘客上下车； 司机操作的规则是只有售票员关门后，司机才能启动开始行驶汽车。 根据同步规则以及操作流程确定信号量的个数是 2 个，S1 和 S2。 S1 的含义是否关门，其初值为 0，表示开门，其值若为 1 表示关门； S2 的含义是否停车，其初值为 1，表示停车，其值若为 0 表示开车。 司机在的操作：在开车前看是否关门？若没关则等待，这是一个 P(S1)操作；若门关， 则开车。到达一个站点，则停车，这是一个 V (S2) 操作； 售票员的操作：看是否停车？若没停则等待，这是一个 P (S2) 操作；若停则开门，这 是一个 V(S1) 操作。 司机与售票员的协调操作描述如下： int S1=0; int S2=1; main() cobegin driver(); busman(); coend driver() while (1) P(S1)； 启动车辆； 正常行车； 到站停车； V(S2)； busserver () while (1) 关车门； V(S1)； 售票； P(S2)； 开车门； 上下乘客； (4)解: 信号量 S 的初值为 300； int S=300 main() P1( ); P2( ); Pn( ); P1() P(S)； 进入售票厅； 购票； 退出售票厅； V(S)； Pn( ) P(S)； 进入售票厅； 购票； 退出售票厅； V(S)； (5)解：解：该算法有错。 若 A 进程永不要求访问临界资源，则不会执行 V(S1)，意味着 B 进程的申请永远得不 到操作临界资源的机会；同理，若 B 进程不要求访问临界资源，则不会执行 V(S2)，意味着 A 进程下次也得不到操作临界资源的机会。 所以问题在于本应进行互斥控制而使用的却是同 步控制。实现改正如下： 设置信号 mutex，初值为 1； A 进程 P(muyex) CSA V(mutex) B 进程 P(mutex) CSB V(mutex) 第(5)题改正图 A 进程 CSA V(S1) P(S2) B 进程 P(S1) CSB V(S2) 图 4-5 第(5)题图 (6) 解解 在本题中，应设置三个信号量S、So、Sa，信号量S表示盘子是否为空，其初值 为1；信号量So表示盘中是否有桔子，其初值为0；信号量Sa表示盘中是否有苹果，其初值 为0。同步描述如下： int S=1; int Sa=0; int So=0; main( ) cobegin father(); son(); daughter(); coend father() while(1) P(S ); 将水果放入盘中； if （放入的是桔子） V(So); else V(Sa); son( ) while(1) P(So); 从盘中取出桔子； V(S); 吃桔子； daughter( ) while(1) P(Sa); 从盘中取出苹果； V(S); 吃苹果； (7) 解解 按序分配是适应于动态分配的一种分配方法。 为了避免产生死锁， 系统将所有资源进行 编号，并规定进程请求资源时，严格按照设备编号的大小，比如由小到大的顺序进程申请。 如果某进程第n号资源没有获得，则进程不能请求第j（jn）号资源。（系统也可以规定由 大到小的请求次序。） 因为按序分配可以破坏环路等待条件，因此可以防止死锁。 (8) 解：(1)从表1分析可知，可用资源数能满足进程P2，当P2运行结束后，释放它所占 有的资源，使可用资源数目变为(6，2，3)。此刻，可用资源可满足其他任一进程，若将可 用资源分配给进程P1，P1结束后，可用资源数变为(7，2，3)。再将可用资源分配给进程P3， P3结束后，可用资源数变为(9，3，4)。最后将可用资源分配给进程P4，P4结束后，可用资源 数变为(9，3，6)。因此，系统在T0时刻是安全的。 （2）由于P3请求资源数(1，0，1)小于可用资源数(1，1，2)，因此现有资源能满足P3的 要求。系统先假定为P3分配资源，则可用资源数变为(0，1，1)。修改相关数据，如表2 所 示。 表 P3申请资源后的资源分配表 资源 进程 Max Allocation Need Available R1 R2 R3 R1 R2 R3 R1 R2 R3 R1 R2 R3 P1 3 2 2 1 0 0 2 2 2 0 1 1 P2 6 1 3 5 1 1 1 0 2 P3 3 1 4 3 1 2 0 0 2 P4 4 2 2 0 0 2 4 2 0 此刻，可用资源数（0，1，1）无法满足任一个进程的需要，故系统进入不安全状态， 因此，系统不能为P3分配资源。 (9) 解 定义信号量S1控制P1与P2之间的同步；S2控制P1与P3之间的同步；empty控制生产者与 消费者之间的同步；mutex控制进程间互斥使用缓冲区。程序如下： Var s1=0,s2=0,empty=N,mutex=1; Cobegin P1:begin X=produce(); P(empty); P(mutex); Put(); If x%2=0 V(s2); else V(s1); V(mutex); end. P2:begin P(s1); P(mutex); Getodd(); Countodd():=countodd()+1; V(mutex); V(empty); end. P3:begin P(s2) P(mutex); Geteven(); Counteven():=counteven()+1; V(mutex); V(empty); end. CoEnd. (10) 解： 互斥资源：取号机(一次只允许一位顾客领号)，因此设一个互斥信号量mutex； 同步问题：顾客需要获得空座位等待叫号，当营业员空闲时，将选取一位顾客并为其服 务。空座位的有、无影响等待顾客数量，顾客的有、无决定了营业员是否能开始服务，故分 别设置信号量empty和full来实现这一同步关系。另外，顾客获得空座位后，需要等待叫号和 被服务。这样，顾客与营业员就服务何时开始又构成了一个同步关系，定义信号量service 来完成这一同步过程。 semaphore mutex=1； /互斥使用取号机 semaphore empty=10； /空座位的数量 semaphore full=0； /已占座位的数量 semaphore service=0； /等待叫号 cobegin process顾客i P(empty)； P(mutex)； 从取号机获得一个号； V(mutex)； V(full)； P(service)； /等待叫号 获得服务； process营业员 while(TRUE) P(full)； V(empty)； V(service)； /叫号 为顾客服务； coend (11) 解答： / 定义两个信号量 Semaphore empty = 500; / / 博物馆可以容纳的最多人数(2 分) Semaphore mutex = 1; / / 用于出入口资源的控制(2 分) cobegin 参观者进程 i; P ( empty ); P ( mutex ); 进门; V( mutex ); 参观; P ( mutex ); 出门; V( mutex ); V( empty ); coend (12) 解答： 本题是一个生产者-消费者的变型，本题是多个生产者-多个消费者类型，生产者和消费 者之间并不互斥访问缓冲区， 但生产者和生产者之间， 消费者和消费者之间要互斥访问缓冲 区， 并且本题的消费者一次需要取走10件产品，如果没有它会等待，而不是等到有了10件 产品后，才进行取走操作。 本题的缓冲区B可描述为 buffer array 1000; 1)生产者之间设互斥信号量mutex1，消费者之间设互斥信号量metex2。 2)上述进程的同步问题，需设置3个信号量，其中empty对应空闲的缓冲单元，初值为 1000；full对应缓冲区中待取走的产品数，初值为0；另外，还需定义2个整型变量in、out， 分别用来指示下一个可存放产品的缓冲单元、下一个取走的缓冲单元，它们的初值均为0。 过程如下： buffer array 1000; /存放产品的缓冲区 buffer nextp; /用于临时存放生产者生产的产品 buffer nextc 10; /用于临时存放消费者取出的产品 semaphore empty = 1000; /空缓冲区的数目 semaphore full = 0; /满缓冲区的数目 semaphore mutex1 = 1; /用于生产者之间的互斥 s emaphore mutex2 = 1; /用于消费者之间的互斥 int in = 0; /指示生产者的存位置 int out = 0; /指示消费者的取位置 Producer() /生产者进程 Produce an item put in nextp; /生产一个产品，存在临时缓冲区 P(empty); /申请一个空缓冲区 P(mutex1); /生产者申请使用缓冲区 arrayin=nextp; /将产品存入缓冲区 in = (in+1)%1000; /指针后移 V(mutex1); /生产者缓冲区使用完毕，释放互斥信号量 V(full); /增加一个满缓冲区 Consumer() /消费者进程 P(mutex2); /消费者申请使用缓冲区 for(int i = 0;i10;i+) /一个消费者进程需从缓冲区连续取走 10 件产品 P(full); /申请一个满缓冲区 nextci = arrayout; /将产品取出，存于临时缓冲区 out = (out+1)%1000; /指针后移 V(empty); /增加一个空缓冲区 V(mutex2); /消费者缓冲区使用完毕，释放互斥信号量 Consume the items in nextc; /消费掉这 10 个产品 (13) 解答： 互斥信号量mutexA，用来实现两个进程互斥地使用A用户的邮箱，其初值为1; 互斥信号量mutexB=1，用来实现两个进程互斥地使用B用户的邮箱，其初值为1; 同步信号量emptyA和fullA用来实现A和B进程的同步使用A的邮箱，emptyA指可接收邮 件数， fullA指已接收邮件数， 因初始时A邮箱中有x件邮件， 因此， emptyA的初值为M-x, fullA 的初值为x; 同步信号量emptyB和fullB用来实现A和B进程的同步使用B的邮箱，emptyB指可接收邮 件数， fullB指已接收邮件数， 因初始时B邮箱中有y件邮件， 因此， emptyB的初值为N-y, fullB 的初值为y. 算法描述如下： Semaphore mutexA=1; Semaphore mutexB=1; Semaphore emptyA=M-x; Semaphore fullA=x; Semaphore emptyB=N-y; Semaphore fullB=y; CoBegin A While(TRUE) P(fullA); P(mutexA) Get a mail from A_mailbox； V(mutexA) V(emptyA) Answer the question and raise a question; P(emptyB) P(mutexB) send the mail to B； V(mutexB); V(fullB); B While(TRUE) P(fullB); P(mutexB) Get a mail from B_mailbox； V(mutexB); V(emptyB); Answer the question and raise a question; P(emptyA); P(mutexA) send the mail to A； V(mutexA); V(fullA); CoEnd 第第 5 章章 存储管理存储管理 思考与练习题参考答案思考与练习题参考答案 1. 选择题 (1) A (2) A (3) D (4) B (5) D (6) A (7) A (8) A (9) C (10)C (11)A (12)B (13)B * (14)D (15)A (16)B (17)C (18)B (19)B (20)C (21)A (22)D (23)B (24)C (25)A (26)D (27)A 注*: 1 页为 1KB，一页可存储 512 个页地址（页表项大小为 2 字节） ，页目录中至少要 有 216/29项=128。) 2. 填空题 (1) 地址重定位(或：地址映射) (2) 静态重定位、动态重定位 (3) 解决在主存容量较小的存储空间中运行较大程序的矛盾（或：为了扩充内存） (4) 存储容量扩充的存储系统 (5) 页面置换 (6) 缺页次数 (7) 执行之前，执行过程中 (8) 内部碎片，外部碎片 (9) 时间局部性、空间局部性 (10) 段表，页表 3. 问答与计算题 (1) 什么是物理地址？什么是逻辑地址？ 答：物理地址是内存中各存储单元的编号，即存储单元的真实地址，它是可识别、可寻 址并实际存在的。用户程序经过编译或汇编形成的目标代码，通常采用相对地址形式，其首 地址为零， 其余指令中的地址都是相对首地址而定。 这个相对地址就称为逻辑地址或虚拟地 址。逻辑地址不是内存中的物理地址，不能根据逻辑地址到内存中存取信息。 (2) 什么是地址重定位？为什么要进行地址重定位？ 答：为了保证 CPU 执行程序指令时能正确访问存储单元，需要将用户程序中的逻辑地 址转换位运行时可由机器直接寻址的物理地址，这一过程称为地址映射或地址重定位。 我们写程序的时候根本不关心变量、常量、指令的位置，因为源程序在编译的时候统一 以 0 为起始地址进行编址， 当程序在运行时， 所在的存储空间中的地址与程序用用的地址不 一致，因此必须要进行地址重定位才能保证程序的正确运行。 (3) 可变式分区存储管理常用的分配算法有哪几种？比较它们的优缺点。 可变式分区存储管理常用的分配算法有： 首次适应(First fit)、循环首次适应(Next fit)、 最佳适应(Best fit)和最坏适应(Worst fit)等算法。 首次适应算法， 每次分配都需要从链首也就是低地址开始查找， 低地址被划分的可能性 比较大，容易形成多个过小分区而难以利用，成为外部碎片。同时可能把一个较大的空闲分 区分配给一些较小的作业，造成大分区逐渐分割成许多小分区，对大作业不利。而且这些小 分区增加了查寻时的判断时间，降低了分配的效率。 循环首次适应算法(Next fit)，可以使内存区分配比较平均，减少查寻次数，但缺失大空 闲分区现象会更加严重，使得大作业无法装入。 最佳适应算法的平均查找次数为分区数的一半， 而且可以避免把大的空闲分区分割成小 的空闲分区，所以说它是“最佳适应”的。但这种算法所造成的剩余空闲分区必定是相对最 小的，也就是说，每次分配一个分区就可能造成一个无法再利用小空闲分区。 最坏适应算法与最佳适应算法相反，它具有查找速度快，分区碎片少的优点，但它会产 生缺失大分区的缺点。 (4) 什么是内部碎片？什么是外部碎片？如何克服外部碎片问题？ 答：可变分区随着作业对存储区域的不断申请与释放，将使分区的数目逐渐增加，每个 分区的长度会逐步减小， 同时也导致空闲分区越来越小， 使得空闲分区满足作业存储要求的 能力下降，甚至有可能分配不出去。在存储管理中，把这种无法满足作业存储请求的空闲区 称为“外部碎片”或“外零头” 。那么，内部碎片是分配给了用户而未被用户完全利用的空 闲部分，而外部碎片则是无法分配给用户使用的空闲分区。可以采用先进的存储管理技术， 比如分页存储管理技术客服外部碎片问题。 (5) 在请求分页式存储管理中，为什么既有快表，又有页表？ (6) 什么是虚拟存储器？使用虚拟存储器有什么好处？ (7) 什么是抖动现象？它有什么危害？ (8) 什么是程序的局部性原理？ (9) 分页式存储管理与分段式存储管理的主要区别是什么？ (10) 假设某作业为 4.3KB 大小， 在逻辑地址 1000 号单元处有指令 MOV R1,3500， 3500 号单元有数据 12345。采用分页式存储管理，页面大小为 1KB 字节，该作业进入内存后， 其页面 0，1，2，3，4 被分配到内存的 2、4、6、7、9 块中，完成下列要求： 1) 画出该作业的页表 2) 画出当执行指令 MOV R1,3500时，如何进行地址重定位，将逻辑地址 3500 号单 元处数据 12345 送入 R1 寄存器。 解: 1) 页表为： 页号 块号 0 2 1 4 2 6 3 7 4 9 2) 逻辑地址到物理地址变换过程如图所示. P=3500/1024=3 W=3500 % 1024 =428 0 2 1 4 2 6 3 7 4 9 7 428 页号 P 页内地址 W 块号 B 块内地址 W 3 428 页表控制寄存器 页表始址 a 页表长度 L 比较 PL 越界中断 页号 块号 3500 内存 0 1 2 7 8 12345 页表 物理地址为 71024+428=7596. (11) 考虑页面走向是:4,3,2,1,4,3,5,4,3,2,1,5。当内存块数量分别为 3 和 4 时,试问采用 LRU、FIFO、OPT 这 3 种置换算法的缺页次数各是多少(假定所有内存块起初为空)? (12) 某系统采用页式存储管理策略，拥有逻辑空间 32 页，每页为 2KB，拥有物理空间 1MB。 1)写出逻辑地址的格式。 2)若不考虑访问权限等，进程的页表有多少项？每项至少有多少位？ 3)如果物理空间减少一半，页表结构应该做怎样的改变？ 答：1)该系统拥有逻辑空间 32 页，故逻辑地址中页号至少用 5 位二进制来描述，而每 页 2KB，因此页内位移必须用 11 位二进制来描述。这样，可得到逻辑地址格式如下图所示。 2) 每个进程最多有 32 个页面，因此进程的页表项最多有 32 项。若不考虑访问权限等， 则页表项中需要给出页所对应的物理块号。1MB 的物理空间可分成 512 个内存块，故每个 页表项至少有 9 位。 3) 如果物理空间减少一半，页表结构可以不改变，也可以将每个页表项的位数定义为 8 位。 注：题目要求“某系统采用页式存储管理策略，拥有逻辑空间 32 页，每页为 2KB” ， 这就说明这个系统可以执行最大的程序为 32 页。 即该存储管理策略可以管理逻辑空间为 32 页。 (13) 1) 略 2) 计算过程如下： S=69732 / 65536 = 1 PW = 69732 % 65536 = 4196 P=4196 / 4096 =1 W=4196 % 4096 =100 由段号 S=1 找到页表 1. 由页号 P=1 找到物理块号 B=8 虚地址 69732 的物理地址为 8*4096+W=32868 图 逻辑地址格式 15 11 10 0 页号 P 页内地址 W 第第 6 章章 设备设备管理管理 思考与练习题参考答案思考与练习题参考答案 1. 选择题 (1) C (2) A (3) C (4) D (5) A (6) C (7) D (8) A (9) A (10)A (11)B (12)B (13)A (14)B (15)B (16)D (17)C (18)C (19)B (20)A (21)B (22)B (23)D (24)B (25)A (26)D 2. 填空题 (1) 字符设备、块设备 (2) 硬件缓冲、软件缓冲 (3) 管理输入输出操作 (4) 静态分配 (5) 虚拟设备 (6) SPOOLing (7) 块 (8) 设备控制表、控制器控制表 (9) 通道命令字 (10) 字符设备、块设备、网络设备 3. 问答题 3. 问答题 (1) 设备管理的目标和功能是什么? (2) 数据传送控制方式有哪几种?它们各自的优缺点是什么？ (3) 什么是通道? 试画出通道控制方式时的 CPU、通道和设备的工作流程图。 (4) 什么是缓冲? 为什么要引入缓冲? (5) I/O 控制可用哪几种方式实现? 各有什么优缺点? (6) 何谓设备驱动程序?为什么要使用设备驱动程序? (7) 简述设备控制器的组成及功能。 (8) 输入/输出软件组织自底向上由哪几个层次组成？ (9) 什么是设备无关性？为什么要引入设备无关性？ (10) 简述与设备无关的 I/O 软件和用户层的 I/O 软件。 (11) 什么是 SPOOLing 系统？SPOOLing 系统有哪几部分组成？ (12) 什么是 RAID？它是如何提高磁盘的访问速度和可靠性的？ (13) 假设磁盘有 200 个磁道(从 0 号到 199 号)。目前正在处理 143 号磁道上的请求，而刚刚处理结 束的请求是 125 号，如果下面给出的顺序是按 FCFS 排成的等待服务队列顺序： 86，147，91，177，94， 150，102，175，130 那么，用下列各种磁盘调度算法来满足这些请求所需的总磁头移动量是多少? FCFS； SSTF； SCAN； C-SCAN。 答： FCFS:565 SSTF:162 SCAN:125 C-SCAN:169 (14) 假设计算机系统采用 CSCAN(循环扫描)磁盘调度策略， 使用 2KB 的内存空间记录 16384 个磁盘块 的空闲状态。 请说明在上述条件下如何进行磁盘块空闲状态的管理。 设某单面磁盘旋转速度为每分钟 6000 转，每个磁道有 100 个扇区，相邻磁道间的平均移动时间为 1ms。若在某时刻，磁头位于 100 号磁道处，并沿着磁道号增大的方向移动(如下图所示)，磁道号请求队列 为 50，90，30，120，对请求队列中的每个磁道需读取 1 个随机分布的扇区，则读完这 4 个扇区点共需要 多少时间？要求给出计算过程。 如果将磁盘替换为随机访问的 Flash 半导体存储器(如 U 盘、 SSD 等)， 是否有比 CSCAN 更高效的磁 盘调度策略？若有，给出磁盘调度策略的名称并说明理由；若无，说明理由。 用位图表示磁盘的空闲状态。每一位表示一个磁盘块的空闲状态，共需要 16384 32=512 个字=512 4 个字节=2KB，正好可放在系统提供的内存中。 采用 CSCAN 调度算法，访问磁道的顺序和移动的磁道数如下表所示： 被访问的下一个磁道号 移动距离(磁道数) 120 20 30 90 50 20 90 40 移动的磁道数为 20+90+20+40=170，故总的移动磁道时间为 170ms。 由于转速为 6000r/m，则平均旋转延迟为 5ms，总的旋转延迟时间=20ms。 由于转速为 6000r/m，则读取一个磁道上一个扇区的平均读取时间为 0.1ms，总的读取 扇区的时间平均读取时间为 0.1ms，总的