Bài giảng Hệ điều hành - Chương 6: Memory Management - Thoại Nam
6. Memory Management
Khaùi nieäm cô sôû
Caùc kieåu ñòa chæ nhôù
Chuyeån ñoåi ñòa chæ nhôù
Overlay vaø swapping
Moâ hình quaûn lyù boä nhôù ñôn giaûn
– Fixed partitioning
– Dynamic partitioning
-9.1-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
Khaùi nieäm cô sôû
Quaûn lyù boä nhôù laø coâng vieäc cuûa heä ñieàu haønh vôùi söï hoã
trôï cuûa phaàn cöùng nhaèm phaân phoái, saép xeáp caùc
process trong boä nhôù sao cho hieäu quaû.
Muïc tieâu caàn ñaït ñöôïc laø naïp caøng nhieàu process vaøo
boä nhôù caøng toát (gia taêng möùc ñoä ña chöông)
Trong haàu heát caùc heä thoáng, kernel seõ chieám moät phaàn
coá ñònh cuûa boä nhôù; phaàn coøn laïi phaân phoái cho caùc
p
Caùc yeâu caàu ñoái vôùi vieäc quaûn lyù boä nhôù
– Caáp phaùt boä nhôù cho caùc process
– Taùi ñònh vò (relocation): khi swapping,...
– Baûo veä: phaûi kieåm tra truy xuaát boä nhôù coù hôïp leä khoâng?
– Chia seû: cho pheùp caùc process chia seû vuøng nhôù chung
– Keát gaùn ñòa chæ nhôù luaän lyù cuûa user vaøo ñòa chæ thöïc (physical)
-9.2-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
1
Caùc kieåu ñòa chæ nhôù
Ñòa chæ vaät lyù (physical address) (ñòa chæ thöïc, ñòa chæ
tuyeät ñoái) laø moät vò trí thöïc trong boä nhôù chính.
Ñòa chæ luaän lyù (logical address) laø tham chieáu ñeán moät vò
trí nhôù ñoäc laäp vôùi caáu truùc, toå chöùc vaät lyù cuûa boä nhôù
– Caùc trình bieân dòch (compiler) taïo ra maõ leänh chöông trình maø
trong ñoù moïi tham chieáu boä nhôù ñeàu laø ñòa chæ luaän lyù
Ñòa chæ töông ñoái (relative address) laø moät kieåu ñòa chæ
luaän lyù trong ñoù caùc ñòa chæ ñöôïc bieåu dieãn töông ñoái so
vôùi moät ñieåm xaùc ñònh naøo ñoù trong chöông trình (ví duï:
12 byte so vôùi ñieåm baét ñaàu chöông trình,...)
Khi moät leänh ñöôïc thöïc thi, caùc tham chieáu ñeán ñòa chæ
luaän lyù phaûi ñöôïc chuyeån ñoåi thaønh ñòa chæ thöïc. Thao
taùc chuyeån ñoåi naøy thöôøng coù söï hoã trôï cuûa phaàn cöùng
ñeå ñaït hieäu suaát cao.
-9.3-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
Naïp chöông trình vaøo boä nhôù(t.t)
Boä linker: keát hôïp caùc object module thaønh moät file nhò
phaân khaû thöïc thi goïi laø load module.
Boä loader: naïp load module vaøo boä nhôù chính
System
staticlinking
Library
System
Library
dynamiclinking
-9.4-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
2
Cô cheá thöïc hieän linking
0
0
ModuleA
ModuleA
Relocatable
ObjectModules
CALLB
LengthL
JMP “L”
Return
Return
L-1
L
L-1
0
ModuleB
ModuleB
CALLC
JMP “L+M”
LoadModule
LengthM
LengthN
L+M-1
Return
Return
M-1
0
L+M ModuleC
ModuleC
L+M+N-1
Return
Return
N-1
-9.5-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
Chuyeån ñoåi ñòa chæ nhôù
Chuyeån ñoåi ñòa chæ – quaù trình aùnh xaï moät ñòa chæ töø
khoâng gian ñòa chæ naøy sang khoâng gian ñòa chæ khaùc.
Bieåu dieãn ñòa chæ nhôù
– Trong source code: symbolic (caùc bieán, haèng, pointer,...)
– Thôøi ñieåm bieân dòch (compile): laø ñòa chæ khaû taùi ñònh vò (re-
locatable address), hay laø ñòa chæ töông ñoái (relative address)
Ví duï: a ôû vò trí 14 bytes so vôùi phaàn header cuûa module.
m
taïi ñòa chæ boä nhôù thöïc: 2030
2000
0
intI;
gotop1;
p1
SymbolicAddress
2250
250
Re-locatableAddress
AbsoluteAddress
(PhysicalMemory)
-9.6-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
3
Chuyeån ñoåi ñòa chæ (t.t)
Ñòa chæ leänh (instruction) vaø döõ lieäu (data) ñöôïc
chuyeån ñoåi thaønh ñòa chæ vaät lyù cuûa boä nhôù thöïc coù
theå xaûy ra taïi ba thôøi ñieåm khaùc nhau
– Compile time: neáu bieát tröôùc ñòa chæ boä nhôù thì coù theå keát
gaùn ñòa chæ vaät lyù (ñòa chæ thöïc) luùc bieân dòch.
⇒ Ví duï: chöông trình .COM cuûa MS-DOS, phaùt bieåu assemply
org xxx
⇒ Khuyeát ñieåm: phaûi bieân dòch laïi neáu thay ñoåi ñòa chæ
– Load time: taïi thôøi ñieåm bieân dòch, neáu khoâng bieát ñòa chæ
thöïc thì vaøo thôøi ñieåm loading, phaûi chuyeån ñoåi ñòa chæ khaû
taùi ñònh vò (re-locatable) theo moät moác chuaån (base
address).
Ñòa chæ thöïc ñöôïc tính toaùn laïi vaøo thôøi ñieåm chöông trình
thöïc thi ⇒ phaûi tieán haønh reload neáu ñòa chæ base thay ñoåi.
-9.7-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
Chuyeån ñoåi vaøo thôøi ñieåm dòch
AbsoluteAddresses
(PhysicalMemory
Addresses)
AbsoluteAddresses
(PhysicalMemory
Addresses)
Symbolic
Addresses
PROGRAM
JUMP i
1024
1024
JUMP 1424
JUMP 1424
i
j
1424
1424
2224
LOAD j
DA
2224
SourceCode
AbsoluteLoadModule
ProcessImage
-9.8-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
4
Chuyeån ñoåi vaøo thôøi ñieåm naïp
Relative
(Relocatable)
Addresses
AbsoluteAddresses
(PhysicalMemory
Addresses)
Symbolic
Addresses
PROGRAM
JUMP i
0
1024
JUMP 400
JUMP 1424
1424
i
j
400
LOAD j
DATA
LOAD 1200
LOAD 2224
Link/Load
Compile
1200
2224
Relative
SourceCode
ProcessImage
LoadModule
-9.9-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
Chuyeån ñoåi ñòa chæ (t.t)
Execution time: quaù trình chuyeån
ñoåi ñöôïc trì hoaõn ñeán thôøi ñieåm
thöïc thi (run time)
Relative(Relocatable)
Addresses
– Trong quaù trình thöïc thi, process
coù theå ñöôïc di chuyeån töø segment
naøy sang segment khaùc trong boä
nhôù.
0
JMP 400
400
– CPU taïo ra caùc ñòa chæ töông ñoái
– Caàn söï hoã trôï cuûa phaàn cöùng cho
vieäc aùnh xaï ñòa chæ (ví duï coù thanh
ghi base vaø limit,...)
1200
MAX
– Söû duïng trong ña soá caùc OS ña
duïng (general-purpose) trong ñoù
coù caùc cô cheá swapping, paging,
segmentation
=2000
-9.10-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
5
Dynamic Linking
Quaù trình link moät soá module ngoaøi (external module)
ñöôïc thöïc hieän sau khi ñaõ taïo xong load module (i.e. file
coù theå thöïc thi – executable)
– Ví duï trong Windows: module ngoaøi laø caùc file .DLL coøn trong
Unix, caùc module ngoaøi laø caùc file .so (shared library)
Load module chæ chöùa caùc tham chieáu (reference) ñeán
caùc external module. Caùc tham chieáu naøy coù theå ñöôïc
chuyeån ñoåi vaøo hai thôøi ñieåm sau:
– Loading time (load-time dynamic linking)
– Run time: khi coù moät lôøi goïi ñeán thuû tuïc ñöôïc ñònh nghóa trong
external module (run-time dynamic linking)
OS chòu traùch nhieäm tìm caùc external module vaø keát noái
vaøo load module (kieåm tra xem external module ñaõ naïp
vaøo boä nhôù chöa)
-9.11-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
Öu ñieåm cuûa Dynamic Linking
Thoâng thöôøng, external module laø moät thuû tuïc, thö vieän
cung caáp caùc tieän ích cuûa OS. Caùc chöông trình thöïc thi
coù theå duøng caùc phieân baûn khaùc nhau cuûa external
module maø khoâng caàn söûa ñoåi, bieân dòch laïi.
Chia seû maõ (code sharing): moät external module chæ caàn
naïp vaøo boä nhôù moät laàn. Caùc process caàn duøng external
module naøy thì cuøng chia seû ñoaïn maõ cuûa external
m
Phöông phaùp dynamic linking caàn söï hoã trôï cuûa OS trong
vieäc kieåm tra xem moät thuû tuïc naøo ñoù coù theå ñöôïc chia
seû giöõa caùc process hay laø phaàn maõ cuûa rieâng moät
process ( bôûi vì chæ coù OS môùi coù quyeàn thöïc hieän vieäc
kieåm tra naøy).
-9.12-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
6
Dynamic Loading
Cô cheá: chæ khi naøo ñöôïc goïi ñeán thì moät thuû tuïc môùi
ñöôïc naïp vaøo boä nhôù chính ⇒ taêng ñoä hieäu duïng cuûa boä
nhôù (memory utilization) bôûi vì caùc thuû tuïc ít ñöôïc duøng
seõ khoâng bao giôø chieám choã trong boä nhôù
Raát hieäu quaû trong tröôøng hôïp toàn taïi khoái löôïng lôùn maõ
chöông trình coù taàn suaát söû duïng thaáp, khoâng ñöôïc söû
duïng thöôøng xuyeân (ví duï caùc thuû tuïc xöû lyù loãi)
Khoâng caàn söï hoã trôï ñaëc bieät cuûa heä ñieàu haønh
– Thoâng thöôøng, user chòu traùch nhieäm thieát keá vaø hieän thöïc caùc
chöông trình coù dynamic-loading.
– Heä ñieàu haønh chuû yeáu cung caáp moät soá thuû tuïc thö vieän hoã trôï,
taïo ñieàu kieän deã daøng hôn cho laäp trình vieân
-9.13-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
Cô cheá Overlay
Taïi moãi thôøi ñieåm, chæ giöõ laïi trong boä nhôù nhöõng
leänh hoaëc döõ lieäu caàn thieát, giaûi phoùng caùc
leänh/döõ lieäu chöa hoaëc khoâng caàn duøng ñeán.
Cô cheá naøy raát höõu duïng khi kích thöôùc moät
process lôùn hôn khoâng gian boä nhôù caáp cho
p
Cô cheá naøy ñöôïc ñieàu khieån bôûi ngöôøi söû duïng
(thoâng qua söï hoã trôï cuûa caùc thö vieän laäp trình)
chöù khoâng caàn söï hoã trôï cuûa heä ñieàu haønh
-9.14-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
7
Cô cheá Overlay (t.t)
Pass1
70K
80K
20K
symbol
table
Pass2
20K
Sym.Table
CommonRoutines 30K
common
routines
Assembler
30K
10K
TotalMemory
Available=150K
overlay
driver
80K
pass2
pass1
70K
-9.15-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
Cô cheá swapping
Moät process coù theå taïm thôøi bò swap ra khoûi boä
nhôù chính vaø löu treân moät heä thoáng löu tröõ phuï.
Sau ñoù, process coù theå ñöôïc naïp laïi vaøo boä nhôù
ñeå tieáp tuïc quaù trình thöïc thi
– Round-robin: swap-out A, swap-in B, thöïc thi C
– Roll out, roll in – duøng trong cô cheá ñònh thôøi theo ñoä
Process coù ñoä öu tieân thaáp hôn seõ bò swap-out
nhöôøng choã cho process coù ñoä öu tieân cao hôn
ñöôïc naïp vaøo boä nhôù ñeå thöïc thi
– Medium-term scheduler
-9.16-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
8
Minh hoïa cô cheá swapping
-9.17-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
Moâ hình quaûn lyù boä nhôù thöïc
Trong chöông naøy, moâ hình quaûn lyù boä nhôù laø moät moâ
hình ñôn giaûn, khoâng coù boä nhôù aûo.
Moät process phaûi ñöôïc naïp hoaøn toaøn vaøo boä nhôù thì
môùi ñöôïc thöïc thi (ngoaïi tröø vieäc söû duïng cô cheá
overlay).
Caùc cô cheá quaûn lyù boä nhôù thöïc sau ñaây raát ít (haàu nhö
khoâng coøn) ñöôïc duøng trong caùc heä thoáng hieän ñaïi, tuy
n
nhôù aûo sau naøy:
– Phaân chia coá ñònh (fixed partitioning)
– Phaân chia ñoäng (dynamic partitioning)
– Phaân trang ñôn giaûn (simple paging)
– Phaân ñoaïn ñôn giaûn (simple segmentation)
-9.18-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
9
Phaân maûnh (fragmentation)
Phaân maûnh ngoaïi (external fragmentation)
– Kích thöôùc khoâng gian boä nhôù coøn troáng ñuû ñeå thoûa maõn
moät yeâu caàu caáp phaùt, tuy nhieân khoâng gian nhôù naøy
khoâng lieân tuïc ⇒ phaûi duøng cô cheá keát khoái (compaction).
Phaân maûnh noäi (internal fragmentation)
– Kích thöôùc vuøng nhôù ñöôïc caáp phaùt coù theå hôi lôùn hôn
vuøng nhôù yeâu caàu. Ví duï: caáp moät khoaûng troáng 18,464
bytes cho moät process yeâu caàu 18,462 bytes
– Hieän töôïng phaân maûnh noäi thöôøng xaûy ra khi boä nhôù thöïc
(physical memory) ñöôïc chia thaønh caùc khoái kích thöôùc coá
ñònh(fixed-sized block) vaø caùc process ñöôïc caáp phaùt theo
ñôn vò khoái. Ví duï: cô cheá phaân trang (paging)
-9.19-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
Phaân maûnh noäi
yeâu caàu keá tieáp laø
operating
system
18,462 bytes !!!
(used)
hole kích thöôùc
1
g
troáng 2 bytes !?!
OS seõ caáp phaùt haún khoái 18,464 bytes
cho yeâu caàu cuûa process ⇒ dö ra 2 bytes
khoâng duøng !
-9.20-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
10
Fixed Partitioning
Chia boä nhôù chính thaønh nhieàu
phaàn khoâng truøng laáp leân nhau goïi
laø caùc partition coù kích thöôùc baèng
nhau hoaëc khaùc nhau
Process naøo coù kích thöôùc nhoû
hôn hoaëc baèng kích thöôùc partition
thì coù theå naïp vaøo partition ñoù.
Neáu chöông trình coù kích thöôùc lôùn
hôn partition thì phaûi duøng cô cheá
overlay.
Nhaän xeùt
– Khoâng hieäu quaû do bò phaân maûnh
noäi: moät chöông trình duø lôùn hay
nhoû ñeàu chieám troïn moät partition.
-9.21-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
Chieán löôïc placement
Partition coù kích thöôùc baèng nhau
– Coøn moät partition troáng ⇒ process
môùi ñöôïc naïp vaøo partition ñoù
– Khoâng coøn partition troáng nhöng
trong ñoù coù process ñang bò blocked
⇒ swap process ñoù ra boä nhôù phuï
nhöôøng choã cho process môùi.
Partition coù kích thöôùc khoâng baèng
nhau
nhaát phuø hôïp vôùi noù
– Coù haøng ñôïi cho moãi partition
– Giaûm thieåu phaân maûnh noäi
– Vaán ñeà: coù theå coù moät soá haøng ñôïi
troáng khoâng (vì khoâng coù process
vôùi kích thöôùc töông öùng) vaø haøng
ñôïi daøy ñaëc
-9.22-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
11
Chieán löôïc placement (t.t)
Partition coù kích thöôùc khoâng
baèng nhau
– Chæ coù moät haøng ñôïi chung
cho caùc partition
– Khi caàn naïp moät process vaøo
boä nhôù chính ⇒ choïn
partition nhoû nhaát coøn troáng
-9.23-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
Dynamic Partitioning
Soá löôïng partition khoâng coá ñònh vaø partition coù kích
thöôùc khaùc nhau
Moãi process ñöôïc caáp phaùt chính xaùc dung löôïng boä nhôù
caàn thieát
Gaây ra hieän töôïng phaân maûnh ngoaïi (external
fragmentation)
-9.24-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
12
Chieán löôïc placement
Duøng ñeå quyeát ñònh caáp phaùt
khoái boä nhôù troáng naøo cho
moät process
Muïc tieâu: giaûm thieåu chi phí
compaction (time consuming)
Caùc chieán löôïc placement
– Best-fit: choïn khoái nhôù troáng
nhoû nhaát
– First-fit: choïn khoái nhôù troáng
phuø hôïp ñaàu tieân keå töø ñaàu
boä nhôù
– Next-fit: choïn khoái nhôù troáng
phuø hôïp ñaàu tieân keå töø vò trí
caáp phaùt cuoái cuøng
– Worst fit: choïn khoái nhôù
troáng lôùn nhaát
-9.25-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
13
13 trang
20680
Free
Bạn đang xem tài liệu "Bài giảng Hệ điều hành - Chương 6: Memory Management - Thoại Nam", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_he_dieu_hanh_chuong_6_memory_management_thoai_nam.pdf
