Thảo luận Bài 8

Vào giờ cao điểm xảy ra tình trạng ->kẹt xe?
Khi đèn đỏ bị chết xảy ra tình trạng ->kẹt xe?
Khi 1 anh nào đó cố tình vượt đèn đỏ ->kẹt xe?
Bạn nào dùng Hệ Điều Hành giải thích hiện trạng này,xử lí tình huống luôn.Phải dùng kiến thức hệ điều hành.

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

*Giải thích:- là một đồ thị có hướng gồm tập nút V và tập cung E
+Tập nút V: có 2 loại
. Tập hợp các tiến trình đang vận hành p={p1,p2,p3….,pn}
. Tập hợp các tài nguyên có trong hệ thống R={R1,R2,R3,…,Rm}
+Tập cung E: có 2 loại
. cung ấn định: cung từ: R1 -> P2 , R3-> P3 , R2->P1 , R2->P2
. cung yêu cầu: cung từ :p1-> R1 , p2->R3
- đồ thị có chu trình thì có thể: có Deadlock (khi các tài nguyên trên chu trình chỉ có 1 phiên bản) hoặc không có Deadlock(khi một tài nguyên thuộc chu trình có nhiều phiên bản).
- đồ thị không có chu trình thì không có Deadlock.
* có trường hợp mô hình RAG có chu trình nhưng không có Deadlock

Giả sử: lúc 18h : R1 được cấp cho p2 , R2 được cấp cho p4
- Đến lúc 18h6 phút:
+thì p1 yêu cầu tài nguyên từ R1 khi đó R1 lấy tài nguyên cấp cho p2 cấp lại cho p1 khi đó cung yêu cầu từ p1 đến R1 sẽ biến thành cung ấn định từ R1 đến p1
+ thì p3 yêu cầu tài nguyên từ R2 khi đó R2 lấy tài nguyên cấp cho p4 cấp lại cho p3 khi đó cung yêu cầu từ p3 đến R3 sẽ biến thành cung ấn định từ R2 đến p3
*Bạn nào biết rõ hơn thì bổ sung giùm mình nha

- Một trạng thái được gọi là "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ả các process thực thi hoàn tất.
- Khi đó hệ thống tồn tại 1 chuỗi an toàn {P1,P2, ..., P3} 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- 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 cho 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..

Deadlock: là tình huống kẹt tiến trình (process) với một tập các process bị blocked, mỗi process giữ tài nguyên và đang chờ tài nguyên mà process khác trong tập đang có.

Ví dụ :

Giả sử hệ thống có 2 file trên đĩa.

P1 và P2 mỗi process đang mở một file và yêu cầu mở file kia.

Ví dụ 2

Semaphore A và B, khởi tạo bằng 1

P0 P1

wait (A); wait(B)

wait (B); wait(A)

Trong môi trường multiprogramming 1 số process có thể tranh nhau 1 số tài nguyên hạn chế. 1 process yêu cầu các tài nguyên. Nếu tài nguyên ko thể đáp ứng tại thời điểm đó thì process sẽ chuyển sang trạng thái chờ. Các process chờ có thể sẽ ko 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 process khác. Và process khác cũng đang ở trạng thái chờ...Tức là các process sẽ mãi mãi bị kẹt ở trạng thá chờ => deadlock.
vd: 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.

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ột trong 4 trường hợp trên xảy ra. đều sẽ dẫn đến Deadlock

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.

TranVanBao(I12A) đã viết:Trong môi trường multiprogramming 1 số process có thể tranh nhau 1 số tài nguyên hạn chế. 1 process yêu cầu các tài nguyên. Nếu tài nguyên ko thể đáp ứng tại thời điểm đó thì process sẽ chuyển sang trạng thái chờ. Các process chờ có thể sẽ ko 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 process khác. Và process khác cũng đang ở trạng thái chờ...Tức là các process sẽ mãi mãi bị kẹt ở trạng thá chờ => deadlock.
vd: 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 thêm một số thông tin sau để làm rõ khái niệm DEADLOCK và tại sao phải chú ý đến deadlock.

Trong môi truờ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 đang chờ khác. Trường hợp này được gọi là deadlock (khoá chết).
Trong chương này chúng ta sẽ mô tả các phương pháp mà hệ điều hành có thể dùng để ngăn chặn hay giải quyết deadlock. Hầu hết các hệ điều hành không cung cấp phương tiện ngăn chặn deadlock nhưng những đặc điểm này sẽ được thêm vào sau đó. Vấn đề deadlock chỉ có thể trở thành vấn đề phổ biến, xu hướng hiện hành gồm số lượng lớn quá trình, chương trình đa luồng, nhiều tài nguyên trong hệ thống và đặc biệt các tập tin có đời sống dài và những máy phục vụ cơ sở dữ liệu hơn là các hệ thống bó.

Đặc điểm deadlock
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.

Điều kiện cần thiết gây ra deadlock
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ương 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.

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ứatấ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 ra. 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:


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ỳ

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.

Nếu tất cả tài nguyên chỉ có một thể hiện thì chúng ta có thể định nghĩa giải thuật phát hiện deadlock dùng một biến dạng của đồ thị cấp phát tài nguyên, được gọi là đồ thị chờ (wait-for). Chúng ta đặt được đồ thị này từ đồ thị cấp phát tài nguyên bằng cách gỡ bỏ các nút của loại tài nguyên và xóa các cạnh tương ứng.


Chính xác hơn, một cạnh từ Pi tới Pj trong đồ thị chờ hiển thị rằng quá trình Pi đang chờ một quá trình Pj để giải phóng tài nguyên mà Pi cần. Cạnh Pi → Pj tồn tại trong đồ thị chờ nếu và chỉ nếu đồ thị cấp phát tài nguyên tương ứng chứa hai cạnh Pi → Rq và Rq → Pj đối với một số tài nguyên Rq. Thí dụ, trong hình VI-7 dưới đây, chúng ta trình bày đồ thị cấp phát tài nguyên và đồ thị chờ tương ứng.
Như đã đề cập trước đó, deadlock tồn tại trong hệ thống nếu và chỉ nếu đồ thị chờ chứa chu trình. Để phát hiện deadlock, hệ thống cần duy trì đồ thị chờ và định kỳ gọi giải thuật để tìm kiếm chu trình trong đồ thị.
Một giải thuật phát hiện chu trình trong đồ thị yêu cầu độ phức tạp n2 thao tác, ở đây n là số cạnh của đồ thị.

Khi nào thì chúng ta nên nạp giải thuật phát hiện deadlock? Câu trả lời phụ thuộc vào hai yếu tố:
1) Deadlock có khả năng xảy ra thường xuyên như thế nào?
2) Bao nhiêu quá trình sẽ bị ảnh hưởng bởi deadlock khi nó sẽ ra?
Nếu deadlock xảy ra thường xuyên thì giải thuật phát hiện nên được nạp lên thường xuyên. Những tài nguyên được cấp phát để các quá trình bị deadlock sẽ rảnh cho đến khi deadlock có thể bị phá vỡ. Ngoài ra, số lượng quá trình liên quan trong chu trình deadlock có thể tăng lên. Deadlock xảy ra chỉ khi một số quá trình thực hiện yêu cầu mà không được cấp tài nguyên tức thì. Yêu cầu này có thể là yêu cầu cuối hoàn thành một chuỗi các quá trình đang yêu cầu. Ngoài ra, chúng ta có thể nạp giải thuật phát hiện mọi khi một yêu cầu cho việc cấp phát không thể được cấp tức thì. Trong trường hợp này, chúng ta không chỉ định nghĩa tập hợp các quá trình bị deadlock, mà còn xác định quá trình đã gây ra deadlock. (Trong thực tế, mỗi quá 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 có thể gây chu trình trong đồ thị tài nguyên, mỗi chu trình hoàn thành bởi yêu cầu mới nhất và “được gây ra” bởi một quá trình có thể xác định.

Dĩ nhiên, nạp giải thuật phát hiện deadlock cho mỗi yêu cầu có thể gây ra một chi phí có thể xem xét trong thời gian tính toán. Một thay đổi ít đắt hơn là nạp giải thuật tại thời điểm ít thường xuyên hơn- thí dụ, một lần một giờ hay bất cứ khi nào việc sử dụng CPU rơi xuống thấp hơn 40%. Nếu giải thuật phát hiện deadlock được nạp trong những thời điểm bất kỳ, thì có nhiều chu trình trong đồ thị tài nguyên.
Chúng ta không thể nói quá trình nào của nhiều quá trình bị deadlock gây ra deadlock.

Để xóa deadlock bằng cách hủy bỏ quá trình, chúng ta dùng một trong hai phương pháp. Trong cả hai phương pháp, hệ thống lấy lại tài nguyên được cấp phát đối với quá trình bị kết thúc.
• Huỷ bỏ tất cả quá trình bị deadlock: phương pháp này rõ ràng sẽ phá vỡ chu trình deadlock, nhưng chi phí cao; các quá trình này có thể đã tính toán trong thời gian dài, và các kết quả của các tính toán từng phần này phải bị bỏ đi và có thể phải tính lại sau đó.
• Hủy bỏ một quá trình tại thời điểm cho đến khi chu trình deadlock bị xóa:phương pháp này chịu chi phí có thể xem xét vì sau khi mỗi quá trình bị hủy bỏ, một giải thuật phát hiện deadlock phải được nạp lên để xác định có quá trình nào vẫn đang bị deadlock.

Hủy bỏ quá trình có thể không dễ. Nếu một quá trình đang ở giữa giai đoạn cập nhật một tập tin, kết thúc nó sẽ để tập tin đó trong trạng thái không phù hợp. Tương tự, nếu quá trình đang ở giữa giai đoạn in dữ liệu ra máy in, hệ thống phải khởi động lại trạng thái đúng trước khi in công việc tiếp theo.
Nếu phương pháp kết thúc một phần được dùng thì với một tập hợp các quá trình deadlock được cho, chúng ta phải xác định quá trình nào (hay các quá trình nào) nên được kết thúc trong sự cố ắng để phá vỡ deadlock. Việc xác định này là một quyết định chính sách tương tự như các vấn đề lập thời biểu CPU. Câu hỏi về tính kinh tế là chúng ta nên hủy bỏ quá trình nào thì sự kết thúc của quá trình đó sẽ chịu chi phí tối thiểu. Tuy nhiên, thuật ngữ chi phí tối thiểu là không chính xác. Nhiều yếu tố có thể xác định quá trình nào được chọn bao gồm:

1) Độ ưu tiên của quá trình là gì.
2) Quá trình đã được tính toán bao lâu và bao lâu nữa quá trình sẽ tính toán trước khi hoàn thành tác vụ được chỉ định của nó.
3) Bao nhiêu và loại tài nguyên gì quá trình đang sử dụng.
4) Bao nhiêu tài nguyên nữa quá trình cần để hoàn thành
5) Bao nhiêu quá trình sẽ cần được kết thúc.
6) Quá trình là giao tiếp hay dạng bó

Để xóa deadlock sử dụng việc trả lại tài nguyên, sau khi chúng ta đòi một số tài nguyên từ các quá trình và cho các tài nguyên này tới các quá trình khác cho đến khi chu trình deadlock bị phá vỡ.
Nếu việc đòi lại được yêu cầu để giải quyết deadlock thì ba vấn đề cần được xác định:
• Chọn nạn nhân: những tài nguyên nào và những quá trình nào bị đòi lại?

Trong khi kết thúc quá trình, chúng ta phải xác định thứ tự đòi lại để tối thiểu chi phí. Các yếu tố chi phí có thể gồm các tham số như số lượng tài nguyên một quá trình deadlock đang giữ, và lượng thời gian một quá trình deadlock dùng trong sự thực thi của nó.

• Trở lại trạng thái trước deadlock: Nếu chúng ta đòi lại tài nguyên từ một quá trình, điều gì nên được thực hiện với quá trình đó? Rõ ràng, nó không thể tiếp tục việc thực thi bình thường; nó đang bị mất một số tài nguyên được yêu cầu. Chúng ta phải phục hồi quá trình tới trạng thái an toàn và
khởi động lại từ trạng thái gần nhất trước đó.

Thông thường, rất khó để xác định trạng thái gì là an toàn vì thế giải pháp đơn giản nhất là phục hồi toàn bộ: hủy quá trình và sau đó khởi động lại nó. Tuy nhiên, hữu hiệu hơn để phục hồi quá trình chỉ đủ xa cần thiết để phá vỡ deadlock. Ngoài ra, phương pháp này yêu cầu hệ thống giữ nhiều thông tin hơn về trạng thái của tất cả các quá trình đang chạy.
Đói tài nguyên: chúng ta đảm bảo như thế nào việc đói tài nguyên không xảy ra? Nghĩa là, chúng ta có thể đảm bảo rằng tài nguyên sẽ không luôn bị đòi lại từ cùng một quá trình.
Trong một hệ thống việc chọn nạn nhân ở đâu dựa trên cơ sở các yếu tố chi phí, nó có thể xảy ra cùng quá trình luôn được chọn như là nạn nhân. Do đó, quá trình này không bao giờ hoàn thành tác vụ được chỉ định của nó, một trường hợp đói tài nguyên cần được giải quyết trong bất kỳ hệ thống thực tế. Rõ ràng, chúng ta phải đảm bảo một quá trình có thể được chọn như một nạn nhân chỉ một số lần xác định (nhỏ). Giải pháp chung nhất là bao gồm số lượng phục hồi trong yếu tố chi phí.

Tóm tắt:

Trạng thái deadlock xảy ra khi hai hay nhiều quá trình đang chờ không xác định một sự kiện mà có thể được gây ra chỉ bởi một trong những quá trình đang chờ. Về nguyên tắc, có ba phương pháp giải quyết deadlock:
• Sử dụng một số giao thức để ngăn chặn hay tránh deadlock, đảm bảo rằng hệ thống sẽ không bao giờ đi vào trạng thái deadlock.
• Cho phép hệ thống đi vào trạng thái deadlock, phát hiện và sau đó phục hồi.
• Bỏ qua vấn đề deadlock và giả vờ deadlock chưa bao giờ xảy ra trong hệ thống. Giải pháp này là một giải pháp được dùng bởi hầu hết các hệ điều hành bao gồm UNIX.

Trường hợp deadlock có thể xảy ra nếu và chỉ nếu bốn điều kiện cần xảy ra cùng một lúc trong hệ thống: loại trừ hỗ tương, giữ và chờ cấp thêm tài nguyên, không đòi lại tài nguyên, và tồn tại chu trình trong đồ thị cấp phát tài nguyên. Để ngăn chặn deadlock, chúng ta đảm bảo rằng ít nhất một điều kiện cần không bao giờ xảy ra.
Một phương pháp để tránh deadlock mà ít nghiêm ngặt hơn giải thuật ngăn chặn deadlock là có thông tin trước về mỗi quá trình sẽ đang dùng tài nguyên như thế nào. Thí dụ, giải thuật Banker cần biết số lượng tối đa của mỗi lớp tài nguyên có thể được yêu cầu bởi mỗi quá trình. Sử dụng thông tin này chúng ta có thể định nghĩa giải thuật tránh deadlock.
Nếu hệ thống không thực hiện một giao thức để đảm bảo rằng deadlock sẽ không bao giờ xảy ra thì lược đồ phát hiện và phục hồi phải được thực hiện. Giải thuật phát hiện deadlock phải được nạp lên để xác định deadlock có thể xảy ra hay không. Nếu deadlock được phát hiện hệ thống phải phục hồi bằng cách kết thúc một số quá trình bị deadlock hay đòi lại tài nguyên từ một số quá trình bị deadlock.
Trong một hệ thống mà nó chọn các nạn nhân để phụv hồi về trạng thái trước đó chủ yếu dựa trên cơ sở yếu tố chi phí, việc đói tài nguyên có thể xảy ra. Kết quả là quá trình được chọn không bao giờ hoàn thành tác vụ được chỉ định của nó.

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