Thw giver:03进程管理2

2.5线程

多线程

操作系统中引入进程的目的是，为了描述和实现多个程序的并发执行，以改善资源利用率及提高系统的吞吐量。

为什么还需要引入线程呢？这是为了减少程序并发执行时系统所付出的额外开销，使操作系统具有更好的并发性。

进程的两个基本属性：

（1） 进程是一个拥有资源的独立单位。

（2） 进程同时又是一个可以独立调度的基本单位。

系统为进程进行的操作

创建进程、撤销进程、进程切换

进程作为资源的拥有者和系统的调度对象，需要花费系统较大的额外开销。故，系统中同时存在的进程数目不宜过多，进程切换的频率也不宜过高，而这也就限制了并发度的进一步提高。

由进程到线程

目标：既能提高进程并发度，又能降低系统的额外开销。

实现：将进程的资源申请和调度属性分开。即进程作为资源的申请和拥有者，但不作为调度的基本单位。这样，就产生了线程的概念。

线程是进程中的一个实体，是独立调度和分派的基本单位。

线程自身基本上不拥有系统资源之拥有少许运行中必不可少的私有资源。线程可与同属一个进程的其他线程共享进程的全部资源。

线程的状态

进程中的所有线程共享该进程的状态。

线程具有三种基本状态：就绪、执行和阻塞。

一般不具有挂起状态，因为线程共享进程的资源，包括存储空间，如果挂起一个进程，器所属的全部进程必将被挂起。而单独挂起某进程中的一个线程，必然会影响同一个进程中的其他线程的执行，只是没有任何意义的。

对线程的操作

一个进程可以创建和撤销一个或多个线程，同一进程中的多个线程可以并发执行。

对线程的操作包括：

1. 派生Spawn，当系统创建一个进程时，同时也为该进程派生一个线程，同一进程中的线程可以再派生其他线程。

2. 阻塞，当线程需要等待某事件时，它将被阻塞，释放处理机执行其他线程。

3．解除阻塞，当线程的阻塞事件发生，其状态转换为就绪，并插入到就绪队列，等待调度执行。

4.结束，当线程执行完毕，释放其私有资源。

注意，线程阻塞不一定会引起整个进程的阻塞，否则，引入线程带来的并发性就不会提高。

进程与线程

传统操作系统中，一个进程可以创建一个线程，如MS DOS就是一个单用户、单进程、单线程的操作系统，UNIX是一个多用户、多进程、单线程的操作系统

现代操作系统和软件设计大多支持多线程运行，例如，Java虚拟机是一个单进程、多线程的运行环境，Windows系列操作系统和linux操作系统都采用了多进程、多线程技术。

进程与线程

传统操作系统，进程既是拥有资源的基本单位，又是独立调度的基本单位。

引入线程操作系统中，线程是独立调度的基本单位，进程是资源拥有的基本单位，从而可以显著地提高系统的并发程度。

同一进程中的线程间切换不会引起进程切换，但当一个进程中的线程切换到另一个进程中的线程时，将会引起进程切换。

进程与线程- --并发

进程之间可以并发执行

同属于一个进程的多个线程之间，亦可并发执行

因而使操作系统具有更好的并发性，从而能更有效的使用系统资源和提高系统吞吐量。

例子

在一个为引入线程的单处理机操作系统中，若仅设置一个文件服务进程，当它由于某种原因而被阻塞时，变没有其他的文件服务进程来提供服务。

引入进程以后，可以，子啊一个文件服务进程中设置多个服务线程，当第一个线程阻塞时，文件服务进程中的第二个线程可以继续运行；当第二个线程阻塞时，第三个线程可以继续执行，从而显著地提高了文件服务的质量和系统吞吐量。

拥有资源

进程是拥有资源的独立单位，它由权申请系统的各类资源。

线程除了拥有很少的私有资源以外，不能申请系统资源，可以共享器所属进程的资源，如已打开的文件、i/0设备等，都可被其内的所有线程共享。

系统开销

操作系统管理进程的开销显著地大于管理线程所需的开销。

进程切换的开销也远大于线程切换的开销。

由于同一进程中的多个线程具有相同的地址空间，使他们之间的同步和通信业比较容易。

有些类型的线程切换、同步和通信都无需操作系统内核的干预。

线程的类型

用户级线程和内核级线程

用户级线程的创建、撤销及切换等操作全部由支持线程的应用程序完成，内核并不知道线程的存在。

一些数据库管理系统，如Informix即支持用户级线程。应用程序可以利用线程库来设计多线程程序，该线程库包含各种用于管理用户级线程的例程，如用于创建和撤销线程的例程、用于线程间传递消息和数据的例程、线程调度例程，以及保护和恢复线程上下文的例程等，

用户级线程

用户级线程阻塞是否会引起整个进程阻塞呢？

这要视具体情况而定，当某进程中的一个线程需要等待另一线程的输出数据而阻塞时，整个进程并不会阻塞。即进程保持执行状态，其内的某个线程也是执行状态。

当某线程因为i/0阻塞时，内核需要启动系统i/0，控制从用户级转到系统内核级，这是常会引起整个进程阻塞。随即将发生进程切换，进程调度程序重新调度另一个就绪进程执行。

优点：用户线程能节省大量的系统额外开销，并提高程序并发性，这是因为：

线程的管理和控制仅在用户级进行，线程切换无需内核干预，没有模式奇幻，减少了模式切换的开销。

调度更灵活。应用程序可以根据需要选用线程库中不同的线程调度算法，而不受系统内核进程调度程序的约束。

由于线程库独立于系统内核，可以运行在不同的操作系统之上，使用户线程可以得到不同操作系统的支持，而无需修改操作系统内核。

存在问题

用户级线程问题

由于很多操作系统的系统调用都会引起阻塞，用户级线程中的系统调用常常会引起线程及整个进程阻塞，削弱了线程的并发性。

由于系统内核不知用户级线程的存在，可能出现进程切换时，强行中断器内某个执行线程的情况。

很难实现不同进程的线程并发。

内核级线程

内核级线程的管理全由系统内核完成，应用程序无权进行线程切换等操作，系统为应用程序提供了相应的应用程序编程接口API

W2K、Linux和OS/2等操作系统即采用内核级线程技术。

特点：系统内部负责内核级线程的创建、撤销、切换等操作。应用程序可以设计成多线程程序，多个线程同属于一个进程。系统以线程为调度单位。

进行线程切换时，需要同时保持真个进程的上下文以及线程的上下文信息。这样，当进程中的某个线程阻塞时，内核可以调度另一个就绪线程执行（同一进程或不同进程）。

线程切换时需要进行模式切换

混合模式

由于用户级线程和内核级线程各有自己的优缺点，实际工程设计可以进行折中，将二者结合起来，形成一种混合模式。

Solaris操作系统即采用这种技术

在混合模式中，线程的创建、撤销、调度、同步的等都在用户级应用程序中完成。

应用程序中多个用户级线程被映射到一个或较少的某些内核级线程

这样，可以使同一应用程序中的多个线程能分散到不同处理机上并行运行，而且，可以避免因为某些用户级线程的阻塞而引起整个进程阻塞的现象。

2.6进程互斥与同步（协调）

我们要解决的问题是怎样的互斥的使用资源，有序地，有效地竞争系统资源

采用多道程序设计技术的操作系统，允许多个进程同时驻留内存并发执行。

同时驻留内存并发执行。

？如何协调多个进程对系统资源，如内存空间、外部设备等的竞争和共享？

？如何解决多个进程因为竞争资源而出现执行结果异常，甚至导致系统不稳定、失效等问题？

？例如，多个进程同时申请文件打印，如何有效分配打印机？

银行同时存取款要互斥完成

原因：两个进程同时修改同一数据，而没有进行有效控制。

正确的方法：如果有多个进程需要同时修改某一数据，系统必须控制，一次仅允许一个进程完成读数据，并修改数据两件事以后，才允许别的进程对同一数据的读和修改操作。

结论

通过上述两个例子可见，采用多道程序并发设计技术的操作系统对诸进程的并发控制是非常重要和必须的。

并发控制 竞争资源

当并发进程竞争使用同一资源时，它们之间就会发生冲突。

如果操作系统将资源分配给其中的某一个进程使用，另一个进程就必须等待，直到申请的资源可用时，由操作系统分配给它。

如果竞争某资源的进程太多，这些进程还必须等待在一个队列中，如就绪队列，阻塞队列等。

一种极端的情况是，被足额色进程永久得不到申请的资源，而死锁。

进程竞争资源首先必须解决互斥问题。某些资源必须互斥使用，如打印机、共享变量、表格文件等

这类资源又称为临界资源，访问临界资源的那段代码称为临界区。

任何时刻，只允许一个进程进入临界区，一次实现进程对临界资源的互斥访问。

互斥使用临界资源

1. 当进程需要使用临界资源时，通过获得临界区的使用权实现的

2. 首先，在进入区判断是否可以进入临界区，如果可以进入，则必须设置临界区使用标志，阻止其它后来的进程进入临界区。后来的进程通过查看临界区使用标志，知道自己不能进入临界区，就进入阻塞队列，将自己阻塞。

3. 当临界区内的进程使用完毕，退出临界区时，即在“推出区”修改临界区使用标志，并负责唤醒阻塞队列中的一个进程，让其进入临界区。

由于同一个临界资源在多个共享它的进程中将对应多个临界区，那么怎样才能保证诸进程间互斥地执行临界区呢？

这就必须保证“临界区使用标志”是可被系统中所有进程共享的全局变量，而且诸进程对该标志的修改操作必须互斥进行。

临界区使用原则（也称为互斥条件）

1.每次只允许一个进程处于临界区（忙则等待）

2.有限等待：进程只能在临界区内逗留有限时间，不得使其他进程在临界外无限期等待

3.空闲让进:如果临界区空闲，则只要有进程申请就立即让其进入

4.让权等待：进入临界区的进程，不能子啊临界区内长时间阻塞等待某事件，必须在一定期限内退出临界区

5.不能限制进程的执行进度及处理机的数量。

竞争资源可能引起死锁

例如，两个进程P1、P2，竞争资源R1、R2

假设，现在P1已经占用了R1，且P2占用了R2，如果此时P1申请R2，且P2申请R1`。会怎么样呢？

结果是P1、P2双方都占用对方申请的资源而阻塞，谁也不让步地永久等待，这就是死锁。

饥饿

1假设有3个进程P1、P2、P3，每个进程都需要周期性的使用资源R

2如果当前P1正在使用临界资源R，P2和P3因为等待R而阻塞。

3当P1退出临界区时，P2立即进入临界区执行，若P2还未退出临界区时，P1又申请使用4临界资源R假设P2退出临界区后，系统将R分给了P1，然后，当R空闲时，又将其分给了P2，如此反复

5使P1、P2都能正常执行，而P3被长时间饥饿。

这种情况不是死锁，但是对P3不公平，也是系统应该避免地

共同协作

多个进程常常需要共同修改某些共享变量、表格、文件数据库等，协作完成一些功能。

必须确保它们对共享变量的修改时正确的，保证数据的完整性。

共享协作同样涉及到互斥、死锁和饥饿问题。但更强调对数据的写操作必须互斥地进行。

必须保证数据的一致性

只有该进程退出临界区以后，才允许别的进程进入临界区进行数据修改，以保证数据的一致性。

同心协作

当进程进行通信合作时，各个进程之间需要建立连接，进程通信需要同步和协调。进程通信的方式很多，包括消息传递、管道、共享存储区等。

通过消息传递实现进程通信时，由于没有共享资源，故无须互斥，但仍可能出现死锁和饥饿。

例如，两个进程相互等待对方发来的数据而永久阻塞，即死锁。

又如，3个进程P1、P2、P3，其中P1不断尝试与P2或P3通信，P2和P3又不断尝试与P1通信，如果P1与P2总能成功建立连接进行通信，而P3一直阻塞等待P1这样P3被长时间饥饿

互斥与同步的解决策略

软件方法

硬件方法

信号量方法

管程方法

消息传递方法

软件方法

软件方法使指由进程自己，通过执行相应的程序指令，实现与别的进程的同步于互斥，无须专门的程序设计语言或操作系统的支持。

实践证明，该方法很难正确控制进程间的同步与互斥，而且可能会大大地增加系统的额外开销。

硬件方法

为了解决软件方法存在的不足，有人提出了硬件解决方法，通过屏蔽中断或采用专门的机器指令控制同步与互斥。

与软件解决方法比较，这种方法减少了系统额外开销，但由于需要太强的硬件约束条件，以及可能导致进程饥饿与死锁现象，一直没有成为通用的解决方法

另一类解决方法是由操作系统，或专门的程序设计语言提供的特别支持，包括信号量方法、管程方法和消息传递方法

其中，信号量方法已经成为控制进程同步于互斥的通用方法。

互斥与同步解决方法之一：软件放法

软件解决方法有很多种，比较有代表性的软件方法有荷兰数学家Dekker提出的Dekker算法和科学家G.L.Peterson提出的Peterson算法

为了说明设计并发程序可能出现的典型错误，下面以Dekker算法为例，分析如何设计并改进一个互斥算法的过程。

初步设想

为了控制两个进程互斥进入临界区，可以让两个进程轮流进入临界区

当一个进程正在临界区执行时，另一个进程就不能进入临界区，而在临界区外等待。

程序实现的伪代码如图2.26所示。

分析特点

保证了互斥

问题1：忙等现象

问题2：进程严格交替进入临界区。如果进程需要多次使用临界区，那么使用临界区频率低的进程严重制约着使用临界区频率高的进程的执行进度。

问题3：任何进程在临界区内或外失败，其他进程将可能因为等待使用临界区，而无法向前推进。

因为两个进程相互依赖对方将临界区的使用权（顺序）进行修改，一旦这种修改不能进行，对方都将因为等待临界区而无法推进。

第一次改进临界区设置一个状态标志，标明临界区是否可用。当临界区空闲时，任何一个进程都能进入，但此时必须修改临界区标志位“被占用”，别的进程就不能进入临界区。当临界区使用完毕，必须修改标志为“空闲”

这样就不再使诸进程严格交替使用临界区，而且，如果某进程在临界区外失败，也不会影响其它进程。其算法描述如图2.27所示。

可以为临界区设置一个状态标志，解决了临界区空闲时可以用，不是严格的交替使用。

如果进程在临界区外失败，其他进程不会阻塞。

问题1：“忙等”

问题2：若进程在临界区内失败且相应的flag为true，则其他进程永久阻塞。

问题3：不能保证进程互斥进入临界区。请试着按一下顺序执行：

第二次改进

互斥算法的第一次改进不能是是实现互斥

因为，进程首先检测临界区状态，若“被占用”，则“忙等”，否则就直接进入临界区。从而，可能出现同时进入临界区的现象。

能否让进程预先标明“希望进入临界区的态度”，然后，再检测临界区状态。实现第二次改进。

假设P0需要进入临界区，首先执行flag【0】：=true，再执行while flag【1】，若P1正在占用临界区，则P0忙等；否则，P0进入临界区。

但是如果此时P1未占用临界P0几乎同时需要使用临界区。

第三次改进

互斥算法的第二次改进可能导致死锁，因为P0、P1都坚持自己的权利，执意进入临界区，且互不谦让“。

可以考虑，允许进程即表明需要进入临界区的态度，又能相互“谦让”，即首先表示自己需要使用临界区，再检测临界区的状态，若临界区“别占用”，可以等一小段时间再申请。

分析：

P0、P1的谦让可能使他们都不能进入临界区。

这种现象不是死锁，因为这种僵局不会是永久行为，某一时刻可能会自动解除。

但是，这种现象也是不希望出现的。

Deeker互斥算法

该算法既允许进程“谦让地”申请进入临界区，又通过给定序号避免“过分谦让”

Peterson互斥算法

Peterson互斥算法与Dekker互斥算法的设计思想类似，但代码更简洁，

算法中同样用到两个全局共享的状态变量flag[0]和flag【1】，表示临界区状态及哪个进程正在占用临界区。

全局共享变量turn（值为1或0），表示能进入临界区的进程序号。

硬件方法

采用软件方法实现进程互斥使用临界资源是很困难的，他们通常能实现两个进程的互斥，很难控制多个进程的互斥。

算法设计需要非常小心，否则可能促销死锁，或互斥失败等严重问题。

软件方法时钟不能解决忙等现象，降低系统效率。硬件方法包括屏蔽中断和专用机器指令

屏蔽中断

由于进程切换需要依赖中断来实现，如果屏蔽中断，则不会出现进程切换。

因此，为了实现对临界资源的互斥使用，可以在进程进入临界区之前，屏蔽中断，当进程退出临界区时，打开系统中断。

中断被屏蔽以后，系统时钟中断也被屏蔽。处理机将不会被切换到其他进程。

于是，一旦屏蔽中断，进程就可以检查和修改共享内存区中的数据，而不必担心其他进程介入。其伪代码如下：

分析：

这种方法约束条件太强，付出的代价太大

因为中断被屏蔽以后，系统将无法响应任何外部请求，也不会响应当前执行进程的任何异常及系统故障，严重地降低了处理机性能。

这种方法仅对单处理机系统有效，如果系统由两个或多个分享内存的处理机，屏蔽中断仅仅对执行本指令的处理机有效，其它处理机仍将继续运行，并可以访问内存空间。

专用机器指令方法

利用一些专用机器指令也能实现互斥，机器指令在一个指令周期内执行，不会受到其它指令的干扰，也不会被中断。

Test and Set指令就是较常用的一种机器指令，

硬件方法-exchange指令

机器指令优点

非常简单，易于证明

同时适合于单处理机系统和共享内存的多处理机系统中多个进程的互斥；

可以分别为临界区设置属于它自己的变量，以是实现对多个临界区的互斥访问。

机器指令缺点

1“忙等”现象仍然存在。进程都需要循环检测，等待时机进入临界区。但是，由于采用了机器指令，这种“忙等”消耗的机器时间比软件方法小，属于‘可接受的忙等“。

2可能出现饥饿现象。当临界区空闲时，执行驯悍检测的若干等待进程能进入临界区的几率是相等的，有的进程可能“运气”非常不好，很难有机会进入临界区，而饥饿

3还可能导致死锁

信号量（semaphores）方法

软件方法和硬件方法都存在“忙等”问题，浪费了处理机时间。

信号量方法能实现进程互斥与同步，而不必忙等。

交通信号灯：红灯停，绿灯行

信号量实现互斥的基本原理

两个或多个进程可以通过传递信号进行合作，可以迫使进程在某个位置暂时停止执行（阻塞等待），直到它受到一个可以“向前推进”的信号（被唤醒）

相应地，将实现信号灯作用的变量称为信号量，通常定义为记录型变量s，其中一个域为整型，另一个域为队列，其元素为等待该信号量的阻塞进程（FIFO）

定义对信号量的两个原子操作

1wait（s）和signal（s）

2.。早期这两个原语被称作P（s）和V（s）

Wait（s）

s.count :=s.count-1;

if s.count<0

then begin

进程阻塞；

进程进入s.queue队列；

End

Signal（s）

s.count :=s.count +1;

if s.count <=0

then begin

唤醒队首进程；

将进程从s.queue阻塞队列中移除；

End

Wait、signal的应用

1. 进程进入临界区之前，首先执行wait（s）原语，若s.count<0,则进程调用阻塞原语，将自己阻塞，并插入到s.queue度列排队。

2. 注意，阻塞进程不会占用处理机时间，不是忙等，直到某个从临界区退出的进程执行signal（s）原语，唤醒它。

3. 一旦其它某个进程执行了signal（s）原语中的s.count+1操作后，发现s.count<=0,即阻塞队列中还有阻塞进程，则调用唤醒原语，把s.queue中第一个进程修改为就绪状体，送就绪队列，准备执行临界区代码。

信号量的类型

信号量分为：互斥信号量和资源信号量

互斥信号量用于申请或释放资源的使用权，长初始化为1.

资源信号量用于申请或归还资源，可以初始化为大于1的正整数，表示系统中某类资源的可用个数。

Wait操作用于申请资源（或使用权），进程执行wait原语时，可能会阻塞自己；

Signal操作用于释放资源（或归还资源使用权），进程执行signal原语时，有责任唤醒一个阻塞进程。

信号量的物理意义

s.count>=0表示还可执行wait（s）而不会阻塞的进程数（可用资源数）。每执行一次wait（s）操作，就意味着请求分配一个单位地资源。

当s.count <0时，表示已无资源可用，一次请求该资源的进程被阻塞。此时，s.count的绝对值等于该信号量阻塞队列中的等待进程数。执行一次signal操作，就意味着释放一个单位的资源。若s.count<0,表示s.queue队列中还有被阻塞的进程，需要唤醒该队列中第一个进程，将它转移到就绪队列中。

s.count的取值范围

当仅有两个并发进程共享临界资源时，互斥信号量仅能取值0、1、-1.

当用s来实现n个进程的互斥时，s.count的取值范围为1~-（n-1）

操作系统内核以系统调用形式提供wait和signal原语，应用程序通过该系统调用实现进程间的互斥。

工程实践证明，利用信号量方法实现进程互斥是高效的，一直被广泛采用。

经典进程互斥与同步问题

生产者/消费者问题

读者/写者问题

哲学家进餐问题

2.7生产者/消费者问题

生产者与消费者是一个广义的概念，可以代表一类具有相同属性的进程。

生产者和消费者进程共享一个大小固定的缓冲区，其中，一个或多个生产者生产数据，并将生产的数据存入缓冲区，并有一个消费者从缓冲区中区数据。

假设缓冲区的大小为n（存储单元的个数），它可以被生产者和消费者循环使用。

分别设置两个指针in和out，指向生产者将存放数据的存储单元和消费者将数据的存储单元，

必须使生产者和消费者互斥进入缓冲区，即，某时刻只允许一个实体（生产者或消费者）访问缓冲区，生产者互斥消费者和其它任何生产者。

生产者不能向满缓冲区写数据，消费者也不能在空缓冲区中取数据，即生产者与消费者必须同步（协调）

可以用资源信号量来实现

注意：

1进程应该先申请资源信号量，再归还资源信号量，顺序不能颠倒。

2.对任何信号量的wait与signal操作必须配对。同一进程中的多对wait与signal语句只能嵌套，不能交叉。

3. 对一个信号量的wait与signal可以不在同一个进程中。

4. wait与signal语句不能颠倒顺序，wait语句一定先于signal语句。

2.8读者/写者问题

问题描述

该问题为多个进程访问一个共享数据区，如数据库、文件、内存区及一组寄存器等的数据问题建立了一个通用模型，其中若干读进程只能读数据，若干写进程只能写数据。

例如，一个联网售票系统

读者写者进程满足的条件

1允许多个读者进程可以同时读数据

2不允许多个写者进程同时写数据，即只能互斥写数据。

3若有写者进程正在写数据，则不允许读者进程读数据。

如何控制读者和写者进程

1如果采用生产者/消费者问题解决方法，严格互斥任何读者和写者进程，可以保证数据更新操作的正确性。

2但是，对于若干读者进程，只不过希望查询售票情况，却被严格互斥，严重影响了系统效率。显然应该让多个读者同时读数据。

3如果一个写者进程正在修改数据，别的写者以及任何读者都不能访问该数据。

读者优先

1当一个读者正在读数据时，另一个读者也需要读数据，应允许第二个读者进入，同理第三个及随后更多的读者都被允许进入。

2现在假设一个写者到来，由于写操作时排他的，所以它不能访问数据，需要阻塞等待。如果一直都有新的读者陆续到来，写者的写操作将被严重推迟。

3该方法称为“读者优先”。即，一旦有读者正在读数据，允许多个读者同时进入读数据，只有当全部读者退出，才允许写者进入写数据。

写者优先

1为了防止“读者优先”可能导致写者饥饿，可以考虑写者优先。

2即，当共享数据区被读者占用时，后续紧邻到达的读者可以继续进入，若这时有一个写者到来且阻塞等待，则写者后面到来的若干读者全部阻塞等待。

3换句话说，只要有一个写者申请写数据，则不再允许新的读者进入读数据。这样，写者只需要等待先于它到来的读者完成其读数据任务，而不用等待其后到来的读者。

这种方案解决了写者饥饿问题，但降低了并发程度，使系统的性能较差。

2.9互斥与同步解决方法之四：管程

1管程是一种在程序设计级进程互斥与同步的机制，具有信号量的功能，且更容易使用和控制。

2目前已有很多程序设计语言支持管程机制，如并发Pascal、Pascal-Plus、Modula-2.Modula-3、Java等，并且还作为程序库提供服务。

3利用管程可以锁定任何对象，尤其是链表型数据结构，可以锁定整个链表，或链表中的某个元素。

管程的结构

管程是由过程、变量及数据结构等组成的集合。典型的管程包括三个部分：

1对局部于管程的共享数据结构的说明；

2对该数据结构进行操作的一组过程；

3对该数据机构初始化的语句。

管程有自己的名字，管程中的各个过程可以带有自己的形式参数，与过程调用一样进行参数替换执行。

管程的使用

管程本身被作为一种临界区，因此，实现管程时，需要考虑互斥、同步和控制变量等问题。

进程可在任何需要的地方调用管程中的过程，但不能再管程外直接访问管程内的数据结构。

用管程实现同步

用管程实现进程同步，是指在管程中药设置一对同步操作员，例如，wait（或block）和signal（或wakeup）

注意，这里的wait和signal与作用于信号量的wait和signal不同，后者作用于信号量。信号量具有累加功能，当信号量为负数时，其绝对值表示等待在该信号量上的阻塞进程数。这里的wait和signal作用于条件变量，条件变量不具有累加功能，如果管程中的进程发出了一个信号量，却没有在对应的条件变量上阻塞等待，则该信号量没有作用，会被丢失。

由于进程阻塞等待的原因有多种，为了区别阻塞等待进程和不同的阻塞队列，管程中设置了不同的条件变量，将因为不同事件阻塞的进程组织在不同的队列中。

当一个进程利用管程申请资源而未能满足时，将调用wait原语阻塞自己，并进入相应阻塞队列。当某进程释放出一个临界资源以后，将用signal原语唤醒等待在该临界资源上的一个阻塞进程。

2.10互斥与同步解决方法之五：消息传递

进程之间的通信内容包含两种类型：控制信息与大批量数据。

低级通信：进程之间交换控制信息的过程。

高级通信：进程之间交换批量数据的过程。

进程之间同步于互斥是一种低级通信，用来控制进程执行速度。

例如：电子邮件的发送与接收过程。

常用的进程通信机制

基于共享存储区方式

消息传递方式

邮箱机制

1基于共享存储区方式

生产者/消费者问题：生产者与消费者通过共享缓冲区，实现数据传递。属于基于共享存储区通信。

这里的共享数据区属于每个互相通信进程的组成部分。这种通信方式不要求数据移动，一般用于本地通信。

对于远程通信来说，每台计算机拥有各自的私有内存区，不易实现共享存储区的访问。

如何通过共享存储区通信

1通过程序设计来实现。程序员设计程序时，利用程序指令设置共享存储区，并处理通信进程之间额同步等问题，操作系统只需提供共享存储区。

2由操作系统在内存中划分出一块区域作为共享存储区。 进程在通信前向系统申请共享存储区中的一个分区。然后，申请进程把获得的共享存储分区连接到本进程上，此后便可以读/写普通存储器一样地读/写共享存储分区。该方式下，通信进程之间的同步于互斥访问共享存储区可以由操作系统实现。

消息传递机制

消息格式： 消息头消息体

消息头：消息类型目的端地址 源端地址 消息长度 控制信息

消息体：消息内容

消息传递的同步

进程之间的通信的两条原语：

Send（destination，message）

Receive（source，message）

消息传递的同步

1. 只有当一个发送进程发送出消息以后，接收进程才能接收消息。

2. 即，当发送进程调用Send原语发送消息时，若没有空闲的消息缓冲区，则发送进程阻塞；当接收进程调用Receive原语接收消息时，如果没有消息可接收，则接收进程阻塞，直到一条消息到达。

三种同步方式

阻塞发送，阻塞接收：进程间的紧密同步

不阻塞发送，阻塞接收：常用于服务进程为其它进程提供服务

不阻塞发送，不阻塞接收

“不阻塞发送”

1. 例如，当将进程执行过程中需要打印输出，通常让打印任务排队等待，而请求打印的进程无需阻塞等待打印完成。即，每当进程需要打印时，都可以以消息形式发出请求，然后继续执行。

2. “不阻塞发送”方式容易导致消息的无限发送。无限发送消息会消耗处理机时间，且由于消息需要占用内存的消息缓冲区，无限发送消息也会消耗其它系统资源。

3. 设计并发程序时，若采用“不阻塞发送”方式，就必须在程序中考虑让接收进程发回应答消息，证实其是否收到消息，这将增加程序设计的难度。

阻塞接收

1并发程序设计中常采用该方式；

2当接收消息的进程未收到期望的消息时，常需要阻塞等待，直到消息到来，但是，如果消息丢失，或发送进程发送消息之前失败，则接收进程将永久阻塞。

3如果采用不阻塞接收方式，则可能因为接收方的缘故，丢失消息。

消息传递中的寻址

1寻址方式：直接寻址和间接寻址

2若采用直接寻址，send原语中必须指定目标进程的具体标识号

3Receive原语中的source地址由两种处理方法：

接收进程显式地指定发送方进程标识号，这就要求接收进程必须事先清楚将结合搜哪个进程发来的消息。

接收进程可以不必指定接收哪个进程的消息。

间接寻址

采用间接寻址传递消息时，消息不再从发送方直接发送到接收方，而是通过发送进程与接收进程共享的一个数据结构进行中转，该数据结构通常称为邮箱。

发送进程将消息发送到指定的邮箱中，接收进程从邮箱中接收消息。

邮箱

邮箱不限制进程数，允许多个发送进程想邮箱发送消息，同时，也允许多个接收进程从邮箱接收消息。

利用消息传递实现互斥

1采用“不阻塞发送，阻塞接收“方式。

2多个并发执行的发送进程和接收进程共享一个邮箱mutex，它被初始化为一个无内容的“空“消息。

3如果一个进程希望进入临界区，首先必须申请从mutex邮箱中接收一条消息。若邮箱为“空“，则该进程阻塞（接收）；若进程收到邮箱中的一条消息，则进入临界区，执行完毕以后，退出临界区，并将该消息发送回邮箱mutex中，如图：

注意：

1”空“消息：代表一条消息体为”空“，但具有消息头的“真正”的一条消息，不是没有消息。

2当第一个希望进入临界区的进程执行Receive（mutex，msg）语句时，从邮箱mutex中接受了这条“空”消息，进入临界区执行。这时，邮箱mutex变为“空”，即没有消息。其后执行Receive（mutex，msg）语句希望进入临界区的进程阻塞。

3当进入临界区的进程执行完临界区的代码，退出临界区时，执行send（mutex，msg）语句，将这条“空”消息归还给邮箱mutex，并唤醒一个阻塞进程，使其取走这条消息，进入临界区执行。

4. 可见，控制进程互斥进入临界区的这条消息本身可以不含任何有用的内容，它仅被当做进程能否进入临界区的一种凭证，或令牌。

5. 只要保证邮箱中最多只有一条消息，就能保证只允许一个进程进入临界区，从而实现进程互斥使用临界资源。

利用消息传递解决生产者-消费者问题

1共享用了capacity条消息，类似于共享内存缓冲区中的capacity各存储单元。

2消费者首先将capacity调“空”消息发送给生产者。当生产者向消费者传递一个数据项时，它取走一条“空”消息，并发送回一条填充了内容的消息。

3通过这种方式进行数据传送，系统中的总消息数保持不变，所以，消息可以存放在预知数量的内存中。