1. 进程互斥

此处输入图片的描述
由于进程具有独立性和异步性等并发特征，计算机的资源有限，导致了进程之间的资源竞争和共享，也导致了对进程执行过程的制约。

1.1 临界资源和临界区（临界部分）

临界资源：一次只能供一个进程访问的资源。
临界区：把不允许多个并发进程交叉执行的一段程序称为临界区（critical region）或临界部分（critical section）。

临界区是由属于不同并发进程的程序段共享公用数据或公用数据变量而引起的，临界区不可能用增加硬件的方法来解决。因此，临界区也可以被称为访问公用数据的那段程序。

当一个进程使用该临界资源时，其他需要访问该资源的进程必须阻塞，直到占用者释放该资源。

1.2 间接制约

把这种由于共享某一公有资源而引起的在临界区内不允许并发进程交叉执行的现象，称为由共享公有资源而造成的对并发进程执行速度的间接制约。这里的“间接”二字主要是指各并发进程的速度受公有资源的制约，而非进程之间的直接制约。

1.3 互斥

互斥：一组并发进程中的一个或多个程序段，因共享某一公有资源而导致它们必须以一个不允许交叉执行的单位执行。也就是说，不允许两个以上的共享该资源的并发进程同时进入临界区。

一般情况下，作为程序段的一个过程不允许多个进程同时访问它。但如果该过程是纯过程，则各并发进程可以同时访问它。纯过程是指在执行过程中不改变过程自身代码的一类过程。

一组并发进程互斥执行时必须满足如下准则：

平等竞争：不能假设各并发进程的相对执行速度。即各并发进程享有平等地、独立地竞争共有资源的权利，且在不采取任何措施的条件下，在临界区内任意指令结束时，其他并发进程可以进入临界区。
不可独占：并发进程中的某个进程不在临界区时，它不能阻止其他进程进入临界区。
互斥使用：并发进程中的若干个进程申请进入临界区时，只能允许一个进程进入。
有限等待：并发进程中的某个进程从申请进入临界区时开始，应在有限时间内得以进入临界区。

1.4 进程互斥软件的实现方法

此处输入图片的描述

2. 信号量和P、V原语

2.1 信号量

此处输入图片的描述

2.1.1 整型信号量

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

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

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

P原语操作：
sem减1；
若sem减1后仍大于或等于0，则P原语返回，该进程继续执行；
若sem减1后小于0，则该进程被阻塞后进入与该信号相对应的队列中，然后转进程调度。

V原语操作：
sem加1；
若相加结果大于0，V原语停止执行，该进程返回调用处，继续执行；
若相加结果小于或等于0，则从该信号的等待队列中唤醒一个等待进程，然后再返回原进程继续执行或转进程调度。

2.1.2 记录型信号量

记录型信号量是不存在“忙等”现象的进程同步机制。除了需要一个用于代表资源数目的整型变量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.value的初值表示系统中某种资源的数目。

对信号量 S 的一次 P 操作意味着进程请求一个单位的该类资源，因此需要执行 S.value–，表示资源数减1，当 S.value < 0 时表示该类资源己分配完毕，因此进程应调用 block 原语进行自我阻塞（当前运行的进程从运行态 →阻塞态），主动放弃处理机，并插入该类资源的等
待队列 S.L 中。可见，该机制遵循了“让权等待”原则，不会出现“忙等”现象。

对信号量 S 的一次 V 操作意味着进程释放一个单位的该类资源，因此需要执行 S.value++，表示资源数加1，若加1后仍是 S.value <= 0，表示依然有进程在等待该类资源，因此应调用 wakeup原语唤醒等待队列中的第一个进程（被唤醒进程从阻塞态→就绪态）。

2.3 利用信号量实现进程同步

信号量机制能用于解决进程间各种同步问题。设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语句
    // …
}

2.4 利用信号量实现进程互斥

信号量机构也能很方便地解决进程互斥问题。设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.5 利用信号量实现前驱关系

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

此处输入图片的描述

semaphore  a=b=c=b2=c=d=e=f=g=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是否已经运行完成
    // …;
}

2.5 小结

此处输入图片的描述

3. 进程同步与互斥经典问题

3.1 简单生产者与消费者问题

3.1.1 问题描述

一组生产者进程和一组消费者进程共享一块初始为空，大小确定的缓冲区，只有当缓冲区为满时，生产者进程才可以把信息放入缓冲区，否则就要等待；只有缓存区不为空时，消费者进程才能从中取出消息，否则就要等待。缓冲区一次只能一个进程访问（临界资源）。

3.1.2 问题分析

生产者与消费者进程对缓冲区的访问是互斥关系，而生产者与消费者本身又存在同步关系，即必须生成之后才能消费。因而对于缓冲区的访问设置一个互斥量，再设置两个信号量一个记录空闲缓冲区单元，一个记录满缓冲区单元来实现生产者与消费者的同步。

3.1.3 问题解决

伪代码实现

semaphore mutex=1;
semaphore full=0;         //同步信号量，表产品数量
semaphore empty=n;        //同步信号量，表空闲缓冲区数量

prodecer()
{
    while(1)
    {
          P(empty);          
          P(mutex);
          把产品放入缓冲区;
          V(mutex);
          V(full);      
    }    
}        

consumer()
{
    while(1)
   {
         P(full);
         P(mutex);
         从缓冲区取出一个产品;
         V(mutex);
         V(empty);     
    }    
}

注意：

在生产者—消费者问题中，不能将生产者进程的P(empty)和P(mutex)语句互换。因为生产者若是先拿到了mutex锁，然后发现没有空缓冲区，那么就会一直等待，同时一直拿着mutex锁。要注意到，mutex锁是生产者和消费者共享的，此时生产者拿着锁一直等待消费者消费，而消费者一直拿不到mutex锁，则会造成死锁。

3.2 读者写者问题

3.2.1 问题描述

有读者与写者两个并发进程共享一个数据，两个或以上的读进程可以访问数据，但是一个写者进程访问数据与其他进程都互斥。

3.2.2 问题分析

读者与写者是互斥关系，写者与写者是互斥关系，读者与读者是同步关系。因而需要一个互斥量实现读与写和写与写互斥，一个读者的访问计数和实现对计数的互斥。

3.2.3 问题解决

三种伪代码实现
1、读者优先
　　读者优先，只要有读者源源不断，写者就得不到资源。容易造成写者饥饿。

//读者优先

semaphore  rw=1;      //用于实现对文件的互斥访问。表示当前是否有进程在访问共享文件
int count = 0;      //记录当前有几个读进程在访问文件 
semaphore mutex = 1; //用于保证对count变量的互斥访问

writer()
{
    while(1)
    {
        P(rw);          //写之前加锁
        writing sth;
        V(rw);          //写之后解锁
    }
}

reader()
{
    while(1)
    {
        P(mutex);       //各读进程互斥访问count
        if(count==0)    //第一个读进程负责“加锁”
            P(rw);
        count++;        //访问文件的读进程数+1
        V(mutex);
        reading sth;
        P(mutex);       //各读进程互斥访问count
        count--;        //访问文件的读进程数-1
        if(count==0)    //最后一个读进程负责“解锁”
            V(rw);
        V(mutex)；
    }
}

2、读写公平
　　读者与写者公平抢占资源，但是只要之前已经排队的读者，就算写者获取的资源，也要等待所有等待的读者进程结束。　　

//读写公平
int count=0；
semaphore mutex=1;    //读者计数锁
semaphore rw=1;        //资源访问锁
semaphore w=1;        //读写公平抢占锁
writer()
{
    while(1)
    {
        P(w);
        P(rw);
        writing sth;
        V(rw);
        V(w);
    }
}

reader()
{
    while(1)
    {
        P(w);
        P(mutex);
        if(count==0)
            P(rw);
        count++;
        V(mutex);
        V(w);
        reading sth;
        P(mutex);
        count--;
        if(count==0)
            V(rw);
        V(mutex);        
    }
}

3、写者优先

　　写者优先，只要写者源源不断，读者就得不到资源，但是在这之前已经排队的的读者进程依然可以优先获得资源，在这之后则等待所有写者进程的结束。这种也易造成读者饥饿。

//写者优先
int write_count=0;         //写计数
int count=0;               //读计数
semaphore w_mutex=1;     //读计数时锁
semaphore r_mutex=1;    //写计数时锁
semaphore rw=1;            //写优先锁
semaphore source=1;        //资源访问锁

writer()
{
    while(1)
    {
        P(w_mutux);
        if(write_count==0)
            P(rw);        //获得则只要有写进程进来就不释放
        write_count++;
        V(w_mutux)
    
        P(resouce);        //写时互斥必须加资源独占的锁
        writing sth;
        V(resouce);
        
        P(w_mutux);
        write_count--;
        if(write_count==0)
            V(rw);
        V(w_mutux);
    }
}

reader()
{
    while(1)
    {
        P(rw);            //使用了立即释放
        P(r_mutex);
        if(count==0)
            P(resouce);
        count++;
        V(r_mutex);
        V(rw);
    
        reading sth;
        
        P(r_mutex);
        count--;
        if(count==0)
            V(resouce);
        V(r_mutex);        
    }
}

3.2.4 小结

读者-写者问题为我们解决复杂的互斥问题提供了一个参考思路。其核心思想在于设置了一个计数器 count 用来记录当前正在访问共享文件的读进程数。我们可以用 count 的值来判断当前进入的进程是否是第一个/最后一个读进程.从而做出不同的处理。另外对 count变量的检查和赋值不能一气呵成导致了一些错误.如果需要实现“一气呵成”.自然应该想到用互斥信号量。最后.还要认真题会我们是如何解决“写进程饥饿”问题的。

3.3 哲学家进餐问题

3.3.1 问题描述

一张圆桌上坐着五名哲学家，每两名哲学家之间的桌子摆一根筷子，哲学家只有同时拿起左右两根筷子时才可以用餐，用餐完了筷子放回原处。

3.3.2 问题分析

这里五名哲学家就是五个进程，五根筷子是需要获取的资源。可以定义互斥数组用于表示五根筷子的互斥访问，为了防止哲学家个取一根筷子出现死锁，需要添加一定的限制条件。一种方法是限制仅当哲学家左右筷子均可以用时，才拿起筷子，这里需要一个互斥量来限制获取筷子不会出现竞争。

3.3.3 问题解决

设置一个互斥信号量mutex是的拿筷子这个动作是互斥的，一次仅能一个哲学家拿起筷子，效率比较低。

semaphore chopstick[5]={1,1,1,1,1};
semaphore mutex=1;
pi()
{
    while(1)
    {
        P(mutex);
        P(chopstick[i]);
        P(chopstick[(i+1)%5]);
        V(mutex);
        
        eating;
        
        V(chopstick[i]);
        V(chopstick[(i+1)%5]);
    }
}

3.3.4 小结

哲学家进餐问题的关键在于解决进程死锁。这些进程之间只存在互斥关系，但是与之前接触到的互斥关系不同的是，每个进程都需要同时持有两个临界资源，因此就有“死锁”问题的隐患。

如果在考试中遇到了一个进程需要同时持有多个临界资源的情况，应该参考哲学家问题的思想，分析题中给出的进程之间是否会发生循环等待，是否会发生死锁。