1. 实验目的

利用实验四提供的方法和例子，解决进程同步相关问题，例如：生产者消费者问题，哲学家进餐等问题。

2. 实验内容

2.1 生产者消费者问题

一组生产者进程向一组消费者进程提供产品，两类进程共享一个由 n 个缓冲区组成的有界缓冲池，生产者进程向空缓冲池中投放产品，消费者进程从放有数据的缓冲池中取得产品并消费掉。只要缓冲池未满，生产者进程就可以把产品送入缓冲池；只要缓冲池未空，消费者进程便可以从缓冲池中取走产品。但禁止生产者进程向满的缓冲池再输送产品，也禁止消费者进程从空的缓冲池中提取产品。为了防止对缓冲池重复操作，故规定在任何时候，只有一个主体可以访问缓冲池。

▶

Code

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <inttypes.h>
#include <unistd.h>
#include <pthread.h>
#include <semaphore.h>

#define PRODUCER_NUM 5    // 生产者数目
#define CONSUMER_NUM 5    // 消费者数目
#define POOL_SIZE 11      // 缓冲池大小
#define PRODUCE_TIMES 10  // 每个生产者生产次数
#define CONSUME_TIMES 10  // 每个消费者消费次数, 总数须与生产总数一致以免死锁

int pool[POOL_SIZE];  // 缓冲区
int head = 0;         // 缓冲池读取指针
int rear = 0;         // 缓冲池写入指针

sem_t pool_sem;     // 同步信号量, 表示缓冲池有可用空间
sem_t product_sem;  // 同步信号量, 表示缓冲池有可用产品
pthread_mutex_t mutex;

void *producer_func(void *arg)
{
    intptr_t id = (intptr_t)arg;  // 取出线程编号
    for (int i = 0; i < PRODUCE_TIMES; i++) {
        sleep(1);
        sem_wait(&pool_sem);
        pthread_mutex_lock(&mutex);

        // 生产者往缓冲池中写入数据
        pool[rear] = 1;
        rear = (rear + 1) % POOL_SIZE;
        printf("Producer %" PRIdPTR " write to pool!\r\n", id);
        printf("Pool size is %d.\r\n", (rear - head + POOL_SIZE) % POOL_SIZE);
        pthread_mutex_unlock(&mutex);
        sem_post(&product_sem);
    }
    return NULL;
}

void *consumer_func(void *arg)
{
    intptr_t id = (intptr_t)arg;  // 取出线程编号
    for (int i = 0; i < CONSUME_TIMES; i++) {
        int data;
        sleep(1);
        sem_wait(&product_sem);
        pthread_mutex_lock(&mutex);

        // 消费者从缓冲池读取数据
        data = pool[head];
        head = (head + 1) % POOL_SIZE;
        printf("Consumer %" PRIdPTR " read from pool!\r\n", id);
        printf("Pool size is %d.\r\n", (rear - head + POOL_SIZE) % POOL_SIZE);
        pthread_mutex_unlock(&mutex);
        sem_post(&pool_sem);
    }
    return NULL;
}

int main()
{
    int i;
    pthread_t producer_id[PRODUCER_NUM];
    pthread_t consumer_id[CONSUMER_NUM];
    pthread_mutex_init(&mutex, NULL);

    int ret = sem_init(&pool_sem, 0, POOL_SIZE - 1);
    if (ret != 0) {
        printf("Failed to init pool_sem.\r\n");
        exit(0);
    }

    ret = sem_init(&product_sem, 0, 0);
    if (ret != 0) {
        printf("Failed to init product_sem.\r\n");
        exit(0);
    }

    for (i = 0; i < PRODUCER_NUM; i++) {
        // 创建生产者线程
        ret = pthread_create(&producer_id[i], NULL, producer_func, (void *)(intptr_t)i);
        if (ret != 0) {
            printf("Create producer thread error.\r\n");
            exit(0);
        }

        // 创建消费者线程
        ret = pthread_create(&consumer_id[i], NULL, consumer_func, (void *)(intptr_t)i);
        if (ret != 0) {
            printf("Create consumer thread error.\r\n");
            exit(0);
        }
    }

    for (i = 0; i < PRODUCER_NUM; i++) {
        pthread_join(producer_id[i], NULL);
        pthread_join(consumer_id[i], NULL);
    }
    return 0;
}

2.2 哲学家进餐问题

有 5 位哲学家倾注毕生精力用于思考和吃饭，他们围坐在一张圆桌旁，在圆桌上有 5 个碗和 5 支筷子。每位哲学家的行为通常是思考，当其感到饥饿时，便试图取其左右最靠近他的筷子进餐。只有他拿到两支筷子后才能进餐，进餐完毕后，释放两支筷子并继续思考。

▶

Code

/*
 * 规定: 只有当哲学家的左右两只筷子均处于可用状态时, 才允许他拿起筷子.
 * 这样可以避免他们同时拿起筷子就餐, 导致死锁.
 */

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <pthread.h>
#include <semaphore.h>

#define PHIL_NUM 5    // 哲学家人数
#define EAT_TIME 3    // 吃饭时间
#define THINK_TIME 3  // 思考时间

#define left(phil_id) ((phil_id + PHIL_NUM - 1) % PHIL_NUM)
#define right(phil_id) ((phil_id + 1) % PHIL_NUM)

typedef enum : int {
    PHIL_THINK = 0,
    PHIL_HUNGRY,
    PHIL_EAT,

    PHIL_MAX
} phil_state_e;

phil_state_e phil_state[PHIL_NUM];  // 所有哲学家的状态
pthread_mutex_t phil_mutex;         // 互斥锁, 用来保护 phil_state 状态数组
sem_t phil_sem[PHIL_NUM];           // 每个哲学家一个信号量, 初始值为 0, 用于在拿不到筷子时阻塞自己

void thinking(int id)
{
    printf("Philosopher[%d] is thinking...\r\n", id);
    sleep(THINK_TIME);
}

void eating(int id)
{
    printf("Philosopher[%d] is eating...\r\n", id);
    sleep(EAT_TIME);
}

void test(int id)
{
    if (phil_state[id] == PHIL_HUNGRY && phil_state[left(id)] != PHIL_EAT && phil_state[right(id)] != PHIL_EAT) {
        phil_state[id] = PHIL_EAT;
        sem_post(&phil_sem[id]);  // 满足条件, 唤醒该哲学家
    }
}

void take_forks(int id)
{
    pthread_mutex_lock(&phil_mutex);    // 进入临界区
    phil_state[id] = PHIL_HUNGRY;       // 宣布自己饿了
    test(id);                           // 尝试同时拿起两只筷子
    pthread_mutex_unlock(&phil_mutex);  // 离开临界区

    sem_wait(&phil_sem[id]);
}

void put_down_forks(int id)
{
    printf("Philosopher[%d] put down forks.\n", id);

    pthread_mutex_lock(&phil_mutex);    // 进入临界区
    phil_state[id] = PHIL_THINK;        // 放下筷子, 恢复思考状态
    test(left(id));                     // 检查左边邻居是否在等筷子, 如果是且条件满足则唤醒他
    test(right(id));                    // 检查右边邻居是否在等筷子, 如果是且条件满足则唤醒他
    pthread_mutex_unlock(&phil_mutex);  // 离开临界区
}

void *philosopher_work(void *arg)
{
    int id = *(int *)arg;
    printf("The philosopher[%d] has sat down.\r\n", id);

    while (1) {
        thinking(id);
        take_forks(id);
        eating(id);
        put_down_forks(id);
    }

    return NULL;
}

int main()
{
    int ret;
    int id[PHIL_NUM];
    pthread_t phil_tid[PHIL_NUM];

    // 初始化互斥锁和信号量
    pthread_mutex_init(&phil_mutex, NULL);
    for (int i = 0; i < PHIL_NUM; i++) {
        if (sem_init(&phil_sem[i], 0, 0) != 0) {
            printf("Failed to init semaphore[%d].\r\n", i);
            return -1;
        }
        phil_state[i] = PHIL_THINK;
    }

    // 创建哲学家线程
    for (int i = 0; i < PHIL_NUM; ++i) {
        id[i] = i;
        ret = pthread_create(&phil_tid[i], NULL, philosopher_work, (void *)(&id[i]));
        if (ret != 0) {
            printf("Failed to create process for philosopher[%d].\r\n", i);
            return -1;
        }
    }

    // 等待子线程
    for (int i = 0; i < PHIL_NUM; i++) {
        pthread_join(phil_tid[i], NULL);
    }

    // 回收资源
    pthread_mutex_destroy(&phil_mutex);
    for (int i = 0; i < PHIL_NUM; i++) {
        sem_destroy(&phil_sem[i]);
    }

    return 0;
}

2.3 和尚打水问题

某寺庙，有小和尚、老和尚若干。有一水缸，由小和尚提水入缸供老和尚饮用。水缸可容 10 桶水，水取自同一井中。水井径窄，每次只能容下一个桶取水。水桶总数为 3 个。每人一次取缸水仅为 1 桶，且不可同时进行。

▶

Code

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <inttypes.h>

#include <unistd.h>
#include <pthread.h>
#include <semaphore.h>

#define LITTLE_MONK_NUM 5  // 小和尚数目, 负责往水缸倒水
#define BIG_MONK_NUM 5     // 大和尚数目, 负责从水缸取水
#define BUCKET_NUM 3       // 水桶数目
#define TANK_SIZE 10       // 水缸容量
#define TASKS_TIMES 10     // 每个和尚打水/取水次数, 生产总数须与消费总数一致以免死锁

int tank_count = 0;          // 水缸中当前水的桶数
sem_t bucket_sem;            // 信号量, 表示空闲水桶数量
sem_t empty_sem;             // 信号量, 表示水缸可用空间
sem_t full_sem;              // 信号量, 表示水缸中已有水的桶数
pthread_mutex_t well_mutex;  // 井边互斥锁, 同一时刻只能有一个小和尚在井边打水
pthread_mutex_t tank_mutex;  // 水缸旁互斥锁, 同一时刻只能有一个和尚在倒水或取水

void *little_monk_func(void *arg)
{
    intptr_t id = (intptr_t)arg;  // 取出线程编号
    for (int i = 0; i < TASKS_TIMES; i++) {
        sleep(1);
        sem_wait(&empty_sem);   // 水缸未满才能去打水, 占用一个空位
        sem_wait(&bucket_sem);  // 有空闲水桶才能去打水
        pthread_mutex_lock(&well_mutex);

        // 小和尚在井边提水
        printf("第 %lld 个小和尚在水井提水\r\n", id);
        pthread_mutex_unlock(&well_mutex);

        pthread_mutex_lock(&tank_mutex);
        // 小和尚在水缸旁倒水
        printf("水缸已有 %d 桶水，第 %lld 个小和尚在水缸旁倒水\r\n", tank_count, id);
        tank_count++;
        pthread_mutex_unlock(&tank_mutex);

        sem_post(&bucket_sem);  // 放下水桶
        sem_post(&full_sem);    // 水缸中水的桶数加 1
    }
    return NULL;
}

void *big_monk_func(void *arg)
{
    intptr_t id = (intptr_t)arg;  // 取出线程编号
    for (int i = 0; i < TASKS_TIMES; i++) {
        sleep(1);
        sem_wait(&full_sem);    // 水缸中有水才能取水, 占用一桶水
        sem_wait(&bucket_sem);  // 有空闲水桶才能去取水
        pthread_mutex_lock(&tank_mutex);

        // 大和尚在水缸旁提水
        printf("水缸已有 %d 桶水, 第 %lld 个大和尚在水缸旁提水\r\n", tank_count, id);
        tank_count--;
        pthread_mutex_unlock(&tank_mutex);

        sem_post(&bucket_sem);  // 放下水桶
        sem_post(&empty_sem);   // 水缸可用空间加 1
    }
    return NULL;
}

int main()
{
    int i;
    pthread_t little_monk_id[LITTLE_MONK_NUM];
    pthread_t big_monk_id[BIG_MONK_NUM];
    pthread_mutex_init(&well_mutex, NULL);
    pthread_mutex_init(&tank_mutex, NULL);

    int ret = sem_init(&bucket_sem, 0, BUCKET_NUM);
    if (ret != 0) {
        printf("Failed to init bucket_sem.\r\n");
        exit(0);
    }

    ret = sem_init(&empty_sem, 0, TANK_SIZE);
    if (ret != 0) {
        printf("Failed to init empty_sem.\r\n");
        exit(0);
    }

    ret = sem_init(&full_sem, 0, 0);
    if (ret != 0) {
        printf("Failed to init full_sem.\r\n");
        exit(0);
    }

    for (i = 0; i < LITTLE_MONK_NUM; i++) {
        // 创建小和尚线程
        ret = pthread_create(&little_monk_id[i], NULL, little_monk_func, (void *)(intptr_t)i);
        if (ret != 0) {
            printf("Create little monk thread error.\r\n");
            exit(0);
        }

        // 创建大和尚线程
        ret = pthread_create(&big_monk_id[i], NULL, big_monk_func, (void *)(intptr_t)i);
        if (ret != 0) {
            printf("Create big monk thread error.\r\n");
            exit(0);
        }
    }

    for (i = 0; i < LITTLE_MONK_NUM; i++) {
        pthread_join(little_monk_id[i], NULL);
        pthread_join(big_monk_id[i], NULL);
    }

    // 释放资源
    pthread_mutex_destroy(&well_mutex);
    pthread_mutex_destroy(&tank_mutex);
    sem_destroy(&bucket_sem);
    sem_destroy(&empty_sem);
    sem_destroy(&full_sem);
    return 0;
}

3. 分析与思考

进程同步是一个操作系统级别的概念，是在多道程序的环境下，存在着不同的制约关系，为了协调这种互相制约的关系，实现资源共享和进程协作，从而避免进程之间的冲突，引入了进程同步。

进程同步也是进程之间直接的制约关系，是为完成某种任务而建立的两个或多个线程，这个线程需要在某些位置上协调他们的工作次序而等待、传递信息所产生的制约关系。

互斥是指当一个进程进入临界区使用临界资源的时候，另外一个进程必须等待，当占用临界资源的进程退出临界区后，另外一个进程才允许去访问此临界资源。