BÀI 7: BỘ NHỚ ẢO
I. Khái niệm
Do tại một thời điểm chỉ có một lệnh được thực hiện nên tại mỗi thời điểm ta có thể chỉ cần lưu trữ
trong bộ nhớ vật lý các chỉ thị và dữ liệu cần thiết cho việc thi hành của một chương trình tại thời điểm
đó. Khi cần, những chỉ thị mới sẽ được nạp vào bộ nhớ. Với giải pháp này, một chương trình có thể lớn
hơn kích thước của vùng nhớ cấp phát cho nó và hđh có thể tăng mức độ đa chương.
1. Định nghĩa
Bộ nhớ ảo là một kỹ thuật dùng bộ nhớ phụ lưu trữ chương trình, và các phần của chương trình được
chuyển vào-ra giữa bộ nhớ chính và bộ nhớ phụ để cho phép xử lý một tiến trình mà không cần nạp
toàn bộ vào bộ nhớ vật lý. Có thể cài đặt bộ nhớ ảo qua kỹ thuật phân trang theo yêu cầu (Demand
paging) hoặc phân đoạn theo yêu cầu (Demand segmentation
)
Hình : Bộ nhớ ảo dùng kỹ thuật phân trang theo yêu cầu
2. Cài đặt bộ nhớ ảo dùng kỹ thuật phân trang theo yêu cầu ( demand paging)
Sử dụng kỹ thuật phân trang kết hợp với kỹ thuật hoán chuyển (swapping). Một tiến trình được chia
thành các trang, thường trú trên bộ nhớ phụ ( thường là đĩa) và một trang chỉ được nạp vào bộ nhớ
chính khi có yêu cầu. Vùng không gian đĩa dùng để lưu trữ tạm các trang gọi là không gian swapping.
* Mỗi phần tử trong bảng trang gồm hai trường:
- một trường chứa bit "kiểm tra" có giá trị 1 (valid) là trang đang ở trong bộ nhớ chính , 0 (invalid) là
trang đang được lưu trên bộ nhớ phụ hoặc trang không thuộc tiến trình. Khởi đầu tất cả bit kiểm tra
trong bảng trang đều bắng 0.
- một trường chứa số hiệu khung trang (nếu bit kt là valid) hoặc chứa địa chỉ của trang trên bộ nhớ
phụ (nếu bit kt là invalid)
1
Hình : Bảng trang với một số trang trên bộ nhớ phụ
* Lỗi trang
Truy xuất đến một trang được đánh dấu invalid sẽ làm phát sinh một lỗi trang (page fault).
* Chuyển đổi địa chỉ tương đối thành tuyệt đối:
Bước 1: MMU tìm trong bảng trang để lấy các thông tin cần thiết cho việc chuyển đổi địa chỉ.
Bước 2: nếu trang đang được yêu cầu truy xuất là invalid, MMU sẽ phát sinh một ngắt để báo cho hệ
điều hành. Hệ điều hành sẽ xử lý lỗi trang như sau :

Gọi p là xác suất xảy ra một lỗi trang (0<= p <=1):
p = 0 : không có lỗi trang nào
p = 1 : mỗi truy xuất sẽ phát sinh một lỗi trang
Thời gian để thực hiện một lần truy xuất bộ nhớ là: Effective Access Time (EAT)
TEA = (1-p)ma + p ([swap out ] + swap in)
ma (memory access) là thời gian truy xuất bộ nhớ
ví dụ:
Giả sử thời gian một lần truy xuất bộ nhớ là 1 microsecond (msec) và giả sử 40% trang được chọn đã
thay đổi nội dung và thời gian hoán chuyển trang là 10 ms. Tính ETA.
Ta có:
swap out= swap in = 10 milisecond (ms) = 10000 microsecond
=> EAT = (1 – p) x 1 + p (10000*0.4+10000) (msec)
3
bộ nhớ logic
vị trí lưu
trang trên đĩa
- > bộ nhớ
ảo
2. Các thuật toán thay thế trang
Mục tiêu của các thuật tóan là chọn trang « nạn nhân » là trang mà sau khi thay thế sẽ gây ra ít lỗi
trang nhất. Thông thường số lỗi trang tỉ lệ nghịch với số khung trang dành cho tiến trình.
Hình: số khung trang tăng thì số lỗi trang giảm.
Có thể đánh giá một thuật toán bằng cách xử lý trên một chuỗi các trang cần truy xuất với số lượng
khung trang cho trước và tính toán số lượng lỗi trang phát sinh.
Ví dụ: Giả sử tiến trình truy xuất các địa chỉ theo thứ tự : 0100, 0432, 0101, 0611
Nếu kích thước của một trang là 100 bytes, có thể viết lại chuỗi địa chỉ thành chuỗi trang: 1, 4, 1, 6
* Thuật toán FIFO: Trang ở trong bộ nhớ lâu nhất sẽ được chọn (vào trước ra trước)
Ví dụ : sử dụng 3 khung trang , ban đầu cả 3 đều trống :
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
7 7 7 2 2 2 2 4 4 4 0 0 0 0 0 0 0 7 7 7

7 7 7 2 2 2 2 2 2 2 2 2 2 2 2 2 2 7 7 7
0 0 0 0 0 0 4 4 4 0 0 0 0 0 0 0 0 0 0
1 1 1 3 3 3 3 3 3 3 3 1 1 1 1 1 1 1
* * * * * * * * *
Thuật toán này bảo đảm số lượng lỗi trang phát sinh là thấp nhất , nó cũng không gánh chịu nghịch lý
Belady, tuy nhiên, đây là một thuật toán khó cài đặt, vì khó có thể biết trước chuỗi truy xuất của tiến
trình.
* Thuật toán « Lâu nhất chưa sử dụng » ( Least-recently-used: LRU)
Thuật toán FIFO sử dụng thời điểm nạp để chọn trang thay thế, thuật toán tối ưu dùng thời điểm
trang sẽ được sử dụng, vì thời điểm này khó có thể xác định trước nên thuật toán LRU phải dùng thời
điểm cuối cùng trang được truy xuất – dùng quá khứ gần để dự đoán tương lai.
5