Giáo trình Nguyên lý hệ điều hành (Phần 1)

 SLEEP and WAKEUP 
int busy; // 1 nếu miền găng đang bị chiếm, nếu không là 0 
int blocked; // đếm số lượng tiến trình đang bị khóa 
while (TRUE) { 
if (busy){ 
blocked = blocked + 1; 
sleep(); 
} 
else busy = 1; 
critical-section (); 
busy = 0; 
if(blocked){ 
wakeup(process); 
blocked = blocked - 1; 
} 
 59
Noncritical-section (); 
} 
Khi sử dụng SLEEP và WAKEUP cần hết sức cẩn thận, nếu không muốn xảy 
ra tình trạng mâu thuẫn truy xuất trong một vài tình huống đặc biệt như sau : giả sử 
tiến trình A vào miền găng, và trước khi nó rời khỏi miền găng thì tiến trình B được 
kích hoạt. Tiến trình B thử vào miền găng nhưng nó nhận thấy A đang ở trong đó, do 
vậy B tăng giá trị biến blocked và chuẩn bị gọi SLEEP để tự khoá. Tuy nhiên trước khi 
B có thể thực hiện SLEEP, tiến trình A lại được tái kích hoạt và ra khỏi miền găng. 
Khi ra khỏi miền găng A nhận thấy có một tiến trình đang chờ (blocked=1) nên gọi 
WAKEUP và giảm giá trị của blocked. Khi đó tín hiệu WAKEUP sẽ lạc mất do tiến 
trình B chưa thật sự « ngủ » để nhận tín hiệu đánh thức !Khi tiến trình B được tiếp tục 
xử lý, nó mới goi SLEEP và tự khó vĩnh viễn ! 
Vấn đề ghi nhận được là tình trạng lỗi này xảy ra do việc kiểm tra tư cách vào 
miền găng và việc gọi SLEEP hay WAKEUP là những hành động tách biệ, có thể bị 
ngắt nửa chừng trong quá trình xử lý, do đó có khi tín hiệu WAKEUP gởi đến một tiến 
trình chưa bị khóa sẽ lạc mất. 
Để tránh những tình huống tương tự, hệ điều hành cung cấp những cơ chế đồng 
bộ hóa dựa trên ý tưởng của chiến lược « SLEEP and WAKEUP » nhưng được xây 
dựng bao hàm cả phương tiện kiểm tra điều kiện vào miền găng giúp sử dụng an toàn. 
a). Semaphore 
Tiếp cận: Được Dijkstra đề xuất vào 1965, một semaphore s là một biến có các 
thuộc tính sau: 
Một giá trị nguyên dương e(s) 
Một hàng đợi f(s) lưu danh sách các tiến trình đang bị khóa (chờ) trên 
semaphore s 
Chỉ có hai thao tác được định nghĩa trên semaphore 
Down(s): giảm giá trị của semaphore s đi 1 đơn vị nếu semaphore có trị e(s) > 
0, và tiếp tục xử lý. Ngược lại, nếu e(s)  0, tiến trình phải chờ đến khi e(s) >0. 
 60
Up(s): tăng giá trị của semaphore s lên 1 đơn vị. Nếu có một hoặc nhiều tiến 
trình đang chờ trên semaphore s, bị khóa bởi thao tác Down, thì hệ thống sẽ chọn một 
trong các tiến trình này để kết thúc thao tác Down và cho tiếp tục xử lý. 
Hình 2.17 Semaphore s 
Cài đặt: Gọi p là tiến trình thực hiện thao tác Down(s) hay Up(s). 
Down(s): 
e(s) = e(s) - 1; 
if e(s) < 0 { 
status(P)= blocked; 
enter(P,f(s)); 
} 
Up(s): 
e(s) = e(s) + 1; 
if s  0 { 
exit(Q,f(s)); //Q là tiến trình đang chờ trên s 
status (Q) = ready; 
enter(Q,ready-list); 
} 
Lưu ý cài đặt này có thể đưa đến một giá trị âm cho semaphore, khi đó trị tuyệt 
đối của semaphore cho biết số tiến trình đang chờ trên semaphore. 
 61
Điều quan trọng là các thao tác này cần thực hiện một cách không bị phân chia, 
không bị ngắt nữa chừng, có nghĩa là không một tiến trình nào được phép truy xuất 
đến semaphore nếu tiến trình đang thao tác trên semaphore này chưa kết thúc xử lý 
hay chuyển sang trạng thái blocked. 
Sử dụng: có thể dùng semaphore để giải quyết vấn đề truy xuất độc quyền hay 
tổ chức phối hợp giữa các tiến trình. 
Tổ chức truy xuất độc quyền với Semaphores: khái niệm semaphore cho phép 
bảo đảm nhiều tiến trình cùng truy xuất đến miền găng mà không có sự mâu thuẫn truy 
xuất. n tiến trình cùng sử dụng một semaphore s, e(s) được khởi gán là 1. Để thực hiện 
đồng bộ hóa, tất cả các tiến trình cần phải áp dụng cùng cấu trúc chương trình sau đây: 
while (TRUE) { 
Down(s) 
critical-section (); 
Up(s) 
Noncritical-section (); 
} 
Hình 3.11 Cấu trúc một chương trình trong giải pháp semaphore 
Ví dụ: 
Lần Tiến 
trình 
Thao 
tác 
E(s) CS F(s) 
1 A Down 0 A 
2 B Down -1 A B 
3 C Down -2 A B, C 
4 A Up -1 B C 
Tổ chức đồng bộ hóa với Semaphores: với semaphore có thể đồng bộ hóa hoạt 
động của hai tiến trình trong tình huống một tiến trình phải đợi một tiến trình khác 
hoàn tất thao tác nào đó mới có thể bắt đầu hay tiếp tục xử lý. Hai tiến trình chia sẻ 
một semaphore s, khởi gán e(s) là 0. Cả hai tiến trình có cấu trúc như sau: 
P1: 
 62
while (TRUE) { 
job1(); 
Up(s); //đánh thức P2 
} 
P2: 
while (TRUE) { 
Down(s); // chờ P1 
job2(); 
} 
Hình 3.12 Cấu trúc chương trình trong giải pháp semaphore 
Nhờ có thực hiện một các không thể phân chia, semaphore đã giải quyết được 
vấn đề tín hiệu "đánh thức" bị thất lạc. Tuy nhiên, nếu lập trình viên vô tình đặt các 
primitive Down và Up sai vị trí, thứ tự trong chương trình, thì tiến trình có thể bị khóa 
vĩnh viễn. 
Ví dụ : while (TRUE) { 
Down(s) 
critical-section (); 
Noncritical-section (); 
} 
tiến trình trên đây quên gọi Up(s), và kết quả là khi ra khỏi miền găng nó sẽ 
không cho tiến trình khác vào miền găng ! 
Vì thế việc sử dụng đúng cách semaphore để đồng bộ hóa phụ thuộc hoàn toàn 
vào lập trình viên và đòi hỏi lập trình viên phải hết sức thận trọng. 
b). Monitors 
Tiếp cận: Để có thể dễ viết đúng các chương trình đồng bộ hóa hơn, 
Hoare(1974) và Brinch & Hansen (1975) đã đề nghị một cơ chế cao hơn được cung 
 63
cấp bởi ngôn ngữ lập trình , là monitor. Monitor là một cấu trúc đặc biệt bao gồm các 
thủ tục, các biến và cấu trúc dữ liệu có các thuộc tính sau : 
Các biến và cấu trúc dữ liệu bên trong monitor chỉ có thể được thao tác bởi các 
thủ tục định nghĩa bên trong monitor đó. (encapsulation). 
Tại một thời điểm, chỉ có một tiến trình duy nhất được hoạt động bên trong một 
monitor (mutual exclusive). 
Trong một monitor, có thể định nghĩa các biến điều kiện và hai thao tác kèm 
theo là Wait và Signal như sau : gọi c là biến điều kiện được định nghĩa trong 
monitor: 
Wait(c): chuyển trạng thái tiến trình gọi sang blocked , và đặt tiến trình này vào 
hàng đợi trên biến điều kiện c. 
Signal(c): nếu có một tiến trình đang bị khóa trong hàng đợi của c, tái kích hoạt 
tiến trình đó, và tiến trình gọi sẽ rời khỏi monitor. 
Hình 2.18 Monitor và các biến điều kiện 
Cài đặt : trình biên dịch chịu trách nhiệm thực hiện việc truy xuất độc quyền 
đến dữ liệu trong monitor. Để thực hiện điều này, một semaphore nhị phân thường 
được sử dụng. Mỗi monitor có một hàng đợi toàn cục lưu các tiến trình đang chờ được 
vào monitor, ngoài ra, mỗi biến điều kiện c cũng gắn với một hàng đợi f(c) và hai thao 
tác trên đó được định nghĩa như sau: 
 64
Wait(c) : 
status(P)= blocked; 
enter(P,f(c)); 
Signal(c) : 
if (f(c) != NULL){ 
exit(Q,f(c)); //Q là tiến trình chờ trên c 
statusQ) = ready; 
enter(Q,ready-list); 
} 
Sử dụng: Với mỗi nhóm tài nguyên cần chia sẻ, có thể định nghĩa một monitor 
trong đó đặc tả tất cả các thao tác trên tài nguyên này với một số điều kiện nào đó.: 
monitor 
condition ; 
; 
 procedure Action1(); 
 { 
 } .... 
 procedure Actionn(); 
 { 
 } 
end monitor; 
Hình 3.14 Cấu trúc một monitor 
Các tiến trình muốn sử dụng tài nguyên chung này chỉ có thể thao tác thông qua 
các thủ tục bên trong monitor được gắn kết với tài nguyên: 
while (TRUE) { 
 65
Noncritical-section (); 
.Actioni; //critical-section(); 
Noncritical-section (); 
} 
Hình 3.15 Cấu trúc tiến trình Pi trong giải pháp monitor 
Với monitor, việc truy xuất độc quyền được bảo đảm bởi trình biên dịch mà 
không do lập trình viên, do vậy nguy cơ thực hiện đồng bộ hóa sai giảm rất nhiều. Tuy 
nhiên giải pháp monitor đòi hỏi phải có một ngôn ngữ lập trình định nghĩa khái niệm 
monitor, và các ngôn ngữ như thế chưa có nhiều. 
c). Trao đổi thông điệp 
Tiếp cận: giải pháp này dựa trên cơ sở trao đổi thông điệp với hai primitive 
Send và Receive để thực hiện sự đồng bộ hóa: 
Send(destination, message): gởi một thông điệp đến một tiến trình hay gởi vào 
hộp thư. 
Receive(source,message): nhận một thông điệp thừ một tiến trình hay từ bất kỳ 
một tiến trình nào, tiến trình gọi sẽ chờ nếu không có thông điệp nào để nhận. 
Sử dụng: Có nhiều cách thức để thực hiện việc truy xuất độc quyền bằng cơ chế 
trao đổi thông điệp. Đây là một mô hình đơn giản: một tiến trình kiểm soát việc sử 
dụng tài nguyên và nhiều tiến trình khác yêu cầu tài nguyên này. Tiến trình có yêu cầu 
tài nguyên sẽ gởi một thông điệp đến tiến trình kiểm soát và sau đó chuyển sang trạng 
thái blocked cho đến khi nhận được một thông điệp chấp nhận cho truy xuất từ tiến 
trình kiểm soát tài nguyên.Khi sử dụng xong tài nguyên , tiến trình gởi một thông điệp 
khác đến tiến trình kiểm soát để báo kết thúc truy xuất. Về phần tiến trình kiểm soát , 
khi nhận được thông điệp yêu cầu tài nguyên, nó sẽ chờ đến khi tài nguyên sẵn sàng để 
cấp phát thì gởi một thông điệp đến tiến trình đang bị khóa trên tài nguyên đó để đánh 
thức tiến trình này. 
while (TRUE) { 
Send(process controler, request message); 
Receive(process controler, accept message); 
critical-section (); 
 66
Send(process controler, end message); 
Noncritical-section (); 
} 
Hình 3.16 Cấu trúc tiến trình yêu cầu tài nguyên trong giải pháp message 
Các primitive semaphore và monitor có thể giải quyết được vấn đề truy xuất 
độc quyền trên các máy tính có một hoặc nhiều bộ xử lý chia sẻ một vùng nhớ chung. 
Nhưng các primitive không hữu dụng trong các hệ thống phân tán, khi mà mỗi bộ xử 
lý sỡ hữu một bộ nhớ riêng biệt và liên lạc thông qua mạng. Trong những hệ thống 
phân tán như thế, cơ chế trao đổi thông điệp tỏ ra hữu hiệu và được dùng để giải quyết 
bài toán đồng bộ hóa. 
2.5. Tắc nghẽn (Deadlock) 
2.5.1. Định nghĩa: 
Một tập hợp các tiến trình được định nghĩa ở trong tình trạng tắc nghẽn khi mỗi 
tiến trình trong tập hợp đều chờ đợi một sự kiện mà chỉ có một tiến trình khác trong 
tập hợp mới có thể phát sinh được. 
Nói cách khác, mỗi tiến trình trong tập hợp đều chờ được cấp phát một tài 
nguyên hiện đang bị một tiến trình khác cũng ở trạng thái blocked chiếm giữ. Như vậy 
không có tiến trình nào có thể tiếp tục xử lý , cũng như giải phóng tài nguyên cho tiến 
trình khác sử dụng, tất cả các tiến trình trong tập hợp đều bị khóa vĩnh viễn ! 
2.5.2. Điều kiện xuất hiện tắc nghẽn 
Coffman, Elphick và Shoshani đã đưa ra 4 điều kiện cần có thể làm xuất hiện 
tắc nghẽn: 
Có sử dụng tài nguyên không thể chia sẻ (Mutual exclusion): Mỗi thời điểm, 
một tài nguyên không thể chia sẻ được hệ thống cấp phát chỉ cho một tiến trình , khi 
tiến trình sử dụng xong tài nguyên này, hệ thống mới thu hồi và cấp phát tài nguyên 
cho tiến trình khác. 
Sự chiếm giữ và yêu cầu thêm tài nguyên (Wait for): Các tiến trình tiếp tục 
chiếm giữ các tài nguyên đã cấp phát cho nó trong khi chờ được cấp phát thêm một số 
tài nguyên mới. 
 67
Không thu hồi tài nguyên từ tiến trình đang giữ chúng (No preemption): Tài 
nguyên không thể được thu hồi từ tiến trình đang chiếm giữ chúng trước khi tiến trình 
này sủ dụng chúng xong. 
Tồn tại một chu kỳ trong đồ thị cấp phát tài nguyên ( Circular wait): 
một tập hợp các tiến 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 giữ bởi Pn 
Pn đang chờ tài nguyên đang giữ bởi P0 
4 điều kiện không hoàn toàn độc lập, các điều kiện là có phụ thuộc lẫn nhau. 
Khi có đủ 4 điều kiện này, thì tắc nghẽn xảy ra. Nếu thiếu một trong 4 điều kiện 
trên thì không có tắc nghẽn. 
Khi có đủ 4 điều kiện này, thì tắc nghẽn xảy ra. Nếu thiếu một trong 4 điều kiện 
trên thì không có tắc nghẽn. 
Có thể sử dụng một đồ thị để mô hình hóa việc cấp phát tài nguyên. Đồ thị này 
có 2 loại nút : các tiến trình được biễu diễn bằng hình tròn, và mỗi tài nguyên được 
hiển thị bằng hình vuông 
Hình 2.19 Đồ thị cấp phát tài nguyên 
2.5.3. Các phương pháp xử lý tắc nghẽn 
 68
Chủ yếu có ba hương tiếp cận để xử lý tắc nghẽn : 
- Sử dụng một vài giao thức (protocol) để bảo đảm rằng hệ thống không bao giờ 
xảy ra tắc nghẽn. 
HĐH không có khả năng chống Deadlock 
Lý do dung phương pháp này: 
Do xác suất xảy ra đealock nhỏ 
Giải quyết deadlock đòi hỏi chi phí cao 
Xử lý bằng tay do người quản trị hệ thống làm. 
Đây là giải pháp của hầu hết các hệ điều hành hiện nay. 
- Cho phép xảy ra tắc nghẽn và tìm cách sữa chữa tắc nghẽn. 
- Hoàn toàn 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. 
2.5.4 Ngăn chặn tắc nghẽn 
Để tắc nghẽn không xảy ra, cần bảo đảm tối thiểu một trong 4 điều kiện cần 
không xảy ra: 
Tài nguyên không thể chia sẻ : nhìn chung 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. Tuy nhiên đối với một số tài nguyên 
về kết xuất, người ta có thể dùng các cơ chế spooling để biến đổi thành tài nguyên có 
thể chia sẻ. 
Sự chiếm giữ và yêu cầu thêm tài nguyên: phải bảo đảm rằng mỗi khi tiến trình 
yêu cầu thêm một tài nguyên thì nó không chiếm giữ các tài nguyên khác. Có thể áp 
đặt một trong hai cơ chế truy xuất 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 bắt đầu xử lý . 
=> phương pháp này có khó khăn là tiến trình khó có thể ước lượng chính xác 
tài nguyên cần sử dụng vì có thể nhu cầu phụ thuộc vào quá trình xử lý . Ngoài ra nếu 
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ả. 
 69
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 làm phát sinh các khó khăn trong việc bảo vệ tính toàn 
vẹn dữ liệu của hệ thống. 
Không thu hồi tài nguyê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 . 
Tồn tại một chu kỳ: tránh tạo chu kỳ trong đồ thị bằng cách 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 phân cấp từ 1-N. 
Ví dụ : F(đĩa) = 2, F(máy in) = 12 
Các tiến trình khi yêu cầu tài nguyên phải tuân thủ quy định : 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). 
2.5.5. Tránh tắc nghẽn 
Ngăn cản tắc nghẽn là một mối bận tâm lớn khi sử dụng tài nguyên. Tránh tắc 
nghẽn là loại bỏ tất cả các cơ hội có thể dẫn đến tắc nghẽn trong tương lai. Cần phải sử 
dụng những cơ chế phức tạp để thực hiện ý định này. 
Một số khái niệm cơ sở 
Trạng thái an toàn : trạng thái A là an toàn nếu hệ thống có thể thỏa mãn các 
nhu cầu tài nguyên (cho đến tối đa) của mỗi tiến trình theo một thứ tự nào đó mà vẫn 
ngăn chặn được tắc nghẽn. 
Một chuỗi cấp phát an toàn: một thứ tự của các tiến trình là an 
toàn đối với tình trạng cấp phát hiện hành nếu với mỗi tiến trình Pi nhu cầu tài nguyên 
của Pi có thể được thỏa mãn với các tài nguyên còn tự do của hệ thống, cộng với các 
tài nguyên đang bị chiếm giữ bởi các tiến trình Pj khác, với j<i. 
 70
Một trạng thái an toàn không thể là trạng thái tắc nghẽn. Ngược lại một trạng 
thái không an toàn có thể dẫn đến tình trạng tắc nghẽn. 
Chiến lược cấp phát : chỉ thỏa mãn yêu cầu tài nguyên của tiến trình khi trạng 
thái kết quả là an toàn! 
Giải thuật xác định trạng thái an toàn 
Cần sử dụng các cấu trúc dữ liệu sau : 
int Available[NumResources]; 
/* Available[r]= số lượng các thể hiện còn tự do của tài nguyên r*/ 
int Max[NumProcs, NumResources]; 
/*Max[p,r]= nhu cầu tối đa của tiến trình p về tài nguyên r*/ 
int Allocation[NumProcs, NumResources]; 
/* Allocation[p,r] = số lượng tài nguyên r thực sự cấp phát cho p*/ 
int Need[NumProcs, NumResources]; 
/* Need[p,r] = Max[p,r] - Allocation[p,r]*/ 
1.Giả sử có các mảng 
int Work[NumProcs, NumResources] = Available; 
int Finish[NumProcs] = false; 
2.Tìm i sao cho 
Finish[i] == false 
Need[i] <= Work[i] 
Nếu không có i như thế, đến bước 4. 
3. Work = Work + Allocation[i]; 
 Finish[i] = true; 
 71
 Đến bước 2 
4.Nếu Finish[i] == true với mọi i, thì hệ thống ở trạng thái an toàn. 
Ví dụ : Giả sử tình trạng hiện hành của hệ thống được mô tả như sau : 
Max Allocation Available 
R1 R2 R3 R1 R2 R3 R1 R2 R3 
P1 3 2 2 1 0 0 
P2 6 1 3 2 1 1 
P3 3 1 4 2 1 1 
P4 4 2 2 0 0 2 
Nếu tiến trình P2 yêu cầu 4 cho R1, 1 cho R3. hãy cho biết yêu cầu này có thể 
đáp ứng mà bảo đảm không xảy ra tình trạng deadlock hay không ? Nhận thấy 
Available[1] =4, Available[3] =2 đủ để thõa mãn yêu cầu của P2, ta có 
Need Allocation Available 
R1 R2 R3 R1 R2 R3 R1 R2 R3 
P1 2 2 2 1 0 0 
P2 0 0 1 6 1 2 
P3 1 0 3 2 1 1 
P4 4 2 0 0 0 2 
Need Allocation Available 
R1 R2 R3 R1 R2 R3 R1 R2 R3 
P1 2 2 2 1 0 0 
P2 0 0 0 0 0 0 
P3 1 0 3 2 1 1 
P4 4 2 0 0 0 2 
Need Allocation Available 
R1 R2 R3 R1 R2 R3 R1 R2 R3 
P1 0 0 0 0 0 0 
P2 0 0 0 0 0 0 
P3 1 0 3 2 1 1 
P4 4 2 0 0 0 2 
Need Allocation Available 
R1 R2 R3 R1 R2 R3 R1 R2 R3 
 72
P1 0 0 0 0 0 0 
P2 0 0 0 0 0 0 
P3 0 0 0 0 0 0 
P4 4 2 0 0 0 2 
Need Allocation Available 
R1 R2 R3 R1 R2 R3 R1 R2 R3 
P1 0 0 0 0 0 0 
P2 0 0 0 0 0 0 
P3 0 0 0 0 0 0 
P4 0 0 0 0 0 0 
Trạng thái kết qủa là an toàn, có thể cấp phát. 
Giải thuật yêu cầu tài nguyên 
Giả sử tiến trình Pi yêu cầu k thể hiện của tài nguyên r. 
1.Nếu k <= Need[i], đến bước 2 
Ngược lại, xảy ra tình huống lỗi 
2.Nếu k <= Available[i],đến bước 3 
Ngược lại, Pi phải chờ 
3.Giả sử hệ thống đã cấp phát cho Pi các tài nguyên mà nó yêu cầu và cập nhật 
tình trạng hệ thống như sau: 
Available[i] = Available[i] - k; 
Allocation[i]= Allocation[i]+ k; 
Need[i] = Need[i] - k; 
Nếu trạng thái kết quả là an toàn, lúc này các tài nguyên trên sẽ được cấp phát 
thật sự cho Pi 
Ngược lại, Pi phải chờ 
Phát hiện tắc nghẽn 
Cần sử dụng các cấu trúc dữ liệu sau : 
 73
int Available[NumResources]; 
// Available[r]= số lượng các thể hiện còn tự do của tài nguyên r 
int Allocation[NumProcs, NumResources]; 
// Allocation[p,r] = số lượng tài nguyên r thực sự cấp phát cho p 
int Request[NumProcs, NumResources]; 
// Request[p,r] = số lượng tài nguyên r tiến trình p yêu cầu thêm 
Giải thuật phát hiện tắc nghẽn 
1. int Work[NumResources] = Available; 
 int Finish[NumProcs]; 
for (i = 0; i < NumProcs; i++) 
 Finish[i] = (Allocation[i] == 0); 
2. Tìm i sao cho 
Finish[i] == false 
 Request[i] <= Work 
Nếu không có i như thế, đến bước 4. 
 3. Work = Work + Allocation[i]; 
Finish[i]= true; 
Đến bước 2 4. Nếu Finish[i] == true với mọi i, 
thì hệ thống không có tắc nghẽn 
Nếu Finish[i] == false với một số giá trị i, 
 thì các tiến trình mà Finish[i] == false sẽ ở trong tình trạng tắc nghẽn. 
2.5.6. Hiệu chỉnh tắc nghẽn 
 74
Khi đã phát hiện được tắc nghẽn, có hai lựa chọn chính để hiệu chỉnh tắc nghẽn 
: 
Đình chỉ hoạt động của các tiến trình liên quan 
Cách tiếp cận này dựa trên việc thu hồi lại các tài nguyên của những tiến trình 
bị kết thúc. Có thể sử dụng một trong hai phương pháp sau : 
Đình chỉ tất cả các tiến trình trong tình trạng tắc nghẽn 
Đình chỉ từng tiến trình liên quan cho đến khi không còn chu trình gây tắc 
nghẽn : để chọn được tiến trình thích hợp bị đình chỉ, phải dựa vào các yếu tố như độ 
ưu tiên, thời gian đã xử lý, số lượng tài nguyên đang chiếm giữ , số lượng tài nguyên 
yêu cầu... 
Thu hồi tài nguyên 
Có thể hiệu chỉnh tắc nghẽn bằng cách thu hồi một số tài nguyên từ các tiến 
trình và cấp phát các tài nguyên này cho những tiến trình khác cho đến khi loại bỏ 
được chu trình tắc nghẽn. Cần giải quyết 3 vấn đề sau: 
Chọn lựa một nạn nhân: tiến trình nào sẽ bị thu hồi tài nguyên ? và thu hồi 
những tài nguyên nào ? 
Trở lại trạng thái trước tắc nghẽn: khi thu hồi tài nguyên của một tiến trình, cần 
phải phục hồi trạng thái của tiến trình trở lại trạng thái gần nhất trước đó mà không 
xảy ra tắc nghẽn. 
Tình trạng « đói tài nguyên »: làm sao bảo đảm rằng không có một tiến trình 
luôn luôn bị thu hồi tài nguyên ?