资源简介

The Best R&D Courses
进程的描述与控制
2.1 前趋图和程序执行
　　在早期未配置OS的系统和单道批处理系统中，程序的执行方式是顺序执行，即在内存中仅装入
一道用户程序，由它独占系统中的所有资源，只有在一个用户程序执行完成后，才允许装入另一个
程序并执行。可见，这种方式浪费资源、系统运行效率低等缺点
The Best R&D Courses
进程的描述与控制
2.1.1 前趋图
　　为了能更好地描述程序的顺序和并发执行情况，我们先介绍用于描述程序执行先后顺序的前趋
图。所谓前趋图(Precedence Graph)，是指一个有向无循环图，可记为DAG(Directed Acyclic
Graph)，它用于描述进程之间执行的先后顺序。图中的每个结点可用来表示一个进程或程序段，乃
至一条语句，结点间的有向边则表示两个结点之间存在的偏序(Partial Order)或前趋关系
(Precedence Relation)。
The Best R&D Courses
进程的描述与控制
　　进程(或程序)之间的前趋关系可用“→”来表示，如果进程Pi和Pj存在着前趋关系，可表示为(Pi，
Pj)∈→，也可写成Pi→Pj，表示在Pj开始执行之前Pi 必须完成。此时称Pi是Pj的直接前趋，而称Pj
是Pi的直接后继。在前趋图中，把没有前趋的结点称为初始结点(Initial Node)，把没有后继的结点
称为终止结点(Final Node)。此外，每个结点还具有一个重量(Weight)，用于表示该结点所含有的程
序量或程序的执行
时间。
The Best R&D Courses
进程的描述与控制
　　在右图所示的前趋图中，存在着如下前趋关
系：
　　P1→P2，P1→P3，P1→P4，P2→P5，
P3→P5，P4→P6，P4→P7，P5→P8，P6→P8，
P7→P9，P8→P9
或表示为：
　P={P1, P2, P3, P4, P5, P6, P7, P8, P9}
　 ={(P1, P2), (P1, P3), (P1, P4), (P2, P5),
(P3, P5), (P4, P6), (P4, P7), (P5, P8), (P6,
P8), (P7, P9), (P8, P9)}
The Best R&D Courses
进程的描述与控制
　　应当注意，前趋图中是不允许有循环的，否则必然会产生不可能实现的前趋关系。如下图所示
的前趋关系中就存在着循环。它一方面要求在S3开始执行之前，S2必须完成，另一方面又要求在S2
开始执行之前，S3必须完成。显然，这种关系是不可能实现的。
　　　　　　　　　S2→S3，S3→S2
The Best R&D Courses
进程的描述与控制
2.1.2 程序顺序执行
　　1. 程序的顺序执行
　　通常，一个应用程序由若干个程序段组成，每一个程序段完成特定的功能，它们在执行时，都
需要按照某种先后次序顺序执行，仅当前一程序段执行完后，才运行后一程序段。例如，在进行计
算时，应先运行输入程序，用于输入用户的程序和数据；然后运行计算程序，对所输入的数据进行
计算；最后才是运行打印程序，打印计算结果。我们用结点(Node)代表各程序段的操作(在前图中用
圆圈表示)，其中I代表输入操作，C代表计算操作，P为打印操作，用箭头指示操作的先后次序。
The Best R&D Courses
进程的描述与控制
　　这样，上述的三个程序段间就存在着这样的前趋关系：Ii→Ci→Pi，其执行的顺序可用上面的前
趋图描述。
　　即使是一个程序段，也可能存在着执行顺序问题，下面示出了一个包含了三条语句的程序段：
　　S1: a :=x+y；
　　S2: b :=a-5；
　　S3: c :=b+1；
其中，语句S2必须在语句S1后(即a被赋值)才能执行，语句S3也只能在b被赋值后才能执行，因此，
三条语句存在着这样的前趋关系：S1→S2→S3，应按下面前趋图所示的顺序执行。
The Best R&D Courses
进程的描述与控制
　　2. 程序顺序执行时的特征
　　由上所述可以得知，在程序顺序执行时，具有这样三个特征：① 顺序性：指处理机严格地按照
程序所规定的顺序执行，即每一操作必须在下一个操作开始之前结束；② 封闭性：指程序在封闭的
环境下运行，即程序运行时独占全机资源，资源的状态(除初始状态外)只有本程序才能改变它，程序
一旦开始执行，其执行结果不受外界因素影响；③ 可再现性：指只要程序执行时的环境和初始条件
相同，当程序重复执行时，不论它是从头到尾不停顿地执行，还是“停停走走”地执行，都可获得
相同的结果。程序顺序执行时的这种特性，为程序员检测和校正程序的错误带来了很大的方便。
The Best R&D Courses
进程的描述与控制
2.1.3　程序并发执行
　　1. 程序的并发执行
　　我们通过一个常见的例子来说明程序的顺序执行和并发执行。在图2-2中的输入程序、计算程序
和打印程序三者之间，存在着Ii→Ci→Pi这样的前趋关系，以至对一个作业的输入、计算和打印三个
程序段必须顺序执行。但若是对一批作业进行处理时，每道作业的输入、计算和打印程序段的执行
情况如下图（程序并发执行时的前趋图）所示。
The Best R&D Courses
进程的描述与控制
　　由前图可以看出，存在前趋关系Ii→Ci，Ii→Ii+1，Ci→Pi，Ci→Ci+1，Pi→Pi+1，而Ii+1和Ci及
Pi-1是重叠的，即在Pi-1和Ci以及Ii+1之间，不存在前趋关系，可以并发执行。
　　对于具有下述四条语句的程序段：
　　S1: a :=x+2
　　S2: b :=y+4
　　S3: c :=a+b
　　S4: d :=c+b
　　右图所示的前趋关系。可以看出：S3必须在a和b被赋值后方能执行；S4必须在S3之后执行；但
S1和S2则可以并发执行，因为它们彼此互不依赖。
The Best R&D Courses
进程的描述与控制
　　2. 程序并发执行时的特征
　　在引入了程序间的并发执行功能后，虽然提高了系统的吞吐量和资源利用率，但由于它们共享
系统资源，以及它们为完成同一项任务而相互合作，致使在这些并发执行的程序之间必将形成相互
制约的关系，由此会给程序并发执行带来新的特征。
　　(1) 间断性。
　　(2) 失去封闭性。
　　(3) 不可再现性。
The Best R&D Courses
进程的描述与控制
2.2 进 程 的 描 述
2.2.1 进程的定义和特征
　　1. 进程的定义
　　在多道程序环境下，程序的执行属于并发执行，此时它们将失去其封闭性，并具有间断性，以
及其运行结果不可再现性的特征。由此，决定了通常的程序是不能参与并发执行的，否则，程序的
运行也就失去了意义。为了能使程序并发执行，并且可以对并发执行的程序加以描述和控制，人们
引入了“进程”的概念。
The Best R&D Courses
进程的描述
　　对于进程的定义，从不同的角度可以有不同的定义，其中较典型的定义有：
　　(1) 进程是程序的一次执行。
　　(2) 进程是一个程序及其数据在处理机上顺序执行时所发生的活动。
　　(3) 进程是具有独立功能的程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的
一个独立单位。
The Best R&D Courses
进程的描述
　　2. 进程的特征
　　进程和程序是两个截然不同的概念，除了进程具有程序所没有的PCB结构外，还具有下面一些
特征：
　　(1) 动态性。
　　(2) 并发性。
　　(3) 独立性。
　　(4) 异步性。
The Best R&D Courses
进程的描述
2.2.2 进程的基本状态及转换
　　1. 进程的三种基本状态
　　由于多个进程在并发执行时共享系统资源，致使它们在运行过程中呈现间断性的运行规律，所
以进程在其生命周期内可能具有多种状态。一般而言，每一个进程至少应处于以下三种基本状态之
一：
　　(1) 就绪(Ready)状态。
　　(2) 执行(Running)状态。
　　(3) 阻塞(Block)状态。
The Best R&D Courses
进程的描述
　　2. 三种基本状态的转换
　　进程在运行过程中会经常发生状态的转换。例如，处于就绪状态的进程，在调度程序为之分配
了处理机之后便可执行，相应地，其状态就由就绪态转变为执行态；正在执行的进程(当前进程)如
果因分配给它的时间片已完而被剥夺处理机暂停执行时，其状态便由执行转为就绪；如果因发生某
事件，致使当前进程的执行受阻(例如进程访问某临界资源，而该资源正被其它进程访问时)，使之
无法继续执行，则该进程状态将由执行转变为阻塞。右图示出了进程的三种基本状态，以及各状态
之间的转换关系。
The Best R&D Courses
进程的描述
　　3. 创建状态和终止状态
　　1) 创建状态
　　如前所述，进程是由创建而产生。创建一个进程是个很复杂的过程，一般要通过多个步骤才能
完成：如首先由进程申请一个空白PCB，并向PCB中填写用于控制和管理进程的信息；然后为该进
程分配运行时所必须的资源；最后，把该进程转入就绪状态并插入就绪队列之中。但如果进程所需
的资源尚不能得到满足，比如系统尚无足够的内存使进程无法装入其中，此时创建工作尚未完成，
进程不能被调度运行，于是把此时进程所处的状态称为创建状态。
The Best R&D Courses
进程的描述
　　2) 终止状态
　　进程的终止也要通过两个步骤：首先，是等待操作系统进行善后处理，最后将其PCB清零，并
将PCB空间返还系统。当一个进程到达了自然结束点，或是出现了无法克服的错误，或是被操作系
统所终结，或是被其他有终止权的进程所终结，它将进入终止状态。进入终止态的进程以后不能再
执行，但在操作系统中依然保留一个记录，其中保存状态码和一些计时统计数据，供其他进程收集。
一旦其他进程完成了对其信息的提取之后，操作系统将删除该进程，即将其PCB清零，并将该空白
PCB返还系统。图2-6示出了增加了创建状态和终止状态后进程的五种状态及转换关系图。
The Best R&D Courses
进程的描述
The Best R&D Courses
进程的描述
2.2.3 挂起操作和进程状态的转换
　　1. 挂起操作的引入
　　引入挂起操作的原因，是基于系统和用户的如下需要：
　　(1) 终端用户的需要。
　　(2) 父进程请求。
　　(3) 负荷调节的需要。
　　(4) 操作系统的需要。
The Best R&D Courses
进程的描述
　　2. 引入挂起原语操作后三个进程状态的转换
　　在引入挂起原语Suspend和激活原语Active后，在它们的作用下，进程将可能发生以下几种状
态的转换：
　　(1) 活动就绪→静止就绪。
　　(2) 活动阻塞→静止阻塞。
　　(3) 静止就绪→活动就绪。
　　(4) 静止阻塞→活动阻塞。
The Best R&D Courses
进程的描述
　　3. 引入挂起操作后五个进程状态的转换
　　如右图示出了增加了创建状态和终止状态后具有挂起状态的进程状态及转换图。
　　如右图所示，引进创建和终止状态后，在进程状态转换时，与前图的进程五状态转换相比较，
要增加考虑下面的几种情况：
　　(1) NULL→创建：
　　(2) 创建→活动就绪：
　　(3) 创建→静止就绪：
　　(4) 执行→终止：
The Best R&D Courses
进程的描述
2.2.4 进程管理中的数据结构
　　1. 操作系统中用于管理控制的数据结构
　 在计算机系统中，对于每个资源和每个进程都设置了一个数据结构，用于表征其实体，我们
称之为资源信息表或进程信息表，其中包含了资源或进程的标识、描述、状态等信息以及一批指针。
通过这些指针，可以将同类资源或进程的信息表，或者同一进程所占用的资源信息表分类链接成不
同的队列，便于操作系统进行查找。
The Best R&D Courses
进程的描述
OS管理的这些数据结构一般分为以下四类：内存表、设备表、文件表和用于进程管理的进程表，通
常进程表又被称为进程控制块PCB。
The Best R&D Courses
进程的描述
2. 进程控制块PCB的作用
(1) 作为独立运行基本单位的标志。
(2) 能实现间断性运行方式。
(3) 提供进程管理所需要的信息。
(4) 提供进程调度所需要的信息。
(5) 实现与其它进程的同步与通信。
The Best R&D Courses
进程的描述
　　3. 进程控制块中的信息
　　在进程控制块中，主要包括下述四个方面的信息。
　　1) 进程标识符
　　进程标识符用于唯一地标识一个进程。一个进程通常有两种标识符：
　　(1) 外部标识符。
　　(2) 内部标识符。
　　2) 处理机状态
　　处理机状态信息也称为处理机的上下文，主要是由处理机的各种寄存器中的内容组成的。
The Best R&D Courses
进程的描述
　　3) 进程调度信息
　　在OS进行调度时，必须了解进程的状态及有关进程调度的信息，这些信息包括：① 进程状态，
指明进程的当前状态，它是作为进程调度和对换时的依据；② 进程优先级，是用于描述进程使用处
理机的优先级别的一个整数，优先级高的进程应优先获得处理机；③ 进程调度所需的其它信息，它
们与所采用的进程调度算法有关，比如，进程已等待CPU的时间总和、进程已执行的时间总和等；
④ 事件，是指进程由执行状态转变为阻塞状态所等待发生的事件，即阻塞原因。
The Best R&D Courses
进程的描述
　　4) 进程控制信息
　　是指用于进程控制所必须的信息，它包括：① 程序和数据的地址，进程实体中的程序和数据的
内存或外存地(首)址，以便再调度到该进程执行时，能从PCB中找到其程序和数据；② 进程同步和
通信机制，这是实现进程同步和进程通信时必需的机制，如消息队列指针、信号量等，它们可能全
部或部分地放在PCB中；③ 资源清单，在该清单中列出了进程在运行期间所需的全部资源(除CPU
以外)，另外还有一张已分配到该进程的资源的清单；④ 链接指针，它给出了本进程(PCB)所在队列
中的下一个进程的PCB的首地址。
The Best R&D Courses
进程的描述
　　4. 进程控制块的组织方式
　　在一个系统中，通常可拥有数十个、数百个乃至数千个PCB。为了能对它们加以有效的管理，
应该用适当的方式将这些PCB组织起来。目前常用的组织方式有以下三种。
(1) 线性方式，即将系统中所有的PCB都组织在一张线性表中，将该表的首址存放在内存的一个专用
区域中。该方式实现简单、开销小，但每次查找时都需要扫描整张表，因此适合进程数目不多的系
统。下图示出了线性表的PCB组织方式。
The Best R&D Courses
进程的描述
　　(2) 链接方式，即把具有相同状态进程的PCB分别通过PCB中的链接字链接成一个队列。这样，
可以形成就绪队列、若干个阻塞队列和空白队列等。对就绪队列而言，往往按进程的优先级将PCB
从高到低进行排列，将优先级高的进程PCB排在队列的前面。同样，也可把处于阻塞状态进程的
PCB根据其阻塞原因的不同，排成多个阻塞队列，如等待I/O操作完成的队列和等待分配内存的队列
等。图2-11示出了一种链接队列的组织方式。
The Best R&D Courses
进程的描述
　　(3) 索引方式，即系统根据所有进程状态的不同，建立几张索引表，例如，就绪索引表、阻塞索
引表等，并把各索引表在内存的首地址记录在内存的一些专用单元中。在每个索引表的表目中，记
录具有相应状态的某个PCB在PCB表中的地址。下图示出了索引方式的PCB组织。
The Best R&D Courses
进程控制
　　　　　2.3 进 程 控 制
　　进程控制是进程管理中最基本的功能，主要包括创建新进程、终止已完成的进程、将因发生异
常情况而无法继续运行的进程置于阻塞状态、负责进程运行中的状态转换等功能。如当一个正在执
行的进程因等待某事件而暂时不能继续执行时，将其转变为阻塞状态，而在该进程所期待的事件出
现后，又将该进程转换为就绪状态等。进程控制一般是由OS的内核中的原语来实现的。
The Best R&D Courses
进程控制
2.3.1 操作系统内核
　　1. 支撑功能
　　(1) 中断处理。
　　(2) 时钟管理。
　　(3) 原语操作。
The Best R&D Courses
进程控制
　　2. 资源管理功能
　　(1) 进程管理。
　　(2) 存储器管理。
　　(3) 设备管理。
The Best R&D Courses
进程控制
2.3.2 进程的创建
　　1. 进程的层次结构
　　在OS中，允许一个进程创建另一个进程，通常把创建进程的进程称为父进程，而把被创建的进
程称为子进程。子进程可继续创建更多的孙进程，由此便形成了一个进程的层次结构。如在UNIX中，
进程与其子孙进程共同组成一个进程家族(组)。
The Best R&D Courses
进程控制
　　2. 进程图
　　为了形象地描述一个进程的家族关系而引入了进程
图(Process Graph)。所谓进程图就是用于描述进程间
关系的一棵有向树，如右图所示。
The Best R&D Courses
进程控制
　　3. 引起创建进程的事件
　　为使程序之间能并发运行，应先为它们分别创建进程。导致一个进程去创建另一个进程的典型
事件有四类：
　　(1) 用户登录。
　　(2) 作业调度。
　　(3) 提供服务。
　　(4) 应用请求。
The Best R&D Courses
进程控制
　　4. 进程的创建(Creation of Process)
　　在系统中每当出现了创建新进程的请求后，OS便调用进程创建原语Creat按下述步骤创建一个
新进程：
　　(1) 申请空白PCB，为新进程申请获得唯一的数字标识符，并从PCB集合中索取一个空白PCB。
　　(2) 为新进程分配其运行所需的资源，包括各种物理和逻辑资源，如内存、文件、I/O设备和
CPU时间等。
　　(3) 初始化进程控制块(PCB)。
　　(4) 如果进程就绪队列能够接纳新进程，便将新进程插入就绪队列。
The Best R&D Courses
进程控制
2.3.3 进程的终止
　　1. 引起进程终止(Termination of Process)的事件
　　(1) 正常结束
　　(2) 异常结束
　　(3) 外界干预
The Best R&D Courses
进程控制
　　2. 进程的终止过程
　　如果系统中发生了要求终止进程的某事件，OS便调用进程终止原语，按下述过程去终止指定的
进程：
　　(1) 根据被终止进程的标识符，从PCB集合中检索出该进程的PCB，从中读出该进程的状态；
　　(2) 若被终止进程正处于执行状态，应立即终止该进程的执行，并置调度标志为真，用于指示该
进程被终止后应重新进行调度；
The Best R&D Courses
进程控制
　　(3) 若该进程还有子孙进程，还应将其所有子孙进程也都予以终止，以防它们成为不可控的进程；
　　(4) 将被终止进程所拥有的全部资源或者归还给其父进程，或者归还给系统；
　　(5) 将被终止进程(PCB)从所在队列(或链表)中移出，等待其它程序来搜集信息。
The Best R&D Courses
进程控制
2.3.4 进程的阻塞与唤醒
　　1. 引起进程阻塞和唤醒的事件
　　有下述几类事件会引起进程阻塞或被唤醒：
　　(1) 向系统请求共享资源失败。
　　(2) 等待某种操作的完成。
　　(3) 新数据尚未到达。
　　(4) 等待新任务的到达。
The Best R&D Courses
进程控制
　　2. 进程阻塞过程
　　正在执行的进程，如果发生了上述某事件，进程便通过调用阻塞原语block将自己阻塞。可见，
阻塞是进程自身的一种主动行为。进入block过程后，由于该进程还处于执行状态，所以应先立即停
止执行，把进程控制块中的现行状态由“执行”改为阻塞，并将PCB插入阻塞队列。如果系统中设
置了因不同事件而阻塞的多个阻塞队列，则应将本进程插入到具有相同事件的阻塞队列。最后，转
调度程序进行重新调度，将处理机分配给另一就绪进程，并进行切换，亦即，保留被阻塞进程的处
理机状态，按新进程的PCB中的处理机状态设置CPU的环境。
The Best R&D Courses
进程控制
　　3. 进程唤醒过程
　　当被阻塞进程所期待的事件发生时，比如它所启动的I/O操作已完成，或其所期待的数据已经到
达，则由有关进程(比如提供数据的进程)调用唤醒原语wakeup，将等待该事件的进程唤醒。
wakeup执行的过程是：首先把被阻塞的进程从等待该事件的阻塞队列中移出，将其PCB中的现行状
态由阻塞改为就绪，然后再将该PCB插入到就绪队列中。
The Best R&D Courses
进程同步
　　　　　2.4　进 程 同 步
　　在OS中引入进程后，一方面可以使系统中的多道程序并发执行，这不仅能有效地改善资源利用
率，还可显著地提高系统的吞吐量，但另一方面却使系统变得更加复杂。如果不能采取有效的措施，
对多个进程的运行进行妥善的管理，必然会因为这些进程对系统资源的无序争夺给系统造成混乱。
致使每次处理的结果存在着不确定性，即显现出其不可再现性。
The Best R&D Courses
进程同步
2.4.1　进程同步的基本概念
　　1. 两种形式的制约关系
　　1) 间接相互制约关系
　　2) 直接相互制约关系
　　2. 临界资源(Critical Resouce)
　　在第一章中我们曾经介绍过，许多硬件资源如打印机、 磁带机等，都属于临界资源，诸进程间
应采取互斥方式，实现对这种资源的共享
The Best R&D Courses
进程同步
　　3. 临界区(critical section)
　　由前所述可知，不论是硬件临界资源还是软件临界资源，多个进程必须互斥地对它进行访问。
人们把在每个进程中访问临界资源的那段代码称为临界区(critical section)。
若能保证诸进程互斥地进入自己的临界区，便可实现诸进程
while(true){ 对临界资源的互斥访问。为此，每个进程在进入临界区之前，
进入区 应先对欲访问的临界资源进行检查，看它是否正被访问。如
临界区 果此刻临界资源未被访问，进程便可进入临界区对该资源进
退出区 行访问，并设置它正被访问的标志；如果此刻该临界资源正被某进程访问，则本进程不能进入临界区。因此，必领在临
剩余区 界区前面增加一段用于进行上达检查的代码，把这段代码称
} 为进入区(entry secion)。相应地，在临界区后面也要加上一
段称为退出区(exit section)的代码，用于将临界区正被访问的
标志恢复为末被访问的标志。进程中除上述进入区、临界区
及退出区之外的其它部分的代码在这里都称为剩余区。
The Best R&D Courses
进程同步
　　4. 同步机制应遵循的规则
　　为实现进程互斥地进入自己的临界区，可用软件方法，更多的是在系统中设置专门的同步机构
来协调各进程间的运行。所有同步机制都应遵循下述四条准则：
　　(1) 空闲让进。
　　(2) 忙则等待。
　　(3) 有限等待。
　　(4) 让权等待。
The Best R&D Courses
进程同步
2.4.2 硬件同步机制
　　虽然可以利用软件方法解决诸进程互斥进入临界区的问题，但有一定难度，并且存在很大的局
限性，因而现在已很少采用。相应地，目前许多计算机已提供了一些特殊的硬件指令，允许对一个
字中的内容进行检测和修正，或者是对两个字的内容进行交换等。可利用这些特殊的指令来解决临
界区问题。
The Best R&D Courses
进程同步
　　关中断
　　关中断是实现互斥的最简单的方法之一。在进入锁测试之前关闭中断，直到完成锁测试并上锁
之后才能打开中断。这样，进程在临界区执行期间，计算机系统不响应中断，从而不会引发调度，
也就不会发生进程或线程切换。由此，保证了对锁的测试和关锁操作的连续性和完整性，有效地保
证了互斥。但是，关中断的方法存在许多缺点：① 滥用关中断权力可能导致严重后果；② 关中断
时间过长，会影响系统效率，限制了处理器交叉执行程序的能力；③ 关中断方法也不适用于多CPU
系统，因为在一个处理器上关中断并不能防止进程在其它处理器上执行相同的临界段代码。
The Best R&D Courses
进程同步
2.4.3　信号量机制
　　1. 整型信号量
　　最初由Dijkstra把整型信号量定义为一个用于表示资源数目的整型量S，它与一般整型量不同，除初始
化外，仅能通过两个标准的原子操作(Atomic Operation) wait(S)和signal(S)来访问。很长时间以来，这
两个操作一直被分别称为P、V操作。
与普通整数变量的区别：对信号量的操作只有三种，即 初始化、P操作、V操作
The Best R&D Courses
进程同步
wait函数将 “检查” 和 “上锁” 一气呵成，
避免了并发、异步导致的问题。但存在存在的
问题：不满足“让权等待”原则，会发生“忙
等”。
The Best R&D Courses
进程同步
　　2. 记录型信号量
　　在整型信号量机制中的wait操作，只要是信号量S≤0，就会不断地测试。因此，该机制并未遵
循“让权等待”的准则，而是使进程处于“忙等”的状态。记录型信号量机制则是一种不存在“忙
等”现象的进程同步机制。但在采取了“让权等待”的策略后，又会出现多个进程等待访问同一临
界资源的情况。为此，在信号量机制中，除了需要一个用于代表资源数目的整型变量value外，还应
增加一个进程链表指针list，用于链接上述的所有等待进程。
The Best R&D Courses
进程同步
The Best R&D Courses
进程同步
2.4.4　信号量的应用
　　1. 利用信号量实现进程互斥
　　为使多个进程能互斥地访问某临界资源，只需为该资源设置一互斥信号量mutex，并设其初始值
为1，然后将各进程访问该资源的临界区CS置于wait(mutex)和signal(mutex)操作之间即可。
The Best R&D Courses
进程同步
　　2. 利用信号量实现前趋关系
　　还可利用信号量来描述程序或语句之间的前趋关系。设有两个并发执行的进程P1和P2。P1中有
语句S1；P2中有语句S2。我们希望在S1执行后再执行S2。为实现这种前趋关系，只需使进程P1和
P2共享一个公用信号量S，并赋予其初值为0，将signal(S)操作放在语句S1后面，而在S2语句前面
插入wait(S)操作，即
　　在进程P1中，用S1；signal(S)；
　　在进程P2中，用wait(S)；S2；
The Best R&D Courses
进程同步
　　由于S被初始化为0，这样，若P2先执行必定阻塞，只有在进程P1执行完S1； signal(S)；操作
后使S增为1时，P2进程方能成功执行语句S2。同样，我们可以利用信号量按照语句间的前趋关系
(见图2-14)，写出一个更为复杂的可并发执行的程序。
The Best R&D Courses
进程同步
2.4.5　管程机制
　　1．管程的定义
　　系统中的各种硬件资源和软件资源均可用数据结构抽象地描述其资
源特性，即用少量信息和对该资源所执行的操作来表征该资源，而忽略
它们的内部结构和实现细节。
　　由上述的定义可知，管程由四部分组成：① 管程的名称；② 局部
于管程的共享数据结构说明；③ 对该数据结构进行操作的一组过程；④
对局部于管程的共享数据设置初始值的语句。右图是一个管程的示意图。
The Best R&D Courses
进程同步
　　2. 条件变量
　　在利用管程实现进程同步时，必须设置同步工具，如两个同步操作原语wait和signal。当某进程
通过管程请求获得临界资源而未能满足时，管程便调用wait原语使该进程等待，并将其排在等待队列
上，如图2-13所示。仅当另一进程访问完成并释放该资源之后，管程才又调用signal原语，唤醒等待
队列中的队首进程。
The Best R&D Courses
进程同步
　　　 2.5　经典进程的同步问题
　　在多道程序环境下，进程同步问题十分重要，也是相当有趣的问题，因而吸引了不少学者对它
进行研究，由此而产生了一系列经典的进程同步问题，其中较有代表性的是“生产者—消费者”问
题、“读者—写者问题”、“哲学家进餐问题”等等。通过对这些问题的研究和学习，可以帮助我
们更好地理解进程同步的概念及实现方法。
The Best R&D Courses
进程同步
2.5.1　生产者-消费者问题
　　1. 利用记录型信号量解决生产者-消费者问题
　　假定在生产者和消费者之间的公用缓冲池中具有n个缓冲区，这
时可利用互斥信号量mutex实现诸进程对缓冲池的互斥使用；利用信
号量empty和full分别表示缓冲池中空缓冲区和满缓冲区的数量。又
假定这些生产者和消费者相互等效，只要缓冲池未满，生产者便可将
消息送入缓冲池；只要缓冲池未空，消费者便可从缓冲池中取走一个
消息。
The Best R&D Courses
进程同步
　　2. 利用AND信号量解决生产者-消费者问题
　　对于生产者-消费者问题，也可利用AND信号量来解决，
即用Swait(empty，mutex)来代替wait(empty)和
wait(mutex)；用Ssignal(mutex，full)来代替signal(mutex)
和signal(full)；用Swait(full，mutex)代替wait(full)和
wait(mutex)，以及用Ssignal(mutex，empty)代替
Signal(mutex)和Signal(empty)。
The Best R&D Courses
进程同步
　　3. 利用管程解决生产
者-消费者问题
　　在利用管程方法来解
决生产者-消费者问题时，
首先便是为它们建立一个
管程，并命名为
procducerconsumer，
或简称为PC。其中包括
两个过程：
　　(1) put(x)过程。
　　(2) get(x)过程。
The Best R&D Courses
进程同步
　　对于条件变量notfull和notempty，分别有两个过程cwait和csignal对它们进行操作：
　　(1) cwait(condition)过程：当管程被一个进程占用时，其他进程调用该过程时阻塞，并挂在条
件condition的队列上。
　　(2) csignal(condition)过程：唤醒在cwait执行后阻塞在条件condition队列上的进程，如果这
样的进程不止一个，则选择其中一个实施唤醒操作；如果队列为空，则无操作而返回。
The Best R&D Courses
进程同步
2.5.2　哲学家进餐问题
　　1. 利用记录型信号量解决哲学家进餐问题
　　经分析可知，放在桌子上的筷子是临界资
源，在一段时间内只允许一位哲学家使用。为
了实现对筷子的互斥使用，可以用一个信号量
表示一只筷子，由这五个信号量构成信号量数
组。
The Best R&D Courses
The Best R&D Courses
进程同步
　　2. 利用AND信号量机制解决哲学家
进餐问题
　　在哲学家进餐问题中，要求每个哲学
家先获得两个临界资源(筷子)后方能进餐，
这在本质上就是前面所介绍的AND同步
问题，故用AND信号量机制可获得最简
洁的解法。
The Best R&D Courses
进程同步
2.5.3　读者-写者问题
　　利用记录型信号量解决读者-写者问题
　　为实现Reader与Writer进程间在读或写时的互斥而设置了一个互斥信号量Wmutex。另外，再
设置一个整型变量Readcount表示正在读的进程数目。由于只要有一个Reader进程在读，便不允许
Writer进程去写。因此，仅当Readcount=0，表示尚无Reader进程在读时，Reader进程才需要执
行Wait(Wmutex)操作。若wait(Wmutex)操作成功，Reader进程便可去读，相应地，做
Readcount+1操作。
The Best R&D Courses
The Best R&D Courses
进程通信
　　　　2.6 进 程 通 信
　　进程通信是指进程之间的信息交换。由于进程的互斥与同步，需要在进程间交换一定的信息，
故不少学者将它们也归为进程通信，但只能把它们称为低级进程通信。我们以信号量机制为例来说
明，它们之所以低级的原因在于：① 效率低，生产者每次只能向缓冲池投放一个产品(消息)，消费
者每次只能从缓冲区中取得一个消息；② 通信对用户不透明，OS只为进程之间的通信提供了共享
存储器。
The Best R&D Courses
进程通信
　　在进程之间要传送大量数据时，应当利用OS提供的高级通信工具，该工具最主要的特点是：
　　(1) 使用方便。OS隐藏了实现进程通信的具体细节，向用户提供了一组用于实现高级通信的命
令(原语)，用户可方便地直接利用它实现进程之间的通信。或者说，通信过程对用户是透明的。这样
就大大减少了通信程序编制上的复杂性。
　　(2) 高效地传送大量数据。用户可直接利用高级通信命令(原语)高效地传送大量的数据。
The Best R&D Courses
进程通信
2.6.1　进程通信的类型
　　1. 共享存储器系统(Shared-Memory System)
　　在共享存储器系统中，相互通信的进程共享某些数据结构或共享存储区，进程之间能够通过这
些空间进行通信。据此，又可把它们分成以下两种类型：
　　(1) 基于共享数据结构的通信方式。
　　(2) 基于共享存储区的通信方式。
The Best R&D Courses
进程通信
　　2. 管道(pipe)通信系统
　　所谓“管道”，是指用于连接一个读进程和一个写进程以实现它们之间通信的一个共享文件，
又名pipe文件。向管道(共享文件)提供输入的发送进程(即写进程)以字符流形式将大量的数据送入管
道；而接受管道输出的接收进程(即读进程)则从管道中接收(读)数据。由于发送进程和接收进程是利
用管道进行通信的，故又称为管道通信。这种方式首创于UNIX系统，由于它能有效地传送大量数据，
因而又被引入到许多其它操作系统中。
The Best R&D Courses
进程通信
　　为了协调双方的通信，管道机制必须提供以下三方面的协调能力：① 互斥，即当一个进程正在
对pipe执行读/写操作时，其它(另一)进程必须等待。② 同步，指当写(输入)进程把一定数量(如4 KB)
的数据写入pipe，便去睡眠等待，直到读(输出)进程取走数据后再把它唤醒。当读进程读一空pipe
时，也应睡眠等待，直至写进程将数据写入管道后才将之唤醒。③ 确定对方是否存在，只有确定了
对方已存在时才能进行通信。
The Best R&D Courses
进程通信
　　3. 消息传递系统(Message passing system)
　　在该机制中，进程不必借助任何共享存储区或数据结构，而是以格式化的消息 (message)为单
位，将通信的数据封装在消息中，并利用操作系统提供的一组通信命令(原语)，在进程间进行消息传
递，完成进程间的数据交换。
　　基于消息传递系统的通信方式属于高级通信方式，因其实现方式的不同，可进一步分成两类：
　　(1) 直接通信方式
　　(2) 间接通信方式
The Best R&D Courses
进程通信
　　4. 客户机-服务器系统(Client-Server system)
　　1) 套接字(Socket)
　　套接字起源于20世纪70年代加州大学伯克利分校版本的UNIX(即BSD Unix)，是UNIX 操作系
统下的网络通信接口。一开始，套接字被设计用在同一台主机上多个应用程序之间的通信(即进程间
的通信)，主要是为了解决多对进程同时通信时端口和物理线路的多路复用问题。随着计算机网络技
术的发展以及UNIX 操作系统的广泛使用，套接字已逐渐成为最流行的网络通信程序接口之一。
The Best R&D Courses
进程通信
　　2) 远程过程调用和远程方法调用
　　远程过程(函数)调用RPC(Remote Procedure Call)，是一个通信协议，用于通过网络连接的系
统。该协议允许运行于一台主机(本地)系统上的进程调用另一台主机(远程)系统上的进程，而对程序
员表现为常规的过程调用，无需额外地为此编程。如果涉及的软件采用面向对象编程，那么远程过
程调用亦可称做远程方法调用。
The Best R&D Courses
进程通信
2.6.2　消息传递通信的实现方式
　　1. 直接消息传递系统
　　在直接消息传递系统中采用直接通信方式，即发送进程利用OS所提供的发送命令(原语)，直接
把消息发送给目标进程。
　　1) 直接通信原语
　　(1) 对称寻址方式。
　　(2) 非对称寻址方式。
The Best R&D Courses
进程通信
　　2) 消息的格式
　　在消息传递系统中所传递的消息，必须具有一定的消息格式。在单机系统环境中，由于发送进
程和接收进程处于同一台机器中，有着相同的环境，所以消息的格式比较简单，可采用比较短的定
长消息格式，以减少对消息的处理和存储开销。该方式可用于办公自动化系统中，为用户提供快速
的便笺式通信。但这种方式对于需要发送较长消息的用户是不方便的。为此，可采用变长的消息格
式，即进程所发送消息的长度是可变的。对于变长消息，系统无论在处理方面还是存储方面，都可
能会付出更多的开销，但其优点在于方便了用户。
The Best R&D Courses
进程通信
　　3) 进程的同步方式
　　在进程之间进行通信时，同样需要有进程同步机制，以使诸进程间能协调通信。不论是发送进
程还是接收进程，在完成消息的发送或接收后，都存在两种可能性，即进程或者继续发送(或接收)或
者阻塞。
　　4) 通信链路
　　为使在发送进程和接收进程之间能进行通信，必须在两者之间建立一条通信链路。有两种方式
建立通信链路。第一种方式是：由发送进程在通信之前用显式的“建立连接”命令(原语)请求系统为
之建立一条通信链路，在链路使用完后拆除链路。
The Best R&D Courses
进程通信
2.6.3　直接消息传递系统实例
　　消息缓冲队列通信机制首先由美国的Hansan提出，并在RC 4000系统上实现，后来被广泛应用
于本地进程之间的通信中。在这种通信机制中，发送进程利用Send原语将消息直接发送给接收进程；
接收进程则利用Receive原语接收消息。
　
The Best R&D Courses
线程
　　　2.7 线程(Threads)的基本概念
2.7.1 线程的引入
　　如果说，在OS中引入进程的目的是为了使多个程序能并发执行，以提高资源利用率和系统吞吐
量，那么，在操作系统中再引入线程，则是为了减少程序在并发执行时所付出的时空开销，使OS具
有更好的并发性。
The Best R&D Courses
线程
　　1. 进程的两个基本属性
　　首先让我们来回顾进程的两个基本属性：
　　① 进程是一个可拥有资源的独立单位，一个进程要能独立运行，它必须拥有一定的资源，包括
用于存放程序正文、数据的磁盘和内存地址空间，以及它在运行时所需要的I/O设备、已打开的文件、
信号量等；
The Best R&D Courses
线程
　　② 进程同时又是一个可独立调度和分派的基本单位，一个进程要能独立运行，它还必须是一个
可独立调度和分派的基本单位。每个进程在系统中有唯一的PCB，系统可根据其PCB感知进程的存
在，也可以根据其PCB中的信息，对进程进行调度，还可将断点信息保存在其PCB中。反之，再利
用进程PCB中的信息来恢复进程运行的现场。正是由于进程有这两个基本属性，才使进程成为一个
能独立运行的基本单位，从而也就构成了进程并发执行的基础。
The Best R&D Courses
线程
　　2. 程序并发执行所需付出的时空开销
　　为使程序能并发执行，系统必须进行以下的一系列操作：
　　(1) 创建进程，系统在创建一个进程时，必须为它分配其所必需的、除处理机以外的所有资源，
如内存空间、I/O设备，以及建立相应的PCB；
　　(2) 撤消进程，系统在撤消进程时，又必须先对其所占有的资源执行回收操作，然后再撤消PCB；
　　(3) 进程切换，对进程进行上下文切换时，需要保留当前进程的CPU环境，设置新选中进程的
CPU环境，因而须花费不少的处理机时间。
The Best R&D Courses
线程
　　3. 线程——作为调度和分派的基本单位
　　如何能使多个程序更好地并发执行，同时又尽量减少系统的开销，已成为近年来设计操作系统
时所追求的重要目标。有不少研究操作系统的学者们想到，要设法将进程的上述两个属性分开，由
OS分开处理，亦即并不把作为调度和分派的基本单位也同时作为拥有资源的单位，以做到“轻装上
阵”；而对于拥有资源的基本单位，又不对之施以频繁的切换。正是在这种思想的指导下，形成了
线程的概念。
The Best R&D Courses
线程
2.7.2 线程与进程的比较
　　1. 调度的基本单位
　　2. 并发性
　　3. 拥有资源
　　4. 独立性
　　5. 系统开销
　　6. 支持多处理机系统
The Best R&D Courses
线程
2.7.3 线程的状态和线程控制块
　　1. 线程运行的三个状态
　　与传统的进程一样，在各线程之间也存在着共享资源和相互合作的制约关系，致使线程在运行
时也具有间断性。相应地，线程在运行时也具有下述三种基本状态：
　　(1) 执行状态，表示线程已获得处理机而正在运行；
　　(2) 就绪状态，指线程已具备了各种执行条件，只须再获得CPU便可立即执行；
　　(3) 阻塞状态，指线程在执行中因某事件受阻而处于暂停状态，例如，当一个线程执行从键盘读
入数据的系统调用时，该线程就被阻塞。
The Best R&D Courses
线程
　　2. 线程控制块TCB
　　如同每个进程有一个进程控制块一样，系统也为每个线程配置了一个线程控制块TCB，将所有
用于控制和管理线程的信息记录在线程控制块中。
　　3. 多线程OS中的进程属性
　　通常在多线程OS中的进程都包含了多个线程，并为它们提供资源。OS支持在一个进程中的多个
线程能并发执行，但此时的进程就不再作为一个执行的实体。多线程OS中的进程有以下属性：
　　(1) 进程是一个可拥有资源的基本单位。
　　(2) 多个线程可并发执行。
　　(3) 进程已不是可执行的实体。
The Best R&D Courses
线程
　　　　2.8 线 程 的 实 现
2.8.1 线程的实现方式
　　线程已在许多系统中实现，但各系统的实现方式并不完全相同。在有的系统中，特别是一些数
据库管理系统，如infomix所实现的是用户级线程； 而另一些系统(如Macintosh和OS/2操作系统)所
实现的是内核支持线程；还有一些系统如Solaris操作系统，则同时实现了这两种类型的线程。
The Best R&D Courses
线程
　　1. 内核支持线程KST(Kernel Supported Threads)
　　在OS中的所有进程，无论是系统进程还是用户进程，都是在操作系统内核的支持下运行的，是
与内核紧密相关的。而内核支持线程KST同样也是在内核的支持下运行的，它们的创建、阻塞、撤
消和切换等，也都是在内核空间实现的。为了对内核线程进行控制和管理，在内核空间也为每一个
内核线程设置了一个线程控制块，内核根据该控制块而感知某线程的存在，并对其加以控制。当前
大多数OS都支持内核支持线程。
The Best R&D Courses
线程
　　这种线程实现方式主要有四个主要优点：
　　(1) 在多处理器系统中，内核能够同时调度同一进程中的多个线程并行执行；
　　(2) 如果进程中的一个线程被阻塞了，内核可以调度该进程中的其它线程占有处理器运行，也可
以运行其它进程中的线程；
　　(3) 内核支持线程具有很小的数据结构和堆栈，线程的切换比较快，切换开销小；
　　(4) 内核本身也可以采用多线程技术，可以提高系统的执行速度和效率。
The Best R&D Courses
线程
　　2. 用户级线程ULT(User Level Threads)
　　用户级线程是在用户空间中实现的。对线程的创建、 撤消、同步与通信等功能，都无需内核的
支持，即用户级线程是与内核无关的。在一个系统中的用户级线程的数目可以达到数百个至数千个。
由于这些线程的任务控制块都是设置在用户空间，而线程所执行的操作也无需内核的帮助，因而内
核完全不知道用户级线程的存在。
The Best R&D Courses
线程
　　使用用户级线程方式有许多优点：
　　(1) 线程切换不需要转换到内核空间。
　　(2) 调度算法可以是进程专用的。
　　(3) 用户级线程的实现与OS平台无关，因为对于线程管理的代码是属于用户程序的一部分，所
有的应用程序都可以对之进行共享。
The Best R&D Courses
线程
　　而用户级线程方式的主要缺点则在于：
　　(1) 系统调用的阻塞问题。在基于进程机制的OS中，大多数系统调用将使进程阻塞，因此，当
线程执行一个系统调用时，不仅该线程被阻塞，而且，进程内的所有线程会被阻塞。而在内核支持
线程方式中，则进程中的其它线程仍然可以运行。
　　(2) 在单纯的用户级线程实现方式中，多线程应用不能利用多处理机进行多重处理的优点，内核
每次分配给一个进程的仅有一个CPU，因此，进程中仅有一个线程能执行，在该线程放弃CPU之前，
其它线程只能等待。
The Best R&D Courses
线程
　　3. 组合方式
　　有些OS把用户级线程和内核支持线程两种方式进行组合，提供了组合方式ULT/KST 线程。在
组合方式线程系统中，内核支持多个内核支持线程的建立、调度和管理，同时，也允许用户应用程
序建立、调度和管理用户级线程。
The Best R&D Courses
线程
The Best R&D Courses
线程
2.8.3 线程的创建和终止
　　1. 线程的创建
　　应用程序在启动时，通常仅有一个线程在执行，人们把线程称为“初始化线程”，它的主要功
能是用于创建新线程。在创建新线程时，需要利用一个线程创建函数(或系统调用)，并提供相应的参
数，如指向线程主程序的入口指针、堆栈的大小，以及用于调度的优先级等。在线程的创建函数执
行完后，将返回一个线程标识符供以后使用。
The Best R&D Courses
线程
　　2. 线程的终止
　　当一个线程完成了自己的任务(工作)后，或是线程在运行中出现异常情况而须被强行终止时，由
终止线程通过调用相应的函数(或系统调用)对它执行终止操作。但有些线程(主要是系统线程)，它们
一旦被建立起来之后，便一直运行下去而不被终止。在大多数的OS中，线程被中止后并不立即释放
它所占有的资源，只有当进程中的其它线程执行了分离函数后，被终止的线程才与资源分离，此时
的资源才能被其它线程利用。
The Best R&D Courses

展开更多......

收起↑