1
1
Nguyên lý hệđiềuhành
NguyễnHải Châu
Khoa Công nghệthông tin
Trường Đạihọc Công nghệ
2
Bộnhớảo
(Virtual Memory)
Yêu cầu phân trang
Tạo tiến trình
Thay thếtrang
Cấp phát frame
Thrashing
3
Virtual memory (Bộnhớảo)
zBộnhớảo– tách biệt bộnhớlogic và vật lý.
zCho phép tiến trình có cỡlớn hơn bộnhớtrong có
thểthực hiện được
zKhông gian địa chỉảo có thểlớn hơn nhiều so với
không gian địa chỉvật lý (về dung lượng)
zCho phép các tiến trình sửdụng chung không gian
địa chỉ
zCho phép tạo tiến trình hiệu quả hơn
zBộnhớảo có thể được cài đặt thông qua:
zYêu cầu phân trang (demand paging)
zYêu cầu phân đoạn (demand segmentation)
4
Minh họa bộnhớảo có dung
lượng lớn hơn bộnhớvật lý
5
Yêu cầu trang (demand paging)
zChỉ đưa một trang vào bộnhớkhi cần thiết
zGiảm thao tác các vào ra
zTiết kiệm bộnhớ
zĐáp ứng nhanh
zTăng được số người sửdụng (tiến trình)
zKhi cần một trang ⇒tham chiếu đến nó
zTham chiếu lỗi⇒Hủy bỏ
zKhông nằm trong bộnhớ⇒Đưa trang vào bộ
nhớ
6
Chuyển một trang (trong bộ
nhớ) ra vùng đĩa liên tục
2
7
Valid-Invalid Bit
zMỗi phần tửbảng trang có một bit hợp
lệ/không hợp lệ(1: trong bộnhớ, 0: không
trong bộnhớ)
zKhởi đầu: valid–invalid bằng 0.
zVí dụbảng trang+bit invalid/valid:
zKhi tính địa chỉ,nếu valid–invalid
ởbảng trang là 0: ⇒lỗi trang
(page-fault trap)
1
1
1
1
0
0
0
#
Frame #
valid-invalid
bit
bảng trang 8
Bảng trang với một sốtrang
không nằm trong bộnhớ
9
Xửlý page-fault (lỗi trang)
zHĐH sẽkiểm tra nguyên nhân lỗi:
zLỗi từtiến trình: kết thúc tiến trình, hoặc
zTrang không nằm trong bộnhớ: Thực hiện tiếp:
zTìm một frame rỗi và đưa trang vào bộnhớ
zSửa lại bảng trang (bit = valid)
zThực hiện lại lệnh tham chiếu trang
zVấn đề hiệu năng: Nếu tại một thời điểm có
yêu cầu nhiều trang (ví dụ: Một trang cho
lệnh và vài trang cho dữliệu)?
10
Các bước xửlý page-fault
11
Nếu không có frame rỗi?
zThực hiện thay thếtrang – swap out một số
trang đang ởtrong bộnhớ nhưng hiện tại
không được sửdụng
zThuật toán nào tốt?
zHiệu năng: Cần một thuật toán có ít page-fault nhất
để hạn chếvào/ra
zNhiều trang có thể được đưa vào bộnhớtại
cùng một thời điểm.
zThuật toán thay thếtrang: FIFO, Optimal,
LRU, LRU-approximation 12
Hiệu năng của yêu cầu trang
zTỷlệpage-fault là p:0 ≤p≤1.0
znếup= 0: Không có page-fault
znếup= 1, mọi yêu cầu truy cập đến trang đều
gây ra page-fault
zEffective Access Time (EAT)
EAT = (1 – p) x memory access
+ p(page fault overhead
+ [swap page out ]
+ swap page in
+ restart overhead
)
3
13
Tạo tiến trình
zBộnhớảo có ưu điểm khi khởi tạo một tiến
trình mới:
- Copy-on-Write (Chỉtạo copy của trang khi
có thay đổi)
- Memory-Mapped Files (Các file ánh xạbộ
nhớ)
14
Copy-on-Write
zCopy-on-Write (COW) cho phép tiến trình
cha và con dùng chung trang trong bộnhớ
khi mới khởi tạo tiến trình con
zChỉkhi nào một trong hai tiến trình sửa đổi
trang dùng chung, thì trang đómới được
copy một bản mới
zCOW làm cho việc tạo tiến trình hiệu quả
hơn: Chỉcác trang bịsửa đổi mới được copy
zCác trang rỗi được cấp phát từmột tập hợp
(pool) các trang được xóa trắng với số0
15
Các file ánh xạbộnhớ
zCác file được xem như một phần bộnhớtrong bằng
các ánh xạmột khối đĩa vào một trang trong bộnhớ
zKhởi đầu các file được đọc khi có yêu cầu trang: Một
phần của file (cỡ=cỡ trang) được đọc vào bộnhớ
zCác thao tác đọc/ghi trên file sau đó được xem như
đọc/ghi trong bộnhớ
zĐơn giản hóa việc truy cập file thông qua bộnhớ hơn
là sửdụng các hàm hệthống read() và write().
zCho phép các tiến trình có thểánh xạchung một file,
do đó cho phép các trang dùng chung trong bộnhớ
16
Ví dụfile ánh xạbộnhớ
17
Thay thếtrang
zThay thếtrang dùng để tránh thực hiện nhiều
lần cấp phát mỗi khi có page-fault
zSửdụng modify bit để giảm chi phí
(overhead) vào/ra với các trang: Chỉcác
trang có thay đổi mới được ghi ra đĩa
zThay thếtrang là một trong các yếu tốxóa đi
sựkhác biệt của bộnhớảo và thật: Tiến trình
lớn hơn dung lượng bộnhớtrong có thểthực
hiện được
18
Ví dụ: Yêu cầu thay thếtrang
4
19
Cơ sởthay thếtrang
1. Tìm vịtrí của trang p cần thay trên đĩa
2. Tìm một frame rỗi f:
1. Nếu có frame rỗi: Sửdụng frame đó
2. Nếu không có frame rỗi: Sửdụng thuật toán thay
thế trang để đưa một trang trong bộnhớ ra để sử
dụng frame ứng với trang đó
3. Đọc trang pvào frame f vừa tìm được và cập
nhật bảng trang, bảng frame
4. Lặp lại quá trình này
20
Thay thếtrang
21
Thuật toán thay thếtrang
zCần tỷlệpage-fault thấp nhất
zĐánh giá thuật toán: Thực hiện trên một danh
sách các yêu cầu truy cập bộnhớvà tính số
lượng các page-fault
zTrong tất cảcác ví dụ, ta sửdụng danh sách
yêu cầu truy cập bộnhớ:
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5.
22
Đồ thịpage-fault
23
Thuật toán FIFO
zYêu cầu truy cập: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
zBộnhớVL có 3 frame: 9 page-faults
zBộnhớVL có 4 frame: 10 page-faults
zThay thếFIFO –
Belady’s anomaly
zCó nhiều frame ⇒ít page-fault
1
2
3
1
2
3
4
1
2
5
3
4
9 page faults
1
2
3
1
2
3
5
1
2
4
5
10 page faults
4
43 24
Thay thếtrang FIFO
5
25
FIFO Illustrating Belady’s
Anamoly
26
Thuật toán tối ưu
zThay thếcác trang sẽ không được sửdụng
trong khoảng thời gian dài nhất
zDanh sách yêu cầu truy cập: 1, 2, 3, 4, 1, 2,
5, 1, 2, 3, 4, 5; có 4 frame
1
2
3
4
6 page-fault
45
27
Thay thếtrang tối ưu
28
Thuật toán LRU (Least
Recently Used )
zThay thếtrang không được sửdụng lâu nhất
zDanh sách yêu cầu truy cập: 1, 2, 3, 4, 1, 2, 5,
1, 2, 3, 4, 5
zCài đặt sửdụng biến đếm
zMỗi trang có một biến đếm; mỗi khi trang được truy
cập, gán giá trị đồng hồthời gian cho biến đếm.
zKhi một cần phải thay thế trang, căn cứvào giá trị
các biến đếm của trang: Cần tìm kiếm trong danh
sách các trang
1
2
3
5
4
43
5
29
Thay thếtrang LRU
30
Thuật toán LRU (tiếp)
zCài đặt sửdụng ngăn xếp: Sửdụng một
ngăn xếp (stack) lưu các sốhiệu trang ở
dạng danh sách móc nối kép:
zKhi trang được tham chiếu đến:
zChuyển trang lên đỉnh ngăn xếp
zCần phải thay đổi 6 con trỏ
zKhi thay thếtrang không cần tìm kiếm