Đề cương môn học Hệ điều hành - Nguyễn Phú Trường (Phần 2)

125 trang hapham 800

Download

Bạn đang xem 20 trang mẫu của tài liệu "Đề cương môn học Hệ điều hành - Nguyễn Phú Trường (Phần 2)", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

de_cuong_mon_hoc_he_dieu_hanh_nguyen_phu_truong_phan_2.pdf

Nội dung text: Đề cương môn học Hệ điều hành - Nguyễn Phú Trường (Phần 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 DEADLOCK IMө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
Ĉҥ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 cǊng 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
Ĉҥ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 cǊng 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
Ĉҥ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
Ĉҥ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 cǊng 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
Ĉҥ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à cǊng 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
Ĉҥ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
Ĉҥ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 cǊ cӫa nó cǊng 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à cǊng 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
Ĉҥ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) 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
Ĉҥ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 thoҧÿiӅu kiӋn an toàn vì quá trình P1 có thӇÿѭӧc cҩp phát tӭc thì tҩt cҧ các әÿƭa tӯ và sau ÿó trҧ lҥi chúng (sau ÿó hӋ thӕng có 5 ә băng tӯ sҷn dùng ), sau ÿó quá trình P0 có thӇ nhұn tҩt cҧә băng tӯ và trҧ lҥi chúng (sau ÿó hӋ thӕng sӁ có 10 ә băng tӯ sҷn dùng), và cuӕi cùng quá trình P2 có thӇ nhұn tҩt cҧә băng tӯ cӫa nó và trҧ lҥi chúng (sau ÿó hӋ thӕng sӁ có tҩt cҧ 12 ә băng tӯ sҷn dùng). Mӝt hӋ thӕng có thӇÿi tӯ trҥng thái an toàn tӟi mӝt trҥng thái không an toàn. Giҧ sӱ rҵng tҥi thӡi ÿiӇm t1, quá trình P2 yêu cҫu và ÿѭӧc cҩp 1 ә băng tӯ nӳa. HӋ thӕng không còn trong trҥng thái an toàn. Tҥi ÿiӇm này, chӍ quá trình P1 có thӇÿѭӧc cҩp tҩt cҧә băng tӯ cӫa nó. Khi nó trҧ lҥi chúng, chӍ quá trình P1 có thӇÿѭӧc cҩp phát tҩt cҧә băng tӯ. Khi nó trҧ lҥi chúng, hӋ thӕng chӍ còn 4 ә băng tӯ sҷn có. Vì quá Biên soҥn: Th.s NguyӉn Phú Trѭӡng - 09/2005 Trang 122
Ĉҥ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
Ĉҥ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
Ĉҥ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 cǊÿѭӧc phөc hӗi. Biên soҥn: Th.s NguyӉn Phú Trѭӡng - 09/2005 Trang 125
Ĉҥ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 ABCABCABC P0 010753332 P1 200322 P2 302902 P3 211222 P4 002433 Nӝi dung ma trұn Need ÿѭӧc ÿӏnh nghƭa là Max-Allocation và là Need ABC P0 743 P1 122 P2 602 P3 011 P4 431 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 ABCABCABC P0 010743230 P1 302020 P2 302600 P3 211011 P4 002431 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 cǊng 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
Ĉҥi Hӑc Cҫn Thѫ - Khoa Công NghӋ Thông Tin - Giáo Trình HӋĈiӅu Hành – V1.0 VIIIPhá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 cǊng 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
Ĉҥ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 ABCABCABC P0 010000000 P1 200202 P2 303000 P3 211100 Biên soҥn: Th.s NguyӉn Phú Trѭӡng - 09/2005 Trang 128
Ĉҥ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 002002 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 ABC P0 000 P1 202 P2 001 P3 100 P4 002 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
Ĉҥ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
Ĉҥ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
Ĉҥ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
Ĉҥi Hӑc Cҫn Thѫ - Khoa Công NghӋ Thông Tin - Giáo Trình HӋĈiӅu Hành – V1.0 QUҦN LÝ BӜ NHӞ IMө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 các cách khác nhau ÿӇ quҧn lý bӝ nhӟ x HiӇu tiӃp cұn quҧn lý bӝ phân trang và phân ÿoҥn x Vұn dөng mӝt tiӃp cұn quҧn lý bӝ nhӟ phù hӧp vӟi hӋ thӕng xác ÿӏnh II Giӟi thiӋu Trong chѭѫng này chúng ta sӁ thҧo luұn nhiӅu cách khác nhau ÿӇ quҧn lý bӝ nhӟ. Các giҧi thuұt quҧn lý bӝ nhӟ tӯ tiӃp cұn máy trѫ cѫ bҧn (primitive bare- machine) là chiӃn lѭӧc phân trang và phân ÿoҥn. Mӛi tiӃp cұn có lӧi ÿiӇm và nhѭӧc cӫa chính nó. Chӑn phѭѫng pháp quҧn lý bӝ nhӟ cho mӝt hӋ thӕng xác ÿӏnh phө thuӝc vào nhiӅu yӃu tӕ, ÿһc biӋt trên thiӃt kӃ phҫn cӭng cӫa hӋ thӕng. Chúng ta sӁ thҩy nhiӅu giҧi thuұt yêu cҫu hӛ trӧ phҫn cӭng mһc dù các thiӃt kӃ gҫn ÿây ÿã tích hӧp phҫn cӭng và hӋÿiӅu hành. III Ĉһt vҩn ÿӅ Bӝ nhӟ là trung tâm ÿӇ ÿiӅu hành hӋ thӕng máy tính hiӋn ÿҥi. Bӝ nhӟ chӭa mӝt mҧng lӟn các tӯ (words) hay các bytes, mӛi phҫn tӱ vӟi ÿӏa chӍ cӫa chính nó. CPU lҩy các chӍ thӏ tӯ bӝ nhӟ dӵa theo giá trӏ cӫa thanh ÿӃm chѭѫng trình. Các chӍ thӏ này có thӇ gây viӋc nҥp bә sung các tӯ và lѭu trӳ tӟi các ÿӏa chӍ bӝ nhӟ xác ÿӏnh. III.1 Liên kӃt ÿӏa chӍ Thông thѭӡng, mӝt chѭѫng trình nҵm trên ÿƭa nhѭ mӝt tұp tin có thӇ thӵc thi dҥng nhӏ phân. Chѭѫng trình này ÿѭӧc mang vào trong bӝ nhӟ và ÿѭӧc ÿһt trong mӝt quá trình ÿӇ nó ÿѭӧc thӵc thi. Phө thuӝc vào viӋc quҧn lý bӝ nhӟÿang dùng, quá trình có thӇÿѭӧc di chuyӇn giӳa ÿƭa và bӝ nhӟ trong khi thӵc thi. Tұp hӧp các quá trình trên ÿƭa ÿang chӡÿѭӧc mang vào bӝ nhӟÿӇ thӵc thi hình thành mӝt hàng ÿӧi nhұp (input queue). Thӫ tөc thông thѭӡng là chӑn mӝt trong nhӳng quá trình trong hàng ÿӧi nhұp và nҥp quá trình ÿó vào trong bӝ nhӟ. Khi mӝt quá trình ÿѭӧc thӵc thi, nó truy xuҩt các chӍ thӏ và dӳ liӋu tӯ bӝ nhӟ. Cuӕi cùng, mӝt quá trình kӃt thúc và không gian bӝ nhӟ cӫa nó ÿѭӧc xác ÿӏnh là trӕng. Hҫu hӃt các hӋ thӕng cho phép mӝt quá trình ngѭӡi dùng nҵm ӣ bҩt cӭ phҫn nào cӫa bӝ nhӟ vұt lý. Do ÿó, mһc dù không gian ÿӏa chӍ cӫa máy tính bҳt ÿҫu tҥi 00000, nhѭng ÿӏa chӍÿҫu tiên cӫa quá trình ngѭӡi dùng không cҫn tҥi 00000. Sҳp xӃp này ҧnh hѭӣng ÿӃn ÿӏa chӍ mà chѭѫng trình ngѭӡi dùng có thӇ dùng. Trong hҫu hӃt các trѭӡng hӧp, mӝt chѭѫng trình ngѭӡi dùng sӁÿi qua mӝt sӕ bѭӟc- mӝt vài trong chúng có thӇ là tuǤ chӑn-trѭӟc khi ÿѭӧc thӵc thi (hình VII-1). Các ÿӏa chӍ có thӇÿѭӧc hiӋn diӋn trong nhӳng cách khác trong nhӳng bѭӟc này. Các ÿӏa chӍ trong chѭѫng trình nguӗn thѭӡng là nhӳng danh biӇu. Mӝt trình biên dӏch sӁ liên kӃt các ÿӏa chӍ danh biӇu tӟi các ÿӏa chӍ có thӇ tái ÿӏnh vӏ (chҷng hҥn nhѭ 14 bytes tӯ vӏ trí bҳt ÿҫu cӫa Biên soҥn: Th.s NguyӉn Phú Trѭӡng - 09/2005 Trang 137
Ĉҥi Hӑc Cҫn Thѫ - Khoa Công NghӋ Thông Tin - Giáo Trình HӋĈiӅu Hành – V1.0 module này). Bӝ soҥn thҧo liên kӃt hay bӝ nҥp sӁ liên kӃt các ÿӏa chӍ có thӇ tái ÿӏnh vӏ tӟi ÿӏa chӍ tuyӋt ÿӕi (chҷng hҥn 74014). Mӛi liên kӃt là mӝt ánh xҥ tӯ mӝt không gian ÿӏa chӍ này tӟi mӝt không gian ÿӏa chӍ khác . Hình 0-1 Xӱ lý nhiӅu bѭӟc cӫa chѭѫng trình ngѭӡi dùng VӅ truyӅn thӕng, liên kӃt các chӍ thӏ và dӳ liӋu tӟi các ÿӏa chӍ có thӇÿѭӧc thӵc hiӋn tҥi bҩt cӭ bѭӟc nào theo cách sau ÿây: x Thӡi gian biên dӏch: nӃu tҥi thӡi ÿiӇm biên dӏch có thӇ biӃt quá trình nҵm ӣÿâu trong bӝ nhӟ thì mã tuyӋt ÿӕi có thӇÿѭӧc phát sinh. Thí dө, nӃu biӃt trѭӟc quá trình ngѭӡi dùng nҵm tҥi vӏ trí R thì mã trình biên dӏch ÿѭӧc phát sinh sӁ bҳt ÿҫu tҥi vӏ trí ÿó và mӣ rӝng tӯÿó. NӃu tҥi thӡi ÿiӇm sau ÿó, vӏ trí bҳt ÿҫu thay ÿәi thì sӁ cҫn biên dӏch lҥi mã này. Các chѭѫng trình ÿӏnh dҥng .COM cӫa MS-DOS là mã tuyӋt ÿӕi giӟi hҥn tҥi thӡi ÿiӇm biên dӏch. x Thӡi ÿiӇm nҥp: nӃu tҥi thӡi ÿiӇm biên dӏch chѭa biӃt nѫi quá trình sӁ nҵm ӣÿâu trong bӝ nhӟ thì trình biên dӏch phҧi phát sinh mã có thӇ tái ÿӏnh vӏ. Trong trѭӡng hӧp này, liên kӃt cuӕi cùng ÿѭӧc trì hoãn cho tӟi thӡi ÿiӇm Biên soҥn: Th.s NguyӉn Phú Trѭӡng - 09/2005 Trang 138
Ĉҥi Hӑc Cҫn Thѫ - Khoa Công NghӋ Thông Tin - Giáo Trình HӋĈiӅu Hành – V1.0 nҥp. NӃu ÿӏa chӍ bҳt ÿҫu thay ÿәi, chúng ta chӍ cҫn nҥp lҥi mã ngѭӡi dùng ÿӇ hӧp nhҩt giá trӏÿѭӧc thay ÿәi này. x Thӡi gian thӵc thi: nӃu quá trình có thӇÿѭӧc di chuyӇn trong thӡi gian thӵc thi tӯ mӝt phân ÿoҥn bӝ nhӟ này tӟi mӝt phân ÿoҥn bӝ nhӟ khác thì viӋc liên kӃt phҧi bӏ trì hoãn cho tӟi thӡi gian chҥy. Phҫn cӭng ÿһc biӋt phҧi sҷn dùng cho cѫ chӃ này ÿӇ thӵc hiӋn công viӋc. Hҫu hӃt nhӳng hӋ ÿiӅu hành này dùng phѭѫng pháp này. Phҫn chӫ yӃu cӫa chѭѫng này ÿѭӧc dành hӃt ÿӇ hiӇn thӏ các liên kӃt khác nhau có thӇÿѭӧc cài ÿһt hӳu hiӋu trong mӝt hӋ thӕng máy tính và thҧo luұn sӵ hӛ trӧ phҫn cӭng tѭѫng ӭng. III.2 Không gian ÿӏa chӍ luұn lý và không gian ÿӏa chӍ vұt lý Mӝt ÿӏa chӍÿѭӧc tҥo ra bӣi CPU thѭӡng ÿѭӧc gӑi là ÿӏa chӍ luұn lý (logical address), ngѭӧc lҥi mӝt ÿӏa chӍÿѭӧc xem bӣi ÿѫn vӏ bӝ nhӟ-nghƭa là, mӝt ÿӏa chӍ ÿѭӧc nҥp vào thanh ghi ÿӏa chӍ bӝ nhӟ-thѭӡng ÿѭӧc gӑi là ÿӏa chӍ vұt lý (physical address). Các phѭѫng pháp liên kӃt ÿӏa chӍ thӡi ÿiӇm biên dӏch và thӡi ÿiӇm nҥp tҥo ra ÿӏa chӍ luұn lý và ÿӏa chӍ vұt lý xác ÿӏnh. Tuy nhiên, cѫ chӃ liên kӃt ÿӏa chӍ tҥi thӡi ÿiӇm thӵc thi dүn ÿӃn sӵ khác nhau giӳa ÿӏa chӍ luұn lý và ÿӏa chӍ vұt lý. Trong trѭӡng hӧp này, chúng ta thѭӡng gӑi ÿӏa chӍ luұn lý nhѭ là ÿӏa chӍҧo (virtual address). Tұp hӧp tҩt cҧÿӏa chӍ luұn lý ÿѭӧc tҥo ra bӣi chѭѫng trình là không gian ÿӏa chӍ luұn lý ; tұp hӧp tҩt cҧÿӏa chӍ vұt lý tѭѫng ӭng ÿӏa chӍ luұn lý này là không gian ÿӏa chӍ vұt lý. Do ÿó, trong cѫ chӃ liên kӃt ÿӏa chӍ tҥi thӡi ÿiӇm thӵc thi, không gian ÿӏa chӍ luұn lý và không gian ÿӏa chӍ vұt lý là khác nhau. ViӋc ánh xҥ tҥi thӡi ÿiӇm thӵc thi tӯÿӏa chӍҧo tӟi ÿӏa chӍ vұt lý ÿѭӧc thӵc hiӋn bӣi mӝt thiӃt bӏ phҫn cӭng ÿѭӧc gӑi là bӝ quҧn lý bӝ nhӟ MMU (memory- management unit). Chúng ta có thӇ chӑn giӳa nhӳng phѭѫng pháp khác nhau ÿӇ thӵc hiӋn viӋc ánh xҥ. Nhѭÿѭӧc hiӇn thӏ trong hình VII-2 ӣ trên, phѭѫng pháp này yêu cҫu sӵ hӛ trӧ phҫn cӭng. Thanh ghi nӅn bây giӡÿѭӧc gӑi là thanh ghi tái ÿӏnh vӏ. Giá trӏ trong thanh ghi tái ÿӏnh vӏÿѭӧc cӝng vào mӛi ÿӏa chӍÿѭӧc tҥo ra bӣi quá trình ngѭӡi dùng tҥi thӡi ÿiӇm nó ÿѭӧc gӣi tӟi bӝ nhӟ. Thí dө, nӃu giá trӏ nӅn là 14000, thì viӋc cӕ gҳng bӣi ngѭӡi dùng ÿӇ xác ÿӏnh vӏ trí 0 ÿѭӧc tӵÿӝng tái ÿӏnh vӏ tӟi vӏ trí 14000; mӝt truy xuҩt tӟi ÿӏa chӍ 346 ÿѭӧc ánh xҥ tӟi vӏ trí 14346. Hình 0-2 ÿӏnh vӏ tӵÿӝng dùng thanh ghi tái ÿӏnh vӏ Biên soҥn: Th.s NguyӉn Phú Trѭӡng - 09/2005 Trang 139
Ĉҥi Hӑc Cҫn Thѫ - Khoa Công NghӋ Thông Tin - Giáo Trình HӋĈiӅu Hành – V1.0 III.3 Nҥp ÿӝng Trong thҧo luұn cӫa chúng ta gҫn ÿây, toàn bӝ chѭѫng trình và dӳ liӋu cӫa mӝt quá trình phҧi ӣ trong bӝ nhӟ vұt lý ÿӇ quá trình thӵc thi. Kích thѭӟc cӫa quá trình bӏ giӟi hҥn bӣi kích thѭӟc cӫa bӝ nhӟ vұt lý. ĈӇ ÿҥt ÿѭӧc viӋc sӱ dөng không gian bӝ nhӟ tӕt hѫn, chúng ta có thӇ sӱ dөng nҥp ÿӝng (dynamic loading). Vӟi nҥp ÿӝng, mӝt thӫ tөc không ÿѭӧc nҥp cho tӟi khi nó ÿѭӧc gӑi. Tҩt cҧ thӫ tөc ÿѭӧc giӳ trên ÿƭa trong ÿӏnh dҥng nҥp có thӇ tái ÿӏnh vӏ. Chѭѫng trình chính ÿѭӧc nҥp vào bӝ nhӟ và ÿѭӧc thӵc thi. Khi mӝt thӫ tөc cҫn gӑi mӝt thӫ tөc khác, thӫ tөc gӑi trѭӟc hӃt kiӇm tra ÿӇ thҩy thӫ tөc khác ÿѭӧc nҥp hay không. NӃu không, bӝ nҥp liên kӃt có thӇ tái ÿӏnh vӏÿѭӧc gӑi ÿӇ nҥp thӫ tөc mong muӕn vào bӝ nhӟ và cұp nhұt các bҧng ÿӏa chӍ cӫa chѭѫng trình ÿӇ phҧn ánh thay ÿәi này. Sau ÿó, ÿiӅu khiӇn này ÿѭӧc truyӅn tӟi thӫ tөc mӟi ÿѭӧc nҥp. Thuұn lӧi cӫa nҥp ÿӝng là ӣÿó mӝt thӫ tөc không ÿѭӧc dùng thì không bao giӡÿѭӧc nҥp. Phѭѫng pháp này ÿһc biӋt có ích khi lѭӧng lӟn mã ÿѭӧc yêu cҫu quҧn lý các trѭӡng hӧp xҧy ra không thѭӡng xuyên, chҷng hҥn nhѭ các thӫ tөc lӛi. Trong trѭӡng hӧp này, mһc dù kích thѭӟc toàn bӝ chѭѫng trình có thӇ lӟn, nhѭng phҫn ÿѭӧc dùng (và do ÿó ÿѭӧc nҥp) có thӇ nhӓ hѫn nhiӅu. Nҥp ÿӝng không yêu cҫu hӛ trӧÿһc biӋt tӯ hӋÿiӅu hành. NhiӋm vө cӫa ngѭӡi dùng là thiӃt kӃ các chѭѫng trình cӫa hӑÿӇÿҥt ÿѭӧc sӵ thuұn lӧi ÿó. Tuy nhiên, hӋ ÿiӅu hành có thӇ giúp ngѭӡi lұp trình bҵng cách cung cҩp các thӫ tөc thѭ viӋn ÿӇ cài ÿһt nҥp tӵÿӝng. III.4 Liên kӃt ÿӝng và các thѭ viӋn ÿѭӧc chia sҿ Trong hình VII-1 cǊng hiӇn thӏ thѭ viӋn ÿѭӧc liên kӃt ÿӝng. Mӝt sӕ hӋÿiӅu hành hӛ trӧ chӍ liên kӃt tƭnh mà trong ÿó các thѭ viӋn ngôn ngӳ hӋ thӕng ÿѭӧc ÿӕi xӱ nhѭ bҩt kǤ module ÿӕi tѭӧng khác và ÿѭӧc kӃt hӧp bӣi bӝ nҥp thành hình ҧnh chѭѫng trình nhӏ phân. Khái niӋm liên kӃt ÿӝng là tѭѫng tӵ nhѭ khái niӋm nҥp ÿӝng. Liên kӃt bӏ trì hoãn hѫn là viӋc nҥp bӏ trì hoãn cho tӟi thӡi ÿiӇm thӵc thi. Ĉһc ÿiӇm này thѭӡng ÿѭӧc dùng vӟi các thѭ viӋn hӋ thӕng nhѭ các thѭ viӋn chѭѫng trình con cӫa các ngôn ngӳ. Không có tiӋn ích này, tҩt cҧ chѭѫng trình trên mӝt hӋ thӕng cҫn có mӝt bҧn sao thѭ viӋn cӫa ngôn ngӳ cӫa chúng (hay ít nhҩt thѭ viӋn ÿѭӧc tham chiӃu bӣi chѭѫng trình) ÿѭӧc chӭa trong hình ҧnh có thӇ thӵc thi. Yêu cҫu này làm lãng phí cҧ không gian ÿƭa và bӝ nhӟ chính. Vӟi liên kӃt ÿӝng, mӝt stub là mӝt ÿoҥn mã hiӇn thӏ cách ÿӏnh vӏ chѭѫng trình con trong thѭ viӋn cѭ trú trong bӝ nhӟ hay cách nҥp thѭ viӋn nӃu chѭѫng trình con chѭa hiӋn diӋn. Khi stub này ÿѭӧc thӵc thi, nó kiӇm tra ÿӇ thҩy chѭѫng trình con ÿѭӧc yêu cҫu ÿã ӣ trong bӝ nhӟ hay chѭa. NӃu chѭa, chѭѫng trình này sӁ nҥp chѭѫng trình con vào trong bӝ nhӟ. Dù là cách nào, stub thay thӃ chính nó vӟi ÿӏa chӍ cӫa chѭѫng trình con và thӵc thi chѭѫng trình con ÿó. Do ÿó, thӡi ÿiӇm tiӃp theo phân ÿoҥn mã ÿҥt ÿѭӧc, chѭѫng trình con trong thѭ viӋn ÿѭӧc thӵc thi trӵc tiӃp mà không gây ra bҩt kǤ chi phí cho viӋc liên kӃt ÿӝng. Dѭӟi cѫ chӃ này, tҩt cҧ các quá trình sӱ dөng mӝt thѭ viӋn ngôn ngӳ thӵc thi chӍ mӝt bҧn sao cӫa mã thѭ viӋn. Biên soҥn: Th.s NguyӉn Phú Trѭӡng - 09/2005 Trang 140
Ĉҥi Hӑc Cҫn Thѫ - Khoa Công NghӋ Thông Tin - Giáo Trình HӋĈiӅu Hành – V1.0 III.5 Phӫ lҳp ĈӇ cho phép mӝt quá trình lӟn hѫn lѭӧng bӝ nhӟÿѭӧc cҩp phát cho nó, chúng ta sӱ dөng cѫ chӃ phӫ lҳp (overlays). Ý tѭӣng phӫ lҳp là giӳ trong bӝ nhӟ nhӳng chӍ thӏ và dӳ liӋu ÿѭӧc yêu cҫu tҥi bҩt kǤ thӡi ÿiӇm nào ÿѭӧc cho. Khi nhӳng chӍ thӏÿó ÿѭӧc yêu cҫu, chúng ÿѭӧc nҥp vào không gian ÿѭӧc chiӃm trѭӟc ÿó bӣi các chӍ thӏ mà chúng không còn cҫn nӳa. Thí dө, xét trình dӏch hӧp ngӳ hai lҫn (two-pass assembler). Trong suӕt lҫn thӭ 1, nó xây dӵng bҧng danh biӇu; sau ÿó, trong lҫn thӭ 2, nó tҥo ra mã máy. Chúng ta có thӇ phân chia trình dӏch hӧp ngӳ thành mã lҫn 1, mã lҫn 2, bҧng danh biӇu, và nhӳng thӫ tөc hӛ trӧ chung ÿѭӧc dùng bӣi lҫn 1 và lҫn 2. Giҧ sӱ kích thѭӟc cӫa các thành phҫn này nhѭ sau: Lҫn 1 70 KB Lҫn 2 80 KB Bҧng danh biӇu 20 KB Các thӫ tөc chung 30 KB ĈӇ nҥp mӑi thӭ mӝt lҫn, chúng ta cҫn 200KB bӝ nhӟ. NӃu chӍ có 150KB sҷn có, chúng ta không thӇ chҥy quá trình cӫa chúng ta. Tuy nhiên, chú ý rҵng lҫn 1 và lҫn 2 không cҫn ӣ trong bӝ nhӟ cùng mӝt lúc. Do ÿó, chúng ta ÿӏnh nghƭa hai phӫ lҳp. Phӫ lҳp A là bҧng danh biӇu, các thӫ tөc chung, lҫn 1, và phӫ lҳp B là bҧng biӇu tѭӧng, các thӫ tөc chung và lҫn 2. Chúng ta bә sung trình ÿiӅu khiӇn phӫ lҳp (10 KB) và bҳt ÿҫu vӟi phӫ lҳp A trong bӝ nhӟ. Khi chúng ta kӃt thúc lҫn 1, chúng ta nhҧy tӟi trình ÿiӅu khiӇn phӫ lҳp, trình ÿiӅu khiӇn này sӁÿӑc phӫ lҳp B vào trong bӝ nhӟ, viӃt chӗng lên phӫ lҳp B và sau ÿó chuyӇn ÿiӅu khiӇn tӟi lҫn 2. Phӫ lҳp A chӍ cҫn 120KB, ngѭӧc lҥi phӫ lҳp B cҫn 130KB (hình VII-3). Bây giӡ chúng ta có thӇ chҥy trình hӧp ngӳ trong 150KB bӝ nhӟ. Nó sӁ nҥp nhanh hѫn vì rҩt ít dӳ liӋu cҫn ÿѭӧc chuyӇn trѭӟc khi viӋc thӵc thi bҳt ÿҫu. Tuy nhiên, nó sӁ chҥy chұm hѫn do nhұp/xuҩt phөÿӑc mã mã cho phӫ lҳp A qua mã cho phӫ lҳp B. Hình 0-3- Các phӫ lҳp cho mӝt bӝ hӧp ngӳ dӏch hai lҫn Biên soҥn: Th.s NguyӉn Phú Trѭӡng - 09/2005 Trang 141
Ĉҥ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ã cho phӫ lҳp A và mã cho phӫ lҳp B ÿѭӧc giӳ trên ÿƭa nhѭ nhӳng hình ҧnh bӝ nhӟ tuyӋt ÿӕi, và ÿѭӧc ÿӑc bӣi trình ÿiӅu khiӇn phӫ lҳp khi cҫn. Tái ÿӏnh vӏÿһc biӋt và các giҧi thuұt liên kӃt ÿѭӧc yêu cҫu xây dӵng các phӫ lҳp. IV Hoán vӏ Mӝt quá trình cҫn ӣ trong bӝ nhӟÿӇÿѭӧc thӵc thi. Tuy nhiên, mӝt quá trình có thӇÿѭӧc hoán vӏ (swapped) tҥm thӡi khӓi bӝ nhӟ tӟi vùng lѭu trӳ phө backing store, sau ÿó mang trӣ lҥi bӝ nhӟÿӇ viӋc thӵc thi ÿѭӧc tiӃp tөc. Thí dө, giҧ sӱ mӝt môi trѭӡng ÿa chѭѫng vӟi giҧi thuұt lұp thӡi biӇu CPU round-robin. Khi ÿӏnh mӭc thӡi gian hӃt, bӝ quҧn lý bӝ nhӟ sӁ bҳt ÿҫu hoán vӏ ra (swap out) vùng lѭu trӳ phө quá trình vӯa mӟi kӃt thúc và hoán vӏ vào (swap in) mӝt quá trình khác tӟi không gian bӝ nhӟÿѭӧc trӕng (hình VII-4). Do ÿó, bӝÿӏnh thӡi biӇu CPU sӁ cҩp nhӳng phҫn thӡi gian tӟi nhӳng quá trình khác trong bӝ nhӟ. Lý tѭӣng, bӝ quҧn lý sӁ hoán vӏ các quá trình ÿӫ nhanh ÿӇ mӝt vài quá trình sӁӣ trong bӝ nhӟ, sҷn sàng thӵc thi, khi bӝÿӏnh thӡi CPU muӕn ÿӏnh thӡi lҥi CPU. Ĉӏnh mӭc cǊng phҧi ÿӫ lӟn ÿӇ phù hӧp lѭӧng tính toán ÿѭӧc thӵc hiӋn giӳa các hoán vӏ. Hình 0-4- Hoán vӏ hai quá trình dùng ÿƭa nhѭ là backing store Mӝt biӃn thӇ cӫa chính sách hoán vӏ này ÿѭӧc dùng cho các giҧi thuұt ÿӏnh thӡi trên cѫ sӣѭu tiên. NӃu mӝt quá trình có ÿӝ ѭu tiên cao hѫn ÿӃn và muӕn phө vө, bӝ quҧn lý bӝ nhӟ có thӇ hoán vӏ ra quá trình có ÿӝ ѭu tiên thҩp hѫn ÿӇ mà nó có thӇ nҥp và thӵc thi quá trình có ÿӝ ѭu tiên cao hѫn. Khi quá trình có ÿӝ ѭu tiên cao hѫn kӃt thúc, quá trình có ÿӝ ѭu tiên thҩp hѫn có thӇÿѭӧc hoán vӏ vào trӣ lҥi và ÿѭӧc tiӃp tөc. BiӃn thӇ cӫa hoán vӏ này thѭӡng ÿѭӧc gӑi là cuӝn ra (roll out), và cuӝn vào (roll in). Thông thѭӡng, mӝt quá trình ÿѭӧc hoán vӏ ra sӁÿѭӧc hoán vӏ trӣ lҥi vào cùng không gian bӝ nhӟ mà nó ÿã chiӃm trѭӟc ÿó. Sӵ giӟi hҥn này ÿѭӧc sai khiӃn bӣi phѭѫng pháp liên kӃt ÿӏa chӍ. NӃu liên kӃt ÿӏa chӍÿѭӧc thӵc hiӋn tҥi thӡi ÿiӇm hӧp dӏch hay nҥp thì quá trình không thӇÿѭӧc di chuyӇn vào không gian bӝ nhӟ khác vì các ÿӏa chӍ vұt lý ÿѭӧc tính trong thӡi gian thӵc thi. Biên soҥn: Th.s NguyӉn Phú Trѭӡng - 09/2005 Trang 142
Ĉҥi Hӑc Cҫn Thѫ - Khoa Công NghӋ Thông Tin - Giáo Trình HӋĈiӅu Hành – V1.0 Hoán vӏ yêu cҫu mӝt vùng lѭu trӳ phө (backing store). Vùng lѭu trӳ phө này thѭӡng là mӝt ÿƭa tӕc ÿӝ cao. Nó phҧi ÿӫ lӟn ÿӇ chӭa các bҧn sao cӫa tҩt cҧ hình ҧnh bӝ nhӟ cho tҩt cҧ ngѭӡi dùng, và nó phҧi cung cҩp truy xuҩt trӵc tiӃp tӟi các hình ҧnh bӝ nhӟ này. HӋ thӕng này duy trì mӝt hàng ÿӧi sҷn sàng chӭa tҩt cҧ quá trình mà các hình ҧnh bӝ nhӟ cӫa nó ӣ trong vùng lѭu trӳ phө hay trong bӝ nhӟ và sҷn sàng ÿӇ thӵc thi. Bҩt cӭ khi nào bӝÿӏnh thӡi CPU quyӃt ÿӏnh thӵc thi mӝt quá trình, nó gӑi bӝ phân phát (dispacher). Bӝ phân phát kiӇm tra ÿӇ thҩy quá trình tiӃp theo trong hàng ÿӧi ӣ trong bӝ nhӟ không. NӃu không, và không có vùng bӝ nhӟ trӕng, bӝ phân phát hoán vӏ ra mӝt quá trình hiӋn hành trong bӝ nhӟ và hoán vӏ vào mӝt quá trình mong muӕn. Sau ÿó, nó nҥp lҥi các thanh ghi và chuyӇn ÿiӅu khiӇn tӟi quá trình ÿѭӧc chӑn. Trong các hӋ hoán vӏ, thӡi gian chuyӇn ÿәi giӳa các tác vө cҫn ÿѭӧc quan tâm. Mӛi quá trình cҫn ÿѭӧc phân chia mӝt khoҧng thӡi gian sӱ dөng CPU ÿӫ lӟn ÿӇ không thҩy rõ sӵ chұm trӉ do các thao tác hoán vӏ gây ra. NӃu không, hӋ thӕng sӁ dùng phҫn lӟn thӡi gian ÿӇ hoán vӏ các quá trình vào ra bӝ nhӟ chính, CPU nhѭ vұy sӁ không sӱ dөng hiӋu quҧ. Hoán vӏ cǊng bӏ ràng buӝc bӣi yӃu tӕ khác. NӃu chúng ta muӕn hoán vӏ mӝt quá trình, chúng ta phҧi ÿҧm bҧo rҵng nó hoàn toàn rӛi. Quan tâm ÿһc biӋt là viӋc chӡ nhұp/xuҩt. Mӝt quá trình có thӇÿang chӡ thao tác nhұp/xuҩt khi chúng ta hoán vӏ quá trình ÿó tӟi nѫi trӕng bӝ nhӟ cӫa nó. Tuy nhiên, nӃu nhұp/xuҩt ÿang truy xuҩt không ÿӗng bӝ bӝ nhӟ ngѭӡi dùng cho nhұp/xuҩt vùng ÿӋm, thì quá trình không thӇÿѭӧc hoán vӏ. Giҧ sӱ rҵng thao tác nhұp/xuҩt ÿang xӃp hàng chӡ vì thiӃt bӏÿang bұn. Sau ÿó, nӃu chúng ta hoán vӏ quá trình P1 ra và hoán vӏ P2 vào thì thao tác nhұp/xuҩt có thӇ cӕ gҳng sӱ dөng bӝ nhӟ hiӋn thuӝc vӅ quá trình P2. Hai giҧi pháp chӫ yӃu cho quá trình này là không bao giӡ hoán vӏ quá trình ÿang chӡ nhұp/xuҩt hay thӵc thi các thao tác nhұp/xuҩt chӍӣ trong vùng ÿӋm cӫa hӋÿiӅu hành. ChuyӇn giӳa các vùng ÿӋm cӫa hӋÿiӅu hành và bӝ nhӟ quá trình thì chӍ xҧy ra khi quá trình ÿѭӧc hoán vӏ vào. VCҩp phát bӝ nhӟ liên tөc Bӝ nhӟ chính phҧi cung cҩp cho cҧ hӋÿiӅu hành và các quá trình ngѭӡi dùng khác nhau. Do ÿó, chúng ta cҫn cҩp phát nhӳng phҫn khác nhau cӫa bӝ nhӟ chính trong nhӳng cách hiӋu quҧ nhҩt có thӇ. Phҫn này chúng ta giҧi thích mӝt phѭѫng pháp thông dөng, cҩp phát bӝ nhӟ liên tөc. Bӝ nhӟ thѭӡng ÿѭӧc phân chia thành hai phân khu, mӝt cho hӋÿiӅu hành ÿӏnh vӏ và mӝt cho các quá trình ngѭӡi dùng. Chúng ta có thӇÿһt hӋÿiӅu hành ӣ bӝ nhӟ cao hay bӝ nhӟ thҩp. YӃu tӕ quan trӑng ҧnh hѭӣng tӟi quyӃt ÿӏnh này là vӏ trí cӫa vector ngҳt. Vì vector ngҳt thѭӡng ӣ trong bӝ nhӟ thҩp nên các lұp trình viên thѭӡng cǊng ÿһt hӋÿiӅu hành trong bӝ nhӟ thҩp. Do ÿó, trong giáo trình này chúng ta sӁ thҧo luұn chӍ trѭӡng hӧp hӋÿiӅu hành ÿӏnh vӏ trong bӝ nhӟ thҩp. Phát triӇn cӫa trѭӡng hӧp khác là tѭѫng tӵ. Chúng ta thѭӡng muӕn nhiӅu quá trình ngѭӡi dùng ÿӏnh vӏ trong bӝ nhӟ tҥi cùng thӡi ÿiӇm. Do ÿó, chúng ta cҫn xem xét cách cҩp phát bӝ nhӟ trӕng tӟi nhӳng quá trình ӣ trong hàng ÿӧi nhұp ÿang chӡÿѭӧc mang vào bӝ nhӟ. Trong cҩp phát bӝ nhӟ liên tөc, mӛi quá trình ÿѭӧc chӭa trong mӝt phҫn bӝ nhӟ liên tөc. V.1 Bҧo vӋ bӝ nhӟ Trѭӟc khi thҧo luұn cҩp phát bӝ nhӟ chúng ta phҧi thҧo luұn vҩn ÿӅ bҧo vӋ bӝ nhӟ-bҧo vӋ hӋÿiӅu hành tӯ quá trình ngѭӡi dùng, và bҧo vӋ các quá trình tӯ mӝt quá trình khác. Chúng ta có thӇ cung cҩp bҧo vӋ này bҵng cách dùng thanh ghi tái ÿӏnh vӏ. Biên soҥn: Th.s NguyӉn Phú Trѭӡng - 09/2005 Trang 143
Ĉҥi Hӑc Cҫn Thѫ - Khoa Công NghӋ Thông Tin - Giáo Trình HӋĈiӅu Hành – V1.0 Thanh ghi tái ÿӏnh vӏ chӭa giá trӏÿӏa chӍ vұt lý nhӓ nhҩt; thanh ghi giӟi hҥn chӭa dãy các ÿӏnh chӍ luұn lý (thí dө: tái ÿӏnh vӏ = 100040 và giӟi hҥn = 74600). Vӟi các thanh ghi tái ÿӏnh vӏ và giӟi hҥn, mӛi ÿӏa chӍ luұn lý phҧi ít hѫn thanh ghi giӟi hҥn; MMU ánh xҥÿӏa chӍ luұn lý ÿӝng bҵng cách cӝng giá trӏ trong thanh ghi tái ÿӏnh vӏ. Ĉӏa chӍ ÿѭӧc tái ÿӏnh vӏ này ÿѭӧc gӱi tӟi bӝ nhӟ (nhѭ hình VII-5). Hình 0-5 Hӛ trӧ phҫn cӭng cho các thanh ghi tái ÿӏnh vӏ và các giӟi hҥn Khi bӝÿӏnh thӡi CPU chӑn mӝt quá trình thӵc thi, bӝ phân phát nҥp thanh ghi tái ÿӏnh vӏ và giӟi hҥn vӟi các giá trӏÿúng nhѭ mӝt phҫn cӫa chuyӇn ÿәi ngӳ cҧnh. Vì mӑi ÿӏa chӍÿѭӧc phát sinh bӣi CPU ÿѭӧc kiӇm tra dӵa trên các thanh ghi này, chúng ta có thӇ bҧo vӋ hӋÿiӅu hành và các chѭѫng trình và dӳ liӋu ngѭӡi dùng khác tӯ viӋc sӱa ÿәi bӣi quá trình ÿang chҥy này. Cѫ chӃ dùng thanh ghi tái ÿӏnh vӏ cung cҩp mӝt cách hiӋu quҧÿӇ cho phép kích thѭӟc hӋÿiӅu hành thay ÿәi ÿӝng. Khҧ năng mӅm dӁo này có thӇ mong muӕn trong nhiӅu trѭӡng hӧp. Thí dө, hӋÿiӅu hành chӭa mã và không gian vùng ÿӋm cho trình ÿiӅu khiӇn thiӃt bӏ. NӃu mӝt trình ÿiӅu khiӇn thiӃt bӏ (hay dӏch vө hӋÿiӅu hành khác) không ÿѭӧc dùng phә biӃn, nó không muӕn giӳ mã và dӳ liӋu trong bӝ nhӟ, khi chúng ta có thӇ dùng không gian ÿó cho mөc ÿích khác. Nhӳng mã nhѭ thӃ thѭӡng ÿѭӧc gӑi là mã hӋÿiӅu hành tҥm thӡi (transient operating system code); nó ÿӃn và ÿi khi ÿѭӧc yêu cҫu. Do ÿó, dùng mã này thay ÿәi kích thѭӟc cӫa hӋÿiӅu hành trong khi thӵc thi chѭѫng trình. Biên soҥn: Th.s NguyӉn Phú Trѭӡng - 09/2005 Trang 144
Ĉҥ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.2 HӋ thӕng ÿѫn chѭѫng Trong phѭѫng pháp này bӝ nhӟÿѭӧc chia sҿ cho hӋÿiӅu hành và mӝt chѭѫng trình duy nhҩt cӫa ngѭӡi sӱ dөng. Tҥi mӝt thӡi ÿiӇm, mӝt phҫn cӫa bӝ nhӟ sӁ do hӋ ÿiӅu hành chiӃm giӳ, phҫn còn lҥi thuӝc vӅ quá trình ngѭӡi dùng duy nhҩt trong hӋ thӕng (Hình VII-6). Quá trình này ÿѭӧc toàn quyӅn sӱ dөng bӝ nhӟ dành cho nó. 0xFFF User process Operating system 0 Hình 0-6 Tә chӭc bӝ nhӟ trong hӋ thӕng ÿѫn chѭѫng Khi bӝ nhӟÿѭӧc tә chӭc theo cách thӭc này, chӍ có thӇ xӱ lý mӝt chѭѫng trình tҥi mӝt thӡi ÿiӇm. Quan sát hoҥt ÿӝng cӫa các quá trình, có thӇ nhұn thҩy rҩt nhiӅu tiӃn trình trҧi qua phҫn lӟn thӡi gian ÿӇ chӡ các thao tác nhұp/xuҩt hoàn thành. Trong suӕt thӡi gian này, CPU ӣ trҥng thái rӛi. Trong trѭӡng hӧp nhѭ thӃ, hӋ thӕng ÿѫn chѭѫng không cho phép sӱ dөng hiӋu quҧ CPU. Ngoài ra, sӵÿѫn chѭѫng không cho phép nhiӅu ngѭӡi sӱ dөng làm viӋc ÿӗng thӡi theo cѫ chӃ tѭѫng tác. ĈӇ nâng cao hiӋu suҩt sӱ dөng CPU, cҫn cho phép chӃÿӝÿa chѭѫng mà trong ÿó các quá trình chia sҿ CPU vӟi nhau ÿӇ hoҥt ÿӝng ÿӗng hành. V.3 HӋ thӕng ÿa chѭѫng vӟi phân khu cӕÿӏnh Mӝt trong nhӳng phѭѫng pháp ÿѫn giҧn nhҩt ÿӇ cҩp phát bӝ nhӟ là chia bӝ nhӟ thành nhӳng phân khu có kích thѭӟc cӕÿӏnh. Mӛi phân khu có thӇ chӭa chính xác mӝt quá trình. Do ÿó, cҩp ÿӝ ÿa chѭѫng ÿѭӧc giӟi hҥn bӣi sӕ lѭӧng phân khu. Trong phѭѫng pháp ÿa phân khu, khi mӝt phân khu rҧnh, mӝt quá trình ÿѭӧc chӑn tӯ hàng ÿӧi nhұp và ÿѭӧc nҥp vào phân khu trӕng. Khi quá trình kӃt thúc, phân khu trӣ nên sҷn dùng cho mӝt quá trình khác. Có hai tiӃp cұn ÿӇ tә chӭc hàng ÿӧi: x Sӱ dөng nhiӅu hàng ÿӧi: mӛi phân khu sӁ có mӝt hàng ÿӧi tѭѫng ӭng (hình VII-7a). Khi mӝt quá trình mӟi ÿѭӧc tҥo ra, nó ÿѭӧc ÿѭa vào hàng ÿӧi cӫa phân khu có kích thѭӟc nhӓ nhҩt thoҧ nhu cҫu chӭa nó. Cách tә chӭc này có khuyӃt ÿiӇm trong trѭӡng hӧp các hàng ÿӧi cӫa mӝt sӕ phân khu trӕng trong khi các hàng ÿӧi cӫa các phân khu khác lҥi ÿҫy, buӝc các quá trình trong nhӳng hàng ÿӧi này phҧi chӡÿѭӧc cҩp phát bӝ nhӟ. x Sӱ dөng mӝt hàng ÿӧi: tҩt cҧ các quá trình ÿѭӧc ÿһt trong hàng ÿӧi duy nhҩt (hình VII-7b). Khi có mӝt phân khu trӕng, quá trình ÿҫu tiên trong hàng ÿӧi có kích thѭӟc phù hӧp sӁÿѭӧc ÿһt vào phân khu và cho xӱ lý. Biên soҥn: Th.s NguyӉn Phú Trѭӡng - 09/2005 Trang 145
Ĉҥi Hӑc Cҫn Thѫ - Khoa Công NghӋ Thông Tin - Giáo Trình HӋĈiӅu Hành – V1.0 Partition 3 200K Partition 3 Partition 4 600K Partition 4 Partition 1 400K Partition 1 Operating system Operating system a. Sӱ dөng nhiӅu hàng ÿӧib.Sӱ dөng mӝt hàng ÿӧi Hình 0-7 Cҩp phát phân khu có kích thѭӟc cӕÿӏnh Khi sӱ dөng giҧi thuұt này ngѭӡi ta muӕn tránh sӵ hao phí mӝt phân khu lӟn cho mӝt công viӋc nhӓ, nhѭng lҥi xҧy ra bҩt bình ÿҷng, bҩt lӧi ÿӕi vӟi các công viӋc nhӓ. ĈӇ giҧi quyӃt ngѭӡi ta thêm vào qui luұt là mӝt công viӋc sӁ không bӏ bӓ qua nӳa nӃu nó ÿã bӏ bӓ qua k lҫn qui ÿӏnh. Mӛi lҫn mӝt công viӋc bӏ bӓ qua nó ÿѭӧc ÿánh dҩu mӝt ÿiӇm. Khi ÿҥt ÿѭӧc sӕÿiӇm qui ÿӏnh, nó sӁ không bӏ bӓ qua nӳa, sӁ ÿѭӧc nҥp vào và thӵc hiӋn mһc dҫu có thӇ trên mӝt phân khu lӟn hѫn. Phѭѫng pháp này ban ÿҫu ÿѭӧc sӱ dөng bӣi hӋÿiӅu hành IBM OS/360, nó ÿѭӧc gӑi là MFT (Multiprogramming with Fixed number of Tasks). HiӋn nay nó không còn sӱ dөng nӳa. V.4 HӋ thӕng ÿa chѭѫng vӟi phân khu ÿӝng Cѫ chӃ này là tәng quát cӫa cѫ chӃ phân khu cӕÿӏnh. Nó ÿѭӧc dùng chӫ yӃu trong môi trѭӡng xӱ lý theo lô. NhiӅu ý tѭӣng ÿѭӧc trình bày ӣÿây cǊng có thӇ áp dөng tӟi môi trѭӡng chia thӡi mà trong ÿó phân ÿoҥn thuҫn ÿѭӧc dùng cho viӋc quҧn lý bӝ nhӟ. HӋÿiӅu hành giӳ mӝt bҧng hiӇn thӏ nhӳng phҫn nào cӫa bӝ nhӟ là sҷn dùng và phҫn nào ÿang bұn. Ban ÿҫu, tҩt cҧ bӝ nhӟ là sҷn dùng cho quá trình ngѭӡi dùng, và ÿѭӧc xem nhѭ mӝt khӕi lӟn bӝ nhӟ sҷn dùng hay mӝt lӛ. Khi mӝt quá trình ÿӃn và cҫn bӝ nhӟ, chúng ta tìm kiӃm mӝt lӛ trӕng ÿӫ lӟn cho quá trình này. NӃu chúng ta tìm thҩy, chúng ta cҩp phát chӍ phҫn bӝ nhӟ nhiӅu bҵng lѭӧng ÿѭӧc yêu cҫu, phҫn còn lҥi sҷn dùng ÿӇ thoҧ mãn nhӳng yêu cҫu tѭѫng lai (Hình VII-8). Biên soҥn: Th.s NguyӉn Phú Trѭӡng - 09/2005 Trang 146
Ĉҥi Hӑc Cҫn Thѫ - Khoa Công NghӋ Thông Tin - Giáo Trình HӋĈiӅu Hành – V1.0 Thӡi gian C C C C C B B B B E A A A D D D OS OS OS OS OS OS OS Hình VIII-8 Cҩp phát các phân khu có kích thѭӟc thay ÿәi Khi các quá trình ÿi vào hӋ thӕng, chúng ÿѭӧc ÿһt vào hàng ÿӧi nhұp. HӋÿiӅu hành xem xét yêu cҫu bӝ nhӟ cӫa mӛi quá trình và lѭӧng không gian bӝ nhӟ sҷn có ÿӇ xác ÿӏnh các quá trình nào ÿѭӧc cҩp phát bӝ nhӟ. Khi mӝt quá trình ÿѭӧc cҩp không gian, nó ÿѭӧc nҥp vào bӝ nhӟ và sau ÿó nó có thӇ cҥnh tranh CPU. Khi mӝt quá trình kӃt thúc, nó giҧi phóng bӝ nhӟ cӫa nó, sau ÿó hӋÿiӅu hành có thӇÿһt mӝt quá trình khác tӯ hàng ÿӧi nhұp. Tҥi bҩt cӭ thӡi ÿiӇm ÿѭӧc cho, chúng ta có mӝt danh sách kích thѭӟc khӕi trӕng và hàng ÿӧi nhұp. HӋÿiӅu hành có thӇ xӃp hàng ÿӧi nhұp dӵa theo giҧi thuұt ÿӏnh thӡi. Bӝ nhӟÿѭӧc cҩp phát tӟi quá trình cho ÿӃn khi các yêu cҫu bӝ nhӟ cӫa quá trình kӃ tiӃp không thӇÿѭӧc thoҧ; không có khӕi bӝ nhӟ trӕng (hay lӛ) ÿӫ lӟn ÿӇ quҧn lý quá trình ÿó. Sau ÿó, hӋÿiӅu hành có thӇ chӡ cho ÿӃn khi khӕi ÿӫ lӟn sҷn dùng hay nó có thӇ di chuyӇn xuӕng hàng ÿӧi nhұp ÿӇ xem các yêu cҫu bӝ nhӟ nhӓ hѫn cӫa các quá trình khác có thӇÿѭӧc thoҧ hay không. Thông thѭӡng, mӝt tұp hӧp các lӛ có kích thѭӟc khác nhau ÿѭӧc phân tán khҳp bӝ nhӟ tҥi bҩt cӭ thӡi ÿiӇm ÿѭӧc cho. Khi mӝt quá trình ÿӃn và yêu cҫu bӝ nhӟ, hӋ thӕng tìm tұp hӧp này mӝt lӛ trӕng ÿӫ lӟn cho quá trình này. NӃu lӛ trӕng quá lӟn, nó ÿѭӧc chia làm hai: mӝt phҫn ÿѭӧc cҩp tӟi quá trình ÿӃn; phҫn còn lҥi ÿѭӧc trҧ vӅ tұp hӧp các lӛ. NӃu lӛ mӟi nҵm kӅ vӟi các lӛ khác, các lӛ nҵm kӅ này ÿѭӧc gom lҥi ÿӇ tҥo thành mӝt lӛ lӟn hѫn. Tҥi thӡi ÿiӇm này, hӋ thӕng cҫn kiӇm tra có quá trình nào ÿang chӡ bӝ nhӟ và bӝ nhӟ trӕng mӟi hay bӝ nhӟ vӯa ÿѭӧc kӃt hӧp lҥi có thӇ thoҧ yêu cҫu cӫa bҩt cӭ quá trình ÿang chӡ này không. Thӫ tөc này là mӝt trѭӡng hӧp ÿһc biӋt cӫa vҩn ÿӅ cҩp phát lѭu trӳÿӝng là làm cách nào ÿӇ thoҧ mãn mӝt yêu cҫu có kích thѭӟc n tӯ danh sách lӛ trӕng. Có hai giҧi pháp chӫ yӃu cho vҩn ÿӅ này. 1) Quҧn lý bҵng bҧn ÿӗ bit: bӝ nhӟÿѭӧc chia thành các ÿѫn vӏ cҩp phát, mӛi ÿѫn vӏÿѭӧc ánh xҥ tӟi mӝt bit trong bҧn ÿӗ bit (Hình VII-9). Giá trӏ bit này xác ÿӏnh trҥng thái cӫa ÿѫn vӏ bӝ nhӟÿó: 0 ÿang tӵ do, 1 ÿã ÿѭӧc cҩp phát. Khi cҫn nҥp mӝt quá trình có kích thѭӟc k ÿѫn vӏ, hӋ thӕng sӁ tìm trong bҧn ÿӗ bit mӝt dãy k bit có giá trӏ 0. Kích thѭӟc cӫa ÿѫn vӏ cҩp phát là vҩn ÿӅ lӟn trong thiӃt kӃ. NӃu kích thѭӟc ÿѫn vӏ cҩp phát nhӓ sӁ làm tăng kích thѭӟc cӫa bҧn ÿӗ bit. Ngѭӧc lҥ, nӃu kích thѭӟc ÿѫn Biên soҥn: Th.s NguyӉn Phú Trѭӡng - 09/2005 Trang 147
Ĉҥ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ӏ cҩp phát lӟn có thӇ gây hao phí cho ÿѫn vӏ cҩp phát sau cùng. Ĉây là giҧi pháp ÿѫn giҧn nhѭng thӵc hiӋn chұm nên ít ÿѭӧc dùng. ABCDE a ) Bӝ nhӟ có 5 quá trình và 3 lӛ trӕng 11111000 11111111 11001111 b ) 11111000 Bҧn ÿӗ bit tѭѫng ӭng Hình 0-9 Quҧn lý bӝ nhӟ bҵng bҧn ÿӗ bit 2) Quҧn lý bҵng danh sách liên kӃt: dùng mӝt danh sách liên kӃt ÿӇ quҧn lý các phân ÿoҥn bӝ nhӟÿã cҩp phát và phân ÿoҥn tӵ do, mӝt phân ÿoҥn có thӇ là mӝt quá trình hay mӝt vùng nhӟ trӕng giӳa hai quá trình. Danh sách liên kӃt gӗm nhiӅu mөc tӯ liên tiӃp. Mӛi mөc tӯ gӗm 1 bit ÿҫu ÿӇ xác ÿӏnh phân ÿoҥn ÿó là lӛ trӕng (H) hay mӝt quá trình (P), sau ÿó là 3 tӯÿӇ chӍÿӏa chӍ bҳt ÿҫu, chiӅu dài và chӍÿiӇm tӟi mөc kӃ tiӃp. ViӋc sҳp xӃp các phân ÿoҥn theo ÿӏa chӍ hay theo kích thѭӟc tuǤ thuӝc vào giҧi thuұt quҧn lý bӝ nhӟ. Sѫÿӗ quҧn lý bҵng danh sách liên kӃt tѭѫng ӭng vӟi sѫÿӗ quҧn lý bҵng bҧn ÿӗ bit ÿѭӧc minh hoҥ trong hình VII-10. 3) Hình 0-10 Quҧn lý bӝ nhӟ bҵng danh sách liên kӃt Tұp hӧp các lӛ trӕng ÿѭӧc tìm thҩy ÿӇ xác ÿӏnh lӛ nào là tӕt nhҩt ÿӇ cҩp phát. Các chiӃn lѭӧc first-fit, best-fit, worst-fit là nhӳng chiӃn lѭӧc phә biӃn nhҩt ÿѭӧc dùng ÿӇ chӑn mӝt lӛ trӕng tӯ tұp hӧp các lӛ trӕng. x First-fit: cҩp phát lӛ trӕng ÿҫu tiên ÿӫ lӟn. Tìm kiӃm có thӇ bҳt ÿҫu tҥi ÿҫu tұp hӧp các lӛ trӕng hay tҥi ÿiӇm kӃt thúc cӫa tìm kiӃm first-fit trѭӟc ÿó. Chúng ta dӯng tìm kiӃm ngay khi chúng ta tìm thҩy mӝt lӛ trӕng ÿӫ lӟn. x Best-fit: cҩp phát lӛ trӕng nhӓ nhҩt ÿӫ lӟn. Chúng ta phҧi tìm toàn bӝ danh sách, trӯ khi danh sách ÿѭӧc xӃp thӭ tӵ theo kích thѭӟc. ChiӃn lѭӧc này tҥo ra lӛ trӕng nhӓ nhҩt còn thӯa lҥi. Biên soҥn: Th.s NguyӉn Phú Trѭӡng - 09/2005 Trang 148
Ĉҥ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 Worst-fit: cҩp phát lӛ trӕng lӟn nhҩt. Chúng ta phҧi tìm toàn danh sách trӯ khi nó ÿѭӧc xӃp theo thӭ tӵ kích thѭӟc. ChiӃn lѭӧc này tҥo ra lӛ trӕng còn lҥi lӟn nhҩt mà có thӇ có ích hѫn lӛ trӕng nhӓ tӯ tiӃp cұn best-fit. Các mô phӓng hiӇn thӏ rҵng cҧ first-fit và best-fit là tӕt hѫn worst-fit vӅ viӋc giҧm thӡi gian và sӱ dөng lѭu trӳ. Giӳa first-fit và best-fit không thӇ xác ÿӏnh rõ chiӃn lѭӧc nào tӕt hѫn vӅ sӱ dөng lѭu trӳ, nhѭng first-fit có tӕc ÿӝ nhanh hѫn. Tuy nhiên, các giҧi thuұt này gһp phҧi vҩn ÿӅ phân mãnh ngoài (external fragmentation). Khi các quá trình ÿѭӧc nҥp và ÿѭӧc xoá khӓi bӝ nhӟ, không gian bӝ nhӟ trӕng bӏ phân rã thành nhӳng mãnh nhӓ. Phân mãnh ngoài tӗn tҥi khi tәng không gian bӝ nhӟÿӫÿӇ thoҧ mãn mӝt yêu cҫu, nhѭng nó không liên tөc; vùng lѭu trӳ bӏ phân mãnh thành mӝt sӕ lѭӧng lӟn các lӛ nhӓ. Vҩn ÿӅ phân mãnh này có thӇ rҩt lӟn. Trong trѭӡng hӧp xҩu nhҩt, chúng có thӇ có mӝt khӕi bӝ nhӟ trӕng nҵm giӳa mӛi hai quá trình. NӃu tҩt cҧ bӝ nhӟ này nҵm trong mӝt khӕi trӕng lӟn, chúng ta có thӇ chҥy nhiӅu quá trình hѫn. Chӑn lӵa first-fit so vӟi best-fit có thӇҧnh hѭӣng tӟi lѭӧng phân mãnh. (First- fit là tӕt hѫn ÿӕi vӟi mӝt sӕ hӋ thӕng, ngѭӧc lҥi best fit là tӕt hѫn cho mӝt sӕ hӋ thӕng khác). Mӝt yӃu tӕ khác là phҫn cuӕi cӫa khӕi trӕng nào ÿѭӧc cҩp phát. (phҫn còn dѭ nào-phҫn trên ÿӍnh, hay phҫn ӣ dѭӟi ÿáy?). Vҩn ÿӅ không do giҧi thuұt nào ÿѭӧc dùng mà do phân mãnh ngoài. V.5 Quҧn lý bӝ nhӟ vӟi hӋ thӕng bҥn thân Nhѭ ta ÿã thҩy trong phҫn trѭӟc, viӋc quҧn lý các lӛ hәng trên nhӳng bҧng liӋt kê ÿѭӧc sҳp xӃp theo kích thѭӟc làm cho viӋc cҩp phát bӝ nhӟ rҩt nhanh, nhѭng lҥi làm chұm cho viӋc ngѭng cҩp phát bӣi vì ta phҧi chú ý ÿӃn các láng giӅng. HӋ thӕng bҥn thân (Buddy System) là mӝt giҧi thuұt quҧn lý bӝ nhӟ tұn dөng thuұn lӧi cӫa viӋc máy tính dùng nhӳng sӕ nhӏ phân cho viӋc ÿánh ÿӏa chӍÿӇ tăng tӕc ÿӝ kӃt hӧp nhӳng lӛ hәng sát nhau khi mӝt quá trình hoàn thành hoһc ÿѭӧc hoán vӏ ra ngoài. Vӟi phѭѫng pháp này, bӝ quҧn lý bӝ nhӟ sӁ có mӝt bҧng liӋt kê nhӳng khӕi còn tӵ do có kích thѭӟc 1, 2, 4, 16 bytes ÿӃn kích thѭӟc cӫa bӝ nhӟ, tӭc là có kích thѭӟc bҵng lǊy thӯa cӫa 2. Khi có mӝt quá trình cҫn cҩp phát bӝ nhӟ, mӝt lӛ hәng có kích thѭӟc bҵng luӻ thӯa cӫa 2 ÿӫ chӭa quá trình sӁÿѭӧc cҩp phát. NӃu không có lӛ hәng yêu cҫu, các lӛ hәng sӁÿѭӧc phân ÿôi cho ÿӃn khi có ÿѭӧc lӛ hӛng cҫn thiӃt. Khi mӝt quá trình chҩm dӭt, các lӛ hәng kӃ nhau có kích thѭӟc bҵng nhau sӁÿѭӧc nhұp lҥi ÿӇ tҥo thành lӛ hәng lӟn hѫn. Do ÿó, giҧi thuұt này ÿѭӧc gӑi là hӋ thӕng bҥn thân. Thí du: vӟi bӝ nhӟ 1M, cҫn phҧi có 21 bҧng liӋt kê nhѭ thӃ sҳp tӯ 1 bytes (20) ÿӃn 1 byte (220). Khӣi ÿҫu toàn bӝ bӝ nhӟ còn tӵ do và bҧng liӋt kê 1M có mӝt mөc tӯ ÿӝc nhҩt chӭa ÿӵng mӝt lӛ hәng 1M, tҩt cҧ các bҧng liӋt kê khác ÿӅu rӛng. Cҩu hình bӝ nhӟ lúc khӣi ÿҫu ÿѭӧc chӍ ra trong hình VII-11. Memory 0 128 K 256 K 384 K 512K 640 K 768 K 896 K 1M Initially 1 Hole request 70 A 128 256 512 3 request 35 A B 64 256 512 3 request 80 A B 64 C 128 512 3 return A 128 B 64 C 128 512 4 Biên soҥn: Th.s NguyӉn Phú Trѭӡng - 09/2005 Trang 149
Ĉҥi Hӑc Cҫn Thѫ - Khoa Công NghӋ Thông Tin - Giáo Trình HӋĈiӅu Hành – V1.0 request 60 128 B D C 128 512 4 return B 128 64 D C 128 512 4 return D 256 C 128 512 3 return C 1024 1 Hình 0-11HӋ thӕng bҥn thân vӟi kích thѭӟc 1M Bây giӡ chúng ta hãy xem cách hӋ thӕng buddy làm viӋc khi mӝt quá trình 70K ÿѭӧc hoán vӏ vào bӝ nhӟ trӕng 1M. Do nhӳng lӛ hәng chӍ có thӇ có kích thѭӟc là lǊy thӯa cӫa 2, 128K sӁÿѭӧc yêu cҫu, bӣi vì ÿó chính là lǊy thӯa nhӓ nhҩt cӫa 2 ÿӫ lӟn. Không có khӕi 128K sҹn, cǊng không có các khӕi 256K và 512K. Vì vұy khӕi 1M sӁÿѭӧc chia làm hai khӕi 512K, ÿѭӧc gӑi là nhӳng bҥn thân; mӝt tҥi ÿӏa chӍ 0 và mӝt tҥi ÿӏa chӍ 512K. Sau ÿó khӕi tҥi ÿӏa chӍ thҩp hѫn, chính là khӕi tҥi 0 lҥi ÿѭӧc phân làm hai khӕi bҥn thân 256K, mӝt tҥi 0 và mӝt tҥi 256K. Cái thҩp hѫn cӫa chúng lҥi ÿѭӧc phân làm hai khӕi 128K, và khӕi tҥi 0, ÿánh dҩu là A trong hình ÿѭӧc cҩp phát cho quá trình. KӃÿӃn, mӝt quá trình 35K ÿѭӧc hoán vӏ vào. Khi ÿó ta cҫn khӕi 64K, nhѭng cǊng không có sҹn, vì thӃ phҧi phân phӕi khӕi 128K thành hai khӕi bҥn thân 64K, mӝt tҥi ÿӏa chӍ 128K, mӝt tҥi 192K. Khӕi tҥi 128K ÿѭӧc cҩp cho quá trình, trong hình là B. Yêu cҫu thӭ ba là 80K. Bây giӡ ta hãy xem nhӳng gì xҧy ra khi mӝt khӕi ÿѭӧc trҧ lҥi. Giҧ sӱ tҥi thӡi ÿiӇm này khӕi 128K (mà chӍ dùng có 70K) ÿѭӧc tӵ do. Khi ÿó khӕi 128K sӁÿѭӧc ÿѭa vào bҧng tӵ do. Bây giӡ cҫn mӝt khӕi 60K. Sau khi kiӇm tra, khӕi 64K tҥi 192K ÿѭӧc cҩp phát và nó ÿѭӧc ÿánh dҩu là C. Bây giӡ khӕi B ÿѭӧc trҧ lҥi. Tҥi thӡi ÿiӇm này có hai khӕi 128K tӵ do nhѭng chúng không ÿѭӧc kӃt hӧp lҥi. Chú ý rҵng ngay cҧ khi khӕi 128K tҥi 0 ÿѭӧc phân ra làm 2, khӕi tҥi 9 ÿѭӧc dùng và khӕi tҥi 84K còn tӵ do, sӵ kӃt hӧp cǊng không xãy ra. Khi D ÿѭӧc trҧ lҥi, sӁ có sӵ kӃt hӧp lҥi thành khӕi 256K tҥi 0. Cuӕi cùng, khi C ÿѭӧc trҧ lҥi, sӁ có kӃt hӧp tҥo thành 1 lӛ hәng 1M nhѭ ban ÿҫu. HӋ thӕng bҥn thân có sӵ thuұn lӧi so vӟi nhӳng giҧi thuұt cùng sҳp xӃp theo kích thѭӟc cӫa khӕi. Sӵ thuұn lӧi này là khi có mӝt khӕi 2k bytes tӵ do, bӝ quҧn lý bӝ nhӟ chӍ cҫn tìm trong bҧng liӋt kê lӛ hәng có kích thѭӟc 2k ÿӇ xem chúng có khҧ năng kӃt hӧp ÿѭӧc hay không. Vӟi nhӳng giҧi thuұt khác mà trong ÿó cho phép các khӕi bӝ nhӟÿѭӧc phân chia mӝt cách tùy ý, viӋc tìm kiӃm phҧi diӉn ra trên tҩt cҧ các bҧng liӋt kê. Do dó, hӋ thӕng bҥn thân làm viӋc nhanh hѫn. Ĉáng tiӃc, nó lҥi cӵc kǤ kém hiӋu quҧ trong viӋc sӱ dөng bӝ nhӟ. Mӝt quá trình 35K phҧi ÿѭӧc cҩp phát ÿӃn 64K, hao phí ÿӃn 29K. Sӵ hao phí này ÿѭӧc gӑi là sӵ phân mҧnh trong (internal fragmentation), bӣi vì phҫn bӝ nhӟ hao phí nҵm bên trong ÿoҥn ÿѭӧc cҩp phát. Còn trong các phҫn trѭӟc ta thҩy nhӳng lӛ hәng ӣ giӳa các ÿoҥn, nhѭng không có sӵ hao phí bên trong các ÿoҥn, do ÿó kiӇu này ÿѭӧc coi là sӵ phân mҧnh ngoài. Biên soҥn: Th.s NguyӉn Phú Trѭӡng - 09/2005 Trang 150
Ĉҥ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.6 Phân mãnh Phân mãnh bӝ nhӟ có thӇ là phân mãnh trong hoһc phân mãnh ngoài. Xét cѫ chӃ cҩp phát nhiӅu phân khu vӟi mӝt lӛ trӕng có kích thѭӟc 18,464 bytes. Giҧ sӱ rҵng quá trình tiӃp theo yêu cҫu 18,462 bytes. NӃu chúng ta cҩp phát chính xác khӕi ÿѭӧc yêu cҫu, chúng ta ÿӇ lҥi mӝt lӛ trӕng có kích thѭӟc 2 bytes. Chi phí ÿӇ giӳ vӃt cӫa lӛ này sӁ lӟn hѫn kích thѭӟc cӫa lӛ trӕng. TiӃp cұn thông thѭӡng là chia bӝ nhӟ vұt lý thành nhӳng khӕi có kích thѭӟc cӕÿӏnh, và cҩp phát bӝ nhӟ dӵa theo ÿѫn vӏ cӫa kích thѭӟc khӕi. Vӟi tiӃp cұn này, bӝ nhӟÿѭӧc cҩp phát tӟi mӝt quá trình có thӇ là lӟn hѫn mӝt chút so vӟi khӕi ÿѭӧc yêu cҫu. Sӵ chênh lӋnh giӳa hai sӕ này là phân mãnh trong-bӝ nhӟ bӏ phân mãnh trong ÿӕi vӟi mӝt phân khu thì không thӇÿѭӧc dùng. Mӝt giҧi pháp ÿӕi vӟi phân mãnh ngoài là kӃt lҥi thành khӕi (compaction). Mөc tiêu là di chuyӇn nӝi dung bӝ nhӟÿӇÿһt tҩt cҧ bӝ nhӟ trӕng vӟi nhau trong mӝt khӕi lӟn. KӃt khӕi không phҧi luôn thӵc hiӋn ÿѭӧc. NӃu viӋc tái ÿӏnh vӏ là tƭnh và ÿѭӧc thӵc hiӋn tҥi thӡi ÿiӇm hӧp dӏch và nҥp thì viӋc kӃt khӕi là không thӇ thӵc hiӋn ÿѭӧc. KӃt khӕi chӍ có thӇ thӵc hiӋn ÿѭӧc chӍ nӃu tái ÿӏnh vӏ là ÿӝng và ÿѭӧc thӵc hiӋn tҥi thӡi ÿiӇm thӵc thi. NӃu ÿӏa chӍÿѭӧc tái ÿӏnh vӏÿӝng, tái ÿӏnh vӏ yêu cҫu chӍ di chuyӇn chѭѫng trình và dӳ liӋu, sau ÿó thay ÿәi thanh ghi nӅn ÿӇ phҧn ánh ÿӏa chӍ nӅn mӟi. Khi kӃt khӕi là có thӇ, chúng ta phҧi xác ÿӏnh chi phí cӫa nó. Giҧi thuұt kӃt khӕi ÿѫn giҧn nhҩt là di chuyӇn tҩt cҧ quá trình tӟi cuӕi bӝ nhӟ; tҩt cҧ lӛ trӕng di chuyӇn theo hѭӟng ngѭӧc lҥi, tҥo ra mӝt lӛ trӕng lӟn cӫa bӝ nhӟ sҷn dùng. Cѫ chӃ này có thӇ ÿҳt. Mӝt giҧi pháp khác cho vҩn ÿӅ phân mãnh ngoài là cho phép không gian ÿӏa chӍ luұn lý cӫa mӝt quá trình là không liên tөc, do ÿó cho phép mӝt quá trình ÿѭӧc cҩp phát bӝ nhӟ vұt lý bҩt cӭÿâu sau khi sҷn dùng. Hai kӻ thuұt bù trӯÿӇÿҥt giҧi pháp này là phân trang và phân ÿoҥn. VI Cҩp phát không liên tөc VI.1 Phân trang Phân trang là cѫ chӃ quҧn lý bӝ nhӟ cho phép không gian ÿӏa chӍ vұt lý cӫa quá trình là không kӅ nhau. Phân trang tránh vҩn ÿӅ ÿһt vӯa khít nhóm bӝ nhӟ có kích thѭӟc thay ÿәi vào vùng lѭu trӳ phө (backing store) mà hҫu hӃt các cѫ chӃ quҧn lý bӝ nhӟ trѭӟc ÿó gһp phҧi. Khi phân ÿoҥn mã và dӳ liӋu nҵm trong bӝ nhӟÿѭӧc hoán vӏ ra, không gian phҧi ÿѭӧc tìm thҩy trên vùng lѭu trӳ phө. Vҩn ÿӅ phân mãnh ÿѭӧc thҧo luұn trong sӵ kӃt nӕi vӟi bӝ nhӟ chính cǊng thông dөng nhѭ vӟi vùng lѭu trӳ phө, ngoҥi trӯ truy xuҩt thҩp hѫn nhiӅu, vì thӃ kӃt khӕi là không thӇ. Vì lӧi ÿiӇm cӫa nó so vӟi các phѭѫng pháp trѭӟc ÿó nên phân trang trong nhӳng dҥng khác nhau ÿѭӧc dùng phә biӃn trong hҫu hӃt các hӋÿiӅu hành. VӅ truyӅn thӕng, hӛ trӧ phân trang ÿѭӧc quҧn lý bӣi phҫn cӭng. Tuy nhiên, nhӳng thiӃt kӃ gҫn ÿây cài ÿһt phân trang bҵng cách tích hӧp chһt chҿ phҫn cӭng và hӋÿiӅu hành, ÿһc biӋt trên các bӝ vi xӱ lý 64-bit. Biên soҥn: Th.s NguyӉn Phú Trѭӡng - 09/2005 Trang 151
Ĉҥi Hӑc Cҫn Thѫ - Khoa Công NghӋ Thông Tin - Giáo Trình HӋĈiӅu Hành – V1.0 VI.1.1 Phѭѫng pháp cѫ bҧn Hình 0-12 Phҫn cӭng phân trang Bӝ nhӟ vұt lý ÿѭӧc chia thành các khӕi có kích thѭӟc cӕÿӏnh ÿѭӧc gӑi là các khung (frames). Bӝ nhӟ luұn lý cǊng ÿѭӧc chia thành các khӕi có cùng kích thѭӟc ÿѭӧc gӑi là các trang (pages). Khi mӝt quá trình ÿѭӧc thӵc thi, các trang cӫa nó ÿѭӧc nҥp vào các khung bӝ nhӟ sҷn dùng tӯ vùng lѭu trӳ phө. Vùng lѭu trӳ phөÿѭӧc chia thành các khӕi có kích thѭӟc cӕÿӏnh và có cùng kích thѭӟc nhѭ các khung bӝ nhӟ. Hӛ trӧ phҫn cӭng cho phân trang ÿѭӧc hiӇn thӏ trong hình VII-12. Mӛi ÿӏa chӍ ÿѭӧc tҥo ra bӣi CPU ÿѭӧc chia thành hai phҫn: sӕ trang (p) và ÿӝ dӡi trang (d). Sӕ trang ÿѭӧc dùng nhѭ chӍ mөc vào bҧng trang. Bҧng trang chӭa ÿӏa chӍ nӅn cӫa mӛi trang trong bӝ nhӟ vұt lý. Ĉӏa chӍ nӅn này ÿѭӧc kӃt hӧp vӟi ÿӝ dӡi trang ÿӇ ÿӏnh nghƭa ÿӏa chӍ bӝ nhӟ vұt lý mà nó ÿѭӧc gӣi ÿӃn ÿѫn vӏ bӝ nhӟ. Mô hình phân trang bӝ nhӟÿѭӧc hiӇn thӏ nhѭ hình VII-13. Kích thѭӟc trang (giӕng nhѭ kích thѭӟc khung) ÿѭӧc ÿӏnh nghƭa bӣi phҫn cӭng. Kích thѭӟc cӫa mӝt trang ÿiӇn hình là luӻ thӯa cӫa 2, tӯ 512 bytes ÿӃn 16MB trên trang, phө thuӝc vào kiӃn trúc máy tính. Chӑn luӻ thӯa 2 cho kích thѭӟc trang thӵc hiӋn viӋc dӏch ÿӏa chӍ luұn lý thành sӕ trang và ÿӝ dӡi trang rҩt dӉ dàng. NӃu kích thѭӟc không gian ÿӏa chӍ là 2m, và kích thѭӟc trang là 2n ÿѫn vӏÿӏa chӍ (byte hay tӯ) thì m-n bits cao cӫa ÿӏa chӍ luұn lý chӍ sӕ trang, n bits thҩp chӍÿӝ dӡi trang. Do ÿó, ÿӏa chӍ luұn lý nhѭ sau: Sӕ trang Ĉӝ dӡi trang PD m –n N ӣÿây p là chӍ mөc trong bҧng trang và d là ÿӝ dӡi trong trang. Biên soҥn: Th.s NguyӉn Phú Trѭӡng - 09/2005 Trang 152
Ĉҥ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-13 Mô hình phân trang cӫa bӝ nhӟ luұn lý và vұt lý Thí dө: xét bӝ nhӟ trong hình VII-14. Sӱ dөng kích thѭӟc trang 4 bytes và bӝ nhӟ vұt lý 32 bytes (có 8 trang), chúng ta hiӇn thӏ cách nhìn bӝ nhӟ cӫa ngѭӡi dùng có thӇÿѭӧc ánh xҥ tӟi bӝ nhӟ vұt lý nhѭ thӃ nào. Ĉӏa chӍ luұn lý 0 là trang 0, ÿӝ dӡi 0. ChӍ mөc trong bҧng trang, chúng ta thҩy rҵng trang 0 ӣ trong khung 5. Do ÿó, ÿӏa chӍ luұn lý 0 ánh xҥ tӟi ÿӏa chӍ vұt lý 20 (=(5x4)+0). Ĉӏa chӍ luұn lý 3 (trang 0, ÿӝ dӡi 3) ánh xҥ tӟi ÿӏa chӍ vұt lý 23 (=(5x4)+3). Ĉӏa chӍ luұn lý 4 ӣ trang 1, ÿӝ dӡi 0; dӵa theo bҧng trang, trang 1 ÿѭӧc ánh xҥ tӟi khung 6. Do ÿó, ÿӏa chӍ luұn lý 4 ánh xҥ tӟi ÿӏa chӍ 24(=(6x4)+0). Ĉӏa chӍ luұn lý 13 ánh xҥ tӟi ÿӏa chӍ vұt lý 9. Có thӇ chú ý rҵng phân trang là mӝt dҥng cӫa tái ÿӏnh vӏÿӝng. Mӛi ÿӏa chӍ luұn lý ÿѭӧc giӟi hҥn bӣi phҫn cӭng phân trang tӟi ÿӏa chӍ vұt lý. Sӱ dөng phân trang tѭѫng tӵ sӱ dөng mӝt bҧng các thanh ghi nӅn (hay tái ÿӏnh vӏ), mӝt thanh ghi cho mӛi khung bӝ nhӟ. Khi chúng ta sӱ dөng mӝt cѫ chӃ phân trang, chúng ta không có phân mãnh bên ngoài: bҩt kǤ khung trӕng có thӇÿѭӧc cҩp phát tӟi mӝt quá trình cҫn nó. Tuy nhiên, chúng ta có thӇ có phân mãnh trong. Chú ý rҵng các khung ÿѭӧc cҩp phát nhѭ các ÿѫn vӏ. NӃu các yêu cҫu bӝ nhӟ cӫa mӝt quá trình không xҧy ra ÿӇ rѫi trên giӟi hҥn cӫa trang, thì khung cuӕi cùng ÿѭӧc cҩp phát có thӇ không ÿҫy hoàn toàn. Thí dө, nӃu các trang là 2048 bytes, mӝt quá trình 72,766 bytes sӁ cҫn 35 trang cӝng vӟi 1086 bytes. Nó ÿѭӧc cҩp phát 36 khung, do ÿó phân mãnh trong là 2048 - 1086 = 962 bytes. Trong trѭӡng hӧp xҩu nhҩt, mӝt quá trình cҫn n trang cӝng vӟi 1 byte. Nó sӁ ÿѭӧc cҩp phát n+1 khung, dүn ÿӃn phân mãnh trong gҫn nhѭ toàn bӝ khung. NӃu kích thѭӟc quá trình ÿӝc lұp vӟi kích thѭӟc cӫa trang, thì chúng ta mong muӕn phân mãnh trong trung bình là ½ trang trên mӝt quá trình. Xem xét này ÿӅ nghӏ rҵng kích thѭӟc trang nhӓ là mong muӕn. Tuy nhiên, chi phí liên quan tӟi mӛi mөc tӯ bҧng trang và chi phí này giҧm khi kích thѭӟc trang tăng. Vì thӃ nhұp/xuҩt ÿƭa là hiӋu quҧ hѫn khi sӕ lѭӧng dӳ liӋu ÿѭӧc truyӅn lӟn hѫn. Thѭӡng thì kích thѭӟc trang lӟn lên theo thӡi gian khi các quá trình, tұp hӧp dӳ liӋu, bӝ nhӟ chính trӣ nên lӟn hѫn. Ngày nay, các trang ÿiӇn hình nҵm trong khoҧng 4 KB tӟi 8 KB, và mӝt sӕ hӋ thӕng hӛ trӧ kích thѭӟc trang lӟn hѫn. CPU và nhân thұm chí hӛ trӧ nhiӅu kích thѭӟc khác Biên soҥn: Th.s NguyӉn Phú Trѭӡng - 09/2005 Trang 153
Ĉҥi Hӑc Cҫn Thѫ - Khoa Công NghӋ Thông Tin - Giáo Trình HӋĈiӅu Hành – V1.0 nhau. Thí dө, Solaris dùng 8 KB và 4 MB kích thѭӟc trang, phө thuӝc dӳ liӋu ÿѭӧc lѭu bӣi trang. HiӋn nay, các nhà nghiên cӭu ÿang phát triӇn viӋc hӛ trӧ kích thѭӟc trang khác nhau. Mӛi mөc tӯ bҧng trang thѭӡng dài 4 bytes, nhѭng kích thѭӟc có thӇ thay ÿәi. Mӝt mөc tӯ 32-bit có thӇ chӍ tӟi mӝt khung trang vұt lý 232. NӃu mӝt khung là 4 KB, thì hӋ thӕng vӟi nhӳng mөc tӯ 4 bytes có thӇÿánh ÿӏa chӍ cho 244 bytes (hay 16 TB) bӝ nhӟ vұt lý. Khi mӝt quá trình ÿi vào hӋ thӕng ÿӇ ÿѭӧc thӵc thi, kích thѭӟc cӫa nó, ÿѭӧc diӉn tҧ trong các trang, ÿѭӧc xem xét. Mӛi trang cӫa quá trình cҫn trên mӝt khung. Do ÿó, nӃu quá trình yêu cҫu n trang, ít nhҩt n khung phҧi sҷn dùng trong bӝ nhӟ. NӃu n khung là sҷn dùng, chúng ÿѭӧc cҩp phát tӟi quá trình ÿang ÿi vào này. Trang ÿҫu tiên cӫa quá trình ÿѭӧc nҥp vào mӝt trong nhӳng khung ÿѭӧc cҩp phát, và sӕ khung ÿѭӧc ÿһt vào trong bҧng trang cho quá trình này. Trang kӃ tiӃp ÿѭӧc nҥp vào mӝt khung khác, và sӕ khung cӫa nó ÿѭӧc ÿһt vào trong bҧng trang, (hình VII-15). Hình 0-14 Thí dө phân trang cho bӝ nhӟ 32 bytes vӟi các trang có kích thӭc 4 bytes Mӝt khía cҥnh quan trӑng cӫa phân trang là sӵ phân chia rõ ràng giӳa tҫm nhìn bӝ nhӟ cӫa ngѭӡi dùng và bӝ nhӟ vұt lý thұt sӵ. Chѭѫng trình ngѭӡi dùng nhìn bӝ nhӟ nhѭ mӝt không gian liên tөc, chӭa chӍ mӝt chѭѫng trình. Sӵ thұt, chѭѫng trình ngѭӡi dùng ÿѭӧc phân bӕ khҳp bӝ nhӟ vұt lý mà nó cǊng quҧn lý các quá trình khác. Sӵ khác nhau giӳa tҫm nhìn bӝ nhӟ cӫa ngѭӡi dùng và bӝ nhӟ vұt lý thұt sӵÿѭӧc làm cho tѭѫng thích bӣi phҫn cӭng dӏch ÿӏa chӍ. Ĉӏa chӍ luұn lý ÿѭӧc dӏch thành ÿӏa chӍ vұt lý. Ánh xҥ này ÿѭӧc che giҩu tӯ ngѭӡi dùng và ÿѭӧc ÿiӅu khiӇn bӣi hӋÿiӅu hành. Chú ý rҵng nhѭÿӏnh nghƭa, quá trình ngѭӡi dùng không thӇ truy xuҩt bӝ nhӟ mà nó Biên soҥn: Th.s NguyӉn Phú Trѭӡng - 09/2005 Trang 154
Ĉҥi Hӑc Cҫn Thѫ - Khoa Công NghӋ Thông Tin - Giáo Trình HӋĈiӅu Hành – V1.0 không sӣ hӳu. Không có cách ÿӏnh ÿӏa chӍ bӝ nhӟ bên ngoài bҧng trang cӫa nó và bҧng chӭa chӍ nhӳng trang mà quá trình sӣ hӳu. Vì hӋÿiӅu hành ÿang quҧn lý bӝ nhӟ vұt lý nên nó phҧi hiӇu nhӳng chi tiӃt cҩp phát bӝ nhӟ vұt lý; khung nào ÿѭӧc cҩp phát, khung nào còn trӕng, tәng khung hiӋn có là bao nhiêu, Thông tin này ÿѭӧc giӳ trong mӝt cҩu trúc dӳ liӋu ÿѭӧc gӑi là bҧng khung. Bҧng khung chӍ có mӝt mөc tӯ cho mӛi khung trang vұt lý, hiӇn thӏ khung trang ÿó ÿang rҧnh hay ÿѭӧc cҩp phát. NӃu khung trang ÿѭӧc cҩp phát, thì xác ÿӏnh trang nào cӫa quá trình nào ÿѭӧc cҩp. Hình 0-15 các khung trӕng. (a) trѭӟc khi cҩp phát. (b) sau khi cҩp phát Ngoài ra, hӋÿiӅu hành phҧi biӃt rҵng quá trình ngѭӡi dùng hoҥt ÿӝng trong không gian ngѭӡi dùng, và tҩt cҧÿӏa chӍ luұn lý phҧi ÿѭӧc ánh xҥÿӇ phát sinh ÿӏa chӍ vұt lý. NӃu ngѭӡi dùng thӵc hiӋn lӡi gӑi hӋ thӕng (thí dө: ÿӇ thӵc hiӋn nhұp/xuҩt) và cung cҩp ÿӏa chӍ nhѭ mӝt tham sӕ (thí dө: vùng ÿӋm), ÿӏa chӍÿó phҧi ÿѭӧc ánh xҥÿӇ sinh ra ÿӏa chӍ vұt lý ÿúng. HӋÿiӅu hành duy trì mӝt bҧn sao cӫa bҧng trang cho mӛi quá trình, nhѭ nó duy trì bҧn sao cӫa bӝÿӃm chӍ thӏ lӋnh và nӝi dung thanh ghi. Bҧn sao này ÿѭӧc dùng ÿӇ dӏch ÿӏa chӍ luұn lý thành ÿӏa chӍ vұt lý bҩt cӭ khi nào hӋÿiӅu hành phҧi ánh xҥÿӏa chӍ luұn lý tӟi ÿӏa chӍ vұt lý dҥng thӫ công. Nó cǊng ÿѭӧc dùng bӣi bӝ phân phát CPU ÿӇ ÿӏa chӍ bҧng trang phҫn cӭng khi mӝt quá trình ÿѭӧc cҩp phát CPU. Do ÿó, trang gia tăng thӡi gian chuyӇn ÿәi ngӳ cҧnh. VI.1.2 Hӛ trӧ phҫn cӭng Mӛi hӋÿiӅu hành có phѭѫng pháp riêng ÿӇ lѭu trӳ các bҧng trang. Hҫu hӃt ÿӅu cҩp phát mӝt bҧng trang cho mӛi quá trình. Mӝt con trӓ chӍ tӟi mӝt bҧng trang ÿѭӧc lѭu trӳ vӟi nhӳng giá trӏ thanh ghi thanh ghi khác nhau (giӕng nhѭ bӝÿӃm chӍ thӏ lӋnh) trong khӕi ÿiӅu khiӇn quá trình. Khi bӝ phân phát ÿѭӧc yêu cҫu bҳt ÿҫu mӝt quá trình, nó phҧi nҥp lҥi các thanh ghi ngѭӡi dùng và ÿӏnh nghƭa các giá trӏ bҧng trang phҫn cӭng phù hӧp tӯ bҧng trang ngѭӡi dùng ÿѭӧc lѭu trӳ. Biên soҥn: Th.s NguyӉn Phú Trѭӡng - 09/2005 Trang 155
Ĉҥi Hӑc Cҫn Thѫ - Khoa Công NghӋ Thông Tin - Giáo Trình HӋĈiӅu Hành – V1.0 Cài ÿһt phҫn cӭng cӫa bҧng trang có thӇÿѭӧc thӵc hiӋn trong nhiӅu cách. Cách ÿѫn giҧn nhҩt, bҧng trang ÿѭӧc cài ÿһt nhѭ tұp hӧp các thanh ghi tұn hiӃn. Các thanh ghi này nên ÿѭӧc xây dӵng vӟi tính logic tӕc ÿӝ rҩt cao ÿӇ thӵc hiӋn viӋc dӏch ÿӏa chӍ trang hiӋu quҧ. Mӑi truy xuҩt tӟi bӝ nhӟ phҧi kiӇm tra kӻ lѭӥng bҧng ÿӗ trang, vì vұy tính hiӋu quҧ là vҩn ÿӅ xem xét chӫ yӃu. Bӝ phân phát CPU nҥp lҥi các thanh ghi này chӍ khi nó nҥp lҥi các thanh ghi khác. Dƭ nhiên, các chӍ thӏÿӇ nҥp hay hiӋu chӍnh các thanh ghi bҧng trang phҧi ÿѭӧc cҩp quyӅn ÿӇ mà chӍ hӋÿiӅu hành có thӇ thay ÿәi bҧn ÿӗ bӝ nhӟ. DEC PDP-11 là mӝt thí dө vӅ kiӃn trúc nhѭ thӃ. Ĉӏa chӍ chӭa 16 bits, và kích thѭӟc trang là 8 KB. Do ÿó, bҧng trang chӭa 8 mөc tӯ mà chúng ÿѭӧc giӳ trong các thanh ghi nhanh. Sӱ dөng các thanh ghi cho bҧng trang chӍ phù hӧp nӃu bҧng trang có kích thѭӟc nhӓ (thí dө: 256 mөc tӯ). Tuy nhiên, hҫu hӃt các máy tính tѭѫng thӡi cho phép bҧng trang rҩt lӟn (thí dө, 1 triӋu mөc tӯ). Ĉӕi vӟi nhӳng máy này, viӋc sӱ dөng các thanh ghi nhanh ÿӇ cài ÿһt bҧng trang là không khҧ thi. Hay ÿúng hѫn là, bҧng trang ÿѭӧc giӳ trong bӝ nhӟ chính, và thanh ghi nӅn bҧng trang (page-table base register- PTBR) chӍ tӟi thanh ghi bҧng trang. Thay ÿәi các bҧng trang yêu cҫu thay ÿәi chӍ mӝt thanh ghi, vӅ căn bҧn cҳt giҧm thӡi gian chuyӇn ngӳ cҧnh. Vҩn ÿӅ vӟi tiӃp cұn này là thӡi gian ÿѭӧc yêu cҫu ÿӇ truy xuҩt vӏ trí bӝ nhӟ ngѭӡi dùng. NӃu chúng ta muӕn truy xuҩt vӏ trí i, ÿҫu tiên chúng ta phҧi xác ÿӏnh chӍ mөc trong bҧng trang, sӱ dөng giá trӏ trong ÿӝ dӡi PTBR bӣi sӕ trang cho i. Tác vө này yêu cҫu mӝt truy xuҩt bӝ nhӟ. Nó cung cҩp chúng ta sӕ khung ÿѭӧc nӕi kӃt vӟi ÿӝ dӡi trang ÿӇ sinh ra ÿӏa chӍ thӵc. Sau ÿó, chúng ta có thӇ truy xuҩt tӟi nѫi ÿѭӧc mong muӕn trong bӝ nhӟ. Vӟi cѫ chӃ này, hai truy xuҩt bӝ nhӟÿѭӧc yêu cҫu ÿӇ truy xuҩt mӝt byte (mӝt cho mөc tӯ bҧng trang, mӝt cho byte ÿó). Do ÿó, truy xuҩt bӝ nhӟ bӏ chұm bӣi mӝt trong hai yӃu tӕÿó. Sӵ trì hoãn này không thӇ chҩp nhұn dѭӟi hҫu hӃt trѭӡng hӧp vì thӃ chúng ta phҧi sӱ dөng ÿӃn hoán vӏ! Giҧi pháp chuҭn cho vҩn ÿӅ này là dùng bӝ lѭu trӳ (cache) phҫn cӭng ÿһc biӋt, nhӓ, tìm kiӃm nhanh ÿѭӧc gӑi là translation look-aside buffer (TLB). TLB là bӝ nhӟ kӃt hӧp tӕc ÿӝ cao. Mӛi mөc tӯ trong TLB chӭa hai phҫn: mӝt khoá (key) và mӝt giá trӏ (value). Khi bӝ nhӟ kӃt hӧp ÿѭӧc biӇu diӉn vӟi mӝt thành phҫn, nó ÿѭӧc so sánh vӟi tҩt cҧ khoá cùng mӝt lúc. NӃu thành phҫn ÿѭӧc tìm thҩy, trѭӡng giá trӏ tѭѫng ӭng ÿѭӧc trҧ vӅ. Tìm kiӃm nhanh nhѭng phҫn cӭng ÿҳt. ĈiӇn hình, sӕ lѭӧng mөc tӯ trong TLB nhӓ, thѭӡng tӯ 64 ÿӃn 1024. TLB ÿѭӧc dùng vӟi các bҧng trang trong cách sau. TLB chӭa chӍ mӝt vài mөc tӯ bҧng trang. Khi mӝt ÿӏa chӍ luұn lý ÿѭӧc phát sinh bӣi CPU, sӕ trang cӫa nó ÿѭӧc hiӋn diӋn trong TLB. NӃu sӕ trang ÿѭӧc tìm thҩy, khung cӫa nó lұp tӭc sҷn dùng và ÿѭӧc dùng ÿӇ truy xuҩt bӝ nhӟ. Toàn bӝ tác vө có thӇ mҩt ít hѫn 10% thӡi gian nӃu dùng tham chiӃu bӝ nhӟ không ÿѭӧc ánh xҥ. NӃu sӕ trang không ӣ trong TLB (còn gӑi là mҩt TLB), tham chiӃu bӝ nhӟ tӟi bҧng trang phҧi ÿѭӧc thӵc hiӋn. Khi sӕ khung ÿҥt ÿѭӧc, chúng ta có thӇ dùng nó ÿӇ truy xuҩt bӝ nhӟ (nhѭ hình VII-16). Ngoài ra, chúng ta thêm sӕ trang và sӕ khung tӟi TLB ÿӇ mà chúng có thӇÿѭӧc tìm thҩy nhanh trên tham chiӃu tiӃp theo. NӃu mӝt TLB ÿã ÿҫy các mөc tӯ, hӋÿiӅu hành phҧi chӑn mӝt mөc tӯÿӇ thay thӃ. Các chính sách thay thӃ rҩt ÿa dҥng tӯ ít ÿѭӧc sӱ dөng gҫn ÿây nhҩt (least recently used-LRU) tӟi chӑn ngүu nhiên. Ngoài ra, mӝt sӕ TLB cho phép các mөc tӯÿѭӧc wired down. Nghƭa là, chúng không thӇÿѭӧc xoá khӓi TLB. ĈiӇn hình, các mөc tӯ cho nhân thѭӡng ÿѭӧc wired down. Mӝt sӕ TLB lѭu trӳ các ÿӏnh danh không gian ÿӏa chӍ (address-space identifers- ASID) trong mӛi mөc tӯ cӫa TLB. Mӝt ASID ÿӏnh danh duy nhҩt mӛi quá trình và ÿѭӧc dùng ÿӇ cung cҩp viӋc bҧo vӋ không gian ÿӏa chӍ cho quá trình ÿó. Khi TLB cӕ Biên soҥn: Th.s NguyӉn Phú Trѭӡng - 09/2005 Trang 156