Bài giảng Hệ điều hành – Chương 6: Deadlocks (Phần 2) – Trường Đại học công nghệ thông tin – Tài liệu, ebook

34 trang

| Chia sẻ : dntpro1256

| Lượt xem: 1239

| Lượt tải : 0

Bạn đang xem trước 20 trang tài liệu Bài giảng Hệ điều hành – Chương 6: Deadlocks (Phần 2) – Trường Đại học công nghệ thông tin, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên

HỆ ĐIỀU HÀNH Chương 6 – Deadlocks ( 2 ) 14/03/2017 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 1 Câu hỏi ôn tập chương 6-1  Deadlock là gì ? Cho ví dụ trong trong thực tiễn ?  Một tiến trình khi nào gọi là bị deadlock ? trì hoãn vô hạn định ?  Khi nào sẽ xảy ra deadlock ?  Các giải pháp xử lý deadlock ?  Làm gì để ngăn deadlock ?  Làm gì để tránh deadlock ? 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 2 Câu hỏi ôn tập chương 6-1 ( tt )  Sơ đồ sau có xảy ra deadlock ? 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 3 R1 R3 P1 P2 P3 R2 R4 Deadlock ? Câu hỏi ôn tập chương 6-1 ( tt )  Hệ thông có 18 tap drive và 4 tiến trình P0, P1, P2, P3 Tại thời gian to 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 4 Max Allocation Need Available P0 10 5 5 5 P1 4 2 2 3 P2 15 2 13 16 P3 10 6 4 10 Mục tiêu chương 6-2  Hiểu được thêm những chiêu thức xử lý deadlock  Tránh deadlock  Phát hiện  Phục hồi  Hiểu và hiện thực được giải thuật Banker 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 5 Nội dung chương 6-2 Giải thuật đồ thị cấp phép tài nguyên  Giải thuật banker  Phát hiện deadlock  Phục hồi deadlock  1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 6 Giải thuật đồ thị cấp phép tài nguyên 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 7 Giải thuật Banker Mỗi loại tài nguyên có nhiều thực thể  Bắt chước nhiệm vụ ngân hàng nhà nước  Điều kiện :  Mỗi tiến trình phải khai báo số lượng thực thể tối đa của mỗi loại tài  nguyên mà nó cần Khi tiến trình nhu yếu tài nguyên thì hoàn toàn có thể phải đợi  Khi tiến trình đã có được rất đầy đủ tài nguyên thì phải hoàn trả trong  một khoảng chừng thời hạn hữu hạn nào đó 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 8 Cấu trúc tài liệu cho giải thuật Banker n : số tiến trình ; m : số loại tài nguyên Available : vector độ dài m  Available [ j ] = k  loại tài nguyên Rj có k instance chuẩn bị sẵn sàng Max : ma trận n x m  Max [ i, j ] = k  tiến trình Pi nhu yếu tối đa k instance của loại tài nguyên Rj Allocation : vector độ dài n x m  Allocation [ i, j ] = k  Pi đã được cấp phép k instance của Rj Need : vector độ dài n x m  Need [ i, j ] = k  Pi cần thêm k instance của Rj => Need [ i, j ] = Max [ i, j ]  – Allocation [ i, j ] 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 9 Ký hiệu Y  X  Y [ i ]  X [ i ], ví dụ ( 0, 3, 2, 1 )  ( 1, 7, 3, 2 ) Giải thuật bảo đảm an toàn 1. Gọi Work và Finish là hai vector độ dài là m và n. Khởi tạo Work = Available Finish [ i ] = false, i = 0, 1, , n-1 2. Tìm i thỏa ( a ) Finish [ i ] = false ( b ) Needi ≤ Work ( hàng thứ i của Need ) Nếu không sống sót i như vậy, đến bước 4. 3. Work = Work + Allocationi Finish [ i ] = true quay về bước 2 4. Nếu Finish [ i ] = true, i = 1, , n, thì mạng lưới hệ thống đang ở trạng thái safe 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 10 Giải thuật Banker – Ví dụ  5 tiến trình P0, , P4  3 loại tài nguyên :  A ( 10 thực thể ), B ( 5 thực thể ), C ( 7 thực thể )  Sơ đồ cấp phép trong mạng lưới hệ thống tại thời gian T0 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 11 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 Giải thuật Banker – Ví dụ ( tt )  Chuỗi bảo đảm an toàn 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 12 Giải thuật nhu yếu tài nguyên cho tiến trình Pi Requesti là request vector của process Pi. Requesti [ j ] = k  Pi cần k instance của tài nguyên Rj. 1. Nếu Requesti ≤ Needi thì đến bước 2. Nếu không, báo lỗi vì tiến trình đã vượt nhu yếu tối đa. 2. Nếu Requesti ≤ Available thì qua bước 3. Nếu không, Pi phải chờ vì tài nguyên không còn đủ để cấp phép. 3. Giả định cấp phép tài nguyên phân phối nhu yếu của Pi bằng cách update trạng thái mạng lưới hệ thống như sau : Available = Available – Requesti Allocationi = Allocationi + Requesti Needi = Needi – Requesti 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 13 Giải thuật nhu yếu tài nguyên cho tiến trình Pi ( tt ) Áp dụng giải thuật kiểm tra trạng thái an toàn lên trạng  thái trên mạng lưới hệ thống mới Nếu trạng thái là safe thì tài nguyện được cấp thực sự  cho Pi Nếu trạng thái là unsafe thì Pi phải đợi và hồi sinh  trạn thái Available = Available + Requesti Allocationi = Allocationi – Requesti Needi = Needi + Requesti 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 14 Ví dụ : P1 nhu yếu ( 1, 0, 2 )  Kiểm tra Request 1 ≤ Available :  ( 1, 0, 2 ) ≤ ( 3, 3, 2 ) => Đúng  Trạng thái mới là safe ( chuỗi bảo đảm an toàn là vậy hoàn toàn có thể cấp phép tài nguyên cho P1 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 15 Ví dụ : P4 nhu yếu ( 3, 3, 0 ) Kiểm tra Request  4 ≤ Available :  ( 3, 3, 0 ) ≤ ( 3, 3, 2 ) => Đúng Trạng thái mới là unsafe vậy không hề cấp phép tài nguyên cho  P4 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 16 Allocation Need Available A B C A B C A B C P0 0 1 0 7 4 3 0 0 2 P1 3 0 2 1 2 2 P2 3 0 2 6 0 0 P3 2 1 1 0 1 1 P4 3 3 2 1 0 1 Ví dụ : P0 nhu yếu ( 0, 2, 0 )  Kiểm tra Request 4 ≤ Available :  ( 0, 2, 0 ) ≤ ( 3, 3, 2 ) => Đúng  Trạng thái mới là safe, chuỗi bảo đảm an toàn vậy hoàn toàn có thể cấp phép tài nguyên cho P0 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 17 Allocation Need Available A B C A B C A B C P0 0 3 0 7 2 3 3 1 2 P1 3 0 2 1 2 2 P2 3 0 2 6 0 0 P3 2 1 1 0 1 1 P4 0 0 2 4 3 1 Phát hiện deadlock  Chấp nhận xảy ra deadlock trong mạng lưới hệ thống  Giải thuật phát hiện deadlock  Cơ chế phục hồi 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 18 Mỗi loại tài nguyên chỉ có một thực thể  Sử dụng wait-for graph  Các Node là những tiến trình  Pi -> Pj nếu Pi chờ tài nguyên từ Pj  Mỗi giải thuật kiểm tra có sống sót quy trình trong wait-for graph hay không sẽ được gọi định kỳ. Nếu có quy trình thì sống sót deadlock  Giải thuật phát hiện quy trình có thời hạn chạy là O ( n2 ), với n là số đỉnh của graph 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 19 Sơ đồ cấp phép tài nguyên và sơ đồ wait-for 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 20 Resource-Allocation Graph Corresponding wait-for graph Mỗi loại tài nguyên có nhiều thực thể Available  : vector độ dài m chỉ số instance chuẩn bị sẵn sàng của mỗi loại tài nguyên Allocation  : ma trận n × m định nghĩa số instance của mỗi loại tài nguyên đã cấp phép cho mỗi process Request  : ma trận n × m chỉ định nhu yếu hiện tại của mỗi tiến trình. Request  [ i, j ] = k ⇔ Pi đang nhu yếu thêm k instance của Rj 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 21 Giải thuật phát hiện deadlock 1. Gọi Work và Finish là vector size m và n. Khởi tạo : a. Work = Available b. For i = 1, 2, , n, nếu Allocationi ≠ 0 thì Finish [ i ] : = false còn không thì Finish [ i ] : = true 2. Tìm i thỏa mãn nhu cầu : a. Finish [ i ] = false b. Requesti ≤ Work Nếu không sống sót i như vậy, đến bước 4. 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 22 Giải thuật phát hiện deadlock ( tt ) 3. Work = Work + Allocationi Finish [ i ] = true quay về bước 2. 4. Nếu Finish [ i ] = false, với một số ít i = 1, , n, thì mạng lưới hệ thống đang ở trạng thái deadlock. Hơn thế nữa, Finish [ i ] = false thì Pi bị deadlocked. Thời gian chạy của giải thuật O ( m · n2 ) 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 23 Giải thuật phát hiện deadlock – Ví dụ  5 quy trình P0, , P4 3 loại tài nguyên :  A ( 7 instance ), B ( 2 instance ), C ( 6 instance ).  Tại thời gian T0 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 24 Allocation Request Available A B C A B C A B C P0 0 1 0 0 0 0 0 0 0 P1 2 0 0 2 0 2 P2 3 0 3 0 0 0 P3 2 1 1 1 0 0 P4 0 0 2 0 0 2 Chuỗi sẽ cho hiệu quả Finish [ i ] = true, i = 1, , n Giải thuật phát hiện deadlock – Ví dụ ( tt )  P2 nhu yếu thêm một instance của C. Ma trận Request như sau : 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 25 Allocation Request Available A B C A B C A B C P0 0 1 0 0 0 0 0 0 0 P1 2 0 0 2 0 2 P2 3 0 3 0 0 1 P3 2 1 1 1 0 0 P4 0 0 2 0 0 2 Phục hồi deadlock  Khi deadlock xảy ra, để phục sinh  Báo người quản lý và vận hành  Hệ thống tự động hóa hồi sinh bằng cách bẻ gãy quy trình deadlock :  Chấm dứt một hay nhiều tiến trình  Lấy lại tài nguyên từ một hay nhiều tiến trình 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 26 Chấm dứt quy trình Chấm dứt quy trình bị deadlock  Chấm dứt lần lượt từng tiến trình cho đến khi không còn  deadlock Sử dụng giải thuật phát hiện deadlock để xác lập còn  deadlock hay không Dựa trên yếu tố nào để chấm hết ?   Độ ưu tiên của tiến trình Th  ời gian đã thực thi của tiến trình và thời hạn còn lại Lo  ại tài nguyên mà tiến trình đã sử dụng  Tài nguyên mà tiến trình cần thêm để hoàn tất việc làm  Số lượng tiến trình cần được chấm hết Ti  ến trình là interactive hay batch 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 27 Lấy tại tài nguyên  Lấy lại tài nguyên từ một tiến trình, cấp phép cho tiến trình khác cho đến khi không còn deadlock nữa. Ch  ọn “ nạn nhân ” để tối thiểu ngân sách ( hoàn toàn có thể dựa trên số tài nguyên chiếm hữu, thời hạn CPU đã tiêu tốn, … ) Tr  ở lại trạng thái trước deadlock ( Rollback ) : Rollback  tiến trình bị lấy lại tài nguyên trở về trạng thái safe, liên tục tiến trình từ trạng thái đó.  Hệ thống cần lưu giữ một số ít thông tin về trạng thái những tiến trình đang thực thi.  Đói tài nguyên ( Starvation ) : để tránh starvation, phải bảo vệ không có tiến trình sẽ luôn luôn bị lấy lại tài nguyên mỗi khi deadlock xảy ra. 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 28 Phương pháp phối hợp để xử lý deadlock  Kết hợp 3 giải pháp cơ bản Ngăn  chặn ( Prevention ) Tr  ánh ( Avoidance ) Ph  át hiện ( Detection ) Cho phép sử dụng cách xử lý tối ưu cho mỗi lớp tài nguyên trong mạng lưới hệ thống. Phân chia  tài nguyên thành những lớp theo thứ bậc.  Sử dụng kỹ thuật thích hợp nhất cho việc quản trị deadlock trong mỗi lớp này. 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 29 Tóm tắt lại nội dung buổi học  Giải thuật đồ thị cấp phép tài nguyên  Giải thuật banker  Phát hiện deadlock  Phục hồi deadlock 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 30 Bài tập 1  Cho 1 mạng lưới hệ thống có 4 tiến trình P1 đến P4 và 3 loại tài nguyên R1 ( 3 ), R2 ( 2 ) R3 ( 2 ). P1 giữ 1 R1 và nhu yếu 1 R2 ; P2 giữ 2 R2 và nhu yếu 1 R1 và 1 R3 ; P3 giữ 1 R1 và nhu yếu 1 R2 ; P4 giữ 2 R3 và nhu yếu 1 R1  Vẽ đồ thị tài nguyên cho mạng lưới hệ thống này ?  Deadlock ?  Chuỗi bảo đảm an toàn ? ( nếu có ) 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 31 Bài tập 2  Tìm Need ?  Hệ thống có bảo đảm an toàn không ?  Nếu P1 nhu yếu ( 0,4,2,0 ) thì hoàn toàn có thể cấp phép cho nó ngay không ? 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 32 Bài tập 3  Sử dụng thuật toán Banker xem những trạng thái sau có bảo đảm an toàn hay không ? Nếu có thì đưa ra chuỗi thực thi bảo đảm an toàn, nếu không thì nêu rõ nguyên do không bảo đảm an toàn ? a. Available = ( 0,3,0,1 ) b. Available = ( 1,0,0,2 ) 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 33 Bài tập 4  Trả lời những câu hỏi sau sử dụng giải thuật Banker a. Hệ thống có bảo đảm an toàn không ? Đưa ra chuỗi bảo đảm an toàn nếu có ? b. Nếu P1 nhu yếu ( 1,1,0,0 ) thì hoàn toàn có thể cấp phép cho nó ngay không ? c. Nếu P4 nhu yếu ( 0,0,2,0 ) thì hoàn toàn có thể cấp phép cho nó ngay không 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 34
Các file đính kèm theo tài liệu này :

• _week11_chapter6_2_7823_2054279.pdf

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