Giáo trình Nguyên lý hệ điều hành - Trần Ngọc Thái - Chương 3: Quản lý bộ nhớ

 : c?n ph?i duy trì nhi?u
ti?n trình trong b? nh? cùng lúc, v?y m?i ti?n trình s?????c c?p bao nhiêu khung trang.
S? khung trang t?i thi?u:
V?i m?i ti?n trình, c?n ph?i c?p phát m?t s? khung trang t?i thi?u nào ?ó ?? ti?n trình có th? ho?t ??ng.
S? khung trang t?i thi?u này ???c quy ??nh b?i ki?n trúc c?a c?a m?t ch? th?.Khi m?t l?i trang x?y ra
tr??c khi ch? th? hi?n hành hoàn t?t, ch? th???ó c?n ???c tái kh?i ??ng, lúc ?ó c?n có ?? các khung
trang ?? n?p t?t c? các trang mà m?t ch? th? duy nh?t có th? truy xu?t.
S? khung trang t?i thi?u ???c qui ??nh b?i ki?n trúc máy tính, trong khi s? khung trang t?i ?a ???c xác
??nh b?i dung l??ng b? nh? v?t lý có th? s? d?ng.
Các thu?t toán c?p phát khung trang
Có hai h??ng ti?p c?n:
C?p phát c????nh:
C?p phát công b?ng: n?u có m khung trang và n ti?n trình, m?i ti?n trình ???c c?p m /n khung trang.
C?p phát theo t? l?: tùy vào kích th??c c?a ti?n trình ?? c?p phát s? khung trang :
si = kích th??c c?a b? nh???o cho ti?n trình pi
S = S si
m = s? l??ng t?ng c?ng khung trang có th? s? d?ng
C?p phát ai khung trang cho ti?n trình pi : ai = (si / S) m
C?p phát theo ?? ?u tiên : s? d?ng ý t??ng c?p phát theo t? l?, nh?ng nh?ng s? l??ng khung trang c?p
cho ti?n trình ph? thu?c vào ?? ?u tiên c?a ti?n trình, h?n là ph? thu?c kích th??c ti?n trình:
N?u ti?n trình pi phát sinh m?t l?i trang, ch?n m?t trong các khung trang c?a nó ?? thay th?, ho?c ch?n
m?t khung trang c?a ti?n trình khác v?i ?? ?u tiên th?p h?n ?? thay th?.
Thay th? trang toàn c?c hay c?c b?
Có th? phân các thu?t toán thay th? trang thành hai l?p chính:
Giáo trình Nguyên lý h?????u hành – KS. Tr?n Ng?c Thái, ?? môn Tin h?c – ??i h?c DL H?i Phòng
Tài li?u l?u hành n?i b? - 26 -
Thay th? toàn c?c: khi l?i trang x?y ra v?i m?t ti?n trình , ch?n trang « n?n nhân » t? t?p t?t c? các
khung trang trong h? th?ng, b?t k? khung trang ?ó ?ang ???c c?p phát cho m?t ti?n trình khác.
Thay th? c?c b?: yêu c?u ch?????c ch?n trang thay th? trong t?p các khung trang ???c c?p cho ti?n
trình phát sinh l?i trang.
M?t khuy?t ???m c?a thu?t toán thay th? toàn c?c là các ti?n trình không th? ki?m soát ???c t? l? phát
sinh l?i trang c?a mình. Vì th?, tuy thu?t toán thay th? toàn c?c nhìn chung cho phép h? th?ng có nhi?u
kh? n?ng x? lý h?n, nh?ng nó có th? d?n h? th?ng ??n tình tr?ng trì tr? toàn b? (thrashing).
3.5.3.1. Trì tr? toàn b? h? th?ng (Thrashing)
N?u m?t ti?n trình không có ?? các khung trang ?? ch?a nh?ng trang c?n thi?t cho x? lý, thì nó s?
th??ng xuyên phát sinh các l?i trang , và vì th? ph?i dùng ??n r?t nhi?u th?i gian s? d?ng CPU ?? th?c
hi?n thay th? trang. M?t ho?t ??ng phân trang nh? th?????c g?i là s? trì tr? ( thrashing). M?t ti?n trình
lâm vào tr?ng thái trì tr? n?u nó s? d?ng nhi?u th?i gian ?? thay th? trang h?n là ?? x? lý !
Hi?n t??ng trì tr? này ?nh h??ng nghiêm tr?ng ??n ho?t ??ng h? th?ng, xét tình hu?ng sau :
H?????u hành giám sát vi?c s? d?ng CPU.
N?u hi?u su?t s? d?ng CPU quá th?p, h?????u hành s? nâng m?c ????a ch??ng b?ng cách ??a thêm
m?t ti?n trình m?i vào h? th?ng.
H? th?ng có th? s? d?ng thu?t toán thay th? toàn c?c ?? ch?n các trang n?n nhân thu?c m?t ti?n trình
b?t k???? có ch? n?p ti?n trình m?i, có th? s? thay th? c? các trang c?a ti?n trình ?ang x? lý hi?n hành.
Khi có nhi?u ti?n trình trong h? th?ng h?n, thì m?t ti?n trình s?????c c?p ít khung trang h?n, và do ?ó
phát sinh nhi?u l?i trang h?n.
Khi các ti?n trình phát sinh nhi?u l?i trang , chúng ph?i tr?i qua nhi?u th?i gian ch? các thao tác thay
th? trang hoàn t?t, lúc ?ó hi?u su?t s? d?ng CPU l?i gi?m
H?????u hành l?i quay tr? l?i b??c 1...
Theo k?ch b?n trên ?ây, h? th?ng s? lâm vào tình tr?ng lu?n qu?n c?a vi?c gi?i phóng các trang ?? c?p
phát thêm khung trang cho m?t ti?n trình, và các ti?n trình khác l?i thi?u khung trang...và các ti?n trình
không th? ti?p t?c x? lý. ?ây chính là tình tr?ng trì tr? toàn b? h? th?ng. Khi tình tr?ng trì tr? này x?y
ra, h? th?ng g?n nh? m?t kh? n?ng x? lý, t?c ?? phát sinh l?i trang t?ng cao kh?ng khi?p, không công
vi?c nào có th? k?t thúc vì t?t c? các ti?n trình ??u b?n r?n v?i vi?c phân trang !
?? ng?n c?n tình tr?ng trì tr? này x?y ra, c?n ph?i c?p cho ti?n trình ?? các khung trang c?n thi?t ??
ho?t ??ng. V?n ?? c?n gi?i quy?t là làm sao bi?t ???c ti?n trình c?n bao nhiêu trang?
Mô hình c?c b? ( Locality) : theo lý thuy?t c?c b?, thì khi m?t ti?n trình x? lý, nó có khuynh h??ng di
chuy?n t? nhóm trang c?c b? này ??n nhóm trang c?c b? khác . M?t nhóm trang c?c b? là m?t t?p các
trang ?ang ???c ti?n trình dùng ??n trong m?t kho?ng th?i gian. M?t ch??ng trình th??ng bao g?m
nhi?u nhóm trang c?c b? khác nhau và chúng có th? giao nhau.
3.5.3.1.1. Mô hình « t?p làm vi?c » (working set)
Ti?p c?n :
Giáo trình Nguyên lý h?????u hành – KS. Tr?n Ng?c Thái, ?? môn Tin h?c – ??i h?c DL H?i Phòng
Tài li?u l?u hành n?i b? - 27 -
Mô hình working set ??t c? s? trên lý thuy?t c?c b?. Mô hình này s? d?ng m?t tham s? D , ?????nh
ngh?a m?t c?a s? cho working set. Gi? s? kh?o sát D???n v? th?i gian (l?n truy xu?t trang) cu?i cùng,
t?p các trang ???c ti?n trình truy xu?t ??n trong D l?n truy c?p cu?i cùng này ???c g?i là working set
c?a ti?n trình t?i th?i ???m hi?n t?i. N?u m?t trang ?ang ???c ti?n trình truy xu?t ??n, nó s? n?m trong
working set, n?u nó không ???c s? d?ng n?a , nó s? b? lo?i ra kh?i working set c?a ti?n trình sau D???n
v? th?i gian k? t? l?n truy xu?t cu?i cùng ??n nó. Nh? v?y working set chính là m?t s? x?p x? c?a khái
ni?m nhóm trang c?c b?.
Hình 2.30 Mô hình working set
M?t thu?c tính r?t quan tr?ng c?a working set là kích th??c c?a nó. N?u tính toán kích th??c working
set, WSSi, cho m?i ti?n trình trong h? th?ng, thì có th? xem nh? :
D = S WSSi
v?i D là t?ng s? khung trang yêu c?u cho toàn h? th?ng. M?i ti?n trình s? d?ng các trang trong
working set c?a nó, ngh?a là ti?n trình i yêu c?u WSSi khung trang. N?u t?ng s? trang yêu c?u v??t quá
t?ng s? trang có th? s? d?ng trong h? th?ng (D > m), thì s? x?y ra tình tr?ng trì tr? toàn b?.
S? d?ng:
H?????u hành giám sát working set c?a m?i ti?n trình và c?p phát cho ti?n trình t?i thi?u các khung
trang ?? ch?a ?? working set c?a nó. Nh? v?y m?t ti?n trình m?i ch? có th?????c n?p vào h? th?ng khi
có ?? khung trang t? do cho working set c?a nó. N?u t?ng s? khung trang yêu c?u c?a các ti?n trình
trong h? th?ng v??t quá các khung trang có th? s? d?ng, h?????u hành ch?n m?t ti?n trình ?? t?m d?ng,
gi?i phóng b?t các khung trang cho các ti?n trình khác hoàn t?t.
Chi?n l??c working set ?ã lo?i tr?????c tình tr?ng trì tr? trong khi v?n ??m b?o m?c ????a ch??ng c?a
h? th?ng là cao nh?t có th?, cho phép s? d?ng t?i ?u CPU.
?i?m khó kh?n c?a mô hình này là theo v?t c?a các working set c?a ti?n trình trong t?ng th?i ???m.
Có th? x?p x? mô hình working set v?i m?t ng?t ??ng h? sau t?ng chu k? nh?t ??nh và m?t bit
reference:
phát sinh m?t ng?t ??ng h? sau t?ng T l?n truy xu?t b? nh?.
khi x?y ra m?t ng?t???ng h?, ki?m tra các trang có bit reference là 1, các trang này ???c xem nh?
thu?c v? working set.
M?t h? th?ng s? d?ng k? thu?t phân trang theo yêu c?u thu?n túy (m?t trang không bao gi?????c n?p
tr??c khi có yêu c?u truy xu?t) ?? l? m?t ??c ???m khá b?t l?i : m?t s? l??ng l?n l?i trang x?y ra khi
kh?i ??ng ti?n trình. Tình tr?ng này là h?u qu? c?a khuynh h??ng ??t t?i vi?c ??a nhóm trang c?c b?
vào b? nh?. Tình tr?ng này c?ng có th? x?y ra khi m?t ti?n trình b? chuy?n t?m th?i ra b? nh? ph?, khi
???c tái kích ho?t, t?t c? các trang c?a ti?n trình ?ã ???c chuy?n lên ??a ph?i ???c mang tr? l?i vào b?
nh?, và m?t lo?t l?i trang l?i x?y ra. ?? ng?n c?n tình hình l?i trang x?y ra quá nhi?u t?i th?i ???m kh?i
Giáo trình Nguyên lý h?????u hành – KS. Tr?n Ng?c Thái, ?? môn Tin h?c – ??i h?c DL H?i Phòng
Tài li?u l?u hành n?i b? - 28 -
??ng ti?n trình, có th? s? d?ng k? thu?t ti?n phân trang (prepaging) : n?p vào b? nh? m?t l?n t?t c? các
trang trong working set c?a ti?n trình.
3.5.3.2. T?n su?t x?y ra l?i trang
Ti?p c?n: T?n su?t l?i trang r?t cao khi?n tình tr?ng trì tr? h? th?ng có th? x?y ra.
Khi t?n su?t l?i trang quá cao, ti?n trình c?n thêm m?t s? khung trang.
Khi t?n su?t l?i trang quá th?p, ti?n trình có th? s? h?u nhi?u khung trang h?n m?c c?n thi?t.
Có th? thi?t l?p m?t giá tr? ch?n trên và ch?n d??i cho t?n su?t x?y ra l?i trang, và tr?c ti?p ??c l??ng
và ki?m soát t?n su?t l?i trang ?? ng?n ch?n tình trang trì tr? x?y ra :
N?u t?n su?t l?i trang v??t quá ch?n trên, c?p cho ti?n trình thêm m?t khung trang
N?u t?n su?t l?i trang th?p h?n ch?n d??i, thu h?i b?t m?t khung trang t? ti?n trình
Tóm t?t
Các k? thu?t h? tr? các mô hình t? ch?c b? nh? hi?n ??i :
Swapping : s? d?ng thêm b? nh? ph???? l?u tr? t?m các ti?n trình ?ang b? khóa, nh? v?y có th? t?ng
m?c ????a ch??ng c?a h? th?ng v?i c?u hình máy có dung l??ng b? nh? chính th?p.
B? nh???o : s? d?ng k? thu?t phân trang theo yêu c?u, k?t h?p thêm k? thu?t swapping ?? m? r?ng b?
nh? chính. Tách bi?t không gian ??a ch? và không gian v?t lý, nh???ó có th? x? lý các ch??ng trình có
kích th??c l?n h?n b? nh? v?t lý th?t s?
Khi cài ??t b? nh?? ?o, ph?i s? d?ng m?t thu?t toán thay th? trang thích h?p ?? ch?n các trang b?
chuy?n t?m th?i ra b? nh? ph?, dành ch? trong b? nh? chính cho trang m?i. Các thu?t toán thay th?
th??ng s? d?ng là FIFO, LRU và các thu?t toán x?p x? LRU, các thu?t toán th?ng kê NFU, MFU...
Khi m?c ????a ch??ng t?ng cao ??n m?t ch?ng m?c nào ?ó, h? th?ng có th? lâm vào tình tr?ng trì tr?
do t?t c? các ti?n trình ??u thi?u khung trang. Có th? áp d?ng mô hình working set ?? dành cho m?i
ti?n trình ?? các khung trang c?n thi?t t?i m?t th?i ???m, t???ó có th? ng?n ch?n tình tr?ng trì tr? x?y ra.
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. B? nh???o là gì ?
2. S? th?t ??ng sau ?o giác: gi?i h?n c?a b? nh???o ? Chi phí th?c hi?n?
3. Các v?n ?? c?a b? nh???o : thay th? trang, c?p phát khung trang ?
4. Mô hình working set : khái ni?m, cách tính trong th?c t?, s? d?ng ?