Thảo luận Bài 8

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.

chauchanduong (I11C) đã viết:Trường hợp deadlock có thể phát sinh nếu bốn điều kiện sau xảy ra cùng một lúc trong hệ thống:

1)Loại trừ hỗ tương: ít nhất một tài nguyên phảiđược giữ trong chế độ không chia sẻ; nghĩa là, chỉ một quá trình tại cùng một thờiđiểm có thể sử dụng tài nguyên. Nếu một quá trình khác yêu cầu tài nguyênđó, quá trình yêu cầu phải tạm dừng chođến khi tài nguyên được giải phóng.

2)Giữ và chờ cấp thêm tài nguyên: quá trình phảiđang giữ ít nhất một tài nguyên vàđang chờ để nhận tài nguyên thêm mà hiệnđangđược giữ bởi quá trình khác.

3)Không đòi lại tài nguyên từ quá trình đang giữ chúng: Các tài nguyên không thể bị đòi lại; nghĩa là, tài nguyên có thể được giải phóng chỉ tự ý bởi quá trìnhđang giữ nó, sau khi quá trìnhđó hoàn thành tác vụ.
4)Tồn tại chu trình trong đồ thị cấp phát tài nguyên: một tập hợp các quá trình {P0, P1,…,Pn} đang chờ mà trong đó P0 đang chờ một tài nguyên được giữ bởi P1,P1 đang chờ tài nguyên đang giữ bởi P2,…,Pn-1 đang chờ tài nguyên đang được giữ bởi quá trình P0.

Chúng ta nhấn mạnh rằng tất cả bốn điều kiện phải cùng phát sinhđể deadlock xảy ra.Điều kiện chờ đợi chươ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.

Bổ sung thêm một ý nữa là :
Để ngăn chặn deadlock, chỉ cần phủ định một trong 4 điều kiện trên !

chipphonui đã viết:

DaoQuangSieu (I11C) đã viết:

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

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

cho mình bổ sung nha.
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.

mình thì có ý kiến thế này
Sự tắc nghẽn có thể tồn tại với ba điều kiện trên, nhưng cũng có thể không xảy ra chỉ với 3 điều kiện đó. Để chắc chắn tắc nghẽn xảy ra cần phải có điều kiện thứ tư Đợi vòng tròn (Circular wait).
Đây là trường hợp của 1 ví dụ mà bài 7 thầy chưa có nói đó là Các nhà hiền triết cùng ngồi 1 bàn tròn


mỗi tiến trình đang chiếm giữ tài nguyên mà tiến trình khác đang cần.
Ba điều kiện đầu là điều kiện cần chứ không phải là điều kiện đủ để xảy ra tắc nghẽn. Điều kiện thứ tư là kết quả tất yếu từ ba điều kiện đầu.
Các nhà hiền triết độc lập với nhau và trầm tư suy nghĩ.khi đói ,mỗi người nhấc đũa 2 bên và nếu dược cả đôi thì bắt đầu ăn,sau đó đặt từng chiếc đũa về vị trí cũ.Deadlkock xảy ra khi các hiền triết cùng 1 lúc nhấc đũa bên trái hoặc đũa bên phải cứ thế chờ nhau mà không ai dược ăn cả.đó là hiện tượng chờ xoay vòng

Bữa có nghe Thầy nói là Thầy có post bài về cách trình bày bài tập kiểm tra và bài thi sao cho hợp lý. Mọi người biết nó nằm ở chỗ nào không. Cám ơn trước.

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

TranQuyThanh (I11C) ơi bạn có thể cho mình vài ví dụ được không ạ. Vì mình thấy bạn trình bày lý thuyết không mình chưa hiểu lắm, mong bạn phản hồi. Cảm ơn nhìu

minhgiangbc đã viết:
mình thì có ý kiến thế này
Sự tắc nghẽn có thể tồn tại với ba điều kiện trên, nhưng cũng có thể không xảy ra chỉ với 3 điều kiện đó. Để chắc chắn tắc nghẽn xảy ra cần phải có điều kiện thứ tư Đợi vòng tròn (Circular wait).
Đây là trường hợp của 1 ví dụ mà bài 7 thầy chưa có nói đó là Các nhà hiền triết cùng ngồi 1 bàn tròn


mỗi tiến trình đang chiếm giữ tài nguyên mà tiến trình khác đang cần.
Ba điều kiện đầu là điều kiện cần chứ không phải là điều kiện đủ để xảy ra tắc nghẽn. Điều kiện thứ tư là kết quả tất yếu từ ba điều kiện đầu.
Các nhà hiền triết độc lập với nhau và trầm tư suy nghĩ.khi đói ,mỗi người nhấc đũa 2 bên và nếu dược cả đôi thì bắt đầu ăn,sau đó đặt từng chiếc đũa về vị trí cũ.Deadlkock xảy ra khi các hiền triết cùng 1 lúc nhấc đũa bên trái hoặc đũa bên phải cứ thế chờ nhau mà không ai dược ăn cả.đó là hiện tượng chờ xoay vòng

Bài viết và ví dụ của bạn đưa ra rất thực tế và phù hợp với nội dung của bài học, hy vọng sẽ tiếp tục nhận được những bài viết hay từ bạn. Thanks!

Deadlock
Tóm tắt nội dung :
1. Định nghĩa Deadlock? Cho các ví dụ?
2. Đặc điểm Deadlock?
3. Ngăn chặn Deadlock?
4. Tránh Deadlock?
5. Phát hiện Deadlock?
6. Phục hồi Deadlock?
-------------------------------
1. Định nghĩa Deadlock? Cho các ví dụ?
Trong môi trường đa nhiệm, nhiều tiến trình khác nhau có thể cùng cạnh tranh 1 tài nguyên. Khi một tiến trình đang chờ được cấp tài nguyên, mà tài nguyên đó đang được một tiến trình khác chiếm giữ, thì tiến trình đó đi vào trạng thái chờ và rất có thể sẽ không bao giờ chuyển trạng thái trở lại nếu không có sự tác động từ bên ngoài. Hiện tượng này được gọi là: Deadlock.
VD : 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 Deadlock.
2. Đặc điểm Deadlock?
Trong một hệ thống, 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ườ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 :
- Loại trừ tương hổ.
- Giữ và chờ cấp thêm tài nguyên.
- Không đòi lại tài nguyên từ quá trình đang giữ chúng.
- Tồn tại chu trình trong cấp phát tài nguyên.
Đồ thị cấp phát tài nguyên : Nếu đồ thị cấp phát tài nguyên không có chu trình thì 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 có trạng thái deadlock.
3. Ngăn chặn Deadlock?
Ngăn chặn deadlock bằng cách sao cho ít nhất 1 trong 4 điều kiện dẫn đến deadlock không xảy ra.
4. Tránh Deadlock.
Một phương pháp khác để tránh deadlock là yêu cầu thông tin bổ sung về cách
tài nguyên được yêu cầu.Với kiến thức về thứ tự hoàn thành của yêu cầu và giải phóng
cho mỗi quá trình, chúng ta có thể quyết định cho mỗi yêu cầu của quá trình sẽ chờ
hay không. Mỗi yêu cầu đòi hỏi hệ thống xem tài nguyên hiện có, tài nguyên hiện
được cấp tới 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,
để yêu cầu của quá trình hiện tại có thể được thoả mãn hay phải chờ để tránh khả năng
xảy ra deadlock. Trạng thái cấp phát tài nguyên được định nghĩa bởi số tài nguyên sẳn dùng
và tài nguyên được cấp phát và số yêu cầu tối đa của các quá trình.
5. Phát hiện Deadlock.
Nếu một hệ thống không thực hiện giải thuật ngăn chặn deadlock 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 phải
cung cấp:
• Giải thuật xem xét trạng thái của hệ thống để quyết định deadlock có xảy
ra hay không.
• Giải thuật phục hồi từ deadlock.
6. Phục hồi Deadlock.
Khi giải thuật phát hiện xác định rằng deadlock tồn tại, nhiều thay đổi tồn tại.
Một khả năng là thông báo người điều hành rằng deadlock xảy ra và để người điều
hành giải quyết deadlock bằng thủ công. Một khả năng khác là để hệ thống tự động
phục hồi. Có hai tuỳ chọn cho việc phá vỡ deadlock. Một giải pháp đơn giản là huỷ bỏ
một hay nhiều quá trình để phá vỡ việc tồn tại chu trình trong đồ thị cấp phát tài
nguyên. Tuỳ chọn thứ hai là lấy lại một số tài nguyên từ một hay nhiều quá trình bị
deadlock.

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!

vothihonggam đã viết:Tình huống kẹt của của một nhóm tiến trình do mỗi tiến trình trong nhóm đều chờ một sự kiện (event) có thể chỉ được gây ra bởi một tiến trình khác.

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

Một khái niệm khác về Deadlock
Trong môi trường đa nhiệm, nhiều tiến trình khác nhau có thể cùng cạnh tranh 1 tài nguyên. Khi một tiến trình đang chờ được cấp tài nguyên, mà tài nguyên đó đang được một tiến trình khác chiếm giữ, thì tiến trình đó đi vào trạng thái chờ và rất có thể sẽ không bao giờ chuyển trạng thái trở lại nếu không có sự tác động từ bên ngoài. Hiện tượng này được gọi là: Deadlock.

Hay nói 1 cách khác: Hiện tượng Deadlock bắt nguồn từ sự xung đột về tài nguyên của 2 hoặc nhiều tiến trình đang hoạt động đông thời trên hệ thống.

LaVanKhuong (I11C) đã viết:Định nghĩa: Tình huống bị kẹt của một nhóm tiến trình do mỗi tiến trình trong nhóm đều chờ một sự kiện(event) có thể chỉ được gây ra bởi một tiến trình khác.
ví dụ:
Có hai xe đi ngược chiều cùng qua 1 cây cầu hẹp, mà cầu thì chỉ có một làm xe nên khi hai xe vào đến giữa cầu thì không thể tiếp tục tiến đi được nữa xảy ra kẹt xe(deadlock) vì không người nào chịu nhường đường.

ví dụ về deadlock không liên quan đến môi trường máy tính:
1. Hai chiếc xe đi qua một cây cầu chỉ có 1 làn đường.

2. Một người đi xuống một cái thang, trong khi một người khác đang leo lên

3. Hai đoàn tàu đi trên cùng một tuyến đường.

4. Hai thợ mộc cùng phải đóng những cái đinh. Có một cây búa duy nhất và một thùng duy nhất chứa những cái đinh. Deadlock xảy ra nếu một người có búa và người khác có đinh.

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

• Loại bỏ điều kiện loại trừ tương hỗ:
  

Vì tại một thời điểm chỉ có 1 tiến trình được sử dụng tài nguyên, mà đây là tài nguyên không chia sẽ nên ta sẽ tăng số lượng tài nguyên lên. Giải pháp này thực tế là không khả thi.
Ví dụ: trong trường hợp ổ cứng bị đầy và chỉ còn đủ để cung cấp trong một tiến trình thì phương pháp này không thực hiện được
Cấp phát tài nguyên dạng ống.(spool)

• Loại bỏ điều kiện giữ và chờ (Hold and Wait):
  

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

• Loại bỏ Không tiếm quyền( No Preemption):
  

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

• Loại bỏ chờ xoay vòng( Circular Wait):
  

Có thể cấp số thứ tự cho mỗi tài nguyên, và mỗi tiến trình chỉ được yêu cầu tài nguyên theo thứ tự tăng dần


Các giải pháp trên đây đều không khả thi trong thực tế, có người cho rằng không cần học, nhưng có thể từ những giải pháp này, sẽ có giải pháp tốt hơn và hoàn thiện hơn được sáng tạo trong tương lai

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!

tannamthanh(I11C) đã viết:Phần lớn, chúng ta có thể giải quyết vấn đề deadlock theo một trong ba cách:
• Chúng ta có thể sử dụng một giao thức để ngăn chặn hay tránh deadlocks, đảm bảo rằng hệ thống sẽ không bao giờ đi vào trạng thái deadlock
• Chúng ta có thể cho phép hệ thống đi vào trạng thái deadlock, phát hiện nó và phục hồi.
• Chúng ta có thể bỏ qua hoàn toàn vấn đề này và giả vờ deadlock không bao giờ xảy ra trong hệ thống. Giải pháp này được dùng trong nhiều hệ điều hành, kể cả UNIX.
• Chúng ta sẽ tìm hiểu vắn tắt mỗi phương pháp. Sau đó, chúng ta sẽ trình bày các giải thuật một cách chi tiết trong các phần sau đây.
Để đảm bảo deadlock không bao giờ xảy ra, hệ thống có thể dùng kế hoạch ngăn chặn hay tránh deadlock. Ngăn chặn deadlock là một tập hợp các phương pháp để đảm bảo rằng ít nhất một điều kiện cần không thể xảy ra. 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.

ban ơi bạn cũng hiểu về deadlocks vậy bạn có thể trình bày ngăn chặn deadlocks bằng cách phủ định 4 điều kiện dẫn đến deaklocks ko?chứ cái bạn nói trên chung chung quá mình ko hiểu cho lắm.thank ban nha!

nguyenvulinh_i11c đã viết:- Trên RAG, lúc ð.u t.t c. nhu c.u v. tài nguyên c.a ti.n tr.nh ph.i ðý.c khai báo trý.c b.ng các Cung Nhu c.u (Claim edge) Pi • • •> Rj ch. báo r.ng Pi có th. s. yêu c.u Rj - Cung Nhu c.u Pi • • •> Rj ðý.c chuy.n thành Cung Yêu c.u (Request edge) Pi • • •> Rj khi Pi th.c s. b.t ð.u c.n ð.n Rj . - N.u yêu c.u Pi • • •> Rj ðý.c HÐH ðáp .ng, cung Pi • • •> Rj chuy.n thành Cung .n ð.nh (Assignment edge) Pi <• • • Rj n.i phiên b.n duy nh.t c.a Rj v.i Pi . - Khi HÐH xét yêu c.u Pi • • •>Rj. H. ch. c.p phát Rj cho Pi n.u Cung .n ð.nh Pi <• • • Rj không t.o ra v.ng tr.n ð.ng hý.ng trong RAG (xét c. các Cung Nhu c.u). - Thu.t gi.i có ð. ph.c t.p o(n²) v.i n là s. ti.n tr.nh trong h.. Ví d. trách deadlock dùng RAG: Ð.u tiên khai báo t.t c. các nhu c.u c.a P1 và P2:P1 và P2 có th. s. d.ng R1,R2.

hic đọc hok được gì hết bạn Linh ui. Bạn có thể post lại được không?
thanks bạn Linh!!!

Là thuật giải tránh Deadlock cho trường hợp mỗi loại tài nguyên có n phiên bản.
- Áp dụng cho hệ thống cấp phát tài nguyên trong đó mỗi loại tài nguyên có thể có nhiều instance.
- Mô phỏng nghiệp vụ ngân hàng (banking)
- Một số giả thiết
Mỗi process phải khai báo số lượng tối đa tài nguyên mỗi loại mà process đó cần để hoàn tất công việc.
Khi process yêu cầu một tài nguyên thì có thể phải đợi mặc dù tài nguyên được yêu cầu đang có sẵn
Khi process đã có được đầy đủ tài nguyên thì phải hoàn trả trong một khoản thời gian hữu hạn nào đó.

BuiHuuThanhLuan(I11C) đã viết:

• Loại bỏ điều kiện loại trừ tương hỗ:

Vì tại một thời điểm chỉ có 1 tiến trình được sử dụng tài nguyên, mà đây là tài nguyên không chia sẽ nên ta sẽ tăng số lượng tài nguyên lên.
Cấp phát tài nguyên dạng ống.(spool)

• Loại bỏ điều kiện giữ và chờ (Hold and Wait):

Do một tiến trình đang giữ tài nguyên và yêu câu một tài nguyên mới nên nguyên tắc để loại bỏ là: ến trình không được giữ tài nguyên khi yêu cầu tài nguyên mới. Khi cần, nó khai báo tài nguyên và đươc cấp phát một lần. Nếu nó yêu cầu thêm tài nguyên và không được thì phải trả cái tài nguyên mà nó đang giữ.

• Loại bỏ Không tiếm quyền( No Preemption):

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

• Loại bỏ chờ xoay vòng( Circular Wait):

Có thể cấp số thứ tự cho mỗi tài nguyên, và mỗi tiến trình chỉ được yêu cầu tài nguyên theo thứ tự tăng dần

Mình xin trình bày vấn đề ngăn chặn Deadlock theo cách khác như sau:
Ngăn chặn deadlock : là đảm bảo ít nhất một trong bốn điều kiện không thể xuất hiện
a.Ngăn cản lẫn nhau – đảm bảo là hệ thống không có các file không thể chia sẻ.
Một tiến trình không bao giờ phải chờ tài nguyên có thể chia sẻ
Ví dụ: read-only files(vì file read only thì nhiều tiến trình truy xuất nó cũng không ảnh hưởng gì-nội dung file không thay đổi)
Một số tài nguyên là không thể chia sẻ
Ví dụ: chế độ toàn màn hình


b.Giữ và đợi cấp thêm tài nguyên – phải đảm bảo rằng mỗi khi một tiến trình yêu cầu một tài nguyên, nó không giữ bất kỳ tài nguyên nào khác.
Đòi hỏi tiến trình yêu cầu và được phân phối tất cả các tài nguyên của nó trước khi nó bắt đầu thực hiện, hoặc chỉ cho phép tiến trình yêu cầu các tài nguyên khi không có tài nguyên nào cả.


c.Không có ưu tiên: không đòi lại tài nguyên từ tiến trình đang giữ chúng_
Nếu một tiến 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 thể được phân phối ngay cho nó thì tất cả các tài nguyên nó đang giữ được giải phóng.
Các tài nguyên ưu tiên được thêm vào danh sách tài nguyên dành cho tiến trình đang chờ đợi.
Tiến trình sẽ được khởi động lại chỉ khi nó có thể lấy lại các 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.


d.Chờ đợi vòng tròn – áp dụng một thứ tự tuyệt đối cho tất cả các loại tài nguyên: mỗi loại được gắn một số nguyên
Mỗi tiến trình yêu cầu các tài nguyên theo thứ tự tăng dần: chỉ có thể nhận được tài nguyên có trọng số cao hơn của bất kỳ tài nguyên nào nó đang giữ
Muốn có tài nguyên j, tiến trình phải giải phóng tất cả các tài nguyên có trọng số i > j (nếu có)

_Nếu đồ thị không chu trình ko xảy ra deadlock.
_______Nếu đồ thị có chu trình
__________Nếu mỗi loại tài nguyên chỉ một cá thể thì chắc chắn xảy ra deadlock.
__________Nếu mỗi loại tài nguyên có một vài cá thể thì deadlock có thể xảy ra hoặc không

tranvantoan83(I11c) đã viết:
_Nếu đồ thị không chu trình ko xảy ra deadlock.
_______Nếu đồ thị có chu trình
__________Nếu mỗi loại tài nguyên chỉ một cá thể thì chắc chắn xảy ra deadlock.
__________Nếu mỗi loại tài nguyên có một vài cá thể thì deadlock có thể xảy ra hoặc không

Bạn có thể giải thích rõ hơn về mô hình này được không? Cám ơn bạn.

dangminhthinh2107 đã viết:Mình tìm trên mạng và có đoạn code về Deadlock này nếu bạn nào có thời gian thì tìm hiểu về nó nhé

Code:


#include<stdio.h>
#include<stdlib.h>

int main()
    {
    int num_p,num_re;
    int all[10] [10],re[10],av[10],cl[10][ 10],used[ 10];
    int more[10];
    int i=0;
    int ap,ar;
    int cp,cr;
    int j=0;
    int pi,ci;
    printf("\nNhap so tien trinh : ");
    scanf("%d",&num_p) ;
    printf("\nNhap so tai nguyen : ");
    scanf("%d",&num_re);
    printf("\nNhap gia tri toi da cua moi tai nguyen : \n\n");
    for(i=0;i<num_re;i++)
        {
        printf("R[%d] = ",i+1);
        scanf("%d",&re[i]) ;
        }

    //Allocation
    printf("\n");
    for(ap=0;ap<num_p;ap++)
        {
        printf("Nhap so tai nguyen da cap phat cho tien trinh %d : ",ap+1);
        for(ar=0;ar<num_re;ar++)
        scanf("%d",&all[ar][ap]);
        }

    //claim matrix
    printf("\n");
    for(cp=0;cp<num_p;cp++)
        {
        printf("Nhap so tai nguyen yeu cau cua tien trinh %d : ",cp+1);
        for(cr=0;cr<num_re;cr++)
        scanf("%d",&cl[cr][cp] );
        }

    //Used & Available
    for(i=0;i<num_re;i++)
        {
        used[i]=0;
        for(j=0;j<num_p;j++)
        used[i]=used[i]+all[i] [j];
        av[i]=re[i]-used[ i];
        }

    //check deadlock
    for(pi=0;pi<num_p;pi++)
        {
        int check=0;
        for(ci=0;ci<num_re;ci++)
            {
            more[ci]=cl[ci][pi]- all[ci][pi];
            if(more[ci] <= av[ci])
            check++;
            }
        if(check==num_re)
        goto l1;
        }
    printf("\n\t\t!! XAY RA DEADLOCK !!\n\n");
    getch();
    return 0;

    l1:
    printf("\n\t\t!! SAFE !!\n\n");
    getch();
    return 0;
    }


Đoạn code trên có nghĩa là nếu tất cả tiến trình "cl" đều yêu cầu tài nguyên nhiều hơn giới hạn thì sảy ra deadlocks
thanks

Ui bạn làm sao mà có thể post lên đoạn code có scroll vậy. Rất hay!
Hihi

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

Mình nói rõ hơn 1 xíu về Deadlock
Đ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.

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.

Ví dụ về deadlock ở đời thường
Ngày nào mình đi học cũng bị deadlock hết , ngay ngã 3 cầu chữ y,kẹt xe mà không ai chịu nhường ai, nhất là mấy chiêc xe bus . Có lần phải đến 30' mới hết deadlock được ( mặc dù đã có các anh giao thông )

Bốn điều kiện cần (necessary condition) để xảy ra deadlock:
1.Mutual exclusion: ít nhất một tài nguyên được giữ theo nonsharable mode (ví dụ: printer; ví dụ sharable resource: read-only files).
2.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.No preemption: (= no resource 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 khi nó muốn..
4.Circular wait: tồn tại một tập {P0,…,Pn} các quá trình đang đợi sao cho
P0 đợi một tài nguyên mà P1 đang giữ
P1 đợi một tài nguyên mà P2 đang giữ
…
Pn đợi một tài nguyên mà P0 đang giữ