QUẢN LÝ BỘ NHỚ
III. CẤP PHÁT KHÔNG LIÊN TỤC
Chương trình được viết trên không gian địa chỉ ảo. Hệ điều hành và phần cứng thực hiện việc chuyển đổi địa chỉ ảo sang địa chỉ thực.
Có 3 dạng bộ nhớ ảo:
Bộ nhớ ảo theo phân trang (paging).
Bộ nhớ ảo theo phân đoạn (segmentation).
Bộ nhớ ảo theo phân đoạn có phân trang (paged segmentation).
1) Bộ nhớ ảo theo phân trang:
a) Tổ chức phân trang:
Không gian địa chỉ ảo được chia thành các khối. Mỗi khối như vậy được gọi là một trang (page).Trong thực tế một trang có kích thước cỡ vài kí lô Byte.
Không gian địa chỉ vật lý được chia thành các khung trang (page frame).
Mỗi khung trang có kích thứơc bằng một trang. Số trang lớn hơn số khung trang rất nhiều. Một ô nhớ trong bộ nhớ ảo có địa chỉ theo dạng:
P OFFSET
P (page number): số hiệu của trang chứa ô nhớ.
OFFSET (offset): khoảng cách từ đầu trang p đến vị trí của ô nhớ trong trang.
Người ta xây dựng một bảng trang (page map table) để chuyển đổi từ địa chỉ ảo sang địa chỉ thực.
Bảng trang có số lượng phần tử bằng với số lượng trang. Mỗi phần tử có dạng:
PR DA PF
PR (present bit): PR=0 nếu trang chưa có trong bộ nhớ thực, PR=1 nếu trang đã có trong bộ nhớ thực.
DA (Disk Address): cho biết địa chỉ của trang ở bộ nhớ ngoài nếu như trang không ở trong bộ nhớ thực.
PF (page frame number): số hiệu của khung trang trong bộ nhớ thực (khi PR=1).
Nếu bảng trang có kích thước nhỏ thì dùng một tập hợp các thanh ghi để cài đặt bảng trang (nên được gọi là phần cứng hỗ trợ bộ nhớ ảo). Nếu bảng trang có kích thước lớn thì bảng trang được lưu trữ trong bộ nhớ chính và sử dụng một thanh ghi để lưu địa chỉ bắt đầu của bảng trang (page table pointer).
b) Cơ chế ánh xạ địa chỉ trực tiếp (direct mapping):
c) Phaân trang theo yeâu caàu:
Khi có yêu cầu truy xuất bộ nhớ, hệ thống phát địa chỉ ảo của ô nhớ cần truy xuất. Từ địa chỉ ảo ta có số hiệu của trang. Nhờ có số hiệu của trang, hệ thống đi đến phần tử tương ứng trên bảng trang. Xét PR của phần tử này.
Nếu PR=1: thì trang đang có trên bộ nhớ thực. Lấy số hiệu của khung trang từ PF rồi đi đến khung trang tương ứng ở bộ nhớ thực. Sau đó truy xuất ô nhớ trong khung trang này theo giá trị trong phần OFFSET.
Nếu PR=0: thì trang chưa có trên bộ nhớ thực. Hệ thống sẽ nạp trang từ bộ nhớ ngoài vào bộ nhớ trong. Sau đó cập nhật phần tử tương ứng trên bảng trang.
d) Thay thế các trang:
Do số khung trang nhỏ hơn số trang rất nhiều nên các khung trang sẽ bị đầy sau một thời gian làm việc. Nếu cần nạp thêm một trang thì phải đưa một trang khác (đang ở trên khung trang) ra trở lại bộ nhớ ngoài rồi mới đưa trang mới vào. Việc làm này gọi là thay thế trang. Vấn đề chính của việc thay thế trang là chọn trang nào cần đưa ra ngoài.
Một số thuật toán thay thế trang: tối ưu, FIFO,LRU, second chance, NRU, ngaãu nhieân.
-FIFO (first in first out): Trang nào ở lâu nhất trong bộ nhớ sẽ được thay ra.
- Ngẫu nhiên: chọn ngẫu nhiên một trang để thay ra.
- Tối ưu: trang sẽ lâu được sử dụng nhất trong tương lai sẽ là trang bị thay ra.
- LRU (least recently used): trang lâu nhất chưa được truy xuất sẽ bị thay ra.
- NRU (not recent used): cải tiến của LRU.
- Second chance: cải tiến của FIFO.
Ví dụ: Giải thuật thay trang FIFO. Giả sử chỉ có 3 khung trang, ban đầu cả 3 khung trang đều trống. Sơ đồ thể hiện sự tồn tại của các trang trên bộ nhớ thực (gồm các khung trang) như sau:
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 0 0 0 0 3 3 3 2 2 2 2 2 1 1 1 1 1 0 0 1 1 1 1 0 0 0 3 3 3 3 3 2 2 2 2 2 1
* * * * * * * * * * * * * * *
Nếu áp dụng giải thuật thay trang LRU, kết quả như sau:
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 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 3 3 3 3 3 3 0 0 0 0 0 1 1 1 3 3 3 2 2 2 2 2 2 2 2 2 7 7 7
* * * * * * * * * * * *
2) Bộ nhớ ảo theo phân đoạn:
a) Tổ chức phân đoạn:
Không gian địa chỉ ảo được tổ chức theo các đoạn có kích thứơc thay đổi được. Mỗi địa chỉ ảo gồm hai thành phần segment number (số hiệu đoạn) và OFFSET (khoảng cách từ đầu đoạn đến vị trí của ô nhớ trong đoạn).
Để quản lý các đoạn người ta dùng bảng đoạn. Mỗi phần tử trong bảng đoạn có dạng:
PR AR LGTH ADDR
PR (present bit):PR=0 nếu đoạn chưa có trong bộ nhớ thực, PR=1 nếu đọan đã có trong bộ nhớ thực.
ADDR (address): là địa chỉ đầu đoạn.
LGTH (length): kích thước của đoạn.
AR (access right): quyền truy xuất, dùng để bảo vệ đoạn. Có các quyền:
R(read),W(write), E(execute), A(append).
b) Cơ chế ánh xạ địa chỉ trực tiếp (direct mapping):
c) Phân đoạn theo yêu cầu:
Cũng tương tự như phân trang, cũng có phân đoạn theo yêu cầu và cũng có sự thay thế đoạn khi bộ nhớ bị đầy. Nhưng do kích thước của của đoạn có thay đổi nên các thao tác trên sẽ phức tạp hơn phân trang nhiều.
3) Phân đoạn có phân trang:
CHệễNG IV