Name: Trần Quốc Bảo
ID: 20521110
Class: IT007.M13
OPERATING SYSTEM
LAB X’S REPORT
SUMMARY
Task

Self-scrores: 8

*Note: Export file to PDF and name the file by following format:
LAB X – <Student ID>.pdf

1


BÀI THỰC HÀNH 6
Câu 1: Vẽ lưu đồ, giải thích và hiện thực lại 3 giải thuật FIFO, OPT, LRU theo u
cầu trong phần 6.4
-

Lưu đồ thuật tốn FIFO

Hình 1. Lưu đồ thuật toán giải thuật FIFO
-

Ý tưởng: Thuật toán của em chia thành 2 nhánh chính, nhánh 1 là trước khi bảng
trang cịn trống để có thể thêm lỗi, nhánh 2 là bảng trang đã đầy và phải chọn ra
phần tử để thay thế. Trước khi thêm hoặc chọn phần tử để “hy sinh” thì ta đều phải
kiểm tra xem trong bảng đã tồn tại lỗi đó hay chưa?

2


Hình 2. Giải thích lưu đồ giải thuật FIFO.
-

Lưu đồ giải thuật LRU

3


Hình 3. Lưu đồ giải thuật LRU
-

-

Ý tưởng: Ở giải thuật này em cũng chia thành 2 nhánh chính, nhánh thứ nhất là
trường hợp trong bảng trang chưa đầy, và trường hợp 2 là bảng trang đã đầy.
Ngoài ra, em có tạo thêm một kiểu dữ liệu để có thể lưu lại vị trí của nó để
thuận tiện cho việc tìm được lỗi lâu sử dụng nhất.
Trường hợp 1: Sẽ kiểm tra sự tồn tại của những phần tử có trong bảng, nếu khơng
có sẽ thêm vào, cịn nếu có rồi thì sẽ cập nhật vị trí.
Trường hợp 2: Cũng sẽ kiểm tra sự tồn tại của phần tử đó trong bảng, nếu khơng
có sẽ chọn ra phần tử có vị trí nhỏ nhất, vì vị trí nhỏ nhất tức là thời gian bị sử
dụng lại lâu nhất, ta sẽ dùng phần tử đó để hy sinh và thay thế.

4


Hình 4. Giải thích về các phần trong lưu đồ thuật toán LRU

-

Lưu đồ thuật toán OPT:

5


Hình 5. Lưu đồ thuật tốn OPT
-

-

Ý nghĩa: Ở thuật tốn này, em sẽ chia thành 3 phần chính, vì có thêm một trường
hợp là trong tương lai một lỗi nào đó sẽ khơng trùng lại. Và mỗi lần kiểm tra lỗi
thì đều cập nhật lại vị trí của lỗi đó trong tương lai
Phần 1: Sẽ kiểm tra bảng trang, nếu chưa đầy thì sẽ thêm các lỗi vào và cập
nhật giá trị ViTri cho nó.
Phần 2: Nếu bảng trang đã đầy, sẽ ưu tiên thay thế cho các phần tử có ViTri = -1,
những phần tử này sẽ khơng bị trùng lặp trong tương lai.
Phần 3: Kiểm tra và cập nhật lại vị trí cho các phần tử trong tương lai sau mỗi lần
kiểm tra lỗi. Và sau đó kiểm tra phần tử có ViTri=-1 để thay thế trước, sau đó mới
ưu tiên những phần tử lâu sử dụng nhất trong tương lai sau.

6


Hình 8. Giải thích lưu đồ thuật tốn OPT
-

Hiện thực:

+ Khi hiện thực có hơi khác chút về phần kết luận và tạo thêm biến để lưu trữ các
giá trị. Ví dụ như thêm 1 string err để lưu lại các lỗi nhưng trong lưu đồ chỉ xuất ra
số lượng lỗi.
Ngồi ra có thêm các hàm xuất, thêm giá trị cho mảng…

7


Hình 9. Khởi tạo kiểu dữ liệu khung trang, hàm xuất dữ liệu

Hình 10. Hàm thêm dữ liệu vơ mảng, xuất mảng 2 chiều.

8


Hình 11. Hàm thêm dữ liệu vào queue.

Hình 12. Hàm kiểm tra tồn tại và giải thuật FIFO.

9


Hình 13. Sau khi kiểm tra phần tử trong khung trang, thêm dữ liệu
nếu khung trang chưa đầy và kiểm tra tồn tại để pop phần tử đầu tiên
trong queue.

Hình 14. Giải thuật LRU, hàm addElement khác hàm add của FIFO ở chỗ FIFO
dùng queue, còn LRU chỉ cần dùng một mảng để lưu giá trị và vị trí.
10



Hình 15. Kiểm tra kích thước khung trang, nếu chưa đầy và khơng có phần tử trùng thì
thêm vào, cịn nếu có rồi thì chỉ cần cập nhật lại vị trí. Nếu khung trang đã đầy thì kiểm
tra trùng và cập nhật vị trí.

Hình 16. Xuất ra kết quả giải thuật LRU, bắt đầu giải thuật OPT. findMaxPos để tìm
kiếm phần tử có vị trí lớn nhất để được chọn thay thế.
11


Hình 17. isArrExists để kiểm tra sự tồn tại của một giá trị nào đó trong mảng, hàm
isEExistsPos là kiểm tra xem khung trang có tồn tại phần tử có vị trí pos hay khơng.

Hình 18. Xử lý dữ liệu nhập vào giải thuật OPT. Kiểm tra kích thước bảng trang, nếu
chưa đầy thì kiểm tra sự tồn tại của phần tử đó để quyết định thêm phần tử, với trường
hợp đầy bảng, chọn phần tử thay thế có độ ưu tiên theo vị trí.
12


Hình 19. Kiểm tra trong bảng trang (đầy), nếu có phần tử nào ít được sử
dụng trong tương lai nhất sẽ được chọn để thay thế và đánh lỗi.

Hình 20. Xuất mảng 2 chiều gồm bảng trang và xuất ra số lỗi có trong bảng. Một
phương thức chính được sử dụng trong hàm main.
13


Hình 21. Hàm main, nhập dữ liệu và chọn ra bảng trang mặc định hoặc bảng trang tự
nhập.


Hình 22. Kiểm tra chọn lựa và trả về thuật toán yêu cầu.

14


-

Các test case:
Trường hợp test case default:

Hình 23. Giải thuật FIFO với test case default.
-

Chạy tay:
2
2

*
-

Vậy số lỗi là 5, giống như giải thuật

15


Hình 24. Giải thuật OPT với test case default.
- Chạy tay:
2
2


*
- Số lỗi là 5, quá trình chạy giống như code.

16


Hình 25. Giải thuật LRU với test case default.
- Chạy tay:
2
2

*
- Manual input sequence:

17


Hình 26. Test case manual 1 – FIFO
-

Chạy tay:
2
2

*
-

Số lỗi là 4, code có đáp án giống với test case.

Hình 27. Mutual test 2 – FIFO

18


- Chạy tay:
2
2
*
- Có tổng cộng 8 lỗi , bảng trang giống kết quả của code.

- Chạy tay:
3
3

*


1
1

*
- Số lỗi bảng trang là 7: Kết quả nhận được giống với code

Hình 30. Mutual test case 2- OPT
20


-

Chạy tay:
3

3

*
-

Số lỗi trang : 4, kết quả của chạy tay trùng với code.

Hình 31. Mutual test 3 – OPT
-

Chạy tay:
5
5

*
-

Số lỗi : 5 , kết quả chạy tay giống với đáp án của code.

21


Hình 32. Mutual test 1 – LRU
-

Chạy tay:
6
6

*

-

Số lỗi là 8, kết quả của chạy tay trùng với đáp án của code.

Hình 33. Mutual test case 2 – LRU
22


- Chạy tay:
3
3
*
- Số lỗi xảy ra: 9, Kết quả trùng với code nhận được

Hình 34. Mutual test 3 – LRU
-

Chạy thử:
3
3

*
-

Số lỗi 7 , kết quả chạy giống với kết quả của code.

23


Câu 2: Thực hiện những câu hỏi trong phần 6.5

1. Nghịch lý Belady là gì? Sử dụng chương trình đã viết trên để chứng minh

nghịch lý này.

-

Trả lời: Nghịch lý Belady phát biểu như sau: Số lỗi trang (page fault) tăng lên
mặc dù quá trình đã được cấp nhiều frame hơn.
Chứng minh: Ta xét với chuỗi 1 2 3 4 1 2 5 1 2 3 4 5
o Trường hơp 1: Với 3 khung trang

Hình 35. Thử nghịch lý Belady với 3 khung trang.
Ta thấy, với trường hợp 3 khung trang thì có 9 lỗi xảy ra.
o Trường hợp 2: Với 4 khung trang

Hình 36. Thử nghịch lý Belady với 4 khung trang.
24


Ta thấy, với trường hợp 4 khung trang thì có 10 lỗi xảy ra.
 Nghịch lý Belady đúng.
2. Nhận xét về mức độ hiệu quả và tính khả thi của các giải thuật

FIFO, OPT, LRU.
a. Giải thuật nào là bất khả thi nhất? Vì sao?
b. Giải thuật nào là phức tạp nhất? Vì sao?

a. Giải thuật bất khả thi nhất là OPT, vì ta khơng thể đốn được trước là có những lỗi

nào sẽ xảy ra để có thể đốn được vị trí lặp lại lâu nhất trong tương lai.

b. Giải thuật phức tạp nhất là OPT, vì phải kiểm tra và cập nhật lại vị trí của các
lỗi trong tương lai sau mỗi lần kiểm tra lỗi, trong khi LRU thì chỉ cần cập
nhật lại vị trí hiện tại nếu trùng lặp và thay thế nếu có vị trí nhỏ nhất. FIFO thì
chỉ cần kiểm tra trùng lặp và pop ra khỏi queue.

25