Chapter 7: Memory management (continue)

Fragmentation

Cả 2 giải pháp first-fit và best-fit dùng trong cấp phát bộ nhớ đều bị ảnh hưởng bởi phân mảnh ngoại – external fragmentation. Khi một process được load vào memory, sau đó lại được remove ra, phần bộ nhớ trống sẽ bị chia thành nhiều mảnh nhỏ. Phân mảnh ngoại tồn tại khi tổng dung lượng bộ nhớ trống đủ để đáp ứng một yêu cầu, nhưng các vùng nhớ trống này lại không liên tục, nằm rải rác; bộ nhớ lúc này sẽ bị phân ra thành một lượng lớn nhiều vùng nhớ nhỏ (small hole). Tác hại của việc phân mảnh này có thể trở nên rất nghiêm trọng. Trong trường hợp xấu nhất, một vùng nhớ trống (có thể không sử dụng được) sẽ tồn tại giữa mỗi 2 process. Đây chính là sự lãng phí vì các vùng nhớ nhỏ có thể không đủ để cấp phát cho bất kì request nào, nếu thay các vùng nhớ nhỏ này bằng một vùng nhớ lớn thì một vài process sẽ có thể hoạt động trên đó.

Dù hệ thống sử dụng giải pháp cấp phát bộ nhớ first-fit hay best-fit thì cả hai cách này đều gây ra tình trạng phân mảnh. (First fit có thể tốt hơn trong một số hệ thống, và best fit lại tốt hơn trong một vài hệ thống khác). Một nguyên nhân khác nữa liên quan đến vùng nhớ trống cuối cùng nào được cấp phát (vùng nhớ nào là vùng nhớ còn lại - ở top hay ở bottom?) Nói chung, dù sử dụng giải thuật nào thì quá trình phân mảnh ngoại vẫn luôn xảy ra.

Bên cạnh phân mảnh ngoại, bộ nhớ còn có thể bị phân mảnh nội (internal fragmentation). Ví dụ chúng ta sử dụng cơ chế cấp phát multiple-partition trong đó có một vùng nhớ (hole) có kích thước 18,464 bytes. Giả sử process tiếp theo yêu cầu dung lượng bộ nhớ là 18,462. Nếu chúng ta cấp phát đúng chính xác dung lượng bộ nhớ mà process yêu cầu, vùng nhớ trống còn lại sẽ chỉ là 2 bytes. Và lúc này, chi phí cần thiết để lưu trữ thông tin về vùng nhớ này sẽ trở nên rất lớn so với dung lượng của chính vùng nhớ đó. Cách thông thường để tránh gặp phải vấn đề này là chia bộ nhớ chính ra thành từng vùng nhớ với kích thước cố định và tùy theo yêu cầu mà sẽ cấp phát vùng nhớ có kích thước phù hợp. Với giải pháp này, thông thường bộ nhớ cấp phát cho process sẽ lớn hơn so với dung lượng mà process đó yêu cầu. Sự sai khác giữa dung lượng vùng nhớ cấp cho process và dung lượng bộ nhớ mà process yêu cầu chính là phân mảnh ngoại (internal fragmentation) – bộ nhớ nằm bên trong của partition nhưng lại không thể sử dụng được.

Một giải pháp để khắc phục phân mảnh ngoại đó là compaction. Mục đích của giải pháp này đó là di chuyển các vùng nhớ trống nằm rải rác lại để kết hợp thành một vùng nhớ trống lớn hơn. Tuy nhiên, không phải lúc nào compaction cũng có thể giải quyết được vấn đề. Nếu quá trình định vị lại địa chỉ bộ nhớ là static và được hoàn thành tại assembly hoặc load time, compaction không thể thực hiện được. Compaction chỉ có thể hoạt động nếu quá trình tái đinh vị được thực hiện dynamic và nó được hoàn tại tại thời điểm thực thi. Nếu địa chỉ được cấp phát động, quá trình cấp phát lại chỉ cần di chuyển chương trình và chữ liệu, sau đó thay đổi giá trị của thanh ghi base phù hợp với địa chỉ bộ nhớ mới. Nếu compaction có thể thực hiện được, chúng ta cần phải xem xét tới chi phí để thực hiện quá trình này. Thuật toán compaction đơn giản nhất đó là di chuyển toàn bộ process về một phía trong bộ nhớ, tất cả các hole sẽ được di chuyển về phía còn lại, nhờ đó sẽ tạo ra một vùng bộ nhớ trống lớn. Cơ chế này thường tốn nhiều chi phí.

Một giải pháp khả thi khác để giải quyết vấn đề phân mảnh nội đó là cho phép địa chỉ luận lý không nhất thiết phải liên tục, nhờ đó cho phép phần bộ nhớ vật lý cấp phát cho process có thể nằm ở bất kì đâu miễn sao vùng nhớ đó còn trống. Hai kĩ thuật dùng để hiện thực giải pháp này đó là paging và segmentation.

Paging – phân trang

Paging là một cơ chế quản lí bộ nhớ cho phép các không gian địa chỉ thực (physical address spaces) cấp phát cho process được nằm rải rác, không liên tục với nhau. Cơ chế này giúp hệ thống tránh được các vấn đề liên quan đến việc đưa các vùng nhớ có kích thước khác nhau vào từng vị trí thích hợp trong backing store; hầu hết các cơ chế quản lí bộ nhớ được sử dụng trước khi cơ chế phân trang ra đời đều gặp khó khăn với vấn đề này. Nguyên nhân của nó là vì, khi một số data hoặc code fragments đang nằm trong bộ nhớ chính nhưng lại cần được swap out, hệ thống phải tìm ra được một không gian nào đó trong backing store để lưu trữ chúng. Và backing store cũng bị phân mảnh tương tự như bộ nhớ chính, chỉ khác một điều là tốc độ truy xuất chậm hơn nhiều, do đó ta không thể sử dụng giải pháp compaction để khắc phục vấn đề phân mảnh trong backing store. Chính vì những lí do trên mà hiện nay cơ chế phân trang (và các dạng khác của cơ chế này) được sử dụng trong hầu hết các hệ điều hành.

Basic Method

Phương pháp cơ bản để sử dụng cơ chế phân trang đòi hỏi phải chia bộ nhớ vật lý ra thành từng khối có kích thước cố định gọi là frames và chia bộ nhớ luận lí thành nhiều khối có cùng kích thước gọi là pages. Khi một process được thực thi, các trang (pages) của nó được load và bất kì khung (frames) bộ nhớ trống nào trong backing store. Backing store được chia thành từng vùng có kích thước cố định và các vùng này có kích thước bằng với kích thước của các frame.

Hình ảnh phía trên chính là sự hỗ trợ của phần cứng trong cơ chế phân trang. Mỗi địa chỉ được sinh ra bởi CPU (logical address) được chia thành hai phần: page number (p) **và **page offset (d). Page number được dùng như chỉ mục (index) trong page table. Page table chứa địa chỉ gốc (base address) ứng với địa chỉ thực trong bộ nhớ chính của mỗi page. Base address này kết hợp với page offset sẽ cho biết chính xác địa chỉ thực (physical memory address) và địa chỉ này sẽ được gởi đến mỗi đơn vị bộ nhớ (memory unit). Hình ảnh bên dưới mô tả một kiểu phân trang trong bộ nhớ:

Kích thước của trang (cũng như kích thước của frame) được xác định bằng phần cứng. Kích thước của một page thông thường là lũy thừa của 2, thay đổi từ 512 bytes cho tới 16 MB mỗi page, tùy thuộc vào kiểu kiến trúc máy tính. Việc chuyển từ địa chỉ luận lý thành page number và page offset thường khá đơn giản. Nếu kích thước của không gian địa chỉ luận lí là 2m và kích thước của trang là 2n (đơn vị địa chỉ - addressing unit, có thể là bytes hoặc word) thì page number bằng m – n, và page offset bằng n. Như vậy, địa chỉ luận lý có dạng như sau:

Ví dụ dưới đây sẽ giúp bạn hiểu rõ hơn. Xét bộ nhớ như hình bên dưới. Sử dụng một page có kích thước 4 bytes và bộ nhớ thực có kích thước 32 bytes (8 pages). Logical address 0 chính là page 0 và offset 0. Thông qua page table, ta thấy page 0 nằm trong frame 5. Như vậy logical address 0 sẽ chính là địa chỉ 20 trong bộ nhớ thực (5 x 4 + 0 = 20). Tương tự, logical address 3 (page 0, offset 3) có địa chỉ thực là 23 (5 x 5 + 3 = 23). Logical address 4 thuộc page 1, offset 0, theo page table, page 1 sẽ trỏ tới frame 6. Do đó, logical address 4 có physical address 24 (6 x 4 + 0 = 24). Cũng như vậy, logical address 13 trỏ tới physical address 9.

Có thể bạn sẽ để ý thấy một điều rằng paging thực ra là một dạng dynamic relocation. Mỗi địa chỉ luận lý được sẽ trỏ vào các địa chỉ thực thông nhờ trung gian là thiết bị phần cứng hỗ trợ phân trang (paging hardware). Sử dụng paging cũng tương tự như sử dụng bảng các thanh ghi base (hoặc thanh ghi relocation), mỗi frame sẽ có một thanh ghi.

Khi chúng ta sử dụng cơ chế phân trang, chúng ta sẽ tránh được tình trạng phân mảnh ngoại: bất kì** **_frame nào còn trống đều có thể được cấp phát cho process nào đang cần. Tuy nhiên, chúng ta sẽ gặp một vài vấn đề liên quan đến phân mảnh nội. Một điều cần lưu ý đó là các frame được cấp phát theo theo kiểu đơn vị. Tức là, nếu một process yêu cầu bộ nhớ có dung lượng _n pages cộng thêm k byte nữa (k không vượt quá kích thước của một page), khi đó nó sẽ được cấp phát n + 1 pages. Giả sử kích thước một page là t, như vậy sẽ có t – k (bytes) không được sử dụng, lãng phí. Một ví dụ cụ thể, cho page size là 2,048 byte, process có kích thước 72,766 bytes nên sẽ yêu cầu 35 pages cộng them 1,086 bytes nữa. Như vậy số frames cấp cho process này là 36, và dung lượng bộ nhớ bị phân mảnh nội là 2,048 – 1,086 = 962 bytes. Trường hợp xấu nhất là khi process cần n page + 1 byte. Số lượng frame cung cấp sẽ là n + 1, như vậy dung lượng phân mảnh nội là rất lớn.

Khi một process vào hệ thống để thực thi, kích thước của nó sẽ được thể hiện bằng số lượng các page. Mỗi page sẽ cần một frame. Như vậy, nếu process yêu cầu n pages, cần tối thiểu n frame còn trống trong memory. Nếu có đủ n frame, tất cả các frame trống này sẽ được cấp phát cho process vừa mới tới. Page đầu tiên của process được load vào một trong các frame đã được cấp phát và frame number sẽ được đặt vào page table của process này. Page tiếp theo sẽ được load vào một frame khác, frame number lại được đưa vào page table, và cứ tiếp tục như vậy cho đến khi kết thúc. (xem hình)

Bởi vì hệ điều hành quản lí các vấn đề về cấp phát bộ nhớ, do đó nó cần phải lưu ý đến các thông tin cấp phát của bộ nhớ chính – bao gồm các frames nào đã được cấp phát, frames nào còn trống, có tổng cộng bao nhiêu frames… Các thông tin này thường được lưu trữ trong một cấu trúc dữ liệu gọi là frame table. Frame table có một entry cho mỗi frame, entry này cho biết frame tiếp theo đang trống hay đã được cấp phát, nếu đã được cấp phát thì nó được cấp phát cho page của process nào.