一. 基本概念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.value0){ add this process to S.L; block; }2.V操作signal ()释放资源2.1 核心操作S.value S.value 12.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 Datamutex 1互斥信号量保护缓冲池 – Mutex Semaphorefull 0满位计数 – Full Semaphoreempty 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 Datamutex 1保护readcount更新 – Mutex for readcountwrt 1写者与第一个/最后一个读者互斥 – Semaphore for writerreadcount 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[(i1) % 5]); // 拿右筷 eat; // 进餐 signal(chopstick[i]); // 放左筷 signal(chopstick[(i1) % 5]); // 放右筷 think; // 思考 } while (1);方案2避免死锁增加一个协调信号量coord 4限制最多4位哲学家同时尝试拿筷子保证至少一人能拿到两根。额外共享数据coord 4Coordination Semaphore伪代码死锁自由do { wait(coord); // 限制并发尝试人数最多4人 wait(chopstick[i]); // 拿左筷 wait(chopstick[(i1) % 5]); // 拿右筷 eat; // 进餐 signal(chopstick[i]); // 放左筷 signal(chopstick[(i1) % 5]); // 放右筷 signal(coord); // 释放名额允许其他人尝试 think; // 思考 } while (1);