Thảo luận Bài 8

Để xảy ra tình huống kẹt tiến trình, cần quan tâm đến bốn điều kiện sau:

1. Loại trừ lẫn nhau (Mutual Exclusion): nghĩa là tại một thời điểm, các tiến trình không được phép hoạt đồng thời. Có thể được hiểu theo cách ngắn gọn của thầy: "hễ anh hoạt động thì tôi thôi, nhường chỗ cho anh, nếu có anh hoạt động thì tôi ngưng hoạt động".

Ví dụ của Thầy: Tranh chấp tài nguyên khi sinh viên sử dụng bảng, nếu anh A được gọi lên bảng thì tại thời điểm anh A đang ghi thì anh B không được phép ghi.

Ví dụ của Khoa: Trong công viên nước, các trò chơi trượt ống, tại một thời điểm chỉ có một người được sử dụng máng trượt để tham gia trò chơi, nếu tại cùng một thời điểm, hai người cùng tham gia trượt chung thì không thể trượt, và cả hai có thể bị thương -> tình huống này cũng giống như kẹt tiến trình.

2. Chờ và giữ (Hold and Wait): tiến trình đang thực hiện thao tác trên tài nguyên và chưa trả tài nguyên về trạng thái ban đầu nhưng đồng thời lại xin thêm một tài nguyên khác.
Minh họa: Tình huống này thật nguy hiểm, hệ thống có thể bị treo do không đủ đáp ứng các request của tiến trình yêu cầu. Cũng giống như các chương trình virus có thể làm hệ thống bị đóng băng và treo toàn cục.

3. Không có tiếm quyền (No Preeption): đang dùng quyền này và bị quyền khác tiếm mất quyền đi: tài nguyên đang giữ bởi tiến trình không thể bị tiếm quyền tiếp mà phải được tự nguyện trả lại hệ thống.
Ví dụ: Hai ô-tô đang di chuyển lên mặt cầu, có thể đưa ra giải quyết tình huống kẹt: cho phép người gác cầu (thanh tra giao thông) bắt một xe không được phép lưu thông và cho xe còn lại di chuyển tới tiếp lộ trình của mình.

4. Chờ xoay vòng (Circular Wait): các lượt chờ xoay vòng như P1 -> R(P2) đang giữ, và P2 ->R(P3),... cứ thế các vòng chờ diễn ra song song bên cạnh các tiến trình -> các tiến trình mắc kẹt lồng nhau.
Ví dụ: Xâu chìa khóa để mở két sắt: phải có chìa khóa P1 để mở được tủ P2, nhưng đồng thời chìa khóa P2 lại được cất chung trong tủ P3... và cuối cùng, chìa khóa để mở két sắt là một ẩn số , (đây là ví dụ minh họa để các bạn dễ hình dung thôi nhưng thực tế thì không có điều này, trừ trường hợp giấu chìa khóa rất kỹ vì độ an toàn và tin cậy rất ít).

Mời các bạn thảo luận tiếp về vấn đề này với mình nha!

Thuật giải nhà băng :
Các bước thực hiện giải thuật toán :
AVAILABLE : Là tài nguyên sẵn có ,hệ điều hành có thể dùng để cấp phát cho các tiến trình khi có yêu cầu.
Cột NEED I : Tìm tiến trình (Pi )có giá trị yêu cầu tài nguyên Bước 1:
Đầu tiên giá trị ban đầu của (cột) WORK = AVAILABLE
có 2 tiến trình là P1 và P3 thỏa điều kiện .
vì NEED 1 (P1) = 1 2 2 ,xét từng cặp 1 so với WORK(A B C)=3 3 2
NEED 3 (P3) = 0 1 1 ,xét từng cặp 1 so với WORK(A B C)=3 3 2
thì đều thỏa điều kiện WORK A B C >= NEED 1 và WORK A B C >= NEED 3

Chúng ta có thể chọn P1 hoặc P3 .mình Chọn P3 để xét tiếp
Cột Allocation là tài nguyên mà HĐH cấp phát cho tiến trình Pi
Trong trường hợp này là P3
Bước 2:
Giá trị của cột WORK=Giá trị của cột WORK dòng trên + giá trị của cột Allocation dòng trên
Trong trường hợp này Giá trị của cột WORK ở dòng thứ hai = 3+2 3+1 2+1= 5 4 3
Như vậy giá trị của WORK ở dòng 2 là : 5 4 3
có 2 tiến trình là P1 và P4 thỏa điều kiện
vì P1 = 1 2 2 =< 5 4 3(WORK) và P4=4 3 1 =< 5 4 3(WORK).mình chọn P1 để xét tiếp.
Bước 3 :
Giá trị của cột WORK ở dòng thứ ba = (5+2) ( 4+0) ( 3+0)= 7 4 3
Như vậy giá trị của WORK ở dòng 3 là : 7 4 3
Có hai tiến trình là P2 và P4 thỏa điều kiện
Vì P2=6 0 0 =< 7 4 3(WORK) và P4=4 3 1 = < 7 4 3(WORK).mình chọn P2 để xét tiếp.
Bước 4 :
Giá trị của cột WORK ở dòng thứ tư = (7+3) ( 4+0) ( 3+2)= 10 4 5
Như vậy giá trị của WORK ở dòng 4 là : 10 4 5
Trong trường hợp này chỉ có tiến trình P4 thỏa điều kiện
Vì P4=4 3 1 =< 10 4 5(WORK)
Bước 5 :
Giá trị của cột WORK ở dòng thứ năm = (10+0) ( 4+0) ( 5+2)= 10 4 7
Như vậy giá trị của WORK ở dòng 5 là : 10 4 7
Và trong trường hợp này chỉ còn lại tiến trình P0
P0=4 3 1 =< 10 4 5(WORK)


Như Vậy : chuỗi an toàn ={P3,P1,P2,P4,P0}
Vậy trạng thái của hệ thống ở thời điểm T0 là an toàn.
Trong khi làm bài không tránh khỏi sai sót,các bạn góp ý và sửa giúp mình với nha.

1. Sử dụng biện pháp ngăn chặn (Prevention) hoặc biện pháp tránh (Avoidance), nhưng hình thức tránh được áp dụng nhiều trong thực thế để giảm thiểu quá trình kẹt khóa tiến trình. Hình thức can thiệp trực tiếp này tuy có nhiều ưu điểm, song song đó cũng có những khiếm khuyết (tốn nhiều chi phí và phải có quyền hạn mới can thiệp được), ví dụ minh họa về hai xe lưu thông trên mặt cầu và tốn thêm khoản chi phí để xây dựng thêm một cần cẩu.

2. Cho phép hệ thống bị Deadlock và xác định (Detection) và tìm cách khắc phục (Recovery). Với phương pháp này, hạn chế được số lần deadlock xảy ra sau này, mang tính chất Maintain (duy trì) hệ thống.

3. Không quan tâm đến quá trình kẹt khóa, nếu hệ thống xảy ra quá trình kẹt khóa và hệ thống bị treo, người dùng chủ động EndProcess những tác vụ "nghi ngờ" Deadlock hoặc khởi động lại thiết bị.

Cung ấn đinh : HĐH cấp phát tài nguyên cho các tiến trình
Ban đầu tất cả các cung đều là cung nhu cầu -> chuyển sang cung yêu cầu -> cuối cùng là cung ấn định(nếu HĐH tính toán được nếu yêu cầu của các tiến trình không vượt quá giới hạn tài nguyên của hệ thống(AVAILABLE) và không có khả năng gây ra Deadlock thì sẽ cấp phát tài nguyên cho các tiến trình)
R1,R2 : Là các tài nguyên ,như (máy in kim,máy in laser…)
P1,P2 là các tiến trình

Bước 1 : Tất cả các cung đều là cung nhu cầu (lúc 18h00)

Bước 2 : Cung nhu cầu từ P1 ,chuyển sang cung yêu cầu (18h02)

Bước 3 : Cung nhu cầu từ P1 ,chuyển sang cung ấn định (18h05)

Bước 4 : Cung nhu cầu từ P2 ,chuyển sang cung yêu cầu(18h10)
Vì Tài nguyên(R1) đã được cấp phát cho P1,nên P2 phải chờ(ngủ).

Bước 6: Trong lúc ngủ(P2 chờ đươc cấp phát tài nguyên R1) thì P2 tiếp tục chuyển từ nhu cầu tài nguyên R2,sang yêu cầu tài nguyên R2.vì P2 có thể là tiến trình đa luồng,trong P2 gồm các luồng con ,như (P21,P22…),trong lúc luồng P21 ngủ(chờ),thì luồng P22 gởi yêu cầu xin cấp phát tài nguyên R2.

Bước 7 : Nhưng HĐH nhận thấy,nếu HĐH cấp phát tài nguyên R2 cho P2 thì có thể dẫn đến khả năng DeadLock xảy ra(vì khi đó sẽ tạo thành 1 chu trình khép kín,nếu như cung nhu cầu từ P1->R2 chuyển sang cung yêu cầu).nên HĐH không cấp phát tài nguyên cho P2.và cung từ P2->R2 vẫn là cung nhu cầu.

Bước 8 : cung nhu cầu từ P1->R2 chuyển sang cung yêu cầu.
anh chị và các bạn sửa giúp mình với nha

Admin
- Hiểu bài, tuy cần nhấn mạnh là R1 và R2 chỉ có 1 phiên bản !
- Trình bày tốt, nhưng cần vẽ thêm Dấu chấm (biểu tượng của phiên bản duy nhất) vào giữa các ô của R1 và R2, rồi vẽ lại các cung ấn định ! (chú ý đưa R1 và R2 ra ngoài)

QuangMinhTuan(I22B) đã viết:Deadlock là trạng thái xảy ra khi một nhóm tiến trình ngưng hoạt động trong thời gian dài do do một hay nhiều tiến trình trong nhóm chờ mãi mãi một sự kiện (event) phát sinh bởi một tiến trình khác hoặc trong nhóm đó.
Ví dụ: A vào thư viện mượn sách để đọc, nhưng B đã mượn trước nên A phải ngồi chờ khi B đọc xong đã.

Ví dụ với khái niệm khác nhau ah. Theo ví dụ A sẽ ngồi chờ 1 thời gian sẽ được đọc còn k/n thì là chờ mãi mãi ak.

1/ Đặc điểm: Trong một deadlock, các quá trình không bao giờ hoàn thành việc thực thi và các tài nguyên hệ thống bị buộc chặt, ngăn chặn các quá trình khác bắt đầu.

2/ Các phương thức
- 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
- Cho phép hệ thống đi vào trạng thái deadlock, sau đó phát hiện và phục hồi
- 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

Các phương pháp xử lý Deadlock
+ Ngăn ngừa hoặc tránh xa, đảm bảo rằng hệ thống sẽ không bao giờ đi vào trạng thái deadlock.
+ Cho phép hệ thống đi vào trạng thái deadlock rồi khôi phục lại.
+ Bỏ qua dead lock , coi như ko có dead trong hệ thống
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ó)

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

Process Allocation Max Need Available
P1 3 9 6 5
P2 1 4 3
P3 1 8 7


Bảng trợ giúp:
Work >= Needi Pi Allocation
5 3 P2 1
6 6 P1 3
9 7 P3 1

Tìm được chuỗi an toàn P2, P1, P3
Do đó trạng thái hệ thống ở thời điểm Ti là an toàn
b.Xác định có nên đáp ứng hay không yêu cầu cấp thêm 1 máy cho tiến trình P3
Gọi yêu cầu là Request3. Ta cáo Request3 = 1
Request3 =< Need3 (vì 1 =<7)
Request3 =< Available (vì 1 =<5)
Trạng thái mới của hệ thống
Allocation = (3,1,2)
Max = (9,4,8 )
Avaible = 10 - (3+1+2) = 4

Process Allocation Max Need Available
P1 3 9 6 4
P2 1 4 3
P3 2 8 6


Bảng trợ giúp:
Work >= Needi Pi Allocation
4 3 P2 1
5 ? ? ?

Cả 2 tiến trình P1 và P3 điều không thỏa điều kiện Work >= Needi (vì Need2 = 6, Need3 = 6)
Vậy ta không nên đáp ứng yêu cầu Request3 vì hệ thông sẽ không còn an toàn

câu 1:

Tiến trình	Đã được cấp	Tối đa cần
P1	5	10
P2	2	4
P3	2	9

Hê có: Available=12-9=3
Need: Max-Allocation
Đang giữ Max Hệ có
P1 5 10 3
P2 2 4
P3 2 9

TT	Need(i)
P1	5
P2	2
P3	8

Nên ta có bảng CN giai bai tap:

Work(i)	Need(i)	P(i)	Allocation(i)
3	2	P2	2
5	5	P1	5
10	2	P3	2

=> =>Chuổi an toàn ở thời điểm T(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 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ó nên đáp ứng yêu cầu (0, 4, 3, 0) của P1 ?
Giải:
a. Xét tại thời điểm To mà 5 tiến trình được cấp phát như đề bài ta có:
Need[i] = Max[i] – Allocation[i]

Tìm chuỗi an toàn:


Vậy tại thời điểm To tồn tại chuỗi an toàn {P0, P2, P3, P4, P1}. Suy ra, hệ thống tại thời điểm T0 ở trạng thái an toàn.

b. Ta thấy, yêu cầu thêm (0, 4, 3, 0) của P1 thoả điều kiện Request1 <= Need1, nhưng không thoả điều kiện: Request1 <= Available vì tài nguyên C trong hệ thống chỉ còn 2 mà yêu cầu 3. Do vậy, không thể cấp phát thêm (0, 4, 3, 0) cho P1 được.

B1. Khai báo nhu cầu sử dụng tài nguyên của các tiến trình tại đầu chương trình, hay còn gọi là cung nhu cầu.

B2. Cung nhu cầu sau khi nhận thông tin request sẽ thành cung yêu cầu.

B3. Cung yêu cầu sẽ chuyển sang cung yêu cầu.

Để giảm thiểu các hiện tượng Deadlock, hệ thống xem xét [nhu cầu] có phù hợp hay không? Nếu phù hợp thì cấp phát, nếu không phù hợp thì hủy bỏ yêu cầu.

VD: Vào lúc 18h00 thì P1, P2 bắt đầu vận hành, chúng khai báo nhu cầu sử dụng R1, R2 (ví dụ như các tài nguyên lên lượt là máy in và máy quét hình).

Đến 18h05 thì bắt đầu hình thành cung ấn định và đồng thời P2 cũng yêu cầu đến R1, nhưng do R1 đang được dùng bởi P1 và R1 phải xử lý và không cấp cho P2 (mặc dù có P2 đã gởi yêu cầu cho R1 trước đó), lúc này P2 phải chờ (ngủ).

Vào mỗi thời điểm khác nhau, các tiến trình hoạt động khai báo nhu cầu, gởi yêu cầu và thực hiện ấn định không đồng đều, đúng với nhu cầu trong thực tế.

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

Bạn ơi, mình không hiểu ví dụ bạn nêu cho lắm! Mình nghĩ ở trong ví dụ bạn nêu thì sao xảy ra deadlock được nhỉ? Vì khi 100 điện thoại viên đều bận, mà có khách hàng 101 hay 102 gọi đến, thì 2 khách hàng này chỉ cần chờ một khoảng thời gian nhất định đến khi có điện thoại viên rảnh thôi. Đâu có chờ mãi mãi đâu.

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.

Các bạn cho mình hỏi: Khi làm bài thi, nêu ví dụ về deadlocks thì có phải nêu ra tài nguyên tranh chấp dẫn đến xảy ra deadlock không nhỉ? Ví dụ Thầy nêu trên lớp: 2 con cua tranh chấp nhau tài nguyên là càng của nhau.

- Mutual exclusion: với mỗi tài nguyên chỉ có một process sử dụng tại một thời điểm.
- Hold and wait: một process vẫn sở hữu tài nguyên đã được cấp phát trong khi yêu cầu một tài nguyên khác.
- No preemption: một tài nguyên không thể bị đoạt lại từ chính process đang sở hữu tài nguyên đó.
- Circular wait: tồn tại một chu trình khép kín các yêu cầu tài nguyên.

-Các tài nguyên hệ thống được chia thành nhiều Loại, mỗi loại có 1 hoặc nhiều Phiên bản(Instances). Các tài nguyên hệ thống này cấp phát cho các tiến trình theo yêu cầu.
- Tài nguyên cùng loại: Giả sử máy có 3 ổ băng từ và có 3 tiến trình đang chạy. Mỗi tiến trìnhđang giữ 1 ổ băng.
- Tài nguyên khác loại: Giả sử có 1 máy in, 1 ổ băng từ. Tiến trình P1 đang giữ ổ băng, P2 giữ máy in.

Ưu điểm: ngăn chặn bế tắc (deadlock
prevention) là phương pháp tránh được bế
tắc bằng cách làm cho điều kiện cần không
được thỏa mãn

Nhược điểm:
_Giảm khả năng tận dụng tài nguyên và giảm
thông lượng của hệ thống
_Không mềm dẻo

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

Giải
a.
Allocation = (3,1,1)
Max = (9,4,8 )
Available = 10 - (3+1+1) = 5
Process Allocation Max Need Available
P1 3 9 6 5
P2 1 4 3
P3 1 8 7
Need = Max – Allocation (tuong ung)

Bảng trợ giúp:
Work >= Needi Pi Allocation
5 3 P2 1
6 6 P1 3
9 7 P3 1
Work dau tien = available
Work = work truoc + allocation(tuong ung)

Tìm được chuỗi an toàn {P2, P1, P3}
Do đó trạng thái hệ thống ở thời điểm Ti là an toàn

b.
Xác định có nên đáp ứng hay không yêu cầu cấp thêm 1 máy cho tiến trình P3

Gọi yêu cầu là Request3. Ta có Request3 = 1
Request3 <= Need3 (vì 1 <=7)
Request3 <= Available (vì 1 <=5)

Trạng thái mới của hệ thống :
Allocation = (3,1,2)
Max = (9,4,8 )
Available = 10 - (3+1+2) = 4
Process Allocation Max Need Available
P1 3 9 6 4
P2 1 4 3
P3 2 8 6


Bảng trợ giúp:
Theo bài tập này mình có 2 cách tạo bảng (vì Need của P1 = Need của P3 = 6):
1)
Work >= Needi Pi Allocation
4 3 P2 1
5 6 P3 2

Hoặc :
2)
Work >= Needi Pi Allocation
4 3 P2 1
5 6 P1 3

Vì cả 2 tiến trình P1 và P3 điều không thỏa điều kiện Work >= Needi (vì 5 < 6)
Vậy ta không nên đáp ứng yêu cầu Request3 vì hệ thống sẽ không còn an toàn

Đị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ụ:
- 5 thầy giáo đều cần máy chiếu để dạy ngay trong khi ở phòng thiết bị hiện tại chỉ có 1 máy chiếu => dẫn đến tranh chấp
- 2 xe đi ngược chiều cùng qua 1 cây cầu hẹp, mà cầu thì chỉ có 1 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 xe nào
[list][*]

Để 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 tài nguyên nào cũng dùng chung được cùng một lúc bởi nhiều tiến trình.
- Với Hold and Wait:
1- Khi tiến trình yêu cầu tài nguyên, nó không được giữ 1 tài nguyên nào khác.
2- Tiến trình phải yêu cầu và được cấp tất cả các tài nguyên mà nó cần ngay đầu công việc.
- Với No Preemption:
1- Khi tiến trình giữ tài nguyên mà xin thêm nhưng không được, các tài nguyên mà nó giữ phải bị tiếm quyền sử dụng và trả lại HĐH.
2- Khi tiến trình xin thêm tài nguyên, nếu tài nguyên này đang được giữ bởi tiến trình khác đang ở trạng thái chờ, tài nguyên của tiến trình khác này bị tiếm quyền sử dụng để cấp cho tiến trình đang xin.
- Với Circular Wait: Cấp tài nguyên theo một thứ tự nào đấy.

Để tìm ít nhất một chuỗi an toàn bằng thuật toán Nhà băng, chúng ta phải chọn P(i) sao cho Work >= Need(i). Vậy chọn P(i) như thế nào là thích hợp?
Ta có tập Work được khởi tạo bằng tập Available và duy trì bằng cách cộng dồn từng phiên bản của tài nguyên với tập Allcation(i). Vậy chúng ta có thể chọn P(i) là P(i) có “Allocation(i) lớn nhất trong tập Allocation”!
Allocation(i) lớn nhất phải thỏa mãn 2 điều kiện:
- Need(i) <= Work
- Tổng phiên bản của tài nguyên trong Allocation lớn nhất.
Tóm lại, ta có thuật toán tìm P(i) như sau:
Bước 1: Tạo tập Temp = {P(i) | Need(i) <= Work}
Bước 2: Chọn P(i) trong tập Temp có Allocation(i) lớn nhất (tổng các phiên bản là lớn nhất)
Ví dụ: Lấy lại bài tập trong Slide bài 8:
Thời điểm T0:
Available(3,3,2)

Process	Allocation	Max	Need
	A B C	A B C	A B C
P0	0 1 0	7 5 3	7 4 3
P1	2 0 0	3 2 2	1 2 2
P2	3 0 2	9 0 2	6 0 0
P3	2 1 1	2 2 2	0 1 1
P4	0 0 2	4 3 3	4 3 1

Áp dụng công nghệ giải bài tập, ta có:

Work	Need(i)	P(i)	Allocation(i)
A B C	A B C		A B C
3 2 2	0 1 1	P3	2 1 1
5 3 3	1 2 2	P1	2 0 0
7 3 3	6 0 0	P2	3 0 2
10 3 5	4 3 1	P4	0 0 2
10 3 7	7 4 3	P0	0 1 0

- Với Work(3,2,2), ta có tập Temp = {P1(1,2,2), P3(0,1,1)}
sum(Allocation(1)) = 2+0+0 = 2
sum(Allocation(3)) = 2+1+1 = 4 -> Max Allocation
Vậy ta chọn P3.

- Với Work(5,3,3), ta có tập Temp = {P1(1,2,2), P4(4,3,1)}
sum(Allocation(1)) = 2+0+0 = 2
sum(Allocation(4)) = 0+0+2 = 2
Trường hợp có nhiều Max ta có thể chọn tùy ý -> Chọn P1

- Với Work(7,3,3), ta có tập Temp = {P2(6,0,0), P4(4,3,1)}
sum(Allocation(2)) = 3+0+2 = 5 -> Max Allocation
sum(Allocation(4)) = 0+0+2 = 2
Chọn P2.

- Với Work(10,3,5), ta có tập Temp = {P0(7,4,3), P4(4,3,1)}
sum(Allocation(0)) = 0+1+0 = 1
sum(Allocation(4)) = 0+0+2 = 2 -> Max Allocation
Chọn P4.

- Với Work(10,3,5), ta có tập Temp = {P0(7,4,3)}
sum(Allocation(0)) = 0+1+0 = 1 -> Max Allocation
Chọn P0.
Ta có chuỗi an toàn: {P3,P1,P2,P4,P0}

Bằng cách này chúng ta có thể tìm ra chuỗi an toàn nhanh nhất mà không mất thời gian bởi việc chọn nhầm Pi.

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
Trong thảo luận dưới đây, chúng ta thảo luận chi tiết về hai yêu cầu khi chúng liên quan đến những hệ thống với chỉ một thể hiện của mỗi loại tài nguyên cũng như đối với hệ thống có nhiều thể hiện cho mỗi loại tài nguyên. Tuy nhiên, tại thời điểm này chúng ta chú ý lược đồ phát hiện và phục hồi yêu cầu chi phí bao gồm không chỉ chi phí tại thời điểm thực thi cho việc duy trì thông tin cần thiết và thực thi giải thuật phát hiện mà còn các lãng phí có thể phát sinh trong việc phát hiện từ deadlock.

* 4 điều kiện cần dẫn đến Deadlocks:
- Loại trừ lẫn nhau (Mutual Exclusion): Ít nhất có 1 tài nguyen có tính không chia sẽ (non-sharable), nghĩa là : Một thời điểm chỉ có 1 tiến trình được sử dụng nó.
VD: Xe qua cầu hẹp. Mỗi thời điểm chỉ có xe ô tô được đi qua cầu thôi. vì cầu hẹp nên không thể dùng chung được.
- Giữ và chờ ( Hold and Wait ) : Có một tiến trình đang giữ 1 tài nguyên và xin thêm tài nguyên đang độc chiếm tiến trình khác.
VD: Xe qua cầu hẹp . 2 xe đang đứng giữa cầu. Mỗi xe đang giữ nửa mặt cầu và muốn "xin" thêm nửa mặt cầu còn lại.
- Không có tiếm quyền ( No Preemption ) : Tài nguyên đang giữ bởi tiến trình không thể bị tiếm quyền mà phải được tiến trình này tự nguyện trả lại hệ thống sau khi sử dung xong.
VD:Xe qua cầu hẹp .Phải để 2 xe A hoặc B tự nguyện trả lại mặt đường (tức là một trong 2 xe phải lùi lại). Còn có tiếm quyền (Preemption) nghĩa là cầu được lắp chiếc "cẩu" để khi cần thiết "nhấc" 1 ô tô lên khoảng 2 m (tiếm quyền sử dụng mặt cầu của nó) để chiếc kia qua được !
- 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 bời giữ P2, tiến trình P2 chờ TN giữ bởi P3,...,Pn chờ P1.

* Phủ định 4 điều kiện:
- 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.

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

• Trình bày 4 cách ngăn chặn Deadlock.
Để ngăn chặn Deadlock ta phải làm sao cho ít nhất 1 trong 4 điều kiện dẫn đến Deadlock không xảy ra. Cụ thể:
- Với Mutual Exclusion: Đảm bảo TN(tai nguyên) nào cũng dùng chung được cùng một lúc bởi nhiều tiến trình.
- Với Hold and Wait:
1- Khi TT yêu cầu TN, nó không được giữ 1 TN nào khác.
2- TT phải yêu cầu và được cấp tất cả các TN mà nó cần ngay đầu công việc.
- Với No Preemption:
1- Khi TT giữ TN mà xin thêm nhưng không được, các TN mà nó giữ phải bị tiếm quyền sử dụng và trả lại HĐH.
2- Khi TT xin thêm TN, nếu TN này đang được giữ bởi TT khác đang ở trạng thái chờ, TN của TT khác này bị tiếm quyền sử dụng để cấp cho TT đang xin.
- Với Circular Wait: Cấp TN theo một thứ tự nào đấy.