目录

一、进程同步与互斥的基本概念

二、进程互斥访问临界区算法

1 单标志法

2 双标志先检查法

3 双标志后检查法

4 Peterson算法

三、信号量互斥访问临界区

一、进程同步与互斥的基本概念

        在多道程序环境下，进程是并发执行的，不同进程之间存在着不同的相互制约关系。为了协调进程之间的相互制约关系，引入了进程同步的概念。我们举一个简单例子帮大家理解这个概念，比如，让系统计算1+2*3，假设系统产生两个进程:一个是加法进程、一个是乘法进程。为了让计算结果是正确的，那么一定要让加法进程发生在乘法进程之后，但实际上操作系统具有异步性,如果不加制约，加法进程发生在乘法进程之前是绝对有可能的，所以就要制定一定的机制， 去约束加法进程，让他在乘法进程完成之后才发生，而这种机制，就是本节要讨论的内容。

        临界区：虽然多个进程可以共享系统中的各种资源，但其中许多资源一次只能为一个进程所使用， 我们把一次仅允许一个进程使用的资源称为临界资源。许多物理设备都属于临界资源，如打印机等。此外，还有许多变量、数据等都可以被若干进程共享，也属于临界资源。对临界资源的访问，必须互斥地进行，在每个进程中，访问临界资源的那段代码称为临界区。

        为了保证临界区资源的使用，可以把临界区资源访问过程分为四个部分：

（1）进入区：为了进入临界区使用临界资源，在进入区要检查可否进入临界区，如果可以进入临界区，则设置正在访问临界区的标志，以阻止其他进程同时进入临界区。（2）临界区：进程中访问临界区资源的那段代码，又称临界段。（3）退出区：将正在访问临界区的标志清除。（4）剩余区：代码中的其余部分。

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

         同步：同步亦称直接制约关系，它是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而等待、传递信息所产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作。例如，输入进程A通过单缓冲向进程B提供数据。当该缓冲区空时，进程B不能获得所需数据而阻塞，一旦进程A将数据送入缓冲区，进程B被唤醒。反之，当缓冲区满时，进程A被
阻塞，仅当进程B取走缓冲数据时，才唤醒进程A。

        互斥：互斥亦称间接制约关系。当一个进程进入临界区使用临界资源时，另一个进程必须等待，当占用临界资源的进程退出临界区后，另一进程才允许去访问此临界资源。例如，在仅有一台打印机的系统中，有两个进程A和进程B,如果进程A需要打印时，系统已将打印机分配给进程B，则进程A必须阻塞。一旦进程B将打印机释放，系统便将进程A唤醒，并将其由阻塞状态变为就绪状态。为禁止两个进程同时进入临界区，同步机制应遵循以下准则:
        1)空闲让进。临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区。
        2)忙则等待。当已有进程进入临界区时，其他试图进入临界区的进程必须等待。
        3)有限等待。对请求访问的进程，应保证能在有限时间内进入临界区。
        4)让权等待。当进程不能进入临界区时，应立即释放处理器，防止进程忙等待。

二、进程互斥访问临界区算法

1 单标志法

        算法思想：两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程。也就是说每个进程进入临界区的权限只能被另一个进程赋予。

int turn=0; //turn 表示当前允许进入临界区的进程号
//P0进程                        
while(turn != 0);  //1       
critical section;  //2        
turn = 1;          //3        
remainder section; //4        

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

        turn的初值为0，即刚开始只允许0号进程进入临界区。若P1先上处理机运行，则会一直卡在5。直到P1的时间片用完，发生调度，切换P0上处理机运行。代码1不会卡住P0，P0可以正常访问临界区，在P0访问临界区期间即时切换回P1，P1依然会卡在5。只有P0在退出区将turn的值改为1后，P1才能进入临界区。

        缺点：只有在P0进程把turn置1后，P1才可以访问临界区，如果P0进程一直不进临界区，那么临界区虽然空闲，但是P1进程不能访问临界区，这违背了“空闲让进”的原则。

2 双标志先检查法

        算法思想:设置一个布尔型数组flag[]，数组中各个元素用来标记各进程想进入临界区的意愿，比如“flag[0] = ture”意味着0号进程P0现在想要进入临界区。每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区，如果没有，则把自身对应的标志flag[i]设为true，之后开始访问临界区。

bool flag[2];     //表示进入临界区意愿的数组
flag[0]=false;    //P0进程：false表示不想进入临界区
flag[1]=false;    //P1进程：false表示不想进入临界区

//P0进程                         
while(flag[1]);   //1       
flag[0]=ture;     //2        
critical section; //3        
flag[0]=false;    //4        
remainder section;           

//P1进程
while(flag[0])    //5 如果此时P0想进入临界区，P1就一直循环等待
flag[1]=ture;     //6 标记为P1进程想要进入临界区
critical section; //7 访问临界区
flag[1]=false;    //8 访问完临界区，修改标记为P1不想使用临界区
remainder section;

 若按照1-5-2-6-3-7....的顺序执行，P0和P1将会同时访问临界区。因此，双标志检查法的主要问题是：违反“忙则等待”原则。原因在于，进入区的“检查”和“上锁”两个处理不是一气呵成的，“检查”后，“上锁”前可能发生进程切换。

3 双标志后检查法

        算法思想:双标志先检查法的改版。前一个算法的问题是先“检查”后“上锁”，但是这两个操作又无法一气呵成，因此导致了两个进程同时进入临界区的问题。因此，人们又想到先“上锁”后“检查'的方法，来避免上述问题。

bool flag[2];  //表示进去临界区意愿的数组
flag[0]=false; //开始设置为两个进程都不想访问临界区
flag[1]=false;
//P0进程
flag[0]=ture;    //1
while(flag[1]);  //2
critical section;//3
flag[0]=false;   //4
remainder section;

//P1进程
flag[1]=ture;    //5  标记为P1进程想要进入临界区
while(flag[0]);  //6  如果P0也想进入临界区，则P1循环等待
critical section;//7  访问临界区
flag[1]=false;   //8  访问完临界去，修改标记为P1不想使用临界区
remainder section;

        若按照1-5-2-6.....的顺序执行，P0和P1都将无法进入临界区。因此，双标志后检查法虽然解决了“忙则等待”的问题，但是又违背了“空闲让进”和“有限等待”原则，会因各进程都长期无法访问临界资源而产生“饥饿”现象。

4 Peterson算法

        算法思想:双标志后检查法中，两个进程都争着想进入临界区，但是谁也不让谁，最后谁都无法进入临界区。Gary L. Peterson想到了一种方法，如果双方都争着想进入临界区，那可以让进程尝试“孔融让梨”，主动让对方先使用临界区。

bool flag[2]; //表示进入临界区意愿数组，初始值都是false
int turn=0;   //turn 表示优先让哪一个进程进入临界区
//P0进程
flag[0]=ture;             //1
turn = 1;                 //2
while(flag[1] && turn==1);//3
critical section;         //4
flag[0]=false;            //5
remainder section;

//P1进程
flag[1]=ture;             //6 表示自己想进入临界区
turn = 0;                 //7 可以优先让对方进入临界区
while(flag[0] && turn==0);//8 对方想进，且最后一次是自己“让梨”，自己就循环等待
critical section;         //9
flag[1]=false;            //10 访问完临界区，表示自己已经不想访问临界区了
remainder section;

        Peterson算法用软件方法解决了进程互斥问题，遵循了空闲让进、忙则等待、有限等待三个原则，但是依然未遵循让权等待的原则。但优于其他三种进程互斥访问临界区算法。

三、信号量互斥访问临界区

        在上述的4中临界区访问算法中，都无法实现“让权等待”原则。用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作， 从而很方便的实现了进程互斥、 进程同步。

        信号量其实就是一个变量 ， 可以用一个信号量来表示系统中某种资源的数量， 比如： 系统中只有一台打印机， 就可以设置一个初值为 1 的信号量。

        原语是一种特殊的程序段， 其执行只能一气呵成， 不可被中断。 原语是由关中断/开中断指令实现的。 软件解决方案的主要问题是由“进入区的各种操作无法一气呵成” ， 因此如果能把进入区、 退出区的操作都用“原语” 实现， 使这些操作能“一气呵成” 就能避免问题。

        一对原语： wait(S) 原语和 signal(S) 原语， 可以把原语理解为我们自己写的函数， 函数名分别为 wait和 signal， 括号里的信号量 S 其实就是函数调用时传入的一个参数。

        wait、 signal 原语常简称为 P、 V操作（来自荷兰语 proberen 和 verhogen） 。 因此， 做题的时候常把wait(S)、 signal(S) 两个操作分别写为 P(S)、 V(S)