Bài giảng Hệ điều hành - Chương 2: Quản lý tiến trình - Đỗ Quốc Huy

ế tắc và xử lí bế tắc  5.1. Khái niệm bế tắc(Deadlock) Hệ thống gồm nhiều TT hoạt động đồng thời cùng sử dụng tài nguyên (TN) T N có nhiều loại (VD: CPU, bộ nhớ,..). Mỗi loại TN có nhiều đơn vị (VD: 2 CPU, 5 máy in..) Mỗi TT thường gồm dãy liên tục các thao tác Đòi hỏi tài nguyên : Nếu TN không có sẵn (đang được s/dụng bởi TT khác) ⇒ TT yêu cầu phải đợi Sử dụng TN theo yêu cầu (in ấn, đọc dữ liệu...) Giải phóng TN được cấp Khi các TT dùng chung ít nhất 2 TN , hệ thống có thể gặp " nguy hiểm " Khái niệm bế tắc Chương 2 Quản lí tiến trình  5.Bế tắc và xử lí bế tắc  5.1. Khái niệm bế tắc(Deadlock) Xét ví dụ: Hệ thống có 2 TT P 1 & P 2 2 TT P 1 & P 2 dùng chung 2 TN R 1 & R 2 R 1 được điều độ bởi đèn báo S 1 (S 1 ← 1) R 2 được điều độ bởi đèn báo S 2 (S 2 ← 1) Đoạn mã cho P 1 và P 2 Khái niệm bế tắc P(S 1 ) P(S 2 ) { Sử dụng R 1 &R 2 } V(S 1 ) V(S 2 ) Chương 2 Quản lí tiến trình  5.Bế tắc và xử lí bế tắc  5.1. Khái niệm bế tắc(Deadlock) Ví dụ P(S 1 ) P(S 2 ) { Sử dụng R 1 &R 2 } V(S 1 ) V(S 2 ) P(S 1 ) P(S 2 ) { Sử dụng R 1 &R 2 } V(S 1 ) V(S 2 ) Process P1 Process P2 Process P1 Process P2 t S2 = 1 S1 = 1 Chương 2 Quản lí tiến trình  5.Bế tắc và xử lí bế tắc  5.1. Khái niệm bế tắc(Deadlock) Ví dụ P(S 1 ) P(S 2 ) { Sử dụng R 1 &R 2 } V(S 1 ) V(S 2 ) P(S 1 ) P(S 2 ) { Sử dụng R 1 &R 2 } V(S 1 ) V(S 2 ) Process P1 Process P2 Process P1 Process P2 t S2 = 1 S1 = 0 P(S1) Chương 2 Quản lí tiến trình  5.Bế tắc và xử lí bế tắc  5.1. Khái niệm bế tắc(Deadlock) Ví dụ P(S 1 ) P(S 2 ) { Sử dụng R 1 &R 2 } V(S 1 ) V(S 2 ) P(S 1 ) P(S 2 ) { Sử dụng R 1 &R 2 } V(S 1 ) V(S 2 ) Process P1 Process P2 Process P1 Process P2 t S2 = 1 S1 = -1 P(S1) P(S1) P 2 block() Vào hàng đợi R1 Chương 2 Quản lí tiến trình  5.Bế tắc và xử lí bế tắc  5.1. Khái niệm bế tắc(Deadlock) Ví dụ P(S 1 ) P(S 2 ) { Sử dụng R 1 &R 2 } V(S 1 ) V(S 2 ) P(S 1 ) P(S 2 ) { Sử dụng R 1 &R 2 } V(S 1 ) V(S 2 ) Process P1 Process P2 Process P1 Process P2 t S2 = 0 S1 = -1 P(S1) P(S1) P 2 block() Vào hàng đợi R1 P(S2) Chương 2 Quản lí tiến trình  5.Bế tắc và xử lí bế tắc  5.1. Khái niệm bế tắc(Deadlock) Ví dụ P(S 1 ) P(S 2 ) { Sử dụng R 1 &R 2 } V(S 1 ) V(S 2 ) P(S 1 ) P(S 2 ) { Sử dụng R 1 &R 2 } V(S 1 ) V(S 2 ) Process P1 Process P2 Process P1 Process P2 t S2 = 0 S1 = 0 P(S1) P(S1) P(S2) Sử dụng R 1 &R 2 V(S1) wakeup(P 2 ) Chương 2 Quản lí tiến trình  5.Bế tắc và xử lí bế tắc  5.1. Khái niệm bế tắc(Deadlock) Ví dụ P(S 1 ) P(S 2 ) { Sử dụng R 1 &R 2 } V(S 1 ) V(S 2 ) P(S 1 ) P(S 2 ) { Sử dụng R 1 &R 2 } V(S 1 ) V(S 2 ) Process P1 Process P2 Process P1 Process P2 t S2 = -1 S1 = 0 P(S1) P(S1) P(S2) Sử dụng R 1 &R 2 V(S1) wakeup(P 2 ) P(S2) P 2 block() Vào hàng đợi R2 Chương 2 Quản lí tiến trình  5.Bế tắc và xử lí bế tắc  5.1. Khái niệm bế tắc(Deadlock) Ví dụ P(S 1 ) P(S 2 ) { Sử dụng R 1 &R 2 } V(S 1 ) V(S 2 ) P(S 1 ) P(S 2 ) { Sử dụng R 1 &R 2 } V(S 1 ) V(S 2 ) Process P1 Process P2 Process P1 Process P2 t S2 = 0 S1 = 0 P(S1) P(S1) P(S2) Sử dụng R 1 &R 2 V(S1) P(S2) V(S2) wakeup(P 2 ) Chương 2 Quản lí tiến trình  5.Bế tắc và xử lí bế tắc  5.1. Khái niệm bế tắc(Deadlock) Ví dụ P(S 1 ) P(S 2 ) { Sử dụng R 1 &R 2 } V(S 1 ) V(S 2 ) P(S 1 ) P(S 2 ) { Sử dụng R 1 &R 2 } V(S 1 ) V(S 2 ) Process P1 Process P2 Process P1 Process P2 t S2 = 0 S1 = 0 P(S1) P(S1) P(S2) Sử dụng R 1 &R 2 V(S1) P(S2) V(S2) wakeup(P 2 ) Sử dụng R 1 &R 2 Chương 2 Quản lí tiến trình  5.Bế tắc và xử lí bế tắc  5.1. Khái niệm bế tắc(Deadlock) Ví dụ P(S 1 ) P(S 2 ) { Sử dụng R 1 &R 2 } V(S 1 ) V(S 2 ) P(S 2 ) P(S 1 ) { Sử dụng R 1 &R 2 } V(S 1 ) V(S 2 ) Process P1 Process P2 Process P1 Process P2 t S2 = 1 S1 = 1 Chương 2 Quản lí tiến trình  5.Bế tắc và xử lí bế tắc  5.1. Khái niệm bế tắc(Deadlock) Ví dụ P(S 1 ) P(S 2 ) { Sử dụng R 1 &R 2 } V(S 1 ) V(S 2 ) P(S 2 ) P(S 1 ) { Sử dụng R 1 &R 2 } V(S 1 ) V(S 2 ) Process P1 Process P2 Process P1 Process P2 t S2 = 1 S1 = 0 P(S1) Chương 2 Quản lí tiến trình  5.Bế tắc và xử lí bế tắc  5.1. Khái niệm bế tắc(Deadlock) Ví dụ P(S 1 ) P(S 2 ) { Sử dụng R 1 &R 2 } V(S 1 ) V(S 2 ) P(S 2 ) P(S 1 ) { Sử dụng R 1 &R 2 } V(S 1 ) V(S 2 ) Process P1 Process P2 Process P1 Process P2 t S2 = 0 S1 = 0 P(S1) P(S2) Chương 2 Quản lí tiến trình  5.Bế tắc và xử lí bế tắc  5.1. Khái niệm bế tắc(Deadlock) Ví dụ P(S 1 ) P(S 2 ) { Sử dụng R 1 &R 2 } V(S 1 ) V(S 2 ) P(S 2 ) P(S 1 ) { Sử dụng R 1 &R 2 } V(S 1 ) V(S 2 ) Process P1 Process P2 Process P1 Process P2 t S2 = -1 S1 = 0 P(S1) P(S2) P(S2) P 1 block() Vào hàng đợi R2 Chương 2 Quản lí tiến trình  5.Bế tắc và xử lí bế tắc  5.1. Khái niệm bế tắc(Deadlock) Ví dụ P(S 1 ) P(S 2 ) { Sử dụng R 1 &R 2 } V(S 1 ) V(S 2 ) P(S 2 ) P(S 1 ) { Sử dụng R 1 &R 2 } V(S 1 ) V(S 2 ) Process P1 Process P2 Process P1 Process P2 t S2 = -1 S1 = -1 P(S1) P(S2) P(S2) P 1 block() Vào hàng đợi R2 P(S1) P 2 block() Vào hàng đợi R1 Chương 2 Quản lí tiến trình  5.Bế tắc và xử lí bế tắc  5.1. Khái niệm bế tắc(Deadlock) Ví dụ P(S 1 ) P(S 2 ) { Sử dụng R 1 &R 2 } V(S 1 ) V(S 2 ) P(S 2 ) P(S 1 ) { Sử dụng R 1 &R 2 } V(S 1 ) V(S 2 ) Process P1 Process P2 Process P1 Process P2 t S2 = -1 S1 = -1 P(S1) P(S2) P(S2) P 1 block() Vào hàng đợi R2 P(S1) P 2 block() Vào hàng đợi R1 Deadlock Chương 2 Quản lí tiến trình  5.Bế tắc và xử lí bế tắc  5.1. Khái niệm bế tắc(Deadlock) Định nghĩa Bế tắc là tình trạng Hai hay nhiều tiến trình cùng chờ đợi một sự kiện nào đó xảy ra Nếu không có sự tác động gì từ bên ngoài, thì sự chờ đợi đó là vô hạn Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.1. Khái niệm bế tắc(Deadlock) Khái niệm bế tắc Điều kiện xảy ra bế tắc Các phương pháp xử lý bế tắc Phòng ngừa bế tắc Phòng tránh bế tắc Nhận biết và khắc phục Chương 2 Quản lí tiến trình  5.Bế tắc và xử lí bế tắc  5.2. Điều kiện xảy ra bế tắc Cần có 4 điều kiện sau, không được thiếu điều kiện nào Tồn tại tài nguyên găng T N được sử dụng theo mô hình không phân chia được Chỉ có 1 TT dùng TN tại 1 thời điểm T T khác cũng yêu cầu TN ⇒ yêu cầu phải được hoãn lại tới khi TN được giải phóng Chờ đợi trước khi vào đoạn găng T T không được vào đoạn găng phải xếp hàng chờ đợi . Trong khi chờ đợi vẫn chiếm giữ các TN được cung cấp Không có hệ thống phân phối lại tài nguyên găng T N không thể được trưng dụng T N được giải phỏng chỉ bởi TT đang chiếm giữ khi đã hoàn thành nhiệm vụ Chờ đợi vòng tròn Tồn tại tập các TT {P 0 , P 2 , . . . , P n } đang đợi nhau theo kiểu: P 0 → R 1 → P 1 ; P 1 → R 2 → P 2 ; . . . P n−1 → R n →P n ; P n → R 0 → P 0 Chờ đợi vòng tròn tạo ra chu trình không kết thúc Điều kiện cần Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.2. Điều kiện xảy ra bế tắc Tài nguyên găng Chờ đợi trước khi vào đoạn găng Trưng dụng tài nguyên găng Chờ đợi vòng tròn Ví dụ: Bài toán bữa ăn tối của triết gia Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.2. Điều kiện xảy ra bế tắc Dùng để mô hình hóa tình trạng bế tắc trong hệ thống Là đ ồ thị định hướng gồm tập đỉnh V và tập cung E Tập đỉnh V được chia thành 2 kiểu đỉnh P = {P 1 , P 2 , . . . P n } Tập chứa tất cả các TT trong hệ thống R = {R 1 , R 2 , . . . R m } Tập chứa tất cả các kiểu TN trong hệ thống Tập các cung E gồm 2 loại Cung yêu cầu : đi từ TT P i tới TN R j : P i → R j Cung sử dụng : Đi từ TN R j tới TT P i : R j → P i Đồ thị cung cấp tài nguyên (Resource Allocation Graph) I Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.2. Điều kiện xảy ra bế tắc Khi 1 TT P i yêu cầu TN R j Cung yêu cầu P i → R j được chèn vào đồ thị Nếu yêu cầu được thỏa mãn , cung yêu cầu chuyển thành cung sử dung R j → P i Khi TT P i giải phóng TN R j , cung sử dụng R j → P i bị xóa khỏi đồ thị Đồ thị cung cấp tài nguyên (Resource Allocation Graph) II Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.2. Điều kiện xảy ra bế tắc Đỉnh kiểu TT Đỉnh kiểu TN Mỗi đơn vị của kiểu TN được biểu thị bằng 1 dấu chấm trong hình chữ nhật Cung yêu cầu đi từ đỉnh TT → đỉnh TN Cung sử dụng xuất phát từ dấu chấm bên trong đỉnh TN → đỉnh TT Đồ thị cung cấp tài nguyên : Biểu diễn đồ trong đồ thị P P P R R R Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.2. Điều kiện xảy ra bế tắc Trạng thái hệ thống 3 TT P 1 , P 2 , P 3 4 tài nguyên R 1 , R 2 , R 3 , R 4 P 3 yêu cầu tài nguyên R 4 Xuất hiện cung yêu cầu P 3 → R 4 Đồ thị cung cấp tài nguyên : Ví dụ P 1 P 2 P 3 R 2 R 3 R 1 R 4 Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.2. Điều kiện xảy ra bế tắc Trạng thái hệ thống 3 TT P 1 , P 2 , P 3 4 tài nguyên R 1 , R 2 , R 3 , R 4 P 3 yêu cầu tài nguyên R 4 Xuất hiện cung yêu cầu P 3 → R 4 Cung yêu cầu P 3 → R 4 chuyển thành cung sử dụng R 4 → P 3 Đồ thị cung cấp tài nguyên : Ví dụ P 1 P 2 P 3 R 2 R 3 R 1 R 4 Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.2. Điều kiện xảy ra bế tắc Trạng thái hệ thống 3 TT P 1 , P 2 , P 3 4 tài nguyên R 1 , R 2 , R 3 , R 4 P 3 yêu cầu tài nguyên R 4 Xuất hiện cung yêu cầu P 3 → R 4 Cung yêu cầu P 3 → R 4 chuyển thành cung sử dụng R 4 → P 3 P 3 Giải phóng tài nguyên R 4 Cung sử dụng R 4 → P 3 bị xóa khỏi đồ thị Đồ thị cung cấp tài nguyên : Ví dụ P 1 P 2 P 3 R 2 R 3 R 1 R 4 Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.2. Điều kiện xảy ra bế tắc Trạng thái hệ thống 3 TT P 1 , P 2 , P 3 4 tài nguyên R 1 , R 2 , R 3 , R 4 P 3 yêu cầu tài nguyên R 4 Xuất hiện cung yêu cầu P 3 → R 4 Cung yêu cầu P 3 → R 4 chuyển thành cung sử dụng R 4 → P 3 P 3 Giải phóng tài nguyên R 4 Cung sử dụng R 4 → P 3 bị xóa khỏi đồ thị P 3 yêu cầu tài nguyên R 1 Xuất hiện cung yêu cầu P 3 → R 1 Trên đồ thị xuất hiện chu trình Hệ thống bế tắc Đồ thị cung cấp tài nguyên : Ví dụ P 1 P 2 P 3 R 2 R 3 R 1 R 4 Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.2. Điều kiện xảy ra bế tắc Đồ thị không chứa chu trình, không bế tắc Nếu đồ thị chứa đựng chu trình Nếu TN chỉ có 1 đơn vị ⇒ Bế tắc Nếu TN có nhiều hơn 1 đơn vị: có khả năng bế tắc Đồ thị cung cấp tài nguyên : Lập luận cơ bản Chu trình trên đồ thị và tình trạng bế tắc có liên quan ? P 1 P 3 P 2 R 2 R 1 Đồ thị có chu trình nhưng hệ thống không bế tắc Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.3 Các phương pháp xử lý bế tắc Khái niệm bế tắc Điều kiện xảy ra bế tắc Các phương pháp xử lý bế tắc Phòng ngừa bế tắc Phòng tránh bế tắc Nhận biết và khắc phục Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.3. Các phương pháp xử lý bế tắc Phòng ngừa Áp dụng các biện pháp để đảm bảo hệ thống không bao giờ rơi vào tình trạng bế tắc Tốn kém Áp dụng cho hệ thống hay xảy ra bế tắc và tổn thất do bế tắc gây ra lớn Phòng tránh Kiểm tra từng yêu cầu TN của TT và không chấp nhận yêu cầu nếu việc cung cấp TN có khả năng dẫn đến tình trạng bế tắc Thường yêu cầu các thông tin phụ trợ Áp dụng cho hệ thống ít xảy ra bế tắc nhưng tổn hại lớn Nhận biết và khắc phục Cho phép hệ thống hoạt động bình thường ⇒có thể rơi vào tình trạng bế tắc Định kỳ kiểm tra xem bế tắc có đang xảy ra không Nếu đang bế tắc, áp dụng các biện pháp loại bỏ bế tắc Áp dụng cho hệ thống ít xảy ra bế tắc và thiệt hại không lớn Phương pháp Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5. 4 Phòng ngừa bế tắc Khái niệm bế tắc Điều kiện xảy ra bế tắc Các phương pháp xử lý bế tắc Phòng ngừa bế tắc Phòng tránh bế tắc Nhận biết và khắc phục Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.4 Phòng ngừa bế tắc Tác động vào 1 trong 4 điều kiện cần của bế tắc để nó không xảy ra Tài nguyên găng Chờ đợi trước khi vào đoạn găng T rưng dụng tài nguyên găng Chờ đợi vòng tròn Nguyên tắc Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.4 Phòng ngừa bế tắc Điều kiện tài nguyên găng Giảm bớt mức độ găng của hệ thống TN phân chia được (file chỉ đọc): Sử dụng đồng thời T N không phân chia được : Sử dụng không đồng thời Kỹ thuật SPOOL( Simultaneous peripheral operation on-line ) Không phân phối TN khi không thực sự cần thiết Chỉ một số ít TT có khả năng yêu cầu TN Chỉ printer daemon mới làm việc với máy in ⇒ Bế tắc cho TN máy in bị hủy bỏ Không phải TN nào cũng dùng kỹ thuật SPOOL được Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.4 Phòng ngừa bế tắc Điều kiện chờ đợi trước khi vào đoạn găng Nguyên tắc : Đảm bảo 1 TT xin TN chỉ khi không sở hữu bất kỳ TN nào khác Cung cấp trước TT xin toàn bộ TN ngay từ đầu và chỉ thực hiện khi đã có đầy đủ TN Hiệu quả sử dụng TN thấp TT chỉ sử dụng TN ở giai đoạn cuối? Tổng số TN đòi hỏi vượt quá khả năng của hệ thống? Giải phóng TN TT giải phóng tất cả TN trước khi xin (xin lại) TN mới Nhận xét Tốc độ thực hiện TT chậm Phải đảm bảo dữ liệu được giữ trong TN tạm giải phóng không bị mất Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.4 Phòng ngừa bế tắc Điều kiện chờ đợi trước khi vào đoạn găng : Ví dụ TT gồm 2 giai đoạn Sao chép dữ liệu từ băng từ sang một file trên đĩa từ Sắp xếp dữ liệu trong file và đưa ra máy in Phương pháp cung cấp trước Xin cả băng từ, file trên đĩa và máy in Lãng phí máy in giai đoạn đầu, băng từ giai đoạn cuối Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.4 Phòng ngừa bế tắc Điều kiện chờ đợi trước khi vào đoạn găng : Ví dụ TT gồm 2 giai đoạn Sao chép dữ liệu từ băng từ sang một file trên đĩa từ Sắp xếp dữ liệu trong file và đưa ra máy in Phương pháp cung cấp trước Xin cả băng từ, file trên đĩa và máy in Lãng phí máy in giai đoạn đầu, băng từ giai đoạn cuối Phương pháp giải phóng tài nguyên Xin băng từ và file trên đĩa cho giai đoạn 1 Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.4 Phòng ngừa bế tắc Điều kiện chờ đợi trước khi vào đoạn găng : Ví dụ TT gồm 2 giai đoạn Sao chép dữ liệu từ băng từ sang một file trên đĩa từ Sắp xếp dữ liệu trong file và đưa ra máy in Phương pháp cung cấp trước Xin cả băng từ, file trên đĩa và máy in Lãng phí máy in giai đoạn đầu, băng từ giai đoạn cuối Phương pháp giải phóng TN Xin băng từ và file trên đĩa cho giai đoạn 1 Giải phóng băng từ và file trên đĩa Xin file trên đĩa và máy in cho giai đoạn 2 Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.4 Phòng ngừa bế tắc Điều kiện trưng dụng tài nguyên găng Nguyên tắc : cho phép trưng dụng TN khi cần thiết TT P i xin tài nguyên R j R j sẵn có: Cung cấp R j cho P i R j không sẵn: ( R j bị chiếm bởi TT P k ) P k đang đợi TN khác Trưng dụng R j từ P k và cung cấp cho P i theo yêu cầu Thêm R j vào danh sách các TN đang thiếu của P k P k được thực hiện trở lại khi Có được TN đang thiếu Đòi lại được R j P k đang thực hiện P i phải đợi ( không giải phóng tài nguyên ) Cho phép trưng dụng TN nhưng chỉ khi cần thiết Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.4 Phòng ngừa bế tắc Điều kiện trưng dụng tài nguyên găng Nguyên tắc : cho phép trưng dụng tài nguyên khi cần thiết Chỉ áp dụng cho các TN có thể lưu trữ và khôi phục trạng thái dễ dàng ( CPU, không gian nhớ ) Khó có thể áp dụng cho các TN như máy in 1 TT bị trưng dụng nhiều lần ? Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.4 Phòng ngừa bế tắc Điều kiện chờ đợi vòng tròn Đặt ra một thứ tự toàn cục của tất cả các kiểu TN R = {R 1 , R 2 , . . . R n } Tập tất cả các kiểu TN Xây dựng hàm trật tự f : R → N Hàm f được xây dựng dựa trên trật tự sử dụng các TN f(Băng từ) = 1 f( Đĩa từ) = 5 f(Máy in) = 12 TT chỉ được yêu cầu TN theo trật tự tăng TT chiếm giữ TN kiểu R k chỉ được xin TN kiểu R j thỏa mãn f(R j ) > f(R k ) TT yêu cầu tới TN R k sẽ phải giải phóng tất cả TN R i thỏa mãn điều kiện f(R i ) ≥ f(R k ) Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.4 Phòng ngừa bế tắc Điều kiện chờ đợi vòng tròn TT chỉ được yêu cầu TN theo trật tự tăng TT chiếm giữ TN kiểu R k chỉ được xin TN kiểu R j thỏa mãn f(R j ) > f(R k ) TT yêu cầu tới TN R k sẽ phải giải phóng tất cả TN R i thỏa mãn điều kiện f(R i ) ≥ f(R k ) Chứng minh Giả thiết bế tắc xảy ra giữa các TT {P 1 , P 2 , . . . P m } R 1 → P 1 → R 2 → P 2 ⇒ f(R 1 ) < f(R 2 ) R 2 → P 2 → R 3 → P 3 ⇒ f(R 2 ) < f(R 3 ) . . . R m → P m → R 1 → P 1 ⇒ f(R m ) < f(R 1 ) f(R 1 ) < f(R 2 ) < . . . < f(R m ) < f(R 1 ) ⇒ Vô lý Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5. 5 Phòng tránh bế tắc Khái niệm bế tắc Điều kiện xảy ra bế tắc Các phương pháp xử lý bế tắc Phòng ngừa bế tắc Phòng tránh bế tắc Nhận biết và khắc phục Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5. 5 Phòng tránh bế tắc Ví dụ P1 P2 S2 = 1 S1 = 1 P(S1) P(S2) P(S2) P(S1) t S1 = 0 yêu cầu R 1 Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5. 5 Phòng tránh bế tắc Ví dụ P1 P2 S2 = 1 P(S1) P(S2) P(S2) P(S1) t S1 = 0 sử dụng R 1 yêu cầu R 2 Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5. 5 Phòng tránh bế tắc Ví dụ P1 P2 S2 = 0 P(S1) P(S2) P(S2) P(S1) t S1 = 0 sử dụng R 1 sử dụng R 2 yêu cầu R 1 Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5. 5 Phòng tránh bế tắc Ví dụ P1 P2 S2 = 0 P(S1) P(S2) P(S2) P(S1) t S1 = -1 Yêu cầu R 2 sử dụng R 2 yêu cầu R 1 sử dụng R 1 S2 = -1 DeadLock Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5. 5 Phòng tránh bế tắc Ví dụ P1 P2 S2 = 1 P(S1) P(S2) P(S2) P(S1) t S1 = 0 sử dụng R 1 yêu cầu R 2 Block(P2) Yêu cầu R 2 Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5. 5 Phòng tránh bế tắc Ví dụ P1 P2 S2 = 0 P(S1) P(S2) P(S2) P(S1) t S1 = 0 sử dụng R 1 yêu cầu R 2 Block(P2) sử dụng R 2 Nhận xét: Nếu b iết được chuỗi yêu cầu/giải phóng TN của các TT , hệ thống có thể đưa ra được chiến lược phân phối TN (chấp thuận hay phải đợi) cho mọi yêu cầu để bế tắc không xảy ra. Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.5 Phòng tránh bế tắc Nguyên tắc Phải biết trước các thông tin về TT và TN TT phải khai báo lượng TN lớn nhất mỗi loại sẽ yêu cầu khi thực hiện Quyết định dựa trên kết quả kiểm tra t / thái cung cấp TN (Resource-Allocation State) –T / thái hệ thống T / thái cung cấp t / nguyên xác định bởi các thông số : Số đơn vị TN có sẵn trong hệ thống đã được cấp cho mỗi TT lớn nhất mỗi TT có thể yêu cầu Nếu hệ thống an toàn , sẽ đáp ứng cho yêu cầu Thực hiện kiểm tra mỗi khi nhận được yêu cầu TN Mục đích: Đảm bảo t / thái hệ thống luôn an toàn Thời điểm ban đầu (chưa c/cấp tài nguyên), hệ thống an toàn Hệ thống chỉ cung cấp TN khi vẫn đảm bảo an toàn ⇒Hệ thống chuyển từ t/ thái an toàn này → t / thái an toàn khác Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.5 Phòng tránh bế tắc Trạng thái an toàn Trạng thái của hệ thống là an toàn khi Có thể cung cấp TN cho từng TT (đến yêu cầu lớn nhất) theo 1 trật tự nào đấy mà không xảy ra bế tắc Tồn tại chuỗi an toàn của tất cả các TT Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.5 Phòng tránh bế tắc Chuỗi an toàn Chuỗi tiến trình P={P1, P2, . . . , Pn} là an toàn nếu Với mỗi TT Pi, mọi yêu cầu TN trong tương lai đều có thể đáp ứng nhờ vào Lượng TN hiện có trong hệ thống TN đang chiếm giữ bởi tất cả các TT Pj(j < i) Trong chuỗi an toàn, khi Pi yêu cầu TN Nếu không thể đáp ứng ngay lập tức, Pi đợi cho tới khi Pj kết thúc (j < i) Khi Pj kết thúc và giải phóng TN , Pi sẽ nhận được TN cần thiết, thực hiện, giải phóng các TN đã được cung cấp và kết thúc Khi Pi kết thúc và giải phóng TN ⇒ Pi+1 sẽ nhận được TN cần thiêt và kết thúc được . . . Tất cả các TT trong chuỗi an toàn đều kết thúc được Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.5 Phòng tránh bế tắc Ví dụ minh họa Xem xét hệ thống gồm 3 TT P 1 , P 2 , P 3 và 1 TN R có 12 đơn vị (P 1 , P 2 , P 3 ) có thể yêu cầu tối đa tới (10, 4, 9) đơn vị TN R Tại thời điểm t 0 , (P 1 , P 2 , P 3 ) đã được cấp (5, 2, 2) đơn vị TN R Tại thời điểm hiện tại (t 0 ) hệ thống có an toàn? Hệ thống đã cấp (5 + 2 + 2) đơn vị, vậy còn lại 3 đơn vị (P 1 , P 2 , P 3 ) còn có thể yêu cầu (5, 2, 7) đơn vị Với 3 đơn vị hiện có, mọi yêu cầu của P 2 đều đáp ứng được ⇒ P 2 chắc chắn kết thúc được và sẽ giải phóng 2 đơn vị R Với 3 + 2 đơn vị, P 1 chắc chắn kết thúc,sẽ giải phóng 5 đơn vị Với 3 + 2 + 5 đơn vị P 3 chắc chắn kết thúc được Ở thời điểm t 0 P 1 , P 2 , P 3 đều chắc chắn kết thúc ⇒ hệ thống an toàn với dãy an toàn (P 2 , P 1 , P 3 ) Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.5 Phòng tránh bế tắc Ví dụ minh họa 2 Xem xét hệ thống gồm 3 TT P 1 , P 2 , P 3 và 1 tài nguyên R có 12 đơn vị Các TT (P 1 , P 2 , P 3 ) có thể yêu cầu tối đa tới (10, 4, 9) đơn vị TN R Tại thời điểm t 0 , các TT (P 1 , P 2 , P 3 ) đã được cấp (5, 2, 2) đơn vị TN R Tại thời điểm t 1, TT P 3 yêu cầu và được cấp 1 đơn vị TN R. Hệ thống có an toàn? Với 2 đơn vị hiện có, mọi yêu cầu của P 2 đều đáp ứng được ⇒ P 2 chắc chắn kết thúc, giải phóng 2 đơn vị R Khi P 2 kết thúc số TN sẵn có trong hệ thống là 4 Với 4 đơn vị TN , P 1 và P 3 đều có thể phải đợi khi xin thêm 5 đơn vị TN Vậy hệ thống không an toàn với dãy (P 1 , P 3 ) Nhận xét : Tại thời điểm t 1 nếu TT P 3 phải đợi khi yêu cầu thêm 1 đơn vị TN , bế tắc sẽ được loại trừ Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.5 Phòng tránh bế tắc Ví dụ minh họa Nhận xét Hệ thống an toàn ⇒ Các TT đều có thể kết thúc được ⇒ không xảy ra bế tắc Hệ thống không an toàn ⇒ Có khả năng xảy ra bế tắc Phương pháp Không để hệ thống rơi vào tình trạng không an toàn Kiểm tra mọi yêu cầu TN Nếu hệ thống vẫn an toàn khi cung cấp ⇒ Cung cấp Nếu hệ thống không an toàn khi cung cấp ⇒ Phải đợi Thuật toán Thuật toán dựa vào đồ thị cung cấp tài nguyên Thuật toán người quản lý nhà băng Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.5 Phòng tránh bế tắc Thuật toán dựa vào đồ thị cung cấp tài nguyên Sử dụng khi mỗi kiểu TN chỉ có 1 đơn vị Có chu trình, sẽ có bế tắc Thêm vào đồ thị loại cung mới: cung đòi hỏi Pi → Rj Cùng hướng với cung yêu cầu, thể hiện trong đồ thị −− > Cho biết Pi có thể yêu cầu Rj trong tương lai TT khi tham gia hệ thống, phải thêm tất cả các cung đòi hỏi tương ứng vào đồ thị Khi Pi yêu cầu Rj, cung đòi hỏi Pi → Rj chuyển thành cung yêu cầu Pi → Rj Khi Pi giải phóng Rj, cung sử dụng Rj → Pi chuyển thành cung đòi hỏi Pi → Rj Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.5 Phòng tránh bế tắc Thuật toán dựa vào đồ thị cung cấp tài nguyên Thuật toán: Yêu cầu tài nguyên Rj của TT Pi được thỏa mãn chỉ khi việc chuyển cung yêu cầu Pi → Rj thành cung sử dụng Rj → Pi không tạo chu trình trên đồ thị . Không chu trình: Hệ thống an toàn Có chu trình: Việc cung cấp tài nguyên đẩy hệ thống vào tình trạng không an toàn Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.5 Phòng tránh bế tắc Ví dụ Hệ thống: 2 TT P 1 , P 2 và 2 tài nguyên R 1 , R 2 , mỗi loại 1 đơn vị P 1 có thể xin R 1 , R 2 trong tương lai P 2 có thể xin R 1 , R 2 trong tương lai P 1 P 2 R 2 R 1 P 1 yêu cầu tài nguyên R 1 Cung đòi hỏi trở thành cung yêu cầu Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.5 Phòng tránh bế tắc Ví dụ Hệ thống: 2 TT P 1 , P 2 và 2 tài nguyên R 1 , R 2 , mỗi loại 1 đơn vị P 1 có thể xin R 1 , R 2 trong tương lai P 2 có thể xin R 1 , R 2 trong tương lai P 1 P 2 R 2 R 1 P 1 yêu cầu tài nguyên R 1 Cung đòi hỏi trở thành cung yêu cầu P 2 yêu cầu tài nguyên R 2 ⇒ cung đòi hỏi trở thành cung yêu cầu P 2 → R 2 Yêu cầu của P 1 được đáp ứng Cung yêu cầu thành cung sử dụng Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.5 Phòng tránh bế tắc Ví dụ Hệ thống: 2 TT P 1 , P 2 và 2 tài nguyên R 1 , R 2 , mỗi loại 1 đơn vị P 1 có thể xin R 1 , R 2 trong tương lai P 2 có thể xin R 1 , R 2 trong tương lai P 1 P 2 R 2 R 1 P 1 yêu cầu tài nguyên R 1 Cung đòi hỏi trở thành cung yêu cầu P 2 yêu cầu tài nguyên R 2 ⇒ cung đòi hỏi trở thành cung yêu cầu P 2 → R 2 Nếu đáp ứng ⇒Cung yêu cầu thành cung sử dụng ⇒ Khi P 1 yêu cầu R 2 ⇒ P 1 phải đợi ⇒ Khi P 2 yêu cầu R 1 ⇒ P 2 phải đợi Yêu cầu của P 1 được đáp ứng Cung yêu cầu thành cung sử dụng Hệ thống bế tắc Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.5 Phòng tránh bế tắc Ví dụ Hệ thống: 2 TT P 1 , P 2 và 2 tài nguyên R 1 , R 2 , mỗi loại 1 đơn vị P 1 có thể xin R 1 , R 2 trong tương lai P 2 có thể xin R 1 , R 2 trong tương lai P 1 P 2 R 2 R 1 P 1 yêu cầu tài nguyên R 1 Cung đòi hỏi trở thành cung yêu cầu P 2 yêu cầu tài nguyên R 2 ⇒ cung đòi hỏi trở thành cung yêu cầu P 2 → R 2 Nếu đáp ứng ⇒Cung yêu cầu thành cung sử dụng ⇒ Khi P 1 yêu cầu R 2 ⇒ P 1 phải đợi ⇒ Khi P 2 yêu cầu R 1 ⇒ P 2 phải đợi Yêu cầu của P 1 được đáp ứng Cung yêu cầu thành cung sử dụng Hệ thống bế tắc Yêu cầu của P 2 không được đáp ứng Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.5 Phòng tránh bế tắc Thuật toán người quản lý nhà băng: Giới thiệu Thích hợp cho các hệ thống gồm các kiểu TN có nhiều đơn vị 1 TT mới xuất hiện trong hệ thống cần khai báo số đơn vị lớn nhất của mỗi kiểu TN sẽ sử dụng Không được vượt quá tổng số TN của hệ thống Khi 1 TT yêu cầu TN , hệ thống kiểm tra liệu đáp ứng cho yêu cầu hệ thống có còn an toàn không Nếu hệ thống vẫn an toàn ⇒ Cung cấp TN cho yêu cầu Nếu hệ thống không an toàn ⇒ TT phải đợi Thuật toán cần Các cấu trúc dữ liệu biểu diễn t / thái phân phối TN Thuật toán kiểm tra tình trạng an toàn của hệ thông Thuật toán yêu cầu TN Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.5 Phòng tránh bế tắc Các cấu trúc dữ liệu I Hệ thống n số TT trong hệ thống m số kiểu TN trong hệ thống Các cấu trúc dữ liệu Available Vector chiều dài m cho biết số đơn vị TN sẵn có trong hệ thống. ( Available[3] = 8 ⇒? ) Max Ma trận n ∗m cho biết số lượng lớn nhất mỗi kiểu TN của từng TT . ( Max[2,3] = 5 ⇒? ) Allocation Ma trận n ∗ m cho biết số lượng mỗi kiểu TN đã cấp cho TT . ( Allocation[2,3] = 2 ⇒? ) Need Ma trận n ∗ m chỉ ra số lượng mỗi kiểu TN còn cần đến của từng TT . Need[2,3] = 3 ⇒? ) Need[i][j] = Max[i][j] - Allocation[i][j] Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.5 Phòng tránh bế tắc Các cấu trúc dữ liệu I Quy ước X, Y là các vector độ dài n X ≤ Y ⇔ X[i] ≤ Y[i] ∀i = 1, 2, . . . , n Các dòng của ma trận Max, Need , Allocation được xử lý như các vector Thuật toán tính toán trên các vector Các cấu trúc cục bộ Work vector độ dài m cho biết mỗi TN còn bao nhiêu Finish vector độ dài n , kiểu logic cho biết TT có chắc chắn kết thúc không Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.5 Phòng tránh bế tắc Thuật toán kiểm tra An toàn BOOL Safe( Current Resource-Allocation State ){ Work←Available for (i : 1 → n) Finish[i]←false flag← true While(flag){ flag←false for (i : 1 → n) if(Finish[i]=false AND Need[i] ≤Work){ Finish[i]← true Work ← Work+Allocation[i] flag← true } //endif } //endwhile for (i : 1 → n) if (Finish[i]=false)return false return true; } //End function Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.5 Phòng tránh bế tắc Ví dụ minh họa Xét hệ thống gồm 5 TT P 0 , P 1 , P 2 , P 3 , P 4 và 3 TN R 0 , R 1 , R 2 T N R 0 có 10 đơn vị, R 1 có 5 đơn vị, R 2 có 7 đơn vị Yêu cầu TN lớn nhất và lượng TN đã cấp của mỗi TT R0 R1 R2 P 0 7 5 3 P 1 3 2 2 P 2 9 0 2 P3 2 2 2 P4 4 3 3 Max R0 R1 R2 P 0 0 1 0 P 1 2 0 0 P 2 3 0 2 P3 2 1 1 P4 0 0 2 Allocation Hệ thống có an toàn? TT P1 yêu cầu thêm 1 đơn vị R0 và 2 đơn vị R2? TT P4 yêu cầu thêm 3 đơn vị R0 và 3 đơn vị R1? TT P0 yêu cầu thêm 2 đơn vị R1. Cung cấp? Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.5 Phòng tránh bế tắc Ví dụ minh họa : Kiểm tra tính an toàn Số tài nguyên còn sẵn trong hệ thống Avaiable (R 0 , R 1 , R 2 ) =(3, 3, 2) Yêu cầu còn lại của mỗi TT ( Need = Max - Allocation ) R 0 R 1 R 2 P 0 7 5 3 P 1 3 2 2 P 2 9 0 2 P 3 2 2 2 P 4 4 3 3 Max R0 R1 R2 P 0 0 1 0 P 1 2 0 0 P 2 3 0 2 P3 2 1 1 P4 0 0 2 Allocation R0 R1 R2 P 0 7 4 3 P 1 1 2 2 P 2 6 0 0 P3 0 1 1 P4 4 3 1 Need Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.5 Phòng tránh bế tắc Ví dụ minh họa : Kiểm tra tính an toàn Số tài nguyên còn sẵn trong hệ thống Avaiable (R 0 , R 1 , R 2 ) =(3, 3, 2) R 0 R 1 R 2 P 0 7 5 3 P 1 3 2 2 P 2 9 0 2 P 3 2 2 2 P 4 4 3 3 Max R0 R1 R2 P 0 0 1 0 P 1 2 0 0 P 2 3 0 2 P3 2 1 1 P4 0 0 2 Allocation R0 R1 R2 P 0 7 4 3 P 1 1 2 2 P 2 6 0 0 P3 0 1 1 P4 4 3 1 Need Tiến trình P 0 P 1 P 2 P 3 P 4 Finish F F F F F Work F F F T (5,3,2) (3,3,2) F T F (7,4,3) Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.5 Phòng tránh bế tắc Ví dụ minh họa : Kiểm tra tính an toàn Số tài nguyên còn sẵn trong hệ thống Avaiable (R 0 , R 1 , R 2 ) =(3, 3, 2) R 0 R 1 R 2 P 0 7 5 3 P 1 3 2 2 P 2 9 0 2 P 3 2 2 2 P 4 4 3 3 Max R0 R1 R2 P 0 0 1 0 P 1 2 0 0 P 2 3 0 2 P3 2 1 1 P4 0 0 2 Allocation R0 R1 R2 P 0 7 4 3 P 1 1 2 2 P 2 6 0 0 P3 0 1 1 P4 4 3 1 Need Tiến trình P 0 P 1 P 2 P 3 P 4 Finish F T F T T Work F F T (7,5,5) (7,4,5) T (10,5,7) Hệ thống an toàn (P1, P3, P4, P0, P2) Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.5 Phòng tránh bế tắc Thuật toán yêu cầu tài nguyên Request[i] Vector yêu cầu tài nguyên của TT Pi Request[3,2] = 2: TT P 3 yêu cầu 2 đơn vị tài nguyên R 2 Khi Pi yêu cầu TN , hệ thống thực hiện if(Request[i]>Need[i]) Error (Yêu cầu vượt quá khai báo TN ) if(Request[i]>Available) Block (Không đủ TN , TT phải đợi) Thiết lập trạng thái phân phối TN mới cho hệ thống Available = Available - Request[i] Allocation[i] = Allocation[i] + Request[i] Need[i] = Need[i] - Request[i] Phân phối TN dựa trên kết quả kiểm tra tính an toàn của trạng thái phân phối TN mới if (Safe(New Resource Allocation State)) Phân phối cho Pi theo yêu cầu else TT Pi phải đợi Khôi phục lại trạng thái cũ (Available, Allocation,Need) Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.5 Phòng tránh bế tắc Ví dụ minh họa : P 1 yêu cầu (1, 0, 2) Request[1]≤Available ((1, 0, 2) ≤ (3, 3, 2)) ⇒ Có thể cung cấp Nếu cung cấp : Available = ( 2 , 3, 0) R0 R1 R2 P 0 0 1 0 P 1 3 0 2 P 2 3 0 2 P3 2 1 1 P4 0 0 2 Allocation at t1 R0 R1 R2 P 0 0 1 0 P 1 2 0 0 P 2 3 0 2 P3 2 1 1 P4 0 0 2 Allocation Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.5 Phòng tránh bế tắc Ví dụ minh họa : P 1 yêu cầu (1, 0, 2) Request[1]≤Available ((1, 0, 2) ≤ (3, 3, 2)) ⇒ Có thể cung cấp Nếu cung cấp : Available = ( 2 , 3, 0) R0 R1 R2 P 0 7 4 3 P 1 0 2 0 P 2 6 0 0 P3 0 1 1 P4 4 3 1 Need at t1 R 0 R 1 R 2 P 0 7 5 3 P 1 3 2 2 P 2 9 0 2 P 3 2 2 2 P 4 4 3 3 Max R0 R1 R2 P 0 7 4 3 P 1 1 2 2 P 2 6 0 0 P3 0 1 1 P4 4 3 1 Need Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.5 Phòng tránh bế tắc Ví dụ minh họa : P 1 yêu cầu (1, 0, 2) Request[1]≤Available ((1, 0, 2) ≤ (3, 3, 2)) ⇒ Có thể cung cấp Nếu cung cấp : Available = ( 2 , 3, 0) R0 R1 R2 P 0 0 1 0 P 1 3 0 2 P 2 3 0 2 P3 2 1 1 P4 0 0 2 Allocation R0 R1 R2 P 0 7 4 3 P 1 0 2 0 P 2 6 0 0 P3 0 1 1 P4 4 3 1 Need Tiến trình P 0 P 1 P 2 P 3 P 4 Finish F F F F F Work (2,3,0) F Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.5 Phòng tránh bế tắc Ví dụ minh họa : P 1 yêu cầu (1, 0, 2) Request[1]≤Available ((1, 0, 2) ≤ (3, 3, 2)) ⇒ Có thể cung cấp Nếu cung cấp : Available = ( 2 , 3, 0) R0 R1 R2 P 0 0 1 0 P 1 3 0 2 P 2 3 0 2 P3 2 1 1 P4 0 0 2 Allocation R0 R1 R2 P 0 7 4 3 P 1 0 2 0 P 2 6 0 0 P3 0 1 1 P4 4 3 1 Need Tiến trình P 0 P 1 P 2 P 3 P 4 Finish F F F F F Work (2,3,0) F Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.5 Phòng tránh bế tắc Ví dụ minh họa : P 1 yêu cầu (1, 0, 2) Request[1]≤Available ((1, 0, 2) ≤ (3, 3, 2)) ⇒ Có thể cung cấp Nếu cung cấp : Available = ( 2 , 3, 0) R0 R1 R2 P 0 0 1 0 P 1 3 0 2 P 2 3 0 2 P3 2 1 1 P4 0 0 2 Allocation R0 R1 R2 P 0 7 4 3 P 1 0 2 0 P 2 6 0 0 P3 0 1 1 P4 4 3 1 Need Tiến trình P 0 P 1 P 2 P 3 P 4 Finish F T F F F Work (5,3,2) F Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.5 Phòng tránh bế tắc Ví dụ minh họa : P 1 yêu cầu (1, 0, 2) Request[1]≤Available ((1, 0, 2) ≤ (3, 3, 2)) ⇒ Có thể cung cấp Nếu cung cấp : Available = ( 2 , 3, 0) R0 R1 R2 P 0 0 1 0 P 1 3 0 2 P 2 3 0 2 P3 2 1 1 P4 0 0 2 Allocation R0 R1 R2 P 0 7 4 3 P 1 0 2 0 P 2 6 0 0 P3 0 1 1 P4 4 3 1 Need Tiến trình P 0 P 1 P 2 P 3 P 4 Finish F T F F F Work (5,3,2) F Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.5 Phòng tránh bế tắc Ví dụ minh họa : P 1 yêu cầu (1, 0, 2) Request[1]≤Available ((1, 0, 2) ≤ (3, 3, 2)) ⇒ Có thể cung cấp Nếu cung cấp : Available = ( 2 , 3, 0) R0 R1 R2 P 0 0 1 0 P 1 3 0 2 P 2 3 0 2 P3 2 1 1 P4 0 0 2 Allocation R0 R1 R2 P 0 7 4 3 P 1 0 2 0 P 2 6 0 0 P3 0 1 1 P4 4 3 1 Need Tiến trình P 0 P 1 P 2 P 3 P 4 Finish F T F T F Work (7,4,3) F Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.5 Phòng tránh bế tắc Ví dụ minh họa : P 1 yêu cầu (1, 0, 2) Request[1]≤Available ((1, 0, 2) ≤ (3, 3, 2)) ⇒ Có thể cung cấp Nếu cung cấp : Available = ( 2 , 3, 0) R0 R1 R2 P 0 0 1 0 P 1 3 0 2 P 2 3 0 2 P3 2 1 1 P4 0 0 2 Allocation R0 R1 R2 P 0 7 4 3 P 1 0 2 0 P 2 6 0 0 P3 0 1 1 P4 4 3 1 Need Tiến trình P 0 P 1 P 2 P 3 P 4 Finish F T F T T Work (7,4,5) F Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.5 Phòng tránh bế tắc Ví dụ minh họa : P 1 yêu cầu (1, 0, 2) Request[1]≤Available ((1, 0, 2) ≤ (3, 3, 2)) ⇒ Có thể cung cấp Nếu cung cấp : Available = ( 2 , 3, 0) R0 R1 R2 P 0 0 1 0 P 1 3 0 2 P 2 3 0 2 P3 2 1 1 P4 0 0 2 Allocation R0 R1 R2 P 0 7 4 3 P 1 0 2 0 P 2 6 0 0 P3 0 1 1 P4 4 3 1 Need Tiến trình P 0 P 1 P 2 P 3 P 4 Finish T T F T T Work (7,5,5) F Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.5 Phòng tránh bế tắc Ví dụ minh họa : P 1 yêu cầu (1, 0, 2) Request[1]≤Available ((1, 0, 2) ≤ (3, 3, 2)) ⇒ Có thể cung cấp Nếu cung cấp : Available = ( 2 , 3, 0) R0 R1 R2 P 0 0 1 0 P 1 3 0 2 P 2 3 0 2 P3 2 1 1 P4 0 0 2 Allocation R0 R1 R2 P 0 7 4 3 P 1 0 2 0 P 2 6 0 0 P3 0 1 1 P4 4 3 1 Need Tiến trình P 0 P 1 P 2 P 3 P 4 Finish T T T T T Work (10,5,7) Yêu cầu được chấp nhận Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.5 Phòng tránh bế tắc Ví dụ minh họa : (tiếp tục) TT P 4 yêu cầu thêm 3 đơn vị R 0 và 3 đơn vị R 2 Request[4] = (3, 0, 3) Available = (2, 3, 0) ⇒ Không đủ tài nguyên, P 4 phải đợi TT P 0 yêu cầu thêm 2 đơn vị R 1 Request[0]≤Available ((0, 2, 0) ≤ (2, 3, 0)) ⇒ Có thể cung cấp Nếu cung cấp : Available = (2 , 1, 0) Thực hiện thuật toán an toàn ⇒ Tất cả các TT đều có thể không kết thúc ⇒ Nếu chấp nhận , hệ thống rơi vào trạng thái không an toàn ⇒ Đủ tài nguyên nhưng không cung cấp . P 0 phải đợi Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.6 Nhận biết và khắc phục Khái niệm bế tắc Điều kiện xảy ra bế tắc Các phương pháp xử lý bế tắc Phòng ngừa bế tắc Phòng tránh bế tắc Nhận biết và khắc phục Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.6 Nhận biết và khắc phục Giới thiệu Nguyên tắc Không áp dụng các biện pháp phòng ngừa hoặc phòng tránh, để cho bế tắc xảy ra Định kỳ kiểm tra xem bế tắc có đang xảy ra không. Nếu có tìm cách khắc phục Để thực hiện, hệ thống phải cung cấp Thuật toán xác định hệ thống đang bế tắc không Biện pháp kỹ thuật chữa bế tắc Nhận biết bế tắc Thuật toán dựa trên đồ thị cung cấp TN Thuật toán chỉ ra bế tắc tổng quát Khắc phục bế tắc Kết thúc TT Trưng dụng tài nguyên Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.6 Nhận biết và khắc phục Thuận toán dựa trên đồ thị cung cấp tài nguyên I Áp dụng khi mỗi TN trong hệ thống có 1 đơn vị K / tra hệ thống có bế tắc bằng cách kiểm tra chu trình trên đồ thị Nếu trên đồ thị có chu trình , hệ thống đang bế tắc Định kỳ gọi tới các thuật toán kiểm tra chu trình trên đồ thị Thuật toán đòi hỏi n 2 thao tác (n: số đỉnh của đồ thị) Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.6 Nhận biết và khắc phục Thuận toán dựa trên đồ thị cung cấp tài nguyên II Sử dụng đồ thị chờ đợi - phiên bản thu gọn của đồ thị cung cấp tài nguyên Chỉ có các đỉnh dạng TT Cung chờ đợi Pi → Pj: TT Pi đang đợi TT Pj giải phóng tài nguyên Pi cần Cung chờ đợi Pi → Pj tồn tại trên đồ thị đợi khi và chỉ khi trên đồ thị phân phối tài nguyên tương ứng tồn tại đồng thời cung yêu cầu Pi → R và cung sử dụng R → Pj Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.6 Nhận biết và khắc phục Đồ thị chờ đợi: Ví dụ P 1 P 3 R 2 R 3 R 1 R 4 R 5 P 5 P 2 P 4 P 1 P 3 P 5 P 2 P 4 Đồ thị chờ đợi Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.6 Nhận biết và khắc phục Thuật toán chỉ ra bế tắc tổng quát : Giới thiệu Áp dụng: hệ thống có các kiểu tài nguyên gồm nhiều đơn vị Thuật toán: tương tự thuật toán người quản lý nhà băng Các cấu trúc dữ liệu Available Vector độ dài m: Tài nguyên sẵn có Allocation Ma trận n ∗ m: Tài nguyên đã cấp Request Ma trận n ∗ m: Tài nguyên yêu cầu Các cấu trúc cục bộ Work Vector độ dài m cho biết TN hiện đang có Finish Vector độ dài n cho biết TT có thể kết thúc không Các qui ước Quan hệ ≤ giữa các Vector Xử lý các dòng ma trận n ∗ m như các vector Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.6 Nhận biết và khắc phục Thuật toán chỉ ra bế tắc tổng quát BOOL Deadlock(Current Resource-Allocation State) { Work←Available for (i : 1 → n) if(Allocation[i] 0) Finish[i]←false else Finish[i] ← true; flag← true w hile(flag){ flag←false for (i : 1 → n) if (Finish[i]=false AND Request [i] ≤Work){ Finish[i]← true Work ← Work+Allocation[i] flag← true } //endif } //endwhile for (i : 1 → n) if (Finish[i]=false)return true; return fals e; } //End function //Allocation= 0 không nằm trong chu trình đợi //Finish[i] = false, tiến trình Pi đang bị bế tắc Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.6 Nhận biết và khắc phục Ví dụ minh họa 5 tiến trình P 0 , P 1 , P 2 , P 3 , P 4 ; 3 tài nguyên R 0 , R 1 , R 2 Tài nguyên R 0 có 7 đơn vị, R 1 có 2 đơn vị, R 2 có 6 đơn vị Trạng thái cung cấp tài nguyên tại thời điểm t 0 R0 R1 R2 P 0 0 0 0 P 1 2 0 2 P 2 0 0 0 P3 1 0 0 P4 6 0 2 Request R0 R1 R2 P 0 0 1 0 P 1 2 0 0 P 2 3 0 3 P3 2 1 1 P4 0 0 2 Allocation Tài nguyên hiện có (R 0 , R 1 , R 2 ) =(0, 0, 0) Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.6 Nhận biết và khắc phục Ví dụ minh họa R0 R1 R2 P 0 0 0 0 P 1 2 0 2 P 2 0 0 0 P3 1 0 0 P4 6 0 2 Request R0 R1 R2 P 0 0 1 0 P 1 2 0 0 P 2 3 0 3 P3 2 1 1 P4 0 0 2 Allocation Tài nguyên hiện có (R 0 , R 1 , R 2 ) =(0, 0, 0) Tiến trình P 0 P 1 P 2 P 3 P 4 Finish F F F F F Work (0,0,0) F Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.6 Nhận biết và khắc phục Ví dụ minh họa R0 R1 R2 P 0 0 0 0 P 1 2 0 2 P 2 0 0 0 P3 1 0 0 P4 6 0 2 Request R0 R1 R2 P 0 0 1 0 P 1 2 0 0 P 2 3 0 3 P3 2 1 1 P4 0 0 2 Allocation Tài nguyên hiện có (R 0 , R 1 , R 2 ) =(0, 0, 0) Tiến trình P 0 P 1 P 2 P 3 P 4 Finish T F F F F Work (0,1,0) F F Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.6 Nhận biết và khắc phục Ví dụ minh họa R0 R1 R2 P 0 0 0 0 P 1 2 0 2 P 2 0 0 0 P3 1 0 0 P4 6 0 2 Request R0 R1 R2 P 0 0 1 0 P 1 2 0 0 P 2 3 0 3 P3 2 1 1 P4 0 0 2 Allocation Tài nguyên hiện có (R 0 , R 1 , R 2 ) =(0, 0, 0) Tiến trình P 0 P 1 P 2 P 3 P 4 Finish T F T F F Work ( 3,1,3 ) F Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.6 Nhận biết và khắc phục Ví dụ minh họa R0 R1 R2 P 0 0 0 0 P 1 2 0 2 P 2 0 0 0 P3 1 0 0 P4 6 0 2 Request R0 R1 R2 P 0 0 1 0 P 1 2 0 0 P 2 3 0 3 P3 2 1 1 P4 0 0 2 Allocation Tài nguyên hiện có (R 0 , R 1 , R 2 ) =(0, 0, 0) Tiến trình P 0 P 1 P 2 P 3 P 4 Finish T F T T F Work ( 5,2,4 ) F Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.6 Nhận biết và khắc phục Ví dụ minh họa R0 R1 R2 P 0 0 0 0 P 1 2 0 2 P 2 0 0 0 P3 1 0 0 P4 6 0 2 Request R0 R1 R2 P 0 0 1 0 P 1 2 0 0 P 2 3 0 3 P3 2 1 1 P4 0 0 2 Allocation Tài nguyên hiện có (R 0 , R 1 , R 2 ) =(0, 0, 0) Tiến trình P 0 P 1 P 2 P 3 P 4 Finish T F T T F Work ( 5,2,4 ) F Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.6 Nhận biết và khắc phục Ví dụ minh họa R0 R1 R2 P 0 0 0 0 P 1 2 0 2 P 2 0 0 0 P3 1 0 0 P4 6 0 2 Request R0 R1 R2 P 0 0 1 0 P 1 2 0 0 P 2 3 0 3 P3 2 1 1 P4 0 0 2 Allocation Tài nguyên hiện có (R 0 , R 1 , R 2 ) =(0, 0, 0) Tiến trình P 0 P 1 P 2 P 3 P 4 Finish T T T T F Work ( 7,2,4 ) F Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.6 Nhận biết và khắc phục Ví dụ minh họa R0 R1 R2 P 0 0 0 0 P 1 2 0 2 P 2 0 0 0 P3 1 0 0 P4 6 0 2 Request R0 R1 R2 P 0 0 1 0 P 1 2 0 0 P 2 3 0 3 P3 2 1 1 P4 0 0 2 Allocation Tài nguyên hiện có (R 0 , R 1 , R 2 ) =(0, 0, 0) Tiến trình P 0 P 1 P 2 P 3 P 4 Finish T T T T T Work ( 7,2,6 ) Hệ thống không bế tắc (P 0 , P 2 , P 3 , P 1 , P 4 ) Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.6 Nhận biết và khắc phục Ví dụ minh họa tại thời điểm t 1 : P 2 yêu cầu thêm 1 đơn vị tài nguyên R 2 Trạng thái cung cấp tài nguyên R0 R1 R2 P 0 0 0 0 P 1 2 0 2 P 2 0 0 1 P3 1 0 0 P4 6 0 2 Request R0 R1 R2 P 0 0 1 0 P 1 2 0 0 P 2 3 0 3 P3 2 1 1 P4 0 0 2 Allocation Tài nguyên hiện có (R 0 , R 1 , R 2 ) =(0, 0, 0) Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.6 Nhận biết và khắc phục Ví dụ minh họa R0 R1 R2 P 0 0 0 0 P 1 2 0 2 P 2 0 0 1 P3 1 0 0 P4 6 0 2 Request R0 R1 R2 P 0 0 1 0 P 1 2 0 0 P 2 3 0 3 P3 2 1 1 P4 0 0 2 Allocation Tiến trình P 0 P 1 P 2 P 3 P 4 Finish F F F F F Work (0,0,0) F Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.6 Nhận biết và khắc phục Ví dụ minh họa R0 R1 R2 P 0 0 0 0 P 1 2 0 2 P 2 0 0 1 P3 1 0 0 P4 6 0 2 Request R0 R1 R2 P 0 0 1 0 P 1 2 0 0 P 2 3 0 3 P3 2 1 1 P4 0 0 2 Allocation Tiến trình P 0 P 1 P 2 P 3 P 4 Finish T F F F F Work (0,1,0) F F F F Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.6 Nhận biết và khắc phục Ví dụ minh họa R0 R1 R2 P 0 0 0 0 P 1 2 0 2 P 2 0 0 1 P3 1 0 0 P4 6 0 2 Request R0 R1 R2 P 0 0 1 0 P 1 2 0 0 P 2 3 0 3 P3 2 1 1 P4 0 0 2 Allocation Tiến trình P 0 P 1 P 2 P 3 P 4 Finish T F F F F Work (0,1,0) F F F F P 0 có thể kết thúc nhưng hệ thống đang bế tắc. Các tiến trình đang chờ đợi lẫn nhau (P 1 , P 2 , P 3 , P 4 ) Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.6 Nhận biết và khắc phục Khắc phục bế tắc: Phương pháp kết thúc tiến trình Nguyên tắc : Hủy bỏ các TT đang trong tình trạng bế tắc và lấy lại tài nguyên đã cấp cho TT bị hủy bỏ Hủy bỏ tất cả các TT Hủy bỏ lần lượt TT cho tới khi bế tắc không xảy ra Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.6 Nhận biết và khắc phục Khắc phục bế tắc: Phương pháp kết thúc tiến trình Hủy bỏ tất cả các TT Nhanh chóng loại bỏ bế tắc Quá tốn kém Các TT bị hủy bỏ có thể gần kết thúc Hủy bỏ lần lượt TT cho tới khi bế tắc không xảy ra Sau khi hủy bỏ, phải kiểm tra xem bế tắc còn tồn tại không Thuật toán kiểm tra bế tắc có độ phức tạp m ∗ n 2 Cần chỉ ra thứ tự TT bị hủy bỏ để phá vỡ bế tắc Độ ưu tiên. T hời gian tồn tại , thực hiện Tài nguyên đang chiếm giữ, còn cần để kết thúc . . . Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.6 Nhận biết và khắc phục Khắc phục bế tắc: Phương pháp kết thúc tiến trình Vấn đề hủy bỏ TT TT đang cập nhật file ⇒ File không hoàn chỉnh TT sử dụng máy in ⇒ Reset trạng thái máy in Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.6 Nhận biết và khắc phục Khắc phục bế tắc: Phương pháp trưng dụng tài nguyên Nguyên tắc: Trưng dụng liên tục một vài tài nguyên từ một số TT đang bế tắc cho các TT khác đến khi bế tắc được hủy bỏ Các vấn đề cần quan tâm Lựa chọn nạn nhân (victim) Quay lui (Rollback) Đói tài nguyên (Starvation) Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.6 Nhận biết và khắc phục Khắc phục bế tắc: Phương pháp trưng dụng tài nguyên Lựa chọn nạn nhân (victim) Tài nguyên nào và tiến trình nào ? Trật tự trưng dụng để chi phí nhỏ nhất Lượng tài nguyên nắm giữ, thời gian sử dụng. . . Quay lui (Rollback) Quay lui tới một trạng thái an toàn trước đó và bắt đầu lại Yêu cầu lưu giữ thông tin trạng thái của TT đang thực hiện Đói tài nguyên (Starvation) 1 TT bị trưng dụng quá nhiều lần ⇒chờ đợi vô hạn Giải pháp: ghi lại số lần bị trưng dụng Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.6 Nhận biết và khắc phục Cách xử lý bế tắc khác ? Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  Tổng kết Bế tắc là tình trạng 2 hay nhiều TT cùng chờ đợi độc lập 1 sự kiện chỉ có thể xảy ra bởi sự hoạt động của các TT đang đợi Bế tắc xảy ra khi hội đủ 4 điều kiện Tồn tại tài nguyên găng Phải chờ đợi trước khi vào đoạn găng Không tồn tại hệ thống phân phối lại tài nguyên Tồn tại hiện tượng chờ đợi vòng tròn Để xử lý bế tắc có 3 lớp thuật toán Phòng ngừa bế tắc Tác động vào các điều kiện xảy ra bế tắc Dự báo và phòng tránh Ngăn ngừa hệ thống rơi vào tình trạng có thể dẫn đến bế tắc Nhận biết và khắc phục Cho phép bế tắc xảy ra, chỉ ra bế tắc và khắc phục sau Chương 2 Quản lí tiến trình 5.Bế tắc và xử lí bế tắc  5.6 Nhận biết và khắc phục Ví dụ minh họa 5 tiến trình P 0 , P 1 , P 2 , P 3 , P 4 ; 3 tài nguyên R 0 , R 1 , R 2 Tài nguyên R 0 có 6 đơn vị, R 1 có 4 đơn vị, R 2 có 7 đơn vị Trạng thái cung cấp tài nguyên tại thời điểm t 0 R0 R1 R2 P 0 0 0 0 P 1 2 1 2 P 2 0 0 2 P3 1 0 0 P4 6 0 2 Request R0 R1 R2 P 0 0 1 1 P 1 1 0 0 P 2 3 0 2 P3 2 1 1 P4 0 2 2 Allocation