Bài giảng Tắc nghẽn (Deadlock)

Khoa KTMT * Chương 6 : Tắc nghẽn(Deadlock) Mụ hỡnh hệ thống Định nghĩa Điều kiện cần của deadlock Resource Allocation Graph (RAG) Phương phỏp giải quyết deadlock Deadlock prevention Deadlock avoidance Deadlock detection Deadlock recovery Phương phỏp kết hợp để giải quyết Deadlock Khoa KTMT * Vấn đề deadlock trong hệ thống Tỡnh huống: một tập cỏc process bị blocked, mỗi process giữ tài nguyờn và đang chờ tài nguyờn mà process khỏc trong tập đang giữ. Vớ dụ 1 Giả sử hệ thống cú 2 file trờn đĩa. P1 và P2 mỗi process đang mở một file và yờu cầu mở file kia. Vớ dụ 2 Semaphore A và B, khởi tạo bằng 1 P0 P1 wait(A); wait(B); wait(B); wait(A); Khoa KTMT * Mụ hỡnh húa hệ thống Hệ thống gồm cỏc loại tài nguyờn, kớ hiệu R1, R2,…, Rm , bao gồm: CPU cycle, khụng gian bộ nhớ, thiết bị I/O, file, semaphore,… Mỗi loại tài nguyờn Ri cú Wi thực thể (instance). Giả sử tài nguyờn tỏi sử dụng theo kỳ (Serially Reusable Resources) Yờu cầu (request): process phải chờ nếu yờu cầu khụng được đỏp ứng ngay Sử dụng (use): process sử dụng tài nguyờn Hoàn trả (release): process hoàn trả tài nguyờn Cỏc tỏc vụ yờu cầu (request) và hoàn trả (release) đều là system call. Vớ dụ request/release device open/close file allocate/free memory wait/signal Khoa KTMT * Định nghĩa Một tiến trỡnh gọi là deadlocked nếu nú đang đợi một sự kiện mà sẽ khụng bao giờ sảy ra. Thụng thường, cú nhiều hơn một tiến trỡnh bị liờn quan trong một deadlock. Một tiến trỡnh gọi là trỡ hoón vụ hạn định (indefinitely postponed) nếu nú bị trỡ hoón một khoảng thời gian dài lặp đi lặp lại trong khi hệ thống đỏp ứng cho những tiến trỡnh khỏc . i.e. Một tiến trỡnh sẵn sàng để xử lý nhưng nú khụng bao giờ nhận được CPU. Khoa KTMT * Điều kiện cần để xảy ra deadlock Bốn điều kiện cần (necessary condition) để xảy ra deadlock Loại trừ hỗ tương (Mutual exclusion): ớt nhất một tài nguyờn được giữ theo nonsharable mode (vớ dụ: printer; vớ dụ sharable resource: read-only files). Giữ và chờ cấp thờm tài nguyờn (Hold and wait): một process đang giữ ớt nhất một tài nguyờn và đợi thờm tài nguyờn do quỏ trỡnh khỏc đang giữ. Khoa KTMT * Điều kiện cần để xảy ra deadlock (tt) Khụng trưng dụng (No preemption): (= no resource preemption) tài nguyờn khụng thể bị lấy lại, mà chỉ cú thể được trả lại từ process đang giữ tài nguyờn đú khi nú muốn. Chu trỡnh đợi (Circular wait): tồn tại một tập {P0,…,Pn} cỏc quỏ trỡnh đang đợi sao cho P0 đợi một tài nguyờn mà P1 đang giữ P1 đợi một tài nguyờn mà P2 đang giữ … Pn đợi một tài nguyờn mà P0 đang giữ Khoa KTMT * Đồ thị cấp phỏt tài nguyờnResource Allocation Graph Resource allocation graph (RAG) là đồ thị cú hướng, với tập đỉnh V và tập cạnh E Tập đỉnh V gồm 2 loại: P = {P1, P2,…, Pn } (Tất cả process trong hệ thống) R = {R1, R2,…, Rm } (Tất cả cỏc loại tài nguyờn trong hệ thống) Tập cạnh E gồm 2 loại: Cạnh yờu cầu (Request edge): ứ Pi Rj Cạnh cấp phỏt (Assignment edge): Rj Pi Khoa KTMT * Resource Allocation Graph (tt) Ký hiệu Process: Loại tài nguyờn với 4 thực thể: Pi yờu cầu một thực thể của Rj : Pi đang giữ một thực thể của Rj : Pi Pi Pi Rj Rj Rj Khoa KTMT * Vớ dụ về RAG R1 R3 P1 P2 P3 R2 R4 Khoa KTMT * Vớ dụ về RAG (tt) R1 R3 P1 P2 P3 R2 R4 Deadlock xảy ra! Khoa KTMT * RAG và deadlock Vớ dụ một RAG chứa chu trỡnh nhưng khụng xảy ra deadlock: P4 cú thể trả lại instance của R2. R1 P1 P2 P3 R2 P4 Khoa KTMT * RAG và deadlock (tt) RAG khụng chứa chu trỡnh (cycle)  khụng cú deadlock RAG chứa một (hay nhiều) chu trỡnh Nếu mỗi loại tài nguyờn chỉ cú một thực thể  deadlock Nếu mỗi loại tài nguyờn cú nhiều thực thể  cú thể xảy ra deadlock Khoa KTMT * Cỏc phương phỏp giải quyết deadlock (1) Ba phương phỏp 1) Bảo đảm rằng hệ thống khụng rơi vào tỡnh trạng deadlock bằng cỏch ngăn (preventing) hoặc trỏnh (avoiding) deadlock. Khỏc biệt Ngăn deadlock: khụng cho phộp (ớt nhất) một trong 4 điều kiện cần cho deadlock Trỏnh deadlock: cỏc quỏ trỡnh cần cung cấp thụng tin về tài nguyờn nú cần để hệ thống cấp phỏt tài nguyờn một cỏch thớch hợp Khoa KTMT * Cỏc phương phỏp giải quyết deadlock (2) 2) Cho phộp hệ thống vào trạng thỏi deadlock, nhưng sau đú phỏt hiện deadlock và phục hồi hệ thống. 3) Bỏ qua mọi vấn đề, xem như deadlock khụng bao giờ xảy ra trong hệ thống. Khỏ nhiều hệ điều hành sử dụng phương phỏp này. Deadlock khụng được phỏt hiện, dẫn đến việc giảm hiệu suất của hệ thống. Cuối cựng, hệ thống cú thể ngưng hoạt động và phải được khởi động lại. Khoa KTMT * 1. Ngăn deadlock (deadlock prevention) Ngăn deadlock bằng cỏch ngăn một trong 4 điều kiện cần của deadlock Ngăn mutual exclusion đối với nonsharable resource (vd: printer): khụng làm được đối với sharable resource (vd: read-only file): khụng cần thiết Khoa KTMT * Ngăn deadlock (tt) Ngăn Hold and Wait Cỏch 1: mỗi process yờu cầu toàn bộ tài nguyờn cần thiết một lần. Nếu cú đủ tài nguyờn thỡ hệ thống sẽ cấp phỏt, nếu khụng đủ tài nguyờn thỡ process phải bị blocked. Cỏch 2: khi yờu cầu tài nguyờn, process khụng được giữ bất kỳ tài nguyờn nào. Nếu đang cú thỡ phải trả lại trước khi yờu cầu. Vớ dụ để so sỏnh hai cỏch trờn: một quỏ trỡnh copy dữ liệu từ tape drive sang disk file, sắp xếp disk file, rồi in kết quả ra printer. Khuyết điểm của cỏc cỏch trờn: Hiệu suất sử dụng tài nguyờn (resource utilization) thấp Quỏ trỡnh cú thể bị starvation Khoa KTMT * Ngăn deadlock (tt) Ngăn No Preemption: nếu process A cú giữ tài nguyờn và đang yờu cầu tài nguyờn khỏc nhưng tài nguyờn này chưa cấp phỏt ngay được thỡ Cỏch 1: Hệ thống lấy lại mọi tài nguyờn mà A đang giữ A chỉ bắt đầu lại được khi cú được cỏc tài nguyờn đó bị lấy lại cựng với tài nguyờn đang yờu cầu Cỏch 2: Hệ thống sẽ xem tài nguyờn mà A yờu cầu Nếu tài nguyờn được giữ bởi một process khỏc đang đợi thờm tài nguyờn, tài nguyờn này được hệ thống lấy lại và cấp phỏt cho A. Nếu tài nguyờn được giữ bởi process khụng đợi tài nguyờn, A phải đợi và tài nguyờn của A bị lấy lại. Tuy nhiờn hệ thống chỉ lấy lại cỏc tài nguyờn mà process khỏc yờu cầu Khoa KTMT * Ngăn deadlock (tt) Ngăn Circular Wait: gỏn một thứ tự cho tất cả cỏc tài nguyờn trong hệ thống. Tập hợp loại tài nguyờn: R={R1, R2,…,Rm } Hàm ỏnh xạ: F: R->N Vớ dụ: F(tape drive) = 1, F(disk drive) = 5, F(printer) = 12 F là hàm định nghĩa thứ tự trờn tập cỏc loại tài nguyờn. Khoa KTMT * Ngăn deadlock (tt) Ngăn Circular Wait (tt) Mỗi process chỉ cú thể yờu cầu thực thể của một loại tài nguyờn theo thứ tự tăng dần (định nghĩa bởi hàm F) của loại tài nguyờn. Vớ dụ Chuỗi yờu cầu thực thể hợp lệ: tape drive  disk drive  printer Chuỗi yờu cầu thực thể khụng hợp lệ: disk drive  tape drive Khi một process yờu cầu một thực thể của loại tài nguyờn Rj thỡ nú phải trả lại cỏc tài nguyờn Ri với F(Ri) > F(Rj). “Chứng minh” giả sử tồn tại một chu trỡnh deadlock F(R4) là một chuỗi an toàn nếu Với mọi i = 1,…,n, yờu cầu tối đa về tài nguyờn của Pi cú thể được thỏa bởi tài nguyờn mà hệ thống đang cú sẵn sàng (available) cựng với tài nguyờn mà tất cả Pj , j là chuỗi an toàn  hệ thống là an toàn Khoa KTMT * Chuỗi an toàn (tt) Giả sử tại thời điểm t1, P2 yờu cầu và được cấp phỏt 1 tape drive cũn 2 tape drive sẵn sàng Hệ thống cũn an toàn khụng? cần tối đa đang giữ Khoa KTMT * Trạng thỏi safe/unsafe và deadlock Nếu hệ thống đang ở trạng thỏi safe  khụng deadlock. Nếu hệ thống đang ở trạng thỏi unsafe  cú thể dẫn đến deadlock. Trỏnh deadlock bằng cỏch bảo đảm hệ thống khụng đi đến trạng thỏi unsafe. safe deadlock unsafe Khoa KTMT * Giải thuật đồ thị cấp phỏt tài nguyờn Khỏi niệm cạnh thỉnh cầu P1 P2 P1 P2 R1 R2 R1 R2 Khoa KTMT * Giải thuật banker Áp dụng cho hệ thống cấp phỏt tài nguyờn trong đú mỗi loại tài nguyờn cú thể cú nhiều instance. Bắt chước nghiệp vụ ngõn hàng (banking) Điều kiện Mỗi process phải khai bỏo số lượng thực thể (instance) tối đa của mỗi loại tài nguyờn mà nú cần Khi process yờu cầu tài nguyờn thỡ cú thể phải đợi mặc dự tài nguyờn được yờu cầu đang cú sẵn Khi process đó cú được đầy đủ tài nguyờn thỡ phải hoàn trả trong một khoảng thời gian hữu hạn nào đú. Khoa KTMT * Giải thuật banker (tt) n: số process, m: số loại tài nguyờn Cỏc cấu trỳc dữ liệu Available: vector độ dài m Available[ j ] = k  loại tài nguyờn Rj cú k instance sẵn sàng Max: ma trận n  m Max[ i, j ] = k  quỏ trỡnh Pi yờu cầu tối đa k instance của loại tài nguyờn Rj Allocation: ma trận n  m Allocation[i, j] = k  Pi đó được cấp phỏt k instance của Rj Need: ma trận n  m Need[i, j] = k  Pi cần thờm k instance của Rj Nhận xột: Need[i, j] = Max[i, j] – Allocation[i, j] Ký hiệu Y  X  Y[i]  X[i], vớ dụ (0, 3, 2, 1)  (1, 7, 3, 2) Khoa KTMT * Giải thuật banker (tt) Giải thuật an toàn Tỡm một chuỗi 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 = 1,…, n 2. Tỡm i thỏa (a) Finish[ i ] = false (b) Needi  Work (hàng thứ i của Need) Nếu khụng tồn tại 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ỡ hệ thống đang ở trạng thỏi safe Thời gian chạy của giải thuật là O(mãn2) Khoa KTMT * Giải thuật banker (tt) Giải thuật yờu cầu (cấp phỏt) tài nguyờn Gọi 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ỡ process đó vượt yờu cầ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ỏt. 3. Giả định cấp phỏt tài nguyờn đỏp ứng yờu cầu của Pi bằng cỏch cập nhật trạng thỏi hệ thống như sau: Available := Available – Requesti Allocationi := Allocationi + Requesti Needi := Needi – Requesti Khoa KTMT * Giải thuật banker (tt) Giải thuật yờu cầu tài nguyờn Á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 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à phục hồi trạng thỏi: Available := Available + Requesti Allocationi := Allocationi – Requesti Needi := Needi + Requesti Khoa KTMT * Giải thuật kiểm tra trạng thỏi an toàn – Vớ dụ Cú 5 process P0 ,…, P4 Cú 3 loại tài nguyờn: A (cú 10 instance), B (5 instance) và C (7 instance). Sơ đồ cấp phỏt trong hệ thống tại thời điểm T0      Khoa KTMT * GT (kiểm tra trạng thỏi)an toàn – Vd (tt) Allocation Need Work A B C A B C A B C P0 0 1 0 7 4 3 3 3 2 P1 2 0 0 1 2 2 P2 3 0 2 6 0 0 P3 2 1 1 0 1 1 P4 0 0 2 4 3 1 Chuỗi an toàn 7 4 3 7 4 5 10 4 7 10 5 7 5 3 2 Khoa KTMT * GT cấp phỏt tài nguyờn – Vớ dụ Yờu cầu (1, 0, 2) của P1 cú thỏa được khụng? Kiểm tra điều kiện Request1  Available: (1, 0, 2)  (3, 3, 2) là đỳng Giả định thỏa yờu cầu, kiểm tra trạng thỏi mới cú phải là safe hay khụng. Trạng thỏi mới là safe (chuỗi an toàn là ), vậy cú thể cấp phỏt tài nguyờn cho P1. P4 (3, 3, 0) ? P0 (0, 2, 0) ? P3 (0, 2, 1)? Khoa KTMT * 3. Phỏt hiện deadlock (Deadlock detection) Chấp nhận xảy ra deadlock trong hệ thống, kiểm tra trạng thỏi hệ thống bằng giải thuật phỏt hiện deadlock. Nếu cú deadlock thỡ tiến hành phục hồi hệ thống Cỏc giải thuật phỏt hiện deadlock thường sử dụng mụ hỡnh RAG. Hệ thống cấp phỏt tài nguyờn được khảo sỏt trong mỗi trường hợp sau Mỗi loại tài nguyờn chỉ cú một thực thể (instance) Mỗi loại tài nguyờn cú thể cú nhiều thực thể Khoa KTMT * Mỗi loại tài nguyờn chỉ cú một thực thể Sử dụng wait-for graph Wait-for graph được dẫn xuất từ RAG bằng cỏch bỏ cỏc node biểu diễn tài nguyờn và ghộp cỏc cạnh tương ứng. Cú cạnh từ Pi đến Pj  Pi đang chờ tài nguyờn từ Pj Một giải thuật kiểm tra cú tồn tại chu trỡnh trong wait-for graph hay khụng sẽ được gọi định kỳ. Giải thuật phỏt hiện chu trỡnh cú thời gian chạy là O(n 2), với n là số đỉnh của graph. R1 R3 R4 P2 P1 P3 P5 R2 R5 P4 P2 P1 P3 P5 P4 Khoa KTMT * Mỗi loại tài nguyờn cú nhiều thực thể Phương phỏp dựng wait-for graph khụng ỏp dụng được cho trường hợp mỗi loại tài nguyờn cú nhiều instance. Cỏc cấu trỳc dữ liệu dựng trong giải thuật phỏt hiện deadlock Available: vector độ dài m số instance sẵn sàng của mỗi loại tài nguyờn Allocation: ma trận n  m số instance của mỗi loại tài nguyờn đó cấp phỏt cho mỗi process Request: ma trận n  m yờu cầu hiện tại của mỗi process. Request [i, j ] = k  Pi đang yờu cầu thờm k instance của Rj Khoa KTMT * Giải thuật phỏt hiện deadlock 1. Gọi Work và Finish là vector kớch thước m và n. Khởi tạo: Work := Available 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: Finish[ i ] := false và Requesti  Work Nếu khụng tồn tại i như thế, đến bước 4. 3. Work := Work + AllocationiFinish[ i ] := truequay về bước 2. 4. Nếu Finish[ i ] = false, với một i = 1,…, n, thỡ 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) Khoa KTMT * Giải thuật phỏt hiện deadlock – Vớ dụ Hệ thống cú 5 quỏ trỡnh P0 ,…, P4 3 loại tài nguyờn: A (7 instance), B (2 instance), C (6 instance). Chạy giải thuật, tỡm được chuỗi với Finish[ i ] = true, i = 1,…, n, vậy hệ thống khụng bị deadlocked. Khoa KTMT * Giải thuật phỏt hiện deadlock – Vớ dụ (tt) P2 yờu cầu thờm một instance của C. Ma trận Request như sau: Request A B C P0 0 0 0 P1 2 0 2 P2 0 0 1 P3 1 0 0 P4 0 0 2 Trạng thỏi của hệ thống là gỡ? Cú thể thu hồi tài nguyờn đang sở hữu bởi process P0 nhưng vẫn khụng đủ đỏp ứng yờu cầu của cỏc process khỏc. Vậy tồn tại deadlock, bao gồm cỏc process P1, P2, P3, và P4 . Khoa KTMT * Phục hồi deadlock (Deadlock Recovery) Khi deadlock xảy ra, để phục hồi bỏo người vận hành (operator) hoặc hệ thống tự động phục hồi bằng cỏch bẻ góy chu trỡnh deadlock: chấm dứt một hay nhiều quỏ trỡnh lấy lại tài nguyờn từ một hay nhiều quỏ trỡnh Khoa KTMT * Deadlock Recovery: Chấm dứt quỏ trỡnh Phục hồi hệ thống bị deadlock bằng cỏch chấm dứt quỏ trỡnh Chấm dứt tất cả process bị deadlocked, hoặc Chấm dứt lần lượt từng process cho đến khi khụng cũn deadlock Sử dụng giải thuật phỏt hiện deadlock để xỏc định cũn deadlock hay khụng Dựa trờn yếu tố nào để chọn process cần được chấm dứt? Độ ưu tiờn của process Thời gian đó thực thi của process và thời gian cũn lại Loại tài nguyờn mà process đó sử dụng Tài nguyờn mà process cần thờm để hoàn tất cụng việc Số lượng process cần được chấm dứt Process là interactive process hay batch process Khoa KTMT * Deadlock recovery: Lấy lại tài nguyờn Lấy lại tài nguyờn từ một process, cấp phỏt cho process khỏc cho đến khi khụng cũn deadlock nữa. Cỏc vấn đề trong chiến lược thu hồi tài nguyờn: Chọn “nạn nhõn” để tối thiểu chi phớ (cú thể dựa trờn số tài nguyờn sở hữu, thời gian CPU đó tiờu tốn,...) Trở lại trạng thỏi trước deadlock (Rollback): rollback process bị lấy lại tài nguyờn trở về trạng thỏi safe, tiếp tục process từ trạng thỏi đú. Hệ thống cần lưu giữ một số thụng tin về trạng thỏi cỏc process đang thực thi. Đúi tài nguyờn (Starvation): để trỏnh starvation, phải bảo đảm khụng cú process sẽ luụn luụn bị lấy lại tài nguyờn mỗi khi deadlock xảy ra. Khoa KTMT * Phương phỏp kết hợp để giải quyết Deadlock Kết hợp 3 phương 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 giải quyết tối ưu cho mỗi lớp tài nguyờn trong hệ thống. Phõn chia tài nguyờn thành cỏc lớp theo thứ bậc. Sử dụng kỹ thuật thớch hợp nhất cho việc quản lý deadlock trong mỗi lớp này. Khoa KTMT * Bài tập Bài 01: Liệt kờ 3 trường hợp xảy ra deadlock trong đời sống Bài 02: R1 R3 P1 P2 P3 R2 R4 Deadlock ? Khoa KTMT * Bài tập Bài 03: A) Tỡm Need B) Hệ thống cú an toàn khụng C)Nếu P1 yờu cầu (0,4,2,0) thỡ cú thể cấp phỏt cho nú ngay khụng?