Giáo trình Hệ điều hành - Chương 2: Quản lý bộ nhớ

k và đ−a lên đầu stack. 
 - trang ở đỉnh stack là trang đ−ợc truy xuất gần nhất, và trang ở đáy stack là 
trang lâu nhất ch−a đ−ợc sử dụng. 
Ví dụ : 
 33
Một ch−ơng trình có kích th−ớc 7 trang, đ−ợc hệ điều hành cấp phát cho 5 
khung trang. Chuỗi truy xuất : 
4 7 0 7 1 0 1 2 1 2 7 1 2 
Ví dụ 2 : Một ch−ơng trình có kích th−ớc 5 trang, đ−ợc OS cung cấp cho 4 
khung trang. Chuỗi (thứ tự) truy xuất đến các trang nh− sau : 
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 
Kết quả : 
Nhìn vào hình ta thấy có 8 lỗi trang ( PF ) 
4. Các thuật toán xấp xỉ LRU 
Có ít hệ thống đ−ợc cung cấp đủ các hỗ trợ phần cứng để cài đặt đ−ợc thuật 
toán LRU thật sự. Tuy nhiên, nhiều hệ thống đ−ợc trang bị thêm một bit tham khảo 
(reference): 
- một bit reference, đ−ợc khởi gán là 0, đ−ợc gắn với một phần tử trong bảng 
trang. 
- bit reference của một trang đ−ợc phần cứng đặt giá trị 1 mỗi lần trang t−ơng 
ứng đ−ợc truy cập, và đ−ợc phần cứng gán trở về 0 sau từng chu kỳ qui định tr−ớc. 
Sau từng chu kỳ qui định tr−ớc, kiểm tra giá trị của các bit reference, có thể 
xác định đ−ợc trang nào đã đ−ợc truy xuất đến và trang nào không, sau khi đã kiểm 
tra xong, các bit reference đ−ợc phần cứng gán trở về 0 . 
Với bit reference, có thể biết đ−ợc trang nào đã đ−ợc truy xuất, nh−ng không 
biết đ−ợc thứ tự truy xuất. Thông tin không đầy đủ này dẫn đến nhiều thuật toán 
xấp xỉ LRU khác nhau. 
- số hiệu trang 
- bit valid-invalid 
- dirty bit 
- bit reference 
 34
 Số hiệu trang Invalid-Valid Bit Dirty bit Referenebit 
Hình 2.28 Cấu trúc một phần tử trong bảng trang 
a. Thuật toán với các bit reference phụ trợ 
 Ta có thể thu thập thêm nhiều thông tin về thứ tự truy xuất hơn bằng cách l−u 
trữ các bit references sau từng khoảng thời gian đều đặn: 
- Với mỗi trang, sử dụng thêm 8 bit lịch sử (history)trong bảng trang 
- Sau từng khoảng thời gian nhất định (th−ờng là 100 millisecondes), một ngắt 
đồng hồ đ−ợc phát sinh, và quyền điều khiển đ−ợc chuyển cho hệ điều hành. Hệ 
điều hành đặt bit reference của mỗi trang vào bit cao nhất trong 8 bit phụ trợ 
củatrang đó bằng cách đẩy các bit khác sang phải 1 vị trí, bỏ luôn bit thấp nhất. 
 Nh− vậy 8 bit thêm vào này sẽ l− u trữ tình hình truy xuất đến trang trong 8 
chu kỳ cuối cùng. 
 Nếu giá trị của 8 bit là 00000000, thì trang t−ơng ứng đã không đ−ợc dùng 
đến suốt 8 chu kỳ cuối cùng, ng−ợc lại nếu nó đ−ợc dùng đến ít nhất 1 lần trong 
mỗi chu kỳ, thì 8 bit phụ trợ sẽ là 11111111. Một trang mà 8 bit phụ trợ có giá 
trị11000100 sẽ đ−ợc truy xuất gần thời điểm hiện tại hơn trang có 8 bit phụ trợ là 
01110111. 
 Nếu xét 8 bit phụ trợ này nh− một số nguyên không dấu, thì trang LRU là 
trang có số phụ trợ nhỏ nhất. Số l−ợng các bit lịch sử có thể thay đổi tùy theo phần 
cứng, và phải đ−ợc chọn sao cho việc cập nhật là nhanh nhất có thể. 
Ví dụ : 
1
0 1 0 0 1 0 0 1
0
0 1 0 0 1 0 01
reference bit
extra bits
before
after
 35
b. Thuật toán “cơ hội thứ hai” 
Sử dụng một bit reference duy nhất. Thuật toán cơ sở vẫn là FIFO, tuy nhiên 
khi chọn đ−ợc một trang theo tiêu chuẩn FIFO, kiểm tra bit reference của trang đó : 
- Nếu giá trị của bit reference là 0, thay thế trang đã chọn. 
- Ng−ợc lại, cho trang này một cơ hội thứ hai, và chọn trang FIFO tiếp theo. 
- Khi một trang đ−ợc cho cơ hội thứ hai, giá trị của bit reference đ−ợc đặt lại là 
0, và thời điểm vào Ready List đ−ợc cập nhật lại là thời điểm hiện tại. 
- Một trang đã đ−ợc cho cơ hội thứ hai sẽ không bị thay thế tr−ớc khi hệ thống 
đã thay thế hết những trang khác. Hơn nữa, nếu trang th−ờng xuyên đ−ợc sử dụng, 
bit reference của nó sẽ duy trì đ−ợc giá trị 1, và trang hầu nh− không bao giờ bị thay 
thế. 
Có thể cài đặt thuật toán “cơ hội thứ hai” với một xâu vòng. 
 36
Hình 2.29 Thuật toán thay thế trang “cơ hội thứ hai” 
c. Thuật toán “cơ hội thứ hai” nâng cao - NRU 
Đối với mỗi trang trong bộ nhớ, ta sử dụng thêm hai bit : 
- R ( Reference ) bit : cho biết là trang có đ−ợc tham chiếu đến trong chu kỳ 
clock cuối cùng hay không 
 37
- M ( Modified hoặc dirty) bit : cho biết là trang có bị thay đổi 
Các bit này sẽ thiết lập đối với mỗi lần truy cập bộ nhớ bằng phần cứng cho 
nên sẽ rất nhanh. Dựa vào các bit này, ta chia các trang trong bộ nhớ thành 4 nhóm : 
- Nhóm 1 ; R =0, M=0 
- Nhóm 2 : R = 0, M =1 
- Nhóm 3 : R = 1, M =1 
- Nhóm 4 : R=1, M=1 
Xem các bit reference và dirty bit nh− một cặp có thứ tự : 
(0,0) không truy xuất, không sửa đổi: đây là trang tốt nhất để thay thế. 
(0,1) không truy xuất gần đây, nh−ng đã bị sửa đổi: tr−ờng hợp này không thật 
tốt, vì trang cần đ−ợc l−u trữ lại tr−ớc khi thay thế. 
(1,0) đ−ợc truy xuất gần đây, nh−ng không bị sửa đổi: trang có thể nhanh 
chóng đ−ợc tiếp tục đ−ợc sử dụng. 
(1,1) đ−ợc truy xuất gần đây, và bị sửa đổi: trang có thể nhanh chóng đ−ợc tiếp 
tục đ−ợc sử dụng, và tr−ớc khi thay thế cần phải đ−ợc l−u trữ lại. 
 Lớp 1 có độ −u tiên thấp nhất, và lớp 4 có độ −u tiên cao nhất. Một trang sẽ 
thuộc về một trong bốn lớp trên, tuỳ vào bit reference và dirty bit của trang đó. 
Trang đ−ợc chọn để thay thế là trang đầu tiên tìm thấy trong lớp có độ −u tiên thấp 
nhất và khác rỗng. 
d. Các thuật toán thống kê 
Sử dụng một biến đếm l−u trữ số lần truy xuất đến một trang, và phát triển hai 
thuật toán sau : 
 Thuật toán LFU: thay thế trang có giá trị biến đếm nhỏ nhất, nghĩa là trang ít 
đ−ợc sử dụng nhất. 
 Thuật toán MFU: thay thế trang có giá trị biến đếm lớn nhất, nghĩa là trang 
đ−ợc sử dụng nhiều nhất (most frequently used). 
6. Cấp phát khung trang 
Vấn đề đặt ra là làm thế nào để cấp phát một vùng nhớ tự do có kích th−ớc cố 
định cho các tiến trình khác nhau? 
 38
Trong tr−ờng hợp đơn giản nhất của bộ nhớ ảo là hệ đơn nhiệm, có thể cấp 
phát cho tiến trình duy nhất của ng−ời dùng tất cả các khung trang trống. 
Vấn đề nảy sinh khi kết hợp kỹ thuật phân trang theo yêu cầu với sự đa ch−ơng 
: cần phải duy trì nhiều tiến trình trong bộ nhớ cùng lúc, vậy mỗi tiến trình sẽ đ−ợc 
cấp bao nhiêu khung trang. 
Với mỗi tiến trình, cần phải cấp phát một số khung trang tối thiểu nào đó để 
tiến trình có thể hoạt động. Số khung trang tối thiểu này đ−ợc quy định bởi kiến trúc 
của của một chỉ thị. Khi một lỗi trang xảy ra tr−ớc khi chỉ thị hiện hành hoàn tất, 
chỉ thị đó cần đ−ợc tái khởi động, lúc đó cần có đủ các khung trang để nạp tất cả 
các trang mà một chỉ thị duy nhất có thể truy xuất. 
Số khung trang tối thiểu đ−ợc qui định bởi kiến trúc máy tính, trong khi số 
khung trang tối đa đ−ợc xác định bởi dung l−ợng bộ nhớ vật lý có thể sử dụng. 
Các thuật toán cấp phát khung trang 
Có hai h−ớng tiếp cận: 
a. Cấp phát cố định 
+ Cấp phát công bằng: nếu có m khung trang và n tiến trình, mỗi tiến trình 
đ−ợc cấp m/n khung trang. 
+ Cấp phát theo tỷ lệ: tùy vào kích th−ớc của tiến trình để cấp phát số khung 
trang : 
si = kích th−ớc của bộ nhớ ảo cho tiến trình pi 
S = ∑ si 
m = số l−ợng tổng cộng khung trang có thể sử dụng 
Cấp phát ai khung trang cho tiến trình pi : 
ai = (si/S).m 
Ví dụ : 
 b. Cấp phát theo độ −u tiên 
Sử dụng ý t−ởng cấp phát theo tỷ lệ, nh−ng nh−ng số l−ợng khung trang cấp 
cho tiến trình phụ thuộc vào độ −u tiên của tiến trình, hơn là phụ thuộc kích th−ớc 
tiến trình: 
Nếu tiến trình pi phát sinh một lỗi trang, chọn một trong các khung trang của 
nó để thay thế, hoặc chọn một khung trang của tiến trình khác với độ −u tiên thấp 
hơn để thay thế. 
7. Thay thế trang toàn cục hay cục bộ 
Có thể phân các thuật toán thay thế trang thành hai lớp chính: 
- Thay thế toàn cục: khi lỗi trang xảy ra với một tiến trình, chọn trang “nạn 
nhân” từ tập tất cả các khung trang trong hệ thống, bất kể khung trang đó đang đ−ợc 
cấp phát cho một tiến trình khác. 
- Thay thế cục bộ: yêu cầu chỉ đ−ợc chọn trang thay thế trong tập các khung 
trang đ−ợc cấp cho tiến trình phát sinh lỗi trang. 
Một khuyết điểm của thuật toán thay thế toàn cục là các tiến trình không thể 
kiểm soát đ−ợc tỷ lệ phát sinh lỗi trang của mình. Vì thế, tuy thuật toán thay thế 
toàn cục nhìn chung cho phép hệ thống có nhiều khả năng xử lý hơn, nh−ng nó có 
thể dẫn hệ thống đến tình trạng trì trệ toàn bộ (thrashing). 
 III.6. Trì trệ toàn bộ hệ thống (Thrashing) 
Nếu một tiến trình không có đủ các khung trang để chứa những trang cần thiết 
cho xử lý, thì nó sẽ th−ờng xuyên phát sinh các lỗi trang, và vì thế phải dùng đến rất 
 39
nhiều thời gian sử dụng CPU để thực hiện thay thế trang. Một hoạt động phân trang 
nh− thế đ−ợc gọi là sự trì trệ ( thrashing). Một tiến trình lâm vào trạng thái trì trệ 
nếu nó sử dụng nhiều thời gian để thay thế trang hơn là để xử lý. 
Hiện t−ợng trì trệ này ảnh h−ởng nghiêm trọng đến hoạt động hệ thống, xét 
tình huống sau : 
 Hệ điều hành giám sát việc sử dụng CPU. 
 B1 : Nếu hiệu suất sử dụng CPU quá thấp, hệ điều hành sẽ nâng mức độ đa 
ch−ơng bằng cách đ−a thêm một tiến trình mới vào hệ thống. 
 Hệ thống có thể sử dụng thuật toán thay thế toàn cục để chọn các trang nạn 
nhân thuộc một tiến trình bất kỳ để có chỗ nạp tiến trình mới, có thể sẽ thay thế cả 
các trang của tiến trình đang xử lý hiện hành. 
 B2 : Khi có nhiều tiến trình trong hệ thống hơn, thì một tiến trình sẽ đ−ợc cấp 
ít khung trang hơn, và do đó phát sinh nhiều lỗi trang hơn. 
 Khi các tiến trình phát sinh nhiều lỗi trang , chúng phải trải qua nhiều thời 
gian chờ các thao tác thay thế trang hoàn tất, lúc đó hiệu suất sử dụng CPU lại giảm 
 Hệ điều hành lại quay trở lại b−ớc 1... 
Theo kịch bản trên đây, hệ thống sẽ lâm vào tình trạng luẩn quẩn của việc giải 
phóng các trang để cấp phát thêm khung trang cho một tiến trình, và các tiến trình 
khác lại thiếu khung trang...và các tiến trình không thể tiếp tục xử lý. Đây chính là 
 40
 41
tình trạng trì trệ toàn bộ hệ thống. Khi tình trạng trì trệ này xảy ra, hệ thống gần 
nh− mất khả năng xử lý, tốc độ phát sinh lỗi trang tăng cao khủng khiếp, không 
công việc nào có thể kết thúc vì tất cả các tiến trình đều bận rộn với việc phân trang.