Cách giải thuật toán FIFO

HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG

KHOA CÔNG NGHỆ THÔNG TIN

CHUYÊN ĐỀ
Tìm Hiểu Các Thuật Toán Quản Lý Bộ Nhớ
Giảng viên hướng dẫn : Nguyễn Mạnh Sơn
Sinh viên thực hiện : Nguyễn Văn Giang
Nguyễn Đình Hiển
Bùi Tuấn Nghĩa
Lớp : L14CN
Nhóm : 12

Hà Nội, tháng 06 /2016


1. Danh sách thành viên trong nhóm:
1. Nguyễn Văn Giang
2. Nguyễn Đình Hiển
3. Bùi Tuấn Nghĩa
2. Tên đề tài:
Tìm hiểu về các thuật toán quản lý bộ nhớ
3. Giới thiệu đề tài:
Hiện nay với sự phổ biến của máy tính cũng như các thiết bị điện tử nhằm mục
đích phục vụ các nhu cầu về sinh hoạt, giải trí, công việc Con người đã không
ngừng nghiên cứu, cải tiến các thiết bị này và một trong những nhân tố quan trọng
trong hệ thống đó là bộ nhớ. Vậy làm sao để cấu thành, làm sao để quản lý và
quản lý một cách có hiệu quả. Với chuyên đề này chúng em mong góp chút kiến
thức để mọi người có thể hiểu sâu về vấn đề này.
Quản lý bộ nhớ là điều hành bộ nhớ ở cấp bậc hệ thống. Mục đích quan trọng
của việc quản lý bộ nhớ là cung cấp những cách thức để cấp phát động các ô nhớ

cho chương trình khi đc yêu cầu và giải phóng các ô nhớ đó khi không cần dung
nữa. Đây là việc rất quan trọng với bất kỳ hệ thống máy tính nào vì sẽ có nhiều
công việc được thực hiện tại mọi thời điểm.
Nhiều phương pháp đã được tìm ra nhằm tang hiệu quả của việc quản lý bộ
nhớ. Những hệ thống bộ nhớ ảo giúp tách những địa chỉ ô nhớ đang được dùng ra
khỏi những địa chỉ thực, từ đó cho phép chia sẻ công việc và tang lượng RAM
một cách hiệu quả nhờ đánh dấu địa chỉ hoặc chuyển đến vùng lưu trữ thứ 2. Chất
lượng của việc quản lý bộ nhớ ảo có thể ảnh hưởng lớn đến hiệu năng làm việc


của hệ thống nói chung
4. Các nội dung chính:

CHƯƠNG 1 : Tổng quan về quản lý bộ nhớ
1.1Khái niệm
Bộ nhớ chính là thiết bị lưu trữ duy nhất thông qua đó CPU có thể trao đổi thông tin với
môi trường ngoài, do vậy nhu cầu tổ chức, quản lý bộ nhớ là một trong những nhiệm vụ
trọng tâm hàng đầu của hệ điều hành
1.1Nhu cầu bộ nhớ của tiến trình
Bộ nhớ chính được tổ chức như một mảng một chiều các từ nhớ [word], mỗi từ nhớ có
một địa chỉ. Việc trao đổi thông tin với môi trường ngoài được thực hiện thông qua các
thao tác đọc hoặc ghi dữ liệu vào một địa chỉ cụ thể nào đó trong bộ nhớ. Hầu hết các hệ
điều hành hiện đại đều cho phép chế độ đa nhiệm nhằm nâng cao hiệu suất sử dụng
CPU. Tuy nhiên kỹ thuật này lại làm nảy sinh nhu cầu chia sẻ bộ nhớ giữa các tiến trình
khác nhau. Vấn đề nằm ở chỗ: bộ nhớ thì hữu hạn và các yêu cầu bộ nhớ thì vô hạn.


CHƯƠNG 2 : Các thuật toán quản lý bộ nhớ

Vấn đề chính khi thay thế trang là chọn lựa một trang « nạn nhân » để chuyển ra

bộ nhớ phụ. Có nhiều thuật toán thay thế trang khác nhau, nhưng tất cả cùng 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.
Có thể đánh giá hiệu qủa của một thuật toán bằng cách xử lý trên một chuỗi các địa chỉ
cần truy xuất và tính toán số lượng lỗi trang phát sinh.

Ví dụ: Giả sữ theo vết xử lý của một tiến trình và nhận thấy tiến trình thực hiện
truy xuất các địa chỉ theo thứ tự sau :

0100, 0432, 0101, 0162, 0102, 0103, 0104, 0101, 0611, 0102, 0103,0104, 0101,
0610,
0102, 0103, 0104, 0101, 0609, 0102, 0105

Nếu có kích thước của một trang là 100 bytes, có thể viết lại chuỗi truy xuất trên
giản lược hơn như sau :

1, 4, 1, 6, 1, 6, 1, 6, 1

Để xác định số các lỗi trang xảy ra khi sử dụng một thuật toán thay thế trang nào
đó trên một chuỗi truy xuất cụ thể, còn cần phải biết số lượng khung trang sử dụng


trong hệ thống.

Để minh hoạ các thuật toán thay thế trang sẽ trình bày, chuỗi truy xuất được sử
dụng là : 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1

Thuật toán FIFO
Tiếp cận: Ghi nhận thời điểm một trang được mang vào bộ nhớ chính. Khi cần
thay thế trang, trang ở trong bộ nhớ lâu nhất sẽ được chọn


Ví dụ : sử dụng 3 khung trang , ban đầu cả 3 đều trốn

Ghi chú : * : có lỗi
trang Thảo luận:
Để áp dụng thuật toán FIFO, thực tế không nhất thiết phải ghi nhận thời điểm
mỗi trang được nạp vào bộ nhớ, mà chỉ cần tổ chức quản lý các trang trong bộ nhớ
trong một danh sách FIFO, khi đó trang đầu danh sách sẽ được chọn để thay thế.

Thuật toán they thế trang FIFO dễ hiểu, dễ cài đặt. Tuy nhiên khi thực hiện
không phải lúc nào cũng có kết qủa tốt : trang được chọn để thay thế có thể là trang


chức nhiều dữ liệu cần thiết, thường xuyên được sử dụng nên được nạp sớm, do vậy
khi bị chuyển ra bộ nhớ phụ sẽ nhanh chóng gây ra lỗi trang.

Số lượng lỗi trang xảy ra sẽ tăng lên khi số lượng khung trang sử dụng tăng.
Hiện tượng này gọi là nghịch lý Belady.

Ví dụ: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

Sử dụng 3 khung trang , sẽ có 9 lỗi trang phát sinh

Sử dụng 4 khung trang , sẽ có 10 lỗi trang phát sinh


Thuật toán tối ưu

Tiếp cận: Thay thế trang sẽ lâu được sử dụng nhất trong tương
lai. Ví dụ : sử dụng 3 khung trang, khởi đầu đều trống:

7 0 1 2 0 3 0 4 2 3 0 32 1 2 01 7 0 1
7 7 7 2 2 2 2 2 2 2 2 22 2 2 22 7 7 7
0 0 0 0 0 0 4 4 4 0 00 0 0 00 0 0 0
1 1 1 3 3 3 3 3 3 33 1 1 11 1 1 1
* * * *

*

*

*

*

*

Thảo luận:

Thuật toán này bảo đảm số lượng lỗi trang phát sinh là thấp nhất , nó cũng
không gánh chịu nghịch lý Belady, tuy nhiên, đây là một thuật toán không khả thi
trong thực tế, vì không thể biết trước chuỗi truy xuất của tiến trình!

Thuật toán « Lâu nhất chưa sử dụng » [ Least-recently-used LRU]

Tiếp cận: Với mỗi trang, ghi nhận thời điểm cuối cùng trang được truy cập,
trang được chọn để thay thế sẽ là trang lâu nhất chưa được truy xuất.

Ví dụ: sử dụng 3 khung trang, khởi đầu đều trống:



Thảo luận:

Thuật toán FIFO sử dụng thời điểm nạp để chọn trang thay thế, thuật toán tối ưu
lại dùng thời điểm trang sẽ được sử dụng, vì thời điểm này không thể xác định trước
nên thuật toán LRU phải dùng thời điểm cuối cùng trang được truy xuất dùng quá
khứ gần để dự đoán tương lai.

Thuật toán này đòi hỏi phải được cơ chế phần cứng hỗ trợ để xác định một thứ tự
cho các trang theo thời điểm truy xuất cuối cùng. Có thể cài đặt theo một trong hai
cách :

Sử dụng bộ đếm:

thêm vào cấu trúc của mỗi phần tử trong bảng trang một trường ghi nhận thời
điểm truy xuất mới nhất, và thêm vào cấu trúc của CPU một bộ đếm.

mỗi lần có sự truy xuất bộ nhớ, giá trị của counter tăng lên 1.


Mỗi lần thực hiện truy xuất đến một trang, giá trị của counter được ghi nhận vào
trường thời điểm truy xuất mới nhất của phần tử tương ứng với trang trong bảng trang.

thay thế trang có giá trị trường thời điểm truy xuất mới nhất là nhỏ nhất.

Sử dụng stack:

tổ chức một stack lưu trữ các số hiệu trang

mỗi khi thực hiện một truy xuất đến một trang, số hiệu của trang sẽ được xóa
khỏi vị trí hiện hành trong stack 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.

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.

Hình 4.28 Cấu trúc một phần tử trong bảng trang

Thuật toán với các bit reference phụ trợ

Tiếp cận: 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 gía 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.

Ví dụ :


Thảo luận: 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ể.

Thuật toán « cơ hội thứ hai »

Tiếp cận: 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ế.

Thảo luận:

Có thể cài đặt thuật toán « cơ hội thứ hai » với một xâu vòng.


Hình 2.29 Thuật toán thay thế trang
Thuật toán « cơ hội thứ hai » nâng cao [Not Recently Used - NRU]
Tiếp cận : xem các bit reference và dirty bit như một cặp có thứ tự .
Với hai bit này, có thể có 4 tổ hợp tạo thành 4 lớp sau :


[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.

Các thuật toán thống kê

Tiếp cận: 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].


5. Tài Liệu Tham Khảo:
[1] chương 4, sách "Modern Operating Systems", Andrew S. Tanenbaum: , 2nd
ed, Prentice Hall
[2] Chương 3, sách Khoa học máy tính, Ths Nguyễn Thị Ngọc Vinh.

[3]. Giáo trình quản lý bộ nhớ, PGS.TS. Đỗ Phúc, Trường ĐH CNTT, ĐHQG
TP.HCM, Nhà xuất bản ĐHQG TP.HCM, 2006
[4] www.google.com.vn