Bài giảng Hệ điều hành (Operating Systems) - Hà Lê Hoài Trung - Chương 7: Quản lý bộ nhớ

ng trang n bao nhiêu bit? 
Khoa KTMT 34 
Khoa KTMT 35 
1.Cơ chế phân trang (tt) 
Trước khi và sau khi cấp phát cho Process mới 
Khoa KTMT 36 
B) Cài đặt bảng trang (Paging hardware) 
 Bảng phân trang thường được lưu giữ trong bộ nhớ chính 
‟ Mỗi process được hệ điều hành cấp một bảng phân trang 
‟ Thanh ghi page-table base (PTBR) trỏ đến bảng phân trang 
‟ Thanh ghi page-table length (PTLR) biểu thị kích thước của bảng 
phân trang (có thể được dùng trong cơ chế bảo vệ bộ nhớ) 
 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) 
Khoa KTMT 37 
B) Cài đặt bảng trang (Paging hardware) 
 Dùng thanh ghi Page-Table Base Register (PTBR) 
p 
Khoa KTMT 38 
Paging hardware với TLB 
Khoa KTMT 39 
C) Effective access time (EAT) 
„ Tính thời gian truy xuất hiệu dụng (effective access time, 
EAT) 
 Thời gian tìm kiếm trong TLB (associative lookup):  
 Thời gian một chu kỳ truy xuất bộ nhớ: x 
 Hit ratio: tỉ số giữa số lần chỉ số trang được tìm thấy (hit) 
trong TLB và số lần truy xuất khởi nguồn từ CPU 
‟ Kí hiệu hit ratio:  
 Thời gian cần thiết để có được chỉ số frame 
‟ Khi chỉ số trang có trong TLB (hit)  + x 
‟ Khi chỉ số trang không có trong TLB (miss)  + x + x 
 Thời gian truy xuất hiệu dụng 
 EAT = ( + x) + ( + 2x)(1 ‟ ) 
 = (2 ‟ )x +  
Khoa KTMT 40 
C) Effective access time (EAT) 
 Ví dụ 1: đơn vị thời gian 
nano giây 
 Associative lookup = 20 
 Memory access = 100 
 Hit ratio = 0.8 
 EAT = (100 + 20)  0.8 + 
 (200 + 20)  0.2 
 = 1.2  100 + 20 
 = 140 
 Ví dụ 2 
 Associative lookup = 20 
 Memory access = 100 
 Hit ratio = 0.98 
 EAT = (100 + 20)  0.98 + 
 (200 + 20)  0.02 
 = 1.02  100 + 20 
 = 122 
Ví dụ 
Xét một hệ thống sử dụng kỹ thuật phân trang, với 
bảng trang được lưu trữ trong bộ nhớ chính. 
a) Nếu thời gian cho một lần truy xuất bộ nhớ bình 
thường là 200nanoseconds, thì mất bao nhiêu thời 
gian cho một thao tác truy xuất bộ nhớ trong hệ 
thống này ? 
b) Nếu sử dụng TLBs với hit-ratio ( tỉ lệ tìm thấy) 
là 75%, thời gian để tìm trong TLBs xem như bằng 
0, tính thời gian truy xuất bộ nhớ trong hệ thống ( 
effective memory reference time) 
Khoa KTMT 41 
Khoa KTMT 42 
D) Tổ chức bảng trang - Phân trang đa cấp 
 Các hệ thống hiện đại đều hỗ trợ không gian địa chỉ ảo 
rất lớn (2
32
 đến 2
64
), ở đây giả sử là 2
32
‟ Giả sử kích thước trang nhớ là 4KB (= 212) 
 bảng phân trang sẽ có 232/212 = 220 = 1M mục. 
‟ Giả sử mỗi mục gồm 4 byte thì mỗi process cần 4MB cho bảng 
phân trang 
 VD: Phân trang hai cấp 
P2 d 
Số trang Độ dời trang 
P1 
10 bit 10 bit 12 
Phân trang đa cấp (tt) 
Khoa KTMT 43 
Khoa KTMT 44 
D) Tổ chức bảng trang 
Phân trang đa cấp 
Khoa KTMT 45 
D) Tổ chức bảng trang 
 Bảng trang nghịch đảo: sử dụng cho tất cả các Process 
i 
Khoa KTMT 46 
E) 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 giữ trong 
bảng phân trang. Các bit này biểu thị các thuộc tính sau 
‟ read-only, read-write, execute-only 
 Ngoài ra, còn có một valid/invalid bit gắn với mỗi mục 
trong bảng phân trang 
‟ “valid”: cho biết là trang của process, do đó là một trang hợp lệ. 
‟ “invalid”: cho biết là trang không của process, do đó là một trang 
bất hợp lệ. 
Khoa KTMT 47 
Bảo vệ bằng valid/invalid bit 
 Mỗi trang nhớ có kích thước 2K = 2048 
 Process có kích thước 10,468  phân mảnh nội ở frame 9 
(chứa page 5), các địa chỉ ảo > 12287 là các địa chỉ invalid. 
 Dùng PTLR để kiểm tra truy xuất đến bảng phân trang có nằm 
trong bảng hay không. 
00000 
10468 
12287 
2 v 
3 v 
4 v 
7 v 
8 v 
9 v 
0 i 
0 i 
frame 
number 
valid/ 
invalid bit 
0 
1 
2 
3 
4 
5 
6 
7 
0 
1 
2 page 0 
3 page 1 
4 page 2 
5 
6 
7 page 3 
8 page 4 
9 page 5 
... 
page n 
16383 
14 bit 
Khoa KTMT 48 
F) Chia sẻ các trang nhớ 
Process 1 
ed 1 
ed 2 
ed 3 
data 1 
ed 1 
ed 2 
ed 2 
data 3 
Process 3 
3 
4 
6 
2 
0 
1 
2 
3 
3 
4 
6 
1 
0 
1 
2 
3 
Process 2 
ed 1 
ed 2 
ed 3 
data 2 
3 
4 
6 
7 
0 
1 
2 
3 
0 
1 data 1 
2 data 3 
3 ed 1 
4 ed 2 
5 
6 ed 3 
7 data 2 
8 
9 
10 
Bộ nhớ thực 
Khoa KTMT 49 
2.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 đoạn (segment). Mỗi đoạn là một đơn 
vị luận lý của chương trình, như 
‟ main program, procedure, function 
‟ local variables, global variables, common block, stack, symbol 
table, arrays,… 
Khoa KTMT 50 
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. 
 Ví dụ, trình biên dịch Pascal sẽ 
tạo ra các segment sau: 
‟ Global variables 
‟ Procedure call stack 
‟ Procedure/function code 
‟ Local variable 
 Trình loader sẽ gán mỗi 
segment một số định danh 
riêng. 
procedure 
stack 
symbol 
table 
function 
sqrt 
main program 
Logical address space 
Khoa KTMT 51 
Phân đoạn 
 Dùng cơ chế phân đoạn để quản lý bộ nhớ có hỗ trợ 
user view 
‟ Không gian địa chỉ ảo là một tập các đoạn, mỗi đ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 đoạn và độ dời (offset) 
bên trong đoạn đó (so sánh với phân trang!) 
Khoa KTMT 52 
Phân đoạn (tt) 
logical address space physical memory space 
segment 1 
segment 2 
segment 3 segment 4 
Khoa KTMT 53 
Cài đặt phân đoạn 
 Địa chỉ luận lý là một cặp giá trị 
 (segment number, offset) 
 Bảng phân đoạn (segment table): gồm nhiều mục, mỗi 
mục chứa 
‟ base, chứa địa chỉ khởi đầu của segment trong bộ nhớ 
‟ limit, xác định kích thước của segment 
 Segment-table base register (STBR): trỏ đến vị trí bảng 
phân đoạn trong bộ nhớ 
 Segment-table length register (STLR): số lượng segment 
của chương trình 
 Một chỉ số segment s là hợp lệ nếu s < STLR 
Khoa KTMT 54 
Một ví dụ về phân đoạn 
procedure 
stack 
symbol 
table 
function 
sqrt 
main program 
segment 0 
segment 3 
segment 1 
segment 2 
segment 4 
procedure 
stack 
main 
symbol table 
function sqrt 
limit base 
0 1000 1400 
1 400 6300 
2 400 4300 
3 1100 3200 
4 1000 4700 
segment 
table 
logical address space 
physical memory space 
1400 
2400 
3200 
4300 
4700 
5700 
6300 
Khoa KTMT 55 
Phần cứng hỗ trợ phân đoạn 
CPU 
 + 
physical 
memory 
no 
trap; addressing error 
limit base 
s 
s d 
yes 
segment 
table 
Khoa KTMT 56 
Chuyển đổi địa chỉ trong cơ chế phân đoạn 
Ví dụ 
Khoa KTMT 57 
Chia sẻ các đoạn 
editor 
data 1 
segment 0 
segment 1 
logical address space 
process P1 
editor 
data 2 
segment 0 
segment 1 
logical address space 
process P2 
limit base 
0 25286 43062 
1 4425 68348 
segment table 
process P1 
limit base 
0 25286 43062 
1 8850 90003 
segment table 
process P2 
editor 
data 1 
data 2 
physical memory 
43062 
72773 
68348 
90003 
98853 
Khoa KTMT 58 
3.Kết hợp phân trang và phân đoạn 
 Kết hợp phân trang và phân đoạn nhằm kết hợp các ưu 
điểm đồng thời hạn chế các khuyết điểm của phân 
trang và phân đoạn: 
‟ Vấn đề của phân đoạn: Nếu một đoạn quá lớn thì có thể không 
nạp nó được vào bộ nhớ. 
‟ Ý tưởng giải quyết: paging đoạn, khi đó chỉ cần giữ trong bộ nhớ 
các page của đoạn hiện đang cần. 
Logic Addr = 
Khoa KTMT 59 
3.Kết hợp phân trang và phân đoạn 
Khoa KTMT 60 
3.Kết hợp phân trang và phân đoạn 
Bài Tập 
 Giả sử bộ nhớ chính được phân thành các phân vùng cĩ kích 
thước là 600K, 500K, 200K, 300K ( theo thứ tự ), cho biết các tiến 
trình cĩ kích thước 212K, 417K, 112K và 426K ( theo thứ tự ) sẽ 
được cấp phát bộ nhớ như thế nào, nếu sử dụng : 
a) Thuật tốn First fit 
b) Thuật tốn Best fit 
c) Thuật tốn Worst fit 
Thuật tốn nào cho phép sử dụng bộ nhớ hiệu qủa nhất trong trường 
hợp trên ? 
Khoa KTMT 61 
Bài Tập 
 Xét một khơng gian cĩ bộ nhớ luận lý kích thước 
1 trang là 1kb. Tính số trang và độ dời (offset) 
của từng địa chỉ sau: 
a) 2.375 
b) 19.366 
c) 30.000 
d) 256 
e) 16.385 
Khoa KTMT 62 
Bài Tập 
 Xét một khơng gian cĩ bộ nhớ luận lý cĩ 64 
trang, mỗi trang cĩ 1024 từ, mỗi từ là 2 byte được 
ánh xạ vào bộ nhớ vật lý cĩ 32 trang: 
a) Địa chỉ bộ nhớ vật lý cĩ bao nhiêu bit? 
b) Địa chỉ bộ nhớ luận lý cĩ bao nhiêu bit? 
c) Cĩ bao nhiêu mục trong bảng phân trang? Mỗi 
mục chứa bao nhiêu bit? 
Khoa KTMT 63 
Bài tập 
Xét một hệ thống sử dụng kỹ thuật phân trang, với 
bảng trang được lưu trữ trong bộ nhớ chính. 
a) Nếu thời gian cho một lần truy xuất bộ nhớ bình 
thường là 100 nanoseconds, thì mất bao nhiêu thời 
gian cho một thao tác truy xuất bộ nhớ trong hệ 
thống này ? 
b) Nếu sử dụng TLBs với hit-ratio ( tỉ lệ tìm thấy) 
là 85%, thời gian để tìm trong TLBs là 20 
nanosecond, tính thời gian truy xuất bộ nhớ trong 
hệ thống ( effective memory reference time) 
Khoa KTMT 64 
Bài tập 
Xét bảng phân đoạn sau đây : 
Cho biết địa chỉ vật lý tương ứng với các địa chỉ logic sau 
đây : 
a. 0,430 b. 1,100 c. 2,500 d. 3,400 e. 4,112 
Khoa KTMT 65 
Segment Base Length 
0 219 600 
1 2300 14 
2 90 100 
3 1327 580 
4 1952 96