Bài giảng Nguyên lý hệ điều hành - Đỗ Công Đức - Chương 3: Quản lý bộ nhớ

ay, chỉ nạp những phần cần thiết của 
chương trình vào trong bộ nhớ chính, khi có yêu cầu thì mới nạp 
các modul vào đúng partition của chương trình và sẽ ghi đè lên 
bất kỳ chương trình hoặc dữ liệu ở trong đó
• Thứ hai: chương trình có kích thước nhỏ hơn với partition thì xảy 
ra hiện tượng phân mảnh bên trong bộ nhớ, gây lãng phí bộ nhớ.
Ví dụ: có 3 không gian trống là 30KB nằm rãi rác trên bộ nhớ, khi 
nạp một modul có kích thước 12KB cũng không thực hiện được, 
hiện tượng này gọi là phân mảnh bộ nhớ.
6/28/2014 Chương 3. Quản lý bộ nhớ 26
KỸ THUẬT CẤP PHÁT BỘ NHỚ CHÍNH
3.3.1 Kỹ thuật phân vùng cố định
 Khắc phục điều này sử dụng phân vùng có kích thước không bằng 
nhau bằng cách:
Hệ điều 
hành
New
Process
Hệ điều 
hành
New
Process
6/28/2014 Chương 3. Quản lý bộ nhớ 27
KỸ THUẬT CẤP PHÁT BỘ NHỚ CHÍNH
3.3.1 Kỹ thuật phân vùng cố định
 Mỗi phân vùng có một hàng đợi: khi tiến trình cần nạp vào bộ nhớ
thì nó đưa đến hàng đợi của phân vùng có kích thước vừa đủ với nó 
đưa nó vào hàng đợi
 Hệ thống dùng hàng đợi chung cho tất cả các phân vùng: các tiến 
trình muốn được nạp vào phân vùng nhưng chưa được vào sẽ được 
đưa vào hàng đợi chung. Khi có phân vùng trống, hệ thống sẽ chọn 
một tiến trình có kích thước vừa đủ đưa vào phân vùng trống đó
Hạn chế của phân vùng cố định 
 Số lượng các tiến trình có thể hoạt động trong hệ thống tại một thời 
điểm phụ thuộc vào số lượng các phân vùng cố định trên bộ nhớ
 Kích thước của tiến trình nhỏ hơn kích thước của một phân vùng 
thì phân mảnh nội vi gây lãng phí trong việc sử dụng bộ nhớ
6/28/2014 Chương 3. Quản lý bộ nhớ 28
KỸ THUẬT CẤP PHÁT BỘ NHỚ CHÍNH
3.3.2 Kỹ thuật phân vùng động
 Số lượng các phân vùng trên bộ nhớ và kích thước của mỗi phân 
vùng có thể thay đổi. Phần user program trên bộ nhớ không được 
phân chia trước mà khi có một tiến trình được nạp vào bộ nhớ thì 
HĐH cấp cho nó một không gian vừa đủ để chứa tiến trình, phần 
còn lại để sẵn sàng cấp cho tiến trình khác sau này 
6/28/2014 Chương 3. Quản lý bộ nhớ 29
KỸ THUẬT CẤP PHÁT BỘ NHỚ CHÍNH
3.3.2 Kỹ thuật phân vùng động
 Khi tiến trình yêu cầu thì nó tìm vùng nhớ vừa đủ, nếu phân vùng 
lớn thì một phần được cấp cho tiến trình, phần còn lại tìm và kết 
hợp với các tiến trình khác để tạo thành vùng lớn hơn cấp cho các 
tiến trình có yêu cầu. Điều này làm giảm tốc độ hệ thống, hơn nữa 
khi tiến trình Swap out và phải swap in vào lại để hoạt động
 Kỹ thuật phân vùng động HĐH quản lý các khối nhớ đã cấp phát 
hay còn trống bằng sử dụng sơ đồ bit và danh sách liên kết:
6/28/2014 Chương 3. Quản lý bộ nhớ 30
KỸ THUẬT CẤP PHÁT BỘ NHỚ CHÍNH
3.3.2 Kỹ thuật phân vùng động
 Bảng đồ bit
6/28/2014 Chương 3. Quản lý bộ nhớ 31
KỸ THUẬT CẤP PHÁT BỘ NHỚ CHÍNH
3.3.2 Kỹ thuật phân vùng động
 Danh sách liên kết
H 0 2 P 2 3
H 5 3
P 8 2 H 10 4 P 14 3
H 17 1 P 18 2 20 2
6/28/2014 Chương 3. Quản lý bộ nhớ 32
KỸ THUẬT CẤP PHÁT BỘ NHỚ CHÍNH
3.3.2 Kỹ thuật phân vùng động
 Khi tiến trình cần được nạp vào bộ nhớ thì HĐH phải lựa chọn 
khối nhớ trống phù hợp nạp vào 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 
• Best-fit: duyệt tất cả để chọn khối nhớ có kích thước vừa đúng 
bằng kích thước của tiến trình cần được nạp vào bộ nhớ
• First-fit: duyệt tất cả các khối nhớ trống trong bộ nhớ và sẽ chọn 
khối nhớ trống đầu tiên có kích thước đủ lớn để nạp tiến trình 
• Next-fit: hệ điều hành bắt đầu quét từ khối nhớ trống kế sau khối 
nhớ vừa được cấp phát và chọn khối nhớ trống kế tiếp đủ lớn để
nạp tiến trình 
6/28/2014 Chương 3. Quản lý bộ nhớ 33
KỸ THUẬT CẤP PHÁT BỘ NHỚ CHÍNH
3.3.2 Kỹ thuật phân vùng động
Ví dụ: giả sử có các khối nhớ như hình sau và có 1 tiến trình 16K cần 
được nạp vào bộ nhớ
8k 12k 22k 18k
8k 6k 14k 36k
khối nhớ vừa
được cấp phát
cuối cùng
 Khối nhớ 22k nếu theo thuật toán First-fit, phân mảnh 6k 
 Khối nhớ 18k nếu theo thuật toán Best-fit, phân mảnh 2k 
 Khối nhớ 36k nếu theo thuật toán Next-fit, phân mảnh 20k 
6/28/2014 Chương 3. Quản lý bộ nhớ 34
KỸ THUẬT CẤP PHÁT BỘ NHỚ CHÍNH
3.3.2 Kỹ thuật phân vùng động
 Các HĐH không cài đặt trước một thuật toán nào cả mà tùy vào 
trường hợp mà chọn thuật toán cấp phát sao cho hạn chế sự phân 
mảnh. Chọn thuật toán nào phụ thuộc vào thứ tự swap và kích 
thước của tiến trình.
• First-fit: đơn giản, dễ cài đặt, tốc độ, có hiệu quả cao nhất 
• Next-fit: thường sử dụng được các khối nhớ trống ở cuối vùng 
nhớ thường có kích thước lớn nên, hạn chế được sự phân mảnh 
• Best-fit: hiệu suất thấp vì phải duyệt qua hết tất cả các khối nhớ
trống để tìm khối nhớ có kích thước của tiến trình yêu cầu, giảm 
hiệu suất và chọn khối nhớ vừ đủ nên dẫn đến sự phân mảnh lớn 
vì có nhiều khối nhớ quá nhỏ
6/28/2014 Chương 3. Quản lý bộ nhớ 35
KỸ THUẬT CẤP PHÁT BỘ NHỚ CHÍNH
3.3.2 Kỹ thuật phân vùng động
 Trong công tác cấp phát bộ nhớ, HĐH có thể Swap out một tiến 
trình ra ngoài đĩa để dành chỗ cấp phát cho tiến trình có yêu cầu và 
sau đó swap in vào lại tại thời điểm thích hợp. Khi nạp lại thì có
thể không đúng với phân vùng nạp đầu tiên. Sự thay đổi này làm 
ảnh hưởng đến việc truy xuất dữ liệu khi một tiến trình được nạp 
vào bộ nhớ lần đầu tiên
 Ví dụ chương trình có code truy xuất tại địa chỉ 100K, nếu được 
nạp vào phân vùng 1 có đị chỉ 100k thì truy xuất là 200K, nếu nạp 
tại phân vùng 2 có địa chỉ 200k thì truy xuất 300k. Để giải quyết 
vấn đề này HĐH phải thực hiện công tác tái định vị tiến trình vào 
bộ nhớ nhưng trách việc truy xuất đến vùng nhớ của tiến trình khác
6/28/2014 Chương 3. Quản lý bộ nhớ 36
KỸ THUẬT CẤP PHÁT BỘ NHỚ CHÍNH
3.3.2 Kỹ thuật phân vùng động
 Sử dụng 2 thanh ghi đặc biệt
• Thanh ghi cơ sở (base register): dùng để ghi địa chỉ cơ sở của 
tiến trình tiến trình được nạp vào bộ nhớ
• Thanh ghi giới hạn (limit register): dùng để ghi địa chỉ cuối 
cùng của tiến trình trong bộ nhớ
 Việc thiết lập giá trị của các thanh ghi này được thực hiện cả khi 
tiến trình lần đầu tiên được nạp và swap in vào lại bộ nhớ
• Thứ nhất: cộng địa chỉ ô nhớ với giá trị địa chỉ trong thanh ghi 
cơ sở để có được địa chỉ tuyệt đối của ô nhớ cần truy xuất 
• Địa chỉ được so sánh với thanh ghi giới hạn: nếu nằm trong giới 
hạn cho truy xuất, ngược lại thì ngát lỗi truy xuất bộ nhớ
6/28/2014 Chương 3. Quản lý bộ nhớ 37
KỸ THUẬT CẤP PHÁT BỘ NHỚ CHÍNH
3.3.2 Kỹ thuật phân vùng động
• Hạn chế của kỹ thuật này là phân mảnh bộ nhớ và lãng phí bộ
nhớ. Để khắc phục HĐH sử dụng phân trang/phân đoạn
Địa chỉ tương đối
Base Register
Limit Register
Cộng
Stack
Điều khiển
tiến trình
So sánh
Program
Data
Gởi ngắt đến hệ
điều hành Tiến trình trong 
bộ nhớ
<
6/28/2014 Chương 3. Quản lý bộ nhớ 38
KỸ THUẬT CẤP PHÁT BỘ NHỚ CHÍNH
3.3.3 Kỹ thuật phân trang đơn
6/28/2014 Chương 3. Quản lý bộ nhớ 39
KỸ THUẬT CẤP PHÁT BỘ NHỚ CHÍNH
3.3.4 Kỹ thuật phân đoạn đơn
6/28/2014 Chương 3. Quản lý bộ nhớ 40
KỸ THUẬT BỘ NHỚ ẢO
3.4.1 Bộ nhớ ảo
 Kỹ thuật bộ nhớ ảo là kỹ thuật hiện đại giải quyết sự giới hạn bộ
nhớ chính của máy tính
 Kỹ thuật cấp phát bộ nhớ phân trang/phân đoạn có đặc điểm:
• Địa chỉ tham chiếu trong một phạm vi tiến trình là địa chỉ logíc 
và được chuyển thành địa chỉ vật lý một cách tự động tại thời 
điểm chạy của tiến trình. Như vậy một tiến trình swap out và
swap in lại không cần phải đúng địa chỉ đã swap out
• Một tiến trình có thể chia thành nhiều trang/đoạn khác nhau và
có thể nạp vào các vị trí liên tục trong bộ nhớ trong quá trình 
thực hiện tiến trình
6/28/2014 Chương 3. Quản lý bộ nhớ 41
KỸ THUẬT BỘ NHỚ ẢO
3.4.1 Bộ nhớ ảo
 Kỹ thuật này khắc phục được hạn chế của phân vùng cố định, phân 
vùng động nhưng còn hạn chế là phải nạp tất cả các trang/đoạn vào 
bộ nhớ vì thế kích thước chương trình ngày càng lớn 
 Khắc phục hạn chế này kỹ thuật bộ nhớ ảo ra đời nó vẫn dựa vào 
kỹ thuật phân trang/đoạn nhưng
• Bộ nhớ ảo không nạp tất cả các trang/đoạn vào bộ nhớ mà chỉ
nạp những trang/đoạn cần thiết. Khi cần bộ nhớ ảo dựa vào 
bảng PCT, SCT để nạp trang tiếp theo
• Nếu nạp mà không còn trang/đoạn trống thì bộ phận quản lý bộ
nhớ đưa các trang/đoạn swap out ra ngoài để lấy không gian nạp 
bộ nhớ cho các tiến trình khác yêu cầu. Các tiến trình bị swap 
out sẽ swap in vào thời điểm thích hợp 
6/28/2014 Chương 3. Quản lý bộ nhớ 42
KỸ THUẬT BỘ NHỚ ẢO
3.4.1 Bộ nhớ ảo
 Để cài đặt bộ nhớ ảo thì HĐH phải
• Không gian bộ nhớ phụ cần thiết chứa các trang/đoạn không 
gian để swap out, không gian đĩa này gọi là không gian swap
• Theo dõi không gian các trang/đoạn nằm trên bộ nhớ chính/phụ
bằng một bít present vào PCT, SCT
• Dựa vào tiêu chuẩn để lựa chọn một trang/đoạn nào đó trên bộ
nhớ chính swap out ra ngoài đĩa
6/28/2014 Chương 3. Quản lý bộ nhớ 43
KỸ THUẬT BỘ NHỚ ẢO
3.4.1 Bộ nhớ ảo
 Việc sử dụng bộ nhớ ảo có một số một số lợi ích sau:
• Nạp được nhiều tiến trình vào bộ nhớ hơn vì bộ phận quản lý bộ
nhớ không nạp tất cả vào bộ nhớ
• Có thể nạp vào bộ nhớ một tiến trình có không gian lớn hơn bộ
nhớ vật lý với thiết kế chương trình cấu trúc Overlay nhờ có sự
hỗ trợ của HĐH và phần cứng.
• Không cần nạp tất cả các tiến trình vào bộ nhớ mà chỉ nạp một 
phần hoặc chỉ nạp vào bộ nhớ các chỉ thị và dữ liệu của chương 
trình cần thiết cho việc thi hành lệnh ở tại thời điểm đó.
• Người sử dụng làm việc với địa chỉ ảo còn việc chuyển đổi sang 
địa chỉ vật lý do HĐH đảm nhiệm bằng cơ chế phần cứng
6/28/2014 Chương 3. Quản lý bộ nhớ 44
KỸ THUẬT BỘ NHỚ ẢO
3.4.2 Cài đặt bộ nhớ ảo
6/28/2014 Chương 3. Quản lý bộ nhớ 45
CÁC THUẬT TOÁN THAY TRANG
3.5.1 Thuật toán FIFO
6/28/2014 Chương 3. Quản lý bộ nhớ 46
CÁC THUẬT TOÁN THAY TRANG
3.5.2 Thuật toán LRU
6/28/2014 Chương 3. Quản lý bộ nhớ 47
CÁC THUẬT TOÁN THAY TRANG
3.5.3 Thuật toán Optional
6/28/2014 Chương 3. Quản lý bộ nhớ 48
CẤP PHÁT KHUNG TRANG
3.5.3 Thuật toán Optional
6/28/2014 Chương 3. Quản lý bộ nhớ 49
TỔNG KẾT
Trong chương này, chúng ta đã học:
6/28/2014 Chương 3. Quản lý bộ nhớ 50
CÂU HỎI VÀ BÀI TẬP VỀ NHÀ