进程同步的基本概念：临界资源、同步和互斥

在多道程序环境下，进程是并发执行的，不同进程之间存在着不同的相互制约关系。为了协调进程之间的相互制约关系，引入了进程同步的概念。

临界资源
虽然多个进程可以共享系统中的各种资源，但其中许多资源一次只能为一个进程所使用，我们把一次仅允许一个进程使用的资源称为临界资源。许多物理设备都属于临界资源，如打印机等。此外，还有许多变量、数据等都可以被若干进程共享，也属于临界资源。


对临界资源的访问，必须互斥地进行，在每个进程中，访问临界资源的那段代码称为临界区。为了保证临界资源的正确使用，可以把临界资源的访问过程分成四个部分：
进入区。为了进入临界区使用临界资源，在进入区要检查可否进入临界区，如果可以进入临界区，则应设置正在访问临界区的标志，以阻止其他进程同时进入临界区。
临界区。进程中访问临界资源的那段代码，又称临界段。
退出区。将正在访问临界区的标志清除。
剩余区。代码中的其余部分。
do {
entry section; //进入区
critical section; //临界区
exit section; //退出区
remainder section; //剩余区
} while (true)


同步
同步亦称直接制约关系，它是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而等待、传递信息所产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作。


例如，输入进程A通过单缓冲向进程B提供数据。当该缓冲区空时，进程B不能获得所需数据而阻塞，一旦进程A将数据送入缓冲区，进程B被唤醒。反之，当缓冲区满时，进程A被阻塞，仅当进程B取走缓冲数据时，才唤醒进程A。

互斥
互斥亦称间接制约关系。当一个进程进入临界区使用临界资源时，另一个进程必须等待, 当占用临界资源的进程退出临界区后，另一进程才允许去访问此临界资源。

例如，在仅有一台打印机的系统中，有两个进程A和进程B，如果进程A需要打印时, 系统已将打印机分配给进程B,则进程A必须阻塞。一旦进程B将打印机释放，系统便将进程A唤醒，并将其由阻塞状态变为就绪状态。


为禁止两个进程同时进入临界区，同步机制应遵循以下准则：
空闲让进。临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区。
忙则等待。当已有进程进入临界区时，其他试图进入临界区的进程必须等待。
有限等待。对请求访问的进程，应保证能在有限时间内进入临界区。
让权等待。当进程不能进入临界区时，应立即释放处理器，防止进程忙等待。



2.10 实现临界区互斥的基本方法

软件实现方法
在进入区设置和检查一些标志来标明是否有进程在临界区中，如果已有进程在临界区，则在进入区通过循环检查进行等待，进程离开临界区后则在退出区修改标志。

1) 算法一：单标志法。
该算法设置一个公用整型变量turn,用于指示被允许进入临界区的进程编号，即若turn=0，则允许P0进程进入临界区。该算法可确保每次只允许一个进程进入临界区。但两个进程必须交替进入临界区，如果某个进程不再进入临界区了，那么另一个进程也将进入临界区（违背“空闲让进”）这样很容易造成资源利用的不充分。
</pre><pre name="code" class="cpp">// P0进程
while(turn!=0);
critical section;
turn=1;
remainder section;


// P1进程
while(turn!=1);  // 进入区
critical section;  // 临界区
turn = 0;  // 退出区
remainder section;  // 剩余区



2) 算法二：双标志法先检查。
该算法的基本思想是在每一个进程访问临界区资源之前，先查看一下临界资源是否正被访问，若正被访问，该进程需等待；否则，进程才进入自己的临界区。为此，设置了一个数据flag[i]，如第i个元素值为FALSE，表示Pi进程未进入临界区，值为TRUE，表示Pi进程进入临界区。
// Pi 进程
while(flag[j]);  // ①    
flag[i]=TRUE;  // ③  
critical section;   
flag[i] = FALSE; 
remainder section;


// Pj 进程
while(flag[i]);  // ② 进入区
flag[j] =TRUE;  // ④ 进入区
critical section;  // 临界区
flag[j] = FALSE;  // 退出区
remainder section;  // 剩余区


优点：不用交替进入，可连续使用；缺点：Pi和Pj可能同时进入临界区。按序列①②③④ 执行时，会同时进入临界区（违背“忙则等待”)。即在检查对方flag之后和切换自己flag 之前有一段时间，结果都检查通过。这里的问题出在检查和修改操作不能一次进行。

3) 算法三：双标志法后检查。
算法二是先检测对方进程状态标志后，再置自己标志，由于在检测和放置中可插入另一个进程到达时的检测操作，会造成两个进程在分别检测后，同时进入临界区。为此，算法三釆用先设置自己标志为TRUE后,再检测对方状态标志，若对方标志为TURE，则进程等待；否则进入临界区。

// Pi进程
flag[i] =TRUE;
while(flag[j]);
critical section;
flag[i] =FLASE;
remainder section;


// Pj进程
flag[j] =TRUE;  // 进入区
while(flag[i]);  // 进入区
critical section;  // 临界区
flag [j] =FLASE;   // 退出区
remainder section;  // 剩余区


当两个进程几乎同时都想进入临界区时，它们分别将自己的标志值flag设置为TRUE，并且同时检测对方的状态（执行while语句），发现对方也要进入临界区，于是双方互相谦让，结果谁也进不了临界区，从而导致“饥饿”现象。

4)算法四：Peterson’s Algorithm。
为了防止两个进程为进入临界区而无限期等待，又设置变量turn，指示不允许进入临界区的进程编号，每个进程在先设置自己标志后再设置turn 标志，不允许另一个进程进入。这时，再同时检测另一个进程状态标志和不允许进入标志，这样可以保证当两个进程同时要求进入临界区，只允许一个进程进入临界区。

// Pi进程
flag[i]=TURE; turn=j;
while(flag[j]&&turn==j); 
critical section;
flag[i]=FLASE;
remainder section;


// Pj进程
flag[j] =TRUE;turn=i;  // 进入区
while(flag[i]&&turn==i);   // 进入区
critical section;  // 临界区
flag[j]=FLASE;  // 退出区
remainder section;  // 剩余区


本算法的基本思想是算法一和算法三的结合。利用flag解决临界资源的互斥访问，而利用turn解决“饥饿”现象。

硬件实现方法
本节对硬件实现的具体理解对后面的信号量的学习很有帮助。计算机提供了特殊的硬件指令，允许对一个字中的内容进行检测和修正，或者是对两个字的内容进行交换等。通过硬件支持实现临界段问题的低级方法或称为元方法。

1) 中断屏蔽方法
当一个进程正在使用处理机执行它的临界区代码时，要防止其他进程再进入其临界区访问的最简单方法是禁止一切中断发生，或称之为屏蔽中断、关中断。因为CPU只在发生中断时引起进程切换，这样屏蔽中断就能保证当前运行进程将临界区代码顺利地执行完，从而保证了互斥的正确实现，然后再执行开中断。其典型模式为：…关中断;临界区;开中断;…这种方法限制了处理机交替执行程序的能力，因此执行的效率将会明显降低。对内核来说，当它执行更新变量或列表的几条指令期间关中断是很方便的，但将关中断的权力交给用户则很不明智，若一个进程关中断之后不再开中断，则系统可能会因此终止。

2) 硬件指令方法
TestAndSet指令：这条指令是原子操作，即执行该代码时不允许被中断。其功能是读出指定标志后把该标志设置为真。指令的功能描述如下：
boolean TestAndSet(boolean *lock){
    boolean old;
    old = *lock;
    *lock=true;
    return old;
}

可以为每个临界资源设置一个共享布尔变量lock，表示资源的两种状态：true表示正被占用，初值为false。在进程访问临界资源之前，利用TestAndSet检查和修改标志lock；若有进程在临界区，则重复检查，直到进程退出。利用该指令实现进程互斥的算法描述如下：

while TestAndSet (& 1 ock);
// 进程的临界区代码段;
lock=false;
// 进程的其他代码

Swap指令：该指令的功能是交换两个字节的内容。其功能描述如下。

Swap(boolean *a, boolean *b){  
    boolean temp;
    Temp=*a;
    *a = *b;
    *b = temp;
}

注意：以上对TestAndSet和Swap指令的描述仅仅是功能实现，并非软件实现定义，事实上它们是由硬件逻辑直接实现的，不会被中断。应为每个临界资源设置了一个共享布尔变量lock，初值为false；在每个进程中再设置一个局部布尔变量key，用于与lock交换信息。在进入临界区之前先利用Swap指令交换lock 与key的内容，然后检查key的状态；有进程在临界区时，重复交换和检查过程，直到进程退出。利用Swap指令实现进程互斥的算法描述如下：

key=true;
while(key!=false)
Swap(&lock, &key); 
// 进程的临界区代码段；
lock=false;
// 进程的其他代码；

硬件方法的优点：适用于任意数目的进程，不管是单处理机还是多处理机；简单、容易验证其正确性。可以支持进程内有多个临界区，只需为每个临界区设立一个布尔变量。硬件方法的缺点：进程等待进入临界区时要耗费处理机时间，不能实现让权等待。从等待进程中随机选择一个进入临界区，有的进程可能一直选不上，从而导致“饥饿”现象。



2.11 信号量：整型、记录型信号量以及利用信号量实现进程互斥和前驱关系
信号量机构是一种功能较强的机制，可用来解决互斥与同步的问题，它只能被两个标准的原语wait(S)和signal(S)来访问，也可以记为“P操作”（通过）和“V操作（释放）”。原语是指完成某种功能且不被分割不被中断执行的操作序列，通常可由硬件来实现完成不被分割执行特性的功能。如前述的“Test-and-Set”和“Swap”指令，就是由硬件实现的原子操作。原语功能的不被中断执行特性在单处理机时可由软件通过屏蔽中断方法实现。原语之所以不能被中断执行，是因为原语对变量的操作过程如果被打断，可能会去运行另一个对同一变量的操作过程，从而出现临界段问题。如果能够找到一种解决临界段问题的元方法，就可以实现对共享变量操作的原子性。

整型信号量
整型信号量被定义为一个用于表示资源数目的整型量S，wait和signal操作可描述为：

wait(S){
    while (S<=0);
    S=S-1;
}
signal(S){
    S=S+1;
}

wait操作中，只要信号量S<=0，就会不断地测试。因此，该机制并未遵循“让权等待” 的准则，而是使进程处于“忙等”的状态。

记录型信号量
记录型信号量是不存在“忙等”现象的进程同步机制。除了需要一个用于代表资源数目的整型变量value外，再增加一个进程链表L，用于链接所有等待该资源的进程，记录型信号量是由于釆用了记录型的数据结构得名。记录型信号量可描述为：

typedef struct{
    int value;
    struct process *L;
} semaphore;

相应的wait(S)和signal(S)的操作如下：

void wait (semaphore S) { //相当于申请资源
    S.value--;
    if(S.value<0) {
        add this process to S.L;
        block(S.L);
    }
}

wait操作，S.value--，表示进程请求一个该类资源，当S.value<0时，表示该类资源已分配完毕，因此进程应调用block原语，进行自我阻塞，放弃处理机，并插入到该类资源的等待队列S.L中，可见该机制遵循了“让权等待”的准则。

void signal (semaphore S) {  //相当于释放资源
    S.value++;
    if(S.value<=0){
        remove a process P from S.L;
        wakeup(P);
    }
}
signal操作，表示进程释放一个资源，使系统中可供分配的该类资源数增1，故S.value++。若加1后仍是S.value<=0，则表示在S.L中仍有等待该资源的进程被阻塞，故还应调用wakeup 原语，将S.L中的第一个等待进程唤醒。

利用信号量实现同步
信号量机构能用于解决进程间各种同步问题。设S为实现进程P1、P2同步的公共信号量，初值为0。进程P2中的语句y要使用进程P1中语句x的运行结果，所以只有当语句x执行完成之后语句y才可以执行。其实现进程同步的算法如下：

semaphore S = 0;  //初始化信号量
P1 ( ) {
    // …
    x;  //语句x
    V(S);  //告诉进程P2,语句乂已经完成
}
P2()）{
    // …
    P(S) ;  //检查语句x是否运行完成
    y;  // 检查无误，运行y语句
    // …
}

利用信号量实现进程互斥
信号量机构也能很方便地解决进程互斥问题。设S为实现进程Pl、P2互斥的信号量，由于每次只允许一个进程进入临界区，所以S的初值应为1（即可用资源数为1)。只需把临界区置于P(S)和V(S)之间，即可实现两进程对临界资源的互斥访问。其算法如下：

semaphore S = 1;  //初化信号量
P1 ( ) {
    // …
    P(S);  // 准备开始访问临界资源，加锁
    // 进程P1的临界区
    V(S);  // 访问结束，解锁
    // …
}
P2() {
    // …
    P(S); //准备开始访问临界资源，加锁
    // 进程P2的临界区；
    V(S);  // 访问结束，解锁
    // …
}
互斥的实现是不同进程对同一信号量进行P、V操作，一个进程在成功地对信号量执行了P操作后进入临界区，并在退出临界区后，由该进程本身对该信号量执行V操作,表示当前没有进程进入临界区，可以让其他进程进入。

利用信号量实现前驱关系
信号量也可以用来描述程序之间或者语句之间的前驱关系。图2-8给出了一个前驱图，其中S1, S2, S3, …, S6是最简单的程序段（只有一条语句）。为使各程序段能正确执行，应设置若干个初始值为“0”的信号量。例如，为保证S1 -> S2、 S1 -> S3的前驱关系，应分别设置信号量a1、a2。同样，为了保证 S2 -> S4、S2
 ->S5、S3 -> S6、S4 -> S6、S5 -> S6,应设置信号量bl、b2、c、d、e。 



图2-8 前驱图举例





实现算法如下：

semaphore  al=a2=bl=b2=c=d=e=0;  //初始化信号量
S1() {
    // …
    V(al);  V(a2) ;  //S1已经运行完成
}
S2() {
    P(a1);  //检查S1是否运行完成
    // …
    V(bl); V(b2); // S2已经运行完成
}
S3() {
    P(a2);  //检查S1是否已经运行完成
    // …
    V(c);  //S3已经运行完成
}
S4() {
    P(b1);  //检查S2是否已经运行完成
    // …
    V(d);  //S4已经运行完成
}
S5() {
    P(b2);  //检查S2是否已经运行完成
    // …
    V(e);  // S5已经运行完成
}
S6() {
    P(c);  //检查S3是否已经运行完成
    P(d);  //检查S4是否已经运行完成
    P(e);  //检查S5是否已经运行完成
    // …;
}



分析进程同步和互斥问题的方法步骤
1) 关系分析。找出问题中的进程数，并且分析它们之间的同步和互斥关系。同步、互斥、前驱关系直接按照上面例子中的经典范式改写。2) 整理思路。找出解决问题的关键点，并且根据做过的题目找出解决的思路。根据进程的操作流程确定P操作、V操作的大致顺序。3) 设置信号量。根据上面两步，设置需要的信号量，确定初值，完善整理。




2.12 管程：管程的定义、组成及基本特性

管程的定义
系统中的各种硬件资源和软件资源，均可用数据结构抽象地描述其资源特性，即用少量信息和对资源所执行的操作来表征该资源，而忽略了它们的内部结构和实现细节。管程是由一组数据以及定义在这组数据之上的对这组数据的操作组成的软件模块，这组操作能初始化并改变管程中的数据和同步进程。

管程的组成
1) 局部于管程的共享结构数据说明。2) 对该数据结构进行操作的一组过程。3) 对局部于管程的共享数据设置初始值的语句。

管程的基本特性
1) 局部于管程的数据只能被局部于管程内的过程所访问。2) 一个进程只有通过调用管程内的过程才能进入管程访问共享数据。3) 每次仅允许一个进程在管程内执行某个内部过程。由于管程是一个语言成分，所以管程的互斥访问完全由编译程序在编译时自动添加，无需程序员关注，而且保证正确。

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

问题描述
一组生产者进程和一组消费者进程共享一个初始为空、大小为n的缓冲区，只有缓冲区没满时，生产者才能把消息放入到缓冲区，否则必须等待；只有缓冲区不空时，消费者才能从中取出消息，否则必须等待。由于缓冲区是临界资源，它只允许一个生产者放入消息，或者一个消费者从中取出消息。

问题分析
1) 关系分析。生产者和消费者对缓冲区互斥访问是互斥关系，同时生产者和消费者又是一个相互协作的关系，只有生产者生产之后，消费者才能消费，他们也是同步关系。2)
 整理思路。这里比较简单，只有生产者和消费者两个进程，正好是这两个进程存在着互斥关系和同步关系。那么需要解决的是互斥和同步PV操作的位置。3) 信号量设置。信号量mutex作为互斥信号量，它用于控制互斥访问缓冲池，互斥信号量初值为1；信号量full用于记录当前缓冲池中“满”缓冲区数，初值为0。信号量empty 用于记录当前缓冲池中“空”缓冲区数，初值为n。生产者-消费者进程的描述如下：

semaphore mutex=1; //临界区互斥信号量
semaphore empty=n;  //空闲缓冲区
semaphore full=0;  //缓冲区初始化为空
producer () { //生产者进程
    while(1){
        produce an item in nextp;  //生产数据
        P(empty);  //获取空缓冲区单元
        P(mutex);  //进入临界区.
        add nextp to buffer;  //将数据放入缓冲区
        V(mutex);  //离开临界区,释放互斥信号量
        V(full);  //满缓冲区数加1
    }
}

consumer () {  //消费者进程
    while(1){
        P(full);  //获取满缓冲区单元
        P(mutex);  // 进入临界区
        remove an item from buffer;  //从缓冲区中取出数据
        V (mutex);  //离开临界区，释放互斥信号量
        V (empty) ;  //空缓冲区数加1
        consume the item;  //消费数据
    }
}
该类问题要注意对缓冲区大小为n的处理，当缓冲区中有空时便可对empty变量执行P 操作，一旦取走一个产品便要执行V操作以释放空闲区。对empty和full变量的P操作必须放在对mutex的P操作之前。如果生产者进程先执行P(mutex)，然后执行P(empty)，消费者执行P(mutex),然后执行P(fall),这样可不可以？答案是否定的。设想生产者进程已经将缓冲区放满，消费者进程并没有取产品，即empty
 = 0，当下次仍然是生产者进程运行时，它先执行P(mutex)封锁信号量，再执行P(empty)时将被阻塞，希望消费者取出产品后将其唤醒。轮到消费者进程运行时，它先执行P(mutex)，然而由于生产者进程已经封锁mutex信号量，消费者进程也会被阻塞，这样一来生产者、消费者进程都将阻塞，都指望对方唤醒自己，陷入了无休止的等待。同理，如果消费者进程已经将缓冲区取空，即 full = 0,下次如果还是消费者先运行，也会出现类似的死锁。不过生产者释放信号量时，mutex、full先释放哪一个无所谓，消费者先释放mutex还是empty都可以。


下面再看一个较为复杂的生产者-消费者问题:

问题描述
桌子上有一只盘子，每次只能向其中放入一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子专等吃盘子中的橘子，女儿专等吃盘子中的苹果。只有盘子为空时，爸爸或妈妈就可向盘子中放一个水果；仅当盘子中有自己需要的水果时，儿子或女儿

可以从盘子中取出。

问题分析
1) 关系分析。这里的关系稍复杂一些，首先由每次只能向其中放入一只水果可知爸爸和妈妈是互斥关系。爸爸和女儿、妈妈和儿子是同步关系，而且这两对进程必须连起来，儿子和女儿之间没有互斥和同步关系，因为他们是选择条件执行，不可能并发，如图2-8所示。


2) 整理思路。这里有4个进程，实际上可以抽象为两个生产者和两个消费者被连接到大小为1的缓冲区上。








图2-9  进程之间的关系



3) 信号量设置。首先设置信号量plate为互斥信号量，表示是否允许向盘子放入水果，初值为1，表示允许放入，且只允许放入一个。信号量 apple表示盘子中是否有苹果，初值为0，表示盘子为空，不许取，若apple=l可以取。信号量orange表示盘子中是否有橘子，初值为0，表示盘子为空，不许取，若orange=l可以取。解决该问题的代码如下：
semaphore plate=l, apple=0, orange=0;
dad() {  //父亲进程
    while (1) {
        prepare an apple;
        P(plate) ;  //互斥向盘中取、放水果
        put the apple on the plate;  //向盘中放苹果
        V(apple);  //允许取苹果
    }
}

mom() {  // 母亲进程
    while(1) {
        prepare an orange;
        P(plate);  //互斥向盘中取、放水果
        put the orange on the plate;  //向盘中放橘子
        V(orange); //允许取橘子
    }
}

son(){  //儿子进程
    while(1){
        P(orange) ;  //互斥向盘中取橘子
        take an orange from the plate;
        V(plate);  //允许向盘中取、放水果
        eat the orange;
    }
}

daughter () {  //女儿进程
    while(1) {
        P(apple);  // 互斥向盘中取苹果
        take an apple from the plate;
        V(plate);  //运行向盘中取、放水果
        eat the apple;
    }
}
进程间的关系如图2-9所示。dad()和daughter()、mam()和son()必须连续执行，正因为如此，也只能在女儿拿走苹果后，或儿子拿走橘子后才能释放盘子，即V(plate)操作。




2.14 经典进程同步问题2：读者-写者问题

问题描述
有读者和写者两组并发进程，共享一个文件，当两个或以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致数据不一致的错误。因此要求：①允许多个读者可以同时对文件执行读操作；②只允许一个写者往文件中写信息；③任一写者在完成写操作之前不允许其他读者或写者工作；④写者执行写操作前，应让已有的读者和写者全部退出。

问题分析
1) 关系分析。由题目分析读者和写者是互斥的，写者和写者也是互斥的，而读者和读者不存在互斥问题。


2) 整理思路。两个进程，即读者和写者。写者是比较简单的，它和任何进程互斥，用互斥信号量的P操作、V操作即可解决。读者的问题比较复杂，它必须实现与写者互斥的同时还要实现与其他读者的同步，因此，仅仅简单的一对P操作、V操作是无法解决的。那么，在这里用到了一个计数器，用它来判断当前是否有读者读文件。当有读者的时候写者是无法写文件的，此时读者会一直占用文件，当没有读者的时候写者才可以写文件。同时这里不同读者对计数器的访问也应该是互斥的。


3) 信号量设置。首先设置信号量count为计数器，用来记录当前读者数量，初值为0; 设置mutex为互斥信号量，用于保护更新count变量时的互斥；设置互斥信号量rw用于保证读者和写者的互斥访问。


代码如下：

int count=0;  //用于记录当前的读者数量
semaphore mutex=1;  //用于保护更新count变量时的互斥
semaphore rw=1;  //用于保证读者和写者互斥地访问文件
writer () {  //写者进程
    while (1){
        P(rw); // 互斥访问共享文件
        Writing;  //写入
        V(rw) ;  //释放共享文件
    }
}

reader () {  // 读者进程
    while(1){
        P (mutex) ;  //互斥访问count变量
        if (count==0)  //当第一个读进程读共享文件时
            P(rw);  //阻止写进程写
        count++;  //读者计数器加1
        V (mutex) ;  //释放互斥变量count
        reading;  //读取
        P (mutex) ;  //互斥访问count变量
        count--; //读者计数器减1
        if (count==0)  //当最后一个读进程读完共享文件
            V(rw) ;  //允许写进程写
        V (mutex) ;  //释放互斥变量 count
    }
}


在上面的算法中，读进程是优先的，也就是说，当存在读进程时，写操作将被延迟，并且只要有一个读进程活跃，随后而来的读进程都将被允许访问文件。这样的方式下，会导致写进程可能长时间等待，且存在写进程“饿死”的情况。


如果希望写进程优先，即当有读进程正在读共享文件时，有写进程请求访问，这时应禁止后续读进程的请求，等待到已在共享文件的读进程执行完毕则立即让写进程执行，只有在无写进程执行的情况下才允许读进程再次运行。为此，增加一个信号量并且在上面的程序中 writer()和reader()函数中各增加一对PV操作，就可以得到写进程优先的解决程序。

int count = 0;  //用于记录当前的读者数量
semaphore mutex = 1;  //用于保护更新count变量时的互斥
semaphore rw=1;  //用于保证读者和写者互斥地访问文件
semaphore w=1;  //用于实现“写优先”

writer(){
    while(1){
        P(w);  //在无写进程请求时进入
        P(rw);  //互斥访问共享文件
        writing;  //写入
        V(rw);  // 释放共享文件
        V(w) ;  //恢复对共享支件的访问
    }
}

reader () {  //读者进程
    while (1){
        P (w) ;  // 在无写进程请求时进入
        P (mutex);  // 互斥访问count变量

        if (count==0)  //当第一个读进程读共享文件时
            P(rw);  //阻止写进程写

        count++;  //读者计数器加1
        V (mutex) ;  //释放互斥变量count
        V(w);  //恢复对共享文件的访问
        reading;  //读取
        P (mutex) ; //互斥访问count变量
        count--;  //读者计数器减1

        if (count==0)  //当最后一个读进程读完共享文件
            V(rw);  //允许写进程写

        V (mutex);  //释放互斥变量count
    }
}

2.15 经典进程同步问题3：哲学家进餐问题

问题描述
一张圆桌上坐着5名哲学家，每两个哲学家之间的桌上摆一根筷子，桌子的中间是一碗米饭，如图2-10所示。哲学家们倾注毕生精力用于思考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿的时候，才试图拿起左、 右两根筷子（一根一根地拿起）。如果筷子已在他人手上，则需等待。饥饿的哲学家只有同时拿到了两根筷子才可以开始进餐，当进餐完毕后，放下筷子继续思考。

问题分析
1) 关系分析。5名哲学家与左右邻居对其中间筷子的访问是互斥关系。


2) 整理思路。显然这里有五个进程。本题的关键是如何让一个哲学家拿到左右两个筷子而不造成死锁或者饥饿现象。那么解决方法有两个，一个是让他们同时拿两个筷子；二是对每个哲学家的动作制定规则，避免饥饿或者死锁现象的发生。








图2-10 5名哲学家进餐



3) 信号量设置。定义互斥信号量数组Ch0PstiCk[5] = {l, 1, 1, 1, 1}用于对5个筷子的互斥访问。


对哲学家按顺序从0～4编号，哲学家i左边的筷子的编号为i，哲学家右边的筷子的编号为(i+l)%5。

semaphore chopstick[5] = {1,1,1,1,1}; //定义信号量数组chopstick[5],并初始化
Pi(){  //i号哲学家的进程
    do{
        P (chopstick[i] ) ; //取左边筷子
        P (chopstick[(i+1) %5] ) ；  //取右边篌子
        eat;  //进餐
        V(chopstick[i]) ; //放回左边筷子
        V(chopstick[(i+l)%5]);  //放回右边筷子
        think;  //思考
    } while (1);
}
该算法存在以下问题：当五个哲学家都想要进餐，分别拿起他们左边筷子的时候（都恰好执行完wait(chopstick[i]);)筷子已经被拿光了，等到他们再想拿右边的筷子的时候（执行 wait(chopstick[(i+l)%5]);)就全被阻塞了，这就出现了死锁。

为了防止死锁的发生，可以对哲学家进程施加一些限制条件，比如至多允许四个哲学家同时进餐;仅当一个哲学家左右两边的筷子都可用时才允许他抓起筷子;对哲学家顺序编号，要求奇数号哲学家先抓左边的筷子，然后再转他右边的筷子，而偶数号哲学家刚好相反。正解制定规则如下：假设釆用第二种方法，当一个哲学家左右两边的筷子都可用时，才允许他抓起筷子。

semaphore chopstick[5] = {1,1,1,1,1}; //初始化信号量
semaphore mutex=l;  //设置取筷子的信号量
Pi(){ //i号哲学家的进程
    do{
        P (mutex) ; //在取筷子前获得互斥量
        P (chopstick [i]) ; //取左边筷子
        P (chopstick[ (i+1) %5]) ;  //取右边筷子
        V (mutex) ; //释放取筷子的信号量
        eat;  //进餐
        V(chopstick[i] ) ;  //放回左边筷子
        V(chopstick[ (i+l)%5]) ;  //放回右边筷子
        think;  // 思考
    }while(1);
}
此外还可以釆用AND型信号量机制来解决哲学家进餐问题，有兴趣的读者可以查阅相关资料，自行思考。





2.16 经典进程同步问题4：吸烟者问题

向题描述
假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它，但是要卷起并抽掉一支烟，抽烟者需要有三种材料：烟草、纸和胶水。三个抽烟者中，第一个拥有烟草、第二个拥有纸，第三个拥有胶水。供应者进程无限地提供三种材料， 供应者每次将两种材料放到桌子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉它，并给供应者一个信号告诉完成了，供应者就会放另外两种材料在桌上，这种过程一直重复（让三个抽烟者轮流地抽烟)。

问题分析
1) 关系分析。供应者与三个抽烟者分别是同步关系。由于供应者无法同时满足两个或 以上的抽烟者，三个抽烟者对抽烟这个动作互斥（或由三个抽烟者轮流抽烟得知）


2) 整理思路。显然这里有四个进程。供应者作为生产者向三个抽烟者提供材料。


3) 信号量设置。信号量offer1、offer2、offer3分别表示烟草和纸组合的资源、烟草和 胶水组合的资源、纸和胶水组合的资源。信号量finish用于互斥进行抽烟动作。


代码如下：

int random; //存储随机数
semaphore offer1=0; //定义信号量对应烟草和纸组合的资源
semaphore offer2=0; //定义信号量对应烟草和胶水组合的资源
semaphore offer3=0; //定义信号量对应纸和胶水组合的资源
semaphore finish=0; //定义信号量表示抽烟是否完成

//供应者
while(1){
    random = 任意一个整数随机数;
    random=random% 3;
    if(random==0)
        V(offerl) ; //提供烟草和纸
    else if(random==l) 
        V(offer2);  //提供烟草和胶水
    else
        V(offer3)  //提供纸和胶水
    // 任意两种材料放在桌子上;
    P(finish);
}

//拥有烟草者
while(1){
    P (offer3);
    // 拿纸和胶水，卷成烟，抽掉;
    V(finish);
}

//拥有纸者
while(1){
    P(offer2);
    // 烟草和胶水,卷成烟，抽掉；
    V(finish);
}

//拥有胶水者
while(1){
    P(offer1);
    // 拿烟草和纸，卷成烟，抽掉;
    v(finish);
}

操作系统的进程同步
进程同步
两种制约关系
临界资源
临界区
同步机制的四个准则
信号量机制
整型信号量
记录型信号量
记录型信号量的P、V操作
说明
AND型信号量
信号量集
信号量机制的应用
实现进程互斥
实现前趋

进程同步
两种制约关系
间接相互制约关系：同处于一个系统中的进程，必然共享着某种系统资源。所谓间接相互制约即源于这种资源共享。例如，有两个进程A和B，如果在A进程提出打印请求时，系统已将唯一的一台打印机分配给了进程B，则此时进程A只能阻塞；一旦进程B将打印机释放，才能使A进程由阻塞改为就绪状态。（进程互斥）

（就是两个进程共同竞争一个资源，当A释放了共享资源后B才能继续进行）



直接相互制约关系：这种制约源于进程间的合作。例如C进程因得不到A进程的数据而阻塞。（进程同步）

（两者是某种顺序关系，A做完B才能继续）


临界资源
临界资源：一次仅允许一个进程使用的资源。

许多物理设备，如输入机、打印机、磁带机等都具有这种性质。

软件资源，如公用变量、数据、表格、队列等也都具有这一特点。

诸进程之间应通过互斥方式，实现对临界资源的共享。
临界区
不论是硬件临界资源，还是软件临界资源，多个进程必须互斥地对它进行访问。

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

每个进程进入临界区之前，应先对欲访问的临界资源进行检查，看它是否正被访问。如果此刻该临界资源未被访问，进程便可进入临界区对该资源进行访问，并设置它正被访问的标志；如果此刻该临界资源正被某进程访问，则本进程不能进入临界区。


同步机制的四个准则

空闲让进：当无进程处于临界区时，应允许一个请求进入临界区的进程进入临界区；
忙则等待：当已有进程进入临界区时，其他试图进入临界区的进程必须等待；
有限等待：对要求访问临界资源的进程，应保证在有限时间内能进入自己的临界区，以免陷入“死等”状态；
让权等待：当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入“忙等”。

信号量机制
整型信号量
思想：定义一个整型量S，除初始化外，仅能通过两个标准的原子操作wait(S)和signal(S)来访问。
wait(S): {
				while S≤0;    /*do no-op*/
                 S--;
               }
signal(S): {
                    S++;
                  }



缺点：当s<=0时，会进入死循环，一直占用CPU，浪费资源。因此，该机制并未遵循“让权等待”的准则，而是使进程处于“忙等”的状态。
记录型信号量
思想：用整型变量value代表资源的数目。用进程链表L来链接等待访问临界资源的进程。
记录型信号量的定义：
  typedef struct {
                     int value;
                      struct process_control_block *list;
                           }semphore;

临界资源阻塞队列：


记录型信号量的P、V操作
wait(semaphare *S)
  {
    S->value--;
    if (S->value<0)  block(S->list);
   }
signal(semphore *S)
 {
     S->value++;
     if (S->value≤0) then wakeup(S->list);
  }



说明
S->value的初值表示系统中某类资源的数目，因而又称为资源信号量，对它的每次wait操作，意味着进程请求一个单位的该类资源，使系统中可供分配的资源数减少一个，因此S->value–；

每次执行完wait操作后，若S->value<0时，说明该类资源已分配完毕，因此进程应调用block原语，进行自我阻塞，放弃处理机，并插入到信号量链表S->list中。此时S->value的绝对值表示在该信号量链表中已阻塞进程的数目。

每次执行signal操作表示资源数目加1，若加1后仍有S->value≤0时，则表示在该信号量链表中，仍有等待该资源的进程被阻塞，故还应调用wakeup原语，将S->list链表中的第一个等待进程唤醒。

若S->value的初值为1，表示只允许一个进程访问临界资源，此时的信号量转化为互斥信号量。
AND型信号量
思想：将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，待进程使用完成后再一起释放。只要尚有一个资源未能分配给进程，其他所有可能为之分配的资源，也不分配给它。亦即，对若干个临界资源的分配，采取原子操作方式：要么全部分配给进程，要么一个也不分配。
Swait(S1,S2,…,Sn)
{   while (TRUE)  
    { 
    if (S1≥1&&… &&Sn≥1){
     for (i=1;i<=n;i++)
          Si--;
     break;
      }
else {
     place the process in the waiting queue associated with the first Si found with Si<1, and set the program count of this process to the beginning of Swait operation
     将进程放入第一个Si<ti的等待队列中,并且将程序指针指向该进程的Swait操作开始处；
       }
   }
}

Ssginal(S1,S2,…,Sn)
  while (TRUE){
 for(i:=1;i<=n;i++){ 
    Si++;
    remove all the process waiting in the queue associated with Si into the ready queue
    将与Si 相关的等待队列中的进程移到就绪队列
   }
  }
}



信号量集
思想：若进程一次需要申请多类临界资源，则在进行临界资源分配时，先测试各类临界资源是否大于其下限值。若低于下限值，则不予分配。

以下的程序中，S为信号量，d为需求值，t为下限值。
Swait(S1,t1,d1,…,Sn,tn,dn)
   while (TRUE){
 if (S1≥t1 && … && Sn≥tn )
        for (i=1;i<=n;i++)   Si:=Si-di;
        break;
}         
else { 
        Place the executing process in the waiting queue of the first Si with Si<ti and set its program counter to the beginning of the Swait Operation.
        将正在执行的进程移入第一个Si<ti的等待队列中，并将程序指针指向该进程中Swait操作开始处
   }
 }
}

Ssignal(Si,di,…,Sn,dn)
{ while (TRUE)
    {   
       for (i=1;i<=n;i++) {
        Si:=Si+di;
        Remove all the process waiting in the queue associated with Si into the ready queue
        将与Si相关的等待队列中的所有进程移到就绪队列
     }
   }
}


信号量机制的应用
实现进程互斥
为使得多个进程能互斥地访问某临界资源，只需为该资源设置一互斥信号量mutex，并设其初始值为1，然后将各进程访问该资源的临界区CS置于wait(mutex)和signal(mutex)操作之间即可。


实现前趋


技巧：后进程实现P（wait）操作，前进程实现V（signal）操作。
大家觉得有帮助的请点个赞啊👍

一、临界区

互相协作的进程之间有共享的数据，于是这里就有一个并发情况下，如何确保有序操作这些数据、维护一致性的问题，即进程同步。为了解决合作进程之间的竞争条件，引入临界区问题模型。 临界区是包含访问共享数据指令的相关代码段，也是多个进程都包含的代码段，在这段代码中可能会进行更新数据表、交换变量等操作。从数据一致性的角度来说，当一个进程进入临界区后，其他进程就不允许进入临界区，也就是不能有多个进程同时处于临界区。

临界区问题（critical-section problem）是设计一个以便进程协作的协议。每个进程必须请求允许进入其临界区。实现请求的代码段称为进入区（entry section），临界区之后可有退出区（exit section），其他代码段成为剩余区（remainder section）。

临界区问题的解答必须满足三项要求：
（1）互斥（mutual exclusion）： 如果进程Pi在其临界区内执行，那么其他进程都不能在其临界区内执行；
（2）渐进（progress）： 如果没有进程在其临界区内执行且有进程需进入临界区，那么只有那么不在剩余区内执行的进程可参加选择，以确定谁能下一个进入临界区，且这种选择不能无限推迟；
（3）有限等待（bounded waiting）： 从一个进程做出进入临界区的请求，直到该请求允许为止，其他进程允许进入其临界区内的次数有上限。

二、信号量

信号量S是个整数变量，除了初始化外，它只能通过两个标准原子操作：wait()和signal()来访问。即P和V。

wait()就是等待资源的过程，定义可表示为：
wait(S)
{
  while(S<=0)
    ;//busy wait
  S--;
}

signal()就是释放资源的过程，定义可表示为：
signal(S)
{
  S++;
}

在wait()和signal()操作中，对信号量整型值的修改必须不可分地执行。即当一个进程修改信号量值时，不能有其他进程同时修改同一信号量的值。另外，对于wait(S)，对于S的整数值测试(S≤0)和对其可能的修改(S–)，也必须不被中断地执行。
信号量的基本用法如下：
do
{
  wait(mutex);
    //critical section
  signal(mutex);
    //remainder section
}while(TRUE);

可以看到互斥锁其实就是信号量的一种特殊形式（当信号量为二进制信号量时），而从互斥锁中可以知道其具有忙等待的缺点，可以通过阻塞自己来解决这一缺点。

将信号量定义为结构体，如下：


typedef struct
{
    int value;                  //记录了这个信号量的值   
    struct process *list;       //储存正在等待这个信号量的进程（PCB链表指针）
}semaphore;
wait实现：
wait(semaphore *S)//消耗资源
        {
  S->value--;
  if(S->value<0)                  //没有资源
  {
  add this process to S->list;      //进入等待队列  
  block();                          //堵塞
  }
}

signal实现：
signal(semaphore *S)//释放资源
{
    S->value++;
    if(S->value<=0)
    {                  //上面++后，S仍然还<=0，说明资源供不应求，等待者还有很多，于是唤醒等待队列中的一个
        remove a process P from S->list;
        wakeup(P);                        //唤醒进程p  
    }
}

在具有忙等的信号量经典定义下，信号量的值不会为负数，但是本实现可能造成信号量为负值。如果信号量为负值，那么其绝对值就是等待该信号量的进程的个数。信号量的关键之处是它们原子的执行。必须确保没有两个进程能同时对一个信号量进行操作，在单处理器情况下，可以在执行wait()和signal()的时候简单的关闭中断，保证只有当前进程进行。

进程同步问题（主要是PV问题）
先了解基本概念
​	因为在多道环境下，进程之间是并发执行的，而程序之间为了抢夺各种资源，相互制约，如果不对这种制约加以协调，操作系统就很容易进入死锁状态，影响进程们的运行。所以我们需要引入进程同步的概念，来协调这种进程之间的制约关系。


临界资源
虽然系统中的资源可以给所有的进程共享，但是对于某些资源而言，同时只能提供给一个进程，这样的资源叫做临界资源，当临界资源已经被占用的时候，我们该如何协调想要访问这个资源的进程之间的关系呢？为此，我们将访问临界资源的过程分为了四个步骤：

进入区：检查是否能进入临界区，能进入的情况，对临界区上锁
临界区：访问临界资源的那一段代码
退出区：解锁
剩余区：代码的其余部分

do {
	entry section;			//进入区
	critical section;		//临界区
	exit section;			//退出区
	remainder section;		//剩余区
}



同步
​	=，=感觉自己也没有很懂，为了协调两个进程之间的工作次序而等待，传递信息所产生的制约关系。
​	大概就是指的，A向缓冲区写数据，缓冲区中写满数据只后，B才能进去读操作。AB之间形成了同步关系。


互斥
​	也叫做间接制约关系，当A访问临界资源时，B必须被阻塞等待，当A释放临界资源了，系统才将B唤醒。AB之间形成互斥关系。


同步机制的四个准则：

空闲让进：屁话
忙则等待：屁话
有限等待：要防止饥饿现象
让权等待：进程不能进入临界区的时候要释放CPU


实现临界区互斥的基本方法


软件方法


单标志法：设置一个公共整型变量turn。当turn=0的时候允许进程P0访问临界资源turn = 1时允许进程P1访问临界资源。但是这样的方法是违反空闲让进原则的。当临界资源空闲时，且turn = 1，这时候P0想要访问临界资源也会被拒绝。
//P0进程
while(turn != 0);
critical section;
turn = 1;
remainder section;

//P1进程
while(turn != 1);
critical section;
turn = 0;
remainder section;



双标志先检查法：为每个进程设置一个flag[i]数据元素，为true表示正在访问临界资源。有点是可以直接进入空闲的临界区，而不用像单标志法一样交替进入。但问题是按照一定的访问顺序，会导致两个进程都进入临界区。违反“忙则等待”。原因在于，检查标志和修改标志的操作不能一气呵成
//Pi进程
while(flag[j]);
flag[i]=true;
critical section;
flag[i]=false;
remainder section;
//Pj进程
while(flag[i]);
flag[j]=true;
critical section;
flag[j]=false;
remainder section;



双标志后检查法：与双标志先检查法相反， 先进行标志修改，再进行标志检查，结果是有可能导致两个进程都无法进入临界区，造成饥饿现象
//Pi进程
flag[i]=true;
while(flag[j]);
critical section;
flag[i]=false;
remainder section;
//Pj进程
flag[j]=true;
while(flag[i]);
critical section;
flag[j]=false;
remainder section



Peterson’s Algorithm（皮特森算法）：在双标志后检查法的基础上加一个turn标志，来表示谦让避免出现饥饿现象
//Pi进程
flag[i]=true; turn = j;
while(flag[j] && turn == j);
critical section;
flag[i] = false;
remainder section;
//Pj进程
flag[j] = true; turn = i;
while(flag[i] && turn == i);
critical section;
flag[j]=false;
remainder section;





硬件方法


中断屏蔽方法：通过关中断来保证互斥的实现。但是这样的方法限制了处理机交替处理程序的能力，降低了系统效率，同时，对于内核而言，将关中断的权力交给用户也是很不明智的。若进程关中断后不再开中断，就会引起系统的终止。
···
关中断
临界区
开中断
···



硬件指令方法：①用的是TestAndSet指令（也叫TestAndSetLock，TSL指令）这条指令是一个原子操作。它的功能是，读出标志位后，将其置为true；②用的swap指令
//TSL指令
boolean TestAndSet(boolean *lock){
	boolean old;
	old = *lock;
	*lock = true;
	return old;
}
//互斥实现
while TestAndSet(&lock);
critical section;
lock=false;
remainder section;

//swap指令
Swap(boolean *a, boolean *b){
	boolean temp;
	temp = *a;
	*a = *b;
	*b = temp;
}
//swap互斥实现 =，=没看懂，感觉怪怪的
key = true;
while(key!=flase) swap(key, lock);
critical section;
lock = false;
remainder section

​	PS：软硬件的实现代码，并不需要掌握，在实际的考试和应用中不会出现。
硬件实现方法优缺点：
​		优点：适用于任意数目的进程，适用于单处理机和多处理机，支持进程内有多个临界区的情况；简单，可以保证正确性。
​		缺点：不满足让权等待的原则，从等待的进程中随机选择一个进程进入临界区，可能有的进程一直不被选中，导致饥饿现象

信号量（本章的超级重难点，也是写这篇博客的意义所在）
​	信号量机制采用两个标准的==原语（P[wait()]V[signal()]操作）==来解决互斥同步的问题。对于PV操作的描述，在不同类型的型号量中实现的方法有所差异。

整型型号量

//P操作
wait(S){
	while(S<=0);
	S = S - 1;
}
//V操作
signal(S){
	S = S + 1;
}


记录型信号量

typedef struct{
	int value;
	struct process *L;//进程的阻塞队列
} semaphore;
//对应P操作
void wait(semaphore S){
	S.value --;
	if(S.value<0){
		add this process to S.L;
		block(S.L);//将进程挂入阻塞队列
	}
}
//V操作
void signal(semaphore S) {
	S.value ++;
	if(S.value<=0){
		remove a process P from S.L;
		wakeup(P);//从阻塞队列中唤醒一个进程
	}
}

block的使用实现了让权等待的功能


利用信号量实现同步（实现一定的顺序关系）

semaphoe S = 0;
P1(){
	....
	x;
	V(S);
}
P2(){
	...
	P(S);
	y;
	...
}
先执行P1才能执行P2.因此是同步关系


利用信号量实现互斥

semaphore S = 1;
P1(){
	...
	P(S);
	进程P1的临界区
	V(S);
	...
}
P2(){
	...
	P(S);
	进程P2的临界区
	V(S);
	...
}
两个进程抢夺一个临界资源，没有特定的先后顺序，是互斥关系



利用信号量实现前驱关系（详见P86）：①在一个节点运行完成后，对该节点后继的所有节点都进行一次V操作，②在一个节点运行前，对它前驱的节点进行一次P操作


分析进程同步和互斥问题的方法步骤

关系分析：①找出进程数目；②分析同步互斥前驱关系；
整理思路：找出问题的关键点，根据以前做过题目的经验，根据进程的操作流程（PS：你妈的，这也太玄学了）
设置信号量，确定初值




管程（互斥访问的特性由编译器来实现）

管程的定义：由代表共享资源的数据结构和能为并发进程所执行的一组操作所组成的资源管理程序。这组操作能同步进程和改变管程中的数据。每次只允许一个进程进入管程。
管程的组成：

名称
内部共享结构数据的说明
对数据结构的一组操作
对共享结构初始化的语句


条件变量：条件变量和信号量的区别在于，条件变量只实现排队等待功能，剩余资源数量由管程内部的共享数据结构记录。


经典同步问题


生产者-消费者问题

问题描述：
​		一组生产者进程和一组消费者进程共享一个初始为空、大小为n的缓冲区，只有缓冲区没满的时候，生产者才能写入数据，只有缓冲区不空的时候消费者才能取出数据，缓冲区是临界资源，同时只允许一个生产者或一个消费者放入消息。

问题分析：
​		互斥关系：任意两个进程之间都是互斥关系
​		同步关系：生产者和消费者之间是同步关系，先生产才能进行消费
​		信号量的设置：设置一个mutex来作为互斥信号量，初始值为1，设置一个full来表示缓冲区中消息的数量，初始值为0，设置一个empty来表示缓冲区中空位的数量，初始值为n

进程描述：
semaphore mutex = 1;
semaphore full = 0;
semaphore empty = n;
//生产者
producer() {
	while(1){
		produce an item in nextp;
		P(empty);//同步关系，分析进程执行顺序，想要什么P一下
		P(mutex);//最靠近临界资源；直接夹住
		访问缓冲区;
		V(mutex);
		V(full);//提供什么V一下
	}
}
//消费者
consumer() {
	while(1) {
		P(full);
		P(mutex);
		取出数据；
		V(mutex);
		V(empty);
	}
}






生产者-消费者问题（复杂情况）

问题描述：
​		桌上有个盘子，每次只能放一个水果。爸爸向盘子里放苹果，妈妈放橘子，儿子等着吃橘子，女儿等着吃苹果。

问题分析：
​		互斥关系：爸爸妈妈对盘子互斥
​		同步关系：爸爸和女儿同步，妈妈和儿子同步
​		信号量设置：设置一个互斥信号量plate = 1；apple = 0；orange = 0;

进程描述：
semaphore mutex = 1;
semaphore apple = 0;
semaphore orange = 0;
//本题中缓冲区大小为1，不需要用mutex夹紧，不设置互斥信号量
daa() {
	while(1) {
		P(plate);
		放苹果；
		//V(mutex);
		V(apple);
	}
}
mom() {
	while(1) {
		P(plate);
		放橘子；
		//V(mutex);
		V(orange);
	}
}
son() {
	while(1) {
		P(orange)
		拿橘子
		V(plate)
	}
}
daughter() {
	while(1) {
		P(apple)
		拿苹果
		V(plate)
	}
}






读者-写者问题

问题描述：
​		读者写者两组并发进程，共享一个文件，当两个以丄的读进程同时访问共享数据时不会发生副作用，但某个写进程和其他进程（包括读和写）同时访问共享数据时则出错。因此要求：①多个读者可以同时对文件进行读操作；②只允许一个写进程往文件中写信息；③任一写着在完成写操作前不允许其他读者写者工作；④写着执行操作前，应该让所有的读者和写者全部退出。（何解？抢夺？）

问题分析：
​		互斥关系：读者和写者互斥，写者和写者互斥
​		同步关系：读者和写者同步
​		信号量设置：mutex = 1; count = 0;

进程描述：
int count = 0;
semaphore mutex = 1;
//写者
writer() {
	while(1) {
		P(mutex);
		写；
		V(mutex);
	}
}
//读者
reader() {
	while(1) {
		//下面的操作无法一气呵成，所以需要增加一个互斥信号量锁住，让其成为一个原子操作
		P(mutex_r);
		if(count == 0) P(mutex);
		count ++;
		V(mutex_r);
		读；
		P(mutex_r);
		count --;
		if(count == 0) V(mutex);
		V(mutex_r);
	}
}






读者写者问题改进

问题描述：
​		在上面的处理方式会导致读者不停进入，写者被“饥饿”的现象。所以我们规定，当有写进程请求访问时，应该禁止后续读进程的请求，等到访问共享资源的读进程执行完毕时，立即让写进程执行。
int count = 0;
semaphore mutex = 1;
semaphore mutex_r = 1;
semaphore mutex_w = 1;
//写者
writer() {
	while(1) {
		P(mutex_w);
		P(mutex);
		写；
		V(mutex);
		V(mutex_w);
	}
}
//读者
reader() {
	while(1) {
		P(mutex_w);
		P(mutex_r);
		if(count == 0) P(mutex);
		count++;
		V(mutex_r);
		V(mutex_w);
		读；
		P(mutex_r);
		count--;
		if(count == 0) V(mutex);
		V(mutex_r);
	}
}








哲学家进餐问题

问题描述：
​		五个哲学家，两个之间一根筷子，两根筷子之间一碗饭，哲学家饥饿时，试图拿起左右两根筷子，筷子在别人手上就等待，只有同时拿到两根筷子才能进餐。

问题分析：
​		互斥关系：五个进程对左右邻居之间的筷子互斥。
​		信号量设置：设置互斥信号量组chopstick[5]={1，1，1，1，1}

进程实现：
semaphore mutex = 1;
semaphore chopsticks[5] = {1, 1, 1, 1, 1};
P1() {
	do() {
		P(mutex);//让拿左右筷子的操作一气呵成~不然会死锁的呢
		P(chopsticks[i]);
		P(chopsticks[(i+1)%5]);
		V(mutex);
		恰饭
		P(mutex);
		V(chopsticks[i]);
		V(chopsticks[(i+1)%5]);
		V(mutex);
	}while(1);
}






吸烟者问题

问题描述：
​		三个抽烟者进程，一个供应者进程。一共有三种材料（ABC），三个抽烟者进程分别持有其中一种。供应者进程每次会供应两种材料，拥有剩下那种材料的抽烟者取走它。

问题分析：
​		同步关系：供应者与三个抽烟者是同步关系
​		互斥关系：三个抽烟者对抽烟这个行为互斥
​		信号量设置：offer1 = 0,  offer2 = 0, offer3 = 0; finish = 0;

进程实现：
int num = 0;
semaphore offer1 = 0;
semaphore offer2 = 0;
semaphore offer3 = 0;
semaphore finish = 0;
//供应者
process P1() {
	while(1) {
		num = num%3;
		if(num == 0) {
			V(offer1);
		}
		else if(num == 1) {
			V(offer2);
		}
		else V(offer3);
		放材料
		P(finish);
	}
}
//抽烟者
process P2() {
	while(1) {
		P(offer1);
		抽烟
		V(finish);
	}
}
process P3() {
	while(1) {
		P(offer2);
		抽烟
		V(finish);
	}
}
process P4() {
	while(1) {
		P(offer3);
		抽烟
		V(finish);
	}
}






关于同步问题的习题=。=

【2019统考】三个进程P1，P2，P3互斥使用一个包含N个单元的缓冲区。P1每次使用produce()生成一个正整数并用put()送入一个缓冲区某一空单元；P2每次使用getodd()从缓冲区中取出一个奇数并用countodd()统计奇数个数；P3用geteven()取出偶数并用counteven()统计偶数个数。

问题分析：
​		互斥关系：P1与P2、P3对缓冲区互斥
​		同步关系：P1与P2、P3分别同步
​		信号量设置：mutex = 1; empty = N; odd = 0; even =0;

进程实现：
semaphore mutex = 1;
semaphore odd = 0;
semaphore even = 0;
semaphore empty = N;
P1() {
	while(1) {
		x = produce();
		x = x % 2;
		P(empty)
		P(mutex);
		put()
		if(x == 0 ) {
			V(even);
		}
		else {
			V(odd);
		}
		V(mutex)
	}
}

P2() {
	while(1) {
		P(odd);
		P(mutex);
		getodd();
		V(mutex);
		V(empty);
		countodd();
	}
}
P3() {
	while(1) {
		P(even);
		P(mutex);
		getodd();
		V(mutex);
		V(empty);
		counteven();
	}
}


【2013年统考】某博物馆最多可容纳500人同时参观，有一个出入口，该出入口一次仅允许一人通过，参观者的活动描述如下：
cobegin
	参观者进程i;
	{
		...
		进门
		...
		参观
		...
		出门
		...
	}
coend;

请添加必要的信号量和PV操作，来实现上述过程中的互斥与同步要求写出完整的过程，并且说明信号量的含义并赋初值。

问题分析：

互斥关系：参观者对出入口和博物馆互斥

信号量设置：door = 1；num = 500;

进程实现：
semaphore door = 1;
semaphore num = 500;
Pi() {
	P(num);
	P(door);
	进门;
	V(door);
	参观;
	P(door);
	出门;
	V(door);
	V(num);
}


【2011统考真题】某银行提供一个服务窗口和10个供顾客等待的座位。顾客到达银行时，若有空座位，则取号机领取一个号。取号机每次仅允许一个顾客使用。当营业员空闲时，叫号选取一个顾客，并为其服务。顾客和营业员的活动描述如下：
cobegin
{
	process 顾客 i
	{
		从取号机获取一个号码；
		等待叫号；
		获取服务；
	}
	process 营业员
	{
		while(1) {
			叫号；
			为客户服务;
		}
	}
}

请添加必要的信号量和PV操作，实现上述过程中的互斥与同步。

问题分析：
​		同步关系：营业员和顾客同步
​		互斥关系：客户之间对服务窗口互斥
​		信号量设置：mutex = 1; full = 0; empty = 10;

进程实现：
semaphore mutex = 1;
semaphore full = 0;
semaphore empty = 10;
cobegin
{
	process 顾客 i
	{
		P(empty);
		P(mutex);
		从取号机获取一个号码；
		V(mutex);
		V(full);
		P(mutex2);
		等待叫号；
		获取服务；
	}
	process 营业员
	{
		while(1) {
			P(full);
			V(empty);
			V(mutex2);
			叫号；
			为客户服务;
		}
	}
}



【2014年统考真题】系统中有多个生产者进程和多个消费者进程，共享一个能存放1000个产品的缓冲区（初始为空），缓冲区没满时，生产者进程可以放入其生产的一件产品，否则等待。缓冲区未空时，消费者可以取走一件产品，否则等待。要求一个消费者进程从缓冲区中连续取走10件产品后，其他消费者进程才可以取产品。

问题分析：
​		互斥关系：消费者和生产者互斥，消费者和消费者互斥
​		同步关系：生产者和消费者同步
​		信号量设置：empty = 1000; full = 0; mutex =1; ~~count = 10;~~mutex2 = 1;

进程实现：
semaphore empty = 1000;
semaphore full = 0;
semaphore mutex = 1;
semaphore mutex2 = 1;
producer() {
	while(1) {
		生产一个产品;
		P(empty);
		P(mutex);
		放入缓冲区
		V(mutex);
		V(full);
	}
}

consumer() {
	while(1) {
		P(mutex2);
		for(int i=0; i<10; i++) {
			P(full);
			P(mutex);
			取走一个产品;
			V(mutex);
			V(empty);
		}
		V(mutex2);
	}
}


【2015年统考真题】有A、B两人通过信箱进行辩论，每个人都从自己的信箱中取得对方的问题。将答案的向对方提出的新问题组成一个邮件放入对方的邮箱中。假设A的信箱中最多放M个邮件，B的信箱中最多放N个邮件。初始时，A的信箱中有x个邮件。B的信箱中有y个邮件。
cobegin
A() {
	while(1) {
		从A的信箱中取出一个邮件；
		回答问题并提出一个新问题；
		将新邮件放入B的信箱中；
	}
}
B() {
	while(1) {
		从B的信箱中取出一个邮件；
		回答问题并提出一个新问题；
		将新邮件放入A的信箱中；
	}
}
coend


问题分析：
​		互斥关系：AB对两个信箱互斥
​		同步关系：AB互相同步
​		信号量设置：mutexA = 1; mutexB = 1; emptyA = M-x;emptyB = N-y;fullA = x;fullB = y;

进程实现：
semaphore mutexA = 1;
semaphore mutexB = 1;
semaphore emptyA = M-x;
semaphore emptyB = N-y;
semaphore fullA = x;
semaphore fullB = y;
A() {
	while(1) {
		P(fullA);
		P(mutexA);
		从A的信箱中取出一个邮件；
		V(mutexA);
		V(emptyA);
		回答问题并提出一个新问题；
		P(emptyB);
		P(mutexB);
		将新邮件放入B的信箱中；
		V(mutexB);
		V(fullB);
	}
}
B() {
	while(1) {
		P(fullB);
		P(mutexB);
		从A的信箱中取出一个邮件；
		V(mutexB);
		V(emptyB);
		回答问题并提出一个新问题；
		P(emptyA);
		P(mutexA);
		将新邮件放入B的信箱中；
		V(mutexA);
		V(fullA);
	}
}


【2017统考真题】某进程中有三个并发执行的线程thread1, thread2, thread3 其伪代码如下：
//复数的结构定义类型
typedef struct
{
	float a;
	float b;
} cnum;
cnum x, y, z;//全局变量

//计算两个复数之和
cnum add(cnum p, cnum q)
{
	cnum s;
	s a = p.a + q.a;
	s b = p.b + q.b;
	return s;
}

//三个线程
thread1
{
	cnum w;
	w = add(x, y);
	...
}
thread2
{
	cnum w;
	w = add(y, z);
	...
}
thread3
{
	cnum w;
	w.a = 1;
	w.b = 1;
	z = add(z, w);
	y = add(y, w);
	...
}


问题分析：
​		互斥关系：123对y互斥，23对z互斥应该注意到12只是读进程，3才是写进程。因此两个读不会互斥。读和写才会互斥。所以1与3关于y互斥，2与3关于yz互斥
​		信号量设置：mutexy1 = 1; mutexy2 = 1;mutexz=1;

进程实现：
thread1
{
	cnum w;
	P(mutexy1);
	w = add(x, y);
	V(mutexy1);
	...
}
thread2
{
	cnum w;
	P(mutexy2);
	P(mutexz);
	w = add(y, z);
	V(mutexz);
	V(mutexy2);
	...
}
thread3
{
	cnum w;
	w.a = 1;
	w.b = 1;
	P(mutexz);
	z = add(z, w);
	V(mutexz);	
	P(mutexy1);	
	P(mutexy2);
	y = add(y, w);
	V(mutexy1);
	V(mutexy2);
	...
}


【2019年统考真题】有n(n>=3)个哲学家围坐在一张圆桌边上，每个哲学家交替地就餐和思考，在圆桌中心，有m个碗，每两名哲学家之间有1根筷子，每名哲学家取得一个碗和两侧的筷子后才能就餐。

问题分析：
​		互斥关系：哲学家对碗互斥，相邻哲学家对筷子互斥；
​		信号量设置：mutex = m; chopsticks[n] = {1};

进程实现：
semaphore mutex = m;
semaphore chopsticks[n];
for(int i = 0;i<n;i++) {
	chopsticks[i] = 1;
}
mutex = min(mutex, n-1);
Pi() {
	while(1){
		P(mutex);
		P(chopsticks[i]);
		P(chopsticks[(i+1)%n]);
		恰饭；
		V(chopsticks[i]);
		V(chopsticks[(i+1)%n]);
		V(mutex);
	}
}






总结：
​		关于问题分析的环节，感觉出了点问题。不应该围绕进程展开进行分析，而是对资源展开进行分析进程之间的关系，而不是简单的判断进程之间的关系（感觉这样于解题并无太大的作用。）另外没有仔细分析自己的解题思路=。=这就很烦，导致解题的过程很随机，很不规范。加油！

先找临界资源
从临界资源入手，分析谁互斥，谁同步
确定临界资源的数量，特别的，对于缓冲区经常会采用empty和full两对变量来进行操作。一个锁住下限，一个锁住上限

​		=。=格式问题，第一次写这么长的感觉好乱写的。而且写的很臃肿。没有想好自己的大纲逻辑就开始动笔了，想到哪写到哪。加油szx
​		写给自己纪念的一篇小玩意儿。