Kiến thức và bài tập về First Fit, Next Fit, Worst Fit, Best Fit - Nguyên lý hệ điều hành - Học Viện Kỹ Thuật Mật Mã
Giả sử bộ nhớ chính được phân thành các phân vùng có kích thước là 900K, 400K, 600K, 300K (theo thứ tự) và con trỏ đang trỏ vào vùng nhớ 400K, cho biết các tiến trình có kích thước 700K, 400K, 300K và 200K (theo thứ tự) sẽ được cấp phát bộ nhớ như thế nào, nếu sử dụng. Tài liệu giúp bạn tham khảo và đạt kết quả tốt. Mời bạn đọc đón xem!
Preview text:
Giả sử bộ nhớ chính được phân thành các phân vùng có kích thước là 900K, 400K, 600K, 300K
(theo thứ tự) và con trỏ đang trỏ vào vùng nhớ 400K, cho biết các tiến trình có kích thước 700K,
400K, 300K và 200K (theo thứ tự) sẽ được cấp phát bộ nhớ như thế nào, nếu sử dụng: • First Fit • Next Fit • Worst Fit • Best Fit Bài làm:
First Fit: (Duyệt từ đầu. Thấy vùng nhớ trống nào đủ để cấp phát cho Process thì cấp luôn) •
700K được cấp phát cho vùng nhớ 900K •
400K được cấp phát cho vùng nhớ 400K •
300K được cấp phát cho vùng nhớ 600K •
200K được cấp phát cho vùng nhớ 200k (vùng nhớ còn dư của 900K – 700K = 200K)
Next Fit: (Giống First Fit nhưng điểm xuất phát là từ con trỏ) •
700K phải chờ vì không có vùng nhớ trống thỏa yêu cầu •
400K được cấp phát cho vùng nhớ 400K •
300K được cấp phát cho vùng nhớ 600K •
200K được cấp phát cho vùng nhớ 300K (vùng nhớ còn dư của 600K – 300K = 300K)
Worst Fit: (Cũng duyệt từ đầu NHƯNG cấp theo kiểu đại gia – thấy vùng trống nào có kích
thước lớn nhất thời điểm hiện tại thì mới dùng nó để cấp cho Process) •
700K được cấp phát cho vùng nhớ 900K •
400K được cấp phát cho vùng nhớ 600K •
300K được cấp phát cho vùng nhớ 400K •
200K được cấp phát cho vùng nhớ 200k (vùng nhớ còn dư của 900K – 700K = 200K)
Best Fit: (Cấp phát vùng nhớ trống nhỏ nhất đủ lớn) •
700K được cấp phát cho vùng nhớ 900K •
400K được cấp phát cho vùng nhớ 400K •
300K được cấp phát cho vùng nhớ 300K •
200K được cấp phát cho vùng nhớ 200k (vùng nhớ còn dư của 900K – 700K = 200K)
1. Quản lý bộ nhớ bằng cách phân vùng động (dynamic partition):
Trong chế độ quản lý này, toàn bộ code chương trình và dữ liệu phải được
nạp vào bộ nhớ trước khi process tương ứng bắt đầu chạy. Ta có thể dùng 1
trong các chiến lược phân phối vùng nhớ cho 1 process như sau :
• "First Fit" tìm vùng nhớ đầu tiên có kích thức đủ chứa process.
• "Best Fit" tìm vùng nhớ nhỏ nhất có kích thức đủ chứa process.
• "Worst Fit" tìm vùng nhớ lớn nhất có kích thức đủ chứa process. 1.1 Câu hỏi 1
Giả sử lúc đầu, bộ nhớ được chia làm 5 vùng nhớ trống có kích thước lần
lượt là 100KB, 500KB, 200KB, 300K, 600KB. Nếu các process được kích
hoạt chạy lần lượt cần dung lượng bộ nhớ như sau: 212KB, 417KB,
112KB, 426KB, chúng được phân phối như thế nào nếu ta dùng chiến
lược Best-Fit và First-Fit? 1.2 Câu hỏi 2
Nếu chia bộ nhớ thành các block độ dài 10KB, vùng nhớ cho 4 process yêu
cầu như câu 1.1 sẽ như thế nào. Ta gọi chiến lược phân phối này là gì? Giải thích kết quả?
Process P1 chiếm chính xác 220KB (22 block), P2 chiếm 420KB (42 block),
P3 chiếm 120KB (12 block) và P4 chiếm 430KB (43 block). Tổng kích thước
vùng nhớ đã phân phối cho 4 process là 220K+420KB+120KB+430KB.
Tổng không gian bị lãng phí là 8K + 3K + 8K + 4K = 23KB.
Ta gọi chiến lược phân phối bộ nhớ này là "chiến lược phân phối theo block",
nó giúp ta tránh được việc tạo ra nhiều partition có kích thước quá nhỏ không
đủ dùng cho process nào hết và như thế là tránh lãng phí. Nếu chọn kích
thước block lớn, không gian bị lãng phí trong việc cấp phát vùng nhớ cho 1 process sẽ lớn.
Nếu dùng chiến lược phân phối bộ nhớ ra thành các partition động như câu
1.1, ta có thể di dời vùng nhớ của các partition lại sát nhau để thu hồi các
vùng nhớ trống nhỏ rời rạc và dùng lại vùng nhớ trống này. Còn nếu dùng
chiến lược phân phối theo block thì mỗi process sẽ không dùng hết block cuối
cùng được phân phối, phần thừa này sẽ bị lãng phí vì ta không thề
thu hồi chúng để dùng cho process khác. Tuy nhiên vùng lãng phí của từng
process thường rất nhỏ vì ta chọn kích thước block nhỏ (thí dụ block = 10KB
thì mỗi process lãng phí tối đa 10KB).
http://www.cse.hcmut.edu.vn/~hiep/SlideHDH/Thuchanh/Tuan%207/Bai%207.1.pdf