Bài giảng Hệ điều hành - Chương 7, Phần 2: Quản lý bộ nhớ - Trần Thị Như Nguyệt

Chương 7: Quản lý bộ nhớ - 2 
 Câu hỏi ôn tập chương 7-1 
 Chuyển đổi địa chỉ là gì? Địa chỉ nhớ được biểu diễn như thế 
 nào trong quá trình chạy một chương trình? 
 Khi nào địa chỉ lệnh và dữ liệu được chuyển thành địa chỉ 
 thật? 
 Thế nào là dynamic linking? Nêu ưu điểm? 
 Thế nào là dynamic loading? 
 Nêu cơ chế overlay? Swapping? 
 Nêu các mô hình quản lý bộ nhớ? 
 2 Quản lý bộ nhớ 
 Câu hỏi ôn tập chương 7-1 
 Thế nào là phân mảnh ngoại? Phân mảnh nội? Cho ví dụ? 
 Fixed partitioning là gì? Các chiến lược placement? 
 Dynamic partitioning là gì? Các chiến lược placement? 
 3 Quản lý bộ nhớ 
 Câu hỏi ôn tập chương 7-1 
Giả sử bộ nhớ chính được cấp phát các phân vùng có 
kích thước là 600K, 500K, 200K, 300K (theo thứ tự), 
sau khi thực thi xong, 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: 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 
 4 Quản lý bộ nhớ 
 Mục tiêu 
 Hiểu và vận dụng các cơ chế quản lý bộ nhớ: 
  Cơ chế phân trang 
  Cơ chế phân đoạn 
 5 Quản lý bộ nhớ 
 Nội dung 
 Cấp phát không liên tục 
  Cơ chế phân trang 
  Cơ chế phân đoạn 
  Cơ chế kết hợp phân trang và phân 
 đoạn 
 6 Quản lý bộ nhớ 
 Cấp phát không liên tục 
 Cơ chế phân trang 
 Cơ chế phân đoạn 
 Cơ chế kết hợp giữa phân trang và phân đoạn 
 7 Quản lý bộ nhớ 
 Cơ chế phân trang 
 Bộ nhớ vật lý thật (của một hệ thống máy tính) được chia thành 
 nhiều khối kích thước bằng nhau, gọi là khung trang (frame) 
 Bộ nhớ luận lý (của một process) cũng được chia thành nhiều 
 khối kích thước bằng nhau (và cũng bằng kích thước của frame 
 trong bộ nhớ vật lý), gọi là trang (page) 
 Các chú ý: 
 Kích thước/dung lượng (size) của frame hay page là lũy thừa của 2 
 (Thường từ khoảng 512 byte đến 16 MB. Một số hệ thống, kích thước 1 
 trang có thể lên đến 1GB) 
 Các hệ thống hiện nay, địa chỉ vật lý và luận lý hoàn toàn tách biệt nhau. 
 Ví dụ một process có thể có không gian địa chỉ 64-bit (tức dùng 64 bit để 
 định một địa chỉ bộ nhớ luận lý tương ứng này có tới 264 byte/word) 
 mặc dù bộ nhớ vật lý thật có ít hơn 264 byte/word 
 8 Quản lý bộ nhớ 
 Cơ chế phân trang 
 Để quản lý các page (biết page nào khi đưa vào bộ 
 nhớ vật lý sẽ được nạp vào frame nào tương ứng), 
 process dùng page table (Bảng phân trang) 
 Bảng phân trang (page table) dùng hỗ trợ ánh 
 xạ địa chỉ luận lý thành địa chỉ vật lý (địa chỉ 
 thực) 
 Để quản lý các frame (biết frame nào còn trống, 
 frame nào không ), hệ điều hành dùng frame 
 table 
 9 Quản lý bộ nhớ 
 Cơ chế phân trang (tt) 
page frame 
number number 
 0 
 0 
 0 1 
 1 
 1 page 0 
 1 4 
 2 
 2 2 3 
 3 page 2 
 3 3 5 
 4 page 1 
 logical memory page table 
 5 page 3 
 physical memory 
 10 Quản lý bộ nhớ 
 Cơ chế phân trang (tt) 
 Chuyển đổi địa chỉ trong paging 
 Cài đặt bảng trang 
 Effective access time 
 Tổ chức bảng trang 
 Bảo vệ bộ nhớ 
 11 Quản lý bộ nhớ 
 Chuyển đổi địa chỉ trong paging 
  Địa chỉ luận lý gồm có: 
  Số hiệu trang (Page number) p 
  Địa chỉ tương đối trong trang (Page offset) d 
  Nếu kích thước của không gian địa chỉ ảo là 2m 
 byte/word, và kích thước của mỗi trang là 2n byte/word 
 (đơn vị là byte hay word tùy theo kiến trúc máy) thì 
 page number page offset 
 p d 
 m - n bits n bits 
 (định vị từ 0 ÷ 2m − n − 1) (định vị từ 0 ÷ 2n − 1) 
 Có tổng cộng 2m/2n = 2m - n trang 
 Bảng phân trang (Page table) sẽ có tổng cộng 2m - n mục (entry) 
 12 Quản lý bộ nhớ 
 Chuyển đổi địa chỉ trong paging (tt) 
 f frames 
 logical physical 
 address address f 0000 
CPU p d f d 
 f 1111 
 p 
 f 
 physical 
 memory 
 page table 
 13 Quản lý bộ nhớ 
 Chuyển đổi địa chỉ trong paging (tt) 
Ví dụ: 
 14 Quản lý bộ nhớ 
(a): Trước khi các page trong một new process được cấp phát vào các 
frame trống trong bộ nhớ vật lý. 
(b): Sau khi các page trong một new process được cấp phát vào các 
frame trống trong bộ nhớ vật lý. 15 Quản lý bộ nhớ 
 Cài đặt bảng trang (paging hardware) 
 Bảng phân trang thường được lưu giữ trong bộ nhớ 
 chính 
  Mỗi process được hệ điều hành cấp một bảng phân 
 trang 
  Thanh ghi page-table base (PTBR) trỏ đến bảng 
 phân trang 
  Thanh ghi page-table length (PTLR) biểu thị kích 
 thước của bảng phân trang (có thể được dùng trong 
 cơ chế bảo vệ bộ nhớ) 
 Thường dùng một bộ phận cache phần cứng có tốc độ 
 truy xuất và tìm kiếm cao, gọi là thanh ghi kết hợp 
 (associative register) hoặc translation look-aside buffers 
 (TLBs) 
 16 Quản lý bộ nhớ 
 Cài đặt bảng trang (tt) 
 Cách dùng thanh ghi Page-Table Base Register (PTBR) 
 17 Quản lý bộ nhớ 
 Cài đặt bảng trang (tt) 
Cài đặt bảng trang có cải tiến với TLB (Translation look-
aside buffer) 
 18 Quản lý bộ nhớ 
 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 + ε 
 19 Quản lý bộ nhớ 
 Effective access time (EAT) (tt) 
 Ví dụ 1: đơn vị thời gian  Ví dụ 2: đơn vị thời gian 
 nano giây nano giây 
  Associative lookup = 20  Associative lookup = 20 
  Memory access = 100  Memory access = 100 
  Hit ratio = 0.8  Hit ratio = 0.98 
  EAT = (100 + 20) × 0.8  EAT = (100 + 20) × 
 + (200 + 20) × 0.2 0.98 + (200 + 20) × 
 = 1.2 × 100 + 20 0.02 
 ×
 = 140 = 1.02 100 + 20 
 = 122 
 20 Quản lý bộ nhớ 
 Tổ chức bảng trang 
Bảng phân trang thường được tổ chức/cấu trúc theo 3 
kiểu: 
• Cấu trúc bảng phân trang theo kiểu kế thừa (Phân 
 trang 2 cấp) - Hierarchical paging 
• Cấu trúc bảng phân trang theo kiểu nghịch đảo – 
 Inverted page tables 
• Cấu trúc bảng phân trang theo kiểu dùng hash function 
 - Hashed page tables 
Slide sau trình chỉ bày 2 kiểu: bảng phân trang 2 cấp 
và nghịch đảo 
 21 Quản lý bộ nhớ 
 Tổ chức bảng trang 2 cấp 
 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 
  Vì 4MB là khá nhiều, để tiện việc tìm kiếm trong bảng phân 
 trang, lúc này bản phân trang cũng được phân trang trong nó 
 Phân trang 2 cấp 
 Soá trang Ñoä dôøi trang 
 P1 P2 d 
 10 bit 10 bit 12 
 Ví dụ với phân trang 2 cấp 
 22 Quản lý bộ nhớ 
Tổ chức bảng trang 2 cấp 
 23 Quản lý bộ nhớ 
Tổ chức bảng trang 2 cấp 
 24 Quản lý bộ nhớ 
 Tổ chức bảng trang nghịch đảo 
 Bảng trang nghịch đảo (IBM system/38, IBM RISC, IBM RT): sử dụng 
 cho tất cả các process 
Địa chỉ luận lý bao gồm: 
 25 Quản lý bộ nhớ 
 Bảo vệ bộ nhớ 
 Việc bảo vệ bộ nhớ có thể được hiện thực bằng cách: 
 các bit bảo vệ frame được giữ kèm 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à không là trang của process, do 
 đó là một trang bất hợp lệ. 
 26 Quản lý bộ nhớ 
 Bảo vệ bằng valid/invalid bit 
 00000 frame valid/ 
 page 0 number invalid bit 
 14 bit page 1 0 
 page 2 1 
 2 
 page 3 
 3 
 page 4 
 4 
 10468 
 page 5 
 12287 5 
 6 
 7 
 16383 
 Moãi trang nhôù coù kích thöôùc 2K = 2048 
 Process coù kích thöôùc 10,468 phaân maûnh noäi ôû frame 9 
 (chöùa page 5), caùc ñòa chæ aûo > 12287 laø caùc ñòa chæ invalid. 
 27 Quản lý bộ nhớ 
 Chia sẻ các trang nhớ 
Process 1 
ed 1 0 3 
ed 2 1 4 
 2 6 Process 2 
ed 3 
 3 
 1 ed 1 0 
data 1 3 
 ed 2 1 4 
 2 6 
 ed 3 
 3 
ed 1 7 
 0 3 data 2 
ed 2 1 4 
ed 2 2 6 
 3 2 
data 3 
Process 3 
 Bô ̣ nhớ thực 
 28 Quản lý bộ nhớ 
 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, 
 29 Quản lý bộ nhớ 
 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 sẽ stack 
 procedure 
 tự động xây dựng các segment. 
 Ví dụ, trình biên dịch tạo ra các symbol 
 segment như hình bên: table 
 function 
  Stack sqrt 
  Symbol table main program 
  Procedure/function code 
 Trình loader sẽ gán mỗi segment 
 một số định danh riêng. 
 Logical address space 
 30 Quản lý bộ nhớ 
 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!) 
 31 Quản lý bộ nhớ 
 Phân đoạn (tt) 
logical address space physical memory space 
 segment 1 
 segment 2 
segment 3 segment 4 
 32 Quản lý bộ nhớ 
 Cài đặt phân đoạn 
 Địa chỉ luận lý là một cặp giá trị 
 Bảng phân đoạn (segment table): gồm nhiều mục 
 (item), mỗi mục gồm limit và base với: 
  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 
 33 Quản lý bộ nhớ 
 Một ví dụ về phân đoạn 
 stack 1400 
 procedure 
 segment 3 2400 
 segment 0 
 symbol 3200 
 table 
 function segment 4 
 sqrt 4300 
 main program 
 4700 
segment 1 segment 
 segment 2 table 
 5700 
 6300 
 logical address space 6700 
 physical memory space 
 34 Quản lý bộ nhớ 
 Phần cứng hỗ trợ phân đoạn 
 segment 
 s table 
CPU 
 yes 
 < physical 
 + memory 
 no 
 trap; addressing error 
 35 Quản lý bộ nhớ 
Chuyển đổi địa chỉ trong cơ chế phân đoạn 
 36 Quản lý bộ nhớ 
 Chia sẻ các đoạn 
 editor 
 data 1 43062 
 segment 0 segment 1 
 segment table 
 process P1 
logical address space 68348 
process P1 
 72773 
 editor 
 data 2 90003 
 segment 1 
 segment 0 98853 
 segment table 
 process P2 
 logical address space 
 process P2 physical memory 
 37 Quản lý bộ nhớ 
 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. 
 Logic Addr = 
 38 Quản lý bộ nhớ 
Kết hợp phân trang và phân đoạn (tt) 
 39 Quản lý bộ nhớ 
Cài đặt phân đoạn 
 40 Quản lý bộ nhớ 
 Ôn tập 
 Cấp phát không liên tục 
  Cơ chế phân trang 
  Cơ chế phân đoạn 
  Cơ chế kết hợp phân trang và phân 
 đoạn 
 41 Quản lý bộ nhớ 
Kết thúc chương 7