Giáo trình môn Hệ điều hành - Chương 8: Bộ nhớ ảo
Hệ thống tại một thời điểm có 5 process:
process 1 cần 5 frame, process 2 cần 15
frame, process 3 cần 10 frame, process 4
cần 9 frame, process 5 cần 11 frame. Hệ
thống hiện có 30 frame. Tính xem mỗi
process được cấp bao nhiêu frame?
Phân bổ đều?
Theo tỷ lệ
30 trang |
Chia sẻ: nguyenlam99 | Lượt xem: 1253 | Lượt tải: 1
Bạn đang xem trước 20 trang tài liệu Giáo trình môn Hệ điều hành - Chương 8: Bộ nhớ ảo, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
Chöông 8
Boä Nhôù AÛo
Khoa KTMT 2
Noäi dung trình baøy
Toång quan veà boä nhôù aûo
Caøi ñaët boä nhôù aûo : demand paging
Caøi ñaët boä nhôù aûo : Page Replacement
– Caùc giaûi thuaät thay trang (Page Replacement Algorithms)
Vaán ñeà caáp phaùt Frames
Vaán ñeà Thrashing
Caøi ñaët boä boä nhôù aûo : Demand Segmentation
Khoa KTMT 3
1. Toång quan boä nhôù aûo
Nhaän xeùt: khoâng phaûi taát caû caùc phaàn cuûa moät process
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 thöïc söï
– Moät soá tính naêng ít khi ñöôïc duøng cuûa moät chöông trình
– Caû chöông trình thì cuõng coù ñoaïn code chöa caàn duøng
Boä nhôù aûo (virtual memory): Boä nhôù aûo laø moät kyõ thuaät
cho pheùp xöû lyù moät tieán trình khoâng ñöôïc naïp toaøn boä
vaøo boä nhôù vaät lyù
Khoa KTMT 4
1. Boä nhôù aûo (tt)
Ö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
– Giaûm nheï coâng vieäc cuûa laäp trình vieân
Khoâng gian traùo ñoåi giöõa boä nhôù chính vaø boä nhôù
phuï(swap space).
„ Ví duï:
– swap partition trong Linux
– file pagefile.sys trong Windows
Khoa KTMT 5
2. Caøi ñaët boä nhôù aûo
Coù hai kyõ thuaät:
– Phaân trang theo yeâu caàu (Demand Paging)
– Phaân ñoaïn theo yeâu caàu (Segmentation Paging)
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 chöông naøy,
– Chæ quan taâm ñeán paging
– Phaàn cöùng hoã trôï hieän thöïc boä nhôù aûo
– Caùc giaûi thuaät cuûa heä ñieàu haønh
Khoa KTMT 6
2.1.Phaân trang theo yeâu caàu
demand paging
„ Demand paging: caùc trang cuûa quaù trình chæ ñöôïc naïp
vaøo boä nhôù chính khi ñöôïc yeâu caàu.
Khi coù moät tham chieáu ñeán moät trang maø khoâng coù
trong boä nhôù chính (valid bit) thì phaàn cöùng seõ gaây ra
moät ngaét (goïi laø page-fault trap) kích khôûi page-fault
service routine (PFSR) cuûa heä ñieàu haønh.
PFSR:
1. Chuyeån process veà traïng thaùi blocked
2. Phaùt ra moät yeâu caàu ñoïc ñóa ñeå naïp trang ñöôïc tham chieáu vaøo
moät frame troáng; trong khi ñôïi I/O, moät process khaùc ñöôïc caáp
CPU ñeå thöïc thi
3. Sau khi I/O hoaøn taát, ñóa gaây ra moät ngaét ñeán heä ñieàu haønh;
PFSR caäp nhaät page table vaø chuyeån process veà traïng thaùi
ready.
Khoa KTMT 7
2.2. Loãi trang vaø caùc böôùc xöû lyù
Khoa KTMT 8
2.3. Thay theá trang nhôù
Böôùc 2 cuûa PFSR giaû söû phaûi thay trang vì khoâng tìm
ñöôïc frame troáng, PFSR ñöôïc boå sung nhö sau
1. Xaùc ñònh vò trí treân ñóa cuûa trang ñang caàn
2. Tìm moät frame troáng:
a. Neáu coù frame troáng thì duøng noù
b. Neáu khoâng coù frame troáng thì duøng moät giaûi thuaät thay trang
ñeå choïn moät trang hy sinh (victim page)
c. Ghi victim page leân ñóa; caäp nhaät page table vaø frame table
töông öùng
3. Ñoïc trang ñang caàn vaøo frame troáng (ñaõ coù ñöôïc töø böôùc 2);
caäp nhaät page table vaø frame table töông öùng.
Khoa KTMT 9
2.3. Thay theá trang nhôù (tt)
Khoa KTMT 10
2.4. Caùc thuaät toaùn thay theá trang
„ Hai vaán ñeà chuû yeáu:
Frame-allocation algorithm
– Caáp phaùt cho process bao
nhieâu frame cuûa boä nhôù thöïc?
Page-replacement algorithm
– Choïn frame cuûa process seõ
ñöôïc thay theá trang nhôù
– Muïc tieâu: soá löôïng page-fault
nhoû nhaát
– Ñöôïc ñaùnh giaù baèng caùch thöïc
thi giaûi thuaät ñoái vôùi moät chuoãi
tham chieáu boä nhôù (memory
reference string) vaø xaùc ñònh
soá laàn xaûy ra page fault
Ví duï
„ Thöù töï tham chieáu caùc ñòa chæ
nhôù, vôùi page size = 100:
„ 0100, 0432, 0101, 0612, 0102,
0103, 0104, 0101, 0611, 0102,
0103, 0104, 0101, 0610, 0102,
0103, 0104, 0101, 0609, 0102,
0105
caùc trang nhôù sau ñöôïc tham
chieáu laàn löôït = chuoãi tham
chieáu boä nhôù (trang nhôù)
„ 1, 4, 1, 6, 1,
„ 1, 1, 1, 6, 1,
„ 1, 1, 1, 6, 1,
„ 1, 1, 1, 6, 1,
„ 1
Khoa KTMT 11
a) Giaûi thuaät thay trang FIFO
Caùc döõ lieäu caàn bieát ban ñaàu:
– Soá khung trang
– Tình traïng ban ñaàu
– Chuoãi tham chieáu
– Trang nhớ cũ nhất sẽ được thay thế
Khoa KTMT 12
Nghòch lyù Belady
Khoa KTMT 13
Nghòch lyù Belady
Baát thöôøng (anomaly) Belady: soá page fault taêng maëc daàu quaù trình
ñaõ ñöôïc caáp nhieàu frame hôn.
Khoa KTMT 14
2.4 b)Giaûi thuaät thay trang OPT(optimal)
Giaûi thuaät thay trang OPT
– Thay theá trang nhôù seõ ñöôïc tham chieáu treã nhaát trong töông lai
– Khó hiện thực?
Ví duï: moät process coù 7 trang, vaø ñöôïc caáp 3 frame
Khoa KTMT 15
c) Giaûi thuaät laâu nhaát chöa söû duïng
Least Recently Used (LRU)
Ví duï:
Moãi trang ñöôïc ghi nhaän (trong baûng phaân trang) thôøi ñieåm ñöôïc
tham chieáu trang LRU laø trang nhôù coù thôøi ñieåm tham chieáu nhoû
nhaát (OS toán chi phí tìm kieám trang nhôù LRU naøy moãi khi coù page fault)
Do vaäy, LRU caàn söï hoã trôï cuûa phaàn cöùng vaø chi phí cho vieäc tìm
kieám. Ít CPU cung caáp ñuû söï hoã trôï phaàn cöùng cho giaûi thuaät LRU.
Khoa KTMT 16
LRU vaø FIFO
So saùnh caùc giaûi thuaät thay trang LRU vaø FIFO
chuoãi tham chieáu
trang nhôù
Khoa KTMT 17
Giải thuật cơ hội thứ hai
Sử dụng các bit tham khảo tại những khoản thời gian đều đặn
Dùng một byte cho mỗi trang trong một bảng nằm trong bộ nhớ
Dùng một thanh ghi dịch chứa lịch sử tham khảo trong 8 lần gần nhất
VD: 00110101, 00000000, 11111111
Là giải thuật thay thế FIFO, trước khi thay thế một trang xem xét bit tham
khảo của nó
Đôi khi sử dụng hai bit: tham khảo và sửa đổi như một cặp (x,x):
– (0,0) không được dùng mới đây và không được sửa đổi-là trang tốt nhất để
thay thế.
– (0,1) không được dùng mới đây nhưng được sửa đổi-không thật tốt vì
trang cần được viết ra trước khi thay thế.
– (1,0) được dùng mới đây nhưng không được sửa đổi-nó có thể sẽ nhanh chóng được
dùng lại.
– (1,1) được dùng mới đây và được sửa đổi-trang có thể sẽ nhanh chóng được dùng lại
và trang sẽ cần được viết ra đĩa trước khi nó có thể được thay thế.
Khoa KTMT 18
Giải thuật cơ hội thứ hai (tt)
Khoa KTMT 19
2.5.Soá löôïng frame caáp cho process
OS phaûi quyeát ñònh caáp cho moãi process bao nhieâu
frame.
– Caáp ít frame nhieàu page fault
– Caáp nhieàu frame giaûm möùc ñoä multiprogramming
Chieán löôïc caáp phaùt tónh (fixed-allocation)
– Soá frame caáp cho moãi process khoâng ñoåi, ñöôïc xaùc ñònh vaøo thôøi
ñieåm loading vaø coù theå tuøy thuoäc vaøo töøng öùng duïng (kích thöôùc
cuûa noù,)
Chieán löôïc caáp phaùt ñoäng (variable-allocation)
– Soá frame caáp cho moãi process coù theå thay ñoåi trong khi noù chaïy
Neáu tyû leä page-fault cao caáp theâm frame
Neáu tyû leä page-fault thaáp giaûm bôùt frame
– OS phaûi maát chi phí ñeå öôùc ñònh caùc process
Khoa KTMT 20
a) Chieán löôïc caáp phaùt tónh
Caáp phaùt baèng nhau: Ví duï, coù 100 frame vaø 5
process moãi process ñöôïc 20 frame
Caáp phaùt theo tæ leä: döïa vaøo kích thöôùc process
Caáp phaùt theo ñoä öu tieân
m
S
s
pa
m
sS
ps
i
ii
i
ii
for allocation
frames ofnumber total
process of size
5964
137
127
564
137
10
127
10
64
2
1
2
a
a
s
s
m
i
Ví duï:
Khoa KTMT 21
3. Trì treân toaøn boä heä thoáng
Thrashing
Neáu moät process khoâng coù ñuû soá frame caàn thieát thì tæ soá
page faults/sec raát cao.
Thrashing: hieän töôïng caùc trang nhôù cuûa moät process bò
hoaùn chuyeån vaøo/ra lieân tuïc.
Khoa KTMT 22
a)Moâ hình cuïc boä (Locality)
Ñeå haïn cheá thrashing, heä ñieàu haønh phaûi cung caáp cho
process caøng “ñuû” frame caøng toát. Bao nhieâu frame thì
ñuû cho moät process thöïc thi hieäu quaû?
Nguyeân lyù locality (locality principle)
– Locality laø taäp caùc trang ñöôïc tham chieáu gaàn nhau
– Moät process goàm nhieàu locality, vaø trong quaù trình thöïc thi,
process seõ chuyeån töø locality naøy sang locality khaùc
Vì sao hieän töôïng thrashing xuaát hieän?
Khi size of locality > memory size
Khoa KTMT 23
b) Giaûi phaùp taäp laøm vieäc (working set)
„ Ñöôïc thieát keá döïa treân nguyeân lyù locality.
Xaùc ñònh xem process thöïc söï söû duïng bao nhieâu
frame.
Ñònh nghóa:
– WS(t) - soá löôïng caùc tham chieáu trang nhôù cuûa process gaàn
ñaây nhaát caàn ñöôïc quan saùt trong khoảng thời gian .
– - khoaûng thôøi gian tham chieáu
„ Ví duï:
2 4 5 6 9 1 3 2 6 3 9 2 1 4
thôøi ñieåm t
1
= 4
chuoãi tham khaûo
trang nhôù
Khoa KTMT 24
b) Giaûi phaùp taäp laøm vieäc (working set)
Ñònh nghóa: working set cuûa process P
i
, kyù hieäu WS
i
, laø taäp goàm
caùc trang ñöôïc söû duïng gaàn ñaây nhaát.
Nhaän xeùt:
„ quaù nhoû khoâng ñuû bao phuû toaøn boä locality.
„ quaù lôùn bao phuû nhieàu locality khaùc nhau.
„ = bao goàm taát caû caùc trang ñöôïc söû duïng.
Duøng working set cuûa moät process ñeå xaáp xæ locality cuûa noù.
chuoãi tham khaûo trang
Ví duï: = 10 và
Khoa KTMT 25
b) Giaûi phaùp taäp laøm vieäc (working set)
Ñònh nghóa WSS
i
laø kích thöôùc cuûa working set cuûa P
i
:
WSS
i
= soá löôïng caùc trang trong WS
i
chuoãi tham khaûo trang
WSS(t1) = 5 WSS(t2) = 2
Ví duï (tieáp): = 10 và
Khoa KTMT 26
b) Giaûi phaùp taäp laøm vieäc (working set)
„ Ñaët D = WSS
i
= toång caùc working-set size cuûa moïi
process trong heä thoáng.
Nhaän xeùt: Neáu D > m (soá frame cuûa heä thoáng) seõ xaûy ra
thrashing.
Giaûi phaùp working set:
– Khi khôûi taïo moät quaù trình: cung caáp cho quaù trình soá löôïng
frame thoûa maûn working-set size cuûa noù.
– Neáu D > m taïm döøng moät trong caùc process.
Caùc trang cuûa quaù trình ñöôïc chuyeån ra ñóa cöùng vaø caùc
frame cuûa noù ñöôïc thu hoài.
Khoa KTMT 27
b) Giaûi phaùp taäp laøm vieäc (working set)
WS loaïi tröø ñöôïc tình traïng trì treä maø vaãn ñaûm baûo möùc
ñoä ña chöông
Theo veát caùc WS? => WS xaáp xæ (ñoïc theâm trong saùch)
Ñoïc theâm:
Heä thoáng taäp tin
Heä thoáng nhaäp xuaát
Heä thoáng phaân taùn
Khoa KTMT 28
Baøi taäp
Bài 01: Một máy tính 32-bit địa chỉ, sử dụng một bảng trang nhị cấp.
Địa chỉ ảo được phân bổ như sau : 9 bit dành cho bảng trang cấp 1, 11
bit cho bảng trang cấp 2, và cho offset. Cho biết kích thước một trang
trong hệ thống, và địa chỉ ảo có bao nhiêu trang ?
Bài 02: Xét chuỗi truy xuất bộ nhớ sau:
1, 2 , 3 , 4 , 3 , 5 , 1 , 6 , 2 , 1 , 2 , 3 , 7 , 5 , 3 , 2 , 1 , 2 , 3 , 6
Có bao nhiêu lỗi trang xảy ra khi sử dụng các thuật toán thay thế sau
đây, giả sử có 4 khung trang và ban đầu các khung trang đều trống ?
a) LRU
b) FIFO
c) Optimal
d) Cơ hội thứ 2
Bài tập
Cho một process có số frame truy cập như
sau:
1,2,4,3,5,2,3,5,6,7,8,9,1,2,3,4,5,2,3,7,6,4,
5,6,7,9,8,1,2,5
Cho biết có biêu nhiêu tập làm việc
(working set)?
Liệt kê các frame trong từng working set?
Biết = 7.
Khoa KTMT 29
Bài tập
Hệ thống tại một thời điểm có 5 process:
process 1 cần 5 frame, process 2 cần 15
frame, process 3 cần 10 frame, process 4
cần 9 frame, process 5 cần 11 frame. Hệ
thống hiện có 30 frame. Tính xem mỗi
process được cấp bao nhiêu frame?
Phân bổ đều?
Theo tỷ lệ?
Khoa KTMT 30
Các file đính kèm theo tài liệu này:
- _biboo_vn_chuong08_virtualmemory_lung_9201.pdf