Lo i tr l n nhau
ạ ừ ẫ
i quy t v n đ lo i tr l n nhau cho hai b x i thu t sau v i m c đích gi ớ ụ ậ ả ề ạ ừ ẫ ế ấ ộ ử ả Cho gi lý p0 và p1
Gi ả i thu t 1 ậ
Bi n chung ph n ế ầ
Turn có giá tr ban đ u là 0 ị ầ
V i m i b x lý pi ỗ ộ ử ớ
Đo n vào ạ
wait until Turn = i
Đo n raạ
Turn := 1 - i
i thu t trên th a mãn nh ng tính ch t nào sau đây : lo i tr l n nhau, không có ả ạ ừ ẫ ữ ấ ỏ Gi khóa ch t, không có khóa đóng, có c n ch ? Gi i thích vì sao. ậ ế ậ ả ờ
Gi ả i thu t 1: ậ
ạ ừ ẫ ể ấ ờ ộ ỉ - Có tính ch t lo i tr l n nhau: do t đo n vào và có ID = Turn nên s vào đ c đo n găng i b t kỳ th i đi m nào ch có m t BXL trong ạ ấ ượ ẽ ạ ạ
thi trong đo n găng và ra ngoài, khi đó t ả ế ừ ở ạ ạ ế ị t BXL i v a ỉ ượ ể ớ ị ẽ ạ i - Có khóa ch t: vì ta gi c đo n vào (vì đo n ra, giá tr Turn = 1-i. Do đó ch có BXL 1-i m i có th vào đ ạ Turn lúc này có giá tr là 1-i). Tuy nhiên n u BXL 1-i không có nhu c u s d ng tài ầ ử ụ ế i ti p t c mu n s d ng tài nguyên thì BXL i s không nguyên trong khi BXL i l bao gi c đo n vào. H th ng s b deadlock. vào đ ạ ế ụ ệ ố ố ử ụ ẽ ị ượ ạ ờ
Do gi i thu t có khóa ch t nên gi i thu t có khóa đóng và không có c n ch ả ế ậ ả ậ ậ ờ
Gi ả i thu t 2 ậ
Bi n chung ph n ế ầ
Flag[0] và Flag[1] có giá tr ban đ u là true ầ ị
Turn có giá tr ban đ u là 0 ị ầ
V i m i b x lý pi ỗ ộ ử ớ
Đo n vào ạ
wait until Flag[1 - i] = false or Turn = i
Đo n raạ
Flag[i] := false
i thu t trên th a mãn nh ng tính ch t nào sau đây : lo i tr l n nhau, không có ả ạ ừ ẫ ữ ấ ỏ Gi khóa ch t, không có khóa đóng, có c n ch ? Gi i thích vì sao. ậ ế ả ậ ờ
Gi i thu t 2 không có tính ch t lo i tr l n nhau do ả ạ ừ ẫ ậ ấ
- Đ u tiên, BXL 0 đo n vào do lúc đ u Turn = 0 ầ ở ạ ầ
- Vì BXL 0 đo n vào nên n u nó vào đo n găng và đo n ra thì nó s ở ế ạ ạ ở ạ ẽ thi t l p Flag[0] = false, còn Turn = 0 ế ậ
ả ế ề ề ệ ờ đo n vào và do đó s cùng - Ti p theo, c hai BXL 0 và 1 đ u th a mãn đi u ki n ch là wait until ở ẽ ạ Flag[1 - i] = false or Turn = i nên s đ u đo n găng m t lúc, vi ph m tính lo i tr l n nhau ạ ỏ ẽ ề ở ạ ừ ẫ ạ ộ
trong đo n vào thì BXL còn l ở ạ ạ i ch a ch c s ư l n nhau nên có th c ạ ấ ạ ừ ẫ ắ ẽ ở ể ả Có khóa ch t: Do m t BXL đang ộ ế trong đo n găng do gi hai BXL đ u ậ ả trong đo n vào ề ở i thu t không có tính ch t lo i tr ạ
Vì gi i thu t có khóa ch t nên có khóa đóng và không có c n ch ả ế ậ ậ ờ
