Thảo luận Bài 8

nguyenthimao_I12A đã viết:

dangvannhan_11h1010085 đã viết:

HoNgocTuan142(I12A) đã viết:

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+...)

Chào bạn !
Bạn vui có thể giải thích dùm mình cách duyệt các tiến trình được không?

   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

chổ cột Pi vì sao xét thứ tự P0 ->P2->P3->P4->P1 khi mình chưa biết chuỗi an toàn?

Bạn chú ý điều kiện Work>=Needi, Đầu tiên tính Available(Thầy đã nói theo thuật giải nhà băng lúc đầu Work=Available) rồi theo điều kiện Work>=Needi mà xét cái nào trước cái nào sau thôi! Ở trên bạn Tuấn cũng đã giải thích rõ rồi ban xem kỹ lại là hiểu ah!

Cảm ơn bạn mình hiểu rồi.Tks bạn nhìu!

huynhthao.hc11th2a đã viết:

Admin đã viết:Thảo luận những vấn đề liên quan đến Bài 8.

Định nghĩa Deadlock & Điều kiện cần để xảy ra deadlock

Định nghĩa Deadlock
- Trong hệ thống đa chương, nhiều quá trình có thể
cạnh tranh một số giới hạn tài nguyên.
- Một quá trình yêu cầu tài nguyên, nếu tài nguyên
không sẵn dùng tại thời điểm đó, quá trình đi vào
trạng thái chờ.
-Quá trình chờ có thể không bao giờ chuyển trạng thái
trở lại vì tài nguyên chúng yêu cầu bị giữ bởi những
quá trình khác
=>Trường hợp này gọi là deadlock(khóa chết).

Điều kiện cần để xảy ra deadlock :
Bốn điều kiện cần (necessary condition) để xảy ra
deadlock
1. Loại trừ tương hổ (Mutual exclusion): ít nhất một
tài nguyển được giữ trong chế độ không chia sẻ
2. Giữ và chờ cấp thêm tài nguyên (Hold and wait):
một process đang giữ ít nhất một tài nguyên và
đợi thêm tài nguyên do quá trình khác đang giữ
3. Không có ưu tiên (No preemption): tài nguyên không thể bị lấy lại,mà chỉ có thể được trả lại từ process đang giử tài nguyên đó khi nó muốn.
4. Chu trình (Circular wait): tồn tại một chu trình của các yêu cầu tài nguyên và tài nguyên đã được cấp phát.

Bổ sung thêm
Trường hợp deadlock có thể phát sinh nếu bốn điều kiện sau xảy ra cùng một lúc trong hệ thống:
1) Loại trừ hỗ tương: ít nhất một tài nguyên phả i được giữ trong chế độ không chia sẻ ; nghĩa là, chỉ một quá trình tại cùng một thời điểm có thể sử dụng tài nguyên. Nếu m ột quá trình khác yêu cầu tài nguyên đó, quá trình yêu cầu phải tạm dừng cho đến khi tài nguyên đượ c giải phóng.
2) Giữ và chờ cấp thêm tài nguyên : quá trình phải đang giữ ít nhất một tài nguyên và đang chờ để nhận tài nguyên thêm mà hiện đang được giữ bởi quá trình khác.
3) Không đòi lại tài nguyên từ quá trình đang giữ chúng : Các tài nguyên không thể bị đòi lại; nghĩa là, tài nguyên có thể được giải phóng chỉ tự ý bở i quá trình đang giữ nó, sau khi quá trình đó hoàn thành tác vụ.
4) Tồn tại chu trình trong đồ thị cấp phát tài nguyên: một tập hợp các quá trình {P0 , P1,…,Pn} đang chờ mà trong đó P0 đang chờ một tài nguyên được giữ bởi P1, P1 đang chờ tài nguyên đang giữ bởi P2 ,…,Pn-1 đang chờ tài nguyên đang được giữ bởi quá trình P0.

Chung quy tắc nghẽn đều bắt nguồn từ sự xung đột về tài nguyên của hai hoặc nhiều tiến trình đang hoạt động đồng thời trên hệ thống. Tài nguyên ở đây có thể là một ổ đĩa, một record trong cơ sở dữ liệu, hay một không gian địa chỉ trên bộ nhớ chính.Trường hợp deadlock có thể phát sinh nếu bốn điều kiện sau xảy ra cùng một lúc trong hệ thống:
1) Loại trừ hỗ tương
2) Giữ và chờ cấp thêm tài nguyên
3) Không đòi lại tài nguyên từ quá trình đang giữ chúng
4) Tồn tại chu trình trong đồ thị cấp phát tài nguyên

 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 ít nhất 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ỏa 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 1 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(tai nguyên) 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ữ 1 TN 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 nhưng 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êm 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 Wait: Cấp TN theo một thứ tự nào đấy.

Sao không thấy bài thuật giải nhà băng và bài thuật giải Round-Robin mà để thảo luận thầy nhỉ

1 hệ thống có 10 máy quét hình và 3 tiến trình P1, P2, 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 các vector


Allocation = (3, 1, 1 )


Và Max= (9, 4, 8 )


a) Dùng Thuật toán nhà băng để CM trạng thái an toàn


b) Xác định có nên đáp ứng hay không yêu cầu cấp them 1 máy
của P3


Giải


a) Thuật toán nhà băng:


Ta có: Available = 10 - (3+1+1) = 5


Need = Max – Allocation

P	Allocation[i]	Max[i]	Need[i]	Available
P1	3	9	6	5
P2	1	4	3
P3	1	8	7

Work >=	Need[i]	P[i]	Allocation[i]
5	3	P2	1
6	6	P1	3
9	7	P3	1

Vậy tồn tại chuỗi an toàn <P2,P1,P3>


=> Trạng thái ở thời điểm Ti là
an toàn





b) Xác định có nên đáp ứng hay không yêu cầu cấp thêm 1 máy
của P3:


Xét 2 trường hợp


- 1) Request3 <= Need3


Vì 1<= 6


- 2) Request3 <= Available


Vì 1<= 4

P[i]	Allocation[i]	Max[i]	Need[i]	Available
P1	3	9	6	4
P2	1	4	3
P3	2	8	6

Available = 10 - (3+1+2) = 4

Work >=	Need[i]	P[i]	Allocation[i]
4	3	P2	1
5	6(không thỏa ĐK)	P3	2

=>Trạng thái không
an toàn


Vậy: Không nên đáp ứng
yêu cầu cấp thêm 1 máy của P3


[i]Đây là bài giải của
Hiệp. Mong thầy và các bạn góp ý thêm.

chào bạn lê phúc hiệp mình có xem bài giải của bạn mình cũng làm tương tự nhưng có chỗ chữ màu đỏ mình chưa hiểu do mình làm khác bạn .Mong thầy và bạn xem lại ai đúng ai sai
1 hệ thống có 10 máy quét hình và 3 tiến trình P1, P2, 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 các vector

Allocation = (3, 1, 1 )
Và Max= (9, 4, 8 )

a) Dùng Thuật toán nhà băng để CM trạng thái an toàn
b) Xác định có nên đáp ứng hay không yêu cầu cấp them 1 máy
của P3


Giải
a) Thuật toán nhà băng:
Ta có: Available = 10 - (3+1+1) = 5
Need = Max – Allocation
P Allocation[i] Max[i] Need[i] Available
P1 3 9 6 5
P2 1 4 3
P3 1 8 7

Work >= Need[i] P[i] Allocation[i]
5 3 P2 1
6 6 P1 3
9 7 P3 1

Vậy tồn tại chuỗi an toàn
=> Trạng thái ở thời điểm Ti là
an toàn

b) Xác định có nên đáp ứng hay không yêu cầu cấp thêm 1 máy
của P3:

Xét 2 trường hợp

- 1) Request3 <= Need3

Vì 1<= 6 ????? chưa hiểu chỗ này,mình làm là 1<=7

- 2) Request3 <= Available

Vì 1<= 4 ????? chưa hiểu chỗ này,mình làm là 1<=5

P[i] Allocation[i] Max[i] Need[i] Available
P1 3 9 6 4
P2 1 4 3
P3 2 8 6

Available = 10 - (3+1+2) = 4

Work >= Need[i] P[i] Allocation[i]
4 3 P2 1
5 6(không thỏa ĐK) P3 2

=>Trạng thái không
an toàn
Vậy: Không nên đáp ứng
yêu cầu cấp thêm 1 máy của P3

phamduyI12A đã viết:

nguyenthimao_I12A đã viết:

dangvannhan_11h1010085 đã viết:

HoNgocTuan142(I12A) đã viết:

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+...)

Chào bạn !
Bạn vui có thể giải thích dùm mình cách duyệt các tiến trình được không?

   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

chổ cột Pi vì sao xét thứ tự P0 ->P2->P3->P4->P1 khi mình chưa biết chuỗi an toàn?

Bạn chú ý điều kiện Work>=Needi, Đầu tiên tính Available(Thầy đã nói theo thuật giải nhà băng lúc đầu Work=Available) rồi theo điều kiện Work>=Needi mà xét cái nào trước cái nào sau thôi! Ở trên bạn Tuấn cũng đã giải thích rõ rồi ban xem kỹ lại là hiểu ah!

OK! đồng ý là ngay Pi là P0 trc, nhưng tại sao mình k xét tới P1 rùi tới P2,P3,P4 là lại để P1 cuối, mình dự vào điều j để xét tiếp, mong các bạn giải thix dùm và nếu dc thì đưa ra 1 vd 1 trường hợp k thỏa, thanks!!!

Mình trình bày lại cách giải xíu bạn đọc thử xem hiểu ko nha, mình cũng tìm tự tìm hiểu và học thêm trên diễn đàn thôi :
Bài thuật giải nhà băng có 2 câu:
Đối với câu a:
1. Tính hệ có Available= (Tổng các loại tài nguyên-viết theo ma trận nếu nhiều)-(Tổng các loại tài nguyên mà các tiến trình đang giữ-viết theo ma trận nếu nhiều) . Trừ theo phương pháp ma trận nếu có nhiều loại tài nguyên .
2. Tính Need(i) của mỗi tiến trình.
3.Vẽ bảng gồm 4 cột với tên cột theo thứ tự work,need(i),P(i),Allocation(i). Nhớ chú ý cái tên loại tài nguyên ABC mà thầy nhắc trên lớp  .
4.Đầu tiên viết số tài nguyên mà hệ có tính được vào dòng đầu tiên ở cột "WORK" (chú ý điều kiện lúc đầu work=Available).
5.Đưa mắt nhìn nhanh tìm xem tiến trình nào chưa xét có need(i)- Nếu không có need(i) nào thỏa điều kiện thì =>Kết luận :"Không tồn tại chuỗi an toàn nên trạng thái ở thời điểm... là không an toàn". =>kết thúc bài toán.
- Nếu có thì viết tiếp các số liệu của tiến trình P(i) vừa tìm được vào hàng đang viết như sau: Need(i),P(i) là tên tiến trình mới tìm,Allocation là số tài nguyên ban đầu tiến trình đang giữ (đề cho ban đầu) =>Loại bỏ tiến trình mới viết để lần sau không xét nữa=>qua bước 6.
6.
+Nếu vẫn còn tiến trình để xét: Tính work ở dòng dưới =work ở dòng sát trên + Allocation ở dòng sát trên và viết vào cột work =>trở về lại bước 5.
+Nếu đã hết tiến trình để xét=>Đã tìm thấy 1 chuỗi an toàn (có thể có nhiều chuỗi nha, chỉ cần tìm 1 là đủ rồi, còn nếu muốn tìm hết chuỗi an toàn thì hãy theo phương pháp vét cạn). Kết luận :"Tồn tại chuỗi an toàn bằng (liệt kê tên các tiến trình trong cột P(i) từ trên xuống dưới. Vậy trạng thái ở thời điểm ... là an toàn."

Đối với câu b: thường sẽ hỏi có nên cấp thêm cho một tiến trình nào đó một máy,hoặc một ổ... nữa không?
Đầu tiên bạn phải xét 2 điều kiện này:
-Request(i)<=Need(i)
-Request(i)<=Available
Nếu cả hai đều thỏa thì lập bảng làm tiếp tương tự câu A,nhưng Allocation sẽ thay đổi( với tiến trình nào đó được cấp thêm máy) . Nếu không thỏa một trong hai điều kiện thì bạn kết luận luôn không có chuỗi an toàn,không nên cấp thêm cho ..........vì có thể dẫn đến dealock
Chú ý:
Với trường hợp không tồn tại chuỗi an toàn, có 2 khả năng:
1. Chỉ tìm được phần đầu của chuỗi (số tiến trình tìm được ≥ 1 và < Tổng số tiến trình).
2. Chuỗi rỗng (không tìm được tiến trình nào).
Dù thế nào, cũng phải lập bảng với các cột Work, Needi, Pi, Allocationi !
Còn ví dụ cụ thể bạn có thể xem bài của bạn: plminhhoangI12A đã giải rồi cũng dễ hiểu!

Đinh Đông Dương đã viết:chào bạn lê phúc hiệp mình có xem bài giải của bạn mình cũng làm tương tự nhưng có chỗ chữ màu đỏ mình chưa hiểu do mình làm khác bạn .Mong thầy và bạn xem lại ai đúng ai sai
1 hệ thống có 10 máy quét hình và 3 tiến trình P1, P2, 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 các vector

Allocation = (3, 1, 1 )
Và Max= (9, 4, 8 )

a) Dùng Thuật toán nhà băng để CM trạng thái an toàn
b) Xác định có nên đáp ứng hay không yêu cầu cấp them 1 máy
của P3


Giải
a) Thuật toán nhà băng:
Ta có: Available = 10 - (3+1+1) = 5
Need = Max – Allocation
P Allocation[i] Max[i] Need[i] Available
P1 3 9 6 5
P2 1 4 3
P3 1 8 7

Work >= Need[i] P[i] Allocation[i]
5 3 P2 1
6 6 P1 3
9 7 P3 1

Vậy tồn tại chuỗi an toàn
=> Trạng thái ở thời điểm Ti là
an toàn

b) Xác định có nên đáp ứng hay không yêu cầu cấp thêm 1 máy
của P3:

Xét 2 trường hợp

- 1) Request3 <= Need3

Vì 1<= 6 ????? chưa hiểu chỗ này,mình làm là 1<=7

- 2) Request3 <= Available

Vì 1<= 4 ????? chưa hiểu chỗ này,mình làm là 1<=5

P[i] Allocation[i] Max[i] Need[i] Available
P1 3 9 6 4
P2 1 4 3
P3 2 8 6

Available = 10 - (3+1+2) = 4

Work >= Need[i] P[i] Allocation[i]
4 3 P2 1
5 6(không thỏa ĐK) P3 2

=>Trạng thái không
an toàn
Vậy: Không nên đáp ứng
yêu cầu cấp thêm 1 máy của P3

Theo mình thì bạn đúng vì:

Vì 1<= 6 ????? chưa hiểu chỗ này,mình làm là 1<=7( phải lấy need đầu tiên: need ở câu a là 7)

- 2) Request3 <= Available

Vì 1<= 4 ????? chưa hiểu chỗ này,mình làm là 1<=5 (lấy Available đầu tiên: Available ở câu a là 5)

Mình nghĩ bạn Hiệp lấy 1<=6 và 1<=4 là sai vì đầu tiên phải xét 2 điều kiện(lúc này chưa lập bảng chưa tính được Need(3) và Available) :
1) Request3 <= Need3
2) Request3 <= Available
phải xét xong cả hai điều kiện này thỏa rồi mới lập bảng làm tiếp mà lúc này làm gì đã tính được need(3) và Available(3) cho câu b ,và 2 số 6 và số 4 ở đâu ra?

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 >

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	Đã được cấp phát(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 để xác định trạng thái này có an toàn hay không?

Ta có
- Available=12-(5+2+2)=3
- Need=Max-Allocation

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

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

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

Vậy tồn tại chuỗi an toàn.Suy ra trạng thái hệ thống ở thời điểm Ti là an toàn.

Định nghĩa Deadlock & Điều kiện cần để xảy ra deadlock

Định nghĩa Deadlock
- Trong hệ thống đa chương, nhiều quá trình có thể
cạnh tranh một số giới hạn tài nguyên.
- Một quá trình yêu cầu tài nguyên, nếu tài nguyên
không sẵn dùng tại thời điểm đó, quá trình đi vào
trạng thái chờ.
-Quá trình chờ có thể không bao giờ chuyển trạng thái
trở lại vì tài nguyên chúng yêu cầu bị giữ bởi những
quá trình khác
=>Trường hợp này gọi là deadlock(khóa chết).

Điều kiện cần để xảy ra deadlock :
Bốn điều kiện cần (necessary condition) để xảy ra
deadlock
1. Loại trừ tương hổ (Mutual exclusion): ít nhất một
tài nguyển được giữ trong chế độ không chia sẻ
2. Giữ và chờ cấp thêm tài nguyên (Hold and wait):
một process đang giữ ít nhất một tài nguyên và
đợi thêm tài nguyên do quá trình khác đang giữ
3. Không có ưu tiên (No preemption): tài nguyên không thể bị lấy lại,mà chỉ có thể được trả lại từ process đang giử tài nguyên đó khi nó muốn.
4. Chu trình (Circular wait): tồn tại một chu trình của các yêu cầu tài nguyên và tài nguyên đã được cấp phát.

Trong một deadlock, các quá trình không bao giờ hoàn thành việc thực thi và
các tài nguyên hệ thống bị buộc chặt, ngăn chặn các quá trình khác bắt đầu.
Mục đích Sau khi học xong chương này, người học nắm được những kiến thức sau:
Hiểu mô hình hệ thống về deadlock
• Hiểu các đặc điểm của deadlock
• Hiểu các phương pháp quản lý deadlock
• Hiểu cách ngăn chặn deadlock
• Hiểu cách tránh deadlock
• Hiểu cách phát hiện deadlock
• Hiểu cách phục hồi từ deadlock

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

a) Allocation= (0,2,1) và Max= (2,2,2)
Available= 3-(0+2+1)=0
Tiến trình---- Đang giữ ---Max ----Hệ có
P1 -------------0 ------------2----------- 0
P2 -------------2 ------------2
P3-------------- 1 -----------2

=> Need= (2,2,2) - (0,2,1)= (2,0,1)
Tiến trình Need
P1 ------------2
P2 -----------0
P3 -----------1

Work >= Need(i) P(i) Allocation(i)
0 -----------0 --------P2 -----2
2 -----------1 -------P3 -----1
3 -----------2 -------P1----- 0

Tồn tại chuỗi an toàn= {P2,P3,P1}. Vậy trạng thái hệ thống ở thời điểm Ti là an toàn.

b) Request(2)= 1
Need(2)= 0
=> Request(2)> Need(2) (1> 0)
Vậy không thể đáp ứng được yêu cầu thêm 1 máy nữa của P2.

Định nghĩa: 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ụ:
Có hai xe đi ngược chiều cùng qua 1 cây cầu hẹp, mà cầu thì chỉ có một làm xe nên khi hai xe vào đến giữa cầu thì không thể tiếp tục tiến đi được nữa xảy ra kẹt xe(deadlock) vì không người nào chịu nhường đường.

1. Thủ thuật phát hiện deadlock:
- Khi nào chúng ta cần giải thuật phát hiện deadlock?
- Câu trả lời phụ thuộc vào hai yếu tố:
+ Deadlock có khả năng xảy ra như thế nào?
+ Có bao nhiêu tiến trình sẽ bị ảnh hưởng bởi deadlock khi nó xảy ra ?
- Nếu deadlock xảy ra thường xuyên thì giải thuật phát hiện deadlock sẽ được thực hiện thường xuyên. Tài nguyên được cấp phát cho deadlock sẽ được rảnh rỗi cho đến khi deadlock bị phá vỡ. Ngoài ra, số lượng tiến trình tham gia vào trong chu trình deadlock có thể tăng lên.

- Deadlock xảy ra khi một tiến trình thực hiện yêu cầu mà không được cấp phát tài nguyên tức thì. Yêu cầu này có thể là yêu cầu cuối cùng hoàn thành một chuỗi các tiến trình chờ. Trong trường hợp này chúng ta có thể gọi giải thuật phát hiện deadlock mỗi khi yêu cầu cấp phát không được cấp phát tức thì. Chúng ta không chỉ biết được tập hợp các tiến trình bị deadlock mà còn xác định tiến trình đã gây ra deadlock (Trong thực tế, mỗi tiến trình trong suốt quá trình bị deadlock là một liên kết trong chu trình của đồ thị tài nguyên vì thế tất cả chúng gây ra deadlock). Nếu có nhiều loại tài nguyên khác nhau, một yêu cầu tạo ra một chu trình trong đồ thị tài nguyên, mỗi chu trình hoàn thành bởi các yêu cầu gần đây nhất và “gây ra” bởi một tiến trình có thể xác định.

- Tất nhiên, nếu thuật toán phát hiện deadlock được gọi cho mọi yêu cầu tài nguyên điều này có thể gây ra chi phí lớn trong thời gian tính toán. Một phương pháp để giảm chi phí là ta gọi giải thuật trong thời điểm ít thường xuyên hơn - ví dụ mỗi giờ hoặc bất cứ khi nào CPU sử dụng dưới 40%. Nếu giải thuật phát hiện deadlock được gọi vào thời điểm bất kỳ, có thể có nhiều chu trình trong đồ thị tài nguyên. Chúng ta không thể xác định được tiến trình nào “gây ra” deadlock.
2. Phục hồi deadlock:
- Khi giải thuật phát hiện deadlock xác định tồn tại một deadlock, có 2 cách để giải quyết:
+ Một là thông báo cho người điều hành biết deadlock xảy ra và để cho người điều hành khắc phục bằng tay.
+ Hai là để cho hệ thống phục hồi tự động. Có hai tùy chọn để phá vỡ deadlock. Một giải pháp đơn giản là hủy một hay nhiều tiến trình để phá vỡ tồn tại chu trình trong đồ thị cấp phát tài nguyên. Lựa chọn thứ hai là lấy lại một hay nhiều tài nguyên từ tiến trình deadlock.

Tìm cách ngăn chặn sao cho 1 trong 4 điều kiện ko xẩy ra:
Ngăn cản lẫn nhau:(mutual exclusion)
- đảm bảo hệ thống ko có các file ko thể chia sẻ
Một process ko bao giờ chờ tài nguyên chia sẻ (shareble resource)
Vd read-only file
Nhưng có 1 số tài nguyên ko chia sẻ được
Vd : chế độ toàn màn hình
Giữ và đợi:(Hold and wait)
- sử dụng cơ chế “All or none”
Cách 1 : bắt buộc mỗi process phải yêu cầu tòan bộ tài nguyên cấn thiết 1 lần, nếu có đủ tài nguyên hế thống sẽ cấp phát, nếu ko đủ tài nguyên, process sẽ bị block.
Cách 2: khi yêu cầu tài nguyên process không được sở hữu bất kỳ tài nguyên nào cả.nếu đang có thì phải trả lại trước khi yêu cầu.
Khuyết điểm :
Hiệu quả sử dụng tài nguyên rất thấp
Có khả năng xẩy ra bị đói starvation

dùng thuật giải nhà băng chứng minh trạng thái này an toàn

tiến trình---- Được cấp(ổ đĩa) ---tối đa cần(ổ đĩa)

P1 ------------ 5------------------------- 10
P2------------- 2-------------------------- 4
P3-------------2--------------------------- 9



-Available=12-9=3
-Need=Max-Allocation
P1=10-5=5
P2=4-2=2
P3=9-2=7

work ≥ Need--- Pi ----- Allocation(i)
3 -------- 2------- P2-----2
5--------- 5------- P1----- 5
10--------7------- P3------2

-Tồn tại chuỗi an toàn T0={P2,P1,P3}
Vậy trạng thái tại thời điểm T0 là an toàn.

HUYNHDUCANHI12A đã viết:Sao không thấy bài thuật giải nhà băng và bài thuật giải Round-Robin mà để thảo luận thầy nhỉ

Hai phần này có mục riêng ở bên ngoài. Trực quan, dễ hiểu
Thuật giải nhà băng & Round Robin
https://hedieuhanh.forumvi.com/t4522-topic

Bài tập Round Robin
https://hedieuhanh.forumvi.com/t4359-topic

- Một trạng thái được gọi là an toàn nếu tồn tại ít nhất 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ỏa 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.

Định nghĩa Deadlock (Kẹt khoá): 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.
- Deadlock là tình huống xuất hiện khi hai hay nhiều “hành động” phải chờ một hoặc nhiều hành động khác để kết thúc, nhưng không bao giờ thực hiện được Máy tính: Bế tắc là tình huống xuất hiện khi hai tiến trình phải chờ đợi nhau giải phóng tài nguyên hoặc nhiều tiến trình chờ sử dụng các tài nguyên theo một “vòng tròn.
+ Yêu cầu tài nguyên.
+ Sử dụng tài nguyên.
+ Trả lại tài nguyên.
vd1: Hiện tượng deadlock xảy ra trên 1 ngõ hẹp ( tại 1 thời điểm chỉ duy nhất 1 xe đi qua ). Khi các xe di chuyển tại 1 thời điểm cả 2 đều đi ngang đoạn ngõ hẹp và cả 2 xe đều kẹt ở ngõ => Xuất hiện deadlock (Trên thực tế chẳng có ai chịu nhường đường cả.).

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 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.

- Trên RAG, lúc ð.u t.t c. nhu c.u v. tài nguyên c.a ti.n tr.nh ph.i ðý.c khai báo trý.c b.ng các Cung Nhu c.u (Claim edge) Pi • • •> Rj ch. báo r.ng Pi có th. s. yêu c.u Rj - Cung Nhu c.u Pi • • •> Rj ðý.c chuy.n thành Cung Yêu c.u (Request edge) Pi • • •> Rj khi Pi th.c s. b.t ð.u c.n ð.n Rj . - N.u yêu c.u Pi • • •> Rj ðý.c HÐH ðáp .ng, cung Pi • • •> Rj chuy.n thành Cung .n ð.nh (Assignment edge) Pi <• • • Rj n.i phiên b.n duy nh.t c.a Rj v.i Pi . - Khi HÐH xét yêu c.u Pi • • •>Rj. H. ch. c.p phát Rj cho Pi n.u Cung .n ð.nh Pi <• • • Rj không t.o ra v.ng tr.n ð.ng hý.ng trong RAG (xét c. các Cung Nhu c.u). - Thu.t gi.i có ð. ph.c t.p o(n²) v.i n là s. ti.n tr.nh trong h.. Ví d. trách deadlock dùng RAG: Ð.u tiên khai báo t.t c. các nhu c.u c.a P1 và P2:P1 và P2 có th. s. d.ng R1,R2.

Để ngăn chặn Deadlock ta phải làm sao cho ít nhất 1 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ữ 1 TN 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 nhưng 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êm 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 Wait: Cấp TN theo một thứ tự nào đấy.

Deadlock : Là Một số tiến trình có thể tranh nhau bởi một số tài nguyên hạn chế.

Tài nguyên hệ thống được chia thành nhiều loại, mỗi loại có 1 hoặc nhiều phiên bản(Instances).
+ Các tiến trình chờ có thể sẽ không bao giờ thay đổi lại trạng thái được vì các tài nguyên mà nó yêu cầu bị giữ bởi các tiến trình chờ khác.

+ Mỗi tiến trình sử dụng tài nguyên theo các bước sau:
• yêu cầu tài nguyên(request): Nếu yêu cầu không được giải quyết ngay( ví dụ khi tài nguyên đang được tiến trình khác sử dụng) thì tiến trình yêu cầu phải đợi cho đến khi nhận được tài nguyên.
• Sử dụng tài nguyên(use)
• Trả lại(Release): Trả tài nguyên cho HĐH quản lý.

ví dụ: Hiện tượng tắc nghẽn trên cầu:
+ Hai (hay nhiều hơn) ô tô đối đầu nhau trên một cây cầu hẹp chỉ đủ độ rộng cho một chiếc.
+ Mỗi đoạn của cây cầu có thể xem như một tài nguyên
+ Nếu deadlock xuất hiện, nó có thể được giải quyết nếu một hay một số ô tô lùi lại nhường đường rồi tiển ra sau. deadlock là kẹt mãi mãi