1
1
Nguyên lý hệđiềuhành
NguyễnHải Châu
Khoa Công nghệthông tin
Trường Đạihọc Công nghệ
2
Bếtắc (Deadlock)
3
Định nghĩa
zBếtắclàtìnhhuống xuấthiệnkhihaihay
nhiều “hành động” phảichờmộthoặc nhiều
hành động khác để kết thúc, nhưng không
bao giờthựchiệnđược
zMáy tính: Bếtắclàtìnhhuống xuấthiệnkhi
hai tiếntrìnhphảichờđợinhaugiải phóng tài
nguyên hoặcnhiềutiếntrìnhchờsửdụng
các tài nguyên theo một “vòng tròn” (circular
chain)
4
Hai con dê qua cầu: Bếtắc
5
Bếtắc giao thông tại ngã tư
6
Bếtắctrongmáytính
zTiếntrìnhA:
{
…
Khóa file F1;
...
Mởfile F2;
…
Đóng F1(mởkhóa F1);
}
zTiếntrìnhB
{
…
Khóa file F2;
...
Mởfile F1;
…
Đóng F1(mởkhóa F1);
}
2
7
Qui trình sửdụng tài nguyên
zMộttiếntrìnhthường sửdụng tài nguyên
theo các bướctuầntựsau:
zXin phép sửdụng (request)
zSửdụng tài nguyên (use)
zGiải phóng tài nguyên sau khi sửdụng (release)
8
Điềukiệncầnđể có bếtắc
zBếtắc xuất hiện nếu 4 điều kiện sau xuất
hiện đồng thời (điều kiện cần):
zC1: Loạitrừlẫn nhau (mutual exclusion)
zC2: Giữvà chờ(hold and wait)
zC3: Không có đặcquyền (preemption)
zC4: Chờvòng (circular wait)
9
C1: Loại trừlẫn nhau
zMột tài nguyên bịchiếm bởi một tiến trình, và
không tiến trình nào khác có thểsửdụng tài
nguyên này
10
C2: Giữvà chờ
zMột tiến trình giữít nhất một tài nguyên và
chờmột sốtài nguyên khác rỗi để sửdụng.
Các tài nguyên này đang bịmột tiến trình
khác chiếm giữ
11
C3: Không có đặc quyền
zTài nguyên bịchiếm giữchỉcó thểrỗi khi tiến
trình “tựnguyện” giải phóng tài nguyên sau
khi đã sửdụng xong.
12
C3: Chờvòng
zMột tập tiến trình {P0, P1, ..., Pn} có xuất hiện
điều kiện “chờvòng” nếu P0chờmột tài
nguyên do P1chiếm giữ, P1chờmột tài
nguyên khác do P2chiếm giữ, ..., Pn-1chờtài
nguyên do Pnchiếm giữvà Pnchờtài nguyên
do P0chiếm giữ
3
13
Đồ thịcấp phát tài nguyên
zThuậtngữ: Resource allocation graph
zĐể mô tảmột cách chính xác bếtắc, chúng
ta sửdụng đồ thịcó hướng gọi là “đồ thịcấp
phát tài nguyên” G=(V, E) với Vlà tập đỉnh, E
là tập cung
zE được chia thành hai tập con P={P0, P1, ...,
Pn} là tập các tiến trình trong hệthống và R=
{R0, R1, ..., Rm} là tập các loại tài nguyên
trong hệthống thỏa mãn P∪R=Evà P∩R= ∅
14
Đồ thịcấp phát tài nguyên
zCung có hướng từtiến trình Piđến tài
nguyên Rj, ký hiệu là Pi
→
Rj có ý nghĩa: Tiến
trình Piyêu cầu một thểhiệncủa Ri. Ta gọi
Pi
→
Rj là cung yêu cầu(request edge)
zCung có hướng từtài nguyên Rj đến tiến
trình Piký hiệu là Rj
→
Picó ý nghĩa: Một thể
hiện của tài nguyên Rj đã được cấp phát cho
tiến trình Pi. Ta gọi Rj
→
Pilà cung cấp phát
(asignment edge)
15
Đồ thịcấp phát tài nguyên
zKý hiệu hình vẽ:
zPilà hình tròn
zRjlà các hình chữnhật với mỗi chấm bên trong là
số lượng các thểhiện của tài nguyên
zMinh họa đồ thịcấp phát tài nguyên:
P1P2P3
R1R2
R3R416
Đồ thịcấp phát tài nguyên
zNếu không có chu trình trong đồ thịcấp phát
tài nguyên: Không có bếtắc. Nếu có chu
trình: Có thểxảy ra bếtắc.
zNếu trong một chu trình trong đồ thịcấp phát
tài nguyên, mỗi loại tài nguyên chỉcó đúng
một thểhiện: Bếtắc đã xảy ra (Điều kiện cần
và đủ)
zNếu trong một chu trình trong đồ thịcấp phát
tài nguyên một sốtài nguyên có nhiều hơn
một thểhiện: Có thểxảy ra bếtắc (Điều kiện
cần nhưng không đủ)
17
Ví dụchu trình dẫn đến bếtắc
zGiảsửP3yêu cầu một thểhiện của R3
zKhi đócó2 chu trình xuất hiện:
zP1→R1→P2→R2→P3→R3→P1, và
zP2→R2→P3→R3→P2
zKhi đócác tiến trình P1, P2, P3bịbếtắc
P1P2P3
R1R2
R3R4
18
Ví dụchu trình không dẫn đến
bếtắc
zChu trình: P1→R1→P3→R2→P1
zBếtắc không xảy ra vì P4có thểgiải phóng
một thểhiện tài nguyên R2và P3sẽ được
cấp phát một thểhiện của R2
R1
R2
P1
P2
P3
P4
4
19
Các phương pháp
xửlý bếtắc
20
Các phương pháp xửlý bếtắc
zMột cách tổng quát, có 3 phương pháp:
zSửdụng một giao thức để hệthống không bao
giờ rơi vào trạng thái bếtắc: Deadlock prevention
(ngăn chặn bếtắc) hoặc Deadlock avoidance
(tránh bếtắc)
zCó thểcho phép hệthống bịbếtắc, phát hiện bế
tắc và khắc phục nó
zBỏqua bếtắc, xem như bếtắc không bao giờ
xuất hiện trong hệthống (Giải pháp này dùng
trong nhiều hệthống, ví dụUnix, Windows!!)
21
Ngăn chặn bếtắc
(Deadlock prevention)
22
Giới thiệu
zNgăn chặn bếtắc (deadlock prevention) là
phương pháp xửlý bếtắc, không cho nó xảy
ra bằng cách làm cho ít nhất một điều kiện
cần của bếtắc là C1, C2, C3 hoặc C4 không
được thỏa mãn (không xảy ra)
zNgăn chặn bếtắc theo phương pháp này có
tính chất tĩnh (statically)
23
Ngăn chặn “loại trừlẫn nhau”
zC1 (Loại trừlẫn nhau): là điều kiện bắt buộc
cho các tài nguyên không sửdụng chung
được →Khó làm cho C1 không xảy ra vì các
hệthống luôn có các tài nguyên không thểsử
dụng chung được
24
Ngăn chặn “giữvà chờ”
zC2 (Giữvà chờ): Có thểlàm cho C2 không
xảy ra bằng cách đảm bảo:
zMột tiến trình luôn yêu cầu cấphát tài nguyên chỉ
khi nó không chiếm giữbất kỳmột tài nguyên
nào, hoặc
zMột tiến trình chỉthực hiện khi nó được cấp phát
toàn bộcác tài nguyên cần thiết
5
25
Ngăn chặn “không có đặc quyền”
zĐể ngăn chặn không cho điều kiện này xảy
ra, có thểsửdụng giao thức sau:
zNếu tiến trình P (đang chiếm tài nguyên R1, ...,
Rn-1) yêu cầu cấp phát tài nguyên Rn nhưng
không được cấp phát ngay (có nghĩa là Pphải
chờ) thì tất cảcác tài nguyên R1, ..., Rn-1 phải
được “thu hồi”
zNói cách khác, R1, ..., Rn-1 phải được “giải phóng”
một cách áp đặt, tức là các tài nguyên này phải
được đưa vào danh sách các tài nguyên mà P
đang chờcấp phát. 26
Ngăn chặn “không có đặc
quyền”: mã lệnh
Tiến trình Pyêu cầu cấp phát tài nguyên R1, ..., Rn-1
if (R1, ..., Rn-1rỗi)
then cấp phát tài nguyên cho P
else if ({Ri...Rj} được cấp phát cho Q và Q đang
trong trạng thái chờmột sốtài nguyên Skhác)
then thu hồi {Ri...Rj} và cấp phát cho P
else đưa P vào trạng thái chờtài nguyên R1, ..., Rn-1
27
Ngăn chặn “chờvòng”
zMột giải pháp ngăn chặn chờvòng là đánh
sốthứtựcác tài nguyên và bắt buộc các tiến
trình yêu cầu cấp phát tài nguyên theo sốthứ
tự tăng dần
zGiảsửcó các tài nguyên {R1, ..., Rn}. Ta gán
cho mỗi tài nguyên một số nguyên dương
duy nhất qua một ánh xạ1-1
f : R→N, với Nlà tập các sốtựnhiên
Ví dụ: f(ổcứng) = 1, f(băng từ) = 5, f(máy in) = 11
28
Ngăn chặn “chờvòng”
zGiao thức ngăn chặn chờvòng:
zKhi tiến trình P không chiếm giữtài nguyên nào,
nó có thểyêu cầu cấp phát nhiều thểhiện của
mộttài nguyên Ribất kỳ
zSau đóPchỉcó thểyêu cầu các thểhiện của tài
nguyên Rjnếu và chỉnếu f(Rj) > f(Ri). Một cách
khác, nếu P muốn yêu cầu cấp phát tài nguyên
Rj, nó đã giải phóng tất cảcác tài nguyên Rithỏa
mãn f(Ri)≥f(Rj)
zNếu Pcần được cấp phát nhiều loại tài nguyên, P
phải lần lượt yêu cầu các thểhiện của từng tài
nguyên đó
29
Chứng minh giải pháp ngăn
chặn chờvòng
zSửdụng chứng minh phản chứng
zGiảsửgiải pháp ngăn chặn gây ra chờvòng
{P0, P1, ..., Pn} trong đóPichờtài nguyên Ri
bịchiếm giữbởi P(i+1) mod n
zVì Pi+1 đang chiếm giữRivà yêu cầu Ri+1, do
đóf(Ri)<f(R(i+1) mod n) ∀i, có nghĩa là ta có:
zf(R0)<f(R1)<f(R2)<..<f(Rn)<f(R0)
zMâu thuẫn! →Giải pháp được chứng minh
30
Ưu nhược điểm của ngăn chặn
giải pháp bếtắc
zƯu điểm: ngăn chặn bếtắc (deadlock
prevention) là phương pháp tránh được bế
tắc bằng cách làm cho điều kiện cần không
được thỏa mãn
zNhược điểm:
zGiảm khả năng tận dụng tài nguyên và giảm
thông lượng của hệthống
zKhông mềm dẻo