深入理解操作系统原理之进程管理（一）

r囧r小猫 2022-06-13 04:21 225阅读 0赞

## 一、概述 ##

### 1、为什么引入进程 ###

程序并发执行时具有如下特征：

*  间断性  
    程序在并发执行时，由于它们共享资源或为完成同一项任务而相互合作，使在并发程序之间形成了相互制约的关系。相互制约将导致并发程序具有“执行-暂停-执行”这种间断性活动规律。
 *  失去封闭性  
    程序在并发执行时，是多个程序共享系统中的各种资源，因而这些资源的状态将由多个程序来改变，致使程序的运行已失去了封闭性。
 *  不可再现性  
    程序在并发执行时，由于失去了封闭性，也将导致失去结果的可再现性。即程序经过多次运行，虽然其各次的环境和初始条件相同，但得到的结果却各不相同。

由于程序在并发执行时，可能会造成执行结果的不可再现，所以用“程序”这个概念已无法描述程序的并发执行，所以必须引入新的概念—进程来描述程序的并发执行，并要对进程进行必要的管理，以保证进程在并发执行时结果可再现。  
进程(Process)定义：“可并发执行的程序在一个数据集合上的运行过程”。进程具有如下特征:

*  动态性  
    动态性是进程的最基本特征，它是程序执行过程，它是有一定的生命期。它由创建而产生、由调度而执行，因得不到资源而暂停，并由撤消而死亡。而程序是静态的，它是存放在介质上一组有序指令的集合，无运动的含义。
 *  并发性  
    并发性是进程的重要特征，同时也是OS的重要特征。并发性指多个进程实体同存于内存中，能在一段时间内同时运行。而程序是不能并发执行。
 *  独立性  
    进程是一个能独立运行的基本单位，即是一个独立获得资源和独立调度的单位，而程序不作为独立单位参加运行。
 *  异步性：进程按各自独立的不可预知的速度向前推进，即进程按异步方式进行，正是这一特征，将导致程序执行的不可再现性，因此OS必须采用某种措施来限制各进程推进序列以保证各程序间正常协调运行。
 *  结构特征：从结构上，进程实体由程序段、数据段和进程控制块三部分组成，UNIX中称为“进程映象”。

### 2、进程的描述 ###

进程的三个基本状态  
![这里写图片描述][20170627102104930]

*  运行态/执行态（Running）：当一个进程在处理机上运行时，则称该进程处于运行状态。
 *  就绪态（Ready）：一个进程获得了除处理机外的一切所需资源，一旦得到处理机即可运行，则称此进程处于就绪状态。
 *  阻塞态（Blocked）：（又称挂起状态、等待状态）：一个进程正在等待某一事件发生（例如请求I／O而等待I／O完成等）而暂时仃止运行，这时即使把处理机分配给进程也无法运行，故称该进程处于阻塞状态。

三个基本状态之间可能转换和转换原因如下：

*  就绪态–＞运行态：当处理机空闲时，进程调度程序必将处理机分配给一个处于就绪态的进程 ，该进程便由就绪态转换为运行态。
 *  运行态–＞阻塞态：处于运行态的进程在运行过程中需要等待某一事件发生后（例如因I／O请求等待I／O完成后），才能继续运行，则该进程放弃处理机，从运行态转换为阻塞态。
 *  阻塞态–＞就绪态：处于阻塞态的进程，若其等待的事件已经发生，于是进程由阻塞态转换为就绪态。
 *  运行态–＞就绪态：处于运行状态的进程在其运行过程中，因分给它的处理机时间片已用完，而不得不让出（被抢占）处理机，于是进程由运行态转换为就绪态。
 *  而阻塞态–＞运行态和就绪态–＞阻塞态这二种状态转换不可能发生。
 *  处于运行态进程:如系统有一个处理机，则在任何一时刻，最多只有一个进程处于运行态。
 *  处于就绪态进程:一般处于就绪态的进程按照一定的算法（如先来的进程排在前面，或采用优先权高的进程排在前面）排成一个就绪队列RL。
 *  处于阻塞态进程:处于阻塞态的进程排在阻塞队列中。由于等待事件原因不同，阻塞队列也按事件分成几个队列WLi。

一个问题：假设一个只有一个处理机的系统中，OS的进程有运行、就绪、阻塞三个基本状态。假如某时刻该系统中有10个进程并发执行，在略去调度程序所占用时间情况下试问  
这时刻系统中处于运行态的进程数最多几个？最少几个  
这时刻系统中处于就绪态的进程数最多几个？最少几个  
这时刻系统中处于阻塞态的进程数最多几个？最少几个？  
解：因为系统中只有一个处理机，所以某时刻处于运行态的进程数最多只有一个。而最少可能为0，此时其它10个进程一定全部排在各阻塞队列中，在就绪队列中没有进程。而某时刻处于就绪态的进程数最多只有9个，不可能出现10个情况，因为一旦CPU有空，调度程序马上调度，当然这是在略去调度程序调度时间时考虑。处于阻塞态的进程数最少是0个。

### 3、进程控制模块（PCB） ###

*  进程控制块的作用  
    由于进程控制块中记录进程存在和特性信息；PCB与进程同生死，创建一个进程就是为其建立一个PCB，当进程被撤消时，系统就回收它的PCB；OS对进程的控制要是根据PCB来进行，对进程管理也通过对PCB管理来实现，所以进程控制块是进程存在的唯一实体。
 *  PCB的信息  
    进程标识符:它用于唯一地标识一个进程。它有外部标识符（由字母组成，供用户使用）和内部标识符（由整数组成，为方便系统管理而设置）二种。  
    进程调度信息：它包括进程状态（running、ready、blacked）、队列（就绪、阻塞队列）、队列指针，调度参数：进程优先级、进程已执行时间和已等待时间等。  
    处理机状态信息：它由处理机各种寄存器（通用寄存器、指令计数器、程序状态字PSW、用户栈指针等）的内容所组成，该类信息使进程被中断后重新执行时能恢复现场从断点处继续运行。  
    进程控制信息：它包括程序和数据的地址、I／O资源清单，保证进程正常运行的同步和通信机制等。  
    家族信息：它包括该进程的父、子进程标识符、进程的用户主等。  
    UNIX的PCB由Proc和user两个结构组成，proc常驻主存的系统区，是PCB中最基本和常用信息，而user可根据需要换进换出。

### 4、进程上下文 ###

进程是由程序、数据和进程控制块组成。进程上下文实际上是执行活动全过程的静态描述。具体说，进程上下文包括系统中与执行该进程有关的各种寄存器（例如：通用寄存器、程序计数器PC、程序状态寄存器PS等）的值，程序段在经编译之后形成的机器指令代码集（或称正文段）、数据集及各种堆栈值和PCB结构。一个进程的执行是在该进程的上下文中执行，而当系统调度新进程占有处理机时，新老进程的上下发生切换。UNIX 操作系统的进程上下文称为进程映象。

## 二、进程控制 ##

### 1、内核 ###

*  核心态和用户态  
    为了防止用户应用程序访问和／或更改重要的操作系统数据，Windows 2000、UNIX使用两种处理器访问模式：核心态和用户态（又称管态和目态）。操作系统代码在核心态下运行，即在x86处理器Ring0运行，它有着最高的特权。而用户应用程序代码在用户态下运行，即在x86处理器Ring3中运行。  
    用户应用程序（在Windows 2000中以用户线程方式出现）运行用户程序一般代码时，它是在用户态下执行。但当程序要调用系统服务，例如要调用操作系统中负责从磁盘文件中读取数据的NT执行体例程时，它就要通过一条专门的指令（自陷指令/访管指令）来完成从用户态切换到核心态，操作系统根据该指令及有关参数，执行用户的请求服务。在服务完成后将处理器模式切换回用户态，并将控制返回用户线程。因此用户线程有时在核心态下执行，在核心态下执行的是调用操作系统有关功能模块的代码。
 *  原语  
    原语是一种特殊的广义指令，它的功能是由系统通过一段不可分割的指令操作来完成，它又称原子操作，原语在核心态下完成。进程控制操作（创建、撤消、阻塞……）大都为原语操作。
 *  内核功能  
    内核是计算机硬件上的第一层扩充软件，它是OS中关键部分，它是管理控制中心。内核在核心态下运行，常驻内存，内核通过执行各种原语操作来实现各种控制和管理功能。

### 2、进程状态的细化 ###

*  “挂起”、 “激活”操作的引入  
    系统管理员有时需要暂停某个进程，以便排除系统故障或暂时减轻系统负荷，用户有时也希望暂停自己的进程以便检查自己作业的中间结果。这就希望系统提供“挂起”操作，暂停进程运行，同是也要提供“激活”的操作，恢复被挂起的进程。由于被挂起前进程的状态有三种，挂起后的进程就分为二种状态：静止就绪态和静止阻塞态（有的称挂起就绪态和挂起阻塞态）。挂起前的进程就绪态和阻塞态也改为活动就绪态和活动阻塞态。  
    ![这里写图片描述][20170627104509308]
 *  当进程处于运行态和活动就绪态时，执行挂起操作，进程状态转换为静止就绪态。当进程处于活动阻塞态时，执行挂起操作，进程状态转换为静止阻塞态。对被挂起的进程施加“激活”操作，则处于静止就绪的进程转换为活动就绪态，处于静止阻塞态的进程转换为活动阻塞态。被挂起的处于静止阻塞态的进程当它等待的事件发生后，它就由静止阻塞态转换为静止就绪态。

### 3、进程控制原语 ###

*  创建原语(Create)  
    一个进程可借助创建原语来创建一个新进程，该新进程是它的子进程，创建一个进程主要是为新进程创建一个PCB。创建原语首先从系统的PCB表中索取一个空白的PCB表目，并获得其内部标识，然后将调用进程提供的参数：如外部名、正文段、数据段的首址、大小、所需资源、优先级等填入这张空白PCB表目中。并设置新进程状态为活动／静止就绪态，并把该PCB插入到就绪队列RQ中，就可进入系统并发执行。
 *  撤消原语（Destroy）/ 终止（Termination）  
    对于树型层次结构的进程系统撤消原语采用的策略是由父进程发出，撤消它的一个子进程及该子进程所有的子孙进程，被撤消进程的所有资源（主存、I/O资源、PCB表目）全部释放出来归还系统，并将它们从所有的队列中移去。如撤消的进程正在运行，则要调用进程调度程序将处理器分给其它进程。
 *  阻塞原语（block）  
    当前进程因请求某事件而不能执行时（例如请求I／O而等待I／O完成时），该进程将调用阻塞原语阻塞自己，暂时放弃处理机。进程阻塞是进程自身的主动行为。阻塞过程首先立即仃止原来程序的执行，把PCB中的现行状态由运行态改为活动阻塞态，并将PCB插入到等待某事件的阻塞队列中，最后调用进程调度程序进行处理机的重新分配。
 *  唤醒原语（wakeup）  
    当被阻塞的进程所期待的事件发生时（例如I／O完成时），则有关进程和过程（例如I／O设备处理程序或释放资源的进程等）调用wakeup原语，将阻塞的进程唤醒，将等待该事件的进程从阻塞队列移出，插入到就绪队列中，将该进程的PCB中现行状态，如是活动阻塞态改为活动就绪态，如是静止阻塞态改为静止就绪态。
 *  挂起原语（suspend）  
    调用挂起原语的进程只能挂起它自己或它的子孙，而不能挂起别的族系的进程。挂起原语的执行过程是：检查要挂起进程PCB的现行状态，若正处于活动就绪态，便将它改为静止就绪态；如是活动阻塞态则改为静止阻塞态。如是运行态，则将它改为静止就绪态，并调用进程调度程序重新分配处理机。为了方便用户或父进程考察该进程的运行情况，需把该进程的PCB复制到内存指定区域。
 *  激活原语（active）  
    用户进程或父进程通过调用激活原语将被挂起的进程激活。激活原语执行过程是：检查被挂起进程PCB中的现行状态，若处于静止就绪态，则将它改为活动就绪态，若处于静止阻塞态，则将它改为活动阻塞态。

### 4、线程概念 ###

*  线程的引入  
    作为并发执行的进程具有二个基本的属性：进程既是一个拥有资源的独立单位，它可独立分配虚地址空间、主存和其它，又是一个可独立调度和分派的基本单位。这二个基本属性使进程成为并发执行的基本单位。在一些OS中，像大多数UNIX系统等，进程同时具有这二个属性。而另一些OS中，象WindowsNT、Solaris、OS／2、Mac OS等，这二个属性由OS独立处理。为了区分二个属性 ，资源拥有单元称为进程（或任务），调度的单位称为线程、又称轻进程（light weight process）。线程只拥有一点在运行中必不可省的资源（程序计数器、一组寄存器和栈），但它可与同属一个进程的其它线程共享进程拥有的全部资源。线程定义为进程内一个执行单元或一个可调度实体。
 *  线程的作用  
    线程的关键好处是从性能应用中得到的，在一个存在的进程中产生（或终止）一个线程比产生（或终止）一个进程化费少得多的时间。类似地，在同一进程内二个线程间切换时间也要比二个进程切换时间小得多。线程机制也增加了通讯的有效性。线程间通讯是在同一进程的地址空间内，共享主存和文件，所以非常简单，无需内核参与。因此假如一个应用或函数作为一组相关执行单元的应用，那么采用一组线程的集合比采用分开进程的集合要有效得多。
 *  线程的分类  
    核心级（系统级）线程(kernel-level thread)：依赖于OS核心，由内核的内部需求进行创建和撤销，用来执行一个指定的函数。  
    用户级线程(user-level thread)：不依赖于OS核心，应用进程利用线程库提供创建、同步、调度和管理线程的函数来控制用户线程。如：数据库系统informix，图形处理Aldus PageMaker。调度由应用软件内部进行，通常采用非抢先式和更简单的规则，也无需用户态/核心态切换，所以速度特别快。一个线程发起系统调用而阻塞，则整个进程在等待。时间片分配给进程，多线程则每个线程就慢。

## 三、进程同步 ##

### 1、进程同步的概念 ###

在多道程序环境下，系统中各进程以不可预测的速度向前推进，进程的异步性会造成了结果的不可再现性。为防止这种现象，异步的进程间推进受到二种限制：

*  资源共享关系  
    像打印机这类资源一次只允许一个进程使用的资源称为临界资源。属于临界资源有硬件打印机、磁带机等，软件在消息缓冲队列、变量、数组、缓冲区等。当然还有一类象磁盘等资源，它允许进程间共享，即可交替使用，所以它称为共享资源，而临界资源又称独享资源。  
    多进程之间如果共享资源，例如各进程争用一台打印机，这时各进程使用这台打印机时有一定的限制。每次只允许一个进程使用一段时间打印机，等该进程使用完毕后再将打印机分配给其它进程。这种使用原则称为互斥使用。
 *  相互合作关系  
    在某些进程之间还存在合作关系，例如一个程序的输入、计算、打印三个程序段作为三个进程并发执行，由于这三个进程间存在着相互合作的关系，即先输入再计算、最后再打印的关系，所以这三个进程在并发执行时推进序列受到限制，要保证其合作关系正确，进程间这种关系称为同步关系。

进程之间竞争资源也面临三个控制问题：

*  互斥（ mutual exclusion )指多个进程不能同时使用同一个资源；
 *  死锁（ deadlock )指多个进程互不相让，都得不到足够的资源；
 *  饥饿（ starvation )指一个进程一直得不到资源（其他进程可能轮流占用资源）。

进程在并发执行时为了保证结果的可再现性，各进程执行序列必须加以限制以保证互斥地使用临界资源，相互合作完成任务。多个相关进程在执行次序上的协调称为进程同步。用于保证多个进程在执行次序上的协调关系的相应机制称为进程同步机制。所有的进程同步机制应遵循下述四条准则：

*  空闲让进  
    当无进程进入临界区时，相应的临界资源处于空闲状态，因而允许一个请求进入临界区的进程立即进入自己的临界区。
 *  忙则等待  
    当已有进程进入自己的临界区时，即相应的临界资源正被访问，因而其它试图进入临界区的进程必须等待，以保证进程互斥地访问临界资源。
 *  有限等待  
    对要求访问临界资源的进程，应保证进程能在有限时间进入临界区，以免陷入“饥饿”状态。
 *  让权等待  
    当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入忙等。

### 2、硬件技术实现进程同步机制 ###

*  提高临界区代码执行中断优先级(IRQL)  
    这种方法在UNIX和Windows 2000中都使用，它是在单机系统中有效地实现互斥的一种方法。因为在传统操作系统中，打断进程对临界区代码的执行只有中断请求、中断一旦被接受，系统就有可能调用其它进程进入临界区，并修改此全局数据库。所以用提高临界区中断优先级方法就可以屏蔽了其它中断，保证了临界段的执行不被打断，从而实现了互斥。
 *  检测和设置（TS）硬件指令  
    许多大型机（如IBM370等）和微型机（如Intel x86等）中都提供了专用的硬件指令，这些指令全部允许对一个字中的内容进行检测和修正，或交换两个字的内容。特别要指出的是这些操作都是在一个存储周期中完成，或者说由一条指令来完成，用这些指令就可以解决临界区问题了。因为临界区问题在多道环境中之所以存在，是由于多个进程共同访问、修改同一公用变量。用这些硬件指令可以简单有效地实现互斥。其方法是为每个临界段或其它互斥资源设置一个布尔变量，例如称为lock。当其值为false则临界区末被使用，反之则说明正有进程在临界区中执行。
 *  自旋锁  
    Windows2000 内核用来达到多处理器互斥的机制“自旋锁”，它类同于TS指令机制。自旋锁是一个与共用数据结构有关的锁定机制。在每个进程进入自己的临界区之前，内核必须获得与所保护的DPC（延迟过程调用）队列有关的自旋锁。如果自旋锁非空，内核将一直尝试得到锁直到成功。因为内核（处理器也如此）被保持在过渡状态“旋转”，直到它获得锁，“自旋锁”由此而得名。  
    自旋锁像它们所保护的数据结构一样，储存在共用内存中。为了速度和使用任何在处理器体系下提供的锁定机构，获取和释放自旋锁的代码是用汇编语言写的。例如在Intel处理器上，Windows2000使用了一个只在486处理器或更高处理器上运行的指令。  
    当线程试图获得自旋锁时，在处理器上所有其它工作将终止。因此拥有自旋锁的线程永远不会被抢先，但允许它继续执行以便使它尽快把锁释放。内核对于使用自旋锁十分小心，当它拥有自旋锁时，它执行的指令数将减至最少。

### 3、信号量机制 ###

1965年，荷兰学者Dijkstra提出的信号量机制是一种卓有成效的进程同步工具，在长期广泛的应用中，信号量机制又得到了很大的发展，它从整型信号量机制发展到记录型信号量机制，进而发展为“信号集”机制。现在信号量机制已广泛应用于OS中。  
信号量按联系进程的关系分成二类：

*  公用信号量（互斥信号量）：它为一组需互斥共享临界资源的并发进程而设置，它代表永久性的共享的临界资源，每个进程均可对它施加P、V操作，即都可申请和释放该临界资源，其初始值置为1。
 *  专用信号量（同步信号量）：它为一组需同步协作完成任务的并发进程而设置，它代表消耗性的专用资源，只有拥有该资源的进程才能对它施加P操作（即可申请资源），而由其合作进程对它施加V操作（即释放资源）。

具体分类如下：

*  整型信号量  
    最初由Dijkstra把整型信号量定义为一个整型量，除初始化外，仅能通过两个标准的原子操作(Atomic Operation) wait(S)和signal(S)来访问。这两个操作一直被分别称为P、V操作。 wait和signal操作可描述为：  
    S .value＞0 ；表示可供使用资源数  
    S .value＝0 ；表示资源已被占用，无其它进程等待。  
    S .value＜0（＝-n） ；表示资源已被占用，还有n个进程因等待资源而阻塞。
 *  记录型信号量  
    在整型信号量机制中的wait操作，只要是信号量S≤0， 就会不断地测试。因此，该机制并未遵循“让权等待”的准则， 而是使进程处于“忙等”的状态。记录型信号量机制，则是一种不存在“忙等”现象的进程同步机制。但在采取了“让权等待”的策略后，又会出现多个进程等待访问同一临界资源的情况。为此，在信号量机制中，除了需要一个用于代表资源数目的整型变量value外，还应增加一个进程链表L，用于链接上述的所有等待进程。记录型信号量是由于它采用了记录型的数据结构而得名的。  
    在记录型信号量机制中，S.value的初值表示系统中某类资源的数目， 因而又称为资源信号量，对它的每次wait操作，意味着进程请求一个单位的该类资源，因此描述为S.value=S.value-1； 当S.value＜0时，表示该类资源已分配完毕，因此进程应调用block原语，进行自我阻塞，放弃处理机，并插入到信号量链表S.L中。可见，该机制遵循了“让权等待”准则。 此时S.value的绝对值表示在该信号量链表中已阻塞进程的数目。 对信号量的每次signal操作，表示执行进程释放一个单位资源，故S.value=S.value+1操作表示资源数目加1。 若加1后仍是S.value≤0，则表示在该信号量链表中，仍有等待该资源的进程被阻塞，故还应调用wakeup原语，将S.L链表中的第一个等待进程唤醒。如果S.value的初值为1，表示只允许一个进程访问临界资源，此时的信号量转化为互斥信号量。
 *  AND型信号量  
    在两个进程中都要包含两个对Dmutex和Emutex的操作。 AND同步机制的基本思想是：将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其它所有可能为之分配的资源，也不分配给他。亦即，对若干个临界资源的分配，采取原子操作方式：要么全部分配到进程，要么一个也不分配。 由死锁理论可知，这样就可避免上述死锁情况的发生。为此，在wait操作中，增加了一个“AND”条件，故称为AND同步，或称为同时wait操作， 即Swait(Simultaneous wait)。

### 4、利用信号量实现进程互斥 ###

为使多个进程能互斥地访问某临界资源，只需为该资源设置一个互斥信号量mutex,并设其初值为1，并规定每个进程在进入临界区CS前必须申请资源，即对互斥信号量mutex施加P操作，在退出临界区CS后必须释放资源，即对互斥信号量mutex施加V操作；即将各进程的临界区CS置于P（mutex）和V(mutex)操作之间。

### 5、经典进程同步问题 ###

#### 1、生产者-消费之问题 ####

在多道程序环境下，进程同步是一个十分重要又令人感兴趣的问题，而生产者-消费者问题是其中一个有代表性的进程同步问题。下面我们给出了各种情况下的生产者-消费者问题。  
（1）一个生产者，一个消费者，公用一个缓冲区。  
定义两个同步信号量：  
empty——表示缓冲区是否为空，初值为1。  
full——表示缓冲区中是否为满，初值为0。  
生产者进程

while(TRUE){ 
    生产一个产品; 
         P(empty); 
         产品送往Buffer; 
         V(full); 
    }

消费者进程

while(True){ 
    P(full); 
       从Buffer取出一个产品; 
       V(empty); 
       消费该产品; 
       }

（2）一个生产者，一个消费者，公用n个环形缓冲区。  
定义两个同步信号量：  
empty——表示缓冲区是否为空，初值为n。  
full——表示缓冲区中是否为满，初值为0。  
设缓冲区的编号为0～n-1，定义两个指针in和out，分别是生产者进程和消费者进程使用的指针，指向下一个可用的缓冲区。  
生产者进程

while(TRUE){ 
         生产一个产品; 
         P(empty); 
         产品送往buffer（in）； 
         in=(in+1)mod n； 
         V(full); 
    }

消费者进程

while(TRUE){ 
    P(full); 
       从buffer（out）中取出产品； 
       out=(out+1)mod n； 
       V(empty); 
       消费该产品; 
       }

（3）一组生产者，一组消费者，公用n个环形缓冲区  
在这个问题中，不仅生产者与消费者之间要同步，而且各个生产者之间、各个消费者之间还必须互斥地访问缓冲区。  
定义四个信号量：  
empty——表示缓冲区是否为空，初值为n。  
full——表示缓冲区中是否为满，初值为0。  
mutex1——生产者之间的互斥信号量，初值为1。  
mutex2——消费者之间的互斥信号量，初值为1。  
设缓冲区的编号为0～n-1，定义两个指针in和out，分别是生产者进程和消费者进程使用的指针，指向下一个可用的缓冲区。  
生产者进程

while(TRUE){ 
         生产一个产品; 
         P(empty); 
         P(mutex1)； 
         产品送往buffer（in）； 
         in=(in+1)mod n； 
         V(mutex1); 
         V(full); 
    }

消费者进程

while(TRUE){ 
    P(full) 
       P(mutex2)； 
       从buffer（out）中取出产品； 
       out=(out+1)mod n； 
       V（mutex2）； 
       V(empty); 
       消费该产品; 
       }

需要注意的是无论在生产者进程中还是在消费者进程中，两个P操作的次序不能颠倒。应先执行同步信号量的P操作，然后再执行互斥信号量的P操作，否则可能造成进程死锁。  
下面给出一个Java描述代码：

package com.kang;
    
    import java.util.concurrent.Semaphore;
    
    class Signs {
        
        static Semaphore empty = new Semaphore(10); // 信号量：表示仓库缓存区
        static Semaphore full = new Semaphore(0); // 信号量：表示仓库满的标志
        static Semaphore mutex = new Semaphore(1); // 临界区互斥访问信号量(二进制信号量)，相当于互斥锁。
    }
    
    class Producer implements Runnable {
        
        // 生产者
        public void run() {
            try {
                while (true) {
                    Signs.empty.acquire(); // 递减仓库缓存区信号量
                    Signs.mutex.acquire(); // 进入临界区
                    System.out.println("生成一个产品放入仓库");
                    Signs.mutex.release(); // 离开临界区
                    Signs.full.release(); // 递增仓库满信号量
                    Thread.currentThread().sleep(100);
                }
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }
    
    class Consumer implements Runnable {
        
        // 消费者
        public void run() {
            try {
                while (true) {
                    Signs.full.acquire(); // 递减仓库满信号量
                    Signs.mutex.acquire(); // 进入临界区
                    System.out.println("从仓库拿出一个产品消费");
                    Signs.mutex.release(); // 离开临界区
                    Signs.empty.release(); // 递增仓库缓存区信号量
                    Thread.currentThread().sleep(1000);
                }
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    
    }
    
    public class Test {
        
    
        public static void main(String[] args) {
            new Thread(new Producer()).start();
            new Thread(new Consumer()).start();
        }
    }

程序运行结果如下：  
![这里写图片描述][20170627155101245]

#### 2、哲学家进餐问题 ####

在1965年，Dijkstra提出并解决了一个他称之为哲学家进餐的同步问题。从那时起，每个发明新的同步原语的人都希望通过解决哲学家进餐间题来展示其同步原语的精妙之处。这个问题可以简单地描述：五个哲学家围坐在一张圆桌周围，每个哲学家面前都有一碟通心面，由于面条很滑，所以要两把叉子才能夹住。相邻两个碟子之间有一把叉子。哲学家的生活包括两种活动:即吃饭和思考。当一个哲学家觉得饿时，他就试图去取他左边和右边的叉子。如果成功地获得两把叉子，他就开始吃饭，吃完以后放下叉子继续思考。  
约束条件：  
(1)只有拿到两只筷子时，哲学家才能吃饭。  
(2)如果筷子已被别人拿走，则必须等别人吃完之后才能拿到筷子。  
(3)任一哲学家在自己未拿到两只筷子吃饭前，不会放下手中拿到的筷子。  
(4)用完之后将筷子返回原处。  
分析：筷子是临界资源，每次只被一个哲学家拿到，这是互斥关系。如果筷子被拿走，那么需要等待，这是同步关系。

在什么情况下5 个哲学家全部吃不上饭？  
考虑两种实现的方式，如下：  
A、设置一个信号量表示一只筷子，有5只筷子，所以设置5个信号量，哲学家每次饥饿时先试图拿左边的筷子，再试图拿右边的筷子，拿不到则等待，拿到了就进餐，最后逐个放下筷子。这种情况可能会产生死锁，因为我们不知道进程何时切换（这也是很多IPC问题的根本原因），如果5个哲学家同时饥饿，同时试图拿起左边的筷子，也很幸运地都拿到了，那么他们拿右边的筷子的时候都会拿不到，而根据第三个约束条件，都不会放下筷子，这就产生了死锁。描述如下：

void philosopher(int i) /*i：哲学家编号，从0 到4*/   
    {   
        while (TRUE) {   
            think( ); /*哲学家正在思考*/   
            take_fork(i); /*取左侧的筷子*/   
            take_fork((i+1) % N); /*取右侧筷子；％为取模运算*/   
            eat( ); /*吃饭*/   
            put_fork(i); /*把左侧筷子放回桌子*/   
            put_fork((i+1) % N); /*把右侧筷子放回桌子*/   
        }   
    }

B、规定在拿到左侧的筷子后，先检查右面的筷子是否可用。如果不可用，则先放下左侧筷子， 等一段时间再重复整个过程。  
分析：当出现以下情形，在某一个瞬间，所有的哲学家都同时启动这个算法，拿起左侧的筷 子，而看到右侧筷子不可用，又都放下左侧筷子，等一会儿，又同时拿起左侧筷子……如此 这样永远重复下去。对于这种情况，所有的程序都在运行，但却无法取得进展，即出现饥饿， 所有的哲学家都吃不上饭。

描述一种没有人饿死（永远拿不到筷子）算法。  
考虑了三种实现的方式（A、B、C）：  
A．原理：至多只允许四个哲学家同时进入房间进餐,以保证至少有一个哲学家在任何情况下能够正常进餐,最终总会释放出他所使用过的两支筷子,从而可使更多的哲学家进餐。  
以下将room作为信号量，只允许4个哲学家同时进入房间就餐，这样就能保证至少有一个哲学家可以就餐，而申请进入房间的哲学家进入room 的等待队列，根据FIFO 的原则，总会进入到房间就餐，因此不会 出现饿死和死锁的现象。  
伪码：

semaphore chopstick[5]={
       1，1，1，1，1};  //筷子信号量
    semaphore room=4;   
    void philosopher(int i)   
    {   
        while(true)   
        {   
            think();  //思考
            wait(room); //请求进入房间进餐   
            wait(chopstick[i]); //请求左手边的筷子   
            wait(chopstick[(i+1)%5]); //请求右手边的筷子   
            eat();   
            signal(chopstick[(i+1)%5]); //释放右手边的筷子   
            signal(chopstick[i]); //释放左手边的筷子   
            signal(room); //退出房间释放信号量room   
        }   
    }

B．原理：仅当哲学家的左右两支筷子都可用时,才允许他拿起筷子进餐。  
方法1：利用AND 型信号量机制实现：在一个原语中，将一段代码同时需 要的多个临界资源，要么全部分配给它，要么一个都不分配，因此不会出现死锁的情形。当某些资源不够时阻塞调用进程;由于等待队列的存在，使得对资源的请求满足FIFO 的要求， 因此不会出现饥饿的情形。  
伪码：

semaphore chopstick[5]={
       1，1，1，1，1};   //筷子信号量
    void philosopher(int I)   
    {   
        while(true)   
        {   
            think();   //思考
            Swait(chopstick[(I+1)]%5,chopstick[I]); //同时获取左右筷子，是AND信号量  
            eat();   //就餐
            Ssignal(chopstick[(I+1)]%5,chopstick[I]);   //释放
        }   
    }

方法2：利用信号量的保护机制实现。通过信号量mutex对eat（）之前的取左侧和右侧筷 子的操作进行保护，使之成为一个原子操作，这样可以防止死锁的出现。  
伪码：

semaphore mutex = 1 ;   //互斥信号量
    semaphore chopstick[5]={
       1，1，1，1，1};   
    void philosopher(int I)   
    {   
        while(true)   
        {   
            think();   
            wait(mutex);   //进入互斥区
            wait(chopstick[(I+1)]%5);  //获取右侧筷子 
            wait(chopstick[I]);   //获取左侧筷子
            signal(mutex);   //离开互斥区
            eat();   
            signal(chopstick[(I+1)]%5);   
            signal(chopstick[I]);   
        }   
    }

C． 原理：规定奇数号的哲学家先拿起他左边的筷子,然后再去拿他右边的筷子;而偶数号 的哲学家则相反。按此规定,将是1,2号哲学家竞争1号筷子,3,4号哲学家竞争3号筷子.即五个哲学家都竞争奇数号筷子,获得后,再去竞争偶数号筷子,最后总会有一个哲学家能获得两支筷子而进餐。而申请不到的哲学家进入阻塞等待队列，根FIFO原则，则先申请的哲学家会较先可以吃饭，因此不会出现饿死的哲学家。  
伪码：

semaphore chopstick[5]={
       1，1，1，1，1};   
    void philosopher(int i)   
    {   
        while(true)   
        {   
            think();   
            if(i%2 == 0) //偶数哲学家，先右后左。   
            {   
                wait (chopstick[ i + 1 ] mod 5) ;   
                wait (chopstick[ i]) ;   
                eat();   
                signal (chopstick[ i + 1 ] mod 5) ;   
                signal (chopstick[ i]) ;   
            }   
            Else //奇数哲学家，先左后右。   
            {   
                wait (chopstick[ i]) ;   
                wait (chopstick[ i + 1 ] mod 5) ;   
                eat();   
                signal (chopstick[ i]) ;   
                signal (chopstick[ i + 1 ] mod 5) ;   
            }   
        }   
    }

解决哲学家进餐问题的一个Java描述：

package com.kang;
    
    import java.util.Random;
    
    class Chopsticks {
        // 用 used[1]至 used[5]五个数组元素分别代表编号 1 至 5 的五支筷 子的状态
        // false 表示未被占用，true 表示已经被占用。 used[0]元素在本程序中未使用
        private boolean used[] = { true, false, false, false, false, false };
    
        // 拿起筷子的操作
        public synchronized void takeChopstick() {
            /* 取得该线程的名称并转化为整型,用此整数来判断该哲学家应该用哪两支筷子 */
            /* i 为左手边筷子编号，j 为右手边筷子编号 */
            String name = Thread.currentThread().getName();
            int i = Integer.parseInt(name);
            /*
             * 1~4 号哲学家使用的筷子编号是 i 和 i+1,5 号哲学家使用 的筷子编号是 5 和 1
             */
            int j = i == 5 ? 1 : i + 1;
            /* 将两边筷子的编号按奇偶顺序赋给 odd,even 两个变量 */
            int odd, even;
            if (i % 2 == 0) {
                even = i;
                odd = j;
            } else {
                odd = i;
                even = j;
            }
            /* 首先竞争奇数号筷子 */
            while (used[odd]) {
                try {
                    wait();
                } catch (InterruptedException e) {
                }
            }
            used[odd] = true;
            /* 然后竞争偶数号筷子 */
            while (used[even]) {
                try {
                    wait();
                } catch (InterruptedException e) {
                }
            }
            used[even] = true;
        }
    
        /* 放下筷子的操作 */
        public synchronized void putChopstick() {
            String name = Thread.currentThread().getName();
            int i = Integer.parseInt(name);
            int j = i == 5 ? 1 : i + 1;
            /*
             * 将相应筷子的标志置为 fasle 表示使用完毕， 并且通知其他等待线程来竞争
             */
            used[i] = false;
            used[j] = false;
            notifyAll();
        }
    }
    
    class Philosopher extends Thread {
        Random rand = new Random();//用来进行随机延时
        Chopsticks chopsticks;
    
        public Philosopher(String name, Chopsticks chopsticks) {
            /* 在构造实例时将 name 参数传给 Thread 的构造函数作为线程的名称 */
            super(name);
            /* 所有哲学家线程共享同一个筷子类的实例 */
            this.chopsticks = chopsticks;
        }
    
        public void run() {
            /* 交替地思考、拿起筷子、进餐、放下筷子 */
            while (true) {
                thinking();
                chopsticks.takeChopstick();
                eating();
                chopsticks.putChopstick();
            }
        }
    
        public void thinking() {
            /* 显示字符串输出正在思考的哲学家，用线程休眠若干秒钟来模拟思考时间 */
            System.out.println("Philosopher " + Thread.currentThread().getName()
                    + " is thinking.");
            try {
                Thread.sleep(1000 * rand.nextInt(5));
            } catch (InterruptedException e) {
            }
        }
    
        public void eating() {
            /* 显示字符串输出正在进餐的哲学家，并用线程休眠 若干 秒钟来模拟进餐时间 */
            System.out.println("Philosopher " + Thread.currentThread().getName()
                    + " is eating.");
            try {
                Thread.sleep(1000 * rand.nextInt(5));
            } catch (InterruptedException e) {
            }
        }
    }
    
    public class Test {
        
    
        public static void main(String[] args) {
            {
                /* 产生筷子类的实例 chopsticks */
                Chopsticks chopsticks = new Chopsticks();
                /* 用筷子类的实例作为参数， 产生五个哲学家线程并启动 */
                /* 五个哲学家线程的名称为 1~5 */
                new Philosopher("1", chopsticks).start();
                new Philosopher("2", chopsticks).start();
                new Philosopher("3", chopsticks).start();
                new Philosopher("4", chopsticks).start();
                new Philosopher("5", chopsticks).start();
            }
        }
    }

#### 3、读者-写者问题 ####

读者一写者问题(Courtois et al., 1971)为数据库访问建立了一个模型。例如，设想一个飞机定票系统，其中有许多竞争的进程试图读写其中的数据。多个进程同时读是可以接受的，但如果一个进程正在写数据库、则所有的其他进程都不能访问数据库，即使读操作也不行。  
我们来分析他们的关系，首先，这个问题没有明显的同步关系，因为在这个问题里，读和写并不要合作完成某些事情。但是是有互斥关系的，写者和写者，写者和读者是有互斥关系的，我们需要设置一个mutex来控制其访问，但是单纯一个信号量的话会出现读者和读者的互斥也出现了，因为我们可能有多个读者，所以我们设置一个变量ReadCount表示读者的数量，好，这个时候，对于ReadCount又要实现多个读者对他的互斥访问，所以还要设置一个RC\_mutex。这样就好了。然后是行为设计：

void Reader() {
     while(1) {
     P(&RC_mutex);
     rc = rc + 1;
     if(rc == 1) P(&mutex); //如果是第一个读者，那么限制写者的访问
     V(&RC_mutex);
     //读数据
     P(&RC_mutex);
     rc = rc - 1;
     if(rc == 0) V(&mutex); //如果是最后一个读者，那么释放以供写者或读者访问
     V(&RC_mutex);
     }
    }
    void Writer() {
     while(1) {
     P(&mutex);
     //写数据
     V(&mutex);
     }
    }

这里给出Java描述：

package com.kang;
    
    import java.util.concurrent.Semaphore;
    
    class Sign {
        
        static Semaphore db = new Semaphore(1); // 信号量：控制对数据库的访问
        static Semaphore mutex = new Semaphore(1); // 信号量：控制对临界区的访问
        static int rc = 0; // 记录正在读或者想要读的进程数
    }
    
    class Reader implements Runnable {
        
    
        public void run(){  
            try {  
                //互斥对rc的操作  
                Sign.mutex.acquire();  
                Sign.rc++;  //又多了一个读线程  
                if(Sign.rc==1) Sign.db.acquire(); //如果是第一个读进程开始读取DB，则请求一个许可，使得写进程无法操作 DB  
                Sign.mutex.release();  
    
                //无临界区控制，多个读线程都可以操作DB  
                System.out.println("[R]   "+Thread.currentThread().getName()+": read data....");  
                Thread.sleep(100);  
    
                //互斥对rc的操作  
                Sign.mutex.acquire();  
                Sign.rc--;  
                if(Sign.rc==0) Sign.db.release(); //如果最后一个读进程读完了，则释放许可，让写进程有机会操作DB  
                Sign.mutex.release();  
    
            } catch (InterruptedException e) {  
                e.printStackTrace();  
            }  
        }}
    
    class Writer implements Runnable {
        
    
        public void run() {
            try {
                // 与读操作互斥访问DB
                Sign.db.acquire();
                System.out.println("[W]   " + Thread.currentThread().getName()
                        + ": write data....");
                Thread.sleep(100);
                Sign.db.release();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
    
        }
    }
    
    public class Test {
        
    
        public static void main(String[] args) {
            new Thread(new Reader()).start();
            new Thread(new Reader()).start();
            new Thread(new Writer()).start();
        }
    }

其实，这个方法是有一定问题的，只要趁前面的读者还没读完的时候新一个读者进来，这样一直保持，那么写者会一直得不到机会，导致饿死。有一种解决方法就是在一个写者到达时，如果后面还有新的读者进来，那么先挂起那些读者，先执行写者，但是这样的话并发度和效率又会降到很低。

[20170627102104930]: /images/20220613/694b31cf339d4b0d8086e44cbb9841b5.png
[20170627104509308]: /images/20220613/e611354cf3eb4790a65dd98e1ba5dd32.png
[20170627155101245]: /images/20220613/6a7088b3b7214b26af9859333584c358.png