Khoa Công Nghệ Thông Tin & Truyền Thông
Đại học Cần Thơ
Giảng viên: Hà Duy An


1.
2.
3.
4.
5.
6.

Tổng quan
Phân trang theo yêu cầu
Thay thế trang
Cấp phát khung trang
Thrashing
Một số tác vụ với kỹ thuật bộ nhớ ảo

10/28/2013

2

Chương 8: Virtual Memory



• Các mã lệnh phải trong bộ nhớ để thực thi, nhưng tồn bộ
chương trình hiếm khi được dùng
o Các lệnh xử lý lỗi, các cấu trúc dữ liệu lớn, các tùy chọn và tính
năng ít dùng.

• Tồn bộ chương trình khơng phải được sử dụng cùng một lúc
• Khả năng nạp chương trình từng phần vào bộ nhớ để thực thi:
o Giải phóng sự ràng buộc với giới hạn của bộ nhớ thực
o Nhiều chương trình có thể thực thi đồng thời
o Thao tác I/O để nạp và hoán vị tiến trình cần ít hơn

10/28/2013

4

Chương 8: Virtual Memory


• Bộ nhớ ảo (Virtual memory): tách biệt bộ nhớ luận lý của người
dùng ra khỏi bộ nhớ vật lý:
o Chỉ một phần của chương trình cần ở trong bộ nhớ để thực thi 
không gian địa chỉ luận lý có thể lớn hơn nhiều so với khơng gian địa
chỉ vật lý.
o Cho phép khơng gian địa chỉ có thể trải rộng ra với các khoảng trống
dành cho việc sử dụng trong tương lai
o Các thư viện chia sẽ hay bộ nhớ chia sẽ có thể được cài đặt bằng cách
ánh xạ đối tượng cần chia sẽ vào trong không gian luận lý của các tiến
trình
o Các trang có thể được chia sẽ trong suốt thời gian tạo tiến trình với lời
gọi hệ thống fork() => tăng tốc độ tạo tiến trình
o Nhiều chương trình có thể được đưa vào bộ nhớ để thực thi đồng thời
o Cần ít thao tác I/O hơn khi nạp hay khi hoán vị
10/28/2013


5

Chương 8: Virtual Memory


10/28/2013

6

Chương 8: Virtual Memory


10/28/2013

7

Chương 8: Virtual Memory


10/28/2013

8

Chương 8: Virtual Memory


• Bộ nhớ ảo có thể được cài đặt:
o Phân trang theo yêu cầu
o Phân đoạn theo yêu cầu


10/28/2013

9

Chương 8: Virtual Memory


10
10/28/2013

Chương 8: Virtual Memory


• Mang tồn bộ tiến trình vào trong bộ nhớ (phân trang thơng
thường)
• Hay chỉ mang một trang vào bộ nhớ khi cần thiết (phân trang theo
yêu cầu – Demand Paging)
o
o
o
o

Cần ít thao tác I/O hơn
Cần ít bộ nhớ vật lý hơn
Rút ngắn thời gian đáp ứng
Phục vụ nhiều người dùng hơn

• Khi cần một trang ⇒ tham khảo tới nó
o Tham khảo khơng hợp lệ ⇒ thốt
o Trang khơng có trong bộ nhớ ⇒ đem nó vào bộ nhớ


• Lazy swapper (bộ hốn vị lười) – khơng bao giờ hốn vị một trang
vào bộ nhớ trừ khi trang đó cần dùng
o Swapper xử lý với các trang gọi là pager
10/28/2013

11

Chương 8: Virtual Memory


10/28/2013

12

Chương 8: Virtual Memory


• Kết hợp với mỗi mục từ trong bảng trang một bit valid/invalid (v (1)
⇒in-memory, i (0) ⇒ not-in-memory)
• Khởi đầu bit valid/invalid của mọi mục từ được đặt là i.
• Ví dụ về thực trạng một bảng trang:
Frame #
valid‐invalid bit

• Trong tiến trình dịch địa chỉ, nếu
bit valid/invalid trong một mục
từ của bảng trang = 0 ⇒
có lỗi trang (Page Fault).


v
v
v
v
i
….
i
i
page table

10/28/2013

13

Chương 8: Virtual Memory


10/28/2013

14

Chương 8: Virtual Memory


• Nếu có một tham khảo đến một trang, tham khảo đầu tiên đến
trang đó ln được giao cho hệ điều hành xử lý: lỗi trang
• Các bước xử lý lỗi trang của HĐH:
o Hệ điều hành sẽ nhìn vào internal table (chứa trong PCB)
để xác định:
• Tham khảo khơng hợp lệ ⇒ kết thúc tiến trình.

• Hay là trang khơng có trong bộ nhớ => mang nó vào
1.
2.
3.
4.
10/28/2013

Tìm một khung trang cịn trống
Hốn vị trang vào khung trang.
Thiết lập lại bảng trang bằng cách đặt bit kiểm tra = v.
Khởi động lại chỉ thị đã bị ngắt bởi lỗi trang
15

Chương 8: Virtual Memory


10/28/2013

16

Chương 8: Virtual Memory


• Khi tiến trình bắt đầu được thực thi – khơng có trang nào trong
bộ nhớ, lỗi trang (page fault):
o Tham khảo đến lệnh đầu tiên của tiến trình
o Mỗi trang của tiến trình được truy cập lần đầu

 Pure demand paging
• Một lệnh có thể truy cập nhiều trang cùng lúc => nhiều lỗi

trang
o Chương trình khuynh hướng tham chiếu cục bộ

• Phần cứng hỗ trợ phân trang theo yêu cầu:
o Bảng trang: valid/invalid bit
o Bộ nhớ phụ (thiết bị hốn vị với khơng gian hốn vị)
o Khởi động lại một lệnh

10/28/2013

17

Chương 8: Virtual Memory


• Một lệnh có thể truy cập vài vị trí khác nhau:
o Lệnh move

o Lỗi trang khi đã di chuyển dữ liệu một phần?
o Nguồn và đích phủ lấp lên nhau?

• Phương pháp giải quyết:
o Truy cập thăm dị
o Lưu giữ giá trị bị ghi đè

10/28/2013

18

Chương 8: Virtual Memory



•

Các bước thực hiện phân trang theo yêu cầu:
1.
2.
3.
4.
5.

Thông báo cho HĐH
Lưu lại các thanh ghi và trạng thái của tiến trình người dùng
Xác định ngắt là một lỗi trang
Kiểm tra tính hợp lệ của trang tham khảo, xác định vị trí của trang trên đĩa
Đọc trang từ đĩa vào khung trống:
a. Chờ trong hàng đợi thiết bị cho đến khi yêu cầu đọc được phục vụ
b. Chờ thiết bị tìm kiếm (độ trễ thời gian - latency time)
c. Bắt đầu chuyển trang vào khung trống

6.
7.
8.
9.
10.

Trong khi chờ đợi, cấp CPU cho người dùng khác
Nhận một ngắt từ hệ thống I/O đĩa (I/O completed)
Lưu các thanh ghi và trạng thái của tiến trình đang thực thi (của người dùng khác)
Xác định ngắt phát ra từ đĩa

Điều chỉnh bảng trang và các bảng khác có liên quan để cho thấy rằng trang bây
giờ đang nằm trong bộ nhớ
11. Chờ để được cấp phát CPU lần nữa
12. Khôi phục lại các thanh ghi, trạng thái của tiến trình, và bảng trang mới, sau đó
khởi động lại lệnh đã bị ngắt

10/28/2013

19

Chương 8: Virtual Memory


• Tỉ lệ lỗi trang 0 ≤ p ≤ 1.0
o if p = 0 khơng có lỗi về trang
o if p = 1, mọi tham khảo trang đều bị lỗi

• Thời gian truy xuất thực (Effective Access Time - EAT)
EAT = (1 – p) x [memory access]
+ p x [page fault time]
• [ page fault time] = [page fault overhead] +
[swap page out ] +
[swap page in] +
[restart overhead] +

10/28/2013

20

Chương 8: Virtual Memory



•
•

Memory access time = 200 nanoseconds
Average page-fault service time = 8 milliseconds

•

EAT = (1 – p) x 200 + p (8 milliseconds)
= (1 – p x 200 + p x 8,000,000
= 200 + p x 7,999,800
Nếu trong 1,000 lần truy xuất có một lỗi trang thì
EAT = 8.2 microseconds.
=> Chậm hơn 40 lần khi không dùng phân trang theo yêu cầu
Nếu muốn truy xuất chỉ chậm hơn < 10%
220 > 200 + 7,999,800 x p
20 > 7,999,800 x p
p < .0000025
< một lỗi trang trong 400,000 lần truy xuất bộ nhớ
=> Cần giữ cho tỉ lệ lỗi trang thấp nhất có thể trong hệ thống phân trang theo
yêu cầu, nếu khơng sự thực thi của tiến trình có thể rất chậm

•

•

10/28/2013


21

Chương 8: Virtual Memory


• Sao chép tồn bộ ảnh của tiến trình vào khơng gian hốn
chuyển (swap space) vào thời gian nạp tiến trình
o Hốn vị trang vào/ra swap space
o Được dùng trong các phiên bản cũ của BSD Unix

• Lấy trang từ chương trình nhị phân trên đĩa, nhưng chỉ xóa
trang (khơng hoán vị trang ra đĩa) khi cần khung trống
o Được dùng trong Soloris và BSD Unix hiện hành

10/28/2013

22

Chương 8: Virtual Memory


23
10/28/2013

Chương 8: Virtual Memory


10/28/2013

24


Chương 8: Virtual Memory


• Điều gì xảy ra khi khơng cịn khung trống?
• Ngăn chặn việc cấp phát bộ nhớ vượt quá mức bằng cách dùng giải
pháp thay thế trang.
o Chọn một trang đã được nạp và khơng đang được dùng, giải phóng nó
bằng cách viết nội dung của nó vào khơng gian hốn chuyển (swap
space).
o Dùng khung đã được giải phóng này để nạp trang được yêu cầu.

• Sử dụng bit modify (dirty) để làm giảm chi phí cho việc chuyển
trang ra đĩa.
• Giải pháp thay thế trang hồn thiện thêm cơng việc tách biệt hóa bộ
nhớ ảo và bộ nhớ vật lý:
o Bộ nhớ ảo có thể lớn hơn bộ nhớ thực
o Thực hiện chương trình trong một vài khung, và tìm một khung trống
mỗi khi cần thiết.

10/28/2013

25

Chương 8: Virtual Memory