Bài giảng Hệ điều hành - Chương 7: Quản lý bộ nhớ (Tiếp theo) - Trường Đại học Công nghệ thông tin

40 trang Hùng Dũng 04/01/2024 690

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 7: Quản lý bộ nhớ (Tiếp theo) - Trường Đại học Công nghệ thông tin", để 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:

bai_giang_he_dieu_hanh_chuong_7_quan_ly_bo_nho_tiep_theo_tru.pdf

Nội dung text: Bài giảng Hệ điều hành - Chương 7: Quản lý bộ nhớ (Tiếp theo) - Trường Đại học Công nghệ thông tin

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 1 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ớ? 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 2
Câu hỏi ơn tập chương 7-1 (tt)  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? 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 3
Câu hỏi ơn tập chương 7-1 (tt) 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 tốn First fit, Best fit, Next fit (con trỏ đang ở vị trí 500K), Worst fit? Thuật tốn nào cho phép sử dụng bộ nhớ hiệu quả nhất trong trường hợp trên 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 4
Cơ chế phân trang  Bộ nhớ vật lý  khung trang (frame). Kích thước của frame là lũy thừa của 2, từ khoảng 512 byte đến 16MB.  Bộ nhớ luận lý (logical memory) hay khơng gian địa chỉ luận lý là tập mọi địa chỉ luận lý mà một chương trình bất kỳ cĩ thể sinh ra  page. Ví dụ MOV REG,1000 //1000 là một địa chỉ luận lý  Bảng phân trang (page table) để ánh xạ địa chỉ luận lý thành địa chỉ thực 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 7
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 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. physical memory 8
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 của khơng gian địa chỉ ảo là 2m, và kích thước của trang là 2n (đơn vị là byte hay word tùy theo kiến trú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) Bảng trang sẽ cĩ tổng cộng 2m/2n = 2m - n mục (entry) 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 10
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 củ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, gọi là thanh ghi kết hợp (associative register) hoặc translation look-aside buffers (TLBs) 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 14
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 kỳ 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 + ε 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 17
Effective access time (EAT) (tt)  Ví dụ 1: đơn vị thời gian nano  Ví dụ 2: đơn vị thời gian nano giây 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) × 0.98 + (200 + 20) × 0.2 (200 + 20) × 0.02 = 1.2 × 100 + 20 = 1.02 × 100 + 20 = 140 = 122 1/17/2018 Copyrights 2017 CE-UIT . All Rights Reserved. 18
Tổ chức bảng trang  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í dụ: Phân trang 2 cấp Số trang Độ dời trang P1 P2 d 10 bit 10 bit 12 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 19
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  Ngồi ra, cò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 của process, do đĩ là một trang hợp lệ. “invalid”: cho biết là trang khơng của process, do đĩ là một trang bất hợp lệ. 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 22
Bảo vệ bằng valid/invalid bit 00000 frame valid/ number invalid bit 14 bit 0 1 2 3 4 10468 12287 5 6 7 16383  Mỡi trang nhớ cĩ kích thước 2K = 2048  Process cĩ kích thước10,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 1/17/2018hay khơng. Copyrights 2017 CE-UIT. All Rights Reserved. 23
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 7 ed 1 0 3 data 2 ed 2 1 4 ed 2 2 6 3 2 data 3 Process 3 Bợ nhớ thực 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 24
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 củ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ý của chương trình, như main program, procedure, function local variables, global variables, common block, stack, symbol table, arrays, 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 25
User view của một chương trình  Thơng thường, một chương trình được stack biên dịch. Trình biên dịch sẽ tự động procedure xây dựng các segment. symbol  Ví dụ, trình biên dịch Pascal sẽ tạo ra table các segment sau: function Global variables sqrt Procedure call stack main program Procedure/function code Local variable  Trình loader sẽ gán mỡi segment một sớ định danh riêng. Logical address space 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 26
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!) 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 27
Cài đặt phan đ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 của segment trong bộ nhớ limit, xác định kích thước củ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 của chương trình  ⇒ Một chỉ sớ segment s là hợp lệ nếu s < STLR 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 29
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 physical memory space 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 30
Chia sẻ các đoạn editor data 1 43062 segment 0 segment 1 segment table process P1 logical address space 68348 process P 1 72773 editor data 2 90003 segment 1 segment 0 98853 segment table process P2 logical address space process P physical memory 1/17/2018 2 Copyrights 2017 CE-UIT. All Rights Reserved. 33
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 của phân trang và phân đoạn: Vấn đề củ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ớ. Ý tưởng giải quyết: paging đoạn, khi đĩ chỉ cần giữ trong bộ nhớ các page của đoạn hiện đang cần. Logic Addr = 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 34
Kết hợp phân trang và phân đoạn (tt) 1/17/2018
Bài tập 1 Xét một khơng gian địa chỉ cĩ 12 trang, mỡi trang cĩ kích thước 2K, ánh xạ vào bộ nhớ vật lý cĩ 32 khung trang. a. Địa chỉ logic gờm bao nhiêu bit? b. Địa chỉ physic gờm bao nhiêu bit? 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 38
Bài tập 2 Xét một hệ thớng sử dụng kỹ thuật phân trang, với bảng trang được lưu trữ trong bộ nhớ chính. a. Nếu thời gian cho một lần truy xuất bộ nhớ bình thường là 200ns thì mất bao nhiêu thời gian cho một thao tác truy xuất bộ nhớ trong hệ thớng này? b. Nếu sử dụng TLBs với hit-ratio là 75%, thời gian để tìm tròn TLBs xem như bằng 0, tính thời gian truy xuất bộ nhớ trong hệ thớng 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 39