Hệ điều hành - Chương 3: Quản lý bộ nhớ - Ngô Hữu Dũng

HỆ ĐIỀU HÀNH (OPERATING SYSTEM CONCEPTS) Wiley - Operating System Concepts(Silberschatz).9th 1.2 Giới thiệu môn học  Mục tiêu môn học  Vai trò của HĐH  Nguyên lý hoạt động của HĐH đa nhiệm  Nội dung  Phần 1: Tổng quan (Overview)  Phần 2: Quản lý tiến trình (Process Management)  Phần 3: Quản lý bộ nhớ (Memory Management)  Phần 4: Quản lý I/O (I/O Management)  Phần 5: Quản lý hệ thống file (Storage Management) 1.3 CHƯƠNG 3: QUẢN LÝ BỘ NHỚ Memory Management 1.4 Dẫn nhập:  Bộ nhớ chính là thiết bị lưu trữ duy nhất thông qua đó CPU có thể trao đổi thông tin với môi trường ngoài  Bộ nhớ chính được tổ chức như một mảng một chiều các từ nhớ (word), mỗi từ nhớ có một địa chỉ  Hầu hết các hệ điều hành hiện đại đều cho phép chế độ đa nhiệm => có nhiều process trong bộ nhớ tại một thời điểm => cần vai trò quản lý bộ nhớ của OS 1.5 Chức năng quản lý bộ nhớ của OS  Sự tương ứng giữa địa chỉ logic và địa chỉ vật lý (physic) : làm cách nào để chuyển đổi một địa chỉ tượng trưng (symbolic) trong chương trình thành một địa chỉ thực trong bộ nhớ chính?  Quản lý bộ nhớ vật lý: làm cách nào để mở rộng bộ nhớ có sẵn nhằm lưu trữ được nhiều tiến trình đồng thời?  Chia sẻ thông tin: làm thế nào để cho phép hai tiến trình có thể chia sẻ thông tin trong bộ nhớ?  Bảo vệ: làm thế nào để ngăn chặn các tiến trình xâm phạm đến vùng nhớ được cấp phát cho tiến trình khác? 1.6 Địa chỉ và chuyển đổi địa chỉ (1)  Địa chỉ  Logic => không gian địa chỉ logic  Vật lý => không gian đia chỉ vật lý  Chuyển đổi địa chỉ logic => vật lý  3 thời điểm chuyển đổi  Được thực hiện bởi ai?  Ưu nhược điểm ? 1.7 Địa chỉ và chuyển đổi địa chỉ (2) Test.c pp Bộ nhớ chính 1.8 Địa chỉ và chuyển đổi địa chỉ (3)  Các bước chuyển đổi chương trình 1.9 Địa chỉ và chuyển đổi địa chỉ (4) 1.10 Các loại địa chỉ  Địa chỉ logic: con 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à chương 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 1.11 Chuyển đổi địa chỉ (1)  Việc chuyển đổi địa chỉ logic -> địa chỉ vật lý có thể thực hiện vào một trong 3 thời điểm  compile time  load time  execution time  Nhận xét  Compile time :  Thực hiện vào thời điểm biên dịch  Phải biết trước vị trí nap tiến trình trong bộ nhớ -> biêndịchlại cho những lần nạp sau 1.12 Chuyển đổi địa chỉ (2) • Nhận xét  load time  Thựchiện bởi bộ loader, khi nạp vào bộ nhớ  Khi có sự thay đổi vị trí của tiến trình (sau đó) cần load lại để tính toán lại địa chỉ  Execution (run) time  Nếu trong quá trình thực thi tiến trình có di chuyển vị trí tiến trình thì thời điểm chuyển đổi địa chỉ là run time  Cần dùng cơ chế phần cứng đặc biệt 1.13 Chuyển đổi địa chỉ (3)  MMU (memory-management unit)– phần cứng giúp chuyển đổi địa chỉ vào thời điểm run-time 1.14 Các 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ữ nhiều tiến trình trong BNC?  Các yêu cầu tổ chức lưu trữ tiến trình:  Relocation  Protection  Sharing  Logical Organization  Physical Organization 1.15 Các mô hình tổ chức bộ nhớ  Tiến trình được nạp toàn bộ vào bộ nhớ  Vùng nhớ cấp cho tiến trình có thể :  Liên tục  Fixed partitioning  Dynamic partitioning  Không liên tục  Segmentation  Paging 1.16 Cấp phát liên tục  Nguyên tắc:  Chương trình được nạp toàn thể vào BNC để thi hành  Cần 1 vùng nhớ liên tục, đủ lớn để chứa Chương trình  KGĐC: liên tục  KGVL: có thể tổ chức  Fixed partition  Variable partition (Dynamic partition)  2 mô hình đơn giản  Linker Loader  Base & Bound 1.17 Cấp phát liên tục – fixed partitioning  Fixed partitioning  Có 2 loại partition :  Kích thước bằng nhau  Không bằng nhau 1.18 Cấp phát liên tục – fixed partitioning  Fixed partitioning  Chiến lược cấp phát  Sử dụng hàng đợi  Nhiều hàng đợi  1 hàng đợi 1.19 Cấp phát liên tục – fixed partitioning  Fixed partitioning- Nhận xét :  Phân mảnh nội (internal fragmentation)  Mức độ đa chương phụ thuộc bởi số partition 1.20 Cấp phát liên tục – dynamic partitioning  Dynamic partitioning 1.21 Cấp phát liên tục – dynamic partitioning  Dynamic partitioning – nhận xét  Phân mảnh ngoại (external fragmentation) 1.22 Cấp phát liên tục dynamic partitioning 1.23 Cấp phát liên tục dynamic partitioning Cấp phát bộ nhớ kích thước X được thực hiện như thế nào? First-fit: cấp phát vùng trống đầu tiên đủ cho yêu cầu. Best-fit: cấp phát vùng trống nhỏ nhất vừa đủ yêu cầu; phải duyệt toàn danh sách, nếu không sắp theo thứ tự. Sẽ tạo ra vùng nhớ trống dư ra nhỏ nhất. Worst-fit: cấp phát vùng trống lớn nhất; phải duyệt toàn danh sách. Sẽ tạo những ô trống dư ra lớn nhất. First-fit và best-fit tốt hơn worst-fit về mặt tốc độ và việc tận dụng bộ nhớ. 1.24 Cấp phát liên tục dynamic partitioning 1.25  Bài tập 1 Trong mô hình cấp phát bộ nhớ liên tục, có bốn phân mảnh bộ nhớ theo thứ tự với kích thước là 600KB, 500KB, 200KB, 300KB. Giả sử có 4 tiến trình đang chờ cấp phát bộ nhớ theo thứ tự P1, P2, P3, P4. Kích thước tương ứng của các tiến trình trên là: 212 KB, 417 KB, 112 KB, 426 KB. Hãy cấp phát bộ nhớ cho các tiến trình trên theo thuật toán First-fit, Best-fit, Worst-fit. 1.26 Memory Compaction (Garbage Collection)  Giải quyết vấn đề External Fragmentaion:  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 1.27 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 quả 1.28 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ỉ (logic) : phân chia thành nhiều partition  Segmentation  Paging  Không gian địa chỉ vật lý : có thể được tổ chức  Variable (Dynamic) partitions : segmentation  Fixed partitions : paging 1.29 Cấp phát không liên tục Segmentation (0)  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 bao 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 các dynamic partitions  Nạp tiến trình:  Mỗi segment cần được nạp vào 1 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 1.30 Cấp phát không liên tục Segmentation (1) 1.31 Cấp phát không liên tục Segmentation (2)  Đ/chỉ logic:  Đ/chỉ physic:  Chuyển đổi địa chỉ:   Chuyển đổi địa chỉ vào lúc run-time - MMU thi hành - sử dụng segment table để lưu thông tin cấp phát bộ nhớ - mỗi tiến trình có một segment table  Lưu trữ segment table : - Cache : nếu đủ nhỏ - Bộ nhớ chính : segment-table base register, segment-table length register - Số phần tử của segment table = số segment của chương trình 1.32 Cấp phát không liên tục Segmentation (3)  Chuyển đổi địa chỉ trong mô hình Segmentation 1.33 Cấp phát không liên tục Segmentation (4) 1.34 Cấp phát không liên tục Segmentation (5) 1.35 Cấp phát không liên tục Segmentation (6)  Logical-to-Physical Address Translation in Segmentation 1.36 Cấp phát không liên tục Segmentation (7)  Bài tập : một segment table Segment Limit Base 0 500 215 1 25 2100 2 100 120 Xác định địa chỉ vật lý của các địa chỉ logic sau ?  0.410  1.12  2.300 1.37 Cấp phát không liên tục Segmentation (8) 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 partirion: chịu đựng  Dynamic allocation: chọn vùng nhớ để cấp cho 1 segment  First fit, Best fit, Worst fit   External Fragmentation:  Memory Compaction: chi phí cao 1.38 Cấp phát không liên tục Paging (1)  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  KGVL ( bộ nhớ) được 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 1 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 1.39 Cấp phát không liên tục Paging (2) 1.40 Cấp phát không liên tục Paging (3)  Địa 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 để luu 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ó 1 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) 1.41 Cấp phát không liên tục Paging (4)  Chuyển đổi địa chỉ trong mô hình paging 1.42 Cấp phát không liên tục Paging (5) 1.43 Cấp phát không liên tục Paging (6)  Bài tập : Một tiến trình được nạp vào bộ nhớ theo mô hình phân trang với kích thước trang là 1024 byte. Bảng trang P F 0 1 1 4 2 2 3 6 Chuyển địa chỉ logic thành địa chỉ vật lý : 1642 3671 1.44  1642  xác định p? d? 1642 div 1024 = 1 => p =1 1642 mod 1024 = 618 => d = 618  Xác định f ? Theo bảng trang : f =4  Xác định địa chỉ vật lý : 1642 => 4 * 1024 + 618 = 4714 1.45  3671  Xác định p? d? 3671 div 1024 = 3 => p =3 3671 mod 1024 = 599 =>d = 599  Xác định f ? F = 6  Xác định địa chỉ vật lý ? 3671 => 6 * 1024 + 599 = 6743 1.46 Cấp phát không liên tục Paging (7) NHẬN XÉT MÔ HÌNH PAGING Loại bỏ  Dynamic Allocation  External Fragmentation 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ỉ 1.47 Cấp phát không liên tục Paging (8)  Lưu trữ Page table : tiết kiệm không gian  Sử dụng bảng trang đa cấp  Chỉ lưu thường trực bảng trang cấp 1, sau đó khi cần sẽ nạp bảng trang thích hợp  Sử dụng bảng trang nghịch đảo  Mô tả không gian vật lý thay vì KGĐC 1.48 Cấp phát không liên tục Paging (9) 1.49 Cấp phát không liên tục Paging (10) 1.50 Cấp phát không liên tục Paging (11)  Bảng trang nghịch đảo :  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  : id của tiến trình đang sở hữu trang  Địa chỉ ảo là 1.51 Cấp phát không liên tục Paging (12) 1.52 Bộ nhớ ảo  Các mô hình quản lý bộ nhớ đã học :  Nạp toàn bộ tiến trình vào bộ nhớ rồi thi hành  Vấn đề : (1) Nếu kích thước tiến trình lớn hơn dung lượng bộ nhớ chính (2) Tại một thời điểm chỉ có 1 chỉ thị được thi hành  Mô hình bộ nhớ ảo :  Nạp và thi hành từng phần của tiến trình 1.53 Bộ nhớ ảo  Bộ nhớ ảo với cơ chế phân trang  Phân chia Không gian địa chỉ logic thành các page  Dùng bộ nhớ phụ (disk) để mở rộng bộ nhớ chính, lưu trữ các phần của tt chưa được nạp  Bổ sung bit cờ hiệu trong Page Table để nhận dạng tình trạng của một page đã được nạp vào bộ nhớ chính chưa  Cơ chế chuyển đổi giữa BNC và BNP : swapping 1.54 1.55 1.56 1.57 Lỗi trang và thay thế trang  Truy suất đến một trang được đánh dấu bất hợp lệ (invalid) sẽ làm phát sinh lỗi trang, hdh sẽ thực hiện : 1. Xác định vị trí trang muốn truy suất trên đĩa 2. Tìm một khung trang trống trong bộ nhớ chính 1. Nếu tìm thấy -> đến bước 3 2. Nếu ko còn khung trang trống -> chọn 1 nạn nhân 3. Chuyển trang từ đĩa vào bnc; cập nhật nội dung bảng trang, bảng khung trang 4. Tái kích hoạt tiến trình của người dùng 1.58 Các thuật toán thay thế trang  Mục tiêu : chọn trang “nạn nhân” là trang mà sau khi thay thế sẽ gây ra ít lỗi trang nhất  Các thuật toán :  FIFO  Ghi nhận thời điểm trang vào bnc => trang ở lâu nhất được chọn  OPT ( tối ưu)  Thay thế trang sẽ lâu được sử dụng nhất trong tương lai => ko khả thi  LRU (least recently used)  Ghi nhận thời điểm cuối cùng trang được truy cập =>trang lâu nhất chưa được truy suất là trang được chọn 1.59  Bài tâp Xét chuỗi truy xuất bộ nhớ sau: 1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3 Giả sử bộ nhớ vật lí có 4 khung trang. Minh họa kết quả trình thay thế trang với các thuật toán thay thế sau: a) FIFO b) OPT c) LRU 1.60  FIFO 1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 * * * * * * * * * * *  1 1 1 1 1  5 5 5 5  3 3 3  2 2 2 2 2  6 6 6 6  7 7  3 3 3 3 3  2 2 2 2  6  4 4 4 4 4  1 1 1 1 1 -Sử dụng 4 khung trang -Ban đầu cả 4 khung trang đều trống -* : có lỗi trang -  : trang được nạp từ đĩa vào bộ nhớ 1.61  OPT 1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 * * * * * * *  1 1 1 1 1 1 1 1 1 1 1  7 7  2 2 2 2 2 2 2 2 2 2 2 2 2  3 3 3 3 3 3 3 3 3 3 3 3  4 4   6 6 6 6 6 6 6 1.62  LRU 1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 * * * * * * * * *  1 1 1 1 1 1 1 1 1 1 1 1  6  2 2 2 2 2 2 2 2 2 2 2 2 2  3 3 3  5 5 5 5  3 3 3  4 4 4  6 6 6 6  7 7 1.63  Đánh giá  Số lỗi trang : FIFO > LRU > OPT  FIFO : dễ cài đặt ; 1.64  Xem xét chuỗi tham chiếu trang sau: 1,2,3,4,2,1,5,6,2,1,4,5,7,6,3,1 Bao nhiêu page_fault xuất hiện đối với giải thuật thay page FIFO, OPT, LRU (giả thuyết là được cấp 4 frame).