Bài tập cấp phát bộ nhớ

BÀI TậP CấP PHÁT Bộ NHớ (FIRST-FIT, BEST-
FIRST, WORST-FIT) 
Best-first 
1./ Trong mô hình cấp phát bộ nhớ liên tục, có năm phân mảnh bộ nhớ theo thứ 
tự với kích thước là 600KB, 500KB, 200KB, 300KB. Giả sử có 4 tiến trình đang 
chờ cấp phát bộ nhớ theo thứ tự P1, P2, P3, P4. Kích thước tương ứng của các 
tiến trình trên là: 212KB, 417KB, 112KB, 426KB. Hãy cấp phát bộ nhớ cho các 
tiến trình trên theo thuật toán First-fit, Best-first, Worst-fit. 
Giải 
P4 chờ 
2./ (đề kiểm tra) Trong mô hình cấp phát bộ nhới liên tục, có 5 phân mảnh bộ 
nhớ với kích thước là 200KB, 400KB, 600KB, 300KB, 500KB. Giả sử có 4 tiến 
trình đang chờ cấp phát bộ nhớ theo thứ tự P1, P2, P3, P4. Kích thước tương ứng 
các tiến trình trên là: 220KB, 250KB, 550KB, 320KB. 
Hãy cấp phát bộ nhớ cho các tiến trình trên theo thuật toán First – fit và Best – 
fit. 
Giải 
Chú ý: - First – fit :tìm vùng nhớ đầu tiên đủ lớn để chứa tiến trình 
- Best – fit: tìm vùng nhớ nhỏ nhất mà có thể chứa tiến trình 
- Worst – fit:tìm vùng nhớ lớn nhất cấp cho tiến trình. 
**** - Câu 1 - **** 
Giải thích sự khác biệt giữa địa chỉ logic và địa chỉ physic? 
- Địa chỉ 
logic (logic address): là vị trí nhớ được diễn tả trong một chương 
trình. Mọi tham chiếu bộ nhớ trong mã lệnh chương trình được compiler 
tạo ra đều là địa chỉ logic. 
- 
Địa chỉ vật lý (physic address): là một địa chỉ thực trong bộ nhớ 
chính. Địa chỉ vật lý được chuyển từ địa chỉ logic khi trình biên dịch 
thức j hiện quá trình linking/loading. 
**** - Câu 2 - **** 
Giải thích sự khác biệt giữa hiện tượng phân mảnh nội vi và ngoại vi? 
- 
Phân mảnh ngoại (external fragmentation): là hiện tượng khi kích thước 
không gian nhớ còn trống đủ để thỏa mãn yêu cầu cấp phát nhưng không 
gian nhớ này lại không liên tục. 
Hiện tượng phân mảnh ngoại xảy ra khi bạn thường xuyên cấp phát vùng 
nhớ mới, sau đó xóa đi những phần vùng nhớ đã cấp phát một cách không 
thứ tự. 
- 
Phân mảnh nội (internal fragmentation): là hiện tượng sẽ có vùng nhớ dư 
thừa khi ta cấp phát một vùng nhớ hơi lớn hơn kích thước yêu cầu. 
Ví dụ: Cấp một khoảng trống 18,464 bytes cho một process yêu cầu 18,462 bytes 
Hiện tượng phân mảnh nội thường xảy ra khi bộ nhớ thực được chia thành 
các khối kích thước cố định (fixed-sized block) và các process được cấp 
phát theo đơn vị khối. 
**** - Câu 3 - **** 
Giả sử bộ nhớ chính được phân thành các vùng có kích thước 600K, 500K, 
200K, 300K (theo thứ tự), cho biết các tiến trình có kích thước 212K, 
417K, 112K, 426K (theo thứ tự) sẽ được cấp phát bộ nhớ như thế nào nếu 
sử dụng: 
 a/ Thuật toán First fit: 
 b/ Thuật toán Best fit: 
 c/ Thuật toán Worst fit: 
 Theo ta thấy, thuật toán Best fit thực hiện tốt việc phân phối bộ nhớ cho các process 
nhất!!! 
**** - Câu 4 - **** 
Xét một hệ thống trong đó một chương trình khi được nạp vào bộ nhớ sẽ phân biệt hoàn 
toàn phân đoạn code và phân đoạn data. Giả sử CPU sẽ xác định được khi nào cần truy 
xuất lệnh hay dữ liệu, và phải truy xuất ở đâu. Khi đó, mỗi chương trình sẽ được cung 
cấp 2 bộ thanh ghi base-limit: một cho phân đoạn code, và một cho phân đoạn data. Bộ 
thanh ghi base-limit của phân đoạn code tự động được đặt thuộc tính readonly. Thảo luận 
các ưu khuyết điểm của hệ thống này. 
**** - Câu 5 - **** 
Tại sao kích thước trang luôn là lũy thừa của 2? 
- Kích thước trang được định nghĩa bởi phần cứng. Kích thước của một trang điển 
hình là lũy thừa của 2, từ 512 bytes đến 16MB trên trang, tùy thuộc vào kiến trúc 
máy tính. Chọn lũy thừa 2 cho kích thước trang để thực hiện việc dịch địa chỉ luận 
lý thành số trang và độ dời trang rất dễ dàng. 
**** - Câu 6 - **** 
Xét một không gian địa chỉ có 8 trang, mỗi trang có kích thước 1K, ánh xạ vào bộ 
nhớ vật lý có 32 khung trang. 
 a/ Địa chỉ logic: 
 – Không gian địa chỉ có 8 trang, vậy ta giả sử có một bảng trang (page table) gồm 
8 mục. 
 – Mỗi trang có kích thước 1K=2^10 byte, như vậy ta sẽ cần 10 bit để quản lý 
phần địa chỉ tương đối trong trang (page – offset). Bảng trang gồm 8 mục ta sẽ cần 
đến 3 bit để quản lý! 
 => như vậy địa chỉ logic gồm có page number + page offset = 3 + 10 = 13 bit 
 b/ Địa chỉ vật lý: 
 – Bộ nhớ vật lý có 32 khung trang, như vậy ta cần 5 bit để quản lý nó (2^5=32). 
 – Thêm với 10 bit offset cho việc quản lý phần địa chỉ tương đối trong trang. 
 => địa chỉ vật lý bao gồm 5 + 10 = 15 bit 
**** - Câu 7 - **** 
Tại sao trong hệ thống sử dụng kỹ thuật phân trang, một tiến trình không thể truy 
xuất đến vùng nhớ không được cấp cho nó? 
Làm cách nào để hệ điều hành có thể cho phép sự truy xuất này xảy ra? Hệ điều 
hành có nên cho phép điều đó không? Tại sao? 
 Phân trang là cơ chế quản lý bộ nhớ cho phép không gian địa chỉ vật lý của quá 
trình là không kề nhau. Phân trang tránh vấn đề đặt vừa khít nhóm bộ nhớ có kích 
thước thay đổi vào vùng lưu trữ phụ (backing store) mà hầu hết các cơ chế quản lý 
bộ nhớ trước đó gặp phải. Khi phân đoạn mã và dữ liệu nằm trong bộ nhớ được 
hoán vị ra, không gian phải được tìm thấy trên vùng lưu trữ phụ. 
 Bộ nhớ vật lý được chia thành các khối có kích thước cố định gọi là các khung 
(frames). Bộ nhớ luận lý cũng được chia thành các khối có cùng kích thước gọi là 
các trang (pages). Khi một quá trình được thực thi, các trang của nó được nạp vào 
các khung bộ nhớ sẵn dùng từ vùng lưu trữ phụ. Vùng lưu trữ phụ được chia thành 
các khối có kích thước cố định và có cùng kích thước như các khung bộ nhớ. 
 Phân trang là một dạng của tái định vị động. Mỗi địa chỉ luận lý được giới hạn 
bởi phần cứng phân trang tới địa chỉ vật lý. Sử dụng phân trang tương tự sử dụng 
một bảng các thanh ghi nền (hay tái định vị), một thanh ghi cho mỗi khung bộ nhớ. 
 Một khía cạnh quan trọng của phân trang là sự phân chia rõ ràng giữa tầm nhìn 
bộ nhớ của người dùng và bộ nhớ vật lý thực sự. Chương trình người dùng nhìn bộ 
nhớ như một không gian liên tục, chứa chỉ một chương trình. Sự thật, chương trình 
người dùng được phân bố khắp bộ nhớ vật lý và nó cũng quản lý các quá trình 
khác. Sự khác nhau giữa tầm nhìn bộ nhớ của người dùng và bộ nhớ vật lý thực sự 
được làm cho tương thích bởi phần cứng dịch địa chỉ. Địa chỉ luận lý được dịch 
thành địa chỉ vật lý. Ánh xạ này được che giấu từ người dùng và được điều khiển 
bởi hệ điều hành. 
 Như vậy, quá trình người dùng không thể truy xuất bộ nhớ mà nó không sở hữu. 
Không có cách định địa chỉ bộ nhớ bên ngoài bảng trang của nó và bảng chỉ chứa 
những trang mà quá trình sở hữu.