进程同步（操作系统层面，不涉及具体系统api）

时间：2021-03-18 18:08:18

1.临界区

对资源进行锁定的那段代码称为临界区。

为了互斥访问临界资源，每个进程在进入临界区之前，需要先进行检查。

//entry section

//critical section

//exit section

2.同步与互斥

同步：多个进程按一定顺序执行；

互斥：多个进程在同一时刻只有一个进程能进入临界区

3.信号量

信号量（Semaphore）是一个整型变量，可以对其执行down和up操作。

down：如果信号量大于0，执行-1；如果信号量等于0，进程阻塞，等候信号量大于0；

up：对于信号执行+1操作，唤醒睡眠的进程让其完成down操作。

down和up操作需要被设计成原语，不可分割，通常的做法是在执行这些操作的时候屏蔽中断。

如果信号量的取值只能是0或者1，那么就成为了互斥量（Mutex），0表示已加锁，1表示已解锁。

使用信号量实现产生者-消费者问题

问题描述：使用一个缓冲区来保存物品，只有缓冲区没有满，生产者才可以放入物品；只有缓冲区不为空，消费者才可以拿走物品。

因为缓冲区属于临界资源，因此需要一个互斥量mutex来控制对缓冲区的互斥访问。

为了同步生产者和消费者的行为，需要记录缓冲区中物品的数量。数量可以使用信号量来进行统计，这里需要使用两个信号量：empty记录空缓冲区的数量，full记录满缓冲区的数量。其中，empty信号量是在生产者进程中使用，当empty不为0时，生产者才可以放入物品；full信号量是在消费者进程中使用，当full信号量不为0时，消费者才可以取走物品。

注意，不能先对缓冲区进行加锁，再测试信号量。也就是说，不能先执行 down(mutex) 再执行 down(empty)。如果这么做了，那么可能会出现这种情况：生产者对缓冲区加锁后，执行 down(empty) 操作，发现 empty = 0，此时生产者睡眠。消费者不能进入临界区，因为生产者对缓冲区加锁了，也就无法执行 up(empty) 操作，empty 永远都为 0，那么生产者和消费者就会一直等待下去，造成死锁。

经典同步问题

1.读写问题

允许多个进程同时对数据进行读操作，但是不允许读和写以及写和写操作同时发生。

2.哲学家进餐问题

五个哲学家围着一张圆桌，每个哲学家面前放着食物。哲学家的生活有两种交替活动：吃饭以及思考。当一个哲学家吃饭时，需要先拿起自己左右两边的两根筷子，并且一次只能拿起一根筷子。

考虑到如果所有哲学家同时拿起左手边的筷子，那么就无法拿起右手边的筷子，造成死锁。

为了防止死锁的发生，可以设置两个条件：

  1. 必须同时拿起左右两根筷子；
  2. 只有在两个邻居都没有进餐的情况下才允许进餐。

#define N 5
#define LEFT (i + N - 1) % N // 左邻居
#define RIGHT (i + 1) % N    // 右邻居
#define THINKING 0
#define HUNGRY   1
#define EATING   2
typedef int semaphore;
int state[N];                // 跟踪每个哲学家的状态
semaphore mutex = 1;         // 临界区的互斥
semaphore s[N];              // 每个哲学家一个信号量

void philosopher(int i) {
    while(TRUE) {
        think();
        take_two(i);
        eat();
        put_tow(i);
    }
}

void take_two(int i) {
    down(&mutex);
    state[i] = HUNGRY;
    test(i);
    up(&mutex);
    down(&s[i]);
}

void put_tow(i) {
    down(&mutex);
    state[i] = THINKING;
    test(LEFT);
    test(RIGHT);
    up(&mutex);
}

void test(i) {         // 尝试拿起两把筷子
    if(state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] !=EATING) {
        state[i] = EATING;
        up(&s[i]);
    }
}




标签：

相关文章