Bài giảng Hệ điều hành - Chương 7: Virtual Memory

7.Virtual Memory

Cô cheá phaân trang vaø phaân ñoaïn

Cô cheá boä nhôù aûo

Caùc chieán löôïc quaûn lyù

– Fetch Policy

– Placement policy

– Page replacement policy

Caáp phaùt frame cho process

Thrashing

-X.1-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

Cô cheá phaân trang (paging)

Cô cheá phaân trang cho pheùp khoâng gian ñòa chæ thöïc (physical

address space) cuûa moät process coù theå khoâng lieân tuïc nhau.

Boä nhôù thöïc ñöôïc chia thaønh caùc khoái kích thöôùc coá ñònh baèng nhau

goïi laø frame.

– Thoâng thöôøng kích thöôùc cuûa frame laø luõy thöøa cuûa 2, töø khoaûng 512

byte ñeán 16MB

Boä nhôù luaän lyù (logical memory) cuõng ñöôïc chia thaønh khoái cuøng

kích thöôùc goïi laø trang nhôù (page).

Heä ñieàu haønh phaûi thieát laäp moät baûng phaân trang (page table) ñeå

aùnh xaï ñòa chæ aûo, luaän lyù thaønh ñòa chæ thöïc (address translation

scheme)

– Moãi process coù moät baûng phaân trang ñöôïc quaûn lyù baèng moät con troû löu

giöõ trong PCB. Coâng vieäc naïp baûng phaân trang vaøo heä thoáng (do CPU

dispatcher thöïc hieän) laø moät phaàn cuûa chuyeån ngöõ caûnh

Cô cheá phaân trang khieán boä nhôù bò phaân maûnh noäi, tuy nhieân laïi

khaéc phuïc ñöôïc phaân maûnh ngoaïi.

-X.2-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

1

Cô cheá phaân trang (t.t)

fram e

number

0

1

2

page0

page1

page2

page3

1

4

3

5

0

1

2

3

page0

page2

page1

page3

3

4

5

pagetable

logicalmemory

physicalmemory

-X.3-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

Moâ hình chuyeån ñoåi ñòa chæ

Ñòa chæ nhôù do CPU taïo ra (logical address) goàm coù:

– Page number (p) – ñöôïc duøng laøm chæ muïc doø tìm trong baûng

phaân trang. Moãi muïc trong baûng phaân trang chöùa ñòa chæ cô sôû

(hay chæ soá frame) cuûa trang töông öùng trong boä nhôù thöïc.

– Page offset (d) – ñöôïc keát hôïp vôùi ñòa chæ cô sôû (base address)

ñeå ñònh vò moät ñòa chæ thöïc.

Neáu kích thöôùc cuûa khoâng gian ñòa chæ aûo laø 2^m, kích

thöôùc cuûa trang laø 2ⁿ

pageoffset

d

pagenumber

p

n bits

m-n bits

(ñònh vò töø 0 ÷ 2^m-n-1)

(ñònh vò töø 0 ÷ 2ⁿ-1)

Do ñoù, baûng phaân trang seõ coù toång coäng 2^m/2ⁿ= 2^m-nmuïc

-X.4-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

2

Paging Hardware

f

physical

address

logical

f000… 0000

f111… 1111

address

d

f

d

CPU

p

f

physical

memory

Neáu kích thöôùc cuûa khoâng

gian nhôù thöïc laø 2^lbytes,

pagetable

thì moãi muïc cuûa baûng phaân

framenumber frameoffset

f(l-nbits) d(nbits)

trang coù l-n bits

-X.5-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

Chuyeån ñoåi boä nhôù vôùi paging

-X.6-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

3

Hieän thöïc baûng phaân trang

Baûng phaân trang ñöôïc löu giöõ trong boä nhôù chính (kernel

memory)

– Moãi process coù moät baûng phaân trang

– Thanh ghi page-table base (PTBR) troû ñeán baûng phaân trang

– Thanh ghi page-table length (PTLR) bieåu thi kích thöôùc cuûa baûng

phaân trang (vaø duøng ñeå baûo veä boä nhôù)

Moãi taùc vuï truy caäp döõ lieäu/leänh caàn hai thao taùc truy

xuaát vuøng nhôù

– Moät thao taùc truy xuaát baûng phaân trang (page number: p) vaø moät

thao taùc truy xuaát döõ lieäu/leänh (page offset: d – displacement)

– Thöôøng duøng moät boä phaän cache phaàn cöùng coù toác ñoä truy xuaát

vaø tìm kieám cao, goïi laø thanh ghi keát hôïp (associative register)

hoaëc translation look-aside buffers (TLBs)

-X.7-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

Associative Register (hardware)

Thanh ghi keát hôïp (associative register): hoã trôï tìm kieám

truy xuaát döõ lieäu ñoàng thôøi vôùi toác ñoä cöïc nhanh.

Soá muïc cuûa TLB

Page#

Frame#

khoaûng 8 ÷ 2048

TLB laø “cache” cuûa

baûng phaân trang

Khi coù chuyeån ngöõ

caûnh, TLB bò xoùa

Khi TLB bò ñaày,

thay theá baèng LRU

AÙnh xaï ñòa chæ aûo (A’, A’’)

–Neáu A’ naèm trong TLB (HIT)⇒ laáy ngay ñöôïc chæ soá frame ⇒ tieát

kieäm ñöôïc ~ 10% thôøi gian tìm kieám.

–Ngöôïc laïi (MISS), phaûi tìm chæ soá frame töø baûng phaân trang nhö

bình thöôøng.

-X.8-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

4

Paging Hardware vôùi TLB

-X.9-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

Effective Access Time (EAT)

Thôøi gian tìm kieám (associative lookup): ε (ñôn vò)

Thôøi gian moät chu kyø truy xuaát boä nhôù: x (ñôn vò)

Hit Ratio – tæ leä phaàn traêm thôøi gian moät chæ soá trang

ñöôïc tìm thaáy (HIT) trong TLB; tæ leä vôùi soá thanh ghi keát

hôïp cuûa TLB.

– Kí hieäu hit ratio = α

Thôøi gian laáy ñöôïc trang

– Khi trang coù trong TLB (HIT)

ε + x

– Khi trang khoâng coù trong TLB (MISS) ε + 2x

Thôøi gian truy xuaát hieäu duïng - Effective Access Time

(EAT)

EAT = (x + ε)α + (2x + ε)(1 – α)

= (2–α) * x + ε

-X.10-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

5

Effective Access Time (t.t)

Ví duï 1

Ví duï 2

– Associate lookup = 20

– Memory access = 100

– Hit ratio = 0.8

– Associate lookup = 20

– Memory access = 100

– Hit ratio = 0.98

– EAT = (100 + 20) * 0.98 +

– EAT = (100 + 20) * 0.8 +

(200 + 20) * 0.2

(200 + 20) * 0.02

= 1.2 * 100 + 20

= 140

= 1.02 * 100 + 20

= 122

22% slow inmemory

accesstime

40% slow inmemory

accesstime

-X.11-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

Baûo veä boä nhôù

Vieäc baûo veä boä nhôù ñöôïc hieän thöïc baèng caùch gaén vôùi

frame caùc bit baûo veä (protection bits). Caùc bit naøy bieåu

thò caùc thuoäc tính sau

– read-only, read-write, execute-only

Ngoaøi ra, coøn coù moät valid/invalid bit gaén vôùi moãi muïc

trong baûng phaân trang

– “valid”: cho bieát laø trang boä nhôù töông öùng naèm trong khoâng gian

nhôù ñòa chæ aûo cuûa process, do ñoù laø moät trang hôïp leä.

– “invalid”: cho bieát laø trang boä nhôù töông öùng khoâng naèm trong

khoâng gian nhôù ñòa chæ aûo cuûa process, do ñoù laø moät trang baát

hôïp leä.

-X.12-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

6

Baûo veä baèng Valid/Invalid bit

00000

0

framenumber

valid-invalidbit

page0

page1

page2

page3

page4

page5

page6

page7

1

2

3

4

5

6

7

8

9

0

1

2

3

4

5

6

7

2

3

4

7

8

9

0

v

i

page0

page1

page2

10468

12287

page3

page4

page5

...

i

pagen

ª Moãi trang nhôù coù kích thöôùc 2K = 2048

ª Process coù kích thöôùc 10,468 ⇒ phaân maûnh noäi ôû page 5

⇒ caùc ñòa chæ > 12287 laø caùc ñòa chæ invalid.

ª Duøng PTLR ñeå kieåm tra kích thöôùc baûng phaân trang

-X.13-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

Hierarchical Page Table

Caùc heä thoáng hieän ñaïi ñeàu hoã trôï khoâng gian ñòa chæ aûo

raát lôùn (2³²ñeán 2⁶⁴).

– Kích thöôùc trang nhôù laø 4KB (= 2¹²) ⇒ baûng phaân trang seõ coù ~

2³²/2¹²= 2²⁰= 1MB.

– Giaû söû moãi phaàn töû laø moät con troû 32 bit thì moãi process caàn

4MB cho baûng phaân trang /

Moät giaûi phaùp ñöôïc ñaët ra laø chia thaønh nhieàu baûng phaân

trang quaûn lyù caùc vuøng khoâng gian boä nhôù aûo khaùc

nhau – baûng ña möùc (multilevel paging table).

Cô cheá taïo baûng phaân trang 2-möùc (two-level page

table), hay coøn ñöôïc goïi laø forward-mapped page table

trong heä thoáng Intel Pentium^®-II

-X.14-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

7

Moâ hình baûng 2-möùc (two-level)

-X.15-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

Phaân trang 2-möùc

Moät ñòa chæ luaän lyù (treân heä thoáng 32-bit vôùi trang nhôù 4K)

ñöôïc chia thaønh caùc phaàn sau:

– Page number: 20 bit

page#

offset

12bit

Neáu moãi muïc 4 byte

⇒ 2²⁰* 4 byte = 4 MB

– Page offset: 12 bit

20bit

Baûng phaân trang cuõng bò chia nhoû neân page number

cuõng ñöôïc chia nhoû thaønh 2 phaàn:

– 10-bit page number

pageoffset

pagenumber

– 10-bit page offset

p₁

p₂

d

10bit

12bit

10bit

Vì vaäy,moät ñòa luaän lyù seõ nhö hình veõ beân

– p₁: chæ muïc cuûa baûng ngoaøi (outer page table)-möùc 1

– p₂: ñoä dôøi (displacement) ôû trong trang möùc 2 (xaùc ñònh bôûi *p₁)

-X.16-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

8

Sô ñoà aùnh xaï ñòa chæ

Sô ñoà aùnh xaï ñòa chæ (address-translation scheme) cho

kieán truùc baûng phaân trang 2 möùc, 32-bit ñòa chæ

MemoryAddress:A

A

-X.17-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

Phaân trang ña möùc (multilevel)

Khoâng gian ñòa chæ luaän lyù 64-bit vôùi trang nhôù 4K

– Trong sô ñoà phaân trang 2-möùc, soá muïc cuûa baûng phaân trang =

2⁵²(2⁶⁴/2¹²= 2⁵²) ⇒ quaù lôùn. Thöïc hieän töông töï moâ hình 2 möùc,

phaân chia thaønh baûng 3, 4,..., n-möùc

pagenumber pageoffset

52 12

pagenumber pageoffset

42 10 12

pagenumber pageoffset

22 1010 10

32

10 10

2

… …

– Heä thoáng SPARC 32-bit hoã trôï cô cheá 3-möùc coøn caùc heä thoáng

Motorolla 68030 32 bit hoã trôï cô cheá 4-möùc. Heä thoáng 64bit

UltraSPARC thì duøng baûng phaân trang 7-möùc

– Hieäu suaát cuûa heä thoáng phaân trang ña möùc ?

-X.18-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

9

Baûng baêm (hashed page table)

Duøng yù töôûng cuûa baûng baêm ñeå giaûm bôùt khoâng gian

baûng phaân trang, taêng toác ñoä tìm kieám trang.

– Raát phoå bieán trong caùc heä thoáng lôùn hôn 32 bit ñòa chæ.

Ñeå giaûi quyeát ñuïng ñoä, moãi phaàn töû cuûa baûng phaân trang

quaûn lyù moät danh saùch lieân keát. Moãi phaàn töû danh saùch

chöùa chæ soá trang aûo vaø chæ soá frame töông öùng.

– Chæ soá trang aûo (virtual page number) ñöôïc bieán ñoåi qua haøm

baêm thaønh moät hashed value. Caùc thoâng tin nhö chæ soá trang aûo

vaø chæ soá frame seõ ñöôïc löu vaøo danh saùch lieân keát taïi vò trí öùng

vôùi hashed value.

Giaûi thuaät doø tìm trang:

– Chæ soá trang aûo ñöôïc bieán ñoåi thaønh hashed value (vôùi cuøng haøm

baêm nhö treân). Hashed value ñöôïc duøng ñeå tìm ra phaàn töû töông

öùng trong baûng phaân trang. Sau ñoù, doø tìm trong danh saùch lieân

keát vôùi chæ soá trang aûo ñeå trích ruùt ra ñöôïc frame töông öùng.

-X.19-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

Hashed Page Tables

Caùc heä thoáng 64-bit ñòa chæ thöôøng duøng clustered page table, i.e.

moãi muïc trong hash table tham chieáu ñeán nhieàu trang (~ 16 trang)

thay vì 1 trang.

-X.20-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

10

Chia seû caùc trang nhôù

Process1

ed1

0

1

data1

data3

ed1

0

3

4

6

1

2

ed2

ed3

1

2

3

Process2

ed1

3

4

ed2

0

3

4

6

7

data1

5

ed2

1

2

3

6

ed3

7

data2

ed1

ed2

data2

0

3

8

4

6

2

1

2

3

9

ed2

10

data3

Process3

-X.21-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

Phaân ñoaïn (segmentation)

Nhìn laïi cô cheá phaân trang

– user-view (khoâng gian ñòa chæ aûo) taùch bieät vôùi khoâng gian boä

nhôù thöïc. Cô cheá phaân trang thöïc hieän pheùp aùnh xaï user-view

vaøo boä nhôù thöïc.

Trong thöïc teá, döôùi goùc nhìn cuûa user, moät chöông trình

caáu thaønh töø nhieàu phaân ñoaïn (segment). Moãi phaân

ñoaïn laø moät ñôn vò luaän lyù, ví duï nhö:

– main program, procedure, function, local variables, global

variables, common block, stack, symbol table, arrays

Cô cheá phaân ñoaïn laø moâ hình quaûn lyù boä nhôù hoã trôï

user-view

– Khoâng gian ñòa chæ aûo laø moät taäp caùc phaân ñoaïn (segment), moãi

phaân ñoaïn coù teân vaø kích thöôùc rieâng.

– Moät ñòa chæ luaän lyù ñöôïc ñònh vò baèng teân phaân ñoaïn vaø ñoä dôøi

(offset) beân trong phaân ñoaïn ñoù (so saùnh vôùi phaân trang ???)

-X.22-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

11

User-view cuûa moät chöông trình

Thoâng thöôøng, moät chöông trình

ñöôïc bieân dòch. Trình bieân dòch

stack

procedure

seõ töï ñoäng xaây döïng caùc

segment.

symbol

table

Ví duï, trình bieân dòch Pascal seõ

taïo ra caùc segment sau:

function

sqrt

– Global variables

mainprogram

– Procedure call stack

– Procedure/function code

– Local variable

Trình loader seõ gaùn moãi

segment moät soá ñònh danh

Logicaladdressspace

rieâng.

-X.23-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

Moâ hình cô cheá phaân ñoïan

physicalmemoryspace

userspace

1

4

2

3

4

2

-X.24-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

12

Toå chöùc cuûa cô cheá phaân ñoaïn

Ñòa chæ luaän lyù laø moät caëp giaù trò

<segment-number, offset>

Baûng phaân ñoaïn (segment table)

– base – chöùa ñòa chæ khôûi ñaàu cuûa phaân ñoaïn trong boä nhôù

– limit – xaùc ñònh kích thöôùc cuûa phaân ñoaïn

Segment-table base register (STBR): troû ñeán vò trí baûng

phaân ñoaïn trong boä nhôù

Segment-table length register (STLR): soá segment cuûa

chöông trình

⇒ Moät chæ soá segment s laø hôïp leä neáu s < STLR

-X.25-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

Moät ví duï veà cô cheá phaân ñoaïn

stack

1400

procedure

segment0

2400

3200

segment3

limit base

1000 1400

400 6300

400 4300

1100 3200

0

1

2

3

4

segment0

symbol

table

segment3

segment2

segment4

function

sqrt

4300

4700

segment4

mainprogram

1000 4700

segment

table

segment1

segment2

5700

6300

6700

segment1

Logicaladdressspace

physicalmemoryspace

-X.26-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

13

Phaàn cöùng hoã trôï phaân ñoaïn

segment

s

table

limit base

s

d

CPU

yes

physical

memory

<

+

no

trap;addressingerror

-X.27-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

Chuyeån ñoåi boä nhôù phaân ñoaïn

-X.28-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

14

Chia seû caùc phaân ñoaïn

limit

25286 43062

4425 68348

base

editor

43062

data1

0

1

segment1

editor

data1

segment0

segmenttable

processP₁

Logicaladdressspace

processP₁

68348

72773

editor

data2

limit

25286 43062

8850 90003

base

90003

98553

0

1

data2

segment1

segment0

segmenttable

processP₂

Logicaladdressspace

processP₂

physicalmemory

-X.29-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

Nhìn laïi paging vaø segmentation

Caùc tham chieáu ñeán boä nhôù ñöôïc chuyeån ñoåi ñoäng

thaønh ñòa chæ thöïc luùc process ñang thöïc thi

Moät process coù theå ñöôïc chi thaønh caùc phaàn nhoû (page

hay segment); caùc phaàn naøy ñöôïc naïp vaøo caùc vò trí

khoâng lieân tuïc trong boä nhôù chính

Nhaän xeùt quan troïng: khoâng phaûi taát caùc caùc phaàn cuûa

moät processs caàn thieát phaûi ñöôïc naïp vaøo boä nhôù chính

taïi cuøng moät thôøi ñieåm

Ví duï

– Ñoaïn maõ ñieàu khieån caùc loãi hieám khi xaûy ra

– Caùc arrays, list, tables ñöôïc caáp phaùt boä nhôù (caáp phaùt tónh)

nhieàu hôn yeâu caàu caàn thieát

– Moät soá tính naêng ít khi ñöôïc duøng cuûa moät chöông trình

– Ngay caû khi toaøn boä chöông trình ñeàu caàn duøng thì … coù theå

khoâng caàn duøng toaøn boä cuøng moät luùc

-X.30-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

15

Quaù trình thöïc thi cuûa process

OS naïp moät soá phaàn cuûa chöông trình vaøo boä nhôù

Moãi baûng phaân trang/ñoaïn coù theâm moät present bit cho

bieát phaàn töông öùng coù naèm trong boä nhôù chính hay

khoâng.

Khi coù moät tham chieáu naèm trong phaàn khoâng coù trong

boä nhôù chính (present bit = 0) thì moät ngaét ñöôïc kích

hoaït goïi laø memory fault

Process chuyeån veà traïng thaùi Blocking

OS phaùt ra moät yeâu caàu ñoïc ñóa ñeå naïp phaàn ñöôïc

tham chieáu vaøo boä nhôù chính vaø trong khi ñoù, moät

process khaùc ñöôïc chieám quyeàn thöïc thi

Sau khi I/O hoaøn taát, moät ngaét ñöôïc kích hoaït, baùo cho

OS chuyeån process töông öùng veà traïng thaùi Ready

-X.31-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

Öu ñieåm cuûa boä nhôù aûo

Soá löôïng process trong boä nhôù nhieàu hôn

Moät process coù theå thöïc thi ngay caû khi kích thöôùc cuûa

noù lôùn hôn boä nhôù thöïc

Boä nhôù tham chieáu bôûi moät ñòa chæ luaän lyù ñöôïc goïi laø

boä nhôù aûo (virtual memory)

– Bao goàm boä nhôù thöïc + moät phaàn boä nhôù thöù caáp (ñóa cöùng,...)

– Nhaèm ñaït hieäu quaû cao, caùc dòch vuï file system thöôøng ñöôïc boû

qua; ñoïc/ghi ñóa tröïc tieáp vôùi caùc khoái döõ lieäu lôùn hôn so vôùi

khoái cuûa heä thoáng file.

– Thoâng thöôøng phaàn boä nhôù aûo ñöôïc löu tröõ ôû moät vuøng ñaëc

bieät goïi laø khoâng gian traùo ñoåi (swap space). Ví duï file system

swap trong Unix/Linux, file pagefile.sys trong Windows2K

Vieäc chuyeån ñoåi töø ñòa chæ luaän lyù thaønh ñòa chæ thöïc ñöôïc thöïc hieän

vôùi söï hoã trôï cuûa phaàn cöùng (memory management hardware)

-X.32-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

16

Yeâu caàu ñoái vôùi boä nhôù aûo

Phaàn cöùng memory management phaûi hoã trôï paging

vaø/hoaëc segmentation

OS phaûi quaûn lyù söï di chuyeån cuûa trang/ñoaïn giöõa boä

nhôù chính vaø boä nhôù thöù caáp

Trong phaïm vi chöông naøy, chuùng ta thaûo luaän veà söï hoã

trôï caáp phaàn cöùng tröôùc, sau ñoù laø caùc giaûi thuaät cuûa heä

ñieàu haønh

Söï hoã trôï cuûa phaàn cöùng ñoái vôùi phaân trang vaø phaân

ñoaïn ñaõ ñöôïc khaûo saùt ôû chöông 9. Chæ coù moät ñieåm

khaùc bieät laø moãi muïc (entry) cuûa baûng phaân trang/ñoaïn

coù theâm caùc bit traïng thaùi ñaëc bieät

– Present bit = 1⇒ hôïp leä vaø in-memory; = 0 ⇒ not-in-memory

hoaëc khoâng hôïp leä

– Modified bit: trang/ñoaïn coù thay ñoåi keå töø khi ñöôïc naïp vaøo hay

khoâng

-X.33-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

Ñieàu khieån page fault

-X.34-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

17

Keát hôïp trang vaø ñoaïn

Nhaèm keát hôïp caùc öu ñieåm ñoàng thôøi haïn cheá caùc khuyeát ñieåm cuûa

hai moâ hình phaân trang vaø phaân ñoaïn

Coù raát nhieàu moâ hình keát hôïp. Sau ñaây laø moät moâ hình ñôn giaûn

Moãi process seõ coù:

– Moät baûng phaân ñoaïn

– Nhieàu baûng phaân trang: moãi phaân ñoaïn coù moät baûng phaân trang

Moät ñòa chæ luaän lyù (ñòa chæ aûo) bao goàm:

– segment number: laø chæ muïc cuûa moät phaàn töû trong baûng phaân ñoaïn,

phaàn töû naøy chöùa ñòa chæ cô sôû (base address) cuûa baûng phaân trang

trong phaân ñoaïn ñoù

– page number: laø chæ muïc trong baûng phaân trang, duøng ñeå tính ra chæ soá

frame trong boä nhôù thöïc töông öùng

– offset: duøng ñeå ñònh vò moät vò trí nhôù trong frame noùi treân.

-X.35-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

Sô ñoà chuyeån ñoåi ñòa chæ

-X.36-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

18

Moâ hình keát hôïp ñôn giaûn

Segment Base: ñòa chæ thöïc cuûa baûng phaân trang

Present bit vaø modified bits chæ toàn taïi trong baûng phaân

trang

Caùc thoâng tin baûo veä vaø chia seû vuøng nhôù thöôøng naèm

trong baûng phaân ñoaïn

– Ví duï: read-only/read-write bit, ...

-X.37-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

Caùc giaûi thuaät cuûa OS

OS cung caáp caùc thö vieän quaûn lyù boä nhôù aûo.

Caùc chöông trình quaûn lyù boä nhôù aûo cuûa OS phuï thuoäc

vaøo söï hoã trôï cuûa phaàn cöùng trong vieäc phaân trang,

phaân ñoaïn hoaëc keát hôïp caû hai.

Raát ít heä thoáng söû duïng cô cheá phaân ñoaïn thuaàn tuùy maø

thoâng thöôøng seõ söû duïng moâ hình keát hôïp trong ñoù caùc

segment ñöôïc aùp duïng cô cheá phaân trang. Nhö vaäy, vaán

ñeà caàn giaûi quyeát cuûa caùc giaûi thuaät naïp, thay theá,...chuû

yeáu höôùng ñeán ñoái töôïng laø trang nhôù.

– Fetch policy

– Placement policy

– Replacement policy

Muïc tieâu cuûa caùc giaûi thuaät naøy laø giaûm thieåu page fault

-X.38-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

19

Fetch & placement policy

Fetch Policy

– Xaùc ñònh thôøi ñieåm neân naïp trang nhôù vaøo boä nhôù. Coù hai chieán

löôïc thoâng duïng

– Demand paging: chæ naïp trang vaøo boä nhôù chính khi vaø chæ khi coù

tham chieáu ñeán trang ñoù (i.e.: chæ naïp theo yeâu caàu maø thoâi)

Khi process môùi thöïc thi thì coù nhieàu page fault nhöng sau ñoù soá

page fault seõ giaûm daàn

– Pre-paging naïp tröôùc caùc trang nhôù: döïa treân tính locality

Placement policy

– Xaùc ñònh vò trí ñaët moät trang nhôù cuûa process trong boä nhôù thöïc

– Vôùi heä thoáng segmentation thuaàn tuùy: first-fit, next fit...

– Vôùi heä thoáng paging hoaëc keát hôïp pagin/segmentation:

Phaàn cöùng quaûn lyù boä nhôù quyeát ñònh vò trí ñaët trang, tuy

nhieân vì caùc trang nhôù coù kích thöôùc nhö nhau neân khoâng

gaëp phaûi khoù khaên gì

-X.39-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

Replacement Policy

Giaûi quyeát vaán ñeà choïn löïa moät trang trong boä nhôù

chính seõ bò thay theá khi coù moät trang môùi caàn naïp vaøo

boä nhôù chính. Tình huoáng naøy xaûy ra khi boä chính ñaày

(khoâng coøn frame troáng naøo)

Khoâng phaûi toaøn boä trang trong boä nhôù ñeàu coù theå ñöôïc

thay, coù moät soá frames bò locked

– Ña soá caùc kernel löu giöõ caùc thoâng tin ñieàu khieån vaø caùc caáu

truùc döõ lieäu quan troïng cuûa heä thoáng trong caùc locked frames

Caùc giaûi thuaät thay theá trang

– Least recently used (LRU)

– First-in, first-out (FIFO)

– Clock

Caùc giaûi thuaät thay theá trang phuï thuoäc vaøo resident set

(soá frame caáp cho moãi process)

-X.40-

Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

20

Bài giảng Hệ điều hành - Chương 7: Virtual Memory - Thoại Nam