Bài giảng Hệ điều hành: Chương 4 - Deadlock

Bài giảng Hệ điều hành: Chương 4 - Deadlock trình bày về mô hình hệ thống; Resource Allocation Graph (RAG); phương pháp giải quyết deadlock; Deadlock prevention; Deadlock avoidance; Deadlock detection; Deadlock recovery. Mời các bạn tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Hệ điều hành: Chương 4 - Deadlock 4.Deadlock Môhìnhhệthống ResourceAllocationGraph(RAG) Phươngphápgiảiquyếtdeadlock Deadlockprevention Deadlockavoidance Deadlockdetection Deadlockrecovery 1 Vấnđềdeadlocktronghệthống Tìnhhuống:mộttậpcácprocessbịblocked,mỗiprocessgiữtài nguyênvàđangchờtàinguyênmàprocesskháctrongtậpđang giữ. Vídụ ● GiảsửhệthốngcómộtprintervàmộtDVDdrive.QuátrìnhP1đanggiữ DVDdrive,quátrìnhP2đanggiữprinter. BâygiờP1yêucầuprintervàphảiđợi,vàP2yêucầuDVDdrivevàphải đợi. 2 Môhìnhhóahệthống Hệthốnggồmcácloạitàinguyên,kíhiệuR1,R2,…,Rm ● Tàinguyên:CPUcycle,khônggianbộnhớ,thiếtbịI/O,file,…• MỗiloạitàinguyênRicóWithựcthể(instance). Processsửdụngtàinguyêntheothứtự ● Yêucầu(request):processphảichờnếuyêucầukhôngđượcđápứngngay ● Sửdụng(use):processsửdụngtàinguyên ● Hoàntrả(release):processhoàntrảtàinguyên Cáctácvụyêucầuvàhoàntrảđượcgọiquasystemcall.Vídụ ● request/releasedevice ● open/closefile ● allocate/freememory 3 Điềukiệncầnđểxảyradeadlock(1/2) Bốnđiềukiệncần(necessarycondition)đểxảyradeadlock1. Mutualexclusion:mộttàinguyêncóthểđượccấpphátcho nhiềulắmlà1quátrình(tứclàkhôngchiasẻđược)2. Holdandwait:mộtquátrìnhđanggiữmộttàinguyênđược phépyêucầuthêmtàinguyênkhác. 4 Điềukiệncầnđểxảyradeadlock(2/2)3. Nopreemption:(=noresourcepreemption)khônglấylạitài nguyênđãcấpphátchoquátrình,ngoạitrừkhiquátrìnhtự hoàntrảnó.4. Circularwait:tồntạimộttập{P1,…,Pn}cácquátrìnhđangđợi saocho P1đợimộttàinguyênmàP1đanggiữ P2đợimộttàinguyênmàP2đanggiữ … PnđợimộttàinguyênmàP0đanggiữ Đểý:tàinguyêncóthểgồmnhiềuinstance 5 ResourceAllocationGraph(1/2) Resourceallocationgraph(RAG)làđồthịcóhướng,vớitập đỉnhVvàtậpcạnhE ● TậpđỉnhVgồm2loại:  P={P1,P2,…,Pn} (Tấtcảprocesstronghệthống)  R={R1,R2,…,Rm} (Tấtcảcácloạitàinguyêntronghệthống) ● TậpcạnhEgồm2loại:  Requestedge:cạnhcóhướngtừPiđếnRj  Assignmentedge:cạnhcóhướngtừRjđếnPi 6 ResourceAllocationGraph(2/2)Kýhiệu Process: Pi Rj Loạitàinguyênvới4thựcthể: Rj Pi PiyêucầumộtthựcthểcủaRj: Rj Pi PiđanggiữmộtthựcthểcủaRj: 7 VídụvềRAG(1/2) R1 R3P1 P2 P3 R2 R4 8 VídụvềRAG(2/2) R1 R3P1 P2 P3 Deadlockxảyra! R2 R4 9 RAGvàdeadlock(1/2) VídụmộtRAGchứachutrìnhnhưngkhôngxảyradeadlock: trườnghợpP4trảlạiinstancecủaR2. R1 P2 P1 R2 P3 P4 10 RAGvàdeadlock(2/2) RAGkhôngchứachutrình khôngcódeadlock RAGchứamột(haynhiều)chutrình ● Nếumỗiloạitàinguyênchỉcómộtthựcthể deadlock ● Nếumỗiloạitàinguyêncónhiềuthựcthể cóthểxảyradeadlock 11 Cácphươngphápgiảiquyếtdeadlock(1/2)• Baphươngpháp• 1.Bảođảmrằnghệthốngkhôngrơivàotìnhtrạng deadlockbằngcáchngăn(preventing)hoặctránh(avoiding) deadlock.• Khácbiệt ● Ngăndeadlock:khôngchophép(ítnhất)mộttrong4điềukiệncần chodeadlock ● Tránhdeadlock:cácquátrìnhcầncungcấpthôngtinvềtàinguyên nó ...