Giáo trình Nguyên lý hệ điều hành (Phần 2)

Giáo trình Nguyên lý h͏ꢀÿL͉u hành – KS. Trҫn Ngӑc Thái, %͡ môn Tin h͕c – Ĉ̩i h͕c DL H̫i Phòng

CHɈɆNG 3: QUɟN LÝ B͘ NH͚

Ch˱˯ng này sͅ giúp các b̩n hình dung nhͷng v̭n ÿ͉ c̯n quan tâm khi thi͇t k͇ module qu̫n lý b͡ nhͣ

cͯa H͏ꢀÿL͉u hành . M͡t s͙ mô hình t͝ chͱc b͡ nhͣ cǊng ÿ˱ͫc giͣi thi͏u và phân tích ˱u, khuy͇t ÿL͋m

ÿ͋ các b̩n có th͋ hi͋u ÿ˱ͫc cách thͱc c̭p phát và thu h͛i b͡ nhͣ di͍n ra nh˱ th͇ nào

Bӝ nhӟ chính là thiӃt bӏ lѭu trӳ duy nhҩt thông qua ÿó CPU có thӇ trao ÿәi thông tin vӟi môi trѭӡng

ngoài, do vұy nhu cҫu tә chӭc, quҧn lý bӝ nhӟ là mӝt trong nhӳng nhiӋm vө trӑng tâm hàng ÿҫu cӫa hӋ

ÿiӅu hành . Bӝ nhӟ chính ÿѭӧc tә chӭc nhѭ mӝt mҧng mӝt chiӅu các tӯ nhӟ (word), mӛi tӯ nhӟ có mӝt

ÿӏa chӍ . ViӋc trao ÿәi thông tin vӟi môi trѭӡng ngoài ÿѭӧc thӵc hiӋn thông qua các thao tác ÿӑc hoһc

ghi dӳ liӋu vào mӝt ÿӏa chӍ cө thӇ nào ÿó trong bӝ nhӟ.

Hҫu hӃt các hӋꢀÿLӅu hành hiӋn ÿҥi ÿӅu cho phép chӃꢀÿӝꢀÿa nhiӋm nhҵm nâng cao hiӋu suҩt sӱ dөng

CPU. Tuy nhiên kӻ thuұt này lҥi làm nҧy sinh nhu cҫu chia sҿ bӝ nhӟ giӳa các tiӃn trình khác nhau .

Vҩn ÿӅ nҵm ӣ chӛ : « b͡ nhͣ thì hͷu h̩n và các yêu c̯u b͡ nhͣ thì vô h̩n ».

HӋꢀÿLӅu hành chӏu trách nhiӋm cҩp phát vùng nhӟ cho các tiӃn trình có yêu cҫu. ĈӇ thӵc hiӋn tӕt nhiӋm

vө này, hӋꢀÿLӅu hành cҫn phҧi xem xét nhiӅu khía cҥnh :

Sӵ tѭѫng ӭng giӳa ÿӏa chӍ logic và ÿӏa chӍ vұt lý (physic) : làm cách nào ÿӇ chuyӇn ÿәi mӝt ÿӏa chӍ

Wѭӧng trѭng (symbolic) trong chѭѫng trình thành mӝt ÿӏa chӍ thӵc trong bӝ nhӟ chính?

Quҧn lý bӝ nhӟ vұt lý: làm cách nào ÿӇ mӣ rӝng bӝ nhӟ có sҹn nhҵm lѭu trӳꢀÿѭӧc nhiӅu tiӃn trình

ÿӗng thӡi?

Chia sҿ thông tin: làm thӃ nào ÿӇ cho phép hai tiӃn trình có thӇ chia sҿ thông tin trong bӝ nhӟ?

Bҧo vӋ: làm thӃ nào ÿӇ ngăn chһn các tiӃn trình xâm phҥm ÿӃn vùng nhӟꢀÿѭӧc cҩp phát cho tiӃn

trình khác?

Các giҧi pháp quҧn lý bӝ nhӟ phө thuӝc rҩt nhiӅu vào ÿһc tính phҫn cӭng và trҧi qua nhiӅu giai ÿRҥn

cҧi tiӃn ÿӇ trӣ thành nhӳng giҧp pháp khá thӓa ÿáng nhѭ hiӋn nay.

3.1 Bӕi cҧnh

Thông thѭӡng, mӝt chѭѫng trình ÿѭӧc lѭu trӳ trên ÿƭa nhѭ mӝt tұp tin nhӏ phân có thӇ xӱ lý. ĈӇ thӵc

hiӋn chѭѫng trình, cҫn nҥp chѭѫng trình vaò bӝ nhӟ chính, tҥo lұp tiӃn trình tѭѫng ӭng ÿӇ xӱ lý .

Hàng ÿͫi nh̵p h͏ th͙ng là tұp hӧp các chѭѫng trình trên ÿƭa ÿang chӡꢀÿѭӧc nҥp vào bӝ nhӟꢀÿӇ tiӃn

hành xӱ lý.

Các ÿӏa chӍ trong chѭѫng trình nguӗn là ÿӏa chӍ tѭӧng trѭng , vì thӃ, mӝt chѭѫng trình phҧi trҧi qua

nhiӅu giai ÿRҥn xӱ lý ÿӇ chuyӇn ÿәi các ÿӏa chӍ này thành các ÿӏa chӍ tuyӋt ÿӕi trong bӝ nhӟ chính.

Có thӇ thӵc hiӋn kӃt buӝc các chӍ thӏ và dӳ liӋu vӟi các ÿӏa chӍ bӝ nhӟ vào mӝt trong nhӳng thӡi ÿLӇm

sau :

Thӡi ÿLӇm biên dӏch: nӃu tҥi thӡi ÿLӇm biên dӏch, có thӇ biӃt vӏ trí mà tiӃn trình sӁ thѭӡng trú trong bӝ

nhӟ, trình biên dӏch có thӇ phát sinh ngay mã vӟi các ÿӏa chӍ tuyӋt ÿӕi. Tuy nhiên, nӃu vӅ sau có sӵ

thay ÿәi vӏ trí thѭӡng trú lúc ÿҫu cӫa chѭѫng trình, cҫn phҧi biên dӏch lҥi chѭѫng trình.

Tài li͏u l˱u hành n͡i b͡ - 1 -

Giáo trình Nguyên lý h͏ꢀÿL͉u hành – KS. Trҫn Ngӑc Thái, %͡ môn Tin h͕c – Ĉ̩i h͕c DL H̫i Phòng

Thӡi ÿLӇm nҥp : nӃu tҥi thӡi ÿLӇm biên dӏch, chѭa thӇ biӃt vӏ trí mà tiӃn trình sӁ thѭӡng trú trong bӝ

nhӟ, trình biên dӏch cҫn phát sinh mã tѭѫng ÿӕi (translatable). Sӵ liên kӃt ÿӏa chӍꢀÿѭӧc trì hoãn ÿӃn thӡi

ÿiӇm chѭѫng trình ÿѭӧc nҥp vào bӝ nhӟ, lúc này các ÿӏa chӍ tѭѫng ÿӕi sӁꢀÿѭӧc chuyӇn thành ÿӏa chӍ

tuyӋt ÿӕi do ÿã biӃt vӏ trí bҳt ÿҫu lѭu trӳ tiӃn trình. Khi có sӵ thay ÿәi vӏ trí lѭu trӳ, chӍ cҫn nҥp lҥi

chѭѫng trình ÿӇ tính toán lҥi các ÿӏa chӍ tuyӋt ÿӕi, mà không cҫn biên dӏch lҥi.

Thӡi ÿLӇm xӱ lý : nӃu có nhu cҫu di chuyӇn tiӃn trình tӯ vùng nhӟ này sang vùng nhӟ khác trong quá

trình tiӃn trình xӱ lý, thì thӡi ÿLӇm kӃt buӝc ÿӏa chӍ phҧi trì hoãn ÿӃn tұn thӡi ÿLӇm xӱ lý. ĈӇ thӵc hiӋn

kӃt buӝc ÿӏa chӍ vào thӡi ÿLӇm xӱ lý, cҫn sӱ dөng cѫ chӃ phҫn cӭng ÿһc biӋt.

3.2 Không gian ÿӏa chӍ và không gian vұt lý

Mӝt trong nhӳng hѭӟng tiӃp cұn trung tâm nhҵm tә chӭc quҧn lý bӝ nhӟ mӝt cách hiӋu qӫa là ÿѭa ra

khái niӋm không gian ÿӏa chӍꢀÿѭӧc xây dӵng trên không gian nhӟ vұt lý, viӋc tách rӡi hai không gian

này giúp hӋꢀÿLӅu hành dӉ dàng xây dӵng các cѫ chӃ và chiӃn lѭӧc quҧn lý bӝ nhӟ hӳu hiӋu :

Ĉ͓a ch͑ logic – còn gӑi là ÿ͓a ch͑ꢀ̫o , là tҩt cҧ các ÿӏa chӍ do bӝ xӱ lý tҥo ra.

Ĉ͓a ch͑ v̵t lý - là ÿӏa chӍ thӵc tӃ mà trình quҧn lý bӝ nhӟ nhìn thҩy và thao tác.

Không gian ÿ͓a ch͑ – là tұp hӧp tҩt cҧ các ÿӏa chӍ ҧo phát sinh bӣi mӝt chѭѫng trình.

Không gian v̵t lý – là tұp hӧp tҩt cҧ các ÿӏa chӍ vұt lý tѭѫng ӭng vӟi các ÿӏa chӍꢀҧo.

Ĉӏa chӍꢀҧo và ÿӏa chӍ vұt lý là nhѭ nhau trong phѭѫng thӭc kӃt buӝc ÿӏa chӍ vào thӡi ÿLӇm biên dӏch

cǊng nhѭ vào thӡi ÿLӇm nҥp. Nhѭng có sӵ khác biӋt giӳa ÿӏa chӍꢀҧo và ÿӏa chӍ vұt lý trong phѭѫng thӭc

kӃt buӝc vào thӡi ÿLӇm xӱ lý.

MMU (memory-management unit) là mӝt cѫ chӃ phҫn cӭng ÿѭӧc sӱ dөng ÿӇ thӵc hiӋn chuyӇn ÿәi ÿӏa

chӍꢀҧo thành ÿӏa chӍ vұt lý vào thӡi ÿLӇm xӱ lý.

Chѭѫng trình cӫa ngѭӡi sӱ dөng chӍ thao tác trên các ÿӏa chӍꢀҧo, không bao giӡ nhìn thҩy các ÿӏa chӍ

vұt lý . Ĉӏa chӍ thұt sӵꢀӭng vӟi vӏ trí cӫa dӳ liӋu trong bô nhӟ chӍꢀÿѭӧc xác ÿӏnh khi thӵc hiӋn truy xuҩt

ÿӃn dӳ liӋu.

3.3 Cҩp phát liên tөc

3.3.1. Mô hình Linker_Loader

Ý tѭӣng : TiӃn trình ÿѭӧc nҥp vào mӝt vùng nhӟ liên tөc ÿӫ lӟn ÿӇ chӭa toàn bӝ tiӃn trình. Tҥi thӡi

ÿiӇm biên dӏch các ÿӏa chӍ bên trong tiӃn trình vүn là ÿӏa chӍ tѭѫng ÿӕi. Tҥi thӡi ÿLӇm nҥp, HӋꢀÿLӅu

hành sӁ trҧ vӅꢀÿӏa chӍ bҳt ÿҫu nҥp tiӃn trình, và tính toán ÿӇ chuyӇn các ÿӏa chӍ tѭѫng ÿӕi vӅꢀÿӏa chӍ

tuyӋt ÿӕi trong bӝ nhӟ vұt lý theo công thӭc ÿӏa chӍ vұt lý = ÿӏa chӍ bҳt ÿҫu + ÿӏa chӍ tѭѫng ÿӕi.

Tài li͏u l˱u hành n͡i b͡ - 2 -

Giáo trình Nguyên lý h͏ꢀÿL͉u hành – KS. Trҫn Ngӑc Thái, %͡ môn Tin h͕c – Ĉ̩i h͕c DL H̫i Phòng

3.3.2. Mô hình Base &Bound

Ý tѭӣng : TiӃn trình ÿѭӧc nҥp vào mӝt vùng nhӟ liên tөc ÿӫ lӟn ÿӇ chӭa toàn bӝ tiӃn trình. Tҥi thӡi

ÿiӇm biên dӏch các ÿӏa chӍ bên trong tiӃn trình vүn là ÿӏa chӍ tѭѫng ÿӕi. Tuy nhiên bә túc vào cҩu trúc

phҫn cӭng cӫa máy tính mӝt thanh ghi nӅn (base register) và mӝt thanh ghi giӟi hҥn (bound register).

Khi mӝt tiӃn trình ÿѭӧc cҩp phát vùng nhӟ, nҥp vào thanh ghi nӅn ÿӏa chӍ bҳt ÿҫu cӫa phân vùng ÿѭӧc

cҩp phát cho tiӃn trình, và nҥp vào thanh ghi giӟi hҥn kích thѭӟc cӫa tiӃn trình. Sau ÿó, mӛi ÿӏa chӍ bӝ

nhӟꢀÿѭӧc phát sinh sӁ tӵꢀÿӝng ÿѭӧc cӝng vӟi ÿӏa chӍ chӭa trong thanh ghi nӅn ÿӇ cho ra ÿӏa chӍ tuyӋt

ÿӕi trong bӝ nhӟ, các ÿӏa chӍ cǊng ÿѭӧc ÿӕi chiӃu vӟi thanh ghi giӟi hҥn ÿӇ bҧo ÿҧm tiӃn trình không

truy xuҩt ngoài phҥm vi phân vùng ÿѭӧc cҩp cho nó.

Hai thanh ghi hә trӧ chuyӇn ÿәi ÿӏa chӍ

Mӝt ѭu ÿiӇm cӫa viӋc sӱ dөng thanh ghi nӅn là có thӇ di chuyӇn các chѭѫng trình trong bӝ nhӟ sau

khi chúng bҳt ÿҫu xӱ lý, mӛi khi tiӃn trình ÿѭӧc di chuyӇn ÿӃn mӝt vӏ trí mӟi, chӍ cҫn nҥp lҥi giá trӏ

cho thanh ghi nӅn, các ÿӏa chӍ tuyӋt ÿӕi sӁꢀÿѭӧc phát sinh lҥi mà không cҫn cұp nhұt các ÿӏa chӍ tѭѫng

ÿӕi trong chѭѫng trình

Chӏu ÿӵng hiӋn tѭӧng phân mҧnh ngoҥi vi( external fragmentation ) : khi các tiӃn trình lҫn lѭӧt vào

và ra khӓi hӋ thӕng, dҫn dҫn xuҩt hiӋn các khe hӣ giӳa các tiӃn trình. Ĉây là các khe hӣꢀÿѭӧc tҥo ra do

kích thѭӟc cӫa tiӃn trình mӟi ÿѭӧc nҥp nhӓ hѫn kích thѭӟc vùng nhӟ mӟi ÿѭӧc giҧi phóng bӣi mӝt tiӃn

trình ÿã kӃt thúc và ra khӓi hӋ thӕng. HiӋn tѭӧng này có thӇ dүn ÿӃn tình huӕng tәng vùng nhӟ trӕng

ÿӫꢀÿӇ thoҧ mãn yêu cҫu, nhѭng các vùng nhӟ này lҥi không liên tөc ! Ngѭӡi ta có thӇ áp dөng kӻ thuұt

« dӗn bӝ nhӟ » (memory compaction ) ÿӇ kӃt hӧp các mҧnh bӝ nhӟ nhӓ rӡi rҥc thành mӝt vùng nhӟ lӟn

liên tөc. Tuy nhiên, kӻ thuұt này ÿòi hӓi nhiӅu thӡi gian xӱ lý, ngoài ra, sӵ kӃt buӝc ÿӏa chӍ phҧi thӵc

hiӋn vào thӡi ÿLӇm xӱ lý, vì các tiӃn trình có thӇ bӏ di chuyӇn trong quá trình dӗn bӝ nhӟ.

Tài li͏u l˱u hành n͡i b͡ - 3 -

Giáo trình Nguyên lý h͏ꢀÿL͉u hành – KS. Trҫn Ngӑc Thái, %͡ môn Tin h͕c – Ĉ̩i h͕c DL H̫i Phòng

Phân mҧnh ngoҥi vi

Vҩn ÿӅ nҧy sinh khi kích thѭӟc cӫa tiӃn trình tăng trѭӣng trong qúa trình xӱ lý mà không còn vùng

nhӟ trӕng gҫn kӅꢀÿӇ mӣ rӝng vùng nhӟ cho tiӃn trình. Có hai cách giҧi quyӃt:

Dӡi chӛ tiӃn trình : di chuyӇn tiӃn trình ÿӃn mӝt vùng nhӟ khác ÿӫ lӟn ÿӇ thӓa mãn nhu cҫu tăng

trѭӣng cӫa tiӃn trình.

Cҩp phát dѭ vùng nhӟ cho tiӃn trình : cҩp phát dӵ phòng cho tiӃn trình mӝt vùng nhӟ lӟn hѫn yêu cҫu

ban ÿҫu cӫa tiӃn trình.

Mӝt tiӃn trình cҫn ÿѭӧc nҥp vào bӝ nhӟꢀÿӇ xӱ lý. Trong các phѭѫng thӭc tә chӭc trên ÿây, mӝt tiӃn

trình luôn ÿѭӧc lѭu trӳ trong bӝ nhӟ suӕt quá trình xӱ lý cӫa nó. Tuy nhiên, trong trѭӡng hӧp tiӃn trình

bӏ khóa, hoһc tiӃn trình sӱ dөng hӃt thӡi gian CPU dành cho nó, nó có thӇꢀÿѭӧc chuyӇn tҥm thӡi ra bӝ

nhӟ phө và sau này ÿѭӧc nҥp trӣ lҥi vào bӝ nhӟ chính ÿӇ tiӃp tөc xӱ lý.

Các cách tә chӭc bӝ nhӟ trên ÿây ÿӅu phҧi chӏu ÿӵng tình trҥng bӝ nhӟ bӏ phân mҧnh vì chúng ÿӅu

tiӃp cұn theo kiӇu cҩp phát mӝt vùng nhӟ liên tөc cho tiӃn trình. Nhѭꢀÿã thҧo luұn, có thӇ sӱ dөng kӻ

thuұt dӗn bӝ nhӟꢀÿӇ loҥi bӓ sӵ phân mҧnh ngoҥi vi, nhѭng chi phí thӵc hiӋn rҩt cao. Mӝt giҧi pháp

khác hӳu hiӋu hѫn là cho phép không gian ÿӏa chӍ vұt lý cӫa tiӃn trình không liên tөc, nghƭa là có thӇ

cҩp phát cho tiӃn trình nhӳng vùng nhӟ tӵ do bҩt kǤ, không cҫn liên tөc.

3.4. Cҩp phát không liên tөc

3.4.1. Phân ÿoҥn (Segmentation)

Ý tѭӣng: quan niӋm không gian ÿӏa chӍ là mӝt tұp các phân ÿo̩n (segments) – các phân ÿoҥn là

nhӳng phҫn bӝ nhӟ kích th˱ͣc khác nhau và có liên h͏ logic vͣi nhau. Mӛi phân ÿRҥn có mӝt tên gӑi

(sӕ hiӋu phân ÿRҥn) và mӝt ÿӝ dài. Ngѭӡi dùng sӁ thiӃt lұp mӛi ÿӏa chӍ vӟi hai giá trӏ : <s͙ hi͏u phân

ÿo̩n, offset>.

Tài li͏u l˱u hành n͡i b͡ - 4 -

Giáo trình Nguyên lý h͏ꢀÿL͉u hành – KS. Trҫn Ngӑc Thái, %͡ môn Tin h͕c – Ĉ̩i h͕c DL H̫i Phòng

Hình 4.17 Mô hình phân ÿoҥn bӝ nhӟ

&ѫ chӃ MMU trong kӻ thuұt phân ÿRҥn:

Cҫn phҧi xây dӵng mӝt ánh xҥꢀÿӇ chuyӇn ÿәi các ÿӏa chӍ 2 chiӅu ÿѭӧc ngѭӡi dùng ÿӏnh nghƭa thành ÿӏa

chӍ vұt lý mӝt chiӅu. Sӵ chuyӇn ÿәi này ÿѭӧc thӵc hiӋn qua mӝt b̫ng phân ÿR̩n. Mӛi thành phҫn

trong bҧng phân ÿRҥn bao gӗm mӝt thanh ghi n͉n và mӝt thanh ghi giͣi h̩n. Thanh ghi nӅn lѭu trӳꢀÿӏa

chӍ vұt lý nѫi bҳt ÿҫu phân ÿRҥn trong bӝ nhӟ, trong khi thanh ghi giӟi hҥn ÿһc tҧ chiӅu dài cӫa phân

ÿoҥn.

ChuyӇn ÿәi ÿӏa chӍ:

Mӛi ÿӏa chӍꢀҧo là mӝt bӝ <s,d> :

s͙ hi͏u phân ÿo̩n s : ÿѭӧc sӱ dөng nhѭ chӍ mөc ÿӃn bҧng phân ÿRҥn

ÿ͓a ch͑ t˱˯ng ÿ͙i d : có giá trӏ trong khoҧng tӯ 0 ÿӃn giӟi hҥn chiӅu dài cӫa phân ÿRҥn. NӃu ÿӏa chӍ

Wѭѫng ÿӕi hӧp lӋ, nó sӁꢀÿѭӧc cӝng vӟi giá trӏ chӭa trong thanh ghi nӅn ÿӇ phát sinh ÿӏa chӍ vұt lý tѭѫng

ӭng.

Hình 4.18 Cѫ chӃ phҫn cӭng hә trӧ kƭ thuұt phân ÿoҥn

Tài li͏u l˱u hành n͡i b͡ - 5 -

Giáo trình Nguyên lý h͏ꢀÿL͉u hành – KS. Trҫn Ngӑc Thái, %͡ môn Tin h͕c – Ĉ̩i h͕c DL H̫i Phòng

Hình 4.19 HӋ thӕng phân ÿRҥn

Cài ÿһt bҧng phân ÿoҥn:

Có thӇ sӱ dөng các thanh ghi ÿӇ lѭu trӳ bҧng phân ÿRҥn nӃu sӕ lѭӧng phân ÿRҥn nhӓ. Trong trѭӡng

hӧp chѭѫng trình bao gӗm quá nhiӅu phân ÿRҥn, bҧng phân ÿRҥn phҧi ÿѭӧc lѭu trong bӝ nhӟ chính.

Mӝt thanh ghi n͉n b̫ng phân ÿR̩n (STBR) chӍꢀÿӃn ÿӏa chӍ bҳt ÿҫu cӫa bҧng phân ÿRҥn. Vì sӕ lѭӧng

phân ÿoҥn sӱ dөng trong mӝt chѭѫng trình biӃn ÿӝng, cҫn sӱ dөng thêm mӝt thanh ghi ÿ̿c t̫ kích

th˱ͣc b̫ng phân ÿR̩n (STLR).

Vӟi mӝt ÿӏa chӍ logic <s,d>, trѭӟc tiên sӕ hiӋu phân ÿRҥn sꢀÿѭӧc kiӇm tra tính hӧp lӋ (s <STLR). KӃ

tiӃp, cӝng giá trӏ s vӟi STBR ÿӇ có ÿѭӧc ÿӏa chӍꢀÿӏa chӍ cӫa phҫn tӱ thӭ s trong bҧng phân ÿRҥn

(STBR+s). Ĉiҥ chӍ vұt lý cuӕi cùng là (STBR+s + d)

Hình 4.20 Sӱ dөng STBR, STLR và bҧng phân ÿRҥn

Bҧo vӋ: Mӝt ѭu ÿiӇm ÿһc biӋt cӫa cѫ chӃ phân ÿRҥn là khҧ năng ÿһc tҧ thuӝc tính bҧo vӋ cho mӛi

phân ÿoҥn. Vì mӛi phân ÿRҥn biӉu diӉn cho mӝt phҫn cӫa chѭѫng trình vӟi ngӳ nghƭa ÿѭӧc ngѭӡi

dùng xác ÿӏnh, ngѭӡi sӱ dөng có thӇ biӃt ÿѭӧc mӝt phân ÿRҥn chӭa ÿӵng nhӳng gì bên trong, do vұy

hӑ có thӇꢀÿһc tҧ các thuӝc tính bҧo vӋ thích hӧp cho tӯng phân ÿRҥn.

&ѫ chӃ phҫn cӭng phө trách chuyӇn ÿәi ÿӏa chӍ bӝ nhӟ sӁ kiӇm tra các bit bҧo vӋꢀÿѭӧc gán vӟi mӛi

phҫn tӱ trong bҧng phân ÿRҥn ÿӇ ngăn chһn các thao tác truy xuҩt bҩt hӧp lӋꢀÿӃn phân ÿRҥn tѭѫng ӭng.

Tài li͏u l˱u hành n͡i b͡ - 6 -

Giáo trình Nguyên lý h͏ꢀÿL͉u hành – KS. Trҫn Ngӑc Thái, %͡ môn Tin h͕c – Ĉ̩i h͕c DL H̫i Phòng

Chia sҿ phân ÿRҥn: Mӝt ѭu ÿiӇm khác cӫa kӻ thuұt phân ÿRҥn là khҧ năng chia sҿꢀӣ mӭc ÿӝ phân

ÿoҥn. Nhӡ khҧ năng này, các tiӃn trình có thӇ chia sҿ vӟi nhau tӯng phҫn chѭѫng trình ( ví dө các thӫ

tөc, hàm), không nhҩt thiӃt phҧi chia sҿ toàn bӝ chѭѫng trình nhѭ trѭӡng hӧp phân trang. Mӛi tiӃn trình

có mӝt bҧng phân ÿRҥn riêng, mӝt phân ÿRҥn ÿѭӧc chia sҿ khi các phҫn tӱ trong bҧng phân ÿRҥn cӫa

hai tiӃn trình khác nhau cùng chӍꢀÿӃn mӝt vӏ trí vұt lý duy nhҩt.

Hình 4.21 Chia sҿ code trong hӋ phân ÿRҥn

Phҧi giҧi quyӃt vҩn ÿӅ cҩp phát ÿӝng: làm thӃ nào ÿӇ thӓa mãn mӝt yêu cҫu vùng nhӟ kích thѭӟc N ?

Cҫn phҧi chӑn vùng nhӟ nào trong danh sách vùng nhӟ tӵ do ÿӇ cҩp phát ? Nhѭ vұy cҫn phҧi ghi nhӟ

hiӋn trҥng bӝ nhӟꢀÿӇ có thӇ cҩp phát ÿúng. Có hai phѭѫng pháp quҧn lý chӫ yӃu :

Quҧn lý bҵng mӝt bҧng các bit : bӝ nhӟꢀÿѭӧc chia thành các ÿѫn vӏ cҩp phát, mӛi ÿѫn vӏꢀÿѭӧc phҧn

ánh bҵng mӝt bit trong bҧng các bit, mӝt bit nhұn giá trӏ 0 nӃu ÿѫn vӏ bӝ nhӟ tѭѫng ӭng ÿang tӵ do, và

nhұn giá trӏ 1 nӃu ÿѫn vӏ tѭѫng ӭng ÿã ÿѭӧc cҩp phát cho mӝt tiӃn trình. Khi cҫn nҥp mӝt tiӃn trình có

kích thѭӟc kꢀÿѫn vӏ, cҫn phҧi tìm trong bҧng các bit mӝt dãy con k bit nhұn giá trӏ 0. Ĉây là mӝt giҧi

pháp ÿѫn giҧn, nhѭng thӵc hiӋn chұm nên ít ÿѭӧc sӱ dөng.

Hình 4.5 Quҧn lý bӝ nhӟ bҵng bҧng các bit

Quҧn lý bҵng danh sách: Tә chӭc mӝt danh sách các phân ÿRҥn ÿã cҩp phát và phân ÿoҥn tӵ do, mӝt

phân ÿoҥn có thӇ là mӝt tiӃn trình (P) hay vùng nhӟ trӕng giӳa hai tiӃn trình (H).

Tài li͏u l˱u hành n͡i b͡ - 7 -

Giáo trình Nguyên lý h͏ꢀÿL͉u hành – KS. Trҫn Ngӑc Thái, %͡ môn Tin h͕c – Ĉ̩i h͕c DL H̫i Phòng

Hình 4.6 Quҧn lý bӝ nhӟ bҵng danh sách

Các thuұt toán thông dөng ÿӇ chӑn mӝt phân ÿoҥn tӵ do trong danh sách ÿӇ cҩp phát cho tiӃn trình là :

First-fit: cҩp phát phân ÿRҥn tӵ do ÿҫu tiên ÿӫ lӟn.

Best-fit: cҩp phát phân ÿRҥn tӵ do nhӓ nhҩt nhѭng ÿӫ lӟn ÿӇ thõa mãn nhu cҫu.

Worst-fit : cҩp phát phân ÿRҥn tӵ do lӟn nhҩt.

Trong hӋ thӕng sӱ dөng kӻ thuұt phân ÿRҥn , hiӋn tѭӧng phân mҧnh ngoҥi vi lҥi xuҩt hiӋn khi các

khӕi nhӟ tӵ do ÿӅu quá nhӓ, không ÿӫꢀÿӇ chӭa mӝt phân ÿRҥn.

3.4.2. Phân trang ( Paging)

Ý tѭӣng:

Phân bӝ nhӟ vұt lý thành các khӕi (block) có kích thѭӟc cӕꢀÿӏnh và bҵng nhau, gӑi là khung trang

(page frame). Không gian ÿӏa chӍ cǊng ÿѭӧc chia thành các khӕi có cùng kích thѭӟc vӟi khung trang,

và ÿѭӧc gӑi là trang (page). Khi cҫn nҥp mӝt tiӃn trình ÿӇ xӱ lý, các trang cӫa tiӃn trình sӁꢀÿѭӧc nҥp

vào nhӳng khung trang còn trӕng. Mӝt tiӃn trình kích thѭӟc N trang sӁ yêu cҫu N khung trang tӵ do.

Hình 4.8 Mô hình bӝ nhӟ phân trang

&ѫ chӃ MMU trong kӻ thuұt phân trang:

&ѫ chӃ phҫn cӭng hӛ trӧ thӵc hiӋn chuyӇn ÿәi ÿӏa chӍ trong cѫ chӃ phân trang là bҧng trang (pages

table). Mӛi phҫn tӱ trong bҧng trang cho biӃt các ÿӏa chӍ bҳt ÿҫu cӫa vӏ trí lѭu trӳ trang tѭѫng ӭng

trong bӝ nhӟ vұt lý ( sӕ hiӋu khung trang trong bӝ nhӟ vұt lý ÿang chӭa trang ).

ChuyӇn ÿәi ÿӏa chӍ:

Mӛi ÿӏa chӍ phát sinh bӣi CPU ÿѭӧc chia thành hai phҫn:

s͙ hi͏u trang (p): sӱ dөng nhѭ chӍ mөc ÿӃn phҫn tӱ tѭѫng ӭng trong bҧng trang.

ÿ͓a ch͑ t˱˯ng ÿ͙i trong trang (d): kӃt hӧp vӟi ÿӏa chӍ bҳt ÿҫu cӫa trang ÿӇ tҥo ra ÿӏa chӍ vұt lý mà trình

quҧn lý bӝ nhӟ sӱ dөng.

Tài li͏u l˱u hành n͡i b͡ - 8 -

Giáo trình Nguyên lý h͏ꢀÿL͉u hành – KS. Trҫn Ngӑc Thái, %͡ môn Tin h͕c – Ĉ̩i h͕c DL H̫i Phòng

Kích thѭӟc cӫa trang do phҫn cӭng qui ÿӏnh. ĈӇ dӉ phân tích ÿӏa chӍꢀҧo thành sӕ hiӋu trang và ÿӏa chӍ

Wѭѫng ÿӕi, kích thѭӟc cӫa mӝt trang thông thѭӡng là mӝt lǊy thӯa cӫa 2 (biӃn ÿәi trong phҥm vi 512

bytes và 8192 bytes). NӃu kích thѭӟc cӫa không gian ÿӏa chӍ là 2^mvà kích thѭӟc trang là 2 ⁿ, thì m-n

bits cao cӫa ÿӏa chӍꢀҧo sӁ biӉu diӉn sӕ hiӋu trang, và n bits thҩp cho biӃt ÿӏa chӍ tѭѫng ÿӕi trong trang.

p

m-n

d

n

Cài ÿһt bҧng trang:

Trong trѭӡng hӧp ÿѫn giҧn nhҩt, bҧng trang mӝt tұp các thanh ghi ÿѭӧc sӱ dөng ÿӇ cài ÿһt bҧng trang.

Tuy nhiên viӋc sӱ dөng thanh ghi chӍ phù hӧp vӟi các bҧng trang có kích thѭӟc nhӓ, nӃu bҧng trang có

kích thѭӟc lӟn, nó phҧi ÿѭӧc lѭu trӳ trong bӝ nhӟ chính, và sӱ dөng mӝt thanh ghi ÿӇ lѭu ÿӏa chӍ bҳt

ÿҫu lѭu trӳ bҧng trang (PTBR).

Theo cách tә chӭc này, mӛi truy xuҩt ÿӃn dӳ liӋu hay chӍ thӏꢀÿӅu ÿòi hӓi hai lҫn truy xuҩt bӝ nhӟ :

mӝt cho truy xuҩt ÿӃn bҧng trang và mӝt cho bҧn thân dӳ liӋu!

Hình 4.10 Mô hình bӝ nhӟ phân trang

Tài li͏u l˱u hành n͡i b͡ - 9 -

Giáo trình Nguyên lý h͏ꢀÿL͉u hành – KS. Trҫn Ngӑc Thái, %͡ môn Tin h͕c – Ĉ̩i h͕c DL H̫i Phòng

Hình 4.11 Sӱ dөng thanh ghi nӅn trӓꢀÿӃn bҧng trang

Có thӇ né tránh bӟt viӋc truy xuҩt bӝ nhӟ hai lҫn bҵng cách sӱ dөng thêm mӝt vùng nhӟꢀÿһc biӋt ,

vӟi tӕc ÿӝ truy xuҩt nhanh và cho phép tìm kiӃm song song, vùng nhӟ cache nhӓ này thѭӡng ÿѭӧc gӑi

là bӝ nhӟ kӃt hӧp (TLBs). Mӛi thanh ghi trong bӝ nhӟ kӃt hӧp gӗm mӝt tӯ khóa và mӝt giá trӏ, khi ÿѭa

ÿӃn bӝ nhӟ kӃt hӧp mӝt ÿӕi tѭӧng cҫn tìm, ÿӕi tѭӧng này sӁꢀÿѭӧc so sánh cùng lúc vӟi các tӯ khóa

trong bӝ nhӟ kӃt hӧp ÿӇ tìm ra phҫn tӱ tѭѫng ӭng. Nhӡꢀÿһc tính này mà viӋc tìm kiӃm trên bӝ nhӟ kӃt

hӧp ÿѭӧc thӵc hiӋn rҩt nhanh, nhѭng chi phí phҫn cӭng lҥi cao.

Trong kӻ thuұt phân trang, TLBs ÿѭӧc sӱ dөng ÿӇ lѭu trӳ các trang bӝ nhӟꢀÿѭӧc truy cұp gҫn hiӋn

tҥi nhҩt. Khi CPU phát sinh mӝt ÿӏa chӍ, sӕ hiӋu trang cӫa ÿӏa chӍ sӁꢀÿѭӧc so sánh vӟi các phҫn tӱ trong

TLBs, nӃu có trang tѭѫng ӭng trong TLBs, thì sӁ xác ÿӏnh ÿѭӧc ngay sӕ hiӋu khung trang tѭѫng ӭng,

nӃu không mӟi cҫn thӵc hiӋn thao tác tìm kiӃm trong bҧng trang.

Tә chӭc bҧng trang:

Mӛi hӋꢀÿLӅu hành có mӝt phѭѫng pháp riêng ÿӇ tә chӭc lѭu trӳ bҧng trang. Ĉa sӕ các hӋꢀÿLӅu hành cҩp

cho mӛi tiӃn trình mӝt bҧng trang. Tuy nhiên phѭѫng pháp này không thӇ chҩp nhұn ÿѭӧc nӃu hӋꢀÿLӅu

hành cho phép quҧn lý mӝt không gian ÿӏa chӍ có dung lѭӧng quá (2³², 2⁶⁴): trong các hӋ thӕng nhѭ

thӃ, bҧn thân bҧng trang ÿòi hӓi mӝt vùng nhӟ qúa lӟn! Có hai giҧi pháp cho vҩn ÿӅ này:

Phân trang ÿa c̭p: phân chia bҧng trang thành các phҫn nhӓ, bҧn thân bҧng trang cǊng sӁꢀÿѭӧc phân

trang

Tài li͏u l˱u hành n͡i b͡ - 10 -

Giáo trình Nguyên lý h͏ꢀÿL͉u hành – KS. Trҫn Ngӑc Thái, %͡ môn Tin h͕c – Ĉ̩i h͕c DL H̫i Phòng

B̫ng trang ngh͓ch ÿ̫o: sӱ dөng duy nhҩt mӝt b̫ng trang ngh͓ch ÿ̫o cho tҩt cҧ các tiӃn trình . Mӛi

phҫn tӱ trong b̫ng trang ngh͓ch ÿ̫o phҧn ánh mӝt khung trang trong bӝ nhӟ bao gӗm ÿӏa chӍ logic

cӫa mӝt trang ÿang ÿѭӧc lѭu trӳ trong bӝ nhӟ vұt lý tҥi khung trang này, cùng vӟi thông tin vӅ tiӃn

trình ÿang ÿѭӧc sӥ hӳu trang. Mӛi ÿӏa chӍꢀҧo khi ÿó là mӝt bӝ ba <idp, p, d >

Trong ÿó : idp là ÿӏnh danh cӫa tiӃn trình

p là sӕ hiӋu trang

d là ÿӏa chӍ tѭѫng ÿӕi trong trang

Mӛi phҫn tӱ trong bҧng trang nghӏch ÿҧo là mӝt cһp <idp, p >. Khi mӝt tham khҧo ÿӃn bӝ nhӟꢀÿѭӧc

phát sinh, mӝt phҫn ÿӏa chӍꢀҧo là <idp, p > ÿѭӧc ÿѭa ÿӃn cho trình quҧn lý bӝ nhӟꢀÿӇ tìm phҫn tӱ tѭѫng

ӭng trong bҧng trang nghӏch ÿҧo, nӃu tìm thҩy, ÿӏa chӍ vұt lý <i,d> sӁꢀÿѭӧc phát sinh. Trong các trѭӡng

hӧp khác, xem nhѭ tham khҧo bӝ nhӟꢀÿã truy xuҩt mӝt ÿӏa chӍ bҩt hӧp lӋ.

Bҧo vӋ:

&ѫ chӃ bҧo vӋ trong hӋ thӕng phân trang ÿѭӧc thӵc hiӋn vӟi các bit bҧo vӋꢀÿѭӧc gҳn vӟi mӛi khung

trang. Thông thѭӡng , các bit này ÿѭӧc lѭu trong bҧng trang , vì mӛi truy xuҩt ÿӃn bӝ nhӟꢀÿӅu phҧi

tham khҧo ÿӃn bҧng trang ÿӇ phát sinh ÿӏa chӍ vұt lý, khi ÿó, hӋ thӕng có thӇ kiӇm tra các thao tác truy

xuҩt trên khung trang tѭѫng ӭng có hӧp lӋ vӟi thuӝc tính bҧo vӋ cӫa nó không.

Ngoài ra, mӝt bit phө trӝi ÿѭӧc thêm vào trong cҩu trúc mӝt phҫn tӱ cӫa bҧng trang : bit hӧp lӋ-bҩt hӧp

lӋ (valid-invalid).

Tài li͏u l˱u hành n͡i b͡ - 11 -

Giáo trình Nguyên lý h͏ꢀÿL͉u hành – KS. Trҫn Ngӑc Thái, %͡ môn Tin h͕c – Ĉ̩i h͕c DL H̫i Phòng

Hͫp l͏ : trang tѭѫng ӭng thuӝc vӅ không gian ÿӏa chӍ cӫa tiӃn trình.

B̭t hͫp l͏ : trang tѭѫng ӭng không nҵm trong không gian ÿӏa chӍ cӫa tiӃn trình, ÿiӅu này có nghƭa tiӃn

trình ÿã truy xuҩt ÿӃn mӝt ÿӏa chӍ không ÿѭӧc phép.

Hình 4.15 Cҩu trúc mӝt phҫn tӱ trong bҧng trang

Chia sҿ bӝ nhӟ trong cѫ chӃ phân trang:

Mӝt ѭu ÿiӇm cӫa cѫ chӃ phân trang là cho phép chia sҿ các trang giӳa các tiӃn trình.Trong trѭӡng hӧp

này, sӵ chia sҿꢀÿѭӧc thӵc hiӋn bҵng cách ánh xҥ nhiӅu ÿӏa chӍ logic vào mӝt ÿӏa chӍ vұt lý duy nhҩt. Có

thӇ áp dөng kӻ thuұt này ÿӇ cho phép có tiӃn trình chia sҿ mӝt vùng code chung: nӃu có nhiӅu tiӃn

trình cӫa cùng mӝt chѭѫng trình, chӍ cҫn lѭu trӳ mӝt ÿRҥn code cӫa chѭѫng trình này trong bӝ nhӟ, các

tiӃn trình sӁ có thӇ cùng truy xuҩt ÿӃn các trang chӭa code chung này. Lѭu ý ÿӇ có thӇ chia sҿ mӝt

ÿoҥn code, ÿRҥn code này phҧi có thuӝc tính reenterable (cho phép mӝt bҧn sao cӫa chѭѫng trình ÿѭӧc

sӱ dөng ÿӗng thӡi bӣi nhiӅu tác vө).

Kӻ thuұt phân trang loҥi bӓꢀÿѭӧc hiӋn tѭӧng phân mҧnh ngoҥi vi : mӛi khung trang ÿӅu có thӇꢀÿѭӧc

cҩp phát cho mӝt tiӃn trình nào ÿó có yêu cҫu. Tuy nhiên hiӋn tѭӧng phân mҧnh nӝi vi vүn có thӇ xҧy

ra khi kích thѭӟc cӫa tiӃn trình không ÿúng bҵng bӝi sӕ cӫa kích thѭӟc mӝt trang, khi ÿó, trang cuӕi

cùng sӁ không ÿѭӧc sӱ dөng hӃt.

Mӝt khiá cҥnh tích cӵc rҩt quan trӑng khác cӫa kӻ thuұt phân trang là sӵ phân biӋt rҥch ròi góc nhìn

cӫa ngѭӡi dùng và cӫa bӝ phұn quҧn lý bӝ nhӟ vұt lý:

Góc nhìn cͯa ng˱ͥi s͵ dͭng: mӝt tiӃn trình cӫa ngѭӡi dùng nhìn thҩy bӝ nhӟ nhѭ là mӝt không gian

liên tөc, ÿӗng nhҩt và chӍ chӭa duy nhҩt bҧn thân tiӃn trình này.

Góc nhìn cͯa b͡ nhͣ v̵t lý: mӝt tiӃn trình cӫa ngѭӡi sӱ dөng ÿѭӧc lѭu trӳ phân tán khҳp bӝ nhӟ vұt

lý, trong bӝ nhӟ vұt lý ÿӗng thӡi cǊng chӭa nhӳng tiӃn trình khác.

Phҫn cӭng ÿҧm nhiӋm viӋc chuyӇn ÿәi ÿӏa chӍ logic thành ÿӏa chӍ vұt lý . Sӵ chuyӇn ÿәi này là trong

suӕt ÿӕi vӟi ngѭӡi sӱ dөng.

Tài li͏u l˱u hành n͡i b͡ - 12 -

Giáo trình Nguyên lý h͏ꢀÿL͉u hành – KS. Trҫn Ngӑc Thái, %͡ môn Tin h͕c – Ĉ̩i h͕c DL H̫i Phòng

ĈӇ Oѭu trӳ các thông tin chi tiӃt vӅ quá trình cҩp phát bӝ nhӟ, hӋꢀÿLӅu hành sӱ dөng mӝt bҧng khung

trang, mà mӛi phҫn tӱ mô tҧ tình trҥng cӫa mӝt khung trang vұt lý : tӵ do hay ÿѭӧc cҩp phát cho mӝt

tiӃn trình nào ÿó .

/ѭu ý rҵng sӵ phân trang không phҧn ánh ÿúng cách thӭc ngѭӡi sӱ dөng cҧm nhұn vӅ bӝ nhӟ.

Ngѭӡi sӱ dөng nhìn thҩy bӝ nhӟ nhѭ mӝt tұp các ÿӕi tѭӧng cӫa cKѭѫng trình (segments, các thѭ

viӋn...) và mӝt tұp các ÿӕi tѭӧng dӳ liӋu (biӃn toàn cөc, stack, vùng nhӟ chia sҿ...). Vҩn ÿӅꢀÿһt ra là cҫn

tìm mӝt cách thӭc biӉu diӉn bӝ nhӟ sao cho có thӇ cung cҩp cho ngѭӡi dùng mӝt cách nhìn gҫn vӟi

quan ÿiӇm logic cӫa hӑ hѫn và ÿó là kӻ thuұt phân ÿRҥn

Kӻ thuұt phân ÿRҥn thõa mãn ÿѭӧc nhu cҫu thӇ hiӋn cҩu trúc logic cӫa chѭѫng trình nhѭng nó dүn

ÿӃn tình huӕng phҧi cҩp phát các khӕi nhӟ có kích thѭӟc khác nhau cho các phân ÿRҥn trong bӝ nhӟ

vұt lý. ĈLӅu này làm rҳc rӕi vҩn ÿӅ hѫn rҩt nhiӅu so vӟi viӋc cҩp phát các trang có kích thѭӟc tƭnh.Mӝt

giҧi pháp dung hoà là kӃt hӧp cҧ hai kӻ thuұt phân trang và phân ÿoҥn : chúng ta tiӃn hành phân trang

các phân ÿo̩n.

3.4.3. Phân ÿoҥn kӃt hӧp phân trang (Paged segmentation)

Ý tѭӣng: Không gian ÿӏa chӍ là mӝt tұp các phân ÿRҥn, mӛi phân ÿRҥn ÿѭӧc chia thành nhiӅu trang.

Khi mӝt tiӃn trình ÿѭӧc ÿѭa vào hӋ thӕng, hӋꢀÿLӅu hành sӁ cҩp phát cho tiӃn trình các trang cҫn thiӃt ÿӇ

chӭa ÿӫ các phân ÿoҥn cӫa tiӃn trình.

&ѫ chӃ MMU trong kӻ thuұt phân ÿRҥn kӃt hӧp phân trang:

ĈӇ hӛ trӧ kӻ thuұt phân ÿRҥn, cҫn có mӝt b̫ng phân ÿR̩n, nhѭng giӡ ÿây mӛi phân ÿRҥn cҫn có mӝt

b̫ng trang phân biӋt.

ChuyӇn ÿәi ÿӏa chӍ:

Mӛi ÿӏa chӍ logic là mӝt bӝ ba: <s,p,d>

s͙ hi͏u phân ÿR̩n (s): sӱ dөng nhѭ chӍ mөc ÿӃn phҫn tӱ tѭѫng ӭng trong bҧng phân ÿRҥn.

s͙ hi͏u trang (p): sӱ dөng nhѭ chӍ mөc ÿӃn phҫn tӱ tѭѫng ӭng trong bҧng trang cӫa phân ÿRҥn.

ÿ͓a ch͑ t˱˯ng ÿ͙i trong trang (d): k͇t hͫp vͣi ÿ͓a ch͑ b̷t ÿ̯u cͯa trang ÿ͋ t̩o ra ÿ͓a chӍ vұt lý mà

trình quҧn lý bӝ nhӟ sӱ dөng.

Tài li͏u l˱u hành n͡i b͡ - 13 -

Giáo trình Nguyên lý h͏ꢀÿL͉u hành – KS. Trҫn Ngӑc Thái, %͡ môn Tin h͕c – Ĉ̩i h͕c DL H̫i Phòng

Hình 4.22 Mô hình phân ÿoҥn kӃ hӧp phân trang

Tҩt cҧ các mô hình tә chӭc bӝ nhӟ trên ÿây ÿӅu có khuynh hѭӟng cҩp phát cho tiӃn trình toàn bӝ các

trang yêu cҫu trѭӟc khi thұt sӵ xӱ lý. Vì bӝ nhӟ vұt lý có kích thѭӟc rҩt giӟi hҥn, ÿLӅu này dүn ÿӃn hai

ÿiӇm bҩt tiӋn sau :

Kích thѭӟc tiӃn trình bӏ giӟi hҥn bӣi kích thѭӟc cӫa bӝ nhӟ vұt lý.

Khó có thӇ bҧo trì nhiӅu tiӃn trình cùng lúc trong bӝ nhӟ, và nhѭ vұy khó nâng cao mӭc ÿӝꢀÿa chѭѫng

cӫa hӋ thӕng.

Tóm tɬt

Có nhiӅu cách tiӃp cұn khác nhau ÿӇ tә chӭc quãn lý bӝ nhӟ, nhѭng tӵu chung mong ÿҥt ÿӃn các mөc

tiêu sau :

Có thӇꢀÿáp ӭng ÿѭӧc ÿҫy ÿӫ các nhu cҫu bӝ nhӟ cӫa chѭѫng trình vӟi mӝt bӝ nhӟ vұt lý giӟi hҥn

Tài li͏u l˱u hành n͡i b͡ - 14 -

Giáo trình Nguyên lý h͏ꢀÿL͉u hành – KS. Trҫn Ngӑc Thái, %͡ môn Tin h͕c – Ĉ̩i h͕c DL H̫i Phòng

Quá trình chuyӇn ÿәi ÿӏa chӍ, tә chӭc cҩp phát bӝ nhӟ là trong suӕt vӟi ngѭӡi dùng, và có khҧ năng

tái ÿӏnh vӏ.

Tұn dөng hiӋu quҧ bӝ nhӟ ( ít có vùng nhӟ không sӱ dөng ÿѭӧc)

Bӝ nhӟꢀÿѭӧc bҧo vӋ tӕt

Có khҧ năng chia sҿ bӝ nhӟ giӳa các tiӃn trình

Mӝt sӕ cách tiӃp cұn tә chӭc bӝ nhӟ chính

C̭p phát liên tͭc : có thӇ cҩp phát các vùng nhӟ liên tөc cho các tiӃn trình trong nhӳng phân vùng có

kích thѭӟc cӕꢀÿӏnh hay biӃn ÿӝng. ĈLӇm yӃu cӫa cách tiӃp cұn này là kích thѭӟc các chѭѫng trình có

thӇ dѭӧc xӱ lý bӏ giӟi hҥn bӣi các kích thѭӟc cӫa khӕi nhӟ liên tөc có thӇ sӱ dөng. Các hiӋn tѭӧng

phân mҧnh ngoҥi vi, nӝi vi ÿӅu có thӇ xuҩt hiӋn

C̭p phát không liên tͭc : có thӇ cҩp phát các vùng nhӟ không liên tөc cho mӝt tiӃn trình. Hai kӻ thuұt

thѭӡng ÿѭӧc áp dөng là phân trang và phân ÿoҥn. Kӻ thuұt phân trang cho phép loҥi bõ hiӋn tѭӧng

phân mҧnh ngoҥi vi, kӻ thuұt phân ÿRҥn loҥi bӓ hiӋn tѭӧng phân mҧnh nӝi vi, nhѭng phҧi giҧi quyӃt

vҩn ÿӅ cҩp phát ÿӝng.

Cӫng cӕ bài hӑc

Các câu hӓi cҫn trҧ lӡi ÿѭӧc sau bài hӑc này :

1. NhiӋm vө quҧn lý bӝ nhӟ bao gӗm các công viӋc nào ? Giai ÿoҥn nào do hӋꢀÿLӅu hành thӵc hiӋn ,

giai ÿoҥn nào cҫn sӵ trӧ giúp cӫa phҫn cӭng?

2. Các khái niӋm : phân mҧnh nӝi vi, phân mҧnh ngoҥi vi, bài toán cҩp phát ÿӝng, ÿLҥ chӍ logic, ÿLҥ chӍ

physic

3. Phân tích ѭu khuyӃt cӫa các mô hình tә chӭc bӝ nhӟ.

3.5. Bӝ nhӟꢀҧo

B͡ nhͣ ̫o là m͡t kͿ thu̵t hi͏n ÿ̩i giúp cho ng˱ͥi dùng ÿ˱ͫc gi̫i phóng hoàn toàn kh͗i m͙i b̵n tâm

v͉ giͣi h̩n b͡ nhͣ. Ý t˱ͧng, ˱u ÿi͋m và nhͷng v̭n ÿ͉ liên quan ÿ͇n vi͏c t͝ chͱc b͡ nhͣꢀ̫o sͅꢀÿ˱ͫc

trình bày trong bài h͕c này.

3.5.1 Dүn nhұp

NӃu ÿһt toàn thӇ không gian ÿӏa chӍ vào bӝ nhӟ vұt lý, thì kích thѭӟc cӫa chѭѫng trình bӏ giӟi hҥn bӣi

kích thѭӟc bӝ nhӟ vұt lý.

Thӵc tӃ, trong nhiӅu trѭӡng hӧp, chúng ta không cҫn phҧi nҥp toàn bӝ chѭѫng trình vào bӝ nhӟ vұt lý

cùng mӝt lúc, vì tҥi mӝt thӡi ÿLӇm chӍ có mӝt chӍ thӏ cӫa tiӃn trình ÿѭӧc xӱ lý. Ví dө, các chѭѫng trình

ÿӅu có mӝt ÿRҥn code xӱ lý lӛi, nhѭng ÿoҥn code này hҫu nhѭ rҩt ít khi ÿѭӧc sӱ dөng vì hiӃm khi xҧy

ra lӛi, trong trѭӡng hӧp này, không cҫn thiӃt phҧi nҥp ÿRҥn code xӱ lý lӛi tӯꢀÿҫu.

Tӯ nhұn xét trên, mӝt giҧi pháp ÿѭӧc ÿӅ xuҩt là cho phép thӵc hiӋn mӝt chѭѫng trình chӍꢀÿѭӧc nҥp

tӯng phҫn vào bӝ nhӟ vұt lý. Ý tѭӣng chính cӫa giҧi pháp này là tҥi mӛi thӡi ÿLӇm chӍ lѭu trӳ trong bӝ

nhӟ vұt lý các chӍ thӏ và dӳ liӋu cӫa chѭѫng trình cҫn thiӃt cho viӋc thi hành tҥi thӡi ÿLӇm ÿó. Khi cҫn

ÿӃn các chӍ thӏ khác, nhӳng chӍ thӏ mӟi sӁꢀÿѭӧc nҥp vào bӝ nhӟ, tҥi vӏ trí trѭӟc ÿó bӏ chiӃm giӳ bӣi các

Tài li͏u l˱u hành n͡i b͡ - 15 -

Giáo trình Nguyên lý h͏ꢀÿL͉u hành – KS. Trҫn Ngӑc Thái, %͡ môn Tin h͕c – Ĉ̩i h͕c DL H̫i Phòng

chӍ thӏ nay không còn cҫn ÿӃn nӳa. Vӟi giҧi pháp này, mӝt chѭѫng trình có thӇ lӟn hѫn kích thѭӟc cӫa

vùng nhӟ cҩp phát cho nó.

Mӝt cách ÿӇ thӵc hiӋn ý tѭӣng cӫa giҧi pháp trên ÿây là sӱ dөng kӻ thuұt overlay. Kӻ thuұt overlay

không ÿòi hӓi bҩt kǤ sӵ trӧ giúp ÿһc biӋt nào cӫa hӋꢀÿLӅu hành , nhѭng trái lҥi, lұp trình viên phҧi biӃt

cách lұp trình theo cҩu trúc overlay, và ÿiӅu này ÿòi hӓi khá nhiӅu công sӭc.

ĈӇ giҧi phóng lұp trình viên khӓi các suy tѭ vӅ giӟi hҥn cӫa bӝ nhӟ, mà cǊng không tăng thêm khó

khăn cho công viӋc lұp trình cӫa hӑ, ngѭӡi ta nghƭꢀÿӃn các kӻ thuұt tӵꢀÿӝng, cho phép xӱ lý mӝt

chѭѫng trình có kích thѭӟc lӟn chӍ vӟi mӝt vùng nhӟ có kích thѭӟc nhӓ . Giҧi pháp ÿѭӧc tìm thҩy vӟi

khái niӋm b͡ nhͣꢀ̫o (virtual memory).

3.5.1.1. Ĉӏnh nghƭa

Bӝ nhӟꢀҧo là mӝt kӻ thuұt cho phép xӱ lý mӝt tiӃn trình không ÿѭӧc nҥp toàn bӝ vào bӝ nhӟ vұt lý. Bӝ

nhӟꢀҧo mô hình hoá bӝ nhӟ nhѭ mӝt bҧng lѭu trӳ rҩt lӟn và ÿӗng nhҩt, tách biӋt hҷn khái niӋm không

gian ÿӏa chӍ và không gian vұt lý. Ngѭӡi sӱ dөng chӍ nhìn thҩy và làm viӋc trong không gian ÿӏa chӍꢀҧo,

viӋc chuyӇn ÿәi sang không gian vұt lý do hӋꢀÿLӅu hành thӵc hiӋn vӟi sӵ trӧ giúp cӫa các cѫ chӃ phҫn

cӭng cө thӇ.

Cҫn kӃt hӧp kӻ thuұt swappingꢀÿӇn chuyӇn các phҫn cӫa chѭѫng trình vào-ra giӳa bӝ nhӟ chính và bӝ

nhӟ phө khi cҫn thiӃt.

Nhӡ viӋc tách biӋt bӝ nhӟꢀҧo và bӝ nhӟ vұt lý, có thӇ tә chӭc mӝt bӝ nhӟꢀҧo có kích thѭӟc lӟn hѫn bӝ

nhӟ vұt lý.

Bӝ nhӟꢀҧo cho phép giҧm nhҽ công viӋc cӫa lұp trình viên vì hӑ không cҫn bұn tâm ÿӃn giӟi hҥn cӫa

vùng nhӟ vұt lý, cǊng nhѭ không cҫn tә chӭc chѭѫng trình theo cҩu trúc overlays.

Hình 2.24 Bӝ nhӟꢀҧo

3.5.1.2. Cài ÿһt bӝ nhӟꢀҧo

Bӝ nhӟꢀҧo thѭӡng ÿѭӧc thӵc hiӋn vӟi kӻ thuұt phân trang theo yêu c̯u (demand paging). CǊng có thӇ

sӱ dөng kӻ thuұt phân ÿo̩n theo yêu c̯u ( demand segmentation)ꢀÿӇ cài ÿһt bӝ nhӟꢀҧo, tuy nhiên viӋc

cҩp phát và thay thӃ các phân ÿRҥn phӭc tҥp hѫn thao tác trên trang, vì kích thѭӟc không bҵng nhau

cӫa các ÿoҥn.

Phân trang theo yêu cҫu ( demand paging)

Tài li͏u l˱u hành n͡i b͡ - 16 -

Giáo trình Nguyên lý h͏ꢀÿL͉u hành – KS. Trҫn Ngӑc Thái, %͡ môn Tin h͕c – Ĉ̩i h͕c DL H̫i Phòng

Mӝt hӋ thӕng phân trang theo yêu cҫu là hӋ thӕng sӱ dөng kӻ thuұt phân trang kӃt hӧp vӟi kӻ thuұt

swapping. Mӝt tiӃn trình ÿѭӧc xem nhѭ mӝt tұp các trang, thѭӡng trú trên bӝ nhӟ phө ( thѭӡng là ÿƭa).

Khi cҫn xӱ lý, tiӃn trình sӁꢀÿѭӧc nҥp vào bӝ nhӟ chính. Nhѭng thay vì nҥp toàn bӝ chѭѫng trình, chӍ

nhӳng trang cҫn thiӃt trong thӡi ÿLӇm hiӋn tҥi mӟi ÿѭӧc nҥp vào bӝ nhӟ. Nhѭ vұy mӝt trang chӍꢀÿѭӧc

nҥp vào bӝ nhӟ chính khi có yêu cҫu.

Vӟi mô hình này, cҫn cung cҩp mӝt cѫ chӃ phҫn cӭng giúp phân biӋt các trang ÿang ӣ trong bӝ nhӟ

chính và các trang trên ÿƭa. Có thӇ sӱ dөng lҥi bit valid-invalid nhѭng vӟi ngӳ nghƭa mӟi:

valid : trang tѭѫng ӭng là hӧp lӋ và ÿang ӣ trong bӝ nhӟ chính .

invalid : hoһc trang bҩt hӧp lӋ (không thuӝc vӅ không gian ÿӏa chӍ cӫa tiӃn trình) hoһc trang hӧp lӋ

nhѭng ÿang ÿѭӧc lѭu trên bӝ nhӟ phө.

Mӝt phҫn tӱ trong bҧng trang mӝ tҧ cho mӝt trang không nҵm trong bӝ nhӟ chính, sӁꢀÿѭӧc ÿánh dҩu

invalid và chӭa ÿӏa chӍ cӫa trang trên bӝ nhӟ phө.

&ѫ chӃ phҫn cӭng :

&ѫ chӃ phҫn cӭng hӛ trӧ kӻ thuұt phân trang theo yêu cҫu là sӵ kӃt hӧp cӫa cѫ chӃ hӛ trӧ kӻ thuұt

phân trang và kӻ thuұt swapping:

B̫ng trang: Cҩu trúc bҧng trang phҧi cho phép phҧn ánh tình trҥng cӫa mӝt trang là ÿang nҵm trong

bӝ nhӟ chính hay bӝ nhӟ phө.

B͡ nhͣ phͭ: Bӝ nhӟ phө lѭu trӳ nhӳng trang không ÿѭӧc nҥp vào bӝ nhӟ chính. Bӝ nhӟ phө thѭӡng

ÿѭӧc sӱ dөng là ÿƭa, và vùng không gian ÿƭa dùng ÿӇ lѭu trӳ tҥm các trang trong kӻ thuұt swapping

ÿѭӧc gӑi là không gian swapping.

Hình 2.24 Bҧng trang vӟi mӝt sӕ trang trên bӝ nhӟ phө

Lӛi trang

Tài li͏u l˱u hành n͡i b͡ - 17 -

Giáo trình Nguyên lý h͏ꢀÿL͉u hành – KS. Trҫn Ngӑc Thái, %͡ môn Tin h͕c – Ĉ̩i h͕c DL H̫i Phòng

Truy xuҩt ÿӃn mӝt trang ÿѭӧc ÿánh dҩu bҩt hӧp lӋ sӁ làm phát sinh mӝt l͟i trang (page fault). Khi dò

tìm trong bҧng trang ÿӇ lҩy các thông tin cҫn thiӃt cho viӋc chuyӇn ÿәi ÿӏa chӍ, nӃu nhұn thҩy trang

ÿang ÿѭӧc yêu cҫu truy xuҩt là bҩt hӧp lӋ, cѫ chӃ phҫn cӭng sӁ phát sinh mӝt ngҳt ÿӇ báo cho hӋꢀÿLӅu

hành. HӋꢀÿLӅu hành sӁ xӱ lý lӛi trang nhѭ sau :

KiӇm tra truy xuҩt ÿӃn bӝ nhӟ là hӧp lӋ hay bҩt hӧp lӋ

NӃu truy xuҩt bҩt hӧp lӋ : kӃt thúc tiӃn trình

Ngѭӧc lҥi : ÿӃn bѭӟc 3

Tìm vӏ trí chӭa trang muӕn truy xuҩt trên ÿƭa.

Tìm mӝt khung trang trӕng trong bӝ nhӟ chính :

NӃu tìm thҩy : ÿӃn bѭӟc 5

NӃu không còn khung trang trӕng, chӑn mӝt khung trang « nҥn nhân » và chuyӇn trang « nҥn nhân »

ra bӝ nhӟ phө (lѭu nӝi dung cӫa trang ÿang chiӃm giӳ khung trang này lên ÿƭa), cұp nhұt bҧng trang

Wѭѫng ӭng rӗi ÿӃn bѭӟc 5

ChuyӇn trang muӕn truy xuҩt tӯ bӝ nhӟ phө vào bӝ nhӟ chính : nҥp trang cҫn truy xuҩt vào khung

trang trӕng ÿã chӑn (hay vӯa mӟi làm trӕng ) ; cұp nhұt nӝi dung bҧng trang, bҧng khung trang tѭѫng

ӭng.

Tái kích hoҥt tiӃn trình ngѭӡi sӱ dөng.

Hình 2.26 Các giai ÿoҥn xӱ lý lӛi trang

3.5.2. Thay thӃ trang

Khi xҧy ra mӝt lӛi trang, cҫn phҧi mang trang vҳng mһt vào bӝ nhӟ . NӃu không có mӝt khung trang

nào trӕng, hӋꢀÿLӅu hành cҫn thӵc hiӋn công viӋc thay th͇ trang – chӑn mӝt trang ÿang nҵm trong bӝ

nhӟ mà không ÿѭӧc sӱ dөng tҥi thӡi ÿLӇm hiӋn tҥi và chuyӇn nó ra không gian swapping trên ÿƭa ÿӇ

giҧi phóng mӝt khung trang dành chӛ nҥp trang cҫn truy xuҩt vào bӝ nhӟ.

Tài li͏u l˱u hành n͡i b͡ - 18 -

Giáo trình Nguyên lý h͏ꢀÿL͉u hành – KS. Trҫn Ngӑc Thái, %͡ môn Tin h͕c – Ĉ̩i h͕c DL H̫i Phòng

Nhѭ vұy nӃu không có khung trang trӕng, thì mӛi khi xҧy ra lӛi trang cҫn phҧi thӵc hiӋn hai thao tác

chuyӇn trang : chuyӇn mӝt trang ra bӝ nhӟ phө và nҥp mӝt trang khác vào bӝ nhӟ chính. Có thӇ giҧm

bӟt sӕ lҫn chuyӇn trang bҵng cách sӱ dөng thêm mӝt bit c̵p nh̵t (dirty bit). Bit này ÿѭӧc gҳn vӟi mӛi

trang ÿӇ phҧn ánh tình trҥng trang có bӏ cұp nhұt hay không : giá trӏ cӫa bit ÿѭӧc cѫ chӃ phҫn cӭng ÿһt

là 1 mӛi lҫn có mӝt tӯꢀÿѭӧc ghi vào trang, ÿӇ ghi nhұn nӝi dung trang có bӏ sӱa ÿәi. Khi cҫn thay thӃ

mӝt trang, nӃu bit cұp nhұt có giá trӏ là 1 thì trang cҫn ÿѭӧc lѭu lҥi trên ÿƭa, ngѭӧc lҥi, nӃu bit cұp nhұt

là 0, nghƭa là trang không bӏ thay ÿәi, thì không cҫn lѭu trӳ trang trӣ lҥi ÿƭa.

sӕ hiӋu trang bit valid-invalid

dirty

bit

Hình 4.27 Cҩu trúc mӝt phҫn tӱ trong bҧng trang

Sӵ thay thӃ trang là cҫn thiӃt cho kӻ thuұt phân trang theo yêu cҫu. Nhӡ cѫ chӃ này, hӋ thӕng có thӇ

hoàn toàn tách rӡi bӝ nhӟꢀҧo và bӝ nhӟ vұt lý, cung cҩp cho lұp trình viên mӝt bӝ nhӟꢀҧo rҩt lӟn trên

mӝt bӝ nhӟ vұt lý có thӇ bé hѫn rҩt nhiӅu lҫn.

3.5.2.1. Sӵ thi hành phân trang theo yêu cҫu

ViӋc áp dөng kӻ thuұt phân trang theo yêu cҫu có thӇꢀҧnh hѭӣng mҥnh ÿӃn tình hình hoҥt ÿӝng cӫa hӋ

thӕng.

GӍa sӱ p là xác suҩt xҧy ra mӝt lӛi trang (0£ p £ 1):

p = 0 : không có lӛi trang nào

p = 1 : mӛi truy xuҩt sӁ phát sinh mӝt lӛi trang

Thӡi gian thұt sӵ cҫn ÿӇ thӵc hiӋn mӝt truy xuҩt bӝ nhӟ (TEA) là:

TEA = (1-p)ma + p (tdp) [+ swap out ] + swap in + tái kích hoҥt

Trong công thӭc này, ma là thӡi gian truy xuҩt bӝ nhӟ, tdp thӡi gian xӱ lý lӛi trang.

Có thӇ thҩy rҵng, ÿӇ duy trì ӣ mӝt mӭc ÿӝ chҩp nhұn ÿѭӧc sӵ chұm trӉ trong hoҥt ÿӝng cӫa hӋ thӕng

do phân trang, cҫn phҧi duy trì tͽ l͏ phát sinh l͟i trang thҩp.

+ѫn nӳa, ÿӇ cài ÿһt kӻ thuұt phân trang theo yêu cҫu, cҫn phҧi giҧi quyӃt hai vҩn ÿӅ chính yӃu : xây

dӵng mӝt thu̵t toán c̭p phát khung trang, và thu̵t toán thay th͇ trang.

3.5.2.2. Các thuұt toán thay thӃ trang

Vҩn ÿӅ chính khi thay thӃ trang là chӑn lӵa mӝt trang « nҥn nhân » ÿӇ chuyӇn ra bӝ nhӟ phө. Có nhiӅu

thuұt toán thay thӃ trang khác nhau, nhѭng tҩt cҧ cùng chung mӝt mөc tiêu : chӑn trang « nҥn nhân »

là trang mà sau khi thay thӃ sӁ gây ra ít lӛi trang nhҩt.

Có thӇꢀÿánh giá hiӋu qӫa cӫa mӝt thuұt toán bҵng cách xӱ lý trên mӝt chu͟i các ÿ͓a ch͑ c̯n truy xṷt

và tính toán sӕ lѭӧng lӛi trang phát sinh.

Tài li͏u l˱u hành n͡i b͡ - 19 -

Giáo trình Nguyên lý h͏ꢀÿL͉u hành – KS. Trҫn Ngӑc Thái, %͡ môn Tin h͕c – Ĉ̩i h͕c DL H̫i Phòng

Ví dө: Giҧ sӳ theo vӃt xӱ lý cӫa mӝt tiӃn trình và nhұn thҩy tiӃn trình thӵc hiӋn truy xuҩt các ÿӏa chӍ

theo thӭ tӵ sau :

0100, 0432, 0101, 0162, 0102, 0103, 0104, 0101, 0611, 0102, 0103,0104, 0101, 0610, 0102, 0103,

0104, 0101, 0609, 0102, 0105

NӃu có kích thѭӟc cӫa mӝt trang là 100 bytes, có thӇ viӃt lҥi chu͟i truy xṷt trên giҧn lѭӧc hѫn nhѭ sau

:

1, 4, 1, 6, 1, 6, 1, 6, 1

ĈӇ xác ÿӏnh sӕ các lӛi trang xҧy ra khi sӱ dөng mӝt thuұt toán thay thӃ trang nào ÿó trên mӝt chuӛi

truy xuҩt cө thӇ, còn cҫn phҧi biӃt sӕ lѭӧng khung trang sӱ dөng trong hӋ thӕng.

ĈӇ minh hoҥ các thuұt toán thay thӃ trang sӁ trình bày, chuӛi truy xuҩt ÿѭӧc sӱ dөng là :

7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1

3.5.2.2.1. Thu̵t toán FIFO

TiӃp cұn: Ghi nhұn thӡi ÿLӇm mӝt trang ÿѭӧc mang vào bӝ nhӟ chính. Khi cҫn thay thӃ trang, trang ӣ

trong bӝ nhӟ lâu nhҩt sӁꢀÿѭӧc chӑn

Ví dө : sӱ dөng 3 khung trang , ban ÿҫu cҧ 3 ÿӅu trӕng :

7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1

7 7 7 2 2 2 2 4 4 4 0 0 0 0 0 0 0 7 7 7

0 0 0 0 3 3 3 2 2 2 2 2 1 1 1 1 1 0 0

1 1 1 1 0 0 0 3 3 3 3 3 2 2 2 2 2 1

* * * *

* * * * * *

* *

* * *

Ghi chú : * : có lӛi trang

ĈӇ áp dөng thuұt toán FIFO, thӵc tӃ không nhҩt thiӃt phҧi ghi nhұn thӡi ÿLӇm mӛi trang ÿѭӧc nҥp vào

bӝ nhӟ, mà chӍ cҫn tә chӭc quҧn lý các trang trong bӝ nhӟ trong mӝt danh sách FIFO, khi ÿó trang ÿҫu

danh sách sӁꢀÿѭӧc chӑn ÿӇ thay thӃ.

Thuұt toán they thӃ trang FIFO dӉ hiӇu, dӉ cài ÿһt. Tuy nhiên khi thӵc hiӋn không phҧi lúc nào cǊng

có kӃt qӫa tӕt : trang ÿѭӧc chӑn ÿӇ thay thӃ có thӇ là trang chӭc nhiӅu dӳ liӋu cҫn thiӃt, thѭӡng xuyên

ÿѭӧc sӱ dөng nên ÿѭӧc nҥp sӟm, do vұy khi bӏ chuyӇn ra bӝ nhӟ phө sӁ nhanh chóng gây ra lӛi trang.

Sӕ lѭӧng lӛi trang xҧy ra sӁ tăng lên khi sӕ lѭӧng khung trang sӱ dөng tăng. HiӋn tѭӧng này gӑi là

ngh͓ch lý Belady.

Ví dө: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

Sӱ dөng 3 khung trang , sӁ có 9 lӛi trang phát sinh

1

2

3

4

1

2

5

1

2

3

4

5

Tài li͏u l˱u hành n͡i b͡ - 20 -