Bài giảng Hệ điều hành - Chương 7: Paging

Nội dung text: Bài giảng Hệ điều hành - Chương 7: Paging

1. Effective access time (EAT) Tính thời gian truy xuất hiệu dụng (effective access time, 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 chỉ số frame – 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 +  Khoa Công Nghệ Thông Tin, Đại Học Bách Khoa TP HCM 9.11
2. Effective access time (tt) ❑ Ví dụ 1: đơn vị thời gian ❑ Ví dụ 2 nano giây ▪ Associative lookup = 20 ▪ Associative lookup = 20 ▪ Memory access = 100 ▪ Memory access = 100 ▪ Hit ratio = 0.98 ▪ Hit ratio = 0.8 ▪ EAT = (100 + 20) 0.98 + ▪ EAT = (100 + 20) 0.8 + (200 + 20) 0.02 (200 + 20) 0.2 = 1.02 100 + 20 = 1.2 100 + 20 = 122 = 140 Khoa Công Nghệ Thông Tin, Đại Học Bách Khoa TP HCM 9.12
3. 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 bits) đượ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ột valid/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ệ. Khoa Công Nghệ Thông Tin, Đại Học Bách Khoa TP HCM 9.13
4. Bảo vệ bằng valid/invalid bit 00000 frame valid/ 0 number invalid bit 1 0 2 v 2 page 0 1 3 v 3 page 1 2 4 v 4 page 2 3 7 v 5 4 8 v 6 10468 12287 5 9 v 7 page 3 6 0 i 8 page 4 9 page 5 7 0 i  Mỗi trang nhớ có kích thước 2K = 2048 page n  Process có kích thước 10,468 phân mảnh nội ở frame 9 (chứa page 5), các địa chỉ ảo > 12287 là các địa chỉ invalid.  Dùng PTLR để kiểm tra truy xuất đến bảng phân trang có nằm trong bảng hay không. Khoa Công Nghệ Thông Tin, Đại Học Bách Khoa TP HCM 9.14
5. 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 – Giả sử kích thước trang nhớ là 4KB (= 212) bảng phân trang sẽ có 232/212 = 220 = 1M mục. – Giả sử mỗi mục gồm 4 byte thì mỗi process cần 4MB 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). Khoa Công Nghệ Thông Tin, Đại Học Bách Khoa TP HCM 9.15
6. Bảng phân trang 2-mức (tt) Ví dụ ❑ Một địa chỉ luận lý trên hệ thống 32-bit với trang nhớ 4K được chia thành các phần sau: – Page number: 20 bit page number offset ▪ Nếu mỗi mục dài 4 byte Cần 220 4 byte = 4 MB cho mỗi page table 20 bit 12 bit – Page offset: 12 bit ❑ Bảng phân trang cũng được chia nhỏ nên page number cũng được chia nhỏ thành 2 phần: page offset – 10-bit page number p p d – 10-bit page offset 1 2 10 bit 10 bit 12 bit ❑ Vì vậy, một địa chỉ luận lý sẽ như hình vẽ bên p1 : chỉ số của trang trong bảng phân trang mức 1 (outer-page table) p2 : chỉ số của trang trong bảng phân trang mức 2 Khoa Công Nghệ Thông Tin, Đại Học Bách Khoa TP HCM 9.16
7. 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 các bảng phân trang mức 2 Khoa Công Nghệ Thông Tin, Đại Học Bách Khoa TP HCM 9.17
8. Bảng phân trang 2 mức (tt) ❑ Sơ đồ chuyển đổi địa chỉ (address-translation scheme) cho cơ chế bảng phân trang 2 mức, 32-bit địa chỉ page table mức 2 Khoa Công Nghệ Thông Tin, Đại Học Bách Khoa TP HCM 9.18
9. 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 không đượ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. Khoa Công Nghệ Thông Tin, Đại Học Bách Khoa TP HCM 9.19
10. Bảng phân trang đa mức ❑ Ví dụ: Không gian địa chỉ luận lý 64-bit với trang nhớ 4K – Bảng phân trang 2-mức vẫn còn quá lớn! Tương tự bảng phân trang 2 mức, ta có bảng phân trang 3, 4, , n mức page number page offset page numbers page offset 52 12 42 10 12 page numbers page offset page numbers page offset 32 10 10 12 22 10 10 10 12 ❑ Tiết kiệm chổ trong bộ nhớ chính bằng cách chỉ giữ trong bộ nhớ chính các bảng phân trang mà process hiện đang cần. Khoa Công Nghệ Thông Tin, Đại Học Bách Khoa TP HCM 9.20
11. Bảng phân trang băm (hashed page table) ❑ Dùng bảng băm để giảm không gian bảng phân trang – Rất phổ biến trong các hệ thống lớn hơn 32 bit địa chỉ. ❑ Để 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 (với cùng hàm băm như trên). 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. Khoa Công Nghệ Thông Tin, Đại Học Bách Khoa TP HCM 9.21
12. Hashed page table (tt) danh sách các cặp (chỉ số trang ảo, chỉ số frame) Khoa Công Nghệ Thông Tin, Đại Học Bách Khoa TP HCM 9.22
13. Chia sẻ các trang nhớ Process 1 0 ed 1 0 3 1 data 1 ed 2 1 4 2 data 3 6 Process 2 ed 3 2 3 ed 1 3 1 ed 1 4 ed 2 data 1 0 3 ed 2 1 4 5 2 6 6 ed 3 ed 3 ed 1 3 7 7 data 2 0 3 data 2 8 ed 2 1 4 9 ed 2 2 6 2 10 data 3 3 Process 3 Bộ nhớ thực Khoa Công Nghệ Thông Tin, Đại Học Bách Khoa TP HCM 9.23
14. Phân đoạn (segmentation) ❑ Nhìn lại cơ chế phân trang – user view (không gian địa chỉ ảo) tách biệt với không gian bộ nhớ thực. Cơ chế phân trang thực hiện phép ánh xạ user-view vào bộ nhớ thực. ❑ Trong thực tế, dưới góc nhìn của user, một chương trình cấu thành từ nhiều đoạn (segment). Mỗi đoạn là một đơn vị luận lý của chương trình, như – main program, procedure, function – local variables, global variables, common block, stack, symbol table, arrays, Khoa Công Nghệ Thông Tin, Đại Học Bách Khoa TP HCM 9.24
15. User view của một chương trình ❑ Thông thường, một chương trình được biên dịch. Trình biên dịch stack sẽ tự động xây dựng các procedure segment. symbol ❑ Ví dụ, trình biên dịch Pascal sẽ table tạo ra các segment sau: function sqrt – Global variables main program – Procedure call stack – Procedure/function code – Local variable ❑ Trình loader sẽ gán mỗi segment một số định danh riêng. Logical address space Khoa Công Nghệ Thông Tin, Đại Học Bách Khoa TP HCM 9.25
16. Phân đoạn ❑ Dùng cơ chế phân đoạn để quản lý bộ nhớ có hỗ trợ user view – Không gian địa chỉ ảo là một tập các đoạn, mỗi đoạn có tên và kích thước riêng. – Một địa chỉ luận lý được định vị bằng tên đoạn và độ dời (offset) bên trong đoạn đó (so sánh với phân trang!) Khoa Công Nghệ Thông Tin, Đại Học Bách Khoa TP HCM 9.26
17. Phân đoạn (tt) logical address space physical memory space segment 1 segment 2 segment 3 segment 4 Khoa Công Nghệ Thông Tin, Đại Học Bách Khoa TP HCM 9.27
18. Hiện thực phân đoạn ❑ Địa chỉ luận lý là một cặp giá trị (segment number, offset) ❑ Bảng phân đoạn (segment table): gồm nhiều mục, mỗi mục chứa – base, chứa địa chỉ khởi đầu của segment trong bộ nhớ – limit, xác định kích thước của segment ❑ Segment-table base register (STBR): trỏ đến vị trí bảng phân đoạn trong bộ nhớ ❑ Segment-table length register (STLR): số lượng segment của chương trình Một chỉ số segment s là hợp lệ nếu s < STLR Khoa Công Nghệ Thông Tin, Đại Học Bách Khoa TP HCM 9.28
19. Một ví dụ về phân đoạn stack 1400 procedure procedure segment 3 limit base 2400 segment 0 0 1000 1400 symbol 3200 table 1 400 6300 stack 2 400 4300 function segment 4 sqrt 4300 3 1100 3200 main main program 4 1000 4700 4700 segment 1 segment symbol table segment 2 table 5700 6300 function sqrt logical address space physical memory space Khoa Công Nghệ Thông Tin, Đại Học Bách Khoa TP HCM 9.29
20. Phần cứng hỗ trợ phân đoạn segment s table limit base CPU s d yes physical + memory no trap; addressing error Khoa Công Nghệ Thông Tin, Đại Học Bách Khoa TP HCM 9.30
21. Chuyển đổi địa chỉ trong cơ chế phân đoạn Ví dụ Khoa Công Nghệ Thông Tin, Đại Học Bách Khoa TP HCM 9.31
22. Chia sẻ các đoạn editor limit base 43062 data 1 0 25286 43062 1 4425 68348 segment 0 segment 1 editor segment table process P1 logical address space 68348 process P data 1 1 72773 editor limit base data 2 0 25286 43062 90003 data 2 segment 1 1 8850 90003 segment 0 98853 segment table process P2 logical address space physical memory process P2 Khoa Công Nghệ Thông Tin, Đại Học Bách Khoa TP HCM 9.32
23. 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 kết hợp các ưu điểm đồng thời hạn chế các khuyết điểm của phân trang và phân đoạn: – Vấn đề của phân đoạn: Nếu một đoạn quá lớn thì có thể không nạp nó được vào bộ nhớ. – Ý tưởng giải quyết: paging đoạn, khi đó chỉ cần giữ trong bộ nhớ các page của đoạn hiện đang cần. Khoa Công Nghệ Thông Tin, Đại Học Bách Khoa TP HCM 9.33
24. Kết hợp phân trang và phân đoạn (tt) ❑ Có nhiều cách kết hợp. Sau đây là một cách đơn giản, gọi là segmentation with paging Mỗi process sẽ có: – Một bảng phân đoạn – Nhiều bảng phân trang: mỗi đoạn có một bảng phân trang Một địa chỉ luận lý (địa chỉ ảo) bao gồm: – segment number: là chỉ số của một mục trong bảng phân đoạn, mục này chứa địa chỉ nền (base address) của bảng phân trang cho đoạn đó – page number: là chỉ số của một mục trong bảng phân trang, mục này chứa chỉ số frame trong bộ nhớ thực – offset: độ dời của vị trí nhớ trong frame nói trên. Khoa Công Nghệ Thông Tin, Đại Học Bách Khoa TP HCM 9.34
25. Segmentation with paging (1) ❑ Minh họa frame 0 frame 1 frame 2 frame 3 frame 4 frame 5 frame 6 Khoa Công Nghệ Thông Tin, Đại Học Bách Khoa TP HCM 9.35
26. Segmentation with paging (2) Khoa Công Nghệ Thông Tin, Đại Học Bách Khoa TP HCM 9.36
27. Segmentation with paging (3) ❑ 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, Khoa Công Nghệ Thông Tin, Đại Học Bách Khoa TP HCM 9.37