Tin học văn phòng - Chapter 7: Bộ nhớ thực

11 Chapter 7: Bộ Nhớ Thực  Các kiểu địa chỉ nhớ  Chuyển đổi địa chỉ nhớ  Overlay và swapping  Vấn đề cấp phát bộ nhớ liên tục (contiguous memory allocation)  Giải pháp fixed partitioning  Giải pháp dynamic partitioning 2 Quản lý bộ nhớ  Kernel chiếm một vùng cố định của bộ nhớ, vùng còn lại dành để cấp phát cho các process  Cấp phát vùng nhớ cho các process sao cho hệ thốâng hoạt động hiệu quả  Vd: Nạp càng nhiều process vào bộ nhớ càng tốt để gia tăng mức độ multiprogramming  Quản lý bộ nhớ  Cấp phát vùng nhớ cho các process  Bảo vệ: kiểm tra truy xuất bộ nhớ có hợp lệ không  Chia sẻ: cho phép các process chia sẻ vùng nhớ chung  Chuyển đổi địa chỉ luận lý sang địa chỉ vật lý 3 Các kiểu địa chỉ nhớ (1/2)  Địa chỉ vật lý -- physical (memory) address -- là địa chỉ mà CPU, hay MMU (nếu có), gửi đến bộ nhớ chính  Địa chỉ luận lý (logical address) là địa chỉ mà một quá trình sinh ra  Các địa chỉ sinh bởi trình biên dịch (compiler) là  tương đối hay khả tái định vị (relocatable): compiler giả thiết không gian địa chỉ của đơn vị biên dịch (compilation unit) bắt đầu từ địa chỉ 0 hoặc  tuyệt đối: kết quả biên dịch có thể nạp được ngay vào bộ nhớ để thực thi; ít được dùng 24 Các kiểu địa chỉ nhớ (2/2)  Khi một lệnh được thực thi, các địa chỉ luận lý phải được chuyển đổi thành địa chỉ vật lý  Sự chuyển đổi này thường có sự hỗ trợ của phần cứng để đạt hiệu năng cao 5 Từ mã nguồn đến file thực thi được  Linker: kết hợp các object module thành một file thực thi được  tái định vị địa chỉ tương đối và phân giải các external reference  kết hợp các object module thành một load module (file nhị phân khả thực thi) System library System library static linking dynamic linking 6 Thực hiện (static) linking  Linker chuyển đổi địa chỉ tương đối sang địa chỉ tuyệt đối Module A CALL B Return length L Module B CALL C Return length M Module C Return length N 0 L - 1 Module A JMP “L” Return Module B JMP “L+M” Return Module C Return L L  M - 1 L  M L  M  N - 1 relocatable object modules load module 0 L - 1 0 M - 1 0 N - 1 37 Chuyển đổi địa chỉ  Chuyển đổi địa chỉ: quá trình ánh xạ một địa chỉ từ không gian địa chỉ này sang không gian địa chỉ khác  Biểu diễn địa chỉ nhớ  Trong source code: symbolic (các biến, hằng, pointer)  Thời điểm biên dịch: thường là địa chỉ tương đối Ví dụ: a ở vị trí 14 byte so với vị trí bắt đầu của module  Thời điểm linking/loading: có thể là địa chỉ tuyệt đối 0 250 2000 2250 relative address physical memory symbolic address int i; goto p1; p1 8 Sinh địa chỉ tuyệt đối vào thời điểm biên dịch Symbolic addresses Absolute addresses Physical memory addresses PROGRAM JUMP i LOAD j DATA i j Source code 1024 JUMP 1424 LOAD 2224 1424 2224 Absolute load module Compile Load 1024 JUMP 1424 LOAD 2224 1424 2224 Process image 9 Chuẩn bị sinh địa chỉ vật lý (1)  Vào thời điểm biên dịch  Compiler sinh địa chỉ tuyệt đối  Cần thông tin cho biết load module sẽ được nạp ở đâu  Không cần linker  Loader rất đơn giản  Hiếm được dùng (MSDOS .COM files) 410 Chuẩn bị sinh địa chỉ vật lý (2)  Vào thời điểm link-edit  Compiler Sinh địa chỉ tương đối (a.k.a. relocatable) cho mỗi đơn vị biên dịch Tham chiếu đến địa chỉ ngoài  Linkage editor Chuyển đổi địa chỉ relocatable sang địa chỉ tuyệt đối Phân giải các tham chiếu đến địa chỉ ngoài Cần thông tin cho biết linked program sẽ được nạp ở đâu  Loader vẫn còn rất đơn giản  Yêu cầu về phần cứng thấp  Một chương trình chỉ có thể được nạp tại nơi đã được đặc tả và không thể dịch chuyển sau khi được nạp  Không còn được dùng nhiều 11 Chuẩn bị sinh địa chỉ vật lý (3)  Vào thời điểm nạp  Tương tự thời điểm link-edit, nhưng không giữ cố định địa chỉ bắt đầu  Chương trình có thể được nạp ở bất cứ đâu  Chương trình có thể dịch chuyển nhưng không tách được  Chỉ cần phần cứng đơn giản: các thanh ghi base/limit  Loader thiết lập trị cho các thanh ghi base/limit  Không còn được dùng phổ biến 12 Sinh địa chỉ vật lý  Vào thời điểm thực thi  Địa chỉ được chuyển đổi động trong khi thực thi  Cần có phần cứng để chuyển đổi địa chỉ ảo sang địa chỉ vật lý được nhanh  “Phân trang” (“paging”)  “Phân đoạn” (“segmentation”)  Rất phổ biến hiện nay 513 Sử dụng vùng nhớ bớt phí phạm  Các kỹ thuật hỗ trợ sử dụng vùng nhớ bớt phí phạm:  Dynamic linking  Dynamic loading  Overlay  Swapping 14 Dynamic linking (1) Trong dynamic linking  Việc link một load module L đến một module ngoài (external module) được thực hiện sau khi đã tạo xong L  MS Windows: module ngoài là các file .dll  Unix: module ngoài là các file .so (shared library)  Load module chứa các stub tham chiếu (refer) đến các routine của external module  Khi process gọi routine lần đầu, stub sẽ nạp routine vào bộ nhớ (nếu routine chưa được nạp trước đó), thay thế địa chỉ mình bằng địa chỉ routine, và gọi routine để thực thi  Các lần gọi routine sau sẽ xảy ra bình thường, không tốn overhead 15 Dynamic linking (2)  Nhắc lại static linking main: ... call printf printf: ... ret 0x08048000 program copy từ libc 616 Dynamic linking (3) main: ... call printf 0x40001234 printf: ... ret 0x08048000 program libc printf: call GOT[5] ... [5]: dlfixup ... PLT (r/o code) GOT (r/w data) dlfixup: GOT[5] = &printf call printf Fig from M. Rosenblum 17 Ưu điểm của dynamic linking  Chương trình thực thi có thể gọi phiên bản mới (ví dụ phiên bản đã sửa lỗi) của external module mà không cần được sửa đổi và/hay biên dịch lại  Chia sẻ mã (code sharing): chỉ cần nạp external module vào bộ nhớ một lần  Các process sử dụng dynamic link với external module này chia sẻ vùng mã của external module  tiết kiệm không gian nhớ và không gian đĩa 18 Dynamic linking  Các external module thường là thư viện cung cấp các tiện ích (như libc)  Stub cần sự hỗ trợ của OS  Kiểm tra xem routine đã được nạp vào bộ nhớ chưa 719 Dynamic loading (1)  Chỉ khi nào cần được gọi đến thì một thủ tục mới được nạp vào bộ nhớ chính  Các thủ tục không được gọi đến sẽ không chiếm chỗ trong bộ nhớ  Rất hiệu quả khi chương trình có khối lượng lớn mã có tần suất sử dụng thấp (ví dụ các thủ tục xử lý lỗi)  Chính quá trình tự điều khiển dynamic loading  Hệ điều hành cung cấp một số thủ tục thư viện hỗ trợ 20 Dynamic loading (2)  Các thủ tục để người dùng thực hiện dynamic loading trong UNIX:  dlopen() – Open một file thư viện  dlsym() – Dò tìm một ký hiệu trong file thư viện  dlclose() – Close một file thư viện 21 Dynamic loading – Ví dụ 822 Kỹ thuật overlay (1/2)  Chỉ giữ trong bộ nhớ những lệnh hoặc dữ liệu cần thiết, giải phóng các lệnh/dữ liệu chưa hoặc không cần dùng đến  Kỹ thuật này rất hữu dụng khi kích thước một process lớn hơn kích thước vùng nhớ cấp cho nó  Quá trình tự điều khiển việc overlay (có sự hỗ trợ của thư viện lập trình)  Có thể được xem là tiền thân của kỹ thuật “bộ nhớ ảo” 23 Pass 1 70K Pass 2 80K Symbol table 20K Common routines 30K Assembler Total memory available = 150KB Kỹ thuật overlay (2/2) symbol table 20K common routines 30K overlay driver 10K pass 1 pass 2 80K70K Đơn vị: byte nạp và thực thi 24 Swapping  Cơ chế: di chuyển một process khỏi bộ nhớ chính và lưu trên bộ nhớ phụ (swap out). Khi thích hợp, nạp process vào bộ nhớ (swap in) để có thể tiếp tục thực thi  Chính sách:  Round-robin: swap out P1 (vừa tiêu thụ hết quantum của nó), swap in P2 , thực thi P3 ,  Roll out, roll in: dùng trong định thời theo độ ưu tiên (priority- based scheduling) Process có độ ưu tiên thấp hơn sẽ bị swap out nhường chỗ cho process có độ ưu tiên cao hơn vừa đến 925 Swapping -- Cơ chế 26 Vấn đề cấp phát bộ nhớ liên tục  Trong phần còn lại của chương này, mô hình quản lý bộ nhớ là một mô hình đơn giản [không dùng “bộ nhớ ảo”]  Một process phải được nạp hoàn toàn và liên tục vào bộ nhớ (ngoại trừ khi dùng kỹ thuật overlay)  Sẽ thảo luận các giải pháp cấp phát bộ nhớ sau  Phân chia cố định (fixed partitioning)  Phân chia động (dynamic partitioning) 27 Hiện tượng phân mảnh  Phân mảnh ngoại (external fragmentation)  Vùng nhớ còn trống đủ lớn để thỏa mãn một yêu cầu cấp phát, nhưng lại không liên tục  Có thể dùng kết khối (compacting) để gom lại thành vùng nhớ liên tục  Phân mảnh nội (internal fragmentation)  Vùng nhớ được cấp phát lớn hơn vùng nhớ yêu cầu  Ví dụ: cấp một khoảng trống 18.464 byte cho một process yêu cầu 18.462 byte  Thường xảy ra khi bộ nhớ thực được chia thành các khối kích thước cố định (fixed-sized block) và các process được cấp phát theo đơn vị khối 10 28 Phân mảnh nội operating system (used) yêu cầu kế tiếp là 18.462 byte hole kích thước 18.464 byte Để tránh overhead quản lý chỉ 2 byte, OS sẽ cấp phát hẳn khối 18.464 byte cho process  dư ra 2 byte không dùng 29 Fixed partitioning (1)  Khi khởi động hệ thống, bộ nhớ chính được chia thành nhiều phần cố định rời nhau, gọi là các partition, có kích thước bằng nhau hoặc khác nhau  Process nào có kích thước nhỏ hơn hoặc bằng kích thước partition thì có thể được nạp vào partition đó 30 Giải pháp fixed partitioning (2)  Nếu process có kích thước lớn hơn partition thì phải dùng kỹ thuật overlay  Không hiệu quả do bị phân mảnh nội: một chương trình dù lớn hay nhỏ đều được cấp phát trọn một partition 11 31 Chiến lược placement khi fixed partitioning (1/3)  Trường hợp các partition có kích thước bằng nhau  Nếu còn partition trống  process mới sẽ được nạp vào partition đó  Nếu không còn partition trống, nhưng có process đang bị blocked  swap out process đó ra bộ nhớ phụ, dành partition cho process mới 32 Chiến lược placement khi fixed partitioning (2/3)  Trường hợp các partition có kích thước không bằng nhau  Giải pháp 1 Gán mỗi process vào partition nhỏ nhất (trống hay không trống) đủ chứa nó [best fit] Có hàng đợi cho mỗi partition  Điểm yếu của giải pháp 1: có thể có một số hàng đợi trống (vì không có process với kích thước tương ứng) và một số hàng đợi dài 33 Chiến lược placement khi fixed partitioning (3/3)  Trường hợp các partition có kích thước không bằng nhau  Giải pháp 2 Khi cần nạp một process vào bộ nhớ chính  chọn partition nhỏ nhất còn trống và đủ chứa nó [best fit] Chỉ có một hàng đợi chung cho mọi partition 12 34 Giải pháp dynamic partitioning  Số lượng và vị trí partition không cố định và partition có thể có kích thước khác nhau  Mỗi process được cấp phát chính xác dung lượng bộ nhớ cần thiết  Gây ra hiện tượng phân mảnh ngoại 35 Chiến lược placement khi dynamic partitioning  Quyết định cấp phát khối bộ nhớ trống nào cho một process  Mục tiêu: giảm chi phí compaction  Các chiến lược placement  Best-fit: chọn khối nhớ trống nhỏ nhất  First-fit: chọn khối nhớ trống phù hợp đầu tiên kể từ đầu bộ nhớ  Next-fit: chọn khối nhớ trống phù hợp đầu tiên kể từ vị trí cấp phát cuối cùng  Worst-fit: chọn khối nhớ trống lớn nhất 36 Nhận xét  Cả hai giải pháp fixed và dynamic partitioning hầu như không còn được dùng trong các hệ thống hiện đại 13 37 Chapter 7  Cơ chế phân trang (paging)  Cơ chế phân đoạn (segmentation)  Segmentation with paging 38 Cơ chế phân trang (1/3)  Cơ chế phân trang (paging) cho phép không gian địa chỉ vật lý (physical address space) của một process có thể không liên tục nhau  Bộ nhớ thực được chia thành các khối cố định và có kích thước bằng nhau gọi là frame  Thông thường kích thước của frame là lũy thừa của 2, từ khoảng 512 byte đến 16 MB  Nhắc lại, bộ nhớ luận lý (logical memory) hay không gian địa chỉ luận lý là tập mọi địa chỉ luận lý của quá trình – Địa chỉ luận lý có thể được quá trình sinh ra bằng cách dùng indexing, base register, segment register, 39 Cơ chế phân trang (2/3)  Bộ nhớ luận lý cũng được chia thành các khối cố định có cùng kích thước gọi là trang nhớ (page)  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) để chuyển đổi (translate) địa chỉ luận lý thành địa chỉ thực  Mỗi process được cấp phát một bảng phân trang  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ớ có thể bị phân mảnh nội, nhưng khắc phục được phân mảnh ngoại 14 40 Cơ chế phân trang (3/3) logical memory 1 4 3 5 0 1 2 3 page table page 0 page 2 physical memory frame number 0 1 2 3 page 14 5 page 3 page number 0 1 2 3 41 Chuyển đổi địa chỉ trong paging  Địa chỉ luận lý gồm có:  Page number, p, là chỉ mục (index) vào bảng phân trang. Mỗi mục (entry) trong bảng phân trang chứa chỉ số frame, gọi là số frame cho gọn, chứ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 để cho địa chỉ thực  Nếu kích thước của không gian địa chỉ ảo là 2m và kích thước của trang là 2n ô nhớ (byte hay word tùy theo kiến trúc máy) Bảng phân trang sẽ có tổng cộng 2m/2n = 2m - n mục p d page number page offset m - n bit (định vị từ 0  2m - n - 1) n bit (định vị từ 0  2n - 1) 42 Paging hardware Nếu kích thước của bộ nhớ thực là 2l (byte), thì mỗi mục của bảng phân trang có l - n bit để chứa frame number frame number frame offset f, l - n bit d, n bit CPU p d f d f p page table logical address physical address physical memory f 0000 f 1111 f frame 15 43 Chuyển đổi địa chỉ nhớ trong paging  Ví dụ: 44 Hiện thực bảng phân trang (1)  Bảng phân trang được giữ trong bộ nhớ chính  Mỗi process được 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) chứa kích thước của bảng phân trang (có thể được dùng trong cơ chế bảo vệ bộ nhớ) 45 Hiện thực bảng phân trang (2)  Mỗi truy cập dữ liệu/lệnh cần hai thao tác truy xuất vùng nhớ 1. Dùng page number p làm index để truy xuất mục trong bảng phân trang nhằm lấy số frame 2. Dùng page offset d để truy xuất dữ liệu/lệnh trong frame  Do đó, thường dùng một 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)  Nguyên lý locality 16 46 TLB  TLB tìm kiếm truy xuất dữ liệu của nó với tốc độ cực nhanh Page number Frame number Số mục của TLB khoảng 8 .. 2048 Khi có chuyển ngữ cảnh, TLB bị xóa TLB là cache của bảng phân trang Ánh xạ page number – Nếu page number có trong TLB (“hit”, trúng)  lấy ngay được frame number  tiết kiệm được việc truy cập bộ nhớ để lấy frame number từ bảng phân trang – Ngược lại (“miss”, trật), phải lấy frame number từ bảng phân trang như bình thường Khi TLB đầy, thay thế mục dùng LRU 47 Paging hardware với TLB 48 Đánh giá hiệu năng của TLB (1/2) • 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:   Thời gian một chu kỳ truy xuất bộ nhớ: x  Hit ratio : tỉ số giữa số lần page number được tìm thấy (hit) trong TLB và số lần truy xuất khởi nguồn từ CPU  0    1  Tính thời gian cần thiết để truy xuất ô nhớ:  Khi page number có trong TLB (“hit”)  + x  Khi page number không có trong TLB (“miss”)  + x + x  Thời gian truy xuất hiệu dụng EAT = ( + x) + ( + 2x)(1 – ) = (2 – )x +  17 49 Đánh giá hiệu năng của TLB (2/2)  Ví dụ 1  Hit ratio = 0,8  EAT = (100 + 20)  0,8 + (200 + 20)  0,2 = 1,2  100 + 20 = 140  Ví dụ 2  Hit ratio = 0,98  EAT = (100 + 20)  0,98 + (200 + 20)  0,02 = 1,02  100 + 20 = 122  Giả sử (đơn vị thời gian: nano giây)  Tìm trong TLB = 20  Memory access = 100 50 Bảo vệ bộ nhớ  Việc bảo vệ bộ nhớ được hiện thực bằng cách dùng các bit bảo vệ (protection bit) được giữ trong mỗi mục của bảng phân trang. Các bit này biểu thị các thuộc tính của trang như  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; trị của bit có thể là  “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ệ 51 Bảo vệ bằng valid-invalid bit 00000 10468 12287 2 v 3 v 4 v 7 v 8 v 9 v - i - i frame number valid-invalid bit 0 1 2 3 4 5 6 7 0 1 2 page 0 3 page 1 4 page 2 5 6 7 page 3 8 page 4 9 page 5 ... page n  Mỗi trang nhớ có kích thước 2K = 2048 ô nhớ  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 18 52 Bảng phân trang 2 mức (1/5)  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à 4 K (= 212) ô nhớ  không gian địa chỉ ảo sẽ gồm 232/212 = 220 = 1 M page  bảng phân trang sẽ có 1 M mục  Giả sử mỗi mục của bảng phân trang gồm 4 byte thì mỗi process cần 4 MB cho bảng phân trang, và 100 quá trình sẽ cần  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ỉ sinh những bảng phân trang cần thiết  bảng phân trang 2 mức (two-level page table) 53 Bảng phân trang 2 mức (2/5) • 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  Nếu mỗi mục dài 4 byte  Cần 220 4 byte = 4 MB cho mỗi page table  Page offset: 12 bit  Bây giờ, bảng phân trang cũng được chia nhỏ nên page number cũng được chia nhỏ thành 2 phần, vd  10-bit page number  10-bit page offset  Vì vậy, một địa chỉ luận lý sẽ như hình vẽ bên • p1 : chỉ số của mục trong bảng phân trang mức 1 (outer-page table) • p2 : chỉ số của mục trong bảng phân trang mức 2 page number offset p2 page offset dp1 10 bit10 bit 12 bit 20 bit 12 bit 54 Bảng phân trang 2 mức (3/5) các bảng phân trang mức 2 - Có 2n1 mục trong bảng phân trang mức 1 - Mỗi bảng phân trang mức 2 chứa 2n2 mục n2 bitn1 bit 19 55 Bảng phân trang 2 mức (4/5)  Sơ đồ chuyển đổi địa chỉ (address-translation scheme) cho kỹ thuật phân trang 2 mức, với 32-bit địa chỉ page table mức 2 56 Bảng phân trang 2 mức (5/5)  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  Hình: để dễ thấy, các frame đã được cấp sao cho text, data, stack, nằm liên tục giống như trong không gian địa chỉ ảo Fig from Gottlieb 57 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  Tiết kiệm chổ trong bộ nhớ chính bằng cách chỉ sinh các bảng phân trang mà process cần page number page offset page numbers page offset page numbers page offset page numbers page offset 52 12 42 10 12 32 10 10 12 22 10 10 10 12 20 58 Bảng phân trang băm (1/2)  Nhận xét: Phí phạm vùng nhớ cho page table khi quá trình chỉ truy cập một số lượng nhỏ các trang  Dùng kỹ thuật băm để giảm kích thước 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 độ khi lưu, mỗi mục của bảng băm được gắn một danh sách liên kết mà mỗi phần tử là một cặp (chỉ số trang, chỉ số frame):  Chỉ số trang được biến đổi qua hàm băm thành một hashed value  Kế đó, cặp (chỉ số trang, 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 59 Bảng phân trang băm (2/2)  Giải thuật tìm trang: Chỉ số trang được biến đổi thành hashed value -- chỉ số của mục cần truy cập trong bảng băm. Sau đó, trong danh sách liên kết của mục, tìm phần tử chứa chỉ số trang để trích ra được chỉ số frame 60 Chia sẻ các trang nhớ Process 1 ed 1 ed 2 ed 3 data 1 ed 1 ed 2 ed 2 data 3 Process 3 3 4 6 2 0 1 2 3 3 4 6 1 0 1 2 3 Process 2 ed 1 ed 2 ed 3 data 2 3 4 6 7 0 1 2 3 0 1 data 1 2 data 3 3 ed 1 4 ed 2 5 6 ed 3 7 data 2 8 9 10 Bộ nhớ thực 21 61 Phân đoạn (1/3)  Dưới góc nhìn của user, một chương trình cấu thành từ nhiều đơn vị luận lý gọi là đoạn (segment)  Lệnh: main program, procedure, function  Dữ liệu: local variables, global variables, common block, stack, symbol table, arrays, 62 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ẽ tự động xây dựng các segment  Ví dụ, trình biên dịch Pascal sẽ tạo ra các segment  Global variables  Procedure call stack  Procedure/function code  Local variable  Trình loader sẽ gán mỗi segment một số định danh riêng procedure stack symbol table function sqrt main program 63 Phân đoạn (2/3)  Dùng cơ chế phân đoạn (segmentation) trong 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ý gồm tên đoạn và độ dời (offset) bên trong đoạn đó (so sánh với phân trang!)  Cho phép không gian địa chỉ vật lý cấp cho process có thể không liên tục nhau 22 64 Phân đoạn (3/3) logical address space physical memory space segment 1 segment 2 segment 3 segment 4 65 Hiện thực phân đoạn  Địa chỉ luận lý là một cặp (segment number, offset)  Bảng phân đoạn (segment table): gồm nhiều mục, mỗi mục mô tả một segment và chứa  limit, xác định kích thước của segment  base, chứa địa chỉ khởi đầu của segment trong bộ nhớ  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 66 Một ví dụ về phân đoạn procedure stack symbol table function sqrt main program segment 0 segment 3 segment 1 segment 2 segment 4 procedure stack main symbol table function sqrt limit base 0 1000 1400 1 400 6300 2 400 4300 3 1100 3200 4 1000 4700 segment table logical address space physical memory space 1400 2400 3200 4300 4700 5700 6300 23 67 Phần cứng hỗ trợ phân đoạn CPU  + physical memory no trap; addressing error limit base s s d yes segment table 68 Phân đoạn: Chuyển đổi địa chỉ  Ví dụ 69 Chia sẻ các đoạn editor data 1 segment 0 segment 1 logical address space process P1 editor data 2 segment 0 segment 1 logical address space process P2 limit base 0 25286 43062 1 4425 68348 segment table process P1 limit base 0 25286 43062 1 8850 90003 segment table process P2 editor data 1 data 2 physical memory 43062 72773 68348 90003 98853 24 70 Kết hợp phân trang và phân đoạn (1/2)  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ớ, mặc dù đủ không gian trống, do phân mảnh ngoại  Ý 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 71 Kết hợp phân trang và phân đoạn (2/2)  Có nhiều cách kết hợp. Một cách đơn giản là segmentation with paging • Mỗi process sẽ được cấp:  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 72 frame 0 frame 1 frame 2 frame 3 frame 4 frame 5 frame 6 Segmentation with paging (1/3) (STE: segment table entry PTE: page table entry) Fig from Gottlieb 25 73 Segmentation with paging (2/3) 74 Segmentation with paging (3/3)  Segment base: địa chỉ thực của bảng phân trang của segment  present (hay valid-invalid) 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,