计算机操作系统第2章进程管理课件

计算机操作系统南京工业大学信息学院计算机操作系统南京工业大学信息学院1第二章进程管理

★进程的基本概念★进程控制★进程同步★经典进程同步问题★进程通信★线程这一章介绍如下几个问题：第二章进程管理★进程的基本概念这一章介绍如下几个问题22.1进程的基本概念(1)程序的顺序执行及其特征顺序执行包含两层含义：

●对于多个用户程序来说，所有程序是依次执行的。（外部顺序性）

●对于一个程序来说，它的所有指令是按序执行的。（内部顺序性）

2.1进程的基本概念(1)程序的顺序执行及其特征顺序执行32.1进程的基本概念(2)程序顺序执行的特征

（1）顺序性：处理机的操作严格按照程序所规定的顺序执行，即每一操作必须在下一操作开始之前结束（或者说下一操作必须在当前操作结束后才能开始）。

（2）封闭性：程序是在封闭的环境下执行的。即●程序运行时独占全机资源，资源的状态（除初始态外）只有本程序才能改变它。●程序一旦开始执行，其执行结果不受外界影响。

（3）可再现性：只要程序执行时的环境和初始条件相同，当程序重复执行时，都将获得相同的结果。

2.1进程的基本概念(2)程序顺序执行的特征（1）顺序42.1进程的基本概念(3)程序的并发执行及其特征

程序的并发执行包括两层含义：

●对于一个程序来说，它的所有指令是按序执行的。（内部顺序性）

●对于多个程序（进程）来说，所有进程是交叉执行的。（外部并发性）

2.1进程的基本概念(3)程序的并发执行及其特征程序的52.1进程的基本概念(4)程序并发执行时的特征

1）间断性:

程序在并发执行时，由于它们共享系统资源，以及为完成同一任务而相互合作，致使这些并发执行的程序之间形成了相互制约的关系。（互斥关系、同步关系）

相互制约导致并发执行的程序具有“执行——暂停——执行”这种间断性活动规律。

2）失去封闭性：

程序在并发执行时，由于多个程序共享系统资源，因而这些资源的状态将由多个程序来改变，致使程序的运行已失去了封闭性。

某程序的执行时，会受到其他程序的影响。

2.1进程的基本概念(4)程序并发执行时的特征1）间断62.1进程的基本概念(5)程序并发执行时的特征

3）不可再现性——与时间有关的错误

程序在并发执行时，由于失去了封闭性，也将导致其再失去可再现性。例如：有两个循环程序A和B，它们共享一个变量N。L1：N=N+1；

gotoL1；

L2：print(N)；N=0；gotoL2；

程序A程序B程序A和B并发执行时，可能出现下述三种情况（设某时刻N的值为10）：（1）N=N+1在print(N)和N=0之前，此时得到的N值分别为11，11，0。（2）N=N+1在print(N)和N=0之后，此时得到的N值分别为10，0，1。（3）N=N+1在print(N)和N=0之间，此时得到的N值分别为10，11，0。

计算结果已与并发程序的执行速度有关，从而使程序执行失去了可再现性。

2.1进程的基本概念(5)程序并发执行时的特征3）不可72.1进程的基本概念(6)进程的特征与状态1．进程的定义和特征

进程是程序在一个数据集上的运行过程，是系统进行资源分配和调度的一个独立单位。(传统OS的定义)定义1）结构特征：

进程的特征程序段、相关的数据段、PCB三部分构成了进程实体。

通常的程序是不能并发执行的，为使程序（含数据）能独立运行，应为之配置一进程控制块（即PCB）。

在许多情况下所说的进程，实际上是指进程实体。如，所谓创建进程，……

2）动态性：进程的实质是进程实体的一次执行过程，故动态性是进程的最基本特征。

3）并发性：这是指多个进程实体同存于内存中，且能在一段时间内同时运行。

2.1进程的基本概念(6)进程的特征与状态1．进程的定82.1进程的基本概念(7)进程的特征与状态4）独立性：进程的特征：在传统的OS中，独立性是指进程实体是一个能独立运行、独立分配资源和独立接受调度的基本单位。

5）异步性：是指进程按各自独立的、不可预知的速度向前推进，或说进程实体按异步方式运行。

2.1进程的基本概念(7)进程的特征与状态4）独立性：92.1进程的基本概念(8)进程的特征与状态进程的三种基本状态：

1）就绪（Ready）状态：

当进程已分配到除CPU以外的所有资源后，只要再获得CPU，便可立即执行，进程这时的状态称为就绪状态。

系统中处于就绪状态的进程可能有多个，通常将它们排成一个队列，称为就绪队列。

2）执行（Running）状态:

进程已获得CPU，其程序正在执行。

3）阻塞（Blocked）状态:

正在执行的进程由于发生某事件而暂时无法继续执行时，便放弃处理机而处于暂停状态，亦即进程的执行受到阻塞，把这种暂停状态称为阻塞状态（或等待状态）。

使进程阻塞的典型事件：请求I/O，申请缓冲空间等等。

2.1进程的基本概念(8)进程的特征与状态进程的三种基本102.1进程的基本概念(9)进程的特征与状态进程的三种基本状态的转换：进程调度：就绪态执行态时间片完：执行态就绪态

请求I/O：执行态阻塞态

I/O完成：阻塞态就绪态

引起进程状态转换的典型事件：2.1进程的基本概念(9)进程的特征与状态进程的三种基本112.1进程的基本概念(10)进程的特征与状态挂起状态：有些系统除了进程的三种基本状态外，还有挂起状态。1）引入挂起状态的原因：

（1）终端用户的请求：

（2）父进程请求：（3）负荷调节的需要

：

（4）操作系统的需要

：

当终端用户在自己的程序运行期间发现有可疑问题时，希望暂停执行。希望考察和修改子进程，或协调各子进程间的活动时实时系统中工作负荷较重时，系统可把一些不重要的进程挂起。操作系统有时希望挂起某些进程，以便检查运行中的资源使用情况或进行记账。2.1进程的基本概念(10)进程的特征与状态挂起状态：有122.1进程的基本概念(11)进程的特征与状态挂起状态：2）进程状态的转换

●活动就绪→静止就绪

●活动阻塞→静止阻塞●静止就绪→活动就绪●静止阻塞→活动阻塞挂起原语Suspend激活原语Active2.1进程的基本概念(11)进程的特征与状态挂起状态：2132.1进程的基本概念(12)进程控制块（PCB）

为了描述和控制进程的运行，系统为每个进程定义了一个数据结构——进程控制块。进程控制块是进程实体的一部分，是操作系统中最重要的记录型数据结构。

1.PCB作用：

使一个在多道程序环境下不能独立运行的程序（含数据），成为一个能独立运行的基本单位，一个能与其它进程并发执行的进程。或者说，OS是根据PCB来对并发进程进行控制和管理的。

例如：进程调度；现场保护和恢复；进程同步和通信。PCB是进程存在的唯一标志2.1进程的基本概念(12)进程控制块（PCB）为了描142.1进程的基本概念(13)进程控制块（PCB）2．进程控制块中的信息

PCB中记录了操作系统所需的、用于描述进程当前情况以及控制进程运行的全部信息。具体包括下述四方面的信息：

1）进程标识符：

内部标识符(进程号)；外部标识符(名)；父进程标识及子进程标识；用户标识2）处理机状态：处理机状态信息主要由处理机的各种寄存器中的内容组成的。寄存器包括：通用寄存器、指令计数器、程序状态字（PSW）寄存器、用户栈指针。(保护、恢复现场)当处理机被中断时，这些信息都必须保存到PCB中，以便该进程重新执行时，能从断点继续执行。

2.1进程的基本概念(13)进程控制块（PCB）2．进程152.1进程的基本概念(14)进程控制块（PCB）2．进程控制块中的信息

3）进程调度信息：在PCB中还存放一些与进程调度和进程对换有关的信息。包括：

★进程状态——作为调度和对换时的依据。

★进程优先级——由于描述进程使用处理机的优先级别的一个整数，优先级高的进程优先获得处理机。

★进程调度所需的其它信息——它们与所采用的进程调度算法有关。……

★事件——即阻塞原因。

2.1进程的基本概念(14)进程控制块（PCB）2．进程162.1进程的基本概念(15)进程控制块（PCB）2．进程控制块中的信息

4）进程控制信息：

▲程序和数据的地址——指程序和数据所在的内存或外存首地址；

▲进程同步和通信机制——如信号量、消息队列指针等，它们可能全部或部分地存放在PCB中；

▲资源清单——是一张列出了除CPU外的、进程所需的全部资源及已经分配到该进程的资源的清单；

▲链接指针——它给出本进程（PCB）所在队列中下一个进程的PCB的首址。

2.1进程的基本概念(15)进程控制块（PCB）2．进程172.1进程的基本概念(16)进程控制块（PCB）3．进程控制块的组织方式(1)

常用的组织方式有两种：链接方式和索引方式。

1）链接方式

把具有同一状态的PCB，用其中的链接字链接成一个队列。形成：就绪队列、阻塞队列、空白队列等2.1进程的基本概念(16)进程控制块（PCB）3．进程182.1进程的基本概念(17)进程控制块（PCB）3．进程控制块的组织方式(2)

2）索引方式:

系统根据所有进程的状态建立几张索引表。如，

●就绪索引表

●阻塞索引表等

▲索引表的首址记录在专用单元中；▲每个索引表的表目中，记录具有相应状态的某个PCB的首址。

2.1进程的基本概念(17)进程控制块（PCB）3．进程192.2进程控制(1)进程控制是进程管理中最基本的功能。

进程控制包括：

◆创建进程

◆终止进程

◆进程状态转换

进程控制是由OS的内核完成的。

2.2进程控制(1)进程控制是进程管理中最基本的功能。202.2进程控制(2)2.2.1进程的创建

1．引起创建进程的事件

▲用户登录

▲作业调度

▲提供服务当用户进程提出某种请求后，系统将专门创建一个进程来提供用户所需的服务。如，文件打印。

上述三种情况，都是由系统内核为它创建一个新进程。

▲应用请求：

是基于应用进程的需求，由应用进程自己创建一个新进程，以便新进程以并发运行方式完成特定任务。

2.2进程控制(2)2.2.1进程的创建1．引起创212.2进程控制(3)2.2.1进程的创建(2)2．进程的创建

调用进程创建原语Create（），按下述步骤创建一个进程：

（1）申请空白PCB；（2）为新进程分配资源。主要是内存空间。

（3）初始化PCB。包括：

初始化标识信息初始化处理机状态信息：程序计数器，堆栈指针等进程状态——就绪或静止就绪、优先级等。初始化处理机控制信息：（4）将新进程插入就绪队列。

2.2进程控制(3)2.2.1进程的创建(2)2．进222.2进程控制(4)2.2.2进程的终止

1．引起进程终止的事件

▲正常结束

▲异常结束

▲外界干预

常见的异常结束事件有：

越界错误

保护错——试图访问不允许访问的资源或文件，或者以不适当方式访问

非法指令

特权指令错——用户程序试图执行只允许OS执行的指令运行超时

等待超时算术运算错——被0除

I/O故障

♥操作员或操作系统干预（如发生死锁）

♥父进程请求

♥父进程终止

2.2进程控制(4)2.2.2进程的终止1．引起进232.2进程控制(5)2.2.2进程的终止

2．进程的终止过程

OS调用终止原语，按下述过程终止进程：（1）根据被终止进程的标识，从PCB集合中找除该进程的PCB，读出该进程状态。（2）若被终止进程正处于执行状态，应立即终止其执行，并置调度标志为真，用于指示该进程被终止后应重新进行调度。若该进程还有子孙进程，应将其所有子孙进程终止，以防止它们成为不可控进程。（3）将被终止进程的所有资源，或者归还给其父进程，或者归还给系统。（4）将被终止进程（它的PCB）从所在队列中移出，等待其他进程来搜索信息。2.2进程控制(5)2.2.2进程的终止2．进程的242.2进程控制(6)2.2.2进程的阻塞和唤醒

1．引起进程阻塞和唤醒的事件

▲请求系统服务▲无新工作可做当执行进程请求OS服务时，由于某种原因，OS并不立即满足该进程的请求时，该进程只能转变为阻塞状态来等待。如，进程请求打印机，……

系统往往设置一些具有特定功能的系统进程，每当这种进程完成任务后，便把自己阻塞起来以等待新任务到来。如，系统中发送数据的进程，……

▲启动某种操作当进程启动某种操作后，如果该进程必须在该操作完成后才能继续执行，则必须先使该进程阻塞，以等待操作完成。如，启动了某I/O设备，……

▲新数据尚未到达对于相互合作的进程，如果其中一个进程需要获得另一个（合作）进程提供的数据才能运行以对数据进行处理，则只要其所需数据尚未到达，该进程只有阻塞（等待）。如，……

2.2进程控制(6)2.2.2进程的阻塞和唤醒1．引起252.2进程控制(7)2.2.2进程的阻塞和唤醒

2．进程阻塞过程

调用阻塞原语block把自己阻塞。（主动行为）阻塞（block）过程：

▲立即停止执行；▲把PCB中进程状态由“执行”改为“阻塞”；▲将PCB插入具有相同事件的阻塞队列；▲转进程调度程序，将处理机分配给某个就绪进程，并进行进程切换——保留被阻塞进程的处理机状态（在PCB中），再按新进程的PCB中处理机状态设置CPU的环境。2.2进程控制(7)2.2.2进程的阻塞和唤醒2．进程262.2进程控制(8)2.2.2进程的阻塞和唤醒

3．进程唤醒过程

调用唤醒原语wakeup()，将等待事件的进程唤醒。唤醒原语执行过程：▲将被唤醒进程的PCB从阻塞队列移出；▲将其PCB中进程状态由“阻塞”改为“就绪”；▲将改PCB插入到就绪队列中。block（）和wakeup（）是成对的。

2.2进程控制(8)2.2.2进程的阻塞和唤醒3．进程272.2进程控制(9)2.2.4

进程的挂起和激活

1．进程的挂起

当出现了引起进程挂起的事件时(用户进程请求将自己挂起，或父进程请求将子进程挂起)，系统将用挂起原语suspend()将指定进程或处于阻塞状态的进程挂起。

挂起原语的执行过程：▲检查被挂起进程的状态：若处于活动就绪或执行状态，则将其转为静止就绪；若处于活动阻塞,则将其转为静止阻塞。

▲把该进程的PCB复制到某指定内存区域

为方便用户或父进程考查该进程的运行状态。

▲若该进程正在执行，则转进程调度程序重新调度。

2.2进程控制(9)2.2.4进程的挂起和激活1．282.2进程控制(10)2.2.4

进程的挂起和激活

2．进程的激活

当发生激活进程的事件时(如父进程或用户请求激活指定进程，而内存中已有足够空间时)，系统利用激活原语active()将指定进程激活。

激活过程是：▲将进程从外存调入内存；若是静止就绪，则改为活动就绪；若是静止阻塞，则改为活动阻塞。

▲若采用的是抢占式调度策略，则应检查被激活就绪进程的优先级，若其优先级比先行执行进程高，则应将处理机分配给被激活进程。

▲检查该进程现行状态：2.2进程控制(10)2.2.4进程的挂起和激活2292.3进程同步由于进程的异步性，尤其是它们竞争临界资源时，可能会给系统造成混乱。进程同步的主要任务，是使并发执行的进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性。2.3进程同步由于进程的异步性，尤其是它们竞争临界资源时302.3进程同步(2)2.3.1进程同步的基本概念

1．两种形式的制约关系

（1）间接制约关系

间接制约关系源于资源共享。如，共享打印机。

进程互斥（2）直接制约关系

源于进程间的合作。如，……

进程同步2．临界资源

在一段时间内只允许一个进程访问的资源，即仅当一个进程访问完并释放该资源后，才允许另一个进程访问的资源，称为临界资源或独占资源。

如，打印机、磁带机、共享变量、队列、……

2.3进程同步(2)2.3.1进程同步的基本概念1312.3进程同步(3)2.3.1进程同步的基本概念

【例】生产者-消费者问题——著名的进程同步问题共享变量：临界资源循环缓冲区生产者投放一个产品后，输入指针in加1：in=(in+1)%n（n是缓冲区个数，整型常量），in初值为0；

消费者每取出一个产品，输出指针out加1：out=(out+1)%n，out初值为0；

引入一个共享变量counter,初值为0。▲生产者投放一个产品，counter加1，counter=n时不能再投放产品

▲消费者每取一个产品，counter减1，counter=0时不能再取出产品

前面交通观察站例子亦然。2.3进程同步(3)2.3.1进程同步的基本概念【32processproducer：while（condition）{…produceaniteminnextp；…while(counter==n)no-op；//no-op表示空操作buffer[in]=nextp；in=(in+1)%n；counter=counter+1；}生产者进程算法如下：processproducer：生产者进程算法如下：33processconsumer：structitemnextc；while（condition）{while（counter==0）no-op；nextc=buffer[out]；out=（out+1）%n；counter=counter–1；consumetheiteminnextc；}消费者进程算法如下：processconsumer：消费者进程算法如下：34上面的生产者程序和消费者程序，在顺序执行时其结果也是正确的。但若并发执行时，可能会出现差错，问题在于这两个进程共享变量counter。生产者对它做加1操作，消费者对它做减1操作，这两个操作在机器语言实现时，常可用下面的形式描述：

生产者执行的操作：

register1=counter；

register1=register1+1；

counter=register1；

消费者执行的操作：

register2=counter；

register2=register2-1；

counter=register2；

假设counter当前的值为5，按下述顺序执行：

register1=counter;(5)register1=register1+1;(6)register2=counter;(5)register2=register2–1;(4)counter=register1;(6)counter=register2;(4)最终counter的值为4，正确的counter值应是5，出现了差错。

学生可以考虑出现6的情况。

解决此问题的关键，是应将变量counter作为临界资源处理，亦即让生产者进程和消费者进程互斥地访问变量counter。

上面的生产者程序和消费者程序，在顺序执行时其结果也是正确的。352.3进程同步(4)2.3.1进程同步的基本概念

3．临界区（criticalsection）

每个进程中访问临界资源的那段代码称为临界区。

不论是硬件临界资源，还是软件临界资源，多个进程必须互斥地对它们访问。

显然，若能保证诸进程互斥地进入自己的临界区，便可实现诸进程对临界区的互斥访问。为此，每个进程在进入临界区之前，应先对欲访问的临界资源进行检查，看是否正被访问，如果此刻该资源未被访问，便可进入临界区对该临界资源进行访问，并设置它正被访问的标志；如果此刻它正被访问，则本进程不能进入临界区。

◆因此必须在临界区前增加一段用于上述检查的代码，把这段代码称为进入区（entrysection）；◆相应地，在临界区后面也要加上一段称为退出区（exitsection）的代码，用于将临界区正被访问的标志恢复为未被访问的标志。

定义：进程互斥——不允许两个或两个以上进程同时访问同一个临界资源。进程互斥——不允许两个或两个以上进程同时进入相关临界区。2.3进程同步(4)2.3.1进程同步的基本概念3362.3进程同步(5)2.3.1进程同步的基本概念

4．同步机制应遵循的原则

为了实现各进程互斥地进入自己的临界区，一般是在系统中设置专门的同步机制来协调各进程间的运行。

所有同步机制都应遵循如下四条准则：◆空闲让进◆忙则等待当无进程处于临界区时，表明临界资源处于空闲状态，应允许一个请求进入临界区的进程立即进入自己的临界区，以便有效地利用临界资源。◆有限等待当已有进程进入临界区时，表明临界资源正在被访问，因而其他试图进入临界区的进程必须等待，以保证对临界资源的互斥访问。◆让权等待对要求访问临界资源的进程，应保证在有限的时间内能进入自己的临界区，以免陷入“死锁”状态。——不死等。当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入“忙等”。——不忙碌等待。2.3进程同步(5)2.3.1进程同步的基本概念4372.3进程同步(6)2.3.2信号量机制信号量（Semaphores）机制是一种卓有成效的进程同步工具。信号量机制已被广泛应用于单处理机和多处理机系统以及计算机网络中。

信号量机制的发展：◆整型信号量

◆记录型信号量

◆AND型信号量

◆信号量集

“忙等”，未遵循“让权等待”准则。

——后边重点介绍。

学生在深刻理解记录型信号量后自学。

2.3进程同步(6)2.3.2信号量机制信号量（S382.3进程同步(7)2.3.2信号量机制记录型信号量

需要一个用于代表临界资源数目的整型变量value；还要一个在该资源上阻塞的队列（链表）指针L)。故信号量应采用记录型（C语言中为结构型）的结构：

structsemaphore{intvalue；structsemphore*L；}；

记录型信号量的结构定义信号量除初始化外，只能通过两个原子操作(称为原语)wait（S）和signal（S）来访问。它们以前被称为P、V操作。下页介绍wait和signal操作。

2.3进程同步(7)2.3.2信号量机制记录型信号392.3进程同步(8)2.3.2信号量机制wait和signal操作可用C/C++语言描述如下：voidwait（S）structsemaphoreS;{S.value=S.value–1;if(S.value<0)block(S.L);

/*让权等待*/}voidsignal(S)structsemaphoreS;{S.value=S.value+1;if(S.value<=0)wakeup(S.L);/*唤醒第一个等待的进程*/}P(S)V(S)S.value的初值表示系统中某类资源的数目。——资源信号量。

2.3进程同步(8)2.3.2信号量机制wait和s402.3进程同步(9)2.3.2信号量机制wait和signal操作的物理意义：对信号量S的每次wait操作，意味着进程请求一个该类临界资源，因此描述为S.value=S.value-1；当S.value<0时，表示该类资源已分配完，因此进程应调用block原语进行自我阻塞，放弃处理机，并插入到信号量链表S.L(阻塞队列)中。可见该机制遵循了“让权等待”准则。类似地，可以解释signal操作……

▲S.value的初值表示系统中某类资源的数目。——资源信号量。

▲S.value的初值为1，表示只允许一个进程访问，此时信号量转化为互斥信号量。

2.3进程同步(9)2.3.2信号量机制wait和s412.3进程同步(10)2.3.3信号量的应用

1．利用信号量实现进程互斥方法要点：

★为临界资源设置一个互斥信号量mutex，其初值为1；

★各进程访问该资源的临界区置于wait（mutex）和signal（mutex）之间即可。

wait（mutex）——进入区signal（mutex）——退出区请看下页的例子2.3进程同步(10)2.3.3信号量的应用1．利42利用信号量实现进程互斥的简单例子某交通路口设置了一个自动计数系统，该系统由“观察者”进程和“报告者”进程组成。观察者进程能识别卡车，并对通过的卡车计数；报告者进程定时（可设为每隔1小时，准点时）将观察者的计数值打印输出，每次打印后把计数值清“0”。两个进程的并发执行可完成对每小时中卡车流量的统计。这两个进程的功能如下：

processobserver{while(condition)observealorry;

wait（S）;count=count+1;

signal（S）;}

临界区

processreporter{wait（S）;print（count）;count=0；

signal（S）;}临界区structsemaphoreS；intcount=0；S.value=1；

【注意】wait（S）和signal（S）必须成对出现

利用信号量实现进程互斥的简单例子某交通路口设置了一个自动计数43利用信号量实现前趋关系

【例】利用信号量，按语句的前趋关系（见图2-6）写出一个可并发执行的程序。图中表示：进程P1中有语句S1；进程P2中有语句S2；……语句S1执行后才能执行语句S2和语句S3；语句S2执行后才能执行语句S4和S5；语句S3、S4和S5执行后，才能执行语句S6。P1执行完应通知P2、P3；P2得到通知后才开始执行；P2执行完应通知P4、P5；……利用信号量实现前趋关系【例】利用信号量，按语句的前趋关系（44structsemaphorea，b，c，d，e，f，g；a.value=b.value=c.value=0;d.value=e.value=g.value=0;程序描述如下：初始化parbegin

/*parbegin表示并发执行开始*/processP1：{S1；signal（a）；signal（b）；}processP2：

{wait（a）；S2；signal（c）；signal（d）；}processP3：{wait（b）；S3；signal（e）；}processP4：{wait（c）；S4；signal（f）；}processP5：{wait（d）；S5；signal（g）；}processP6：

{wait（e）；wait（f）；wait（g）；S6；}parend

/*用parend表示并发执行结束*/structsemaphorea，b，c，d，e，f，g452.4

经典进程同步问题生产者-消费者问题

读者-写者问题

哲学家进餐问题

在多道程序环境下，进程同步问题十分重要，引起了不少学者对它进行研究，由此产生了一系列经典的进程同步问题，其中较有代表性的是：通过对这些问题的研究和学习，可以帮助我们更好地理解进程同步概念及实现方法。2.4经典进程同步问题生产者-消费者问题在多道程序环462.4

经典进程同步问题(2)2.4.1生产者-消费者问题

前面已经对生产者-消费者问题做了一些描述，但是未考虑进程的互斥和同步问题，因而造成了共享变量counter的不确定性。

生产者-消费者问题是相互合作进程关系的一种抽象，例如，……先介绍最简单的P-C问题生产者-消费者问题从特殊到一般(从易到难)可以分3种形式：▲一个生产者、一个消费者、一个缓冲区的问题；▲一个生产者、一个消费者、n个缓冲区的问题；▲k个生产者、m个消费者、n个缓冲区的问题；2.4经典进程同步问题(2)2.4.1生产者-消费者472.4

经典进程同步问题(3)最简单的生产者-消费者问题缓冲区PC一个生产者、一个消费者、一个缓冲区的问题如右图所示。★当缓冲区空时，生产者可将产品存入缓冲区；当缓冲区满时，生产者必须等待(阻塞)，待消费者取走产品后将其唤醒后，才能将产品存入。★当缓冲区满时，消费者可从缓冲区取出产品进行消费；当缓冲区空时，消费者必须等待(阻塞)，待生产者存入产品后将其唤醒后，才能再从缓冲区取产品。用信号量机制解决进程同步问题的基本方法：1．为生产者设置1个私有信号量empty，其初值为1，表示有1个空缓冲区；为消费者设置1个私有信号量full，其初值为0，表示开始时没有空缓冲区；（由物理意义确定）2．生产者将产品存入缓冲区之前，应先测试缓冲区是否空：执行wait(empty)操作；离开临界区(存入产品)后，应通知(可能会唤醒)消费者：执行signal(full)操作；3．消费者从缓冲区取产品之前，应先测试缓冲区是否满：执行wait(full)操作；离开临界区(取走产品)后，应通知(可能会唤醒)生产者：执行signal(empty)操作2.4经典进程同步问题(3)最简单的生产者-消费者问题缓482.4

经典进程同步问题(4)最简单的生产者-消费者问题一个生产者、一个消费者、一个缓冲区的生产者-消费者问题的算法描述如下所示：semaphoreempty,full;empty=1;full=0;parbeginprocessProducer:{...produceaniteminnextp;wait(empty);//测试buffer=nextp;signal(full);//通知消费者}processConsumer:{wait(full);//测试nextc=buffer;signal(empty);//通知consumetheiteminnextc;}parend2.4经典进程同步问题(4)最简单的生产者-消费者问题一492.4

经典进程同步问题(5)一个生产者、一个消费者、n个缓冲区的P-C问题n-1543210PC循环缓冲区…信号量empty=n(初值)信号量full=0(初值)资源信号量semaphoreempty,full;empty=n;full=0;intin=0,out=0;//下标parbeginprocessProducer:{...produceaniteminnextp;wait(empty);//测试buffer[in]=nextp;in=(in+1)%n;signal(full);//通知消费者}资源信号量processConsumer:{wait(full);//测试nextc=buffer[out];out=(out+1)%n;signal(empty);//通知consumetheiteminnextc;}parend与前不同本题中in和out不是共享变量，无需互斥访问。2.4经典进程同步问题(5)一个生产者、一个消费者、n个502.4

经典进程同步问题(6)2.4.1生产者-消费者问题下面介绍生产者-消费者问题一般形式：k个生产者、m个消费者、n个缓冲区的问题。一般形式的生产者-消费者问题的图示如下：012345…n-1P1P2P3PK…C1C2C3Cm…生产者消费者n个缓冲区的循环缓冲图2-5生产者-消费者问题示意图2.4经典进程同步问题(6)2.4.1生产者-消费者512.4.1生产者-消费者问题◆用互斥信号量mutex对缓冲区(共享变量in和out)的互斥使用，互斥信号量mutex初值为1；

◆用资源信号量empty表示多缓冲中空缓冲区的数目，empty的初值为n；◆用资源信号量full表示多缓冲中满缓冲区的数目，full的初值为0；◆只要多缓冲未满，生产者便可将消息送入缓冲区；◆只要多缓冲不空，消费者便可从缓冲区取走一个消息。◆生产者用共享变量in作为下标访问缓冲区，mutex为其互斥信号量；消费者用共享变量out作为下标访问缓冲区，其互斥信号量也用mutex。2.4.1生产者-消费者问题◆用互斥信号量mutex对缓52parbegin//并发执行开始

processproduceri(i=1,2,…,k）{itemnextp；while（condition）{…produceaniteminnextp；…wait（empty）；wait（mutex）；

buffer[in]=nextp；in=（in+1）%n；signal（mutex）；signal（full）；}}生产者-消费者问题可描述如下：

processconsumerj(j=1,2,…,m）{itemnextc；while（condition）{wait（full）；wait（mutex）；

nextc=buffer[out]；out=（out+1）%n；signal（mutex）；signal（empty）；consumetheiteminnextc；}}parend//并发执行结束

临界区◆在每个进程中，实现互斥的wait（mutex）和signal（mutex）必须成对出现；◆对资源信号量empty和full的wait和signal操作也要成对地出现，但它们处于不同的进程中。◆在每个进程中的多个wait操作顺序不能颠倒，应先执行对资源信号量（也称私有信号量）的wait操作，然后执行对互斥信号量（公有信号量）的wait操作，否则可能引起进程死锁。(Why?)semaphoremutex,empty,full;itembuffer[n];intin=0，out=0；mutex.value=1;empty.value=n，full.value=0;初始化临界区parbegin//并发执行开始生产者-消费者问题可描述532.4

经典进程同步问题(7)2.4.2哲学家进餐问题

Dijkstra提出并解决的哲学家就餐问题是经典的进程同步问题。哲学家就餐问题描述如下：

有5个哲学家共用一张圆桌，分别坐在周围的5张椅子上，在圆桌上有5个碗和5只筷子，他们的生活方式是交替地进行思考和进餐。平时，每个哲学家进行思考，饥饿时便试图拿起其左右最靠近他的筷子，只有在他拿到两只筷子时才能进餐。进餐完毕，放下筷子继续思考。图2-7是其示意图。

2.4经典进程同步问题(7)2.4.2哲学家进餐问题542.4

经典进程同步问题(8)利用记录型信号量解决哲学家进餐问题

桌子上的筷子f0，f1，…，f4是临界资源，应互斥使用，可用一个信号量表示一只筷子，5只筷子的5个信号量构成信号量数组，所有信号量的初值均为1。

structsemaphorechopstick[5]；chopstick[0].value=chopstick[1].value=1;chopstick[2].value=chopstick[3].value=1;chopstick[4].value=1;初始化每个哲学家算法流程为(1)拿起左、右筷子；(2)吃面条；(3)放下左、右筷子；(4)思考问题；(5)返回(1)。2.4经典进程同步问题(8)利用记录型信号量解决哲学家进552.4

经典进程同步问题(9)第i个哲学家的活动可描述如下：

parbeginprocessPi（i=0，1，2，3，4）{while（logical）{wait（chopstick[i]）；

//拿起左边筷子wait（chopstick[（i+1）%5]）；

//拿起右边筷子

eating；signal（chopstick[i]）；

//放下左边筷子signal（chopstick[（i+1）%5]）；//放下右边筷子thinking；}}parend此算法虽然能保证相邻哲学家对筷子的访问互斥，但可能引起死锁。(Why?)

2.4经典进程同步问题(9)第i个哲学家的活动可描述如下562.4

经典进程同步问题(10)对上述哲学家算法的死锁问题，可采取下面几种解决方法之一：（1）至多允许4个哲学家同时取左边的筷子，这样能至少保证一个哲学家能就餐，并在用毕后释放他用过的两只筷子，从而使更多的哲学家能够进餐。（请学生考虑算法的描述）（2）仅当哲学家左右两只筷子均可用时，才允许他拿起筷子进餐。（用AND信号量机制）（3）规定奇数号哲学家先拿左边筷子，然后再拿右边筷子；而偶数号哲学家先拿右边筷子，然后再拿左边筷子。（4）规定每个哲学家先拿序号小的筷子——按序号分配。请学生考虑算法的描述。

2.4经典进程同步问题(10)对上述哲学家算法的死锁问题572.4

经典进程同步问题(11)2.4.3读者-写者问题

一个数据文件或记录，可被多个进程共享，我们把只要求读该文件的进程称为“读者进程”，其他进程称为“写者进程”。◆允许多个读者进程同时读一个共享文件，因为读操作不会使数据文件混乱；◆不允许两个或两个以上写者进程同时访问共享文件，因为这种访问将会引起混乱；◆不允许一个写者进程和其他读者进程同时访问共享文件，因为这种访问将会引起混乱。

所谓“读者-写者问题”——是指保证一个Writer进程必须与其它进程互斥地访问共享对象的同步问题。2.4经典进程同步问题(11)2.4.3读者-写者问582.4

经典进程同步问题(12)利用记录型信号量解决读者-写者问题

【算法分析】

▲

为实现Reader进程和Writer进程间的互斥，设置一个互斥信号量Wmutex，其初值为1；▲

设置一个整型变量Rcounter，记录正在读的读者进程数。其初值为0；

▲

由于只要有一个Reader进程在读，便不允许Writer进程去写，因此第一个读者进程需要执行wait（Wmutex）操作，即当Rcounter=0时，Reader进程才需要执行wait（Wmutex）操作。若wait（Wmutex）操作成功（表示此时无Writer进程在写），Reader进程便可去读，同时做Rcounter+1的操作。若wait（Wmutex）操作成功（表示此时无Writer进程在写），Reader进程便可去读，同时做Rcounter+1的操作。▲

同理，最后一个Reader进程离开时(Rcounter-1后变为0)应执行signal（mutex）操作，以便让Writer进程写。▲

Rcounter是被多个Reader进程访问的临界资源，为了对它互斥访问，应为它设置一个互斥信号量Rmutex。

2.4经典进程同步问题(12)利用记录型信号量解决读者-592.4

经典进程同步问题(13)根据前面分析，读者-写者问题可描述如下：

semaphoreWmutex，Rmutex;intRcounter=0;Wmutex.value=Rmutex.value=1;

parbeginprocessReaderi(i=1，2，…){wait(Rmutex);if(Rcounter==0)wait(Wmutex);Rcounter=Rcounter+1;signal(Rmutex);…Reading;…wait(Rmutex);Rcounter=Rcounter–1;if(Rcounter==0)signal(Wmutex);signal(Rmutex);}processWriterj(j=1，2，…){wait(Wmutex);

Writing;signal(Wmutex);}parend

【分析】▲当第一个读者在读文件时，后续读者也可进入临界区读该文件，后续写者不能写(在Wmutex上阻塞)；待所有读者退出时，由最后退出的读者唤醒一个写者。▲当有一个写者在写时，后续写者不能写，在Wmutex上阻塞；后续读者不能读，其中第一个读者在Wmutex上阻塞，其余读者在Rmutex上阻塞。该写者退出时，唤醒一个写者或读者。读者优先2.4经典进程同步问题(13)根据前面分析，读者-写者问602.4

经典进程同步问题(14)上述算法实际上是“优先读者”算法，当有读者正在读，且后续读者源源不断到来时，写者将长期得不到服务。写者“饿死”。

为此，可以考虑“优先写者”的算法——当有写者要写时，待目前正在读的读者读完后，立即让写者去写（即一旦有写者到达，后续的读者都必须等待，而无论是否有读者在读文件）。请学生思考，写出该算法的描述。

可以增加一个互斥信号量W，用于在写进程到达时封锁后续的读者进程:读者进程进入时访问Rcouter时,增加执行wait(W)和signal(W)；写者进入临界区时，增加执行wait(W)和signal(W)。2.4经典进程同步问题(14)上述算法实际上是“优先读者612.4

经典进程同步问题(15)复习思考题

1．若一只盘子一次只能放一个水果，A只往盘中放苹果，B只往盘中放梨子，C只从盘中取苹果，D只从盘中取梨子。试用P、V操作写出同步算法。

2．有三个进程PA、PB、PC共享两个缓冲器B1和B2。缓冲器B1中可存放n件产品，缓冲器B2中可存放m件产品。进程PA每次生产一件产品并将其存入缓冲器B1中；进程PB每次从缓冲器B1中取出一件产品后再把它送到缓冲器B2中；进程PC每次从缓冲器B2中取出一件产品去消费。为防止把产品存入已满的缓冲器、或从空的缓冲器取产品、或重复取产品，试用PV操作实现它们之间的制约。(先考虑m=n=1的特例)3．今有一个文件F供进程共享，现把这些进程分成A、B两组，规定同组的进程可以同时读文件F；但当有A组（或B组）的进程在读文件F时就不允许B组（或A组）的进程读文件F。试用P、V操作（记录型信号量）来进行管理。

2.4经典进程同步问题(15)复习思考题1．若一只盘子62进程同步复习思考题(续)4．生产者-消费者问题中，如果将wait（full）和wait（mutex）互相置换，或者将signal（mutex）和signal（empty）互相置换，结果会如何？5．试利用记录型信号量写出一个不会出现死锁的哲学家进餐问题的算法。6.设自行车生产车间有两个货架，货架A可以存放8个车架，货架B可以存放20个车轮；又设有4个工人，他们的活动是重复劳动，分别为：工人1加工一个车架放入货架A中；工人2、3分别加工车轮放入货架B中（每人每次放入1个车轮）；工人4从货架A中取一个车架，再从货架B中取两个车轮，组装成一辆自行车。试用PV操作实现四个工人的合作。进程同步复习思考题(续)4．生产者-消费者问题中，如果将632.6进程通信

进程通信——进程之间的信息交换。进程之间的互斥和同步，交换的信息量少——低级通信。信号量机制作为通信工具不够理想，表现在：

效率低；通信对用户不透明。

本节介绍进程高级通信——是指用户可直接利用OS所提供的一组通信命令，高效地传送大量数据的一种通信方式。高级通信过程对用户是透明的。大大减少了通信程序编制的复杂性。

2.6进程通信进程通信——进程之间的信息交换。642.6进程通信(2)2.6.1进程通信的类型

高级通信机制可归结为三类：

■共享存储器通信；

■管道通信(共享文件)；

■消息传递通信。直接通信方式间接通信方式——信箱通信单机(集中式)适合单机或网络2.6进程通信(2)2.6.1进程通信的类型单机(652.6.1进程通信的类型

1．共享存储器系统（Shared-MemorySystem）（1）基于共享数据结构的通信方式如生产者-消费者问题中，是用有界缓冲区这种数据结构来实现通信的。公用数据结构的设置及对进程间同步的处理，都是程序员的职责，增加了程序员的负担，而操作系统只需提供共享存储器。——低效的通信方式（低级通信）2.6.1进程通信的类型1．共享存储器系统（Share662.6.1进程通信的类型先向系统申请共享存储区中的一个分区，并指定该分区的关键字；若系统已经将该分区分配给其它进程，则将其描述符返回给申请者；申请者将获得的共享存储分区连接到本进程上；此后，便可象读写普通存储器那样地读写该公用存储分区。——UNIX/LINUX与之有关的系统调用有4个1．共享存储器系统（Shared-MemorySystem）（2）基于共享数据结构的通信方式：在存储区中划出一块共享存储区，诸进程可通过对共享存储区中数据的读和写来实现通信。——属于高级通信方式。

2.6.1进程通信的类型先向系统申请共享存储区中的一个分672.6进程通信(3)2．管道（pipe）通信

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

首创于UNIX系统

◆写进程以字节流的形式将大量数据送入管道；

◆读进程从管道中接收（读）数据。

由于发送进程和接收进程是通过管道进行通信的，故称为管道通信。为协调双方的通信，管道机制必须提供以下三方面的协调能力：

★互斥——当一个进程正在对pipe执行读/写操作时，其它进程必须等待；★同步——★确定对方是否存在——当写进程把一定数据写入pipe，便去睡眠等待，直至读进程取走数据后，再把它唤醒；当读进程读一空pipe时，也应睡眠等待，直至写进程将数据写入pipe后，再把它唤醒。

只有确定对方以存在时，才能进行通信。

2.6进程通信(3)2．管道（pipe）通信管道——用682.6进程通信(4)2．消息传递系统(Messagepassingsystem)消息传递机制——单机系统、多机系统、计算机网络，用得最广泛的一种高级通信机制。●进程间的数据交换,是以格式化的消息(message)为单位的。●计算机网络中，message又称为报文。●利用系统提供的一组通信命令（原语）进行通信。●OS隐蔽了通信实现细节，大大简化了通信程序编制的复杂性，因而得到广泛应用。

其通信方式

直接通信方式

间接通信方式2.6进程通信(4)2．消息传递系统(Messagep692.6进程通信(5)2.6.2消息传递通信的实现方法

1.直接通信方式是指发送进程利用OS所提供的命令，直接把消息发送给目标进程。

要求发送和接收进程都以显式方式提供对方的标识符。两条通信原语为：

send（Receiver，message）；

发送一个消息message给接收进程Receiverreceive（Sender，message）；

接收Sender发来的消息message有时，接收进程可能与多个发送进程通信，故不可能事先知道发送进程。对于这样的应用，接收原语中的源进程参数，是完成通信后的返回值。接收原语可表示为：receive（id，message）；

id是返回值（标识符）

2.6进程通信(5)2.6.2消息传递通信的实现方法702.6进程通信(6)2.6.2消息传递通信的实现方法

2.间接通信方式是指进程之间的通信，需要通过作为共享数据结构的实体——信箱。▲信箱暂存发送进程发送给目标进程的消息；▲接收进程从信箱中取出对方发给自己的消息。

既可实现实时通信，也可实现非实时通信。2.6进程通信(6)2.6.2消息传递通信的实现方法712.6进程通信(6)2.6.2消息传递通信的实现方法

2.间接通信方式系统为信箱通信提供了若干条原语：

（1）信箱的创建和撤消。信箱可由OS创建，也可由用户用OS命令创建。

（2）消息的发送和接收。send（mailbox，message）；receive（mailbox，message）；将一个消息message发送到指定的信箱mailbox从指定信箱mailbox接收消息message2.6进程通信(6)2.6.2消息传递通信的实现方法722.6进程通信(7)2.6.3消息传递系统实现中的进程同步方式三种情况：

（1）发送进程阻塞、接收进程阻塞两个进程平时都处于阻塞状态，直到有消息传递时。

主要用于发送进程和接收进程之间无缓冲时的进程之间紧密同步。

这种同步方式称为汇合（2）发送进程不阻塞、接收进程阻塞接收进程如服务器上通常都设置了多个服务进程，分别用于提供不同的服务：如打印服务

应用最广泛的进程同步方式（3）发送进程和接收进程均不阻塞发送进程和接收进程都忙于自己的事情，仅当发生某事件使它无法继续执行时，才把自己阻塞起来等待

也是较常见的进程同步形式有消息队列时采用2.6进程通信(7)2.6.3消息传递系统实现中的三732.6进程通信(8)【略】2.6.4消息缓冲队列通信机制

美国的hansan提出，被广泛应用于本地进程之间的通信

1．消息缓冲队列通信机制中的数据结构（1）消息缓冲区其结构可描述如下：

structmessage_buffer{longsender；

//发送者进程标识符intsize；

//消息长度chartext[N]；

//消息正文structmessage_buffer*next；

//指向下一个消息缓冲区的指针}；

2.6进程通信(8)【略】2.6.4消息缓冲队列通742.6进程通信(9)2.6.4消息缓冲队列通信机制1．消息缓冲队列通信机制中的数据结构