同步和互斥

//Swap指令 key= true; while (key != false) Swap(&lock,&key); critical section; lock = false; remainder section;

</TabItem>
</Tabs>

## 同步的实现

### 管程Monitor

```cpp
monitor Demo{
    sharing_struct S;//系统中某种资源定义的共享数据结构
    condition x;//阻塞原因条件变量,保存一个等待队列.实现同步
    condition y;//多个条件变量的设置
    init_code(){
        S = 5;
    }
    take_away(){
        if(S<=0) x.wait(); //资源不够,在x上阻塞等待
        --S;
    }
    give_back(){
        ++S;
        if(x.hasNext) x.signal();//唤醒一个阻塞进程
    }
};

1. 共享资源的操作封装起来,管程内的共享数据结构只能被管程内的过程所访问
2. 每次仅允许一个进程进入管程,从而实现进程互斥
3. 使用条件变量这种同步机制

信号量Semaphore(PV)

// 整型信号量
wait(S){
    while(S<=0);
    S = S - 1;
}
signal(S){
    S = S + 1;
}

//记录型信号量
typedef struct{
	int value;
	struct process *Q;//阻塞进程的排队链表
} semaphore;

void wait(semaphore S){
    S.value --;
    if(S.value <0){
        block(S.Q);//运行态进入阻塞态
        add this process to S.Q;
    }
}

void signal(semaphore S){
    S.value ++;
    if(S.value<=0){
        remve a process P from S.Q;
        wakeup(P);//唤醒阻塞队伍中的第一个进程
    }
}

//同步实现
semaphore S = 0;
P1(){
     x;
     V(S);
 }
P2(){
    P(S);
    y;
}

// 互斥实现
semaphore S = 1;
P1(){
    P(S);
    critical section;
    V(S);
}
P2(){
    P(S);
    critical section;
    V(S);
}

经典同步问题的处理方法

1. 生产者和消费者问题
2. 申请资源P操作一定在互斥加锁P操作之前，否则会导致死锁。
3. 生产者消费者问题中如果生产者和消费者都是唯一，mutex互斥信号量可以不要。
4. 读者写者问题：写者优先、读者优先、顺序访问
5. 哲学家进餐问题：死锁问题解决：
   1. 最多允许n-1个同时进餐
   2. 仅当一个哲学家左右两边的筷子同时可用，才会拿起筷子
   3. 哲学家编号，奇数先拿左筷子，偶数先拿右筷子

//生产者消费者问题
Semaphore filledBuffer = 0;
Semaphore emptyBuffer = n;
Semaphore mutex = 1;

//读者写者问题
Semaphore mutex = 1; //read or write mutex
Semaphore rmutex = 1; //change count mutex in readers
Semaphore wmutex = 1; //顺序锁，当有writer等待读写锁时，后来的reader不再进入count
int count = 0;

//哲学家进餐问题
semaphore fork[5] = {1,1,1,1,1};