1Dang Minh Quan: Institute of IT for Economics-NEU, 2011
Operating System
Chapter 8: H th ng phân tánệ ố
2Dang Minh Quan: Institute of IT for Economics-NEU, 2011
Overview
•Khái ni m chungệ
•T c ngh nắ ẽ
•S p x p s ki nắ ế ự ệ
•Giao d ch nguyên tị ử
3Dang Minh Quan: Institute of IT for Economics-NEU, 2011
S p x p s ki nắ ế ự ệ
•Nhi u ng d ng có th yêu c u chúng ta xác đnh ề ứ ụ ể ầ ị
tr t t . Ví d , trong m tậ ự ụ ộ k ho ch phân b tài ế ạ ổ
nguyên, chúng ta xác đnh r ng m t tài nguyên có ị ằ ộ
th đc s d ng ch sau khi tài nguyên đã đc ể ượ ử ụ ỉ ượ
c p.ấ
•Quan h x y ra tr cệ ả ướ (đc ký hi u ượ ệ ).
–N u ếA và B là các s ki n trong cùng m t ti n trình, và ự ệ ộ ế
A đc ch y tr c B, ta có ượ ạ ướ A B.
–N u ếA là s ki n g i thông đi p c a m t ti n trình và ự ệ ử ệ ủ ộ ế
B là s ki n nh n thông đi p đó c a m t ti n trình ự ệ ậ ệ ủ ộ ế
khác, ta có A B.
–N u ếA B và B C thì A C.
4Dang Minh Quan: Institute of IT for Economics-NEU, 2011
Cách th c hi n ự ệ
•Dùng m t nhãn th i gian cho m i s ki n h th ng. V i ộ ờ ỗ ự ệ ệ ố ớ
m i c p s ki n ỗ ặ ự ệ A và B, n u ếA B, thì nhãn th i gian c a ờ ủ
A nh h n nhãn th i gian c a ỏ ơ ờ ủ B.
•M i ti n trình ỗ ế Pi có m t đng h logic ộ ồ ồ LCi. Đng h logic ồ ồ
có th đc th c hi n nh m t b đm đn gi n, nó ể ượ ự ệ ư ộ ộ ế ơ ả
đc tăng lên khi có hai s ki n liên ti p đc th c hi n ượ ự ệ ế ượ ự ệ
trong m t ti n trình. ộ ế
•M t ti n trình tăng đng h logic c a nó khi nó nh n m t ộ ế ồ ồ ủ ậ ộ
thông đi p có nhãn th i gian l n h n giá tr hi n t i c a ệ ờ ớ ơ ị ệ ạ ủ
đng h logic.ồ ồ
•N u nhãn th i gian c a 2 s ki n ế ờ ủ ự ệ A và B là gi ng nhau, 2 ố
s ki n là đng th i. Chúng ta có th dùng đ u tiên c a ự ệ ồ ờ ể ộ ư ủ
ti n trình đ t o ra th t . A < B : ti n trình A có đ u ế ể ạ ứ ự ế ộ ư
tiên cao h n B.ơ
5Dang Minh Quan: Institute of IT for Economics-NEU, 2011
Lo i tr phân tán - Distributed ạ ừ
Mutual Exclusion (DME)
•Gi sả ử
–H th ng bao g m ệ ố ồ n ti n trình; m i ti n trình ế ỗ ế Pi ch y ạ ở
m t b x lý khác nhau.ộ ộ ử
–M i ti n trình có m t mi n găng yêu c u truy c p ỗ ế ộ ề ầ ậ
mutual exclusion.
•Yêu c uầ
–N u ếPi đang x lý trong mi n găng, thì không m t ti n ử ề ộ ế
trình nào khác đc vào mi n găng c a nó.ượ ề ủ
•Chúng ta s xem xét 2 thu t toán đ đm b o các ẽ ậ ể ả ả
ti n trình ch y mutual exclusion trong mi n găng ế ạ ề
c a nó. ủ