OS-5
对于书上基础算法较为形象的描述:
其实更应该说是一些较为经典的错误案例
单标志法:
如果现在没有轮到我用,我等
如果现在轮到我用
我用
下次给他用
评价:
这个算法的缺点其实比较明显的,如果下次他不用而我要用,那我就得一直等
更何况就算他用了也不一定考虑我用不用的问题,可能转手就把这个机会让给别人用了
极有可能会导致资源的浪费,甚至说长时间得不到使用导致的饥饿问题
违反了“空闲让进”,并且没有实现“让权等待”
其实核心就是,没有考虑到下次给他用的时候,他到底会不会用,以及会不会让给我用
双标志先检查法:
如果现在他想要用,那么给他用,我等
如果他现在不想用
那么我想用
我用
我用完了不想用了
评价:
这个算法同样存在漏洞
检查的时候他可能不想用,但是就在我设置想用的前那么几刻,他也想用了
而这时候我还没想用,他可能就会以为我不想用,于是我们两个一起想用,冲突了
简单来说就是两者检查均通过
违反了“忙则等待”,没有实现“让权等待”
核心是检查和设置中有一个间隔,这个间隔时间就会导致另一者的检查也通过
双标志后检查法:
我想用
如果他现在想用,那么给他用,我等
如果他现在不想用
我用
我用完了不想用了
评价:
这个算法就是在之前的状态改进了下,可以避免同时检查通过的情况
但依旧会有问题,在检查前两者可能都设置了想用,结果一检查的时候发现都想用
好好好我让你用,于是就互相谦让了半天谁都没有用,于是这下是真的要饥饿了
违反了“有限等待”,没有实现“让权等待”
核心是产生了死锁问题,互相谦让导致谁都没有成功
Peterson算法:
我想用
这轮让给他用
如果他现在想用并且这轮我们协商完了后让他先用
他用,我等
如果他现在不想用或者他想用但是我们协商完了后让我先用
我用
我用完了不想用了
评价:
对于协商过程以及后续的切换过程稍微做些解释,免得到时候看不懂
协商其实实际上是对轮数的设置,因为设置最终只有一个生效,所以不会产生一直谦让
同时在一个进程结束占用后,表达了自己不想用之后,其他进程的循环自然破解
其他都实现,唯独没有实现“让权等待”
硬件实现法:
关中断、开中断,单纯就是我执行的时候你不准来,你执行的时候我也不准来
TestAndSet:
测试资源当前是否上锁,不可访问
如果被上锁,不可访问,那么暂时等待
如果资源当前没有上锁,那么占用资源同时对资源上锁,使得其不可被其他访问
与Swap的区别在于这个封装了测试和上锁过程
Swap:
测试当前资源是否上锁,不可访问
如果被上锁,不可访问,那么暂时等待
如果资源当前没有上锁,那么占用资源同时对资源上锁,使得其不可被其他访问
与TestAndSet区别在于这个没有封装测试和上锁过程
Test和Swap均没有实现“让权等待”,因为其一直需要循环检查,互斥锁也是如此
和信号量的差别就在于信号量当占用资源检查失败时直接阻塞到等待队列,让出处理器
同时当别的进程释放资源的时候,唤醒一个进程
将原先古老而粗糙的反复敲门动作给细致化为没有资源不必反复追问
有资源的时候仅有可能是别的进程释放了资源,别的进程会唤醒进程,不需要主动追问
思想上是明显先进了的
互斥锁:
测试当前资源是否可用
如果不可用,那么暂时等待
如果可用,那么占据资源同时使得其不可用,不能被其他占据
信号量中,整型信号量中的wait当资源量小于等于零会一直测试所以没遵循“让权等待”
记录型信号量则实现了“让权等待”,因为其并没有循环
这里的资源,都设置为了物理意义,即资源数是多少,就代表还有多少资源
初始就是当前有的资源数
为0的时候就是当前没有资源了,为负一就是当前有一个预约了资源
整型信号量、记录型信号量:
整:
wait:
如果当前资源量不够,那么一直循环等待,反复追问(资源量小于等于0
其实说实话这边就算设置为等于0也没关系,因为不可能出现负数
如果当前资源量足够,那么占用一个资源(同时资源数量减一
signal:
释放自身占用的一个资源(资源数量加一
记录型:
wait:
先预约一个资源(资源量先减一
如果预约的资源目前被占据,那么进入阻塞队列等待(资源量小于0,主动阻塞
如果预约的资源目前没有被占据,那么占据该资源
signal:
释放自身占用的一个资源(资源量加一
如果资源被预约占据,那么从阻塞队列唤醒该进程(资源量小于等于0,被动唤醒
信号量实现互斥:
A:
P,如果没有别人占据(或,现在能得到这个资源,那么占据这个资源,并进入运行
如果别人占据或者说当前得不到这个资源,那么阻塞
V,释放该资源,可以让别人占据
B:
P,如果没有别人占据(或,现在能得到这个资源,那么占据这个资源,并进入运行
如果别人占据或者说当前得不到这个资源,那么阻塞
V,释放该资源,可以让别人占据
附:
简单来说就是对独占式资源的操作,资源只能被他人或者自己独占
要么你占,要么我占,要么谁都不占,只有一把椅子
信号量实现同步
P:如果现在能得到这个资源,那么占据这个资源并进入运行,否则就阻塞
V:创造出这个资源
附:
简单来说就是先得到了这个资源,再去消耗,没有这个资源,那么就先阻塞等待
主要是处理逻辑上的先后关系
前驱关系:
P1、P2、P3、P4、P5…
如果现在能得到这些资源,那么占据这个资源并进入运行,否则就阻塞
V1、V2、V3、V4、V5…
创造出这些资源
附:
本质是多同步问题,把上述的一个同步换为了多个同步问题
自然需要得到一系列的同步资源、条件后,才能占用资源并运行,否则就阻塞