Giáo trình Hệ điều hành - Chương 8: Bộ nhớ ảo - Nguyễn Phú Trường

nh đang xử lý hiện hành. 
4) Khi có nhiều quá trình trong hệ thống hơn, thì một quá trình sẽ được cấp ít 
khung trang hơn và do đó phát sinh nhiều lỗi trang hơn. 
5) Khi các quá 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. 
6) 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 quá trình, và các quá trình 
khác lại thiếu khung trang..và các quá trình không thể tiếp tục xử lý. Đây chính là 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 rất cao không công việc nào có thể kết 
thúc vì tất cả quá trình đều bận rộn với việc phân trang. 
Để ngăn cản tình trạng trì trệ này xảy ra, cần phải cấp cho quá trình đủ các 
khung trang cần thiết để hoạt động. Vấn đề cần giải quyết là làm sao biết được quá 
trình cần bao nhiêu trang? 
VII.1 Mô hình cục bộ 
Theo lý thuyết cục bộ thì khi một quá trình xử lý nó có khuynh hướng di 
chuyển từ nhóm trang cục bộ này đến nhóm trang cục bộ khác. Một nhóm trang cục 
bộ là một tập các trang đang được quá trình dùng đến trong một khoảng thời gian. 
Một chương trình thường bao gồm nhiều nhóm trang cục bộ khác nhau và chúng có 
thể giao nhau. 
Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 193
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 
VII.2 Mô hình tập làm việc 
Mô hình tập làm việc (working set model) này dựa trên cơ sở lý thuyết cục bộ. 
Mô hình này sử dụng tham số ∆ để định nghĩa cửa sổ cho tập làm việc. Giả sử, khảo 
sát ∆ đơn vị thời gian (lần truy xuất trang) cuối cùng, tập các trang được quá trình truy 
xuất đến trong ∆ lần truy cập cuối cùng được gọi là tập làm việc của quá trình tại thời 
điểm hiện tại. Nếu một trang đang được quá trình truy xuất tới, nó sẽ nằm trong tập 
làm việc nếu nó không sử dụng nữa, nó sẽ bị loại khỏi tập làm việc của quá trình sau 
∆ đơn vị thời gian kể từ lần truy xuất cuối cùng đến nó. Như vậy, tập làm việc chính 
là sự xấp xỉ của khái niệm nhóm trang cục bộ. 
 Hình 0-13 Mô hình tập làm việc 
Thuộc tính rất quan trọng của tập làm việc là kích thước của nó. Nếu tính toán 
kích thước tập làm việc WSSi, cho mỗi tiến trình trong hệ thống thì có thể xem: 
D = ∑ WSSi
Với D là tổng số khung trang yêu cầu cho toàn hệ thống. Mỗi quá trình sử dụng 
các trang trong tập làm việc của nó, nghĩa là quá trình i yêu cầu WSSi khung trang. 
Nếu tổng số trang yêu cầu vượt quá tổng số trang có thể sử dụng trong hệ thống (D > 
m), thì sẽ xảy ra tình trạng trì trệ toàn bộ. 
Dùng mô hình tập làm việc là đơn giản. Hệ điều hành kiểm soát tập làm việc 
của mỗi quá trình và cấp phát cho quá trình tối thiểu các khung trang để chứa đủ tập 
làm việc của nó. Nếu có đủ khung trang bổ sung thì quá trình khác có thể được khởi 
tạo. Nếu tổng kích thước tập làm việc gia tăng vượt quá tổng số khung sẳn có, hệ điều 
hành chọn một quá trình để tạm dừng. Những trang của quá trình này được viết ra đĩa 
và các khung trang của nó được cấp phát lại cho quá trình khác. Quá trình được tạm 
dừng có thể khởi động lại sau đó. 
Chiến lược tập làm việc ngăn chặn sự trì trệ trong khi giữ cấp độ đa chương cao 
nhất có thể. Do đó, nó tối ưu việc sử dụng CPU. 
Khó khăn với mô hình tập làm việc này là giữ vết của tập làm việc. Cửa sổ tập 
làm việc là một cửa sổ di chuyển. Tại mỗi tham khảo bộ nhớ, một tham khảo mới xuất 
hiện khi một tham khảo trước đó kết thúc và tham khảo cũ nhất trở thành điểm kết 
thúc khác. Một trang ở trong tập làm việc nếu nó được tham khảo bất cứ nơi nào trong 
cửa sổ tập làm việc. Chúng ta có thể xem mô hình tập làm việc gần xấp xỉ với ngắt 
đồng hồ sau từng chu kỳ cố định và bit tham khảo. 
VII.3 Tần suất lỗi trang 
Tần suất lỗi trang rất cao khiến tình trạng trì trệ hệ thống xảy ra. Khi tần suất 
lỗi trang quá cao, quá trình cần thêm một số khung trang. Ngược lại, khi tần suất quá 
thấp, quá trình có thể sở hữu nhiều khung trang hơn mức cần thiết. Có thể thiết lập 
một giá trị cận trên và cận dưới cho tần suất xảy ra lỗi trang và trực tiếp ước lượng và 
kiểm soát tần suất lỗi trang để ngăn chặn tình trạng trì trệ xảy ra: 
Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 194
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 
• Nếu tần suất lỗi trang vượt quá cận trên, cấp cho quá trình thêm một khung 
trang 
• Khi tần suất lỗi trang thấp hơn cận dưới, thu hồi bớt một khung trang từ 
quá trình. 
Với chiến lược tập làm việc, chúng ta có thể có phải tạm dừng một quá trình. 
Nếu tỉ lệ lỗi trang tăng và không có trang nào trống, chúng ta phải chọn một số quá 
trình và tạm dừng nó. Sau đó, những khung trang được giải phóng sẽ được phân phối 
lại cho các quá trình với tỉ lệ lỗi trang cao. 
VIII Các vấn đề khác 
VIII.1 Kích thước trang 
Kích thước trang thông thường được xác định bởi phần cứng. Không có sự chọn 
lựa lý tưởng cho kích thước trang: 
• Kích thước trang càng lớn thì kích thước bảng trang càng giảm 
• Kích thước trang càng nhỏ thì cho phép tổ chức nhóm trang cục bộ tốt hơn 
và giảm sự phân mãnh trong 
• Thời gian nhập xuất nhỏ khi kích thước trang lớn 
• Kích thước trang nhỏ thì có thể giảm số lượng thao tác nhập xuất cần thiết 
vì có thể xác định các nhóm trang cục bộ chính xác hơn 
• Kích thước trang lớn sẽ giảm tần xuất lỗi trang 
Đa số các hệ thống chọn kích thước trang là 4 KB. 
VIII.2 Cấu trúc chương trình 
Về nguyên tắc, kỹ thuật phân trang theo yêu cầu được thiết kế nhằm giúp 
người dùng khỏi bận tâm đến việc sử dụng bộ nhớ một cách hiệu quả. Tuy nhiên, nếu 
hiểu rõ tổ chức bộ nhớ trong kỹ thuật phân trang, lập trình viên có thể giúp cho hoạt 
động của hệ thống tốt hơn với chương trình được xây dựng phù hợp. 
Thí dụ, giả sử 1 trang có kích thước 128 bytes, một chương trình khởi tạo và 
gán giá trị mảng có kích thước 128x128 như sau: 
Var A: array[1..128] of array [1..128] of byte; 
 For i:= 1 to 128 do 
 For j:=1 to 128 do 
 A[i][j]:=0; 
Trong Pascal, C, PL/I, mảng trên đây được lưu trữ theo thứ tự dòng, mỗi dòng 
mảng chiếm một trang bộ nhớ, do đó tổng số lỗi trang phát sinh sẽ là 128. 
Trong Fortran, mảng trên đây lại được lưu trữ theo thứ tự cột, do đó tổng số lỗi 
trang phát sinh sẽ là 128x128 = 1638. 
VIII.3 Neo các trang trong bộ nhớ chính 
Khi áp dụng kỹ thuật phân trang đôi lúc có nhu cầu “neo” trong bộ nhớ chính 
một số trang quan trọng hoặc thường được sử dụng hoặc không thể chuyển ra bộ nhớ 
phụ để bảo toàn dữ liệu. 
Khi đó sử dụng thêm một bit khoá gán tương ứng cho từng khung trang. Một 
khung trang có bit khoá được đặt sẽ không bị chọn để thay thế. 
Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 195
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 
IX Tóm tắt 
Mong muốn có thể thực thi một quá trình có không gian địa chỉ luận lý lớn hơn 
không gian địa chỉ vật lý sẳn có. Người lập trình có thể làm một quá trình như thế có 
thể thực thi bằng cách cấu trúc lại nó dùng cơ chế phủ lắp, nhưng thực hiện điều này 
thường là một tác vụ lập trình khó. Bộ nhớ ảo là một kỹ thuật cho phép không gian 
địa chỉ luận lý được ánh xạ vào bộ nhớ vật lý nhỏ hơn. Bộ nhớ ảo cho phép những quá 
trình cực lớn được chạy và cũng cho phép cấp độ đa chương được gia tăng, tăng khả 
năng sử dụng CPU. Ngoài ra, nó giải phóng người lập trình ứng dụng từ việc lo lắng 
khả năng sẳn có của bộ nhớ. 
Thuần phân trang theo yêu cầu mang vào một trang cho tới khi trang đó được 
tham khảo. Tham khảo đầu tiên gây ra lỗi trang tới hệ điều hành. Hệ điều hành xem 
xét bảng trang bên trong để xác định nơi trang được định vị trên vùng bộ nhớ phụ. 
Bảng trang được cập nhật để phản ánh sự thay đổi này, cho phép một quá trình chạy 
mặc dù toàn bộ hình ảnh bộ nhớ của nó không ở trong bộ nhớ chính. Khi tỉ lệ lỗi trang 
tương đối thấp, năng lực có thể chấp nhận. 
Chúng ta có thể dùng phân trang theo yêu cầu để giảm số khung trang được cấp 
phát tới quá trình. Sắp xếp này có thể tăng cấp độ đa chương (cho phép nhiều quá 
trình sẳn sằng thực thi tại một thời điểm). Nó cũng cho phép các quá trình được thực 
thi mặc dù yêu cầu bộ nhớ vượt quá toàn bộ bộ nhớ vật lý sẳn có. Những quá trình 
như thế chạy trong bộ nhớ ảo. 
Nếu tổng số yêu cầu bộ nhớ vượt quá bộ nhớ vật lý, thì nó cần thay thế trang từ 
bộ nhớ tới các khung trang trống cho những trang mới. Những giải thuật thay thế 
trang khác nhau được dùng. Thay thế trang FIFO là dễ dàng đối với chương trình 
nhưng gặp phải lỗi Belady. Thay thế trang tối ưu yêu cầu kiến thức tương lai. Thay 
thế LRU là xấp xỉ tối ưu nhưng nó rất khó cài đặt. Hầu hết các giải thuật thay thế 
trang như giải thuật cơ hội thứ hai là xấp xỉ thay thế LRU. 
Ngoài ra đối với giải thuật thay thế trang, chính sách cấp phát khung trang được 
yêu cầu. Cấp phát có thể cố định, đề nghị thay thế trang cục bộ, hay động, đề nghị 
thay thế toàn cục. Mô hình tập làm việc cho rằng các quá trình thực thi trong các vị 
trí. Tập làm việc là tập các trang trong các vị trí hiện hành. Theo đó, mỗi quá trình nên 
được cấp phát đủ các khung cho tập làm việc hiện hành của nó. 
Nếu một quá trình không có đủ bộ nhớ cho tập làm việc của nó, nó sẽ bị trì trệ. 
Cung cấp đủ khung cho mỗi quá trình để tránh trì trệ có thể yêu cầu quá trình hoán vị 
và định thời. 
Ngoài ra, để yêu cầu chúng ta giải quyết các vấn đề chính của thay thế trang và 
cấp phát khung trang, thiết kế hợp lý hệ thống phân trang yêu cầu chúng ta xem xét 
kích thước trang, nhập/xuất, khoá, phân lại trang, tạo quá trình, cấu trúc chương trình, 
sự trì trệ,.. Bộ nhớ ảo có thể được xem như một cấp của cơ chế phân cấp trong các cấp 
lưu trữ trong hệ thống máy tính. Mỗi cấp có thời gian truy xuất, kích thước và tham số 
chi phí của chính nó. 
Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 196