2.3 同步与互斥

2.3.1 同步与互斥的概念

1.临界资源

一次只允许一个进程使用的资源称为临界资源

2.同步

为完成某种人//如果 S.L 该资源不够，该进程进入阻塞队列某些地方上协调它们的工作次序而等待、传递信息所产生的制约关系。

3.互斥

互斥也称间接制约关系

（1）空闲让进

（2）忙则等待

（3）有限等待

（4）让权等待//不一定实现

P 操作即 wait 操作，表示等待某种资源直到可用，若这种资源暂时不可用，则进程进入阻塞态，执行 P 操作时的进程处于运行态。

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

1.软件实现方法

算法一：单标志法

别人允许你上厕所，你才能上。

缺点：两个进程必须轮流进入临界区，如果一个进程不再进入临界区，则另一个进程也无法进入临界区，违背“空闲让进”。

算法二：双标志先检查法

如果所有人都不用厕所，则自己进去上锁。

缺点：可能两个人同时进入厕所

算法三：双标志法后检查

算法四：Peterson 算法

缺点：未确定让权等待

2.硬件实现方法

（1）中断屏蔽方法

关中断；
临界区；
开中断；

（2）硬件指令方法

TestAndSet 指令

boolean TestAndSet(boolean *lock)
{
    boolean old;
    old = *lock;
    *lock = true;
    return old;
}
while TestAndSet(&lock);//读出 lock 后把 lock 设置为 true
进程的临界区代码段;
lock=false;
进程的其他代码;

Swap 指令

Swap(boolean *a,boolean *b){
    boolean temp;
    Temp=*a;
    *a=*b;
    *b=temp;
}
key=true;
while(key!=false)//如果 key 为 true
    Swap(&lock,&key);//检查时都上锁，直到 key 为 false，说明不上锁
进程的临界区代码段;
lock=false;
进程的其他代码;

2.3.3 互斥锁

acquire(){
    while(!available)
        ; //忙等待
    available=false; //获得锁
}
release(){
    available=true;
}

缺点：忙等待，进程时间片用完才下处理机。

需要连续循环忙等待的互斥锁，都可称为自旋锁。

2.3.4 信号量

信号量	互斥量	资源量
	1 表示临界区只允许一个进程进入	可用资源
	0 表示临界区进入了一个进程，无等待	无可用资源
	<0 表示临界区有一个进程，有绝对值等待	<0 表示资源用完，有绝对值等待

1.整型信号量

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

缺点：未遵循让权等待。

2.记录型信号量

typedef struct
{
    int value;
    struct process *L;
} semaphore;
void wait(semaphore S)
{
    S.value--;
    if (S.value < 0)
    { //如果 S.L 该资源不够，该进程进入阻塞队列
        add this process to S.L;
        block(S.L);
    }
}
void signal(semaphore)
{
    S.value++;
    if (S.value < 0)
    { //如果 S.L 中还有等待该资源的进程被阻塞，唤醒一个进程
        remove a process P from S.L;
        wakeup(P);
    }
}

3.利用信号量实现同步

semaphore S = 0;
P1()
{
    x;
    V(S);
}
P2()
{
    P(S);
    y;
}

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

semophore S = 1;
P1()
{
    P(S);
    进程P1的临界区;
    V(S);
}
P2()
{
    P(S);
    进程P2的临界区;
    V(S);
}

2.3.5 管程

2.3.6 经典同步问题

1.生产者 - 消费者问题

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

semophore mutex = 1; //临界区互斥信号量
semophore empty = n; //空闲缓冲区
semophore 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;           //消费数据
    }
}

同步的 P 操作一定要放在互斥的 P 操作前。

2.多生产者 - 多消费者问题

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

semophare plate = 1, 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;
    }
}

3.读者 - 写者问题

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

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(mutex); //互斥访问 count 变量
        if (count == 0)
            P(rw)
        count++;
        V(mutex); //释放互斥变量 count
        reading;  //读取
        P(mutex); //互斥访问 count 变量
        count--;//读写计数器减 1
        if(count==0)//当最后一个读进程读完共享文件
            V(rw);//允许写进程写
        V(mutex);//释放互斥变量 count
    }
}

4.哲学家进餐问题

问题描述：一张圆桌边上坐着 5 名哲学家，没两名哲学家之间的桌上摆一根筷子，两根筷子中间时一碗米饭，哲学家们只思考和吃饭。哲学家思考时不影响他人。只有当哲学家饥饿时，才试图拿起左、右两根筷子（一根一根地拿起）。若筷子已在他人手上，则需要等待。饥饿的哲学家只有同时拿到了两根筷子才可以开始进餐。进餐完毕后，放下筷子进行思考。

解决方法：同时取左右两边筷子

semaphore chopstick[5] = {1, 1, 1, 1, 1};
semaphore mutex = 1; //设置取筷子的信号量
Pi()
{
    do
    {
        P(mutex);                  //在取筷子前获得互斥量
        P(chopstick[i]);           //取左边筷子
        P(chopstick[(i + 1) % 5]); //取右边筷子
        V(mutex);                  //释放筷子的信号量
        eat;
        V(chopstick[i]);           //放回左边筷子
        V(chopstick[(i + 1) % 5]); //放回右边筷子
        think;                     //思考
    } while (1);
}

5.吸烟者问题

问题描述：假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它，但要卷起并抽掉一只烟，抽烟者需要有三种材料：烟草、纸和胶水。三个抽烟者中，第一个拥有烟草，第二个拥有纸，第三个拥有胶水。供应者每次提供两种材料，一个抽烟者抽掉，并告诉供应者已完成，此时供应者就会放另外两种材料在桌子上。

int num = 0;          //存储随机数
semaphore offer1 = 0; //定义信号量对应烟草和纸组合的资源
semaphore offer2 = 0; //定义信号量对应烟草和胶水组合的资源
semaphore offer3 = 0; //定义信号量对应纸和胶水组合的资源
semaphore finish = 0; //定义信号量表示抽烟是否完成
process P1()
{
    while (1)
    {
        num++;
        num = num % 3;
        if (num == 0)
            V(offer1);
        else if (num == 1)
            V(offer2);
        else
            V(offer3);
        任一两种材料放在桌子上;
        P(finish);
    }
}
process P2()
{
    while (1)
    {
        P(offer3);
        拿纸和胶水，卷成烟，抽掉;
        V(finish);
    }
}
process P3()
{
    while (1)
    {
        P(offer2);
        拿烟草和胶水，卷成烟，抽掉;
        V(finish);
    }
}
process P4()
{
    while (1)
    {
        P(offer1);
        拿纸和烟草，卷成烟，抽掉;
        V(finish);
    }
}