Thảo luận Bài 8

MaiXuanSon (I22B) đã viết:

Tình huống sau đây có được gọi là Deadlock không?
Một máy tính đang hoạt động bình thường, người sử dụng mở 1 lúc nhiều chương trình quá máy tính xử lý không kịp, người sử dụng cứ thế là click và click chuột liên tục làm máy tính bị đứng luôn. Chỉ còn cách reset lại máy tính thì mới sử dụng lại được.

Nhờ Thầy và các bạn giúp đỡ. Thanks

Mình nghĩ đây cũng được gọi là Deadlock đó bạn.

Các phương pháp xử lý tắc nghẽn và ngăn chặn tắc nghẽn
* Các phương pháp xử lý tắc nghẽn
+ Sử dụng một thuật toán cấp phát tài nguyên nào đó mà bảo đảm không bao giờ xảy ra tắc nghẽn. + Hoặc cho phép xảy ra tắc nghẽn và tìm cách sữa chữa tắc nghẽn.
+ Hoặc bỏ qua việc xử lý tắc nghẽn, xem như hệ thống không bao giờ xảy ra tắc nghẽn. Thường áp dụng phương pháp này khi hệ thống rất ít khi bị tắc nghẽn và chi phí kiểm tra tắc nghẽn cao (UNIX và WINDOWS sử dụng phương pháp này)

* Ngăn chặn tắc nghẽn
Để không xảy ra tắc nghẽn, cần bảo đảm tối thiểu một trong 4 điều kiện đã nêu ở trên không xảy
ra:
+ Điều kiện 1 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.
+ Để điều kiện 2 không xảy ra, thì có thể áp dụng một trong hai nguyên tắc sau :
- Tiến trình phải yêu cầu tất cả các tài nguyên cần thiết trước khi cho bắt đầu xử lý. Phương pháp
này gặp khó khăn là hệ điều hành khó có thể biết trước các tài nguyên tiến trình cần sử dụng vì
nhu cầu tài nguyên còn phụ thuộc vào quá trình tiến trình thực hiện. Ngoài ra nếu cho tiến trình
chiếm giữ sẵn các tài nguyên chưa cần sử dụng ngay thì việc sử dụng tài nguyên sẽ kém hiệu quả.
- Khi tiến trình yêu cầu một tài nguyên mới và bị từ chối, nó phải giải phóng các tài nguyên đang chiếm giữ , sau đó lại được cấp phát trở lại cùng lần với tài nguyên mới. Phương pháp này sẽ gặp khó khăn trong việc bảo vệ tính toàn vẹn dữ liệu của hệ thống.
+ Để điều kiện 3 không xảy ra, hệ điều hành cần cho phép hệ thống được thu hồi tài nguyên từ các tiến trình bị khoá 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 sự toàn vẹn dữ liệu.
+ Để điều kiện 4 không xảy ra, có thể cấp phát tài nguyên theo một sự phân cấp như sau :
Gọi R = {R1, R2,...,Rm} là tập các loại tài nguyên. Các loại tài nguyên được đánh số thứ tự .
Ví dụ : F(đĩa) = 2, F(máy in) = 12,…
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).

deadlock là hiện tượng một tiến trình chiếm hữu tài nguyên lâu dài làm cho các tiến trình có nhu cầu sử dụng tài nguyên này luôn chờ mãi mãi .
Cho em hỏi vậy mình chỉ có thể ngăn chăn deadlock thôi đúng không ạ. Deadlock có thể được xử lý và giải phóng không ạ

NguyenMinhTam(I22B) đã viết:deadlock là hiện tượng một tiến trình chiếm hữu tài nguyên lâu dài làm cho các tiến trình có nhu cầu sử dụng tài nguyên này luôn chờ mãi mãi .
Cho em hỏi vậy mình chỉ có thể ngăn chăn deadlock thôi đúng không ạ. Deadlock có thể được xử lý và giải phóng không ạ

Deadlock có thể được xử lý và giải phóng thì đâu gọi là Deadlock nữa.

1.Hệ thống thu hồi tài nguyên của các tiến trình bị DeadLock :Phá vỡ toàn bộ chu trình bị Deadlock nhưng phí tổn khá lớn vì nhiều tiến trình có thể đã thực thi trong thời gian dài và một phần kết quả thực thi bị loại bỏ sau đó có thể phải thực hiện lại

2.Lần lượt chấm dứt từng tiến trình cho tới khi phá vỡ chu trình bế tắc (deadlock). Cứ sau khi kết thúc một tiến trình,hệ thống kiểm tra xem bế tắc còn hay không

Việc chấm dứt tiến trình có thể không đơn giản. Nếu chấm dứt một tiến trình đang trong quá trình cập nhật file có thể bị lỗi file .
Nếu sử dụng phương pháp thứ 2 nêu trên thì hệ thống phải xác định thứ tự chấm dứt tiến trình hoặc nhóm tiến trình để phá vỡ bế tắc. Quyết định này phụ thuộc vào chính sách của hệ thống,tương tự như vấn đề điều phối CPU

Như vậy các vấn đề cần phải tính đến là:
- Độ ưu tiên của tiến trình
- Tiến trình thực thi được bao lâu và cần bao lâu để kết thúc
- Tiến trình sử dụng bao nhiêu tài nguyên và bao gồm những tài nguyên nào?
- Tiến trình cần thêm bao nhiêu tài nguyên để hoàn thành.
- Có bao nhiêu tiến trình cần bị chấm dứt.
- Tiến trình có tương tác với người dùng hay không ?

NguyenMinhTam(I22B) đã viết:deadlock là hiện tượng một tiến trình chiếm hữu tài nguyên lâu dài làm cho các tiến trình có nhu cầu sử dụng tài nguyên này luôn chờ mãi mãi .

Deadlock là hiện tượng chờ mãi mãi. Tức là tiến trình này chờ tiến trình kia. Còn tiến trình chiếm hữu tài nguyên lâu thì chưa thể xảy ra deadlock. Vì ở đây tiến trình đó vẫn đang chạy và sử dụng tài nguyên chứ ko phải là giữ và chờ.

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

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.

Hiện tượng kẹt mạng tại tổng đài 1080:
+ ví dụ tổng đài 1080 gồm có 100 điện thoại viên.
+ 100 khách hàng gọi tới cùng một lúc. Khách hàng 101,102…. Gọi tới, sẽ phải chờ.
+ 1 khách hàng ứng với một điện thoại viên có thể xem như một tài nguyên.
+ nếu deadlock xuất hiện, nó có thể được giải quyết nếu 1 trong 100 khách hàng đã được điện thoại viên trả lời xong và nhường tài nguyên cho các khách hàng tiếp theo..

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:
Allocation Max Available
A B C A B C A B C
Po 0 1 0 7 5 3 3 3 2
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 >
P1 muốn tăng tiền vay (1,0,2) thì phải thỏa điều kiện:
1 – Request (yêu cầu) <= Need vì (1,0,2) <= (1,2,2) // Thỏa điều kiện
2- Request (yêu cầu) <= Available vì (1,0,2) <= (3,3,2) // Thỏa điều kiện
Ta lại làm lại từ đầu và xét trạng thái mới
Ta có:
Bảng Max sẽ được thay bằng bảng Need (Vì Need đã là giá trị lớn nhất để có thể tồn tại chuổi an toàn).
Allocation của P1 sẽ đổi do cộng đồn giá trị Allocation ban đầu với giá trị Allocation mới:
(2,0,0) + (1,0,2) = (3,0,2)
Need của P1 cũng thay đổi do điều kiện xét ta có:
Need (P1)[mới] = Need(P1)[cũ] – Request = (1,2,2) – (1,0,2) = (0,2,0)
Available cũng thay đổi do:
Available (mới) = Available (củ) – Request = (3,3,2,) – (1,0,2) = (2,3,0)
Allocation Need Available
A B C A B C A B C
Po 0 1 0 7 4 3 2 3 0
P1 3 0 2 0 2 0
P2 3 0 2 6 0 0
P3 2 1 1 0 1 1
P4 0 0 2 4 3 1
Work Need(i) P(i) Allocation
A B C A B C A B C
2 3 0 0 2 0 P1 3 0 2
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
104 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 >

NguyenMinhTam(I22B) đã viết:deadlock là hiện tượng một tiến trình chiếm hữu tài nguyên lâu dài làm cho các tiến trình có nhu cầu sử dụng tài nguyên này luôn chờ mãi mãi .
Cho em hỏi vậy mình chỉ có thể ngăn chăn deadlock thôi đúng không ạ. Deadlock có thể được xử lý và giải phóng không ạ

Theo mjh thì deadlock sẽ tự giải phóng được. Nhanh hoặc chậm tùy thuộc vào số tiến trình. Ít tiến trình tranh chấp tài nguyện thì thời gian thoát ra khỏi deadlock sẽ nhanh. Ngược lại nhiều tiến trình thì thời gian thoát ra tình trang deadloack chập hoặc rất chập. Do đoán được thời gian thoát ra tình trạng đang bị deadlock quá lâu để tránh mất thời gian thì khi đó con người sẽ can thiệp hoặc có công cụ hổ trợ khác.

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.

NguyenVanLanh (I22A) đã viết:

NguyenMinhTam(I22B) đã viết:deadlock là hiện tượng một tiến trình chiếm hữu tài nguyên lâu dài làm cho các tiến trình có nhu cầu sử dụng tài nguyên này luôn chờ mãi mãi .
Cho em hỏi vậy mình chỉ có thể ngăn chăn deadlock thôi đúng không ạ. Deadlock có thể được xử lý và giải phóng không ạ

Theo mjh thì deadlock sẽ tự giải phóng được. Nhanh hoặc chậm tùy thuộc vào số tiến trình. Ít tiến trình tranh chấp tài nguyện thì thời gian thoát ra khỏi deadlock sẽ nhanh. Ngược lại nhiều tiến trình thì thời gian thoát ra tình trang deadloack chập hoặc rất chập. Do đoán được thời gian thoát ra tình trạng đang bị deadlock quá lâu để tránh mất thời gian thì khi đó con người sẽ can thiệp hoặc có công cụ hổ trợ khác.

Uhm,mình đồng ý kiến với bạn , biết là chờ mãi mãi.nhưng đọc 1 số tài liệu lại thấy có thể giải phóng để hếtdeadlock

NguyenVanLanh (I22A) đã viết:

NguyenMinhTam(I22B) đã viết:deadlock là hiện tượng một tiến trình chiếm hữu tài nguyên lâu dài làm cho các tiến trình có nhu cầu sử dụng tài nguyên này luôn chờ mãi mãi .
Cho em hỏi vậy mình chỉ có thể ngăn chăn deadlock thôi đúng không ạ. Deadlock có thể được xử lý và giải phóng không ạ

Theo mjh thì deadlock sẽ tự giải phóng được. Nhanh hoặc chậm tùy thuộc vào số tiến trình. Ít tiến trình tranh chấp tài nguyện thì thời gian thoát ra khỏi deadlock sẽ nhanh. Ngược lại nhiều tiến trình thì thời gian thoát ra tình trang deadloack chập hoặc rất chập. Do đoán được thời gian thoát ra tình trạng đang bị deadlock quá lâu để tránh mất thời gian thì khi đó con người sẽ can thiệp hoặc có công cụ hổ trợ khác.

Mình nghĩ Deadlock cũng như hiện tượng kẹt xe vậy, cách giải quyết là cứ để mặc nó, dù có công an giao thông thì nó vẫn cứ kẹt, ai bị kẹt xe thì sẽ biết, cách tốt nhất là làm sao để tránh bị kẹt xe và hệ điều hành có chức năng làm công việc đó

Khá vui về Deadlock

Huynh Xuan Dat(I22A) đã viết:Để ngăn chặn Deadlock ta phải làm sao?
vd1 :2 con dê đi qua cầu, dê trắng và dê đen đều mún mình qua cầu chẳng ai chịu nhường ai cả, và cả 2 đều mắc kẹt mãi trên cầu....(có thể tranh chấp dẫn đến xảy ra đến cả 2 con đều rơi xuống cầu) tham khảo khóa trước
vd2:Giả sử tổng đài 1080 có tất cả 50 điện thoại viên. Cùng 1 lúc có 50 khách gọi đến nhờ phục vụ . Lúc này người thứ 51 gọi vào 1080 phải chờ . Xãy ra hiện tượng deadlock
tham khảo khóa trước
nhưng vd2 minh chưa thực sự hiểu bản chất lắm máy bạn giải thích giúp

Theo mình nghĩ ví dụ 2 vẫn chưa gọi là deadlockl vì khi một người nào đó trong 50 người đã được phục vụ cúp máy thì người 51 vẫn được đáp ứng nhu cầu bình thường

Các bạn tham khảo thêm!
Để 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ảyra 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ệncầ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 đếndeadlock. 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ìnhnà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ấyl ạ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 đượcgiữ 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ầutà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).

PhamQuocCuong (I22A) đã viết:

NguyenVanLanh (I22A) đã viết:

NguyenMinhTam(I22B) đã viết:deadlock là hiện tượng một tiến trình chiếm hữu tài nguyên lâu dài làm cho các tiến trình có nhu cầu sử dụng tài nguyên này luôn chờ mãi mãi .
Cho em hỏi vậy mình chỉ có thể ngăn chăn deadlock thôi đúng không ạ. Deadlock có thể được xử lý và giải phóng không ạ

Theo mjh thì deadlock sẽ tự giải phóng được. Nhanh hoặc chậm tùy thuộc vào số tiến trình. Ít tiến trình tranh chấp tài nguyện thì thời gian thoát ra khỏi deadlock sẽ nhanh. Ngược lại nhiều tiến trình thì thời gian thoát ra tình trang deadloack chập hoặc rất chập. Do đoán được thời gian thoát ra tình trạng đang bị deadlock quá lâu để tránh mất thời gian thì khi đó con người sẽ can thiệp hoặc có công cụ hổ trợ khác.

Mình nghĩ Deadlock cũng như hiện tượng kẹt xe vậy, cách giải quyết là cứ để mặc nó, dù có công an giao thông thì nó vẫn cứ kẹt, ai bị kẹt xe thì sẽ biết, cách tốt nhất là làm sao để tránh bị kẹt xe và hệ điều hành có chức năng làm công việc đó

Đối với những trường hợp mà Deadlock xảy ra gây ảnh hưởng nghiêm trọng đến hệ thống thì chúng ta cần phải có giải pháp ngăn chặn và tránh nó, còn đối với những trường hợp Deadlock xảy ra mà không gây ảnh hưởng nhiều đến hệ thống thì chúng ta có thể bỏ mặt, coi như không có.Việc đưa ra giải pháp giải quyết vấn đề deadlock tùy thuộc vào mức độ ảnh hưởng và tần số xuất hiện của deadlock đó.Cũng ví dụ trong trường hợp kẹt xe trên một đoạn đường, nếu đoạn đường bị kẹt xe này chỉ là đoạn đường phụ không phải là đoạn đường huyết mạch thì ta có thể bỏ mặt nó không cần phải quan tâm.Nhưng nếu nó là một đoạn đường chính, là giao thông huyết mạch của thành phố thì cần phải tìm giải pháp để giải quyết nó, chấp nhận tốn kém.ví dụ như ở ngã tư hàng xanh trước kia chiều nào cũng kẹt xe kinh khủng, nhưng bây giơ UBNND thành phố đã cho xây cầu vượt(chấp nhận tốn kém) để giải quyết vấn đề kẹt xe

PhamQuocCuong (I22A) đã viết:

Khá vui về Deadlock

video này minh họa cho bài toán về bữa ăn của năm triết gia

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

khái niệm Deadlock.
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 qua cầu cùng lúc tới đoạn hẹp, 2 xe moi xe chiếm giữ nữa phần đường không xe nào chịu nhường xe nao, lúc này xảy ra hiện tượng Deadlock.

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

Các điều kiện dẫn đến Deadlock.
-Deadlock xảy ra khi co 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.
+ Giữ và chờ (Hold and wait): có 1 tiến trình đang giữ 1 tài nguyên và xin thêm đ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 đượ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.

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

phần mềm vẽ đồ thị RGAPH.
http://www.mediafire.com/?0jngzqtmuuo

Bản chất của Deadlock bao gồm hai phần: các điều kiện dẫn đến tình huống kẹt và đồ thị cấp phát tài nguyên (RAG)
Deadlock không phải là dạng chờ tài nguyên (máy photocopy) để in ấn hay phô-tô tài liệu của nhân viên. Đây không phải là Deadlock như một số bạn đã thảo luận. Vì hiện tượng Kẹt khóa là tình trạng các tiến trình "bám chặt" lấy tài nguyên, và các tiến trình khác gởi yêu cầu đến vẫn không được đáp ứng. Mình sẽ thảo luận về vấn đề cung: nhu cầu, yêu cầu và ấn định tại những mục tiếp theo.

Một số tình huống kẹt tiến trình Deadlock mình đã được nghe giảng tại tiết học của thầy, cụ thể như: "Hai con cua" của thầy, ví dụ "xe đi qua cầu hẹp" hay chuyện ngụ ngôn "Dê trắng - dê đen" đã được học.

- Đồ thị cấp phát tài nguyên (Resource allocation graph-RAG) là đồ thị có hướng với tập nút V và tập cung E.
+ Tập nút V gồm 2 loại:
P ={P1, P2, ..., Pn} tập hợp các tiến trình đang vận hành trong hệ thống.
R ={R1, R2, ..., Rm} tất cả các tài nguyên trong hệ thống. Mỗi loại Rj có từ 1 đến nhiều
phiên bản. VD: máy in có 3 phiên bản, ...
+Tập cung E bao gồm:
Cung yêu cầu (Request edge): có hướng từ Pi -> Rj, P1 yêu cầu 1 phiên bản tài nguyên Rj.
Cung ấn định (Assignment edge): có hướng từ Rj->Pi, 1 phiên bản tài nguyên Rj được cấp
phát cho Pi.
Đồ thị cấp phát tài nguyên gồm có: chu trình và không có chu trình.
o Không có chu trình: không tồn tại Deadlock
o Có chu trình: có hoặc không có Deadlock
.Có Deadlock khi mỗi tài nguyên trên chu trình chỉ có duy nhất 1 phiên bản.
.Có thể không có Deadlock khi tài nguyên thuộc chu trình có nhiều phiên bản.





- Cách vẽ:
Hiển thị mỗi tiến 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 phiên bản, chúng ta hiển thị mỗi phiên bản là một chấm nằm trong hình vuông. Chú ý rằng một cung yêu cầu trỏ tới chỉ một hình vuông Rj (tới đường viền), trái lại một cung ấn định cũng phải trỏ tới một trong các dấu chấm trong hình vuông(vào trong viền).




- Giải thích:
Hình 1:
Các tập P, R, và E:
P = {P1, P2, P3}
R = {R1, R2, R3, R4}
E = {P1→R1, P2 →R3, R1 →P2, R2→P2, R3→P3}

Tiến trình P1 đang giữ một phiên bản của loại tài nguyên R2 và yêu cầu được cấp phát 1 phiên bản của loại tài nguyên R1. Tiến trình P2 đang giữ 1 phiên bản của loại tài nguyên R1 và 1 phiên bản của R2 và yêu cầu được được tài nguyên R3 cấp cho 1 phiên bản của nó. Tiến trình P3 đang giữ 1 phiên bản của tài nguyên R3. Còn lại tài nguyên R4 với các phiên bản của nó vẫn chưa có tiến trình nào xin được cấp phát. Từ hình vẽ Đồ thị cấp phát tài nguyên cho thấy không tồn tại chu trình cũng như Deadlock.

Hình 2:
Các tập P, R tương tự hình 1, tập E = {P1 → R1, R1 → P2, P2 → R3, R3 → P3, P3 → R2, R2 → P1, R2→P2}
Tiến trình P1 đang giữ một phiên bản của loại tài nguyên R2 và yêu cầu được cấp phát 1 phiên bản của loại tài nguyên R1. Tiến trình P2 đang giữ 1 phiên bản của loại tài nguyên R1 và 1 phiên bản của R2 và yêu cầu được được tài nguyên R3 cấp cho 1 phiên bản của nó. Tiến trình P3 đang giữ 1 phiên bản của tài nguyên R3 và yêu cầu cấp phát 1 phiên bản của tài nguyên R2. 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, do nhìn hình lại chúng ta thấy có 2 chu trình: P1 → R1 → P2 → R3 → P3 → R2 → P1 và P2 → R3 → P3 → R2 → P2. Nghĩa là tiến trình P3 đang chờ tiến trình P1 hay P2 trả lại tài nguyên R2. Ngoài ra, tiến trình P1 đang chờ tiến trình P2 trả lại phiên bản tài nguyên R1 cho nên tiến trình P1, P2, P3 đã bị Deadlock vì không có phiên bản tài nguyên yêu cầu hiện có (vi phạm điều kiện deadlock).

Hình 3:
Các tập P, R, và E:
P = {P1, P2, P3, P4}
R = {R1, R2}
E = {P1 → R1, R1 → P2 , R1 → P3, P3 → R2, R2 → P1, R2→P4}
Tiến trình P1 đang giữ một phiên bản của loại tài nguyên R2 và yêu cầu được cấp phát 1 phiên bản của loại tài nguyên R1. Tiến trình P2 đang giữ 1 phiên bản của loại tài nguyên R1. Tiến trình P3 đang giữ 1 phiên bản của tài nguyên R1 và yêu cầu cấp phát 1 phiên bản của tài nguyên R2. Tiến trình P4 đang giữ 1 phiên bản của tài nguyên R2. Từ hình chúng ta thấy xảy ra 1 chu trình P1 → R1 → P3 → R2 → P1 nhưng không có deadlock vì tiến trình P4 có thể trả lại phiên bả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.