Thảo luận Bài 8

-Dấu chấm:là phiên bản cấp cho p1,p2,p3,p4
-Không có Deadlock:các tiến trình p1,p2,p3,p4 và tài nguyên R1, R2 không tạo thành chu trình
-có Deadlock:các tiến trình p1,p2,p3,p4 và tài nguyên R1, R2 tạo thành chu trình


Ví dụ tại thời điểm 18h5' khi p4 dùng xong R2 nên lúc này p4 tự do được tự do đi làm công việc khác
tại thời điểm 18h6' cung yêu cầu p3 sang R2 được ấn định nên mũi tên từ P3 sang R2 sẽ trỏ ngược lại lúc này đồ thị sẽ không có chu trình



mình trình bày theo cách hiểu trên có gì sai sót các bạn và thầy bổ sung góp ý cho mình nhé

đây là đồ thị có chu trình nhưng không có xảy ra Deadlock vì tài nguyên R1 va R2 có tới 2 phiên bản trở lên thì khả năng xảy ra Deadlock rất thấp
biểu diển đồ thị lúc 8h tối

lúc này p3 cần cấp phát từ R2 nhưng lúc 8h R2 đang cấp phát cho P1 và P4
đồ thị lúc 8h20 thì P4 dùng xong tài nguyên 3 R2 nó trả lại tài nguyên cho R2

lúc này R2 đáp ứng yêu cầu của P3 và hướng cung yêu cầu tới cho P3
lúc này đồ thị không còn là đồ thị có chu trình nửa và sẻ không xảy ra Deadlock

RAG (Resource Allocation Graph): Đồ thị cấp phát tài nguyên
Sau đây là ví dụ về RAG có chu trỉnh nhưng không có Deadlock khi tài nguyên thuộc chu trình có nhiều hơn 1 phiên bản.
- Tại thời điểm 10 giờ: RAG có chu trình, và tài nguyên R1, R2 có 2 phiên bản



- Tại thời điểm 10 giờ 5 phút: sau khi P4 dùng xong tài nguyên, sẽ trả lại tài nguyên cho R2.



-Tại thời điểm 10 giờ 6 phút: cung yêu cầu từ P3 đến R2 (P3 -> R2), sẽ trở thành cung ấn định R2 đến P3 (R2 -> P3). Lúc này đồ thị không còn chu trình, tức là sẽ không có Deadlock.



Mong thầy và các bạn góp ý kiến cho mình!

PhamQuangHien_I12A đã viết:
-Dấu chấm:là phiên bản cấp cho p1,p2,p3,p4
-Không có Deadlock:các tiến trình p1,p2,p3,p4 và tài nguyên R1, R2 không tạo thành chu trình
-có Deadlock:các tiến trình p1,p2,p3,p4 và tài nguyên R1, R2 tạo thành chu trình


Ví dụ tại thời điểm 18h5' khi p4 dùng xong R2 nên lúc này p4 tự do được tự do đi làm công việc khác
tại thời điểm 18h6' cung yêu cầu p3 sang R2 được ấn định nên mũi tên từ P3 sang R2 sẽ trỏ ngược lại lúc này đồ thị sẽ không có chu trình



mình trình bày theo cách hiểu trên có gì sai sót các bạn và thầy bổ sung góp ý cho mình nhé

HÌNH CUỐI CÙNG BẠN VẼ CHƯA ĐÚNG VÌ TÀI NGUYÊN R2 KHI CẤP PHÁT TÀI NGUYÊN CHO P3 THÌ MŨI TÊN PHẢI ĐI TỪ CHẤM RA TIẾN TRÌNH P3 MỚI ĐÚNG ( THẦY NÓI NHẤN MẠNH CÁI NÀY KHI VẼ MỚI ĐÚNG)
MÌNH VẼ LẠI HÌNH CUỐI NHƯ SAU:

1. loại trừ lẫn nhau(mutual exclusion): có ít nhất một tài nguyên không chia sẻ (không dùng chung được)
VD: 2 xe qua cầu hẹp tại 1 thời điểm chỉ có 1 xe qua cầu không thể có 2 xe qua cầu được , cầu ko dùng chung được tại 1 thời điểm đó.

2. giữ và chờ (hold and wait): có 1 tiến trình đang giữ 1 tài nguyên và xin thêm 1 tài nguyên khác.
VD: 2 xe qua cầu hẹp và 2 xe bị kẹt mỗi xe giữ một nữa mặt cầu, và cứ chờ để được qua cầu

3. không tiếm quyền( no preemption): không bắt các tiến trình trả lại tài nguyên.
VD: 2 xe qua cầu hẹp , để cho 1 trong 2 xe trả lại mặt cầu còn lại phải có 1 cần cẫu, nâng 1 trong 2 xe lên, nhường cho xe còn lại.

4. chờ xoay vòng(circular wait): p1 chờ tài nguyên của p2, p2 chờ tài nguyên của p3,p3 chờ tài nguyên của p4,...,p(n-1) chờ tài nguyên cua p(n), p(n) chờ tài nguyên của p1
VD: 4 xe bị kẹt ở ngã tư, xe 1 chờ xe 2 , xe 2 chờ xe 3, xe 3 chờ xe 4, xe 4 chờ xe 1

--> muốn ngặn chặn Deadlock, ta phủ định(không cho xảy ra) 4 điều kiện xảy ra deadlock trên.

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.

Chúng ta nhấn mạnh rằng tất cả bốn điều kiện phải cùng phát sinh để deadlock
xảy ra. Điều kiện chờ đợi ch trình đưa đến điều kiện giữ-và-chờ vì thế bốn điều kiện
không hoàn toàn độc lập.

LeThiMaiPhuongI12A đã viết:Deadlock là tình trạng kẹt của một nhóm tiến trình.
vd:
2 xe đi ngược chiều cùng qua 1 cây cầu hẹp, mà cầu thì cho được 1 xe qua nên khi 2 xe vào đến giữa cầu thì không thể tiếp tục tiến tới nữa, xãy ra kẹt xe (deadlock) vì không xe nào chịu nhường xe nào.

TÌNH TRẠNG XE QUA CẦU HẸP:



GIẢI QUYẾT VẤN ĐỀ KẸT LÀ SẼ CÓ 1 XE PHẢI TRẢ LẠI TÀI NGUYÊN MẶT ĐƯỜNG CHO XE CÒN LẠI QUA VẬY LÀ GIẢI QUYẾT ĐƯỢC DEADLOCK. NHƯNG 2 XE KO XE NÀO CHỊU TRẢ LẠI TÀI NGUYÊN MẶT ĐƯỜNG VÌ VẬY HĐH ÉP 1 TIẾN TRÌNH (XE) GIẢI PHÓNG TÀI NGUYÊN MẶT ĐƯỜNG VẬY LÀ GIẢI QUYẾT ĐƯỢC KẸT XE TRÊN CẦU HẸP CHO XE CÒN LẠI.

Định nghĩa Deadlock (Kẹt khó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ụ minh họa Deadlock:Đi lễ hội (chùa Hương,Đền Hùng),giữa dòng người đi ra và đi vào trong khi con đường đi ra vào lại lại chỉ có một đường nên không đủ cho việc ra vào,dẫn đến kẹt và chờ đợi

Nguyen Sy Hung I12A đã viết: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.

Chúng ta nhấn mạnh rằng tất cả bốn điều kiện phải cùng phát sinh để deadlock
xảy ra. Điều kiện chờ đợi ch trình đưa đến điều kiện giữ-và-chờ vì thế bốn điều kiện
không hoàn toàn độc lập.

THẦY NÓI LÀ 1 TRONG 4 TRƯỜNG HỢP XẢY RA LÀ HIỆN TƯỢNG DEADLOCK XẢY RA MÀ ???

SORRY CÓ THỂ MÌNH NGHE NHẦM

NẾU VẬY CHỈ CẦN PHỦ ĐỊNH 1 TRONG 4 TRƯỜNG HỢP TRÊN THÌ KO XẢY RA HIỆN TƯỢNG DEADLOCK NỮA NHỈ

Đị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 hay 1 tài nguyên 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.

tranvanthien27(I12C) đã viết:Đị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 hay 1 tài nguyên 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.

ADD THÊM CÁI HÌNH CHO DỄ HIỂU

Giải pháp để ngăn chặn DeadLock là bằng cách phủ định một trong bốn điều kiện trên như sau:
+Loại trừ lẫn nhau: để ngăn tình trạng này xảy ra thì ta có thể tạo nhiều tài nguyên dùng chung để các tiến trình sử dụng 1 cách hiệu quả.
+Giữ và chờ: để ngăn tình trạng này ta sẽ cho các tiến trình giữ và chờ trong một khoảng thời gian nhất định nào đó. Như thế, sẽ giải phóng được tài nguyên và các tiến trình khác tiếp tục sử dụng tài nguyên đó.
+Không có tiếm quyền: để ngăn tình trạng này thì ta phải làm cho hệ điều hành lấy lại tài nguyên mà tiến trình đó đang giữ (có tiếm quyền).
+ Chờ xoay vòng: cách giải quyết cũng giống (Loại trừ lẫn nhau) là phải tạo nhiều tài nguyên dùng chung.

Định nghĩa Deadlock (Kẹt khó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ụ minh họa Deadlock:
Đi Lễ (Chùa Hương,Đền Hùng) khi giữa dòng người đi ra và đi vào trên cùng một tuyến đường gây ra kẹt và chờ nhau

Trường hợp deadlock có thể phát sinh nếu một bốn điều kiện sau xảy ra:
- Loại trừ lẫn nhau (Multual Exclusion): Ít nhất có 1 tài nguyên có tính không chia sẻ (non-shareable), nghĩa là mỗi thời điểm chỉ có một tiến trình được sử dụng nó.
- Giữ và chờ (Hold and Wait): Có 1 tiến trình đang giữ tài nguyên và xin thêm tài nguyên đang bị độc chiếm bởi tiến trình khác.
- Không có tiếm quyền (No Preemption): Tài nguyên đang giữ bởi tiến trình không thể bị tiếm quyền mà phải được tiên trình này tự nguyên trả lại hệ thống sau khi dung xong.
- Chờ xoay vòng (Circular Wait): Giả sử có n tiến trình đang chờ tài nguyên {P1,P2…Pn}, khi đó P1 chờ TN giữ bởi P2, tiến trình P2 chờ TN giữ bởi P3, …, Pn chờ P1.

Giải pháp để ngăn chặn DeadLock là bằng cách phủ định một trong bốn điều kiện trên như sau:

+Loại trừ lẫn nhau: để ngăn tình trạng này xảy ra thì ta có thể tạo nhiều tài nguyên dùng chung để các tiến trình sử dụng 1 cách hiệu quả.
+Giữ và chờ: để ngăn tình trạng này ta sẽ cho các tiến trình giữ và chờ trong một khoảng thời gian nhất định nào đó. Như thế, sẽ giải phóng được tài nguyên và các tiến trình khác tiếp tục sử dụng TN đó.
+Không có tiếm quyền: để ngăn tình trạng này thì ta phải làm cho hệ điều hành lấy lại tài nguyên mà tiến trình đó đang giữ (có tiếm quyền).
+ Chờ xoay vòng: cách giải quyết cũng giống (Loại trừ lẫn nhau) là phải tạo nhiều TN dùng chung.

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

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

Giải thích vẽ được đồ thị cấp phát tài nguyên:


* Dấu chấm được ký hiệu gọi là phiên bản
- Hình không có Deadlock ta giải thích như sau: Ta nhìn thấy tiến trình từ R2->P1->R1->P2->R3->P3 kết thúc và R2->P2->R3->P3 kết thúc.Các tiến trình đều dừng tại P3,trong khi ta thấy R2->P1->R1->P2<-R2 như một chu trình vòng tròn nhưng thật ra không đúng vậy vì P2 được cấp phát từ R1 và R2.Nên tài nguyên R1, R2,R3 không tạo thành chu trình và không có Deadlock.
- Hình có Deadlock ta giải thích như sau: tiến trình từ R2->P1->R1->P2->R3->P3->R2 kết thúc và R2->P2->R3->P3->R3 kết thúc.Các tiến trình đều bắt đầu và kết thúc tại R2 nên tài nguyên R1, R2,R3 tạo thành chu trình và có Deadlock

Có bốn điều kiện cần thiết để deadlock có thể xảy ra.
- Điều kiện loại trừ lẫn nhau: Một tài nguyên không thể sử dụng bởi nhiều hơn một tiến trình tại một thời điểm
- Điều kiện giữ và chờ: Các tiến trình giữ tài nguyên và chờ tài nguyên mới
- Điều kiện không thể chiếm: Các tài nguyên không thể bị đòi lại, chúng chỉ có thể được giải phóng bởi chính tiến trình chiếm giử chúng
- Điều kiện chu trình chờ: Các tiến trình giử tài nguyên và chờ các tài nguyên bị giử bởi tiến trình khác, tạo thành một chu trình. Ví dụ: Tiến trình 1, chiếm A1, chờ A2. Tiến trình 2 chiếm A2, chờ A3,... Tiến trình N chiếm An, chờ A1.
ví dụ:

Thread 1	Thread 2
Muốn lấy tài nguyên A và B	Muốn lấy tài nguyên A và B
Chiếm tài nguyên A , chờ Thread 2 bắt đầu chạy cho tới khi Thread 2 đợi tài nguyên A giải phóng
	Chiếm tài nguyên B
	Đợi tài nguyên A giải phóng
Đợi tài nguyên B giải phóng

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

- Loại trừ lẫn nhau (Multual Exclusion): Ít nhất có 1 tài nguyên có tính không chia sẻ (non-shareable), nghĩa là mỗi thời điểm chỉ có một tiến trình được sử dụng nó.
- Giữ và chờ (Hold and Wait): Có 1 tiến trình đang giữ tài nguyên và xin thêm tài nguyên đang bị độc chiếm bởi tiến trình khác.
- Không có tiếm quyền (No Preemption): Tài nguyên đang giữ bởi tiến trình không thể bị tiếm quyền mà phải được tiên trình này tự nguyên trả lại hệ thống sau khi dung xong.
- Chờ xoay vòng (Circular Wait): Giả sử có n tiến trình đang chờ tài nguyên {P1,P2…Pn}, khi đó P1 chờ TN giữ bởi P2, tiến trình P2 chờ TN giữ bởi P3, …, Pn chờ P1.

- Đồ thị cấp phát tài nguyên (Resource allocation graph-RAG) là đồ thị có hướng với tập nút V và tập cung E.

+ Tập nút V gồm 2 loại:
P ={P1, P2, ..., Pn} tập hợp các tiến trình đang vận hành trong hệ thống.
R ={R1, R2, ..., Rm} tất cả các tài nguyên trong hệ thống. Mỗi loại Rj có từ 1 đến nhiều
phiên bản. VD: máy in có 3 phiên bản, ...

+Tập cung E bao gồm:
Cung yêu cầu (Request edge): có hướng từ Pi -> Rj, P1 yêu cầu 1 phiên bản tài nguyên Rj.
Cung ấn định (Assignment edge): có hướng từ Rj->Pi, 1 phiên bản tài nguyên Rj được cấp
phát cho Pi.

Đồ thị cấp phát tài nguyên gồm có: chu trình và không có chu trình.
o Không có chu trình: không tồn tại Deadlock
o Có chu trình: có hoặc không có Deadlock
.Có Deadlock khi mỗi tài nguyên trên chu trình chỉ có duy nhất 1 phiên bản.
.Có thể không có Deadlock khi tài nguyên thuộc chu trình có nhiều phiên bản.

RAFG có chu trình nhưng không có Deadlock:
R1,R2 đều có hai phiên bản
R1 một phiên bản cấp phát cho P2 và một phiên bản nhận từ P1 cấp phát cho P3
R2 môt phiên bản cấp phát cho P4 và một phiên bản nhận từ P3 cấp phát cho P1









Tiến trình P4 có thể giải phóng một đơn vị của loại tài nguyên R2,tài nguyên đó có thể được cấp phát tới P3 sau đó chu trình sẽ không còn.Nếu đồ thị cấp phát tài nguyên không có chu trình thì hệ thống không có trạng thái Deadlock,nếu có chu trình thì có thế có hoặc không trạng thái Deadlock

Phân tích 4 điều kiện cần dẫn đến Deadlock:

- Loại trừ lẫn nhau (Multual Exclusion): Ít nhất có 1 tài nguyên có tính không chia sẻ (non-shareable), nghĩa là mỗi thời điểm chỉ có một tiến trình được sử dụng nó.
- Giữ và chờ (Hold and Wait): Có 1 tiến trình đang giữ tài nguyên và xin thêm tài nguyên đang bị độc chiếm bởi tiến trình khác.
- Không có tiếm quyền (No Preemption): Tài nguyên đang giữ bởi tiến trình không thể bị tiếm quyền mà phải được tiên trình này tự nguyên trả lại hệ thống sau khi dung xong.
- Chờ xoay vòng (Circular Wait): Giả sử có n tiến trình đang chờ tài nguyên {P1,P2…Pn}, khi đó P1 chờ TN giữ bởi P2, tiến trình P2 chờ TN giữ bởi P3, …, Pn chờ P1.

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

Bốn điều kiện:
+ Loại trừ lẫn nhau (Mutual Exclusion): Ít nhất có 1 tài nguyên có tính không chia sẻ (non-sharable), nghĩa là: Mỗi thời điểm chỉ có 1 tiến trình được sử dụng nó.
+ Giữ và chờ (Hold and Wait): Có 1 tiến trình đang giữ 1 tài nguyên và xin thêm tài nguyên đang độc chiếm bởi tiến trình khác.
+ Không có tiếm quyền (No Preemption): Tài nguyên đang giữ bởi tiến trình không thể bị tiếm quyền mà phải được tiến trình này tự nguyện trả lại hệ thống sau khi sử dụng xong.
+ Chờ xoay vòng (Circular Wait): Giả sử có n tiến trình đang chờ tài nguyên là { P1 , P2, ... , Pn }, khi đó P1 chờ TN giữ bởi P2 , tiến trình P2 chờ TN giữ bởi P3 , ... , Pn chờ P1 .
* Bốn điều kiện này không hoàn toàn độc lập với nhau: ví dụ, Điều kiện 4 kéo theo Điều kiện 2.

Giải pháp xử lý:
1. Sử dụng quy tắc Ngăn chặn (Prevention) hoặc Tránh (Avoidance) để Deadlock không bao giờ xảy ra.
2. Cho phép hệ thống bị Deadlock, sau đó Xác định (Detection) và tìm cách Khắc phục (Recover).
3. Không xét vấn đề Deadlock, coi như không bao giờ xảy ra, còn nếu xảy ra thì Khởi động lại hệ thống (Cách này có thể có ý nghĩa thực tế vì không cần đưa vào HĐH các phương tiện xử trí thường trực).

Biện pháp ngăn chặn:
Bằng cách sao cho ít nhất 1 trong 4 điều kiện cần kể trên không xảy ra.
° 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.