Bài giảng Hệ điều hành - Chương 3: Quản lý bộ nhớ - Đặng Minh Quân

Hệ điều hành 
Chương 3 : Quản lý bộ nhớ 
Tổng quan 
Giới thiệu tổng quan về quản lý bộ nhớ 
Cấp phát bộ nhớ liên tục 
Cấp phát bộ nhớ không liên tục 
Bộ nhớ ảo 
Vấn đề 
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 nhằm nâng cao hiệu suất sử dụng CPU. Tuy nhiên kỹ thuật này lại làm nảy sinh nhu cầu chia sẻ bộ nhớ giữa các tiến trình khác nhau . Vấn đề nằm ở chỗ  : «    bộ nhớ thì hữu hạn và các yêu cầu bộ nhớ thì vô hạn ». 
Vấn đề 
Thông thường , một chương trình được lưu trữ trên đĩa như một tập tin nhị phân có thể xử lý . 
Các địa chỉ trong chương trình nguồn là địa chỉ tượng trưng , vì thế , một chương trình phải trải qua nhiều giai đoạn xử lý để chuyển đổi các địa chỉ này thành các địa chỉ tuyệt đối trong bộ nhớ chính . 
Không gian điạ chỉ và không gian vật lý 
Địa chỉ logic – còn gọi là địa chỉ ảo , là tất cả các địa chỉ do CPU tạo ra . 
Địa chỉ vật lý - là địa chỉ thực tế mà 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 . 
Cấp phát liên tục - Mô hình Linker_Loader 
Ý tưởng : Tiến trình được nạp vào một vùng nhớ liên tục đủ lớn để chứa toàn bộ tiến trình . 
Hệ điều hành sẽ trả về địa chỉ bắt đầu nạp tiến trình , và tính toán để chuyển các địa chỉ tương đối về địa chỉ tuyệt đối trong bộ nhớ vật lý theo công thức địa chỉ vật lý = địa chỉ bắt đầu + địa chỉ tương đối . 
Cấp phát liên tục - Mô hình Linker_Loader 
Thời điểm kết buôc địa chỉ là thời điểm nạp , do vậy sau khi nạp không thể dời chuyển tiến trình trong bộ nhớ . 
Không có khả năng kiểm soát địa chỉ các tiến trình truy cập , do vậy không có sự bảo vệ . 
Cấp phát liên tục - Mô hình Base &Bound 
Ý tưởng : Tiến trình được nạp vào một vùng nhớ liên tục đủ lớn để chứa toàn bộ tiến trình . 
Khi một tiến trình được cấp phát vùng nhớ , nạp vào thanh ghi nền địa chỉ bắt đầu của phân vùng được cấp phát cho tiến trình , và nạp vào thanh ghi giới hạn kích thước của tiến trình . 
Sau đó , mỗi địa chỉ bộ nhớ được phát sinh sẽ tự động được cộng với địa chỉ chứa trong thanh ghi nền để cho ra địa chỉ tuyệt đối trong bộ nhớ , các địa chỉ cũng được đối chiếu với thanh ghi giới hạn để bảo đảm tiến trình không truy xuất ngoài phạm vi phân vùng được cấp cho nó . 
Cấp phát liên tục - Mô hình Base &Bound 
Cấp phát liên tục - Mô hình Base &Bound 
Một ưu điểm của việc sử dụng thanh ghi nền là có thể di chuyển các chương trình trong bộ nhớ sau khi chúng bắt đầu xử lý . 
Chịu đựng hiện tượng phân mảnh ngoại vi( external fragmentation ) 
P hân mảnh ngoại vi 
Cấp phát không liên tục - Phân đoạn 
Ý tưởng : quan niệm không gian địa chỉ là một tập các phân đoạn (segments) – các phân đoạn là những phần bộ nhớ kích thước khác nhau và có liên hệ logic với nhau . 
 Mỗi phân đoạn có một tên gọi (số hiệu phân đoạn) và một độ dài. Người dùng sẽ thiết lập mỗi địa chỉ với hai giá trị : . 
Cấp phát không liên tục - Phân đoạn 
S ự chuyển đổi được thực hiện qua một bảng phân đoạn . Mỗi thành phần trong bảng phân đoạn bao gồm một thanh ghi nền và một thanh ghi giới hạn . 
Mỗi địa chỉ ảo là một bộ  : 
số hiệu phân đoạn s : được sử dụng như chỉ mục đến bảng phân đoạn 
địa chỉ tương đối d : có giá trị trong khoảng từ 0 đến giới hạn chiều dài của phân đoạn . 
Cấp phát không liên tục - Phân đoạn 
Cấp phát không liên tục - Phân đoạn 
Một ưu điểm đặc biệt của cơ chế phân đoạn là khả năng đặc tả thuộc tính bảo vệ cho mỗi phân đoạn . 
Một ưu điểm khác của kỹ thuật phân đoạn là khả năng chia sẻ ở mức độ phân đoạn . 
Phân đoạn – Cấp phát động 
L àm thế nào để thỏa mãn một yêu cầu vùng nhớ kích thước N ? 
Cần phải chọn vùng nhớ nào trong danh sách vùng nhớ tự do để cấp phát  ? 
Như vậy cần phải ghi nhớ hiện trạng bộ nhớ để có thể cấp phát đúng . 
Phân đoạn – Quản lý bằng một bảng các bit  
bộ nhớ được chia thành các đơn vị cấp phát , mỗi đơn vị được phản ánh bằng một bit trong bảng các bit, một bit nhận giá trị 0 nếu đơn vị bộ nhớ tương ứng đang tự do, và nhận giá trị 1 nếu đơn vị tương ứng đã được cấp phát cho một tiến trình . 
Phân đoạn – Quản lý bằng danh sách   
Tổ chức một danh sách các phân đoạn đã cấp phát (P) và phân đoạn tự do (H). 
Các thuật toán thông dụng để chọn một phân đoạn tự do trong danh sách để cấp phát cho tiến trình là  : 
First-fit: cấp phát phân đoạn tự do đầu tiên đủ lớn . 
Best-fit: cấp phát phân đoạn tự do nhỏ nhất nhưng đủ lớn để thõa mãn nhu cầu . 
Worst-fit : cấp phát phân đoạn tự do lớn nhất . 
Phân trang 
Phân bộ nhớ vật lý thành các khối (block) có kích thước cố định và bằng nhau, gọi là khung trang (page frame) . 
 Không gian địa chỉ cũng được chia thành các khối có cùng kích thước với khung trang, và được gọi là trang ( page ). 
Khi cần nạp một tiến trình để xử lý, các trang của tiến trình sẽ được nạp vào những khung trang còn trống. Một tiến trình kích thước N trang sẽ yêu cầu N khung trang tự do. 
Phân trang 
Phân trang 
Cơ chế phần cứng hỗ trợ thực hiện chuyển đổi địa chỉ trong cơ chế phân trang là bảng trang ( pages table ). Mỗi phần tử trong bảng trang cho biết các địa chỉ bắt đầu của vị trí lưu trữ trang tương ứng trong bộ nhớ vật lý 
Mỗi địa chỉ phát sinh bởi CPU được chia thành hai phần : 
số hiệu trang (p) : sử dụng như chỉ mục đến phần tử tương ứng trong bảng trang . 
địa chỉ tương đối trong trang (d) : kết hợp với địa chỉ bắt đầu của trang để tạo ra địa chỉ vật lý mà trình quản lý bộ nhớ sử dụng . 
Kích thước của trang do phần cứng qui định . 
Phân trang 
Phân trang – Chia sẻ bộ nhớ 
C ho phép chia sẻ các trang giữa các tiến trình . 
Phân trang – Thảo luận 
Kỹ thuật phân trang loại bỏ được hiện tượng phân mảnh ngoại vi : mỗi khung trang đều có thể được cấp phát cho một tiến trình nào đó có yêu cầu . 
Tuy nhiên hiện tượng phân mảnh nội vi vẫn có thể xảy ra khi kích thước của tiến trình không đúng bằng bội số của kích thước một trang , khi đó , trang cuối cùng sẽ không được sử dụng hết . 
Kết hợp phân đoạn và phân trang 
Không gian địa chỉ là một tập các phân đoạn, mỗi phân đoạn được chia thành nhiều trang. 
Khi một tiến trình được đưa vào hệ thống, hệ điều hành sẽ cấp phát cho tiến trình các trang cần thiết để chứa đủ các phân đoạn của tiến trình . 
Cần có một bảng phân đoạn , nhưng giờ đây mỗi phân đoạn cần có một bảng trang phân biệt. 
Kết hợp phân đoạn và phân trang 
Mỗi địa chỉ logic là một bộ ba : 
số hiệu phân đoạn (s) : sử dụng như chỉ mục đến phần tử tương ứng trong bảng phân đoạn . 
số hiệu trang (p) : sử dụng như chỉ mục đến phần tử tương ứng trong bảng trang của phân đoạn . 
địa chỉ tương đối trong trang (d): kết hợp với địa chỉ bắt đầu của trang để tạo ra địa chỉ vật lý mà trình quản lý bộ nhớ sử dụng . 
Kết hợp phân đoạn và phân trang