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ớ

Giáo trình nghiên cứu nguyên lý các hệ điều hành phần 2, trình bày lý thuyết rõ ràng, minh họa ví dụ thực tế, phù hợp sinh viên ., phục vụ nghiên cứu và ứng dụng thực tiễn

• 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.

Trích đoạn nội dung tài liệu

chương I) và cần cơ chế để bảo vệ các chương trình hệ thống với chương trình người dùng. Đến chế độ đa chương trình thực sự thì vấn đề bảo vệ bộ nhớ không chỉ xảy ra giữa chương trình người dùng với chương trình hệ thống mà còn giữa các chương trình người dùng lẫn nhau. Như đã biết, việc phân chương bộ nhớ góp phần đảm bảo cho việc bảo vệ bộ nhớ. Ngoài ra, thường có một cơ chế kỹ thuật sử dụng các thanh ghi: thanh ghi cơ sở và thanh ghi bảo vệ; và hơn thế nữa, có thể kể đến việc đưa ra những thuộc tính của bộ nhớ và thuộc tính của chương trình về quyền thâm nhập đến bộ nhớ.

Một bài toán cơ bản là số lượng và kích cỡ của các chương bộ nhớ được phân. Người ta phân ra 2 lớp các bài toán mà các chương trình xử lý: tính toán nhiều và vào/ra nhiều. Theo một số thống kê, để bộ xử lý đạt hiệu quả 90%, thường đồng thời có 4 hoặc 5 chương trình trong bộ nhớ. Tồn tại chiến lược giới hạn tĩnh (cận cố định) và chiến lược giới hạn động (cận thay đổi).

Chiến lược giới hạn tĩnh (cận cố định) Một trong những phương pháp điển hình phân phối bộ nhớ liên tục là chiến lược giới hạn tĩnh còn gọi là chiến lược phân chương (tương ứng với chế độ MET của hệ điều hành). Bộ nhớ được chia thành các chương: gán tên chương, địa chỉ, dung lượng trong quá trình khởi tạo hệ điều hành.4 cho một hình ảnh phân chương bộ nhớ và việc phân phối bộ nhớ cho một số chương trình. 184K P4 112K P3 72K P2 32K 0K PO Dia chi Chương bộ nhớ Hình 3. Bộ nhớ được phân chương.

NGUYÊN LÝ CÁC HỆ ĐIỀU HÀNH 7 Đối với ví dụ theo hình vẽ 3.4, bộ nhớ được phân ra thành 5 chương: PO (32K), PI (40K), P2 (40K), P3 (72K), P4 (72K). Chương P0 được dành cho nhân, mỗi chương còn lại đã có một chương trình được tải (load). Kích cỡ (dung lượng) trung bình của mỗi chương phụ thuộc vào dung lượng của bộ nhớ và số lượng chương. Các chương trình được gán số hiệu để chỉ có thể tải vào những chương nhất định.

Nảy sinh trường hợp có thể có những chương rỗi mà không tải được chương trình: lớp gắn với nó bị bận hoặc độ rộng của chương không đủ để tải. Lúc đó hoặc hệ thống hoặc thao tác viên thực hiện việc thay đổi lớp gắn cho chương trình hoặc thay đổi số lượng chương, kích cỡ chương song phổ biến là thao tác viên dùng lệnh để thực hiện công việc đó. Tuy điều đó xem ra có vẻ thủ công song tránh được sự phức tạp cho chương trình điều khiển. Để quản lý bộ nhớ trong trường hợp này, sử dụng bảng mô tả chương (partition đescription table : PDT), có dạng: Số hiệu chương Địa chỉ Độ dài Tình trạng 0 0K 32K đã load 1 32K 40K đã load 2 72K 40K đã load 112K 72K đã load 3 184K 72K đã load 4 nhớ, chiến lược Đối với một bài toán, nó được gắn với một vài chương bộ phối nhanh nhất phân phối bộ nhớ cho nó có thể được kể làm hai hướng: phân tối ưu (chọn chương với (gặp chương được gắn, đủ độ rộng đầu tiên), phân phối nhớ: vùng nhớ dừ thừa là ít nhất).

Trở lại vấn đẻ vướng mắc khi phân phối bộ trình; - Không có chương nào đủ để phân phối cho chương - Mọi chương đã được tải; 78 CHƯƠNG 3. ĐIỀU KHIỂN BỘ NHỚ - Một số chương rỗi, mỗi chương rỗi không đủ chứa bài toán song nối vài chương rỗi tạo ra một vùng bộ nhớ đủ đẻ tải bài toán. Việc phân phối bộ nhớ cho bài toán (quá trình) được coi như gắn với mỗi chương có 1 dòng xếp hàng các bài toán cần được phân phối bộ nhớ đối với nó. Mỗi bài toán lại có thé gan với một vài chương, có sự chung nhau giữa một số dòng xếp hàng.

Việc phân phối bộ nhớ cho một bài toán liên quan tới việc thao tác đối với các đòng xếp hàng nói trên. Mối liên kết giữa chương và lớp bài toán không phải là luôn chặt chẽ. Như trên đã thấy, tồn tại một số cách thức thay đổi mối liên kết nói trên (hoặc do chương trình hệ thống hoặc do thao tác viên v. Chiến lược giới hạn động (cận thay đổi) Như trên đã thấy, chế độ phân phối cận cố định (phân phối tĩnh) nảy sinh một số vấn đề trong việc sử dụng tối ưu bộ nhớ, với phương án khắc phục đưa vào lệnh của thao tác viên.

Trong cách thức phân phối liên tục bộ nhớ, chế độ giới hạn thay đổi được áp dụng. Trong chế độ này (tương ứng với chế độ MVT của hệ điều hành), bộ nhớ không chia thành các chương giống như ở chế độ giới hạn cố định. Các chương trình nạp liên tục vào bộ nhớ cho đến khi còn nạp được. Một ví dụ về hình ảnh của bộ nhớ trong được cho trong hình 3.

Trong quá trình làm việc, các chương trình được thực hiện và giải phóng, các vùng bộ nhớ giải phóng đó có thể liên tục hoặc rời rạc. Sử dụng vùng bộ nhớ đó ra làm sao. Một số tình huống nảy sinh (hình 3. Trên hình vẽ thứ 6, chương trình 4 (Prg.

4) được giải phóng đầu tiên. Ngay trước chương trình 4, một vùng nhớ rỗi với dung lượng 20K. Khi giải phóng chương trình 4, có một vùng rỗi liên tục với dung lượng 102K. Chương trình 8 với độ dài 52K được tải vào trong bộ nhớ trong và sau đó chương trình 6 được giải phóng.

Hiện tại, trên dòng đợi, đến lượt chương trình Pr9 có độ dài 80K. Mỗi vùng rỗi riêng rẽ trong bộ nhớ không thể chứa nối chương trình 9, trong khi đó dung tích rỗi tổng cộng là 88K. Hệ thống cân nhập hai vùng nhớ rỗi trên để nạp được chương trình Pr9. NGUYÊN LÝ CÁC HỆ ĐIỀU HÀNH 79 24K 82K 42K 30K 50K 92K 62K 26K 32K 24K 82K 82K 30K fg 20K 62K 60K 26K lễ 38K 32K Hình 3.

Các hình trạng bộ nhớ với cận thay đổi. Điều khiển bộ nhớ theo cận thay đổi sử dụng linh hoạt tối ưu bộ nhớ, tránh được một số hạn chế so với cận cố định (cho phép độ dài của môdun chương trình lớn) và miền nhớ rỗi được sử dụng linh hoạt. Tuy vậy, công việc phân phối bộ nhớ là phức tạp: - quản lý bộ nhớ luôn thay đổi; - định vị lại bộ nhớ cho các chương trình. Khi chương trình đang hoạt động, nó đang ở trạng thái trung gian, nếu không có những cơ chế thích hợp thì việc định vị lại sẽ ảnh hưởng đến sự thực hiện của chương trình.

Điều này cũng liên quan đến vấn để địa chỉ hóa trong chương trình: sử dụng địa chỉ cơ sở không tường minh. Chỉ khi có thể quy chiếu trên địa chỉ không tường minh mới có thể giải quyết được bài toán định vị lại như trên. Chương Mặt khác, không phải thời điểm nào cũng cho phép định vị lại. trở ngại lớn trình đang đợi kết quả của công việc vào/ra thì việc định vị lại gặp trong vấn đề liên kết kết quả công việc vào/ra với chương trình.

ĐIỀU KHIỂN BỘ NHỚ Van dé định vị lại có ý nghĩa không chỉ trong phân phối bộ nhớ liên tục mà cả trong phân phối bộ nhớ gián đoạn. Việc sử dụng địa chỉ tương đối là một hình tức phù hợp với việc định vị lại. Có một số cách thức liên quan đến định vị lại: định vị tĩnh và định vị động. Quản lý bộ nhớ rỗi Trong bộ nhớ trong, phân chia ra các vùng nhớ đã được phân phối cho các chương trình đang hoạt động và một số vùng nhớ khác lại chưa được sử dụng.

Vùng bộ nhớ rỗi nói trên, khi cần tải một chương trình mới sẽ cần tới nó, và lúc đó nó đã được phân phối (bị bận). Sau khi chương trình hoàn thiện công việc của mình, nó được kết thúc, vùng nhớ dành cho nó được giải phóng. Bài toán quản lý, phân phối bộ nhớ thường xuyên xảy ra, trong đó bài toán quản lý bộ nhớ rỗi là một bài toán quan trọng. Có một số phương pháp để quản lý bộ nhớ rỗi.

Ví dụ như hệ điều hành đơn chương trình, sử dụng cận về vùng bộ nhớ đã phân phối cho thông tin về vùng nhớ rỗi chưa được phân phối. Một trong những phương pháp quản lý bộ nhớ rỗi điển hình là phương pháp kẻ cận. Phương pháp kẻ cận có thể được chia ra: kể cận nhị phân và kể cận tổng quát. Phương pháp kề cận nhị phân 0 ee 1 * 2 3 4 16 5 32 6 64 7 128 Hình 3.

Quản lý bộ nhớ rỗi theo kể cận nhị phân. Phương pháp kể cận nhị phân tương ứng với việc phân chia nhị phân: bộ nhớ được chia làm các khối nhớ có độ dài là 2* đơn vị bộ nhớ (đơn vị phổ biến là trang), mỗi vùng bộ nhớ có độ dài 2* phải được đặt ở địa chỉ chia hết cho 2, NGUYÊN LÝ CÁC HỆ ĐIỀU HÀNH 81 Có một bảng quản lý các vùng bộ nhớ rỗi, phân từ k (k = 0,1,2,. ) trong bảng chứa danh sách móc nối mà các vùng bộ nhớ 2* còn đang rỗi (xem hình trên). Khi một chương trình đòi hỏi một vùng nhớ có độ dài x thì thuật toán xử lý như sau: Tìm số k bé nhất để cung cấp đủ độ dài x đó (2* > x).

Nếu không có báo sai sót. Nếu có, phân phối vào đầu vùng đó : như vậy liên quan đến các thao tác: loại bỏ, bổ sung, hay vừa loại bỏ vừa bổ sung các phân tử trong các danh sách trong bang. Trong các danh sách trên, chú ý có 3 danh sách không rỗng: Danh sách với k=0: có 1 phần tử trỏ vào 6 25; Danh sách với k=l: có 2 phần tử trỏ vào ô 2 và ô 4; Danh sách với k=3: có 1 phần tử trỏ vào ô 16. Phương pháp kê cận tổng quát Kê cận tổng quát: nảy sinh vấn đề nếu độ dài x là 2*+1, phải phân phối một miền bộ nhớ 2**! là khá lãng phí.

Vì vậy, cải tiến các độ dài được chia không theo các vùng nhớ theo độ dài 2* mà theo dãy nào đó, chẳng hạn theo dãy số Fibonaxy :1,1,2,3,5,8,. Chu y rang, day số Fibonaxy va day lũy thừa 2 có cùng công thức chung: L= L4 + Ley trong đój hoặc là ! hoặc 2 (khij = I chúng ta nhận lại dãy luỹ thừa 2 theo kẻ cận nhị phân, còn khi j=2 thì nhận được day Fibonaxy), và tổng quát hóa Lý = Ly; + Lạy, trong đó b(k) là hàm theo k nào đó: b(k)<k. BẬN RỒI 82 CHƯƠNG 3.