›

Giáo trình Hệ điều hành - Chương 5: Quản lí bộ nhớ - Trần Công Án

pdf 58 trang huongle 12260
Download
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Hệ điều hành - Chương 5: Quản lí bộ nhớ - Trần Công Án", để 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:

  • pdfgiao_trinh_he_dieu_hanh_chuong_5_quan_li_bo_nho_tran_cong_an.pdf

Nội dung text: Giáo trình Hệ điều hành - Chương 5: Quản lí bộ nhớ - Trần Công Án

  1. Hệ Điều Hành Chương 5. Quản Lý Bộ Nhớ Giảng viên TS. Trần Công Án tcan@cit.ctu.edu.vn Khoa Công Nghệ Thông Tin & Truyền Thông Đại học Cần Thơ
  2. [HĐH] Ch5. Quản lý bộ nhớ Mục Tiêu I Mô tả chi tiết các phương pháp tổ chức bộ nhớ. I Giải thích các kỹ thuật quản lý bộ nhớ bao gồm phân trang và phân đoạn. I Một số ví dụ thực tế về quản lý bộ nhớ: quản lý phân đoạn trong bộ xử lý Intel Pentium và quản lý địa chỉ bộ nhớ trong HĐH Linux. TS. Trần Công Án [HĐH] Ch5. Quản lý bộ nhớ 2
  3. [HĐH] Ch5. Quản lý bộ nhớ Nội Dung Tổng quan về Bộ nhớ và Tiến trình Hoán vị (swapping) Cấp phát bộ nhớ kề nhau (Contigous allocation) Phân trang (Paging) Các cấu trúc bảng trang Phân đoạn (Segmentation) Kết hợp phân trang và phân đoạn Phụ lục – Một Số Ví Dụ TS. Trần Công Án [HĐH] Ch5. Quản lý bộ nhớ 3
  4. [HĐH] Ch5. Quản lý bộ nhớ Tổng quan về Bộ nhớ và Tiến trình Tổng quan về bộ nhớ Giới Thiệu Bộ Nhớ I CPU chỉ có thể truy xuất trực tiếp thanh ghi và bộ nhớ chính. ⇒ Để thực thi một chương trình, đoạn mã của chương trình phải được tải vào trong bộ nhớ chính và đặt trong một tiến trình. I Thanh ghi: một dạng bộ nhớ đặc biệt, đặt bên trong CPU và chỉ mất tối đa 1 chu kỳ CPU để truy xuất. I Bộ nhớ chính: tốc độ truy xuất chậm hơn thanh ghi, đòi hỏi vài chu kỳ. I Bộ nhớ cache: là bộ nhớ trung gian giữa thanh ghi và bộ nhớ chính, tốc độ truy xuất nhanh, chỉ chậm hơn thanh ghi. I Việc bảo vệ bộ nhớ là cần thiết để đảm bảo thực thi đúng đắn của các tiến trình, đặc biệt trong môi trường đa nhiệm. TS. Trần Công Án [HĐH] Ch5. Quản lý bộ nhớ 4
  5. [HĐH] Ch5. Quản lý bộ nhớ Tổng quan về Bộ nhớ và Tiến trình Thanh ghi nền và thanh ghi giới hạn Thanh Ghi Nền & Thanh Ghi Giới Hạn 8.1 Background 353 0 operating I Hỗ trợ việc phân chia vùng nhớ system cho các tiến trình. 256000 I Thanh ghi nền (base): xác định process giới hạn vùng nhớ vật lý thấp 300040 300040 nhất. base process I Thanh ghi giới hạn (limit): xác định kích thước của vùng nhớ. 420940 120900 limit ⇒ Địa chỉ vùng nhớ mà một tiến process trình có thể truy xuất: [base, 880000 base+limit] 1024000 Figure 8.1 Abaseandalimitregisterdefinealogicaladdressspace. TS. Trần Công Án [HĐH] Ch5. Quản lý bộ nhớ 5 300040 and the limit register is 120900, then the program can legally access all addresses from 300040 through 420939 (inclusive). Protection of memory space is accomplished by having the CPU hardware compare every address generated in user mode with the registers. Any attempt by a program executing in user mode to access operating-system memory or other users’ memory results in a trap to the operating system, which treats the attempt as a fatal error (Figure 8.2). This scheme prevents a user program from (accidentally or deliberately) modifying the code or data structures of either the operating system or other users. The base and limit registers can be loaded only by the operating system, which uses a special privileged instruction. Since privileged instructions can be executed only in kernel mode, and since only the operating system executes in kernel mode, only the operating system can load the base and limit registers. base base ϩ limit address yes yes CPU ≥ < no no trap to operating system monitor—addressing error memory Figure 8.2 Hardware address protection with base and limit registers.
  6. 8.1 Background 353 0 operating system 256000 process 300040 300040 base process 420940 120900 limit process 880000 1024000 Figure 8.1 Abaseandalimitregisterdefinealogicaladdressspace. 300040 and the limit register is 120900, then the program can legally access all addresses from 300040 through 420939 (inclusive). [HĐH] Ch5. QuảnProtection lý bộ nhớ of memory space is accomplished by having the CPU hardware Tổng quancompare về Bộ nhớ every và Tiến address trình generated in user mode with the registers. Any attempt Bảo vệby không a program gian nhớ executing in user mode to access operating-system memory or other users’ memory results in a trap to the operating system, which treats the attempt as a fatal error (Figure 8.2). This scheme prevents a user program from Bảo(accidentally Vệ Không or deliberately) Gian modifying Nhớ the Bằng code or data Phần structures Cứng of either the operating system or other users. The base and limit registers can be loaded only by the operating system, which uses a special privileged instruction. Since privileged instructions can I Đượcbe executed thực thi only bởi in kernel CPU, mode, sử dụng and since t/ghi only cơ the sở operating và t/ghi system giới executes hạn. in kernel mode, only the operating system can load the base and limit registers. I Hai thanh ghi chỉ có thể được thay đổi bởi HĐH, với quyền đặc biệt. base base ϩ limit address yes yes CPU ≥ < no no trap to operating system monitor—addressing error memory Figure 8.2 Hardware address protection with base and limit registers. TS. Trần Công Án [HĐH] Ch5. Quản lý bộ nhớ 6
  7. [HĐH] Ch5. Quản lý bộ nhớ Hoán vị (swapping) Hoán Đổi (Swapping) I Là một kỹ thuật cho phép tổng không gian bộ nhớ của các tiến trình lớn hơn tổng không gian nhớ vật lý: I Một (hay một phần) tiến trình có thể được di chuyển tạm thời từ bộ nhớ chính ra các thiết bị lưu trữ phụ (cuộn ra – roll/swap out) rồi sau đó di chuyển ngược vào bộ nhớ chính để tiếp tục thực thi (cuộn vào – roll/swap in). I Cho phép tăng độ đa nhiệm của các hệ thống đa chương. I Tốc độ của thiết bị lưu trữ phụ phải đủ nhanh để sao chép hiện trạng bộ nhớ (memory image) của các tiến trình và cho phép truy cập trực tiếp các dữ liệu này. TS. Trần Công Án [HĐH] Ch5. Quản lý bộ nhớ 7
  8. 358 Chapter 8 Main Memory programs would need to be relinked to gain access to the new library. So that programs will not accidentally execute new, incompatible versions of libraries, version information is included in both the program and the library. More than one version of a library may be loaded into memory, and each program uses its version information to decide which copy of the library to use. Versions with minor changes retain the same version number, whereas versions with major changes increment the number. Thus, only programs that are compiled with the new library version are affected by any incompatible changes incorporated in it. Other programs linked before the new library was installed will continue using the older library. This system is also known as shared libraries. Unlike dynamic loading, dynamic linking and shared libraries generally require help from the operating system. If the processes in memory are protected from one another, then the operating system is the only entity that can check to see whether the needed routine isinanotherprocess’smemoryspace or that can allow multiple processes to access the same memory addresses. We elaborate on this concept when we discuss paging in Section 8.5.4. 8.2 Swapping A process must be in memory to be executed. A process, however, can be swapped temporarily out of memory to a backing store and then brought back into memory for continued execution (Figure 8.5). Swapping makes it possible for the total physical address space of all processes to exceed the real physical [HĐH] Ch5.memory Quản lý of bộ the nhớ system, thus increasing the degree of multiprogramming in a Hoán vịsystem. (swapping) Roll in, Roll out 8.2.1 Standard Swapping SwapStandard Out, swapping Swap involves In moving processes between main memory and abackingstore.Thebackingstoreiscommonlyafastdisk.Itmustbelarge operating system process P 1 swap out 1 process P2 2 swap in user space backing store main memory Figure 8.5 Swapping of two processes using a disk as a backing store. TS. Trần Công Án [HĐH] Ch5. Quản lý bộ nhớ 8
  9. [HĐH] Ch5. Quản lý bộ nhớ Hoán vị (swapping) Cài Đặt Hoán Đổi Cài Đặt Hoán Đổi I Phần chính của thời gian hoán đổi là thời gian chuyển dữ liệu (transfer time), thường tỷ lệ với kích thước bộ nhớ hoán đổi. I Hệ thống duy trì một hàng đợi sẵn sàng để lưu trữ danh sách các tiến trình sẵn sàng thực thi và đang được hoán đổi ra vùng lưu trữ phụ. I Thời gian chuyển ngữ cảnh trong cách tiếp cận này tương đối cao ⇒ thường không khả thi trong thực tế. I Các phiên bản được sửa đổi của swapping được sử dụng trong các hệ điều hành hiện tại: I Swapping bình thường bị vô hiệu hóa. I Nó chỉ được kích hoạt khi nhu cầu bộ nhớ đạt đến 1 ngưỡng nào đó. TS. Trần Công Án [HĐH] Ch5. Quản lý bộ nhớ 9
  10. [HĐH] Ch5. Quản lý bộ nhớ Cấp phát bộ nhớ kề nhau (Contigous allocation) Giới thiệu Cấp Phát Bộ Nhớ Kề Nhau I Là một trong các p/pháp cấp phát bộ nhớ được sử dụng đầu tiên. I Bộ nhớ chính thường được chia thành 2 phần: I Phần thường trú của HĐH: tổ chức trong vùng nhớ thấp (các vector ngắt). I Tiến trình người dùng: được tổ chức trong vùng nhớ cao. I Mỗi tiến trình được cấp phát một vùng nhớ đơn, liên tục. I Bộ quản lý bộ nhớ thực hiện ánh xạ địa chỉ luận lý sang vật lý vào thời gian thực thi (động): I địa chỉ vật lý = địa chỉ luận lý + giá trị thanh ghi tái định vị. TS. Trần Công Án [HĐH] Ch5. Quản lý bộ nhớ 10
  11. [HĐH] Ch5. Quản lý bộ nhớ Cấp phát bộ nhớ kề nhau (Contigous allocation) Bảo vệ vùng nhớ Bảo vệ vùng nhớ I Thanh ghi tái định vị được sử dụng để bảo vệ vùng nhớ của các tiến trình người dùng và HĐH (mã lệnh và dữ liệu). I Thanh ghi tái định vị: chứa địa chỉ vật lý thấp nhất của tiến trình. I Thanh ghi giới hạn: chứa phạm vi địa chỉ luận lý của tiến trình. limit relocation register register logical physical address yes address CPU Ͻ ϩ memory no trap: addressing error TS. Trần Công Án [HĐH] Ch5. Quản lý bộ nhớ 11
  12. [HĐH] Ch5. Quản lý bộ nhớ Cấp phát bộ nhớ kề nhau (Contigous allocation) Cấp phát đa phân khu động Cấp Phát Đa Phân Khu Động I Dùng cho hệ thống đa chương: mỗi t/trình được cấp phát 1 phân khu. I Cấp độ đa chương được xác định bởi số lượng phân khu. I K/thước mỗi phân khu có thể thay đổi tùy vào nhu cầu của t/trình. I Lỗ trống (hole): là vùng nhớ còn trống chưa được cấp phát. I Có thể nằm rãi rác trong bộ nhớ (do sự cấp phát, thu hồi bộ nhớ). I Khi 1 t/trình xuất hiện, nó được phân 1 lỗ trống đủ chứa nó. I Khi 1 t/trình kết thúc, vùng nhớ dành cho nó sẽ được thu hồi thành lỗ trống và kết hợp với lỗ trống liền kề nếu có. I Hệ thống sẽ duy trì thông tin về các phân khu đã cấp phát và lỗ trống. TS. Trần Công Án [HĐH] Ch5. Quản lý bộ nhớ 12
  13. [HĐH] Ch5. Quản lý bộ nhớ Cấp phát bộ nhớ kề nhau (Contigous allocation) Cấp phát đa phân khu động Chiến Lược Cấp Phát I Làm thế nào để đáp ứng một yêu cầu bộ nhớ kích thước n? I First-fit: Cấp phát lỗ trống đủ lớn đầu tiên. I Best-fit: Cấp phát lỗ trống đủ lớn nhỏ nhất. I Phải kiểm tra toàn bộ các lỗ trống nếu các lỗ trống không được sắp xếp. I Sẽ phát sinh lỗ trống có kích thước nhỏ nhất. I Worst-fit: Cấp lỗ trống lớn nhất I Có thể phải k/tra toàn bộ các lỗ trống. I Sinh ra lỗ trống còn lại lớn nhất. I First-fit và best-fit cho hiệu năng và tốc độ tốt hơn worst-fit. TS. Trần Công Án [HĐH] Ch5. Quản lý bộ nhớ 13
  14. [HĐH] Ch5. Quản lý bộ nhớ Cấp phát bộ nhớ kề nhau (Contigous allocation) Cấp phát đa phân khu động Sự Phân Mảnh I Phân mảnh trong: Phân khu cấp phát cho tiến trình lớn hơn nhu cầu. I Phân mảnh ngoài: Các lỗ trống nằm rãi rác ⇒ có thể xảy ra trường hợp tổng kích các lỗ trống lớn hơn như cầu nhưng chúng không nằm liên tục nên không thể cấp phát. I Khử phân mảnh ngoài: cô đặc lại bộ nhớ – sắp xếp lại bộ nhớ để gom các lỗ trống lại. I chỉ thực hiện được khi việc tái định vị là động (thực hiện lúc thực thi). I Một phương pháp khử phân mảnh ngoài là cấp phát không liên tục. TS. Trần Công Án [HĐH] Ch5. Quản lý bộ nhớ 14
  15. [HĐH] Ch5. Quản lý bộ nhớ Phân trang (Paging) Cơ Chế Phân Trang (Paging) I Cho phép không gian địa chỉ vật lý cấp phát cho 1 tiến trình có thể không liên tục nhau ⇒ tránh được phân mãnh ngoài bộ nhớ. n I Bộ nhớ vật lý được chia thành các khối có kích thước cố định (2 bytes, thường từ 512K – 16MB), gọi là các khung (frame). I Vùng nhớ luận lý của tiến trình cũng được chia thành các khối có kích thước cố định (bằng kích thước frame), gọi là trang nhớ (page). I Một chương trình cần n trang sẽ được cấp phát n khung. I Có thể phát sinh phân mảnh trong. I Hệ thống sẽ theo dõi các khung trống và thiết đặt một bảng trang (table page) để ánh xạ địa chỉ luận lý sang địa chỉ vật lý. TS. Trần Công Án [HĐH] Ch5. Quản lý bộ nhớ 15
  16. [HĐH] Ch5. Quản lý bộ nhớ Phân trang (Paging) Định địa chỉ trong phân trang Định Địa Chỉ Trong Phân Trang I Một địa chỉ luận lý bao gồm: I Số hiệu trang (page number – p): dùng làm chỉ mục trong bảng phân trang để tìm ra chỉ số khung tương ứng (địa chỉ nền) trong bộ nhớ vật lý. I Độ dời trang (page offset – d): được kết hợp với địa chỉ nền để định vị địa chỉ vật lý bộ nhớ. m I Nếu kích thước của vùng nhớ luận lý là 2 bytes và kích thước trang là 2n bytes thì m-n bits cao được dùng để đánh số trang và n bits thấp được dùng để gán độ dời trang. page number page offset pd m – n n TS. Trần Công Án [HĐH] Ch5. Quản lý bộ nhớ 16
  17. [HĐH] Ch5. Quản lý bộ nhớ Phân trang (Paging) Cấu trúc hệ thống dịch địa chỉ Cấu Trúc Hệ Thống Dịch Địa Chỉ f logical physical address address f0000 0000 CPU p d f d f1111 1111 p f physical memory page table TS. Trần Công Án [HĐH] Ch5. Quản lý bộ nhớ 17
  18. [HĐH] Ch5. Quản lý bộ nhớ Phân trang (Paging) Mô hình phân trang Mô Hình Phân Trang frame number page 0 0 0 1 page 1 1 4 1 page 0 2 3 page 2 2 3 7 page 3 page table 3 page 2 logical 4 page 1 memory 5 6 7 page 3 physical memory TS. Trần Công Án [HĐH] Ch5. Quản lý bộ nhớ 18
  19. [HĐH] Ch5. Quản lý bộ nhớ Phân trang (Paging) Ví dụ về phân trang Ví Dụ Về Phân Trang 0 a 0 1 b 2 c 3 d 4 e 4 i 5 f j 0 5 6 g k 7 h 1 6 l 8 i 2 1 8 m 9 j n 3 2 10 k o 11 l page table p 12 m 12 I Một trang có kích thước 4 bytes 13 n 14 o 15 p I Bộ nhớ vật lý: 32 bytes (8 khung). logical memory 16 I Địa chỉ luận lý 3 được ánh xạ vào 20 a b địa chỉ vật lý 23. c d 24 e f g h 28 physical memory TS. Trần Công Án [HĐH] Ch5. Quản lý bộ nhớ 19
  20. [HĐH] Ch5. Quản lý bộ nhớ Phân trang (Paging) Ví dụ về phân trang Ví Dụ Về Phân Trang - Quản Lý Khung Trống free-frame list free-frame list 14 15 13 13 page 1 13 18 20 14 14 page 0 15 15 15 page 0 16 page 0 16 page 1 page 1 page 2 17 page 2 17 page 3 page 3 new process 18 new process 18 page 2 19 0 14 19 1 13 20 2 18 20 page 3 3 20 21 new-process page table 21 TS. Trần Công Án [HĐH] Ch5. Quản lý bộ nhớ 20
  21. [HĐH] Ch5. Quản lý bộ nhớ Phân trang (Paging) Phân mảnh trong trong phân trang Phân Mảnh Trong Trong Phân Trang I Trang cuối cùng được cấp phát có thể không được sử dụng hết ⇒ phân mảnh trong. I Ví dụ: I Kích thước trang: 2.048 bytes. I Kích thước tiến trình: 72.766 bytes. I 35 trang + 1.086 bytes I Cấp phát: 36 trang. I Phân mảnh trong: 2.048 - 1.086 = 962 bytes I Trường hợp phân mảnh xấu nhất = kích thước 1 trang - 1 bytes. TS. Trần Công Án [HĐH] Ch5. Quản lý bộ nhớ 21
  22. [HĐH] Ch5. Quản lý bộ nhớ Phân trang (Paging) Cài đặt bảng trang Cài Đặt Bảng Trang I Bảng trang thường được lưu giữ trong bộ nhớ chính: I Mỗi tiến trình có một bảng trang. I Thanh ghi bảng trang nền: trỏ đến bảng trang. I Thanh ghi chiều dài bảng trang: chỉ định kích thước của bảng trang. I Mỗi tác vụ truy cập bộ nhớ cần 2 thao tác truy cập vùng nhớ: I 1 thao tác truy xuất bảng trang, sử dụng p để lấy số khung. I 1 thao tác truy xuất bộ nhớ vật lý, sử dụng d để tính đ/chỉ vật lý. I Thường sử dụng cache phần cứng để tăng tốc độ các thao tác này như thanh ghi kết hợp (associative register) hoặc bộ đệm tìm kiếm phụ cho việc dịch địa chỉ (Translation Look-aside Buffer – TLBs). TS. Trần Công Án [HĐH] Ch5. Quản lý bộ nhớ 22
  23. [HĐH] Ch5. Quản lý bộ nhớ Phân trang (Paging) Bộ nhớ kết hợp Bộ Nhớ Kết Hợp – TLBs I Là thanh ghi cực nhanh, chứa ánh xạ giữa trang và khung. I Có kích thước nhỏ: 64 – 1024 mục. I Được xem như là bộ đệm của bảng trang. I Cơ chế làm việc (ánh xạ hp, di vào bộ nhớ vật lý): I Nếu p nằm trong TLBs: lấy ngay được số frame. I Ngược lại: truy xuất bảng trang để lấy số khung trang như bình thường. Đồng thời, đưa ánh xạ trang–khung mới sử dụng vào TLBs. TS. Trần Công Án [HĐH] Ch5. Quản lý bộ nhớ 23
  24. [HĐH] Ch5. Quản lý bộ nhớ Phân trang (Paging) Phân trang với TLB Phân Trang Với TLB logical address CPU p d page frame number number TLB hit physical address fd TLB p TLB miss f physical memory page table TS. Trần Công Án [HĐH] Ch5. Quản lý bộ nhớ 24
  25. [HĐH] Ch5. Quản lý bộ nhớ Phân trang (Paging) Thời gian truy xuất hiệu dụng (Effective Access Time – EAT) Thời Gian Truy Xuất Hiệu Dụng I Thời gian truy xuất hiệu dụng (EAT): EAT = (ε + m)α + (ε + 2m)(1 − α) = (2 − α)m + ε I ε: thời gian tìm kiếm trên thanh ghi kết hợp (đ/vị thời gian). I m: thời gian 1 chu kỳ truy xuất bộ nhớ. I α: tỷ lệ tìm thấy (hit ratio) – tỷ số giữa số lần chỉ số trang được tìm thấy trong TLB trên tổng số lần truy cập bộ nhớ. I Ví dụ: ε = 20ns, α = 0.8, m = 100ns ⇒ ETA = 140ns TS. Trần Công Án [HĐH] Ch5. Quản lý bộ nhớ 25
  26. [HĐH] Ch5. Quản lý bộ nhớ Phân trang (Paging) Bảo vệ bộ nhớ Bảo Vệ Bộ Nhớ (Memory Protection) I Mỗi khung được gắn một số bit bảo vệ (protection bits) để chỉ định các tiến trình có thể thực hiện các thao tác gì trên khung. I read-only, read-write, execute, . . . I Mỗi mục trong bảng trang được gắn 1 bit xác định tính hợp lệ: I valid: trang tương ứng đang nằm trong không gian địa chỉ luận lý của tiến trình ⇒ trang hợp lệ (có thể truy xuất). I invalid: trang tương ứng không nằm trong không gian địa chỉ luận lý của bất kỳ tiến trình nào ⇒ không hợp lệ (không thể truy xuất). I Giải pháp khác bằng phần cứng: dùng thanh ghi độ dài bảng trang (page-table length register – PTLR) để xác định kích thước bảng trang. TS. Trần Công Án [HĐH] Ch5. Quản lý bộ nhớ 26
  27. [HĐH] Ch5. Quản lý bộ nhớ Phân trang (Paging) Bảo vệ bộ nhớ Bit Hợp Lệ, Không Hợp Lệ 0 1 2 page 0 00000 frame number valid–invalid bit page 0 3 page 1 0 2 v 4 page 2 page 1 1 3 v 2 4 v page 2 5 3 7 v page 3 4 8 v 6 5 9 v page 4 6 0 i 7 page 3 7 0 i 10,468 page 5 8 page 4 12,287 page table 9 page 5 • • • page n TS. Trần Công Án [HĐH] Ch5. Quản lý bộ nhớ 27
  28. [HĐH] Ch5. Quản lý bộ nhớ Phân trang (Paging) Chia sẻ trang Chia Sẻ Trang (Shared Page) I Chia sẻ mã lệnh: I Các tiến trình của cùng 1 ch/trình có thể chia sẻ trang chứa mã lệnh. I Trang được chia sẻ thường được gán thuộc tính chỉ đọc. I Giao tiếp liên tiến trình: I Các trang nhớ có thể được chia sẻ giữa các tiến trình để thực hiện giao tiếp liên tiến trình. I Phải được gán thuộc tính đọc-ghi. I Ngoài ra, mặc nhiên thì các luồng trong cùng một tiến trình có thể chia sẻ chung các trang nhớ trong cùng một không gian tiến trình. TS. Trần Công Án [HĐH] Ch5. Quản lý bộ nhớ 28
  29. [HĐH] Ch5. Quản lý bộ nhớ Phân trang (Paging) Chia sẻ trang Chia Sẻ Trang (Shared Page) 8.5 Paging 377 ed 1 0 3 1 data 1 ed 2 4 6 ed 3 2 data 3 1 data 1 page table 3 ed 1 for P1 ed 1 process P 4 ed 2 1 3 ed 2 4 5 6 ed 3 7 6 ed 3 data 2 page table for P 7 data 2 ed 1 2 process P2 3 8 ed 2 4 9 6 ed 3 2 10 data 3 page table for P3 11 process P3 TS. Trần Công Án Figure 8.16 [HĐH]Sharing Ch5. of code Quản in lý a paging bộ nhớ environment. 29 Each process has its own copy of registers and data storage to hold the data for the process’s execution. The data for two different processes will, of course, be different. Only one copy of the editor need be kept in physical memory. Each user’s page table maps onto the same physical copy of the editor, but data pages are mapped onto different frames. Thus, to support 40 users, we need only one copy of the editor (150 KB), plus 40 copies of the 50 KB of data space per user. The total space required is now 2,150 KB instead of 8,000 KB—a significant savings. Other heavily used programs can also be shared—compilers, window systems, run-time libraries, database systems, and so on. To be sharable, the code must be reentrant. The read-only nature of shared code should not be left to the correctness of the code; the operating system should enforce this property. The sharing of memory among processes on a system is similar to the sharing of the address space of a task by threads, described in Chapter 4. Furthermore, recall that in Chapter 3 we described shared memory as a method of interprocess communication. Some operating systems implement shared memory using shared pages. Organizing memory according to pages provides numerous benefits in addition to allowing several processes to share the same physical pages. We cover several other benefits in Chapter 9.
  30. [HĐH] Ch5. Quản lý bộ nhớ Các cấu trúc bảng trang Các cấu Trúc Bảng Trang I Kích thước bảng trang có thể rất lớn nếu bảng trang được cấu trúc đơn giản. 12 I Xét 1 hệ thống máy tính 32-bit; kích thước trang: 4K (2 ) ⇒ Số mục của bảng trang: 232/212 = 220 I Nếu kích thước mỗi mục là 4 bytes thì kích thước bảng trang là 4MB. ⇒ Tương đối lớn cho việc truy xuất và cấp phát liên tục. I Một số cấu trúc bảng trang: I Bảng trang phân cấp (hierarchical page table). I Bảng trang được băm (hashed page table). I Bảng trang đảo (inverted page table). TS. Trần Công Án [HĐH] Ch5. Quản lý bộ nhớ 30
  31. [HĐH] Ch5. Quản lý bộ nhớ Các cấu trúc bảng trang Bảng trang phân cấp (Hierarchical Page Tables) Bảng Trang Phân Cấp I Phân không gian địa chỉ luận lý vào nhiều bảng trang. I Số bảng trang được gọi là số cấp (số mức). I Ví dụ: bảng trang phân cấp đơn giản là bảng trang 2 cấp (two-level page table), trong đó không gian bộ nhớ được chia vào 2 bảng trang I bảng trang cấp 1 (bảng trang ngoài – outer page table): chỉ mục cho bảng trang bên trong. I bảng trang cấp 2 (bảng trang trong – inner page table): ánh xạ địa chỉ luận lý vào địa chỉ vật lý. I Đây là 1 hình thức phân trang cho bảng trang. TS. Trần Công Án [HĐH] Ch5. Quản lý bộ nhớ 31
  32. [HĐH] Ch5. Quản lý bộ nhớ Các cấu trúc bảng trang Bảng trang phân cấp (Hierarchical Page Tables) Bảng Trang Phân Cấp 0 1 1 • • • • • • 100 500 • • • • • • 100 500 • • • • • • • • 708 • • • 708 • • outer page 929 • 900 • table • • • • 900 • • page of 929 page table • • page table • memory TS. Trần Công Án [HĐH] Ch5. Quản lý bộ nhớ 32
  33. [HĐH] Ch5. Quản lý bộ nhớ Các cấu trúc bảng trang Bảng trang phân cấp (Hierarchical Page Tables) Cấu Trúc Địa Chỉ Luận Lý I Cấu trúc địa chỉ bộ nhớ luận lý cho bảng trang 2 cấp gồm 3 phần: page number page offset p1 p2 d I p1: chỉ mục bảng trang cấp 1 (bảng trang ngoài – outter page table). I p2: chỉ mục bảng trang cấp 2 (bảng trang trong – inner page table). I d: độ dời bên trong khung. I Cấu trúc trên có thể được tổng quát hóa cho trường hợp bảng trang phân cấp cấp n. TS. Trần Công Án [HĐH] Ch5. Quản lý bộ nhớ 33
  34. [HĐH] Ch5. Quản lý bộ nhớ Các cấu trúc bảng trang Bảng trang phân cấp (Hierarchical Page Tables) Cấu Trúc Địa Chỉ Luận Lý – Ví Dụ 12 I Trong một hệ thống 32-bit với trang nhớ có kích thước 4K (2 ): 32−12 20 I Bảng trang có thể chứa đến 2 = 2 mục (entries). ⇒ Cần 20 bits để đánh số hiệu trang, 12 bits chỉ định độ dời. page number offset page number offset p d p1 p2 d 20 12 10 10 12 I Bảng trang 2 cấp: số hiệu trang được chia thành 2 phần (2 cấp). I Nếu muốn mỗi bảng trang cấp 2 có thể được chứa trong 1 trang bộ nhớ, giả sử mỗi mục trong bảng trang chiếm 4B: cần 10 bits để đánh chỉ số cho các mục trong bảng trang. I Còn lại 10 bits dùng để đánh chỉ số các mục của bảng trang cấp 1. TS. Trần Công Án [HĐH] Ch5. Quản lý bộ nhớ 34
  35. [HĐH] Ch5. Quản lý bộ nhớ Các cấu trúc bảng trang Bảng trang phân cấp (Hierarchical Page Tables) Sơ Đồ Chuyển Đổi Địa Chỉ logical address p1 p2 d p1 p2 outer page d table page of page table TS. Trần Công Án [HĐH] Ch5. Quản lý bộ nhớ 35
  36. [HĐH] Ch5. Quản lý bộ nhớ Các cấu trúc bảng trang Bảng trang phân cấp (Hierarchical Page Tables) Không Gian Nhớ Luận Lý 64-Bit I Bảng trang 2 cấp không phù hợp cho không gian nhớ 64-bit. 52 I Giả sử kích thước trang là 4K ⇒ bảng trang có 2 mục. 10 I Nếu dùng bảng trang 2 cấp, bảng trang cấp 2 có 2 mục ⇒ sử dụng 10 bits để đánh chỉ số cho bảng trang cấp 2. 42 I Bảng trang cấp 1 có tối đa 2 mục ⇒ kích thước lên đến 4TB. I Giải pháp là tăng số cấp của bảng trang: số cấp trong trường hợp này là tương đối lớn vì đến 3 cấp thì k/thước bảng trang cấp 1 vẫn là 16G. outer page inner page offset 2nd outer page outer page inner page offset p1 p2 d p1 p2 p3 d 42 10 12 32 10 10 12 TS. Trần Công Án [HĐH] Ch5. Quản lý bộ nhớ 36
  37. [HĐH] Ch5. Quản lý bộ nhớ Các cấu trúc bảng trang Bảng trang phân cấp (Hierarchical Page Tables) Nhận Xét I Ưu điểm: I Cấu trúc bảng trang phân cấp giúp tiết kiệm bộ nhớ cấp phát cho bảng trang: chỉ cấp phát đúng số bảng trang tiến trình cần dùng. I Phương pháp cấp phát, ánh xạ địa chỉ nhớ đơn giản. I Cho phép chia sẻ bộ nhớ giữa các tiến trình ở mức trang. I Khuyết điểm: I Đòi hỏi thực hiện nhiều thao tác tìm kiếm (ánh xạ) địa chỉ nhớ cho mỗi truy cập bộ nhớ. I Phải tốn chi phí bộ nhớ cho bảng trang. I Kích thước bảng trang sẽ rất lớn trong các hệ thống có không gian địa chỉ lớn. TS. Trần Công Án [HĐH] Ch5. Quản lý bộ nhớ 37
  38. [HĐH] Ch5. Quản lý bộ nhớ Các cấu trúc bảng trang Bảng trang băm (Hashed Page Table) Bảng Trang Băm (Hashed Page Table) I Dùng bảng băm để giảm không gian bảng trang. I Được sử dụng trong các hệ thống có không gian bộ nhớ > 32-bits. I Số hiệu trang ảo được băm vào bảng trang. I Mỗi mục từ của bảng băm sẽ chỉ đến một danh sách liên kết các phần tử được băm vào cùng vị trí. I Một phần tử trong danh sách là một cặp hchỉ số trang ảo, chỉ số framei. I Tìm trang (p, d): I Số trang ảo được băm để tìm vị trí của mục từ trong bảng băm. I Duyệt qua d/sách l/kết của mục từ để tìm số khung trang tương ứng. TS. Trần Công Án [HĐH] Ch5. Quản lý bộ nhớ 38
  39. [HĐH] Ch5. Quản lý bộ nhớ Các cấu trúc bảng trang Bảng trang băm (Hashed Page Table) Bảng Trang Băm (Hashed Page Table) physical logical address address pd rd hash physical qs pr • • • function memory hash table TS. Trần Công Án [HĐH] Ch5. Quản lý bộ nhớ 39
  40. [HĐH] Ch5. Quản lý bộ nhớ Các cấu trúc bảng trang Bảng Trang Đảo Bảng Trang Đảo (Inverted Page Table) I Mỗi mục từ của bảng trang đại diện cho 1 khung trong bộ nhớ. I Một mục từ chứa địa chỉ ảo của trang được chứa trong bộ nhớ thực và thông tin về tiến trình sở hữu nó. I Phương pháp này giảm bộ nhớ cần thiết lưu trữ các bảng trang, nhưng lại mất thời gian tìm kiếm bảng trang khi truy xuất 1 trang được yêu cầu. I Có thể dùng bảng băm để giới hạn tìm kiếm cho 1 hoặc 1 vài mục từ của bảng trang. TS. Trần Công Án [HĐH] Ch5. Quản lý bộ nhớ 40
  41. [HĐH] Ch5. Quản lý bộ nhớ Các cấu trúc bảng trang Bảng Trang Đảo Bảng Trang Đảo (Inverted Page Table) logical address physical address physical CPU pid p d id memory search i pid p page table TS. Trần Công Án [HĐH] Ch5. Quản lý bộ nhớ 41
  42. [HĐH] Ch5. Quản lý bộ nhớ Phân đoạn (Segmentation) Phân Đoạn (Segmentation) I Bộ nhớ ở góc độ người dùng: subroutine stack I Chương trình là một tập các đoạn (segment). symbol I Mỗi đoạn là một đơn vị luận lý table như: chương trình chính, hàm, đối tượng, mảng, . . . Sqrt I Phân đoạn: main program I Là một sơ đồ quản lý bộ nhớ hỗ trợ cái nhìn về bộ nhớ theo góc độ người dùng. logical address TS. Trần Công Án [HĐH] Ch5. Quản lý bộ nhớ 42
  43. [HĐH] Ch5. Quản lý bộ nhớ Phân đoạn (Segmentation) Hai Góc Nhìn Bộ Nhớ I Phân đoạn cung cấp cơ chế ánh xạ giữa không gian địa chỉ luận lý và không gian địasubroutine chỉ vậtstack lý. 1400 segment 3 segment 0 2400 symbol segment 0 table subroutine stack limit base 1400 Sqrt segment 4 0 1000 1400 3200 segment 3 1 400 segment6300 0 main 2 2400400 4300 symbol program 3 1100 3200 segment 3 segment 0 table 4 1000 4700 segment table segment 1 segment 2 limit base 4300 segment 4 0 1000 1400 segment 2 Sqrt 4700 1 400 6300 3200 main 2 400 4300 programlogical address space3 1100 3200 segment 3 segment 4 4 1000 4700 segment table 5700 segment 1 segment 2 4300 segment 2 4700 6300 segment 1 6700 segment 4 logical address space physical memory 5700 6300 TS. Trần Công Án [HĐH] Ch5. Quản lý bộ nhớ segment 1 43 6700 physical memory
  44. [HĐH] Ch5. Quản lý bộ nhớ Phân đoạn (Segmentation) Kiến trúc hệ thống phân đoạn Kiến Trúc Hệ Thống Phân Đoạn I Một địa chỉ luận lý bao gồm một cặp: hsegment_number, offseti I Bảng phân đoạn (segment table): chứa các mục ánh xạ các địa chỉ luận lý (2 chiều) vào các địa chỉ vật lý 1 chiều; mỗi mục gồm: I base: chứa địa chỉ vật lý khởi đầu của đoạn trong bộ nhớ vật lý. I limit: chỉ định chiều dài của đoạn. I Segment-table base register (STBR): là thanh ghi trỏ đến bảng phân đoạn trong bộ nhớ. I Segment-table length register (STLR): là thanh ghi chỉ ra số lượng các đoạn đang được sử dụng bởi chương trình. TS. Trần Công Án [HĐH] Ch5. Quản lý bộ nhớ 44
  45. [HĐH] Ch5. Quản lý bộ nhớ Phân đoạn (Segmentation) Phần cứng hỗ trợ phân đoạn Phần Cứng Hỗ Trợ Phân Đoạn I366MộtChapter đoạn có8 Main số hiệu Memorys hợp lệ nếu s < STLR. s limit base segment table CPU sd yes <+ no trap: addressing error physical memory TS. Trần Công Án Figure[HĐH] 8.8 Ch5.Segmentation Quản lý bộ hardware. nhớ 45 addresses. This mapping is effected by a segment table.Eachentryinthe segment table has a segment base and a segment limit.Thesegmentbase contains the starting physical address where the segment resides in memory, and the segment limit specifies the length of the segment. The use of a segment table is illustrated in Figure 8.8. A logical address consists of two parts: a segment number, s, and an offset into that segment, d. The segment number is used as an index to the segment table. The offset d of the logical addressmust be between 0 and the segmentlimit. If it is not, we trap to the operating system (logical addressing attempt beyond end of segment). When an offset is legal, it is added to the segment base to produce the address in physical memory of the desired byte. The segment table is thus essentially an array of base–limit register pairs. As an example, consider the situation shown in Figure 8.9. We have five segments numbered from 0 through 4. The segments are stored in physical memory as shown. The segment table has a separate entry for each segment, giving the beginning address of the segment in physical memory (or base) and the length of that segment (or limit). For example, segment 2 is 400 bytes long and begins at location 4300. Thus, a reference to byte 53 of segment 2 is mapped onto location 4300 + 53 = 4353. A reference to segment 3, byte 852, is mapped to 3200 (the base of segment 3) + 852 = 4052. A reference to byte 1222 of segment 0wouldresultinatraptotheoperatingsystem,asthissegmentisonly1,000 bytes long. 8.5 Paging Segmentation permits the physical address space of a process to be non- contiguous. Paging is another memory-management scheme that offers this advantage. However, paging avoids external fragmentation and the need for
  46. [HĐH] Ch5. Quản lý bộ nhớ Phân đoạn (Segmentation) Phần cứng hỗ trợ phân đoạn Ví Dụ Về Phân Đoạn subroutine stack 1400 segment 3 segment 0 2400 symbol segment 0 table limit base Sqrt segment 4 0 1000 1400 1 400 6300 3200 main 2 400 4300 program 3 1100 3200 segment 3 4 1000 4700 segment table segment 1 segment 2 4300 segment 2 4700 logical address space segment 4 5700 6300 segment 1 6700 physical memory TS. Trần Công Án [HĐH] Ch5. Quản lý bộ nhớ 46
  47. [HĐH] Ch5. Quản lý bộ nhớ Phân đoạn (Segmentation) Bảo vệ và chia sẻ đoạn Bảo Vệ Và Chia Sẻ Đoạn I Bảo vệ đoạn: kết hợp I Chia sẻ đoạn: mỗi mục trong bảng editor limit base 43062 phân đoạn data 1 0 25286 43062 1 4425 68348 I 1 bit bảo vệ để đánh segment 0 segment 1 editor segment table dấu đoạn hợp process P1 logical address space 68348 lệ/không hợp lệ. process P data 1 1 72773 I các bits kiểm soát editor limit base quyền (đọc, ghi, thực data 2 0 25286 43062 90003 thi, . . . ) data 2 segment 1 1 8850 90003 segment 0 98853 segment table process P2 logical address space physical memory! process P2 TS. Trần Công Án [HĐH] Ch5. Quản lý bộ nhớ 47
  48. [HĐH] Ch5. 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 I Nhằm giải quyết trường hợp bảng phân đoạn quá lớn. I Ý tưởng: phân đoạn bảng phân trang (segmented paging) I Mỗi tiến trình sẽ có 1 bảng phân đoạn và nhiều bảng phân trang. I Mỗi mục bảng phân đoạn sẽ ánh xạ vào 1 bảng phân trang. I Cấu trúc một địa chỉ luận lý: hseg_number, page_number, offseti I seg_number: chỉ số của các mục trong bảng phân đoạn, dùng để xác định địa chỉ bảng phân trang. I page_number: chỉ số các mục trong bảng phân trang, dùng để xác định số khung. I offset: xác định địa chỉ nhớ vật lý. TS. Trần Công Án [HĐH] Ch5. Quản lý bộ nhớ 48
  49. [HĐH] Ch5. Quản lý bộ nhớ Kết hợp phân trang và phân đoạn Dịch Địa Chỉ TS. Trần Công Án [HĐH] Ch5. Quản lý bộ nhớ 49
  50. [HĐH] Ch5. Quản lý bộ nhớ Kết hợp phân trang và phân đoạn Ví Dụ frame 0 frame 1 frame 2 frame 3 frame 4 frame 5 frame 6 TS. Trần Công Án [HĐH] Ch5. Quản lý bộ nhớ 50
  51. Phụ Lục – Ví Dụ
  52. [HĐH] Ch5. Quản lý bộ nhớ Phụ lục – Một Số Ví Dụ Phân Trang Trong BXL Intel Pentium I Sử dụng 2 sơ đồ: phân đoạn và kết hợp phân đoạn với phân trang. I Sơ đồ dịch địa chỉ và phân đoạn: logical linear physical address segmentation address paging address physical CPU unit unit memory I Địa chỉ luận lý (segmentation): s g p 13 1 2 page number page offset Địa chỉ tuyến tính (paging): I p1 p2 d TS. Trần Công Án [HĐH] Ch5. Quản lý bộ nhớ 52
  53. [HĐH] Ch5. Quản lý bộ nhớ Phụ lục – Một Số Ví Dụ Phân Đoạn logical address selector offset descriptor table segment descriptor + 32-bit linear address TS. Trần Công Án [HĐH] Ch5. Quản lý bộ nhớ 53
  54. [HĐH] Ch5. Quản lý bộ nhớ Phụ lục – Một Số Ví Dụ Phân Trang (linear address) page directory page table offset 31 22 21 12 11 0 page 4-KB table page page directory CR3 4-MB register page page directory offset 31 22 21 0 TS. Trần Công Án [HĐH] Ch5. Quản lý bộ nhớ 54
  55. [HĐH] Ch5. Quản lý bộ nhớ Phụ lục – Một Số Ví Dụ Mở Rộng Địa Chỉ PAE TS. Trần Công Án [HĐH] Ch5. Quản lý bộ nhớ 55
  56. [HĐH] Ch5. Quản lý bộ nhớ Phụ lục – Một Số Ví Dụ Phân Trang 3 Cấp Trên Linux TS. Trần Công Án [HĐH] Ch5. Quản lý bộ nhớ 56
  57. [HĐH] Ch5. Quản lý bộ nhớ Tổng Kết Tổng Kết Tổng quan về Bộ nhớ và Tiến trình Hoán vị (swapping) Cấp phát bộ nhớ kề nhau (Contigous allocation) Phân trang (Paging) Các cấu trúc bảng trang Phân đoạn (Segmentation) Kết hợp phân trang và phân đoạn Phụ lục – Một Số Ví Dụ TS. Trần Công Án [HĐH] Ch5. Quản lý bộ nhớ 57