那接下来我们讲一下
管程和条件变量的设计与实现
首先我们再回顾一下管程的原理
管程的定义是什么呢
管程是一个特殊的结构
在这里面包含了几部分内容
第一部分是共享变量shared data
这是需要互斥访问的
第二部分呢是条件变量
那是说当在里面某些操作中
有可能某些条件满足或者不满足
它会做相应一个等待
或者唤醒的一个操作
第三个呢是并发执行的进程
在这里面有一系列操作呢
它需要互斥去完成
然后有一些进程可以进来
来完成相应的一些操作
而这些操作可以并发来执行
但需要保证
对共享变量的访问是互斥的
第四个在管程做相应的启动之前呢
它需要有一系列初始化过程
这有一些共享变量初始化值
以及对条件变量
也有一定的初始化的一些要求
那我们既然讲了大致原理之后呢
我们看看怎么来定义这个管程
那么管程其实主要用在
一些高级语言里面
会有管程的一个设计与实现
包括对它的使用
在操作系统里面
这上面的使用稍微少一些
我们看看在ucore lab里面
怎么来完成这个管程的设计与实现
首先我们对它要定义一个数据结构
这是一个管程数据结构的定义
那它有一个mutex
来保证对这些操作互斥的执行
需要注意这些操作里面
是包含了对共享变量的一些访问
所以需要互斥
第二个呢有一个next和next_count
next是一个semaphore（信号量）
next_count是一个int（整型）
这一块的具体解释
我们在后面随着进一步的展开
会给大家做进一步的讲解
第三个cv就是条件变量
对某些条件是否满足的
所需要条件变量
它类比我们这个信号量
但和信号量的具体实现是有不同的
这就构成了一个所谓的管程
好 讲了数据结构之后
我们看它大致的实现
这个管程里面各个操作呢
是以函数形式存在的
function_in_monitor 对应这里面
一个一个的操作
好在这个操作里面
我们可以看到
首先在操作开始和结束
它有一个sem.wait
和sem_signal
类似于信号量的P操作
和信号量的V操作
从而可以确保中间的一些
对共享变量的访问
是一种互斥的操作
在这里面如果对某一个条件的判断
发觉条件能够满足
我们就会做cond_signal
或者做进一步的操作
如果条件不能满足
那我们就需要做cond_wait
来完成一个等待
这个是用到了条件变量
这是通常位于管程中的一个操作
所要完成的一个流程
另外呢我们也可以看到
在管程里面有两个特殊的信号量
和跟信号量相匹配的一个
next_count这么一个记录
这个记录和这里面的操作
是有对应关系的
它的具体含义
我们会在后面进一步展开讲解
这里面就不展开了
好 那我们来看一下
关于条件变量的一个定义
那我们知道条件变量和管程
是有一个紧密联系的
应该说条件变量
是管程重要的组成部分
根据我们原理课的介绍呢
我们可以知道条件变量
这个是它的一个数据结构定义
包含了等待在条件变量上的
进程的个数
第二是等待队列
这是它的一个数据结构
同时它也有一个wait操作
和一个signal操作
wait操作是什么意思呢
就说当一个条件得不到满足之后
我们会让当前线程睡眠
这个所谓睡眠
让它执行一个condition: :wait（条件变量等待）
如果说这个条件得到满足
那么另一个进程或者另一个线程
它会执行一个condition: :signal（条件变量唤醒）
来把这个睡眠的线程给唤醒
这就是它大致一个执行过程
看起来和我们前面讲的
信号量呢很类似
但其实它们在具体实现上
是有比较大的不同
那我们看看原理上这个条件变量
和我们具体的实现之间
是什么样对应关系
可以看出来
这个等待的这个线程个数呢
这里面有个count
和这个numWaiting是对应的
这个等待队列需要注意
在这里面具体的实验上面呢
用的是一个信号量
来代替了这个等待队列
因为大家都知道
前面讲的信号量实验中呢
也用到了等待队列
通过这个方式呢
可以更加灵活来完成
对线程的唤醒
和让它睡眠这么一个操作
另外条件变量和管程之间的关系
通过另外一个monitor
这么一个变量来建立好了
这个条件变量是属于这个管程的
这也是我们说
条件变量是管程重要组成部分
的一个体现
这就是我们说关于条件变量的定义
大致就这么多了
第二个是关于它的两个操作
一个是wait操作
一个是signal操作
对于wait操作而言
我们可以看到它是它的原理部分
它其实对应红色部分呢
就是它的具体实现
比如它对它的numWaiting ++
我们cv.count++是和它对应的
另外呢它会有一个
信号量的signal机制
来完成互斥一个通知
与release(lock)是对应的
最后呢sem_wait和schedule是对应的
可以看出来
对原理部分一些描述呢
基本上在我们具体实验中有涉及
但是需要注意还有很多地方
是没有涉及的
那这个需要结合我们signal一起来看
比如说前面讲到numWaiting--这个操作
其实在前面的waiting这个地方
做了一个相应的实现
而对于其它部分
比如说要判断
numWaiting是否大于0
这里面是判断了什么
cv.count是否大于0
这里面wakeup唤醒操作呢
在我们这里面是
信号量一个signal操作
起到一个唤醒一个作用
但是也一样可以看到
非红色部分呢
这些操作在这里面
没有直接的对应关系
那这意味着什么呢
其实这说明了我们原理
和我们具体实现
还是有比较大一个区别
这个区别呢我们在后面具体实验中
给大家逐一展开讲解
那我们以两个线程来做一个表述
假设我们存在两个线程
都想对一个管程
进行一个相应的操作
首先线程A先进入管程
然后在进入之后呢
通过对共享变量的访问
发现某个条件不满足
那么它会执行一个条件等待
我们说条件变量的等待
这是线程A的一个大致工作
那么线程B呢它后进入管程
因为前面等待之后呢
很显然另一个进程
它有机会可以进入到
管程里面去执行
进入管程之后
它会设置条件满足
因为它会查询
或者修改共享的变量
然后把条件设成满足
设成满足之后
它就需要把线程A给唤醒
这是线程A和线程B
它大致的执行过程
在这个过程中我们来体会一下
想看一下条件变量是如何有效地
来让进程A和进程B
既互斥 又能够同步地
完成它们各自的工作
这里面可以看出来我们设置是
线程A是在这儿 线程B在这儿
线程A先执行 线程B后执行
它们分别进入到管程里面去
完成各自工作一个过程
这是线程A在管程中
大致执行过程的一个描述
它首先会有一个互斥的一个操作
比如说信号量的mutex
以及对它一个释放操作
这是wait 这是释放
这是保证了中间的
处理过程是互斥的
然后呢它会完成
对共享变量的一些访问
然后判断条件是否满足
如果条件不满足
它会做cond_wait
就是条件变量的等待
这就是关于线程A的一个操作
如果等待满足了它会被唤醒
然后它会退出整个操作执行过程
对进程B而言类似
它有一个互斥信号量的
一个等待和唤醒的一个操作
确保了后续的中间这部分工作呢
是能够互斥完成
如果它发现它对某些共享变量
形成的一个条件
能够让它满足之后呢
它会发出一个cond_signal
这个操作呢会使得前面的线程A
能够被唤醒并继续执行
大家需要注意什么呢
线程A和线程B
它们在进入管程之后呢
只有一个可以去互斥地
访问那些共享变量
所以说当它唤醒完线程A之后呢
其实怎么确保这个互斥性
是有一定讲究的
这也是我们说在具体实验上
和原理上有一些很细微的差别
在我们具体实验中
需要去仔细地去体会
我们来看看一个大致的执行过程
这是线程A的这个wait的
条件变量的一个操作
这是线程B的signal的
一个条件变量的一个操作
这是原理部分的内容
那我们可以跟具体实现对照一下
看看我们的实现是否能够
满足原理的功能
同时呢它和原理
在实现上具体有哪些不同
我们可以第一个看着
既然要等待所以说
对应的线程个数会做一个加操作
那么唤醒的时候
会把这个线程个数做减操作
对应我们具体的
条件变量实现可以看到
这有一个cv.count++ cv.count--
和这两个是对应起来的
这一步是有直接的对应关系
第二个对于条件不满足之后
当前线程它会需要去
做一个等待操作
同时把自己挂到
这个等待队列里面去
这是线程A一个工作
对于线程B而言它后进入
它会发现当前有线程在等待
但它条件也满足了
所以它会把线程A呢
从等待队列里面移出来
同时唤醒线程A
这是它的一个工作过程
那么这个呢也是原理上一个实现
我们看看如果落到具体实现上面
怎么来完成
OK 可以看着先执行线程A
它会做一个等待的时候
会有cv.count++
然后接着它会由于条件不满足
它会做一个sem_wait来完成睡眠
需要注意的是它这里面
用到的信号量是cv.sem
不是管程里面那个信号量
它这儿就睡着了
紧接着呢我们的线程B会继续执行
线程B执行到一定程度之后会发现
条件满足同时有线程正在等待
为什么呢因为cv.count是大于0的
和这个是一致的
如果cv.count>0它会去把这个线程A
从等待队列里面移出来
同时唤醒线程A
那么这里面是用一个sem_signal
就是信号量的一个V操作
来完成对cv.sem的一个处理
那么这两个是匹配的
可以看出来
这一步也是可以和我们原理
是一一对应的
再接下来我们看一下
会发现线程A当它要睡眠的时候
它会把刚才进入管程里面
那个操作那个mutex要给释放掉
这样才能使得其它的进程或者线程
才有机会进入到管程中
去执行对应的一些操作
所以这里面有release(lock)
这么一个操作
在具体实现这上面也存在一个
信号量的一个signal就是V操作
来完成对关于管程那个mutex
的一个释放操作
但是这个和这边
好像没有对应的关系
大家觉得在哪呢
它对应进入P操作在哪呢
其实我们可以看到
在wait具体实现中呢
就是条件变量的具体实现中呢
有一个sem_signal
那么这个signal
其实和我们另一个进程
它的sem_wait是对应起来的
这使得我们线程A
通过执行sem_wait
处于等待状态之后呢
且释放了它所占用的互斥的信号量
就是monitor.mutex的时候
使得其它另外一个线程
比如线程B可以进一步执行
因为线程B这时候
在执行sem_wait的时候
它就可以继续往下走了
这已经被释放了
然后线程B在执行这个
sem_wait之后
它会去查询共享变量
看这个变量所对应条件是否满足
如果满足它会执行cond_signal
就是关于条件变量一个唤醒操作
那么执行这个条件变量唤醒操作之后呢
它可以使得我们的线程A
能够进一步执行
但是这里面有一些
微妙一些处理过程大家需要注意
那我们看一下关于条件变量的signal
它到底做哪些具体的实现
前面我们说到的monitor中
关于我们管程
它有两个特殊的成员变量
一个是next_count（在monitor中）
一个是next信号量（在monitor中）
那么这两者呢
其实我们没有做进一步解释
这里面我们可以展开看一看
当我们发现有线程处于
等待在某个条件变量的时候
它的cv.count是大于0的
一旦大于0它会做进一步的一些操作
比如说
把monitor.next_count做一个加操作
发出signal信号
这是cv.sem
对应的就是wakeup
那它会把另一个我们thread A给唤醒
这是一个正常操作
但是接下来 又做了一个
sem_wait
wait什么呢 是monitor.next
就是在管程中那个next信号量
那做了这个操作
使得自身会陷入睡眠状态
这也就意味着对于原理课上来说的
wakeup(t)这一步操作呢
除了唤醒我们的其他线程之外呢
还把自身给处于一个睡眠状态了
这是sem_wait干的事情
OK 那这个wait之后
谁来唤醒它呢
我们再来看一下
线程A中的一部分实现
线程A中其实有一块判断
如果monitor.next_count>0
那么它就会做一个semaphore的唤醒
唤醒的正好是这边所等待的
monitor.next
貌似thread A可以用来唤醒thread B
但这里面有个时间差的问题
我们先说了
thread A是先执行的
thread B是后执行的
当thread A执行到
sem_wait(cv.sem)的时候
它已经处于睡眠状态了
在这个时候
这个if操作根本没有执行
而我们的thread B
当它执行到sem_wait的时候
它唤醒的thread A在这个地方
thread A可以继续往下走
但是无法再回去执行
所以sem_wait(monitor.next)
不能靠这部分语句来帮它唤醒
那是靠哪来唤醒呢
大家想一想
其实这个唤醒操作
还要看thread A的后续的执行
我们看看当thread A在等待cv
就是等待条件变量
满足了之后呢它会被唤醒
进一步去执行
执行到最后 会注意
在thread A的某一个function中呢
会执行一个
sem_signal的一个操作
而这个操作正好是
执行的是monitor.next
但需要注意的是
执行这个操作有个前提
是monitor.next_count>0
也就意味着这个next_count
其实它的含义是什么呢
含义是发出条件变量signal（操作）的
线程的个数
当某一个线程
比如在这里面我们是thread B
它这个线程
由于发出了条件变量的signal操作
且把自身置于一个睡眠状态
使得被唤醒的线程A呢
有机会在它退出的时候
把线程B给唤醒
唤醒是monitor.next
为什么要这么做
好像把这个问题给复杂化了
其实这是有一定的原因
原因在哪呢
就在于这是管程里面的一个函数
这是管程里面的另一个函数
这是线程B在执行
这是线程A在执行
这两个函数都会涉及到
对共享变量的访问
既然都会涉及到
对动共享变量的访问
那其实根据我们管程的定义呢
只允许一个进程
对这个共享变量进行操作
也就意味着这两个函数中
只有一个可以去执行
另一个只能等待
所以当我们的线程B
把线程A唤醒之后
它自身必须要睡眠
这使得线程A的
对应的函数才能继续执行
才能保证对共享变量的
一个互斥的操作
但是线程A执行完之后
在最后的阶段
它需要把我们的线程B给唤醒
使得线程B能够持续往下走
这样就确保了两个线程
可以对两个不同的操作
互斥地访问
这是它们的一个执行过程
另外我们还要注意一点
在这里面这个mutex出现了多次
那么这个多次呢
其实它有时间顺序
它们之间不会出现
我们说死锁或者说重复的现象
为什么 大家注意一下
以线程A开始执行为例
一开始它要执行
一个mutex的一个wait
就是信号量的一个wait
在0时刻在执行这个地方
执行到wait_cv的时候
它会再次发出一个sem_signal
那么这个sem_signal呢
实际上是把这个信号给释放掉了
这个释放使得我们的
线程B可以执行
那么第三个时刻
就是2标记的时刻呢
会做一个sem_wait
当线程B最后离开的时候呢
又会做一个sem_signal
来完成对这个互斥信号量的
一个释放操作
可以看出来 0 1 2 3
这个呢是确保了
我们的线程A和线程B
互斥地来访问相应的共享变量
或者是访问相应的操作
且不会引起冲突
另外大家还需要注意一点
当线程A被唤醒之后呢
需要注意它这时候位置位于
sem_wait之后这一点
根据我们的原理课的讲解
在这里我们需要重新得互斥锁（monitor.mutex）
但我们在具体实验中
（线程A）并没有重新获得这个互斥锁（monitor.mutex）
那怎么能确保
这个互斥的正确执行呢
那其实是在于线程A这时候
它的互斥是通过线程B的
这个操作来完成的
所以说大家要注意 0 1 2 3
2这一步呢
实际上是帮助我们线程A
继续保证了它后续的操作的互斥性
大家这一点需要理解一下
那我们来看一下
想结合一下线程A
和线程B的执行过程
看看我们这个条件变量的
等待操作和signal操作
它们具体怎么来完成
正确的同步互斥的执行过程
我们这里面专门用0到17来标注了
它的一个大致的执行的过程
我们一步一步来分析一下
首先线程A来先执行
它首先通过monitor.mutex
这个信号量进入到临界区执行
它用到了sem_wait
OK 这是第一步
进去之后它发现
它对共享变量所需要的那些条件
得不到满足
因此它会调用条件变量的wait操作（wait_cv）
这个条件变量是在哪呢
是在这里面来实现的wait操作
所以这是第一步
然后呢第二个时刻
是进入了条件变量的wait操作的
具体的一个函数里面去
当前等待的个数
条件变量的等待个数
会做一个加一的操作
在第三步因为在这个时刻
monitor.next_count还是为0的
所以说它是执行else操作
第三步有一个sem_signal
这个signal是把临界区的
wait操作给退出出去
它做了一个monitor.mutex的
一个signal操作
这是第三步
那么第四步它自身要进入睡眠
所以说有个sem_wait
睡在哪呢 睡在条件变量的
那个信号量里面
就是cv.sem里面
这是第四步
当执行到这一步的时候呢
我们可以发现
线程A处于等待状态
它已经不能再继续往下执行了
那我们线程B能够继续执行吗
可以看一下
线程B一开始执行的
也是一个信号量的wait操作
这个信号量是什么呢
是monitor.mutex
由于前面在这第三步的时候呢
线程A已经释放了
这个monitor.mutex
所以这一步可以进去
这是第五个时刻
进去之后也进入了一个临界区
在这里面呢线程B会判断一下
跟共享变量相关的一些条件
发现这些条件可以满足
因此发出一个signal_cv操作
而这个操作会唤醒线程A
具体怎么做呢我们看一下
这是第时刻六完成的造作
在这它完成对条件变量的
signal的一个函数调用
首先它的判断
cv.count是否大于0
这里面可以看着
这做了++操作
所以说在这里面count是大于0的
会进一步去执行
执行到哪呢
sem_signal(cv.sem)
这个是有什么用呢
这一步会完成对线程A的唤醒
这里面可以看着
在线程A的条件变量的等待操作中
它有一个对信号量cv.sem的
一个等待
通过线程B的
sem_signal(cv.sem)
可以完成对它的一个唤醒操作
然后紧接着线程B
自身再执行一个sem_wait 在哪呢
wait在monitor.next条件变量上面
使得线程B又睡眠了
这是第九步
那线程A会被唤醒
唤醒之后会执行一个cv.count--操作
从而使得cv.count从1又变成了0
这是第十个时刻
执行完之后呢
这个函数就执行完毕
它会跳出wait_cv这么一个函数
这是第十一步 这一个过程
并进一步判断
当前的monitor.next_count是否大于0
大家注意一下
在第七步之后呢
有一个monitor.next_count++
这么一个操作
所以这个条件是成立的
所以它会执行sem_signal
monitor.next信号量
那么这个信号量呢
会唤醒刚才线程B睡眠的
那个信号量
monitor.next在这sem_wait
然后它自身就退出了
退出了管程的一个操作
那我们可以看着
线程B这个时候它唤醒之后呢
会在第14个时刻继续执行
完成对next_count的一个减减操作
使得count也变成了0
然后这个函数会跳出
跳出返回到15这个时刻
然后继续往下走
在15这个时刻它会进一步判断
是否monitor.next_count大于0
这里面做了一个减操作
所以它已经是为0了
这一步不会执行
所以会执行第16和17
就是else之后的这个语句
完成对monitor.mutex
这么一个互斥信号量的
一个释放操作
那么这个操作呢
是和第五步的
sem.wait monitor.mutex
是对应的 那完成这一步之后呢
使得线程A和线程B
都完成了各自的对管程中的
特定操作的一个执行过程
且保证了正确的同步互斥关系