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

ck mà chúng ta xem xét 
sau đây có thể áp dụng cho hệ thống này. Giải thuật thực hiện nhiều cấu trúc dữ liệu 
thay đổi theo thời gian tương tự như được sử dụng trong giải thuật Banker. 
- Available: một vector có chiều dài m thể hiện số lượng tài nguyên còn rỗi có 
của mỗi loại. 
- Allocation: ma trận nxm định nghĩa số lượng thể hiện của mỗi loại tài 
nguyên đã được cấp phát. 
- Request: ma trận nxm thể hiện yêu cầu tài nguyên hiện tại của mỗi tiến trình. 
Nếu Request[i,j] = k, thì tiến trình Pi đang yêu cầu thêm k thể hiện của loại tài nguyên 
Rj. 
Quan hệ ≤ giữa hai vectors được định nghĩa tương tự như trong giải thuật 
Banker. Để ký hiệu đơn giản, chúng ta sẽ xem những hàng trong ma trận Allocation 
và Request như các vector, và sẽ tham chiếu chúng như Allocationi và Requesti tương 
ứng. Giải thuật phát hiện deadlock được mô tả ở đây sẽ xem xét mọi thứ tự cấp phát 
có thể thực hiện được đối với các tiến trình chưa thực hiện xong công việc để hoàn 
thành được công việc. 
Bước 1) Gọi Work và Finish là các vector có chiều dài m và n tương ứng. 
Khởi tạo Work:=Available với i = 1, 2, , n 
Nếu Allocationi ≠ 0, thì Finish[i]:= false; ngược lại Finish[i]:= true. 
Bước 2) Tìm chỉ số i thỏa: 
a) Finish[i] = false 
146 
b) Request i ≤ Work. 
Nếu không có i nào thỏa, chuyển tới bước 4 
Bước 3) Work:=Work + Allocationi 
Finish[i] := true 
Chuyển về bước 2 
Bước 4) Nếu có Finish[i] = false, với 1 ≤ i ≤ n thì hệ thống đang ở trạng thái 
deadlock. Ngoài ra, nếu Finish[i] = false thì tiến trình Pi bị deadlock. 
Câu hỏi đặt ra là tại sao chúng ta trả lại tài nguyên của tiến trình Pi (trong bước 
3) ngay sau khi chúng ta xác định rằng Requesti ≤ Work (trong bước 2b). Chúng ta 
biết rằng Pi hiện tại không liên quan deadlock (vì Requesti ≤ Work). Do đó, chúng ta 
lạc quan và khẳng định rằng Pi sẽ không yêu cầu thêm tài nguyên nữa để hoàn thành 
công việc của nó; do đó tiến trình Pi sẽ trả lại tất cả tài nguyên hiện đang được cấp 
phát cho hệ thống. Nếu giả định trên của chúng ta không đúng, deadlock có thể xảy ra 
sao đó. Deadlock sẽ được phát hiện tại thời điểm kế tiếp mà giải thuật phát hiện 
deadlock được nạp. 
Để minh hoạ giải thuật này, chúng ta xét hệ thống với 5 tiến trình P0 đến P4 và 
3 loại tài nguyên A, B, C. Loại tài nguyên A có 7 thể hiện, loại tài nguyên B có 2 thể 
hiện và loại tài nguyên C có 6 thể hiện. Giả sử rằng tại thời điểm T0, chúng ta có 
trạng thái cấp phát tài nguyên sau: 
Chúng ta khẳng định rằng hệ thống không ở trong trạng thái deadlock. Thật 
vậy, nếu chúng ta thực hiện giải thuật, chúng ta sẽ tìm ra thứ tự 
sẽ dẫn đến trong Finish[i] = true cho tất cả i. 
Bây giờ giả sử rằng tiến trình P2 thực hiện yêu cầu thêm thể hiện loại C. Ma 
trận yêu cầu như sau: 
147 
Chúng ta khẳng định rằng hệ thống hiện tại bị deadlock. Mặc dù chúng ta có 
thể đòi lại tài nguyên được giữ bởi tiến trình P0, số lượng tài nguyên sẵn dùng không 
đủ để hoàn thành các yêu cầu của các tiến trình còn lại. Do đó, deadlock tồn tại và các 
tiến trình P1, P2, P3, P4 gây ra deadlock. 
3) Sử dụng giải thuật phát hiện deadlock 
Khi nào thì chúng ta nên thực hiện giải thuật phát hiện deadlock? Câu trả lời 
phụ thuộc vào hai yếu tố: 
1) Mức độ thường xuyên xảy ra deadlock của hệ thống? 
2) Bao nhiêu tiến trình sẽ bị ảnh hưởng nếu deadlock xảy ra? 
Nếu deadlock xảy ra thường xuyên thì giải thuật phát hiện nên được thực hiện 
thường xuyên. Những tài nguyên được cấp phát cho các tiến trình bị deadlock chỉ 
được thu hồi cho đến khi deadlock bị phá vỡ. Ngoài ra, số lượng tiến trình liên quan 
trong chu trình deadlock có thể tăng lên nếu không kiểm tra deadlock thường xuyên. 
Deadlock xảy ra chỉ khi một số tiến trình yêu cầu tài nguyên nhưng không 
được cấp phát. 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 tiến trình 
đang yêu cầu. Ngoài ra, chúng ta có thể thực hiện giải thuật phát hiện deadlock khi 
một yêu cầu cấp phát không thể thực hiện tức thì. Trong trường hợp này, chúng ta 
không chỉ kết luận hệt hống có bị deadlock hay không, mà còn xác định tiến trình đã 
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 tiến trình có thể xác định. 
Khi thực hiện 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. Có thể thực hiện giải thuật ít thường 
xuyên hơn (thí dụ như một lần trong một giờ hay bất cứ khi nào hiệu suất sử dụng 
CPU thấp hơn 40%). 
148 
2.4.6 Khôi phục từ bế tắc 
Khi giải thuật phát hiện xác định rằng deadlock tồn tại, cần phải phụ hồi hệ 
thống từ trạng thái deadlock. Có thể thực hiện phục hồi bằng cách thông báo tới 
người điều hành là hệ thống đang bị deadlock và để người điều hành giải quyết 
deadlock thủ công. Một phương pháp giải quyết khác là để hệ thống tự động phục 
hồi. Có hai cách để phá vỡ deadlock. Một cách đơn giản là huỷ bỏ một hay nhiều tiến 
trình để phá vỡ việc tồn tại chu trình trong đồ thị cấp phát tài nguyên. Cách thứ hai là 
lấy lại một số tài nguyên từ một hay nhiều tiến trình bị deadlock. 
1) Kết thúc tiến trình 
Để xóa deadlock bằng cách hủy bỏ tiến trình, chúng ta dùng một trong hai 
phương pháp. Trong cả hai phương pháp, hệ thống lấy lại tài nguyên được cấp phát 
đối với tiến trình bị kết thúc. 
- Huỷ bỏ tất cả tiến trình bị deadlock: phương pháp này rõ ràng sẽ phá vỡ 
các chu trình gây deadlock, nhưng chi phí cao; các tiến trình này có thể đã tính toán 
trong thời gian dài, và các kết quả của các tính toán từng phần này bị huỷ bỏ và có thể 
phải tính lại sau đó. 
- Hủy bỏ lần lượt từng tiến trình cho đến khi chu trình gây deadlock bị 
xóa: phương pháp này chịu chi phí có thể xem xét vì sau khi mỗi tiến trình bị hủy bỏ, 
một giải thuật phát hiện deadlock phải được nạp lên để xác định có tiến trình nào vẫn 
đang bị deadlock. 
Hủy bỏ tiến trình có thể không dễ. Nếu một tiến trình đang ở giữa giai đoạn 
cập nhật một tập tin, kết thúc nó sẽ để tập tin đó trong trạng thái không phù hợp. 
Tương tự, nếu tiến trình đang ở giữa giai đoạn in dữ liệu ra máy in, hệ thống phải 
khởi động lại trạng thái đúng trước khi in công việc tiếp theo. 
Nếu phương pháp kết thúc một phần được dùng thì với một tập hợp các tiến 
trình deadlock được cho, chúng ta phải xác định tiến trình nào (hay các tiến trình nào) 
nên được kết thúc để phá vỡ deadlock. Việc xác định này là một quyết định chính 
sách tương tự như các vấn đề lập thời biểu CPU. Nhiều yếu tố có thể xác định tiến 
trình nào được chọn để huỷ bỏ như: 
1) Độ ưu tiên của tiến trình 
149 
2) Tiến trình đã được tính toán bao lâu và bao lâu nữa tiến trình sẽ tính toán 
trước khi hoàn thành công việc của nó. 
3) Loại và số lượng tài nguyên mà tiến trình đang sử dụng. 
4) Số lượng tài nguyên cần thêm để tiến trình hoàn thành công việc 
5) Bao nhiêu tiến trình sẽ cần được kết thúc. 
6) Tiến trình là giao tiếp hay dạng bó 
2) Lấy lại tài nguyên 
Để xóa deadlock, có thể đòi một số tài nguyên đã cấp cho các tiến trình và cấp 
lại các tài nguyên này cho các tiến trình khác, thực hiẹn cho đến khi chu trình 
deadlock bị phá vỡ. 
Để đòi lại tài nguyên nhằm giải quyết deadlock, có ba vấn đề cần được xác 
định: 
- Chọn tiến trình: những tài nguyên nào và những tiến trình nào bị đòi lại? 
Trong khi kết thúc tiến trình, chúng ta phải xác định thứ tự đòi lại để tối thiểu chi phí. 
Các yếu tố chi phí có thể gồm các tham số như số lượng tài nguyên mà một tiến trình 
deadlock đang giữ, và lượng thời gian một tiến trình deadlock sử dụng. 
- Trở lại trạng thái trước deadlock: Nếu chúng ta đòi lại tài nguyên từ một 
tiến trình, điều gì nên được thực hiện với tiến trình đó? Rõ ràng, nó không thể tiếp tục 
việc thực hiện bình thường; nó đang bị mất một số tài nguyên được yêu cầu. Chúng ta 
phải phục hồi tiến trình tới trạng thái an toàn và khởi động lại từ trạng thái gần nhất 
trước đó. 
Thông thường, rất khó để xác định trạng thái nào là an toàn vì thế giải pháp 
đơn giản nhất là phục hồi toàn bộ: hủy tiến trình và sau đó khởi động lại nó. 
Như vậy, trạng thái deadlock xảy ra khi hai hay nhiều tiến 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 tiến 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. 
150 
- Bỏ qua vấn đề deadlock và coi như deadlock không 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 nhiều hệ điều hành trong đó có 
UNIX. 
Trường hợp deadlock có thể xảy ra khi và chỉ khi bốn điều kiện cần xảy ra 
cùng một lúc trong hệ thống: loại trừ lẫn nhau, 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 xảy ra. 
Một phương pháp để phòng tránh deadlock mà ít nghiêm ngặt hơn giải thuật 
ngăn chặn deadlock là có thông tin trước về mỗi tiến trình sẽ đang dùng tài nguyên 
như thế nào. Thí dụ, giải thuật Banker cần biết số lượng tối đa của mỗi lớp tài nguyên 
có thể được yêu cầu bởi mỗi tiến trình. Sử dụng thông tin này chúng ta có thể thực 
hiện giải thuật tránh deadlock. 
Nếu hệ thống không thực hiện một giao thức để đảm bảo rằng deadlock sẽ 
không bao giờ xảy ra thì cần phát hiện và phục hồi deadlock. Giải thuật phát hiện 
deadlock phải được thực hiện lên để xác định deadlock có thể xảy ra hay không. Nếu 
deadlock được phát hiện hệ thống phải phục hồi bằng cách kết thúc một số tiến trình 
bị deadlock hay đòi lại tài nguyên từ một số tiến trình bị deadlock. 
Trong một hệ thống mà nó chọn các nạn nhân để phục hồi về trạng thái trước 
đó chủ yếu dựa trên cơ sở yếu tố chi phí, việc đói tài nguyên có thể xảy ra. Kết quả là 
tiến trình được chọn không bao giờ hoàn thành tác vụ được chỉ định của nó. 
Câu hỏi và bài tập chương 2 
1. Nêu khái niệm về tiến trình và các mối quan hệ giữa các tiến trình trong hệ 
thống. Trình bày đặc trưng của các mối quan hệ đó 
2. Cho chương trình C như sau: 
int main(int argc, char** argv) 
{ 
 printf(“Hello\n"); 
 exit(0); 
} 
151 
Hãy chỉ ra chuỗi các trạng thái khi thực hiện chương trình trên (trong trường 
hợp tốt nhất) 
3. Cho chương trình C như sau: 
int a 
int main(int argc, char** argv) 
{ 
 printf(“nhap so nguyen a = "); 
 scanf(“%d”, &a); 
 printf(“a = %d", a); 
 exit(0); 
} 
Hãy chỉ ra chuỗi các trạng thái khi thực hiện chương trình trên (trong trường 
hợp tốt nhất) 
4. Nêu ý nghĩa của khối điều khiển tiến trình. Trình bày nội dung của khối điều 
khiển tiến trình 
5. Trình bày lưu đồ chuyển trạng thái giữa các tiến trình. Vì sao khi chuyển trạng 
thái, hệ điều hành phải lưu trạng thái của tiến trình vào khối điều khiển tiến 
trình, các thông tin nào sẽ được lưu. 
6. Hàng đợi tiến trình được tổ chức như thế nào? 
7. Vì sao phải lập lịch cho các tiến trình, có các bộ lập lịch nào, vị trí của chúng ở 
đâu? 
8. Các bộ lập lịch tiến trình được thực hiện khi sự kiện nào xảy ra? 
9. Nêu và phân tích các tiêu chuẩn lập lịch CPU 
10. CPU burst, I/O burst là gì, lấy ví dụ minh hoạ 
11. Nêu các thuật toán lập lịch 
- FCFS (First Come First Served) 
- SJF (Shortest Job First) với 2 trường hợp 
+ Độc quyền CPU (không trưng dụng) 
+ Không độc quyền CPU (trưng dụng) 
- Round-Robin (RR) 
Lấy ví dụ minh hoạ 
152 
12. Cho 5 tiến trình P1, P2, P3, P4, P5 nằm trong hàng đợi Ready List: 
STT Tiến trình Thời điểm vào Thời gian xử lý 
1 P1 0 3 
2 P2 1 7 
3 P3 2 5 
4 P4 3 6 
5 P5 5 4 
Mô tả hoạt động, tính thời gian chờ đợi trung bình bằng các thuật toán lập lịch: 
- FCFS (First Come First Served) 
- SJF (Shortest Job First) với 2 trường hợp 
+ Độc quyền CPU (không trưng dụng) 
+ Không độc quyền CPU (trưng dụng) 
- Round-Robin (RR), với Quantum = 3 
13. Lập lịch nhiều hàng đợi được tổ chức như nào, lấy ví dụ minh hoạ 
14. Đồng bộ hoá tiến trình là gì? Vì sao phải đồng bộ hoá tiến trình? 
15. Trình bày khái niệm về tài nguyên găng và đoạn găng 
16. Trình bày cấu trúc chung để các tiến trình thực hiện đoạn găng 
17. Nêu các điều kiện để tiến trình điều độ qua đoạn găng 
18. Trình bày giải thuật 1, giải thuật 2, giải thuật Peterson để điều độ tiến trình qua 
đoạn găng 
19. Trình bày giải thuật Semaphone để điều độ tiến trình qua đoạn găng, phân tích 
rõ toán tử wait() và signal(). 
20. Trình bày hoạt động của Semaphone nhị phân. 
21. Nêu khái niệm bế tắc và các điều kiện để xảy ra bế tắc 
22. Trình bày đồ thị cấp phát tài nguyên, lấy ví dụ minh hoạ 
23. Trong đồ đồ thị cấp phát tài nguyên, chu trình nào gây ra bế tắc, chu trình nào 
không gây ra bế tắc, lấy ví dụ minh họa 
24. Trình bày nguyên tắc chung và các phương pháp xử lý bế tắc 
25. Để ngăn chặn bế tắc thì cần thực hiện như thế nào? 
26. Nêu khái niệm về dãy an toàn, trạng thái an toàn, trạng thái không an toàn, lấy 
ví dụ minh hoạ 
153 
27. Trình bày thuật toán đồ thị cấp phát tài nguyên, lấy ví dụ minh hoạ 
28. Trình bày thuật toán benker, lấy ví dụ minh hoạ 
29. Trình bày thuật toán trạng thái an toàn, lấy ví dụ minh hoạ 
30. Trình bày thuật toán yêu cầu tài nguyên, lấy ví dụ minh hoạ 
31. Xét một hệ thống với 5 tiến trình P0, P1, P2, P3, P4, và 3 loại tài nguyên A, B, 
C, các tiến trình đã được cấp phát tài nguyên như bảng sau: 
 Allocation Max Available 
A B C A B C A B C 
P0 3 3 2 6 5 4 5 3 2 
P1 3 2 4 4 4 6 
P2 5 0 1 5 1 4 
P3 0 1 3 0 2 3 
P4 1 0 2 2 2 2 
b) Xác định ma trận Need 
c) Xác định xem trạng thái của hệ thống có an toàn hay không, nếu có chỉ rõ thứ 
tự an toàn 
32. Xét một hệ thống với 5 tiến trình P0, P1, P2, P3, P4, và 4 loại tài nguyên A, B, 
C, D các tiến trình đã được cấp phát tài nguyên như bảng sau: 
 Allocation Max Available 
A B C D A B C D A B C D 
P0 3 2 2 3 6 4 4 5 5 3 2 2 
P1 3 3 4 2 4 3 6 4 
P2 5 1 1 0 5 4 4 1 
P3 0 2 3 1 0 3 3 2 
P4 1 0 2 0 2 1 2 2 
a) Xác định ma trận Need 
b) Giả sử các tiến trình yêu cầu thêm các tài nguyên như sau 
 Request 
A B C D 
P0 1 0 0 2 
154 
P1 0 0 2 0 
P2 0 1 1 0 
P3 1 1 0 1 
P4 0 1 0 0 
 Kiểm tra xem có thể phân bổ tài nguyên cho các tiến trình được nữa không? 
33. Trình bày các cách phát hiện bế tắc, lấy ví dụ minh hoạ 
34. Cho đồ thị cấp phát tài nguyên như hình vẽ 
a) Xác định đồ thị chờ tương ứng 
b) Từ đồ thị chờ, kết luận xem hệ thống có bị deadlock hay không 
c) Nếu hệ thống bị deadlock, hãy bỏ đi một số cạnh của đồ thị cấp phát tài 
nguyên sao cho hệ thống hết deadlock và số cạnh bỏ đi ít nhất. 
Nếu hệ thống không bị deadlock, hãy thêm một số cạnh vào đồ thị cấp phát tài 
nguyên sao cho hệ thống bị deadlock và số cạnh thêm vào ít nhất. 
35. Trình bày cách khôi phục hệ thống khi có bế tắc 
P0 
P1 
P4 P5 
P3 
P2 
R1 R2 
R3 
R5 R6 
R4