第五拿并行性:互斥和同步 531互斥的软件方法(算法2:双标 志,先检查) 优点:不用交替进入,可连续使用 缺点:P和Pj可能同时进入临界区 ■按下面序列执行时,会同时进入:"Pi<a> Pja>Pi<b>Pj<b>"。即在检查对方fag 之后和切换自己fag之前有一段时间,结 果都检查通过。这里的问题出在检查和修 改操作不能连续进行
第五章 并行性：互斥和同步 5.3.1 互斥的软件方法（算法2：双标 志，先检查） ◼ 优点：不用交替进入，可连续使用； ◼ 缺点：Pi和Pj可能同时进入临界区。 ◼ 按下面序列执行时，会同时进入："Pi<a> Pj<a> Pi<b> Pj<b>"。即在检查对方flag 之后和切换自己flag之前有一段时间，结 果都检查通过。这里的问题出在检查和修 改操作不能连续进行
第五拿并行性:互斥和同步 531互斥的软件方法(算法3:双 标志,后检查) flagli]= true <b> while (flagljl) Ka> critical section flagli]= false remainder section 类似于算法2,与互斥算法2的区别在于 先修改后检查。可防止两个进程同时进 入临界区
第五章 并行性：互斥和同步 5.3.1 互斥的软件方法（算法3：双 标志，后检查） ◼ 类似于算法2，与互斥算法2的区别在于 先修改后检查。可防止两个进程同时进 入临界区。 flag[i] = TRUE; <b> while (flag[j]); <a> critical section flag[i] = FALSE; remainder section
第五拿并行性:互斥和同步 531互斥的软件方法(算法3:双标 志,后检查) 缺点:P和Pj可能都进入不了临界区 按下面序列执行时,会都进不了临界区: "Pi<a>Pja>Pi<b>Pj<b>"。即在切换自 己fag之后和检查对方fag之前有一段时间, 结果都切换fag,都检查不通过
第五章 并行性：互斥和同步 5.3.1 互斥的软件方法（算法3：双标 志，后检查） ◼ 缺点：Pi和Pj可能都进入不了临界区。 ◼ 按下面序列执行时，会都进不了临界区： "Pi<a> Pj<a> Pi<b> Pj<b>"。即在切换自 己flag之后和检查对方flag之前有一段时间， 结果都切换flag，都检查不通过
第五拿并行性:互斥和同步 5.3.1互斥的软件方法(算法4 先修改,后检查,后修改者等待) flag[i]= TRue turn = j ■结合算法1和算法3 while (flaglj]&& turn = j) 是正确的算法 critical section tun=j;描述可进入的 flagli= faLse 进程(同时修改标志 remainder section 时) 在进入区先修改后检查,并检查并发修改的先后: ■检查对方fag,如果不在临界区则自己进入一一空闲则入 否则再检査turn:保存的是较晚的一次赋值,则较晚的进 程等待,较早的进程进入一一先到先入,后到等待
第五章 并行性：互斥和同步 5.3.1 互斥的软件方法（算法4： 先修改，后检查，后修改者等待） ◼ 结合算法1和算法3， 是正确的算法 ◼ turn=j;描述可进入的 进程（同时修改标志 时） flag[i] = TRUE; turn = j; while (flag[j] && turn == j); critical section flag[i] = FALSE; remainder section 在进入区先修改后检查，并检查并发修改的先后： 检查对方flag，如果不在临界区则自己进入－－空闲则入 否则再检查turn：保存的是较晚的一次赋值，则较晚的进 程等待，较早的进程进入－－先到先入，后到等待
第五拿并行性:互斥和同步 5.3.2互斥的硬件方法 完全利用软件方法,有很大局限性(如不适于 多进程等),现在已很少采用。 ■可以采用中断屏蔽方法(只能适用于单处理器 系统) ■也可以利用某些硬件指令一一其读写操作由 条指令完成,因而保证读操作与写操作不被打 断 aTS( Test and set)指令 SWap指令
第五章 并行性：互斥和同步 5.3.2 互斥的硬件方法 ◼ 完全利用软件方法，有很大局限性（如不适于 多进程等），现在已很少采用。 ◼ 可以采用中断屏蔽方法（只能适用于单处理器 系统） ◼ 也可以利用某些硬件指令－－其读写操作由一 条指令完成，因而保证读操作与写操作不被打 断； ◼ TS(Test and Set)指令 ◼ Swap指令