intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Giáo trình môn học Hệ điều hành: Phần 2

Chia sẻ: Minh Vũ | Ngày: | Loại File: PDF | Số trang:125

Thêm vào BST
Báo xấu
66
lượt xem 7
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Nối tiếp nội dung phần 1 giáo trình môn học "Hệ điều hành", phần 2 giới thiệu tới người học các kiến thức: Deadlock, quản lý bộ nhớ, bộ nhớ ảo, quản lý tập tin, cài đặt hệ thống tập tin, quản lý hệ thống nhập xuất. Mời các bạn cùng tham khảo nội dung chi tiết.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Giáo trình môn học Hệ điều hành: Phần 2

  1. Ĉҥi Hӑc Cҫn Thѫ - Khoa Công NghӋ Thông Tin - Giáo Trình HӋ ĈiӅu Hành – V1.0 DEADLOCK I Mөc ÿích Sau khi hӑc xong chѭѫng này, ngѭӡi hӑc nҳm ÿѭӧc nhӳng kiӃn thӭc sau: x HiӇu mô hình hӋ thӕng vӅ deadlock x HiӇu các ÿһc ÿiӇm cӫa deadlock x HiӇu các phѭѫng pháp quҧn lý deadlock x HiӇu cách ngăn chһn deadlock x HiӇu cách tránh deadlock x HiӇu cách phát hiӋn deadlock x HiӇu cách phөc hӗi tӯ deadlock II Giӟi thiӋu Trong môi truӡng ÿa chѭѫng, nhiӅu quá trình có thӇ cҥnh tranh mӝt sӕ giӟi hҥn tài nguyên. Mӝt quá trình yêu cҫu tài nguyên, nӃu tài nguyên không sҷn dùng tҥi thӡi ÿiӇm ÿó, quá trình ÿi vào trҥng thái chӡ. Quá trình chӡ có thӇ không bao giӡ chuyӇn trҥng thái trӣ lҥi vì tài nguyên chúng yêu cҫu bӏ giӳ bӣi nhӳng quá trình ÿang chӡ khác. Trѭӡng hӧp này ÿѭӧc gӑi là deadlock (khoá chӃt). Trong chѭѫng này chúng ta sӁ mô tҧ các phѭѫng pháp mà hӋ ÿiӅu hành có thӇ dùng ÿӇ ngăn chһn hay giҧi quyӃt deadlock. Hҫu hӃt các hӋ ÿiӅu hành không cung cҩp phѭѫng tiӋn ngăn chһn deadlock nhѭng nhӳng ÿһc ÿiӇm này sӁ ÿѭӧc thêm vào sau ÿó. Vҩn ÿӅ deadlock chӍ có thӇ trӣ thành vҩn ÿӅ phә biӃn, xu hѭӟng hiӋn hành gӗm sӕ lѭӧng lӟn quá trình, chѭѫng trình ÿa luӗng, nhiӅu tài nguyên trong hӋ thӕng và ÿһc biӋt các tұp tin có ÿӡi sӕng dài và nhӳng máy phөc vө cѫ sӣ dӳ liӋu hѫn là các hӋ thӕng bó. III Mô hình hӋ thӕng Mӝt hӋ thӕng chӭa sӕ tài nguyên hӳu hҥn ÿѭӧc phân bә giӳa nhiӅu quá trình cҥnh tranh. Các tài nguyên này ÿѭӧc phân chia thành nhiӅu loҥi, mӛi loҥi chӭa mӝt sӕ thӇ hiӋn xác ÿӏnh. Không gian bӝ nhӟ, các chu kǤ CPU và các thiӃt bӏ nhұp/xuҩt (nhѭ máy in, ÿƭa tӯ) là nhӳng thí dө vӅ loҥi tài nguyên. NӃu hӋ thӕng có hai CPUs, thì loҥi tài nguyên CPU có hai thӇ hiӋn. Tѭѫng tӵ, loҥi tài nguyên máy in có thӇ có năm thӇ hiӋn. NӃu mӝt quá trình yêu cҫu mӝt thӇ hiӋn cӫa loҥi tài nguyên thì viӋc cҩp phát bҩt cӭ thӇ hiӋn nào cӫa loҥi tài nguyên này sӁ thoҧ mãn yêu cҫu. NӃu nó không có thì các thӇ hiӋn là không xác ÿӏnh và các lӟp loҥi tài nguyên sӁ không ÿѭӧc ÿӏnh nghƭa hӧp lý. Thí dө, mӝt hӋ thӕng có thӇ có hai máy in. Hai loҥi máy in này có thӇ ÿѭӧc ÿӏnh nghƭa trong cùng lӟp loҥi tài nguyên nӃu không có quá trình nào quan tâm máy nào in ra dӳ liӋu. Tuy nhiên, nӃu mӝt máy in ӣ tҫng 9 và máy in khác ӣ tҫng trӋt thì ngѭӡi dùng ӣ tҫng 9 không thӇ xem hai máy in là tѭѫng tӵ nhau và lӟp tài nguyên riêng rҿ cҫn ÿѭӧc ÿӏnh nghƭa cho mӛi máy in. Mӝt quá trình phҧi yêu cҫu mӝt tài nguyên trѭӟc khi sӱ dөng nó, và phҧi giҧi phóng sau khi sӱ dөng nó. Mӝt quá trình có thӇ yêu cҫu nhiӅu tài nguyên nhѭ nó ÿѭӧc Biên soҥn: Th.s NguyӉn Phú Trѭӡng - 09/2005 Trang 113
  2. Ĉҥi Hӑc Cҫn Thѫ - Khoa Công NghӋ Thông Tin - Giáo Trình HӋ ĈiӅu Hành – V1.0 yêu cҫu ÿӇ thӵc hiӋn tác vө ÿѭӧc gán cӫa nó. Chú ý, sӕ tài nguyên ÿѭӧc yêu cҫu không vѭӧt quá sӕ lѭӧng tәng cӝng tài nguyên sҷn có trong hӋ thӕng. Nói cách khác, mӝt quá trình không thӇ yêu cҫu ba máy in nӃu hӋ thӕng chӍ có hai. Dѭӟi chӃ ÿӝ ÿiӅu hành thông thѭӡng, mӝt quá trình có thӇ sӱ dөng mӝt tài nguyên chӍ trong thӭ tӵ sau: 1) Yêu cҫu: nӃu yêu cҫu không thӇ ÿѭӧc gán tӭc thì (thí dө, tài nguyên ÿang ÿѭӧc dùng bӣi quá trình khác) thì quá trình ÿang yêu cҫu phҧi chӡ cho tӟi khi nó có thӇ nhұn ÿѭӧc tài nguyên. 2) Sӱ dөng: quá trình có thӇ ÿiӅu hành tài nguyên (thí dө, nӃu tài nguyên là máy in, quá trình có thӇ in máy in) 3) Giҧi phóng: quá trình giҧi phóng tài nguyên. Yêu cҫu và giҧi phóng tài nguyên là các lӡi gӑi hӋ thӕng. Thí dө nhѭ yêu cҫu và giҧi phóng thiӃt bӏ, mӣ và ÿóng tұp tin, cҩp phát và giҧi phóng bӝ nhӟ. Yêu cҫu và giҧi phóng các tài nguyên khác có thӇ ÿҥt ÿѭӧc thông qua thao tác chӡ wait và báo hiӋu signal. Do ÿó, cho mӛi trѭӡng hӧp sӱ dөng, hӋ ÿiӅu hành kiӇm tra ÿӇ ÿҧm bҧo rҵng quá trình sӱ dөng yêu cҫu và ÿѭӧc cҩp phát tài nguyên. Mӝt bҧng hӋ thӕng ghi nhұn mӛi quá trình giҧi phóng hay ÿѭӧc cҩp phát tài nguyên. NӃu mӝt quá trình yêu cҫu tài nguyên mà tài nguyên ÿó hiӋn ÿѭӧc cҩp phát cho mӝt quá trình khác, nó có thӇ ÿѭӧc thêm vào hàng ÿӧi ÿӇ chӡ tài nguyên này. Mӝt tұp hӧp quá trình trong trҥng thái deadlock khi mӛi quá trình trong tұp hӧp này chӡ sӵ kiӋn mà có thӇ ÿѭӧc tҥo ra chӍ bӣi quá trình khác trong tұp hӧp. Nhӳng sӵ kiӋn mà chúng ta quan tâm chӫ yӃu ӣ ÿây là nhұn và giҧi phóng tài nguyên. Các tài nguyên có thӇ là tài nguyên vұt lý (thí dө, máy in, ÿƭa tӯ, không gian bӝ nhӟ và chu kǤ CPU) hay tài nguyên luұn lý (thí dө, tұp tin, semaphores, monitors). Tuy nhiên, các loҥi khác cӫa sӵ kiӋn có thӇ dүn ÿӃn deadlock. ĈӇ minh hoҥ trҥng thái deadlock, chúng ta xét hӋ thӕng vӟi ba ә ÿƭa tӯ. Giҧ sӱ mӛi quá trình giӳ các mӝt ә ÿƭa tӯ này. Bây giӡ, nӃu mӛi quá trình yêu cҫu mӝt ә ÿƭa tӯ khác thì ba quá trình sӁ ӣ trong trҥng thái deadlock. Mӛi quá trình ÿang chӡ mӝt sӵ kiӋn “ә ÿƭa tӯ ÿѭӧc giҧi phóng” mà có thӇ ÿѭӧc gây ra chӍ bӣi mӝt trong nhӳng quá trình ÿang chӡ. Thí dө này minh hoҥ deadlock liên quan ÿӃn cùng loҥi tài nguyên. Deadlock cNJng liên quan nhiӅu loҥi tài nguyên khác nhau. Thí dө, xét mӝt hӋ thӕng vӟi mӝt máy in và mӝt ә ÿƭa tӯ. Giҧ sӱ, quá trình Pi ÿang giӳ ә ÿƭa tӯ và quá trình Pj ÿang giӳ máy in. NӃu Pi yêu cҫu máy in và Pj yêu cҫu ә ÿƭa tӯ thì deadlock xҧy ra. Mӝt ngѭӡi lұp trình ÿang phát triӇn nhӳng ӭng dөng ÿa luӗng phҧi quan tâm ÿһc biӋt tӟi vҩn ÿӅ này: Các chѭѫng trình ÿa luӗng là ӭng cӱ viên cho vҩn ÿӅ deadlock vì nhiӅu luӗng có thӇ cҥnh tranh trên tài nguyên ÿѭӧc chia sҿ. IV Ĉһc ÿiӇm deadlock Trong mӝt deadlock, các quá trình không bao giӡ hoàn thành viӋc thӵc thi và các tài nguyên hӋ thӕng bӏ buӝc chһt, ngăn chһn các quá trình khác bҳt ÿҫu. Trѭӟc khi chúng ta thҧo luұn các phѭѫng pháp khác nhau giҧi quyӃt vҩn ÿӅ deadlock, chúng ta sӁ mô tҧ các ÿһc ÿiӇm mà deadlock mô tҧ. Biên soҥn: Th.s NguyӉn Phú Trѭӡng - 09/2005 Trang 114
  3. Ĉҥi Hӑc Cҫn Thѫ - Khoa Công NghӋ Thông Tin - Giáo Trình HӋ ĈiӅu Hành – V1.0 IV.1 Nhӳng ÿiӅu kiӋn cҫn thiӃt gây ra deadlock Trѭӡng hӧp deadlock có thӇ phát sinh nӃu bӕn ÿiӅu kiӋn sau xҧy ra cùng mӝt lúc trong hӋ thӕng: 1) Loҥi trӯ hӛ tѭѫng: ít nhҩt mӝt tài nguyên phҧi ÿѭӧc giӳ trong chӃ ÿӝ không chia sҿ; nghƭa là, chӍ mӝt quá trình tҥi cùng mӝt thӡi ÿiӇm có thӇ sӱ dөng tài nguyên. NӃu mӝt quá trình khác yêu cҫu tài nguyên ÿó, quá trình yêu cҫu phҧi tҥm dӯng cho ÿӃn khi tài nguyên ÿѭӧc giҧi phóng. 2) Giӳ và chӡ cҩp thêm tài nguyên: quá trình phҧi ÿang giӳ ít nhҩt mӝt tài nguyên và ÿang chӡ ÿӇ nhұn tài nguyên thêm mà hiӋn ÿang ÿѭӧc giӳ bӣi quá trình khác. 3) Không ÿòi lҥi tài nguyên tӯ quá trình ÿang giӳ chúng: Các tài nguyên không thӇ bӏ ÿòi lҥi; nghƭa là, tài nguyên có thӇ ÿѭӧc giҧi phóng chӍ tӵ ý bӣi quá trình ÿang giӳ nó, sau khi quá trình ÿó hoàn thành tác vө. 4) Tӗn tҥi chu trình trong ÿӗ thӏ cҩp phát tài nguyên: mӝt tұp hӧp các quá trình {P0, P1,…,Pn} ÿang chӡ mà trong ÿó P0 ÿang chӡ mӝt tài nguyên ÿѭӧc giӳ bӣi P1, P1 ÿang chӡ tài nguyên ÿang giӳ bӣi P2,…,Pn-1 ÿang chӡ tài nguyên ÿang ÿѭӧc giӳ bӣi quá trình P0. Chúng ta nhҩn mҥnh rҵng tҩt cҧ bӕn ÿiӅu kiӋn phҧi cùng phát sinh ÿӇ deadlock xҧy ra. ĈiӅu kiӋn chӡ ÿӧi ch trình ÿѭa ÿӃn ÿiӅu kiӋn giӳ-và-chӡ vì thӃ bӕn ÿiӅu kiӋn không hoàn toàn ÿӝc lұp. IV.2 Ĉӗ thӏ cҩp phát tài nguyên Deadlock có thӇ mô tҧ chính xác hѫn bҵng cách hiӇn thӏ ÿӗ thӏ có hѭӟng gӑi là ÿӗ thӏ cҩp phát tài nguyên hӋ thӕng. Ĉӗ thӏ này chӭa mӝt tұp các ÿӍnh V và tұp hӧp các cҥnh E. Mӝt tұp các ÿӍnh V ÿѭӧc chia làm hai loҥi nút P = {P1, P2,…,Pn} là tұp hӧp các quá trình hoҥt ÿӝng trong hӋ thӕng, và R = {R1, R2, ..., Rm} là tұp hӧp chӭa tҩt cҧ các loҥi tài nguyên trong hӋ thӕng. Mӝt cҥnh có hѭӟng tӯ quá trình Pi tӟi loҥi tài nguyên Rj ÿѭӧc ký hiӋu Pi oRj; nó biӇu thӏ rҵng quá trình Pi ÿã yêu cҫu loҥi tài nguyên Rj và hiӋn ÿang chӡ loҥi tài nguyên ÿó. Mӝt cҥnh có hѭӟng tӯ loҥi tài nguyên Rj tӟi quá trình Pi ÿѭӧc hiӇn thӏ bӣi Rj o Pi; nó hiӇn thӏ rҵng thӇ hiӋn cӫa loҥi tài nguyên Rj ÿã ÿѭӧc cҩp phát tӟi quá trình Pi. Mӝt cҥnh có hѭӟng Pi o Rj ÿѭӧc gӑi là cҥnh yêu cҫu; mӝt cҥnh có hѭӟng Rj o Pi ÿѭӧc gӑi là cҥnh gán. Bҵng hình tѭӧng, chúng ta hiӇn thӏ mӛi quá trình Pi là mӝt hình tròn, và mӛi loҥi tài nguyên Rj là hình chӳ nhұt. Vì loҥi tài nguyên Rj có thӇ có nhiӅu hѫn mӝt thӇ hiӋn, chúng ta hiӇn thӏ mӛi thӇ hiӋn là mӝt chҩm nҵm trong hình vuông. Chú ý rҵng mӝt cҥnh yêu cҫu trӓ tӟi chӍ mӝt hình vuông Rj, trái lҥi mӝt cҥnh gán cNJng phҧi gán tӟi mӝt trong các dҩu chҩm trong hình vuông. Khi quá trình Pi yêu cҫu mӝt thӇ hiӋn cӫa loҥi tài nguyên Rj, mӝt cҥnh yêu cҫu ÿѭӧc chèn vào ÿӗ thӏ cҩp phát tài nguyên. Khi yêu cҫu này có thӇ ÿѭӧc ÿáp ӭng, cҥnh yêu cҫu lұp tӭc ÿѭӧc truyӅn tӟi cҥnh gán. Khi quá trình không còn cҫn truy xuҩt tӟi tài nguyên, nó giҧi phóng tài nguyên, và khi ÿó dүn ÿӃn cҥnh gán bӏ xoá. Ĉӗ thӏ cҩp phát tài nguyên ÿѭӧc hiӇn thӏ trong hình VI-1 dѭӟi ÿây mô tҧ trѭӡng hӧp sau: Biên soҥn: Th.s NguyӉn Phú Trѭӡng - 09/2005 Trang 115
  4. Ĉҥi Hӑc Cҫn Thѫ - Khoa Công NghӋ Thông Tin - Giáo Trình HӋ ĈiӅu Hành – V1.0 Hình 0-1 Ĉӗ thӏ cҩp phát tài nguyên x Các tұp P, R, và E: o P = {P1, P2, P3} o R = {R1, R2, R3, R4} o E = {P1oR1, P2 oR3, R1 oP2, R2oP2, R3oP3} x Các thӇ hiӋn tài nguyên o Mӝt thӇ hiӋn cӫa tài nguyên loҥi R1 o Hai thӇ hiӋn cӫa tài nguyên loҥi R2 o Mӝt thӇ hiӋn cӫa tài nguyên loҥi R3 o Mӝt thӇ hiӋn cӫa tài nguyên loҥi R4 x Trҥng thái quá trình o Quá trình P1 ÿang giӳ mӝt thӇ hiӋn cӫa loҥi tài nguyên R2 và ÿang chӡ mӝt thӇ hiӋn cӫa loҥi tài nguyên R1. o Quá trình P2 ÿang giӳ mӝt thӇ hiӋn cӫa loҥi tài nguyên R1 và R2 và ÿang chӡ mӝt thӇ hiӋn cӫa loҥi tài nguyên R3. o Quá trình P3 ÿang giӳ mӝt thӇ hiӋn cӫa R3 Ĉӗ thӏ cҩp phát tài nguyên hiӇn thӏ rҵng, nӃu ÿӗ thӏ không chӭa chu trình, thì không có quá trình nào trong hӋ thӕng bӏ deadlock. NӃu ÿӗ thӏ có chӭa chu trình, thì deadlock có thӇ tӗn tҥi. NӃu mӛi loҥi tài nguyên có chính xác mӝt thӇ hiӋn, thì mӝt chu trình ngө ý rҵng mӝt deadlock xҧy ra. NӃu mӝt chu trình bao gӗm chӍ mӝt tұp hӧp các loҥi tài nguyên, mӛi loҥi tài nguyên chӍ có mӝt thӇ hiӋn thì deadlock xҧy ra. Mӛi quá trình chӭa trong chu trình bӏ deadlock. Trong trѭӡng hӧp này, mӝt chu trình trong ÿӗ thӏ là ÿiӅu kiӋn cҫn và ÿӫ ÿӇ tӗn tҥi deadlock. NӃu mӛi loҥi tài nguyên có nhiӅu thӇ hiӋn thì chu trình không ngө ý deadlock xҧy. Trong trѭӡng hӧp này, mӝt chu trình trong ÿӗ thӏ là ÿiӅu kiӋn cҫn nhѭng chѭa ÿӫ ÿӇ tӗn tҥi deadlock. ĈӇ hiӇn thӏ khái niӋm này, chúng ta xem lҥi ÿӗ thӏ ӣ hình VII-1 ӣ trên. Giҧ sӱ quá trình P3 yêu cҫu mӝt thӇ hiӋn cӫa loҥi tài nguyên R2. Vì không có thӇ hiӋn tài nguyên hiӋn có, mӝt cҥnh yêu cҫu P3 o R2 ÿѭӧc thêm vào ÿӗ thӏ (hình VI-2). Tҥi thӡi ÿiӇm này, hai chu trình nhӓ tӗn tҥi trong hӋ thӕng: Biên soҥn: Th.s NguyӉn Phú Trѭӡng - 09/2005 Trang 116
  5. Ĉҥi Hӑc Cҫn Thѫ - Khoa Công NghӋ Thông Tin - Giáo Trình HӋ ĈiӅu Hành – V1.0 P1 o R1 o P2 o R3 o P3 o R2 o P1 P2 o R3 o P3 o R2 o P2 Hình 0-2 Ĉӗ thӏ cҩp phát tài nguyên vӟi deadlock Quá trình P1, P2, và P3 bӏ deadlock. Quá trình P3 ÿang chӡ tài nguyên R3, hiӋn ÿѭӧc giӳ bӣi quá trình P2. Hay nói cách khác, quá trình P3 ÿang chӡ quá trình P1 hay P2 giҧi phóng tài nguyên R2. Ngoài ra, quá trình P1 ÿang chӡ quá trình P2 giҧi phóng tài nguyên R1. Bây giӡ xem xét ÿӗ thӏ cҩp phát tài nguyên trong hình VI-3 dѭӟi ÿây. Trong thí dө này, chúng ta cNJng có mӝt chu kǤ P1 o R1 o P3 o R2 o P1 Hình 0-3 Ĉӗ thӏ cҩp phát tài nguyên có chu trình nhѭng không bӏ deadlock Biên soҥn: Th.s NguyӉn Phú Trѭӡng - 09/2005 Trang 117
  6. Ĉҥi Hӑc Cҫn Thѫ - Khoa Công NghӋ Thông Tin - Giáo Trình HӋ ĈiӅu Hành – V1.0 Tuy nhiên, không có deadlock. Chú ý rҵng quá trình P4 có thӇ giҧi phóng thӇ hiӋn cӫa loҥi tài nguyên R2. Tài nguyên ÿó có thӇ ÿѭӧc cҩp phát tӟi P3 sau ÿó, chu trình sӁ không còn. Tóm lҥi, nӃu ÿӗ thӏ cҩp phát tài nguyên không có chu trình thì hӋ thӕng không có trҥng thái deadlock. Ngoài ra, nӃu có chu trình thì có thӇ có hoһc không trҥng thái deadlock. Nhұn xét này là quan trӑng khi chúng ta giҧi quyӃt vҩn ÿӅ deadlock. V Các phѭѫng pháp xӱ lý deadlock Phҫn lӟn, chúng ta có thӇ giҧi quyӃt vҩn ÿӅ deadlock theo mӝt trong ba cách: x Chúng ta có thӇ sӱ dөng mӝt giao thӭc ÿӇ ngăn chһn hay tránh deadlocks, ÿҧm bҧo rҵng hӋ thӕng sӁ không bao giӡ ÿi vào trҥng thái deadlock x Chúng ta có thӇ cho phép hӋ thӕng ÿi vào trҥng thái deadlock, phát hiӋn nó và phөc hӗi. x Chúng ta có thӇ bӓ qua hoàn toàn vҩn ÿӅ này và giҧ vӡ deadlock không bao giӡ xҧy ra trong hӋ thӕng. Giҧi pháp này ÿѭӧc dùng trong nhiӅu hӋ ÿiӅu hành, kӇ cҧ UNIX. x Chúng ta sӁ tìm hiӇu vҳn tҳt mӛi phѭѫng pháp. Sau ÿó, chúng ta sӁ trình bày các giҧi thuұt mӝt cách chi tiӃt trong các phҫn sau ÿây. ĈӇ ÿҧm bҧo deadlock không bao giӡ xҧy ra, hӋ thӕng có thӇ dùng kӃ hoҥch ngăn chһn hay tránh deadlock. Ngăn chһn deadlock là mӝt tұp hӧp các phѭѫng pháp ÿӇ ÿҧm bҧo rҵng ít nhҩt mӝt ÿiӅu kiӋn cҫn (trong phҫn VI.4.1) không thӇ xҧy ra. Các phѭѫng pháp này ngăn chһn deadlocks bҵng cách ràng buӝc yêu cҫu vӅ tài nguyên ÿѭӧc thӵc hiӋn nhѭ thӃ nào. Chúng ta thҧo luұn phѭѫng pháp này trong phҫn sau. Ngѭӧc lҥi, tránh deadlock yêu cҫu hӋ ÿiӅu hành cung cҩp nhӳng thông tin bә sung tұp trung vào loҥi tài nguyên nào mӝt quá trình sӁ yêu cҫu và sӱ dөng trong thӡi gian sӕng cӫa nó. Vӟi nhӳng kiӃn thӭc bә sung này, chúng ta có thӇ quyӃt ÿӏnh ÿӕi vӟi mӛi yêu cҫu quá trình nên chӡ hay không. ĈӇ quyӃt ÿӏnh yêu cҫu hiӋn tҥi có thӇ ÿѭӧc thoҧ mãn hay phҧi bӏ trì hoãn, hӋ thӕng phҧi xem xét tài nguyên hiӋn có, tài nguyên hiӋn cҩp phát cho mӛi quá trình, và các yêu cҫu và giҧi phóng tѭѫng lai cӫa mӛi quá trình. NӃu mӝt hӋ thӕng không dùng giҧi thuұt ngăn chһn hay tránh deadlock thì trѭӡng hӧp deadlock có thӇ xҧy ra. Trong môi trѭӡng này, hӋ thӕng có thӇ cung cҩp mӝt giҧi thuұt ÿӇ xem xét trҥng thái cӫa hӋ thӕng ÿӇ xác ÿӏnh deadlock có xҧy ra hay không và giҧi thuұt phөc hӗi tӯ deadlock. NӃu hӋ thӕng không ÿҧm bҧo rҵng deadlock sӁ không bao giӡ xҧy ra và cNJng không cung cҩp mӝt cѫ chӃ ÿӇ phát hiӋn và phөc hӗi deadlock thì có thӇ dүn ÿӃn trѭӡng hӧp hӋ thӕng ӣ trong trҥng thái deadlock. Trong trѭӡng hӧp này, deadlock không ÿѭӧc phát hiӋn sӁ làm giҧm năng lӵc hӋ thӕng vì tài nguyên ÿang ÿѭӧc giӳ bӣi nhӳng quá trình mà chúng không thӇ thӵc thi, ÿi vào trҥng thái deadlock. Cuӕi cùng, hӋ thӕng sӁ dӯng các chӭc năng và cҫn ÿѭӧc khӣi ÿӝng lҥi bҵng thӫ công. Mһc dù phѭѫng pháp này dѭӡng nhѭ không là tiӃp cұn khҧ thi ÿӕi vӟi vҩn ÿӅ deadlock nhѭng nó ÿѭӧc dùng trong mӝt sӕ hӋ ÿiӅu hành. Trong nhiӅu hӋ thӕng, deadlock xҧy ra không thѭӡng xuyên; do ÿó phѭѫng pháp này là rҿ hѫn chi phí cho phѭѫng pháp ngăn chһn deadlock, tránh deadlock, hay phát hiӋn và phөc hӗi deadlock mà chúng phҧi ÿѭӧc sӱ dөng liên tөc. Trong mӝt sӕ trѭӡng hӧp, hӋ thӕng ӣ trong trҥng thái cô ÿһc nhѭng không ӣ trҥng thái deadlock. Nhѭ thí dө, xem xét mӝt quá trình thӡi thӵc chҥy tҥi ÿӝ ѭu tiên cao nhҩt (hay bҩt cӭ quá trình ÿang chҥy trên bӝ Biên soҥn: Th.s NguyӉn Phú Trѭӡng - 09/2005 Trang 118
  7. Ĉҥi Hӑc Cҫn Thѫ - Khoa Công NghӋ Thông Tin - Giáo Trình HӋ ĈiӅu Hành – V1.0 ÿӏnh thӡi biӇu không trѭng dөng) và không bao giӡ trҧ vӅ ÿiӅu khiӇn ÿӕi vӟi hӋ ÿiӅu hành. Do ÿó, hӋ thӕng phҧi có phѭѫng pháp phөc hӗi bҵng thӫ công cho các ÿiӅu kiӋn không deadlock và có thӇ ÿѫn giҧn sӱ dөng các kӻ thuұt ÿó cho viӋc phөc hӗi deadlock. VI Ngăn chһn deadlock ĈӇ deadlock xҧy ra, mӝt trong bӕn ÿiӅu kiӋn cҫn phҧi xҧy ra. Bҵng cách ÿҧm bҧo ít nhҩt mӝt trong bӕn ÿiӅu kiӋn này không thӇ xҧy ra, chúng ta có thӇ ngăn chһn viӋc xҧy ra cӫa deadlock. Chúng ta tìm hiӇu tӹ mӻ tiӃp cұn này bҵng cách xem xét mӛi ÿiӅu kiӋn cҫn riêng rҿ nhau. VI.1 Loҥi trӯ hӛ tѭѫng ĈiӅu kiӋn loҥi trӯ hӛ tѭѫng phҧi giӳ cho tài nguyên không chia sҿ. Thí dө, mӝt máy in không thӇ ÿѭӧc chia sҿ cùng lúc bӣi nhiӅu quá trình. Ngѭӧc lҥi, các tài nguyên có thӇ chia sҿ không ÿòi hӓi truy xuҩt loҥi trӯ hӛ tѭѫng và do ÿó không thӇ liên quan ÿӃn deadlock. Nhӳng tұp tin chӍ ÿӑc là mӝt thí dө tӕt cho tài nguyên có thӇ chia sҿ. NӃu nhiӅu quá trình cӕ gҳng mӣ mӝt tұp tin chӍ ÿӑc tҥi cùng mӝt thӡi ÿiӇm thì chúng có thӇ ÿѭӧc gán truy xuҩt cùng lúc tұp tin. Mӝt quá trình không bao giӡ yêu cҫu chӡ tài nguyên có thӇ chia sҿ. Tuy nhiên, thѭӡng chúng ta không thӇ ngăn chһn deadlock bҵng cách tӯ chӕi ÿiӅu kiӋn loҥi trӯ hӛ tѭѫng: mӝt sӕ tài nguyên vӅ thӵc chҩt không thӇ chia sҿ. VI.2 Giӳ và chӡ cҩp thêm tài nguyên ĈӇ ÿҧm bҧo ÿiӅu kiӋn giӳ-và-chӡ cҩp thêm tài nguyên không bao giӡ xҧy ra trong hӋ thӕng, chúng ta phҧi ÿҧm bҧo rҵng bҩt cӭ khi nào mӝt quá trình yêu cҫu tài nguyên, nó không giӳ bҩt cӭ tài nguyên nào khác. Mӝt giao thӭc có thӇ ÿѭӧc dùng là ÿòi hӓi mӛi quá trình yêu cҫu và ÿѭӧc cҩp phát tҩt cҧ tài nguyên trѭӟc khi nó bҳt ÿҫu thӵc thi. Chúng ta có thӇ cài ÿһt sӵ cung cҩp này bҵng cách yêu cҫu các lӡi gӑi hӋ thӕng yêu cҫu tài nguyên cho mӝt quá trình trѭӟc tҩt cҧ các lӡi gӑi hӋ thӕng khác. Mӝt giao thӭc khác cho phép mӝt quá trình yêu cҫu tài nguyên chӍ khi quá trình này không có tài nguyên nào. Mӝt quá trình có thӇ yêu cҫu mӝt sӕ tài nguyên và dùng chúng. Tuy nhiên, trѭӟc khi nó có thӇ yêu cҫu bҩt kǤ tài nguyên bә sung nào, nó phҧi giҧi phóng tҩt cҧ tài nguyên mà nó hiӋn ÿang ÿѭӧc cҩp phát. ĈӇ hiӇn thӏ sӵ khác nhau giӳa hai giao thӭc, chúng ta xét mӝt quá trình chép dӳ liӋu tӯ băng tӯ tӟi tұp tin ÿƭa, sҳp xӃp tұp tin ÿƭa và sau ÿó in kӃt quҧ ra máy in. NӃu tҩt cҧ tài nguyên phҧi ÿѭӧc yêu cҫu cùng mӝt lúc thì khӣi ÿҫu quá trình phҧi yêu cҫu băng tӯ, tұp tin ÿƭa và máy in. Nó sӁ giӳ máy in trong toàn thӡi gian thӵc thi cӫa nó mһc dù nó cҫn máy in chӍ ӣ giai ÿoҥn cuӕi. Phѭѫng pháp thӭ hai cho phép quá trình yêu cҫu ban ÿҫu chӍ băng tӯ và tұp tin ÿƭa. Nó chép dӳ liӋu tӯ băng tӯ tӟi ÿƭa, rӗi giҧi phóng cҧ hai băng tӯ và ÿƭa. Sau ÿó, quá trình phҧi yêu cҫu lҥi tұp tin ÿƭa và máy in. Sau ÿó, chép tұp tin ÿƭa tӟi máy in, nó giҧi phóng hai tài nguyên này và kӃt thúc. Hai giao thӭc này có hai nhѭӧc ÿiӇm chӫ yӃu. Thӭ nhҩt, viӋc sӱ dөng tài nguyên có thӇ chұm vì nhiӅu tài nguyên có thӇ ÿѭӧc cҩp nhѭng không ÿѭӧc sӱ dөng trong thӡi gian dài. Trong thí dө ÿѭӧc cho, chúng ta có thӇ giҧi phóng băng tӯ và tұp tin ÿƭa, sau ÿó yêu cҫu lҥi tұp tin ÿƭa và máy in chӍ nӃu chúng ta ÿҧm bҧo rҵng dӳ liӋu cӫa chúng ta sӁ vүn còn trên tұp tin ÿƭa. NӃu chúng ta không thӇ ÿҧm bҧo rҵng dӳ liӋu Biên soҥn: Th.s NguyӉn Phú Trѭӡng - 09/2005 Trang 119
  8. Ĉҥi Hӑc Cҫn Thѫ - Khoa Công NghӋ Thông Tin - Giáo Trình HӋ ĈiӅu Hành – V1.0 vүn còn tұp tin ÿƭa thì chúng ta phҧi yêu cҫu tҩt cҧ tài nguyên tҥi thӡi ÿiӇm bҳt ÿҫu cho cҧ hai giao thӭc. Thӭ hai, ÿói tài nguyên là có thӇ. Mӝt quá trình cҫn nhiӅu tài nguyên phә biӃn có thӇ phҧi ÿӧi vô hҥn ÿӏnh vì mӝt tài nguyên mà nó cҫn luôn ÿѭӧc cҩp phát cho quá trình khác. VI.3 Không ÿòi lҥi tài nguyên tӯ quá trình ÿang giӳ chúng ĈiӅu kiӋn cҫn thӭ ba là không ÿòi lҥi nhӳng tài nguyên ÿã ÿѭӧc cҩp phát rӗi. ĈӇ ÿҧm bҧo ÿiӅu kiӋn này không xҧy ra, chúng ta có thӇ dùng giao thӭc sau. NӃu mӝt quá trình ÿang giӳ mӝt sӕ tài nguyên và yêu cҫu tài nguyên khác mà không ÿѭӧc cҩp phát tӭc thì tӟi nó (nghƭa là, quá trình phҧi chӡ) thì tҩt cҧ tài nguyên hiӋn ÿang giӳ ÿѭӧc ÿòi lҥi. Nói cách khác, nhӳng tài nguyên này ÿѭӧc giҧi phóng hoàn toàn. Nhӳng tài nguyên bӏ ÿòi lҥi ÿѭӧc thêm tӟi danh sách các tài nguyên mà quá trình ÿang chӡ. Quá trình sӁ ÿѭӧc khӣi ÿӝng lҥi chӍ khi nó có thӇ nhұn lҥi tài nguyên cNJ cӫa nó cNJng nhѭ các tài nguyên mӟi mà nó ÿang yêu cҫu. Có mӝt sӵ chӑn lӵa khác, nӃu mӝt quá trình yêu cҫu mӝt sӕ tài nguyên, ÿҫu tiên chúng ta kiӇm tra chúng có sҷn không. NӃu tài nguyên có sҷn, chúng ta cҩp phát chúng. NӃu tài nguyên không có sҷn, chúng ta kiӇm tra chúng có ÿѭӧc cҩp phát tӟi mӝt sӕ quá trình khác ÿang chӡ tài nguyên bә sung. NӃu ÿúng nhѭ thӃ, chúng ta lҩy lҥi tài nguyên mong muӕn ÿó tӯ quá trình ÿang ÿӧi và cҩp chúng cho quá trình ÿang yêu cҫu. NӃu tài nguyên không sҷn có hay ÿѭӧc giӳ bӣi mӝt quá trình ÿang ÿӧi, quá trình ÿang yêu cҫu phҧi chӡ. Trong khi nó ÿang chӡ, mӝt sӕ tài nguyên cӫa nó có thӇ ÿѭӧc ÿòi lҥi chӍ nӃu quá trình khác yêu cҫu chúng. Mӝt quá trình có thӇ ÿѭӧc khӣi ÿӝng lҥi chӍ khi nó ÿѭӧc cҩp các tài nguyên mӟi mà nó ÿang yêu cҫu và phөc hӗi bҩt cӭ tài nguyên nào ÿã bӏ lҩy lҥi trong khi nó ÿang chӡ. Giao thӭc này thѭӡng ÿѭӧc áp dөng tӟi tài nguyên mà trҥng thái cӫa nó có thӇ ÿѭӧc lѭu lҥi dӉ dàng và phөc hӗi lҥi sau ÿó, nhѭ các thanh ghi CPU và không gian bӝ nhӟ. Nó thѭӡng không thӇ ÿѭӧc áp dөng cho các tài nguyên nhѭ máy in và băng tӯ. VI.4 Tӗn tҥi chu trình trong ÿӗ thӏ cҩp phát tài nguyên ĈiӅu kiӋn thӭ tѭ và cNJng là ÿiӅu kiӋn cuӕi cùng cho deadlock là ÿiӅu kiӋn tӗn tҥi chu trình trong ÿӗ thӏ cҩp phát tài nguyên. Mӝt cách ÿӇ ÿҧm bҧo rҵng ÿiӅu kiӋn này không bao giӡ xҧy ra là áp ÿһt toàn bӝ thӭ tӵ cӫa tҩt cҧ loҥi tài nguyên và ÿòi hӓi mӛi quá trình trong thӭ tӵ tăng cӫa sӕ lѭӧng. Gӑi R = {R1, R2, …, Rm} là tұp hӧp loҥi tài nguyên. Chúng ta gán mӛi loҥi tài nguyên mӝt sӕ nguyên duy nhҩt, cho phép chúng ta so sánh hai tài nguyên và xác ÿӏnh tài nguyên này có ÿӭng trѭӟc tài nguyên khác hay không trong thӭ tӵ cӫa chúng ta. Thông thѭӡng, chúng ta ÿӏnh nghƭa hàm ánh xҥ mӝt-mӝt F: R o N, ӣ ÿây N là tұp hӧp các sӕ tӵ nhiên. Thí dө, nӃu tұp hӧp các loҥi tài nguyên R gӗm các ә băng tӯ, ә ÿƭa và máy in thì hàm F có thӇ ÿѭӧc ÿӏnh nghƭa nhѭ sau: F(ә băng tӯ) = 1, F(ÿƭa tӯ) = 5, F(máy in) = 12. Bây giӡ chúng ta xem giao thӭc sau ÿӇ ngăn chһn deadlock: mӛi quá trình có thӇ yêu cҫu tài nguyên chӍ trong thӭ tӵ tăng cӫa sӕ lѭӧng. Nghƭa là, mӝt quá trình ban ÿҫu có thӇ yêu cҫu bҩt cӭ sӕ lѭӧng thӇ hiӋn cӫa mӝt loҥi tài nguyên Ri. Sau ÿó, mӝt quá trình có thӇ yêu cҫu các thӇ hiӋn cӫa loҥi tài nguyên Rj nӃu và chӍ nӃu F(Rj) > F(Ri). NӃu mӝt sӕ thӇ hiӋn cӫa cùng loҥi tài nguyên ÿѭӧc yêu cҫu, thì mӝt yêu cҫu cho tҩt cҧ thӇ hiӋn phҧi ÿѭӧc cҩp phát. Thí dө, sӱ dөng hàm ÿѭӧc ÿӏnh nghƭa trѭӟc ÿó, Biên soҥn: Th.s NguyӉn Phú Trѭӡng - 09/2005 Trang 120
  9. Ĉҥi Hӑc Cҫn Thѫ - Khoa Công NghӋ Thông Tin - Giáo Trình HӋ ĈiӅu Hành – V1.0 mӝt quá trình muӕn dùng ә băng tӯ và máy in tҥi cùng mӝt lúc trѭӟc tiên phҧi yêu cҫu ә băng tӯ và sau ÿó yêu cҫu máy in. Nói mӝt cách khác, chúng ta yêu cҫu rҵng, bҩt cӭ khi nào mӝt quá trình yêu cҫu mӝt thӇ hiӋn cӫa loҥi tài nguyên Rj, nó giҧi phóng bҩt cӭ tài nguyên Ri sao cho F(Ri) t F(Rj). NӃu có hai giao thӭc ÿѭӧc dùng thì ÿiӅu kiӋn tӗn tҥi chu trình không thӇ xҧy ra. Chúng ta có thӇ giҧi thích ÿiӅu này bҵng cách cho rҵng tӗn tҥi chu trình trong ÿӗ thӏ cҩp phát tài nguyên tӗn tҥi. Gӑi tұp hӧp các quá trình chӭa tӗn tҥi chu trình trong ÿӗ thӏ cҩp phát tài nguyên là {P0, P1, … , Pn}, ӣ ÿây Pi ÿang chӡ mӝt tài nguyên Ri, mà Ri ÿѭӧc giӳ bӣi quá trình Pi+1. Vì sau ÿó quá trình Pi+1 ÿang giӳ tài nguyên Ri trong khi yêu cҫu tài nguyên Ri+1, nên chúng ta có F(Ri) < F(Ri+1) cho tҩt cҧ i. Nhѭng ÿiӅu kiӋn này có nghƭa là F(R0) < F(R1) < …< F(Rn) < F(R0). Bҵng qui tҳc bҳt cҫu F(R0) < F(R0), ÿiӅu này là không thӇ. Do ÿó, không thӇ có chӡ chu trình. Chú ý rҵng hàm F nên ÿѭӧc ÿӏnh nghƭa dӵa theo thӭ tӵ tӵ nhiên cӫa viӋc sӱ dөng tài nguyên trong hӋ thӕng. Thí dө, vì ә băng tӯ thѭӡng ÿѭӧc yêu cҫu trѭӟc máy in nên có thӇ hӧp lý ÿӇ ÿӏnh nghƭa F( ә băng tӯ) < F(máy in). VIITránh deadlock Các giҧi thuұt ngăn chһn deadlock, ÿѭӧc thҧo luұn ӣ VII-6, ngăn chһn deadlock bҵng cách hҥn chӃ cách các yêu cҫu có thӇ ÿѭӧc thӵc hiӋn. Các ngăn chһn ÿҧm bҧo rҵng ít nhҩt mӝt trong nhӳng ÿiӅu kiӋn cҫn cho deadlock không thӇ xҧy ra. Do ÿó, deadlock không thӇ xҧy ra. Tuy nhiên, các tác dөng phө có thӇ ngăn chһn deadlock bӣi phѭѫng pháp này là viӋc sӱ dөng thiӃt bӏ chұm và thông lѭӧng hӋ thӕng bӏ giҧm. Mӝt phѭѫng pháp khác ÿӇ tránh deadlock là yêu cҫu thông tin bә sung vӅ cách tài nguyên ÿѭӧc yêu cҫu. Thí dө, trong mӝt hӋ thӕng vӟi mӝt ә băng tӯ và mӝt máy in, chúng ta có thӇ bҧo rҵng quá trình P sӁ yêu cҫu ә băng tӯ trѭӟc và sau ÿó máy in trѭӟc khi giҧi phóng cҧ hai tài nguyên. Trái lҥi, quá trình Q sӁ yêu cҫu máy in trѭӟc và sau ÿó ә băng tӯ. Vӟi kiӃn thӭc vӅ thӭ tӵ hoàn thành cӫa yêu cҫu và giҧi phóng cho mӛi quá trình, chúng ta có thӇ quyӃt ÿӏnh cho mӛi yêu cҫu cӫa quá trình sӁ chӡ hay không. Mӛi yêu cҫu ÿòi hӓi hӋ thӕng xem tài nguyên hiӋn có, tài nguyên hiӋn ÿѭӧc cҩp tӟi mӛi quá trình, và các yêu cҫu và giҧi phóng tѭѫng lai cӫa mӛi quá trình, ÿӇ yêu cҫu cӫa quá trình hiӋn tҥi có thӇ ÿѭӧc thoҧ mãn hay phҧi chӡ ÿӇ tránh khҧ năng xҧy ra deadlock. Các giҧi thuұt khác nhau có sӵ khác nhau vӅ lѭӧng và loҥi thông tin ÿѭӧc yêu cҫu. Mô hình ÿѫn giҧn và hӳu ích nhҩt yêu cҫu mӛi quá trình khai báo sӕ lӟn nhҩt tài nguyên cӫa mӛi loҥi mà nó cҫn. Thông tin trѭӟc vӅ sӕ lѭӧng tӕi ÿa tài nguyên cӫa mӛi loҥi ÿѭӧc yêu cҫu cho mӛi quá trình, có thӇ xây dӵng mӝt giҧi thuұt ÿҧm bҧo hӋ thӕng sӁ không bao giӡ ÿi vào trҥng thái deadlock. Ĉây là giҧi thuұt ÿӏnh nghƭa tiӃp cұn tránh deadlock. Giҧi thuұt tránh deadlock tӵ xem xét trҥng thái cҩp phát tài nguyên ÿӇ ÿҧm bҧo ÿiӅu kiӋn tӗn tҥi chu trình trong ÿӗ thӏ cҩp phát tài nguyên có thӇ không bao giӡ xҧy ra. Trҥng thái cҩp phát tài nguyên ÿѭӧc ÿӏnh nghƭa bӣi sӕ tài nguyên sҷn dùng và tài nguyên ÿѭӧc cҩp phát và sӕ yêu cҫu tӕi ÿa cӫa các quá trình. VII.1 Trҥng thái an toàn Mӝt trҥng thái là an toàn nӃu hӋ thӕng có thӇ cҩp phát các tài nguyên tӟi mӛi quá trình trong mӝt vài thӭ tӵ và vүn tránh deadlock. Hay nói cách khác, mӝt hӋ thӕng ӣ trong trҥng thái an toàn chӍ nӃu ӣ ÿó tӗn tҥi mӝt thӭ tӵ an toàn. Thӭ tӵ cӫa các quá trình là mӝt thӭ tӵ an toàn cho trҥng thái cҩp phát hiӋn hành nӃu ÿӕi Biên soҥn: Th.s NguyӉn Phú Trѭӡng - 09/2005 Trang 121
  10. Ĉҥi Hӑc Cҫn Thѫ - Khoa Công NghӋ Thông Tin - Giáo Trình HӋ ĈiӅu Hành – V1.0 vӟi mӛi thӭ tӵ Pi, các tài nguyên mà Pi yêu cҫu vүn có thӇ ÿѭӧc thoҧ mãn bӣi tài nguyên hiӋn có cӝng vӟi các tài nguyên ÿѭӧc giӳ bӣi tҩt cҧ Pj, vӟi j
  11. Ĉҥi Hӑc Cҫn Thѫ - Khoa Công NghӋ Thông Tin - Giáo Trình HӋ ĈiӅu Hành – V1.0 trình P0 ÿѭӧc cҩp phát 5 ә băng tӯ, nhѭng có tӕi ÿa 10, quá trình P0 phҧi chӡ. Tѭѫng tӵ, quá trình P2 có thӇ yêu cҫu thêm 6 ә băng tӯ và phҧi chӡ dүn ÿӃn deadlock. Lӛi cӫa chúng ta là gán yêu cҫu tӯ quá trình P2 cho 1 ә băng tӯ nӳa. NӃu chúng ta làm cho P2 phҧi chӡ cho ÿӃn khi các quá trình khác kӃt thúc và giҧi phóng tài nguyên cӫa nó thì chúng ta có thӇ tránh deadlock. Vӟi khái niӋm trҥng thái an toàn ÿѭӧc cho, chúng ta có thӇ ÿӏnh nghƭa các giҧi thuұt tránh deadlock. Ý tѭӣng ÿѫn giҧn là ÿҧm bҧo hӋ thӕng sӁ luôn còn trong trҥng thái an toàn. Khӣi ÿҫu, hӋ thӕng ӣ trong trҥng thái an toàn. Bҩt cӭ khi nào mӝt quá trình yêu cҫu mӝt tài nguyên hiӋn có, hӋ thӕng phҧi quyӃt ÿӏnh tài nguyên có thӇ ÿѭӧc cҩp phát tӭc thì hoһc quá trình phҧi chӡ. Yêu cҫu ÿѭӧc gán chӍ nӃu viӋc cҩp phát ÿӇ hӋ thӕng trong trҥng thái an toàn. Trong mô hình này, nӃu quá trình yêu cҫu tài nguyên ÿang có, nó có thӇ vүn phҧi chӡ. Do ÿó, viӋc sӱ dөng tài nguyên có thӇ chұm hѫn mà không có giҧi thuұt tránh deadlock. VII.2 Giҧi thuұt ÿӗ thӏ cҩp phát tài nguyên NӃu chúng ta có mӝt hӋ thӕng cҩp phát tài nguyên vӟi mӝt thӇ hiӋn cӫa mӛi loҥi, mӝt biӃn dҥng cӫa ÿӗ thӏ cҩp phát tài nguyên ÿѭӧc ÿӏnh nghƭa trong phҫn VI.4.2 có thӇ ÿѭӧc dùng ÿӇ tránh deadlock. Ngoài các cҥnh yêu cҫu và gán, chúng ta giӟi thiӋu mӝt loҥi cҥnh mӟi ÿѭӧc gӑi là c̩nh th͑nh c̯u (claim edge). Mӝt cҥnh thӍnh cҫu Pi o Rj hiӇn thӏ quá trình Pi có thӇ yêu cҫu tài nguyên Rj vào mӝt thӡi ÿiӇm trong tѭѫng lai. Cҥnh này tѭѫng tӵ cҥnh yêu cҫu vӅ phѭѫng hѭӟng nhѭng ÿѭӧc hiӋn diӋn bӣi dҩu ÿӭt khoҧng. Khi quá trình Pi yêu cҫu tài nguyên Rj, cҥnh thӍnh cҫu Pi o Rj chuyӇn tӟi cҥnh yêu cҫu. Tѭѫng tӵ, khi mӝt tài nguyên Rj ÿѭӧc giҧi phóng bӣi Pi, cҥnh gán Rj o Pi ÿѭӧc chuyӇn trӣ lҥi thành cҥnh thӍnh cҫu Pi o Rj. Chúng ta chú ý rҵng các tài nguyên phҧi ÿѭӧc yêu cҫu trѭӟc trong hӋ thӕng. Nghƭa là, trѭӟc khi Pi bҳt ÿҫu thӵc thi, tҩt cҧ các cҥnh thӍnh cҫu cӫa nó phҧi xuҩt hiӋn trong ÿӗ thӏ cҩp phát tài nguyên. Chúng ta có thӇ giҧm nhҽ ÿiӅu kiӋn này bҵng cách cho phép mӝt cҥnh Pi o Rj ÿӇ ÿѭӧc thêm tӟi ÿӗ thӏ chӍ nӃu tҩt cҧ các cҥnh gҳn liӅn vӟi quá trình Pi là các cҥnh thӍnh cҫu. Giҧ sӱ rҵng Pi yêu cҫu tài nguyên Rj. Yêu cҫu có thӇ ÿѭӧc gán chӍ nӃu chuyӇn cҥnh yêu cҫu Pi o Rj tӟi cҥnh gán RjoPi không dүn ÿӃn viӋc hình thành chu trình trong ÿӗ thӏ cҩp phát tài nguyên. Chú ý rҵng chúng ta kiӇm tra tính an toàn bҵng cách dùng giҧi thuұt phát hiӋn chu trình. Mӝt giҧi thuұt ÿӇ phát hiӋn mӝt chu trình trong ÿӗ thӏ này yêu cҫu mӝt thӭ tӵ cӫa n2 thao tác, ӣ ÿây n là sӕ quá trình trong hӋ thӕng. Hình 0-5 Ĉӗ thӏ cҩp phát tài nguyên ÿӇ tránh deadlock NӃu không có chu trình tӗn tҥi, thì viӋc cҩp phát tài nguyên sӁ ÿӇ lҥi hӋ thӕng trong trҥng thái an toàn. NӃu chu trình ÿѭӧc tìm thҩy thì viӋc cҩp phát sӁ ÿһt hӋ thӕng Biên soҥn: Th.s NguyӉn Phú Trѭӡng - 09/2005 Trang 123
  12. Ĉҥi Hӑc Cҫn Thѫ - Khoa Công NghӋ Thông Tin - Giáo Trình HӋ ĈiӅu Hành – V1.0 trong trҥng thái không an toàn. Do ÿó, quá trình Pi sӁ phҧi chӡ yêu cҫu cӫa nó ÿѭӧc thoҧ. ĈӇ minh hoҥ giҧi thuұt này, chúng ta xét ÿӗ thӏ cҩp phát tài nguyên cӫa hình VI- 5. Giҧ sӱ rҵng P2 yêu cҫu R2. Mһc dù R2 hiӋn rҧnh nhѭng chúng ta không thӇ cҩp phát nó tӟi P2 vì hoҥt ÿӝng này sӁ tҥo ra chu trình trong ÿӗ thӏ (Hình VI-6). Mӝt chu trình hiӇn thӏ rҵng hӋ thӕng ӣ trong trҥng thái không an toàn. NӃu P1 yêu cҫu R2 và P2 yêu cҫu R1 thì deadlock sӁ xҧy ra. Hình 0-6 Trҥng thái không an toàn trong ÿӗ thӏ cҩp phát tài nguyên VII.3 Giҧi thuұt cӫa Banker Giҧi thuұt ÿӗ thӏ cҩp phát tài nguyên không thӇ áp dөng tӟi hӋ thӕng cҩp phát tài nguyên vӟi nhiӅu thӇ hiӋn cӫa mӛi loҥi tài nguyên. Giҧi thuұt tránh deadlock mà chúng ta mô tҧ tiӃp theo có thӇ áp dөng tӟi mӝt hӋ thӕng nhѭng ít hiӋu quҧ hѫn cѫ chӃ ÿӗ thӏ cҩp phát tài nguyên. Giҧi thuұt này thѭӡng ÿѭӧc gӑi là giҧi thuұt cӫa Banker. Tên ÿѭӧc chӑn vì giҧi thuұt này có thӇ ÿѭӧc dùng trong hӋ thӕng ngân hàng ÿӇ ÿҧm bҧo ngân hàng không bao giӡ cҩp phát tiӅn mһt ÿang có cӫa nó khi nó không thӇ thoҧ mãn các yêu cҫu cӫa tҩt cҧ khách hàng. Khi mӝt quá trình mӟi ÿѭa vào hӋ thӕng, nó phҧi khai báo sӕ tӕi ÿa các thӇ hiӋn cӫa mӛi loҥi tài nguyên mà nó cҫn. Sӕ này có thӇ không vѭӧt quá tәng sӕ tài nguyên trong hӋ thӕng. Khi mӝt ngѭӡi dùng yêu cҫu tұp hӧp các tài nguyên, hӋ thӕng phҧi xác ÿӏnh viӋc cҩp phát cӫa các tài nguyên này sӁ ÿӇ lҥi hӋ thӕng ӣ trҥng thái an toàn hay không. NӃu trҥng thái hӋ thӕng sӁ là an toàn, tài nguyên sӁ ÿѭӧc cҩp; ngѭӧc lҥi quá trình phҧi chӡ cho tӟi khi mӝt vài quá trình giҧi phóng ÿӫ tài nguyên. NhiӅu cҩu trúc dӳ liӋu phҧi ÿѭӧc duy trì ÿӇ cài ÿһt giҧi thuұt Banker. Nhӳng cҩu trúc dӳ liӋu này mã hoá trҥng thái cӫa hӋ thӕng cҩp phát tài nguyên. Gӑi n là sӕ quá trình trong hӋ thӕng và m là sӕ loҥi tài nguyên trong hӋ thӕng. Chúng ta cҫn các cҩu trúc dӳ liӋu sau: x Available: mӝt vector có chiӅu dài m hiӇn thӏ sӕ lѭӧng tài nguyên sҷn dùng cӫa mӛi loҥi. NӃu Available[j]= k, có k thӇ hiӋn cӫa loҥi tài nguyên Rj sҷn dùng. x Max: mӝt ma trұn n x m ÿӏnh nghƭa sӕ lѭӧng tӕi ÿa yêu cҫu cӫa mӛi quá trình. NӃu Max[ i , j ] = k, thì quá trình Pi có thӇ yêu cҫu nhiӅu nhҩt k thӇ hiӋn cӫa loҥi tài nguyên Rj. x Allocation: mӝt ma trұn n x m ÿӏnh nghƭa sӕ lѭӧng tài nguyên cӫa mӛi loҥi hiӋn ÿѭӧc cҩp tӟi mӛi quá trình. NӃu Allocation[ i, j ] = k, thì quá trình Pi hiӋn ÿѭӧc cҩp k thӇ hiӋn cӫa loҥi tài nguyên Rj. Biên soҥn: Th.s NguyӉn Phú Trѭӡng - 09/2005 Trang 124
  13. Ĉҥi Hӑc Cҫn Thѫ - Khoa Công NghӋ Thông Tin - Giáo Trình HӋ ĈiӅu Hành – V1.0 x Need: mӝt ma trұn n x m hiӇn thӏ yêu cҫu tài nguyên còn lҥi cӫa mӛi quá trình. NӃu Need[ i, j ] = k, thì quá trình Pi có thӇ cҫn thêm k thӇ hiӋn cӫa loҥi tài nguyên Rj ÿӇ hoàn thành tác vө cӫa nó. Chú ý rҵng, Need[ i, j ] = Max[ i, j ] – Allocation [ i, j ]. Cҩu trúc dӳ liӋu này biӃn ÿәi theo thӡi gian vӅ kích thѭӟc và giá trӏ ĈӇ ÿѫn giҧn viӋc trình bày cӫa giҧi thuұt Banker, chúng ta thiӃt lұp vài ký hiӋu. Gӑi X và Y là các vector có chiӅu dài n. Chúng ta nói rҵng X d Y nӃu và chӍ nӃu X[i] d Y[i] cho tҩt cҧ i = 1, 2, …, n. Thí dө, nӃu X = (1, 7, 3, 2) và Y = (0, 3, 2, 1) thì Y d X, Y < X nӃu Y d X và Y z X. Chúng ta có thӇ xem xét mӛi dòng trong ma trұn Allocation và Need nhѭ là nhӳng vectors và tham chiӃu tӟi chúng nhѭ Allocationi và Needi tѭѫng ӭng. Vector Allocationi xác ÿӏnh tài nguyên hiӋn ÿѭӧc cҩp phát tӟi quá trình Pi; vector Needi xác ÿӏnh các tài nguyên bә sung mà quá trình Pi có thӇ vүn yêu cҫu ÿӇ hoàn thành tác vө cӫa nó. VII.3.1 Giҧi thuұt an toàn Giҧi thuұt ÿӇ xác ÿӏnh hӋ thӕng ӣ trҥng thái an toàn hay không có thӇ ÿѭӧc mô tҧ nhѭ sau: 1) Gӑi Work và Finish là các vector có chiӅu dài m và n tѭѫng ӭng. Khӣi tҥo Work:=Available và Finish[i]:=false cho i = 1, 2, …,n. 2) Tìm i thӓa: a) Finish[i] = false b) Need i d Work. NӃu không có i nào thӓa, di chuyӇn tӟi bѭӟc 4 3) Work:=Work + Allocation i Finish[i] := true Di chuyӇn vӅ bѭӟc 2. 4) NӃu Finish[i] = true cho tҩt cҧ i, thì hӋ thӕng ÿang ӣ trҥng thái an toàn. Giҧi thuұt này có thӇ yêu cҫu ÿӝ phӭc tҥp mxn2 thao tác ÿӇ quyӃt ÿӏnh trҥng thái là an toàn hay không. VII.3.2 Giҧi thuұt yêu cҫu tài nguyên Cho Requesti là vector yêu cҫu cho quá trình Pi. NӃu Requesti[j] = k, thì quá trình Pi muӕn k thӇ hiӋn cӫa loҥi tài nguyên Rj. Khi mӝt yêu cҫu tài nguyên ÿѭӧc thӵc hiӋn bӣi quá trình Pi, thì các hoҥt ÿӝng sau ÿѭӧc thӵc hiӋn: 1) NӃu Requesti d Needi, di chuyӇn tӟi bѭӟc 2. Ngѭӧc lҥi, phát sinh mӝt ÿiӅu kiӋn lӛi vì quá trình vѭӧt quá yêu cҫu tӕi ÿa cӫa nó. 2) NӃu Requesti d Available, di chuyӇn tӟi bѭӟc 3. Ngѭӧc lҥi, Pi phҧi chӡ vì tài nguyên không sҷn có. 3) Giҧ sӱ hӋ thӕng cҩp phát các tài nguyên ÿѭӧc yêu cҫu tӟi quá trình Pi bҵng cách thay ÿәi trҥng thái sau: Available := Available – Requesti; Allocationi := Allocationi + Requesti; Needi := Needi – Requesti; NӃu kӃt quҧ trҥng thái cҩp phát tài nguyên là an toàn, thì giao dӏch ÿѭӧc hoàn thành và quá trình Pi ÿѭӧc cҩp phát tài nguyên cӫa nó. Tuy nhiên, nӃu trҥng thái mӟi là không an toàn, thì Pi phҧi chӡ Requesti và trҥng thái cҩp phát tài nguyên cNJ ÿѭӧc phөc hӗi. Biên soҥn: Th.s NguyӉn Phú Trѭӡng - 09/2005 Trang 125
  14. Ĉҥi Hӑc Cҫn Thѫ - Khoa Công NghӋ Thông Tin - Giáo Trình HӋ ĈiӅu Hành – V1.0 VII.3.3 Thí dө minh hӑa Xét mӝt hӋ thӕng vӟi 5 quá trình tӯ P0 tӟi P4, và 3 loҥi tài nguyên A, B, C. Loҥi tài nguyên A có 10 thӇ hiӋn, loҥi tài nguyên B có 5 thӇ hiӋn và loҥi tài nguyên C có 7 thӇ hiӋn. Giҧ sӱ rҵng tҥi thӡi ÿiӇm T0 trҥng thái hiӋn tҥi cӫa hӋ thӕng nhѭ sau: Allocation Max Available A B C A B C A B C P0 0 1 0 7 5 3 3 3 2 P1 2 0 0 3 2 2 P2 3 0 2 9 0 2 P3 2 1 1 2 2 2 P4 0 0 2 4 3 3 Nӝi dung ma trұn Need ÿѭӧc ÿӏnh nghƭa là Max-Allocation và là Need A B C P0 7 4 3 P1 1 2 2 P2 6 0 2 P3 0 1 1 P4 4 3 1 Chúng ta khҷng ÿӏnh rҵng hӋ thӕng hiӋn ӣ trong trҥng thái an toàn. Thұt vұy, thӭ tӵ thӓa tiêu chuҭn an toàn. Giҧ sӱ bây giӡ P1 yêu cҫu thêm mӝt thӇ hiӋn loҥi A và hai thӇ hiӋn loҥi C, vì thӃ Request1 = (1, 0, 2). ĈӇ quyӃt ÿӏnh yêu cҫu này có thӇ ÿѭӧc cҩp tӭc thì hay không, trѭӟc tiên chúng ta phҧi kiӇm tra Request1 d Available (nghƭa là, (1, 0, 2)) d (3, 3, 2)) là ÿúng hay không. Sau ÿó, chúng ta giҧ sӱ yêu cҫu này ÿҥt ÿѭӧc và chúng ta ÿi ÿӃn trҥng thái mӟi sau: Allocation Max Available A B C A B C A B C P0 0 1 0 7 4 3 2 3 0 P1 3 0 2 0 2 0 P2 3 0 2 6 0 0 P3 2 1 1 0 1 1 P4 0 0 2 4 3 1 Chúng ta phҧi xác ÿӏnh trҥng thái mӟi này là an toàn hay không. ĈӇ thӵc hiӋn ÿiӅu này, chúng ta thӵc thi giҧi thuұt an toàn cӫa chúng ta và tìm thӭ tӵ thӓa yêu cҫu an toàn. Do ÿó, chúng ta có thӇ cҩp lұp tӭc yêu cҫu cӫa quá trình P1. Tuy nhiên, chúng ta cNJng thҩy rҵng, khi hӋ thӕng ӣ trong trҥng thái này, mӝt yêu cҫu (3, 3, 0) bӣi P4 không thӇ ÿѭӧc gán vì các tài nguyên là không sҷn dùng. Mӝt yêu cҫu cho (0, 2, 0) bӣi P0 không thӇ ÿѭӧc cҩp mһc dù tài nguyên là sҷn dùng vì trҥng thái kӃt quҧ là không an toàn. Biên soҥn: Th.s NguyӉn Phú Trѭӡng - 09/2005 Trang 126
  15. Ĉҥi Hӑc Cҫn Thѫ - Khoa Công NghӋ Thông Tin - Giáo Trình HӋ ĈiӅu Hành – V1.0 VIII Phát hiӋn Deadlock NӃu mӝt hӋ thӕng không thӵc hiӋn giҧi thuұt ngăn chһn deadlock hay tránh deadlock thì trѭӡng hӧp deadlock có thӇ xҧy ra. Trong môi trѭӡng này, hӋ thӕng phҧi cung cҩp: x Giҧi thuұt xem xét trҥng thái cӫa hӋ thӕng ÿӇ quyӃt ÿӏnh deadlock có xҧy ra hay không. x Giҧi thuұt phөc hӗi tӯ deadlock Trong thҧo luұn dѭӟi ÿây, chúng ta thҧo luұn chi tiӃt vӅ hai yêu cҫu khi chúng liên quan ÿӃn nhӳng hӋ thӕng vӟi chӍ mӝt thӇ hiӋn cӫa mӛi loҥi tài nguyên cNJng nhѭ ÿӕi vӟi hӋ thӕng có nhiӅu thӇ hiӋn cho mӛi loҥi tài nguyên. Tuy nhiên, tҥi thӡi ÿiӇm này chúng ta chú ý lѭӧc ÿӗ phát hiӋn và phөc hӗi yêu cҫu chi phí bao gӗm không chӍ chi phí tҥi thӡi ÿiӇm thӵc thi cho viӋc duy trì thông tin cҫn thiӃt và thӵc thi giҧi thuұt phát hiӋn mà còn các lãng phí có thӇ phát sinh trong viӋc phát hiӋn tӯ deadlock. VIII.1 Mӝt thӇ hiӋn cӫa mӛi loҥi tài nguyên NӃu tҩt cҧ tài nguyên chӍ có mӝt thӇ hiӋn thì chúng ta có thӇ ÿӏnh nghƭa giҧi thuұt phát hiӋn deadlock dùng mӝt biӃn dҥng cӫa ÿӗ thӏ cҩp phát tài nguyên, ÿѭӧc gӑi là ÿӗ thӏ chӡ (wait-for). Chúng ta ÿҥt ÿѭӧc ÿӗ thӏ này tӯ ÿӗ thӏ cҩp phát tài nguyên bҵng cách gӥ bӓ các nút cӫa loҥi tài nguyên và xóa các cҥnh tѭѫng ӭng. Hình 0-7 a) Ĉӗ thӏ cҩp phát tài nguyên. b) Ĉӗ thӏ chӡ tѭѫng ӭng Chính xác hѫn, mӝt cҥnh tӯ Pi tӟi Pj trong ÿӗ thӏ chӡ hiӇn thӏ rҵng quá trình Pi ÿang chӡ mӝt quá trình Pj ÿӇ giҧi phóng tài nguyên mà Pi cҫn. Cҥnh Pi o Pj tӗn tҥi trong ÿӗ thӏ chӡ nӃu và chӍ nӃu ÿӗ thӏ cҩp phát tài nguyên tѭѫng ӭng chӭa hai cҥnh Pi o Rq và Rq o Pj ÿӕi vӟi mӝt sӕ tài nguyên Rq. Thí dө, trong hình VI-7 dѭӟi ÿây, chúng ta trình bày ÿӗ thӏ cҩp phát tài nguyên và ÿӗ thӏ chӡ tѭѫng ӭng. Nhѭ ÿã ÿӅ cұp trѭӟc ÿó, deadlock tӗn tҥi trong hӋ thӕng nӃu và chӍ nӃu ÿӗ thӏ chӡ chӭa chu trình. ĈӇ phát hiӋn deadlock, hӋ thӕng cҫn duy trì ÿӗ thӏ chӡ và ÿӏnh kǤ gӑi giҧi thuұt ÿӇ tìm kiӃm chu trình trong ÿӗ thӏ. Mӝt giҧi thuұt phát hiӋn chu trình trong ÿӗ thӏ yêu cҫu ÿӝ phӭc tҥp n2 thao tác, ӣ ÿây n là sӕ cҥnh cӫa ÿӗ thӏ. Biên soҥn: Th.s NguyӉn Phú Trѭӡng - 09/2005 Trang 127
  16. Ĉҥi Hӑc Cҫn Thѫ - Khoa Công NghӋ Thông Tin - Giáo Trình HӋ ĈiӅu Hành – V1.0 VIII.2 NhiӅu thӇ hiӋn cӫa mӝt loҥi tài nguyên Lѭӧc ÿӗ ÿӗ thӏ chӡ không thӇ áp dөng ÿӕi vӟi hӋ thӕng cҩp phát tài nguyên vӟi nhiӅu thӇ hiӋn cho mӛi loҥi tài nguyên. Giҧi thuұt phát hiӋn deadlock mà chúng ta mô tҧ sau ÿây có thӇ áp dөng cho hӋ thӕng này. Giҧi thuұt thӵc hiӋn nhiӅu cҩu trúc dӳ liӋu thay ÿәi theo thӡi gian mà chúng tѭѫng tӵ nhѭ ÿѭӧc dùng trong giҧi thuұt Banker. x Available: mӝt vector có chiӅu dài m hiӇn thӏ sӕ lѭӧng tài nguyên sҷn có cӫa mӛi loҥi. x Allocation: ma trұn nxm ÿӏnh nghƭa sӕ lѭӧng tài nguyên cӫa mӛi loҥi hiӋn ÿѭӧc cҩp phát tӟi mӛi quá trình. x Request: ma trұn nxm hiӇn thӏ yêu cҫu hiӋn tҥi cӫa mӛi quá trình. NӃu Request[i,j] = k, thì quá trình Pi ÿang yêu cҫu k thӇ hiӋn nӳa cӫa loҥi tài nguyên Rj. Quan hӋ d giӳa hai vectors ÿѭӧc ÿӏnh nghƭa trong phҫn VI.7.3. ĈӇ ký hiӋu ÿѫn giҧn, chúng ta sӁ xem nhӳng hàng trong ma trұn Allocation và Request nhѭ các vector, và sӁ tham chiӃu chúng nhѭ Allocationi và Requesti tѭѫng ӭng. Giҧi thuұt phát hiӋn ÿѭӧc mô tҧ ӣ ÿây ÿѫn giҧn khҧo sát mӑi thӭ tӵ cҩp phát có thӇ ÿӕi vӟi các quá trình còn lҥi ÿӇ ÿѭӧc hoàn thành. So sánh giҧi thuұt này vӟi giҧi thuұt Banker. 1) Gӑi Work và Finish là các vector có chiӅu dài m và n tѭѫng ӭng. Khӣi tҥo Work:=Available. Cho i = 1, 2, …,n, nӃu Allocationi  0, thì Finish[i]:= false; ngѭӧc lҥi Finish[i]:= true. 2) Tìm chӍ sӕ i thӓa: a) Finish[i] = false b) Request i d Work. NӃu không có i nào thӓa, di chuyӇn tӟi bѭӟc 4 3) Work:=Work + Allocation i Finish[i] := true Di chuyӇn vӅ bѭӟc 2. 4) NӃu Finish[i] = false cho mӝt vài i, 1 d i d n thì hӋ thӕng ÿang ӣ trҥng thái deadlock. Ngoài ra, nӃu Finish[i] = false thì quá trình Pi bӏ deadlock. Giҧi thuұt này yêu cҫu ÿӝ phӭc tҥp mxn2 ÿӇ phát hiӋn hӋ thӕng có ӣ trong trҥng thái deadlock hay không. Câu hӓi ÿһt ra là tҥi sao chúng ta trҧ lҥi tài nguyên cӫa quá trình Pi (trong bѭӟc 3) ngay sau khi chúng ta xác ÿӏnh rҵng Requesti d Work (trong bѭӟc 2b). Chúng ta biӃt rҵng Pi hiӋn tҥi không liên quan deadlock (vì Requesti d Work). Do ÿó, chúng ta lҥc quan và khҷng ÿӏnh rҵng Pi sӁ không yêu cҫu thêm tài nguyên nӳa ÿӇ hoàn thành công viӋc cӫa nó; do ÿó nó sӁ trҧ vӅ tҩt cҧ tài nguyên hiӋn ÿѭӧc cҩp phát tӟi hӋ thӕng. NӃu giҧ ÿӏnh cӫa chúng ta không ÿúng, deadlock có thӇ xҧy ra sao ÿó. Deadlock sӁ ÿѭӧc phát hiӋn tҥi thӡi ÿiӇm kӃ tiӃp mà giҧi thuұt phát hiӋn deadlock ÿѭӧc nҥp. ĈӇ minh hoҥ giҧi thuұt này, chúng ta xét hӋ thӕng vӟi 5 quá trình P0 ÿӃn P4 và 3 loҥi tài nguyên A, B, C. Loҥi tài nguyên A có 7 thӇ hiӋn, loҥi tài nguyên B có 2 thӇ hiӋn và loҥi tài nguyên C có 6 thӇ hiӋn. Giҧ sӱ rҵng tҥi thӡi ÿiӇm T0, chúng ta có trҥng thái cҩp phát tài nguyên sau: 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 Biên soҥn: Th.s NguyӉn Phú Trѭӡng - 09/2005 Trang 128
  17. Ĉҥi Hӑc Cҫn Thѫ - Khoa Công NghӋ Thông Tin - Giáo Trình HӋ ĈiӅu Hành – V1.0 P4 0 0 2 0 0 2 Chúng ta khҷng ÿӏnh rҵng hӋ thӕng không ӣ trong trҥng thái deadlock. Thұt vұy, nӃu chúng ta thӵc thi giҧi thuұt, chúng ta sӁ tìm ra thӭ tӵ sӁ dүn ÿӃn trong Finish[i] = true cho tҩt cҧ i. Bây giӡ giҧ sӱ rҵng quá trình P2 thӵc hiӋn yêu cҫu thêm thӇ hiӋn loҥi C. Ma trұn yêu cҫu ÿѭӧc hiӋu chӍnh nhѭ sau: Need A B C P0 0 0 0 P1 2 0 2 P2 0 0 1 P3 1 0 0 P4 0 0 2 Chúng ta khҷng ÿӏnh rҵng hӋ thӕng bây giӡ bӏ deadlock. Mһc dù chúng ta có thӇ ÿòi lҥi tài nguyên ÿѭӧc giӳ bӣi quá trình P0, sӕ lѭӧng tài nguyên sҷn dùng không ÿӫ ÿӇ hoàn thành các yêu cҫu cӫa các quá trình còn lҥi. Do ÿó, deadlock tӗn tҥi và bao gӗm các quá trình P1, P2, P3, P4. VIII.3 Sӱ dөng giҧi thuұt phát hiӋn deadlock Khi nào thì chúng ta nên nҥp giҧi thuұt phát hiӋn deadlock? Câu trҧ lӡi phө thuӝc vào hai yӃu tӕ: 1) Deadlock có khҧ năng xҧy ra thѭӡng xuyên nhѭ thӃ nào? 2) Bao nhiêu quá trình sӁ bӏ ҧnh hѭӣng bӣi deadlock khi nó sӁ ra? NӃu deadlock xҧy ra thѭӡng xuyên thì giҧi thuұt phát hiӋn nên ÿѭӧc nҥp lên thѭӡng xuyên. Nhӳng tài nguyên ÿѭӧc cҩp phát ÿӇ các quá trình bӏ deadlock sӁ rҧnh cho ÿӃn khi deadlock có thӇ bӏ phá vӥ. Ngoài ra, sӕ lѭӧng quá trình liên quan trong chu trình deadlock có thӇ tăng lên. Deadlock xҧy ra chӍ khi mӝt sӕ quá trình thӵc hiӋn yêu cҫu mà không ÿѭӧc cҩp tài nguyên tӭc thì. Yêu cҫu này có thӇ là yêu cҫu cuӕi hoàn thành mӝt chuӛi các quá trình ÿang yêu cҫu. Ngoài ra, chúng ta có thӇ nҥp giҧi thuұt phát hiӋn mӑi khi mӝt yêu cҫu cho viӋc cҩp phát không thӇ ÿѭӧc cҩp tӭc thì. Trong trѭӡng hӧp này, chúng ta không chӍ ÿӏnh nghƭa tұp hӧp các quá trình bӏ deadlock, mà còn xác ÿӏnh quá trình ÿã gây ra deadlock. (Trong thӵc tӃ, mӛi quá trình trong suӕt quá trình bӏ deadlock là mӝt liên kӃt trong chu trình cӫa ÿӗ thӏ tài nguyên, vì thӃ tҩt cҧ chúng gây ra deadlock). NӃu có nhiӅu loҥi tài nguyên khác nhau, mӝt yêu cҫu có thӇ gây chu trình trong ÿӗ thӏ tài nguyên, mӛi chu trình hoàn thành bӣi yêu cҫu mӟi nhҩt và “ÿѭӧc gây ra” bӣi mӝt quá trình có thӇ xác ÿӏnh. Dƭ nhiên, nҥp giҧi thuұt phát hiӋn deadlock cho mӛi yêu cҫu có thӇ gây ra mӝt chi phí có thӇ xem xét trong thӡi gian tính toán. Mӝt thay ÿәi ít ÿҳt hѫn là nҥp giҧi thuұt tҥi thӡi ÿiӇm ít thѭӡng xuyên hѫn- thí dө, mӝt lҫn mӝt giӡ hay bҩt cӭ khi nào viӋc sӱ dөng CPU rѫi xuӕng thҩp hѫn 40%. NӃu giҧi thuұt phát hiӋn deadlock ÿѭӧc nҥp trong nhӳng thӡi ÿiӇm bҩt kǤ, thì có nhiӅu chu trình trong ÿӗ thӏ tài nguyên. Chúng ta không thӇ nói quá trình nào cӫa nhiӅu quá trình bӏ deadlock gây ra deadlock. Biên soҥn: Th.s NguyӉn Phú Trѭӡng - 09/2005 Trang 129
  18. Ĉҥi Hӑc Cҫn Thѫ - Khoa Công NghӋ Thông Tin - Giáo Trình HӋ ĈiӅu Hành – V1.0 IX Phөc hӗi deadlock Khi giҧi thuұt phát hiӋn xác ÿӏnh rҵng deadlock tӗn tҥi, nhiӅu thay ÿәi tӗn tҥi. Mӝt khҧ năng là thông báo ngѭӡi ÿiӅu hành rҵng deadlock xҧy ra và ÿӇ ngѭӡi ÿiӅu hành giҧi quyӃt deadlock bҵng thӫ công. Mӝt khҧ năng khác là ÿӇ hӋ thӕng tӵ ÿӝng phөc hӗi. Có hai tuǤ chӑn cho viӋc phá vӥ deadlock. Mӝt giҧi pháp ÿѫn giҧn là huӹ bӓ mӝt hay nhiӅu quá trình ÿӇ phá vӥ viӋc tӗn tҥi chu trình trong ÿӗ thӏ cҩp phát tài nguyên. TuǤ chӑn thӭ hai là lҩy lҥi mӝt sӕ tài nguyên tӯ mӝt hay nhiӅu quá trình bӏ deadlock. IX.1 KӃt thúc quá trình ĈӇ xóa deadlock bҵng cách hӫy bӓ quá trình, chúng ta dùng mӝt trong hai phѭѫng pháp. Trong cҧ hai phѭѫng pháp, hӋ thӕng lҩy lҥi tài nguyên ÿѭӧc cҩp phát ÿӕi vӟi quá trình bӏ kӃt thúc. x Huӹ bӓ tҩt cҧ quá trình bӏ deadlock: phѭѫng pháp này rõ ràng sӁ phá vӥ chu trình deadlock, nhѭng chi phí cao; các quá trình này có thӇ ÿã tính toán trong thӡi gian dài, và các kӃt quҧ cӫa các tính toán tӯng phҫn này phҧi bӏ bӓ ÿi và có thӇ phҧi tính lҥi sau ÿó. x Hӫy bӓ mӝt quá trình tҥi thӡi ÿiӇm cho ÿӃn khi chu trình deadlock bӏ xóa:phѭѫng pháp này chӏu chi phí có thӇ xem xét vì sau khi mӛi quá trình bӏ hӫy bӓ, mӝt giҧi thuұt phát hiӋn deadlock phҧi ÿѭӧc nҥp lên ÿӇ xác ÿӏnh có quá trình nào vүn ÿang bӏ deadlock. Hӫy bӓ quá trình có thӇ không dӉ. NӃu mӝt quá trình ÿang ӣ giӳa giai ÿoҥn cұp nhұt mӝt tұp tin, kӃt thúc nó sӁ ÿӇ tұp tin ÿó trong trҥng thái không phù hӧp. Tѭѫng tӵ, nӃu quá trình ÿang ӣ giӳa giai ÿoҥn in dӳ liӋu ra máy in, hӋ thӕng phҧi khӣi ÿӝng lҥi trҥng thái ÿúng trѭӟc khi in công viӋc tiӃp theo. NӃu phѭѫng pháp kӃt thúc mӝt phҫn ÿѭӧc dùng thì vӟi mӝt tұp hӧp các quá trình deadlock ÿѭӧc cho, chúng ta phҧi xác ÿӏnh quá trình nào (hay các quá trình nào) nên ÿѭӧc kӃt thúc trong sӵ cӕ gҳng ÿӇ phá vӥ deadlock. ViӋc xác ÿӏnh này là mӝt quyӃt ÿӏnh chính sách tѭѫng tӵ nhѭ các vҩn ÿӅ lұp thӡi biӇu CPU. Câu hӓi vӅ tính kinh tӃ là chúng ta nên hӫy bӓ quá trình nào thì sӵ kӃt thúc cӫa quá trình ÿó sӁ chӏu chi phí tӕi thiӇu. Tuy nhiên, thuұt ngӳ chi phí tӕi thiӇu là không chính xác. NhiӅu yӃu tӕ có thӇ xác ÿӏnh quá trình nào ÿѭӧc chӑn bao gӗm: 1) Ĉӝ ѭu tiên cӫa quá trình là gì. 2) Quá trình ÿã ÿѭӧc tính toán bao lâu và bao lâu nӳa quá trình sӁ tính toán trѭӟc khi hoàn thành tác vө ÿѭӧc chӍ ÿӏnh cӫa nó. 3) Bao nhiêu và loҥi tài nguyên gì quá trình ÿang sӱ dөng. 4) Bao nhiêu tài nguyên nӳa quá trình cҫn ÿӇ hoàn thành 5) Bao nhiêu quá trình sӁ cҫn ÿѭӧc kӃt thúc. 6) Quá trình là giao tiӃp hay dҥng bó Biên soҥn: Th.s NguyӉn Phú Trѭӡng - 09/2005 Trang 130
  19. Ĉҥi Hӑc Cҫn Thѫ - Khoa Công NghӋ Thông Tin - Giáo Trình HӋ ĈiӅu Hành – V1.0 IX.2 Lҩy lҥi tài nguyên ĈӇ xóa deadlock sӱ dөng viӋc trҧ lҥi tài nguyên, sau khi chúng ta ÿòi mӝt sӕ tài nguyên tӯ các quá trình và cho các tài nguyên này tӟi các quá trình khác cho ÿӃn khi chu trình deadlock bӏ phá vӥ. NӃu viӋc ÿòi lҥi ÿѭӧc yêu cҫu ÿӇ giҧi quyӃt deadlock thì ba vҩn ÿӅ cҫn ÿѭӧc xác ÿӏnh: x Chӑn nҥn nhân: nhӳng tài nguyên nào và nhӳng quá trình nào bӏ ÿòi lҥi? Trong khi kӃt thúc quá trình, chúng ta phҧi xác ÿӏnh thӭ tӵ ÿòi lҥi ÿӇ tӕi thiӇu chi phí. Các yӃu tӕ chi phí có thӇ gӗm các tham sӕ nhѭ sӕ lѭӧng tài nguyên mӝt quá trình deadlock ÿang giӳ, và lѭӧng thӡi gian mӝt quá trình deadlock dùng trong sӵ thӵc thi cӫa nó. x Trӣ lҥi trҥng thái trѭӟc deadlock: NӃu chúng ta ÿòi lҥi tài nguyên tӯ mӝt quá trình, ÿiӅu gì nên ÿѭӧc thӵc hiӋn vӟi quá trình ÿó? Rõ ràng, nó không thӇ tiӃp tөc viӋc thӵc thi bình thѭӡng; nó ÿang bӏ mҩt mӝt sӕ tài nguyên ÿѭӧc yêu cҫu. Chúng ta phҧi phөc hӗi quá trình tӟi trҥng thái an toàn và khӣi ÿӝng lҥi tӯ trҥng thái gҫn nhҩt trѭӟc ÿó. Thông thѭӡng, rҩt khó ÿӇ xác ÿӏnh trҥng thái gì là an toàn vì thӃ giҧi pháp ÿѫn giҧn nhҩt là phөc hӗi toàn bӝ: hӫy quá trình và sau ÿó khӣi ÿӝng lҥi nó. Tuy nhiên, hӳu hiӋu hѫn ÿӇ phөc hӗi quá trình chӍ ÿӫ xa cҫn thiӃt ÿӇ phá vӥ deadlock. Ngoài ra, phѭѫng pháp này yêu cҫu hӋ thӕng giӳ nhiӅu thông tin hѫn vӅ trҥng thái cӫa tҩt cҧ các quá trình ÿang chҥy. Ĉói tài nguyên: chúng ta ÿҧm bҧo nhѭ thӃ nào viӋc ÿói tài nguyên không xҧy ra? Nghƭa là, chúng ta có thӇ ÿҧm bҧo rҵng tài nguyên sӁ không luôn bӏ ÿòi lҥi tӯ cùng mӝt quá trình. Trong mӝt hӋ thӕng viӋc chӑn nҥn nhân ӣ ÿâu dӵa trên cѫ sӣ các yӃu tӕ chi phí, nó có thӇ xҧy ra cùng quá trình luôn ÿѭӧc chӑn nhѭ là nҥn nhân. Do ÿó, quá trình này không bao giӡ hoàn thành tác vө ÿѭӧc chӍ ÿӏnh cӫa nó, mӝt trѭӡng hӧp ÿói tài nguyên cҫn ÿѭӧc giҧi quyӃt trong bҩt kǤ hӋ thӕng thӵc tӃ. Rõ ràng, chúng ta phҧi ÿҧm bҧo mӝt quá trình có thӇ ÿѭӧc chӑn nhѭ mӝt nҥn nhân chӍ mӝt sӕ lҫn xác ÿӏnh (nhӓ). Giҧi pháp chung nhҩt là bao gӗm sӕ lѭӧng phөc hӗi trong yӃu tӕ chi phí. X Tóm tҳt Trҥng thái deadlock xҧy ra khi hai hay nhiӅu quá trình ÿang chӡ không xác ÿӏnh mӝt sӵ kiӋn mà có thӇ ÿѭӧc gây ra chӍ bӣi mӝt trong nhӳng quá trình ÿang chӡ. VӅ nguyên tҳc, có ba phѭѫng pháp giҧi quyӃt deadlock: x Sӱ dөng mӝt sӕ giao thӭc ÿӇ ngăn chһn hay tránh deadlock, ÿҧm bҧo rҵng hӋ thӕng sӁ không bao giӡ ÿi vào trҥng thái deadlock. x Cho phép hӋ thӕng ÿi vào trҥng thái deadlock, phát hiӋn và sau ÿó phөc hӗi. x Bӓ qua vҩn ÿӅ deadlock và giҧ vӡ deadlock chѭa bao giӡ xҧy ra trong hӋ thӕng. Giҧi pháp này là mӝt giҧi pháp ÿѭӧc dùng bӣi hҫu hӃt các hӋ ÿiӅu hành bao gӗm UNIX. Trѭӡng hӧp deadlock có thӇ xҧy ra nӃu và chӍ nӃu bӕn ÿiӅu kiӋn cҫn xҧy ra cùng mӝt lúc trong hӋ thӕng: loҥi trӯ hӛ tѭѫng, giӳ và chӡ cҩp thêm tài nguyên, không ÿòi lҥi tài nguyên, và tӗn tҥi chu trình trong ÿӗ thӏ cҩp phát tài nguyên. ĈӇ ngăn chһn deadlock, chúng ta ÿҧm bҧo rҵng ít nhҩt mӝt ÿiӅu kiӋn cҫn không bao giӡ xҧy ra. Mӝt phѭѫng pháp ÿӇ tránh deadlock mà ít nghiêm ngһt hѫn giҧi thuұt ngăn chһn deadlock là có thông tin trѭӟc vӅ mӛi quá trình sӁ ÿang dùng tài nguyên nhѭ thӃ nào. Thí dө, giҧi thuұt Banker cҫn biӃt sӕ lѭӧng tӕi ÿa cӫa mӛi lӟp tài nguyên có thӇ ÿѭӧc Biên soҥn: Th.s NguyӉn Phú Trѭӡng - 09/2005 Trang 131
  20. Ĉҥi Hӑc Cҫn Thѫ - Khoa Công NghӋ Thông Tin - Giáo Trình HӋ ĈiӅu Hành – V1.0 yêu cҫu bӣi mӛi quá trình. Sӱ dөng thông tin này chúng ta có thӇ ÿӏnh nghƭa giҧi thuұt tránh deadlock. NӃu hӋ thӕng không thӵc hiӋn mӝt giao thӭc ÿӇ ÿҧm bҧo rҵng deadlock sӁ không bao giӡ xҧy ra thì lѭӧc ÿӗ phát hiӋn và phөc hӗi phҧi ÿѭӧc thӵc hiӋn. Giҧi thuұt phát hiӋn deadlock phҧi ÿѭӧc nҥp lên ÿӇ xác ÿӏnh deadlock có thӇ xҧy ra hay không. NӃu deadlock ÿѭӧc phát hiӋn hӋ thӕng phҧi phөc hӗi bҵng cách kӃt thúc mӝt sӕ quá trình bӏ deadlock hay ÿòi lҥi tài nguyên tӯ mӝt sӕ quá trình bӏ deadlock. Trong mӝt hӋ thӕng mà nó chӑn các nҥn nhân ÿӇ phөv hӗi vӅ trҥng thái trѭӟc ÿó chӫ yӃu dӵa trên cѫ sӣ yӃu tӕ chi phí, viӋc ÿói tài nguyên có thӇ xҧy ra. KӃt quҧ là quá trình ÿѭӧc chӑn không bao giӡ hoàn thành tác vө ÿѭӧc chӍ ÿӏnh cӫa nó. Biên soҥn: Th.s NguyӉn Phú Trѭӡng - 09/2005 Trang 132
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2