Thảo luận Bài 8

Các phương pháp giải quyết deadlock

•Ba phương pháp

•1) Bảo đảm rằng hệ thống không rơi vào tình trạng deadlock bằng cách ngăn (preventing) hoặc tránh (avoiding) deadlock.

•Khác biệt

–Ngăn deadlock: không cho phép (ít nhất) một trong 4 điều kiện cần cho deadlock

–Tránh deadlock: các quá trình cần cung cấp thông tin về tài nguyên nó cần để hệ thống cấp phát tài nguyên một cách thích hợp

•2) Cho phép hệ thống vào trạng thái deadlock, nhưng sau đó phát hiện deadlock và phục hồi hệ thống.

•3) Bỏ qua mọi vấn đề, xem như deadlock không bao giờ xảy ra trong hệ thống.

Khá nhiều hệ điều hành sử dụng phương pháp này.

–Deadlock không được phát hiện, dẫn đến việc giảm hiệu suất của hệ thống. Cuối cùng, hệ thống có thể ngưng hoạt động và phải được khởi động lại.

=========
Ngăn deadlock bằng cách ngăn một trong 4 điều kiện cần của deadlock

1.Ngăn mutual exclusion

–đối với nonsharable resource (vd: printer): không làm được

–đối với sharable resource (vd: read-only file): không cần thiết

2.Ngăn Hold and Wait

–Cách 1: mỗi process yêu cầu toàn bộ tài nguyên cần thiết một lần. Nếu có đủ tài nguyên thì hệ thống sẽ cấp phát, nếu không đủ tài nguyên thì process phải bị blocked.

–Cách 2: khi yêu cầu tài nguyên, process không được giữ bất kỳ tài nguyên nào. Nếu đang có thì phải trả lại trước khi yêu cầu.

–Ví dụ để so sánh hai cách trên: một quá trình copy dữ liệu từ tape drive sang disk file, sắp xếp disk file, rồi in kết quả ra printer.

–Khuyết điểm của các cách trên:

§Hiệu suất sử dụng tài nguyên (resource utilization) thấp

§Quá trình có thể bị starvation

3.Ngăn No Preemption:

nếu process A có giữ tài nguyên và đang yêu cầu tài nguyên khác nhưng tài nguyên này chưa cấp phát ngay được thì

–Cách 1: Hệ thống lấy lại mọi tài nguyên mà A đang giữ

§A chỉ bắt đầu lại được khi có được các tài nguyên đã bị lấy lại cùng với tài nguyên đang yêu cầu

–Cách 2: Hệ thống sẽ xem tài nguyên mà A yêu cầu

§Nếu tài nguyên được giữ bởi một process khác đang đợi thêm tài nguyên, tài nguyên này được hệ thống lấy lại và cấp phát cho A.

§Nếu tài nguyên được giữ bởi process không đợi tài nguyên, A phải đợi và tài nguyên của A bị lấy lại. Tuy nhiên hệ thống chỉ lấy lại các tài nguyên mà process khác yêu cầu

4.Ngăn Circular Wait:

tập các loại tài nguyên trong hệ thống được gán một thứ tự hoàn toàn.

–Ví dụ: F(tape drive) = 1, F(disk drive) = 5, F(printer) = 12

§F là hàm định nghĩa thứ tự trên tập các loại tài nguyên.

Các cách ngăn Circular Wait

–Cách 1: mỗi process chỉ có thể yêu cầu thực thể của một loại tài nguyên theo thứ tự tăng dần (định nghĩa bởi hàm F) của loại tài nguyên. Ví dụ

§Chuỗi yêu cầu thực thể hợp lệ: tape drive ® disk drive ® printer

§Chuỗi yêu cầu thực thể không hợp lệ: disk drive ® tape drive

–Cách 2: Khi một process yêu cầu một thực thể của loại tài nguyên Rj thì nó phải trả lại các tài nguyên Ri với F(Ri) > F(Rj).

–“Chứng minh” cho cách 1: phản chứng

§F(R4) < F(R1)

§F(R1) < F(R2)

§F(R2) < F(R3)

§F(R3) < F(R4)

•Vậy F(R4) < F(R4), mâu thuẩn!

Tất cả hiện tượng tắc nghẽn đều bắt nguồn từ sự xung đột về tài nguyên của hai hoặc nhiều tiến trình đang hoạt động đồng thời trên hệ thống. Tài nguyên ở đây có thể là một ổ đĩa, một record trong cơ sở dữ liệu, hay một không gian địa chỉ trên bộ nhớ chính. Sau đây là một số ví dụ để minh hoạ cho điều trên.

Ví dụ 1: Giả sử có hai tiến trình P1 và P2 hoạt động đồng thời trong hệ thống. Tiến trình P1 đang giữ tài nguyên R1 và xin được cấp R2 để tiếp tục hoạt động, trong khi đó tiến trình P2 đang giữ tài nguyên R2 và xin được cấp R1 để tiếp tục hoạt động. Trong trường hợp này cả P1 và P2 sẽ không tiếp tục hoạt động được. Như vậy P1 và P2 rơi vào trạng thái tắc nghẽn. Ví dụ này có thể được minh hoạ bởi sơ đồ ở hình 2.

Tắc nghẽn thường xảy ra do xung đột về tài nguyên thuộc loại không phân chia được, một số ít trường hợp xảy ra với tài nguyên phân chia được. Ví dụ sau đây là trường hợp tắc nghẽn do xung đột về tài nguyên bộ nhớ, là tài nguyên thuộc loại phân chia được.

Ví dụ 2: Trong các ứng dụng cơ sở dữ liệu, một chương trình có thể khoá một vài record mà nó sử dụng, để dành quyền điều khiển về cho nó. Nếu tiến trình P1 khoá record R1, tiến trình P2 khoá record R2, và rồi sau đó mỗi tiến trình lại cố gắng khoá record của một tiến trình khác. Tắc nghẽn sẽ xảy ra.

Như vậy tắc nghẽn là hiện tượng: Trong hệ thống xuất hiện một tập các tiến trình, mà mỗi tiến trình trong tập này đều chờ được cấp tài nguyên, mà tài nguyên đó đang được một tiến trình trong tập này chiếm giữ. Và sự đợi này có thể kéo dài vô hạn nếu không có sự tác động từ bên ngoài.

Trong trường hợp của ví dụ 1 ở trên: hai tiến trình P1 và P2 sẽ rơi vào trạng thái tắc nghẽn, nếu không có sự can thiệp của hệ điều hành. Để phá bỏ tắc nghẽn này hệ điều hành có thể cho tạm dừng tiến trình P1 để thu hồi lại tài nguyên R1, lấy R1 cấp cho tiến trình P2 để P2 hoạt động và kết thúc, sau đó thu hồi cả R1 và R2 từ tiến trình P2 để cấp cho P1 và tái kích hoạt P1 để P1 hoạt động trở lại. Như vậy sau một khoảng thời gian cả P1 và P2 đều ra khỏi tình trạng tắc nghẽn.

Khi hệ thống xảy ra tắc nghẽn nếu hệ điều hành không kịp thời phá bỏ tắc nghẽn thì hệ thống có thể rơi vào tình trạng treo toàn bộ hệ thống. Như trong trường hợp tắc nghẽn ở ví dụ 1, nếu sau đó có tiến trình P3, đang giữ tài nguyên R3, cần R2 để tiếp tục thì P3 cũng sẽ rơi vào tập tiến trình bị tắc nghẽn, rồi sau đó nếu có tiến trình P4 cần tài nguyên R1 và R3 để tiếp tục thì P4 cũng rơi vào tập các tiến trình bị tắc nghẽn như P3, … cứ thế dần dần có thể dẫn đến một thời điểm tất cả các tiến trình trong hệ thống đều rơi vào tập tiến trình tắc nghẽn. Và như vậy hệ thống sẽ bị treo hoàn toàn.

1.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.
2.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.
3.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.

08H1010052 đã viết:

BuiHuuThanhLuan(I11C) đã viết:

08H1010052 đã viết:

TranQuyThanh (I11C) đã viết: Một hệ thống có 3 loại tài nguyên và 3 tiến trình với trạng thái cấp phát như sau:

Loại tài nguyên	Số phiên bản	Được các tiến trình yêu cầu	Đã cấp cho các tiến trình
Máy in kim	2	P1	P2, P3
Máy in laser	1		P3
Ổ băng từ	2	P2	P1, P3

Mình xin vẽ đồ thị bài này như sau:

=> Không xảy ra deadlock trong đồ thị trên mặc dù xảy ra chu trình giữa 2 tiến trình P2 và P1. Lý do là vì tiến trình P3 sẽ giải phóng tài nguyên trả lại cho máy in kim và ổ băng từ khi kết thúc tiến trình của nó. Từ đó chu trình P1 và P2 sẽ bị phá vỡ và tránh được deadlock.
Mong các bạn góp ý nhé.
Thân chào các bạn!

Đồ thị bạn vẽ và giải thích đúng rồi. cảm ơn bạn nhé
Thêm ý nữa là mình thấy tài nguyên trong chu trình có 2 phiên bản nên không có Deadlock

Ừm đúng rồi, cám ơn bạn ThanhLuan bổ sung.
Thân chào!

Đồ thị vẽ đẹp chú thích rõ, cám ơn bạn.

Để 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.
1 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ẻ.
2 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.
3 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ừ.
4 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).

Đang giữ Max Available
P1 1 2 1
P2 1 2
Need
P1 1
P2 1
work >= needi Pi Allocation
1 1 P1 1
2 1 P2 1
Chuỗi trạng thái an toàn = {P1,P2}
Yêu cầu này thỏa điều kiện :
1.Request2 =< Need2 vì 1=<1
2.Request2 =< Available vì 1 =< 1
Trạng thái mới :
Đang giữ Need Hệ có
P1 1 1 1
P2 1 0

work >= needi Pi Allocation
1 1 P1 1
2 0 P2 1
Chuỗi trạng thái an toàn Ti = {P1,P2}

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

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

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

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

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

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

Bài tập: hệ thống có 12 ổ băng và 3 tiến trình
dùng thuật giải nhà băng chứng minh trạng thái này an toàn

tiến trình		Được cấp(ổ đĩa)		tối đa cần(ổ đĩa)
P1		5		10
P2		2		4
P3		2		9

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

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

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

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

DuongTrungTinh(I11C) đã viết:

08H1010052 đã viết:

BuiHuuThanhLuan(I11C) đã viết:

08H1010052 đã viết:

TranQuyThanh (I11C) đã viết: Một hệ thống có 3 loại tài nguyên và 3 tiến trình với trạng thái cấp phát như sau:

Loại tài nguyên	Số phiên bản	Được các tiến trình yêu cầu	Đã cấp cho các tiến trình
Máy in kim	2	P1	P2, P3
Máy in laser	1		P3
Ổ băng từ	2	P2	P1, P3

Mình xin vẽ đồ thị bài này như sau:

=> Không xảy ra deadlock trong đồ thị trên mặc dù xảy ra chu trình giữa 2 tiến trình P2 và P1. Lý do là vì tiến trình P3 sẽ giải phóng tài nguyên trả lại cho máy in kim và ổ băng từ khi kết thúc tiến trình của nó. Từ đó chu trình P1 và P2 sẽ bị phá vỡ và tránh được deadlock.
Mong các bạn góp ý nhé.
Thân chào các bạn!

Đồ thị bạn vẽ và giải thích đúng rồi. cảm ơn bạn nhé
Thêm ý nữa là mình thấy tài nguyên trong chu trình có 2 phiên bản nên không có Deadlock

Ừm đúng rồi, cám ơn bạn ThanhLuan bổ sung.
Thân chào!

Đồ thị vẽ đẹp chú thích rõ, cám ơn bạn.

hay bài viết bạn dể hiểu, thanks bạn

_ Thế nào là trạng thái an toàn của hệ thống?
Một trạng thái được gọi là an toàn “safe” nếu tồn tại ít nhất một cách mà trong một khoảng thời gian hữu hạn nào đó, hệ thống có thể cấp phát tài nguyên thỏa mãn cho tất cả process thực thi hoàn tất .
Khi đó hệ thống tồn tại một Chuỗi an toàn {P1, P2, … , Pn } bao gồm tất cả các tiến trình sao cho với mỗi Pi, các tài nguyên mà nó yêu cầu có thể được đáp ứng bởi số lượng hiện có cộng thêm của tất cả các Pj mà j < i.
Nếu các TN yêu cầu không có đủ, Pi phải chờ cho đến khi tất cả các Pj trả lại các TN mà chúng chiếm giữ.
Khi Pi nhận được đủ TN cần thiết, nó sử dụng và trả lại HĐH để Pi+1 có thể vận hành, cứ như thế cho đến Pn
Khi một process yêu cầu một tài nguyên đang sẵn có, hệ thống sẽ kiểm tra: nếu việc cấp phát này không dẫn đến tình trạng unsafe thì sẽ cấp phát ngay.

_ Trình bày 4 cách ngăn chặn Deadlock.
Để ngăn chặn Deadlock ta phải làm sao cho ít nhất 1 trong 4 điều kiện dẫn đến Deadlock không xảy ra. Cụ thể:
- Với Mutual Exclusion: Đảm bảo TN(tai nguyên) nào cũng dùng chung được cùng một lúc bởi nhiều tiến trình.
- Với Hold and Wait:
a/ Khi TT yêu cầu TN, nó không được giữ 1 TN nào khác.
b/ 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:
a/ 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.
b/ 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.

Đề 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) kô >= (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) 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)

Kết Luận : Tại thời điểm P1 y/cầu mới là (1,0,2) thì hệ thống sẽ rơi vào trạng thái kô an toàn nếu đáp ứng y/cầu của P1, vì vậy sẽ nên đáp ứng y/cầu của P1 để đảm bảo hệ thống vẫn an toàn.
=========
Bài này giải theo ý của mình hiểu nên có chỗ nào sai thì xin chỉ giáo nha các bạn.

Duongthithanhhuynh (I11C) đã viết:Bài tập: hệ thống có 12 ổ băng và 3 tiến trình
dùng thuật giải nhà băng chứng minh trạng thái này an toàn

tiến trình		Được cấp(ổ đĩa)		tối đa cần(ổ đĩa)
P1		5		10
P2		2		4
P3		2		9

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

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

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

Tương tự như vậy sau khi tính toán thì bài toán này chỉ có 1 chuỗi an toàn duy nhất tại thời điểm T0 thôi nhỉ.

Đề bài: Một hệ thống có 5 tiến trình với tình trạng tài nguyên như sau:
Dùng giải thuật nhà băng để xác định:
a. Nội dung ma trận Need.
b. Trạng thái này có an toàn không.
c. Nếu P1 nêu yêu cầu (0, 4, 2, 0) có thể đáp ứng ngay được không.
Giải:
a. Xét tại thời điểm T0 mà 5 tiến trình được cấp phát như đề bài ta có:
Need[i] = Max[i] -Allocation[i].
b. Tìm chuỗi an toàn.
Thời điểm T0 tồn tại chuổi an toàn {P0, P2, P3, P4, P1}. Vậy hệ thống tại thời điểm T0 đạt trạng thái an toàn.
c. Ta thấy, yêu cầu thêm(0, 4, 2, 0) của P1 thỏa điều kiện Request1<= Need1 và thỏa điều kiện Request1 < Available. Giả sử ta cấp phát theo yêu cầu của P1 thì vẫn tồn tại chuỗi an toàn. Do vậy hoàn toàn có thể cấp phát thêm {0, 4, 2, 0} cho P1 được vì thỏa các điều kiện.

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

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

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

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

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

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

Tìm chuỗi an toàn khác:
Work >= Need(i) P(i) Allocation(i)
0 0 P2 2
2 2 P1 0
2 1 P3 1
=>Tồn tại chuỗi an toàn= {P2,P1,P3}. Vậy trạng thái hệ thống ở thời điểm Ti là an toàn.

Đồ thị cấp phát tài nguyên là một đồ thị có hướng, đồ thị có hai loại nút V và tập cung E, Trong đó tập nút V chia ra làm hai loại: tập hợp các tiến trình đang vận hành P ={P1,P2,...,Pn}, tập hợp các tài nguyên có trong hệ thống gọi là R= {R1,R2,...,Rn} mổi loại Ri có từ 1 đến nhiều phiên bản. Tập cung E bao gồm cung yêu cầu (Pi ->Ri), cung ấn định (Ri->Pi).

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

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

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

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

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

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

Thanks bạn, giờ thì mình đã hiểu

câu a:
Allocation=(1,1), Max=(2,2);
Available=3-(1+1)=1;
Ta có: Need(i)=Max(i)-Allocation(i)
=> p1=(2-1)=1; p2=(2-1)=1;
Work >= Need(i) P(i) Allocation
1 1 p1 1
2 1 p2 1
. Tồn tại chuỗi an toàn=<p1,p2>.
Vậy trạng thái hệ thống ở thời điểm Ti là an toàn.
câu b:
Request(2)<=Need(2) vì 1<=1
Request(2)<=Available vì 1<=1
Trạng thái mới:
Allocation(1,1+1)(vì thêm 1 máy nữa nên cộng thêm 1)
Available=3-(1+1+1)=0
Need(i):
p1 1
p2 0
Work >= Need(i) P(i) Allocation
0 0 p2 2
2 1 p1 1
Tồn tại trạng thái an toàn=<p2,p1>
Vậy trạng thái hệ thống ở thời điểm Ti là an toàn.

Các bạn có thể góp ý xem mình giải đúng chưa nhe!!!

giải thích đồ thị:
trong đồ đị hiện có hai tài nguyên R1 & R2 ta cho trong hai tài nguyên đó R1 có hai phiên bản là máy in HP1, HP2. R2 cũng có hai phiên bản là Canon1, Canon2
giả sử tại thời điểm lúc 6h
- Cung yêu cầu từ P1 -> R1: Thể hiện tiến trình (TT) P1 yêu cầu R1 cấp cho một phiên bản.
- Tài nguyên (TN) R1 đã cấp cho P2 một phiên bản (một máy in) nghĩa là tại thời điểm này P2 được cấp phát một máy in hoặc được sở hữu một máy in HP.
- TN R1 cũng đã cấp phát cho TT P3 một máy in HP.
- Đồng thời lúc này P3 yêu cầu R2 cấp cho mình một phiên bản Canon
- R2 đã cấp phát cho TT P1 một phiên bản máy in Canon
Ta nhìn thấy đồ thị lúc này có chu trình các mũi tên đuổi nhau hiện tượng chờ xoay vòng (Circular Wait) đây là dấu hiệu của deadlock (vòng tròn). P1 đang chờ tài nguyên R1 cấp một máy in HP nhưng TN của R1 đang được P2 & P3 giữ.
giã sử tại thời điểm 6h5p
- Lúc 6h R1 & R2 cấp TN (máy in HP & Canon) cho hai TT P2 & P4 ( hai TT này nằm ngoài chu trình) nhưng tại thời điểm 6h5p hai TT P2 & P4 đã làm việc xong nên TN được trả lại.
- TN được trả lại sẻ được cấp phát cho P1 & P3 yêu cầu
Tại thời điểm này sẻ không xảy ra hiện tượng deadlock.
Những lý giải này là theo cách nghĩ của mình có gì không đúng mong các bạn bổ xung thêm.

Bạn nào hiểu thuật giải nhà băng giúp mình giải thích và giải bài toán này. Theo đề bên trên.
Cảm ơn các bạn đã giúp mình.

NgoDucTuan (I11C) đã viết:
Bạn nào hiểu thuật giải nhà băng giúp mình giải thích và giải bài toán này. Theo đề bên trên.
Cảm ơn các bạn đã giúp mình.

Hi bạn, mình sẽ giải theo những gì mình hiểu nhé. nếu sai thì cùng nhau sửa và học hỏi lẫn nhau nhé
a) Buớc 1 : Phải đi tính Need = MAX - Allocation

TT		Need
		ABCD
P0		0000
P1		0750
P2		1002
P3		0020
P4		0642

Bước 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.

b) Giả sử P1 có y/cầu mới = (0,4,3,0)
Dựa vào y/cầu mới của P1 ta có thể khẳng định không nên đáp ứng y/cầu của P1 lý do:
vì không đáp ứng điều kiện Request1 <= Available <==> (0,4,3,0) kô <= (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)
===========
Xin mọi người chỉ giáo thêm.

dangminhthinh2107 đã viết:



giải thích đồ thị:
trong đồ đị hiện có hai tài nguyên R1 & R2 ta cho trong hai tài nguyên đó R1 có hai phiên bản là máy in HP1, HP2. R2 cũng có hai phiên bản là Canon1, Canon2
giả sử tại thời điểm lúc 6h
- Cung yêu cầu từ P1 -> R1: Thể hiện tiến trình (TT) P1 yêu cầu R1 cấp cho một phiên bản.
- Tài nguyên (TN) R1 đã cấp cho P2 một phiên bản (một máy in) nghĩa là tại thời điểm này P2 được cấp phát một máy in hoặc được sở hữu một máy in HP.
- TN R1 cũng đã cấp phát cho TT P3 một máy in HP.
- Đồng thời lúc này P3 yêu cầu R2 cấp cho mình một phiên bản Canon
- R2 đã cấp phát cho TT P1 một phiên bản máy in Canon
Ta nhìn thấy đồ thị lúc này có chu trình các mũi tên đuổi nhau hiện tượng chờ xoay vòng (Circular Wait) đây là dấu hiệu của deadlock (vòng tròn). P1 đang chờ tài nguyên R1 cấp một máy in HP nhưng TN của R1 đang được P2 & P3 giữ.
giã sử tại thời điểm 6h5p
- Lúc 6h R1 & R2 cấp TN (máy in HP & Canon) cho hai TT P2 & P4 ( hai TT này nằm ngoài chu trình) nhưng tại thời điểm 6h5p hai TT P2 & P4 đã làm việc xong nên TN được trả lại.
- TN được trả lại sẻ được cấp phát cho P1 & P3 yêu cầu
Tại thời điểm này sẻ không xảy ra hiện tượng deadlock.
Những lý giải này là theo cách nghĩ của mình có gì không đúng mong các bạn bổ xung thêm.

Theo ý mình thì lúc 6h5p bạn cũng nên vẽ lại sơ đồ để nó kô còn có vẻ chu trình nữa nhỉ.

LaVanKhuong (I11C) đã viết:câu a:
Allocation=(1,1), Max=(2,2);
Available=3-(1+1)=1;
Ta có: Need(i)=Max(i)-Allocation(i)
=> p1=(2-1)=1; p2=(2-1)=1;
Work >= Need(i) P(i) Allocation
1 1 p1 1
2 1 p2 1
. Tồn tại chuỗi an toàn=<p1,p2>.
Vậy trạng thái hệ thống ở thời điểm Ti là an toàn.
câu b:
Request(2)<=Need(2) vì 1<=1
Request(2)<=Available vì 1<=1
Trạng thái mới:
Allocation(1,1+1)(vì thêm 1 máy nữa nên cộng thêm 1)
Available=3-(1+1+1)=0
Need(i):
p1 1
p2 0
Work >= Need(i) P(i) Allocation
0 0 p2 2
2 1 p1 1
Tồn tại trạng thái an toàn=<p2,p1>
Vậy trạng thái hệ thống ở thời điểm Ti là an toàn.

Các bạn có thể góp ý xem mình giải đúng chưa nhe!!!

Thanks ban
Mình xin bổ xung thêm câu a nếu chứng minh đủ ra thì nó có hai trạng thái an toàn
{P2,P1} & {P1, P2} vì hai Need đều là (1,1) & Allocation (1,1)

Duongthithanhhuynh (I11C) đã viết:Bài tập: hệ thống có 12 ổ băng và 3 tiến trình
dùng thuật giải nhà băng chứng minh trạng thái này an toàn

tiến trình		Được cấp(ổ đĩa)		tối đa cần(ổ đĩa)
P1		5		10
P2		2		4
P3		2		9

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

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

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

mình ko hiểu lắm.có ai làm rõ hơn ko

doanhongdao030(I11C) đã viết:

Duongthithanhhuynh (I11C) đã viết:Bài tập: hệ thống có 12 ổ băng và 3 tiến trình
dùng thuật giải nhà băng chứng minh trạng thái này an toàn

tiến trình		Được cấp(ổ đĩa)		tối đa cần(ổ đĩa)
P1		5		10
P2		2		4
P3		2		9

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

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

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

mình ko hiểu lắm.có ai làm rõ hơn ko

So sánh với vd đầu tiên trong tài liệu, ở vd đầu có 5 tiến trình và 3 tài nguyên A (10 phiên bản), B (5 phiên bản),C (7 phiên bản). còn bài tập này thì 1 hệ thống có 12 ổ băng và 3 tiến trình ta có thể hiểu tương đương vd đầu là 1 hệ thống ~ 1 tài nguyên, 12 ổ băng ~ 12 phiên bản, và cứ tìm available, ma trận need và giải bình thường như vd đầu trong tài liệu.