Bài giảng Nguyên lý hệ điều hành - Đỗ Công Đức - Chương :2 Quản lý tiến trình

 bế tắc: 
1 Có chiếm giữ tài nguyên không chia sẽ hay độc quyền: độc quyền 
sử dụng cho đến khi kết thúc xử lý
2 Sự chiếm giữ và yêu cầu thêm tài nguyên: chiếm giữ tài nguyên 
được cấp phát và đồng thời được cấp phát tài nguyên mới
3 Không thu hồi tài nguyên từ tiến trình đang chiếm giữ chúng: không 
thể giải phóng tài nguyên từ một tiến trình khác chiếm giữ
4 Tồn tại một chu kỳ trong cấp phát tài nguyên: tiến trình này chờ 
được cấp phát tài nguyên đang bị tiến trình kia chiếm giữ và ngược 
lại 
6/28/2014 Chương 2. Quản lý tiến trình 97
BẾ TẮC VÀ CHỐNG BẾ TẮC
2.6.2 Điều kiện hình thành bế tắc
 Sự độc quyền là cần thiết cho việc bảo đảm tính đúng đắng của kết 
quả và tính toàn vẹn của dữ liệu (Tài nguyên găng).
 Sự ưu tiên của các tiến trình là cần thiết nhưng không được tùy tiện 
đặc biệt đối với các tiến trình có liên quan, sự giải phóng tiến trình 
này có thể ảnh hưởng đến kết quả xử lý của các tiến trình khác 
 Sự bế tắc có thể tồn tại với 3 điều kiện trên nhưng cũng có thể
không xảy ra. Để chắc chắn xảy ra bế tắc là phải có điều kiện thứ 4, 
3 điều kiện đầu là điều kiện cần chứ không phải điều kiện đủ, còn 
điều kiện thứ 4 là tất yếu
6/28/2014 Chương 2. Quản lý tiến trình 98
BẾ TẮC VÀ CHỐNG BẾ TẮC
2.6.3 Ngăn chặn bế tắc
Để ngăn chặng bế tắc thì làm cho hệ thống không thể xảy ra đồng 
thời 4 điều kiện bế tắc 
1 Tài nguyên không thể chia sẻ: Không thể tránh khỏi vì độc quyền là
rất cần thiết
2 Sự kiện chiếm giữ và yêu cầu thêm tài nguyên: 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 
6/28/2014 Chương 2. Quản lý tiến trình 99
BẾ TẮC VÀ CHỐNG BẾ TẮC
2.6.3 Ngăn chặn bế tắc
3 Không thu hồi tài nguyên tiến trình đang chiếm giữ: khi tiến trình 
rơi vào trạng thái khóa thì HĐH thu hồi tài nguyên để cấp cho phát 
cho tiến trình khác và sau đó cấp lại đầy đủ tài nguyên cho tiến trình 
được đưa ra khỏi trạng thái khóa. Nhưng việc này khó thực hiện vì
vi phạm sự toàn vẹn dữ liệu
4 Tồn tại chu kỳ cấp phát tài nguyên vòng tròn: bằng cách phân lớp 
tài nguyên, tiến trình được cấp phát tài nguyên ở lớp L, nó chỉ có thể
yêu cầu các tài nguyên ở lớp thấp hơn lớp L 
Khi tiến trình đang giữ tài nguyên Ri, có thể yêu cầu tài nguyên Rj 
sao cho F(Rj)>F(Ri) 
6/28/2014 Chương 2. Quản lý tiến trình 100
BẾ TẮC VÀ CHỐNG BẾ TẮC
2.6.4 Phát hiện bế tắc
 Để phát hiện bế tắc HĐH thường cài đặt một thuật toán để phát hiện 
hệ thống có tồn tại hiện tượng chờ đợi vòng tròn hay không.
 HĐH phải cài đặt cơ chế độc quyền để bảm bảo tài nguyên chia sẻ
và thực hiện cấp phát tài nguyên một lần để ngăn chặng việc chiếm 
giữ và yêu cầu cấp mới tài nguyên.
 Kiểm tra hệ thống thường xuyên để phát hiện bế tắc
6/28/2014 Chương 2. Quản lý tiến trình 101
BẾ TẮC VÀ CHỐNG BẾ TẮC
2.6.4 Phát hiện bế tắc
Khi phát hiện bế tắc HĐH sử dụng một số giải pháp:
 Thoát tất cả các tiến trình bị bế tắc.
 Sao lưu lại mỗi tiến trình bị bế tắc tại một vài điểm, sau đó khởi 
động lại tất cả các tiến trình 
 Thu hồi tài nguyên của tiến trình bế tắc, để cấp phát cho một tiến 
trình trong tập tiến trình bế tắc, giúp tiến trình này ra khỏi bế tắc 
 Dùng toàn bộ quyền ưu tiên sử dụng tài nguyên cho một tiến trình, 
để tiến trình này ra khỏi bế tắc 
6/28/2014 Chương 2. Quản lý tiến trình 102
BẾ TẮC VÀ CHỐNG BẾ TẮC
2.6.4 Phát hiện bế tắc
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 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
6/28/2014 Chương 2. Quản lý tiến trình 103
BẾ TẮC VÀ CHỐNG BẾ TẮC
2.6.4 Phát hiện bế tắc
Giải thuật phát hiện bế tắc.
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ó bế tắc.
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 bế tắc. 
6/28/2014 Chương 2. Quản lý tiến trình 104
BẾ TẮC VÀ CHỐNG BẾ TẮC
2.6.5 Tránh bế tắc
Để giải quyết bài toán bế tắc ta sử dụng phương pháp tránh bế tắc :
 Ngăn chặn một trong ba điều kiện cần của bế tắc, hoặc trực tiếp 
ngăn chặn không cho xảy ra hiện tượng chờ đợi vòng tròn 
 Tránh bế tắc có thể thực hiện là cho phép 3 điều kiện cần xảy ra 
nhưng cung cấp các lựa chọn đúng để không xảy ra điểm bế tắc 
 HĐH tuân thủ 2 nguyên tắc cơ bản để tránh bế tắc
- Không hoạt động nếu yêu cầu tài nguyên có nguy cơ dẫn đến bế tắc 
- Không cấp thêm tài nguyên nếu cung cấp có nguy cơ dẫn đến bế tắc 
6/28/2014 Chương 2. Quản lý tiến trình 105
BẾ TẮC VÀ CHỐNG BẾ TẮC
2.6.5 Tránh bế tắc
Hệ điều hành sử dụng 2 khái niệm là trạng thái và trạng thái an toàn 
để tránh được bế tắc trong công tác phòng chống bế tắc 
 Trạng thái của hệ thống: là sự cấp phát tài nguyên hiện tại cho các 
tiến trình 
 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 (đến tối đa) của mỗi tiến trình mà vẫn 
ngăn chặn được bế tắc 
HĐH xây dựng thuật toán, tác động vào cấu trúc dữ liệu để xác 
định trạng thái an toàn hoặc không an toàn để phục vụ cấp phát tài 
nguyên. Nếu là an toàn thì cấp phát, nếu không an toàn thì từ chối cấp 
phát cho đến khi nào xác định được trạng thái an toàn 
6/28/2014 Chương 2. Quản lý tiến trình 106
BẾ TẮC VÀ CHỐNG BẾ TẮC
2.6.5 Tránh bế tắc
Sử dụng các cấu trúc dữ liệu sau:
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 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 need[numprocs,numresources];
//need[p,r]=max[p,r]-allocation[p,r]
int available[numresources]
//available[r] số lượng tài nguyên r còn tự do
6/28/2014 Chương 2. Quản lý tiến trình 107
BẾ TẮC VÀ CHỐNG BẾ TẮC
2.6.5 Tránh bế tắc
int word[numresouces]=available;
int finish[numproces]=false;
1.Tìm i sao cho
a. finish[i]==false;
b. need[i,j]<=word[j]; với mọi tài nguyên j
nếu không có i như thế, đến bước 3
2.Word[j]=word[j]+allocation[i,j];
finish[i]=true;
đến bước 1;
3.Nếu finish[i]==true với mọi i thì hệ thống ở trạng thái an toàn. 
Ngược lại hệ thống bị tắc nghẽn
6/28/2014 Chương 2. Quản lý tiến trình 108
BẾ TẮC VÀ CHỐNG BẾ TẮC
2.6.5 Tránh bế tắc
ví dụ: giả sử tình trạng hiện hành của hệ thống được mô tả ở bảng 
dưới. Nếu tiến trình P2 yêu cầu cấp 4 R1, 1 R3. Hãy cho biết yêu cầu 
này có thể đáp ứng mà không xảy ra tình trạng tắt nghẽn
200224P4
112413P3
112316P2
214001223P1
R3R2R1R3R2R1R3R2R1
AvailableAllocationMax
6/28/2014 Chương 2. Quản lý tiến trình 109
BẾ TẮC VÀ CHỐNG BẾ TẮC
2.6.5 Tránh bế tắc
ví dụ: Available[1]=4, Available[3]=2 đủ để thoả mãn yêu cầu của 
P2, ta có
200024P4
112301P3
216100P2
110001222P1
R3R2R1R3R2R1R3R2R1
AvailableAllocationNeed
6/28/2014 Chương 2. Quản lý tiến trình 110
BẾ TẮC VÀ CHỐNG BẾ TẮC
2.6.5 Tránh bế tắc
200024P4
112301P3
000000P2
326001222P1
R3R2R1R3R2R1R3R2R1
AvailableAllocationNeed
6/28/2014 Chương 2. Quản lý tiến trình 111
BẾ TẮC VÀ CHỐNG BẾ TẮC
2.6.5 Tránh bế tắc
200024P4
112301P3
000000P2
327000000P1
R3R2R1R3R2R1R3R2R1
AvailableAllocationNeed
6/28/2014 Chương 2. Quản lý tiến trình 112
BẾ TẮC VÀ CHỐNG BẾ TẮC
2.6.5 Tránh bế tắc
200024P4
000000P3
000000P2
439000000P1
R3R2R1R3R2R1R3R2R1
AvailableAllocationNeed
6/28/2014 Chương 2. Quản lý tiến trình 113
BẾ TẮC VÀ CHỐNG BẾ TẮC
2.6.5 Tránh bế tắc
000000P4
000000P3
000000P2
639000000P1
R3R2R1R3R2R1R3R2R1
AvailableAllocationNeed
Trạng thái kết quả là an toàn, có thể cấp phát
6/28/2014 Chương 2. Quản lý tiến trình 114
BẾ TẮC VÀ CHỐNG BẾ TẮC
2.6.6 Hiệu chỉnh bế tắc
Khi đã phát hiện được bế tắc, có 2 lựa chọn chính để hiệu chỉnh bế tắc 
1 Đình chỉ hoạt động của các tiến trình có liên quan, thu hồi tất cả các 
tài nguyên bị kết thúc và sử dụng 2 phương pháp sau 
 Đình chỉ tất cả các tiến trình trong tình trạng bế tắc 
 Đình chỉ từng tiến trình liên quan cho đến khi không còn chu trình 
gây bế tắc 
2 Thu hồi tài nguyên để cấp cho một số tiến trình khác loại bỏ bế tắc
 Chọn lựa tiến trình thu hồi và thu hồi tài nguyên của tiến trình đó
 Trở lại trạng thái trước bế tắc
 Tình trạng đói tài nguyên
6/28/2014 Chương 2. Quản lý tiến trình 115
TỔNG KẾT
Trong chương này, chúng ta đã học:
 Các khái niệm về dữ liệu, thông tin, hệ thống thông tin, hệ 
đếm, tin học, CNTT, máy tính
 Đơn vị đo thông tin
 Quá trình xử lý thông tin
 Các hệ đếm và cách chuyển đổi
 Các phép tính với số nhị phân
 Các hệ mã biểu diễn ký tự trong máy tính
 Các lĩnh vực và ứng dụng của tin học
 Máy tính ĐT: phân loại và lịch sử phát triển
6/28/2014 Chương 2. Quản lý tiến trình 116
CÂU HỎI VÀ BÀI TẬP VỀ NHÀ
 Thực hiện các câu hỏi và bài tập trong sách “Giáo trình tin 
học đại cương” trang 8-9
 Thực hiện chuyển đổi thành thạo các hệ số đếm từ cơ số b 
(2,8,16) sang thập phân và từ thập phân sang cơ số b
 Thực hiện chuyển đổi giữa cơ số 2 và 16, 2 và 8, 8 và 16 
và ngược lại (dùng qua trung gian cơ số 2)
 Ví dụ: 65,97,127,255
 Xem trước phần giáo trình chương 2: Cấu trúc máy tính
6/28/2014 Chương 2. Quản lý tiến trình 117
Tiến trình Thời gian đến Thời gian xử lý
P1 0 7
P2 2 4
P3 4 1
P4 5 4
 Không ưu tiên SJF
Ví dụ về không ưu tiên SJF
P1 P3 P2
7 160
P4
8 12
ĐIỀU PHỐI TIẾN TRÌNH
Thời gian chờ trung bình = (0 + 6 + 3 + 7)/4 = 4
6/28/2014 Chương 2. Quản lý tiến trình 118
Ví dụ về ưu tiên SJF
Tiến trình Thời gian đến Thời gian xử lý
P1 0 7
P2 2 4
P3 4 1
P4 5 4
 Ưu tiên SJF 
P1 P3P2
42 110
P4
5 7
P2 P1
16
ĐIỀU PHỐI TIẾN TRÌNH
Thời gian chờ trung bình = (9 + 1 + 0 +2)/4 = 3