2.5 经典同步问题

目录

• 目录
• 生产者消费者问题
• 哲学家进餐问题
• 读者写者问题

生产者消费者问题

问题描述：

1. 有一个缓冲区，缓冲区的大小为 n，初始为空
2. 有两类进程：生产者和消费者，这两个进程并发执行
3. 生产者进程不断地向缓冲区中放入数据，消费者进程不断地从缓冲区中取出数据
4. 同时只能有一个进程访问缓冲区，如果缓冲区满了，生产者进程就不能放入数据，如果缓冲区空了，消费者进程就不能取出数据

解决方法：

使用记录型变量来记录缓冲区的状态，使用信号量来实现对缓冲区的互斥访问。

// 有n个缓冲区
item buffer[n];
// 缓冲区的下标
int in = 0, out = 0;
// 定义信号量mutex，用于对缓冲区的互斥访问
semaphore mutex=1;
// 定义信号量empty，用于记录缓冲区的空闲空间
semaphore empty=n;
// 定义信号量full，用于记录缓冲区的已用空间
semaphore full=0;

// 生产者进程
void producer(){
    while(true){
        // 生产者进程申请一个空闲空间
        P(empty);
        // 生产者进程申请对缓冲区的互斥访问
        P(mutex);
        // 生产者进程将数据放入缓冲区
        buffer[in] = item;
        in = (in + 1) % n;
        // 生产者进程释放对缓冲区的互斥访问
        V(mutex);
        // 生产者进程释放一个已用空间
        V(full);
    }
}

// 消费者进程
void consumer(){
    while(true){
        // 消费者进程申请一个已用空间
        P(full);
        // 消费者进程申请对缓冲区的互斥访问
        P(mutex);
        // 消费者进程从缓冲区取出数据
        item = buffer[out];
        out = (out + 1) % n;
        // 消费者进程释放对缓冲区的互斥访问
        V(mutex);
        // 消费者进程释放一个空闲空间
        V(empty);
    }
}

void main(){
    cobegin{
        producer();
        consumer();
    }
}

使用 AND 型信号量集来实现：

// 有n个缓冲区
item buffer[n];
// 缓冲区的下标
int in = 0, out = 0;
// 定义信号量mutex，用于对缓冲区的互斥访问
semaphore mutex=1;
// 定义信号量empty，用于记录缓冲区的空闲空间
semaphore empty=n;
// 定义信号量full，用于记录缓冲区的已用空间
semaphore full=0;

// 生产者进程
void producer(){
    while(true){
        // 生产者进程同时申请一个空闲空间和对缓冲区的互斥访问
        SP(empty,mutex);
        // 生产者进程将数据放入缓冲区
        buffer[in] = item;
        in = (in + 1) % n;
        // 生产者进程同时释放一个已用空间和对缓冲区的互斥访问
        SV(full,mutex);
    }
}

// 消费者进程
void consumer(){
    while(true){
        // 消费者进程同时申请一个已用空间和对缓冲区的互斥访问
        SP(full,mutex);
        // 消费者进程从缓冲区取出数据
        item = buffer[out];
        out = (out + 1) % n;
        // 消费者进程同时释放一个空闲空间和对缓冲区的互斥访问
        SV(empty,mutex);
    }
}

void main(){
    cobegin{
        producer();
        consumer();
    }
}

利用管程来实现：

待写

哲学家进餐问题

问题描述：

1. 有五个哲学家，围坐在一张圆桌旁，每个哲学家面前有一碗饭和一只筷子
2. 哲学家的生活方式是交替地进行思考和进餐，思考的时候不需要筷子，进餐的时候需要两只筷子
3. 哲学家只能同时拿起自己面前和左边的筷子，并且只有同时拿到两只筷子的时候才能进餐

解决方法：

使用记录型变量来记录筷子的状态，使用信号量来实现对筷子的互斥访问。

// 定义记录型变量，记录筷子的状态
semaphore chopstick[5]={1,1,1,1,1};

// 第i位哲学家进程
void philosopher(int i){
    while(true){
        // 哲学家进程申请左边的筷子
        P(chopstick[i]);
        // 哲学家进程申请右边的筷子
        P(chopstick[(i+1)%5]);
        // 哲学家进程进餐
        eat();
        // 哲学家进程释放左边的筷子
        V(chopstick[i]);
        // 哲学家进程释放右边的筷子
        V(chopstick[(i+1)%5]);
        // 哲学家进程思考
        think();
    }
}

这种方法会造成死锁，因为当所有的哲学家都拿起了自己左边的筷子，那么所有的哲学家都在等待右边的筷子，造成死锁。可以通过算法优化

使用 AND 型信号量集来实现：

// 定义记录型变量，记录筷子的状态
semaphore chopstick[5]={1,1,1,1,1};

// 第i位哲学家进程
void philosopher(int i){
    while(true){
        // 哲学家进程申请左边和前面的筷子
        SP(chopstick[i],chopstick[(i+1)%5]);
        // 哲学家进程进餐
        eat();
        // 哲学家进程释放左边和前面的筷子
        SV(chopstick[i],chopstick[(i+1)%5]);
        // 哲学家进程思考
        think();
    }
}

读者写者问题

问题描述：

1. 有一个文件，多个进程可以同时读这个文件，但是只能有一个进程写这个文件
2. 如果有一个进程在写这个文件，那么其他进程就不能读和写这个文件
3. 如果有一个进程在读这个文件，那么其他进程可以继续读这个文件，但是不能写这个文件
4. 读者进程和写者进程并发执行

解决方法：

使用记录型变量来记录文件的状态，使用信号量来实现对文件的互斥访问。

// 定义记录型变量，记录文件的写状态
semaphore wmutex = 1;
// 记录读者的数量
int readcount = 0;
// 由于读者数量也是一个临界资源，所以需要对其进行互斥访问
semaphore rmutex = 1;

// 读者进程
void reader(){
    while(true){
        // 读者进程申请对读者数量的互斥访问
        P(rmutex);
        // 如果没人读，那么读者进程申请对文件的互斥访问
        if(readcount == 0){
            P(wmutex);
        }
        // 读者数量加一
        readcount++;
        // 读者进程释放对读者数量的互斥访问
        V(rmutex);
        // 读取文件
        read();
        // 读者进程申请对读者数量的互斥访问
        P(rmutex);
        // 读者数量减一
        readcount--;
        // 如果没人读，那么读者进程释放对文件的互斥访问
        if(readcount == 0){
            V(wmutex);
        }
        // 读者进程释放对读者数量的互斥访问
        V(rmutex);
    }
}

// 写者进程
void writer(){
    while(true){
        // 写者进程申请对文件的互斥访问
        P(wmutex);
        // 写文件
        write();
        // 写者进程释放对文件的互斥访问
        V(wmutex);
    }
}

在读者进程中，我们看到对于读者数量的互斥访问，这是因为读者数量也是一个临界资源，如果不对其进行互斥访问，那么可能会造成读者数量的错误。

例如：当某个读者执行了if(readcount == 0){后V(wmutex);前，另一个读者执行了readcount++;，这个时候会导致资源的错误释放

使用信号量集来实现：

这里规定同时只能有 RN 个读者进程访问文件，这样方便信号量机制的使用

// 定义RN
int RN;
// 定义记录型变量，记录文件的写状态
semaphore wmutex = 1;
// 定义信号量集，用于记录读者的数量
semaphore rmutex = RN;

// 读者进程
void reader(){
    while(true){
        // 读者进程申请对读者数量的访问
        SP(rmutex,1,1);
        // 需要在文件未被写的时候才能读
        SP(wmutex,1,0);
        // 读取文件
        read();
        // 读者进程释放对读者数量的访问
        SV(rmutex,1,1);
        // 这里不需要释放对文件的访问，因为读者进程不会对文件进行修改
    }
}

// 写者进程
void writer(){
    while(true){
        // 写者进程申请对文件的访问
        SP(wmutex,1,1,rmutex,RN,0);
        // 写文件
        write();
        // 写者进程释放对文件的访问
        SV(wmutex,1);
    }
}