QUẢN LÝ BỘ NHỚ
II. CẤP PHÁT LIÊN TỤC
1) Các hệ đơn chương, đa chương:
a) Các hệ đơn chương:
Tại một thời điểm chỉ có một chương trình người dùng được nạp vào bọâ nhớ để thực thi. Bộ nhớ được chia sẻ cho hệ điều hành và một process duy nhất của người sử dụng. Process này toàn quyền sử dụng vùng nhớ dành cho nó.
Khi bộ nhớ được tổ chức theo kiểu này thì chỉ có thể xử lý một chương trình tại một thời điểm. Đồng thời cần phải bảo vệ vùng nhớ dành cho hệ điều hành khỏi sự xâm hại của chương trình người dùng.
Để bảo vệ như thế, người ta dùng một thanh ghi giới hạn ghi nhớ lại địa chỉ cao nhất của phần vùng nhớ dành cho hệ điều hành. Tất cả các địa chỉ mà process của người dùng truy xuất đến sẽ so sánh với địa chỉ chứa trong thanh ghi giới hạn xem có hợp lệ hay không.
b) Các hệ đa chương:
Quan sát hoạt động của các process có thể nhận thấy nhiều process trải qua phần lớn thời gian để chờ sự hoàn thành của thao tác nhập xuất. Trong suốt thời gian này, CPU nhàn rỗi. Trong các tình huống như thế hệ thống đơn chương không cho phép sử dụng CPU có hiệu quả.
Để nâng cao hiệu suất sử dụng CPU, cần cho phép chế độ đa chương. Tại cùng một thời điểm, cho phép nhiều chương trình được nạp vào bộ nhớ. Mỗi chương trình chiếm một phần riêng nào đó trong bộ nhớ. Khi đó, các process chia sẻ CPU với nhau để hoạt động đồng hành. Cần phải có các chiến lược cấp phát và quản lý bộ nhớ cho các process theo chế độ đa chương này để chúng không xâm phạm lẫn nhau.
Hệ điều hành Process cuûa
người dùng
0
2) Hệ thống đa chương với phân vùng cố định: (fixed partition) a) Ý tưởng:
Bộ nhớ thực được chia thành các vùng (partition) cố định. Các vùng có thể có kích thước bằng nhau hay không bằng nhau. Mỗi process khi được thực thi sẽ được nạp vào một trong các partition đó.
b) Cách quản lý:
Các process khi có nhu cầu thực thi sẽ được đưa vào trong hàng đợi.Có 2 cách tổ chức hàng đợi:
- Mỗi partition có riêng một hàng đợi: Một process mới vừa được tạo lập sẽ được đưa vào hàng đợi của phân vùng có kích thước nhỏ nhất đủ thõa mãn chứa được process đó. Cách tổ chức này bộc lộ khuyết điểm là: hàng đợi của một số phân vùng thì trống trong khi hàng đợi của một số phân vùng khác thì đầy. Buộc các process trong hàng đợi ở vùng bị đầy phải chờ.
- Dùng một hàng đợi chung cho tất cảc các partition: tất cảc các process được đặt trong một hàng đợi duy nhất. Khi có một partition tự do, process đầu tiên trong hàng đợi có kích thước phù hợp sẽ được đặt vào partition này và cho thực thi.
c) Nhận xét:
- Nếu process có kích thước lớn thì một partition không đủ, phải dùng kỹ thuật overlay.
- Nếu process có kích thước nhỏ thì vẫn dùng 1 partition. Nếu kích thước của process nhỏ hơn kích thước partition chứa nó thì phần bộ nhớ bị dư trong partition bị lãng phí. Hiện tượng này được gọi là phân mãnh nội (internal fragmentation).
- Do chia partition cố định nên số process tối đa chứa trong bộ nhớ thực bị giới hạn.
3) Hệ thống đa chương với phân vùng động: (dynamic partition) a) Ý tưởng:
Khi một process được đưa vào hệ thống, hệ thống cấp phát cho process một vùng nhớ vừa đúng với kích thước của nó. Phần bộ nhớ còn lại dành cho các process khác. Khi một process kết thúc, vùng nhớ cấp phát cho nó sẽ được giải phóng và có thể cấp phát cho một process khác. Như vậy vùng nhớ cấp phát cho process là động. Vị trí bắt đầu và kết thúc của partition cấp cho process cũng động.
b) Nhận xét:
Không có hiện tượng phân mãnh nội nhưng xuất hiện hiện tượng phân mãnh ngoại (external fragmentation) như sau:Khi các process lần lượt vào và ra khỏi bộ nhớ, dần dần xuất hiện các khe hở giữa các process trong bộ nhớ. Đây là các khe hở (hole) được tạo ra do kích thước của process mới nạp vào nhỏ hơn kích thước vùng nhớ vừa mới được giải phóng.
c) Cách giải quyết:
Để dọn các khoảng trống người ta dùng phương pháp collecting-holes hoặc garbage-collection. Collecting holes: gom các hole lại thành một hole lớn hơn. Garbage-collection: gom các process về đầu bộ nhớ chính.
Trong quá trình gom thì phải ngưng các công việc khác. Vì vậy chi phí cho các chương trình dọn chỗ trống là đáng kể và hệ thống phải có khả năng định vị lại địa chỉ khi gom (di chuyển) các process.
d) Các giải thuật nạp process mới:
Đây là các giải thuật chọn một vùng trống trên bộ nhớ để nạp process vào. Có 3 giải thuật:
Best fit: Cấp phát vùng tự do nhỏ nhất nhưng đủ lớn để thõa mãn nhu cầu.
First fit: Dò từ đầu bộ nhớ chọn ra vùng tự do đầu tiên có kích thước lơn hôn yeâu caàu.
Next fit: Yêu cầu phải nhớ lại vị trí kết thúc của lần dò trước để lần sau sẽ bắt đầu từ vị trí đó. Giải thuật này dò từ vị trí của lần trước, chọn ra vùng đầu tiên có kích thước lơn hơn yêu cầu.
Ví dụ: Cho trạng thái của bộ nhớ như trong hình vẽ. Trong đó:
Có yêu cầu cần cấp phát cho 1 process có kích thứơc 16K.
Kết quả:
− Best fit chọn vùng có kích thước 18K.
− First fit chọn ra vùng có kích thước 22K.
− Next Fix chọn vùng có kích thứơc 36 K.
Nhận xét:
Best fit không phải là giải thuật tốt nhất. Vì gây chi phí cao cho việc chọn vùng trống do tốn thời gian dò tìm nhiều hơn. Sau khi được nạp vào, thực thi xong và thoát ra thì các hole sinh ra là rất nhỏ. Do các hole quá nhỏ không dùng được vào việc gì nên làm tăng khả năng phải dọn chỗ.
First fix là giải thuật đơn giản nhất và được dùng nhiều trong thực tế.
Next fix nhìn chung là tương đương với First fix. Nhưng nếu ở lần thứ i+1 mà yêu vùng nhớ cho một process lớn hơn vùng nhớ cho lần thứ i thì Next fix toát hôn First fix.