Bài giảng Hệ điều hành - Chương 7: Quản lý bộ nhớ (Phần 2) - Trường Đại học Công nghệ thông tin

HỆ ĐIỀU HÀNH
Chương 7 – Quản lý bộ nhớ (2)
14/03/2017
1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 1
Câu hỏi ôn tập chương 7-1
1/17/2018 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)
1/17/2018 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)
1/17/2018 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 
1/17/2018 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 
1/17/2018 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
1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 7
Cơ chế phân trang (tt)
1/17/2018 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ớ
1/17/2018 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ì
1/17/2018 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
1/17/2018 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)
1/17/2018 12Copyrights 2017 CE-UIT. All Rights Reserved.
Ví dụ:
Cơ chế phan trang (tt)
1/17/2018 13Copyrights 2017 CE-UIT. All Rights Reserved.
Cài đặt bảng trang (paging hardware)
1/17/2018 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)
1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 15
Dùng thanh ghi Page -Table Base Register (PTBR)
Cài đặt bảng trang (tt)
1/17/2018 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 + ε
1/17/2018 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
1/17/2018 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
1/17/2018 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)
1/17/2018 20Copyrights 2017 CE-UIT. All Rights Reserved.
Tổ chức bảng trang (tt)
1/17/2018 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ộ