Giáo trình Nguyên Lý Hệ Điều Hành Phần 2: Điều Khiển và Quản Lý Bộ Nhớ

• Trường học: Không rõ
• Chuyên ngành: Hệ điều hành
• Đề tài: Quản Lý Bộ Nhớ
• Loại tài liệu: Bài giảng
• Năm xuất bản: Không rõ
• Địa điểm: Không rõ

Mục lục chi tiết

• 3. CHƯƠNG 3: ĐIỀU KHIỂN BỘ NHỚ
• 3.1. Một số khái niệm liên quan đến bộ nhớ
• 3.2. Quản lý phân phối bộ nhớ. Vấn đề bảo vệ bộ nhớ
• 3.3. Điều khiển bộ nhớ trong chế độ đơn chương trình
• 3.4. Điều khiển bộ nhớ liên tục theo đa bài toán
• 3.5. Giới thiệu
• 3.6. Điều khiển bộ nhớ theo cận thay đổi
• 3.7. Quản lý bộ nhớ rỗi

Tóm tắt

I. Khám phá vai trò của quản lý bộ nhớ trong hệ điều hành

Quản lý bộ nhớ là một trong những chức năng cốt lõi và phức tạp nhất của mọi hệ điều hành hiện đại. Nhiệm vụ chính của nó là điều phối và phân bổ tài nguyên bộ nhớ chính một cách hiệu quả cho nhiều tiến trình đang chạy đồng thời. Nếu không có một cơ chế quản lý chặt chẽ, các chương trình có thể ghi đè lên dữ liệu của nhau, gây ra lỗi hệ thống và làm giảm hiệu suất tổng thể. Mục tiêu cơ bản của quản lý bộ nhớ là đảm bảo mỗi tiến trình có không gian riêng để hoạt động, bảo vệ không gian đó khỏi sự truy cập trái phép, và tối ưu hóa việc sử dụng dung lượng bộ nhớ vật lý có hạn. Để làm được điều này, hệ điều hành phải theo dõi trạng thái của từng vùng nhớ, quyết định cấp phát cho tiến trình nào, và thu hồi khi tiến trình kết thúc. Nền tảng của quá trình này là sự phân biệt rõ ràng giữa không gian địa chỉ mà chương trình "nhìn thấy" và không gian địa chỉ thực tế trên phần cứng, một khái niệm sẽ được làm rõ trong các phần tiếp theo.

1.1. Mục tiêu và nhiệm vụ cốt lõi của quản lý bộ nhớ

Bài toán cơ bản của điều phối bộ nhớ là giải quyết ba yêu cầu chính. Thứ nhất là phân phối các vùng nhớ cho chương trình và dữ liệu để chúng có thể thực thi một cách chính xác. Thứ hai là bảo vệ chương trình và dữ liệu không bị xóa hoặc chồng chéo bởi các tiến trình khác. Cuối cùng là sử dụng bộ nhớ hiệu quả nhất có thể. Để đạt được các mục tiêu này, hệ điều hành phải có khả năng phân rã không gian địa chỉ để tránh xung đột, đồng thời cho phép chia sẻ bộ nhớ khi cần thiết. Ví dụ, nhiều tiến trình người dùng có thể cần truy cập vào cùng một thư viện hệ thống. Cơ chế quản lý bộ nhớ phải hỗ trợ việc dùng chung này một cách an toàn, đảm bảo tính toàn vẹn của cả hệ thống và các ứng dụng.

1.2. Phân biệt không gian địa chỉ logic và địa chỉ vật lý

Một khái niệm nền tảng trong quản lý bộ nhớ là sự tách biệt giữa hai loại không gian địa chỉ. Không gian địa chỉ logic (hay địa chỉ ảo) là tập hợp các địa chỉ được tạo ra bởi CPU trong quá trình một chương trình thực thi. Chương trình và lập trình viên làm việc với không gian này mà không cần biết về cấu trúc vật lý của bộ nhớ. Ngược lại, không gian địa chỉ vật lý là tập hợp các địa chỉ thực tế trong bộ nhớ chính (RAM). Địa chỉ vật lý là địa chỉ mà bộ điều khiển bộ nhớ "nhìn thấy". Việc ánh xạ từ địa chỉ logic sang địa chỉ vật lý là nhiệm vụ quan trọng, thường được thực hiện bởi phần cứng chuyên dụng.

1.3. Vai trò của MMU trong việc ánh xạ và bảo vệ bộ nhớ

Bộ quản lý bộ nhớ, hay MMU (Memory Management Unit), là một thành phần phần cứng thiết yếu nằm giữa CPU và bộ nhớ chính. Chức năng chính của MMU là chuyển đổi nhanh chóng các địa chỉ logic do CPU tạo ra thành các địa chỉ vật lý tương ứng. Quá trình này được gọi là "Binding địa chỉ lúc thực thi" (Execution time binding). MMU sử dụng các thanh ghi cơ sở và thanh ghi giới hạn để thực hiện việc ánh xạ. Ngoài ra, MMU còn đóng vai trò quan trọng trong việc bảo vệ bộ nhớ. Nó kiểm tra mọi địa chỉ do người dùng tạo ra, đảm bảo rằng địa chỉ đó nằm trong phạm vi hợp lệ đã được cấp phát cho tiến trình, từ đó ngăn chặn các truy cập trái phép vào không gian bộ nhớ của hệ điều hành hoặc của các tiến trình khác.

II. Phân mảnh Thách thức lớn nhất trong quản lý bộ nhớ

Một trong những vấn đề cố hữu và khó giải quyết nhất khi quản lý bộ nhớ là hiện tượng phân mảnh. Phân mảnh xảy ra khi các vùng nhớ trống không liên tục với nhau, bị xé lẻ thành nhiều mảnh nhỏ nằm rải rác. Mặc dù tổng dung lượng bộ nhớ trống có thể đủ lớn để đáp ứng một yêu cầu cấp phát, nhưng không có một vùng trống liên tục nào đủ lớn. Điều này dẫn đến lãng phí tài nguyên và suy giảm hiệu năng hệ thống. Hệ điều hành phải đối mặt với hai loại phân mảnh chính là phân mảnh nội và phân mảnh ngoại. Việc hiểu rõ bản chất và nguyên nhân gây ra chúng là bước đầu tiên để tìm ra các chiến lược cấp phát và kỹ thuật quản lý bộ nhớ hiệu quả hơn, nhằm giảm thiểu tác động tiêu cực của hiện tượng này.

2.1. Cấp phát bộ nhớ liên tục và nguyên nhân gây phân mảnh

Trong kỹ thuật cấp phát bộ nhớ liên tục, mỗi tiến trình khi được nạp vào sẽ chiếm một khối bộ nhớ duy nhất và liền kề. Kỹ thuật này đơn giản trong việc quản lý nhưng lại là nguyên nhân chính gây ra phân mảnh bộ nhớ. Khi các tiến trình được nạp vào và giải phóng khỏi bộ nhớ theo thời gian, chúng sẽ để lại các "lỗ hổng" (vùng trống) có kích thước khác nhau. Các lỗ hổng này nằm xen kẽ với các vùng đã được cấp phát. Khi một tiến trình mới cần bộ nhớ, hệ điều hành phải tìm một lỗ hổng đủ lớn. Quá trình này, lặp đi lặp lại, sẽ làm cho các vùng trống ngày càng bị chia nhỏ, dẫn đến phân mảnh.

2.2. Phân biệt phân mảnh nội và phân mảnh ngoại là gì

Có hai loại phân mảnh chính. Phân mảnh ngoại (External Fragmentation) xảy ra khi tổng dung lượng bộ nhớ trống đủ cho một yêu cầu nhưng không liên tục. Các vùng trống bị phân tán thành nhiều mảnh nhỏ, không có mảnh nào đủ lớn để chứa tiến trình mới. Đây là vấn đề của các hệ thống dùng cấp phát liên tục. Ngược lại, phân mảnh nội (Internal Fragmentation) xảy ra khi vùng nhớ được cấp phát cho một tiến trình lớn hơn so với nhu cầu thực tế của nó. Phần bộ nhớ dư thừa bên trong khối đã cấp phát này bị lãng phí vì không thể cấp cho tiến trình khác. Vấn đề này thường xuất hiện trong các hệ thống chia bộ nhớ thành các khối có kích thước cố định, ví dụ như trong kỹ thuật phân trang.

2.3. Các chiến lược cấp phát First fit Best fit và Worst fit

Để cấp phát bộ nhớ từ danh sách các vùng trống, hệ điều hành sử dụng các chiến lược khác nhau. Chiến lược "chọn cái đầu tiên" (First-fit) sẽ duyệt danh sách và chọn vùng trống đầu tiên đủ lớn. Chiến lược này nhanh nhưng có thể để lại nhiều mảnh vụn nhỏ. Chiến lược "chọn cái tốt nhất" (Best-fit) duyệt toàn bộ danh sách để tìm vùng trống nhỏ nhất mà vẫn đủ lớn. Cách này giảm lãng phí nhưng tốn thời gian tìm kiếm. Cuối cùng, Worst-fit chọn vùng trống lớn nhất, với hy vọng phần còn lại sẽ đủ lớn cho các yêu cầu sau này. Tuy nhiên, mỗi chiến lược đều có ưu nhược điểm riêng và không có giải pháp nào loại bỏ hoàn toàn được phân mảnh ngoại.

III. Phương pháp phân trang Giải pháp quản lý bộ nhớ tối ưu

Để khắc phục triệt để vấn đề phân mảnh ngoại do cấp phát liên tục gây ra, kỹ thuật phân trang (Paging) đã ra đời. Đây là một trong những phương pháp quản lý bộ nhớ phổ biến và hiệu quả nhất trong các hệ điều hành hiện đại. Ý tưởng cốt lõi của phân trang là cho phép không gian địa chỉ vật lý của một tiến trình có thể không liên tục. Thay vì cấp một khối nhớ lớn duy nhất, hệ điều hành chia bộ nhớ vật lý thành các khối có kích thước cố định gọi là khung trang (frame), và chia không gian địa chỉ logic của tiến trình thành các khối cùng kích thước gọi là trang (page). Bằng cách này, một tiến trình có thể được nạp vào các khung trang rải rác bất kỳ trong bộ nhớ, loại bỏ hoàn toàn phân mảnh ngoại. Tuy nhiên, nó lại có thể gây ra phân mảnh nội ở trang cuối cùng của tiến trình.

3.1. Cơ chế hoạt động của kỹ thuật phân trang Paging

Khi một tiến trình cần thực thi, các trang của nó sẽ được nạp vào các khung trang (Page Frame) còn trống trong bộ nhớ chính. Hệ điều hành duy trì một bảng trang (Page Table) cho mỗi tiến trình để theo dõi việc ánh xạ này. Địa chỉ logic do CPU tạo ra được chia làm hai phần: số hiệu trang (p) và độ dời trong trang (d). Số hiệu trang (p) được dùng làm chỉ số để tra cứu trong bảng trang, tìm ra địa chỉ cơ sở của khung trang tương ứng trong bộ nhớ vật lý. Địa chỉ vật lý cuối cùng được tính bằng cách cộng địa chỉ cơ sở của khung trang với độ dời (d). Cơ chế này cho phép các trang của một chương trình nằm rải rác, tạo ra sự linh hoạt tối đa trong việc sử dụng bộ nhớ.

3.2. Cấu trúc và chức năng của bảng trang Page Table

Mỗi tiến trình có một bảng trang riêng, lưu trữ ánh xạ giữa các trang logic và các khung trang vật lý. Mỗi phần tử trong bảng trang chứa số hiệu của khung trang vật lý nơi trang logic tương ứng được lưu trữ. Ngoài ra, mỗi phần tử còn có thể chứa các bit thông tin bổ sung như bit hợp lệ/không hợp lệ (valid/invalid bit) để bảo vệ, bit truy cập (access bit), và bit sửa đổi (dirty bit). Bảng trang được lưu trong bộ nhớ chính. Hệ điều hành sử dụng một thanh ghi đặc biệt (Page Table Base Register - PTBR) để trỏ đến vị trí bắt đầu của bảng trang của tiến trình đang chạy. Việc truy cập bộ nhớ trong cơ chế phân trang đòi hỏi hai lần truy cập: một lần để lấy thông tin từ bảng trang và một lần để truy cập dữ liệu thực sự.

3.3. Tăng tốc độ truy cập với bộ đệm TLB Cache

Việc phải truy cập bộ nhớ chính hai lần cho mỗi tham chiếu làm chậm đáng kể hệ thống. Để giải quyết vấn đề này, các hệ thống hiện đại sử dụng một bộ nhớ đệm phần cứng đặc biệt, tốc độ cao gọi là TLB (Translation Lookaside Buffer). TLB hoạt động như một bộ nhớ cache cho bảng trang, lưu trữ các cặp (số hiệu trang, số hiệu khung trang) được truy cập gần đây. Khi CPU tạo ra một địa chỉ logic, số hiệu trang sẽ được tìm kiếm song song trong TLB. Nếu tìm thấy (TLB hit), số hiệu khung trang được lấy ra ngay lập tức và địa chỉ vật lý được hình thành. Nếu không tìm thấy (TLB miss), hệ thống phải truy cập bảng trang trong bộ nhớ chính, và sau đó cập nhật mục mới vào TLB. Tỉ lệ TLB hit cao giúp giảm đáng kể thời gian truy cập bộ nhớ.

IV. Cách quản lý bộ nhớ ảo và kỹ thuật phân đoạn hiệu quả

Bên cạnh phân trang, phân đoạn (Segmentation) và bộ nhớ ảo (Virtual Memory) là hai khái niệm nâng cao giúp hệ điều hành quản lý bộ nhớ một cách linh hoạt và mạnh mẽ hơn. Phân đoạn cung cấp một góc nhìn logic hơn về bộ nhớ cho người lập trình, trong khi bộ nhớ ảo phá vỡ giới hạn của bộ nhớ vật lý, cho phép chạy các chương trình lớn hơn nhiều so với dung lượng RAM thực có. Bộ nhớ ảo là một kỹ thuật cho phép tách biệt bộ nhớ logic của người dùng khỏi bộ nhớ vật lý. Điều này không chỉ cho phép không gian địa chỉ logic có thể lớn hơn rất nhiều so với không gian địa chỉ vật lý mà còn giúp chia sẻ tệp và thư viện hiệu quả hơn, cũng như hỗ trợ tạo tiến trình hiệu quả. Các kỹ thuật này thường được kết hợp với phân trang để tạo ra các hệ thống quản lý bộ nhớ phức tạp và tinh vi.

4.1. Kỹ thuật phân đoạn Segmentation và ưu nhược điểm

Kỹ thuật phân đoạn (Segmentation) chia bộ nhớ theo góc nhìn của người dùng. Một chương trình được xem là một tập hợp các đoạn logic (segment) như: đoạn mã chính, thủ tục, hàm, biến toàn cục, stack... Mỗi đoạn có kích thước thay đổi. Địa chỉ logic bao gồm hai phần: số hiệu đoạn và độ dời trong đoạn. Hệ thống sử dụng một bảng đoạn (Segment Table) để ánh xạ. Ưu điểm của phân đoạn là hỗ trợ chia sẻ và bảo vệ bộ nhớ theo cấu trúc logic của chương trình. Tuy nhiên, nhược điểm lớn của nó là kích thước đoạn thay đổi gây ra phân mảnh ngoại, một vấn đề mà phân trang đã giải quyết. Nhiều hệ thống hiện đại kết hợp cả phân trang và phân đoạn để tận dụng ưu điểm của cả hai.

4.2. Khái niệm bộ nhớ ảo Virtual Memory và các lợi ích

Bộ nhớ ảo là một kỹ thuật cho phép thực thi một tiến trình mà không cần nạp toàn bộ nó vào bộ nhớ vật lý. Chỉ những phần cần thiết của chương trình mới được đưa vào bộ nhớ. Lợi ích chính là chương trình không còn bị giới hạn bởi dung lượng RAM. Nó cũng cho phép nhiều tiến trình chạy đồng thời hơn, tăng hiệu suất CPU. Hơn nữa, bộ nhớ ảo đơn giản hóa việc lập trình, vì lập trình viên không cần lo lắng về việc quản lý không gian bộ nhớ hạn chế. Cơ chế này thường được hiện thực hóa bằng phân trang theo yêu cầu (Demand Paging), kết hợp với kỹ thuật hoán đổi (Swapping) để đưa các trang ra/vào giữa bộ nhớ chính và bộ nhớ phụ (đĩa cứng).

4.3. Xử lý lỗi trang Page Fault và phân trang theo yêu cầu

Demand Paging (Phân trang theo yêu cầu) là một kỹ thuật cốt lõi của bộ nhớ ảo. Theo đó, một trang chỉ được nạp vào bộ nhớ khi nó thực sự được tham chiếu đến. Khi một tiến trình cố gắng truy cập một trang chưa có trong bộ nhớ (được đánh dấu là không hợp lệ trong bảng trang), một ngắt đặc biệt gọi là Page Fault sẽ xảy ra. Hệ điều hành sẽ xử lý ngắt này bằng cách: tìm trang yêu cầu trên đĩa, tìm một khung trang trống trong bộ nhớ (hoặc giải phóng một khung trang đang dùng), nạp trang từ đĩa vào khung trang đó, và cập nhật lại bảng trang. Sau đó, lệnh gây ra lỗi sẽ được thực thi lại. Quá trình này diễn ra một cách trong suốt đối với tiến trình.

V. Top các thuật toán thay thế trang trong quản lý bộ nhớ

Khi sử dụng bộ nhớ ảo và phân trang theo yêu cầu, một tình huống tất yếu sẽ xảy ra: bộ nhớ chính bị đầy nhưng hệ thống lại cần nạp một trang mới từ đĩa vào. Lúc này, hệ điều hành phải quyết định "hy sinh" một trang nào đó hiện có trong bộ nhớ để giải phóng khung trang. Việc lựa chọn trang nào để thay thế có ảnh hưởng lớn đến hiệu suất hệ thống. Một thuật toán tốt sẽ chọn trang ít có khả năng được sử dụng trong tương lai gần nhất, nhằm giảm thiểu số lần xảy ra Page Fault. Có nhiều thuật toán thay thế trang đã được đề xuất, mỗi thuật toán có sự cân bằng khác nhau giữa độ phức tạp và hiệu quả. Việc lựa chọn thuật toán phù hợp phụ thuộc vào yêu cầu cụ thể của hệ điều hành.

5.1. Thuật toán FIFO Đơn giản nhưng có thể kém hiệu quả

Thuật toán FIFO (First-In, First-Out) là thuật toán đơn giản nhất. Nó hoạt động giống như một hàng đợi: trang nào được nạp vào bộ nhớ sớm nhất sẽ là trang đầu tiên bị thay thế. Để cài đặt, hệ điều hành chỉ cần duy trì một danh sách các trang theo thứ tự thời gian chúng được nạp vào. Mặc dù dễ cài đặt, FIFO có thể hoạt động không tốt. Nó có thể loại bỏ một trang quan trọng đã được nạp vào từ lâu và vẫn đang được sử dụng thường xuyên. Trong một số trường hợp, việc tăng số khung trang có sẵn cho một tiến trình thậm chí có thể làm tăng số lỗi trang, một hiện tượng dị thường gọi là "Anomalous Belady".

5.2. Thuật toán LRU Tối ưu dựa trên tần suất sử dụng

Thuật toán LRU (Least Recently Used) hoạt động dựa trên nguyên tắc: trang nào không được sử dụng trong một khoảng thời gian dài nhất thì ít có khả năng được sử dụng trong tương lai gần. Do đó, LRU sẽ chọn trang ít được sử dụng gần đây nhất để thay thế. Về mặt lý thuyết, LRU cho hiệu suất rất tốt và không bị Anomalous Belady. Tuy nhiên, việc cài đặt LRU một cách chính xác đòi hỏi sự hỗ trợ phần cứng đáng kể để theo dõi thời điểm cuối cùng mỗi trang được truy cập. Các phương pháp cài đặt phổ biến bao gồm sử dụng bộ đếm thời gian cho mỗi mục trong bảng trang hoặc sử dụng một ngăn xếp để duy trì thứ tự truy cập. Do sự phức tạp này, nhiều hệ thống sử dụng các thuật toán xấp xỉ LRU.