第二章 进程管理 2.1 进程(PROCESS)的基本概念 2.2 进程控制 2.3 进程同步 2.4 经典进程的同步问题 2.6 管程机制 为了描述程序在并发执行时对系统资源的共享，我们需要一个描述程序执行时动态特征的概念，这就是进程。在本章中，我们将讨论进程概念、进程控制和进程间关系。 2.1 进程(PROCESS)的基本概念 2.2 进程控制 2.3 进程同步 2.4 经典进程的同步问题 2.6 管程机制 2.6 进程间通信(IPC, INTER-PROCESS COMMUNICATION) 2.7 线程(THREAD)

2.1 进程(PROCESS) 2.1.1 程序的顺序执行和并发执行 2.1.2 进程的定义和描述 2.1.3 进程的状态转换 返回

2.1.1 程序的顺序执行和并发执行 程序的执行有两种方式：顺序执行和并发执行。 顺序执行是单道批处理系统的执行方式，也用于简单的单片机系统； 现在的操作系统多为并发执行，具有许多新的特征。引入并发执行的目的是为了提高资源利用率。

程序的顺序执行 通常，一个应用程序分成若干程序段。在各个程序段之间，必须按照某种先后次序顺序执行。仅当前一操作完成后，才能执行后继操作。 例如 ，下列程序段： s1: a=20; s2: x=a++; s3 printf(“x=%d”,x); s1 s2 s3

前驱图 p1 P2 前驱图是一个有向无循环图，用于描述进程之间执行的前后顺序。 图中，每个节点表示一个进程，节点间的有向边则表示两个节点间的前驱关系。 在前驱图中，把没有前驱的节点称作初始节点，把没有后继的节点称作终止节点。有时，每个节点还有一个重量，表示该节点含有的程序量或执行时间。 p1 P2

程序的并发执行 例子：输入程序，计算程序，打印程序之间的关系。

顺序执行的特征 并发执行的特征 顺序性：按照程序结构所指定的次序（可能有分支或循环） 封闭性：独占全部资源，计算机的状态只由于该程序的控制逻辑所决定 可再现性：初始条件相同则结果相同。如：可通过空指令控制时间关系。 并发执行的特征 间断(异步)性："走走停停"，一个程序可能走到中途停下来，失去原有的时序关系； 失去封闭性：共享资源，受其他程序的控制逻辑的影响。如：一个程序写到存储器中的数据可能被另一个程序修改，失去原有的不变特征。 失去可再现性：失去封闭性 －>失去可再现性；外界环境在程序的两次执行期间发生变化，失去原有的可重复特征。

程序 P(i) 针对共享变量的读集和写集 R(i)和W(i) 条件：任意两个程序P(i)和P(j)，有： 并发执行的条件：达到封闭性和可再现性 并发执行失去封闭性的原因是共享资源的影响，去掉这种影响就行了。1966年，由Bernstein给出并发执行的条件。（这里没有考虑执行速度的影响。） 程序 P(i) 针对共享变量的读集和写集 R(i)和W(i) 条件：任意两个程序P(i)和P(j)，有： R(i)W(j)=; W(i)R(j)=; W(i)W(j)=; 前两条保证一个程序的两次读之间数据不变化；最后一条保证写的结果不丢掉。 现在的问题是这个条件不好检查。

2.1.2 进程的定义和描述 1、进程的定义 比较典型的进程定义有： ⑴进程是程序的一次执行。 ⑵进程是一个程序及其数据在处理机上顺序执行时所发生的活动。 ⑶进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。 ⑷进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。

进程是一个具有一定独立功能的程序在一个数据集合上的一次动态执行过程。 其它 通常的程序是不能并发执行的，为使程序能独立运行，为之配置一进程控制块，即PCB（Process Control Block),而由程序段、相关数据段和PCB三部分便构成进程实体。 其它定义 进程是一个具有一定独立功能的程序在一个数据集合上的一次动态执行过程。

2. 进程的特征 动态性：动态性是进程的最基本特征。表现在，进程由创建而产生，由调度而执行，由撤销而消亡。即进程具有一定的生命周期。 独立性：各进程的地址空间相互独立，互不干扰。 并发性：指多个进程实体同存于内存中，且能在一段时间内同时运行。并发性是进程的重要特征。 异步性：指进程按各自独立的、不可预知的速度向前推进。 结构化：指进程可划分为代码段、数据段和核心段（在地址空间中）；核心段通常就是OS核心（由各个进程共享，包括各进程的PCB）

3. 进程与程序的区别 进程是动态的，程序是静态的：程序是有序代码的集合；进程是程序的执行。通常进程不可在计算机之间迁移；而程序通常对应着文件、静态和可以复制。 进程是暂时的，程序的永久的：进程是一个状态变化的过程，程序可长久保存。 进程与程序的组成不同：进程的组成包括程序、数据和进程控制块（即进程状态信息）。 进程具有并行性，而程序没有。在不考虑资源共享的情况下，各进程的执行是独立的，执行速度是异步的。程序不反映执行过程，所以不具有并行性。 进程与程序的对应关系：通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可包括多个程序。

4、进程的三种基本状态 运行中的进程可能具有下列三种状态： 1、就绪状态 当进程已分配了除CPU以外的所有必要资源后，只有再获得CPU，便可立即执行，进程的这种状态称为就绪状态。将就绪状态的多个进程排成一个队列，称为就绪队列。 2、执行状态 进程获得CPU，其程序正在执行。 3、阻塞状态 正在执行的进程由于发生某事件而暂时无法执行时，便放弃处理机而处于暂停状态，称为阻塞状态。致使进程阻塞的典型事件有： I/O请求，申请缓冲区等。

进程三种基本状态的转换 就绪 时间片完 I/O完成 进程调度 执行 阻塞 I/O请求

5. 进程控制块 (PCB, process control block) 进程控制块的作用是使一个在多道程序环境下不能独立运 行的程序，成为一个能独立运行的基本单位。OS是根据PCB来对并发执行的进程进行控制和管理的。 PCB是进程存在的唯一标志。 当系统创建一个新进程时，就为它建立一个PCB。进程结束时又收回PCB，进程也随之消亡。 由于PCB经常被系统访问，故其应常驻内存。

进程控制块的内容 进程标识符： 处理机状态： 进程调度信息： 进程控制信息： 进程内部标识符(process ID)，唯一，通常是一个整数； 进程外部标识符，它由创建者提供，通常由字母、数字组成。往往由用户访问该进程时使用； 处理机状态： 处理机状态信息主要由处理机的各种寄存器中的内容组成。 进程调度信息： 包括 进程状态、优先级、进程调度所需要的其它信息和事件组成。 进程控制信息： 程序和数据地址； 进程同步和通信机制； 资源清单； 链接指针；

6. PCB的组织方式 链表：同一状态的进程其PCB成一链表，多个状态对应多个不同的链表 各状态的进程形成不同的链表：就绪链表、阻塞链表 索引表：同一状态的进程归入一个index表（由index指向PCB），多个状态对应多个不同的index表 各状态的进行形成不同的索引表：就绪索引表、阻塞索引表

2.1.3 进程的状态转换 2.1.3.1 两状态进程模型 2.1.3.2 五状态进程模型 2.1.3.3 挂起进程模型

2.1.3.1 两状态进程模型

1. 状态 运行状态(Running)：占用处理机资源； 暂停状态(Not-Running)：等待进程调度分配处理机资源；

2. 转换 进程创建(Enter)：系统创建进程，形成PCB，分配所需资源，排入暂停进程表(可为一个队列)； 调度运行(Dispatch)：从暂停进程表中选择一个进程(要求已完成I/O操作)，进入运行状态； 暂停运行(Pause)：用完时间片或启动I/O操作后，放弃处理机，进入暂停进程表； 进程结束(Exit)：进程运行中止；

2.1.3.2 五状态进程模型 两状态模型无法区分暂停进程表中的可运行和阻塞，五状态模型就是对暂停状态的细化。 五状态进程模型(状态变迁)

五状态进程模型(单队列结构)

五状态进程模型(多队列结构)

1. 状态 运行状态(Running)：占用处理机资源；处于此状态的进程的数目小于等于CPU的数目。 在没有其他进程可以执行时（如所有进程都在阻塞状态），通常会自动执行系统的idle进程（相当于空操作）。 就绪状态(Ready)：进程已获得除处理机外的所需资源，等待分配处理机资源；只要分配CPU就可执行。 可以按多个优先级来划分队列，如：时间片用完－>低优，I/O完成－>中优，页面调入完成－>高优 阻塞状态(Blocked)：由于进程等待某种条件（如I/O操作或进程同步），在条件满足之前无法继续执行。该事件发生前即使把处理机分配给该进程，也无法运行。如：等待I/O操作的完成。

创建状态(New)：进程刚创建，但还不能运行(一种可能的原因是OS对并发进程数的限制)；如：分配和建立PCB表项（可能有数目限制）、建立资源表格（如打开文件表）并分配资源，加载程序并建立地址空间表。 结束状态(Exit)：进程已结束运行，回收除PCB之外的其他资源，并让其他进程从PCB中收集有关信息（如记帐，将退出码exit code传递给父进程）。

2. 转换 创建新进程：创建一个新进程，以运行一个程序。可能的原因为：用户登录、OS创建以提供某项服务、批处理作业。 收容(Admit, 也称为提交)：收容一个新进程，进入就绪状态。由于性能、内存、进程总数等原因，系统会限制并发进程总数。 调度运行(Dispatch)：从就绪进程表中选择一个进程，进入运行状态； 释放(Release)：由于进程完成或失败而中止进程运行，进入结束状态； 运行到结束：分为正常退出Exit和异常退出abort（执行超时或内存不够，非法指令或地址，I/O失败，被其他进程所终止） 就绪或阻塞到结束：可能的原因有：父进程可在任何时间中止子进程；

超时（Timeout）：由于用完时间片或高优先进程就绪等导致进程暂停运行； 事件等待（Event Wait）：进程要求的事件未出现而进入阻塞；可能的原因包括：申请系统服务或资源、通信、I/O操作等； 事件出现（Event Occurs）：进程等待的事件出现；如：操作完成、申请成功等； 注：对于五状态进程模型，一个重要的问题是当一个事件出现时如何检查阻塞进程表中的进程状态。当进程多时，对系统性能影响很大。一种可能的作法是按等待事件类型，排成多个队列。

2.1.3.3 挂起进程模型 ①终端用户的请求。 ②父进程请求。 ③负荷调节的需要。 ④操作系统的需要。 为了更好地管理和调度进程及适应系统的功能，在许多系统中都有“挂起”和“解挂”一个进程的功能。原因如下： ①终端用户的请求。 ②父进程请求。 ③负荷调节的需要。 ④操作系统的需要。

单挂起进程模型

双挂起进程模型

1. 状态 注：这里只列出了意义有变化或新的状态。 就绪状态(Ready)：进程在内存且可立即进入运行状态； 阻塞状态(Blocked)：进程在内存并等待某事件的出现； 阻塞挂起状态（Blocked, suspend）：进程在外存并等待某事件的出现； 就绪挂起状态（Ready, suspend）：进程在外存，但只要进入内存，即可运行；

2. 转换 挂起（Suspend）：把一个进程从内存转到外存；可能有以下几种情况： 阻塞到阻塞挂起：没有进程处于就绪状态或就绪进程要求更多内存资源时，会进行这种转换，以提交新进程或运行就绪进程； 就绪到就绪挂起：当有高优先级阻塞（系统认为会很快就绪的）进程和低优先级就绪进程时，系统会选择挂起低优先级就绪进程； 运行到就绪挂起：对抢先式分时系统，当有高优先级阻塞挂起进程因事件出现而进入就绪挂起时，系统可能会把运行进程转到就绪挂起状态； 激活（Activate）：把一个进程从外存转到内存；可能有以下几种情况： 就绪挂起到就绪：没有就绪进程或挂起就绪进程优先级高于就绪进程时，会进行这种转换； 阻塞挂起到阻塞：当一个进程释放足够内存时，系统会把一个高优先级阻塞挂起（系统认为会很快出现所等待的事件）进程；

事件出现（Event Occurs）：进程等待的事件出现；如：操作完成、申请成功等；可能的情况有： 阻塞到就绪：针对内存进程的事件出现； 阻塞挂起到就绪挂起：针对外存进程的事件出现； 收容(Admit)：收容一个新进程，进入就绪状态或就绪挂起状态。进入就绪挂起的原因是系统希望保持一个大的就绪进程表（挂起和非挂起）；

2.2 进程控制 进程控制是进程管理中最基本的功能。它用于创建一个新进程，终止一个进程，还有负责进程运行中的状态转换。 进程控制一般由OS的内核来完成。 1、进程的创建 进程图 进程图是用于描述一个进程的家族关系的有向图。图中节点表示进程。在进程Pi创建了Pj之后，pi称作Pj 的父进程，Pj是Pi的子进程。用一条由Pi指向Pj的有向边描述它们之间的父子关系。 返回

进程树 创建父进程的进程称为祖先进程 A B C D G E F

子进程可以继承父进程所拥有的资源。当子进程被撤销时，应将从父进程那里获得的资源全部归还给父进程。此外，在撤销父进程时，必须同时撤销其所以的子进程。 引起创建进程的事件： ㈠ 用户登录 若是合法用户登录，系统将创建一个进程。 ㈡ 作业调度 ㈢ 提供服务 ㈣ 应用请求

进程创建步骤 使用进程创建原语Create（）按下列步骤创建新进程： ①申请空白PCB ②为新进程分配资源 ③初始化进程控制块 ④将新进程插入就绪队列

2、进程的终止 1、引起进程终止的事件 ⑴ 正常结束 ⑵ 异常结束 常见的事件是：越界错误，保护错，非法指令，运行超时，算术错误等 ⑴ 正常结束 ⑵ 异常结束 常见的事件是：越界错误，保护错，非法指令，运行超时，算术错误等 ⑶ 外界干预 如操作系统或操作员干预，父进程请求，父进程终止

进程的终止过程 1、根据被终止进程的标识符，检索出该进程的PCB，从中读出该进程的状态。 2、 若被终止的进程处于执行状态，则终止该进程，并置 调度状态为真，重新调度。 3、 若该进程还有子进程，还应将其子进程终止。 4、 将被终止进程的所有资源，归还给父进程或系统。 5 将被终止进程从所在队列中移出。

3、进程的阻塞与唤醒 进程阻塞和唤醒的原因： 1、请求系统服务 2、启动某种操作 3、新数据尚未到达 4、无新工作可做 进程阻塞过程： 正在执行的进程，由于无法继续执行，进程便继续通过调用阻塞原语Block把自己阻塞。它是进程自身的一种主动行为。 进程唤醒过程： 当被阻塞进程所期待的事件出现时，则有关进程调用唤醒原语wakeup(),将等待进程唤醒。

4、进程的挂起与激活 1、进程的挂起 当出现引起进程挂起的事件时，系统利用挂起原语suspend()将指定进程或处于阻塞的进程挂起。 2、进程的激活 当发生激活进程的事件时，系统利用激活原语active()将指定进程激活。激活原语先将进程从外存调入内存，检查该进程的现行状态，将静止的改成就绪的，然后再调度。 返回

2.7线程(THREAD) 2.7.1 线程的引入 2.7.2 进程和线程的比较 2.7.3 线程举例 引入线程的目的是简化进程间的通信，以小的开销来提高进程内的并发程度。 2.7.1 线程的引入 2.7.2 进程和线程的比较 2.7.3 线程举例 返回

2.7.1 线程的引入 进程：资源分配单位（存储器、文件）和CPU调度（分派）单位。又称为"任务(task)" 只拥有必不可少的资源，如：线程状态、寄存器上下文和栈 同样具有就绪、阻塞和执行三种基本状态 线程的优点：减小并发执行的时间和空间开销（线程的创建、退出和调度），因此容许在系统中建立更多的线程来提高并发程度。 线程的创建时间比进程短； 线程的终止时间比进程短； 同进程内的线程切换时间比进程短； 由于同进程内线程间共享内存和文件资源，可直接进行不通过内核的通信；

线程的属性 在多线程os中，通常是一个进程包含多个线程。每个线程都是作为利用cpu的基本单位，是花费最小开销的实体。 1、轻型实体 2、独立调度和分派的基本单位 3、可并发执行性 4、共享进程资源 线程的状态 1、状态参数 在OS中，每个线程都是利用线程标识符和一组状态参数进行描述。状态参数包括：寄存器状态、堆栈、线程运行状态、优先级、线程专有存储器、信号屏蔽等。 2、线程运行状态

线程运行时有三种状态：执行状态、就绪状态、阻塞状态 线程的创建和终止 应用程序启动时，通常一个线程在执行。该线程被称作“初始化”线程。它可根据需要再去创建若干个线程。 线程也具有生命期，通常有两种方式：一种是自愿，另一种是强制终止。在大多数os中，线程被终止后，并不立即释放它占有的资源，只有当进程中的其它线程执行了分离函数后，被终止的线程才与资源分离。 多线程os中的进程 1、作为系统资源分配的单位。 2、可包括多个线程。 3、进程不是一个可执行实体。

进程与线程的关系

OS对线程的实现方式 内核线程(kernel-level thread) 依赖于OS核心，由内核的内部需求进行创建和撤销，用来执行一个指定的函数。Windows NT和OS/2支持内核线程； 内核维护进程和线程的上下文信息； 线程切换由内核完成； 一个线程发起系统调用而阻塞，不会影响其他线程的运行。 时间片分配给线程，所以多线程的进程获得更多CPU时间。

用户线程(user-level thread) 不依赖于OS核心，应用进程利用线程库提供创建、同步、调度和管理线程的函数来控制用户线程。如：数据库系统informix，图形处理Aldus PageMaker。调度由应用软件内部进行，通常采用非抢先式和更简单的规则，也无需用户态/核心态切换，所以速度特别快。一个线程发起系统调用而阻塞，则整个进程在等待。时间片分配给进程，多线程则每个线程就慢。 用户线程的维护由应用进程完成； 内核不了解用户线程的存在； 用户线程切换不需要内核特权； 用户线程调度算法可针对应用优化；

轻权进程(LightWeight Process) 它是内核支持的用户线程。一个进程可有一个或多个轻权进程，每个轻权进程由一个单独的内核线程来支持。

2.7.2 进程和线程的比较 地址空间和其他资源（如打开文件）：进程间相互独立，同一进程的各线程间共享－－某进程内的线程在其他进程不可见 通信：进程间通信IPC，线程间可以直接读写进程数据段（如全局变量）来进行通信－－需要进程同步和互斥手段的辅助，以保证数据的一致性 调度：线程上下文切换比进程上下文切换要快得多；

线程切换和进程切换

2.7.3 线程举例 1. SUN Solaris 2.3 Solaris支持内核线程(Kernel threads)、轻权进程(Lightweight Processes)和用户线程(User Level Threads)。一个进程可有大量用户线程；大量用户线程复用少量的轻权进程，不同的轻权进程分别对应不同的内核线程。

Solaris用户线程和轻权进程

用户级线程在使用系统调用时（如文件读写），需要“捆绑(bound)”在一个LWP上。 永久捆绑：一个LWP固定被一个用户级线程占用，该LWP移到LWP池之外 临时捆绑：从LWP池中临时分配一个未被占用的LWP 在使用系统调用时，如果所有LWP已被其他用户级线程所占用（捆绑），则该线程阻塞直到有可用的LWP－－例如6个用户级线程，而LWP池中有2个LWP 如果LWP执行系统调用时阻塞（如read()调用），则当前捆绑在LWP上的用户级线程也阻塞。

用户线程、轻权进程和核心线程的关系

有关的C库函数 有关的系统调用 /* 创建用户级线程 */ /* 创建用户级线程 */ int thr_create(void *stack_base, size_t stack_size, void *(*start_routine)(void *), void *arg, long flags, thread_t *new_thread_id); 其中flags包括：THR_BOUND（永久捆绑）, THR_NEW_LWP（创建新LWP放入LWP池），若两者同时指定则创建两个新LWP，一个永久捆绑而另一个放入LWP池 有关的系统调用 /* 在当前进程中创建LWP */ int _lwp_create(ucontext_t *contextp, unsigned long flags, lwpid_t *new_lwp_id); /* 构造LWP上下文 */ void _lwp_makecontext(ucontext_t *ucp, void (*start_routine)( void *), void *arg, void *private, caddr_t stack_base, size_t stack_size); /* 注意：没有进行"捆绑"操作的系统调用 */

2. Windows NT 就绪状态(Ready)：进程已获得除处理机外的所需资源，等待执行。 备用状态(Standby)：特定处理器的执行对象，系统中每个处理器上只能有一个处于备用状态的线程。 运行状态(Running)：完成描述表切换，线程进入运行状态，直到内核抢先、时间片用完、线程终止或进行等待状态。 等待状态(Waiting)：线程等待对象句柄，以同步它的执行。等待结束时，根据优先级进入运行、就绪状态。 转换状态(Transition)：线程在准备执行而其内核堆栈处于外存时，线程进入转换状态；当其内核堆栈调回内存，线程进入就绪状态。 终止状态(Terminated)：线程执行完就进入终止状态；如执行体有一指向线程对象的指针，可将线程对象重新初始化，并再次使用。 初始化状态(Initialized)：线程创建过程中的线程状态；

Windows NT的线程状态

Windows 2000线程状态

Windows NT的线程状态

NT线程的有关API CreateThread()函数在调用进程的地址空间上创建一个线程，以执行指定的函数；返回值为所创建线程的句柄。 ExitThread()函数用于结束本线程。 SuspendThread()函数用于挂起指定的线程。 ResumeThread()函数递减指定线程的挂起计数，挂起计数为0时，线程恢复执行。

2.3 进程同步 2.3.1进程同步的基本概念 2.3.2 信号量机制(semaphore) 2.3.3信号量的应用 2.3 进程同步 在OS中引入进程，虽然提高了资源的利用率和系统的吞吐量，但由于进程的异步性，也会给系统造成混乱。进程同步的主要任务是使并发执行的诸进程之间能有效地共享资源和相互合作，从而使程序的执行具有可 再现性。 2.3.1进程同步的基本概念 2.3.2 信号量机制(semaphore) 2.3.3信号量的应用 返回

2.3.1进程同步的基本概念 1、两种形式的制约关系 2、临界资源(Critical Resouce) 3、临界区(Critical Section) 4、同步机制遵循的规则

1、两种形式的制约关系 在多道程序环境下，当程序并发执行时，由于资源共享和进程合作，使处于一个系统中的诸进程间，可能存在以下两种形式的制约关系： 1、间接制约关系：同处于一个系统的进程，必然共享着某种系统资源，如CPU, I/O等。间接制约关系源于这种资源共享。 2、直接制约关系：这种制约关系主要源于进程间的合作。 间接制约：进行竞争－－独占分配到的部分或全部共享资源，“互斥” 直接制约：进行协作－－等待来自其他进程的信息，“同步”

2、临界资源 进程间资源访问冲突 共享变量的修改冲突 操作顺序冲突 把一段时间内只允许一个进程访问的资源称为临界资源或独占资源。 计算机系统中的大多数物理设备、以及某些软件中所用的栈、变量和表格，都属于临界资源。如打印机、磁带机等。它们要求被互斥共享。 进程间资源访问冲突 共享变量的修改冲突 操作顺序冲突

共享变量的修改冲突

例子： 编制一个记录序列复制程序，它把文件 f 中的每一个记录先读 到缓冲区 s 中，然后 s 复制到缓冲区 t 中，最后把它写到文件 g 中。假定缓冲区 s 和 t 的大小只能存放一个记录，共有m个记录要复制。要求文件g上的记录顺序和记录个数与文件f上的一致。 f g 1 2 3 m 1 输入缓冲区s put copy s t get 输出缓冲区 t

这个程序有三个子程序get、copy、put组成。get 负责 按序从文件f 中得到记录，并把它送入s；copy负责把s中的记录复制到t ；put 负责把t 中的记录顺序写入g中。 可以 把 get ,copy, put 当作三个并发进程来处理。并发执行时，由于get和copy共享缓冲区s, copy和put 共享缓冲区t ,所以应对它们的执行次序加以限制，否则会发生错误。

有3个进程：get, copy和put，它们对2个存储区域s、t进行操作。 操作顺序冲突

有6种可能的操作顺序，只有一种结果是正确的。

例3 生产者－消费者问题 这是一个著名的进程同步问题。描述如下： 例3 生产者－消费者问题 这是一个著名的进程同步问题。描述如下： 有一群生产者进程在生产产品，并将这些产品提供给消费者进程消费。为使这两种进程能并发执行，在两者之间设置了一个具有n个缓冲区的缓冲池。生产者将产品放入缓冲池中的一个缓冲区，消费者可以从缓冲区中取走产品去消费。不允许消费者进程到一个空缓冲区去取产品，也不允许生产者进程向一个已装满产品且未被取走的缓冲区投放产品。

利用一个数组表示具有n个缓冲区的缓冲池。指针 in表示下一个可投放产品的缓冲区，指针out 表示下一个可以获取产品的缓冲区。每当生产者进程投放一个产品，输入指针加1，每当消费者进程取走一个产品，输出指针减1。由于缓冲池是循环缓冲的，可以表示下列形式： in:= (in+1) mod n ; out:=(out +1) mod n ; 当 （in +1) mod n = out 时，表示缓冲池满，而当 in=out 时，表示缓冲池空。 引入一个整型变量－－counter，其初始值为0，表示产品的个数。当生产者投放一个产品时，counter加1。当消费者取出一个产品时，counter减1。生产者、消费者共享的变量如下： var n : integer ; type item : … ; var buffer : array[0,1,…,n-1] of item ; in , out : 0,1,…,n-1; counter : 0,1,…,n;

在生产者进程中使用一局部变量，nextp, 表示暂时存放每次刚生产出来的产品；在消费者进程中，使用一个局部变量nextc，用于存放每次要消费的产品。生产者－消费者进程描述如下： procudure: repeat . procedure an item in nextp; while counter= n do no-op; buffer[in]:= nextp ; in := in +1 mod n ; counter: = counter + 1; until false;

Consumer : repeat while counter = 0 do no-op; nextc := buffer[out]; out := (out+1) mod n ; counter := counter – 1; consumer the item in nextc ; until false ; 上面生产者、消费者程序顺序执行时，都正确。但若并发执行，则会出现差错。原因在于counter 是一个共享变量。 对counter 的描述如下： r1 := counter； ② r1 := r1＋ 1；③ counter := r1 ; r2 := counter ; ⑤ r2:= r2 – 1; ⑥ counter := r2; 若按下列顺序执行，则会出现错误。 ① ②④⑤③⑥ 返回

进程的交互关系：可以按照相互感知的程度来分类 互斥，指多个进程不能同时使用同一个资源； 死锁，指多个进程互不相让，都得不到足够的资源； 饥饿，指一个进程一直得不到资源（其他进程可能轮流占用资源）

3、临界区 临界区的访问 Repeat Until false 临界区

临界区(critical section)：进程中访问临界资源的一段代码。 进入区(entry section)：在进入临界区之前，检查可否进入临界区的一段代码。如果可以进入临界区，通常设置相应"正在访问临界区"标志 退出区(exit section)：用于将"正在访问临界区"标志清除。 剩余区(remainder section)：代码中的其余部分。

4、同步机制应遵循的准则 空闲则入：其他进程均不处于临界区； 忙则等待：已有进程处于其临界区； 有限等待：等待进入临界区的进程不能"死等"； 让权等待：不能进入临界区的进程，应释放CPU（如转换到阻塞状态）

2. 3信号量(semaphore)机制 2.3.1 信号量和P、V原语 2.3.2 信号量集 2.3.3 信号量的应用 1965年，荷兰学者 Dijkstra 提出的信号量机制是一种卓有成效的进程同步工具。在长期且广泛的应用中，信号量机制又得到很大的发展，它从整型信号量经记录型信号量，进而发展为“信号量集”机制。现在，信号量机制广泛地应用于单处理机和多处理机系统以及计算机网络中。 · 2.3.1 信号量和P、V原语 2.3.2 信号量集 2.3.3 信号量的应用

2.3.1 信号量和P、V原语 由Dijkstra提出了一种实现进程同步与互斥的通用方法，称为信号量s及其上的P(s),V(s)操作。（P、V分别是荷兰语的pass(passeren)和increment(verhoog)），这是一种卓有成效的进程同步机制。（现在称为wait和signal操作） 在操作系统中，信号量是一个与队列有关的、具有非负初值的整型变量。其值除了初始化外，只能由下面定义的p、v操作来改变。操作系统利用它的值的变化，对进程和资源进行管理，实现进程间的同步和互斥。一个信号量s由值s.value和队列s.queue组成。 每个信号量s的值s.value，大于等于0时，表示可供并发进程使用的资源实体数。当它小于0时，表示正在等待使用临界区的进程数。信号量的进程等待队列s.queue，存放阻塞在该信号量的各个进程。

建立一个信号量，必须说明所建信号量代表的意义，以及初始化。－－若初始化为非负值，表示当前的空闲资源数，若为负值其绝对值表示当前等待进入临界区的进程数。 信号量只能通过初始化和两个标准的原语来访问。作为OS核心代码执行，不受进程调度的打断。 1、P(s)操作的定义（wait(s) ) 当一个进程对信号量s 执行P操作时，应顺序做下列两个不可分割的动作。 ① S.value = S.value – 1 ; ② 若 S.value ≥ 0，则本进程继续执行；若 S.value ＜0 , 则本进程由运行状态变成等待状态，令其到S.queue队列上排队，直到别的进程在S上执行V操作而释放它为止。

开始 S.value= S.value – 1 ; 是 S.value ≥ 0 S < 0 返回 调用进程入等待队列 转入进程调度

2、 V(S)操作的定义( signal(s)) 当一个进程对信号量s 执行V操作时，应顺序做下列两个不可分割的动作。 ① S.value = S.value ＋1 ; ② 若 S.value > 0，则本进程继续执行；若 S.value ≤0 , 则从S.queue队列中移出一个等待进程加以唤醒，使它从等待状态变为就绪状态，本进程继续允许。

开始 S.value= S.value +1 ; 否 S.value ≤0 是 返回 唤醒等待队列中的一个进程 返回或 转入进程调度

说明 1、信号量有自身的物理意义，它的值的大小表示要管理的某类资源的数量，与其相关的队列是等待申请这种资源的进程的等待队列。 2、S>0，表示还有该资源可以分配；S<0,其绝对值恰好表示在相关队列中，等待资源的进程数目。 3、某进程在S上做一次P操作，意味着要求分配给它这 类资源中的一个单位，如果在S减1后，S≥0,表明该进程能得到这种资源的一个单位；若S<0, 表示当前已无资源可分配，于是提出申请的进程只能被阻塞，放到S的队列上排队等候。

4、 某进程在S上做一次V操作，意味着它释放了原先占用的一个单位资源。若在S上加1后，S>0 , 表示申请此种资源的等待队列上已没有进程等待；若S≤0,则表示申请资源的等待队列中有申请资源未得到满足而在此等待的进程，故应按照一定的原则唤醒队列上的一个进程 ，让它转到就绪队列以获得所需的资源，而V操作的进程仍运行下去。 返回

3. 利用信号量实现互斥 为临界资源设置一个互斥信号量mutex(MUTual Exclusion)，其初值为1；在每个进程中将临界区代码置于P(mutex)和V(mutex)原语之间 必须成对使用P和V原语：遗漏P原语则不能保证互斥访问，遗漏V原语则不能在使用临界资源之后将其释放（给其他等待的进程）；P、V原语不能次序错误、重复或遗漏

var mutex : integer; mutex:= 1; Parbegin process A : begin repeat P(mutex); 临界资源 V(mutex); remainder section; until false; end; process B : begin P(mutex); 临界资源；V(mutex); parend

2. 利用信号量来描述前趋关系 前趋关系：并发执行的进程P1和P2中，分别有代码C1和C2，要求C1在C2开始前完成； 为每个前趋关系设置一个互斥信号量S12，其初值为0

返回 s1 a b s2 s3 d c e s4 s5 f g s6

2.3.2 信号量集 信号量集用于同时需要多个资源时的信号量操作； 1. AND型信号量集 AND型信号量集用于同时需要多种资源且每种资源占用一个信号量时的信号量操作； 一段处理代码需要同时获取两个或多个临界资源――可能死锁：各进程分别获得部分临界资源，然后等待其余的临界资源，“各不相让”。例如，进程A、B对两个信号量S1、S2进行操作，S1、S2的初始值为1，即： process A process B P(S1) ; P(S2) ; P(S2) ; P(S1); 若进程A、B交替执行，则导致死锁。

基本思想：在一个原语中，将一段代码同时需要的多个临界资源，要么全部分配给它，要么一个都不分配。称为Swait(Simultaneous Wait)。在Swait时，各个信号量的次序并不重要，虽然会影响进程归入哪个阻塞队列，但是由于是对资源全部分配或不分配，所以总有进程获得全部资源并在推进之后释放资源，因此不会死锁。

Swait(S1, S2, …, Sn) //P原语； { while (TRUE) if (S1 >=1 && S2 >= 1 && … && Sn >= 1) { //满足资源要求时的处理； for (i = 1; i <= n; ++i) --Si; //注：与wait的处理不同，这里是在确信可满足 //资源要求时，才进行减1操作； break; } else { //某些资源不够时的处理； 调用进程进入第一个小于1信号量的等待队列Sj.queue; 阻塞调用进程;

Ssignal(S1, S2, …, Sn) { for (i = 1; i <= n; ++i) ++Si; //释放占用的资源； for (each process P waiting in Si.queue) //检查每种资源的等待队列的所有进程； 从等待队列Si.queue中取出进程P; if (判断进程P是否通过Swait中的测试) //注：与signal不同，这里要进行重新判断； { //通过检查（资源够用）时的处理； 进程P进入就绪队列; } else { //未通过检查（资源不够用）时的处理； 进程P进入某等待队列；

2. 一般“信号量集” 一次需要N个某类临界资源时，就要进行N次wait操作－－低效又可能死锁 一般信号量集用于同时需要多种资源、每种资源的占用数目不同、且可分配的资源还存在一个临界值时的处理；（所谓的临界值，就是指在某些情况下，当资源数量低于某一下限值时，便不予分配。这个下限值称作临界值。） 一次需要N个某类临界资源时，就要进行N次wait操作－－低效又可能死锁 基本思想：在AND型信号量集的基础上进行扩充：进程对信号量Si的下限值为ti（用于信号量的判断，即Si <= ti，表示资源数量低于ti时，便不予分配），需求值为di（用于信号量的增减，即Si = Si - di和Si = Si + di） Swait(S1, t1, d1; ...; Sn, tn, dn); Ssignal(S1, d1; ...; Sn, dn);

Swait( S1,t1,d1,……, Sn, tn, dn) if ( S1≥t1 and … Sn≥tn ) then for i := 1 to n do Si := Si- di; endfor else 进程释放其占用的全部临界资源，插入到信号量的就绪队列中，等待调用。 end if Ssignal( S1,d1,……,Sn, dn ） Si := Si +di ; 唤醒信号量队列中的进程，放入到就绪队列。 End for

一般"信号量集"未必成对使用Swait和Ssignal：如：一起申请，但不一起释放； 一般"信号量集"的几种特定情况： Swait(S, d, d)表示每次申请d个资源，当少于d个时，便不分配；此时，信号量集中，只有一个信号量－－s。 Swait(S, 1, 1)表示互斥信号量； Swait(S, 1, 0)作为一个可控开关 当S>=1时，允许多个进程进入临界区； 当S=0时，禁止任何进程进入临界区； 一般"信号量集"未必成对使用Swait和Ssignal：如：一起申请，但不一起释放； 返回

2.2.3 经典进程同步问题 1. 生产者－消费者问题(the producer-consumer problem) 返回 1. 生产者－消费者问题(the producer-consumer problem) 问题描述：若干进程通过有限的共享缓冲区交换数据。其中，“生产者”进程不断写入，而“消费者”进程不断读出；共享缓冲区共有N个；生产者和消费者必须保持同步。

由于前面讨论时，没有涉及进程的互斥和同步问题，所以造成计数器counter的不确定性。 利用互斥信号量mutex实现诸进程对缓冲池的互斥使用。利用信号量empty和full 分别表示缓冲池中空缓冲区和满缓冲区的数量。假定这些生产者和消费者相互等效，只要缓冲池不满，生产者可将消息送入缓冲池。只要缓冲池未空，消费者便可从缓冲池中取走一个消息。

每个进程中各个P操作的次序是重要的：先检查资源数目，再检查是否互斥――否则可能死锁(为什么？) 采用信号量机制： full是"满"数目，初值为0，empty是"空"数目，初值为N。实际上，full和empty是同一个含义：full + empty == N mutex用于访问缓冲池时的互斥，初值是1 每个进程中各个P操作的次序是重要的：先检查资源数目，再检查是否互斥――否则可能死锁(为什么？)

生产者－消费者算法描述： Var mutex ,empty, full : integer ; buffer : array [0,1,…,n] of item; in , out : integer ; nextp, nextc : item ; mutex := 1; empty := n ; full := 0 ; in := 0 ; out := 0 ; Procedure procedurer begin repeat … procedure an item in nextp ; wait( empty); wait( mutex); buffer[in]:= nextp ; in := ( in +1) mod n ; signal( mutex); signal(full) ; until false; end ; end;

Procedure consumer begin repeat wait(full ); wait( mutex); nextc := buffer( out) ; out := ( out +1） mod n;; signal( mutex ); signal(empty); consumer the item in nexc ; until false; end; BEGIN (主程序） parbegin procedurer 1 ; procedurer 2; procedurer 3: …… procedurer M; consumer 1 ; consumer 2 ;…… consumer n ; parend END

利用 AND信号量解决生产者－消费者问题 注意事项： 1、每个程序中，用于实现互斥的wait(mutex)和 signal(mutex)必须成对出现。 2、对资源信号量full 和empty 的wait、signal操作，同样需要成对出现，但它们分别处于不同的程序中。 3、在每个程序中，多个wait操作顺序不能颠倒，应首先对资源信号量的wait操作，然后再执行对互斥信号量的wait操作，否则可能引起死锁 利用 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)

Var mutex ,empty, full : integer ; buffer : array [0,1,…,n] of item; in , out : integer ; nextp, nextc : item ; mutex := 1; empty := n ; full := 0 ; in := 0 ; out := 0 ; Procedure procedurer begin repeat … procedure an item in nextp ; Swait( empty,mutex); buffer[in]:= nextp ; in := ( in +1) mod n ; Ssignal( mutex, full); until false; end ;

Procedure consumer begin repeat Swait(full, mutex ); nextc := buffer( out) ; out := ( out +1） mod n; Ssignal( mutex , empty); consumer the item in nexc ; until false; end;

2. 读者－写者问题(the readers-writers problem) 一个数据文件或记录，可被多个进程共享。只要求读文件的进程称为“Reader”进程，其它进程称为“Writer”进程。允许多个进程同时读一个共享对象，但不允许一个Writer进程和其它Reader进程或Writer进程同时访问共享对象。所谓的“读者－写者问题”是 保证一个Writer进程必须与其它进程互斥地访问共享对象的同步问题。

问题描述：对共享资源的读写操作，任一时刻“写者”最多只允许一个，而“读者”则允许多个 “读－写”互斥， “写－写”互斥， "读－读"允许

为实现Reader与Writer进程间在读或写时的互斥而设置了一个互斥信号量Wmutex。 设置一个整型变量Rcount记录正在读的进程数目。由于只要有一个Reader进程在读，便不允许Writer进程去写。因此，仅当Rcount＝0时，Reader进程才需要执行Wait(Wmutex)操作。若Wait(Wmutex)操作成功，Reader进程便可去读。相应地，Rcount加1。 同理，当Reader进程读完数据后，在退出之前，Rcount减1，若其值为0，表示没有其它读进程，须执行signal(Wmutex)操作，以便让Writer进程写。 又因为Rcount是一个可被多个Reader进程访问的临界资源，因此，应该设置一个互斥信号量Rmutex进行互斥。

采用信号量机制： Wmutex表示"允许写"，初值是1。 公共变量Rcount表示“正在读”的进程数，初值是0； Rmutex表示对Rcount的互斥操作，初值是1。

Var Rmutex,Wmutex,Rcount : integer ; begin parbegin reader: begin repeat wait(Rmutex); if Rcount=0 then wait(Wmutex); Rcount:= Rcount +1; signal(Rmutex); ….. Read data …… wait( Rmutex); Rcount := Rcount- 1; if Rcount = 0 then signal(Wmutex); until false; end;

Writer: begin repeat wait(Wmutex); write data ; signal(Wmutex) ; until false; end; Parend; end

采用一般“信号量集”机制：问题增加一个限制条件：同时读的“读者”最多R个,为此引入一个信号量L，赋予其初值为R。通过执行wait(L,1,1)，控制读者的数目。 Wmutex表示"允许写"，初值是1 L表示"允许读者数目"，初值为R

Var L，Wmutex : integer ; L:= R ; Wmutex := 1; Begin parbegin reader : begin repeat Swait( L,1,1); Swait(Wmutex, 1, 0); … read data … Ssignal( L,1); until false; end writer : begin

repeat Swait(Wmutex, 1,1 ; L, R,0); write data ; Ssignal(Wmutex, 1); until false ; end parend 其中，Swait(Wmutex, 1,0)语句起着开关作用。只要无Writer进程进入，Wmutex＝1，Reader进程就可以进入读。但只要一旦有Writer进程进入时，其Wmutex＝0 任何Reader进程就无法进入读。Swait(Wmutex,1,1,L,R,0)语句表示仅当既无Writer进程写入又无Reader进程在读，Writer进程才能进入临界区写。

3. 哲学家进餐问题 (the dining philosophers problem) 问题描述：（由Dijkstra首先提出并解决）5个哲学家围绕一张圆桌而坐，桌子上放着5支筷子，每两个哲学家之间放一支；哲学家的动作包括思考和进餐，进餐时需要同时拿起他左边和右边的两支筷子，思考时则同时将两支筷子放回原处。如何保证哲学家们的动作有序进行？如：不出现相邻者同时要求进餐；不出现有人永远拿不到筷子；

放在桌子上的筷子是临界资源，在一段时间内只供一位哲学家使用。为了实现对筷子的互斥使用，可以用一个信号量表示一支筷子。由这5个信号量构成信号量数组，其描述如下： Var chopstick : array[0,…,4] of semaphore ; 所有信号量都被初始化为1，第 I 位哲学家的活动可描述为： repeat wait(chopstick[i]); wait(chopstick[i+1]); eat ; signal(chopstick[i]); signal(chopstick[i+1]); think; until false;

上述解法可保证不会有两个相邻的哲学家同时进餐，但有时可能引起死锁。对于这样的死锁问题，可采取以下几种解决方法。 1、至多允许有四位哲学家同时拿起左边的筷子，最终能保证至少有一位哲学家能够进餐。 2、仅当哲学家的左右两只筷子均可用时，才允许他拿起筷子进餐。 3、 规定奇数哲学家先拿起他左边的筷子，然后再拿右边的筷子。而偶数哲学家则相反。

2.6 管程(monitor) 用信号量可实现进程间的同步，但由于信号量的控制分布在整个程序中，其正确性分析很困难。管程是管理进程间同步的机制，它保证进程互斥地访问共享变量，并方便地阻塞和唤醒进程。管程可以函数库的形式实现。相比之下，管程比信号量好控制。

1. 信号量同步的缺点 同步操作分散：信号量机制中，同步操作分散在各个进程中，使用不当就可能导致各进程死锁（如P、V操作的次序错误、重复或遗漏） 易读性差：要了解对于一组共享变量及信号量的操作是否正确，必须通读整个系统或者并发程序； 不利于修改和维护：各模块的独立性差，任一组变量或一段代码的修改都可能影响全局； 正确性难以保证：操作系统或并发程序通常很大，很难保证这样一个复杂的系统没有逻辑错误；

2. 管程的引入 1973年，Hoare和Hanson所提出；其基本思想是把信号量及其操作原语封装在一个对象内部。即：将共享变量以及对共享变量能够进行的所有操作集中在一个模块中。 管程的定义：管程是关于共享资源的数据结构及一组针对该资源的操作过程所构成的软件模块。 管程可增强模块的独立性：系统按资源管理的观点分解成若干模块，用数据表示抽象系统资源，同时分析了共享资源和专用资源在管理上的差别，按不同的管理方式定义模块的类型和结构，使同步操作相对集中，从而增加了模块的相对独立性 引入管程可提高代码的可读性，便于修改和维护，正确性易于保证：采用集中式同步机制。一个操作系统或并发程序由若干个这样的模块所构成，一个模块通常较短，模块之间关系清晰。

3. 管程的主要特性 模块化：一个管程是一个基本程序单位，可以单独编译； 抽象数据类型：管程是一种特殊的数据类型，其中不仅有数据，而且有对数据进行操作的代码 信息封装：管程是半透明的，管程中的外部过程（函数）实现了某些功能，至于这些功能是怎样实现的，在其外部则是不可见的；

2. 管程的实现要素 管程中的共享变量在管程外部是不可见的，外部只能通过调用管程中所说明的外部过程（函数）来间接地访问管程中的共享变量； 为了保证管程共享变量的数据完整性，规定管程互斥进入； 管程通常是用来管理资源的，因而在管程中应当设有进程等待队列以及相应的等待及唤醒操作；

5. 管程中的多个进程进入 当一个进入管程的进程执行等待操作时，它应当释放管程的互斥权；当一个进入管程的进程执行唤醒操作时（如Ｐ唤醒Ｑ），管程中便存在两个同时处于活动状态的进程。 管程中的唤醒切换方法： P等待Q继续，直到Q等待或退出； Q等待P继续，直到P等待或退出； 规定唤醒为管程中最后一个可执行的操作；

入口等待队列：因为管程是互斥进入的，所以当一个进程试图进入一个巳被占用的管程时它应当在管程的入口处等待，因而在管程的入口处应当有一个进程等待队列，称作入口等待队列。 紧急等待队列：如果进程Ｐ唤醒进程Ｑ，则Ｐ等待Ｑ继续，如果进程Ｑ在执行又唤醒进程Ｒ，则Ｑ等待Ｒ继续，...，如此，在管程内部，由于执行唤醒操作，可能会出现多个等待进程（已被唤醒，但由于管程的互斥进入而等待），因而还需要有一个进程等待队列，这个等待队列被称为紧急等待队列。它的优先级应当高于入口等待队列的优先级。

6. 条件变量(condition) 由于管程通常是用于管理资源的，因而在管程内部，应当存在某种等待机制。当进入管程的进程因资源被占用等原因不能继续运行时使其等待。为此在管程内部可以说明和使用一种特殊类型的变量----条件变量。每个表示一种等待原因，并不取具体数值－－相当于每个原因对应一个队列。

同步操作原语cwait和csignal：针对条件变量c，cwait(c)将自己阻塞在c队列中，csignal(c)将c队列中的一个进程唤醒。 cwait（c）：如果紧急等待队列非空，则唤醒第一个等待者；否则释放管程的互斥权，执行此操作的进程排入c队列尾部（紧急等待队列与c队列的关系：紧急等待队列是由于管程的互斥进入而等待的队列，而c队列是因资源被占用而等待的队列） csignal（c）：如果c队列为空，则相当于空操作，执行此操作的进程继续；否则唤醒第一个等待者，执行此操作的进程排入紧急等待队列的尾部 若进程P唤醒进程Q，则随后可有两种执行方式（进程P、Q都是管程中的进程） P等待，直到执行Q离开管程或下一次等待。Hoare采用。 Q送入Ready队列，直到执行P离开管程或下一次等待。1980年，Lampson和Redell采用。原语由csignal(x)改为cnotify(x)。

7. 管程的格式 TYPE monitor_name = MONITOR; 共享变量说明 define 本管程内所定义、本管程外可调用的过程（函数）名字表 use 本管程外所定义、本管程内将调用的过程（函数）名字表 PROCEDURE 过程名（形参表）； 过程局部变量说明； BEGIN 语句序列； END; ......

FUNCTION 函数名（形参表）：值类型； 函数局部变量说明； BEGIN 语句序列； END; ...... 共享变量初始化语句序列；

8. 管程的的组成 名称：为每个共享资源设立一个管程 数据结构说明：一组局部于管程的控制变量 操作原语：对控制变量和临界资源进行操作的一组原语过程（程序代码），是访问该管程的唯一途径。这些原语本身是互斥的，任一时刻只允许一个进程去调用，其余需要访问的进程就等待。 初始化代码：对控制变量进行初始化的代码

TYPE one_instance=RECORD mutex:semaphore;（入口互斥队列类型，初值1） urgent:semaphore;（紧急等待队列类型，初值0） urgent_count:integer;（紧急等待队列计数类型，初值0） END; TYPE monitor_elements=MODULE; define enter,leave,wait,signal; mutex（入口互斥队列） urgent（紧急等待队列） urgent_count（紧急等待计数）

PROCEDURE enter(VAR instance:one_instance); BEGIN P(instance.mutex) END; PROCEDURE leave(VAR instance:one_instance); IF instance.urgent_count >0 THEN BEGIN instance.urgent--; V(instance.urgent) END ELSE V(instance.mutex)

PROCEDURE wait(VAR instance:one_instance; VAR s:semephore;VAR count:integer); BEGIN count++; IF instance.urgent_count>0 THEN instance.urgent_count--; V(instance.urgent) END ELSE V(instance. mutex); P(s); END;

PROCEDURE signal(VAR instance:one_instance; VAR s:semaphore;VAR count:integer); BEGIN IF count>0 THEN count--; instance.urgent_count++; V(s); P(instance.urgent) END END;

9. 例子：生产者－消费者问题 Type producer-consumer Monitor VAR buffer : array[0..n] of Record ; In, out ,count : integer ; notempty, notfull : condition ; Procedure append(x : Record ); begin if count =n then waitc(notempty);/缓冲区满，等待/ buffer[in] = x; in:= (in +1) mod n ; count:= count + 1; signalc(notfull); end

Procedure take(x : Record); Begin if count=0 then waitc(notfull); /缓冲区空，等待/ x := buffer[out]; out := (out +1) mod n ; count := count -1 ; signalc(notempty); End; Begin in:= 0; out := 0; count := 0; End;/管程体，初始化/ Procedure producer; var x: Record; repeat 生产 x; append(x); Forever End ;

Procedure consumer ; Var x : Record ; Begin repeat take(x) ; 消费或处理 x; Forever End; Begin/主程序/ parbegin producer ; …… consumer; Parend

10. 管程和进程的异同点 设置进程和管程的目的不同 系统管理数据结构 管程被进程调用 管程是操作系统的固有成分，无创建和撤消 进程：PCB 管程：等待队列 管程被进程调用 管程是操作系统的固有成分，无创建和撤消 返回

2.2.6 进程互斥和同步举例 2.2.6.1 Solaris 2.3 2.2.6.2 Windows NT

2.2.6.1 Solaris 2.3 支持信号量和信号量集，通过semaphore ID来标识 有关的系统调用： 获取信号量集semget（依据用户给出的整数值key，创建新信号量或打开现有信号量，返回一个信号量ID） 信号量控制操作semctl semop（对信号量的原子操作）

2.2.6.2 Windows NT Mutex对象：互斥对象，相当于互斥信号量，在一个时刻只能被一个线程使用。有关的API： 对象可用(signaled state)表示该对象不被任何线程使用或所有； 1. NT支持的三种同步对象 对象名称是由用户给出的字符串。不同进程中用同样的名称来创建或打开对象，从而获得该对象在本进程的句柄。 Mutex对象：互斥对象，相当于互斥信号量，在一个时刻只能被一个线程使用。有关的API： CreateMutex创建一个互斥对象，返回对象句柄； OpenMutex返回一个已存在的互斥对象的句柄，用于后续访问； ReleaseMutex释放对互斥对象的占用，使之成为可用；

Semaphore对象：相当于资源信号量，取值在0到指定最大值之间，用于限制并发访问的线程数。有关的API： CreateSemaphore创建一个信号量对象，指定最大值和初值，返回对象句柄； OpenSemaphore返回一个已存在的信号量对象的句柄，用于后续访问； ReleaseSemaphore释放对信号量对象的占用；

Event对象：事件对象，相当于"触发器"，可通知一个或多个线程某事件的出现。有关的API： CreateEvent创建一个事件对象，返回对象句柄； OpenEvent返回一个已存在的事件对象的句柄，用于后续访问； SetEvent和PulseEvent设置指定事件对象为可用状态； ResetEvent设置指定事件对象为不可用状态（nonsignaled）；手工复位，并唤醒所有等待线程；

2. 同步对象等待 (1) WaitForSingleObject在指定的时间内等待指定对象为可用状态(signaled state)； DWORD WaitForSingleObject( HANDLE hHandle, // handle of object to wait for DWORD dwMilliseconds // time-out interval in milliseconds ); (2) WaitForMultipleObjects在指定的时间内等待多个对象为可用状态； DWORD WaitForMultipleObjects( DWORD nCount, //对象句柄数组中的句柄数； CONST HANDLE *lpHandles, // 指向对象句柄数组的指针，数组中可包括多种对象句柄； BOOL bWaitAll, // 等待标志：TRUE表示所有对象同时可用，FALSE表示至少一个对象可用； DWORD dwMilliseconds // 等待超时时限；

3. 子进程对同步对象的继承 对象在创建时指定可否被子进程继承，另外还要把对象的句柄通过命令行参数传递给子进程（才能引用该对象）。DuplicateHandle可以将对象句柄复制给指定的另一个进程； BOOL DuplicateHandle( HANDLE hSourceProcessHandle, //被复制对象句柄所在进程的进程对象句柄； HANDLE hSourceHandle, //被复制对象句柄； HANDLE hTargetProcessHandle, //复制后对象句柄所在进程的进程对象句柄； LPHANDLE lpTargetHandle, //指向复制后对象句柄的指针； DWORD dwDesiredAccess, //复制后对象句柄的访问类型，不同类型对象的访问类型会不同； BOOL bInheritHandle,//复制后对象句柄在子进程中的继承方式； DWORD dwOptions //选项； );

2. 其他同步方法 Critical Section对象：只能在同一进程内使用的临界区，同一进程内各线程对它的访问是互斥进行的。把变量说明为CRITICAL_SECTION类型，就可作为临界区使用。有关的API： InitializeCriticalSection对临界区对象进行初始化； EnterCriticalSection等待占用临界区的使用权，得到使用权时返回； TryEnterCriticalSection非等待方式申请临界区的使用权；申请失败时，返回0； LeaveCriticalSection释放临界区的使用权； DeleteCriticalSection释放与临界区对象相关的所有系统资源；

互锁变量访问：相当于硬件指令，对一个整数（进程内的变量或进程间的共享变量）进行操作。其目的是避免线程间切换的影响。有关的API： InterlockedExchange进行32位数据的先读后写原子操作； InterlockedCompareExchange依据比较结果进行赋值的原子操作； InterlockedExchangeAdd先加后存结果的原子操作； InterlockedDecrement先减1后存结果的原子操作； InterlockedIncrement先加1后存结果的原子操作；

作业 设有5个哲学家，共享一张放有5把椅子的桌子，每人分得1把椅子。但是，桌子上总共只有5支筷子，在每人两边分开各放一支。哲学家们在肚子饥饿时才试图分两次从两边拾起筷子就餐。 条件： 1）只有拿到两支筷子时，哲学家才能吃饭。 2）如果筷子已在他人手上，则该哲学家必须等待到他人吃完之后才能拿到筷子。 3）任劳任怨哲学家在自己未拿到两支筷子吃饭之前，决不放下自已手中的筷子。 要求： 1）有什么情况下5个哲学家全部吃不上饭？ 2）描述一种没有人饿死（永远拿不到筷子）算法。

实验二 用信号灯来实现读者-写者问题

2.6进程间通信 (IPC, INTER-PROCESS COMMUNICATION) 2.6.0 进程间通信的类型 2.6.1 信号(signal) 2.6.2 共享存储区(shared memory) 2.6.3 管道(pipe) 2.6.2 消息(message) 2.6.5 套接字(socket) 返回

2.6.0 进程间通信的类型 1. 低级通信和高级通信 低级通信：只能传递状态和整数值（控制信息），包括进程互斥和同步所采用的信号量和管程机制。优点的速度快。缺点是： 传送信息量小：效率低，每次通信传递的信息量固定，若传递较多信息则需要进行多次通信。 编程复杂：用户直接实现通信的细节，编程复杂，容易出错。 高级通信：能够传送任意数量的数据，包括三类：共享存储区、管道、消息。 返回

2. 直接通信和间接通信 直接通信：信息直接传递给接收方，如管道。 在发送时，指定接收方的地址或标识，也可以指定多个接收方或广播式地址； 在接收时，允许接收来自任意发送方的消息，并在读出消息的同时获取发送方的地址。 间接通信：借助于收发双方进程之外的共享数据结构作为通信中转，如消息队列。通常收方和发方的数目可以是任意的。

3. 高级通信的特征 通信链路(communication link)： 消息格式： 收发操作的同步方式 点对点/多点/广播 单向/双向 有容量（链路带缓冲区）/无容量（发送方和接收方需自备缓冲区） 消息格式： 字节流(byte stream)：各次发送之间的分界，在接收时不被保留，没有格式； 报文(datagram/message)：各次发送之间的分界，在接收时被保留，通常有格式（如表示类型），定长/不定长报文，可靠报文/不可靠报文。 收发操作的同步方式 发送进程阻塞和接收进程也阻塞。 发送进程不阻塞，接收进程阻塞。 发送进程，接收进程均不阻塞。

2.6.1 信号(signal) 2.6.1.1 UNIX信号 2.6.1.2 Windows NT信号 信号相当于给进程的“软件”中断；进程可发送信号，指定信号处理例程；它是单向和异步的。 2.6.1.1 UNIX信号 2.6.1.2 Windows NT信号 返回

2.6.1.1 UNIX信号 1. 信号类型 一个进程向另一个进程或进程组（或自己）发送（kill系统调用）：发送者必须具有接收者同样的有效用户ID，或者发送者是超级用户身份 某些键盘按键，如：中断字符（通常是Ctrl+C或Del）、暂停字符（如Ctrl+Z） 硬件条件，如：除数为零、浮点运算错、访问非法地址等异常条件 软件条件，如：Socket中有加急数据到达

2. 对信号的处理 进程可以设置信号处理例程（signal系统调用），在接收到信号时就被调用，称为"捕获"该信号。信号处理例程的参数是接收到信号的编号。 进程也可以忽略指定的信号(SIG_IGN)。 只有SIGKILL信号（无条件终止进程）和SIGSTOP（使进程暂停）不能被忽略。 在库函数system()的实现中，通过fork和exec加载新程序之后，在父进程中对SIGINT和SIGQUIT都要忽略，然后wait直到子进程终止，才恢复对SIGINT和SIGQUIT的原有处理例程。 进程创建后为信号设立了默认处理例程(SIG_DFL)，如：终止并留映象文件(core)

2.6.1.2 Windows NT信号 1. SetConsoleCtrlHandler和GenerateConsoleCtrlEvent SetConsoleCtrlHandler在本进程的处理例程(HandlerRoutine)列表中定义或取销用户定义的处理例程；如：缺省时，它有一个CTRL+C输入的处理例程，我们可利用本调用来忽视或恢复CTRL+C输入的处理； GenerateConsoleCtrlEvent发送信号到与本进程共享同一控制台的控制台进程组；

处理信号列表(5种)

2. signal和raise signal设置中断信号处理例程；如：SIGINT（CTRL+C）、SIGABRT异常中止等信号的处理； 处理信号列表（6种）

2.6.2 共享存储区(shared memory) 1. UNIX的共享存储区 相当于内存，可以任意读写和使用任意数据结构（当然，对指针要注意），需要进程互斥和同步的辅助来确保数据一致性 1. UNIX的共享存储区 创建或打开共享存储区(shmget)：依据用户给出的整数值key，创建新区或打开现有区，返回一个共享存储区ID。 连接共享存储区(shmat)：连接共享存储区到本进程的地址空间，可以指定虚拟地址或由系统分配，返回共享存储区首地址。父进程已连接的共享存储区可被fork创建的子进程继承。 拆除共享存储区连接(shmdt)：拆除共享存储区与本进程地址空间的连接。 共享存储区控制(shmctl)：对共享存储区进行控制。如：共享存储区的删除需要显式调用shmctl(shmid, IPC_RMID, 0)； 返回

2. UNIX的文件映射 mmap：建立进程地址空间到文件或共享存储区对象的映射，将文件偏移off起的len字节映射到进程地址addr处： caddr_t mmap(caddr_t addr, size_t len, int prot, int flags, int fildes, off_t off); munmap：拆除映射 int munmap(void *addr, size_t len); 优点： 提高效率（消除不必要的数据拷贝）、 降低复杂性（直接读写操作而不必管理缓冲区）、 可直接将内存的数据类型记录在文件上（如指针）

3. Windows NT的文件映射 采用文件映射(file mapping)机制：可以将整个文件映射为进程虚拟地址空间的一部分来加以访问。在CreateFileMapping和OpenFileMapping时可以指定对象名称。 CreateFileMapping为指定文件创建一个文件映射对象，返回对象指针； OpenFileMapping打开一个命名的文件映射对象，返回对象指针； MapViewOfFile把文件映射到本进程的地址空间，返回映射地址空间的首地址； 这时可利用首地址进行读写； FlushViewOfFile可把映射地址空间的内容写到物理文件中； UnmapViewOfFile拆除文件映射与本进程地址空间间映射关系； 随后，可利用CloseHandle关闭文件映射对象；

2.6.3 管道(pipe) 管道是一条在进程间以字节流方式传送的通信通道。它由OS核心的缓冲区（通常几十KB）来实现，是单向的；常用于命令行所指定的输入输出重定向和管道命令。在使用管道前要建立相应的管道，然后才可使用。 返回

1. UNIX管道 通过pipe系统调用创建无名管道，得到两个文件描述符，分别用于写和读。 int pipe(int fildes[2]); 文件描述符fildes[0]为读端，fildes[1]为写端； 通过系统调用write和read进行管道的写和读； 进程间双向通信，通常需要两个管道； 只适用于父子进程之间或父进程安排的各个子进程之间； UNIX中的命名管道，可通过mknod系统调用建立：指定mode为S_IFIFO int mknod(const char *path, mode_t mode, dev_t dev);

2. Windows NT管道 无名管道：类似于UNIX管道，CreatePipe可创建无名管道，得到两个读写句柄；利用ReadFile和WriteFile可进行无名管道的读写； BOOL CreatePipe( PHANDLE hReadPipe, // address of variable for read handle PHANDLE hWritePipe, // address of variable for write handle LPSECURITY_ATTRIBUTES lpPipeAttributes, // pointer to security attributes DWORD nSize // number of bytes reserved for pipe );

命名管道：一个服务器端与一个客户进程间的通信通道；可用于不同机器上进程通信； 类型分为：字节流，消息流（报文）； 访问分为：单向读，单向写，双向； 还有关于操作阻塞(wait/nowait)的设置。相应有一个文件句柄 通常采用client-server模式，连接本机或网络中的两个进程 管道名字：作为客户方（连接到一个命名管道实例的一方）时，可以是"\\serverName\pipe\pipename"；作为服务器方(创建命名管道的一方)时，只能取serverName为\\.\pipe\PipeName，不能在其它机器上创建管道；

命名管道服务器支持多客户：为每个管道实例建立单独线程或进程。 CreateNamedPipe在服务器端创建并返回一个命名管道句柄； ConnectNamedPipe在服务器端等待客户进程的请求； CallNamedPipe从管道客户进程建立与服务器的管道连接； ReadFile、WriteFile（用于阻塞方式）、ReadFileEx、WriteFileEx（用于非阻塞方式）用于命名管道的读写；

2.6.2 消息(message) 与窗口系统中的“消息”不同。通常是不定长数据块。消息的发送不需要接收方准备好，随时可发送。 返回

1. UNIX消息 消息队列(message queue)：每个message不定长，由类型(type)和正文(text)组成 UNIX消息队列API： msgget依据用户给出的整数值key，创建新消息队列或打开现有消息队列，返回一个消息队列ID； msgsnd发送消息； msgrcv接收消息，可以指定消息类型；没有消息时，返回-1； msgctl对消息队列进行控制，如删除消息队列； 通过指定多种消息类型，可以在一个消息队列中建立多个虚拟信道 注意：消息队列不随创建它的进程的终止而自动撤销，必须用msgctl(msgqid, IPC_RMID, 0)。另外，msgget获得消息队列ID之后，fork创建子进程，在子进程中能否继承该消息队列ID而不必再一次msgget。

2. Windows NT邮件槽 邮件槽(mailslot)：驻留在OS核心，不定长数据块（报文），不可靠传递 通常采用client-server模式：单向的，从client发往server；server负责创建邮件槽，它可从邮件槽中读消息；client可利用邮件槽的名字向它发送消息； 邮件槽名字：作为client（发送方）打开邮件槽时，可以是"\\range\mailslot\[path]name"，这里range可以是 .(local computer), computerName, domainName, *(primary domain)；作为server（接收方）只能在本机建立邮件槽，名字可为"\\.\mailslot\[path]name"；

在邮件槽的所有服务器句柄关闭后，邮件槽被关闭。这时，未读出的报文被丢弃，所有客户句柄都被关闭。 有关的API如： CreateMailslot服务器方创建邮件槽，返回其句柄； GetMailslotInfo服务器查询邮件槽的信息，如：消息长度、消息数目、读操作等待时限等； SetMailslotInfo服务器设置读操作等待时限； ReadFile服务器读邮件槽； CreateFile客户方打开邮件槽； WriteFile客户方发送消息； 在邮件槽的所有服务器句柄关闭后，邮件槽被关闭。这时，未读出的报文被丢弃，所有客户句柄都被关闭。

2.6.5 套接字(socket) 双向的，数据格式为字节流（一对一）或报文（多对一，一对多）；主要用于网络通信； 支持client-server模式和peer-to-peer模式，本机或网络中的两个或多个进程进行交互。提供TCP/IP协议支持 UNIX套接字(基于TCP/IP)：send, sendto, recv, recvfrom; 在Windows NT中的规范称为"Winsock"(与协议独立，或支持多种协议)：WSASend, WSASendto, WSARecv, WSARecvfrom; 返回