系列文章目录进程同步之硬件同步机制、信号量机制文章目录系列文章目录前言一、什么是管程面向对象的思想封装条件变量二、条件变量conditon三、管程大幅降低死锁概率的精髓四、管程的两种经典模型五、管程的底层实现管程区别于信号量管程区别于进程六、管程优化管程优化之超时机制管程优化之广播原语七、哲学家就餐问题前言对于此前介绍的机制由于每个访问临界资源的进程都必备同步操作P、V使得大量的同步操作分散在各个进程中给系统管理带来麻烦还可能导致系统死锁。因此引入新的进程同步工具——管程 Monitors监视器核心是将共享资源、操作共享资源的函数、同步机制封装成一个 “黑盒”让程序员无需关心底层的P/V操作就能安全地实现进程同步。一、什么是管程定义 一个数据结构和能为并发进程所执行在该数据结构上 的一组操作这组操作所能同步进程和改变管程中的数据管程是一个抽象数据类型组成如下管程的名称Monitor 自定义的管程名字共享数据结构抽象地表示系统中的共享资源对共享数据结构的操作定义为一组过程函数进程对共享资源的申请、释放和其他操作都需要通过这组过程即对共享数据结构操作的过程外部进程无法直接访问共享数据同步机制条件变量 wait/signal隐式互斥锁 条件变量wait()/signal()代替手动P/V操作面向对象的思想封装条件变量1.互斥执行共享资源的数据结构、过程、同步机制集中封装在一个对象内部这些东西仅能被封装于管程内的进程访问且最多只能有一个进程在管程内执行任何函数。相当于管程自带一个 “隐式互斥锁”进程进入管程时自动加锁退出时自动解锁。这就避免了程序员忘记加锁 / 解锁的问题信号量的常见坑。2.条件同步进程在管程内若不满足执行条件需通过条件变量阻塞放到队列中等待同时释放管程的互斥锁此时其他进程可再次调用管程函数满足条件后被唤醒重新获取互斥锁继续执行。相当于进程在管程外部运行通过调用管程的公开函数如insert()来操作共享资源。同时管程在内部自动处理同步和互斥也就是为什么说像一个“黑盒”二、条件变量conditon条件变量是管程内的一个抽象对象只有wait()和signal()两个操作,用于管程中的同步。根据阻塞或挂起的原因不同可设置多个条件变量每个条件变量保存了一个链表用于记录因该条件变量阻塞的所有进程。condition c //管程内定义条件变量其核心操作c.wait()当前进程阻塞放入条件变量c的等待队列;自动释放管程的互斥锁让其他进程进入管程;然后重新竞争管程的互斥锁拿在这里插入代码片到锁后才能执行“阻塞 释放锁”—— 管程避免死锁的核心c.signal()唤醒条件变量c等待队列中的一个进程或所有进程被唤醒进程不会立即执行需等待当前进程退出管程、释放互斥锁后再竞争锁类似于V操作但不会立即释放锁这里以一个打印机的实际代码例子便于理解管程封装和条件变量// 1. 定义管程名字monitor PrinterMonitor{// 第一部分封装共享资源 // 共享资源1打印机的状态true空闲false忙碌boolis_freetrue;// 共享资源2等待打印的进程数intwait_count0;// 第二部分封装同步机制条件变量 // 条件变量表示“打印机空闲”这个条件 → 进程等待这个条件成立condition a;// 第三部分封装操作共享资源的函数核心 // 函数1申请打印机外部进程调用这个函数来使用打印机publicvoidacquire_printer(){// 管程自动加锁隐式互斥锁→ 同一时间只有一个进程能进这个函数// 检查条件打印机是否忙碌while(!is_free){// 打印机忙说明该申请进程需要等待等待数加一wait_count;a.wait();//等待“打印机空闲”wait_count--;//若有被唤醒从wait()里出来因此也要--}// 退出while后说明该进程已经占用打印机is_freefalse;// 管程自动解锁隐式互斥锁→ 其他进程可以进入函数}// 函数2释放打印机外部进程用完后调用publicvoidrelease_printer(){// 管程自动加锁// 进程用完释放打印机 → 标记为空闲is_freetrue;// 唤醒等待“打印机空闲”的进程a.signal();// 关键操作唤醒等待的进程// 管程自动解锁}}场景一此时如果进程 A先 申请打印机假如名字是pm进程 A调用 pm.acquire_printer() → 管程自动加锁。不会执行 wait()把 is_free 设为 false占用打印机→ 管程自动解锁。进程 A 开始打印。 场景二进程 B 申请打印机 进程 B 调用 pm.acquire_printer() → 管程自动加锁。此时is_freefalse打印机忙 进入 while 循环。执行a.wait()→ 这个操作做了3件事1.阻塞进程 B把进程 B 放入 a 的等待队列暂停执行。2.堵塞同时释放了管程锁允许其他进程比如后续的进程 C调用管程函数但它们也会因为打印机忙而等待。3.等待被唤醒进程B此时就停在了a.wait()里面直到被 signal() 唤醒。 场景三进程 A 释放打印机当进程 A 打印完成调用 pm.release_printer() → 管程自动加锁。把 is_free 设为 true。然后执行a.signal()→ 这个操作做了2件事1.唤醒进程 B把等待队列里的进程 B 移到 “就绪队列”标记为 “可以继续执行”。2.不立即释放锁进程 A 继续执行完函数管程才自动解锁。 最后等进程 A 退出函数 → 管程解锁。三、管程大幅降低死锁概率的精髓死锁的必要条件之一是“占有并等待”进程持有一个资源同时等待另一个资源。信号量的死锁几乎都源于这个条件首先管程只有一把全局隐式锁也是保证了同一时间只能有一个进程在管程内进程使用管程的任何函数以及进程执行wait()→ 自动释放这把锁。而进程退出管程的任何函数 → 自动释放这把锁。正因为有了这把锁导致两个进程在占有资源同时申请使用对方资源然后进入wait()被堵在对方的队列时此时这把锁是释放的在两个进程对峙的同时给了“第三方进程” 的机会只有当没有第三方进程时才会陷入业务逻辑死锁并非信号量那种无法挽救的机制性死锁。四、管程的两种经典模型1. Hoare 模型强语义规则执行c.signal()的进程立即阻塞释放管程锁让被唤醒的进程优先执行被唤醒进程执行完后再唤醒原来的进程。特点严格保证唤醒顺序同步逻辑精准但上下文切换次数多效率稍低2.Mesa 模型弱语义主流规则执行c.signal()的进程继续执行被唤醒的进程只是从等待队列移到就绪队列等待当前进程退出管程后release再竞争互斥锁。特点上下文切换少效率高是现代操作系统如 Java 的synchronized、Linux 的 pthread 条件变量的默认模型。注意被唤醒的进程需要重新检查条件因为条件可能再次不满足所以通常用while循环判断条件而非if。这里Mesa模型也叫Lampson/Redell模型上图中的Hansen 模型是另一位学者的早期尝试理论上有区别但因为逻辑相似都用 while在很多基础教材里会被合并讲解或者直接统称 Mesa 管程包含了 Hansen 的改进思想。现代工业标准标准多用Mesa模型。Mesa管程优于 Hoare 管程1.Hoare 管程的缺陷在于其用if判断条件如果有错误地发出了signal()/broadcast()被唤醒的进程不会重新检查条件直接执行临界区代码就会导致数据错乱、程序崩溃。而Mesa模型由于使用了 while 结构一个进程不正确地广播或发信号不会导致收到信号的程序出错。收到信号的程序将检查相关的变量若期望的条件得不到满足它会继续等待。2.Hoare 管程的signal()隐含了一个承诺「我已经满足了你的所有需求你直接执行就行」难以考虑到2级条件。而Mesa模型的进程只需要管 1 级条件不需要关心每个进程的 2 级条件因为每个被唤醒的进程自己通过while循环检查自己的 2 级条件满足就执行不满足就继续等。其2级条件完全隐藏在等待进程自己的代码里改需求的时候只需要改等待进程的代码不需要改动发信号的进程完全符合数据抽象和模块化的软件工程原则代码更好维护、扩展性更强。1 级条件条件变量本身的基础条件比如「缓冲区有空闲」「内存有空闲」是发信号的进程能直接控制的条件。2 级条件每个等待进程自己的个性化需求比如「缓冲区的字符数≥我要消费的数量」「空闲内存≥我要申请的大小」不同进程的需求不一样发信号的进程很难全部知道。五、管程的底层实现可以把管程看作是“用信号量包装出来的高级工具”操作系统内核里并没有管程的原生支持它的两个核心组件隐式互斥锁、条件变量都是用信号量实现的。1.用互斥信号量实现管程锁管程的 “同一时间只能一个进程进入”本质是一个互斥信号量mutex初始值为 1。// 管程底层的互斥信号量semaphore mutex1;// 进程进入管程 → 加锁P(mutex);// 进程退出管程 → 解锁V(mutex);2.用同步信号量 等待队列实现 “条件变量”每个条件变量c底层对应两个东西一个同步信号量sem_c初始值为 0用于阻塞进程。一个计数器count_c初始值为 0记录等待队列的进程数// 条件变量 打印机a 的底层结构semaphore sem_not_full0;// 同步信号量用于阻塞intcount_not_full0;// 等待队列的进程数// 实现 a.wait()voida_wait(){count_not_full;// 等待进程数1V(mutex);// 释放管程的互斥锁P(sem_not_full);// 阻塞当前进程sem_not_full0count_not_full--;// 被唤醒后等待进程数-1}// 实现 a.signal()voida_signal(){if(count_not_full0){V(sem_not_full);// 唤醒一个进程sem_not_full1}}我们在写管程代码时不用关心这些底层的信号量细节。操作系统或编程语言的库已经帮我们封装好了这些逻辑。管程区别于信号量管程机制底层是基于信号量实现相当于是把P/V、block、wakeup封装到条件变量的wait()/signal()中管程再封装共享资源 条件变量 操作函数管程区别于进程1.操作不同进程由顺序程序执行有关操作管程主要进行同步操作和初始化操作2.进程是主动工作方式管程被进程调用以实现对共享数据结构的操作属于被动工作方式3.进程可并发执行管程不能与其调用者并发4.进程具有动态性管程是一个资源管理模块供进程调用六、管程优化管程优化之超时机制之前我们讲的wait()操作进程会一直阻塞在条件变量的等待队列里直到收到signal()才会被唤醒。如果本该发信号的进程意外崩溃 / 退出了等待的进程就会无限期阻塞陷入 “饥饿” 状态。超时机制就是给wait()操作加一个超时时间进程等待超过这个时间就算没收到signal()也会自动被唤醒退出等待队列。从根源上避免进程无限等待提升系统的鲁棒性。管程优化之广播原语我们之前讲的signal()只能唤醒等待队列里的 1 个进程但很多场景下发信号的进程不知道该唤醒谁、需要唤醒多少个单个signal()无法满足需求。而广播原语即broadcast会唤醒当前条件变量等待队列里的所有进程让所有等待的进程都被唤醒自己去检查条件是否满足。以内存分配这个场景为例子内存有j个空闲字节一个进程释放了k个字节现在总共有jk个空闲内存。但发信号的进程不知道哪个等待的进程需要的内存小于等于jk。用signal()随机唤醒一个进程万一这个进程需要的内存比jk大还是无法分配其他需要小内存的进程也没被唤醒。而用broadcast唤醒所有等待内存的进程每个进程自己检查空闲内存够不够自己的需求够就分配不够就继续等待。七、哲学家就餐问题该问题是操作系统中最经典的进程同步与死锁问题由艾兹格・迪杰斯特拉Edsger Dijkstra于 1965 年提出。问题内容是有五个哲学家共用一张圆桌分别坐在周围的五张椅子上在圆桌上有五个碗和五支筷子他们的生活方式是交替地进行思考和进餐。规则只有拿到左手和右手两根筷子才能吃饭。吃完饭后放下两根筷子继续思考。互斥关系分析 筷子临界资源同一时刻只能有一个哲学家进程拿起筷子同步关系分析 就餐只有获得两个筷子后才能进餐死锁情况如果每个哲学家都拿起一只筷子全部等待另一支都饿死并行程度五只筷子允许两人同时进餐解决方案一破坏死锁的 “请求并保持” 必要条件。规定哲学家必须同时申请左右两根筷子要么两根都拿到要么一根都不拿。使用AND 型信号量机制Swait。对左右两根筷子同时进行 P 操作。缺点资源利用率低。比如只有两根筷子但两个哲学家都想吃其中一个得等资源闲置时间变长。semaphore chopstick[5]{1,1,1,1,1};do{....//思考Swait(chopstick[(i1)%5],chopstick[i]);//进餐Signal(chopstick[(i1)%5],chopstick[i]);}while(true);解决方法二给 5 根筷子编号为 1, 2, 3, 4, 5。规定哲学家必须先申请编号小的筷子再申请编号大的筷子。特例如果是 5 号筷子最右边和 1 号筷子最左边相邻也是先拿 1 号再拿 5 号。效果假设 5 个哲学家同时饿了依次拿到左边编号小的那个筷子但是一号哲学家与五号哲学家是共同争取编号为1的筷子这就导致两个人总有一个拿不到筷子那么自然也就多余一个筷子打破了循环链的等待最终总会有人拿到2根用完然后释放。// 定义5根筷子作为互斥信号量初值均为1semaphore chopstick[5]{1,1,1,1,1};// 哲学家 i 的代码voidphilosopher(inti){while(true){think();// 思考// 核心逻辑按编号顺序申请 intlefti;intright(i1)%5;// 保证总是先申请编号小的后申请编号大的if(leftright){swap(left,right);// 交换变量强制从小到大}P(chopstick[left]);// 先拿小号P(chopstick[right]);// 后拿大号eat();// 吃饭V(chopstick[right]);// 释放大号V(chopstick[left]);// 释放小号}}解决方法三最多允许 4 位哲学家同时去拿筷子破坏 “互斥” 或 “资源不足”原理限制并发数。既然 5 个人会死锁那只允许 4 个人同时去竞争筷子保证了至少有一位哲学家能左右筷子都拿到并开始吃饭打破了僵局。设置一个信号量count 4。每个哲学家想去吃饭前必须先执行P(count)申请一个 “名额”。只有拿到名额才能去拿筷子吃饭吃完释放筷子后执行Vcount释放名额。semaphore chopstick[5}{1,1,1,1,1};//各信号量初始化为1semaphore count4哲学家活动描述为:Do{wait(count);wait(chopstick[i]);wait(chopstick[(i1)%5]);// 吃饭signal(chopstick(i);signal(chopstick[(i1)%5]);signal(count);//思考}while(TRUE);