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

 cầu 18,462 bytes.
 Hiện tượng phân mảnh nội thường xảy ra khi bộ nhớ thực
được chia thành các khối kích thước cố định (fixed-sized
block) và các process được cấp phát theo đơn vị khối. Ví
dụ: cơ chế phân trang (paging).
20
Phân mảnh nội
operating
system
(used)
yêu cầu kế tiếp là
18,462 bytes !!!
hole kích thước
18,464 bytes
cần quản lý khoảng 
trống 2 bytes !?!
OS sẽ cấp phát hẳn khối 18,464 bytes 
cho process  dư ra 2 bytes không dùng!
21
Phân cấp bộ nhớ
22
– Là nguyên tắc quan trọng của hệ thống máy
tính.
– Thông tin từ RAM có thể được cơ chế phần
cứng đưa vào bộ nhớ nhanh hơn gọi là Cache.
Khi CPU cần chính thông tin đó, không cần phải
truy xuất RAM, mà lấy ngay từ Cache.
– Loại bộ nhớ này không do HĐH quản lý và cấp
phát.
– Thực tế, RAM (Bộ nhớ Sơ cấp) là loại Cache
nhanh so với đĩa cứng (Bộ nhớ thứ cấp) và HĐH
có chức năng quản lý sự lưu chuyển dữ liệu
giữa 2 loại bộ nhớ
NGUYÊN TẮC LƯU GẦN (CACHING)
23
2. KỸ THUẬT CẤP PHÁT BỘ NHỚ
25
 Kỹ thuật phân vùng cố định (Fixed partitioning)
 Kỹ thuật phân vùng động (Dynamic partitioning)
 Kỹ thuật phân trang (Paging)
 Kỹ thuật phân đoạn (Segmentation)
2.1 Kỹ thuật phân vùng cố định
 Khơng gian địa chỉ được chia thành 2 vùng cố
định
 Vùng địa chỉ thấp dùng để chứa HĐH
 Vùng cịn lại cấp cho các tiến trình được nạp vào
bộ nhớ chính (user program) 
26
2.1 Kỹ thuật phân vùng cố định
 Với hệ thống đơn chương:
 Việc quản lý bộ nhớ đơn giản vì vùng nhớ user program
chỉ cấp cho 1 chương trình
 HĐH sử dụng 1 thanh ghi giới hạn để ghi địa chỉ ranh
giới giữa HĐH và chương trình người sử dụng
 Khi chương trình người sử dụng đưa ra địa chỉ cần truy
xuất, HĐH sẽ so sánh với giá trị giới hạn được ghi trong
thanh ghi giới hạn
 Nếu nhỏ hơn giá trị giới hạn thì HĐH từ chối việc truy suất
 Ngược lại, nếu lớn hơn sẽ cho phép truy xuất
=> Nhiệm vụ quản lý sẽ trở nên đơn giản
27
2.1 Kỹ thuật phân vùng cố định
 Với hệ thống đa chương:
 Vùng nhớ user program được chia n phần khơng nhất thiết
phải bằng nhau. Mỗi phần được được gọi là 1 phân vùng
 Mỗi tiến trình cĩ thể được nạp vào 1 phân vùng bất kỳ nếu
kích thước của nĩ <= kích thước của phân vùng và phân
vùng này cịn trống
 Khi cĩ tiến trình cần được nạp vào bộ nhớ mà khơng cịn
phân vùng trống thí HĐH sẽ swap-out 1 tiến trình tại 1 phân
vùng nào đĩ cĩ kích thước vừa đủ, khơng chứa tiến trình
đang ở trạng thái ready hoặc running và khơng cĩ quan hệ
với tiến trình đang ở trạng thái running khác để nạp tiến
trình vừa cĩ yêu cầu
28
2.1 Kỹ thuật phân vùng cố định
(8M)
(8M)
(8M)
(8M)
(8M)
(8M)
(8M)
OS (8M)
2M
4M
6M
8M
8M
12M
16M
OS(8M)
Phân vùng kích thước bằng nhau Phân vùng kích thước khơng bằng nhau
Ví dụ về phân vùng cố định của bộ nhớ 64MByte
29
2.1 Kỹ thuật phân vùng cố định
 Cĩ 2 khĩ khăn với việc dùng phân vùng cố định cĩ
kích thước bằng nhau
 Thứ 1: Nếu chương trình cĩ kích thước quá lớn so với
1 kích thước của phân vùng, để giải quyết việc này thì:
 Người lập trình phải thiết kế chương trình theo cấu
trúc overlay
 Chỉ 1 phần cần thiết của chương trình mới được nạp
vào bộ nhớ lúc nạp chương trình. Khi cần mudun nào
đĩ mà khơng sẵn cĩ trong bộ nhớ người sử dụng phải
nạp nĩ vào đúng phân vùng của chương trình và sẽ
ghi đè lên bất kỳ chương trình hoặc dữ liệu ở trong đĩ
30
2.1 Kỹ thuật phân vùng cố định
 Thứ 2: Khi kích thước của chương trình nhỏ hơn
kích thước của 1 phân vùng hoặc lớn hơn kích
thước của phân vùng nhưng khơng phải là bội
số của kích thước phân vùng.
Điều này gây ra sự phân mảnh nội vi, lãng phí
bộ nhớ
31
2.1 Kỹ thuật phân vùng cố định
 Để khắc phục nhược điểm này cĩ thể sử dụng
phân vùng cố định cĩ kích thước khơng bằng
nhau
 Cĩ 2 lựa chọn để đưa tiến trình vào dạng phân
vùng này
32
2.1 Kỹ thuật phân vùng cố định
 Lựa chọn 1:
 Mỗi phân vùng cĩ một hàng
đợi tương ứng
 Khi 1 tiến trình cần được nạp
vào bộ nhớ sẽ đưa vào hàng
đợi của phân vùng cĩ kích
thước vừa đủ để chứa nĩ để
được đưa vào phân vùng
 Nhược điểm: Cĩ thể cĩ phân
vùng đang trống nhưng lại cĩ
nhiều tiến trình đang chờ để
vào phân vùng khác
OS
Tiến trình
mới
33
2.1 Kỹ thuật phân vùng cố định
 Lựa chọn 2:
 Dùng 1 hàng đời chung cho
tất cả các phân vùng
 Khi cĩ tiến trình muốn nạp
vào bộ nhớ nhưng chưa
được nạp sẽ được đưa vào
hàng đợi
 Khi cĩ phân vùng trống,
HĐH sẽ chọn tiến trình cĩ
kích thước vừa đủ để đưa
vào phân vùng
 Phương pháp này gây khĩ
khăn trong việc lựa chọn tiến
trình để nạp vào phân vùng
OS
Tiến trình
mới
34
2.2 Kỹ thuật phân vùng động
 Vùng nhớ user program khơng được phân chia
trước
 Khi cĩ tiến trình nạp vào bộ nhớ HĐH cấp cho
nĩ khơng gian nhớ đúng kích thước của nĩ
 Khi tiến trình kết thúc vùng nhớ của nĩ sẽ được
thu hồi để HĐH cấp cho tiến trình khác kể cả tiến
trình mới cĩ kích thước nhỏ hơn vùng nhớ của
tiến trình đã giải phĩng đã giải phĩng
35
2.2 Kỹ thuật phân vùng động
OS- 128k
Process1
64k
Process2
128k
Process3
32k
Process4
128k
Process5
120kProcess6
65k
1. Tiến trình 1,2,3,4 lần lượt được
nạp vào bộ nhớ
2. Tiến trình 2 kết thúc, vùng nhớ
được giải phĩng
3. Tiến trình 5 được nạp vào vùng
nhớ của tiến trình
2 vừa giải phĩng
4. Tiến trình 6 yêu cầu được nạp vào
bộ nhớ nhưng khơng thể vì khơng
cĩ vùng nhớ trống phù hợp để
nạp trong khi tổng dung lượng
nhớ cịn trống lớn hơn kích thước
mà tiến trình yêu cầu
36
2.2 Kỹ thuật phân vùng động
 Trong kỹ thuật phân vùng động, HĐH phải đưa ra các
cơ chế thích hợp để quản lý các khối nhớ đã cấp phát
hay cịn trống trên bộ nhớ.
 HĐH sử dụng 2 cơ chế: Bản đồ bít và Danh sách liên
kết.
 Hai cơ chế HĐH đều chia khơng gian nhớ thành các
đơn vị cấp phát cĩ kích thước bằng nhau, các đơn vị
cấp phát liên tiếp nhau tạo thành 1 khối nhớ, HĐH
cấp phát các khối nhớ này cho các tiến trình
37
2.2 Kỹ thuật phân vùng động
Cơ chế bản đồ Bit: Mỗi đơn vị cấp phát được đại
diện bởi một Bit trong bản đồ bit. Đơn vị cấp phát
cịn trống đại diện bằng bit 0, ngược lại đại diện
bằng bit 1.
Bản đồ bit
38
2.2 Kỹ thuật phân vùng động
 Cơ chế danh sách liên kết:
 Mỗi khối trên bộ nhớ được đại diện bởi một phần tử
trong danh sách liên kết
Mỗi phần tử gồm 4 trường chính:
 Trường đầu tiên: cho biết khối nhớ đã cấp phát (kí
hiệu P) hay cịn trống (kí hiệu H)
 Trường thứ 2: cho biết thư tự của đơn vị cấp phát
đầu tiên trong khối
 Trường thứ 3: cho biết đơn vị tổng số đơn vị cấp
phát trong khối
 Con trỏ Next
39
2.2 Kỹ thuật phân vùng động
40
2.2 Kỹ thuật phân vùng động
 Khi cĩ một tiến trình cần được nạp vào bộ nhớ mà
bộ nhớ cĩ nhiều hơn một khối nhớ trống cĩ kích
thước lớn hơn kích thước của tiến trình đĩ, HĐH
phải quyết định chọn một khối nhớ phù hợp để nạp
tiến trình sao cho việc lựa chọn này dẫn đến việc sử
dụng bộ nhớ chính là hiệu quả nhất.
Thuật tốn mà HĐH sử dụng trong trường hợp này:
Best-fit, Worst-fit, First-fit, và Next-fit
41
42
Dùng để quyết định cấp
phát khối bộ nhớ trống
nào cho một process
Mục tiêu: giảm chi phí
compaction
Các chiến lược placement
Best-fit: chọn khối nhớ trống
nhỏ nhất
First-fit: chọn khối nhớ trống
phù hợp đầu tiên kể từ đầu
bộ nhớ
Next-fit: chọn khối nhớ trống
phù hợp đầu tiên kể từ vị trí
cấp phát cuối cùng
Worst-fit: chọn khối nhớ
trống lớn nhất
Bộ nhớ chính được chia thành các phần bằng
nhau và cố định, được đánh số bắt đầu từ 0 và
được gọi là các khung trang (page frame).
Khơng gian địa chỉ của các tiến trình cũng được
chia thành các phần cĩ kích thước bằng kích
thước của một khung trang được gọi là các trang
(page).
Khi tiến trình nạp vào bộ nhớ thì các trang được
nạp vào các khung trang bất kỳ cịn trống cĩ thể
khơng liên tiếp nhau.
2.3 Kỹ thuật phân trang
Cơ chế MMU trong kỹ thuật phân trang
44
Cơ chế phần cứng hỗ trợ thực hiện chuyển đổi địa
chỉ trong cơ chế phân trang là bảng trang (pages
table). Mỗi phần tử trong bảng trang cho biết các địa
chỉ bắt đầu của vị trí lưu trữ trang tương ứng trong
bộ nhớ vật lý (số hiệu khung trang trong bộ nhớ vật
lý đang chứa trang ). Mỗi tiến trình cĩ bảng trang
riêng
Chuyển đổi địa chỉ
45
Mỗi địa chỉ phát sinh bởi CPU được chia thành hai
phần:
 số hiệu trang - Page number (p): sử dụng như chỉ
mục đến phần tử tương ứng trong bảng trang.
 địa chỉ tương đối trong trang - Page offset (d): kết hợp
với địa chỉ bắt đầu của trang để tạo ra địa chỉ vật lý mà
trình quản lý bộ nhớ sử dụng.
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à 2
n
(đơn vị là byte hay word tùy theo
kiến trúc máy) thì
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 phân trang sẽ có tổng cộng 2
m
/2
n
= 2
m  n
mục (entry)
2.3 Kỹ thuật phân trang
CPU p d f d
f
p
page table
logical
address 
physical
address 
physical
memory
f 0000
f 1111
f frames
46
VD
47
Tổ chức lưu trữ bảng trang:
48
Đa số các hệ điều hành cấp cho mỗi tiến trình 
một bảng trang.
Nếu hệ điều hành quản lý một khơng gian địa chỉ 
cĩ dung lượng quá thì bảng trang địi hỏi một 
vùng nhớ qúa lớn
=> Giải pháp: Phân trang đa cấp.
49
Phân trang đa cấp
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ệ.
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.
 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
Chia sẻ bộ nhớ trong cơ chế phân trang
52
Cho phép chia sẻ các trang giữa các tiến trình ánh
xạ nhiều địa chỉ logic vào một địa chỉ vật lý duy nhất.
HĐH kiểm tra các thao tác truy xuất trên khung trang
tương ứng cĩ hợp lệ với thuộc tính bảo vệ của nĩ
khơng.
53
 Loại bỏ được hiện tượng phân mảnh ngoại vi nhưng vẫn
cịn hiện tượng nội vi Nếu kích thước của tiến trình khơng
phải là bội số của kích thước 1 khung trang.
Cĩ sự phân biệt rạch rịi giữa gĩc nhìn của người
dùng và bộ phận quản lý bộ nhớ:
Gĩc nhìn của người sử dụng: Tiến trình của người dùng
nhìn bộ nhớ như là một khơng gian liên tục, đồng nhất
và chỉ chứa duy nhất bản thân tiến trình này.
Gĩc nhìn của bộ nhớ vật lý: Tiến trình của người sử
dụng được lưu trữ phân tán khắp bộ nhớ, trong bộ nhớ
đồng thời cũng chứa những tiến trình khác.
Phần cứng đảm nhiệm việc chuyển đổi địa chỉ logic
thành địa chỉ vật lý. Sự chuyển đổi này là trong suốt
đối với người sử dụng.
2.4 Kỹ thuật phân đoạn
 Bộ nhớ chính được chia thành các phần cố định
cĩ kích thước khơng bằng nhau, được đánh số bắt
đầu từ 0 được gọi là các phân đoạn
 Khơng gian địa chỉ là một tập các phân đoạn
(segments).
 Các phân đoạn là những phần bộ nhớ kích thước
khác nhau và cĩ liên hệ logic với nhau. Mỗi phân
đoạn cĩ một tên gọi (số hiệu phân đoạn) và một độ
dài.
 Người dùng sẽ thiết lập mỗi địa chỉ với hai giá trị:
.
54
55
Cơ chế MMU trong kỹ thuật phân đoạn
56
 Cần phải xây dựng một ánh xạ để chuyển đổi các
địa chỉ 2 chiều được người dùng định nghĩa
thành địa chỉ vật lý một chiều. Sự chuyển đổi
này được thực hiện qua một bảng phân đoạn.
 Mỗi thành phần trong bảng phân đoạn bao gồm
một thanh ghi nền và một thanh ghi giới hạn:
 Thanh ghi nền lưu trữ địa chỉ vật lý nơi bắt đầu phân
đoạn trong bộ nhớ
 Thanh ghi giới hạn đặc tả chiều dài của phân đoạn.
2.4 Kỹ thuật phân đoạn
Chuyển đổi địa chỉ:
 Mỗi địa chỉ ảo là một bộ 
 Số hiệu phân đoạn s : được sử dụng như chỉ mục đến
bảng phân đoạn (địa chỉ cơ sở của phân đoạn mà
đoạn chương trình tương ứng được nạp)
 địa chỉ tương đối d : cĩ giá trị trong khoảng từ 0 đến
giới hạn chiều dài của phân đoạn. Nếu địa chỉ
tương đối hợp lệ, nĩ sẽ được cộng với giá trị chứa
trong thanh ghi nền để phát sinh địa chỉ vật lý tương
ứng (cho biết độ dài của phân đoạn)
57
58
9.59
VD
Chia sẻ phân đoạn
60
 Một ưu điểm khác của kỹ thuật phân đoạn là khả
năng chia sẻ ở mức độ phân đoạn. Nhờ khả năng
này, các tiến trình cĩ thể chia sẻ với nhau từng
phần chương trình (ví dụ các thủ tục, hàm), khơng
nhất thiết phải chia sẻ tồn bộ chương trình như
trường hợp phân trang
 Mỗi tiến trình cĩ một bảng phân đoạn riêng, một
phân đoạn được chia sẻ khi các phần tử trong
bảng phân đoạn của hai tiến trình khác nhau cùng
chỉ đến một vị trí vật lý duy nhất
Chia sẻ code trong hệ phân đoạn
61
2.4 Kỹ thuật phân đoạn
 Khi tiến trình được nạp vào bộ nhớ thì tất cả các
đoạn của nĩ được nạp vào các phân đoạn cịn trống
trên bộ nhớ, các phân đoạn này cĩ thể khơng liên tục
nhau
 Để theo dõi các đoạn của các tiến trình khác nhau
trên bộ nhớ HĐH sử dụng các bảng phân đoạn
(SCT), thơng thường mỗi tiến trình cĩ 1 bảng phân
đoạn riêng
62
63
Trong hệ thống sử dụng kỹ thuật phân đoạn , hiện
tượng phân mảnh ngoại vi lại xuất hiện khi các khối
nhớ tự do đều quá nhỏ, khơng đủ để chứa một
phân đoạn.
Tường minh với người sử dụng, cung cấp một sự
thuận lợi để người lập trình tổ chức chương trình
và dữ liệu.
Kỹ thuật này cũng phải giải quyết vấn đề cấp phát
động
Kỹ thuật phân đoạn phải cấp phát các khối nhớ cĩ
kích thước khác nhau cho các phân đoạn trên bộ
nhớ vật lý kết hợp phân trang với phân đoạn.
2.5. Phân đoạn kết hợp phân trang 
(Paged segmentation)
64
Khơng gian địa chỉ là một tập các phân đoạn, mỗi
phân đoạn được chia thành nhiều trang. Khi một tiến
trình được đưa vào hệ thống, hệ điều hành sẽ cấp
phát cho tiến trình các trang cần thiết để chứa đủ
các phân đoạn của tiến trình.
Cơ chế MMU trong kỹ thuật phân đoạn kết 
hợp phân trang
65
Khơng gian địa chỉ là một tập các phân đoạn, mỗi
phân đoạn được chia thành nhiều trang.
Khi một tiến trình được đưa vào hệ thống, hệ điều
hành sẽ cấp phát cho tiến trình các trang cần thiết
để chứa đủ các phân đoạn của tiến trình.
Cơ chế MMU: Để hỗ trợ kỹ thuật phân đoạn, cần cĩ
một bảng phân đoạn, nhưng giờ đây mỗi phân
đoạn cần cĩ một bảng trang phân biệt.
Chuyển đổi địa chỉ
66
Mỗi địa chỉ logic là một bộ ba: 
 số hiệu phân đoạn (s): sử dụng như chỉ
mục đến phần tử tương ứng trong bảng phân
đoạn.
 số hiệu trang (p): sử dụng như chỉ mục đến
phần tử tương ứng trong bảng trang của
phânđoạn.
 địa chỉ tương đối trong trang (d): kết hợp với
địa chỉ bắt đầu của trang để tạo ra địa chỉ vật
lý mà trình quản lý bộ nhớ sử dụng.
Mơ hình phân đoạn kế hợp phân trang
67
68
Tĩm tắt
69
 Cĩ nhiều cách tiếp cận khác nhau để tổ chức quãn lý bộ nhớ, nhưng
tựu chung mong đạt đến các mục tiêu sau :
 Cĩ thể đáp ứng được đầy đủ các nhu cầu bộ nhớ của chương trình
với một bộ nhớ vật lý giới hạn
 Quá trình chuyển đổi địa chỉ, tổ chức cấp phát bộ nhớ là trong suốt
với người dùng, và cĩ khả năng tái định vị.
 Tận dụng hiệu quả bộ nhớ ( ít cĩ vùng nhớ khơng sử dụng được)
 Bộ nhớ được bảo vệ tốt
 Cĩ khả năng chia sẻ bộ nhớ giữa các tiến trình
 Một số cách tiếp cận tổ chức bộ nhớ chính
 Cấp phát liên tục : cĩ thể cấp phát các vùng nhớ liên tục cho các tiến
trình trong những phân vùng cĩ kích thước cố định hay biến động.
Điểm yếu của cách tiếp cận này là kích thước các chương trình cĩ thể
dược xử lý bị giới hạn bởi các kích thước của khối nhớ liên tục cĩ thể
sử dụng. Các hiện tượng phân mảnh ngoại vi, nội vi đều cĩ thể xuất
hiện
 Cấp phát khơng liên tục : cĩ thể cấp phát các vùng nhớ khơng liên tục
cho một tiến trình. Hai kỹ thuật thường được áp dụng là phân trang và
phân đoạn. Kỹ thuật phân trang cho phép loại bõ hiện tượng phân
mảnh ngoại vi, kỹ thuật phân đoạn loại bỏ hiện tượng phân mảnh nội
vi, nhưng phải giải quyết vấn đề cấp phát động.
3. KỸ THUẬT BỘ NHỚ ẢO
3.1 Khái niệm nhớ ảo (virtual memory)
 Để thực thi chương trình cĩ kích thước lớn hơn bộ
nhớ vật lý cấp phát cho nĩ
 cần xây dựng chương trình theo cấu trúc Overlay gây
khĩ khăn cho người lập trình
 Để khắc phục khĩ khăn cho người lập trình, ý
tưởng sử dụng bộ nhớ ảo ra đời
 Kỹ thuật bộ nhớ ảo cho phép xử lý một tiến trình
khơng được nạp tồn bộ vào bộ nhớ vật lý
71
Bộ nhớ ảo là một kỹ thuật hiện đại giúp cho người 
dùng được giải phĩng hồn tồn khỏi mối bận tâm 
về giới hạn bộ nhớ
3.1 Khái niệm nhớ ảo
 Bộ nhớ ảo mơ hình hố bộ nhớ như một bảng
lưu trữ rất lớn và đồng nhất, tách biệt hẳn khái
niệm khơng gian địa chỉ và khơng gian vật lý
Người sử dụng chỉ nhìn thấy và làm việc trong
khơng gian địa chỉ ảo, chuyển đổi sang khơng
gian vật lý do hệ điều hành thực hiện với sự trợ
giúp của các cơ chế phần cứng
72
3.2 Cài đặt bộ nhớ ảo
Cĩ thể cài đặt bộ nhớ ảo theo 2 kỹ thuật
 Phân trang theo yêu cầu (demand paging): Sử dụng
kỹ thuật phân trang kết hợp với kỹ thuật swap
 Phân đoạn theo yêu cầu: sử dụng kỹ thuật phân đoạn
kết hợp với kỹ thuật swap
73
3.2.1 Phân trang theo yêu cầu
Sử dụng kỹ thuật phân trang kết hợp với kỹ thuật
swap
Một chương trình được xem như 1 tập hợp các trang
thường trú trên bộ nhớ ngồi
Khi thực thi hệ thống khơng nạp tồn bộ chương
trình vào bộ nhớ trong mà chỉ nạp những trang cần
thiết trong thời điểm hiện tại
 Một trang chỉ được nạp vào bộ nhớ trong khi cần thiết
74
3.2.1 Phân trang theo yêu cầu
Với mơ hình này, cần cung cấp một cơ chế phần
cứng giúp phân biệt các trang đang ở trong bộ nhớ
chính và các trang trên đĩa. Cĩ thể sử dụng lại
bit valid-invalid nhưng với ngữ nghĩa mới:
 valid : trang tương ứng là hợp lệ và đang ở trong bộ
nhớ chính .
 invalid : hoặc trang bất hợp lệ (khơng thuộc về khơng
gian địa chỉ của tiến trình) hoặc trang hợp lệ
nhưng đang được lưu trên bộ nhớ phụ.
Một phần tử trong bảng trang mộ tả cho một trang
khơng nằm trong bộ nhớ chính, sẽ được đánh dấu
invalid và chứa địa chỉ của trang trên bộ nhớ phụ.
75
Cơ chế phần cứng
76
Cơ chế phần cứng hỗ trợ kỹ thuật phân trang theo
yêu cầu là sự kết hợp của cơ chế hỗ trợ kỹ thuật
phân trang và kỹ thuật swapping:
 Bảng trang: Cấu trúc bảng trang phải cho phép phản
ánh tình trạng của một trang là đang nằm trong bộ nhớ
chính hay bộ nhớ phụ.
 Bộ nhớ phụ: Bộ nhớ phụ lưu trữ những trang
khơng được nạp vào bộ nhớ chính. Bộ nhớ phụ
thường được sử dụng là đĩa, và vùng khơng gian đĩa
dùng để lưu trữ tạm các trang trong kỹ thuật
swapping được gọi là khơng gian swapping.
Thay thế trang
Thuật tốn thay thế trang: Thuật tốn lựa một trang
“nạn nhân” để chuyển ra bộ nhớ phụ với chung một
mục tiêu: Chọn trang “nạn nhân” là trang mà sau khi
thay thế sẽ gây ra ít lỗi trang nhất.
Chúng ta đánh giá một giải thuật bằng cách chạy nĩ
trên một chuỗi các tham chiếu bộ nhớ cụ thể và tính
số lượng lỗi trang.
 Giải thuật thay thế tối ưu.
 Giải thuật thay thế NRU (Not-Recently-Used).
 Giải thuật thay thế FIFO.
 Giải thuật thay thế Second Chance.
 Giải thuật thay thế vịng trịn.
 Giải thuật thay thế LRU (Least Recently Used).
77
3.2.2 Phân đoạn đoạn theo yêu cầu
Bộ nhớ ảo bao gồm các đoạn (segment)
cĩ kích thuớc khơng cố định
Khi nạp đoạn vào bộ nhớ thì hệ điều
hành tìm khoảng trống đủ để nạp đoạn
Cĩ bảng đoạn quản lý các đoạn
78
3.2.3 Phân đoạn kết hợp phân trang
 Kết hợp các ưu điểm của phân đoạn và
phân trang
 Bộ nhớ ảo bao gồm các đoạn
 Trong mỗi đoạn thực hiện phân trang
79