Thảo luận Bài 8

Trong bài giảng thầy chỉ nói “xử trí deadlock” chứ không nói “xử lý deadlock” là tại sao?
Là tại vì tuy chúng gần gần nghĩa với nhau nhưng cách làm của mỗi từ là hoàn toàn khác nhau.
+ Xử lý: là làm theo những thao tác cụ thể, có sẵn, áp dụng một cách máy móc, thụ động.
+ Xử trí: là xử lý nhưng có trí tuệ, có suy nghĩ, cân nhắc để quyết định vấn đề. Làm việc một cách khoa học, linh hoạt chứ không thụ động, đơn giản.

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.

Khi 1 tiến trình yêu cầu tài nguyên, HĐH phải xác định việc cấp phát TN đó có đảm bảo hệ thống trong Trạng thái an toàn hay không. Nếu an toàn, tiến trình nhận được tài nguyên cần. Nếu không an toàn, tiến trình phải chờ.


Trạng thái hệ thống được gọi là An toàn nếu 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


Cấp phát tài nguyên theo chuỗi an toàn sẽ không dẫn đến Deadlock.


Nếu không tồn tại chuỗi an toàn, trạng thái hệ thống gọi là Không an toàn.


Deadlock là trạng thái không an toàn nhưng không phải tất cả các trạng thái không an toàn là trạng thái 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.

Bốn điều kiện cần để dẫn đến Deadlock
-Loai trừ tương hỗ: có 1 tài nguyên không chia sẽ tài nguyên. là tại 1 thời điểm có 1 tiến trình sử dụng nó.
-Giữ và chờ : có 1 tiến trình đang giữ 1 tài nguyên và xin thêm tài nguyên đang bị chiếm giữ.
-Không có tiếm quyền : tài nguyên đang dùng ko bị tiếm quyền mà tự động trả lại HĐH
- Chờ xoay vị : giả sử P1,P2 ,P3... p1 chờ tài nguyên của P2 giữ và P2 chờ tài nguyên của P3. Mong các bạn góp ý

Đặ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. Trước khi chúng ta thảo luận các phương pháp khác nhau giải quyết vấn đề deadlock, chúng ta sẽ mô tả các đặc điểm mà deadlock mô tả.

Câu 1:Trình bày các phương thức xử trí Deadlock.
Giải:
- Sử dụng quy tắc Ngăn chặn (Prevention) hoặc Tránh (Avoidance) để Deadlock không bao giờ xảy ra.
- Cho phép hệ thống bị Deadlock, sau đó Xác định (Detection) và tìm cách Khắc phục (Recover).
- 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).

Câu 2: Trình bày 4 cách ngăn chặn Deadlock.
Giải:
Để 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.
Câu 3: Thế nào là trạng thái an toàn của hệ thống?
Giải:
- 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.

Máy tính của mình lâu lâu nếu vô tình nhấn phím hay nhấn chuột nhiều lần làm cho nhiều chương trình cùng chạy một lúc, thì máy dễ bị treo, bị đứng. Khi bị như vậy chỉ có cách là nhấn Reset để khởi động lại. Thì trường hợp này có phải máy tính bị deadlock không mấy bạn!

Thế nào là trạng thái an toàn của hệ thống?
Giải:
- 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

Ngăn chặn 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.

Loại trừ hỗ tương

Điều kiện loại trừ hỗ tương phải giữ cho tài nguyên không chia sẻ. Thí dụ, một máy in không thể được chia sẻ cùng lúc bởi nhiều quá trình. Ngược lại, các tài nguyên có thể chia sẻ không đòi hỏi truy xuất loại trừ hỗ tương và do đó không thể liên quan đến deadlock. Những tập tin chỉ đọc là một thí dụ tốt cho tài nguyên có thể chia sẻ. Nếu nhiều quá trình cố gắng mở một tập tin chỉ đọc tại cùng một thời điểm thì chúng có thể được gán truy xuất cùng lúc tập tin. Một quá trình không bao giờ yêu cầu chờ tài nguyên có thể chia sẻ. Tuy nhiên, thường chúng ta không thể ngăn chặn deadlock bằng cách từ chối điều kiện loại trừ hỗ tương: một số tài nguyên về thực chất không thể chia sẻ.

Giữ và chờ cấp thêm tài nguyên

Để đảm bảo điều kiện giữ-và-chờ cấp thêm tài nguyên không bao giờ xảy ra trong hệ thống, chúng ta phải đảm bảo rằng bất cứ khi nào một quá trình yêu cầu tài nguyên, nó không giữ bất cứ tài nguyên nào khác. Một giao thức có thể được dùng là đòi hỏi mỗi quá trình yêu cầu và được cấp phát tất cả tài nguyên trước khi nó bắt đầu thực thi. Chúng ta có thể cài đặt sự cung cấp này bằng cách yêu cầu các lời gọi hệ thống yêu cầu tài nguyên cho một quá trình trước tất cả các lời gọi hệ thống khác.

Một giao thức khác cho phép một quá trình yêu cầu tài nguyên chỉ khi quá trình này không có tài nguyên nào. Một quá trình có thể yêu cầu một số tài nguyên và dùng chúng. Tuy nhiên, trước khi nó có thể yêu cầu bất kỳ tài nguyên bổ sung nào, nó phải giải phóng tất cả tài nguyên mà nó hiện đang được cấp phát.

Để hiển thị sự khác nhau giữa hai giao thức, chúng ta xét một quá trình chép dữ liệu từ băng từ tới tập tin đĩa, sắp xếp tập tin đĩa và sau đó in kết quả ra máy in. Nếu tất cả tài nguyên phải được yêu cầu cùng một lúc thì khởi đầu quá trình phải yêu cầu băng từ, tập tin đĩa và máy in. Nó sẽ giữ máy in trong toàn thời gian thực thi của nó mặc dù nó cần máy in chỉ ở giai đoạn cuối.

Phương pháp thứ hai cho phép quá trình yêu cầu ban đầu chỉ băng từ và tập tin đĩa. Nó chép dữ liệu từ băng từ tới đĩa, rồi giải phóng cả hai băng từ và đĩa. Sau đó, quá trình phải yêu cầu lại tập tin đĩa và máy in. Sau đó, chép tập tin đĩa tới máy in, nó giải phóng hai tài nguyên này và kết thúc.

Hai giao thức này có hai nhược điểm chủ yếu. Thứ nhất, việc sử dụng tài nguyên có thể chậm vì nhiều tài nguyên có thể được cấp nhưng không được sử dụng trong thời gian dài. Trong thí dụ được cho, chúng ta có thể giải phóng băng từ và tập tin đĩa, sau đó yêu cầu lại tập tin đĩa và máy in chỉ nếu chúng ta đảm bảo rằng dữ liệu của chúng ta sẽ vẫn còn trên tập tin đĩa. Nếu chúng ta không thể đảm bảo rằng dữ liệu vẫn còn tập tin đĩa thì chúng ta phải yêu cầu tất cả tài nguyên tại thời điểm bắt đầu cho cả hai giao thức. Thứ hai, đói tài nguyên là có thể. Một quá trình cần nhiều tài nguyên phổ biến có thể phải đợi vô hạn định vì một tài nguyên mà nó cần luôn được cấp phát cho quá trình khác.

Không đòi lại tài nguyên từ quá trình đang giữ chúng

Điều kiện cần thứ ba là không đòi lại những tài nguyên đã được cấp phát rồi. Để đảm bảo điều kiện này không xảy ra, chúng ta có thể dùng giao thức sau. Nếu một quá trình đang giữ một số tài nguyên và yêu cầu tài nguyên khác mà không được cấp phát tức thì tới nó (nghĩa là, quá trình phải chờ) thì tất cả tài nguyên hiện đang giữ được đòi lại. Nói cách khác, những tài nguyên này được giải phóng hoàn toàn. Những tài nguyên bị đòi lại được thêm tới danh sách các tài nguyên mà quá trình đang chờ. Quá trình sẽ được khởi động lại chỉ khi nó có thể nhận lại tài nguyên cũ của nó cũng như các tài nguyên mới mà nó đang yêu cầu.

Có một sự chọn lựa khác, nếu một quá trình yêu cầu một số tài nguyên, đầu tiên chúng ta kiểm tra chúng có sẳn không. Nếu tài nguyên có sẳn, chúng ta cấp phát chúng. Nếu tài nguyên không có sẳn, chúng ta kiểm tra chúng có được cấp phát tới một số quá trình khác đang chờ tài nguyên bổ sung. Nếu đúng như thế, chúng ta lấy lại tài nguyên mong muốn đó từ quá trình đang đợi và cấp chúng cho quá trình đang yêu cầu. Nếu tài nguyên không sẳn có hay được giữ bởi một quá trình đang đợi, quá trình đang yêu cầu phải chờ. Trong khi nó đang chờ, một số tài nguyên của nó có thể được đòi lại chỉ nếu quá trình khác yêu cầu chúng. Một quá trình có thể được khởi động lại chỉ khi nó được cấp các tài nguyên mới mà nó đang yêu cầu và phục hồi bất cứ tài nguyên nào đã bị lấy lại trong khi nó đang chờ.

Giao thức này thường được áp dụng tới tài nguyên mà trạng thái của nó có thể được lưu lại dễ dàng và phục hồi lại sau đó, như các thanh ghi CPU và không gian bộ nhớ. Nó thường không thể được áp dụng cho các tài nguyên như máy in và băng từ.

Tồn tại chu trình trong đồ thị cấp phát tài nguyên

Điều kiện thứ tư và cũng là điều kiện cuối cùng cho deadlock là điều kiện tồn tại chu trình trong đồ thị cấp phát tài nguyên. Một cách để đảm bảo rằng điều kiện này không bao giờ xảy ra là áp đặt toàn bộ thứ tự của tất cả loại tài nguyên và đòi hỏi mỗi quá trình trong thứ tự tăng của số lượng.

Gọi R = {R1, R2, …, Rm} là tập hợp loại tài nguyên. Chúng ta gán mỗi loại tài nguyên một số nguyên duy nhất, cho phép chúng ta so sánh hai tài nguyên và xác định tài nguyên này có đứng trước tài nguyên khác hay không trong thứ tự của chúng ta. Thông thường, chúng ta định nghĩa hàm ánh xạ một-một F: R  N, ở đây N là tập hợp các số tự nhiên. Thí dụ, nếu tập hợp các loại tài nguyên R gồm các ổ băng từ, ổ đĩa và máy in thì hàm F có thể được định nghĩa như sau:

F(ổ băng từ) = 1,

F(đĩa từ) = 5,

F(máy in) = 12.

Bây giờ chúng ta xem giao thức sau để ngăn chặn deadlock: mỗi quá trình có thể yêu cầu tài nguyên chỉ trong thứ tự tăng của số lượng. Nghĩa là, một quá trình ban đầu có thể yêu cầu bất cứ số lượng thể hiện của một loại tài nguyên Ri. Sau đó, một quá trình có thể yêu cầu các thể hiện của loại tài nguyên Rj nếu và chỉ nếu F(Rj) > F(Ri). Nếu một số thể hiện của cùng loại tài nguyên được yêu cầu, thì một yêu cầu cho tất cả thể hiện phải được cấp phát. Thí dụ, sử dụng hàm được định nghĩa trước đó, một quá trình muốn dùng ổ băng từ và máy in tại cùng một lúc trước tiên phải yêu cầu ổ băng từ và sau đó yêu cầu máy in.

Nói một cách khác, chúng ta yêu cầu rằng, bất cứ khi nào một quá trình yêu cầu một thể hiện của loại tài nguyên Rj, nó giải phóng bất cứ tài nguyên Ri sao cho F(Ri)  F(Rj).

Nếu có hai giao thức được dùng thì điều kiện tồn tại chu trình không thể xảy ra. Chúng ta có thể giải thích điều này bằng cách cho rằng tồn tại chu trình trong đồ thị cấp phát tài nguyên tồn tại. Gọi tập hợp các quá trình chứa tồn tại chu trình trong đồ thị cấp phát tài nguyên là {P0, P1, … , Pn}, ở đây Pi đang chờ một tài nguyên Ri, mà Ri được giữ bởi quá trình Pi+1. Vì sau đó quá trình Pi+1 đang giữ tài nguyên Ri trong khi yêu cầu tài nguyên Ri+1, nên chúng ta có F(Ri) < F(Ri+1) cho tất cả i. Nhưng điều kiện này có nghĩa là F(R0) < F(R1) < …< F(Rn) < F(R0). Bằng qui tắc bắt cầu F(R0) < F(R0), điều này là không thể. Do đó, không thể có chờ chu trình.

Chú ý rằng hàm F nên được định nghĩa dựa theo thứ tự tự nhiên của việc sử dụng tài nguyên trong hệ thống. Thí dụ, vì ổ băng từ thường được yêu cầu trước máy in nên có thể hợp lý để định nghĩa F( ổ băng từ) < F(máy in).

PhamQuocAnh02 (113A) đã viết:ví dụ : thông tin 8 bạn nữ chết đuối ở huyện mỹ đức hà nội. các bạn nữ này rơi xuống nước do hoảng loạn và kém bình tĩnh bạn này níu lấy bạn kia không ai chịu thả ra dẫn đến 8 bạn đều bị chết đuối ( xảy ra deallock)

Ví dụ ác!

Một tập hợp các tiến trình được định nghĩa ở trong tình trạng tắc nghẽn khi mỗi tiến trình trong tập hợp đều chờ đợii một sự kiện mà chỉ có một tiến trình khác trong tập hợp mới có thể phát sinh được.
Nói cách khác, mỗi tiến trình trong tập hợp đều chờ được cấp phát một tài nguyên hiện đang bị một tiến trình khác cũng ở trạng thái Blocked chiếm giữ. Như vậy không có tiến trình nào có thể tiếp tục xử lý, cũng như giải phóng tài nguyên cho các tiến trinh khác sử dụng, tất cả tiến trình trong tập hợp đều bị khóa vĩnh viễn.

Coffman, Elphick và shoshani đã đưa ra 4 điều kiện tắc nghẽn:
1. Có sử dụng tài nguyên không thể chia sẻ (Mutual exclusion): Mỗi thời điểm, một tài nguyên không thể chia sẻ được hệ thống cấp phát chỉ cho một tiến trình, khi tiến trình sử dụng xong tài nguyên này hệ thống mới thu hội và cấp phát tài nguyên cho tiến trình khác.
2. Sự chiếm giữ và yêu cầu thêm tài nguyên (Wait for): Các tiến trình tiếp tục chiếm giữ các tài nguyên đã cấp phát cho nó trong khi chờ được cấp phát thêm 1 số tài nguyên mới.
3. Không thu hồi tài nguyên từ tiến trình đang giữ chúng (No preeption): Tài nguyên không thể thu hồi từ tiến trình đang chiếm giữ chúng trước khi tiến trình này sử dụng chúng xong.
4. Tồn tại của một chu kỳ trong đồ thị cấp phát tài nguyên (Circular wait): có ít nhất hai tiến trình chờ đợi lẫn nhau: tiến trình này chờ đợi cấp phát tài nguyên đang bị tiến trình kia chiếm giữ và ngược lại

Khi có đủ 4 điều kiện này thì tắc nghẽn xảy ra. Nếu thiếu 1 trong 4 điều kiện trên thì không có tắc nghẽn.

Để tắc nghẽn không xảy ra thì ta cẩn đảm bảo tối thiểu 1 trong 4 điều kiện cần không xảy ra:

1. Tài nguyên không thể chia sẻ: Nhìn chung gần như không thể tránh được điều kiện này vì bản chất tài nguyên gần như cố định. Tuy nhiên đối với một số tài nguyên về kết xuất người ta có thể dùng các cơ chế spooling để biến đổi thành tài nguyên có thể chia sẻ
2. Sự chiếm giữ và yêu cầu thêm tài nguyên: Phải đảm bảo rằng mỗi khi tiến trình yêu cầu thêm 1 tài nguyên thì nó không chiếm giữ các tài nguyên khác.
3. Không thu hồi tài nguyên: cho phép hệ thống được thu hồi tài nguyên từ các tiến trình bị khóa và cấp phát trở lại cho tiến trình khi nó thoát khỏi tình trạng bị khóa. Tuy nhiên với một số loại tài nguyên việc thu hồi sẽ rất khó khăn vì vi phạm toàn sự toàn vẹn dữ liệu
4. Tồn tại 1 chu kỳ: Tránh tạo chu kỳ trong đồ thị bằng cách cấp phát tài nguyên theo 1 sự phân cấp như sau:
Gọi R={R1, R2, ..., Rn} là tập hợp các loại tài nguyên
Các loại tài nguyên được phân cấp từ 1->n
Ví dụ:
F(đĩa)=2, F(máy in) =12
Các tiến trình khi yêu cầu tài nguyên phải tuân thủ quy định khi tiến trình đang chiếm giữ tài nguyên Ri thì chỉ có thể yêu cầu các tài nguyên Rj nếu F(Rj)>F(Ri)

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.

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

Deadlock xảy ra khi có 4 điều kiện cần sau:

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

Chú ý: 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.

- Các 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 tài nguyên hệ thống này cấp phát cho các tiến trình theo yêu cầu.

- Tài nguyên cùng loại: Giả sử máy có 3 ổ băng từ và có 3 tiến trình đang chạy. Mỗi tiến trình đang giữ 1 ổ băng.

- Tài nguyên khác loại: Giả sử có 1 máy in, 1 ổ băng từ. Tiến trình P1 đang giữ ổ băng, P2 giữ máy in.

Nhiều cấu trúc dữ liệu phải được duy trì để cài đặt giải thuật Banker. Những cấu
trúc dữ liệu này mã hoá trạng thái của hệ thống cấp phát tài nguyên. Gọi n là số quá
trình trong hệ thống và m là số loại tài nguyên trong hệ thống. Chúng ta cần các cấu
trúc dữ liệu sau:
• Available: một vector có chiều dài m hiển thị số lượng tài nguyên sẳn dùng
của mỗi loại. Nếu Available[j]= k, có k thể hiện của loại tài nguyên Rj sẳn
dùng.
• Max: một ma trận n x m định nghĩa số lượng tối đa yêu cầu của mỗi quá
trình. Nếu Max[ i , j ] = k, thì quá trình Pi có thể yêu cầu nhiều nhất k thể
hiện của loại tài nguyên Rj.
• Allocation: một ma trận n x m định nghĩa số lượng tài nguyên của mỗi loại
hiện được cấp tới mỗi quá trình. Nếu Allocation[ i, j ] = k, thì quá trình Pi
hiện được cấp k thể hiện của loại tài nguyên Rj.
• Need: một ma trận n x m hiển thị yêu cầu tài nguyên còn lại của mỗi quá
trình. Nếu Need[ i, j ] = k, thì quá trình Pi có thể cần thêm k thể hiện của loại
tài nguyên Rj để hoàn thành tác vụ của nó. Chú ý rằng, Need[ i, j ] = Max[ i, j ] – Allocation [ i, j ].

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 >