同步与互斥¶

while (true) {
  entry section;     // 进入区
  critical section;  // 临界区
  exit section;      // 退出区
  remainder section; // 剩余区
}

// 全局变量
int turn = 0;  // 0表示进程0可以进入，1表示进程1可以进入

// 进程0的代码
void process0() {
    while (true) {
        // 进入区：检查是否可以进入
        while (turn != 0) {
            // 忙等待，直到轮到自己
        }

        // 临界区
        critical_section();

        // 退出区：让给另一个进程
        turn = 1;

        // 剩余区
        remainder_section();
    }
}

// 进程1的代码
void process1() {
    while (true) {
        // 进入区：检查是否可以进入
        while (turn != 1) {
            // 忙等待，直到轮到自己
        }

        // 临界区
        critical_section();

        // 退出区：让给另一个进程
        turn = 0;

        // 剩余区
        remainder_section();
    }
}

// 全局变量
bool flag[2] = {false, false};  // 标志数组，表示进程是否想进入临界区

// 进程0的代码
void process0() {
    while (true) {
        // 进入区：先检查其他进程是否想进入
        while (flag[1]) {
            // 如果进程1想进入，等待
        }

        // 然后才设置自己的标志
        flag[0] = true;

        // 临界区
        critical_section();

        // 退出区：清除自己的标志
        flag[0] = false;

        // 剩余区
        remainder_section();
    }
}

// 进程1的代码
void process1() {
    while (true) {
        // 进入区：先检查其他进程是否想进入
        while (flag[0]) {
            // 如果进程0想进入，等待
        }

        // 然后才设置自己的标志
        flag[1] = true;

        // 临界区
        critical_section();

        // 退出区：清除自己的标志
        flag[1] = false;

        // 剩余区
        remainder_section();
    }
}

// 全局变量
bool flag[2] = {false, false};  // 标志数组，表示进程是否想进入临界区

// 进程0的代码
void process0() {
    while (true) {
        // 进入区：先设置自己的标志
        flag[0] = true;

        // 检查其他进程是否也想进入
        while (flag[1]) {
            // 如果进程1也想进入，等待
        }

        // 临界区
        critical_section();

        // 退出区：清除自己的标志
        flag[0] = false;

        // 剩余区
        remainder_section();
    }
}

// 进程1的代码
void process1() {
    while (true) {
        // 进入区：先设置自己的标志
        flag[1] = true;

        // 检查其他进程是否也想进入
        while (flag[0]) {
            // 如果进程0也想进入，等待
        }

        // 临界区
        critical_section();

        // 退出区：清除自己的标志
        flag[1] = false;

        // 剩余区
        remainder_section();
    }
}

// 全局变量
bool flag[2] = {false, false};  // 标志数组，表示进程是否想进入临界区
int turn = 0;                   // 轮转变量，0表示进程0可以进入，1表示进程1可以进入

// 进程0的代码
void process0() {
    while (true) {
        // 进入区
        flag[0] = true;          // 1. 声明自己想进入
        turn = 1;                // 2. 主动让给进程1

        // 3. 等待条件：进程1不想进入 或 轮到自己
        while (flag[1] && turn == 1) {
            // 忙等待
        }

        // 临界区
        critical_section();

        // 退出区
        flag[0] = false;

        // 剩余区
        remainder_section();
    }
}

// 进程1的代码
void process1() {
    while (true) {
        // 进入区
        flag[1] = true;          // 1. 声明自己想进入
        turn = 0;                // 2. 主动让给进程0

        // 3. 等待条件：进程0不想进入 或 轮到自己
        while (flag[0] && turn == 0) {
            // 忙等待
        }

        // 临界区
        critical_section();

        // 退出区
        flag[1] = false;

        // 剩余区
        remainder_section();
    }
}

// 伪代码示例，实际由硬件逻辑实现，这里仅作描述性展示
void process_critical_section() {
    disable_interrupts();  // 进入区：关闭中断

    // 临界区：这段代码不会被其他进程打断
    shared_resource++;
    critical_operation();

    enable_interrupts();  // 退出区：恢复中断
}

// 伪代码示例，实际由硬件逻辑实现，这里仅作描述性展示
bool test_and_set(bool *lock) {
    bool old = *lock;   // old 用于存放锁的旧值
    *lock = !old;       // 无论之前是否已加锁，都将锁设置为新值
    return old;         // 返回锁的旧值
}

// 伪代码示例，实际由硬件逻辑实现，这里仅作描述性展示
void swap(bool *a, bool *b) {
    bool temp = *a;
    *a = *b;
    *b = temp;
}

bool key = true;

void process() {
    // 进入区
    while (key != false) {
        // 忙等待
        swap(&lock, &key);
    }

    // 临界区
    critical_section();

    // 退出区
    lock = false;
}

typedef struct {
    volatile bool available;  // true = 可用, false = 不可用
} spinlock_t;

// 获取锁
void acquire(spinlock_t *lock) {
    // 检查锁是否可用，如果不可用则忙等待
    while (!lock->available) {
        // 忙等待
    }
    // 退出循环 = 成功获得锁，原子地设置为不可用
    // 在实际硬件实现中，从检查到设置必须是原子操作（如 TS 指令）
    lock->available = false;
}

// 释放锁
void release(spinlock_t *lock) {
    // 原子地将 available 设置为 true（释放锁）
    // 实际实现中需要使用硬件原子指令（如 __sync_lock_release）
    lock->available = true;
}

// 使用示例
spinlock_t my_lock = {true};  // 初始化为可用

void thread_function() {
    acquire(&my_lock);  // 获取锁

    // 临界区：安全地访问共享资源
    critical_section();

    release(&my_lock);  // 释放锁
}

void wait(S) {   // 相当于进入区
    while (S <= 0) {
            // 若资源不足等待
    }
    S--;    // 若资源充足，则占用一个资源
}

void signal(S) {   // 相当于退出区
    S++;      // 使用完毕，释放一个资源
}

typedef struct {
    int value;
    struct process *list;
} semaphore_t;

void wait(semaphore_t *sem) {   // 相当于申请资源
    sem->value--;
    if (sem->value < 0) {
        add_to_queue(sem->list, current_process);   // 将当前进程加入该资源的等待队列
        block(sem->list);   // 调用 block 原语进行自我阻塞
    }
}

void signal(semaphore_t *sem) {   // 相当于释放资源
    sem->value++;
    if (sem->value <= 0) {
        remove_from_queue(pop(sem->list));   // 从等待队列中移除第一个进程
        wakeup(pop(sem->list));   // 调用 wakeup 原语唤醒等待队列中的第一个进程
    }
}

semaphore_t mutex = {1}; // 初始化为 1，表示资源可用

void process0() {
    wait(&mutex);       // 准备访问临界资源，加锁
    critical_section();
    signal(&mutex);     // 访问完毕，释放锁
}

void process1() {
    wait(&mutex);       // 准备访问临界资源，加锁
    critical_section(); // 临界区
    signal(&mutex);     // 访问完毕，释放锁
}

semaphore_t S = {0}; // 初始化为 0

void process0() {
    critical_section0();
    signal(&S);
}

void process1() {
    wait(&S);
    critical_section1();
}

semaphore_t S12 = 0;
semaphore_t S13 = 0;
semaphore_t S24 = 0;
semaphore_t S25 = 0;
semaphore_t S36 = 0;
semaphore_t S56 = 0;
semaphore_t S46 = 0;

void process1() {
    critical_section1();
    signal(&S12);
    signal(&S13);
}

void process2() {
    wait(&S12);
    critical_section2();
    signal(&S24);
    signal(&S25);
}

void process3() {
    wait(&S13);
    critical_section3();
    signal(&S36);
}

void process4() {
    wait(&S24);
    critical_section4();
    signal(&S46);
}

void process5() {
    wait(&S25);
    critical_section5();
    signal(&S56);
}

void process6() {
    wait(&S36);
    wait(&S46);
    wait(&S56);
    critical_section6();
}

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

void producer() {
    while (true) {
        // 生产一个产品
        wait(&empty);       // 等待空闲缓冲区
        wait(&mutex);       // 进入临界区
        put_into_buffer();  // 将产品添加到缓冲区
        signal(&mutex);     // 退出临界区，释放临界区互斥信号量
        signal(&full);      // 增加满缓冲区数量
    }
}

void consumer() {
    while (true) {
        wait(&full);        // 等待满缓冲区
        wait(&mutex);       // 进入临界区
        get_from_buffer();  // 从缓冲区中取出产品
        signal(&mutex);     // 退出临界区，释放临界区互斥信号量
        signal(&empty);     // 增加空闲缓冲区数量
    }
}

semaphore_t mutex = 1;  // 计数器互斥信号量
semaphore_t rw_mutex = 1;  // 读者-写者互斥信号量
int reader_count = 0;  // 读者计数器

void writer() {
    wait(&rw_mutex);
    write_shared_resource();
    signal(&rw_mutex);
}

void reader() {
    wait(&mutex);               // 访问计数器，加锁
    reader_count++;
    if (&reader_count == 0) {   // 当第一个读者读取共享资源时
        wait(&rw_mutex);        // 阻止写者访问
    }
    reader_count++;             // 读者计数器加一
    signal(&mutex);             // 释放计数器，解锁

    read_shared_resource();

    wait(&mutex);
    reader_count--;
    if (&reader_count == 0) {   // 当最后一个读者读取共享资源时
        signal(&rw_mutex);      // 允许写者访问
    }
    signal(&mutex);
}

int reader_count = 0;           // 读者计数器
semaphore_t writer_mutex = 1;   // 写者优先互斥信号量
semaphore_t rw_mutex = 1;       // 读者-写者互斥信号量
semaphore_t mutex = 1;          // 计数器互斥信号量

void writer() {
    while (true) {
        wait(&writer_mutex);    // 无写者时请求进入
        wait(&rw_mutex);        // 阻止读者访问
        write_shared_resource();
        signal(&rw_mutex);
        signal(&writer_mutex);
    }
}

void reader() {
    while (true) {
        wait(&writer_mutex);    // 无写者时请求进入
        wait(&mutex);           // 访问计数器，加锁
        if (&reader_count == 0) {   // 当第一个读者读取共享资源时
            wait(&rw_mutex);        // 阻止写者访问
        }
        reader_count++;             // 读者计数器加一
        signal(&mutex);             // 释放计数器，解锁
        signal(&writer_mutex);      // 允许写者访问

        read_shared_resource();

        wait(&mutex);               // 访问计数器，加锁
        reader_count--;             // 读者计数器减一
        if (&reader_count == 0) {   // 当最后一个读者读取共享资源时
            signal(&rw_mutex);      // 允许写者访问
        }
        signal(&mutex);             // 释放计数器，解锁
    }
}

semaphore_t chopstick[5] = {1, 1, 1, 1, 1}; // 筷子互斥访问信号量
semaphore_t mutex = 1;      // 哲学家取筷子互斥信号量

void philosopher(int i) {   // i 号哲学家
    do {
        wait(&mutex);       // 请求取筷子
        wait(&chopstick[i]); // 请求取左边筷子
        wait(&chopstick[(i + 1) % 5]); // 请求取右边筷子
        signal(&mutex);       // 释放取筷子互斥信号量

        eat();

        signal(&chopstick[i]); // 释放左边筷子
        signal(&chopstick[(i + 1) % 5]); // 释放右边筷子

        think();
    } while (true);
}

monitor name {  // 管程名称
    // 共享数据结构说明
    struct ShareData;

    // 初始化语句
    init() {
        // 初始化共享数据结构
        S = 5;    // 初始化资源数量
        // ...
    }

    // 对该数据结构进行操作的一组过程
    take_away() {
        S--;    // 申请资源
        // ...
    }
    put_back() {
        S++;    // 归还资源
        // ...
    }
    ...
}

monitor name {  // 管程名称
    // 共享数据结构说明
    struct ShareData;
    condition_t condition0;
    condition_t condition1;
    // ...

    // 初始化语句
    init() {
        // 初始化共享数据结构
        S = 5;    // 初始化资源数量
        // ...
    }

    // 对该数据结构进行操作的一组过程
    take_away() {
        if (S <= 0) {
            wait(condition0);
        }
        if (condition1_verifiy()) {
            wait(condition1);
        }
        S--;    // 申请资源
        // ...
    }
    put_back() {
        S++;    // 归还资源
        if (!&condition0.empty()) {    // 如果条件变量等待队列不为空，则唤醒一个进程
            signal(condition0);
        }
        if (!&condition1.empty()) {    // 如果条件变量等待队列不为空，则唤醒一个进程
            signal(condition1);
        }
        // ...
    }
    ...
}