Thảo luận Bài 8

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.

Để 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:
- Mutual Exclusion (loại trừ lẫn nhau): Đảm bảo tài nguyên nào cũng dùng chung được cùng một lúc bởi nhiều tiến trình.
- Hold and Wait (giữ và chờ):
a/ Khi tiến trình yêu cầu tài nguyên, nó không được giữ 1 tài nguyên nào khác.
b/ Tiến trình phải yêu cầu và được cấp tất cả các tài nguyên mà nó cần ngay đầu công việc.
- No Preemption (không có tiếm quyền):
a/ Khi tiến trình giữ tài nguyên mà xin thêm nhưng không được, các tài nguyên mà nó giữ phải bị tiếm quyền sử dụng và trả lại hệ điều hành.
b/ Khi tiến trình xin thêm tài nguyên, nếu tài nguyên này đang được giữ bởi tiến trình khác đang ở trạng thái chờ, tiến trình của tiến trình khác này bị tiếm quyền sử dụng để cấp cho tiến trình đang xin.
- Circular Wait (chờ xoay vòng): Cấp tài nguyên theo một thứ tự nào đó.

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

VD:cầu hẹp thì chỉ có 1 xe được đi qua.

• 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 tài nguyên khác.

• Không có tiếm quyền(No Premption):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.

VD:xe qua cầu hẹp,để cho 2 xe A và B trả lại mặt đường,thì phải bắt 1 trong 2 xe phải trả.

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

Ít nhất 1 trong 4 điều kiện này xảy ra sẽ dẫn đến Deadlocks.

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.

Mình xin thêm 1 ý: chỉ cần có 1 trong 4 điều kiện trên thì sẽ dẫn đến Deadlocks.

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.

Mình nhớ rằng thầy có nói chỉ cần 1 trong 4 điều kiện trên mà xảy ra thì sẽ có Deadlocks mà bạn. tuy nhiên không phải là điều kiện nào cũng xảy ra 1 mình mà nó có thể kéo theo những điều kiện khác cùng xảy ra.
Ví dụ: điều kiện 2 có thể sẽ kéo theo kiều kiện 4.
Không biết mình có nhớ nhầm không mong thầy và các bạn góp ý.

1. Sử dụng quy tắc Ngăn chặn hoặc Tránh để Deadlock không bao giờ xảy ra
VD: tại mỗi ngã tư (nơi có nguy cơ xảy ra Deadlock, nên để đèn báo hiệu, hoặc 1 CSGT để điều khiển luồng xe cộ)
2. Cho phép hệ thống bị Deadlock, sau đó xác định và tìm cách khắc phục
VD: nếu tại ngã tư đã xảy ra kẹt xe, trước tiên người điều khiển giao thông cần phải xác định kẹt tại chỗ nào, sau đó ra lệnh cho các cần cẩu ở 4 ngã tư, tiến hành nhấc các chiếc xe này lên không trung, đến khi nào dòng xe cộ bình thường thì thả xe xuống)
3. Nếu không xét về Deadlock, nếu xảy ra thì Khởi động lại hệ thống
VD: nếu tại 1 ngã tư có xảy ra tình trang kẹt xe, thì ngay lập tức, HĐH (có thể là chúa trời) làm cho tất cả các chiếc xe biến mất hết, tất cả xe quay lại về nơi khởi đầu của mình
Hoặc nếu HĐH, có sử dụng hệ thống (Sao lưu thời gian thực) nếu xảy ra xử cố Deadllock kẹt xe, thì khôi phục lại thời điểm trước đó 10s, và sử dụng lại nguyên tắc 1 và 2 ở trên để tránh xảy ra 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.

nguyenthingocmai_I12A đã viết:

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.

Mình xin thêm 1 ý: chỉ cần có 1 trong 4 điều kiện trên thì sẽ dẫn đến Deadlocks.

nhưng các điều kiện trên không hoàn toàn độc lập, điều kiện 4 có thể kéo theo điều kiện 2 gây ra deadlock.

Loại bỏ điều kiện loại trừ tương hỗ:
Vì tại một thời điểm chỉ có 1 tiến trình được sử dụng tài nguyên, mà đây là tài nguyên không chia sẽ nên ta sẽ tăng số lượng tài nguyên lên. Giải pháp này thực tế là không khả thi.

Loại bỏ điều kiện giữ và chờ (Hold and Wait):
Do một tiến trình đang giữ tài nguyên và yêu câu một tài nguyên mới nên nguyên tắc để loại bỏ là: tiến trình không được giữ tài nguyên khi yêu cầu tài nguyên mới. Khi cần, nó khai báo tài nguyên và đươc cấp phát một lần. Nếu nó yêu cầu thêm tài nguyên và không được thì phải trả cái tài nguyên mà nó đang giữ.
Giải pháp này cũng không khả thi bởi trong thực tế một tiến trình cần nhiều hơn 1 tài nguyên mới có thể hoạt động được.
Tiến trình phải yêu cầu và được cấp tất cả tài nguyên mà nó cần ngay đầu công việc. Giải pháp này cũng không khả thi vì nó tốn nhiều tài nguyên

Loại bỏ Không tiếm quyền( No Preemption):
Hệ điều hành sẽ lấy lại tài nguyên từ tiến trình mà nó đang chiếm giữ khi sử dụng xong. Nhưng với một số tài nguyên có thể không lấy lại được.

Loại bỏ chờ xoay vòng( Circular Wait):
Có thể cấp số thứ tự cho mỗi tài nguyên, và mỗi tiến trình chỉ được yêu cầu tài nguyên theo thứ tự tăng dần.

LeThanhTung (I11C) đã viết: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.

Mình bổ sung thêm vd
- vd: như trong máy tính chúng ta, nếu ta mở quá nhiều chương trình mà máy tính cấu hình thấp như RAM ít, CPU chậm, sẽ gây ra hiện tương deadlock(mình thì thích kêu là thắt cổ chai ) gây treo mấy, do có quá nhìu chương trình yêu cầu tài nguyên từ CPU và RAM.
- vd: hằng tháng ba mẹ cho chúng ta 1 triệu, nhưng tháng này có quá nhiều khoảng để chi tiêu và ta chi quá 1 triệu=> deadlock, chúng ta không thể chi trả tiếp và kẹt tiền(giống sv tụi mình ).

---Phát hiện deadlock:
- 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ờ.
- 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.
--Phục hồi deadlock:
+ 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.
+ Để 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.

Để deadlock xảy ra, một trong bốn điều kiện cần phải xảy ra. Bằng cách đảm
bảo ít nhất một trong bốn điều kiện này không thể xảy ra, chúng ta có thể ngăn chặn
việc xảy ra của deadlock. Chúng ta tìm hiểu tỷ mỹ tiếp cận này bằng cách xem xét
mỗi điều kiện cần riêng rẻ nhau.

Thuật giải tránh deadlock RAG (áp dụng cho trường hợp loại tài nguyên chỉ có 1 phiên bản) nếu có nhiều phiên bản thuật giải này không dùng được:
- 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.

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

- Nếu không có chu trình nào thì không có Deadlock.
- Nếu có chu trình thì có hoặc không có Deadlock:
+ Có Deadlock khi các tài nguyên có 1 phiên bản.
+ Có thể không có Deadlock khi 1 tài nguyên thuộc chu trình có nhiều phiên bản.
Ví dụ:


R1,R2 có 2 phiên bản nên H1 được xem là không có Deadlock.
Bởi vì: Giả sử H1 phản ánh trạng thái hệ thống ở thời điểm 16g và p3 xin tài nguyên trong R2. Đến 16g5, giả sử p4 dùng xong phiên bản trong R2 nên nó không còn mũi tên nữa. Lúc đó mũi tên từ R2 trỏ đến p3 có nghĩa là lúc này p3 đang dùng tài nguyên của R2 và yêu cầu xin tài nguyên R2 được đáp ứng. Do đó ko còn dấu hiệu của Deadlock nữa (trên hình sau, hoàn toàn không có chu trình với mũi tên "đuổi nhau").
Hình được vẽ lại như sau:



Admin
Tốt. Thày có sửa một số câu chữ (nhưng không hết được).

Là trạng thái, tình huống kẹt khi mà không tiến trình nào kết thúc công việc.

ví dụ: 2 người chết đuối ở sông không ai chịu nhả (trạng thái kẹt)

Phần lớn, chúng ta có thể giải quyết vấn đề deadlock :
• 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.

1.Không giải quyết - Giải thuật đà điểu:
• Coi như không có vấn đề deadlock.
• Dựa trên cơ sở:
Deadlock rất ít xảy ra.
Chi phí giải quyết rất cao.
• Được dùng trên các hệ điều hành: Unix, Windows.
2.Phát hiện và phục hồi từ deadlock:
• Phát hiện deadlock:
Dùng các giải thuật phát hiện vòng chờ các process.
Do người quản trị hệ thống.
• Phục hồi từ deadlock:
Kết thúc các process bị deadlock.
Kết thúc tất cả các process bị deadlock.
Lần lượt kết thúc các process bị deadlock cho đến khi hết deadlock.
Thông số chọn process để kết thúc:
Độ ưu tiên.
Thời gian đã thực thi.
Thời gian còn lại.
Số tài nguyên đã cấp phát.
Số tài nguyên đang chờ.
Lấy lại tài nguyên từ process.
Lần lượt lấy lại các tài nguyên đã cấp phát cho các process cho đến khi hết deadlock.
Phụ thuộc bản chất của tài nguyên.
Sử dụng công cụ của hệ điều hành.
Phục hồi các điểm kiểm tra.
Định kỳ tạo các điểm kiểm tra (checkpoint).
Lưu trạng thái hệ thống tại điểm kiểm tra.
Thực hiện lại (rollback) các process bị deadlock tại các điểm kiểm tra.
Lần lượt thực hiện lại các process bị deadlock tại các điểm kiểm tra cho đến khi hết deadlock.
3.Ngăn chặn deadlock:
Loại bỏ các điều kiện dẫn đến deadlock.
Các điều kiện xem như không thể loại bỏ:
Loại trừ tương hỗ.
Không lấy lại tài nguyên từ process.
• Loại bỏ điều kiện loại trừ tương hỗ:
Giảm số tài nguyên tranh chấp.
Tăng số lượng tài nguyên.
Cấp phát tài nguyên dạng spool.
Vd: chỉ 1 printer daemon dùng máy in.
Các process gởi yêu cầu cho printer daemon.
• Loại bỏ điều kiện giữ và chờ tài nguyên:
Nguyên tắc: process không được giữ tài nguyên khi yêu cầu tài nguyên mới.
Process khai báo tài nguyên và được cấp phát 1 lần.
Nếu process yêu cầu tài nguyên và không được cấp phát thì phải trả các tài nguyên đang giữ.
• Loại bỏ điều kiện không lấy lại tài nguyên:
Lấy lại tài nguyên từ process.
Không thể với tài nguyên như máy in.
• Loại bỏ vòng chờ các process:
Có thể quy định số thứ tự tài nguyên.
Process chỉ được yêu cầu tài nguyên theo thứ tự tăng.
Giả sử có deadlock:
P1 giữ Ri, chờ Rj -> i < j.
P2 giữ Rj, chờ Rj -> j < i.
4.Tránh deadlock:
• Chấp nhận các điều kiện tạo deadlock.
• Theo dõi và tránh dẫn đến deadlock.
• Hai hướng giải quyết.
• Không tạo process mới nếu có thể dẫn đến deadlock.:
Process cần khai báo số lượng tài nguyên cần sử dụng.
Không tạo process mới nếu số lượng tài nguyên hệ thống không đủ, có thể dẫn đến deadlock.
• Không cấp phát thêm tài nguyên cho process:
Liên quan đến việc sử dụng tài nguyên trong tương lai của các process.
Định nghĩa trạng thái hệ thống với:
Vector E: tổng số các loại tài nguyên.
Vector A: số tài nguyên mỗi loại chưa dùng.
Ma trận C: số tài nguyên đã cấp phát cho các process.
Ma trận R: số lượng tài nguyên các process sẽ tiếp tục yêu cầu.

* Định nghĩa: Deadlock là tình huống hoặc trạng thái của một nhóm tiến trình đang trong tình trạng bị kẹt, do có quá nhiều tiến trình cùng nhau chờ đợi một, tranh chấp 1 sự kiện, dữ liệu nào đó xảy ra.
* Các ví dụ minh họa:
VD1: Trên 1 cây cầu hẹp chỉ có thể cho 1 xe đi qua, mà nếu trong cùng 1 lúc có 2 xe cùng chạy lên cầu xe nào cũng ko chịu nhường xe nào cùng nhau tranh chấp cầu để mình được đi => cuối cùng do cầu quá hẹp nên hậu quả là ko xe nào qua cầu được bị kẹt lại giữa cầu, thậm chí là bị ngã xuống nước.
VD2: Trong thực tế vừa qua "khi nhà sản xuất smartphone hàng đầu thế giới Apple công bố sẽ bán điện thoại IP 4s trong vào khoảng tháng 10/2011" thì một số lượng lớn tính đồ IP đã tìm đến các trung tâm Apple Store để chờ và mua cho bằng được sản phẩm mơ ước này, làm cho các cửa hàng bán IP chật kín cả người tại thời điểm sắp ra mắt IP 4s do có một số người muốn mua trước nên đã chen lấn gây mất ổn định làm cho cửa hàng phải ngừng bán sản phẩm ra=> ko ai mua được.
VD3: Có 2 người cùng té xuống sông và cả hai đều ko biết bơi và đuối sức, nếu 1 trong 2 buôn tay người kia ra thì có thể 1 người sẽ sống sót, nhưng ko ai chịu buôn ra hết (theo hoán tính của con người) => cả 2 đều chết đuối.

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

Deadlock xảy ra khi có 4 điều kiện cần sau:
1. Loại trừ lẫn nhau(Mutual Exclusion): có một tài nguyên ko có tính Share, tại một thời điểm chỉ có duy nhất một tiến trình được phép sử dụng, thao tác với nó.
VD: Một cây cầu hẹp thì chỉ cho phép một chiếc xe đi qua, chứ nó ko cho phép cả 2 xe đi qua cùng một lúc lý do cầu hẹp
2. Giữ và chờ(Hold and Wait): nghĩa là có một tiến trình đang chiếm giữ một tài nguyên và ko chịu giải phóng cho nó, mà còn xin thêm một tài nguyên khác nữa để độc chiếm.
VD: Một Sv đi lấy Micro sau khi lấy xong về lớp sinh viên đó lại tiếp tục đi xuống văn phòng xin thêm một cái khác nữa, làm cho người khác ko có Micro để dùng do mỗi phòng chỉ được cấp 1 Micro.
3. Không có tiếm quyền(No Preemption): tài nguyên đang bị giữ bởi tiến trình này không thể bị tiếm quyền đề giành lại quyền sử dụng và để cấp phát cho tiến trình khác được mà phải được tiến trình đó tự nguyện trao trả.
VD: Trên đường mà ko có CSGT thì ko biết chuyện gì sẽ xảy ra, tất cả mọi người ai ai cũng đều muốn giành đường đi cho riêng mình ko ai chịu ngừng cho ai hết thì điều đó thật là tai hại. Phải có CSGT mới có thể bắt người này nhường đường đi cho người kia và ngược lại để mọi người đều được lưu thông
4. Chờ xoay vòng(Circular Wait): Khi có hàng loạt tiến trình chờ tại nguyên xoay vòng lẩn nhau, tiến trình P1 chờ TN giữ bởi P2, P2 chờ TN giữ bởi P3, ..., Pn chờ TN giữ bởi P1.
VD: Xe bị kẹt ngay tại các vòng xay ngã 4, ngã 5, xe chạy hướng này thì phải chờ xe chạy hướng kia , xe chạy hướng kia phải chờ xe chạy hướng nọ, xe chạy hướng nọ phải chờ xe chạy hướng đầu tiên cứ thế ko xe nào chịu nhường xe nào dẫn đến kẹt xe.
=> Chỉ cần xảy ra 1 trong 4 TH trên thì đã có thể xảy ra Deadlock rùi
*Note: Phủ định 4 TH trên là cách để chúng ta ngăn chặng Deadlocks

Deadlock xuất hiện nếu 1 trong 4 điều kiện sau xuất
hiện đồng thời (điều kiện cần):
z C1: Loạitrừ lẫnnhau(mutual exclusion)
z C2: Giữ vàchờ (hold and wait)
z C3: Khôngcó đặcquyền(preemption)
z C4: Chờ vòng(circular wait)

LuongGiaDuc(I12A) đã viết:Đị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 : Dead là chết,lock là cái khỏa,như thầy đã định nghĩa,cái khỏa chết thì ko còn làm được gì nữa,tương tự như Hệ điều hành xuất hiện deadlock sẽ như 1 cái khóa chết.

- Đồ 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.
Deadlock có thể mô tả chính xác hơn bằng cách hiển thị đồ thị có hướng gọi là
đồ thị cấp phát tài nguyên hệ thống. Đồ thị này chứa một tập các đỉnh V và tập hợp
các cạnh E. Một tập các đỉnh V được chia làm hai loại nút P = {P1, P2,…,Pn} là tập
hợp các quá trình hoạt động trong hệ thống, và R = {R1, R2, ..., Rm} là tập hợp chứa
tất cả các loại tài nguyên trong hệ thống.
Một cạnh có hướng từ quá trình Pi tới loại tài nguyên Rj được ký hiệu Pi →Rj;
nó biểu thị rằng quá trình Pi đã yêu cầu loại tài nguyên Rj và hiện đang chờ loại tài
nguyên đó. Một cạnh có hướng từ loại tài nguyên Rj tới quá trình Pi được hiển thị bởi
Rj → Pi; nó hiển thị rằng thể hiện của loại tài nguyên Rj đã được cấp phát tới quá trình
Pi. Một cạnh có hướng Pi → Rj được gọi là cạnh yêu cầu; một cạnh có hướng Rj → Pi
được gọi là cạnh gán.
Bằng hình tượng, chúng ta hiển thị mỗi quá trình Pi là một hình tròn, và mỗi
loại tài nguyên Rj là hình chữ nhật. Vì loại tài nguyên Rj có thể có nhiều hơn một thể
hiện, chúng ta hiển thị mỗi thể hiện là một chấm nằm trong hình vuông. Chú ý rằng
một cạnh yêu cầu trỏ tới chỉ một hình vuông Rj, trái lại một cạnh gán cũng phải gán
tới một trong các dấu chấm trong hình vuông.
Khi quá trình Pi yêu cầu một thể hiện của loại tài nguyên Rj, một cạnh yêu cầu
được chèn vào đồ thị cấp phát tài nguyên. Khi yêu cầu này có thể được đáp ứng, cạnh
yêu cầu lập tức được truyền tới cạnh gán. Khi quá trình không còn cần truy xuất tới
tài nguyên, nó giải phóng tài nguyên, và khi đó dẫn đến cạnh gán bị xoá.
Đồ thị cấp phát tài nguyên được hiển thị trong hình VI-1 dưới đây mô tả trường hợp
sau:



• Các tập P, R, và E:
o P = {P1, P2, P3}
o R = {R1, R2, R3, R4}
o E = {P1→R1, P2 →R3, R1 →P2, R2→P2, R3→P3}
• Các thể hiện tài nguyên
o Một thể hiện của tài nguyên loại R1
o Hai thể hiện của tài nguyên loại R2
o Một thể hiện của tài nguyên loại R3
o Một thể hiện của tài nguyên loại R4
• Trạng thái quá trình
o Quá trình P1 đang giữ một thể hiện của loại tài nguyên R2 và đang chờ
một thể hiện của loại tài nguyên R1.
o Quá trình P2 đang giữ một thể hiện của loại tài nguyên R1 và R2 và
đang chờ một thể hiện của loại tài nguyên R3.
o Quá trình P3 đang giữ một thể hiện của R3
Đồ thị cấp phát tài nguyên hiển thị rằng, nếu đồ thị không chứa chu trình, thì
không có quá trình nào trong hệ thống bị deadlock. Nếu đồ thị có chứa chu trình, thì
deadlock có thể tồn tại.
Nếu mỗi loại tài nguyên có chính xác một thể hiện, thì một chu trình ngụ ý rằng
một deadlock xảy ra. Nếu một chu trình bao gồm chỉ một tập hợp các loại tài nguyên,
mỗi loại tài nguyên chỉ có một thể hiện thì deadlock xảy ra. Mỗi quá trình chứa trong
chu trình bị deadlock. Trong trường hợp này, một chu trình trong đồ thị là điều kiện
cần và đủ để tồn tại deadlock.
Nếu mỗi loại tài nguyên có nhiều thể hiện thì chu trình không ngụ ý deadlock
xảy. Trong trường hợp này, một chu trình trong đồ thị là điều kiện cần nhưng chưa đủ
để tồn tại deadlock.
Để hiển thị khái niệm này, chúng ta xem lại đồ thị ở hình VII-1 ở trên. Giả sử
quá trình P3 yêu cầu một thể hiện của loại tài nguyên R2. Vì không có thể hiện tài
nguyên hiện có, một cạnh yêu cầu P3 → R2 được thêm vào đồ thị (hình VI-2). Tại thời
điểm này, hai chu trình nhỏ tồn tại trong hệ thống:
P1 → R1 → P2 → R3 → P3 → R2 → P1
P2 → R3 → P3 → R2 → P2



Quá trình P1, P2, và P3 bị deadlock. Quá trình P3 đang chờ tài nguyên R3, hiện
được giữ bởi quá trình P2. Hay nói cách khác, quá trình P3 đang chờ quá trình P1 hay
P2 giải phóng tài nguyên R2. Ngoài ra, quá trình P1 đang chờ quá trình P2 giải phóng
tài nguyên R1.
Bây giờ xem xét đồ thị cấp phát tài nguyên trong hình VI-3 dưới đây. Trong thí
dụ này, chúng ta cũng có một chu kỳ
P1 → R1 → P3 → R2 → P1



Tuy nhiên, không có deadlock. Chú ý rằng quá trình P4 có thể giải phóng thể
hiện 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.
Tóm lại, 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. Ngoài ra, nếu có chu trình thì có thể có hoặc không trạng thái
deadlock. Nhận xét này là quan trọng khi chúng ta giải quyết vấn đề deadlock.

- Mutual exclusion: với mỗi tài nguyên, chỉ có một process sử dụng tại một thời điểm.
- Hold and wait : một process vẫn sở hữu tài nguyên đã được cấp phát trong khi yêu cầu một tài ngyên khác.
- No preemption : một tài nguyên không thể bị đoạt lại từ chính process đang sở hữu tài nguyên đó.
- Circular wait : tồn tại một chu kỳ khép kín các yêu cầu tài nguyên

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.

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.

  P là tiến trình đang vận hành
  R là các loại tài nguyên có trong hệ thống
  Ở trên là có 3 tiến trình đang vận hành đó là (hình tròn)
  P1,P2,P3 là các số hiệu.
  Có 4 loại tài nguyên khác nhau R1, R2, R3, R4 (hình vuông chữ nhật)
  Còn dấu chấm tròn đen là phiên bản

  Các mũi tên màu đỏ mà trỏ vào các tiến trình là đang được cấp.
  Còn các mũi tên màu đen là nó đang xin tài nguyên.
  R4 trạng thái ngủ không ai xin tài nguyên hết quá rảnh.
  Hình trên không phải Deadlock vì không có chu trình





  Tương tự như hình trên nhưng hình này lai có Deadlock? Tại vì có mũi tên màu tím
  Dấu hiệu để biết có Deadlock là có chu trình xoay vòng các mui tên đuổi nhau.
    P1 → R1 → P2 → R3 → P3 → R2 → P1
    P2 → R3 → P3 → R2 → P2
  P3 đang xin tài nguyên nhưng hiên tại R3 đã hết tài nguyên tài nguyên cảu R3 đã được cấp phát cho P1 và P2 hết rồi.
  Trường hợp mà có xoay vòng chu trình nhưng mà:
     Có Deadlock khi các tài nguyên trên chu trình chỉ có một phiên bản.
     Có thể không có Deadlock khi 1 tài nguyên thuộc chu trình có nhiều phiên bản.