Thảo luận Bài 8

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

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

Định nghĩa Deadlock & Điều kiện cần để xảy ra deadlock

Định nghĩa Deadlock
- Trong hệ thống đa chương, nhiều quá trình có thể
cạnh tranh một số giới hạn tài nguyên.
- Một quá trình yêu cầu tài nguyên, nếu tài nguyên
không sẵn dùng tại thời điểm đó, quá trình đi vào
trạng thái chờ.
-Quá trình chờ có thể không bao giờ chuyển trạng thái
trở lại vì tài nguyên chúng yêu cầu bị giữ bởi những
quá trình khác
=>Trường hợp này gọi là deadlock(khóa chết).

Điều kiện cần để xảy ra deadlock :
Bốn điều kiện cần (necessary condition) để xảy ra
deadlock
1. Loại trừ tương hổ (Mutual exclusion): ít nhất một
tài nguyển được giữ trong chế độ không chia sẻ
2. Giữ và chờ cấp thêm tài nguyên (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. Không có ưu tiên (No 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 nó muốn.
4. Chu trình (Circular wait): tồn tại một chu trình của các yêu cầu tài nguyên và tài nguyên đã được cấp phát.

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

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

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

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

Trong một deadlock, các quá trình không bao giờ hoàn thành việc thực thi và
các tài nguyên hệ thống bị buộc chặt, ngăn chặn các quá trình khác bắt đầu.
Mục đích Sau khi học xong chương này, người học nắm được những kiến thức sau:
Hiểu mô hình hệ thống về deadlock
• Hiểu các đặc điểm của deadlock
• Hiểu các phương pháp quản lý deadlock
• Hiểu cách ngăn chặn deadlock
• Hiểu cách tránh deadlock
• Hiểu cách phát hiện deadlock
• Hiểu cách phục hồi từ deadlock

- Sử dụng quy tắc Ngăn chặn (Prevention) hoặc Tránh (Avoidance) để Deadlock không bao giờ xảy ra.
- Cho phép hệ thống bị Deadlock, sau đó Xác định (Detection) và tìm cách Khắc phục (Recover).
- Không xét vấn đề Deadlock, coi như không bao giờ xảy ra, còn nếu xảy ra thì Khởi động lại hệ thống (Cách này có thể có ý nghĩa thực tế vì không cần đưa vào HĐH các phương tiện xử trí thường trực).

còn thiếu gì mong các bạn bổ sung thêm nhé !!!

Định nghĩa Deadlock (Kẹt khoá): 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.

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

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

Chú ý: Bốn điều kiện này không hoàn toàn độc lập với nhau: ví dụ, Điều kiện 4 kéo theo Điều kiện 2.

1 .Định Nghĩa 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.

vd1: 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.
vd2: 5 lớp học điều cần máy chiếu . Trong khi đó phòng thiết bị chỉ có 1 máy chiếu .điều này dẫn tới ranh chấp chữa các lớp dùng máy chiếu .
vd3 : 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

Điều kiện xuất hiện tắc nghẽn :
1 . Có sử dụng tài nguyên không thể chia sẻ .
2. Sự chiếm giữ và yêu cầu tài nguyên thêm .
3. Không thu hồi tài nguyên từ tiến trình đã sử dụng ,
4. Tồn tại 1 chu kỳ trong đồ thị cấp phát tài nguyên .
5. Có 2 tiến trình chờ đợi lẫn nhau : tiến trình này đang chờ được cấp phá tài nguyên đang bị tiến trình kia chiếm giữ và ngược lại .
=> Khi có 4 điều kiện này thì tắc nghẽn xảy ra . Nếu thiếu 1 trong 4 điều kiện trên thì không có tắc nghẽn.

vd : 5 nhà triết học cùng ngồi vào bàn ăn để thưởng hức món mì ý . Để dùng bữa thì mỗi người cần dùng 2 cái nĩa mà trên bàn thì chỉ có 5 nĩa xếp xen kẽ 5 đĩa mì , Vậy nếu 5 người cùng ăn 1 lúc thì sẽ xảy ra hiện tượng tranh chấp gây ra hiện tượng .==> Hiên tượng Deadlock

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

- Deadlock là tình huống kẹt tiến trình (process) với một tập các process bị blocked, mỗi process giữ tài nguyên và đang chờ tài nguyên mà process khác trong tập đang có.

VD1:
- Giả sử hệ thống có 2 files trên đĩa.
- P1 và P2 mỗi process đang mở 1 file và yêu cầu mở file kia.

VD2:
Semaphore A và B, khởi tạo bằng 1


VD3 - Minh hoạ đời thường:


p/s: Link giành cho những bạn giỏi tiếng anh muốn nghiên cứu thêm: Deadlock

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

Thứ tự sử dụng tài nguyên của tiến trình:

1. Yêu cầu (Request): Nếu không được đáp ứng do bị tiến trình khác giữ => tiến trình phải chờ.

2. Sử dụng (Use): Sau khi được cấp phát, tiến trình thao tác với tài nguyên (thực hiệnI/O, in ra giấy, ...).

3. Trả lại (Release): Trả tài nguyên cho HĐH quản lý.

- 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 kỳ khép kín các yêu cầu tài nguyê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.

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.

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

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:
1/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.

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

Trạng thái deadlock xảy ra khi hai hay nhiều quá trình đang chờ không xác định
một sự kiện mà có thể được gây ra chỉ bởi một trong những quá trình đang chờ. Về
nguyên tắc, có ba phương pháp giải quyết deadlock:
• Sử dụng một số giao thức để ngăn chặn hay tránh deadlock, đả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, phát hiện và sau đó phục hồi.
• Bỏ qua vấn đề deadlock và giả vờ deadlock chưa bao giờ xảy ra trong hệ
thống. Giải pháp này là một giải pháp được dùng bởi hầu hết các hệ điều
hành bao gồm UNIX.
Trường hợp deadlock có thể xảy ra nếu và chỉ nếu bốn điều kiện cần xảy ra
cùng một lúc trong hệ thống: loại trừ hỗ tương, giữ và chờ cấp thêm tài nguyên,
không đòi lại tài nguyên, và tồn tại chu trình trong đồ thị cấp phát tài nguyên. Để ngăn
chặn deadlock, chúng ta đảm bảo rằng ít nhất một điều kiện cần không bao giờ xảy ra.

Khi nào thì chúng ta nên nạp giải thuật phát hiện deadlock? Câu trả lời phụ thuộc
vào hai yếu tố:
1) Deadlock có khả năng xảy ra thường xuyên như thế nào?
2) Bao nhiêu quá trình sẽ bị ảnh hưởng bởi deadlock khi nó sẽ ra?

Nếu deadlock xảy ra thường xuyên thì giải thuật phát hiện nên được nạp lên
thường xuyên. Những tài nguyên được cấp phát để các quá trình bị deadlock sẽ rảnh
cho đến khi deadlock có thể bị phá vỡ. Ngoài ra, số lượng quá trình liên quan trong
chu trình deadlock có thể tăng lên.

Deadlock xảy ra chỉ khi một số quá trình thực hiện yêu cầu mà không được cấp tài
nguyên tức thì. Yêu cầu này có thể là yêu cầu cuối hoàn thành một chuỗi các quá trình
đang yêu cầu. Ngoài ra, chúng ta có thể nạp giải thuật phát hiện mọi khi một yêu cầu
cho việc cấp phát không thể được cấp tức thì. Trong trường hợp này, chúng ta không
chỉ định nghĩa tập hợp các quá trình bị deadlock, mà còn xác định quá trình đã gây ra
deadlock. (Trong thực tế, mỗi quá trình trong suốt quá trình bị deadlock là một liên
kết trong chu trình của đồ thị tài nguyên, vì thế tất cả chúng gây ra deadlock). Nếu có
nhiều loại tài nguyên khác nhau, một yêu cầu có thể gây chu trình trong đồ thị tài
nguyên, mỗi chu trình hoàn thành bởi yêu cầu mới nhất và “được gây ra” bởi một quá
trình có thể xác định.

Dĩ nhiên, nạp giải thuật phát hiện deadlock cho mỗi yêu cầu có thể gây ra một
chi phí có thể xem xét trong thời gian tính toán. Một thay đổi ít đắt hơn là nạp giải
thuật tại thời điểm ít thường xuyên hơn- ví dụ, một lần một giờ hay bất cứ khi nào
việc sử dụng CPU rơi xuống thấp hơn 40%. Nếu giải thuật phát hiện deadlock được
nạp trong những thời điểm bất kỳ, thì có nhiều chu trình trong đồ thị tài nguyên.
Chúng ta không thể nói quá trình nào của nhiều quá trình bị deadlock gây ra deadlock

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

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.

Để ngăn chặn Deadlock ta phải làm sao cho ít nhất 1 trong 4 điều kiện dẫn đến Deadlock không xảy ra. Cụ thể:

- Với Mutual Exclusion: Đảm bảo TN nào cũng dùng chung được cùng một lúc bởi nhiều tiếntrì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ếmquyề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.

Deadlock : Là Một số tiến trình có thể tranh nhau bởi một số tài nguyên hạn chế.

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 tiến trình chờ có thể sẽ không bao giờ thay đổi lại trạng thái được vì các tài nguyên mà nó yêu cầu bị giữ bởi các tiến trình chờ khác.

+ Mỗi tiến trình sử dụng tài nguyên theo các bước sau:
• yêu cầu tài nguyên(request): Nếu yêu cầu không được giải quyết ngay( ví dụ khi tài nguyên đang được tiến trình khác sử dụng) thì tiến trình yêu cầu phải đợi cho đến khi nhận được tài nguyên.
• Sử dụng tài nguyên(use)
• Trả lại(Release): Trả tài nguyên cho HĐH quản lý.

ví dụ: Hiện tượng tắc nghẽn trên cầu:
+ Hai (hay nhiều hơn) ô tô đối đầu nhau trên một cây cầu hẹp chỉ đủ độ rộng cho một chiếc.
+ Mỗi đoạn của cây cầu 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 một hay một số ô tô lùi lại nhường đường rồi tiển ra sau. deadlock là kẹt mãi mãi

Deadlock và các ví dụ minh họa hiện tượng này.
- Định nghĩa Deadlock (Kẹt khoá): 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.
- Deadlock là tình huống xuất hiện khi hai hay nhiều “hành động” phải chờ một hoặc nhiều hành động khác để kết thúc, nhưng không bao giờ thực hiện được Máy tính: Bế tắc là tình huống xuất hiện khi hai tiến trình phải chờ đợi nhau giải phóng tài nguyên hoặc nhiều tiến trình chờ sử dụng các tài nguyên theo một “vòng tròn.
+ Yêu cầu tài nguyên.
+ Sử dụng tài nguyên.
+ Trả lại tài nguyên.

Các VD minh họa:
vd1: Hiện tượng deadlock xảy ra trên 1 cây cầu mà ở giữa cầu có 1 đoạn cầu rất hẹp ( tại 1 thời điểm chỉ duy nhất 1 xe đi qua cầu). Khi các ô tô duy chuyển trên cầu và đi qua đoạn cầu hẹp, tại 1 thời điểm cả 2 đều đi ngang đoạn giữa cầu hẹp và cả 2 xe đều kẹp ở giữa cầu => Xuất hiện deadlock (Trên thực tế chẳng có ai chịu nhường đường cả.)
vd2: 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) vd này đơn giản dể hiểu và dể nhớ Razz .
Phương pháp xử lý deadlock :
- Sử dụng 1 giao thức để hệ thống không bao giờ rơi vào trạng thái deadlock (Ngăn chặn bế tắc, tránh bế tắc ).
- Có thể cho phép hệ thống bị deadlock, phát hiện deadlock và xử lý deadlock đó.
- Bỏ qua deadlock, xem như deadlock chẳng bao giờ xuất hiện trong hệ thống (dùng nhiều trong windows và Unix).
Giải pháp chặn deadlock : 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 (Mutual Exclusion).
+ Giữ và chờ (Hold and Wait).
+ Không có tiếm quyền (No Preemption).
+ Chờ xoay vòng (Circular Wait).

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 đó