下面我们来介绍软件同步方法
基于软件的同步方法呢
它是在两个进程之间
通过共享变量的访问
来实现线程之间的同步
那这一类方法呢
我们给它的大致模式先给它描述
假定有两个线程 T0和T1
然后每一个线程呢
它的实现代码都是这样一种格局
进入区 临界区 退出区
然后我们在这里控制的地方呢
是在进入区和退出区里头
通过一些共享变量的修改
来同步它们之间的行为
那我们在这里的所有的方法呢
都是要讨论在进入区里头
我要对哪些共享的变量
进行什么样的设置和判断
那这些方法呢跟我们前面讨论到的
生活当中同步问题呢是一致的
我们跟那儿呢做一个类比性的讨论
首先第一个尝试 说
我在这里呢
在两个线程之间共享一个变量
这个变量呢表示允许谁进入临界区
那这里是允许进入
临界区的线程的ID
好 那这时候我们说
线程Ti实现代码呢是这样的
它先判断当前这个turn的值
到底是不是i
如果不是 也就相当于我本身是i
允许另外一个线程进入临界区
i不允许进入临界区
那这时候呢它就一直等待
等待另一个线程把它改成i
好 如果 这样的话就是
在它自己等待它变成是它之后
它能进去 进去之后呢
执行临界区的代码
执行完毕之后退出的时候呢
在退出区呢 它把turn改成j
也就说另一个线程ID
那我们看这种情况
能满足我们的要求吗
如果说turn的值是i
那么这时候呢线程Ti
进入一个判断是可以的
OK 它就进去了
好 如果不是那就它一直等着
那这时候说如果这个地方
是j来访问那它就进不去
那这时候我们看到
i和j之间访问临界区的
关系是啥样的
开始的时候假定它等于i
那么这时候呢i能进去
j能进去吗 j进不去
好 i进去之后它改成j
好 这时候如果i再来进的话
它进不去了 j也能进去
这时候我们就会发现一种现象
它们俩是交替进入临界区
这是很好的一种做法
但如果说某一个线程
想连续两次进入临界区
那这时候它就会有麻烦
所以这种做法呢
它能够满足我们说的忙则等待
也就说我在这里头
任何一个线程进到里头去的时候
不会有第二个同时在里头
但是它不满足空闲则入
也就相当于如果说这里是空闲的
但是这时候编号不是你
那你进不去了
好 那我们对这种做法呢
进行进一步的修改
那这是第二种做法
我们在前面呢
设置一个变量turn不够用
那我们这儿呢现在设置两个变量
也就相当于一个数组
描述每个线程它是否是在临界区
这种做法和刚才那个地方
有什么不一样呢
这就相当于我是用两个来表示
我尝试着解决两个线程
需要交替进入的问题
好 那这时候呢
线程Ti的实现代码我们这样来做
先判断另外一个线程它的flag是1
如果它不是
也就相当于它没在临界区里头
那我就把自己的标识改成1
那这时候我在临界区
然后进入临界区
出来的时候
我把自己这个标识呢改成0
那这种做法呢
和我们前面的第一种尝试
想想看有什么区别
线程Ti想进入临界区
它做判断
假设另一个没有在临界区
那它判断是通过的
OK 好 它这时候呢
把自己的标识改了然后进去
如果它再来一遍可以吗
它再来一遍同样的做法仍然没问题
一个线程连续进入是可以的
好 如果说它交替进入呢
那也没问题
好像改善了我们前面
第一种尝试里头的麻烦
但是它有什么问题吗
还记得我们在前面讲
采购当中那个同步
说两个先判断 后设置
两个同时判断之后会出现什么
同时设置
那同时设置之后呢
两个线程就同时进入到
临界区里头去了
那这时候这是它的毛病
它就不能满足忙则等待
好 那这种做法不行了
之后怎么办呢
我们把前面含义做一下改动
也就说前面我们就像
我们在采购那个同步里头
我们是先贴标签还是后贴标签
刚才那种做法呢
相当于是后贴标签
那这时候呢我把这个flag含义改了
不表示我在临界区
而表示我想进入临界区
那这时候呢相当于我是先贴标签
这是它的实现代码
先贴标签后做判断
这时候我们说 前面的采购同步里头
先贴标签后做判断会出现什么问题
两个都有可能判断完了之后
都觉得自己进不去
OK 那就都进不去了
那这是它的问题
它能够满足不能同时进
但是不能满足如果空闲我可以进去
这就是空闲则入
好 这种做法呢也不行
也就相当于我把标签贴在前头
贴在后头都不行
好 那这时候呢
我把这两个合在一起
这就是我们这里的Peterson算法
这是两个进程之间
能够完成同步的算法
它怎么做的呢
turn表示当前谁进入临界区
而flag表示我请求进入临界区
好 这时候我们说
进入区的代码是先设置标志
相当于这时候设置的标志有两个
一个是我想进入
第二个是turn的值
然后我在后面做一个判断
那这时候想想看
这和我们前面先设置标志
后做判断有什么区别
那这地方它俩同时
设置了一个变量 turn
这是问题的关键
我把这一步设置完了之后呢
我后面的判断
就能够区别出来它们俩
好 我们具体看一下
如果说另一个线程j
它没有申请进入
那我这儿直接能进去没问题
因为这两个条件里头
有一个不成立它就进来了
好 假定说另一个也申请了
它也变成true
好 那这时候会什么呢
会有这样一个turn在这儿等着
因为这个变量是
往存储单元里写数据
两个线程同时往里写
或者并发往里写
那总是有一前一后
好 不管是哪一个
因为在总线上仲裁之后
我是有一前一后的
在这里呢
假定我在这儿
我写的是j
如果我是最后一个写的
会什么样的情况
另一个flag是true
然后我的标志呢
turn的标志是按我最后写的
那我判断相当于
如果两个同时想进入的话
后设置turn这个标志的
那这个条件就成立
而先写的后面这个条件不成立
好 那这样的话
就是先写turn这个标志的能进去
而后写的就会在这儿等着
那等到在退出区里头我把flag改了
好 那么这个条件呢
前面这个就不成立了
好 那这是后写标志turn
也就能进去了
好 那这一个呢
我们说跟我们前面讲
采购同步一样的
把它们所有的情况
罗列出来进行分析
写标志 判断它们
所有可能的顺序一一进行分析
我们说Peterson算法呢
是可以完成
我们的两个进程之间同步
好 那在这种情况下我们说
要是更多的进程怎么办
我们先把这个两个进程的做法呢
换一种形式来写
这就是Dekkers算法
它的做法是什么呢
跟标志 跟我们前面的几乎一样的
但是这个进入区的判断呢
相对来说复杂一些
那实际上也是先写
然后后面去判断
判断完了之后
那看如果另一个也想进入
实际上它就把自己改为false
然后开始等待 前面这个
这种做法呢
退出去的做法跟那儿是一样的
这种做法呢
它可以很方便的扩展到多个线程
而扩展到多个线程的做法呢
就是我们这个图呢给出的图示
我在这里有一个turn这个变量
这是共享的
然后是每一个线程 若干个
我把它排成一个环
每一个里头有一个flag的标志
好 那我在进入的时候呢
我先填这个flag标志说我想进入
然后去看turn标志
如果有多个想写
那这个时候呢它总是会有最后一个
好 那么在这种情况下
这是当前正在访问临界区的那一个线程
好 我要做什么呢
进入区我就从这儿往后一直到i
这是个环
也可能会在另外一个位置
就从它起头 到i这个地方
这一段里是不是有其它线程
也跟我一样的 同时想进入
如果有 让他们先访问
访问完了之后
这个turn会一直往后蹿
蹿到我这儿
那这时候我进去
那这就是我们这里说的
进入区的做法
而退出区等我用完了之后
后面有可能
也有其他在等着的
我顺序的把标志
给到下一个想进入的
如果都没有转一圈之后
我把自己留这儿就行了
好 这是N个进程的软件同步方法
好 那我们看到
这几种方法搁到一起之后
我们发现这个
基于软件的同步方法它很复杂
两个进程之间需要多个共享数据项
我才能够完成这个同步
同时这是一个盲等待
也就说我在进入区里头
我必须频繁地来
查询共享变量的状态
那这是呢软件同步方法
所面临的问题
好 经过这几个算法的介绍呢
我们知道通过软件方法
是可以实现多个进程之间的同步的
但是这个方法比较复杂
里头有错之后也不好查找
如果说你是多个线程
多个临界区
那么这时候这个问题会变得更复杂