一. 基本概念

1.两大核心

• 进程同步 Synchronization（直接制约） 多个进程为完成共同任务相互协作，需要协调执行次序、互相等待传递消息形成的制约关系，本质前驱后继逻辑，同步信号量初值一般为 0。
• 进程互斥 Mutual Exclusion（间接制约） 进程竞争临界资源产生的制约关系，一个进程进入临界区，其余进程必须等待，互斥是同步的特例，互斥信号量初值固定为 1。

2.四大同步准则

• 空闲让进（前进准则） ：临界区空闲时，请求进入的进程必须立刻允许进入。
• 忙则等待 ：当已有进程进入临界区时，其他进程必须等待，确保互斥访问。
• 有限等待 ：任何进程从发出请求到进入临界区的时间必须有上界，不能无限等待。
• 让权等待 ： 进程无法进入临界区时主动放弃 CPU，防止忙等。

3.相关概念

• 临界资源 Critical Resource 一段时间内只允许一个进程访问使用的资源（硬件、共享变量）。
• 临界区 Critical Section 每个进程内部访问临界资源的那段代码区域。
• 竞争条件 Race Condition（竞态条件） 多个进程并发读写共享数据，运行结果依赖进程调度顺序。
• 原子操作 Atomic Operation 不可分割、执行过程不能被中断的操作。
• 信号量 Semaphore 用来实现同步与互斥的变量，分为整型信号量、记录型信号量，仅能通过 PV 原语访问。
• P 操作 wait /down（申请资源） 信号量自减 1，若值小于 0，当前进程阻塞并插入等待队列。
• V 操作 signal /up（释放资源） 信号量自加 1，若值小于等于 0，唤醒等待队列中的一个进程。
• 阻塞 Block 进程放弃 CPU，由运行态转入阻塞态，进入阻塞队列。
• 唤醒 Wakeup 将阻塞态进程移出阻塞队列，转入就绪队列。
• 忙等待（忙等）Busy Waiting 进程一直循环检测标志，不放弃 CPU，整型信号量存在忙等，记录型消除忙等。
• 死锁 Deadlock 一组进程各自占有对方所需资源，相互循环等待，若无外力干预永远无法向前推进。
• 饥饿 Starvation 进程长期得不到调度，无限等待资源，不存在资源环路等待，一般由调度不公平导致。

二. P操作与V操作

1.P操作（wait ()，申请资源）

1.1  核心动作

S.value = S.value - 1（自减）

1.2  分两种情况：

• 减完后 S.value ≥ 0：还有剩余资源，进程直接进入临界区执行；
• 减完后 S.value ＜ 0：当前无可用资源，S.value 的绝对值 = 阻塞队列里等待该资源的进程数量，当前进程调用阻塞原语 wakeup 的反向：block()，进入信号量的阻塞队列休眠。

1.3 伪代码

typedef struct{
   int value;
   struct process *L;
}semaphore

wait (S):
   S.value--;
   if(S.value<0){
      add this process to S.L;
      block;
   }

2.V操作（signal ()，释放资源）

2.1 核心操作

S.value = S.value + 1

2.2 判断逻辑

• 自增后如果 S.value ≤ 0，说明阻塞队列里还有进程在等资源，需要调用wakeup()唤醒队首一个阻塞进程；;
• 若 S.value > 0：无等待进程，直接结束 V 操作。

2.3 伪代码

typedef struct{
   int value;
   struct process *L;
}semaphore;

signal(S):
  S.value ++;
  if(S.value <= 0){
   remove a process P from S.L;
   wakeup(P);
   }   

三 . 三大经典同步问题

1.有限缓冲问题（生产者-消费者）Bounded-Buffer Problem (Producer-Consumer)

• 场景：生产者（Producer）放数据到有限大小的缓冲区（Buffer），消费者（Consumer）取数据。需保证满时生产者停，空时消费者停。

• 共享数据（Shared Data）：

  • mutex = 1（互斥信号量，保护缓冲池） – Mutex Semaphore

  • full = 0（满位计数） – Full Semaphore

  • empty = n（空位计数，n为缓冲区大小） – Empty Semaphore

• 核心思路：
  生产者先 wait(empty) 申请空位，消费者先 wait(full) 申请满位；二者都需 wait(mutex) 互斥访问缓冲池，操作完后分别 signal(full) / signal(empty)。

• 伪代码：

生产者伪代码（Producer Process）：
while(1){
  produce an item in nextp; //生产产品
  wait(empty);             //申请空位
  wait(mutex);            //申请缓冲池互斥
  add nextp to buffer;   // 放入产品
  signal(mutex);        // 释放缓冲池
  signal(full);        // 增加满位计数
 }
消费者伪代码（Consumer Process）：
while(1){
  wait(full);                       // 申请满位数据  
  wait(mutex);                     // 申请缓冲池互斥
  remove an item to nextc;        // 取出产品
  signal(mutex);                 // 释放缓冲池
  signal(empty);                // 增加空位计数 
  consume the item in nextc;   // 消费产品
 }

2.读者-写者问题Readers-Writers Problem

• 场景：共享数据对象，读者（Reader）只读，写者（Writer）会修改。要求写者与任何人互斥，但多个读者可同时读。读者优先指只要有读者在读，写者就得等。

• 共享数据（Shared Data）：

  • mutex = 1（保护 readcount 更新） – Mutex for readcount

  • wrt = 1（写者与第一个/最后一个读者互斥） – Semaphore for writer

  • readcount = 0（当前读者数） – Reader count

• 核心思路：第一个读者进入时 wait(wrt) 阻止写者，最后一个读者离开时 signal(wrt) 唤醒写者；mutex 保证 readcount 安全增减。

• 伪代码：

写者进程（Writer Process）：
  wait(wrt);               // 申请写权限
  writing is performed;    // 执行写操作
  signal(wrt);             // 释放写权限
读者进程（Reader Process）：
  wait(mutex);             // 保护 readcount
  readcount++;
  if (readcount == 1) 
     wait(wrt);           // 第一个读者阻止写者
  signal(mutex);

  reading is performed;   // 执行读操作（可多个读者同时）

  wait(mutex);
  readcount--;
  if (readcount == 0) 
     signal(wrt);         // 最后一个读者唤醒写者
  signal(mutex);

wait(wrt) 只是抢占读写互斥权，和计数器锁 mutex 无关， wrt 管的是 “能不能读写文件”；mutex 只管 “能不能改 readcount 数字”，两套独立锁不能嵌套持有

3.哲学家就餐问题 Dining-Philosophers Problem

• 场景：5位哲学家围坐，每人左右各一根筷子，必须同时拿到两根才能吃饭。模拟多进程竞争有限资源，需避免死锁和饥饿。

• 方案1（可能死锁）  每人先拿左筷再拿右筷，若同时伸手则全部阻塞。

  • 共享数据：chopstick[5] = {1,1,1,1,1}（每根筷子是互斥信号量）

  • 伪代码（含死锁风险）：

    do {
        wait(chopstick[i]);                  // 拿左筷
        wait(chopstick[(i+1) % 5]);          // 拿右筷
        eat;                                 // 进餐
        signal(chopstick[i]);                // 放左筷
        signal(chopstick[(i+1) % 5]);        // 放右筷
        think;                               // 思考
    } while (1);

• 方案2（避免死锁）增加一个协调信号量 coord = 4，限制最多4位哲学家同时尝试拿筷子，保证至少一人能拿到两根。

  • 额外共享数据：coord = 4（Coordination Semaphore）

  • 伪代码（死锁自由）：

    do {
        wait(coord);                         // 限制并发尝试人数（最多4人）
        wait(chopstick[i]);                  // 拿左筷
        wait(chopstick[(i+1) % 5]);          // 拿右筷
        eat;                                 // 进餐
        signal(chopstick[i]);                // 放左筷
        signal(chopstick[(i+1) % 5]);        // 放右筷
        signal(coord);                       // 释放名额，允许其他人尝试
        think;                               // 思考
    } while (1);