第一章 操作系统的基本概念

一.填空题

1. 1．计算机系统是由硬件系统和____系统两部分组成。

2. 2．操作系统是计算机系统的一种系统软件，它以尽量合理、有效的方式组织和管理计算 机的________，并控制程序的运行，使整个计算机系统能高效地运行。

3. 3.从资源分配的角度讲，计算机系统中的资源分为处理机、_______ 、输入／输出设备 和文件资源。

4. 5．按内存中同时运行程序的数目可以将批处理系统分为两类：单道批处理系统和____。

5. 6．操作系统的主要性能参数有____和利用率等。前者指的是单位时间内系统处理的作业 量。后者指的是在一个给定时间内，系统的一个指定成分被使用的时间比例。

6. 4．并发和______是操作系统的两个最基本的特征，两者之间互为存在条件。

7. 7. __________系统不允许用户随时干预自己程序的运行。

8. 8．实时系统通常采用﹎﹎﹎方法来提高可靠性。

9. 9.UNIX操作系统是著名的﹎﹎﹎系统。

10. 10.DOS系统是﹎﹎﹎操作系统。

11. 11. ﹎﹎﹎系统一般采用时间片轮转的办法，使一台计算机同时为多个终端用户服务， 对每个用户都能保证足够快的响应时间，并提供交互会话能力；

12. 12. ﹎﹎﹎系统是操作系统的另一种类型，要求对外部输入的信息能以足够快的速度进 行处理，并在被控对象允许的时间范围内作出快速响应，其响应时间要求特别高。

13. 13.允许多个用户在其终端上同时交互地使用计算机的OS称为分时OS，它通常采用﹎﹎

﹎

策略为用户服务；

14. 14.允许用户把若干个作业提交计算机系统集中处理的OS，称为批处理OS，衡量这种系统

性能的一个主要指标是系统的 ﹎﹎﹎。

15. 15.在﹎﹎﹎的控制下，计算机系统能及时处理由过程控制反馈的数据并作出响应。设计 这种系统时，应首先考虑系统的实时性和可靠性。

解答:

1. 答：软件

2. 答：资源

3. 【答案】存储器 【解析】计算机系统中的资源分为硬件资源和软件资源。硬件资源有处理机、内／外存 储器及输入／输出设备。而软件资源指的是程序、数据和相应的文档。从资源管理的观点， 操作系统是计算机资源系统的管理系统，它提供了处理机管理、存储器管理、输入／输出设 备管理和信息文件管理的功能。对每种资源的管理都可从提供资源情况的记录、资源分配策 略、资源分配和回收等几个方面来加以讨论。

4. 答：多道批处理系统

5. 答：吞吐率

6. 答：共享

7. 答：批处理

8. 【答案】双工体制 【解析】在实时系统中，为了追求高可靠性，最一般的方法是采用硬件的冗余技术 。所谓双工体制，就是采用性能完全一样的两套设备并让它们同步工作。

9. 答案：分时系统

10. 答案：单用户（或单用户、单任务）

11. 答案：分时系统

12. 答案：实时系统

13. 【答案】时间片轮转

14. 【答案】吞吐率

15. 【答案】实时OS

二.简答题

1. 1．简述操作系统有哪些特征？

2. 2．操作系统的功能有哪几方面？它们各自的含义是什么？

3. 3．操作系统有哪几种类型，各自的工作方式是怎样的？

4. 4．简述操作系统在一个计算机系统中的地位。

5. 5. 试对分时系统和实时系统进行比较。

6. 6、什么是操作系统？它有什么基本特征？

7. 7、在批处理系统、分时系统和实时系统中，分别常用哪种调度算法？

8. 8. 简述三种基本类型操作系统的优缺点。

9. 9、简述设备管理的任务和功能。

10. 10．现有一下应用计算机的场合，请为其选择适当的操作系统。1）航天航空，核变研究 ；2）国家统计局数据处理中心；3）学校学生上机学习编程 4）高炉炉温控制；5）民航定票

系统，6）发送电子邮件（在两个地区之间）

解答:

1. 【解析】 （1）并行性：即系统中存在着多个程序，宏观上它们同时“运行”。而实际上，在单

CP

U系统中，这些并发执行的程序是交替的在CPU上运行。 （2）共享性：即系统中存在的多个并发执行的程序，它们共享系统所有的软、硬件资源 。

2. 【解析】 操作系统负责管理计算机系统的所有资源，并调度这些资源的使用。具体来说，其 主要功能有： （1）处理机管理 处理机管理也称为进程管理，主要解决的问题是按一定的算法将处理机分配给系统 中某个并发执行的程序即“进程”，使CPU资源得到充分地应用。 （2）存储管理 存储管理主要负责内存空间的管理，按一定策略为多个并发执行的程序（进程）分 配内存空间，以充分利用内存空间，并负责保证内存中各程序间的信息不相互破坏、窃取。 （3）设备管理 设备管理负责对系统中所有的输入/输出设备进行管理，除了一般意义上的I/O设备

外，这里还应包括外存、通道、控制器。设备管理负责对设备进行分配、启动和故障处理。 目的是提高设备使用效率，方便用户进行输入/输出。 （4）文件管理 计算机系统中的信息是以文件形式存放在外存上的。文件管理的任务是负责对系统 中的文件进行存储、组织、检索等对文件的操作，以方便用户对文件的访问，并解决多用户 间文件的共享、保护、保密等问题。 （5）作业管理 作业管理的任务是为用户提供一个使用计算机系统的环境，使用户能有效、方便地组织 自己的作业（工作流程），并尽可能地提高整个系统的效率。

3. 【解析】 操作系统的基本类型有：批处理系统、分时系统、实时系统、个人计算机操作系统 、网络操作系统和分布式操作系统。 （1）批处理系统 在批处理系统中，用户不能直接控制其作业的运行。一个作业包括：程序、数据和 作业说明书，作业说明书中描述该作业的处理要求。 用户通过输入设备将作业提交给系统后，系统将其放入外存的后备作业队列中，系 统按一定调度策略从后备作业队列中选择一个或多个作业进入内存，系统按作业说明书运行 作业。即运行过程中，用户与作业间没有交互作用，不能直接干预作业的运行。 （2）分时系统 在分时系统中，主机连接着多个终端（Terminal），用户使用各自的终端直接控制 自己“程序”运行，操作系统采用时间片轮转的方法轮流为多个用户服务。UNIX就是一个非

常著名的分时系统。 分时系统具有以下特点： ? 多路性 微观上各用户轮流使用计算机，宏观上各用户并行工作。

? 交互性 用户直接控制自己的“程序”运行，以人-机会话方式工作。 ? 独立性 各用户可独立操作，互不干涉，不会发生混淆或破坏现象。 ? 及时性 对用户的请求能及时作出响应，尤其是较批处理系统响应时间 快。 （3）实时系统 实时系统往往是作为一控制设备使用的，它能够及时响应随机发生的外部事件，并在严 格的时间范围内完成事件的处理，主要特点一是及时性、一是高可靠性。实时系统又分为实 时控制系统（如工业过程控制）和实时信息处理系统（如航空、铁路订票系统）。 （4）个人计算机操作系统 由于近年来个人计算机（PC）的发展，个人计算机操作系统也有了很大发展，如Windows 95/98/2000系列操作系统、DOS、OS2等，它们都是较为著名的个人计算机操作系统，用户 以联机交互方式使用计算机。 （5）网络操作系统 网络操作系统是使网络上各计算机能方便而有效地通信及共享网络资源，为网络用户提 供所需各种服务的软件、有关协议的集合。包括网络管理、通信、系统安全和多种服务。 （6）分布式操作系统 分布式操作系统也是通过网络将具有自治功能的计算机互联，实现通信和资源共享，并 协作完成任务。它更强调如何将某个大任务划分为小任务，分派到不同系统协作完成。

4. 【解析】 操作系统是计算机系统中非常重要的系统软件，它是紧挨着硬件的第一层软件，提 供其它软件的运行环境，可以将其看成是用户与硬件的接口，是整个计算机系统的控制和指 挥中心。 它是一组用以控制、管理计算机系统中软、硬件资源，提高资源管理效率、方便用户使 用计算机的程序集合。

5. 答：分时操作系统是使一台计算机同时为多个用户服务的一种操作系统。 实时操作系统是使计算机能及时响应外部事件的请求，在严格规定的时间内完成对该事 件的处理，并控制所有实时设备和实时任务协调一致地工作的操作系统。 分时系统通用性强，交互性强，及时响应性要求一般（通常数量级为秒）；实时系统往 往是专用的，系统与应用很难分离，常常紧密结合在一起，实时系统并不强调资源利用率， 而更关心及时响应性（通常数量级为毫秒或微秒）、可靠性等。

6. 答：操作系统是计算机系统中的一个系统软件，能有效的组织和管理计算机系统中的硬 件及软件资源，合理的组织计算机工作流程，控制程序的执行，并向用户提供各种服务功能 ，使得用户能够灵活、方便、有效地使用计算机，使整个计算机系统能高效运行的一些程序 模块的集合。 操作系统有如下基本特征： （1）并行与并发 并行性：在同一时刻同时发生 并发性：宏观上在同一时间段内同时运行 CPU 与各个I/O 设备之间的并行 各应用程序“ 进程” 之间的并发 （2）共享性（Sharing）

操作系统中的资源可供内存中多个并发的执行的进程共同执行。 （3）虚拟性（Virtual） 通过某种技术把一个物理设备实体变为若干个逻辑上的对应物。 （4）异步性（Asynchronism） 进程是以人们不可预知的速度向前推进的，但结果要保证是固定的。

7. 答：批处理系统使用先来先服务算法。 分时系统使用时间片轮转算法。 实时系统使用优先级算法。

8. 答：操作系统有以下几种类型：多道批处理系统、分时系统、实时系统。 多道批处理系统的特点：多道、成批。 分时系统的特点：同时性、交互性、独立性、及时性。 实时系统的特点：交互能力较弱，系统专用，响应时间更严格、及时、可靠性要求更高 。

9. 答：主要功能：缓冲管理，设备分配和设备处理，以及虚拟设备等。 主要任务：完成用户提出的I/O请求，为用户分配I/O设备；提高CPU和I/O设备的利用率

；提高I/O速度；以及方便用户使用I/O设备。

10. 答：1)航天航空，核变研究：嵌入式操作系统 2）分布式操作系统 3）个人计算机操作系统 4）实时操作系统 5）批处理操作系统 6）网络操作系统。

三.应用题 解答:

第二章 操作系统的运行环境

一.填空题

1. 1. 计算机执行一个程序时，必须把程序和数据存放到计算机的_______中，并且占用硬 件资源________执行时才能完成程序的功能。

2. 2. 操作系统程序占用CPU时应让中央处理器工作在 ________状态，而用户程序占用CPU 时应让中央处理器工作在________状态。

3. 3. 每个计算机系统都有自己的中断机构，中断系统由两部分组成：________ 和操作系 统的________。

4. 4. 引起中断的事件称为 ________ ，对出现事件进行处理的程序称为________ 。

5. 5. PSW是用来控制指令执行顺序并且保留和指示与程序相关的系统状态，一般来说，PSW 包含程序的基本状态 、________和________三部分内容。

6. 6. 中断处理程序通常只屏蔽比自己级别________的中断事件，而________是不能屏蔽的 。

7. 7. 中断优先级的高低顺序为________ 、________、程序性中断、外部中断和输入输出 中断。

8. 8. 中断优先级是按中断事件的________来确定的，中断优先级是在硬件设计时规定的， 若要调整中断响应次序可通过 实现。

9. 9. 强迫性中断事件有硬件故障中断、________、外部中断和________事件．

10. 10. 外中断是指源自CUP以外事件的中断，通常与当前程序（进程）运行 ，内中断

（又叫异常）是指源自CUP内部时间的中断，通常与当前程序（进程）运行 。

11. 11. 操作系统借助于硬件的________和________装置，使得中央处理器与各种外围设备 以及外围设备之间均可并行工作，不仅使多个作业可以同时执行，而且加快了作业的执行速 度，提高了系统的吞吐量。

12. 12. 在多道程序设计中，应采用 的方法保证各道程序互不侵犯。多道程 序设计提高了系统的吞吐量，但可能会________某些程序的执行时间。

13. 13. 采用多道程序设计技术能充分发挥__________与__________并行工作的能力。

14. 14. 采用多道程序设计技术后可有效地提高系统中资源的________，增加单位时间的算 题量，从而提高了系统的________。

15. 15. 大、中型计算机的I/O硬件组织大多采用通道结构，具有通道结构的计算机系统，主

存、 、控制器和 之间采用四级连接，实施三级控制。

16. 16. 具有通道结构的I/O系统中，一个CPU可以连接多个 ，一个通道可以连接多

个 ，一个控制器可连接同类型的多台设备。

解答: 1. 2. 3. 4. 5.

6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16.

二.简答题

1. 1. 计算机系统中“引导程序”的主要功能是什么？

2. 2. 试述程序状态字寄存器的作用。

3. 3. 为什么要设置特权指令？哪些指令属于特权指令？

4. 4. 怎样限制用户程序使用特权指令？

5. 5. 什么是通道？通道起什么作用？

6. 6. 怎样解决中断响应顺序与处理顺序的不一致性和中断嵌套处理的问题？

7. 7. 多道程序设计从哪几方面提高系统的效率?

8. 8. 多道程序设计的特点有哪些？

9. 9. 实现多道程序设计必须解决哪些问题？

解答: 1. 2. 3. 4. 5. 6. 7. 8. 9.

三.应用题

1. 1. 在单CPU和两台I/O(I1,I2)设备的多道程序设计环境下，同时投入三个作业运行。它 们的执行情况如下： Job1：I2(30ms)、CPU(10ms)、I1(30ms)、CPU(10ms)

Job2：I1(20ms)、CPU(20ms)、I2(40ms) Job3：CPU(30ms)、I1(20ms) 如果CPU、I1和I2都能并行工作，优先级从高到低为Job1、Job2和Job3，优先级高的作业

可以抢占优先级低的作业的CPU，但不抢占I1和I2。试求： ①每个作业从投入到完成分别所需的时间。 ②从投入到完成CPU的利用率。 ③I/O设备利用率。

2. 2. 若程序PA和Pb单独执行时分别用Ta和Tb，Ta＝1小时，Tb＝1.5小时，其中处理器工作

时间分别TA＝18分钟,TB＝27分钟。如果采用多道程序设计方法，让PA,Pb并行工作，假定处

理器利用率达到50％，另加15分钟系统开销，请问系统效率能提高百分之几?

3. 3. 设主存中有3道程序A、B、C，A的优先级最高、B次之、C的优先级最低，它们的计算

时间和I/O操作的时间如下表所示（单位：ms）。假设3道程序使用相同的设备进行I/O操作，

即程序以串行方式使用设备。试画出单道运行和多道运行的时间关系图(调度程序的执行时间

忽略不计)，并计算3道程序并发执行比单道执行节省的时间。

4. 4. 现有作业序列：作业1（提交时间8：00，运行时间2.00h）；作业2（提交时间8：30 ，运行时间3．00h）；作业3（提交时间9：00，运行时间0.10h）；作业4（提交时间9：30， 运行时间0．50h）；时间单位为小时，以十进制计。使用FIFS和SJF调度算法处理该作业程序

，问哪种作业调度算法性能更好（要求给出计算的数据和必要的步骤）。

5. 5. 假定要在一台处理机上执行下列作业： 作业 执行时间 优先级 1 10 3 2 1 1 3 2 3 4 1 4 5 5 2

且假定这些作业在时刻0以1，2，3，4，5的顺序到达。

(1)说明分别使用FCFS，SJF以及非剥夺式优先级调度算法时，这些作业的执行情况。 (2)针对上述每种调度算法，给出平均周转时间和平均带权周转时间。

6. 6. 假定在一个处理机上执行以下5个作业： 作业号 到达时间 运行时间 1 0 4 2 1 6 3 2 5 4 3 3 5 4 2 分别画出采用FCFS、SJB、HRN调度算法时调度图，并分别计算每种调度算法中的每个作

业的周转时间和平均周转时间。

7. 7. 在单道批处理系统中，有四个作业到达输入井和需要的计算时间如表所示，现采用响 应比最高者优先算法，忽略作业调度所化的时间。当第一个作业进入系统后就可开始调度。 作业 到达输入井时间 需计算时间 开始时间 完成时间 周转时间

（1）填充表中空白处 （2）四个作业的执行次序为__________________。 （3）四个作业的平均周转时间为__________________。

8. 8. 在一个单CPU的计算机系统中，有两台外部设备R1、R2和三个进程P1、P2、P3。系统

采用可剥夺式优先级的进程调度方案，且所有进程可以并行使用I/O设备，三个进程的优先级

、使用设备的先后顺序和占用设备的间如下表所示：

假设操作系统的开销忽略不计，三个进程从投入运行到全部完成，CPU的利用率约为多少

？R2的利用率约为多少？（设备的利用率指该设备的使用时间与进程组全部完成所占用时间

的比率）。

解答: 1. 2. 3. 4. 5. 6. 7. 8.

第三章 操作系统提供的用户接口

一.填空题

1. 1．用户程序调用操作系统有关功能的途径是﹎﹎﹎。

2. 2．用户与操作系统的接口有命令接口，﹎﹎﹎ 两种。

3. 3．操作系统为用户提供两个接口。一个是操作员接口，用户利用它来组织和控制作业的

执行或管理计算机系统。另一个是___，编程人员使用它们来请求操作系统提供服务。

4. 4．所谓系统调用，就是用户在程序中调用__________所提供的一些子功能。

5. 5．按命令接口对作业控制方式的不同可将命令接口分为联机命令接口和____。

6. 6.把用户要求计算机完成的一个计算过程或者一次事务的处理过程称为一个????___ _。

7. 7.根据计算机系统的作业处理方式的不同，作业可以分为脱机作业和____两类。

8. 8.作业的输入、输出方式有联机I/O方式、脱机I/O和_____方式三种。

9. 9. SPOOL又称“_____“，他是英文Simultaneous Periphral Operations Online的首字 母缩写。

10. 10.各计算机系统提供一条_____作为调用操作系统功能服务的手段。

11. 11.UNIX系统的访管指令是_____；

12. 12. _____是操作系统为用户提供的各种操作命令，用户利用这些操作命令来组织作业的 工作流程和控制作业的运行。

13. 13.把用户要求计算机完成的一个计算过程或者一次事务的处理过程称为一个_____。

14. 14：在批处理系统中，通常把一大批作业按照某种原则一次通过输入设备自动输入到磁 盘的“输入#”中，这样就形成了一股“_____”。

15. 15._____就是用户在程序中能用访管指令去调用的由操作系统提供的子程序包。

解答:

1. 【答案】利用系统调用命令 【解析】系统调用命令是操作系统专门给编程人员提供的调用操作系统有关功能的 途径，一般在汇编语言和C语言中都提供了使用系统调用命令的方法。编程人员可以在这些语

言中利用系统调用命令动态请求和释放系统资源。

2. 【答案】系统调用 【解析】按用户界面的观点，操作系统是用户与计算机之间的接口。用户通过操作系统 提供的服务来有效地使用计算机。一般操作系统提供了两类接口为用户服务，一种是程序一 级的接口，即通过一组广义指令（或称系统调用）供用户程序和其他系统程序调用；另一种 是作业一级的接口，提供一组控制命令供用户去组织和控制自己的作业。

3. 答：程序接口

4. 答：操作系统

5. 答：脱机命令接口

6. 答案：作业链接

7. 答案：联机作业

8. 答案： SPOOLing

9. 答案：假脱机技术

10. 答案：

11. 答案：Trap

12. 答案：操作员接口（或称作业控制级接口）

13. 答案:作业

14. 答案:作业流

15. 答案:系统功能调用（简称系统调用）

二.简答题

1. 1. 什么是Spooling技术？他有什么用？你认为未来先进的个人计算机会把假脱机作为一 个关键特性吗？

2. 2.系统调用与一般过程调用有什么区别？

3. 3.简述操作系统为用户提供的接口？

4. 4．什么是作业？作业分为那几类？

5. 5.用户程序怎样调用操作系统功能？

6. 6.什么是系统调用？操作系统为什么要提供系统调用？

7. 7.系统调用的设计与实现必须解决哪些问题？

8. 8.系统调用的分类有哪些？

9. 9.系统调用的处理过程?

解答:

1. 答：假脱机（SPOOLing.）技术的全称是同时得外部设备联机操作，这种技术的基本思想 是用磁盘设备作为主机的直接输入输出设备，主机直接从磁盘上选取作业运行作业的执行结 果。

2. 答：（1）运行的状态不同 （2）进入的方式不同 （3）提供的方式不同 （4）调用的方式不同 （5）被调用代码位置不同

3. 答：（1）程序员接口：即用户在程序中请求操作系统的服务，称之为系统调用或操作系 统应用程序接口。 （2）操作员接口：用户通过对操作系统提供的操作控制命令输入、调试和执行程序。

4. 答：把用户要求计算机完成的一个计算过程或者一次事务的处理过程称为一个作业。 根据计算机系统的作业处理方式的不同，作业可以分为脱机作业和联机两类。

5. 答：就是用户在程序中能用访管指令去调用的由操作系统提供的子程序包。其中的每个 子程序完成一个特定的功能，称为一条系统调用命令。操作系统的基本服务是通过系统功能 调用实现的，系统功能调用提供运行程序和操作系统之间的接口。系统调用的实现取决于计

算机的结构，它是由特定的硬件指令实现多操作系统某一服务历程的调用。

6. 答：就是用户在程序中能用访管指令去调用的由操作系统提供的子程序包。 操作系统为用户提供系统调用的目的有两个方面： （1）为了方便用户 （2）出于安全和效率考虑。

7. 答：（1）编写系统调用处理程序 （2）设计一张系统调用入口地址表，每个入口地址都指向一个系统功能调用的处理程序

，有的系统还包含系统调用自带的参数 （3）陷入处理机制需开辟现场保护区，以保存发生系统调用时的处理器现场。

8. 答：设备管理器、文件管理器、进程控制类、进程通信类、存储管理类、信息维护。

9. 答：1）用户执行到系统调用指令 2）通过访管指令产生中断 3）系统进入访管中断处理 4）保护现场 5）执行相应例行程序。

三.应用题 解答:

第四章 进程管理与处理机调度

一.填空题

1. 1. 用户提交给系统的一个作业，原则上由 和 两部分组成 。

2. 2. 在具有SPOOLing功能的多道批处理系统中，通常把作业在系统中所经历的状态分为四 种，这四种状态依次是提交、 、 和完成。

3. 3. 作业调度程序实现了作业从 状态到 状态的转换。

4. 4. 当一个程序被分配了 和建立了一个 时，就可以说是创建了一个进 程。

5. 5. 进程控制块应包括标识信息、________、________和管理信息。

6. 6. 为保证原语操作的正确性，在现代计算机系统中，一般采取两种方法：一种是 ，即软件硬化的方法，将一个原语硬化为一条机器指令；另一种是采用 的 方法。

7. 7. 当一个进程完成了特定的任务后，系统收回这个进程所占的__________和取消该进程

的__________就撤消了该进程。

8. 8. 进程的切换是由 的变化引起的，而进程状态的变化又与出现的 有 关。

9. 9. 在单处理机系统中，如果系统中同时存在n个进程，则处于“运行”状态的进程最多 为1个，处于“就绪”状态的进程最多为 个，处于“阻塞”状态的进程最多为 个。

10. 10. 作业调度分配的是一台 处理机，进程调度为进程分配的是 处理 机。

11. 11. 引入中级调度的主要目的是为了起到平滑和调整系统负荷、提高 的利用率 和系统吞吐量的作用，它实际上就是存储器管理种的 功能。

12. 12. 进程调度方式有两种：第一种方式是 ；第二种方式是 。

13. 13. 对PCB的组织通常有线性表、 和 三种方式。

14. 14. 优先级调度算法又可分为 算法和 算法两种。

15. 15. 在引入线程的操作系统中，__________ 是作为独立分配资源的单位，而__________ _____是被独立调度和分派处理机的基本单位。

16. 16. 根据线程的切换是否依赖于内核把线程分成 ________ 、________和混合式线程三 类。

解答: 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16.

二.简答题

1. 1. 为什么要引入进程？进程与程序有什么区别？

2. 2. 画出作业和进程状态转换图。

3. 3. 什么是“可再入”程序？

4. 4. 为什么要设置进程队列？

5. 5. 什么是处理机三级调度?处理机三级调度分别在什么情况下发生?各级调度分别完成什 么工作?

6. 6. 阐述作业调度的职责。常用的作业调度算法有哪些？

7. 7. 选择作业调度算法有哪些准则？

8. 8. 假定有一个支持实时、分时和批处理的操作系统，对该系统应如何设计进程调度策略 ？

9. 9. 非抢占方式和可抢占方式进程调度的区别是什么？

10. 10. 进程调度中“可抢占”和“非抢占”两种方式，哪一种系统的开销更大？为什么

11. 11. 常用的进程调度算法有哪些？选择进程调度算法有哪些准则？

12. 12. 多个就绪队列的分级调度算法有什么优点？

13. 13. 在分时系统中采用时间片轮转调度算法有什么优越性？

14. 14. 在操作系统中引入线程概念的主要目的是什么？

15. 15. 试述线程的特点及其与进程的主要异同点。 解答: 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11.

12. 13. 14. 15.

三.应用题

1. 1. 有一个具有两道作业的批处理系统，作业调度采用短作业优先的调度算法，进程调度 采用以优先数为基础的抢占式调度算法，在下表所示的作业序列，作业优先数即为进程优先 数，优先数越小优先级越高。

①列出所有作业进入内存时间及结束时间。 ②计算平均周转时间。

2. 2. 设某系统的状态除了三个基本状态外，还增加了创建状态、完成状态和延迟状态。试 画出该系统的进程状态变迁图，并表明状态变迁可能的原因。 3. 3. 有一个四道作业的操作系统，若在一段时间内先后到达6个作业，它们的提交和估

计运行时间由下表给出：系统采用SJF调度算法，作业被调度进入系统后中途不会退出，但作

业运行时可被更短作业抢占。

①分别给出6个作业的执行时间序列、即开始执行时间、作业完成时间、作业周转时间 。 ②计算平均作业周转时间。

4. 4. 给定一组作业J1，J2?Jn，它们的运行时间分别为T1，T2，?，Tn，假定这些作业是 同时到达，并且将在一台CPU上按单道方式运行。 ①试证明：若按最短作业优先调度算法运行这些作业，则平均周转时间最短； ②采用最短作业优先调度算法会产生什么问题？

5. 5. 设有进程A、B、C、D依次进入就绪队列（相隔一个时间单位），它们的优先级如下表 所示：

试问采用“先来先服务”、“静态优先数法”调度算法（注：优先数大的优先级高）， 选中进程的执行次序。

解答: 1. 2. 3. 4. 5.

第五章 并发进程及死锁问题

一.填空题

1. 1．死锁产生的原因是__________和进程推进路径非法。

2. 2．产生死锁的四个必要条件是互斥条件、_________、占有且等待资源条件、循环等待 条件。

3. 3．产生死锁的四个必要条件是__________、非抢占条件、占有且等待资源条件、循环等 待条件。

4. 4．产生死锁的四个必要条件是互斥条件、非抢占条件__________、循环等待条件。

5. 5．产生死锁的四个必要条件是互斥条件、非抢占条件、占有且等待资源条件、________ __。

6. 6.死锁是指在系统中的多个__________无限期地等待永远不会发生的条件。

7. 7．对待死锁，一般应考虑死锁的预防、避免、检测和解除四个问题。典型的银行家算法 是属于死锁的____。

8. 8．对待死锁，一般应考虑死锁的预防、避免、检测和解除四个问题。破坏环路等待条件 是属于死锁的____。

9. 9．对待死锁，一般应考虑死锁的预防、避免、检测和解除四个问题。剥夺资源是死锁的 ____的基本方法。

10. 10.当检测到有死锁存在时，一般采用两种方式来解除，分别是____和剥夺法。

11. 11. 如果要求所有进程一次性申请它所需要的全部资源。若系统有足够的资源分配给进 程，便一次把所有的资源分配给该进程。但在分配时只要有一种资源要求不能满足，则资源 全不分配，进程等待。这种死锁预防方法破坏了死锁产生必要条件中的____条件。

12. 12.如果操作系统能够保证所有进程在有限时间内得到需要的全部资源，则成系统处于__ ________。

13. 13.死锁产生的原因是系统资源不足和__________。

14. 14.当检测到有死锁存在时，一般采用两种方式来解除，分别是删除法和____。

15. 15.若系统中存在一组进程，它们中的每一个进程都占用了某些资源而又都在等待其中另 一个进程所占用的资源，这种等待永远不呢个结束，说明系统出现了____。

16. 16．利用信号量实现进程的 _____ ①，应为临界区设置一个信号量 mutex。

17. 17. 利用信号量实现进程的互斥，应为临界区设置一个信号量 mutex。其初值为1，表示

该资源尚未使用，临界区应置于_____和_____原语之间。

18. 18.消息传递系统分为两种：__________和间接通信。

19. 19.当一个进程独占处理器顺序执行时，具有两个特性：__________性和可再现性。

20. 20.高级进程通信方式可分为3类：共享存储器系统、消息传递系统和__________。

21. 21.高级进程通信方式可分为3类：共享存储器系统、__________和管道通信系统。

22. 22.高级进程通信方式可分为3类：__________、消息传递系统和管道通信系统。

23. 23.进程的“同步”和“互斥”反映了进程间直接制约和__________的关系。

24. 24.在消息传递系统中，进程之间的数据交换以__________为单位，程序员直接利用操作 系统提供的一组高级通信原语来实现进程间的消息通信。

25. 25．进程调度负责__________的分配工作。

26. 26. 在操作系统中，信号量是表示资源的物理实体，它是一个与队列有关的整型变量， 其值仅能由__________原语来改变。

27. 27.信号量机制是由__________和__________组成。

28. 28.在多道程序系统中，由于资源共享与进程合作使得并发执行的进程之间可能无关，也 可能是有交往的，从而产生相互制约关系，并发进程之间的竞争关系体现为__________。

29. 29.在多道程序系统中，由于资源共享与进程合作使得并发执行的进程之间可能无关，也 可能是有交往的，从而产生相互制约关系，并发进程之间的协作关系体现为__________。

30. 30.系统中并发进程的工作正确与否不仅取决与它的程序编制的正确性，而且与它在执行 过程中能否与其他相关进程__________有关。

解答:

1. 【答案】系统资源不足、 【解析】死锁产生的根本原因是系统的资源不足而引发了并发进程之间的资源竞争。由

于资源总是有限的，我们不可能为所有要求资源的进程无限地提供资源。而另一个原因是操 作系统应用的动态分配系统各种资源的策略不当，造成并发进程联合推进的路径进入进程相 互封锁的危险区。所以，采用适当的资源分配算法，来达到消除死锁的目的是操作系统主要 研究的课题之一。

2. 答案：非抢占条件

3. 答案：互斥条件

4. 答案：占有且等待资源条件

5. 【答案】循环等待条件 【解析】 互斥条件：进程对它所需的资源进行排它性控制，即在一段时间内，某资源为一进 程所独占。 非抢占条件：进程所获得的资源在未使用完毕之前，不能被其它进程强行夺走，即 只能由获得资源的进程自己释放。 占有且等待资源条件：进程每次申请它所需的一部分资源，在等待新资源的同时， 继续占有已分配到的资源， 循环等待条件：存在一进程循环链，链中每一个进程已获得的资源同时被下一个进程所 请求。

6. 答：进程

7. 答：避免

8. 答：预防

9. 答：解除

10. 答：删除法

11. 答：部分分配

12. 答：安全状态

13. 【答案】进程推进路径非法、

14. 答：剥夺法

15. 答：死锁 16.

17. 【答案】P（mutex），V（mutex）

【解析】一次仅允许一个进程使用的资源称为临界资源，对临界资源实施操作的那段程 序称为临界区。对于具有临界区问题的并发进程，它们之间必须互斥，以保证不同时进入临 界区。利用信号量和P-V原语能方便地解决临界区问题。mutex为互斥公用信号量，初值为1，

临界区的代码被置于P（mutex）、V（mutex）原语之间时，任何欲进入临界区的进程，必须 在公用信号量mutex上执行P原语，在完成对临界资源的访问后再执行V原语。由于mutex初值

为1，当第一个进程执行P原语后减为0，表示临界资源空闲，可分配给该进程使之进入临界区 ，在第一个进程没有退出临界区之前，若此时第二个进程想进入临界区，也应先执行P原语。 而结果是mutex变为负值，就意味着临界资源已被占用，因此，第二个进程被阻塞。直到第一

个进程执行V原语，释放该临界资源mutex到0后，方可唤醒第二个进程，使之进入临界区，待

它完成对临界资源的访问后，又执行V原语，使mutex恢复到初始值。

18. 答:直接通信 19.

20. 答：管道通信系统

21. 答：消息传递系统

22. 答：共享存储器系统

23. 【答案】间接制约

24. 答：消息

25. 答：处理机

26. 【答案】P-V 【解析】信号量的概念和 P-V原语是荷兰科学家 E．W．Dijkstra提出来的。信号量

是一个特殊的整型量，它与一个初始状态为空的队列相联系。信号量代表了资源的实体，操 作系统利用它的状态对并发进程共享资源进行管理。信号量的值只能由P-V原语来改变。 27.

28. 答：进程互斥

29. 答：进程同步 30.

二.简答题

1. 1．产生死锁的原因是什么？

2. 2．死锁发生的必要条件有哪些？

3. 3.何谓系统的安全状态？试说明银行家算法避免死锁的原理。

4. 4．阐述按序分配资源法是如何进行死锁预防的。

5. 5.银行家算法是怎样避免死锁的？

6. 6. 按序分配是防止死锁的一种策略。什么是按序分配？为什么按序分配可以防止死锁？

7. 7．防止死锁的分配策略中,它们各自存在的缺点。

8. 8.如何检测死锁？

9. 9．阐述预先静态分配法是如何进行死锁预防的。

10. 10．进程通信方式有两种即：直接通信、间接通信，给出各自使用的原语形式。

11. 11.操作系统中为什么要引入进程的概念？为了实现并发进程间的合作和协调工作，以及 保证系统的安全，操作系统在进程管理方面应做哪些工作？

12. 12.进程间同步和互斥的含义是什么?

13. 13. 简述信号量S的物理含义：

14. 14．PV操作本身的如何定义的？

15. 6.解决临界段问题的原则是什么？

16. 16.什么是临界区？什么是相关临界区？对相关临界区的管理有哪些要求？

17. 17.什么是进程的间接制约关系？间接制约要求进程如何执行？

18. 18.说明下列活动是属于哪些制约关系？

19. 19. 一个快餐店有四类雇员：1）领班，他们接受顾客点的菜单；2)厨师，准备饭菜；3 ）打包工，将饭菜装在袋子里；4）收银元，将食品袋交给顾客并收钱，每个雇员都可以看作

一个进行通信的顺序进程，他们采用的进程间通信方式是什么？

解答:

1. 【解析】 （1）系统资源不足； （2）进程推进顺序不合适。 在早期的系统中，由于系统规模较小，结构简单，以及资源分配大多采用静态分配 法，使得操作系统死销问题的严重性未能充分暴露出来。但今天由于多道程序系统，以至于 数据库系统的出现，系统中的共享性和并行性的增加，软件系统变得日益庞大和复杂等原因 ，使得系统出现死锁现象的可能性大大增加。

2. 【解析】 发生死锁的必要条件有四点：互斥条件、不可抢占条件、部分分配条件和循环等待 条件。 （1）互斥条件：系统中存在一个资源一次只能被一个进程所使用； （2）非抢占条件：系统中存在一个资源仅能被占有它的进程所释放，而不能被别的

进程强行抢占； （3）占有且等待条件：系统中存在一个进程已占有了分给它的资源，但仍然等待其

它资源； （4）循环等待条件：在系统中存在一个由若干进程形成的环形请求链，其中的每一个进

程均占有若干种资源中的某一种，同时每一个进程还要求（链上）下一个进程所占有的资源。 3.

4. 【解析】 Havender提出的第二个策略是有序资源使用法，这是针对循环等待条件的，即系统

设计者把系统中所有资源类都分给一个唯一的序号，如输入机=1，打印机=2，穿孔输出机=3 ，磁带机=4，等等。并且要求每个过程均应严格按递增的次序请求资源。亦即，只要进程提 出请求资源，那么以后它只能请求排列在其后面的那些资源，而不能再要求序号低的那些资 源。不难看出，由于对资源的请求作出了这种限制，在系统中就不可能形成几个进程对资源 的环形请求链，破坏了循环等待条件。

这种方法由于不是采用预先静态分配方法，而是基本上基于动态分配方法，所以资源利 用率较前一方法提高了，特别是小心地安排资源序号，把一些各作业经常用到的、比较 普通

的资源安排成低序号，把一些比较贵重或稀少的资源安排成高序号，便可能使最有价值的资 源的利用率大为提高。因为高序号的资源往往等到进程真正需要时，才提出请求分配给进程 。而低序号的资源，在进程即使暂不需要的情况下，但是进程需要使用高序号资源，所以在 进程请求分配高序号资源时，不得不提前同时请求以后需要的低序号资源，从而造成资源空闲等待的浪费现象。

5. 答：P132

6. 答：按序分配是把系统中所有资源排一个顺序，每一个资源给一个确定的编号，规定任 何一个进程申请两个以上资源时，总是先申请编号小的资源，再申请编号大的资源。 按序分配可以防止死锁，证明如下： 假设存在一组循环等待的进程记为(P0，P1，?，Pn)，其中Pi拥有资源ri，编号为F(ri) ；根据按序分配原则，有F(r0)＜F(r1)＜?＜F(rn)，因存在循环等待，所以Pn申请的下一个 资源就为P0所占的rn，，若Pn能正常运行，必须依据资源顺序分配原则，即下次申请资源标

号应比其所占有的资源标号大，于是有F(rn)＜F(r0)，这与前面的不等式有矛盾，故不能存在。

7. 【解析】 在防止死锁的分配策略中，有的只适用于对某些资源的分配，有的则会影响资源的使用 效率。例如，剥夺式分配目前只适合于对处理器和主存资源的分配。静态分配策略把资源预 先分配给进程，而这些进程占有了资源但可能在一段时间里并不使用它，这时其它想使用这 些资源的进程却又得不到而等待，降低了资源的利用率。采用按序分配时各进程要求使用资 源的次序往往不能与系统安排的次序一致，但申请资源时必须按编号的次序来申请，可能出 现先申请到的资源在很长一段时间里闲置不用，也降低了资源的利用率。

8. （P140）

9. 【解析】 Havender（1968）提出的第一个策略就是预先静态分配法，这是针对部分分配条件 的策略。要求每一个进程在开始执行前就申请它所需要的全部资源，仅当系统能满足进程的 资源要求且把资源分配给进程后，该进程才能开始执行。 这个策略毫无疑问能够防止死锁的发生，因为这样做破坏了部分分配条件，但是它 导致了严重的资源浪费。例如一个进程可能在运行到最后时需要一台打印机打印结果数据， 但必须在进程运行前就把打印机分配给它，而且在进程运行的过程中并不使用打印机。

10. 【解析】 直接通信： 这种通信是固定在一对进程之间。例如，进程A把信件只发送给进程B,而进程B也只

接收进程A的信件。那么，“send”和“receive”两条原语的形式如下：

send(B，M） 把信件M发送给进程B receive（A，X) 接收来自进程 A的信件且存入 X中 进程A和进程B通过“send”和“receive”操作而自动建立了一种联结。 间接通信： 这种通信是以信箱为媒体来实现通信的，只要接收信件的进程设立一个信箱，那么 ，若干个进程都可向同一个进程发送信件。利用信箱通信时，“send”，“receive”原语中 应给出信箱名，即： send（N，M） 把信件M送入信箱N中 receive(N，X) 从信箱N中取出一封信存入X 11.

12. 答：进程互斥：是指若干进程都要使用同一个资源时，任何时刻最多允许一个进程使用 其他要使用该资源的进程必须等待，知道占有资源的进程释放该资源。 进程同步：是完成统一任务的伙伴进程间因需要在某些位置上协调他们的工作或相互交 换信息所产生的进程之间的直接制约关系。

13. 【解析】 S＞0时，S表示可使用的资源数；或表示可使用资源的进程数。 S＝0时，表示无资源可供使用；或表示不允许进程再进入临界区。 S＜0时，|S|表示等待使用资源的进程个数；或表示等待进入临界区的进程个数。 当S＞0时，调用P（S）的进程不会等待；调用V（S）后使可用资源数加1或使可用资

源的进程数加1。 当S<= 0时，调用P（S）的进程必须等待；调用V（S）后将释放一个等待使用资源者

或释放一个等待进入临界区者。

14. 【解析】 PV操作是对信号量的操作，而信号量可以简单地理解为只允许PV操作对其操作的整

型变量。它们的定义如下，其中S是信号量。 P（S）：将S信号量值减1，若结果小于0，则调用P（S）的进程被置成等待状态；否

则该进程继续执行。 V（S）：将信号量S值加 1，若结果不大干0，则释放一个等待信号量S的进程，使其

变为就绪状态。 P操作和V操作可表示成如下两个过程： Procedure P（Var S：Semaphore）； begin S:=S-1； if S＜0 then W（S） end;{P} Procedure V（Var S：Semaphore）； beam S:=S＋1 if S<=0 then R（S） end ;{V}

其中W（S）表示将调用过程的进程置成等待状态；R（S）表示释放一个等待信号量S的进

程。信号量的值应在初始化时确定。

15. 【解析】 对若干并发进程共享某一变量的相关临界区的管理有三点要求： （1）一次至多一个进程能够进入临界区，当有进程处于临界区时，其它要进入临界区的

进程必须等待。 （2）处于临界区中的进程必须在有限时间内退出。 （3）当有进程退出临界区时，应选择一个等待进入临界区的进程使其进入临界区。 16. 17.

18. 1）若干同学去图书馆借书 进程互斥 2）两队进行篮球比赛 进程互斥 3）流水线生产中的各道工序 进程同步 4）商品生产和社会消费 进程同步

19. 答：通信方式为消息传递。

三.应用题

1. 1．试描述避免死锁的银行家算法，若系统运行中出现下述资源分配情况 进程 ALLOCATION NEED AVAILABLE A B C D A B C D A B C D P0 0 0 3 2 0 0 1 2 1 6 2 2 P1 1 0 0 0 1 7 5 0 P2 1 3 5 4 2 3 5 6 P3 0 3 3 2 0 6 5 2 P4 0 0 1 4 0 6 5 6

该系统是否安全？如果进程P2此时提出资源申请（1，2，2，2），系统能否将资源分配 给它？为什么？

2. 2.P(130)设系统有打印机、读卡机各一台，被进程P和Q共享。两个进程并发执行，按以 下顺序请求和释放资源： 进程P 进程Q A1：请求读卡机 B1：请求打印机 A2：请求打印机 B2：请求读卡机 A3：释放读卡机 B3：释放读卡机 A4：释放打印机 B4：释放打印机 进程P和Q的执行存在下列可能的顺序： （1） A1,A2,A3,A4,B1,B2,B3,B4 （2） B1,B2,B3,B4 ,A1,A2,A3,A4

（3） A1,A2, B1,B2, A3,A4, B3,B4 （4） A1, B1, A2, B2, A3, B3, A4,B4

上面列出的哪几种顺序不会产生死锁？为什么？

3. 3.（P132）设系统有某类资源10个，有3个并发进程A、B、C对该类资源的最大需求量分

别为：4、6、8.显然总的资源能够满足每个进程对资源的最大需求，但系统总的资源数少于3

个进程对资源需求的总和。假定A、B、C已分别占用系统资源数为2、3、3，如表：5.1，试按

银行家算法说明系统分配资源的情况。 表5.1 进程名 已分配资源数 尚需申请资源数 最大资源需求数 A 2 2 4 B 3 3 6 C 3 5 8

4. 4.某系统中有10台打印机，有3个进程P1、P2、P3分别需要8台、7台和4台。若P1、P2、P

3已经申请到4台、2台和2台。试问：按银行家算法能安全分配吗？试说明分配过程.

5. 5.一台计算机有8台磁带机。它们由N个进程竞争使用，每个进程可能需要3台磁带机。请

问N为多少时，系统没有死锁危险，并说明原因。

6. 6.有三个进程P1，P2和P3并发工作。进程P1需用资源S3和S1；进程P2需用资源S1和S2；

进程P3需用资源S2和S3。回答： (1)若对资源分配不加限制，会发生什么情况?为什么? (2)为保证进程正确工作，应采用怎样的资源分配策略?为什么?

7. 7、有一个仓库，可以存放A和B两种产品，但要求： (1)、每次只能存放一种产品（A或B）; (2)、-N < A产品数量 - B产品数量 < M。 其中，N和M是正整数。试用P、V操作描述产品A与产品B的入库过程。

8. 8、用P、V操作实现下述问题的解。桌上有一个盘子，可以存放一个水果。父亲总是放

苹

果到盘子中，而母亲总是放香蕉到盘子中；一个儿子专等吃盘子中的香蕉，而一个女儿专等 吃盘中的苹果。

9. 9、设公共汽车上，司机和售票员的活动分别是： 司机的活动：启动车辆；正常行车；到站停车。 售票员的活动：关车门；售票；开车门。 在汽车不断地到站、停站、行驶过程中，这两个活动有什么同步关系？用信号量和P、V

操作实现它们的同步。

10. 10.假定一个阅览室最多可以容纳100人，读者进入和离开阅览室都必须在阅览室门口的 一个登记表上标志（进入时登记，离开时去掉登记项）而且每次只允许一人登记或者去掉登 记，问： 1)应编写几个进程完成这项工作，程序的主要动作是些什么？应该设置几个进程？进程 和程序间的关系如何？ 2)用P,V操作写出这些进程的同步通信关系

11. 11、某寺庙，有小、老和尚若干，有一水缸，有小和尚提水入缸供老和尚饮用。水缸可 容10桶水，水取自同一井中。水井径窄，每次只能容一个桶取水。水桶总数为3个。每次入、

取缸水仅为1桶，且不可同时进行。试给出取水、入水的算法描述。

12. 12.如果一个生产者和一个消费者他们共享的缓冲器(B)容量为可以存放n件物品，如何用 PV操作来实现他们正确地同步。

13. 13．爱睡觉的理发师问题，一个理发店有两间相连的屋子，一间是私室，里面有一把理 发椅，另一个是等候室，有一个滑动门和N把椅子。理发师忙的时候，通向私室的门被关闭，

新来的顾客找一把空椅子坐下，如果椅子都被占用了，则顾客只好离去，如果没有顾客，则 理发师在理发椅上睡觉。并打开通向私室的门。理发师睡觉时，顾客可以叫醒他理发，请编 写理发师和顾客的程序，正确实现同步和互斥问题！

14. 14.某银行有人民币储蓄业务，由n个柜员负责，每个顾客进入银行后，先取一个号，并 且 等着叫号，当一个柜员人员空闲下来，就叫上一个号，使用P,V操作正确编写柜台人员和 顾客进程的程序！

15. 15.在一间酒吧里有三个音乐爱好者队列，第一列音乐爱好者只有随身听，第二列只有音 乐磁带，第三列只有电池，而要听音乐就必须有随身听，音乐磁带和电池这三中物品酒吧老 板一次出售这三种物品中的任意两种，当一名音乐爱好者得到这三种物品并听完乐曲后，酒 吧老板才能再一次出售这三种物品中任意两种，于是第二名音乐爱好者得到这三种物品。并 开始听乐曲，全部买卖九这样进行下去。使用P,V操作正确解决这一买卖。

16. 16．今有3个并发进程R、M、P，它们共享一个缓冲器B。进程R负责向B中输入数据；进程

R每输入一数据，进程M对其进行加工；进程M加工完成后，进程P负责打印输出。缓冲器B中

每次只能存放一个数据，数据一旦被打印，进程R又可存放下一个数据，??。它们之间的关

系如图所示。 用PV操作机制进行控制，写出三个进程的工作流程。

17. 17．在某展示厅设置一个自动计数系统，以计数器count表示在场的人数，count是动态 变化的，若有一个人进入展示厅进程pin对计数器count加1，当有一个人退出展示厅时，进程

pout实现计数器减1由于进、出所以展示厅的人是随机的，用P-V操作实现。（并发进程之间

的互斥问题）

18. 18．现有四个进程：R1，R2，W1和W2，它们共享可以存放一个数的缓冲区B。进程R1每次

把从键盘上读入的一个数存到缓冲区B中，供进程W1打印输出；进程R2每次把从磁盘上读一个

数存放到缓冲区B中，供进程W2打印输出。怎样用P、V操作协调四个并发进程的工作。

19. 19.有一个售票厅只能容纳200人，当少于200人时，可以进入；否则需要在外等候；若将

每一个购票者作为一个进程，请用P、V操作描写其同步.

20. 20．有K个进程共享一个临界区，对于下述情况，请说明信号量值的初值，含义，并用P,

V操作写出相关的互斥算法。

1） 一次只允许一个进程进入临界区 2） 一次只允许m个进程进入临界区

21. 21．在生产者和消费者问题中，如果对调生产者（或消费者）进程中的两个P操作和两个 V操作的次序，会发生什么情况？请说明！

22. 22.用PV操作解决读者写者问题的正确程序如下： begin S, Sr: Semaphore; rc: integer; S:=1; Sr:=1; rc:=0; cobegin PROCESS Reader i ( i=1,2…) begin P(Sr) rc:=rc+1; if rc=1 then P(S); V(Sr); read file; P(Sr); rc:=rc-1 if rc=0 thenV(S); V(Sr); end ; PROCESS Writer j (j=1,2…) begin P(S); Write file; V(S) end; coend ; end; 请回答：（1）信号量 Sr的作用；（2）程序中什么语句用于读写互斥，写写互斥；（3 ）若规定仅允许5个进程同时读怎样修改程序？

23. 23．（8分）某系统中有10台打印机，有三个进程P1，P2，P3分别需要8台，7台和4台。

若P1，P2，P3已申请到4台，2台和2台。试问：按银行家算法能安全分配吗？请说明分配过程 。

解答: 1. 答案：

进程 Allocation Need Availabe Avelable+ Allocation No A B C D A B C D A B C D A B C D P0 0 0 3 2 0 0 1 2 1 6 2 2 1 6 5 4 1 P1 1 0 0 0 1 7 5 0 1 9 8 6 2 9 8 6 3 P2 1 3 5 4 2 3 5 6 2 9 8 6 3 12 13 10 4 P3 0 3 3 2 0 6 5 2 1 6 5 4 1 9 8 6 2 P4 0 0 1 4 0 6 5 6 3 12 13 10 3 12 14 14 5 可以找到一个安全序列{P0、P3、P1、P2、P4}，系统是安全的。 进程P2此时提出资源申请（1，2，2，2）, 如系统实施此次分配使系统可用资源减到（0

，4，0，0），再也无法满足各进程对资源的需求，系统进入一个不安全状态，系统不能将资 源分配给进程P2。 进程 Allocation Need Availabe Avelable+ Allocation No A B C D A B C D A B C D A B C D P0 0 0 3 2 0 0 1 2 0 4 0 0 P1 1 0 0 0 1 7 5 0 P2 2 5 7 6 1 1 3 4 P3 0 3 3 2 0 6 5 2 P4 0 0 1 4 0 6 5 6

2. 答案：前三种不会产生死锁，第四种进程推进顺序产生了死锁。

3. 答案分析：现在系统还剩资源2个。按照银行算法执行的话，不管是进程B还是进程C向系

统提出1个资源的请求，系统都不能满足她们的要求，因为满足了她们的要求，系统中的进程

没有一个能达到资源最大需求量，从而产生死锁。只有进程A对资源的请求可以满足。因为系

统剩余资源数能够使A达到最大资源需求量，从而A可以运行结束，并释放他所占有的全部资

源（4个），然后系统又可以满足B达到最大资源需求量而运行结束并释放他所占有的全部资

源，最后进程C也可以达到最大资源需求量而运行结束。 银行家算法能保证在任何时刻至少有一个进程可以得到所需要的全部资源而执

行结束，执行结束后，归还的资源加入到系统的剩余资源中，这些资源又至少可以满足另一 个进程的最大需求?。于是保证了所有进程都能在有限时间内得到需要的全部资源，使系统 一直出于安全状态。这样的资源分配当然避免了死锁。 4. 5.

6. 答.(1)可能会发生死锁 (2分) 例如：进程P1，P2和P3分别获得资源S3，S1和S2后再继续申请资源时都要等

待(2分)，这是循环等待。 (或进程在等待新源时均不释放已占资源)

(2)可有几种答案： A.采用静态分配 (2分) 由于执行前已获得所需的全部资源，故不会出现占有资源又等待别的资源

的现象(或不会出现循环等待资源现象)。 (2分) 或B.采用按序分配 (2分) 不会出现循环等待资源现象。(2分) 或C.采用银行家算法 (2分) 因为在分配时，保证了系统处于安全状态。 (2分)

7. 答：设置两个信号量来控制 A、B产品的存放数量，sa表示当前 允许A产品比B产品

多入库的数量，即在当前库存量和B产品不入库的情况下，还可以允 许sa个A产品入库;sb 表示当前允许B产品比A产品多入库的数量，即在当前库存量和 A产品不入库的情况下，还

可以允许sb个B产品入库。初始时，sa为M一1，sb为N一1，当往库中存放入一个A产品时，则

允许存入B产品的数量也增加1;当往库中存放入一个B产品时，则允许存入A产品的数量也增加

1。 产品 A、B的入库过程描述如下： int mutex=1; /*互斥信号量*／ int sa=M-1; int sb=N-1; main( ) { while(1) {

取一个产品;

if(取的是A产品) {

p(sa); p(mutex); 将产品入库; v(mutex);

v(sb)： }

else /*取的产品是B*／ {

p(sb);

p(mutex); 将产品入库; v(mutex); v(pa); } } }

8. 答：这个问题实际上是两个生产者和两个消费者被连结到仅能放一个产品的缓冲器 上。生产者各自生产不同的产品，但就其本质而言，他们是同一类生产者。而消费者 则各自取需要的产品消费，他们的消费方式不同。实现爸爸、妈妈、儿子和女儿正确 同步工作的程序如下： var plate : integer;

sp:semaphore; /* 盘子里可以放几个水果 */ sg1:semaphore; /* 盘子里有香蕉 */ sg2:semaphore; /* 盘子里有苹果 */ sp := 1; /* 盘子里允许放入一个水果*/ sg1:= 0; /* 盘子里没有香蕉 */ sg2:= 0; /* 盘子里没有苹果*/ cobegin

process father begin

L1: 削一个苹果; P(sp);

把苹果放入plate; V(sg2);

goto L1; end; process mother begin

L2: 剥一个香蕉; P(sp);

把桔子放入plate; V(sg1);

goto L2; end; process son begin L3: P(sg1);

从plate 中取香蕉; V(sp); 吃桔子; goto L3; end; process daughter begin L4: P(sg2); 从plate 中取苹果;

9. 答：定义两个信号量，一个信号量start表示是否允许司机启动车辆，另一个信号量open 表示是否允许售票员开车门。初始状态是车停在始发站，车门开着，等待乘客上车。因此， 两个信号量的初值都是0。 semaphore start=0; semaphore open=0;

//司机的活动: P1: do{ P(start); 启动车辆; 正常行车; 到站停车; V(open); }while (1); //售票员的活动: P2: do{ 关车门; V(start); 售票; P(open); 开车门; 上下乘客; }while (1)

10. 答：编写两个进程，一个处理读者进入，一个处理读者离开，进程是程序的动态执行 设置信号量 full 为初值为 0， 空的信号量 empty 初值为100, 互斥信号量 mutex 初 值 为1 进入 离开 P(empty) P(full) P(mutex) P(mutex) 登记 取消登记 V(mutex) V(mutex) V(full) V(empty) 进入 离开 11.

12. 【解析】 设信号量empty（表示缓冲器中可存放多少件物品）的初值为n, 信号量full（表示 缓冲器中存有几件物品）的初值为0。当缓冲器中没有放满n件物品时，生产者调用P（empty ）都不会成为等待状态而可把物品存入缓冲器。但当缓冲器中已经有n件物品，生产者想再存

入一件物品将被拒绝。每存入一件物品后，由于调用V（full），故empty的值表示缓冲器中 可用的物品数，只要full>0，消费者调用P（full）后总可去取物品。每取走一件物品后，由 于调用V（empty），便增加了一个可用来存放物品的位置。用指针k和t分别指示生产者往缓

冲器存物品和消费者从缓冲器中取物品的相对位置，它们的初值为0，那么，一个生产者和一

个消费者共用容量为n的缓冲器时，可如下进行同步工作： 设信号量empty,full,初值为empty=n,full=0；整型变量k,t,初值k=t=0。 生产者进程： begin L1：produce a product; P（empty）； B［k］:=product; k：=（k十1）mod n; V（full）; go to L1 end; 消费者进程： begin L2：P（full）； take a product from B［t］； t：＝（t＋1）mod n； V（empty）； consume； go to L2 end

13. 答：解：VAR: S1,S2 ：Semaphore;{初值为0,实现理发师与顾客的同步} Mutex：Semaphore：{初值为1,实现对waiting的互斥} waiting：INTEGER:{初值为0,等待的顾客数} 理发师进程 REPEAT P(S1) {若无顾客，则睡觉 } P(mutex) Waiting:=waiting-1

V(S2); (唤醒一个等待的客户) V(mutex) 理发 Until FALSE 顾客进程 P(mutex)

IF(waiting

Waiting：=-waiting+1 ;(等待顾客数加1) V(mutex); V(S1) {通知理发师}

P(S2) {若无理发师，挂起} 坐下理发

END ELSE V(mutex)

14. 解; 取号的互斥信号量 mutex,叫号的互斥信号量mutex1 柜台人员和顾客进程的同步信号量为 S1,S2, 初值分别为n,0 柜台人员进程： P(S2) (无顾客则等待) P(mutex1) 叫号 V(mutex1) 服务 V(S1) 顾客进程 P(mutex) 取号 V(mutex)

P(S1) 享受服务 V(S2)

15. 解：买方有三个进程，卖方有1个进程 卖方，和买方的同步信号量 S1,S2 ,初值为0,1. 听音乐时的互斥信号量;mutex 卖方进程 P(S1) (没有音乐爱好者，等待) 卖物品 P(mutex)

放音乐 V(mutex)

V(S2) 买方进程 P(S2) 买物品 V(S1) {老板可以卖东西}

16. 【参考答案】 设信号量e,f1,f2:semaphore; 初值 e=1;f1=f2=0; Cobegin Process R Begin L1:P(e); 生产一数据，放入缓冲区B； V(f1); Goto L1; End; Process M Begin L2:P(f1); 加工缓冲区B中数据； V(f2); Goto L2; End; Process P Begin

L3:P(f2);

打印缓冲区B中数据； V(e); Goto L3; End; Coend

17. 解：定义信号量：S：表示是否有进程进入临界区，初值为1.（表示没有进程进入临界区 ） begin count: Integer; S: semaphore; count:=0; S:=1; cobegin process Pin R1: Integer; begin P (S); R1:=count; R1:=R1+1; count:=R1; V(S); end; Process Pout R2: Integer; begin P (S); R2:=count; R2:=R2-1; count:=R2; V (S); end; count; end;

18. 【解析】 设信号量e,f1,f2; 其初值分别为 e=1,f1=0,f2=0 R1： R2： L: P(e) 从键盘上读入 的一个数存到缓冲区B中 V(f1) Goto L L: P(e) 从键盘上读入的一个数存到缓冲区B中 V(f2) Goto L W1： W2： P(f1) 将缓冲区B中的数据打印输出 V(e) Goto L L:

L:

19.

P(f2) V(e) goto L

将缓冲区B中的数据打印输出

20. 答：1)设置互斥信号量mutex，初值为1 P(mutex) Enter_region V(mutex)

2)设置同步信号量mutex,初值为m; P(mutex) Enter_region V(mutex)

21. 答：对调P操作, 会发生死锁 因为P(empty)在 p(mutex)和 v(mutex)内部，也就是临界 区中，当 empty≤0,时，P(empty)在临界区中进入到了休眠状态。那么就别的进程都进 入 不到临界区中，进入死锁状态。而两个V操作无关紧要 22. 23.

第六章 存储管理

一.填空题

1. 1. 计算机系统中的存储器可以分成两大类：________和_________，前者可以被处理器 直接访问，而后者不能被处理器直接访问。

2. 2. 主存储器的空间分成两部分：_ _______和___________,前者用来存放操作系统与硬 件的接口、操作系统的管理信息和程序、标准子程序等，后者用来存放用户的程序和数据。

3. 3. 主存储器是以字节为编址单位的，假定主存储器的容量为ｎ，其地址编号为０，ｌ， ２?，ｎ－ｌ，这些地址称为主存储器的___________；而用户程序使用的是一组从0开始的

地址，称为______ __。

4. 4. 用户程序中使用的是 地址，而处理器执行程序时要按 地址访问主存 。

5. 5. 地址重定位是指把用户程序中的逻辑地址转换成主存的物理地址；地址重定位的方式 包括____ __和__ ___两种。

6. 6. 采用可变分区方式管理主存时，主存分配表可用两张表格组成，一张是 ，另一张是 。

7. 7. 页式存储管理分配内存空间是以_______为单位的，其大小是固定的，页式存储管理 采用的地址重定位方式是___________，需要有硬件的地址转换机构作支持。

8. 8. 分页存储管理系统中的页表保存作业中逻辑页号与主存块号之间的对应关系，每个作 业具有________张页表。当要按照给定的逻辑地址进行存取时，至少需要______ 次访问主存 。

9. 9. 页式存储管理按给定的逻辑地址读写时，要访问两次主存，第一次访问_________， 将逻辑地址变换成物理地址，第二次访问物理地址 。为了提高存取速度，根据程序执行具有

局部性的特点，系统通常设置一个________ ，加快地址变换速度。

10. 10. 页式存储管理提供的逻辑地址是一维的，而段式存储管理的逻辑地址是 _______； 分页是由＿＿＿自动地完成的，而分段是由用户决定的。

11. 11. 段页式存储管理兼顾了段式存储管理在________方面的优点和页式存储管理在_____

___ 方面的优点。

12. 12. 缺页中断率与分配给作业的主存块数有关，分配给作业的主存块数多，能_______ 缺页中断率；反之，缺页中断率就 ________。

13. 13. 在虚拟段式存储管理的系统中，地址变换过程可能会因为_______、__________ 和 访问权限错等原因而产生中断。

14. 14. 虚拟存储器实际上是为扩大主存容量而采用的一种设计技巧，虚拟存储器的最大容 量是由__________ 和_______________共同决定的。

15. 15. 操作系统实现虚拟存储器需要_____________、________________ 和中断机构等硬 件支持。

16. 16. 采用虚拟存储器的前提是程序的两个特点，—是程序执行时某些部分是___________ _______的、二是程序的执行往往具有________________。

17. 17. 在段页式存储管理系统中，面向_________的地址空间是段式划分，面向__________ _____ 的地址空间是页式划分。

解答: 1. 2.

3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17.

二.简答题

1. 1. 简述存储管理的功能。

2. 2. 主存空间信息保护有哪些措施？

3. 3. 为什么要做“重定位”?何谓静态重定位和动态重定位?

4. 4. 在固定分区管理下，如何改善主存空间利用率?

5. 5. 可变分区方式常用的主存分配算法有哪几种？

6. 6. 何谓页表和快表?它们各起什么作用?

7. 7. 段式和页式存储管理的地址结构相似，它们有什么实质性差异?

8. 8. 操作系统如何处理缺页中断和缺段中断?

9. 9. 常用的页面调度算法有哪几种?

10. 10. 影响缺页中断有哪几个主要因素？

11. 11. 分页与分段两种存储管理方案中，哪个更易于实现信息共享，为什么？

12. 12. 为什么段式管理有段内越界问题，而页式管理不会发生页内越界问题？

13. 13. 什么叫虚拟存储器？实现虚拟存储器的条件是什么？

14. 14. 为什么要采用虚拟存储器管理，其工作原理和理论依据又是什么？

15. 15. 简述段页式存储管理的基本思想。

解答: 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15.

三.应用题

1. 1. 采用可变分区方式管理主存空间时，若主存中按地址顺序依次有五个空闲区，空闲区 的大小分别为15K，28K，10K，226K，110K，现有五个作业Ja，Jb，Jc，Jd和Je，它们所需的

主存依次为10K、15K，l02K，2６K和80K，如果采用最先适应分配算法能把这五个作业按Ja～

Je的次序全部装入主存吗?用什么分配算法装入这五个作业可使主存的利用率最高?

2. 2. 某系统采用动态分区存储管理技术，某时刻在内存中有三个空闲区，其首地址和大小 分别是：空闲区1（100KB，10KB），空闲区2（200KB，20KB），空闲区3（300KB，15KB）。 现有如下作业序列：作业1要求15KB，作业2要求16KB，作业3要求10KB。要求： （1）画出该时刻内存分布图； （2）有首次适应算法和最佳适应算法，画出此时的自由内存队列结构； （3）哪些算法能将该作业序列装入内存（给出简要的分配过程）。

3. 3. 某系统采用请求分页存储管理方案，其逻辑地址结构有20位，其中页内地址占11位； 某作业有4页，页号为0——3，分别存放在主存的4、7、5、8块中。试问： ①作业的虚存地址空间有多大？ ②系统的页面大小为多少？ ③逻辑地址5000对应的物理地址是多少

4. 某段表内容如下：

一逻辑地址为（2，154）的实际物理地址为多少？

5. 5. 在一个采用页式虚拟存储管理的系统中，有一用户作业，它依次要访问的字地址序列 是：115，228，120，88，446，102，321，432，260，167，若该作业的第0页已经装入主存

，现分配给该作业的主存共300字，页的大小为100字，回答下列问题： （1）按FIFO算法将产生次缺页中断？依次淘汰的页号为哪些？缺页中断率为多少？ （2）按LRU算法将产生多少次缺页中断，依次淘汰的页号为哪些？缺页中断率为多少？

6. 6. 考虑下述页面走向：1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3 ，6，当内存块数量分别为3时，试问FIFO、LRU置换算法的缺页次数各是多少？

7. 7. 如果有一个程序要把50×50的数组赋初值形成单位矩阵，每个主存块为200个字节， 每个数组元素占2个字节，若已分配到2个主存块可供使用，数组中的元素按行编址，其初始

状态为空，程序编制如下： (a) Var：A：ARRAY［l．．50，1．．50］ Of INTEGER； I,J:INTEGER; BEGIN FOR J:＝1 TO 50 DO FOR I:＝1 to 50 DO IF I=J THEN A[i，J]：＝1 ELSE A[i，J]:＝0 END;

(b) VAR：A：ARRAY［l．．50，1．．50］ Of INTEGER； I,J:INTEGER; BEGIN

FOR I:＝1 to 50 DO FOR j：＝1 to 50 D0 IF I=J THEN

A[i，J]：＝1 ELSE

A[i，J]：＝0

END;

（1）程序a执行时的缺页中断次数是（ ）次。 （2）程序b执行时的缺页中断次数是（ ）次。

8. 8. 在某一时刻，存储分块表的状态如下图所示，现有作业3的页5需要入页。试问：按FI

FO算法应该淘汰哪一页？并画出淘汰后的存储分块表。

9. 9. 设内存驻留四个页面，在某一时刻各引用标志位及淘汰指针如下图所示，此时需淘汰 一页，试用近似的LRU算法确定应淘汰哪一页？并画出淘汰后的MBT图。

10. 10. 设作业的虚拟地址为32位，其中高12位为段号，低20位为段内相对地址。试问： ①一个作业最多可以有多少段？ ②每段的最大长度为多少字节？

11. 11. 某采用段式存储管理的系统为装入主存的一个作业建立了如下表所示的段表。回答 下列问题： ①计算该作业分别访问［０，４３２］、［ｌ，１０］、［２， ５００］、［３， ４ ００］时的绝对地址；其中方括号内第一个元素是段号，第二个元素是段内地址； ②总结段式存储管理方式的地址转换过程。

12. 12. 在一个页式存储管理系统中，一个作业有四个页面，被分别装入主存的3，4，6，8 块中。假定页面和存储块的大小均1K字节，主存容量为10K字节。 (1)写出该作业的页面变换表； (2)当该作业在CPU上运行时，执行到其地址空间第500号处遇到一条传送指令： MOV 2100，3100 请用地址变换图计算出MOV指令中两个操作数的物理地址。

13. 13. 一进程己分配到4个页框，如表所示。当进程访问第4页时，产生缺页中断。请分别

用FIFO和LRU 算法，决定缺页中断服务程序选择换出的页面。

14. 14. 某虚拟存储器中的用户空间共有32个页面，每页1KB，主存16KB。假定某时刻系统为

用户的笫0、1、2、3页分别分配物理块为5、10、4、7，虚拟地址0A6F对应的物理地址为多少 ?

15. 15. 在分页式存储管理中，什么叫快表，说明其工作原理和过程，画出具有快表的地址 变换机构。

16. 16. 段页式系统中，其中作业的段表、页表格式如图所示，页的大小为1K，现有逻辑地

址为[2]|<2248>，其对应的物理地址为多少？

解答: 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16.

第七章 文件系统

一.填空题

1. 1．文件系统主要管理计算机系统的软件资源，即对于各种﹎﹎﹎的管理。

2. 2．从用户的角度看，文件系统的功能是要实现﹎﹎﹎。为了达到这一目的，一般要建立 文件目录

3. 4．文件存储空间管理的基本方法有位示图法、﹎﹎﹎。

4. 3．文件存储器一般都被分成若干大小相等的﹎﹎﹎，并以它为单位进行 信息交换。

5. 5．文件的物理存储结构有三种方式，即__________、链接文件、索引文件

6. 6．单级（一级）文件目录不能解决﹎﹎﹎的问题。多用户系统所用的文件目录结构至少 应是二级文件目录。

7. 7．大多数文件系统为了进行有效的管理，为用户提供了两种特殊操作，即在使用文件前 应先打开文件，文件使用完应﹎﹎﹎ 。

8. 8．对磁盘上一个物理块的访问要提供三个参数，分别是柱面号、磁头号、和﹎﹎﹎

9. 9．目录文件是由文件说明组成的，文件系统利用﹎﹎﹎完成“按名存取”和对文件信息 的共享和保护。

10. 10. 磁盘与主机之间传递数据是以__________为单位进行的。

11. 11. 在文件系统中，要求物理块必须连续的物理文件是__________。

12. 12. 文件的结构就是文件的组织形式，从用户观点出发所看到的文件组织形式称为文件 的逻辑结构；从实现观点出发，文件在外存上的存放组织形式称为文件的____。

13. 13.通常，文件的逻辑结构可以分为两大类：无结构的﹎﹎和有结构的记录式文件。

14. 14.文件系统的按名存取主要是通过﹎﹎﹎实现的。

15. 15. 磁盘文件目录表的内容至少应包含文件名和____。

16. 16．文件系统为每个文件另建立一张指示逻辑记录和物理块之间的对应关系表，由此表 和文件本身构成的文件是__________。

解答:

1. 【答案】文件 【解析】用户使用计算机来完成自己的某项任务时，总会碰到这样一些问题：其一 ，使用现有的软件资源来协助自己工作。例如，利用系统调用和利用库函数与实用程序等来 减少编程的工作量，避开与硬件有关的部分。其二，编制完成的或未完成的程序存放在什么 地方，需要访问的数据存放在什么地方。这实际上是怎样对软件资源进行透明的存放，并能 透明地存取，文件系统也就应运而生了。

2. 【答案】①按名存取 【解析】文件系统的建立就是要让用户透明地对文件进行存取，这就要求文件系统 要解决把每个文件的符号名与其所在的文件存储空间中的物理地址联系起来的问题，这也是 文件系统最基本的功能。实现符号名与具体物理地址的转换，其主要环节是查目录。所以， 文件目录的组织是文件系统研究的主要问题之一。

3. 【答案】空闲块链接法。 【解析】文件存储空间的管理实质上是空闲块的组织和管理问题，它包括空闲块的分配 与空闲块的回收等问题，这就要求对文件存储空间的空闲块进行有效的组织和管理。

4. 【答案】①物理块 【解析】文件存储空间的管理是文件系统的重要任务之一，磁盘、磁带是常见的文件存 储器。

5. 【答案】顺序文件 【解析】顺序文件、链接文件适合顺序访问，而索引文件既适合顺序访问又适合随机访 问。

6. 【答案】文件重名 【解析】因为单级文件目录表中，各文件说明项处于平等地位，只能按连续结构或 顺序结构存放，因此，文件名与文件必须—一对应。如果两个不同的文件重名，则系统将把 它们视为同一文件。在二级文件目录结构中，各文件的说明信息被组织成目录文件，且以用 户为单位把各自的文件说明划分为不同的组，而把不同的、组名有关的存取控制信息存放在 用户的主目录的目录项中。

7. 【答案】关闭文件 【解析】打开文件就是把该文件有关的目录表复制到内存中约定的区域，使用户能

实现按名存取。所谓关闭文件，就是当用户宣布这个文件当前不再使用时，系统将此文件在