Bài giảng Hệ điều hành nâng cao - Trần Hạnh Nhi - Bài giảng 7: Bộ nhớ ảo

trống, chọn một khung trang nạn nhân để swap 
out, cập nhật bảng trang tương ứng rồi đến bước 5
5. Chuyển trang muốn truy xuất từ bộ nhớ phụ vào bộ nhớ chính : nạp 
trang cần truy xuất vào khung trang trống đã chọn (hay vừa mới làm 
trống ) ; cập nhật nội dung bảng trang, bảng khung trang tương ứng.
6. Tái kích hoạt tiến trình người sử dụng.
12/2/2005 Trần Hạnh Nhi 18
Các câu hỏi
1. Chọn trang nào để nạp ? => Chiến lược nạp
ƒ Demand Paging / Prepageing
2. Chọn trang nạn nhân ? => Chiến lược thay thế trang
ƒ FIFO / OPTIMAL/LRU
3. Cấp phát khung trang => Chiến lược cấp phát khung trang
ƒ Công bằng/ Tỷ lệ...
12/2/2005 Trần Hạnh Nhi 19
Chiến lược nạp
„ Quyết định thời điểm nạp một/nhiều page vào BNC
„ Nạp trước : làm sao biết ? =>prepaging
„ Nạp sau : tần suất lỗi trang cao ? => pure demand paging
„ Prepaging : 
„ Nạp sẵn một số trang cần thiết vào BNC trước khi truy xuất chúng
„ Demand paging : 
„ Chỉ nạp trang khi được yêu cầu truy xuất đến trang đó
ld init pages ld page ld page ld page ...
init pages = ?
12/2/2005 Trần Hạnh Nhi 20
Chiến lược thay thế trang (Page Replacement)
„ Mục tiêu : 
„ thay thế trang sao cho tần suất xảy ra lỗi trang thấp nhất
„ Đánh giá
„ Sử dụng số frame cụ thể
„ Giả sử có một chuỗi truy xuất cụ thể
„ adresse : 0100, 0432, 0101, 0612, 0102, 0103, 0104, 0611
„ # page : 1, 4, 1, 6, 1, 1, 1, 6,
„ Thực hiện một thuật toán thay thế trang trên chuỗi truy xuất này
„ Đếm số lỗi trang phát sinh
„ Chuỗi truy xuất
„ 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
„ 3 frames
12/2/2005 Trần Hạnh Nhi 21
Chiến lượt thay thế trang
„ FIFO
„ Optimal
„ LRU (Least Recently Used)
12/2/2005 Trần Hạnh Nhi 22
Chiến lược thay thế trang FIFO
„ Nguyên tắc : Nạn nhân là trang “già” nhất
„ Được nạp vào lâu nhất trong hệ thống
„ Thực hiện
„ Lưu thời điểm nạp, so sánh để tìm min
„ Chi phí cao
„ Tổ chức FIFO các trang theo thứ tự nạp
„ Trang đầu danh sác là nạn nhân
„ Nhận xét
„ Đơn giản
„ Công bằng ?
„ Không xét đến tính sử dụng !
„ Trang được nạp vào lâu nhất có thể là trang
cần sử dụng thường xuyên !
addvictim
12/2/2005 Trần Hạnh Nhi 23
Ví dụ : FIFO
7 0 1 00 32 4 2 0 3 2 1 2 0 ...
7 7 7 22 27 2 4 4 0 0 0 0 0
0 0 30 00 3 3 2 2 2 2 1 1
1 11 11 0 0 3 3 3 3 3 2
* * * *** * * * * *
2
3
0
4
2
3
4
0
*
2
3
0
1
2
12/2/2005 Trần Hạnh Nhi 24
FIFO và hiệu ứng Belady
„ Sử dụng càng nhiều frame...càng có nhiều lỗi trang !
12/2/2005 Trần Hạnh Nhi 25
Chiến lược thay thế trang : Optimal
AGBDCABCABCGABC
victim
Cur page
„ Nguyên tắc : Nạn nhân là trang lâu sử
dụng đến nhất trong tương lai
„ Làm sao biết ?
„ Nhận xét
„ Bảo đảm tần suất lỗi trang thấp nhất
„ Không khả thi ! 
12/2/2005 Trần Hạnh Nhi 26
Ví dụ : Optimal
7 0 1 00 32 4 2 0 3 2 1 2 0 ...
7 7 7 22 27
0
2
4
2 2 2 2 0
0 0 00
1
0
2
4
2
0 0
3
0 1
1 31
0
1 3 3 3 3 3
0
1 2
* * * ** * * *
2
3
4
3
2
3
4 0
1
12/2/2005 Trần Hạnh Nhi 27
Chiến lược thay thế trang : LRU
AGBDCABCABCGABC
victim
Cur page
„ Nguyên tắc : Nạn nhân là trang lâu nhất
chưa sử dụng đến trong quá khứ
„ Nhìn lui : đủ thông tin
„ Nhận xét
„ Xấp xỉ Optimal 
„ Thực hiện ?
12/2/2005 Trần Hạnh Nhi 28
Ví dụ : LRU
7 0 1 00 32 4 2 0 3 2 1 2 0 ...
7 7 7 22 27 2 4
2
0 0 0 1 1
0 0 00
1
0
3
0
4
3 3
2
3 3
1 31
0
1
0
3
3
2 2
3
2 2
* * * ** * * *
2
3
4
3
4
2
0
0 1
3
* *
0
*
2
12/2/2005 Trần Hạnh Nhi 29
Thực hiện LRU 
„ Sử dụng bộ đếm:
„ Thêm trường reference time cho mỗi phần tử trong bảng trang 
„ Thêm vào cấu trúc của CPU một bộ đếm counter. 
„ mỗi lần có sự truy xuất đến một trang trong bộ nhớ
„ giá trị của counter tăng lên 1.
„ giá trị của counter được ghi nhận vào reference time của trang tương ứng.
„ thay thế trang có reference time là min .
„ Sử dụng stack:
„ tổ chức một stack lưu trữ các số hiệu trang
„ mỗi khi thực hiện một truy xuất đến một trang, số hiệu của trang sẽ được xóa 
khỏi vị trí hiện hành trong stack và đưa lên đầu stack. 
„ trang ở đỉnh stack là trang được truy xuất gần nhất, và trang ở đáy stack là
trang lâu nhất chưa được sử dụng..
12/2/2005 Trần Hạnh Nhi 30
Thực hiện LRU với stack
12/2/2005 Trần Hạnh Nhi 31
Thực hiện LRU : thực tế
„ Hệ thống được hỗ trợ phần cứng hoàn chỉnh để cài đặt LRU ?
„ Đừng có mơ !
„ Hệ thống chỉ được trang bị thêm một bit reference :
„ gắn với một phần tử trong bảng trang.
„ được khởi gán là 0
„ được phần cứng đặt giá trị 1 mỗi lần trang tương ứng được truy cập
„ được phần cứng gán trở về 0 sau từng chu kỳ qui định trước.
„ Bit reference chỉ giúp xác định những trang có truy cập, không xác định thứ tự
truy cập
„ Không cài đặt được LRU
„ Xấp xỉ LRU...
frame protectmodifyreference
12/2/2005 Trần Hạnh Nhi 32
4-53
bit reference
các bits history
thời gian
0
0
0
0
0
0
1
0
1
0
1
0
1
1
0
0
1
0
1
0
1
1
0
0
0
Xấp xỉ LRU : Sử dụng các bits History
ƒ sử dụng thêm N bit history phụ trợ
ƒ Sau từng chu kỳ, bit reference sẽ được chép lại vào một bit history 
trước khi bi reset
ƒ N bit history sẽ lưu trữ tình hình truy xuất đến trang trong N chu kỳ cuối cùng. 
Thời gian
0
0
0
0
0
0
1
0
1
0
0
1
0
1
0
Thời gian
0
0
0
0
0
0
1
0
1
0
1
0
1
1
0
0
1
0
1
0
1
0
1
1
0
Thời gian
0
0
0
0
0
0
1
0
1
0
1
0
1
1
0
0
1
0
1
0
0
1
0
1
0
1
0
1
1
0
0
1
0
1
0
Thời gian
0
0
0
0
0
0
1
0
1
0
1
0
1
1
0
0
1
0
1
0
1
1
0
0
0
0
1
0
1
0
1
0
1
1
0
0
1
0
1
0
1
1
0
0
0
12/2/2005 Trần Hạnh Nhi 37
Xấp xỉ LRU : Cơ hội thứ 2 (Clock algorithme)
„ Sử dụng một bit reference duy nhất. 
„ Chọn được trang nạn nhân theo FIFO 
„ Kiểm tra bit reference của trang đó :
„ Nếu reference = 0, đúng là nạn nhân rồi ☺
„ Nếu reference = 1, cho trang này một cơ hội thứ hai
„ reference = 0
„ thời điểm vào Ready List được cập nhật lại là thời điểm hiện tại. 
„ Chọn trang FIFO tiếp theo...
„ Nhận xét : 
„ Một trang đã được cho cơ hội thứ hai sẽ không bị thay thế trước khi hệ thống 
đã thay thế hết những trang khác. 
„ Nếu trang thường xuyên được sử dụng, bit reference của nó sẽ duy trì được 
giá trị 1, và trang hầu như không bao giờ bị thay thế.
12/2/2005 Trần Hạnh Nhi 38
4-55
page#0
page#0
page#1
page#1
page#0
page#1
page#1
Trang FIFO
Nạn nhân
0
0
0
0
Trang FIFO
Xấp xỉ LRU : Cơ hội thức 2 (Clock algorithme)
12/2/2005 Trần Hạnh Nhi 39
Xấp xỉ LRU : NRU 
„ Sử dụng 2 bit Reference và Modify 
„ Với hai bit này, có thể có 4 tổ hợp 
tạo thành 4 lớp sau :
„ (0,0) không truy xuất, không sửa đổi
„ (0,1) không truy xuất gần đây, nhưng 
đã bị sửa đổi
„ (1,0) được truy xuất gần đây, nhưng 
không bị sửa đổi
„ (1,1) được truy xuất gần đây, và bị sửa 
đổi
„ Chọn trang nạn nhân là trang có độ
ưu tiên cao nhất khi kết hợp bit R 
và bit M
Priority R M
4 0 0
3 0 1
2 1 0
1 1 1
12/2/2005 Trần Hạnh Nhi 40
Chiến lược cấp phát frame
„ Số frame cần cấp phát cho mỗi tiến trình ?
„ Giải sử có m frame và n process
„ Cấp phát công bằng: #frame(Pi) = m/n
„ Công bằng ???
„ Cấp phát theo tỷ lệ: #frame(pi) = (si / (Σ si ))* m
„ si = kích thước của bộ nhớ ảo cho tiến trình pi
„ Lỗi trang xảy ra tiếp theo, cấp phát thêm frame cho tiến trình như thế nào ?
„ Ỉ Tùy thuộc chiến lược thay thế trang
„ Cục bộ : chỉ chọn trang nạn nhân trong tập các trang của tiến trình phát 
sinh lỗi trang -> số frame không tăng
„ Toàn cục: được chọn bất kỳ trang nạn nhân nào (dù của tiến trình khác) -
> số frame có thể tăng, lỗi trang lan truyền
12/2/2005 Trần Hạnh Nhi 41
Thay thế trang toàn cục và...kết cục bi thảm !
„ Tất cả các tiến trình bận rộn thay thế trang !
Running CPU IO
P1
P2
P1
P3
P1, error
1
P1, swap out
P2, error P2, swap out
P3, error
12/2/2005 Trần Hạnh Nhi 42
Thrashing
ƒ Tất cả tiến trình đầu bận rộn xử lý lỗi trang !
ƒ IO hoạt động 100 %, CPU rảnh ! 
ƒ Hệ thống ngừng trệ
Real mem
P1 P2 P3
ƒ Virtual Memory = Tha hồ xài bộ nhớ
Thrashing = ảo tưởng sụp đổ !
ƒ Các tiến trình trong hệ thống yêu cầu bộ nhớ nhiều hơn khả
năng cung cấp của hệ thống !
12/2/2005 Trần Hạnh Nhi 43
Working set (1968, Denning)
„ Working set:
„ Working set = tập hợp các trang tiến trình đang truy xuất tại 1 
thời điểm
„ Các pages được truy xuất trong Δ lần cuối cùng sẽ nằm trong working set 
của tiến trình
„ Δ : working set parameter
„ Kích thước của WS thay đổi theo thời gian tùy vaò locality của tiến trình
12/2/2005 Trần Hạnh Nhi 44
Working-Set Model
„ Δ ≡ working-set window ≡ số lần truy cập
VD: 10,000 instruction
„ 2 6 1 5 7 7 7 7 5 1 6 2 3 4 1 2 3 4 4 4 3 4 3 4 4 4 1 3 2 3 
„ Δ=10
„ WS(t1) = {1,2,5,6,7}, WS(t2) = {3,4}
„ WSSi (working set of Process Pi) =
tổng số trang được truy cập trong Δ lần gần đây nhất
„ D = ΣWSSi ≡ Tổng các frame cần cho N tiến trình trong
hệ thống
„ if D > m⇒ Thrashing
„ if D > m, chọn mộ/một số tiến trình để đình chỉ tạm thời.
12/2/2005 Trần Hạnh Nhi 45
Giải quyết thrasing với mô hình Working set
ƒ Sử dụng Working set
ƒ Cache partitioning: Cấp cho mỗi tiến trình số frame đủ
chứa WS của nó
ƒ Page replacement: ưu tiên swap out các non-WS pages. 
ƒ Scheduling: chỉ thi hành tiến trình khi đủ chỗ để nạp WS 
của nó