Bài Giảng Hệ điều Hành Chương 6 Deadlock (khóa Chết) - Tài Liệu Text

Có thể bạn quan tâm

Tải bản đầy đủ (.pdf) (49 trang)

Trang chủ

Công Nghệ Thông Tin

Hệ điều hành

Bài giảng hệ điều hành chương 6 deadlock (khóa chết)

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (1.47 MB, 49 trang )

CT107. Hệ Điều HànhChương 6. Deadlock (Khóa Chết)Giảng viên: Trần Công Án ()Bộ môn Mạng máy tính & Truyền thôngKhoa Công Nghệ Thông Tin & Truyền ThôngĐại học Cần Thơ2014[CT107] Ch6. DeadlockMục TiêuMô tả tình trạng deadlock của hệ thống – một trạng thái mà các tiếntrình không thể tiến triển để hoàn thành các tác vụ của chúng.Trình bày các phương pháp để ngăn chặn hoặc tránh deadlock; và cácbiện pháp để phát hiện và phục hồi hệ thống một khi deadlock xảy ra.TS. Trần Công Án (Khoa CNTT&TT)[CT107] Ch6. Deadlock2[CT107] Ch6. DeadlockNội DungTS. Trần Công Án (Khoa CNTT&TT)[CT107] Ch6. Deadlock3[CT107] Ch6. DeadlockGiới thiệu DeadlockDeadlock là gì?Deadlock Là Gì?Deadlock là một trạng thái của hệ thống trong đó:một tập hợp các tiến trình đang bị nghẽnmỗi tiến trình đang giữ một tài nguyên và cũng đang chờ một tàinguyên đang bị giữ bởi một tiến trình khác trong tập các tiến trìnhđang bị nghẽn.Ví dụ 1:Giả sử 1 hệ thống có 2 tiến trình P và Q và F1, F2 là 2 tập tin.Tiến trình P đang giữ F1 và cần truy xuất thêm F2.Tiến trình Q đang giữ F2 và cần truy xuất thêm F1.TS. Trần Công Án (Khoa CNTT&TT)[CT107] Ch6. Deadlock4[CT107] Ch6. DeadlockGiới thiệu DeadlockDeadlock là gì?Ví Dụ2 – Traffic DeadlockChapter 7 Deadlocks342••••••••••••Figure 7.10 Traffic deadlock for Exercise 7.11.TS. Trần Công Án (Khoa CNTT&TT)[CT107] Ch6. Deadlock5[CT107] Ch6. DeadlockGiới thiệu DeadlockĐiều kiện phát sinh deadlockĐiều Kiện Phát Sinh Deadlock1. Loại trừ hỗ tương: ít nhất một tài nguyên được giữ ở chế độ khôngchia sẻ (nonsharable mode).2. Giữ và chờ: một tiến trình đang giữ ít nhất một tài nguyên và đợithêm tài nguyên đang bị giữ bởi tiến trình khác.3. Không trưng dụng tài nguyên: không trưng dụng tài nguyên cấpphát tiến trình, trừ khi tiến trình tự hoàn trả.4. Chờ đợi vòng tròn: tồn tại một tập các tiến trình {P0 , P1 , . . . , Pn }đang chờ đợi như sau: P0 đợi một tài nguyên P1 đang giữ, P1 đợi mộttài nguyên P2 đang giữ, . . . , Pn đang đợi một tài nguyên P0 đang giữ.TS. Trần Công Án (Khoa CNTT&TT)[CT107] Ch6. Deadlock6[CT107] Ch6. DeadlockGiới thiệu DeadlockMô hình hóa hệ thốngMô Hình Hóa Hệ ThốngHệ thống gồm một tập các loại tài nguyên, kí hiệu R1 , R2 , . . . , RmVí dụ: CPU cycles, memory space, I/O devices, . . .Mỗi loại tài nguyên Ri có một tập các thể hiện (instances) WiTiến trình sử dụng tài nguyên theo các bước:1. Yêu cầu (request) – phải chờ nếu không được đáp ứng ngay.2. Sử dụng (use)3. Giải phóng (release)Các tác vụ yêu cầu và hoàn trả được thực hiện bằng các lời gọi hệthống.TS. Trần Công Án (Khoa CNTT&TT)[CT107] Ch6. Deadlock7[CT107] Ch6. DeadlockGiới thiệu DeadlockĐồ thị cấp phát tài nguyên (Resourece Allocation Graph – RAG)Đồ Thị Cấp Phát Tài Nguyên – RAGLà đồ thị có hướng, với tập đỉnh V và tập cạnh ETập đỉnh V gồm 2 loại:Tập P = {P1 , P2 , . . . , Pn }: tập các tiến trình trong hệ thốngTập R = {R1 , R2 , . . . , Rm }: tập các tài nguyên của hệ thốngTập cạnh cũng gồm 2 loại:Cạnh yêu cầu (request edge): có hướng từ Pi đến RjCạnh cấp phát (assignment edge): có hướng từ RJ đến PiTS. Trần Công Án (Khoa CNTT&TT)[CT107] Ch6. Deadlock8[CT107] Ch6. DeadlockGiới thiệu DeadlockĐồ thị cấp phát tài nguyên (Resourece Allocation Graph – RAG)Ký HiệuTiến trình:Pi ●●●●Loại tài nguyên (với 4 thể hiện):Pi yêu cầu 1 thể hiện của Rj :Pi đang giữ 1 thể hiện của Rj :TS. Trần Công Án (Khoa CNTT&TT)Pi Pi [CT107] Ch6. Deadlock●●●●●●●●RjRj9[CT107] Ch6. DeadlockGiới thiệu DeadlockĐồ thị cấp phát tài nguyên (Resourece Allocation Graph – RAG)Đồ Thị Cấp Phát Tài Nguyên – Ví Dụ 1ksĐồ thị cấp phát tài nguyên (không có chu trình và không deadlock):R1R3P = {P1 , P2 , P3 }R = {R1 , R2 , R3 , R4 }P1P2P3E = {P1 → R1 , P2 → R3 , R1 → P2 ,R2 → P2 , R2 → P1 , R3 → P3 }Thể hiện của các loại tài nguyên:R1 : 1; R2 : 2; R3 : 1; R4 : 3.Trạng thái của các tiến trình:P1 : giữ (R2 , 1); chờ (R1 , 1)R2P2 : giữ (R1 , 1), (R2 , 1); chờ (R3 , 1)R4FigureTS.Trần 7.1Công Resource-allocationÁn (Khoa CNTT&TT)P3 : giữ (R3 , 1)graph.[CT107] Ch6.Deadlock10[CT107] Ch6. DeadlockGiới thiệu DeadlockĐồ thị cấp phát tài nguyên (Resourece Allocation Graph – RAG)Đồ Thị Cấp Phát Tài Nguyên – Ví Dụ 2CharacterizationĐồ thị cấp 7.2phátDeadlocktài nguyênvới chu trình và 321deadlock:R1R3Trạng thái của các tiến trình:P1 : giữ (R2 , 1); chờ (R1 , 1)P1P2P3P2 : giữ (R1 , 1), (R2 , 1); chờ (R3 , 1)P3 : giữ (R3 , 1); chờ (R2 , 1)2 chu trình nhỏ nhất (minimal cycles):P1 → R1 → P2 → R3 → P3 → R2 → P1P2 → R3 → P3 → R2 → P2R2R4Deadlock: cả 3 tiến trình P1 , P2 , P3eTS.7.2TrầnResource-allocationgraph with a [CT107]deadlock.Công Án (Khoa CNTT&TT)Ch6.Deadlock11by[CT107]processP3 . Process P3 is waiting for either process P1 orCh6. DeadlockGiới thiệu Deadlockase resourceR2 . In addition, process P1 is waiting for processthị cấp phát tài nguyên (Resourece Allocation Graph – RAG)urce RĐồ1.r the resource-allocation graph in Figure 7.3. In this example,Đồ Thị Cấp Phát Tài Nguyên – Ví Dụycle:3P1 → R1 → P3 → R2 → P1Đồ thị cấp phát tài nguyên có chu trình nhưng không deadlock:R1P2P3P1Chu trình:P1 → R1 → P3 → R2 → P1Tại sao không deadlock?R2P43 Resource-allocation graph with a cycle but no deadlock.TS. Trần Công Án (Khoa CNTT&TT)[CT107] Ch6. Deadlock12[CT107] Ch6. DeadlockGiới thiệu DeadlockĐồ thị cấp phát tài nguyên (Resourece Allocation Graph – RAG)Đồ Thị Cấp Phát Tài Nguyên & DeadlockNếu đồ thị không có chu trình: chắc chắn không có deadlockNếu đồ thị có chu trình:Nếu mỗi loại tài nguyên chỉ có một thể hiện: chắc chắn có deadlock.Nếu mỗi loại tài nguyên có nhiều thể hiện: có thể có deadlock.TS. Trần Công Án (Khoa CNTT&TT)[CT107] Ch6. Deadlock13[CT107] Ch6. DeadlockCác cách tiếp cận với vấn đề deadlockCác Cách Tiếp Cận Đối Với Vấn Đề Deadlock1. Đề ra các giao thức để đảm bảo cho hệ thống không bao giờ rơi vàotrạng thái deadlock.2. Cho phép hệ thống rơi vào trạng thái deadlock, sau đó sử dụng cácgiải thuật để phát hiện deadlock và phục hồi.3. Không quan tâm và không xử lý vấn đề deadlock trong hệ thốngKhá nhiều hệ điều hành sử dụng phương pháp này.Tuy nhiên, nếu deadlock không được phát hiện và xử lý sẽ dẫn đến việcgiả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 khởi động lại.TS. Trần Công Án (Khoa CNTT&TT)[CT107] Ch6. Deadlock14[CT107] Ch6. DeadlockNgăn chặn và tránh deadlockNgăn chặn và tránh deadlockCó hai biện pháp để đảm bảo hệ thống không rơi vào trạng tháideadlock:1. Ngăn chặn deadlock (deadlock prevention): không cho phép (ít nhất)một trong bốn điều kiện cần cho deadlock xảy ra.2. Tránh deadlock (deadlock avoidance): các tiến trình cần cung cấpthông tin về tài nguyên nó cần để hệ thống cấp phát tài nguyên mộtcách thích hợp.TS. Trần Công Án (Khoa CNTT&TT)[CT107] Ch6. Deadlock15[CT107] Ch6. DeadlockNgăn chặn và tránh deadlockNgăn chặn deadlockNgăn Chặn Deadlock – Điều kiện 1Ngăn một trong bốn điều kiện cần của deadlock – thắt chặt cách thức yêucầu tài nguyên của tiến trình.1. Ngăn Loại trừ hỗ tương (mutual exclusion):Tài nguyên có thể chia sẻ: không cần thiết.Tài nguyên không thể chia sẻ: không thể thực hiện được do một số tàinguyên không thể được chia sẻ đồng thời cho nhiều tiến trình.TS. Trần Công Án (Khoa CNTT&TT)[CT107] Ch6. Deadlock16[CT107] Ch6. DeadlockNgăn chặn và tránh deadlockNgăn chặn deadlockNgăn Chặn Deadlock – Điều Kiện 22. Ngăn Chờ và giữ (wait & hold): phải đảm bảo khi một tiến trình yêucầu một tài nguyên, nó không đang giữ một tài nguyên nào khác.Cách 1: mỗi t/trình yêu cầu toàn bộ tài nguyên cần thiết một lần.Cách 2: khi yêu cầu tài nguyên, tiến trình không đang giữ bất kỳ tàinguyên nào. Nếu đang giữ thì phải trả lại trước khi yêu cầu.Ví dụ: xét một tiến trình P copy dữ liệu từ băng từ sang đĩa từ, sau đósắp xếp dữ liệu trên đĩa từ rồi in kết quả ra máy in.Cách 1: P → {băng từ, đĩa từ, máy in} ngay khi t/trình bắt đầu.Cách 2: P → {băng từ, đĩa từ} → P; P → {đĩa từ, máy in}Khuyết điểm: hiệu suất sử dụng t/nguyên thấp + có thể bị đóit/nguyênTS. Trần Công Án (Khoa CNTT&TT)[CT107] Ch6. Deadlock17[CT107] Ch6. DeadlockNgăn chặn và tránh deadlockNgăn chặn deadlockNgăn Chặn Deadlock – Điều Kiện 33. Ngăn Không trưng dụng (no prermption): nếu một tiến trình A cóđang giữ tài nguyên và yêu cầu thêm tài nguyên đang giữ bởi tiếntrình khác thì:Cách 1: hệ thống lấy lại mọi tài nguyên A đang giữ và A sẽ khởi độnglại khi cả tài nguyên cũ và mới sẵn sàng cho nó.Cách 2: hệ thống xem tài nguyên mà A yêu cầu:Nếu tài nguyên đó đang được giữ bởi một tiến trình B cũng đang đợithêm tài nguyên, hệ thống sẽ lấy lại tài nguyên của B và cấp phát cho A.Nếu tài nguyên đó đang được giữ bởi một tiến trình không đang đợithêm tài nguyên thì A phải đợi (⇒ tài nguyên của A đang giữ sẽ bị thuhồi nếu có tiến trình khác cần – trường hợp 1).TS. Trần Công Án (Khoa CNTT&TT)[CT107] Ch6. Deadlock18[CT107] Ch6. DeadlockNgăn chặn và tránh deadlockNgăn chặn deadlockNgăn Chặn Deadlock – Điều Kiện 44. Ngăn Chờ đợi vòng tròn (circular wait):Mỗi tài nguyên sẽ được gán một thứ tự toàn cục.Các tiến trình khi yêu cầu tài nguyên phải theo đúng thứ tự.Thông thường, một hàm one-to-one được định nghĩa để thực hiện gánthứ tự toàn cục: F : R → N; với R là tập các tài nguyên.Một tiến trình đầu tiên có thể yêu cầu bất kỳ tài nguyên Ri nào.Sau đó, một yêu cầu tài nguyên Rj chỉ được đáp ứng nếu F (Rj ) > F (Ri ),hoặc nó phải trả lại tài nguyên Ri trước khi xin tài nguyên Rj .TS. Trần Công Án (Khoa CNTT&TT)[CT107] Ch6. Deadlock19[CT107] Ch6. DeadlockNgăn chặn và tránh deadlockTránh deadlockTránh DeadlockCách tiếp cận tránh deadlock cho phép sử dụng tài nguyên hiệu quảhơn ngăn chặn deadlock, bằng cách:Yêu cầu mỗi tiến trình khai báo số lượng tài nguyên tối đa cần để thựchiện công việc.Giải thuật tránh deadlock sẽ kiểm tra trạng thái cấp phát tài nguyên đểđảm bảo hệ thống không rơi vào trạng thái deadlock.Trạng thái cấp phát tài nguyên được định nghĩa bởi số lượng tài nguyêncòn lại, số tài nguyên đã được cấp phát, và yêu cầu tối đa của các tiếntrình.Các giải thuật: giải thuật Đồ thị cấp phát tài nguyên và giải thuậtBanker.TS. Trần Công Án (Khoa CNTT&TT)[CT107] Ch6. Deadlock20[CT107] Ch6. DeadlockNgăn chặn và tránh deadlockTránh deadlockTrạng Thái An Toàn (Safe State)Một hệ thống ở trạng thái an toàn nếu tồn tại một chuỗi an toàn.Một chuỗi tiến trình P1 , P2 , . . . , Pn là một chuỗi an toàn nếu:Với mọi Pi , i = 1..n, mọi yêu cầu về tài nguyên của Pi có thể được thỏamãn bởi các tài nguyên đang sẵn sàng hoặc các tài nguyên đang bị giữbởi Pj , với j < i (ngăn chờ đợi vòng tròn).Một hệ thống ở trạng thái không an toàn nếu không tồn tại chuỗi antoàn.TS. Trần Công Án (Khoa CNTT&TT)[CT107] Ch6. Deadlock21[CT107] Ch6. DeadlockNgăn chặn và tránh deadlockTránh deadlockVí Dụ Về Chuỗi An ToànCho một hệ thống có 12 băng từ và 3 tiến trình P0 , P1 , P2 .Trạng thái và nhu cầu sử dụng tài nguyên của 3 tiến trình tại thờiđiểm t0 được cho trong bảng sau:7.5 Deadlock AvoidanceP0P1P2Maximum NeedsCurrent Needs1049522329At timeis in aansafestate.sequence<P1 , P0 , P2 > satisfiesChuỗiP1t,0 ,Pthetoàn⇒ Thehệ thốngan toàn.0 , Psystem2 là chuỗithe safety condition. Process P1 can immediately be allocated all its tape drivesGiảthensử tạithờithemđiểm (thet1 , Psystemđượccấpphát1 băngtapetừ ⇒hệandreturnwill vàthenhavefiveavailabledrives);2 yêu cầuthenprocesscan getits sàngtape drivesreturnthemkhông(the systemwill(?)thenthốngcòn P20 băngtừallsẵnvà hệ andthốngtrở nênan toàn.have ten available tape drives); and finally process P2 can get all its tape drivesand return them (the system will then have all twelve tape drives available).TS. Trần Công(Khoa canCNTT&TT)[CT107]Ch6. Deadlock22A Ánsystemgo from a safestateto an unsafe state. Suppose that, at time[CT107] Ch6. DeadlockNgăn chặn và tránh deadlockTránh deadlockAn unsafe state may lead to a deadlock. As long asoperating system can avoid unsafe (and deadlocked) statthe operating system cannot prevent processes from reqsuch a way that a deadlock occurs. The behavior of thunsafe states.To illustrate, we consider a system with twelve magthree processes: P0 , P1 , and P2 . Process P0 requires ten tamay need as many as four tape drives, and process P2 maydrives. Suppose that, at time t0 , process P0 is holding fivP1 istháiholdingtape⇒drives,and deadlock.process P2 is holding twtrạngan twotoànkhôngthere are three free tape drives.)Trạng Thái An Toàn Và DeadlockNếu hệ thống đang trongNếu hệ thống đang ở trạng thái không an toàn ⇒ có thể có deadlock.Ý tưởng cho giải pháp tránh deadlock:đảm bảo hệ thống không rơi vào trạng tháikhông an toàn bằng cách:unsafedeadlocksafeKhi một tiến trình yêu cầu một tài nguyênđang sẵn sàng, hệ thống sẽ kiểm tra nếuviệc cấp phát không dẫn đến trạng tháikhông an toàn thì sẽ cấp phát ngay.Figure 7.6 Safe, unsafe, and deadlocked stateTS. Trần Công Án (Khoa CNTT&TT)[CT107] Ch6. Deadlock23[CT107] Ch6. DeadlockNgăn chặn và tránh deadlockTránh deadlockGiải Thuật Đồ Thị Cấp Phát Tài NguyênĐược áp dụng cho hệ thống chỉ có 1 thể hiện cho mỗi loại tài nguyên.Bổ sung thêm 1 loại cạnh, “cạnh dự định” yêu cầu, Pi → Rj : Pi có thể330 biểuChapter7 Deadlocksyêu cầu Rj , đượcdiễn bằngđường ngắt khúc trên đồ thị.Việc yêu cầu tài nguyên phải được dự tínhtrước trong hệ thống⇒ các cạnh dự định phải xuất hiện sẵntrong đồ thị.R1P1P2R2TS. Trần Công Án (Khoa CNTT&TT)Figure 7.7 Resource-allocation graph for deadlo[CT107] Ch6. Deadlock24[CT107] Ch6. DeadlockNgăn chặn và tránh deadlockTránh deadlockGiải Thuật Đồ Thị Cấp Phát Tài NguyênSự chuyển đổi của các cạnh trong đồ thị:Khi tiến trình yêu cầu tài nguyên: cạnh dự định → cạnh yêu cầu.Khi tài nguyên được cấp phát: cạnh yêu cầu → cạnh cấp phát .Khi tài nguyên được giải phóng: cạnh cấp phát → cạnh dự định yêu cầu.Nguyên tắc cấp phát tài nguyên: một yêu cầu tài nguyên Rj củatiến trình Pi chỉ được cấp phát khi việc chuyển từ Pi → Rj (cạnh yêucầu) sang Rj → Pi (cạnh cấp phát) không tạo thành chu trình trongđồ thị cấp phát tài nguyên.TS. Trần Công Án (Khoa CNTT&TT)[CT107] Ch6. Deadlock25