Quan Ly Tien Trinh (tt)
Tài nguyên găng (Critical Resource)
v Tài nguyên găng?
§ Nh ững tài nguyên đý ợc HĐH chia s ẻ cho nhi ều ti ến trình ho ạt đ ộng đ ồng th ời dùng chung mà có nguy cõ tranh ch ấp gi ữa các ti ến trình này khi s ử d ụng chúng.
Có 2 tiến trình P1 vs P2 cùng thao tác rút tiền từ 1 tài khoản.
IF (Tai khoan – tien rut >= 0)
Tai khoan := Tai khoan – tien rut
else
Thong bao loi
Đoạn găng(Critical Section)
v Các đoạn code trong các chýõng trình dùng để truy cập đến tài nguyên găng đýợc gọi là đoạn găng.
Yêu cầu của công tác điều độ tiến trình qua đoạn găng
v Tại 1 thời điểm chỉ cho phép 1 tiến trình nằm trong đoạn găng, các tiến trình khác có nhu cầu vào đoạn găng phải chờ
v Tiến trình chờ ngoài đoạn găng không đýợc ngăn cản các tiến trình khác vào đoạn găng
v Không có tiến trình nào phải chờ lâu để đýợc vào đoạn găng
v Đánh thức các tiến trình trong hàng đợi để tạo điều kiện cho nó vào đoạn găng khi tài nguyên găng đýợc giải phóng
3. Điều độ tiến trình qua đoạn găng
3.1. Giải pháp phần cứng
v Dùng cặp chỉ thị STI(setting interrupt) và CLI (clean interrupt)
Ví dụ:
Procedure P(i: integer)
begin
repeat
CLI;
<đoạn găng của p>;
STI;
<Đoạn không găng>;
until .F.
end;
v Dùng chỉ thị TSL(Test and set)
Function TestAnhSetLock(Var i:integer):boolean
Begin
if i=0 then
begin
i:=1;
TestAnhSetLock:=true
end;
else
TestAnhSetLock:=false
End;
Procedure P(lock: integer);
begin
repeat
while (TestAnhSetLock(lock)) do;
<đoạn găng của p>;
lock:=0
<Đoạn không găng>;
until .F.
end;
3.2. Giải pháp dùng biến khóa
v Dùng biến khóa chung
Procedure P(lock: integer);
begin
repeat
while lock=1 do;
Lock=1
<đoạn găng của p>;
lock:=0
<Đoạn không găng>;
until .F.
end;
v Dùng biến khóa riêng
Var lock1, lock2: byte;
begin
lock1:=0; lock2:=1
p1: repeat
while lock2=1 do;
Lock1:=1
<đoạn găng của p>;
lock1:=0
<Đoạn không găng>;
until .F.
p2: repeat
while lock1=1 do;
Lock2:=1
<đoạn găng của p>;
lock2:=0
<Đoạn không găng>;
until .F.
end
3.3. Giải pháp đýợc hỗ trợ bởi HĐH và ngôn ngữ lập trình
v Dùng Semaphore(đèn báo)
§ Semaphore S là 1 biến nguyên, khởi gán bằng 1 giá trị không âm, là khả năng phục vụ của tài nguyên găng týõng ứng với nó
§ Ứng với S có 1 hàng đợi F(s) lýu các tiến trình đang chờ trên S
§ Thao tác Down giảm S 1 đõn vị, Up tăng S 1 đõn vị
§ Mỗi tiến trình trýớc khi vào đoạn găng cần gọi Down để giảm S và kiểm tra nếu S>=0 thì đýợc vào đoạn găng
§ Mỗi tiến trình khi ra khỏi đoạn găng phải gọi Up để tăng S lên 1 đõn vị và ktra nếu S <=0 thì đýa 1 tiến trình trong F(s) vào đoạn găng
Procedure Down(S);
Begin
S:=S-1;
If s<0 then
Begin
Status(p)=waiting;
Enter(p,F(s));
end
End;
Procedure Up(S);
Begin
S:=S+1;
If s<=0 then
Begin
Exit(Q,F(S));
Status(Q)=ready;
Enter(Q,ready-list);
end
End;
Program MultualExclution;
Const
n=2;
Var
s:semaphore;
{---------------------}
Procedure P(i:Integer);
Begin
REpeat
Down(s); {kiem tra va xac lap quyen vao doan gang}
<Doan gang>;
Up(s);
<Doan khong gang>;
Until .F.;
End;
{---------------------}
BEGIN
S:=1;
ParBegin
P(1);
P(2);
ParEnd;
END.
Ví dụ 2 :
Có 6 tiến trình
A B C D E F
Độ ýu tiên
1 1 2 4 2 5
Thời gian thực hiện
4 2 2 2 1 1
Giải pháp dùng Monitor
****Wait(c)
Procedure Wait(c);
Begin
Status(p)=blocked;
Enter(p,f(c));
End;
****Signal(c)
Begin
If f(c) <> Null Then
Begin
Exit(Q,f(c)); {Q la tien trinh cho tren C}
Status(Q)=ready;
Enter(Q,ready-list);
End;
End;
Monitor <Ten monitor>
Condition <Danh sach cac bien dieu kien>;
{----------------------------}
Procedure Action1(); {thao tac 1}
Begin
.....
End;
{--------------------}
Procedure Actionn(); {thao tac n}
Begin
.....
End;
{--------------------}
End monitor;
Program MultualExclution;
Monitor ... Endmonitor; {monitor duoc dinh nghia nhu tren}
{-----------------------}
BEGIN
ParBegin
P1:Repeat
<Doan khong gang cua P1>;
<>monitor>.Actioni; {Doan gang cua P1};
<Doan khong gang cua P1>;
Until .F.
P2:Repeat
<Doan khong gang cua P2>;
<monitor>.Actionj; {Doan gang cua P1};
<Doan khong gang cua P2>;
Until .F.
ParEnd
END.
{-----------------------}
Giải pháp trao đổi Message
Procedure P(i:Integer);
Begin
Repeat
Send(process controler, request message);
Receive(process controler, accept message);
<Doan gang cua P>;
Send(process controler, end message);
<Doan khong gang cua P>;
Until .F.
End;
Bài toán điều phối
Giải pháp Semaphore
Program Producer/Consumer;
Var Full,Empty,Mutex:Semaphore;
{-------------------------}
Procedure Producer();
Begin
Repeat
<Tao du lieu>;
Down(Empty); {kiem tra xem bufer con cho trong?}
Down(Mutex); {kiem tra va xac lap quyen truy xuat Buffer}
<Dat du lieu vao Buffer>;
Up(Mutex); {ket thuc truy xuat buffer}
Up(Full); {da co 1 phan tu du lieu trong Buffer}
Until .F.
End;
{-------------------------}
Procedure Consumer();
Begin
Repeat
Down(Full); {con phan tu du lieu trong Buffer}
Down(Mutex); {kiem tra va xac lap quyen truy xuat Buffer}
<Nhan du lieu tu dem>;
Up(Mutex); {ket thuc truy xuat Buffer}
Up(Empty); {da lay 1 phan tu du lieu trong Buffer}
Until .F.
End;
BEGIN
Full=0;Empty=3;Mutex=1;
Producer();
Consumer();
END.
Giải pháp Monitor
Program Producer/Consumer;
Monitor ProducerConsumer;
Condition Full,Empty;
Var Count:Integer; {da lay 1 phan tu du lieu Buffer}
N:Integer; {so phan tu cua Buffer}
{------------------------}
Procedure Enter();
Begin
If Count=N Then Wait(Full); {neu Buffer day thi doi}
<Dat du lieu vao dem>; {Buffer rong}
Count:=Count+1;
If Count=1 Then Signal(Empty); {neu Buffer khong rong thi}
End; {bao cho consumer biet}
{------------------------}
Procedure Remove();
Begin
If Count=0 Then Wait(Empty); {neu Buffer rong thi doi day}
<Nhan du lieu tu den>;
Count:=Count-1;
If Count=N-1 Then Signal(Full); {neu Buffer khong day thi}
End; {bao cho producer}
Endmonitor;
{------------------------}
BEGIN
Count=0;N=3;
ParBegin
Procedure Producer();
Begin
Repeat
<Tao du lieu>;
Producer/Consumer.Enter;
Until .F.
End;
{------------------------}
Procedure Consumor();
Begin
Repeat
Producer/Consumer.Remove;
<Xu ly du lieu>;
Until .F.
End;
ParEnd
END.
{------------------------}
Message
Program Producer/Consumer;
Var
Buffersize:integer; {kich thuoc Buffer}
M,m:Message;
{-------------------------}
BEGIN
Bufersize=N;
ParBegin
Procedure Producer();
Begin
Repeat
<Tao du lieu>;
Receive(Consumer,m);
<Tao thong diep du lieu>;
Send(Consumer,m);
Until .F.
End;
{-------------------------}
Procedure Consumer()
Var I:integer;
Begin
For I:=0 to N Do Send(Producer,m);
Repeat
Receive(Producer,m);
<Lay du lieu tu thong diep>;
Send(Producer,m);
<Xu ly du lieu>;
Until .F.
End.
Parend
END.
Không có nhận xét nào:
Đăng nhận xét