›
›

Bài giảng Hệ điều hành - Chương 6: Quản lý bộ nhớ - Trần Hạnh Nhi

pdf 72 trang huongle 4660
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Hệ điều hành - Chương 6: Quản lý bộ nhớ - Trần Hạnh Nhi", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_he_dieu_hanh_chuong_6_quan_ly_bo_nho_tran_hanh_nhi.pdf

Nội dung text: Bài giảng Hệ điều hành - Chương 6: Quản lý bộ nhớ - Trần Hạnh Nhi

  1. Bài giảng 6 : Quản lý bộ nhớ Tổng quan Nhu cầu bộ nhớ của tiến trình Các vấn đề về bộ nhớ Chuyển đổi địa chỉ Các công đoạn Các mô hình chuyển đổi địa chỉ Vai trò Quản lý bộ nhớ của HĐH Các yêu cầu Các mô hình tổ chức bộ nhớ Mô hình Liên tục Mô hình Không liên tục 12/2/2005 Trần Hạnh Nhi 1
  2. Tổng quan : Nhu cầu về bộ nhớ của tiến trình Chương trình cần được nạp vào Bộ nhớ chính để thi hành CPU chỉ có thể truy xuất trực tiếp Main Memory Chương trình khi được nạp vaò BNC sẽ được tổ chức theo cấu trúc của tiến trình tương ứng Ai cấp phát BNC cho tiến trình ? Chương trình nguồn sử dụng địa chỉ symbolic Tiến trình thực thi truy cập điạ chỉ thực trong BNC Ai chuyển đổi địa chỉ ? HĐH Bộ phận Quản lý Bộ nhớ Mô hình tổ chức ? Cơ chế hỗ trợ Chiến lược thực hiện 12/2/2005 Trần Hạnh Nhi 2
  3. Tổng quan : Các vấn đề về Bộ nhớ Cấp phát Bộ nhớ : Uniprogramming : Không khó Multiprogramming : BNC giới hạn, N tiến trình ? Bảovệ? Chiasẻ? Tiến trình thay đổi kích thước ? Tiến trình lớn hơn BNC ? Chuyển đổi địa chỉ tiến trình Thời điểm chuyển đổi địa chỉ ? Công thức chuyển đổi ? Phụ thuộc vào Mô hình tổ chức BNC ? Cần sự hỗ trợ của phần cứng ? Tiến trình thay đổi vị trí trong BNC ? 12/2/2005 Trần Hạnh Nhi 3
  4. Ví dụ 0x9000 OS 0x7000 Môi trường đa nhiệm gcc 0x4000 nachos 0x3000 emacs 0x0000 Nếu nachos cần thêm không gian ? Nếu nachos có lỗi và thực hiện thao tác ghi vào địa chỉ 0x7100? Khi nào gcc biết rằng nó thường trú tại 0x4000? Nếu emacs cần nhiều bộ nhớ hơn dung lượng vật lý hiện có? 12/2/2005 Trần Hạnh Nhi 4
  5. Các bước chuyển đổi chương trình C program: test.c Compiler Object:test.o Linker lib.o Executable: test.exe Loader Memory 12/2/2005 Trần Hạnh Nhi 5
  6. Các bước chuyển đổi source program -> .exe
  7. A.C B.C int x; F() OS int y; { x = 12; printf(“Hi”); y = 5; } F(); A.O B.O ? // F() 0 // x 0 -2 // F() ? // x 2 // y ? // y 4 // [0] = 12; ? // [?] = 12; ? // [?] = 5; 5 // [2] = 5; 0 // F() ? // jmp ? 6 // jmp F 3 // x //external // object 5 // y 7 // [3] = 12; 8 // [5] = 5; 9 // jmp 0 Test.exe
  8. Thuật ngữ Địa chỉ logic – còn gọi là địa chỉ ảo , là tất cả các địa chỉ do bộxửlýtạo ra Địa chỉ physic - là địa chỉ thực tế mà trình quản lý bộ nhớ nhìn thấy và thao tác Không gian địa chỉ – là tập hợp tất cả các địa chỉ ảo phát sinh bởi một chương trình Không gian vật lý – là tập hợp tất cả các địa chỉ vật lý tương ứng với các địa chỉ ảo 12/2/2005 Trần Hạnh Nhi 8
  9. Nhu cầu bộ nhớ của tiến trình low address system data segment (PCB) Tiếntrìnhgồmcĩ: code segment 8048314 : 8048314: push %ebp read from program file by exec code segment 8048315: mov %esp,%ebp usually read-only 8048317: mov 0xc(%ebp),%eax can be shared 804831a: add 0x8(%ebp),%eax initialized variables 804831d: pop %ebp data segment 804831e: ret initialized global variables (0 / NULL)804831f : uninitialized variables uninitialized global variables 804831f: push %ebp data segment heap 8048320: mov %esp,%ebp process A 8048322: sub $0x18,%esp dynamic memory 8048325: and $0xfffffff0,%esp heap segment data e.g., allocated using malloc 8048328: mov $0x0,%eax grows against higher addresses 804832d: sub %eax,%esp 804832f: movl $0x0,0xfffffffc(%ebp) stack segment 8048336: movl $0x2,0x4(%esp,1) variables in a function 804833e: movl $0x4,(%esp,1) y or stored register states (e.g. calling function8048345: call 8048314 em EIP) 804834a: mov %eax,0xfffffffc(%ebp) m d” grows against lower addresses 804834d: leave e us 804834e: ret n “u system data segment (PCB)804834f: nop segment pointers pid program and stack pointers Stack cho các thread possiblestack stacks for more threads high address 12/2/2005 Trần Hạnh Nhi 9
  10. Logical and Physical Address Spaces 12/2/2005 Trần Hạnh Nhi 10
  11. Truy xuất bộ nhớ Địa chỉ của Instruction và data trong program source code là symbolic: goto errjmp; X = A + B; Những địa chỉ symbolic này cần được liên kết (bound) với các địa chỉ thực trong bộ nhớ vật lý trước khi thi hành code Address binding: ánh xạ địa chỉ từ không gian địa chỉ (KGĐC) này vào KGĐC khác Thời điểm thực hiện address binding ? compile time load time execution time. 12/2/2005 Trần Hạnh Nhi 11
  12. Thời điểm kết buộc địa chỉ ? Có thể thực hiện việc kết buộc địa chỉ tại 1 trong 3 thời điểm : Compile-time: Phát sinh địa chỉ tuyệt đối Phải biết trước vị trí nạp chương trình Phải biên dịch lại chương trình khi vị trí nạp thay đổi Load-time: Khi biên dịch chỉ phát sinh địa chỉ tương đối Khi nạp, biết vị trí bắt đầu sẽ tính lại địa chỉ tuyệt đối Phải tái nạp khi vị trí bắt đầu thay đổi Execution-time: Khi biên dịch,nạp chỉ phát sinh địa chỉ tuong đối Trì hoãn thời điểm kêt buộc địa chỉ tuyệt đối đến khi thi hành Khi đó ai tính toán địa chỉ tuyệt đối ? Phần cứng : MMU 12/2/2005 Trần Hạnh Nhi 12
  13. Chuyển đổi địa chỉ MMU gcc Translation box Physical Load Store address Physical virtual legal addr? address Illegal? memory CPU error data 12/2/2005 Trần Hạnh Nhi 13
  14. CPU, MMU and Memory 12/2/2005 Trần Hạnh Nhi 14
  15. Yêu cầu quản lý bộ nhớ Tăng hiệu suất sử dụng CPU Cần hỗ trợ Multiprogramming Lưu trữ cùng lúc nhiều tiến trình trong BNC ? Các yêu cầu khi tổ chức lưu trữ tiến trình: 1. Relocation 2. Protection 3. Sharing 4. Logical Organization 5. Physical Organization 12/2/2005 Trần Hạnh Nhi 15
  16. Tái định vị (Relocation) Không biết trước chương trình sẽ được nạp vào BN ở vị trí nào để xử lý. Một tiến trình có thể được di dời trong bộ nhớ sau khi đã nạp C Tiến trình tăng trưởng ? HĐH sắp xếp lại các tiến trình để có thể sử dụng BNC hiệu qủa hơn. 12/2/2005 Trần Hạnh Nhi 16
  17. Bảo vệ (Protection) Không cho phép tiến trình truy cập đến các vị trí nhớ đã cấp cho tiến trình khác (khi chưa có phép). Không thể thực hiện việc kiểm tra hợp lệ tại thời điểm biên dịch hay nạp, vì chương trình có thể được tái định vị. Thực hiện kiểm tra tại thời điểm thi hành Cần sự hỗ trợ của phần cứng. 12/2/2005 Trần Hạnh Nhi 17
  18. Chia sẻ (Sharing) Cần cho phép nhiều tiến trình tham chiếu đến cùng một vùng nhớ mà không tổn hại đến tính an toàn hệ thống : Tiết kiệm chổ lưu trữ cho các module dùng chung. Cho phép các tiến trình cộng tác có khả năng chia sẻ dữ liệu. 12/2/2005 Trần Hạnh Nhi 18
  19. Tổ chức logic (Logical Organization) Người dùng viết chương trình gồm nhiều module, với các yêu cầu bảo vệ cho từng module có thể khác nhau: instruction modules : execute-only. data modules : read-only hay read/write. một số module là private, số khác có thể là public. OS cần hỗ trợ các cơ chế có thể phản ánh mô hình logic của chuơng trình 12/2/2005 Trần Hạnh Nhi 19
  20. Tổ chức vật lý (Physical Organization) Cấp phát vùng nhớ vật lý sao cho hiệu quả Và dễ dàng chuyển đổi chương trình qua lại giữa BNC và BNP 12/2/2005 Trần Hạnh Nhi 20
  21. Các mô hình tổ chức bộ nhớ Cấp phát Liên tục (Contigous Allocation) Linker – Loader Base & Bound Cấp phát Không liên tục (Non Contigous Allocation) Segmentation Paging 12/2/2005 Trần Hạnh Nhi 21
  22. Cấp phát Liên tục (Contigous Allocation) Nguyên tắc : Chương trình được nạp toàn thể vào BNC để thi hành Cần một vùng nhớ liên tục, đủ lớn để chứa Chương trình Không gian địa chỉ : liên tục Không gian vật lý : có thể tổ chức Fixed partition Variable partition 2 mô hình đơn giản Linker – Loader Base & Bound 12/2/2005 Trần Hạnh Nhi 22
  23. Fixed Partitioning Phân chia KGVL thành các partitions Có 2 cách phân chia partitions : kích thước bằng nhau kích thước khác nhau Mỗi tiến trình sẽ được nạp vào một partition để thi hành Chiến lược cấp phát partition ? 12/2/2005 Trần Hạnh Nhi 23
  24. Chiến lược cấp phát partitions cho tiến trình Kích thước partition bằng nhau không có gì phải suy nghĩ ! Kích thước partition không bằng nhau : Sử dụng nhiều hàng đợi Cấp cho tiến trình partition với kích thước bé nhất (đủ lớn để chứa tiên trình) Khuyết điểm : phân bố các tiến trình vào các partition không đều, một số tiến trình phải đợi trong khi có partition khác trống 12/2/2005 Trần Hạnh Nhi 24
  25. Chiến lược cấp phát partitions cho tiến trình Kích thước partition không bằng nhau : Sử dụng 1 hàng đợi Cấp cho tiến trình partition tự do với kích thước bé nhất (đủ lớn để chứa tiên trình) Cần dùng một CTDL để theo dõi các partition tự do 12/2/2005 Trần Hạnh Nhi 25
  26. Nhận xét Fixed Partitioning Sử dụng BN không hiệu quả internal fragmentation : kích thước chương trình không đúng bằng kích thước partition Mức độ đa chương của hệ thống (Số tiến trình được nạp) bị giới hạn bởi số partitions P1 (2M) 3M internal frag P2 (4M) 8M internal frag 12/2/2005 Trần Hạnh Nhi 26
  27. Dynamic Partitioning BNC không được phân chia trước P1 (2M) Các partition có kích thước tùy ý, P2 (4M) sẽ hình thành trong quá trình nạp các tiến trình vào hệ thống Mỗi tiến trình sẽ được cấp phát đúng theo kích thước yêu cầu không còn internal fragmentation 12/2/2005 Trần Hạnh Nhi 27
  28. Dynamic Partitioning: tình huống P1 (2M) external P2 (4M) fragmentation P4 (1.5M) P3 (8M) 2M Chọn lựa partition để cấp phát cho tiến trình ? Đồng thời có nhiều partition tự do đủ lớn để chứa tiến trình Dynamic Allocation problem Tiến trình vào sau không lấp đầy chỗ trống tiến trình trước để lại external fragmentation
  29. Ví dụ Dynamic Partitioning 12/2/2005 Trần Hạnh Nhi 29
  30. Ví dụ Dynamic Partitioning 12/2/2005 Trần Hạnh Nhi 30
  31. Giải quyết vấn đề Dynamic Allocation Các chiến lược thông dụng để chọn partition: First-fit: chọn partition tự do đầu tiên Best-fit: chọn partition tự do nhỏ nhất đủ chứa tiến trình Worst-fit: chọn partition tự do lớn nhất đủ chứa tiến trình 2M First Fit P1 P3 (1M) 8M Worst Fit P2 1.5M Best Fit 12/2/2005 Trần Hạnh Nhi 31
  32. Memory Compaction (Garbage Collection) Giải quyết vấn đề External Fragmentation : Dồn các vùng bị phân mảnh lại với nhau để tạo thành partition liên tục đủ lớn để sử dụng Chi phí thực hiện cao 2M External P1 fragmentations 1M P2 1.5M 12/2/2005 Trần Hạnh Nhi 32
  33. Các mô hình chuyển đổi địa chỉ Fixed/Dynamic partition là mô hình tổ chức nạp tiến trình vào KGVL Cần có mô hình để chuyển đổi địa chỉ từ KGĐC vào KGVL Linker Loader Base & Bound 12/2/2005 Trần Hạnh Nhi 33
  34. Mô hình Linker-Loader OS test.exe 0x4000 0x7000 test.exe jump 0x5000 jump 0x2000 0x3000 0x0000 (base) Tại thời điểm Link, giữ lại các địa chỉ logic Vị trí base của tiến trình trong bộ nhớ xác định được vào thời điểm nạp : địa chỉ physic = địa chỉ logic + base 12/2/2005 Trần Hạnh Nhi 34
  35. Nhận xét mô hình Linker-Loader Không cần sự hỗ trợ phần cứng để chuyển đổi địa chỉ Loader thực hiện Bảo vệ ? Không hỗ trợ Dời chuyển sau khi nạp ? Không hỗ trợ tái định vị Phải nạp lại ! 12/2/2005 Trần Hạnh Nhi 35
  36. Mô hình Base & Bound OS Test.exe Bound 0x4000 Test.exe 0x7000 jump 0x2000 jump 0x2000 Base 0x0000 0x3000 Tại thời điểm Link, giữ lại các địa chỉ logic Vị trí base , bound được ghi nhận vào 2 thanh ghi: Kết buộc địa chỉ vào thời điểm thi hành => tái định vị được : địa chỉ physic = địa chỉ logic + base register Bảo vệ : địa chỉ hợp lệ ⊆ [base, bound] 12/2/2005 Trần Hạnh Nhi 36
  37. Nhận xét mô hình Base & Bound Kết buộc địa chỉ tại thời điểm thi hành => cần hỗ trợ của phần cứng physical logical addrs addrs MMU memory CPU + base reg Hỗ trợ Bảo vệ Tái định vị 12/2/2005 Trần Hạnh Nhi 37
  38. Khuyết điểm của cấp phát liên tục Không có vùng nhớ liên tục đủ lớn để nạp tiến trình ? Bó tay Sử dụng BNC không hiệu qua”! 1M P1 P3 (9M) 8M P2 1M 12/2/2005 Trần Hạnh Nhi 38
  39. Các mô hình tổ chức bộ nhớ Cấp phát Liên tục (Contigous Allocation) Linker – Loader Base & Bound Cấp phát Không liên tục (Non Contigous Allocation) Segmentation Paging 12/2/2005 Trần Hạnh Nhi 39
  40. Các mô hình cấp phát không liên tục Cho phép nạp tiến trình vào BNC ở nhiều vùng nhớ không liên tục Không gian địa chỉ : phân chia thành nhiều partition Segmentation Paging Không gian vật lý : có thể tổ chức Fixed partition : Paging Variable partition : Segmentation 12/2/2005 Trần Hạnh Nhi 40
  41. Segmentation Lập trình viên : chương trình là một tập các segments Một segment là một đơn vị chương trình gồm các đối tượng có cùng nhóm ngữ nghĩa Ví dụ : main program, procedure, function, local variables, global variables,common block,stack, symbol table, arrays Các segment có thể có kích thước khác nhau Mô hình Segmentation : KGĐC : phân chia thành các segment KGVL : tổ chức thành dynamic partitions Nạp tiến trình : Mỗi segment cần được nạp vào một partition liên tục, tự do, đủ lớn cho segment partition nào ? Dynamic Allocation ! Các segment của cùng 1 chương trình có thể được nạp vào những partition không liên tục 12/2/2005 Trần Hạnh Nhi 41
  42. Mô hình Segmentation int m; heap main () { F1(m); stack } data F1(int x) (m) { x = 9; code } (main,F1) Quản lýKGDC địa chỉ ? KGVL 12/2/2005 Trần Hạnh Nhi 42
  43. Tổ chức Segmentation Điạ chỉ logic : Địa chỉ physic : Chuyển đổi địa chỉ : Chuyển đổi địa chỉ vào thời điểm thi hành MMU thi hành Sử dụng Segment Table (bảng phân đoạn) để lưu thông tin cấp phát BNC, làm cơ sở thực hiện ánh xạ địa chỉ Mỗi tiến trình có một Segment Table Sâegment Table: Số phần tử của Segment Table = Số Segment của chương trình Mỗi phần tử của Segment Table mô tả cho 1 segment, và có cấu trúc : base: địa chỉ vật lý trong BNC của partition chứa segment limit : kích thước segment Lưu trữ Segment Table ? Cache : nếu đủ nhỏ BNC : Segment-table base register (STBR), Segment-table length register (STLR) 12/2/2005 Trần Hạnh Nhi 43
  44. Chuyển đổi địa chỉ trong mô hình Segmentation fault Logical Addr no mem yes 3 128 ? + 0x1000 Seg# offset Seg table 128 seg base limit 0 1 2 3 0x1000 512 12/2/2005 Trần Hạnh Nhi 44
  45. Logical-to-Physical Address Translation in segmentation 12/2/2005 Trần Hạnh Nhi 45
  46. Nhận xét Mô hình Segmentation Cấp phát không liên tục => tận dụng bộ nhớ hiệu quả Hỗ trợ tái định vị Từng Segment Hỗ trợ Bảo vệ và Chia sẻ được ở mức module Ý nghĩa của “mức module” ? Chuyển đổi địa chỉ phức tạp ☺ Đã có MMU Sử dụng dynamic partition : chịu đựng Dynamic Allocation : chọn vùng nhớ để cấp cho một segment ☺ First fit, Best fit, Worst fit External Fragmentation : Memory Compaction : chi phí cao 12/2/2005 Trần Hạnh Nhi 46
  47. Paging Hỗ trợ HĐH khắc phục bài toán cấp phát bộ nhớ động, và loại bỏ external fragmentation Mô hình Paging : KGĐC : phân chia chương trình thành các page có kích thước bằng nhau Không quan tâm đến ngữ nghĩa của các đối tượng nằm trong page KGVL : tổ chức thành các fixed partitions có kích thước bằng nhau gọi là frame page size = frame size Nạp tiến trình : Mỗi page cần được nạp vào một frame tự do Các pages của cùng 1 chương trình có thể được nạp vào những frames không kế cận nhau. Tiến trình kích thước N pages -> cần N frame tự do để nạp 12/2/2005 Trần Hạnh Nhi 47
  48. Mô hình Paging int m; int m; main () main () { F1(int x) F1(m); } stack F1(int x) { x = 9; heap } KGDC Quản lý địa chỉ ? KGVL 12/2/2005 Trần Hạnh Nhi 48
  49. Tổ chức Paging Điạ chỉ logic : Địa chỉ physic : Chuyển đổi địa chỉ : Chuyển đổi địa chỉ vào thời điểm thi hành MMU thi hành Sử dụng Page Table để lưu thông tin cấp phát BNC, làm cơ sở thực hiện ánh xạ địa chỉ Mỗi tiến trình có một Page Table Page Table Số phần tử của Page Table = Số Page trong KGĐC của chương trình Mỗi phần tử của bảng Page Table mô tả cho 1 page, và có cấu trúc : frame: số hiệu frame trong BNC chứa page Lưu trữ Page Table ? Cache : không đủ BNC : Page-table base register (PTBR), Page-table length register (PTLR) 12/2/2005 Trần Hạnh Nhi 49
  50. Chuyển đổi địa chỉ trong mô hình Paging Logical Physical addr addr CPU p d f d KGVL f Page table 12/2/2005 Trần Hạnh Nhi 50
  51. Logical-to-Physical Address Translation in Paging 12/2/2005 Trần Hạnh Nhi 51
  52. Nhận xét Mô hình Paging Loại bỏ Dynamic Allocation External Fragmentation “Trong suốt” với LTV Hỗ trợ Bảo vệ và Chia sẻ ở mức page Internal Fragmentation Lưu trữ Page Table trong bộ nhớ Tốn chỗ Tăng thời gian chuyển đổi địa chỉ 12/2/2005 Trần Hạnh Nhi 52
  53. Lưu trữ Page Table Giả sử hệ thống sử dụng m bit địa chỉ Size of KGĐC = 2m Kích thước page Trên nguyên tắc tùy ý, thực tế chọn pagesize = 2n Tại sao ? Số trang trong KGĐC: #pages = 2m / 2n = 2m-n Ví dụ : 32-bits địa chỉ, pagesize = 4K KGĐC = 232 -> #pages= 232-212 = 220 = 1.000.000 pages ! #pages = #entry trong PT Điạ chỉ logic : p d Page Table (m-n) n Mỗi tiến trình lưu 1 Page Table Số lượng phần tử quá lớn -> Lưu BNC Mỗi truy xuất địa chỉ sẽ tốn 2 lần truy xuất BNC 12/2/2005 Trần Hạnh Nhi 53
  54. Lưu trữ Page Table : Tiết kiệm không gian Sử dụng bảng trang đa cấp Chia bảng trang thành các phần nhỏ, bản thân bảng trang cũng sẽ được phân trang Chỉ lưu thường trực bảng trang cấp 1, sau đó khi cần sẽ nạp bảng trang cấp nhỏ hơn thích hợp Có thể loại bỏ những bảng trang chứa thông tin về miền địa chỉ không sử dụng Sử dụng Bảng trang nghịch đảo Mô tả KGVL thay vì mô tả KGĐC -> 1 IPT cho toàn bộ hệ thống 12/2/2005 Trần Hạnh Nhi 54
  55. Bảng trang đa cấp 0 0 1 1 0 2 2 1 Page Table cấp 2 3 3 2 4 3 4 5 4 5 6 5 6 7 0 6 7 Page Table cấp 2 8 1 7 9 2 8 8 10 3 9 9 11 10 10 12 Page Table cấp 1 11 Page Table cấp 2 11 13 12 12 12 13 13 13 14 14 Page Table cấp 2 14 15 15 15
  56. Mô hình bảng trang 2 cấp 12/2/2005 Trần Hạnh Nhi 56
  57. Ví dụ mô hình bảng trang 2 cấp Một máy tính sử dụng địa chỉ 32bít với kích thước trang 4Kb. Địa chỉ logic được chia thành 2 phần: Số hiệu trang : 20 bits. Offset tính từ đầu mỗi trang :12 bits. Vì bảng trang lại được phân trang nên số hiệu trang lại được chia làm 2 phần: Số hiệu trang cấp 1. Số hiệu trang cấp 2. 12/2/2005 Trần Hạnh Nhi 57
  58. Ví dụ mô hình bảng trang 2 cấp Vì thế, địa chỉ logic sẽ có dạng như sau: page number page offset pi p2 d 10 10 12 12/2/2005 Trần Hạnh Nhi 58
  59. Bảng trang đa cấp 0 0 1 1 1 2 100 2 2 3 Page Table cấp 2 3 4 0 5 1 6 2 0 7 3 Page Table cấp 2 8 1 9 2 0 10 3 1 11 2 12 Page Table cấp 1 3 Page Table cấp 2 13 0 14 1 15 2 Page Table cấp 2 16 3 17
  60. Bảng trang nghịch đảo (Inverted Page Table) Sử dụng duy nhất một bảng trang nghịch đảo cho tất cả các tiến trình Mỗi phần tử trong bảng trang nghịch đảo mô tả một frame, có cấu trúc : số hiệu page mà frame đang chứa đựng : id của tiến trình đang được sỡ hữu trang Mỗi địa chỉ ảo khi đó là một bộ ba Khi một tham khảo đến bộ nhớ được phát sinh, một phần địa chỉ ảo là được đưa đến cho trình quản lý bộ nhớ để tìm phần tử tương ứng trong bảng trang nghịch đảo, nếu tìm thấy, địa chỉ vật lý sẽ được phát sinh 12/2/2005 Trần Hạnh Nhi 60
  61. Kiến trúc bảng trang nghịch đảo 12/2/2005 Trần Hạnh Nhi 61
  62. Lưu trữ Page table : Tiết kiệm thời gian Mỗi truy cập BNC cần truy xuất BNC 2 lần : Tra cứu Page Table để chuyển đổi địa chỉ Tra cưu bản thân data Làm gì để cải thiện : Tìm cách lưu PT trong cache Cho phép tìm kiếm nhanh PT lớn, cache nhỏ : làm sao lưu đủ ? Lưu 1 phần PT Phần nào ? Các số hiệu trang mới truy cập gần đây nhất 12/2/2005 Trần Hạnh Nhi 62
  63. Translation Lookaside Buffer (TLB) Vùng nhớ Cache trong CPU được sử dụng để lưu tạm thời một phần của PT được gọi là Translation Lookaside Buffer (TLB) Cho phép tìm kiếm tốc độ cao Kích thước giới hạn (thường không quá 64 phần tử) Mỗi entry trong TLB chứa một số hiệu page và frame tương ứng đang chứa page Khi chuyển đổi địa chỉ, truy xuất TLB trước, nếu không tìm thấy số hiệu page cần thiết, mới truy xuất vào PT để lấy thông tin frame. 12/2/2005 Trần Hạnh Nhi 63
  64. Translation Lookaside Buffer 12/2/2005 Trần Hạnh Nhi 64
  65. Chuyển đổi địa chỉ với Paging virtual address CPU pd f physical address d fd TLB p f f Memory f PT 12/2/2005 Trần Hạnh Nhi 65
  66. Sử dụng TBL 12/2/2005 Trần Hạnh Nhi 66
  67. Bảo vệ và chia sẻ trong Segmentation và Paging Bảo vệ Segmentation : mỗi phần tử trong ST được gắn thêm các bit bảo vệ Mỗi segment có thể được bảo vệ tùy theo ngữ nghĩa của các đối tượng bên trong segment Paging : mỗi phần tử trong PT được gắn thêm các bit bảo vệ Mỗi page không nhận thức được ngữ nghĩa của các đối tượng bên trong page, nên bảo vệ chỉ áp dụng cho toàn bộ trang, không phân biệt. Chia sẻ: Cho nhiều phần tự trong KGĐC cùng trỏ đến 1 vị trí trong KGVL Segmentation : chia sẻ mức module chương trình Paging : chia sẻ các trang 12/2/2005 Trần Hạnh Nhi 67
  68. Sharing Pages: A Text Editor
  69. Sharing Pages: A Text Editor ed 3 + data 1 ed 3 + data 2 ed 3 + data 3 Chia sẻ Page 2 = Chia sẻ cả code và data !
  70. Sharing of Segments: Text Editor
  71. Đánh giá các mô hình chuyển đổi địa chỉ Giả sử có: tm : thời gian truy xuất BNC tc : thời gian truy xuất cache hit-ration : tỉ lệ tìm thấy một số hiệu trang p trong TLB Công thức tính thời gian truy cập thực tế (Time Effective Acess) đến một đối tượng trong BNC bao gồm thời gian chuyển đổi địa chỉ và thời gian truy xuất dữ liệu TEA = (time biding add + time acces memory) 12/2/2005 Trần Hạnh Nhi 71
  72. Linker-Loader TEA = tm (data) Base + Bound TEA = (tc + tc) + tm (Base & Bound) (data) Segmentation TEA = tc + tm (ST trong cache) (data) Paging Không sử dụng TLB : TEA = tm + tm (PT trong mem) (data) Có sử dụng TLB : TEA = hit-ratio ( tc + tm ) + (1- hit-ratio)( tc + tm + tm ) (TLB) (data) (TLB) (PT) (data)