一、知识总览
二、单标志法
**1.算法思想:**两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程,也就是说每个进程进入临界区的权限只能被另一个进程赋予。
**单标志法所存在的问题:**只能按照P0–>P1–>P0–>P1…这样轮流的访问。这种必须“轮流访问”带来的问题是,如果此时允许进入临界区的进程是P0,而P0一直不访问临界区,那么虽然此时临界区空闲,但是并不允许P1访问。
因此单标志法存在的主要问题是:违背了“空闲让进” 的原则。
三、双标志先检查法
注意:若按照1,5,2,6,3,7…这样的顺序执行,P0和P1将会同时访问临界区。
因此,双标志先检查法的主要问题是:违反了“忙则等待”原则(在两个进程并发执行的情况下发生)
原因在于:进入区的“检查”和“上锁”两个处理不是一气呵成的。“检查”后,“上锁”前可能发生进程切换。
四、双标志后检查法
按照1,5,2,6…的顺序执行,P0和P1将无法进入临界区
因此,双标志后检查法虽然解决了“忙则等待”的问题,但是又违背了“空闲让进”(可能两个进程都无法访问临界区)和“有限等待”(可能卡死在while循环处)原则,会因各进程都长期无法访问临界资源而产生“饥饿”现象。两个进程都争着想要进入临界区,但是谁也不让谁,最后谁也无法进入临界区。
五、Peterson
1.其实Peterson算法的实质是:
进入区:
1)主动争取
2)主动谦让
3)检查对方是否也想使用,且最后一次是不是自己说了“客气话”
注意:谁最后说了“客气话”,谁就失去了行动的优先权。
2.Peterson算法用软件方法解决了进程互斥问题,遵循了空闲让进、忙则等待、优先等待三个原则,但是依然未遵循**让权等待(当一个进程暂时不能访问临界区,应该释放占用的CPU使用权,但是Peterson并未释放CPU的使用权)**的原则。