(2)利用软件方法解决进程互斥 Mutua Exclusion)问题 问题:有二个进程Pi和Pj互斥共享临界资源R, begin parbegin Pi:,, P parend end 下列算法只写出进程Pi程序
(2)利用软件方法解决进程互斥(Mutual Exclusion )问题 问题：有二个进程Pi和Pj互斥共享临界资源R， begin parbegin Pi: ...… Pj: ..... parend end 下列算法只写出进程Pi程序
利用软件方法解决进程互斥问题-1 算法1 该算法设置了一个公用整型变量turn,用于指示被允许进 入临界区的进程编号,既若ture=0,表示允许P进程进入 临界区。该算法可确保每次只允许一个进入临界区。但采 用强制两个进程轮流进入临界区,很容易造成资源利用不 充分。 PO进程 P1进程: repeat repeat while turn≠0 do no op while turn≠1 do no op Critical section Critical section turn=1 turn=0 Remain section Remain section until false until false
利用软件方法解决进程互斥问题-1 算法1 该算法设置了一个公用整型变量turn，用于指示被允许进 入临界区的进程编号，既若ture=0，表示允许Pi进程进入 临界区。该算法可确保每次只允许一个进入临界区。但采 用强制两个进程轮流进入临界区，很容易造成资源利用不 充分。 P0进程: P1进程: repeat repeat while turn≠0 do no op while turn≠1 do no op Critical section Critical section turn=1 turn=0 Remain Section Remain Section until false until false
利用软件方法解决进程互斥问题-2 算法2: 算法基本思想:在每一个进程访问临界区资源之前,先动查 看一下临界资源是否正被访问,若正被访问,该进程需等待, 否则才进入自己的临界区。为此设置了一个数据ag0,1 如第个元素值为 false表示Pi进程未进入临界区,值为true表 示P进程进入临界区。 PO:repeat P1: repeat While flag[1] do no op; 2while flag[o] do no op ③flag[0]:=true; ④flag[1]:=true; ⑤ critical section; ⑥ critical section flag[o]: =false flag[1]: =false remainder section remainder section until false until false 按①②③④⑤⑥序列执行会出现Pi和Pj同时进入临界区错误
利用软件方法解决进程互斥问题-2 算法2: 算法基本思想：在每一个进程访问临界区资源之前，先动查 看一下临界资源是否正被访问，若正被访问，该进程需等待， 否则才进入自己的临界区。为此设置了一个数据flag[0,1]， 如第i个元素值为false表示Pi进程未进入临界区，值为true表 示Pi进程进入临界区。 P0:repeat P1:repeat ①while flag[1] do no_op; ②while flag[0] do no_op; ③flag[0]:=true; ④flag[1]:=true; ⑤critical_section; ⑥critical_section; flag[0]:=false; flag[1]:=false; remainder section; remainder section; until false until false 按①②③④⑤ ⑥序列执行会出现Pi和Pj同时进入临界区错误
利用软件方法解决进程互斥问题-3 算法3 算法2是先检测对方进程状态标志后再置自己标志,由于在检 测和放置中可插入另一个进程时检测操作,会造成二个进程 在分别检测后同时进入临界区。为此算法3采用先设置自己标 志后再检测对方状态标志,它的程序如下,但也可能出现二 个进程先后同时设置后再分别检测对方状态标志,造成对方 都不能进入临界区,无限期等待 PO:repeat Plsrepeat ①flag[0]:=true; ②flag[1]:=true; 3⑤ while flag[1] do no op;④⑥ while flag[0]dono_op critical section critical section: flag[o]: =false flag[1]: =false remainder section remainder section until false until false
利用软件方法解决进程互斥问题-3 算法3: 算法2是先检测对方进程状态标志后再置自己标志，由于在检 测和放置中可插入另一个进程时检测操作，会造成二个进程 在分别检测后同时进入临界区。为此算法3采用先设置自己标 志后再检测对方状态标志，它的程序如下，但也可能出现二 个进程先后同时设置后再分别检测对方状态标志，造成对方 都不能进入临界区，无限期等待。 P0:repeat P1:repeat ①flag[0]:=true; ②flag[1]:=true; ③⑤ while flag[1] do no_op;④⑥while flag[0] do no_op critical_section; critical_section; flag[0]:=false; flag[1]:=false; remainder section; remainder section; until false until false
利用软件方法解决进程互斥问题-4 算法4( Peterson1981): 该算法组合了算法1和算法4,为了防止二进程进入临界 区而无限期等待,又设置变量turn,表示不允许进入临界 区的编号,每个进程在先设置自己标志后再设置turn标志, 不允许另一个进程进入,这时再同时检测另一个进程状 态标志和不允许进入标志,这样可以保证当二个进程同 时要求进入临界区时,只允许一个进程进入临界区。 Pi: repeat flagli]:true; turn: =j while (flaglj] and turn=j)do no op critical section flag[i]: =false remainder section until false
利用软件方法解决进程互斥问题-4 算法4(Peterson 1981)： 该算法组合了算法1和算法4，为了防止二进程进入临界 区而无限期等待，又设置变量turn，表示不允许进入临界 区的编号，每个进程在先设置自己标志后再设置turn标志， 不允许另一个进程进入，这时再同时检测另一个进程状 态标志和不允许进入标志，这样可以保证当二个进程同 时要求进入临界区时，只允许一个进程进入临界区。 Pi: repeat flag[i]:=true; turn:=j; while (flag[j] and turn=j) do no_op; critical_section; flag[i]:=false; remainder section; until false