Thảo luận Bài 8

Dùng thuật toán Banker chứng minh không tồn tại trạng thái an toàn thay vì phải tính ra hết tất cả các trường hợp thì mình có ý này :
ta cứ đi theo một hướng bất kì, miễn nó còn tồn tại tiến trình kế tiếp cho tới khi nó không còn tiến trình nào có thể thêm vào chuỗi nữa.
Giả sử ta có chuỗi < P1,P0,P3> rồi còn lại 2 tiến trình P4 và P2 không đủ tài nguyên để đi vào. Lúc này ta có thể suy ra không tồn tại chuỗi an toàn.
Vì nếu giả sử tồn tại một chuỗi an toàn chẳng hạn là
thì ta bắt đầu xét từ tiến trình Pa xem Pa có thể thêm vào sau P3 trong chuỗi trên hay không, vì Pa là tiến trình đầu tiên của chuỗi an toàn nên nó không cần sự trao trả tài nguyên của tiến trình nào trước nó. Nếu Pa không thêm vào được thì do Pa đã tồn tại sau P3 rồi có thể là P1 hay P0, và như vậy nếu Pa đã thêm vào rồi thì ta có thể thêm Pb vì Pb cân Pa thực hiện xong thì nó mới có thể thực hiện. Cứ như vậy thì suy ra sau P3 luôn tồn tại một tiến trình có thể thêm vào --> Nếu tồn tại một chuỗi an toàn thì ta luôn tìm ra chuỗi an toàn khác cho dù có đi từ tiến trình nào trước và chọn lựa như thế nào. Ngược lại thì --- > không tồn tại chuỗi an toàn.

Trong ví dụ về: Tránh deadlock dùng Rag trong slide, thầy có đưa ra câu hỏi:
Tại trạng thái 2: Tại sao lúc này P2 đang ngủ và chờ yêu cầu từ R1 nhưng nó vẫn có thể yêu cầu được R2?
Trong thực tế thì tiến trình P2 là tiến trình đa luồng, 1 luồng chờ r1 nhưng có thể có 1 luồng nó thức yêu cầu r2.
Các bạn thảo luận thêm nhé

Phần lớn, chúng ta có thể giải quyết vấn đề deadlock theo một trong ba cách:
• Chúng ta có thể sử dụng một giao thức để ngăn chặn hay tránh deadlocks, đảm
bảo rằng hệ thống sẽ không bao giờ đi vào trạng thái deadlock
• Chúng ta có thể cho phép hệ thống đi vào trạng thái deadlock, phát hiện nó và
phục hồi.
• Chúng ta có thể bỏ qua hoàn toàn vấn đề này và giả vờ deadlock không bao
giờ xảy ra trong hệ thống. Giải pháp này được dùng trong nhiều hệ điều hành,
kể cả UNIX.
• Chúng ta sẽ tìm hiểu vắn tắt mỗi phương pháp. Sau đó, chúng ta sẽ trình bày
các giải thuật một cách chi tiết trong các phần sau đây.

Để đảm bảo deadlock không bao giờ xảy ra, hệ thống có thể dùng kế hoạch
ngăn chặn hay tránh deadlock. Ngăn chặn deadlock là một tập hợp các phương pháp
để đảm bảo rằng ít nhất một điều kiện cần (trong phần VI.4.1) không thể xảy ra. Các
phương pháp này ngăn chặn deadlocks bằng cách ràng buộc yêu cầu về tài nguyên
được thực hiện như thế nào. Chúng ta thảo luận phương pháp này trong phần sau.
Ngược lại, tránh deadlock yêu cầu hệ điều hành cung cấp những thông tin bổ sung tập trung vào loại tài nguyên nào một quá trình sẽ yêu cầu và sử dụng trong thời
gian sống của nó. Với những kiến thức bổ sung này, chúng ta có thể quyết định đối
với mỗi yêu cầu quá trình nên chờ hay không. Để quyết định yêu cầu hiện tại có thể
được thoả mãn hay phải bị trì hoãn, hệ thống phải xem xét tài nguyên hiện có, tài
nguyên hiện cấp phát cho mỗi quá trình, và các yêu cầu và giải phóng tương lai của
mỗi quá trình.
Nếu một hệ thống không dùng giải thuật ngăn chặn hay tránh deadlock thì
trường hợp deadlock có thể xảy ra. Trong môi trường này, hệ thống có thể cung cấp
một giải thuật để xem xét trạng thái của hệ thống để xác định deadlock có xảy ra hay
không và giải thuật phục hồi từ deadlock.
Nếu hệ thống không đảm bảo rằng deadlock sẽ không bao giờ xảy ra và cũng
không cung cấp một cơ chế để phát hiện và phục hồi deadlock thì có thể dẫn đến
trường hợp hệ thống ở trong trạng thái deadlock. Trong trường hợp này, deadlock
không được phát hiện sẽ làm giảm năng lực hệ thống vì tài nguyên đang được giữ bởi
những quá trình mà chúng không thể thực thi, đi vào trạng thái deadlock. Cuối cùng,
hệ thống sẽ dừng các chức năng và cần được khởi động lại bằng thủ công.
Mặc dù phương pháp này dường như không là tiếp cận khả thi đối với vấn đề
deadlock nhưng nó được dùng trong một số hệ điều hành. Trong nhiều hệ thống,
deadlock xảy ra không thường xuyên; do đó phương pháp này là rẻ hơn chi phí cho
phương pháp ngăn chặn deadlock, tránh deadlock, hay phát hiện và phục hồi deadlock
mà chúng phải được sử dụng liên tục. Trong một số trường hợp, hệ thống ở trong
trạng thái cô đặc nhưng không ở trạng thái deadlock. Như thí dụ, xem xét một quá
trình thời thực chạy tại độ ưu tiên cao nhất (hay bất cứ quá trình đang chạy trên bộ định thời biểu không trưng dụng) và không bao giờ trả về điều khiển đối với hệ điều
hành. Do đó, hệ thống phải có phương pháp phục hồi bằng thủ công cho các điều
kiện không deadlock và có thể đơn giản sử dụng các kỹ thuật đó cho việc phục hồi
deadlock.

-Hệ thống có 12 ổ băng.
-Có 3 tiến trình P1,P2,P3.

Tiến trình	Được cấp (đang giữ)	Max
P1	5	10
P2	2	4
P3	2	9

a) Chứng minh trạng thái là an toàn.
-Hệ có (Available)=Tổng- (P1+ P2 + P3)= 12- (5+2+2)=3.
-Need= Max- Allocation(đang giữ).

	Need
P1	10-5 =5
P2	4-2 =2
P3	9-2= 7

Work	Need(i)	P(i)	Allocation
3 >=	2	P2	2
5 >=	4	P1	5
10 >=	7	P3	2

- Kết luận :
+Tồn tại một chuỗi an toàn= {P2,P1,P3}
+Vậy trạng thái hệ thống ở thời điểm To là an toàn.

b) Xác định có nên đáp ứng nhu cầu cần thêm một ổ băng nữa của P3?
-Xét điều kiện :
+ Request(1) <= Need(i) thỏa vì 1<=7.
+Request(1) <= Available thỏa vì 1<=3.
Available = Tổng - (P1+P2+P3) = 12- (5+2 +3)=2.
Trạng thái mới là

	Đang giữ	Need	Hệ có
P1	5	5	2
P2	2	2	2
P3	3	6	2

[tr]

Work	Need(i)	P(i)	Allocation
2 >=	2	P2	2
4 <	5	P1	5

Kết luận:
+ Không tồn tại chuỗi an toàn nào vì Work < P1 và nếu thay cho P3 thì Work < P3
+Vậy trạng thái ở thời điểm T1 là không an toàn
+ Không thể cấp thêm cho P3 thêm một máy nữa vỉ có thể gây ra deadlock.

[img] [/img]

1/ dùng giải thuật nhà băng để chứng minh trạng thái này an toàn.
2/ xác định có nên đáp ứng yêu cầu <0,4,3,0> của tiến trình P1?

GIẢI:
1/chứng minh trạng thái an toàn
-tính Need = MAX - Allocation

Tiến 		  Need
Trình		A  B  C  D
P0 		0  0  0  0
P1 		0  7  5  0
P2 		1  0  0  2
P3 		0  0  2  0
P4 		0  6  4  2

-Tìm chuỗi an toàn của hệ thống:

   Work       >=        Needi            Pi      Allocation
A   B   C   D 	   A   B   C   D                A   B   C   D
1   5   2   0 	   0   0   2   0         P3     0   6   3   2
1  11   5   2 	   0   6   4   2         P4     0   0   1   4
1  11   6   6 	   1   0   0   2         P2     1   3   5   4
2  14  11  10 	   0   7   5   0         P1     1   0   0   0
3  14  11  10 	   0   0   0   0         P0     0   0   1   2

Từ đây suy ra hệ thống tồn tại chuỗi an toàn = {P3,P4,P2,P1,P0} => hệ thống tại thời điểm này an toàn.

2/Giả sử P1 có yêu cầu mới = <0,4,3,0>
Dựa vào yêu cầu mới của P1 ta có thể khẳng định không nên đáp ứng yêu cầu của P1 lý do:
vì không đáp ứng điều kiện Request1 <= Available
Suy ra: <0,4,3,0> Không <= (1,5,2,0)

giải thích thêm : việc xem xét có đáp ứng y/cầu mới hay kô thì phải thỏa 2 đk sau :
1. Request(i) <= Available
2. Request(i) <= MAX(i)

Đề bài :
Có 5 tiến trình {P0,P1,P2,P3,P4} và 3 loại tài nguyên A(10 phiên bản), B(5 phiên bản), C(7 phiên bản). Tại thời điểm T0 :
TT Đang Giữ MAX Hệ Có
ABC ABC ABC
P0 010 753 332
P1 200 322
P2 302 902
P3 211 222
P4 002 433
a) Tìm tất cả các chuỗi an toàn có thể có của hệ thống.
b) Giả xử P1 bây giờ nêu y/cầu mới là (1,0,2) thì xác định xem có nên đáp ứngy/cầu của P1 hay kô? vì sao?

Bài giải
a)
Tính Available = (10,5,7) - (7,2,5) = (3,3,2)
Tính Need = MAX - Allocation
TT Need
ABC
P0 743
P1 122
P2 600
P3 011
P4 431
Tìm chuỗi an toàn :
Work >= Needi Pi Allocation
ABC ABC ABC
332 011 P3 211
543 431 P4 002
545 122 P1 200
745 743 P0 010
755 600 P2 302
=> Chuỗi an toàn = {P3,P4,P1,P0,P2}
Work >= Needi Pi Allocation
ABC ABC ABC
332 011 P3 211
543 431 P4 002
545 122 P1 200
745 600 P2 302
1047 743 P0 010
=> Chuỗi an toàn = {P3,P4,P1,P2,P0}

Work >= Needi Pi Allocation
ABC ABC ABC
332 011 P3 211
543 112 P1 200
743 743 P0 010
753 600 P2 302
1055 431 P4 002
=> Chuỗi an toàn = {P3,P1,P0,P2,P4}
Work >= Needi Pi Allocation
ABC ABC ABC
332 122 P1 200
532 431 P4 002
534 011 P3 211
745 743 P0 010
755 600 P2 302
=> Chuỗi an toàn = {P1,P4,P3,P0,P2}
Work >= Needi Pi Allocation
ABC ABC ABC
332 122 P1 200
532 431 P4 002
534 011 P3 211
745 600 P2 302
1047 743 P0 010
=> Chuỗi an toàn = {P1,P4,P3,P0,P2}
Work >= Needi Pi Allocation
ABC ABC ABC
332 122 P1 200
532 011 P3 211
743 431 P4 002
745 743 P0 010
755 600 P2 302
=> Chuỗi an toàn = {P1,P3,P4,P0,P2}
Work >= Needi Pi Allocation
ABC ABC ABC
332 122 P1 200
532 011 P3 211
743 431 P4 002
745 600 P2 302
1047 743 P0 010
=> Chuỗi an toàn = {P1,P3,P4,P0,P2}
b)P1 y/cầu mới là (1,0,1) thì y/cầu này thoả đk:
- Request1 <= Need1 vì (1,0,1) <= (1,2,2)
- Request1 <= Available vì (1,0,1) <= (3,3,2)
Nên trạng thái mới là :
TT Đang Giữ MAX Hệ Có
ABC ABC ABC
P0 010 753 230
P1 302 322
P2 302 902
P3 211 222
P4 002 433
Tính Need = MAX - Allocation
TT Need
ABC
P0 743
P1 020
P2 600
P3 011
P4 431
Work >= Needi Pi Allocation
ABC ABC ABC
230 020 P1 200
430 011 P3 211
641 431 P4 002
643 600 P2 302
942 743 P0 010 =>tại thời điểm này kô thể cấp phát cho P0 vì (9,4,2) ko >= (7,4,3)

Work >= Needi Pi Allocation
ABC ABC ABC
230 011 P3 211
441 433 P4 002
443 020 P1 010
453
=>tại thời điểm này kô thể cấp phát cho P2 vì (4,5,3) kô >= (6,0,0)
=>tại thời điểm này kô thể cấp phát cho P0 vì (4,5,3) kô >= (7,4,3)

Work >= Needi Pi Allocation
ABC ABC ABC
230 011 P3 211
441 020 P1 010
451 431 P1 002
453
=>tại thời điểm này kô thể cấp phát cho P2 vì (4,5,3) ko >= (6,0,0)
=>tại thời điểm này kô thể cấp phát cho P0 vì (4,5,3) ko >= (7,4,3)

Kết Luận : Tìm được chuỗi an toàn ={P1,P3,P4,P0,P2} Vậy trạng thái hệ thống an toàn

Một hệ thống có 12 ổ băng từ và 3 tiến trình với bảng cấp phát tài nguyên sau:

Tiến trình	Đã được cấp ( số ổ băng)	Tối đa cần ( số ổ băng)
P1	5	10
P2	2	4
P3	2	9

Dùng thuật giải nhà băng :
a. Chứng minh trạng thái an toàn
b.Có nên đáp ứng hay không yêu cầu xin thêm 1 đĩa nữa của P3

Giải

a. Avatlable = 12 -(5+2+2) = 3
Need = Max - Allocation

P[i]	Allocation	Max	Need
P1	5	10	5
P2	2	4	2
P3	2	9	7

Xét tại thời điểm Ti:

Work>=	Need[i]	P[i]	Allocation[i]
2(Avilable)	2	P2	2
4	5	P1	5
10	7	P3	2

Vậy tồn tại chuỗi an toàn . Suy ra trạng thái ở trạng thái an toàn.

b. Yêu cầu thêm 1 ổ băng của P3 thỏa Request 3<= Need 3 và Request 3 <= Available. Ta có trạng thái mới:
Avatlable = 12 -(5+2+3) = 2

P[i]	Allocation	Max	Need
P1	5	10	5
P2	2	4	2
P3	3	9	6

Xét tại thời điểm Ti:
[tr]

Work>=	Need[i]	P[i]	Allocation[i]
3(Avilable)	2	P2	2
4 <	5

Vậy không tồn tại chuỗi an toàn. Suy ra không nên cấp cho P3 thêm 1 ổ băng . Nếu đáp ứng sẽ làm mất trạng thái an toàn của hệ thống

Giải thích thuật giải Nhà băng
Dữ liệu : - có 5 tiến trình : P0,……,P4 (Ví dụ là : 5 công ty khác nhau cần vay )
- 3 loại tài nguyên : A(10 phiên bản), B(5 phiên bản), C(7 phiên bản)
=>Đây là các loại tiền mà nhà băng có.
- Tại thời điểm To:
Đang giữ(Allocation) Max Hệ có (Available)
A B C A B C A B C
3 3 2
Po 0 1 0 7 5 3
P1 2 0 0 3 2 2
P2 3 0 2 9 0 2
P3 2 1 1 2 2 2
P4 0 0 2 4 3 3

Tổng loại tiền mà các công ty có (Cộng theo cột từ trên xuống của Allocation)
Tổng :7 2 5

Chú ý :
- Allocation tổng số các loại tiền mà các công ty đang có
- Max : Tổng các loại tiền (tối đa ) mà các công ty có thể có
- Hệ có : Available = ( 10 ,5 ,7 ) – ( 7, 2 ,5 ) = ( 3 ,3 ,2 )
Ta có : Need = Max – Allocation
=>Số loại tiền tối đa mà các công ty có thể vay thêm.
Ta có ma trận sau : Need
A B C
P0 7 4 3 (7,5,3) – (0,1,0)
P1 1 2 2 (3,2,2) – (2,0,0)
P2 6 0 0 (9,0,2) - (3,0,2)
P3 0 1 1 (2,2,2) - (2,1,1)
P4 4 3 1 (4,3,3) – (0,0,2)

Giả sử tại thời điểm To công ty : Ta phải kiểm tra tổng số các loại tiền mà công ty cần : Need <= Work : hệ số các loại tiền có trong nhà băng. Trong thời điểm này thì chỉ có P1,P3 là thỏa điều kiện được vay trước.
Giả sử P1 vay trước : Ta có bảng sau đảm bảo số tiền vay không vượt qua số tiền nhà băng cần có.
Work Need(i) P(i) Allocation
A B C A B C A B C
3 2 2 1 2 2 P1 2 0 0
Số tiền ít nhất nhà băng cần có cho P1 vay là (3,2,2)
Vậy hệ số tiền mà nhà băng có ít nhẩt cho công ty tiếp theo vay là:
Work = (3,2,2)+(2,0,0) = (5,3,2)
Ta xét hệ số các loại tiền Need <=Work. Trong trường hợp này thì P1 và P4 có thể vay.Giả sử P3 vay.Và làm các bước tương tự cho các công ty còn lại ta có bảng sau
Work Need(i) P(i) Allocation
A B C A B C A B C
3 2 2 1 2 2 P1 2 0 0

5 3 2 0 1 1 P3 2 1 1
7 4 3 4 3 1 P4 0 0 2
7 4 5 6 0 0 P2 3 0 2
10 4 7 7 4 3 P0 0 1 0

Chú ý : Hệ số các loại tiền của nhà băng cần có để cho vay (10,4,7) <= (10,5,7) các tài nguyên ban đầu
Như vậy : Ở thời điểm To hệ thống nhà băng trong trạng thái an toàn vì tồn tại chuỗi an toàn : < P1 ,P3 ,P4 ,P2 ,P0 >

tại thời điểm này P2 đã ngủ nhưng vẫn yêu cầu R2 cấp tài nguyên được vì đây là các tiến trình đa luồng, có thể có nhiều luồng đã ngủ nhưng có một số luồng vẫn thức và gửi yêu cầu cấp phát tài nguyên tới R2

DeadLock : Tình huống bị kẹt của một nhóm tiến trình do mỗi tiến trình trong nhóm đều chờ một sự kiện (event) có thể chỉ được gây ra bởi một tiến trình khác.

Ví dụ : Do con đường nhỏ,2 xe ô tô đi ngược chiều nhau.Nên 2 xe không thể đi về phía mình muốn được.

hoxuanvu_I12A đã viết:Giải thích thuật giải Nhà băng
Dữ liệu : - có 5 tiến trình : P0,……,P4 (Ví dụ là : 5 công ty khác nhau cần vay )
- 3 loại tài nguyên : A(10 phiên bản), B(5 phiên bản), C(7 phiên bản)
=>Đây là các loại tiền mà nhà băng có.
- Tại thời điểm To:
Đang giữ(Allocation) Max Hệ có (Available)
A B C A B C A B C
3 3 2
Po 0 1 0 7 5 3
P1 2 0 0 3 2 2
P2 3 0 2 9 0 2
P3 2 1 1 2 2 2
P4 0 0 2 4 3 3

Tổng loại tiền mà các công ty có (Cộng theo cột từ trên xuống của Allocation)
Tổng :7 2 5

Chú ý :
- Allocation tổng số các loại tiền mà các công ty đang có
- Max : Tổng các loại tiền (tối đa ) mà các công ty có thể có
- Hệ có : Available = ( 10 ,5 ,7 ) – ( 7, 2 ,5 ) = ( 3 ,3 ,2 )
Ta có : Need = Max – Allocation
=>Số loại tiền tối đa mà các công ty có thể vay thêm.
Ta có ma trận sau : Need
A B C
P0 7 4 3 (7,5,3) – (0,1,0)
P1 1 2 2 (3,2,2) – (2,0,0)
P2 6 0 0 (9,0,2) - (3,0,2)
P3 0 1 1 (2,2,2) - (2,1,1)
P4 4 3 1 (4,3,3) – (0,0,2)

Giả sử tại thời điểm To công ty : Ta phải kiểm tra tổng số các loại tiền mà công ty cần : Need <= Work : hệ số các loại tiền có trong nhà băng. Trong thời điểm này thì chỉ có P1,P3 là thỏa điều kiện được vay trước.
Giả sử P1 vay trước : Ta có bảng sau đảm bảo số tiền vay không vượt qua số tiền nhà băng cần có.
Work Need(i) P(i) Allocation
A B C A B C A B C
3 2 2 1 2 2 P1 2 0 0
Số tiền ít nhất nhà băng cần có cho P1 vay là (3,2,2)
Vậy hệ số tiền mà nhà băng có ít nhẩt cho công ty tiếp theo vay là:
Work = (3,2,2)+(2,0,0) = (5,3,2)
Ta xét hệ số các loại tiền Need <=Work. Trong trường hợp này thì P1 và P4 có thể vay.Giả sử P3 vay.Và làm các bước tương tự cho các công ty còn lại ta có bảng sau
Work Need(i) P(i) Allocation
A B C A B C A B C
3 2 2 1 2 2 P1 2 0 0

5 3 2 0 1 1 P3 2 1 1
7 4 3 4 3 1 P4 0 0 2
7 4 5 6 0 0 P2 3 0 2
10 4 7 7 4 3 P0 0 1 0

Chú ý : Hệ số các loại tiền của nhà băng cần có để cho vay (10,4,7) <= (10,5,7) các tài nguyên ban đầu
Như vậy : Ở thời điểm To hệ thống nhà băng trong trạng thái an toàn vì tồn tại chuỗi an toàn : < P1 ,P3 ,P4 ,P2 ,P0 >

Bạn Sai chỗ này available (3,2,2)->(3,3,2) mình xin sữa lại như sau
Work Need(i) P(i) Allocation
A B C A B C A B C
3 3 2 1 2 2 P1 2 0 0
Số tiền ít nhất nhà băng cần có cho P1 vay là (3,3,2)
Vậy hệ số tiền mà nhà băng có ít nhẩt cho công ty tiếp theo vay là:
Work = (3,3,2)+(2,0,0) = (5,3,2)
Ta xét hệ số các loại tiền Need <=Work. Trong trường hợp này thì P1 và P4 có thể vay.Giả sử P3 vay.Và làm các bước tương tự cho các công ty còn lại ta có bảng sau
Work Need(i) P(i) Allocation
A B C A B C A B C
3 3 2 1 2 2 P1 2 0 0

5 3 2 0 1 1 P3 2 1 1
7 4 3 4 3 1 P4 0 0 2
7 4 5 6 0 0 P2 3 0 2
10 4 7 7 4 3 P0 0 1 0

Chú ý : Hệ số các loại tiền của nhà băng cần có để cho vay (10,4,7) <= (10,5,7) các tài nguyên ban đầu
Như vậy : Ở thời điểm To hệ thống nhà băng trong trạng thái an toàn vì tồn tại chuỗi an toàn : < P1 ,P3 ,P4 ,P2 ,P0 >

Một hệ thống có 3 ổ băng từ và 3 tiến trình P1, P1, P3 với trạng thái cấp phát tài nguyên ở thời điểm Ti thể hiện bằng véc-tơ Allcation=(1,0,1) và Max = (1,2,2).
Dùng thuật giải nhà băng để:
a> Chứng minh trạng thái an toàn.
b> Xác định có nên đáp ứng hay không yêu cầu xin thêm 1 ổ nữa của P3.
Giải:
a.Xét tại thời điểm Ti mà 3 tiến trình được cấp phát như đề bài ta có:



Trong đó: Need[i] = Max[i] - Allocation[i]
Available = 3 – (1 + 0 + 1)= 1
Tìm chuỗi an toàn:



Vậy tai thời điểm T0 tồn tại chuỗi {P1, P2, P3}. Suy ra, hệ thống tại thời điểm Ti ở trạng thái an toàn.
b. Ta thấy, yêu cầu cần thêm 1 ổ nữa của P3 thỏa các điều kiện:
+ Requuest3 <= Need3 và Request1 <= Available
+ Hơn nữa việc cấp phát thêm 1 ổ nữa cho P3 thì hệ thống vẫn ở trạng thái an toàn vì tồn tại chuỗi an toàn {P1, P2, P3} trong khi tài nguyên trong hệ thống không còn nữa



Do vậy ta có thể cấp thêm cho yêu cầu xin thêm 1 của P3 tại thời điểm này.

NgoPhuQuoc_I12C đã viết:-Hệ thống có 12 ổ băng.
-Có 3 tiến trình P1,P2,P3.

Tiến trình	Được cấp (đang giữ)	Max
P1	5	10
P2	2	4
P3	2	9

a) Chứng minh trạng thái là an toàn.
-Hệ có (Available)=Tổng- (P1+ P2 + P3)= 12- (5+2+2)=3.
-Need= Max- Allocation(đang giữ).

	Need
P1	10-5 =5
P2	4-2 =2
P3	9-2= 7

Work	Need(i)	P(i)	Allocation
3 >=	2	P2	2
5 >=	4	P1	5
10 >=	7	P3	2

- Kết luận :
+Tồn tại một chuỗi an toàn= {P2,P1,P3}
+Vậy trạng thái hệ thống ở thời điểm To là an toàn.

b) Xác định có nên đáp ứng nhu cầu cần thêm một ổ băng nữa của P3?
-Xét điều kiện :
+ Request(1) <= Need(i) thỏa vì 1<=7.
+Request(1) <= Available thỏa vì 1<=3.
Available = Tổng - (P1+P2+P3) = 12- (5+2 +3)=2.
Trạng thái mới là

	Đang giữ	Need	Hệ có
P1	5	5	2
P2	2	2	2
P3	3	6	2

[tr]

Work	Need(i)	P(i)	Allocation
2 >=	2	P2	2
4 <	5	P1	5

Kết luận:
+ Không tồn tại chuỗi an toàn nào vì Work < P1 và nếu thay cho P3 thì Work < P3
+Vậy trạng thái ở thời điểm T1 là không an toàn
+ Không thể cấp thêm cho P3 thêm một máy nữa vỉ có thể gây ra deadlock.

bạn ơi giải thích dùm mình chỗ chuỗi an toàn được không, làm sao để mình xác định cái P nào đầu tiên, mình dựa vào cái j vậy bạn.thanks

Thay moi day hoi chieu ma cac anh em phang nhau ghe qua.Pai phuc.Nhin thay chong ca mat.

Admin
- Cần trình bày lại cho Đẹp và Đúng !
- Nên nhập văn bản, không dùng hình tất cả !

**Lúc 1h00 : P1 và P2 cùng có nhu cầu về tài nguyên tới R1 và R2 (R1 và R2 chỉ có 1 phiên bản duy nhất)

**Lúc 1h05 : yêu cầu của P1 được HĐH đáp ứng và chuyển thành Cung ấn định ,nối phiên bản duy nhất của R1 với P1,P1 được R1 cấp,P2 yêu cầu R1

**Lúc 1h10 :yêu cầu của P2 được HĐH đáp ứng và chuyển thành Cung ấn định,nối phiên bản duy nhất của R2 với P2 ,P2 được R2 cấp và P2 vẫn còn yêu cầu R1 =>trạng thái không an toàn có thể xảy ra Deadlock
**Nhược điểm của RAG là chỉ áp dụng trong trường hợp mỗi tài nguyên chỉ có 1 phiên bản duy nhất

Admin
Chưa đạt yêu cầu vì cần phải "chẻ nhỏ" ra nhiều trạng thái hơn nữa !

LeXuanHau (I12C) đã viết:

NgoPhuQuoc_I12C đã viết:-Hệ thống có 12 ổ băng.
-Có 3 tiến trình P1,P2,P3.

Tiến trình	Được cấp (đang giữ)	Max
P1	5	10
P2	2	4
P3	2	9

a) Chứng minh trạng thái là an toàn.
-Hệ có (Available)=Tổng- (P1+ P2 + P3)= 12- (5+2+2)=3.
-Need= Max- Allocation(đang giữ).

	Need
P1	10-5 =5
P2	4-2 =2
P3	9-2= 7

Work	Need(i)	P(i)	Allocation
3 >=	2	P2	2
5 >=	4	P1	5
10 >=	7	P3	2

- Kết luận :
+Tồn tại một chuỗi an toàn= {P2,P1,P3}
+Vậy trạng thái hệ thống ở thời điểm To là an toàn.

b) Xác định có nên đáp ứng nhu cầu cần thêm một ổ băng nữa của P3?
-Xét điều kiện :
+ Request(1) <= Need(i) thỏa vì 1<=7.
+Request(1) <= Available thỏa vì 1<=3.
Available = Tổng - (P1+P2+P3) = 12- (5+2 +3)=2.
Trạng thái mới là

	Đang giữ	Need	Hệ có
P1	5	5	2
P2	2	2	2
P3	3	6	2

[tr]

Work	Need(i)	P(i)	Allocation
2 >=	2	P2	2
4 <	5	P1	5

Kết luận:
+ Không tồn tại chuỗi an toàn nào vì Work < P1 và nếu thay cho P3 thì Work < P3
+Vậy trạng thái ở thời điểm T1 là không an toàn
+ Không thể cấp thêm cho P3 thêm một máy nữa vỉ có thể gây ra deadlock.

bạn ơi giải thích dùm mình chỗ chuỗi an toàn được không, làm sao để mình xác định cái P nào đầu tiên, mình dựa vào cái j vậy bạn.thanks

Bạn dựa vào hai giá trị Available (TN hệ thống đang sẵn sàng) và giá trị Needi của tiến trình Pi (tiến trình này xét theo thứ tự từ trên xuống dưới) để biết sẽ cấp TN cho tiến trình thứ i nào là hợp lý.

a) Giải thích bảng:

Work	Need(i)	P(i)	Allocation
3 >=	2	P2	2
5 >=	5	P1	5
10 >=	7	P3	2

hàng 1:
+ TN hệ thống đang có sẵn= 12 - (5+2+2) = 3
+ P1 cần 5 TN, TN hệ thống đang có sẵn kg đủ để cấp cho P1. Xét tiếp tới tiến trình P2, P2 chỉ cần 2 TN, (2<=3) nên tại thời điểm này, sẽ chọn P2 để cấp TN.
hàng 2:
+ Sau khi P2 thực hiện xong, nó sẽ trả hết TN lại cho hệ thống. Tại thời điểm này TN hệ thống đang có sẵn là 5.
+ P1 cần 5 TN, TN hệ thống sẵn sàng là 5, (5<=5) => chọn P1 để cấp tiếp tài nguyên
hàng 3:
+ Sau khi P1 thực hiện xong, nó sẽ trả hết TN lại cho hệ thống. Tại thời điểm này, TN hệ thống đang có sẵn là 10.
+ P3 cần 7 TN, hệ thống có sẵn là 10, (7<=10) => chọn tiếp P3 để cấp tài nguyên

=>Tìm được chuỗi an toàn {P2, P1, P3}. Vậy trạng thái hệ thống là an toàn

-Hệ thống có 12 ổ băng.
-Có 3 tiến trình P1,P2,P3.

Tiến trình	Được cấp (đang giữ)	Max
P1	5	10
P2	2	4
P3	2	9

a) Chứng minh trạng thái là an toàn.
-Hệ có (Available)=Tổng- (P1 P2 P3)= 12- (5 2 2)=3.
-Need= Max- Allocation(đang giữ).

	Need
P1	10-5=5
P2	4-2=2
P3	9-2=7

vì hệ số là 3, nên để work >= Need(i), nên chỉ chọn P2 vì Need của P2 =2 thỏa điều kiện nên tiến trình P2 xét trước.
Tiếp tục lấy allocation work (2 3=5) ,5 so với bảng Need(i) thỏa điều kiện với P1 vì Need (P1=5), nên P(i) lúc này =5, Làm tương tự ta cho đến P3, sẽ được bảng như sau

	Work	Need(i)	P(i)	Allocation
Available	3 >=	2	P2	2
	5 >=	5	P1	5
	10 >=	7	P3	2

- Kết luận :
-Tìm được chuỗi an toàn= {P2,P1,P3} vậy trạng thái hệ thống an toàn.
b) Xác định có nên đáp ứng nhu cầu cần thêm một ổ băng nữa của P3?
-Xét điều kiện :
Request(1) <= Need(i) thỏa vì 1<=7.
Request(1) <= Available thỏa vì 1<=3.
Available = Max - (P1 P2 P3) = 12- (5 2 3)=2.
Ta có trạng thái mới là

	Đang giữ	Need	Hệ có
P1	5	5	2
P2	2	2
P3	3	6

Work	Need(i)	P(i)	Allocation
2 >=	2	P2	2
4 <	5	P1	5

Kết luận:
Không tồn tại chuỗi an toàn nào vì Work < P1 và nếu thay cho P3 thì Work < P3
Vậy trạng thái ở thời điểm lúc ban đầu là an toàn
Nên không thể cấp thêm cho P3 thêm một máy nữa vỉ có thể gây ra deadlock.

Đã chỉnh sửa

-------------------------------------------------------------------------------------------------------

-------------------------------------------------------------------------------------------------------

-------------------------------------------------------------------------------------------------------

-------------------------------------------------------------------------------------------------------

-------------------------------------------------------------------------------------------------------

-------------------------------------------------------------------------------------------------------


Admin
- Rất đẹp và Đúng với yêu cầu ! Trình bày có Sáng tạo !
- Cần sửa: "Cung Ứng định" (sai !) thành "Cung Ấn định" (Assignment Edge)
- Tiến trình P1 không nhất thiết phải có 2 luồng A-B. Chỉ 1 luồng A cũng được: Lúc đầu A yêu cầu R1 và được cấp, sau đó một khoảng thời gian, yêu cầu thêm R2 vì cần cả 2 loại tài nguyên cùng một lúc.

Câu 4: KHÁI NIỆM TRẠNG THÁI AN TOÀN VÀ GIẢI PHÁP TRÁNH DEADLOCK
Thế nào là trạng thái an toàn của hệ thống
- Một trạng thái được gọi là an toàn "safe" nếu tồn tại một cách mà trong một khoảng thời gian hữu hạn nào đó hệ thống có thể cấp phát tài nguyên thảo mãn cho tất cả Process thực thi hoàn tất
- khi đó hệ thống tồn tại một chuỗi an toàn (p1,p2.......,pn) bao gồm tất cả các tiến trình sao cho với mỗi pi các tài nguyên mà nó yêu cầu có thể được đáp ứng bởi số lượng hiện có cộng thêm của tất cả các pj mà j<i
- nếu các TN yêu cầu không có đủ pi phải chờ cho đến khi tất cả các pj trả lại các TN mà chúng chiễm giữ
- Khi pi nhận được đủ TN cần thiết nó sự dụng và trả lại HĐH để pi+1 có thể vận hành cứ như thế cho đến pn
- Khi một process yêu cầu một tài nguyên đang sẵn có hệ thống sẽ kiểm tra nếu việc cấp phát này không dẫn đến tình trạng unsafe thì sẽ cấp phát ngay
Trình bày 4 cách ngăn chặn Deadlock
-Để ngăn chặn Deadlock ta phải làm sao cho ít nhất trong 4 điều kiện dẫn đến Deadlock không xảy ra cụ thể
- Với Mutual Exclusion: Đảm bảo TN nào cũng dùng chung được cùng một lúc bởi nhiều tiến trình
- Với Hold and Wait:
1 - Khi TT yêu cầu TN nó không được giữ 1TN nào khác
2- TT phải yêu cầu và được cấp tất cả các TN mà nó cần ngay đầu công việc
- Với No Preemption
1 - Khi TT giữ TN mà xin thêm sao không được các TN mà nó giữ phải bị tiếm quyền sự dụng và trả lại HĐH
2 - Khi TT xin thê TN nếu TN này đang được giữ bởi TT khác đang ở trạng thái chờ TN của TT khác này bị tiếm quyền sự dụng để cấp cho TT đang xin
- Với Circular : Cấp TN theo một thứ tự nào đấy

LeXuanHau (I12C) đã viết:
bạn ơi giải thích dùm mình chỗ chuỗi an toàn được không, làm sao để mình xác định cái P nào đầu tiên, mình dựa vào cái j vậy bạn.thanks

mình xin trả lời câu hỏi của bạn Lê Xuân Hậu, nếu ace thấy chưa đúng hay chưa thỏa đáng thì cứ chém thẳng tay nha.
thực ra tìm chuỗi an toàn rất dễ, tại một thời điểm (ở đây mình xin phép nói là bài toán cho dễ hiểu) có thể có nhiều chuỗi an toàn khác nhau.
Ở ví dụ của thầy trong Slide là thầy đã biết trước kết quả nên thầy chọn ra một chuỗi an toàn tốt nhất đấy thôi, còn nếu muốn dễ hiểu thì bạn cứ duyệt từ trên xuống, nếu thấy tiến trình P_i nào có Need_i <= Work thì bạn đưa vào xét thôi (chú ý: Work đầu tiên cho bằng Available, sau đó Work = Work + Allocation_i của tiến trình P_i vừa được chọn).
nói thì có vẻ khó hiểu để mình làm luôn một ví dụ cho dễ hiểu (tuy hơi lười nhưng vì sự nghiệp kháng chiến... quất tới thôi )
Bài Tập (lấy lại ví dụ của mình trong bài trước)

1/ dùng giải thuật nhà băng để chứng minh trạng thái này an toàn.
2/ xác định có nên đáp ứng yêu cầu <0,4,3,0> của tiến trình P1?

GIẢI:
1/chứng minh trạng thái an toàn
-tính Need = MAX - Allocation

Tiến 		  Need
Trình		A  B  C  D
P0 		0  0  0  0
P1 		0  7  5  0
P2 		1  0  0  2
P3 		0  0  2  0
P4 		0  6  4  2

-Tìm chuỗi an toàn của hệ thống:
trước tiên cho Work = Available. Sau đó duyệt theo bảng Need từ trên xuống nếu thỏa Need<=Work thì chọn. Tiến trình nào chọn rồi hoặc không thỏa thì bỏ qua, kiểm tra tiến trình kế tiếp, đến cuối dãy thì lặp lại.

   Work       >=        Needi            Pi      Allocation
A   B   C   D 	   A   B   C   D                A   B   C   D
1   5   2   0 	   0   0   0   0         P0     0   0   1   2
1   5   3   2 	   1   0   0   2         P2     1   3   5   4
2   8   8   6 	   0   0   2   0         P3     0   6   3   2
2  14  11  8 	   0   6   4   2         P4     0   0   1   4
2  14  12  12 	   0   7   5   0         P1     1   0   0   0

Từ đây suy ra hệ thống tồn tại chuỗi an toàn = {P0,P2,P3,P4,P1} => hệ thống tại thời điểm này là an toàn.
-ở đây đã "may mắn" tìm ra được chuỗi an toàn. dừng lại và kết luận trạng thái này an toàn.
-nếu không tìm ra chuỗi an toàn thì ta duyệt theo một thứ tự khác cũng gần như vậy. miễn tìm ra được chuỗi an toàn thỏa mãn tất cả các điều kiện.
****Trên đây là cách duyệt cơ bản. Vì có thể có nhiều chuỗi an toàn khác nhau nên có nhiều cách tìm ra nó. Theo mình nghĩ cách của thầy trong ví dụ ở Slide là khá tối ưu, vì trong những tiến trình thỏa điều kiện Need<= Word thì chọn tiến trình nào có Need thấp và Allocation cao trước. Như thế sẽ có nhiều Availble (Work) dư ra để dễ dàng cấp cho các tiến trình sau hơn. cách này mà không tìm ra được chuỗi an toàn thì không cách nào tìm ra được (Nghĩa là không tồn tại chuỗi an toàn)
Và đây là kết quả của một thứ tự duyệt khác:

   Work       >=        Needi            Pi      Allocation
A   B   C   D 	   A   B   C   D                A   B   C   D
1   5   2   0 	   0   0   2   0         P3     0   6   3   2
1  11   5   2 	   0   6   4   2         P4     0   0   1   4
1  11   6   6 	   1   0   0   2         P2     1   3   5   4
2  14  11  10 	   0   7   5   0         P1     1   0   0   0
3  14  11  10 	   0   0   0   0         P0     0   0   1   2

Từ đây suy ra hệ thống tồn tại chuỗi an toàn = {P3,P4,P2,P1,P0} => hệ thống tại thời điểm này an toàn.
giống như bài viết của bạn Hiển đã tìm ra tất cả các chuỗi an toàn rồi đấy, các bạn có thể tham khảo thêm tại đây
2/Giả sử P1 có yêu cầu mới = (0,4,3,0)
Dựa vào yêu cầu mới của P1 ta có thể khẳng định không nên đáp ứng yêu cầu của P1 lý do:
vì không đáp ứng điều kiện Request1 <= Available
Suy ra: (0,4,3,0) Không <= (1,5,2,0)

đó là theo cách hiểu của mình tự "mổ xẻ" từ ví dụ thầy giải trên lớp. các bạn thấy không đúng chỗ nào không đúng hay không thỏa đáng thì góp ý cho mình nha.
tất cả vì sự nghiệp thi đậu

Admin
- Rất Hiểu bài, Nhiệt tình và Tự nhiên !
- Đã sửa đôi chỗ, nhất là Word (từ) => Work (biến tạm, làm việc, trung gian, dùng tích lũy tổng Available+Allocation_i1+Allocation_i2+...)

TranHuyCuong17 (I12A) đã viết:

ốh, Bác Cường vẽ đẹp quá. có đầu tư. phát huy nhé. chả bù với hình của em vẽ, hình của Bác ăn đứt rồi. khà khà

Một hệ thống có 12 ổ băng từ và 3 tiến trình với bảng cấp phát tài nguyên như sau:

Tiến trình	Đang giữ	Max
P1	5	10
P2	2	4
P3	2	9

Hệ thống có: Available = (số tài nguyên lúc đầu - đang giữ) = 12 - (5+2+2) = 3

Need = (Max - Đang giữ)

Tiến trình	Need
P1	5
P2	2
P3	7

	Work	>=	Need i	P i	Allocation
Available	3		2	P2	2
	5		5	P1	5
	10		7	P3	2

=> tìm được chuỗi an toàn = {P2,P1,P3}, vậy trạng thái hệ thống an toàn


Giả sử P3 yêu cầu thêm 1 ổ

yêu cầu này thỏa các điều kiện

Request3 <= Need 3 vì 1<=7

Request3 <= Availabe vì 1<=3

Tiến trình	Đang giữ	Max
P1	5	10
P2	2	4
P3	3	9

Hệ thống có: Available = (số tài nguyên lúc đầu - đang giữ) = 12 - (5+2+3) = 2

Need = (Max - Đang giữ)

Tiến trình	Need
P1	5
P2	2
P3	6

	Work	>=	Need i	P i	Allocation
Available	2		2	P2	2
	4		5	P1	3	ko thỏa
	4		6	P3	5	ko thỏa

--> tới đây, ko thỏa, nên ko biết kết luận thế nào, ai giúp dùm với