计算机操作系统讲义9

《计算机操作系统》讲义

一、课程简介

操作系统是计算机系统的核心，它负责控制和管理整个计算机系统的软

硬件资源，并使之协调工作。随着计算机的功能不断地发展和创新，计算机

系统仍然遵循冯•诺依曼提出的体系结构，操作系统的核心功能依然是对处

理器、存储器和输入输出设备的管理。对操作系统的基本原理和核心功能的

学习和理解，是进一步创新的基础。

学习本课程，使学生了解操作系统的基本概念、功能、分类和发展历史，

掌握操作系统的使用操作方法，掌握进程和线程的管理技术，掌握处理机的

管理和调度策略，掌握存储管理系统、文件系统和设备管理技术，在此基础

上结合Linux的进程和存储管理与文件系统进行深入学习与分析，掌握目前

主流操作系统Linux的基本原理和功能以及特点。使学生比较清楚地了解现

在主流操作系统的一般面貌和内部结构，为进一步学习软、硬件技术及移植、

修改、设计和使用系统打下良好的理论基础。通过本课程的学习，可深刻理

解计算机软硬件如何协同工作，而且明确开发大型软件必然需要取得操作系

统的支持，为以后设计和实现大型应用软件和系统软件打好基础；具备基本

的分析问题和解决问题的能力。课程中应使学生掌握计算机操作系统的基本

理论知识，基本原理与设计分析方法，掌握基本的实验技能。学生学习本课

程后，为后续课程《计算机网络》、《数据库原理》、《编译原理》、《计算机接

口技术》、《计算机组成原理》、《嵌入式系统》、《软件工程》的学习打下一个

坚实的基础。

二、课程教材

教材：张尧学，史美林，张高.计算机操作系统教程（第3版）.北京：清华大

学出版社,2006

教学内容：

第一章绪论

第二章操作系统用户界面

第三章进程管理

第四章处理机调度

第五章存储管理

第六章进程与存储管理示例

第七章文件系统

第八章设备管理

第九章Linux文件系统

三、课程安排

1、学时安排

总学时：56

理论学时：46

实验学时：10

2、参考书目

[1]张尧学编.计算机操作系统教程（第三版）习题解答与实验指导.北京:清华

大学出版社，2006

[2]汤子瀛主编.计算机操作系统（第三版）.西安:西安电子科技大学出版社，

2001

[3]AndrewS.Tanenbaum.ModernOperatingSystems,SecondEdition.Englewood

Cliffs,N.J,PrenticeHall,2001

14J屠祁等编.操作系统基础（第三版）.北京:清华大学出版社，2000

[5]冯耀霖等编.操作系统.西安:西安电子科技大学出版社，2001

[6]左万历.计算机操作系统教程（第二版）.北京：高等教育出版社，2004

备课札记

第一章操作系统引论

主要内容:

本章主要介绍什么是操作系统；操作系统在计算机

系统中的地位、作用；操作系统的发展过程；操作系统

的基本特征和功能；操作系统的结构设计模式；并对操

作系统的今后发展动向和现在流行的操作系统进行介

绍。

教学安排：

理论教学；共2学时y

1.1什么是操作系统

一、系统软件的构成

银行系统航空订票系统游戏｝应用程序

编译器编辑器命令解释器

系统程序

操作系统

机器语言

微程序硬件

物理设备

二、操作系统的作用

1、操作系统作为用户与计算机硬件系统之间的接口

用户通过两种方式使用计算机：一是命令方式；二是系统

调用方式。

2、操作系统作为计算机系统资源的管理者

系统资源分为：处理机资源（一个或多个）、存储器资源、

I/O设备资源以及信息资源。

相应操作系统的管理分为：处理机管理（进程管理）、存储

器管理、I/O设备管理和文件管理

3、操作系统作为扩充机器一虚拟机

计算机安装了操作系统后，易于程序设计人员在逻辑上编

写程序，方便了用户使用。

三、操作系统的定义

操作系统可以定义为如下3个方面的程序集合：

1、控制和管理计算机系统的硬件和软件资源;

2、合理地组织计算机的工作流程；备课札记

3、方便用户的使用。

1.2操作系统的发展史和分类

一、操作系统的发展简史

二、操作系统分类

迄今为止，各类操作系统均属于下列操作系统之一或它们的组

介.

1、单用户（微机）操作系统；

2、批处理系统；

3、分时系统；

4、实时系统；

5、网络操作系统；

6、分布式操作系统；

7、多处理机操作系统；

其中前4类操作系统的运行环境以单处理机系统为主，后3类以多

计算机系统为主。备课札记

1.3操作系统的特征与功能

一、操作系统的特征

1并发(Concurrence)

指宏观上在一段时间内有多道程序在同时运行，而微观上

这些程序是在交替执行。

*注意区分并行。并行是指两个或多个事件在同一时刻发

生。

2^共享(Sharing)-------------

程序的并发执行使系统中的全部资源不在为某个程序所独

占，而是有多个程序共同使用。

3、虚拟(Virtual)

多道程序设计技术把一台物理计算机虚拟为多台逻辑上的

计算机，使的每个用户都感觉是“独占”计算机。

4、异步性(Asynchronism)-------------

指一组事件在多次出现时，它们出现的时间和次序没有一

定规律。多道程序环境下，指每道持续均以人们不可预知的速

度向前推进。

其中并发和共享是操作系统的两个基本特征。

二、操作系统的功能

五大管理功能：

1、进程管理一处理机管理

主要任务：对处理机的分配和运行实施有效的管理。

2、存储器管理

主要任务：对内存进行分配、保护和扩充。

3、设备管理

主要任务：根据设备分配原则对设备进行分配，使设备与

主机并行工作，为用户提供良好的设备使用界面。

4、文件管理

主要任务：有效地管理文件的存储空间，合理地组织和管

理文件系统，为文件访问和文件保护提供良好的使用手段。

5、作业管理

作业：是用户需要计算机完成任务的总和。

主要任务：根据用户要求对作业的运行进行合理的组织和

控制。

1.4操作家统.结构设计模式

1、模块化结构模式

备课札记

系统由许多标准的、可兼容的基本单位（模块）构成。各模块

功能独立，可以单独设计，模块之间通过规定的接口相互调用。

系统开发周期短，但模块之间调用关系复杂、相互依赖，使分

析、移植和维护系统较为困难。

2、层次化结构模式

把操作系统分成许多基本的模块，并将这些模块按照某种逻辑

关系进行分层，各层之间只能单向依赖，即上层软件基于下层之

后，不能构成循环。

整个系统的正确性由各层次的正确性来保证，易于保证可靠性,

也便于维护和移植。

3、客户/服务器结构模式

操作系统的基本功能构成了内核。用户进程（即客户进程）向

服务器进程发出请求，服务器进程完成操作后，把结果返回给客

户进程。服务器进程运行在用户态下而不是核心态下。

4、对象模式

利用面向对象技术设计的操作系统。

5、对称多处理模式

操作系统工作在所有的处理机上且共享同一内存。

1.5主要操作系统的介绍

一、Windows系列

个人操作系统商用操作系统

1985Windows1.0

1987Windows2.0

1990Windows3.0

1993Windows3.XWindowsNT3.1（NT第1版）1993

WindowsNT3.5（NT第2版）1994

1995Windows95WindowsNTs.51（NT第3版）1995

WindowsNT4.0（NT第4版）1996

1998Windows98WindowsCE1998

2000WindowsMEWindows2000（NT5.0）2000

2001WindowsXP

二、UNIX系列备课札记

三、Linux发展

Linux是由LinusTorvalds于1991年开发的。

1991年9月，Linux0.0.1,很不完善。

1991年10月，Linux0.0.2,第一个“正式”版本。两周后0.0.3。

1991年12月，Linux0.1.0,已经有许多人在上面工作了。

1994年3月，Linux1.0

1.6小结

操作系统是由一系列程序模块组成的，它的基本功能是资源管理和方

便用户：它管理处理机、内存、I/O设备和文件，提供用户接口。

操作系统发展40年来，主要有两个目的：第一，为程序开发和执行提

供一个方便的环境；第二，为保证计算机系统顺利执行，操作系统对各个

计算机活动进行调度。

操作系统的形成和发展是与计算机硬件发展密切相关的。

操作系统这类系统软件有自己的基本特征，这就是：并发、共享和异步性。

操作系统提供大量的服务，在最低层是系统调用，它允许正在运行的程序直接得到

操作系统的服务；在较高层，命令解释程序为用户提供请求服务的机制，而不必编写程

序

第二章进程的描述与控制

乙£要内容：

本章的重点在于建立进程的概念，深入理解进程动态性以及

进程间的相互作用。程序是静态的，进程是动态的。进程有不同

的状态，在一定的条件下发生状态变迁，每个进程有惟一的进程

控制块（PCB）,PCB是进程存在的惟一标志。

教学安排：

,理论教学；共6学时

2.1前趋图和程序执行

-、前趋图的定义

1、前趋图

前趋图是一个有向无环图。有向是指结点Pi到Pj有边，用〈Pi,Pj）表示。无

环是指在整个图中不存在循环。

2、前趋图的表示

使用两个集合来表示。一个是结点集合“P”，另一个是前趋关系（有向边）的

集合“一”。

例：

P={P1,P2,P3,P4,P5,P6,P7},

一={<P1,P2),〈Pl,P3),<P2,P4>,<P3,P5),<P4,P6),<P5,P6〉，<P6,

P7)}0

二、程序的顺序执行（单道程序设计环境）

备课札记

顺序程序活动有三个主要特点：

(1)程序所规定的动作在机器上严格地按顺序执行。备课札记

(2)只有程序本身的动作才能改变程序的运行环境。

(3)程序的执行结果与程序运行的速度无关。

上述特点概括起来就是程序顺序性、封闭性和可再现性。所谓顺序性

就是处理机的操作严格按程序所规定的顺序执行，即程序和机器执行程序

的操作一一对应。所谓封闭性就是指程序一旦运行起来，其计算结果仅取

决于程序本身；除了人为地改变运行状态或机器出现故障外，没有别的因

素能影响程序运行的过程。所谓可再现性就是当机器在同一数据集上重复

执行同一程序，每次执行都会得到相同的结果。

程序顺序执行的特征：顺序性、封闭性、可再现性

三、程序的并发执行(多道程序设计环境)

1、多道程序设计

在硬件引入通道和中断机构后，使得处理机和外部设备之间，外部设

备和外部设备之间可以并行操作。这样就引入了多道程序设计技术。

多道程序设计是在一台计算机上同时运行两个或更多个程序。从宏观

上看，系统中的多个程序都同时得到执行，从微观上看它们是在交替执行,

即程序是并发执行的。多道程序设计具有提高系统资源利用率和增加作业

吞吐量的优点。

例：(一个极端化的例子，但能说明问题)

假定有两道作业A和B都在执行，每个作业都是执行一秒钟，然后等

待一秒钟，进行数据输入，随后再执行，再等待……一直重复60次。如果

按单道方式，先执行作业A,A作完了再执行B,那么两个作业都运行完，

共需要4分钟，CPU的利用率为百分之五十。如果我们采用多道程序技术

来执行同样的作业A和B就能大大改进系统性能，作业A先运行，它运行

一秒后等待输入。此时让B运行，B运行一秒后等待输入，此时恰好A输

入完，可以运行了，……就这样在CPU上交替地运行A和B,在这种理想

的情况下，CPU不空转，其使用率升到百分之百，并且吞吐量也随之增加

了。

2、并发程序的表示

为了在高级语言以及描述程序中的并发成分，Dijkstra引出了一组并

发语句Parbegin/Parendo

具体形式：

Parbegin

S1；

S2；

Sn；

parend备课札记

其中SI,S2,…，Sn表示可以并发执行的语句。

3、程序并发执行时的特征-------

1)间断性(制约性)

并发程序在执行期间可以相互制约

2)失去封闭性

由于资源共享，所以资源状态的改变不再取决于某一个程序，

而是由并发执行的多个程序所共同决定。

3)不可再现性

失去封闭性后，对于同一个程序来说，即使初始条件相同，但

在程序重复执行时.，因资源状态受到其他并发程序的影响，每次

并不相同，所以其运行的结果可能不同。

四、程序并发执行的条件

程序的并发执行能有效的提高资源利用率和系统的吞吐量，但并

发执行也带来了“不可再现性”缺点。为了去掉这一缺点，由Bernstein-------

于1966年提出了程序并发执行的条件。

1、读集和写集

R(Pi)={al,a2,…，am},表示程序Pi在执行期间所需参考

的所有变量的集合，称“读集”。

W(Pi)={bl,b2,…，bn},表示程序Pi在执行期间要参改变一

的所有变量的集合，称“写集”。

2、程序并发执行的条件

程序Pi和Pj若满足下述条件，他们能并发执行，且具有“可再

现性”。

Bernstein条件：

R(Pi)nw(Pj)UR(PJ)nw(Pi)uw(Pi)nw(Pj)={}o

2.2进程的描述

一、进程的定义与特征

1、进程概念的引入

由于多道程序并发执行时共享系统资源，共同决定这些资源的状态，

因此系统中各程序在执行过程中就出现了相互制约的关系，程序的执行出

现“走走停停”的新状态。这些都是在程序的动态过程中发生的。而程序

本身是机器能够翻译或执行的一组动作或指令，是静止的。因此，用程序

这个静态概念已不能如实反映程序并发执行过程中的这些特征。为此，人们引入“进程”

(Process)这一概念来描述程序动态执行过程的性质。即进程就是操作系统为进行处理

机管理而引入的概念。

2、进程的定义备课札记

进程定义为：在并发环境下，程序在一个数据集合上的的执行过程。

即：进程是进程实体的运行过程。

3、进程的特征

序号特征说明

是动态概念，有一事实

上的生命期，是动态地

1动态性

产生和消亡的。

多个进程的实体能存在

2并发性于同一内存中，在一段

时间内都能运行。

作为资源申请和独立调

独立性

3度的基本单位。

各进程向前推进的速度

4异步性

是不可预知的。

程序段、数据段、控制

5结构性

结构和堆栈段等组成。

*小结：进程与程序的主要区别:

序号进程程序

1动态的静态的

是独立性的，能并发执不能并发执行

2

行

程序和进程无一一对应关系。一个程序可由多个进程

3共用；另一方面，一个进程在其活动中又可顺序地执

行

4异步运行，会相互制约程序不具备此特征

二、进程的基本状态

进程的动态性是由它的状态和转换体现出来的。

1、进程的基本状态

三种基本状态是：执行态、就绪态和阻塞态(或等待态)

(1)执行态(Running)

运行状态是指当前进程已分配到CPU,它的程序正在处理机上执行时的状态。

(2)就绪态(Ready)

就绪状态是指进程已具备运行条件，但因为其它进程正占用CPU,所

以暂时不能运行而等待分配CPU的状态。备课札记

(3)阻塞态(Blocked)------------

阻塞态是指进程因等待某种事件发生而暂时不能运行的状态。

进程的状态及其转换：如下图

2、进程状态的转换

(1)就绪一一执行

处于就绪状态的进程被调度程序选中，分配到CPU后，该进程的状态

就由就绪态变为运行态。

(2)执行一一阻塞

正在运行的进程因某个条件未满足而放弃对CPU的占用，这个进程的

状态就由运行态变为阻塞态。

(3)阻塞一一就绪

处于阻塞状态的进程所等待事件发生了，系统就把该进程的状态由阻

塞态变为就绪态。

(4)执行----就绪

正在运行的进程如用完了本次分配给它的CPU时间片，它就得从CPU

上退下来，暂停运行。该进程状态就由运行态变为就绪态.

所等待事件发生

(如I/O完成)

*小结：进程基本状态

执行态：此时正用CPU；

就绪态：可运行，但未分到CPU；

阻塞态：不能运行，等待某个外部事件发生。

在一定条件下，进程状态才发生转换

三、进程的组成

1、进程的组成

进程实体通常由程序、数据集合和PCB这三部分组成。进程的这三部分构成进程在

系统中的存在和活动的实体，有时也统称为“进程映象”。

__________备课札记

PCB

程序段

数据段

2、进程控制块的组成（ProcessControlBlock,简称PCB）

进程控制块有时也称进程描述块（ProcessDescriptor）它是进程组成中

最关键的部分。其中含有进程描述信息和控制信息，是进程动态性的集中

反映，它是系统对进程进行识别和控制的依据。用来描述进程当前的状态、

本身的特性的数据结构被称为进程控制块。

一般来说，进程控制块包括如下内容：

1）进程标识符信息

①外部标识符：进程名；

②内部标识符：进程的序号（PID）；

③其他：族系关系，UID,GID,PPID

2）处理机状态信息

当进程进行切换时一，需要保护的信息包括：通用寄存器、指令计数器、

程序状态字（PSW）和用户栈指针。

3）进程调度信息

进程状态、进程优先权、调度所需的其它信息和事件（原因）。

4）进程控制信息

程序和数据的存储情况；同步和通信机制；资源清单和链接指针。

3、进程控制块的作用：

进程控制块是进程组成中最关键的部分。每个进程有惟一的进程控制

块。操作系统根据PCB对进程实施控制和管理。

进程的动态、并发等特征是利用PCB表现出来的。

PCB是进程存在的惟一标志。

4、PCB的组织方式

有链接方式和索引方式两种。

1）链接方式

把具有相同状态的PCB,用其中的链接指针，链接成一个队列。如教

材P45图2-7所示。

2）索引方式

系统根据所有进程的状态，建立几张索引表。索引表目中，记录相应状态的PCB在

PCB表中甲地址。每张索引表的地址放在相应的专用单元中。如教材P46

图2-8所示。备课札记

2.3进程控制--------

为了防止用户程序对系统程序的破坏，系统提供了不同的处理机执行

状态，通常分为系统态（也称做管理态）和用户态两种。

1、系统态：当操作系统程序执行时，处理机处于系统态。即内核运行

在系统态下。

2、用户态：用户程序在用户态下执行。^^3

—＞操作系统内核（Kernel）

1、操作系统内核

内核是计算机硬件的第一层扩充软件。它们常住内存，对进程进行控

制、对存储器进行管理以及对设备进行管理。

内核一般由中断处理程序、各种常用设备的驱动程序以及一些运行频

率较高的模块（如时钟管理、进程调度等）组成。

2、内核的功能

1）支撑功能

•中断管理

是内核的最基本功能。是整个操作系统赖以活动的基础。

•时钟管理

是内核的基本功能。操作系统中的许多活动也都需要它。

•原语操作

所谓原语（Primitive）是机器指令的延伸，往往是为了完成某些特

定的功能而编制的一段系统程序。为保证操作的正确性，在许多机

器中规定，执行原语操作时，要屏蔽中断，以保证操作的不可分割

性，即一个操作中的所有动作要么全做，要么全不做。操作系统中

完成某些基本操作时，往往利用原语操作来实现。

2）资源管理功能

•进程管理

由于进程管理的运行频率高，所以这些模块的全部或部分功能都放

一内核'中。

•存储器管理

目的是保证存储器管理的运行速度。

•设备管理

设备管理和设备密切相关，因此其中一大部分也放在内核中。

二、进程的控制

1、进程图

进程图是用来描述进程家族关系的有向树。由父进程创建子进程，子

备课札记

进程再创建子进程，……,从而构成一棵树型的进程图。如教材P48图2-90

2、进程控制原语

内核中有很多原语，如创建进程、终止进程、阻塞进程等。

1）进程创建

•引起进程创建的事件

用户登录、作业调度、提供服务和应用请求。

•进程创建原语的主要操作过程

（1）申请一个空闲的PCB；

（2）为新进程分配资源；

（3）将进程的PCB初始化；

（4）将新进程加到就绪队列中。

2）进程终止

•引起进程终止的事件

正常终止、异常结束和外界干预。

•终止进程的主要操作过程

（1）从系统的PCB表中找到指定进程PCB；

（2）回收该进程所占用的全部资源；

（3）若该进程还有子孙进程，则还要终止其所有子孙进程，回收它们

所占用的全部资源；

（4）释放被终止进程的PCB,并从原来队列中摘走。

3）进程阻塞

正在运行的进程通过调用阻塞原语主动地把自己阻塞。

•引起进程阻塞的事件

请求系统服务、启动某种操作、新数据尚未到达和无新工作可做。

•阻塞的过程

（1）立即停止当前进程的执行；

（2）将现行进程的CPU现场送到该进程的PCB现场保护区中保存起

来，以便将来重新运行时恢复此时的现场。

（3）把该进程PCB中的现行状态由“运行”改为阻塞，把它插入到

具有相同事件的阻塞队列中。

（4）然后转到进程调度程序，重新从就绪队列中挑选一个合适进程投

入运行。

4）进程唤醒

唤醒原语执行过程：

（1）首先把被阻塞进程从相应的阻塞队列中摘下；

（2）将现行状态改为就绪态，然后把该进程插入到就绪队列中；

（3）如果被唤醒进程比运行进程有更高的优先级，则设置重新调度标备课札记

,志O

阻塞原语与唤醒原语恰好是--对相反的原语：调用前者（阻塞原语）

是自己去睡眠，调用后者（唤醒原语）是把“别人”唤醒。使用时也要成

对，前边有睡的，后边有叫醒的。否则，前者就要“长眠”了。如同两个

士兵轮流站岗值班和睡觉休息。相关者唤醒，自己不能唤醒自己。

2.4线程的基本概念

一、线程的引入

1、处理机分配单位的演变

进程的两个基本属性：一是拥有资源的独立单位；二是独立调度和分

配的基本单位。由于进程是一个资源的拥有者，所以进程在创建、终止和

切换中，系统必须为之付出较大的时空开销。于是想把这两个属性分开，

即对拥有资源的基本单位，不进行频繁的切换；而对于调度和分配的基本

单位，使其轻装运行。

3

2>

^^

多进程、每个进程一个线程多进程、每个进程多个线程

2、线程的定义

线程是进程中的一个实体，是被系统独立调度和分配的基本单位。又

称为轻型进程。

二、线程与进程的比较

1、单线程和多线程的进程模型

单线程进程模式多线程进程模式

线程线程备课札记

进程用户栈进程控制块控制块

控制块控制块用户栈用户栈

用户内核栈用户

内核栈内核栈

地址空间地址空间

2、线线程线程

程与进程

的比较

性能进程线程

进程内的线程切

换，不会引起进程

调度切换。当不同进程调度的基本单位

内的线程进行切换

时，进程进行切换。

并发性可以可以

拥有资源的独立单仅拥有能运行的基

拥有资源

位本资源

系统开销大小

三、线程的分类

线程分为用户级线程（ULT）和内核支持线程（KLT）。

1、用户级线程（ULT）

线程仅存在用户级中，对于线程的创建、撤消和切换，都不利用系统

调用来实现,因而这种线程与内核无关。

2、内核支持线程（KLT）

又称轻便进程。线程的实现依赖内核

用户空间备课札记

内核空间

2.5小结

进程可以理解为：”程序在并发环境中的执行过程。”它最基本的特征

是并发性和动态性，一个进程至少应有三种状态，它们在一定条件下相互

转化。

每一个进程都有惟一的进程控制块（PCB）,它是进程存在的惟一标志。

PCB表的物理组织方式有若干种，最常见的是线性方式、链接方式和

索引方式。

第三章进程的同步与通信

主要内容：

本章将在系统动态模型基础上讨论进程（线程）间的

同步和互斥、进程通信以及操作系统提供的相应工具。

教学安排：

理论教学；共6学时

3.1进程同步的基本概念

一、进程的同步与互斥

进程间的相互关系分为同步关系和互斥关系。

1、同步（直接制约关系）

同步是指为完成同一任务的伙伴进程间，因为需要在某些位置上协调

它们的工作而相互等待、相互交换信息所产生的制约的关系。

两者要步调协调一致，是同步关系，同时又相互牵制。

2、互斥（间接制约关系）

两个进程在逻辑上本来完全独立，毫无关系，只是由于竞争同一个物理资源而相互

制约。攵

二、临界资源和临界区备课札圮

1、临界区的定义

一次仅允许一个进程使用的这类资源称为临界资源，在每个进程中访

问临界资源的那段程序区叫临界区。

访问临界资源的程序结构描述：

repeat

Entrysection

Criticalsection；

Exitsection

Remaindersection；

Untilfalse；

2、互斥准则

•空闲让进

只要临界资源空闲，允许请求者使用。

•忙则等待

当临界资源正被进程访问，其他请求则等待，保证临界资源的

互斥访问。

•有限等待

让等待进入临界资源的进程，在等待一段有限的时间后进入临

界区，以免出现“死等”。

•让权等待

当请求进程不能进入临界区时，应立即释放处理机，以免进程

陷入“忙等”。

三、利用软件方法解决进程互斥问题

使用软件设计方法，在Entrycode和exitcode位置上设计相应

代码，实现对临界区的互斥执行。

在进行下面的讲解前，首先假设进程Pi（i=0,1）和Pj（j=l-i）。

算法］一严格轮换法

设置整形变量turn（令牌），用turn=i还是j来区分进入临界区

的进程。

Pi进程算法的描述

repeat

备课札记

WhileturnWidoskip；

Criticalsection；

Turn=j；

noncriticalsection；

untilfalse；

缺点：如果初值tum=i；则算法严格按Pi-Pj轮换使用临界资

源，即使某时刻临界区空闲（准则1空闲让进）。

算法2

为了避免出现忙等的情况，使用数组flag来记录各进程使用临

界区的情况。

Varflag：array[O..l]ofBoolean＞；

Flag[i]=true表示进程Pi正在执行其临界区。

Pi进程算法的描述

repeat

Whileflag[j]doskip；

Flag[i]=true；

Criticalsection；

Flag[i]=false；

noncriticalsection；

untilfalse；

缺点：虽然解决了算法1中的忙等，但却不能保证临界资源的

互斥使用（准则2忙则等待）。

算法3

为了解决while语句和Hag]]设置语句之间为另一进程执行留

有可乘之机的情况，交换这两个语句执行的顺序。

Pi进程算法的描述

repeat

Flag[i]=true；

Whileflag[j]doskip；

Criticalsection；

Flag[i]=false；

noncriticalsection；备课札记

untilfalse；

缺点：虽然解决了算法2中的不能互斥使用的情况，但却导致

了都不能进入的情况(准则1空闲让进)。

算法4

为了解决上述问题，同时引入两个变量，一个Hag[i]表示Pi进

程要求进入或正在执行临界区，另一个turn表示要求进入的进程编

号。

Pi进程算法的描述

repeat

Flag[i]=true；tum=j；

Whileflag[j]andturn=jdoskip；

Flag[i]=false；

Criticalsection；

noncriticalsection；

untilfalse；

缺点：能保证互斥使用，但却导致了浪费处理机资源的情况(准

则4让权等待)。

四、利用硬件方法解决进程互斥问题

使用硬件指令保证其操作的原子性，但不能满足“让权等待”。

1、Test—and一Set指令实现互斥

1)Test—and-Set指令功能

functionTS(varlock：boolean)：boolean

begin

TS=lock；

Lock=true；

End

LOCK：TRUE表示在使用；FALSE表示空闲。TS是一条指令,

执行过程，不会被打断。

2)利用TS实现进程互斥

repeat

WhileTS(lock)doskip；

Criticalsection；

lock=false；

noncriticalsection；备课札记

untilfalse；

2、利用SWAP指令实现进程互斥

1)SWAP指令功能

procedureSWAP(vara,b：boolean)

vartemp：boolean；

begin

temp=a；

a=b；

b=temp；

End

交换变量a和b的值。

2)利用SWAP实现进程互斥

Key=true；

Whilekeydoswap(key,lock)；

repeat

Criticalsection；

lock=false；

noncriticalsection；

untilfalse；

3.2信号量机制

信号量是操作系统解决进程互斥与同步的工程。

一、整型信号量机制

1、整型信号量

定义：把信号量定义为一个整型量，除初始化外，仅能通过两个原子

操作WAIT和SIGNAL来访问。

WAIT和SIGNAL的描述：

WAIT(S)：WHILE(S〈=0〉DOSKIP；

S=S-1；

SIGNAL(S)：S=S+1；

小结：

•S是正数，表示资源的个数。

•WAIT和SIGNAL是原子操作。

备课札记

•原子操作的实现一般采用屏蔽中断(适用于单处理机)或利用

TS和SWAP硬指令(适用于多处理机)实现。

•仍然不能实现让权等待。

2、利用整型信号量实现互斥问题

repeat

WAIT(S)；______

Criticalsection；

SIGNAL(S)；

noncriticalsection；

untilfalse；

3、利用整型信号量描述前趋关系

Vara,b,c：semaphore=0,0,0；

Parbegin

BeginSI；SIGNAL(a)；end；

BeginS2；SIGNAL(b)；end；

BeginWAIT(a)；WAIT(b)；S3；SIGNAL(c)；end；

BeginWAIT(c)；S4；end；

parend

二、记录型信号量机制

1、定义

typesemaphore=record

value：integer；

L：Listofprocess；

End；

其中L表示等待信号量进程的链表。

S取值为负、零和正。负和零表示阻塞进程个数，正表示现有资源的个数。

2、原子操作

WAIT(S)：S.value=S.value-1;备课札记

IfS.VALUE<0THENBLOCK(S.L);

SIGNAL(S):S.VALUE=S.VALUE+1;

IfS.VALUE<=0THENWAKEUP(S.L);

三、信号量集机制

当进程互斥使用多个临界资源时，可能出现死锁问题(在第四章中介

绍)。为了解决上述问题，引入了信号量集的技术。

1、AND型信号量集机制

就是将进程在整个运行过程中所需要的所有临界资源，一次性的全部

分配给它，待进程使用完后一次性的释放，只要尚有一个资源不能分配给一

它，则全部不能进行分配。

2、两个原子操作

SWAIT(SI,Tl,D1,...»Sn,Tn,Dn)；

其中Si表示某类资源数，Ti表示分配下限，Di表一次分配的个数。

SSIGNAL(SI,D1,...»Sn,Dn)；

其中Si表示某类资源数，Di表示回收的个数。

3.3经典进程同步问题

一、生产者——消费者问题

1、问题的提出

2、问题的解决

varmutex,full,empty：semaphore=1,0,n；

buff：array[0..n-lJofitem；

in,out：integer=0,0；

begin

parbegin备课札记

producer()；

consumer0；

parend

end

procedureproducer()procedureconsumer()

beginbegin—

repeatrepeat

produceaniteminnextp；wait(full)；

wait(empty)；wait(mutex)；

wait(mutex)；nextc=buff[outj；

buff[in]=nextp；out=(out+l)modn；

in=(in+1)modn；signal(mutex)；

signal(mutex)；signal(empty)；

signal(full)；consumetheiteminnextc；

untilfalse；untilfalse；

endend

3、小结________

MUTEX用于控制互斥访缓存池，问初值为1,表示消费者进程和生产

者进程在对缓存池使用时，按照互斥方式。

FULL用于同步控制，初值为0,表示当前缓存池中“满”缓存区数。

EMPTY用于同步控制，初值为N,表示当前缓存池中“空”缓存区数。

不论是互斥还是同步，WAIT和SIGNAL操作都配对出现。

WAIT操作不能颠倒，SIGNAL操作可以。

二、读者——写者问题

1、问题描述

有两种情况：一是READER有较高的优先权；二是WRITER有较

高的优先权。下面描述的是READER有较高优先权的情况。

1）如果当前无人访问数据，无论READER或WRITER都可直接进

入访问。

2）如果已有一个READER正在访问数据，那么其它欲访问数据的

READER可直接进行访问，而当前欲访问数据的WRITER则必须无条件等待。

3）若某个WRITER正在访问数据，则当前欲访问数据的READER和WRITER

均须等待。

4）当最后一个结束访问数据的READER发现有WRITER正在等待

时，则将其中的一个唤醒。备课札记

5）当某个WRITER结束访问数据时发现存在等待者，则按FIFO或

其他原则唤醒READER和WRITERo

2、,可题解决

varmutex,wmt：semaphore=1,1；

rcount：integer=0；

begin

parbegin

reader()；

writer0；

parend

end

procedurereader()procedurewriter()

beginbegin

repeatrepeat

wait(mutex)；wait(wmt)；

rcount=rcount+l；writingisperformed；

ifrcount==1wait(wmt)；signal(wmt)；

signal(mutex)；untilfalse；

readingisperformed；end

wait(mutex)；

rcount=rcount-l；

ifrcount==0signal(wmt)；

signal(mutex)；

untilfalse；

end

三、哲学家就餐问题

1、问题描述

有5位哲学家，他们的生活方式是交替进行思考和进餐。他们共用一

张圆桌，分别坐在5把椅子上，有5只碗和5支筷子，平时哲学家进行思

考，饥饿时便试图取其左、右两支筷子，取道后开始进餐，进餐后放下筷

子又继续思考。

2、问题解决

varmutex：array[0..4]ofsemaphore=1,1,1,1,1；

begin

parbegin备课札记

p(0)；

p(1);

p(2)；

p(3)；

p(4)；

parend

end

procedurep(vari：integer)

begin