Bài giảng Hệ điều hành - Chương 6: Quản lý bộ nhớ

đị hỉ ơ ở (hrang. o mục rong ang p an rang c a a c c s ay 
chỉ số frame) của trang tương ứng trong bộ nhớ thực.
– Page offset (d) – được kết hợp với địa chỉ cơ sở (base address) 
để định vị một địa chỉ thực.
 Nếu kích thước của không gian địa chỉ ảo là 2m, kích 
thước của trang là 2n 
d
page number page offset
p
m-n bits
(định vị từ 0  2m-n -1)
n bits 
(định vị từ 0  2n-1)
-9.28-
Do đó, bảng phân trang sẽ có tổng cộng 2m/2n = 2m-n mục
Paging hardware
logical
physical
address 
f000 0000
f
CPU p d f d
address …
p
f111…1111
f
physical
Nếu kích thước của không 
gian nhớ thực là 2l bytes, 
thì mỗi mục của bảng phân 
t ù l bit
frame number frame offset
page table
memory
-9.29-
rang co -n s f (l-n bits) d (n bits)
Chuyển đổi bộ nhớ với paging
-9.30-
Hiện thực bảng phân trang
 Bảng phân trang được lưu giữ trong bộ nhớ chính (kernel 
memory)
M ãi ù ät b û h â t– o process co mo ang p an rang
– Thanh ghi page-table base (PTBR) trỏ đến bảng phân trang
– Thanh ghi page-table length (PTLR) biểu thi kích thước của bảng 
åphân trang (và dùng đe bảo vệ bộ nhớ)
 Mỗi tác vu truy cập dữ liệu/lệnh cần hai thao tác truy xuất ï 
vùng nhớ
– Một thao tác truy xuất bảng phân trang (page number: p) và một 
thao tác truy xuất dữ liệu/lệnh (page offset: d displacement) –
– Thường dùng một bộ phận cache phần cứng có tốc độ truy xuất 
và tìm kiếm cao, gọi là thanh ghi kết hợp (associative register) 
hoặc translation look aside buffers (TLBs)
-9.31-
 - 
Associative register (hardware)
 Thanh ghi kết hợp (associative register): hỗ trợ tìm kiếm truy xuất dữ 
liệu đồng thời với tốc độ cực nhanh.
page # frame # Số mục của TLB khoảng 8  2048
TLB là “cache” của
Khi có chuyển ngữ 
cảnh TLB bị xóa
bảng phân trang
, 
Khi TLB bị đầy, thay 
thế bằng LRU
Ánh xạ địa chỉ ảo (A’, A’’)
–Nếu A’ nằm trong TLB (hit)  lấy ngay được chỉ số frame  tiết kiệm được 
~ 10% thời gian tìm kiếm.
-9.32-
–Ngược lại (miss), phải tìm chỉ số frame từ bảng phân trang như bình thường.
Paging hardware với TLB
-9.33-
Bảo vệ bộ nhớ
 Việc bảo vệ bộ nhớ được hiện thực bằng cách gắn với frame các bit 
bảo vệ (protection bits). Các bit này biểu thị các thuộc tính sau
d l d it t l– rea -on y, rea -wr e, execu e-on y
 Ngoài ra, còn có một valid-invalid bit gắn với mỗi muc trong bảng ï 
phân trang
– “valid”: cho biết là trang bộ nhớ tương ứng nằm trong không gian nhớ địa 
chỉ ảo của process do đó là một trang hơp lệ , ï .
– “invalid”: cho biết là trang bộ nhớ tương ứng không nằm trong không gian 
nhớ địa chỉ ảo của process, do đó là một trang bất hợp lệ.
-9.34-
Bảo vệ bằng valid-invalid bit
page 0
00000
page 1 2 v
frame number valid-invalid bit
0
0
1
2 page 0
page 2
page 3
3 v
4 v
7
1
2
3
3 page 1
4 page 2
5
10468
page 4
page 5
12287
v
8 v
9 v
4
5
6
7 page 3
page 6 0 i
0 i
6
7page 7
8 page 4
9 page 5
...
 Mỗi trang nhớ có kích thước 2KB = 2048 bytes
 Process có kích thước 10,468bytes  phân mảnh nội ở page 5 
 các địa chỉ > 12287 là các địa chỉ invalid
page n
-9.35-
 .
 Dùng PTLR để kiểm tra kích thước bảng phân trang
Hierarchical page table
 Các hệ thống hiện đại đều hỗ trợ không gian địa chỉ ảo rất lớn (232
đến 264). 
Kích thước trang nhớ là 4KB ( 212) bảng phân trang sẽ có 232/212– = ~ = 
220 = 1M entries. 
– Giả sử mỗi phần tử là một con trỏ 32 bit thì mỗi process cần 4MB cho 
bảng phân trang  
 Một giải pháp được đặt ra là chia thành nhiều bảng phân trang quản 
lý các vùng không gian bộ nhớ ảo khác nhau – bảng đa mức 
(multilevel paging table).
 Cơ chế tạo bảng phân trang 2-mức (two-level page table), hay còn 
được gọi là forward-mapped page table trong hệ thống Intel 
P ti ® II
-9.36-
en um -
Mô hình bảng 2-mức (two-level)
-9.37-
Phân trang 2-mức
 Một địa chỉ luận lý (trên hệ thống 32-bit với trang nhớ 4KB) được 
chia thành các phần sau:
– Page number: 20 bit
 Nếu mỗi mục 4 byte 
 220 * 4 byte = 4 MB
– Page offset: 12 bit
20 bit
page # offset
12 bit
 Bảng phân trang cũng bị chia nhỏ nên page number cũng được chia 
nhỏ thành 2 phần: 
– 10-bit page number 
– 10-bit page offset p2
page number page offset
dp1
10 bit10 bit 12 bit
 Vì vậy, một địa luận lý sẽ biểu diễn như hình vẽ
– p1 : chỉ mục của bảng ngoài (outer page table)-mức 1
p : độ dời (displacement) ở trong trang mức 2 (xác định bởi *p )
-9.38-
– 2 1
Sơ đồ ánh xạ địa chỉ
 Sơ đồ ánh xạ địa chỉ (address-translation scheme) cho kiến trúc 
bảng phân trang 2 mức, 32-bit địa chỉ
A
Memory Address: A
-9.39-
Phân trang đa mức (multilevel)
 Không gian địa chỉ luận lý 64-bit với trang nhớ 4KB 
– Trong sơ đồ phân trang 2-mức, số mục của bảng phân trang = 
252 (264/212 = 252)  quá lớn. Thực hiện tương tự mô hình 2 mức, 
h â hi th ø h b û 3 4 ứp an c a an ang , ,..., n-m c 
page number page offset
52 12
page number page offset
42 10 12 
b ff t b ff tpage num er page o se
32 10 10 2
page num er page o se
22 10 10 10 2
– Hệ thống SPARC 32-bit hỗ trợ cơ chế 3-mức còn các hệ thống 
Motorolla 68030 32 bit hỗ trợ cơ chế 4-mức. Hệ thống 64bit 
Ult SPARC thì d ø b û h â t 7 ứ
……
-9.40-
ra ung ang p an rang -m c
– Hiệu suất của hệ thống phân trang đa mức?
Bảng băm (hashed page table)
 Dùng bảng băm để giảm bớt không gian bảng phân trang, tăng tốc 
độ tìm kiếm trang.
– Rất phổ biến trong các hệ thống lớn hơn 32 bit địa chỉ.
 Để giải quyết đụng độ, mỗi entry của bảng phân trang được gán một 
danh sách liên kết. Mỗi phần tử danh sách chứa chỉ số trang ảo 
(virtual page number) và chỉ số frame tương ứng.
– Chỉ số trang ảo được biến đổi qua hàm băm thành một hashed value. 
Các thông tin như chỉ số trang ảo và chỉ số frame sẽ được lưu vào danh 
sách liên kết tại vị trí ứng với hashed value.
 Giải thuật dò tìm trang: 
– Chỉ số trang ảo được biến đổi thành hashed value (với cùng hàm băm 
như trên). Hashed value được dùng để truy xuất đến entry tương ứng 
trong bảng phân trang. Sau đó, dò tìm trong danh sách liên kết phần tử 
chứa chỉ số trang ảo để trích rút ra đươc số frame tương ứng
-9.41-
 ï .
Hashed page tables
 Các hệ thống 64-bit địa chỉ thường dùng clustered page table, i.e. 
ãi t h h t bl th hi á đ á hi à t ( 16 t )
-9.42-
mo mục rong as a e am c eu en n eu rang ~ rang 
thay vì 1 trang.
Chia sẻ các trang nhớ
Process 1
ed 1 30
0
1 data 1
ed 2
ed 3
4
6
1
1
2
3
Process 2
ed 1
2 data 3
3 ed 1
4 d 2
data 1
ed 2
ed 3
3
4
6
0
1
2
e 
5
6 ed 3
ed 1
ed 2
3
4
0
1
data 2
73 7 data 2
8
ed 2
data 3
6
2
2
3
9
10
-9.43-
Process 3
Phân đoạn (segmentation)
 Nhìn lại cơ chế phân trang
– user-view (không gian địa chỉ ảo) tách biệt với không gian bộ nhớ thực. 
Cơ chế phân trang thực hiện phép ánh xạ user-view vào bộ nhớ thực.
 Trong thực tế, dưới góc nhìn của user, một chương trình cấu thành từ 
nhiều phân đoạn (segment). Mỗi phân đoạn là một đơn vị luận lý, ví 
dụ như:
– main program, procedure, function, local variables, global variables, 
common block, stack, symbol table, arrays
 Cơ chế phân đoạn là mô hình quản lý bộ nhớ hỗ trợ user-view
– Không gian địa chỉ ảo là một tập các phân đoạn (segment), mỗi phân 
đoạn có tên và kích thước riêng.
– Một địa chỉ luận lý được định vị bằng tên phân đoạn và độ dời (offset) 
bên trong phân đoạn đó
-9.44-
User-view của một chương trình
 Thông thường, một chương trình 
được biên dịch. Trình biên dịch sẽ 
tự động xây dựng các segment. procedure
stack
 Ví dụ, trình biên dịch Pascal sẽ tạo 
ra các segment sau:
symbol 
table
– Global variables
– Procedure call stack
– Procedure/function code
function
sqrt
main program
– Local variable
 Trình loader sẽ gán mỗi segment 
một số định danh riêng.
Logical address space
-9.45-
Mô hình cơ chế phân đọan 
user space physical memory space
1
1
2
4
3
4 3
2
-9.46-
Tổ chức của cơ chế phân đoạn 
 Địa chỉ luận lý là một cặp giá trị
 Bảng phân đoạn (segment table)
– base – chứa địa chỉ khởi đầu của phân đoạn trong bộ nhớ
– limit – xác định kích thước của phân đoan ï
 Segment-table base register (STBR): trỏ đến vị trí bảng phân đoạn 
trong bộ nhớ 
 Segment-table length register (STLR): số segment của chương trình
M ät hỉ á t l ø hơ l ä á STLR o c so segmen s a ïp e neu s < 
-9.47-
Một ví dụ về cơ chế phân đoạn 
stack 1400
procedure
symbolsegment 0
segment 3
segment 0
limit base
0 1000 1400
2400
3200 
table
function
sqrt segment 4
segment 3
segment 2
1 400 6300
2 400 4300
3 1100 3200
4300
main program
segment 1
segment 2
segment 4
4 1000 4700
segment
table
4700
5700 
segment 1
Logical address space
6300
6700
-9.48-
physical memory space
Phần cứng hỗ trợ phân đoạn
s
segment
table
limit base
CPU s d
< + physicalmemory
yes
no
t dd i
-9.49-
rap; a ress ng error
Chuyển đổi bộ nhớ phân đoạn
-9.50-
Chia sẻ các phân đoạn
editor
data 1
limit base
0 25286 43062
43062
segment 0 segment 1
1 4425 68348
segment table 
process P1
editor
Logical address space 
process P1
data 1
72773
68348
editor
data 2
limit base
0 25286 43062
d t 2
90003
segment 0 segment 1
L i l dd
1 8850 90003
segment table 
process P2
a a 
98553
-9.51-
og ca a ress space 
process P2
physical memory