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

HỆ ĐIỀU HÀNH
Chương 7 – Quản lý bộ nhớ (2)
14/03/2017
11/2/2017 Copyrights 2017 CE-UIT. All Rights Reserved. 1
Câu hỏi ôn tập chương 7-1
11/2/2017 Copyrights 2017 CE-UIT. All Rights Reserved. 2
 Chuyển đổi địa chỉ là gì? Địa chỉ nhớ được biểu diễn 
như thế nào trong quá trình chạy 1 chương trình?
 Khi nào địa chỉ lệnh và dữ liệu được chuyển thành địa 
chỉ thật?
 Thế nào là dynamic linking? Nêu ưu điểm?
 Thế nào là dynamic loading?
 Nêu cơ chế overlay? Swapping?
 Nêu các mô hình quản lý bộ nhớ?
Câu hỏi ôn tập chương 7-1 (tt)
11/2/2017 Copyrights 2017 CE-UIT. All Rights Reserved. 3
 Thế nào là phân mảnh ngoại? Phân mảnh nội? Cho ví 
dụ?
 Fixed partitioning là gì? Các chiến lược placement?
 Dynamic partitioning là gì? Các chiến lược placement?
Câu hỏi ôn tập chương 7-1 (tt)
11/2/2017 Copyrights 2017 CE-UIT. All Rights Reserved. 4
Giả sử bộ nhớ chính được cấp phát các phân vùng có kích 
thước là 600K, 500K, 200K, 300K (theo thứ tự), sau khi 
thực thi xong, các tiến trình có kích thước 212K, 417K, 
112K, 426K (theo thứ tự) sẽ được cấp phát bộ nhớ như thế 
nào, nếu sử dụng: Thuật toán First fit, Best fit, Next fit 
(con trỏ đang ở vị trí 500K), Worst fit? Thuật toán nào cho 
phép sử dụng bộ nhớ hiệu quả nhất trong trường hợp trên
Mục tiêu chương 7-2
 Hiểu và vận dụng các cơ chế quản lý bộ nhớ: 
 Cơ chế phân trang
 Cơ chế phân đoạn
11/2/2017 Copyrights 2017 CE-UIT. All Rights Reserved. 5
Nội dung chương 7-1
Cấp phát không liên tục
 Cơ chế phân trang
 Cơ chế phân đoạn
 Cơ chế kết hợp phân trang và phân đoạn
11/2/2017 Copyrights 2017 CE-UIT. All Rights Reserved. 6
Cơ chế phân trang
 Bộ nhớ vật lý  khung trang (frame).
 Kích thước của frame là lũy thừa của 2, từ khoảng 512 byte đến
16MB.
 Bộ nhớ luận lý (logical memory) hay không gian địa chỉ luận lý là tập
mọi địa chỉ luận lý mà một chương trình bất kỳ có thể sinh ra  page.
 Ví dụ
MOV REG,1000 //1000 là một địa chỉ luận lý
 Bảng phân trang (page table) để ánh xạ địa chỉ luận lý thành địa chỉ
thực
11/2/2017 Copyrights 2017 CE-UIT. All Rights Reserved. 7
Cơ chế phân trang (tt)
11/2/2017 Copyrights 2017 CE-UIT. All Rights Reserved. 8
logical memory
1
4
3
5
0
1
2
3
page table
page 0
page 2
physical memory
frame
number
0
1
2
3
page 14
5 page 3
page
number
0
1
2
3
Cơ chế phân trang (tt)
 Chuyển đổi địa chỉ trong paging
 Cài đặt bảng trang
 Effective access time
 Tổ chức bảng trang
 Bảo vệ bộ nhớ
11/2/2017 Copyrights 2017 CE-UIT. All Rights Reserved. 9
Chuyển đổi địa chỉ trong paging
 Địa chỉ luận lý gồm có:
 Số hiệu trang (Page number) p
 Địa chỉ tương đối trong trang (Page offset) d
 Nếu kích thước của không gian địa chỉ ảo là 2m, và kích thước của trang
là 2n (đơn vị là byte hay word tùy theo kiến trúc máy) thì
11/2/2017 Copyrights 2017 CE-UIT. All Rights Reserved. 10
p d
page number page offset
m - n bits
(định vị từ 0 ÷ 2m − n − 1)
n bits
(định vị từ 0 ÷ 2n − 1)
Bảng trang sẽ có tổng cộng 2m/2n = 2m - n mục (entry)
Chuyển đổi địa chỉ trong paging
11/2/2017 Copyrights 2017 CE-UIT. All Rights Reserved. 11
CPU p d f d
f
p
page table
logical
address 
physical
address 
physical
memory
f 0000
f 1111
f frames
Chuyển đổi địa chỉ trong paging (tt)
11/2/2017 12Copyrights 2017 CE-UIT. All Rights Reserved.
Ví dụ:
Cơ chế phan trang (tt)
11/2/2017 13Copyrights 2017 CE-UIT. All Rights Reserved.
Cài đặt bảng trang (paging hardware)
11/2/2017 Copyrights 2017 CE-UIT. All Rights Reserved. 14
 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)
Cài đặt bảng trang (tt)
11/2/2017 Copyrights 2017 CE-UIT. All Rights Reserved. 15
Dùng thanh ghi Page -Table Base Register (PTBR)
Cài đặt bảng trang (tt)
11/2/2017 Copyrights 2017 CE-UIT. All Rights Reserved. 16
 Dùng TLB
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 + ε
11/2/2017 17Copyrights 2017 CE-UIT. All Rights Reserved.
Effective access time (EAT) (tt)
 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
11/2/2017 18
 Ví dụ 2: đơn vị thời gian nano
giây
Associative lookup = 20
Memory access = 100
Hit ratio = 0.98
EAT = (100 + 20) × 0.98 +
(200 + 20) × 0.02
= 1.02× 100 + 20
= 122
Copyrights 2017 CE-UIT . All Rights Reserved.
Tổ chức bảng trang
 Các hệ thống hiện đại đều hỗ trợ không gian địa chỉ ảo rất lớn (232
đến 264), ở đây giả sử là 232
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 
Ví dụ: Phân trang  2 cấp
11/2/2017 19Copyrights 2017 CE-UIT. All Rights Reserved.
P2 d
Soá trang Ñoä dôøi trang
P1
10 bit 10 bit 12
Tổ chức bảng trang (tt)
11/2/2017 20Copyrights 2017 CE-UIT. All Rights Reserved.
Tổ chức bảng trang (tt)
11/2/2017 21Copyrights 2017 CE-UIT. All Rights Reserved.
Bảng trang nghịch đảo (IBM system/38, IBM RISC, IBM RT): sử
dụng cho tất cả các Process
Bảo vệ bộ nhớ
11/2/2017 22Copyrights 2017 CE-UIT. All Rights Reserved.
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ệ.
Bảo vệ bằng valid/invalid bit
11/2/2017 23Copyrights 2017 CE-UIT. All Rights Reserved.
00000
10468
12287
frame
number
valid/
invalid bit
0
1
2
3
4
5
6
7
16383
14 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.
Chia sẻ các trang nhớ
11/2/2017 24Copyrights 2017 CE-UIT. All Rights Reserved.
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
Bộ nhớ thực
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,
11/2/2017 25Copyrights 2017 CE-UIT. All Rights Reserved.
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.
11/2/2017 26Copyrights 2017 CE-UIT. All Rights Reserved.
procedure
stack
symbol 
table
function
sqrt
main program
Logical address space
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!)
11/2/2017 27Copyrights 2017 CE-UIT. All Rights Reserved.
Phân đoạn (tt)
11/2/2017 28Copyrights 2017 CE-UIT. All Rights Reserved.
logical address space physical memory space
segment 1
segment 2
segment 3 segment 4
Cài đặt phan đ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
11/2/2017 29Copyrights 2017 CE-UIT. All Rights Reserved.
Một ví dụ về phân đoạn
11/2/2017 30Copyrights 2017 CE-UIT. All Rights Reserved.
procedure
stack
symbol 
table
function
sqrt
main program
segment 0
segment 3
segment 1
segment 2
segment 4
segment
table
logical address space
physical memory space
1400
2400
3200
4300
4700
5700
6300
Phần cứng hỗ trợ phân đoạn
11/2/2017 31Copyrights 2017 CE-UIT. All Rights Reserved.
CPU
< +
physical
memory
no
trap; addressing error
s
yes
segment
table
Chuyển đổi địa chỉ trong cơ chế phan đoạn
11/2/2017 32Copyrights 2017 CE-UIT. All Rights Reserved.
Chia sẻ các đoạn
11/2/2017 33Copyrights 2017 CE-UIT. All Rights Reserved.
editor
data 1
segment 0 segment 1
logical address space 
process P1
editor
data 2
segment 0 segment 1
logical address space 
process P2
segment table 
process P1
segment table 
process P2
physical memory
43062
72773
68348
90003
98853
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 = 
11/2/2017 34Copyrights 2017 CE-UIT. All Rights Reserved.
Kết hợp phân trang và phân đoạn (tt)
11/2/2017
Cài đặt phân đoạn
11/2/2017 36Copyrights 2017 CE-UIT. All Rights Reserved.
Tóm tắt lại nội dung buổi học
Cấp phát không liên tục
Cơ chế phân trang 
Cơ chế phân đoạn 
Cơ chế kết hợp phân trang và phân đoạn 
11/2/2017 Copyrights 2017 CE-UIT. All Rights Reserved. 37
Bài tập 1
11/2/2017 Copyrights 2017 CE-UIT. All Rights Reserved. 38
Xét một không gian địa chỉ có 12 trang, mỗi trang có kích 
thước 2K, ánh xạ vào bộ nhớ vật lý có 32 khung trang.
Địa chỉ logic gồm bao nhiêu bit?a.
Địa chỉ physic gồm bao nhiêu bit?b.
Bài tập 2
11/2/2017 Copyrights 2017 CE-UIT. All Rights Reserved. 39
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.
Nếua. thời gian cho một lần truy xuất bộ nhớ bình
thường là 200ns 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?
Nếub. sử dụng TLBs với hit-ratio là 75%, thời gian để
tìm tròn TLBs xem như bằng 0, tính thời gian truy xuất
bộ nhớ trong hệ thống
Bài tập 3
11/2/2017 Copyrights 2017 CE-UIT. All Rights Reserved. 40
Xét bảng phân đoạn trong hình
Tính địa chỉ vật lý tương ứng với các địa chỉ logic sau đây:
430a.
110b.
2500c.
3400d.
4112e.