Bài giảng Hệ điều hành - Nguyễn Thị Ngọc Vinh - Chương 4: Quản lý tiến trình

 Cách 2:
 Tiến trình chỉ đƣợc yêu cầu tài nguyên nếu không giữ tài nguyên khác
 Trƣớc khi yêu cầu thêm tài nguyên, tiến trình phải giải phóng tài 
nguyên đã đƣợc cấp và yêu cầu lại (nếu cần) cùng với tài nguyên mới
V. BẾ TẮC 
3. Ngăn ngừa bế tắc
www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH
BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1
Trang 79
 Không có phân phối lại:
 Cách 1:
 Khi một tiến trình yêu cầu tài nguyên nhƣng không đƣợc do đã bị cấp 
phát, HDH sẽ thu hồi lại toàn bộ tài nguyên nó đang giữ
 Tiến trình chỉ có thể thực hiện tiếp sau khi lấy đƣợc tài nguyên cũ cùng 
với tài nguyên mới yêu cầu
 Cách 2:
 Khi tiến trình yêu cầu tài nguyên, nếu còn trống, sẽ đƣợc cấp phát ngay
 Nếu tài nguyên do tiến trình khác giữ mà tiến trình này đang chờ cấp 
thêm tài nguyên thì thu hồi lại để cấp cho tiến trình yêu cầu
 Nếu hai điều kiện trên đều không thỏa thì tiến trình yêu cầu tài nguyên 
phải chờ
V. BẾ TẮC 
3. Ngăn ngừa bế tắc (tt)
www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH
BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1
Trang 80
 Chờ đợi vòng tròn:
 Xác định thứ tự cho các dạng tài nguyên và chỉ cho phép tiến trình 
yêu cầu tài nguyên sao cho tài nguyên mà tiến trình yêu cầu sau có 
thứ tự lớn hơn tài nguyên mà nó yêu cầu trƣớc
 Giả sử trong hệ thống có n dạng tài nguyên ký hiệu R1, R2, …, Rn
 Giả sử những dạng tài nguyên này đƣợc sắp xếp theo thứ tự tăng 
dần của chỉ số
 Nếu tiến trình đã yêu cầu một số tài nguyên dạng Ri thì sau đó tiến 
trình chỉ đƣợc phép yêu cầu tài nguyên dạng Rj nếu j > i
 Nếu tiến trình cần nhiều tài nguyên cùng dạng thì tiến trình phải 
yêu cầu tất cả tài nguyên dạng đó cùng một lúc
V. BẾ TẮC 
3. Ngăn ngừa bế tắc (tt)
www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH
BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1
Trang 81
 Ngăn ngừa bế tắc: 
 Sử dụng quy tắc hay ràng buộc khi cấp phát tài nguyên để ngăn 
ngừa điều kiện xẩy ra bế tắc
 Sử dụng tài nguyên kém hiệu quả, giảm hiệu năng của tiến trình
 Phòng tránh bế tắc:
 Cho phép 3 điều kiện đầu xẩy ra và chỉ đảm bảo sao cho trạng thái 
bế tắc không bao giờ đạt tới
 Mỗi yêu cầu cấp tài nguyên của tiến trình sẽ đƣợc xem xét và 
quyết định tùy theo tình hình cụ thể
 HDH yêu cầu tiến trình cung cấp thông tin về việc sử dụng tài 
nguyên (số lƣợng tối đa tài nguyên tiến trình cần sử dụng)
V. BẾ TẮC 
4. Phòng tránh bế tắc
www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH
BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1
Trang 82
 Khi tiến trình muốn khởi tạo, thông báo dạng tài nguyên và 
số lƣợng tài nguyên tối đa cho mỗi dạng sẽ yêu cầu
 Nếu số lƣợng yêu cầu không vƣợt quá khả năng hệ thống, 
tiến trình sẽ đƣợc khởi tạo
 Trạng thái đƣợc xác định bởi tình trạng sử dụng tài nguyên 
hiện thời trong hệ thống:
 Số lƣợng tối đa tài nguyên mà tiến trình yêu cầu:
 Dƣới dạng ma trận M[n][m]: n là số lƣợng tiến trình, m: số tài nguyên
 M[i][j]: số lƣợng tài nguyên tối đa dạng j mà tiến trình i yêu cầu
V. BẾ TẮC 
4. Phòng tránh bế tắc – thuật toán người cho vay
www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH
BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1
Trang 83
 Số lƣợng tài nguyên còn lại:
 Dƣới dạng vectơ A[m] 
 A[j] là số lƣợng tài nguyên dạng j còn lại và có thể cấp phát
 Lƣợng tài nguyên đã cấp cho mỗi tiến trình:
 Dƣới dạng ma trận D[n][m]
 D[i][j] là lƣợng tài nguyên dạng j đã cấp cho tiến trình i
 Lƣợng tài nguyên còn cần cấp
 Dƣới dạng ma trận C[n][m]
 C[i][j]=M[i][j]-D[i][j] là lƣợng tài nguyên dạng j mà tiến trình i còn cần 
cấp
V. BẾ TẮC 
4. Phòng tránh bế tắc – thuật toán người cho vay
www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH
BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1
Trang 84
 Trạng thái an toàn: trạng thái mà từ đó có ít nhất một 
phƣơng án cấp phát sao cho bế tắc không xẩy ra
 Cách phòng tránh bế tắc:
 Khi tiến trình có yêu cầu cấp tài nguyên, hệ thống giả sử tài 
nguyên đƣợc cấp
 Cập nhật lại trạng thái & xác định xem trạng thái đó có an toàn?
 Nếu an toàn, tài nguyên sẽ đƣợc cấp thật
 Ngƣợc lại, tiến trình bị phong tỏa &chờ tới khi có thể cấp phát an toàn
V. BẾ TẮC 
4. Phòng tránh bế tắc – thuật toán người cho vay
www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH
BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1
Trang 85
 Hệ thống có 3 dạng tài nguyên X, Y, Z với số 
lƣợng ban đầu X=10, Y=5, Z=7
 4 tiến trình P1, P2, P3, P4 có yêu cầu tài nguyên 
tối đa cho trong bảng
 Xét trạng thái sau của hệ thống:
 Là trạng thái an toàn
 Có thể tìm ra cách cấp phát không 
dẫn đến bế tắc, VD: P2, P4, P3, P1
V. BẾ TẮC 
4. Phòng tránh bế tắc – thuật toán người cho vay
X Y Z
P1 7 5 3
P2 3 2 2
P3 9 0 2
P4 2 2 2
Yêu cầu tối đa
X Y Z
P1 0 1 0
P2 2 0 0
P3 3 0 2
P4 2 1 1
Đã cấp
X Y Z
3 3 4
Còn lại
X Y Z
P1 7 4 3
P2 1 2 2
P3 6 0 0
P4 0 1 1
Còn cần cấp
X Y Z
3 0 4
Còn lại
X Y Z
P1 7 1 3
P2 1 2 2
P3 6 0 0
P4 0 1 1
Còn cần cấp
 P1 yêu cầu cấp phát 3 tài nguyên dạng Y, tức là yêu cầu = (0,3,0). Nếu yêu cầu
thỏa mãn, hệ thống chuyển sang trạng thái:
 Trạng thái không an toàn
 => yêu cầu (0,3,0) bị từ chối
www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH
BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1
Trang 86
 Thuật toán xác định trạng thái an toàn:
V. BẾ TẮC 
4. Phòng tránh bế tắc – thuật toán người cho vay
1. Khai báo mảng W kích thước m và mảng F kích thước n. (F[i] chứa tình
trạng tiến trình thứ i đã kết thúc hay chưa, W chứa lượng tài nguyên còn
lại)
Khởi tạo W=A và F[i]=false (i=0,…,n-1)
2. Tìm i sao cho:
F[i] = false và C[i][j] W[j] với mọi j=0,…,m-1
Nếu không có i như vậy thì chuyển sang bước 4
3. a) W = W + D[i]
b) F[i] = true
c) Quay lại bước 2
4. If F[i] = true với mọi i =0,…,n-1 thì trạng thái an toàn
Else trạng thái không an toàn
www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH
BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1
Trang 87
 Hệ thống không thực hiện biện pháp ngăn ngừa/phòng 
tránh => bế tắc có thể xảy ra
 Hệ thống định kỳ kiểm tra để phát hiện có tình trạng bế tắc 
hay không?
 Nếu có, hệ thống sẽ xử lý để khôi phục lại trạng thái không 
có bế tắc
V. BẾ TẮC 
5. Phát hiện bế tắc và xử lý
www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH
BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1
Trang 88
V. BẾ TẮC 
5. Phát hiện bế tắc và xử lý (tt)
 Phát hiện bế tắc:
 Trƣờng hợp mỗi dạng tài nguyên chỉ có một tài nguyên duy nhất
=>sử dụng đồ thị biểu diễn quan hệ chờ đợi lần nhau giữa tiến 
trình
 Xây dựng đồ thị cấp phát tài nguyên:
 Các nút là tiến trình và tài nguyên
 Tài nguyên đƣợc nối với tiến trình bằng cung 
có hƣớng nếu tài nguyên đƣợc cấp cho tiến 
trình đó
 Tiến trình đƣợc nối với tài nguyên bằng cung 
có hƣớng nếu tiến trình đang đƣợc cấp tài 
nguyên đó
www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH
BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1
Trang 89
 Phát hiện bế tắc:
 Đồ thị chờ đợi:
 Đƣợc xây dựng từ đồ thị cấp phát tài nguyên bằng cách bỏ đi các nút tƣơng 
ứng với tài nguyên và nhập các cung đi qua nút bị bỏ
 Cho phép phát hiện tình trạng tiến trình chờ đợi vòng tròn là điều kiện đủ để 
sinh ra bế tắc
 Sử dụng thuật toán phát hiện chu trình trên đồ thị có hƣớng để phát hiện bế 
tắc trên đồ thị chờ đợi
V. BẾ TẮC 
5. Phát hiện bế tắc và xử lý (tt)
www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH
BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1
Trang 90
 Thời điểm phát hiện bế tắc:
 Bế tắc chỉ có thể xuất hiện sau khi một tiến trình nào đó yêu cầu 
tài nguyên và không đƣợc thỏa mãn
 => Chạy thuật toán phát hiện bế tắc mỗi khi có yêu cầu cấp phát 
tài nguyên không đƣợc thỏa mãn
 => Cho phép phát hiện bế tắc ngay khi vừa xẩy ra
 Chạy thƣờng xuyên làm giảm hiệu năng hệ thống
 => Giảm tần suất chạy thuật toán phát hiện bế tắc: 
 Sau từng chu kỳ từ vài chục phút tới vài giờ
 Khi có một số dấu hiệu nhƣ hiệu suất sử dụng CPU giảm xuống dƣới một 
ngƣỡng nào đó
V. BẾ TẮC 
5. Phát hiện bế tắc và xử lý (tt)
www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH
BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1
Trang 91
 Xử lý khi bị bế tắc:
 Kết thúc tất cả tiến trình đang bị bế tắc
 Kết thúc lần lƣợt từng tiến trình đang bị bế tắc đến khi hết bế tắc:
 HDH phải chạy lại thuật toán phát hiện bế tắc sau khi kết thúc 1 tiến trình
 HDH có thể chọn thứ tự kết thúc tiến trình dựa trên tiêu chí nào đó
 Khôi phục tiến trình về thời điểm trƣớc khi bị bế tắc sau đó cho 
các tiến trình thực hiện lại từ điểm này:
 Đòi hỏi HDH lƣu trữ trạng thái để có thể thực hiện quay lui và khôi phục 
về các điểm kiểm tra trƣớc đó
 Khi chạy lại, các tiến trình có thể lại rơi vào bế tắc tiếp
 Lần lƣợt thu hồi lại tài nguyên từ các tiến trình bế tắc cho tới khi 
hết bế tắc
V. BẾ TẮC 
5. Phát hiện bế tắc và xử lý (tt)
www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH
BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1
Trang 92
 Đặt hai thao tác lấy đũa của mỗi triết gia vào đoạn nguy 
hiểm để đảm bảo triết gia lấy đƣợc hai đũa cùng một lúc
 Quy ƣớc bất đối xứng về thứ tự lấy đũa: ví dụ ngƣời có số 
thứ tự chẵn lấy đũa trái trƣớc đũa phải, ngƣời có số thứ tự 
lẻ lấy đũa phải trƣớc đũa trái
 Tại mỗi thời điểm chỉ cho tối đa bốn ngƣời ngồi vào bàn:
 Sử dụng thêm một cờ hiệu table có giá trị khởi tạo bằng 4
 Triết gia phải gọi thao tác wait(table) trƣớc khi ngồi vào bàn và 
lấy đũa
V. BẾ TẮC 
6. Ngăn ngừa bế tắc cho bài toán triết gia ăn cơm
www.ptit.edu.vn GIẢNG VIÊN: THS NGUYỄN THỊ NGỌC VINH
BỘ MÔN: KHOA HỌC MÁY TÍNH – KHOA CNTT1
Trang 93
V. BẾ TẮC 
6. Ngăn ngừa bế tắc cho bài toán triết gia ăn cơm
semaphore chopstick[5] = {1,1,1,1,1,1};
semaphore table = 4;
void Philosopher(int i){ //tiến trình P(i)
for(;;){ //lặp vô hạn
wait(table);
wait(chopstick[i]); //lấy đũa bên trái
wait(chopstick[(i+1)%5]); //lấy đũa bên phải
signal(chopstick[(i+1)%5]);
signal(chopstick[i]);
signal(table);
}
}
void main(){
StartProcess(Philosopher(1));
...
StartProcess(Philosopher (5));
}