经典同步问题

在考题中，经常需要你基于信号量的PV操作去实现某个同步问题，你首先需要熟练掌握本节的经典同步问题，并能在真实场景中自定义数据结构以及信号量，去设计同步问题的解决方案。

生产者消费者问题

生产者-消费者问题是并发编程中的经典问题，涉及到两种线程——生产者和消费者，它们共享一个固定大小的缓冲区或存储区。生产者的任务是生成数据并将其放入缓冲区，而消费者的任务是从缓冲区中取出并消费这些数据。关键的挑战在于确保生产者不会在缓冲区满时添加数据，同时确保消费者不会在缓冲区空时尝试消费数据。

semaphore mutex = 1;          // 临界区互斥信号量
semaphore empty = n;          // 空闲缓冲区数量
semaphore full  = 0;          // 忙缓冲区数量

producer() {
    while (1) {
        P(empty)              // 等待一个空位置
        P(mutex)              // 进入临界区前先获取mutex
        ....                  // 将数据项添加到缓冲区
        V(mutex)              // 离开临界区，释放mutex
        V(full)               // 增加一个数据项的计数
    }
}

consumer() {
    while (1) {
        P(full)               // 等待一个数据项
        P(mutex)              // 进入临界区前先获取mutex
        ...                  // 从缓冲区取出数据项并消费
        V(mutex)              // 离开临界区，释放mutex
        V(empty)              // 增加一个空位置的计数
    }
}

生产者消费者问题C代码实现

读者-写者问题

读者-写者问题是另一个经典的并发编程问题，涉及到对共享数据或资源的访问，这些资源可以被多个读者同时读取，但只能被一个写者写入，而且当写者正在写入数据时，没有其他读者或写者可以访问该资源。

这个问题的挑战在于：

允许多个读者同时读取资源。
确保当有一个写者访问资源时，没有其他读者或写者可以同时访问。

int read_count = 0;
semaphore wrt  = 1;
semphore mutex = 1;

reader() {
    while (1) {
        P(mutex)                     // 获取互斥访问权，以修改read_count
        read_count += 1
        if (read_count == 1) {       // 如果这是第一个读者，需要锁定资源，防止写者写入
            P(wrt)
        }
        V(mutex)                     // 释放互斥访问权
        ...                          // 读取资源
        P(mutex)                     // 获取互斥访问权，以修改read_count
        read_count -= 1
        if (read_count == 0) {       // 如果没有读者在读取，释放资源，允许写者写入
            V(wrt)
        }
        V(mutex)                     // 释放互斥访问权
    }
}

writer() {
    while (1) {
        P(wrt)                       // 获取资源的互斥访问权
        ...                          // 写入资源
        V(wrt)                       // 释放资源的互斥访问权
    }
}

int read_count = 0;
int write_count = 0;
semaphore wrt = 1;
semaphore mutex = 1;
semaphore write_mutex = 1;

reader() {
    while (1) {
        P(write_mutex)                  // 在读取之前，确保没有写者正在等待或写入
        P(mutex)                        // 获取互斥访问权，以修改read_count
        read_count += 1
        if (read_count == 1) {
            P(wrt)
        }
        V(mutex)
        V(write_mutex)

        ...                             // 读取资源

        P(mutex)                        // 获取互斥访问权，以修改read_count
        read_count -= 1
        if (read_count == 0) {
            V(wrt)
        }
        V(mutex)
    }
}

writer() {
    while (1) {
        P(write_mutex)                  // 获取互斥访问权，以修改write_count
        write_count += 1
        if (write_count == 1) {         // 如果这是第一个写者，锁定资源，防止新的读者读取
            P(wrt)
        }
        V(write_mutex)

        ...                             // 写入资源

        P(write_mutex)                  // 获取互斥访问权，以修改write_count
        write_count -= 1
        if (write_count == 0) {         // 如果没有其他写者在等待或写入，释放资源
            V(wrt)
        }
        V(write_mutex)
    }
}

int read_count = 0;
int write_count = 0;
semaphore wrt = 1;
semaphore mutex = 1;
semaphore queue = 1; // 新增队列信号量，以确保公平性

reader() {
    while (1) {
        P(queue);                 // 进入队列
        P(mutex);                 // 获取互斥访问权，以修改read_count
        read_count += 1;
        if (read_count == 1) {
            P(wrt);               // 如果是第一个读者，锁定资源
        }
        V(mutex);
        V(queue);                 // 离开队列
        ...                       // 读取资源
        P(mutex);                 // 获取互斥访问权，以修改read_count
        read_count -= 1;
        if (read_count == 0) {
            V(wrt);               // 如果是最后一个读者，释放资源
        }
        V(mutex);
    }
}

writer() {
    while (1) {
        P(queue);                 // 进入队列
        P(wrt);                   // 锁定资源
        ...                       // 写入资源
        V(wrt);                   // 释放资源
        V(queue);                 // 离开队列
    }
}

读者优先C代码实现

哲学家就餐问题

假设有五位哲学家坐在一个圆桌周围，每两位哲学家之间有一把叉子。哲学家的生活由思考和吃饭两种活动组成。为了吃饭，一个哲学家需要两把叉子——左边和右边的一把。问题在于，如何设计一个算法使得哲学家们可以正常就餐，而不会因为竞争叉子而导致死锁或饥饿。

哲学家就餐问题有多种解法，这里只提供一种最直观的解法，对于包含N各哲学家的问题：

前N-1个哲学家先拿起左边的叉子，再拿起右边的叉子
最后一个哲学家先拿起右边的叉子，再拿起左边的叉子

semaphore fork[5] = {1, 1, 1, 1, 1};      // 五个叉子，初始都是可用的

void philosopher(int i) {
    if (i < 5) {
        // 对于前面的哲学家，先左后右
        first = i;
        second = (i + 1) % 5;
    } else {
        // 对于最后一个哲学家，先右后左
        first = (i + 1) % 5;
        second = i;
    }
    while (1) {
        think();
        P(fork[first]);
        P(fork[second]);
        eat();
        V(fork[first]);
        V(fork[second]);
    }
}

哲学家就餐问题C代码实现

经典同步问题

生产者消费者问题

读者-写者问题

哲学家就餐问题

视频讲解