Bài Tập Hệ Điều Hành - Chương 3: Phân Trang và Cấp Phát Bộ Nhớ

BÀI TẬP PHÂN TRANG
1. (Bài tập mẫu) Xét một không gian địa chỉ có 12 trang, mỗi trang có kích thước
2K, ánh xạ vào bộ nhớ vật lý có 32 khung trang.
a. Địa chỉ logic gồm bao nhiêu bit?
b. Địa chỉ physic gồm bao nhiêu bit? Trả lời:
a. Địa chỉ logic gồm 2 phần: chỉ số trang và độ dời (offset) trong trang. Cần 4 bit để
biểu diễn chỉ số trang và 11 bit (211 = 2K = 2048) để biểu diễn độ dời trong trang.
Vậy địa chỉ logic gồm 15 bit.
b. Thực hiện tương tự. Địa chỉ physic gồm 16 bit.
2. (Bài tập mẫu) Xét một hệ thống sử dụng kỹ thuật phân trang, với bảng trang đđược
lưu trữ trong bộ nhớ chính.
a. Nếu thời gian cho một lần truy xuất bộ nhớ bình thường (memory reference) là
200ns thì mất bao nhiêu thời gian cho một thao tác truy xuất bộ nhớ (paged
memory reference) trong hệ thống này?
b. Nếu sử dụng TLBs với hit-ratio là 75%, thời gian để tìm trong TLBs xem như
bằng 0, tính thời gian truy xuất bộ nhớ (effective access time) trong hệ thống? Trả lời:
a. Mỗi thao tác truy xuất bộ nhớ trong hệ thống này sẽ cần thực hiện 2 lần truy xuất
bộ nhớ thông thường: truy xuất bảng trang ( để xác định vị trí khung trang) và truy
xuất vị trí bộ nhớ (xác định dựa trên sự kết hợp giá trị khung trang tìm đđược ở
lần trước với độ dời trong trang).
Do đó thời gian của một thao tác truy xuất bộ nhớ sẽ là 200*2 = 400ns.
b. Thời gian truy xuất bộ nhớ (effective access time) trong hệ thống:
EAT = (2 – α)x + ε = 250 ns.
3. Một máy tính 32-bit địa chỉ, sử dụng một bảng trang 2 cấp. Địa chỉ ảo đđược phân
bổ như sau: 9 bit dành cho bảng trang cấp 1, 11 bit cho bảng trang cấp 2 và còn lại cho
offset. Cho biết kích thước một trang trong hệ thống và địa chỉ ảo có bao nhiêu trang?
4. Giả sử địa chỉ ảo 32-bit đđược phân tách thành 4 trường a, b, c, d. 3 trường đầu tiên
đđược dùng cho bảng trang 3 cấp, trường thứ 4 dành cho offset. Số lượng trang có phụ
thuộc vào kích thước của cả 4 trường này không? Nếu không, những trường nào ảnh
hưởng đến số lượng trang, những trường nào không ảnh hưởng?
5. (Bài tập mẫu) Cho bảng trang như hình bên. 0 6
a. Địa chỉ vật lý 6568 sẽ đđược chuyển thành địa chỉ ảo bao nhiêu? Biết rằng 1 4 2 5
kích thước mỗi frame là 1K bytes. 3 7
b. Địa chỉ ảo 3254 sẽ đđược chuyển thành địa chỉ vật lý bao nhiêu? Biết rằng 4 1
kích thước mỗi frame là 2K bytes. 5 9 Trả lời: a.
Địa chỉ vật lý 6568 nằm ở khung trang 6 với độ dời 424. Trang 0 đđược nạp
vào khung trang 6 => Địa chỉ ảo là 424. b.
Địa chỉ 3254 nằm ở trang 1 với độ dời 1206. Trang 1 đđược nạp vào khung
trang 4 => Địa chỉ vật lý là 9398.
6. Xét một hệ thống sử dụng kỹ thuật phân trang, với bảng trang đđược lưu trữ trong bộ nhớ chính.
a. Nếu thời gian cho một lần truy xuất bộ nhớ bình thường là 124 nanoseconds,
thì mất bao nhiêu thời gian cho một thao tác truy xuất bộ nhớ trong hệ thống này?
b. Nếu sử dụng TLBs với hit-ratio (tỉ lệ tìm thấy) là 95%, thời gian để tìm trong
TLBs bằng 34ns, tính thời gian cho một thao tác truy xuất bộ nhớ trong hệ thống
(effective memory reference time).
7. Xét một hệ thống sử dụng kỹ thuật phân trang, với bảng trang đđược lưu trữ trong
bộ nhớ chính. Nếu sử dụng TLBs với hit-ratio (tỉ lệ tìm thấy) là 87%, thời gian để tìm
trong TLBs là 24 ns. Thời gian truy xuất bộ nhớ trong hệ thống (effective memory
reference time) là 175ns. Tính thời gian cho một lần truy xuất bộ nhớ bình thường?
8. Biết thời gian truy xuất trong bộ nhớ thường không sử dụng TLBs là 250ns. Thời
gian tìm kiếm trong bảng TLBs là 26ns. Hỏi xác suất tìm thấy trong TLBs bằng bao
nhiêu nếu thời gian truy xuất trong bộ nhớ chính là 182ns?
9. Xét một không gian địa chỉ có 8 trang, mỗi trang có kích thước 1KB. Ánh xạ vào
bộ nhớ vật lý có 32 khung trang.
a) Địa chỉ luận lý (logical address) gồm bao nhiêu bit?
b) Địa chỉ vật lý (physical address) gồm bao nhiêu bit?
c) Bảng trang có bao nhiêu mục? Mỗi mục trong bảng trang cần bao nhiêu bit? Trả lời: a) 13 bits
Địa chỉ luận lý gồm 2 vùng p và d: Vùng p cho biết biết dữ liệu đang ở trang (page)
nào, vùng d cho biết trong trang đó, dữ liệu ở vị trí nào. p d
Đề cho 8 trang (23 = 8) ⟶ Cần 3 bits cho vùng p
Mỗi trang có kích thước 1KB = 1024 bytes (210 = 1024) ⟶ Cần 10 bits cho vùng d
Địa chỉ luận lý cần 3 + 10 = 13 bits b) 15 bits
Địa chỉ vật lý gồm 2 vùng f và d: Vùng f cho biết biết dữ liệu đang ở khung trang
(frame) nào, vùng d cho biết trong khung trang đó, dữ liệu ở vị trí nào. f d
Đề cho 32 khung trang (25 = 32) ⟶ Cần 5 bits cho vùng f.
Mỗi trang có kích thước 1KB ⟶ Mỗi frame cũng có kích thước 1KB ⟶ Cần 10 bits cho vùng d
⇨ Địa chỉ luận lý cần 5 + 10 = 15 bits
10. Cho bảng phân trang (bảng ánh xạ) của một process như hình, hãy cho biết a) Địa 0 6 chỉ 1 4 vật
lý 6578 sẽ đđược chuyển thành địa chỉ luận lý bao nhiêu? Biết rằng kích thước mỗi frame là 1 KB
b) Địa chỉ luận lý 3654 sẽ đđược chuyển thành địa chỉ vật lý bao nhiêu? Biết rằng
kích thước mỗi frame là 2 KB Trả lời:
a) Tìm địa chỉ luận lý tương ứng của địa chỉ vật lý 6578 6578(10) = 100110110010(2) Địa chỉ luận lý: p d Địa chỉ vật lý: f d
Kích thước mỗi frame là 1 KB (mỗi page cũng là 1 KB) ⟶ vùng d trong địa chỉ luận lý và vật lý là 10 bits
➔ Địa chỉ vật lý 1100110110010 đang ở frame 110(2) = 6(10)
Tra vào bảng phân trang, frame 6 đang tương ứng với page 0
➔ Địa chỉ luận lý sẽ là (vùng d của vật lý và luận lý giữ nguyên):
00110110010(2) = 434(10)
b) Chuyển địa chỉ luận lý 3654 thành địa chỉ vật lý 3654(10) = 111001000110(2) Địa chỉ luận lý: p d Địa chỉ vật lý: f d
Kích thước mỗi frame là 2 KB (Mỗi page cũng là 2 KB) ⟶ vùng d trong địa chỉ luận lý và vật lý là 11 bits
➔ Địa chỉ luận lý 111001000110 đang ở page 1
Tra vào bảng phân trang, tìm đến phần tử/mục thứ 1 của bảng phân trang ⟶
thấy 4, tức page 1 trong bộ nhớ luận lý đang được lưu ở frame 4.
➔ Địa chỉ vật lý sẽ là (vùng d của vật lý và luận lý giữ nguyên):
10011001000110(2) = 9798(10)
BÀI TẬP PHÂN VÙNG CÁC CHIẾN LĐƯỢC CẤP PHÁT BỘ NHỚ
1. Giả sử bộ nhớ chính đđược cấp phát thành các phân vùng có kích thước là
600K, 500K, 200K, 300K (theo thứ tự). 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 (theo thứ tự) sẽ đđược cấp phát bộ nhớ
như thế nào, nếu sư dụng: Thuật toán First fit, Best fit, Next fit, Worst fit?
Thuật toán nào cho phép sử dụng bộ nhớ hiệu quả nhất trong trường hợp trên? Lời giải chi tiết:
a. Xét trường hợp bộ nhớ đđược phân vùng cố định: • First fit:
Tiến trình 212K sẽ được cấp phát vùng nhớ 600K.
Tiến trình 417K sẽ được cấp phát vùng nhớ 500K.
Tiến trình 112K sẽ được cấp phát vùng nhớ 200K.
Tiến trình 426K sẽ phải chờ vì không còn vùng nhớ trống thỏa yêu cầu. • Best fit:
Tiến trình 212K sẽ được cấp phát vùng nhớ 300K.
Tiến trình 417K sẽ được cấp phát vùng nhớ 500K.
Tiến trình 112K sẽ được cấp phát vùng nhớ 200K.
Tiến trình 426K sẽ được cấp phát vùng nhớ 600K. • Next fit:
Tiến trình 212K sẽ được cấp phát vùng nhớ 600K.
Tiến trình 417K sẽ được cấp phát vùng nhớ 500K.
Tiến trình 112K sẽ được cấp phát vùng nhớ 200K.
Tiến trình 426K sẽ phải chờ vì không còn vùng nhớ trống thỏa yêu cầu. • Worst fit:
Tiến trình 212K sẽ được cấp phát vùng nhớ 600K.
Tiến trình 417K sẽ được cấp phát vùng nhớ 500K.
Tiến trình 112K sẽ được cấp phát vùng nhớ 300K.
Tiến trình 426K sẽ phải chờ vì không còn vùng nhớ trống thỏa yêu cầu.
b. Xét trường hợp bộ nhớ được phân vùng động: • First fit:
Tiến trình 212K sẽ được cấp phát vùng nhớ 600K => Vùng nhớ trống 388K.
Tiến trình 417K sẽ được cấp phát vùng nhớ 500K.
Tiến trình 112K sẽ được cấp phát vùng nhớ 388K.
Tiến trình 426K sẽ phải chờ vì không còn vùng nhớ trống thỏa yêu cầu. • Best fit:
Tiến trình 212K sẽ được cấp phát vùng nhớ 300K.
Tiến trình 417K sẽ được cấp phát vùng nhớ 500K.
Tiến trình 112K sẽ được cấp phát vùng nhớ 200K.
Tiến trình 426K sẽ được cấp phát vùng nhớ 600K. • Next fit:
Tiến trình 212K sẽ được cấp phát vùng nhớ 600K.
Tiến trình 417K sẽ được cấp phát vùng nhớ 500K.
Tiến trình 112K sẽ được cấp phát vùng nhớ 200K.
Tiến trình 426K sẽ phải chờ vì không còn vùng nhớ trống thỏa yêu cầu. • Worst fit:
Tiến trình 212K sẽ được cấp phát vùng nhớ 600K. => Vùng nhớ trống 388K.
Tiến trình 417K sẽ được cấp phát vùng nhớ 500K.
Tiến trình 112K sẽ được cấp phát vùng nhớ 388K.
Tiến trình 426K sẽ phải chờ vì không còn vùng nhớ trống thỏa yêu cầu.
2. Giả sử bộ nhớ chính đđược cấp phát thành các phân vùng có kích thước là
580K, 500K, 200K, 300K (theo thứ tự). 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 (theo thứ tự) sẽ đđược cấp phát bộ nhớ
như thế nào, nếu sư dụng:
Thuật toán First fit, Best fit, Next fit, Worst fit, Last-fit.
Thuật toán nào cho phép sử dụng bộ nhớ hiệu quả nhất trong trường hợp trên?
3. Cho 6 phân vùng bộ nhớ có thứ tự và kích thước lần lượt là 300KB, 600 KB.
350 KB, 200 KB, 750 KB, 125 KB và 6 tiến trình có thứ tự và kích thước lần
lượt là 115 KB, 500 KB, 358 KB, 200 KB, 375 KB, 320 KB.
Hãy cấp phát bộ nhớ cho các tiến trình trên lần lượt theo các thuật toán first fit,
best fit, và worst fit từ đó hãy cho biết thuật toán nào cho phép sử dụng bộ nhớ
hiệu quả nhất trong trường hợp trên?
4. Cho 4 phân vùng bộ nhớ có thứ tự và kích thước lần lượt là 480KB, 450 KB.
250 KB, 300 KB và 4 tiến trình có thứ tự và kích thước lần lượt là 255 KB, 435 KB, 215 KB, 452 KB.
Hãy cấp phát bộ nhớ cho các tiến trình trên lần lượt theo các thuật toán first fit,
best fit, và worst fit từ đó hãy cho biết thuật toán nào cho phép sử dụng bộ nhớ
hiệu quả nhất trong trường hợp trên?
Document Outline

• BÀI TẬP PHÂN TRANG
• BÀI TẬP PHÂN VÙNG CÁC CHIẾN LĐƯỢC CẤP PHÁT BỘ NHỚ