Chương 3 Quản lý bộ nhớ 1 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 2 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? 3 Đị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 ? 4 Địa chỉ và chuyển đổi địa chỉ (2) Test.cpp Bộ nhớ chính 5 Địa chỉ và chuyển đổi địa chỉ (4) 6 Địa chỉ và chuyển đổi địa chỉ (3) • Các bước chuyển đổi chương trình 7 Các loại địa chỉ 8 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 9 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 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 10 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 11 Các yêu cầu quản lý bộ nhớ 12 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 13 Cấp phát liên tục 14 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 15 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 16 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 17 Cấp phát liên tục – dynamic partitioning • Dynamic partitioning 18 Cấp phát liên tục – dynamic partitioning • Dynamic partitioning – nhận xét – Phân mảnh ngoại (external fragmentation) 19 Cấp phát liên tục dynamic partitioning 20 Cấp phát liên tục dynamic partitioning 21 • 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.
22 Cấp phát liên tục • Cách chuyển đổi địa chỉ – Linker Loader • Thực hiện vào thời điểm nạp – Base & Bound • Thực hiện vào thời điểm run-time 23 Cấp phát liên tục 24 Hai thanh ghi hổ trợ chuyển đổi địa chỉ 25 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 – Segmentation – Paging • Không gian địa chỉ vật lý : có thể được tổ chức – Variable partitions : segmentation – Fixed partitions : frame 26 Cấp phát không liên tục Segmentation (1) 27 Cấp phát không liên tục Segmentation (2) • 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 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 28 Cấp phát không liên tục Segmentation (3) 29 Cấp phát không liên tục Segmentation (4) 30 Cấp phát không liên tục Segmentation (5) 31 Cấp phát không liên tục Segmentation (6) 32 Cấp phát không liên tục Segmentation (7) • Bài tập : một segment table Segment Length 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.300 33 Cấp phát không liên tục Segmentation (8) 34 Cấp phát không liên tục Paging (1) • Mô hình – 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 – Các page của 1 chương trình có thể nạp vào những frame không nằm liên tục nhau 35 Cấp phát không liên tục Paging (2) 36 Cấp phát không liên tục Paging (3) • Chuyển đổi địa chỉ trong mô hình paging 37 Cấp phát không liên tục Paging (4) 38 Cấp phát không liên tục Paging (5) • 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 39 • 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 40 • 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 41 Cấp phát không liên tục Paging (6) 42 Cấp phát không liên tục Paging (7) • 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 43 Cấp phát không liên tục Paging (8) 44 Cấp phát không liên tục Paging (9) 45 Cấp phát không liên tục Paging (10) • 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 • <page> : số hiệu page mà frame đang chứa • <idp> : id của tiến trình đang sở hữu trang – Địa chỉ ảo là <idp, p, d> 46 Cấp phát không liên tục Paging (11) 47 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 48 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 49 50