Bài giảng Nguyên lý hệ điều hành - Nguyễn Hải Châu - Tuần 6: Quản lý bộ nhớ

 tiên 
cao: roll in để tiếp tục thực hiện
z Thời gian swap tỷ lệ thuận với dung lượng bộ nhớ 
được swap vào/ra 
z UNIX, Linux, and Windows sử dụng swapping
14
Minh họa swapping
15
Cấp phát liên tục 
(Contiguous allocation)
16
Cấp phát bộ nhớ liên tục
z Bộ nhớ trong thường được chia thành 2 phần:
z Phần dành cho hệ điều hành (resident) thường 
dùng phần thấp của bộ nhớ với các ngắt
z NSD dùng phần cao của bộ nhớ. Mỗi tiến trình 
được cấp phát một vùng liên tục của bộ nhớ
z Thanh ghi relocation dùng để bảo vệ các tiến 
trình của NSD và để tránh thay đổi mã và dữ
liệu của HĐH
z Thanh ghi relocation chứa giá trị nhỏ nhất của 
địa chỉ vật lý, thanh ghi limit chứa độ lớn của 
miền địa chỉ ảo (địa chỉ ảo < limit)
17
Minh họa thanh ghi relocation, limit
18
Cấp phát liên tục (tiếp): MFT
z Bộ nhớ được chia thành các khối với cỡ cố 
định, mỗi tiến trình được cấp phát một khối
z Khi tiến trình kết thúc, khối bộ nhớ đã cấp 
phát cho tiến trình được giải phóng để cấp 
phát cho tiến trình khác
z Mức độ đa chương trình bị hạn chế bởi các 
khối
z Cỡ của tiến trình bị hạn chế bởi cỡ của khối
z Các HĐH/máy tính sử dụng MFT: IBM/360
419
Cấp phát liên tục (tiếp): MVT
z Cấp phát MVT
z Hole – khối bộ nhớ rỗi; các khối rỗi với kích cỡ khác 
nhau rải rác trong bộ nhớ
z Một tiến trình sẽ được cấp phát một khối bộ nhớ đủ
lớn để thực hiện
z HĐH có thông tin về các khối đã cấp phát và khối rỗi
HĐH
Tiến trình 5
Tiến trình 8
Tiến trình 2
HĐH
Tiến trình 5
Tiến trình 2
HĐH
Tiến trình 5
Tiến trình 2
HĐH
Tiến trình 5
Tiến trình 9
Tiến trình 2
Tiến trình 9
Tiến trình 10
20
Các chiến lược cấp phát
z First-fit: Cấp phát khối nhớ đầu tiên thỏa 
mãn điều kiện.
z Best-fit: Cấp phát khối nhớ bé nhất thỏa 
mãn điều kiện: Phải duyệt toàn bộ danh sách 
khối nhớ
z Worst-fit: Cấp phát khối nhớ lớn nhất thỏa 
mãn điều kiện: Phải duyệt toàn bộ danh sách 
khối nhớ
z First-fit và best-fit tốt hơn worst-fit theo nghĩa 
tốc độ và tận dụng bộ nhớ
21
Vấn đề phân mảnh
z External Fragmentation (Phân mảnh ngoài): Tổng 
dung lượng đáp ứng được nhu cầu cấp phát nhưng 
các khối không liên tục
z Internal Fragmentation (Phân mảnh trong) –
Dung lượng bộ nhớ đã cấp phát cho tiến trình 
không được sử dụng hết
z Giảm phân mảnh ngoài: Compaction
z Xáo trộn các khối để các khối nhớ rỗi nằm liên tục
z Compaction chỉ thực hiện được khi relocation là động, và 
được thực hiện ở execution-time
z Ví dụ: Tiện ích Defragmentation của Windows
22
Phân trang (Paging)
23
Phân trang (paging)
z Phân trang là chiến lược cấp phát bộ nhớ cho phép không 
gian địa chỉ logic của một tiến trình có thể không liên tục; 
tiến trình được cấp phát bộ nhớ vật lý khi có bộ nhớ rỗi
z Bộ nhớ vật lý được chia thành các frame cỡ cố định, nhỏ
(là lũy thừa của 2, ví dụ 512, 1024, 8192)
z Chia bộ nhớ ảo thành các khối cùng cỡ gọi là trang (page)
z HĐH có danh sách các frame rỗi
z Để thực hiện một chương trình cỡ n trang, cần tìm n frame 
rỗi để nạp chương trình
z Có một bảng trang để ánh xạ trang→frame
z Bảng trang: chung trong HĐH, mỗi tiến trình có một copy 24
Cách đánh địa chỉ theo trang
z Địa chỉ được đánh một cách phân cấp:
z Số hiệu trang (Page number - p) – Được sử dụng làm chỉ số 
đến phần tử trong bảng trang chứa địa chỉ cơ sở của các 
frame trong bộ nhớ vật lý
z Offset trang (Page offset - d) – Địa chỉ tương đối trong trang
z Địa chỉ ảo có m bit, sử dụng m-n bit cao làm số hiệu 
trang và n bit thấp làm offset
z Không có phân mảnh ngoài, có phân mảnh trong:
z Giảm cỡ trang→Giảm phân mảnh trong→Giảm hiệu năng
z Tăng cỡ trang→Tăng hiệu suất→Tăng phân mảnh trong
525
Chuyển đổi địa chỉ
26
Ví dụ phân trang 1
27
Ví dụ phân trang 2
Cỡ của 
một trang 
là 4 bytes
28
Bảng frame rỗi
Trước cấp phát Sau cấp phát
29
Cài đặt bảng trang
z Bảng trang được lưu ở bộ nhớ trong
z Thanh ghi cơ sở bảng trang (page-table base 
register) (PTBR) trỏ đến bảng trang
z Thanh ghi độ dài bảng trang (page-table
length register) (PTLR) lưu cỡ bảng trang
z Sử dụng bảng trang, mọi thao tác truy cập 
dữ liệu/lệnh cần tới 2 lần truy cập bộ nhớ (1 
cho bảng trang, 1 cho dữ liệu/lệnh)
30
Cài đặt bảng trang (tiếp)
z Truy cập bộ nhớ hai lần: Giảm tốc độ
z Giải quyết vấn đề 2 lần truy cập bộ nhớ: Sử
dụng phần cứng cache có tốc độ truy cập 
cao gọi là bộ nhớ kết hợp (associative 
memory) hoặc vùng đệm hỗ trợ chuyển đổi 
(translation look-aside buffers -TLB)
z Mỗi phần tử trong TLB có hai phần: khóa và
giá trị
z Số lượng các phần tử của TLB thường từ 64 
đến 1024
631
Bộ nhớ kết hợp
z Bộ nhớ kết hợp
z Chuyển đổi địa chỉ (A´, A´´)
if A´ nằm trong thanh ghi kết hợp, lấy frame#.
else lấy frame# từ bảng trang trong bộ nhớ
Page # Frame #
32
Phân trang phần cứng với TLB
33
Thời gian truy cập hiệu quả
z Thời gian tìm kiếm ở thanh ghi kết hợp = ε
(đơn vị thời gian)
z Thời gian truy cập bộ nhớ là n đơn vị thời gian
z Hit ratio: Số phần trăm (%) địa chỉ trang được 
tìm thấy ở các thanh ghi kết hợp/TLB
z Hit ratio = α
z Thời gian truy cập hiệu quả (EAT):
EAT = (n + ε) α + (2n + ε)(1 – α) = 2n + ε – αn
34
Bảo vệ bộ nhớ
z Bộ nhớ được bảo vệ nhờ kết hợp bit bảo vệ
trong mỗi phần tử ở bảng trang
z Bit hợp lệ-không hợp lệ (valid-invalid) kết nối 
với mỗi phần tử trong bảng trang:
z “valid” chỉ ra rằng trang thuộc không gian địa chỉ
logic của tiến trình → trang hợp lệ
z “invalid” chỉ ra rằng trang không thuộc không gian 
địa chỉ logic của tiến trình
35
Ví dụ bit valid (v)/invalid (i) 
trong bảng trang
36
Các trang chung
z Mã dùng chung
z Nhiều tiến trình (soạn thảo, compiler...) có thể dùng 
chung các đoạn mã reentrant (đoạn mã không tự 
thay đổi chính nó)
z Đoạn mã chung phải xuất hiện ở cùng một vị trí địa 
chỉ trong không gian địa chỉ logic/ảo của tất cả các 
tiến trình
z Mã lệnh và dữ liệu riêng
z Mỗi tiến trình có một bản riêng chứa lệnh và dữ liệu
z Các trang chứa lệnh và dữ liệu riêng có thể ở bất 
kỳ vị trí nào trong không gian địa chỉ của tiến trình
737
Ví dụ các trang chung
38
Cấu trúc bảng trang
Bảng trang phân cấp
Bảng trang băm
Bảng trang ngược
39
Bảng trang phân cấp
z Bộ nhớ máy tính lớn (232-264 bytes): Nếu 
dùng bảng trang một cấp thì bảng trang có
cỡ rất lớn: Tốn bộ nhớ, tìm kiếm chậm
z Không gian địa chỉ logic được quản lý bởi 
nhiều bảng trang ở nhiều cấp
z Một kỹ thuật đơn giản nhất là bảng trang hai 
cấp. Có thể có bảng trang hai, ba, bốn cấp
40
Ví dụ bảng trang hai cấp
z Địa chỉ logic (trên máy 32-bit, trang cỡ 4K=212) được 
chia thành:
z Địa chỉ trang: 20 bits.
z Địa chỉ offset: 12 bits.
z Bảng trang 2 cấp (địa chỉ 20 bit) được chia thành:
z 10-bit địa chỉ trang cấp 1
z 10-bit địa chỉ trang cấp 2
z Khi đó địa chỉ logic có dạng:
trong đó p1 là chỉ số đến bảng trang ngoài, p2 là chỉ
số đến trang (thực sự) ở bảng trang ngoài
Địa chỉ trang Offset
p1 p2 d
10 10 12
41
Sơ đồ bảng trang hai cấp
42
Tính địa chỉ với bảng trang hai 
cấp
843
Bảng trang băm
z Thường sử dụng khi địa chỉ > 32 bit
z Số hiệu/địa chỉ trang được băm trong bảng 
trang. Bảng trang này chứa dãy các phần tử
(các trang) được băm ở cùng một vị trí
z Số hiệu trang được so sánh trong dãy các 
trang được băm ở cùng một vị trí để từ đó
tìm ra frame vật lý
44
Bảng trang băm
45
Bảng trang ngược
z Giải pháp giảm bộ nhớ lưu các bảng trang
z Mỗi phần tử trong bảng ứng với một frame
z Mỗi phần tử chứa địa chỉ ảo của trang và
thông tin về tiến trình đang sử dụng trang đó
z Giảm dung lượng bộ nhớ cần để lưu các 
bảng trang, nhưng tăng thời gian cần để tìm 
trong bảng khi cần tham chiếu đến một trang
z Sử dụng bảng băm để hạn chế số lần tìm 
kiếm trong các phần tử bảng trang
46
Kiến trúc bảng trang ngược
47
Phân đoạn 
(Segmentation)
48
Phân đoạn
z Phương thức quản lý bộ nhớ cho phép NSD “nhìn”
bộ nhớ một cách dễ dàng dưới góc độ lập trình
z Một chương trình gồm nhiều phân đoạn, mỗi phân 
đoạn thể hiện dưới góc độ lập trình ở dạng:
main program, // Chương trình chính
function, // Các hàm
method, // Các phương thức
object, // Các đối tượng, lớp
local/global variables, // Các biến
common block, // Các khối chung
stack, // Ngăn xếp
symbol table, arrays // Bảng ký hiệu, mảng
949
Chương trình nhìn từ NSD
50
Phân đoạn: Cách nhìn logic
1
3
2
4
1
4
2
3
Không gian địa chỉ của NSD Không gian bộ nhớ vật lý
51
Kiến trúc phân đoạn
z Địa chỉ ảo/logic là một bộ đôi:
z Bảng phân đoạn (segment table) – ánh xạ địa 
chỉ vật lý 2 cấp; mỗi phần tử bảng có:
z base: Địa chỉ vật lý bắt đầu của phân đoạn (segment)
z limit: Độ dài của phân đoạn (segment).
52
Kiến trúc phân đoạn (tiếp)
z Thanh ghi cơ sở bảng phân đoạn (Segment-
table base register STBR) trỏ đến base
z Thanh ghi độ dài bảng phân đoạn (Segment-
table length register - STLR) chỉ ra số lượng 
phân đoạn được sử dụng trong tiến trình;
z Số hiệu phân đoạn s là hợp lệ nếu thỏa mãn 
điều kiện: s < STLR.
53
Kiến trúc phân đoạn (tiếp)
z Định vị lại (relocation)
z Động
z Sử dụng bảng phân đoạn
z Dùng chung (sharing)
z Có các phân đoạn dùng chung
z Sử dụng cùng một số hiệu phân đoạn (segment 
number)
z Cấp phát (allocation)
z first fit/best fit
z Phân mảnh ngoài 54
Kiến trúc phân đoạn (tiếp)
z Bảo vệ bộ nhớ:Mỗi phân đoạn có:
z Bit kiểm tra = 0 ⇒ phân đoạn không hợp lệ
z read/write/execute privileges
z Protection bits associated with segments; 
code sharing occurs at segment level.
z Do phân đoạn có cỡ biến đổi → Gặp vấn đề 
tương tự trong cấp phát bộ nhớ liên tục
z Kết hợp phân đoạn với phân trang để tăng 
hiệu quả sử dụng bộ nhớ, dễ cấp phát hơn 
(ví dụ: MULTICS, Intel 386)
10
55
Phần cứng phân đoạn
56
Ví dụ phân đoạn
57
Tóm tắt
z Địa chỉ logic (ảo)/Địa chỉ vật lý (thật)
z Các phương án ánh xạ địa chỉ của chương trình 
vào bộ nhớ
z Cấp phát bộ nhớ liên tục, phân mảnh, các chiến 
lược cấp phát first-fit, best-fit, worst-fit
z Phân trang
z Trang, frame
z Bảng trang, bảng trang phân cấp, bảng trang ngược
z Phân đoạn, bảng phân đoạn