Bài giảng Hệ điều hành nâng cao - Trần Hạnh Nhi - Bài giảng 6: Quản lý bộ nhớ

„ KGĐC : phân chia thành các segment
„ KGVL : tổ chức thành dynamic partitions
„ Nạp tiến trình :
„ Mỗi segment cần được nạp vào một partition liên tục, tự do, đủ lớn cho
segment
„ partition nào ? ...Dynamic Allocation !
„ Các segment của cùng 1 chương trình có thể được nạp vào những partition 
không liên tục
12/2/2005 Trần Hạnh Nhi 42
Mô hình Segmentation
KGVL
int m;
main ()
{ 
F1(m);
}
F1(int x)
{ x = 9;
}
code
(main,F1)
data
(m)
stack
heap
KGDCQuản lý địa chỉ ?
12/2/2005 Trần Hạnh Nhi 43
Tổ chức Segmentation
„ Điạ chỉ logic : 
„ Địa chỉ physic : 
„ Chuyển đổi địa chỉ : Ư 
„ Chuyển đổi địa chỉ vào thời điểm thi hành
„ MMU thi hành
„ Sử dụng Segment Table (bảng phân đoạn) để lưu thông tin cấp phát BNC, làm cơ
sở thực hiện ánh xạ địa chỉ
„ Mỗi tiến trình có một Segment Table
„ Sâegment Table:
„ Số phần tử của Segment Table = Số Segment của chương trình
„ Mỗi phần tử của Segment Table mô tả cho 1 segment, và có cấu trúc :
„ base: địa chỉ vật lý trong BNC của partition chứa segment
„ limit : kích thước segment
„ Lưu trữ Segment Table ?
„ Cache : nếu đủ nhỏ
„ BNC : Segment-table base register (STBR), Segment-table length register (STLR)
12/2/2005 Trần Hạnh Nhi 44
Chuyển đổi địa chỉ trong mô hình Segmentation
Logical Addr
Seg# offset
3 128
Seg table
base limit
3 0x1000 512
mem
seg
128
+ 0x1000?
yes
no
fault
0
1
2
12/2/2005 Trần Hạnh Nhi 45
Logical-to-Physical Address Translation in segmentation
12/2/2005 Trần Hạnh Nhi 46
Nhận xét Mô hình Segmentation
„ Cấp phát không liên tục => tận dụng bộ nhớ hiệu quả
„ Hỗ trợ tái định vị
„ Từng Segment
„ Hỗ trợ Bảo vệ và Chia sẻ được ở mức module
„ Ý nghĩa của “mức module” ?
/ Chuyển đổi địa chỉ phức tạp
☺ Đã có MMU...
/ Sử dụng dynamic partition : chịu đựng
/ Dynamic Allocation : chọn vùng nhớ để cấp cho một segment
☺ First fit, Best fit, Worst fit
/ External Fragmentation :
/ Memory Compaction : chi phí cao
12/2/2005 Trần Hạnh Nhi 47
Paging
„ Hỗ trợ HĐH khắc phục bài toán cấp phát bộ nhớ động, và loại bỏ
external fragmentation
„ Mô hình Paging :
„ KGĐC : phân chia chương trình thành các page có kích thước bằng nhau
„ Không quan tâm đến ngữ nghĩa của các đối tượng nằm trong page
„ KGVL : tổ chức thành các fixed partitions có kích thước bằng nhau gọi là frame
„ page size = frame size
„ Nạp tiến trình :
„ Mỗi page cần được nạp vào một frame tự do
„ Các pages của cùng 1 chương trình có thể được nạp vào những frames 
không kế cận nhau.
„ Tiến trình kích thước N pages -> cần N frame tự do để nạp
12/2/2005 Trần Hạnh Nhi 48
Mô hình Paging
KGVL
int m;
main ()
{ 
F1(m);
}
F1(int x)
{ x = 9;
}
KGDC
Quản lý địa chỉ ?
int m;
main ()
F1(int x)
stack
heap
12/2/2005 Trần Hạnh Nhi 49
Tổ chức Paging
„ Điạ chỉ logic : 
„ Địa chỉ physic : 
„ Chuyển đổi địa chỉ : Ư 
„ Chuyển đổi địa chỉ vào thời điểm thi hành
„ MMU thi hành
„ Sử dụng Page Table để lưu thông tin cấp phát BNC, làm cơ sở thực hiện ánh xạ địa
chỉ
„ Mỗi tiến trình có một Page Table
„ Page Table 
„ Số phần tử của Page Table = Số Page trong KGĐC của chương trình
„ Mỗi phần tử của bảng Page Table mô tả cho 1 page, và có cấu trúc :
„ frame: số hiệu frame trong BNC chứa page
„ Lưu trữ Page Table ?
„ Cache : không đủ
„ BNC : Page-table base register (PTBR), Page-table length register (PTLR)
12/2/2005 Trần Hạnh Nhi 50
Chuyển đổi địa chỉ trong mô hình Paging
CPU
KGVL
Physical 
addr
Logical 
addr
p d f d
f
Page table
12/2/2005 Trần Hạnh Nhi 51
Logical-to-Physical Address Translation in Paging
12/2/2005 Trần Hạnh Nhi 52
Nhận xét Mô hình Paging
„ Loại bỏ
„ Dynamic Allocation
„ External Fragmentation
„ “Trong suốt” với LTV
„ Hỗ trợ Bảo vệ và Chia sẻ ở mức page
/ Internal Fragmentation
/ Lưu trữ Page Table trong bộ nhớ
/Tốn chỗ
/Tăng thời gian chuyển đổi địa chỉ
12/2/2005 Trần Hạnh Nhi 53
Lưu trữ Page Table
„ Giả sử hệ thống sử dụng m bit địa chỉ
„ Size of KGĐC = 2m
„ Kích thước page
„ Trên nguyên tắc tùy ý, thực tế chọn pagesize = 2n
„ Tại sao ?
„ Số trang trong KGĐC: #pages = 2m / 2n = 2m-n
„ Ví dụ : 32-bits địa chỉ, pagesize = 4K
„ KGĐC = 232 -> #pages= 232-212 = 220 = 1.000.000 pages !
„ #pages = #entry trong PT
„ Điạ chỉ logic : 
„ Page Table
/ Mỗi tiến trình lưu 1 Page Table 
/ Số lượng phần tử quá lớn -> Lưu BNC
/ Mỗi truy xuất địa chỉ sẽ tốn 2 lần truy xuất BNC
p d
(m-n) n
12/2/2005 Trần Hạnh Nhi 54
Lưu trữ Page Table : Tiết kiệm không gian
„ Sử dụng bảng trang đa cấp
„ Chia bảng trang thành các phần nhỏ, bản thân bảng trang 
cũng sẽ được phân trang
„ Chỉ lưu thường trực bảng trang cấp 1, sau đó khi cần sẽ nạp 
bảng trang cấp nhỏ hơn thích hợp...
„ Có thể loại bỏ những bảng trang chứa thông tin về miền địa 
chỉ không sử dụng
„ Sử dụng Bảng trang nghịch đảo
„ Mô tả KGVL thay vì mô tả KGĐC -> 1 IPT cho toàn bộ hệ thống
Bảng trang đa cấp
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
0
1
2
3
13
0
1
2
3
4
5
6
7
8
9
10
11
12
12
13
14
15
Page Table cấp 1
Page Table cấp 2
Page Table cấp 2
Page Table cấp 2
Page Table cấp 2
12/2/2005 Trần Hạnh Nhi 56
Mô hình bảng trang 2 cấp
12/2/2005 Trần Hạnh Nhi 57
Ví dụ mô hình bảng trang 2 cấp
„Một máy tính sử dụng địa chỉ 32bít với kích thước trang 4Kb.
„Địa chỉ logic được chia thành 2 phần:
„Số hiệu trang : 20 bits.
„Offset tính từ đầu mỗi trang :12 bits.
„Vì bảng trang lại được phân trang nên số hiệu trang lại được
chia làm 2 phần:
„Số hiệu trang cấp 1. 
„Số hiệu trang cấp 2.
12/2/2005 Trần Hạnh Nhi 58
Ví dụ mô hình bảng trang 2 cấp
„Vì thế, địa chỉ logic sẽ có dạng như sau:
page number page offset
pi p2 d
10 10 12
Bảng trang đa cấp 0
1
2
3
0
1
2
3
0
1
2
3
0
1
2
3
0
1
2
3
13
0
1
2
3
4
5
6
7
8
9
10
11
12
14
15
16
17
Page Table cấp 1
Page Table cấp 2
Page Table cấp 2
Page Table cấp 2
Page Table cấp 2 
1 2 100
12/2/2005 Trần Hạnh Nhi 60
Bảng trang nghịch đảo (Inverted Page Table)
„ Sử dụng duy nhất một bảng trang nghịch đảo cho tất cả các tiến 
trình 
„ Mỗi phần tử trong bảng trang nghịch đảo mô tả một frame, có cấu 
trúc
„ : số hiệu page mà frame đang chứa đựng
„ : id của tiến trình đang được sỡ hữu trang
„ Mỗi địa chỉ ảo khi đó là một bộ ba 
„ Khi một tham khảo đến bộ nhớ được phát sinh, một phần địa chỉ ảo 
là được đưa đến cho trình quản lý bộ nhớ để tìm phần tử
tương ứng trong bảng trang nghịch đảo, nếu tìm thấy, địa chỉ vật lý
 sẽ được phát sinh
12/2/2005 Trần Hạnh Nhi 61
Kiến trúc bảng trang nghịch đảo
12/2/2005 Trần Hạnh Nhi 62
Lưu trữ Page table : Tiết kiệm thời gian
„ Mỗi truy cập BNC cần truy xuất BNC 2 lần :
„ Tra cứu Page Table để chuyển đổi địa chỉ
„ Tra cưu bản thân data
„ Làm gì để cải thiện :
„ Tìm cách lưu PT trong cache
„ Cho phép tìm kiếm nhanh
„ PT lớn, cache nhỏ : làm sao lưu đủ ?
„ Lưu 1 phần PT...
„ Phần nào ?
„ Các số hiệu trang mới truy cập gần đây nhất...
12/2/2005 Trần Hạnh Nhi 63
Translation Lookaside Buffer (TLB)
„ Vùng nhớ Cache trong CPU được sử dụng để lưu tạm thời
một phần của PT được gọi là Translation Lookaside Buffer 
(TLB)
„ Cho phép tìm kiếm tốc độ cao
„ Kích thước giới hạn (thường không quá 64 phần tử)
„ Mỗi entry trong TLB chứa một số hiệu page và frame tương
ứng đang chứa page
„ Khi chuyển đổi địa chỉ, truy xuất TLB trước, nếu không tìm
thấy số hiệu page cần thiết, mới truy xuất vào PT để lấy
thông tin frame.
12/2/2005 Trần Hạnh Nhi 64
Translation Lookaside Buffer
12/2/2005 Trần Hạnh Nhi 65
Chuyển đổi địa chỉ với Paging
CPU p d
f d
f
d
TLB
Memory
physical address
virtual address
p f
f
PT
f
12/2/2005 Trần Hạnh Nhi 66
Sử dụng TBL
12/2/2005 Trần Hạnh Nhi 67
Bảo vệ và chia sẻ trong Segmentation và Paging
„ Bảo vệ
„ Segmentation : mỗi phần tử trong ST được gắn thêm các bit bảo
vệ
„ Mỗi segment có thể được bảo vệ tùy theo ngữ nghĩa của các đối tượng
bên trong segment
„ Paging : mỗi phần tử trong PT được gắn thêm các bit bảo vệ
„ Mỗi page không nhận thức được ngữ nghĩa của các đối tượng bên trong
page, nên bảo vệ chỉ áp dụng cho toàn bộ trang, không phân biệt.
„ Chia sẻ: Cho nhiều phần tự trong KGĐC cùng trỏ đến 1 vị
trí trong KGVL
„ Segmentation : chia sẻ mức module chương trình
„ Paging : chia sẻ các trang
Sharing Pages: A Text Editor
Sharing Pages: A Text Editor
ed 3 + 
data 1
ed 3 + 
data 3
ed 3 + 
data 2
Chia sẻ Page 2 = Chia sẻ cả code và data !
Sharing of
Segments: 
Text Editor
12/2/2005 Trần Hạnh Nhi 71
Đánh giá các mô hình chuyển đổi địa chỉ
„Giả sử có: 
„ tm : thời gian truy xuất BNC
„ tc : thời gian truy xuất cache
„ hit-ration : tỉ lệ tìm thấy một số hiệu trang p trong TLB
„ Công thức tính thời gian truy cập thực tế (Time Effective 
Acess) đến một đối tượng trong BNC 
„ bao gồm thời gian chuyển đổi địa chỉ và thời gian truy xuất dữ liệu
„ TEA = (time biding add + time acces memory)
„ Linker-Loader
„ TEA = tm
(data)
„ Base + Bound
„ TEA = (tc+ tc) + tm
(Base & Bound) (data)
„ Segmentation
„ TEA = tc + tm
(ST trong cache) (data)
„ Paging
„ Không sử dụng TLB : 
„ TEA = tm + tm
(PT trong mem) (data)
„ Có sử dụng TLB : 
„ TEA = hit-ratio ( tc + tm ) + (1- hit-ratio)( tc + tm + tm ) 
(TLB) (data) (TLB) (PT) (data)