操作系统习题集(南京晓庄学院操作系统习题答案)

操作系统基础

习题解析及实验指导

第一篇操作系统基础知识点及习题解答

该部分罗列操作系统基础各章节的学习要点，指出学习的重点和难点，在回顾相关知识点的基

础上，对典型习题进行分析和解答。

第一章操作系统引论

本章学习要点

[1]掌握操作系统的概念与作用

[2]掌握操作系统的基本类型与特点

[3]掌握操作系统的特征与功能

[4]深入领会多道程序设计技术

本章学习难点

[1]多道程序设计技术

【2】操作系统的特征

知识点回顾

—.操作系统的概念

一个完整的计算机系统由计算机硬件系统和计算机软件系统两部分组成。操作系统是配置

在计算机硬件上的第一层软件，是对硬件系统功能的第一次扩充。

1.操作系统(OperatingSystem,简称OS)的作用

(1)OS作为用户与计算机硬件系统之间的接口

OS处于用户与计算机硬件系统之间，用户通过OS来使用计算机系统。或者说，用户在OS

的帮助下能够方便、快捷、安全、可靠地操纵计算机硬件和运行自己的程序。

(2)OS作为计算机系统资源的管理者

这是广为流行的一个关于OS作用的观点。在一个计算机系统中，通常都包含了各种各样的

硬件和软件资源。归纳起来可将资源分为四类：处理器、存储器、I/O设备以及信息(数据和

程序)。OS的主要功能正是针对这四类资源进行有效的管理。

(3)OS用作扩充机器

对于一台完全没有软件配置的计算机系统(裸机)，即使功能再强，也必定难于使用。0$在

裸机上分别覆盖I/O设备管理软件、文件管理软件等，此时用户所看到的机器，将是一台比裸

机功能更强、使用更方便的机器。通常把覆盖了软件的机器称为扩充机器或虚机器。

在计算机系统上覆盖上一层软件后，系统功能便增强一级。由于OS自身包含了若干层软件,

因此当在裸机上覆盖上OS后，便可获得一台功能显著增强，使用极为方便的多层扩充机器或多

层虚机器。

2.操作系统的概念

操作系统是一组控制和管理计算机硬件和软件资源、合理组织计算机的工作流程，方便用

户使用的程序的集合。

操作系统是裸机上的第一层软件，是对硬件功能的首次扩充。

二.操作系统的发展过程

人工操作方式f脱机输入输出技术一批处理技术一分时、实时系统一通用操作系统一微机操作

系统一网络操作系统一分布式操作系统

1.脱机输入输出技术

为解决人工操作阶段存在的人机矛盾以及CPU与I/O速度不匹配的矛盾，引入脱机输入输

出技术。系统中除主机外配置一台外围机（又称卫星机），它只与输入输出设备打交道，不与主

机相连，即脱机。用户程序与数据可以在外围机控制下（脱离主机控制）预先从低速设备输入

到磁带上，CPU需要时再从磁带上输入到主机，即脱机输入技术，以解决CPU与I/O速度不匹

配的矛盾。类似地，脱机输出技术通过外围机完成数据从主机到磁带，再到低速输出设备上的

输出操作。由于主机CPU只与高速的输入输出设备打交道，从而有效地减少了CPU等待低速设

备输入输出的时间。

图1-2脱机输入/输出方式

2.批处理技术

批处理技术是指计算机对一批作业自动进行处理的一种技术。

早期的计算机系统为了充分利用系统资源，通常把一批作业以脱机输入方式输入到磁带上,

并在系统中配置监督程序，依次将作业装入存，控制磁带上的作业自动地、一个接一个地进行

处理，这样就形成了早期的单道批处理系统。

3.多道程序设计技术

为进一步改进单道批处理系统中CPU和存利用率较低的问题，引进多道程序设计技术。多

道程序设计技术同时将多个作业放入存并允许作业交替执行，共享系统中的资源。宏观上并行,

微观上串行。

多道程序设计技术能有效提高系统的吞吐量和改善资源利用率，但是为了协调存中运行的

多道程序，应妥善解决处理机分配、存分配、设备分配、文件安全、作业组织的问题。为解决

上述问题而设置的一组软件就形成了操作系统。

程序A程序B程序A程序B

CPU

!

输入设备----------i-----

输出设备1u

运行处理输入数据运行处理输出数据

程序AI____________I__________I_________

运行处理输出数据等待CPU运行处理

程序B_______I_________L_____L

图1-3多道程序运行情况

三.操作系统的分类

1.单用户操作系统

2.批处理操作系统

(1)单道批处理系统

把一批作业以脱机方式输入到磁带上，在系统中配上监督程序，在它的控制下使这批作业

能自动地一个接一个地顺序处理。对作业的处理是成批进行的、且存中始终只保持一道作业。

(2)多道批处理系统

5引入多道批处理的目的

a)提高CPU的利用率

b)提高存和I/O设备的利用率

c)增加系统吞吐量

U多道批处理的特征一一多道性、无序性、调度性

8多道批处理的优缺点

资源利用率高，系统吞吐量大，但平均周转时间长，无交互能力。

3.分时操作系统

在分时操作系统中，一台计算机和多台终端相连，每个用户通过自己的终端向系统发出命

令请求，系统分析并完成各用户的请求。

(1)单道分时系统

存中只驻留一道作业，当其运行一个时间片后，调至外存，再从外存上选一个作业进入存。

作业频繁调进调出，开销大，系统性能较差。

(2)具有''前台”和“后台”的分时系统

存被固定地划分为“前台区”和“后台区前台区存放按时间片“调进”和“调出”的作

业流，后台区存放批处理作业。仅当前台无作业运行时，方才运行后台的作业。

(3)多道分时系统

存中的多道作业轮流获得一个时间片来运行。

分时系统的特征具有多路性、独立性、及时性和交互性等特征。

4.实时操作系统

能使计算机系统接收到外部信号后及时进行处理，并且在严格的规定时间处理结束，再给

出反馈信号的操作系统。实时操作系统分为实时控制系统和实时信息处理系统。例如生产过程

控制系统、航空订票系统等。实时系统具有多路性、独立性、及时性、交互性和可靠性等特征。

实时控制系统是以计算机为中心的生产过程控制系统，又称为计算机控制系统，要求快速

的响应时间，可靠性要求高。实时信息处理系统在响应时间上和分时系统处于同一级别，但更

强调可靠性和安全性，交互性差。

批处理操作系统、分时操作系统、实时操作系统是三种基本的操作系统类型。如果一个操

作系统兼有三者或其中二者的功能，则该操作系统称为通用操作系统。

5.其它操作系统

包括网络操作系统、分布式操作系统等。

四.操作系统特征一一并发、共享、虚拟、异步性

1.并发

并发是指两个或多个事件在同一时间间隔发生。宏观上是同时的，微观上是交替的。程序

的并发执行能有效改善系统资源的利用率，但会使系统复杂化。要注意区别并发和并行两个概

念。

2.共享

系统中的资源可供存中多个并发执行的进程共同使用。根据资源的不同属性，可分为两种

资源共享方式：互斥共享和同时访问。

并发和共享是操作系统的两个最基本的特征，两者之间互为存在的条件。一方面，资源的

共享是以程序的并发执行为前提的；另一方面，系统若不能对资源共享实施有效管理，则程序

的并发执行则无法实现。

3.虚拟

通过某种技术把一个物理实体变成若干个逻辑上的对应物，物理实体是实的，即实际存在，

而后者是虚的，是用户的感觉。例如虚拟存、虚拟设备等。

4.异步性

在多道程序环境下，多个进程并发执行，但由于资源等因素的限制，存中的每个进程何时

执行，何时暂停，以怎样的速度向前推进，每道程序需多少时间才能完成，都是不可预知的，

进程以异步的方式运行。但只要运行环境相同，作业经过多次运行，都会获得完全相同的结果。

五.操作系统的功能

操作系统引入多道程序设计技术，一方面改善了系统资源的利用率，但另一方面也引发了

复杂的系统管理问题，诸如存中的作业如何存储，系统资源如何共享等，操作系统必须具有控

制和管理各种并发活动的能力，合理组织计算机的工作流程，有效地提高各类资源的利用率。

1.处理机管理

主要任务是对处理机进行分配，并对其进行有效的控制和管理。在多道程序环境下，处理

机的分配和运行是以进程为基本单位，又称进程管理。

(1)进程控制一一为作业创建进程，撤消已结束的进程，以及控制进程的状态转换。

(2)进程同步一一对诸进程的运行进行协调(互斥和同步)。

(3)进程通信一一实现相互合作进程之间的信息交换。

(4)进程调度一一从就绪队列中，按照一定的算法选出一新进程，分配处理机，设置运行现

场，使之投入运行。

2.存储器管理

存储器管理的主要任务是为多道程序的运行提供良好的环境，方便用户使用存储器，提高

存储器的利用率，以及从逻辑上来扩充存。

(1)存分配——为每道程序分配存空间，提高存的利用率。

(2)存保护一一确保每道用户作业都在自己的存空间中运行，互不干扰。

(3)地址映射一一将地址空间中的逻辑地址转换为存空间中与之对应的物理地址。

(4)存扩充一一借助虚拟技术，从逻辑上扩充存容量。

3.设备管理

主要任务是完成用户提出的I/O请求，为用户分配I/O设备；提高CPU和I/O设备的利用

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

(1)缓冲管理一一管理各种类型的缓冲区。

(2)设备分配一一根据用户的I/O请求，分配所需设备。

(3)设备处理一一实现CPU和设备控制器之间的通信。

(4)设备独立性和虚拟设备

4.文件管理

程序和数据都是以文件的形式存储在存储介质上。文件管理的主要任务是对用户文件和系

统文件进行管理，方便用户使用，保证文件的安全性。

(1)文件存储空间的管理

(2)目录管理一一建立目录项，实现按名存取、实现文件共享。

(3)文件的读、写管理和存取控制

(4)文件保护

5.作业管理

(1)操作系统接口

(2)作业的控制方式

六.操作系统的结构一一模块接口法、有序分层法

1.模块接口法

按功能划分模块，模块间可以不加控制的相互调用和转移。这种结构紧凑、接口简单直接,

系统效率高；但模块间的调用随便，独立性差，系统结构不清晰。

2.有序分层法

Ao,Ai..A,(Ai+i....An

A。宿主系统(底)，An是目标系统(顶)。既可采用自底向上法，逐步扩充，也可采用自顶

向下法，逐层分解。

(1)单向依赖

(2)同一层中各模块的功能应相近

(3)与硬件紧密相关的模块安排在A。层，便于移植

(4)运行频率较高的公用模块应放置在较低的层次

(5)由于设计目标不同而变化的部分放在外层，增强系统的适应性

习题分析

一.判断改错题(判断由下划线标明的关键词的叙述是否正确，正确的打错误的打X并改正。)

(1)实时系统只能应用于生产控制系统,不能应用于信息处理系统。()

(2)并发含有''同时进行”的里念，是指两个或者是多个事件在同一时刻发生。()

(3)操作系统虚拟机在逻辑功能上与裸机一样,具有一个物理实体。()

(4)对用户而言，操作系统是一种人机交互的环境,对设计者而言，它是一种强功能的系统资源

管理程序。()

(5)资源的共享是以程序的并行执行为受仕的，没有程序的并行执行，就没有资源的共享。

()

(6)计算机系统的复遮包括程序和数据两大部分。()

(7)若把计算机系统分为若干层次,则按由上而下顺序可分为应用系统与应用软件、操作系统、

其它系统软件和裸机。()

(8)批处理控制程序解决了作业间的自动转换,减少了时间浪费，尤其是主机CPU时间的浪费，

如果一个用户的计算作业非常庞大，也不会独自一直占据CPU。()

习题解答：

(1)错；应为：实时系统能应用于生产控制系统，也能应用于信息处理系统。

(2)错；应为：……是指两个或者是多个事件在一段时间间隔同时发生。

(3)错；应为：操作系统虚拟机在逻辑功能上与裸机不同，但只具有一个物理实体。

(4)对；

(5)错；应为：资源的共享是以程序的并发执行为条件的，没有程序的并发执行，就没有资源的

共享。

(6)错；应为：计算机系统的资源包括硬件资源和软件资源两大部分。

(7)错：应为：若把计算机系统分为若干层次，则按由上而下顺序可分为应用系统与应用软件、

其它系统软件、操作系统和裸机。

(8)错；应为：……，尤其是主机CPU时间的浪费，如果一个用户的计算作业非常庞大，就会独

自一直占据CPU。

(9)对；

二.填空题

(1)实时含有立即、及时之意，因而是实时系统最关键的因素。

(2)操作系统的层次结构中，与或运行频率较高的模块都安排在紧靠硬件的软件

层中，这一部分通常称为,它在执行基本操作时，往往是利用操作来实现，

该操作具有原子性。

(3)UNIX是一个真正的用户、任务的操作系统。

(4)如果一个操作系统兼有、和三者或其中两者的

功能，这样的操作系统称为通用操作系统。

(5)实现多道程序设计必须妥善解决三个问题：、和系统资源的管理和调度。

(6)批处理系统的主要优点是,资源利用率高，系统开销小，它的缺点在于作

业处理的,用户交互能力较弱。

(7)操作系统是对计算机进行的程序，是计算机和的接口。

(8)提供网络通讯和网络资源共享功能的操作系统称为操作系统。

(9)对系统总体设计目标来说，批处理系统注重提高计算机的效率，尽量增加系统的,分

时系统应保证用户的,而实时系统在及时响应和处理的前提下，再考

虑。

(10)在主机控制下进行的输入/输出操作称为操作。

(11)在计算机系统中，是整个系统硬件的核心和基础，而在计算机软件系统中，

具有同样的核心和基础作用。

习题解答：

(1)响应时间；

(2)硬件紧密相关，核，原语；

(3)多，多，网络；

(4)批处理操作系统、分时操作系统、实时操作系统；

(5)文件，作业；

(6)系统吞吐量大，平均周转时间较长；

(7)控制和管理，用户；

(8)网络；

(9)吞吐量，交互性，与用户的交互性；

(10)联机I/O操作；

(11)CPU,操作系统；

三.简答题

1.简述操作系统在计算机系统中的位置。

答：操作系统OS是运行在计算机硬件系统上的最基本的系统软件。它在计算机系统中位于计算机裸

机和计算机用户之间，为系统软件和用户应用软件提供了强大的支持。

2.简述描述操作系统的两种主要观点。

答：描述操作系统有两种主要观点，一种是虚拟机的观点一一装有操作系统的计算机极扩展了原计

算机的功能，给用户提供了一个友好的、易于操作的界面，对用户来说，好像是一个扩展了的机器,

即一台虚拟机器。另一种是资源管理的观点，操作系统完成对处理机、存储器、I/O设备等硬件资

源和文件等软件资源的管理。

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

答：操作系统是一组控制和管理计算机硬件和软件资源、合理组织计算机的工作流程，以及方便用

户的程序的集合。操作系统的基本特征是：

并发一一是指两个或多个事件在同一时间间隔发生。宏观上是同时的，微观上是交替的。

共享一一系统中的资源可供存中多个并发执行的进程共同使用。根据资源的不同属性，可分为两种

资源共享方式：互斥共享和同时访问。

虚拟一一通过某种技术把一个物理实体变成若干个逻辑上的对应物，物理实体是实的，即实际存在，

而后者是虚的，是用户的感觉。

异步性一一在多道程序环境下，多个进程并发执行，但由于资源等因素的限制，存中的每个进程何

时执行，何时暂停，以怎样的速度向前推进，每道程序需多少时间才能完成，都是不可预知的，进

程以异步的方式运行。但只要运行环境相同，作业经过多次运行，都会获得完全相同的结果。

4.多道程序设计时应注意什么问题？

答：处理机管理问题一一多道程序之间如何分配CPU,使CPU既能满足各程序运行的需要，又能提

高处理机的利用率。

存管理问题一一为每道程序分配必要的存空间，并防止程序遭破坏。

I/O设备管理一一分配为多道程序共享的I/O设备，方便用户使用，提高设备利用率。

文件管理问题一一组织大量的程序和数据，便于用户使用，保证数据的安全和一致。

作业管理问题一一对系统中各种类型的作业进行组织。

四.练习题

1.实时操作系统必须在（）处理来自外部的事件。

A.一个机器周期B.被控制对象规定的时间

C.周转时间D.时间片

2.操作系统中最基本的两个特征是（）

A.并发和不确定性B.并发和共享C.共享和虚拟D.虚拟和不确定性

3.分时系统追求的目标是（）

A.充分利用I/O设备B.快速响应用户

C.提高系统吞吐量D.充分利用存

4.批处理系统的主要缺点是（）

A.系统吞吐量小B.CPU利用率不高C.资源利用率低D.无交互能力

5.在主机控制下进行的输入输出操作称为（）操作。

6.如果操作系统具有很强的交互性，可同时供多个用户使用，系统响应比较及时，则属于（）

类型；如果系统可靠，响应及时但仅有简单交互能力则属于（）类型；如果操作系统在

用户提交作业后不提供交互能力，它追求的是计算机资源的高利用率，大吞吐量和作业流程的

自动化，则属于（）类型。

7.设存中有三道程序A、B、C,它们按A、B、C的优先次序执行。它们的计算和I/O操作时间

操作,程序ABC

计算306020

I/O403040

计算101020

如下表所示（单位：ms）。假设三道程序使用相同设备进行I/O操作，即程序以串行方式使用设备。

试画出单道运行和多道运行的时间关系图（调度程序的时间忽略不计）。在两种情况下，完成三道程

序各要花多少时间？

8.试比较分时系统和实时系统。

9.简述DOS、Windows和UNIX操作系统的特点。

第二章进程管理

本章学习要点

[1]掌握进程的定义和特征

[2]深入领会进程状态及其状态转换的原因

[3]熟练运用信号量解决进程同步问题

[4]掌握调度的类型与方式

[5]掌握常用的进程调度算法

[6]掌握死锁的相关知识

[7]深入领会银行家算法

本章学习重点和难点

[1]运用信号量解决进程同步问题

[2]进程调度算法

[2]银行家算法

知识点回顾

多道程序设计技术的引入，实现了资源的共享和程序的并发执行。为了描述并发执行的动

态特点，引入进程的概念。进程是可并发执行的程序在一个数据集合上的运行过程，具有动态

性、并发性、独立性、异步性和结构特征。进程管理包括进程控制、进程同步、进程通信和进

程调度四个主要方面。

一.前趋图和程序执行

1.前趋图是一个有向无循环图，以描述结点（语句、程序段或进程）之间的前趋关系，前趋

关系描述了结点执行的先后次序。

2.程序顺序执行和并发执行的特征

令程序的顺序执行

数据1：1输入2计算3打印数据2：4输入5计算6打印

对较大程序的若干个程序段，或者某个程序段的多条语句，执行时必须按照某种先后次序

逐个执行。具备顺序性、封闭性和可再现性。

令程序的并发执行

输入

计算

输出

同一数据的不同操作之间、不同数据的同一操作之间存在着前趋关系。但不同数据的不同

操作之间可考虑并发执行。例：13、C2、P1,可并发执行。并发执行出现了新特征：间断性、

失去封闭性和不可再现性。

3.程序并发执行的条件。(Bernstein条件)

R(pi)：读集，表示程序pi在执行期间所需参考的所有变量的集合。

W(pi):写集,表示程序pi在执行期间要改变的所有变量的集合。

若两个进程P1和P2能满足下述Bemstein条件，它们便能并发执行，且具有可再现性。

R(PDnw(P2)UR(P2)nw(pi)uw(pi)nw(P2)={}

二.进程的描述

1.进程的定义和特征

进程是可并发执行的程序在一个数据集合上的运行过程。具有以下特征：

令动态性一一是进程最基本的特性。进程有一定的生命期，由创建而产生，由调度而执

行，因得不到资源而暂停执行，由撤消而消亡。而程序是一组有序指令的集合，是静

态实体。

令并发性一一多个进程在一段时间间隔同时运行。

令独立性一一进程实体是一个能独立运行的基本单位，也是系统中独立获得资源和独立

调度的基本单位。

令异步性一一进程按各自独立的、不可预知的速度向前推进。

令结构特征一一进程实体由程序段、数据段和进程控制块PCB组成。

令

A：进程调度B：发生某事件无法执行

C：时间片到或优先级高的进程到达I)：阻塞的事件消失

3.进程控制块

令进程控制块是进程实体的一部分，它记录了操作系统所需的、用于描述进程情况及控

制进程运行所需的全部信息。

令进程控制块的作用是使一个在多道程序环境下不能独立运行的程序(含数据)，成为一

个能独立运行的基本单位，一个能和其它进程并发执行的进程。

令PCB是进程存在的唯一标志。创建新进程时建立一个PCB,进程结束时回收PCB。

令PCB经常被系统访问，应常驻存。

令PCB的容

>进程标识符信息一一外部标识符、部标识符(唯一整数)。

A处理机状态信息

>进程调度信息一一进程状态、优先级等。

>进程控制信息一一程序和数据地址、同步机制、资源清单等。

令PCB的组.织方式

A方式----相同状态的PCB,成一个队列。

A索引方式---建立索引表。

三.进程控制

1.操作系统的核

核是计算机硬件的第一层扩充软件，由与硬件紧密相关的模块以及运行频率较高的模块组成，

常驻存，以提高OS的运行效率。

令支撑功能

>中断处理

是核最基本的功能，它是整个操作系统赖以活动的基础。核只对中断进行''有限的处

理”，然后转由有关进程继续处理。

>时钟管理

>原语操作

原语本身是由若干条指令构成，用于完成一定功能的一个过程。原语是一个不可分割

的原子操作。

令资源管理功能一一进程管理、存储器管理和设备管理。

2.进程的创建、终止、阻塞与唤醒

(1)进程的创建

令进程图一一是描述进程家族关系的有向树。有向边表示了进程的创建关系，即父子关

系，(注：并不能说明前趋关系)，子进程可以继承父进程所拥有的资源，父进程撤消

时必须同时撤消其所有子进程。

令引起创建进程的事件

>用户登录(分时系统)'

>作业调度(批处理系统)C由系统核创建进程

>提供服务J

>应用请求一一应用进程创建

令进程的创建一一创建原语

申请空白PCB—>为进程分配资源一►初始化PCB->插入就绪队列

(2)进程的终止一一正常结束、异常结束、外界干预

(3)进程的阻塞与唤醒

令原因一一•请求系统服务、启动某种操作、新数据未到达、无新工作

令阻塞一一当出现上述事件，进程无法继续执行，进程通过调用阻塞原语block把自己

阻塞，是进程自身的一种主动行为。

令唤醒一一当阻塞事件结束，由发现者进程调用唤醒原语将阻塞进程唤醒，是一种被动

行为。

四.进程同步

1.进程同步的基本概念

多道程序环境下，系统中的进程间可能存在两种关系：

间接制约关系一一资源共享，进程同步保证诸进程互斥访问临界资源。

直接制约关系一一相互合作，进程同步保证诸进程在执行次序上的协调。

令临界资源-----段时间只允许一个进程访问的资源。例如：打印机。

令临界区

进程中访问临界资源的那段代码称为临界区。要保证对临界资源的互斥访问，只需保证进程互

斥地进入自己的临界区。

Repeat

进入区(entrysection)检查临界资源的使用，设置访问标志

临界区(criticalsection)

退出区(exitsection)］恢复未访问标志

剩余区(remaindersection)

untilfalse

令同步机制应遵循的准则

>空闲让进一一有效利用

>忙则等待一一互斥

>有限等待一一避免“死等”

>让权等待一一避免“忙等”

令利用硬件方法解决进程互斥一一特殊的硬件指令

2.信号量机制

令整型信号量机制

>将整型信号量定义为一个整型量，仅能通过两个标准的原子(不可中断)操作(P、

V)来访问。

P(S)：whilesWOdonoop"忙等”

s：=sT；

V(S)：s：=s+l；

A利用信号量实现互斥

为使多个进程能互斥地访问某临界资源，应为该临界资源设置一互斥信号量

mutex,并设初始值为1,然后将各进程的临界区置于P(mutex)和V(mutex)操作

之间。注意实现进程互斥时P、V操作必须成对出现。

Repeat

进入区P(mutex)

临界区(criticalsection)

退出区V(mutex)

剩余区(remaindersection)

untilfalse

由于mutex的初值为1任何时刻只能有一个进程进入临界区，此时互斥信号量=0,

其它欲进入临界区的进程忙等。

>利用信号量描述前趋关系一一设置公用信号量So

令记录型信号量机制一一采用记录型的数据结构

>typesemaphore=record

value：integer；表示资源数目

L：listofprocess；等待该资源的进程链表

end

>p(s)

s.value：=s.value-1；

ifs.value<0thenblock(s,1)

s.value的初值表示系统中某类资源的数目。

s.value<0(不含=0)表示资源已分配完毕，自我阻塞。

s.value<0时，s.value的绝对值表示在该信号量等待队列中已阻塞进程的数

目。

>v(s)

s.value:=s.value+1；

ifs.value/0thenwakeup(s,1)；

s.valueWO表示仍有等待该资源的进程，将第一个等待进程唤醒。

当一个进程需要共享多个临界资源时，若进程的推进顺序不当，可能会产生死锁。

令信号量集机制

>AND型信号量集机制

将进程在整个运行过程中所需要的所有临界资源，一次性地全部分配给进程，待该进

程使用完后一起释放。

SP(SI,S2,...Sn)

SV(SI,S2,...Sn)

>一般“信号量集”机制

P(Si,t”di)ti表示资源下限&表示资源需求或分配数目

条件：Si>ti分配：Si：=Si-di

©p(s,d,d)一般信号量

©p(s,1,1)(s>l)一般的记录型信号量(s=l)互斥信号量

©p(s,1,0)可控开关

3.经典进程的同步问题

令生产者——消费者问题：相互合作进程关系的抽象

公用缓冲池

0

empty=n空缓冲的数量mutex=l互斥信号量

full=0满缓冲的数量

生产者消费者

是否有产品可消费

>每个程序中实现互斥的p(mutex)和v(mutex)必须成对出现。

>对生产者和消费者的Pv操作同样需要成对出现，但它们是分别处于不同的程

序中。

>在每个程序中多个P操作顺序不能颠倒。

令读者一一写者问题

一个数据对象(数据文件或记录)，可被多个进程共享。允许多个reader进程同时读一个

共享对象，但绝不允许一个writer进程和其它reader进程或writer进程同时访问共享对

象。

>利用记录型信号量解决读者一一写者问题

readcount=0：读者数目，临界资源

rmutex=l：对readcount互斥访问的互斥信号量

wmutex=l：写互斥信号量

流程见下图。

A利用信号量集机制解决读者一一写者问题

读者：写者：

repeatrepeat

sp(L,l,l)L为读者数(RN)sp(mx,1,1；L,RN,O)

sp(mx,,1,0)mx为控制开关写操作

...读操作....sv(mx,1)

sv(L,1)untilfalse

untilfalse

读者：写者:

p(rmutex)p(wiimtex)

readcount=0?第一个读者

n

p(wmutex)写操作

re3dcount：=readcount+l

v(rmutex)v(wmutex)

读操作

p(rmutex)

readcount：=readcountT

readcount=0?Tj最后一个读者读完

nv(wmutex)

v(rmiYtex)

令哲学家进餐问题

五.进程通信

进程通信是指进程间的信息交换。进程的同步是低级通信，效率低，对用户不透明。高级通信是指

用户直接利用操作系统所提供的一组通信命令（隐藏了进程通信的实现细节），高效地传送大量数据

的一种通信方式。

1.共享存储器系统

相互通信的进程共享某些数据结构或共享存储区。

令基于共享数据结构的通信方式（低级）

令基于共享存储区的通信方式

2.消息传递系统

进程间的数据交换以消息为单位。程序员直接利用系统提供的一组通信命令（原语）来实现通

信。

直接通信方式

发送进程利用OS所提供的发送命令，直接把消息发送给目标进程。要求发送进程和接

收进程都以显式的方式提供对方的标识符。

Send（receiver,message）

Receive（sender,message）

令间接通信方式

通过中间实体（信箱）进行通信，广泛用于计算机网络中。

消息在信箱中可以安全保存，只允许核准的用户随时读取。

系统为信箱提供了创建、撤消、消息发送、接收等原语。

信箱的种类：

私用信箱一一用户进程自己创建，作为该进程的一部分，采用单向链路，其他用

户发送消息，主人读取消息。

公用信箱一一操作系统创建，在系统运行期始终存在，采用双向通信链路，核准

用户可发送和取出消息。

共享信箱一一某进程创建，指明共享进程的名字。主人和共享者都有权取走自己

的消息。

信箱通信，发送和接收进程之间存在1:1、n：Ll：n（广播）、m：n（公用信箱）

的关系。

3.管道通信一一共享文件的通信方式

管道是指用于连接一个读进程和一个写进程，以实现它们之间通信的共享文件，又称pipe文件。

UNIX系统采用。

写进程以字符流的形式将大量数据送入管道，读进程接收数据。

读进程6~Q1进程

管道通信机制必须提供互斥、同步和确定对方的三种协调能力。

六.进程调度

i.调度队列模型

作业调度时间片完

批量

作业

2.调度类型

令高级调度一一作业调度

批处理系统中使用，周期较长。

令低级调度一一进程调度

是最基本的一种调度，在三种类型的OS中都必须配置。进程调度可采用非抢占或抢占两种

方式。其中抢占方式允许调度程序根据某种原则，例时间片原则、优先权原则、短进程优

先原则等去停止某个正在执行的进程，将已分配给该进程的处理机，重新分配给另一进程。

进程调度的运行频率最高，故算法不能太复杂。

令中级调度

引入中级调度的目的是为了提高存的利用率和系统吞吐量。中级调度实际上是存储器管理

中的对换功能。

3.选择调度方式和算法的准则

「周转时间（批处理）

面向用户.响应时间（分时）

的准则|截止时间的保证（实时）

I优先权准则

面向系统「系统吞吐量高（批处理）

的准则4处理机利用率好

I各类资源的平衡利用

令周转时间一一指作业提交系统开始，到作业完成为止的时间间隔。

令带权周转时间一一作业的周转时间与系统为它提供的实际服务时间之比。W-T/TS

令响应时间一一从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的时间。

令截止时间一一某任务必须开始执行的最迟时间，或必须完成的最迟时间。

令吞吐量一一单位时间所完成的作业数。

4.调度算法（作业调度、进程调度）

令先来先服务调度算法（FCFS）

>按进入后备（或就绪）队列的先后选择目标作业（或进程）。

>有利于长作业（进程），不利于短作业（进程）。

令最短作业优先调度算法SJ（P）F

>从后备（或就绪）队列中选择估计运行时间最短的作业（或进程）"产

t„+（l-）„t„为实际值，„为预测值

>SJF有效地降低作业的平均等待时间，提高了系统的吞吐量。

A对长作业（或进程）不利，可能死等，且未考虑作业的紧迫程度。

令时间片轮转调度算法（进程调度）

>系统将所有的就绪进程按先来先服务原则，排成一个队列，每次调度时把CPU

分配给队首进程，令其执行一个时间片。

>就绪队列中所有进程，在一个给定的时间，均能获得一个时间片的处理机执

行时间。T=nq

令优先权调度算法

>适用于作业调度和进程调度。

>非抢占式、抢占式优先权调度算法

>优先权类型：静态优先权、动态优先权

令高响应比优先调度算法（作业调度）

响应比R尸响应时间/要求服务时间=（等待时间+要求服务时间）/要求服务时间

=1+等待时间/要求服务时间

>同时到达的作业(等待时间相同)，要求服务时间越短(短作业)，响应比越

高，有利于短作业。

>要求服务时间相同的作业，等待时间越长，响应比越高，相当于先来先服务。

>长作业在等待足够长时间后，响应比上升，也可被调度，避免长作业的死等。

>每次调度需计算响应比，增加系统的开销。

令多级队列调度

>根据作业的性质或类型的不同，将就绪进程队列分成若干个子队列，各个作

业固定分属于一个队列。每个队列采用各自的调度算法。

令多级反馈队列调度算法

>UNIX系统中的进程调度算法。

>处理方法：

©设置多个就绪队列，每个队列赋予不同的优先权⑹展……>S„),且各队列中

进程执行的时间片的大小各不相同(q,2q……nq)o

©新进程进入存，首先放在8的末尾，按FCFS排队调度，执行q时间片，若未

完成，该进程转入Sz,依次类推。

©仅当S,空闲，才会调度Si”中进程。

>能较好地满足各种类型用户的需要。

七.死锁

1.死锁的概念

死锁是指多个进程因竞争资源而造成的一种僵局，若无外力作用，这些进程都将永远不能向前

推进。

2.死锁产生的原因

(1)竞争资源一一竞争非剥夺资源、竞争临时性资源

(2)进程推进顺序不当

3.产生死锁的必要条件(同时具备)

(1)互斥条件一一进程对所分配到的资源进行排它性使用。

(2)请求和保持条件一一请求新资源阻塞，保持其它已获得资源不放。

(3)不剥夺条件一一进程获得的资源在使用完之前不能被剥夺。

(4)环路等待条件一一存在进程一资源环形链。

4.处理死锁的基本方法

(1)预防死锁一一设置某些限制条件，破坏必要条件中的一个或几个。

(2)避免死锁一一在资源的动态分配过程中，防止系统进入不安全状态。

(3)检测死锁一一通过系统设置的检测机构，及时检测出死锁的发生，并精确确定与死锁有

关的进程和资源。

令保存有关资源的请求和分配信息一一资源分配图

资源分配图由一组结点N和一组边E组成。

N被分成两个互斥的子集，一组进程结点P={p“P2,……，P"},一组资源结点R={n,

...,r»}

E中的边e连接着P中的一个结点和R中的一个结点。

e={Pi,口}表示进程pi请求一个单位的n资源

e={rj,pj表示把一个单位的由资源分配给进程8

令提供算法检测系统是否死锁一一死锁定理

在资源分配图上，找出一个既不阻塞又非独立的进程结点，简化后使其成为孤立的结

点。

在进行一系列的简化后，若能消去图中所有的边，使所有结点都成为孤立的结点，则

该图是可完全简化的。

所有的简化顺序将得到相同的不可简化图。

s为死锁状态的充分条件是，当且仅当S状态的资源分配图是不可完全简化的。

（4）解除死锁一一将进程从死锁状态下解脱出来。

©剥夺资源

©撤消进程

5.银行家算法

令系统的安全状态

所谓安全状态，是指系统能按某种顺序，如PLP2…Pn,来为每个进程分配其所需资源，

直至最大需求，使每个进程都可顺利完成。若系统不存在这样一个安全序列，则称系统处

于不安全状态。

如果不按照安全序列分配资源，则系统可能由安全状态进入不安全状态。例，系统共有12

台磁带机，TO时刻的情况如下表，已分配出9台，可用磁带机为3台。经分析发现，TO时

刻存在安全序列P2,Pl,P3,故系统是安全的。

进程最大需求已分配尚需要可用

Pl10553(2)

P2422

P392(3)7(6)

若此时P3请求1台磁带机，则分配情况如上表（括号的数据），此时系统不存在安全序列,

进入不安全状态，将导致死锁。

令利用银行家算法避免死锁

>数据结构（n个进程，m类资源）

可利用资源available[1..m]

最大需求矩阵（n*m）max

分配矩阵（n*ni）allocation

需求矩阵（n*m）need[i,j]=max[i,j]-allocation[i,j]

>步骤

设request[j]=k,表示进程P需要k个j类资源。

分配拒绝分配

>安全性算法

（1）设置向量work和finish的初始值

work=available目前可提供的资源数目

finish[i]=false表示该进程尚未运行完成。

r->（2）从进程集合中找到满足下述条件的进程

finish[i]=false；need：work；

若找到，执行（3）,否则执行（4）。-------

（3）进程获得资源，执行并完成，释放资源

work=work+allocation

finish[i]=true

（4）若所有进程的finish[i]=true,则表示系统处于安全状态；否则，系统处

于不安全状态。

习题分析

一.判断改错题（判断由下划线标明的关键词的叙述是否正确，正确的打错误的打X并改正。）

（1）进程由程序和数据两部分组成。（）

（2）在生产者消费者进程中，V操作的次序无关紧要，而P操作次序不能颠倒。（）

（3）产生死锁的鹿区之一是对计算机操作不当，造成计算机死机。（）

(4)原语是指操作系统中的初始化程序。()

(5)若进程处于阻塞状态，当引起阻塞的条件被解除时，进程状态应变为运行状态。()

(6)并发进程可以同时进入临界区,交替访问临界资源。()

(7)程序的封闭性是指该程序不允许某些进程调用。()

(8)消息通信因为常数据量较小,因而它是一种低级通信方式。()

(9)单机系统最多允许二个进程处于运行状态。()

(10)管道通信,是以管道消息为单位进行读写的，可进行大批量数据交换，其工作是以先进先出

为顺序的。()

(11)死锁产生，必须要满足四个必要条件，所以，为避免死锁产生,主要注意如何不让这四个必

要条件成立，并打破循环等待资源的环路。()

(12)操作系统的进程管理是整个操作系统管理中的核心,它包含了进程的调度、协调以及进程通

信。()

习题解答：

(1)错；应为：进程由程序、数据和进程控制块及相关表格组成。

(2)对；

(3)错；应为：产生死锁的原因是：进程推进顺序不当或竞争资源。

(4)错；应为：原语由若干条指令所构成、用于完成一定功能的一个过程，具有原子性。

(5)错；应为：……当引起阻塞的条件被解除时，进程状态应变为就绪状态。

(6)错；应为：并发进程必须互斥进入临界区，互斥访问临界资源。