Bài giảng Kỹ thuật Máy tính - Chương 10: Kỹ thuật phân mảnh bộ nhớ - Nguyễn Thanh Sơn

Nội dung text: Bài giảng Kỹ thuật Máy tính - Chương 10: Kỹ thuật phân mảnh bộ nhớ - Nguyễn Thanh Sơn

1. Nội dung Có 2 kỹ thuật chính:  Kỹ thuật phân trang (paging)  Kỹ thuật phân đoạn (segmentation)  Kỹ thuật kết hợp BK TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 2
2. Kỹ thuật phân trang (tt.)  Frame và trang nhớ có kích thước bằng nhau.  Hệ điều hành phải thiết lập một bảng phân trang (page table) để ánh xạ địa chỉ luận lý thành địa chỉ thực  Mỗi process có một bảng phân trang, được quản lý qua một con trỏ lưu giữ trong PCB.  Thiết lập bảng phân trang cho process là một phần của chuyển ngữ cảnh  Kỹ thuật phân trang khiến bộ nhớ bị phân mảnh nội, nhưng khắc phục được phân mảnh ngoại. BK TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 4
3. Chuyển đổi địa chỉ trong paging  Địa chỉ luận lý gồm có:  Page number, p, được dùng làm chỉ mục vào bảng phân trang. Mỗi mục (entry) trong bảng phân trang chứa chỉ số frame (còn gọi là số frame cho gọn) của trang tương ứng trong bộ nhớ thực.  Page offset, d, được kết hợp với địa chỉ nền (base address) của frame để định vị địa chỉ thực. m n  Nếu kích thước của không gian địa chỉ ảo là 2 , và kích thước của trang là 2 (byte hay word tùy theo kiến trúc máy) page number page offset p d m n bit n bit (định vị từ 0  2m n 1) (định vị từ 0  2n 1) BK m n m n TP.HCM Bảng phân trang sẽ có tổng cộng2 /2 = 2 mục Khoa Khoa học & Kỹ thuật Máy tính 6
4. Chuyển đổi địa chỉ nhớ trong paging  Ví dụ: BK TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 8
5. Associative register (hardware)  hay TLB, là thanh ghi hỗ trợ tìm kiếm truy xuất dữ liệu với tốc độ cực nhanh. Số mục của TLB Page # Frame # khoảng 8  2048 TLB là “cache” của bảng phân trang Khi có chuyển ngữ cảnh, TLB bị xóa Khi TLB đầy, thay thế mục dùngLRU Ánh xạ page #  Nếu page number nằm trong TLB (: hit, trúng) lấy ngay được số frame tiết kiệm được thời gian truy cập bộ nhớ chính để lấy số frame trong bảng phân trang.  Ngược lại (: miss, trật), phải lấy số frame từ bảng phân trang như bình thường. BK TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 10
6. Effective access time (EAT) Tính thời gian truy xuất hiệu dụng (EAT)  Thời gian tìm kiếm trong TLB (associative lookup):   Thời gian một chu kỳ truy xuất bộ nhớ: x  Hit ratio: tỉ số giữa số lần chỉ số trang được tìm thấy (hit) trong TLB và số lần truy xuất khởi nguồn từ CPU  Kí hiệu hit ratio:  Thời gian cần thiết để có được địa chỉ thực  Khi chỉ số trang có trong TLB (hit) ε + x  Khi chỉ số trang không có trong TLB (miss) ε + x + x  Thời gian truy xuất hiệu dụng EAT = ( + x) + ( + 2x)(1 – ) = (2 – )x +  BK TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 12
7. Bảo vệ bộ nhớ  Việc bảo vệ bộ nhớ được hiện thực bằng cách gắn với frame các bit bảo vệ (protection bit) được giữ trong bảng phân trang. Các bit này biểu thị các thuộc tính sau  read-only, read-write, execute-only  Ngoài ra, còn có mộtvalid/invalid bit gắn với mỗi mục trong bảng phân trang  “valid”: cho biết là trang của process, do đó là một trang hợp lệ.  “invalid”: cho biết là trang không của process, do đó là một trang bất hợp lệ. BK TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 14
8. Bảng phân trang 2 mức  Các hệ thống hiện đại đều hỗ trợ không gian địa chỉ ảo rất lớn (232 đến 264), ở đây giả sử là 232 12  Giả sử kích thước trang nhớ là 4 KB (= 2 ) bảng phân trang sẽ có 232/212 = 220 = 1 M mục.  Giả sử mỗi mục gồm 4 byte thì mỗi process cần 4 MB cho bảng phân trang   Một giải pháp là, thay vì dùng một bảng phân trang duy nhất cho mỗi process, “paging” bảng phân trang này, và chỉ giữ những bảng phân trang cần thiết trong bộ nhớ bảng phân trang 2 mức (two-level page table). BK TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 16
9. Bảng phân trang 2-mức (tt.) Minh họa . Có 2p1 mục trong bảng phân trang mức 1 . Mỗi bảng phân trang mức 2 chứa 2p2 mục BK TP.HCM các bảng phân trang mức2 Khoa Khoa học & Kỹ thuật Máy tính 18
10. Bảng phân trang 2 mức (tt.)  Bảng phân trang 2 mức giúp tiết kiệm bộ nhớ:  Vùng màu đỏ tương ứng với phần chưa được sử dụng của không gian địa chỉ ảo. Các mục màu đỏ được đánh dấu là không có frame nên sẽ gây ra page fault nếu được tham chiếu đến; khi đó OS sẽ tạo thêm bảng phân trang mức 2 mới. BK TP.HCM Fig from Gottlieb Khoa Khoa học & Kỹ thuật Máy tính 20
11. Bảng phân trang băm  Dùng kỹ thuật băm để giảm không gian bảng phân trang  Phổ biến trong các hệ thống có địa chỉ lớn hơn 32 bit.  Để giải quyết đụng độ, mỗi mục của bảng băm được gắn một danh sách liên kết. Mỗi phần tử của danh sách là một cặp (chỉ số trang ảo, chỉ số frame).  Chỉ số trang ảo (virtual page number) được biến đổi qua hàm băm thành một hashed value. Cặp (chỉ số trang ảo, chỉ số frame) sẽ được lưu vào danh sách liên kết tại mục có chỉ số là hashed value.  Giải thuật tìm trang:  Chỉ số trang ảo được biến đổi thành hashed value. Hashed value là chỉ số của mục cần truy cập trong bảng băm. Sau đó, tìm trong danh sách liên kết phần tử chứa chỉ số trang ảo để trích ra được chỉ số frame tương ứng. BK TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 22
12. Chia sẻ các trang nhớ 0 ed 1 0 3 1 data 1 ed 2 1 4 2 data 3 6 ed 3 2 3 ed 1 3 1 ed 1 4 ed 2 data 1 0 3 ed 2 1 4 5 Process 1 2 6 6 ed 3 ed 3 ed 1 3 7 7 data 2 0 3 data 2 8 ed 2 4 1 Process 2 9 ed 2 2 6 2 10 data 3 3 BK Process 3 TP.HCM Bộ nhớ thực Khoa Khoa học & Kỹ thuật Máy tính 24
13. Chương trình: user view  Thông thường, một chương trình được biên dịch. Trình biên dịch sẽ tự động xây dựng các segment. stack procedure  Ví dụ, trình biên dịch Pascal sẽ tạo ra các segment sau: symbol table  Global variables function sqrt  Procedure call stack main program  Procedure/function code  Local variable  Trình loader sẽ gán mỗi segment một số định danh riêng. BK TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 26
14. Phân đoạn (tt.) logical address space physical memory space segment 1 segment 2 segment 3 segment 4 BK TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 28
15. Một ví dụ về phân đoạn stack 1400 procedure procedure 2400 segment 3 limit base 0 1000 1400 segment 0 3200 symbol 1 400 6300 table stack 2 400 4300 function 4300 segment 4 3 1100 3200 main sqrt 4 1000 4700 main program 4700 segment symbol table segment 1 table segment 2 5700 6300 function sqrt logical address space BK physical memory space TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 30
16. Chuyển đổi địa chỉ trong kỹ thuật phân đoạn  Ví dụ BK TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 32
17. Kết hợp phân trang và phân đoạn  Kết hợp phân trang và phân đoạn nhằm tận dụng các ưu điểm và hạn chế các khuyết điểm của chúng:  Vấn đề của phân đoạn: một đoạn có thể không nạp được vào bộ nhớ do phân mảnh ngoại, mặc dù đủ không gian trống.  Ý tưởng giải quyết: paging đoạn, cho phép các page của đoạn được nạp vào các frame không cần nằm liên tục nhau. BK TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 34
18. Segmentation with paging  Minh họa frame 0 frame 1 frame 2 frame 3 frame 4 frame 5 frame 6 BK TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 36
19. Segmentation with paging (tt.)  Segment base: địa chỉ thực của bảng phân trang  Present bit và modified bit chỉ tồn tại trong bảng phân trang  Các thông tin bảo vệ và chia sẻ vùng nhớ thường nằm trong bảng phân đoạn  Ví dụ: read-only/read-write bit, BK TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 38