Chapter 7: Memory Management (continue)

Swapping

Một process muốn thực thi trước hết cần phải nằm trong bộ nhớ chính. Tuy nhiên, một process có thể được swap ra khỏi bộ nhớ và lưu trữ trong backing store, sau đó nó có thể được mang trở lại vào bộ nhớ chính để tiếp tục thực thi. Ví dụ: một hệ thống multiprogramming sử dụng giải thuật định thời round-robin, khi hết một quantum, bộ phận quản lí bộ nhớ sẽ swap tiến trình vừa mới kết thúc ở quantum đó ra ngoài, sau đó swap một process khác vào memory để bắt đầu quantum tiếp theo. Một ví dụ khác sử dụng cơ chế swapping đó là trong các hệ thống sử dụng giải thuật định thời ưu tiên (priority-based scheduling). Nếu một process có độ ưu tiên cao hơn xuất hiện và nó muốn sử dụng một dịch vụ nào đó, memory manager có thể swap out process có độ ưu tiên tấp hơn, sau đó load và thực thi process có độ ưu tiên cao hơn đó. Khi process này thực thi xong, lower-priority process có thể được swap trở lại vào bộ nhớ và tiếp tục thực thi. Việc swap này còn được gọi là roll out, roll in.

---

Thông thường, một process khi bị swap out sẽ được swap trở lại vào đúng vùng nhớ mà nó sử dụng trước đó. Việc này tùy thuộc vào phương pháp kết nối địa chỉ bộ nhớ. Nếu quá trình binding hoàn thành ở assembly hoặc load time thì process không thể dễ dàng move tới một vị trí khác được. Còn nếu binding được thực hiện tại execution-time, process có thể được swap trở lại vào một vùng nhớ khác bởi vì địa chỉ vật lý được tính toán trong quá trình thực thi.

Hiện nay, cơ chế swapping này chỉ còn được sử dụng trong một số ít hệ thống. Lí do là vì nó yêu cầu quá nhiều thời gian để swap và cung cấp quá ít thời gian thực thi, những lí do đó làm cho cơ chế này không thể trở thành một giải pháp quản lí bộ nhớ hợp lý. Tuy nhiên, các phiên bản cải tiến của cơ chế swapping lại được khá nhiều hệ thống sử dụng.

Memory Allocation

Một trong các phương pháp cấp phát bộ nhớ đơn giản nhất đó là chia bộ nhớ thành một vài phân vùng với kích thước nhất định – những phần này gọi là partition. Mỗi partition có thể chứa duy nhất một process. Do đó, mức độ đa nhiệm của hệ thống sẽ phụ thuộc vào số lượng các partition. Trong giải pháp multiple-partition này, khi một partition được giải phóng, một process sẽ được chọn từ input queue và được nạp vào partition trống đó. Khi một process kết thúc, partition chứa process đó sẽ có thể chứa bất kì process nào khác. Phương pháp này ban đầu được sử dụng trong hệ điều hành IBM OS/360 (gọi là MFT); tới bây giờ thì nó đã không còn được sử dụng nữa. Phương pháp được giới thiệu tiếp theo là tổng quát của cơ chế fixed-partition (gọi là MVT), nó được sử dụng chủ yếu trong các hệ thống batch.

Trong cơ chế fixed-partition, hệ điều hành sử dụng một bảng chỉ ra phần nào của bộ nhớ đang còn trống và phần nào đang được sử dụng. Ban đầu, tất cả bộ nhớ có thể được sử dụng bởi user processes được xem như mà một vùng bộ nhớ trống lớn, gọi là **hole. **Khi một process đi vào hệ thống và yêu cầu cấp phát bộ nhớ, hệ thống sẽ tìm xem có cái “lỗ” nào đủ rộng để chứa process này không. Nếu có, hệ thống chỉ cấp phát dung lượng bộ nhớ vừa đủ dùng, phần bộ nhớ còn dư sẽ được dùng để đáp ứng các yêu cầu sau này.

Mỗi khi có process được đưa vào hệ thống, nó sẽ được chuyển vào input queue. Hệ điều hành sẽ tiến hành tính toán dung lượng bộ nhớ mà mỗi process yêu cầu, so sánh với dung lượng bộ nhớ còn trống, sau đó sẽ xác định process nào sẽ được cấp phát bộ nhớ. Khi một process được cấp phát, nó sẽ được nạp vào bộ nhớ chính và lúc này nó sẽ tham gia tranh chấp để được sử dụng CPU. Khi process terminate, nó trả lại tất cả bộ nhớ trước đó, hệ điều hành sẽ sử dụng phần bộ nhớ trả lại này và cấp phát cho các process khác còn nằm trong input queue.

Tại bất cứ thời điểm nào, chúng ta đều có thể biết được danh sách kích thước của từng khối bộ nhớ trống cũng như input queue. Hệ điều hành có thể sắp xếp input queue tùy theo thuật toán định thời mà nó sử dụng. Memory được cấp phát cho các process cho tới khi nó không còn đủ dung lượng để cấp phát cho process tiếp theo – tức là không có khối bộ nhớ (hole) trống nào đủ lớn để chứa process đó. Lúc này, hệ điều hành có thể chờ cho đến khi có đủ bộ nhớ để cấp phát, hoặc nó sẽ bỏ qua process đó và xem xét process tiếp theo trong input queue và cứ tiếp tục như vậy để tìm xem liệu có process nào yêu cầu dung lượng bộ nhớ nhỏ vừa đủ với dung lượng bộ nhớ trống hiện tại hay không và tiến hành cấp phát bộ nhớ.

Thông thường, tại mọi thời điểm, hệ thống đều có một tập hợp các hole với kích thước khác nhau nằm rải rác trong bộ nhớ. Khi một process đến và yêu cầu bộ nhớ, hệ thống sẽ tìm một hole nào đủ lớn trong tập hợp và cấp phát cho process. Nếu kích thước của hole tìm thấy quá lớn, nó sẽ bị chia làm 2 phần. Phần thứ nhất được cấp phát cho process yêu cầu, phần còn lại sẽ trở thành một phần tử trong tập hợp các vùng nhớ trống. Khi một process terminate, nó trả lại phần bộ nhớ sử dụng và tất nhiên phần bộ nhớ này cũng sẽ trở về tập hợp của nó. Nếu hole mới này kế cận một hoặc nhiều hole khác, các hole này sẽ được gộp lại để tạo thành một hole mới lớn hơn. Lúc này, hệ thống có thể phải kiểm tra xem liệu có process nào đang đợi để được cấp phát bộ nhớ hay không.

Thủ tục này chính là một điển hình của các vấn đề phổ biến liên quan đến cấp phát bộ nhớ động (general dynamic storage allocation problem), hay rõ ràng hơn đó là làm sao để đáp ứng một yêu cầu với kích thước n từ trong danh sách các free holes. Có nhiều giải pháp cho vấn đề này, trong đó first-fit, best-fit **và worst-fit **là các giải pháp phổ biến nhất để chọn ra một hole trong tập hợp các hole.

• First fit. Cấp phát vùng bộ nhớ đầu tiên (first hole) có kích thước đủ lớn. Quá trình tìm kiếm có thể bắt đầu từ phần tử đầu tiên trong tập hợp, hoặc bắt đầu tiếp từ vị trí đã tìm thấy cho yêu cầu trước đó. Quá trình tìm kiếm sẽ kết thúc khi tìm ra được vùng nhớ đạt yêu cầu.

• Best fit. Cấp phát vùng nhớ nhỏ nhất (smallest hole) nhưng vẫn đủ lớn để đáp ứng được yêu cầu. Giải pháp này yêu cầu phải tìm kiếm trong toàn bộ danh sách, trừ khi danh sách này đã được sắp xếp. Giải pháp này sẽ sinh ra vùng nhớ thừa nhỏ nhất.

• Worst fit. Cấp phát vùng nhớ lớn nhất (largest hole) trong danh sách. Một lần nữa, chúng ta phải tìm kiếm trong cả danh sách để tìm được vùng nhớ này, trừ khi danh sách đã được sắp xếp. Giải pháp này sẽ sinh ra vùng nhớ dư thừa lớn nhất, và vùng nhớ dôi ra này sẽ có ích hơn so với vùng nhớ được sinh ra nếu sử dụng giải pháp best-fit.

Chúng ta có thể thấy các giải pháp first fit và best fit sẽ tốt hơn worst fit trong vấn đề giảm thiểu thời gian và tận dụng đĩa cứng. Không thể khẳng định chắc chắn giải pháp nào tốt hơn trong việc tận dụng bộ nhớ giữa first fit và best fit, nhưng first fit thông thường nhanh hơn so với best fit.

Xem thêm: Memory management