Nguyên lý hệ điều hành – Bế tắc (Deadlock) – Tài liệu, ebook, giáo trình

bao giờthựchiệnđược

zMáy tính : Bếtắclàtìnhhuống xuấthiệnkhihai tiếntrìnhphảichờđợinhaugiải phóng tàinguyên hoặcnhiềutiếntrìnhchờsửdụngnhững tài nguyên theo một “ vòng tròn ” ( circularchain )

11 trang | Chia sẻ : Mr Hưng| Lượt xem : 3392

| Lượt tải: 1

Nội dung tài liệu Nguyên lý hệ điều hành – Bế tắc (Deadlock), để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên

11
Nguyên lý hệ điều hành
Nguyễn Hải Châu
Khoa Công nghệ thông tin
Trường Đại học Công nghệ
2
Bế tắc (Deadlock)
3
Định nghĩa
z Bế tắc là tình huống xuất hiện khi hai hay
nhiều “hành động” phải chờ một hoặc nhiều
hành động khác để kết thúc, nhưng không
bao giờ thực hiện được
z Máy tính: Bế tắc là tình huống xuất hiện khi
hai tiến trình phải chờ đợi nhau giải phóng tài
nguyên hoặc nhiều tiến trình chờ 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ắc trong máy tính
z Tiến trình A:
{
Khóa file F1;
…
Mở file F2;
Đóng F1 (mở khóa F1);
}
z Tiến trình B
{
Khóa file F2;
…
Mở file F1;
Đóng F1 (mở khóa F1);
}
27
Qui trình sử dụng tài nguyên
z Một tiến trình thường sử dụng tài nguyên
theo các bước tuần tự sau:
z Xin phép sử dụng (request)
z Sử dụng tài nguyên (use)
z Giải phóng tài nguyên sau khi sử dụng (release)
8
Điều kiện cần để có bế tắc
z Bế 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):
z C1: Loại trừ lẫn nhau (mutual exclusion)
z C2: Giữ và chờ (hold and wait)
z C3: Không có đặc quyền (preemption)
z C4: Chờ vòng (circular wait)
9
C1: Loại trừ lẫn nhau
z Mộ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ờ
z Mộ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
z Tà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
z Một tập tiến trình {P0, P1, …, Pn} có xuất hiện
điều kiện “chờ vòng” nếu P0 chờ một tài
nguyên do P1 chiếm giữ, P1 chờ một tài
nguyên khác do P2 chiếm giữ, …, Pn-1 chờ tài
nguyên do Pn chiếm giữ và Pn chờ tài nguyên
do P0 chiếm giữ
313
Đồ thị cấp phát tài nguyên
z Thuật ngữ: 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 V là tập đỉnh, E
là tập cung
z E đượ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=E và P∩R= ∅
14
Đồ thị cấp phát tài nguyên
z Cung 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 Pi yêu cầu một thể hiện của Ri. Ta gọi
Pi→Rj là cung yêu cầu (request edge)
z Cung có hướng từ tài nguyên Rj đến tiến
trình Pi ký hiệu là Rj→Pi có ý 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→Pi là cung cấp phát
(asignment edge)
15
Đồ thị cấp phát tài nguyên
z Ký hiệu hình vẽ:
z Pi là hình tròn
z Rj là 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
z Minh họa đồ thị cấp phát tài nguyên:
P1 P2 P3
R1 R2
R3 R4 16
Đồ thị cấp phát tài nguyên
z Nế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.
z Nế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à đủ)
z Nế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
z Giả sử P3 yêu cầu một thể hiện của R3
z Khi đó có 2 chu trình xuất hiện:
z P1→R1→P2→R2→P3→R3→P1, và
z P2→R2→P3→R3→P2
z Khi đó các tiến trình P1, P2, P3 bị bế tắc
P1 P2 P3
R1 R2
R3 R4
18
Ví dụ chu trình không dẫn đến
bế tắc
z Chu trình: P1→R1→P3→R2→P1
z Bế tắc không xảy ra vì P4 có thể giải phóng
một thể hiện tài nguyên R2 và P3 sẽ được
cấp phát một thể hiện của R2
R1
R2
P1
P2
P3
P4
419
Các phương pháp
xử lý bế tắc
20
Các phương pháp xử lý bế tắc
z Một cách tổng quát, có 3 phương pháp:
z Sử 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)
z Có thể cho phép hệ thống bị bế tắc, phát hiện bế
tắc và khắc phục nó
z Bỏ 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
z Ngă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)
z Ngă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”
z C1 (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ờ”
z C2 (Giữ và chờ): Có thể làm cho C2 không
xảy ra bằng cách đảm bảo:
z Mộ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
z Mộ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
525
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:
z Nế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à P phải
chờ) thì tất cả các tài nguyên R1, …, Rn-1 phải
được “thu hồi”
z Nó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 P yêu cầu cấp phát tài nguyên R1, …, Rn-1
if (R1, …, Rn-1 rỗ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 S khá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”
z Mộ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
z Giả 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 N là 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”
z Giao thức ngăn chặn chờ vòng:
z Khi 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ột tài nguyên Ri bất kỳ
z Sau đó P chỉ có thể yêu cầu các thể hiện của tài
nguyên Rj nế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 Ri thỏa
mãn f(Ri)≥f(Rj)
z Nếu P cầ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
z Sử dụng chứng minh phản chứng
z Giả sử giải pháp ngăn chặn gây ra chờ vòng
{P0, P1, …, Pn} trong đó Pi chờ tài nguyên Ri
bị chiếm giữ bởi P(i+1) mod n
z Vì Pi+1 đang chiếm giữ Ri và yêu cầu Ri+1, do
đó f(Ri) quyết đinh cấp tài nguyên cho
P2 là sai.
39
Thuật toán đồ thị cấp phát tài
nguyên
z Giả sử các tài nguyên chỉ có 1 thể hiện
z Sử dụng đồ thị cấp phát tài nguyên như ở
slide 16 và thêm một loại cung nữa là cung
báo trước (claim)
z Cung báo trước Pi→Rj chỉ ra rằng Pi có thể
yêu cầu cấp phát tài nguyên Rj, được biểu
diễn trên đồ thị bằng các đường nét đứt
z Khi tiến trình Pi yêu cầu cấp phát tài nguyên
Rj, đường nét đứt trở thành đường nét liền
40
Thuật toán đồ thị cấp phát tài
nguyên
z Chú ý rằng các tài nguyên phải được thông
báo trước khi tiến trình thực hiện
z Các cung báo trước sẽ phải có trên đồ thị
cấp phát tài nguyên
z Tuy nhiên có thể giảm nhẹ điều kiện: cung
thông báo Pi→Rj được thêm vào đồ thị nếu
tất cả các cung gắn với Pi đều là cung thông
báo
41
Thuật toán đồ thị cấp phát tài
nguyên
z Giả sử Pj yêu cầu cấp phát Rj. Yêu cầu này
chỉ có thể được chấp nhận nếu ta chuyển
cung báo trước Pi→Rj thành cung cấp phát
Rj→Pi và không tạo ra một chu trình
z Chúng ta kiểm tra bằng cách sử dụng thuật
toán phát hiện chu trình trong đồ thị: Nếu có
n tiến trình trong hệ thống, thuật toán phát
hiện chu trình có độ phức tạp tính toán O(n2)
z Nếu không có chu trình: Cấp phát->trạng thái
an toàn, ngược lại: Trạng thái không an toàn
42
Ví dụ
z Giả sử P1 yêu cầu cấp
phát R2
z Mặc dù R2 rỗi nhưng
chúng ta không thể cấp
phát R2, vì nếu cấp phát
ta sẽ có chu trình trong
đồ thị và gây ra chờ vòng
→ Hệ thống ở trạng thái
không an toàn
P1 P2
R2
R1
P1 P2
R2
R1
843
Thuật toán banker
z Thuật toán đồ thị phân phối tài nguyên không
áp dụng được cho các hệ thống có những tài
nguyên có nhiều thể hiện
z Thuật toán banker được dùng cho các hệ có
tài nguyên nhiều thể hiện, nó kém hiệu quả
hơn thuật toán đồ thị phân phối tài nguyên
z Thuật toán banker có thể dùng trong ngân
hàng: Không bao giờ cấp phát tài nguyên
(tiền) gây nên tình huống sau này không đáp
ứng được nhu cầu của tất cả các khách hàng 44
Ký hiệu dùng trong banker
z Tài nguyên rỗi: Vector m thành phần
Available, Available[j]=k nghĩa là có k thể
hiện của Rj rỗi
z Max: Ma trận nxm xác định yêu cầu tài
nguyên max của mỗi tiến trình. Max[i][j]=k có
nghĩa là tiến trình Pi yêu cầu nhiều nhất k thể
hiện của tài nguyên Rj.
45
Ký hiệu dùng trong banker
z Cấp phát: Ma trận nxm xác định số thể hiện
của các loại tài nguyên đã cấp phát cho mỗi
tiến trình. Allocation[i][j]=k có nghĩa là tiến
trình Pi được cấp phát k thể hiện của Rj.
z Cần thiết: Ma trận nxm chỉ ra số lượng thể
hiện của các tài nguyên mỗi tiến trình cần
cấp phát tiếp. Need[i][j]=k có nghĩa là tiến
trình Pi còn có thể cần thêm k thể hiện nữa
của tài nguyên Rj.
46
Ký hiệu dùng trong banker
z Số lượng và giá trị các biến trên biến đổi theo
trạng thái của hệ thống
z Qui ước: Nếu hai vector X, Y thỏa mãn
X[i]≤Y[i] ∀i thì ta ký hiệu X≤Y.
z Giả sử Work và Finish là các vector m và n
thành phần.
z Request[i] là vector yêu cầu tài nguyên của
tiến trình Pi. Request[i][j]=k có nghĩa là tiến
trình Pi yêu cầu k thể hiện của tài nguyên Rj
47
Thuật toán trạng thái an toàn
1. Khởi tạo Work=Available và Finish[i]=false
∀i=1..n
2. Tìm i sao cho Finish[i]==false và Need[i]≤Work
Nếu không tìm được i, chuyển đến bước 4
3. Work=Work+Allocation[i], Finish[i]=true
Chuyển đến bước 2
4. Nếu Finish[i]==true ∀i thì hệ thống ở trạng thái
an toàn
z Độ phức tạp tính toán của thuật toán trạng thái
an toàn: O(m.n2) 48
Thuật toán yêu cầu tài nguyên
1. Nếu Request[i]≤Need[i], chuyển đến bước 2
Ngược lại thông báo lỗi (không có tài nguyên rỗi)
2. Nếu Request[i]≤Available, chuyển đến bước 3.
Ngược lại Pi phải chờ vì không có tài nguyên
3. Nếu việc thay đổi trạng thái giả định sau đây:
Available=Availalble-Request[i]
Allocation=Allocation+Request[i]
Need[i]=Need[i]-Request[i]
đưa hệ thống vào trạng thái an toàn thì cấp phát tài
nguyên cho Pi, ngược lại Pi phải chờ Request[i] và
trạng thái của hệ thống được khôi phục như cũ
949
Ví dụ banker
z Xét một hệ thống các tiến trình và tài nguyên
như sau:
Allocation Max Available Need
A B C A B C A B C A B C
P0 0 1 0 7 5 3 3 3 2 7 4 3
P1 2 0 0 3 2 2 1 2 2
P2 3 0 2 9 0 2 6 0 0
P3 2 1 1 2 2 2 0 1 1
P4 0 0 2 4 3 3 4 3 1
50
Ví dụ banker
z Hệ thống hiện đang ở trạng thái an toàn
z Thứ tự thỏa mãn tiêu chuẩn
an toàn
z Giả sử P1 có yêu cầu: Request[1]=(1,0,2)
z Để quyết định xem có cấp phát tài nguyên
theo yêu cầu này không, trước hết ta kiểm tra
Request[1]≤Available: (1,0,2)<(3,3,2): Đúng z Giả sử yêu cầu này được cấp phát, khi đó trạng thái giả định của hệ thống là: 51 Ví dụ banker Allocation Need Available A B C A B C A B C P0 0 1 0 7 4 3 3 3 2 P1 3 0 2 0 2 0 P2 3 0 2 6 0 0 P3 2 1 1 0 1 1 P4 0 0 2 4 3 1 z Thực hiện thuật toán trạng thái an toàn và thấy rằng thứ tự. Do đó có thể cấp phát tài nguyên cho P1 ngay. 52 Ví dụ banker z Tuy nhiên, nếu hệ thống ở trạng thái sau thì z Yêu cầu (3,3,0) của P4 không thể cấp phát ngay vì các tài nguyên không rỗi z Yêu cầu (0,2,0) của P0 cũng không thể cấp phát ngay vì mặc dù các tài nguyên rỗi nhưng việc cấp phát sẽ làm cho hệ thống rơi vào trạng thái không an toàn z Bài tập: Thực hiện kiểm tra và quyết định cấp phát hai yêu cầu trên 53 Phát hiện bế tắc z Nếu không áp dụng phòng tránh hoặc ngăn chặn bế tắc thì hệ thống có thể bị bế tắc z Khi đó: z Cần có thuật toán kiểm tra trạng thái để xem có bế tắc xuất hiện hay không z Thuật toán khôi phục nếu bế tắc xảy ra 54 Tài nguyên chỉ có một thể hiện z Sử dụng thuật toán đồ thị chờ: Đồ thị chờ có được từ đồ thị cấp phát tài nguyên bằng cách xóa các đỉnh tài nguyên và nối các cung liên quan z Cung Pi→Pj có nghĩa là Pi đang chờ Pj giải phóng tài nguyên mà Pi cần z Cung Pi→Pj tồn tại trong đồ thị chờ nếu và chỉ nếu đồ thị cấp phát tài nguyên tương ứng có hai cung Pi→Rq và Rq→Pj với Rq là tài nguyên z Hệ thống có bế tắc nếu đồ thị chờ có chu trình z Để phát hiện bế tắc: Cần cập nhật đồ thị chờ và thực hiện định kỳ thuật toán phát hiện chu trình 10 55 56 Tài nguyên có nhiều thể hiện z Available: Vector m thành phần chỉ ra số lượng thể hiện của mỗi loại tài nguyên z Allocation: Ma trận nxm xác định số thể hiện của mỗi loại tài nguyên đang được cấp phát cho các tiến trình z Request: Ma trận nxm xác định yêu cầu hiện tại của mỗi tiến trình. Nếu Request[i][j]=k thì tiến trình Pi yêu cầu cấp phát k thể hiện của tài nguyên Rj. 57 Tài nguyên có nhiều thể hiện 1. Giả sử Work và Finish là các vector m và n thành phần. Khởi tạo Work=Available. Với mỗi i=0..n-1 gán Finish[i]=false nếu Allocation[i]≠0, ngược lại gán Finish[i]=true 2. Tìm i sao cho Finish[i]==false và Request[i]≤Work. Nếu không tìm thấy i, chuyển đến bước 4 3. Work=Work+Allocation, Finish[i]=true; chuyển đến bước 2 4. Nếu Finish[i]==false với 0≤i≤n-1 thì hệ thống đang bị bế tắc (và tiến trình Pi đang bế tắc). z Độ phức tạp tính toán của thuật toán: O(m.n2) 58 Sử dụng thuật toán phát hiện z Tần suất sử dụng phụ thuộc: z Tần suất xảy ra bế tắc z Bao nhiêu tiến trình bị ảnh hưởng bởi bế tắc? z Sử dụng thuật toán phát hiện: z Định kỳ: Có thể có nhiều chu trình trong đồ thị, không biết được tiến trình/request nào gây ra bế tắc z Khi có yêu cầu cấp phát tài nguyên: Tốn tài nguyên CPU 59 Khôi phục khi có bế tắc z Kết thúc tiến trình: z Kết thúc toàn bộ các tiến trình bị bế tắc (1) z Kết thúc từng tiến trình và dừng quá trình này khi bế tắc chấm dứt (2) z Tiến trình bị kết thúc ở (2) căn cứ vào: z Độ ưu tiên z Thời gian đã thực hiện và thời gian còn lại z Số lượng và các loại tài nguyên đã sử dụng z Các tài nguyên cần cấp phát thêm z Số lượng các tiến trình phải kết thúc z Tiến trình là tương tác hay xử lý theo lô (batch) 60 Khôi phục khi có bế tắc z Giải phóng tài nguyên một cách bắt buộc (preemption): z Chọn tài nguyên nào và tiến trình nào để thực hiện? z Khôi phục trạng thái của tiến trình đã chọn ở (1) như thế nào? z Làm thế nào để tránh tình trạng một tiến trình luôn bị bắt buộc giải phóng tài nguyên? 11 61 Tóm tắt z Khái niệm bế tắc z Các điều kiện cần để có bế tắc z Đồ thị phân phối tài nguyên z Các phương pháp xử lý bế tắc: Ngăn chặn và tránh bế tắc (thuật toán đồ thị cấp phát tài nguyên và thuật toán banker) z Khôi phục khi bế tắc đã xảy ra: Kết thúc tiến trình và preemption 62 Bài tập z Thực hiện lại ví dụ phát hiện bế tắc ở trang 264 trong giáo trình z Làm bài tập số 7.1 trong giáo trình (trang 268) z Làm bài tập số 7.11 trong giáo trình (trang 270)

Các file đính kèm theo tài liệu này :

• nlhdh_tuan5_9063.pdf

Source: https://vh2.com.vn
Category : Ứng Dụng