Phương Pháp Cấp Trang Khi Có Yêu Cầu Và Mô Hình Tập Làm Việc

Kỹ thuật này đã được sử dụng rộng rãi trong nhiều năm, nhưng nó đòi hỏi nhiều công sức của người lập trình cho việc quản lý overlay. Năm 1961 một nhóm nhà khoa học ở Manchester, nước Anh, đã đề xuất một phương pháp thực hiện quá trình overlay một cách tự động, thậm chí không đòi hỏi người lập trình phải biết điều gì đang xảy ra. Phương pháp này được gọi là bộ nhớ ảo– virtual memory. Phương pháp bắt đầu được sử dụng trong một số máy tính vào những năm 1960, hầu hết liên quan đến các dự án nghiên cứu về thiết kế hệ thống máy tính. Đầu những năm 1970 bộ nhớ ảo đã trở nên thông dụng trong các hầu hết các máy tính. Ngày nay thậm chí cả các bộ vi xử lý, trong đó có 80386 của Intel và 68030 Motorola cũng có các hệ thống bộ nhớ ảo rất tinh vi.

4.6.1. Việc phân trang – Paging

Ý tưởng mà các nhóm nhà khoa học ở Manchester đưa ra làm tách biệt các khái niệm về không gian địa chỉ và các vị trí nhớ. Chúng ta hãy xem xét một thí dụ về một máy tính trong đó các chỉ thị có trường địa chỉ 16 bit và có bộ nhớ 4096 word. Một chương trình chạy trên máy tính này có thể đánh địa chỉ 65536 word bộ nhớ. Số word có thể đánh địa chỉ chỉ phụ thuộc vào số bit trong trường địa chỉ của chỉ thị và không liên quan tới số word mà bộ nhớ thực sự có. Không gian địa chỉ của máy tính này bao gồm các số 0, 1, 2, …, 65535.

Khi còn chưa phát minh ra bộ nhớ ảo, người ta phải phân biệt giữa các địa chỉ nhỏ hơn 4096 và các địa chỉ lớn hơn hoặc bằng 4096. Có thể coi miền thứ nhất là không gian địa chỉ khả dụng và miền thứ hai là không gian địa chỉ không khả dụng. Người ta thường không phân biệt rò ràng giữa không gian địa chỉ và các địa chỉ bộ nhớ thực sự, bởi vì phần cứng bắt buộc phải có sự tương ứng một – một giữa chúng. Chương trình không được phép sử dụng các địa chỉ không khả dụng.

Ý tưởng về việc làm tách biệt không gian địa chỉ và các địa chỉ bộ nhớ thực (bộ nhớ vật lý) như sau: Vào bất cứ thời điểm nào, 4096 word bộ nhớ có thể được truy nhập trực tiếp, nhưng chúng không nhất thiết phải tương ứng với các địa chỉ từ 0…4095. Ví dụ chúng ta có thể “bảo” cho máy tính rằng từ lúc này trở đi, mỗi khi địa chỉ 4096 được truy nhập thì word 0 của bộ nhớ sẽ được sử dụng. Mỗi khi địa chỉ 4097 được truy nhập thì word 1 của bộ nhớ sẽ được sử dụng, mỗi khi địa chỉ 8191 được truy nhập thì word 4095 của bộ nhớ sẽ được sử dụng… Nói cách khác, chúng ta đã định nghĩa một sự ánh xạ từ không gian địa chỉ vào các địa chỉ bộ nhớ thực, như được minh họa trên hình 4.55.

Bằng cách ánh xạ các địa chỉ của không gian địa chỉ vào các vị trí nhớ thực như trên hình 4.55, một máy với 4k bộ nhớ nếu không có bộ nhớ ảo thì chỉ có một sự xạ cố định các địa chỉ từ 0…4095 vào 4096 word bộ nhớ. Có một câu hỏi thú vị là: điều gì sẽ xảy ra nếu chương trình nhảy tới một địa chỉ nằm trong khoảng 8192...12287? Trong máy tính không có bộ nhớ ảo, chương trình này sẽ gây ra một bẫy lỗi, nó sẽ in ra

màn hình một thông báo, chẳng hạn “Nonexistent memory referenced” rồi dừng chương trình. Trong máy tính có bộ nhớ ảo, một dãy các bước sau có thể sẽ lần lượt diễn ra:

1. Nội dung của bộ nhớ chính được cất vào bộ nhớ phụ.

2. Các word 8192..12287 đang nằm trong bộ nhớ phụ được nạp vào bộ nhớ chính.

3. Ánh xạ địa chỉ sẽ được thay đổi để ánh xạ các địa chỉ 8192..12287 vào các vị trí nhớ 0..4095

Có thể bạn quan tâm!

Xem toàn bộ 233 trang tài liệu này.

4. Chương trình tiếp tục như không có điều gì xảy ra.

Hình 4. 55. Ánh xạ các địa chỉ 4096..8191vào các địa chỉ bộ nhớ chính 0..4095

Kỹ thuật thực hiện overlay tự động gọi là phân trang – paging, các đoạn chương trình được đọc vào bộ nhớ chính từ bộ nhớ phụ được gọi là các trang. Người ta cũng đã nghiên cứu các cách tinh vi hơn để ánh xạ các địa chỉ từ không gian địa chỉ vào các địa chỉ bộ nhớ thực.

Để nhấn mạnh chúng ta sẽ gọi miền địa chỉ mà chương trình có thể truy cập là không gian địa chỉ ảo (virtual address space) còn các địa chỉ bộ nhớ thực, bằng các mạch điện, được gọi là không gian địa chỉ vật lý (physical address space). Ánh xạ bộ nhớ liên hệ các địa chỉ ảo với các địa chỉ vật lý.

Trên thực tế người lập trình có thể viết chương trình mà không cần phải biết đến sự tồn tại của bộ nhớ ảo. Đối với họ máy tính dường như có một bộ nhớ chính rất lớn. Việc phân trang làm cho người lập trình có ảo giác về bộ nhớ chính tuyến tính, liên tục và lớn, có kích thước bằng kích thước của không gian địa chỉ; trong khi đó trên bộ nhớ chính có thể nhỏ hơn không gian địa chỉ nhớ. Sự mô phỏng địa chỉ bộ nhớ chính lớn như thế không thể phát hiện ra được bằng chương trình (trừ việc cho chạy

các chương trình kiểm tra thời gian), vì vậy cơ chế phân trang có thể coi là trong suốt đối với người lập trình.

Đặc điểm trên của phương pháp phân trang bộ nhớ rất quan trọng, làm cho nó khác với phương pháp phân đoạn bộ nhớ (segmentation), trong đó người lập trình phải ý thức về sự tồn tại của các phân đoạn. Tuy nhiên giáo trình này sẽ không trình bày vấn đề phân đoạn bộ nhớ.

4.6.2. Thực hiện việc phân trang

Một đòi hỏi cốt yếu của bộ nhớ ảo là phải có bộ nhớ phụ để chứa toàn bộ chương trình. Nếu ta coi bản copy của chương trình trong bộ nhớ phụ là bản gốc, còn các phần của chương trình thỉnh thoảng được đưa vào bộ nhớ chính là các bản copy thì một số khái niệm mà chúng ta sử dụng sau này sẽ đơn giản hơn. Một công việc tự nhiên và quan trọng là cập nhật cho bản gốc, những thay đổi xảy ra với bản copy trong bộ nhớ chính, cuối cùng cần được phản ánh trong bản gốc.

Không gian đĩa ảo được chia thành các trang có kích thước bằng nhau. Hiện nay người ta sử dụng kích thước trang nằm trong khoảng 512..4096. Nó luôn được chọn là số mũ của 2. Tương tự như vậy, không gian địa chỉ vật lý cũng được chia thành các mảnh, mỗi mảnh có cùng kích thước với trang, để cho mỗi mảnh của bộ nhớ chính có thể chưa được vừa vặn một trang. Các mảnh của bộ nhớ chính mà các trang sẽ đưa vào được gọi là khung trang – page frame. Trên hình 4.56 bộ nhớ chính chỉ có một khung trang. Trong các thiết kế thực, bộ nhớ chính của các máy tính lớn có thể có hàng chục, hàng trăm hay thậm chí hàng nghìn khung trang.

Hình 4.56 minh họa một cách chia không gian địa chỉ 64K. Bộ nhớ ảo trên hình này có thể được triển khai thực hiện ở mức 2 bằng cách sử dụng một bảng phân trang

– page table có 16 word (bảng phân trang sẽ được trình bày ngay dưới đây). Khi một chương trình truy cập bộ nhớ, dù là để lấy dữ liệu, chứa dữ liệu, lấy chỉ thị, hay là nhảy, đầu tiên nó sẽ sinh ra một địa chỉ 16 bit tương ứng với một địa chỉ ảo nằm trong miền 0..65535.

Trong ví dụ này, địa chỉ 16 bit được sử dụng với 4 bit cao làm số trang ảo và 12 bit thấp làm địa chỉ trong trang ảo đã được chọn, như thể hiện trên hình 4.56a. Trong hình này địa chỉ 16 bit có giá trị là 12310 (số nhị phân trên hình vẽ là 0011 0000 0001 0110), theo cách sử dụng trên nó sẽ xem là địa chỉ của 22 của trang 3. Mối liên hệ giữa trang và địa chỉ ảo trong thí dụ này được thể hiện trên hình 4.56b. Nếu địa chỉ ảo của trang 3 là tại địa chỉ vật lý 12288, thì địa chỉ ảo 22 phải là tại địa chỉ vật lý 12310.

Sau khi đã tính ra được rằng cần trang ảo số 3, hệ điều hành phải tìm ra được trang ảo số 3 nằm ở đâu. Có 9 khả năng sảy ra: trong đó 8 khả năng là trang ảo số 3

nằm ở trong một trong số 8 khung trang trong bộ nhớ chính; khả năng thứ chín là trang ảo không có trong bộ nhớ chính mà nằm ở đâu đó trong bộ nhớ phụ.

Hình 4. 56. Một cách chia không gian địa chỉ

- Bảng phân trang

Để tìm ra được khả năng nào trong 9 khả năng nói trên là đúng, hệ điều hành sẽ đối chiếu với bảng phân trang. Có số đề mục (entry) bằng số lượng trang ảo, mỗi đề mục giống như một bản ghi (record) có 3 trường (hình 4.58).

Trường đầu tiên kích thước 1 bit, nó sẽ bằng 0 nếu trang ảo tương ứng không nằm trong bộ nhớ chính và sẽ bằng 1 nếu ngược lại.

Trường thứ 2 chứa địa chỉ nơi chứa trang ảo trong bộ nhớ phụ khi nó không nằm trong bộ nhớ chính (thí dụ số hiệu track hay sector trên đĩa). Phải có địa chỉ này để khi cần có thể tìm được trang trong bộ nhớ phụ và đọc nó vào bộ nhớ chính và sau này ghi nó trở lại vị trí ban đầu trong bộ nhớ phụ khi nó không còn cần phải nằm trong bộ nhớ chính nữa.

Trường thứ 3 kích thước 3 bit chứa một con số chỉ khung trang, là nơi mà trang nằm nếu nó ở bộ nhớ chính. Nếu trang không nằm trong bộ nhớ chính thì trường này không có ý nghĩa gì và được lờ đi.

Hình 4. 57. Ví dụ một địa chỉ ảo

Hình 4. 58. Ví dụ một bảng phân trang

- Cách tạo địa chỉ bộ nhớ chính (bộ nhớ vật lí) từ địa chỉ ảo

Giả sử trang ảo nằm trong bộ nhớ chính, trường khung trang 3 bit sẽ chỉ ra trang nằm ở đâu. Con số 3 bit này sẽ được nạp vào 3 bit trái nhất của thanh ghi địa chỉ của bộ nhớ MAR, còn 12 bit bên phải là địa chỉ trong ảo sẽ được nạp vào 12 bit bên phải của MAR. Đó là cách tạo thành địa chỉ bộ nhớ chính, được minh họa trên hình 4.59.

Ba bit số chỉ khung trang cộng với 12 bit offset tạo thành địa chỉ 15 bit, đó là địa chỉ cần cho bộ nhớ chính dung lượng 32 bit như trên hình 4.55 mà chúng ta đã xem xét. Bây giờ phần cứng có thể sử dụng địa chỉ này để lấy về word mà nó cần nạp vào thanh ghi đệm bộ nhớ MBR (nếu thao tác với bộ nhớ là đọc – read) hoặc có thể chứa nội dung của thanh ghi MBR vào một word cần thiết nào đó (nếu thao tác với bộ nhớ là ghi-write).

Hình 4. 59. Cách tạo ra địa chỉ bộ nhớ chính từ địa chỉ ảo

Hình 4.60 cho thấy một ánh xạ có thể giữa các trang ảo và khung trang vật lí. Trang ảo số 0 nằm ở khung trang số 1. Trang ảo số 1 nằm ở khung trang số 0. Trang ảo số 2 không nằm trong bộ nhớ chính. Trang ảo số 3 nằm ở khung trang số 2. Trang ảo số 4 không nằm trong bộ nhớ chính. Trang ảo số 5 nằm ở khung trang số 6…

Nếu hệ điều hành phải chuyển đổi địa chỉ ảo của chỉ thị mức 3 thành địa chỉ thực thì một máy mức 3 có bộ nhớ ảo có thể chạy chậm hơn một máy mức 3 không có bộ nhớ ảo rất nhiều lần và như vậy toàn bộ tưởng sẽ là không có nghĩa thực tế.

Hình 4. 60. Ánh xạ từ không gian địa chỉ ảo lên không gian bộ nhớ chính có 8 khung trang

Để tăng tốc độ việc chuyển đổi địa chỉ ảo thành địa chỉ vật lí, bảng phân trang thường được giữ trong các thanh ghi phần cứng đặc biệt, việc chuyển đổi thực hiện chuyển tiếp bằng phần cứng. Cách này đòi hỏi các chi phí phần cứng.

Một cách khắc để tăng tốc là giữ bảng phân trang trong các thanh ghi tốc độ cao và dùng vi chương trình thực hiện chuyển đổi bằng cách lập trình trực tiếp đối với các thanh ghi. Tùy thuộc vào kiến trúc của mức vi chương trình, chuyển đổi bằng cách này có thể gần nhanh bằng cách chuyển đổi trực tiếp bằng phần cứng mà không đòi hỏi phải có mạch điện đặc biệt.

4.6.3. Phương pháp cấp trang khi có yêu cầu và mô hình tập làm việc

Trong thực tế bộ nhớ chính nói chung không đủ lớn để chứa tất cả các trang. Sự truy cập tới một địa chỉ thuộc một trang mà trang đó không có trong bộ nhớ chính được gọi là lỗi trang – page fault. Khi lỗi trang xảy ra, hệ điều hành cần phải đọc trang

được yêu cầu từ bộ nhớ phụ vào bộ nhớ chính, nhập vị trí nhớ vật lí mới của nó vào bảng phân trang và sau dó lặp lại chỉ thị đã gây ra lỗi trang.

4.6.3.1. Phương pháp cấp trang khi có yêu cầu

Với máy có bộ nhớ ảo có thể khởi động một chương trình ngay cả khi không có phần nào của chương trình này nằm trong bộ nhớ chính, chỉ cần thiết lập cho bảng phân trang để chỉ ra là mọi trang ảo nằm trong bộ nhớ phụ chứ không phải là trong bộ nhớ chính. Khi CPU lấy chỉ thị đầu tiên, lập tức nó gặp một lỗi trang, điều này làm cho trang có chứa chỉ thị đầu tiên được nạp vào và bảng phân trang được cập nhập thông tin. Sau đó chỉ thị đầu tiên có thể bắt đầu thực hiện. Nếu chỉ thị đầu tiên có chứa hai địa chỉ mà chúng lại nằm ở trang khác với trang chứa chính chỉ thị, thì lại xảy ra hai lỗi trang nữa và sẽ lại có thêm hai trang được nạp vào bộ nhớ chính trước khi chỉ thị này được thi hành. Các chỉ thị tiếp theo của chương trình cũng có thể gây ra các lỗi trang nữa và quá trình tren lại tiếp diễn….

Phương pháp vận hành bộ nhớ ảo như thế gọi là: cấp trang khi có yêu cầu – demand paging, nó giống thuật toán nổi tiếng demand feeding (cho ăn khi đòi) đối với trẻ con: khi đứa trẻ khóc bạn cần cho nó ăn, chứ không cho nó ăn những giờ đã dịnh trong ngày. Trong phương pháp cấp trang khi có yêu cầu, các trang chỉ được nạp vào bộ nhớ chính khi xuất hiện một yêu cầu thực hiện về trang, chứ không phải là được nạp từ trước.

Việc xem xét có sử dụng phương pháp cấp trang khi có yêu cầu hay không chỉ liên quan tới lúc bắt đầu chạy một chương trình lần đầu tiên. Khi chương trình này đã chạy được một lúc rồi, thì các trang cần đến đã được tập hợp trong bộ nhớ chính.

Nếu máy tính hoạt động trong chế độ chia sẻ thời gian và người sử dụng được chuyển đổi kiểu quay vòng, ví dụ mỗi chương trình của người sử dụng được cho chạy 100ms rồi tạm dừng để cho chạy một chương trình khác… thì từng chương trình sẽ khởi động lại nhiều lần trong quá trình chạy của nó.

Bởi vì mỗi chương trình có một bản đồ nhớ duy nhất và bản đồ này sẽ thay đổi khi các chương trình sẽ được chuyển đổi, cho nên vấn đề thay đổi lặp đi lặp lại nó trở thành một vấn đề nghiêm trọng, làm giảm hiệu suất của hệ thống.

4.6.3.2. Phương pháp mô hình tập làm việc

Một cách tiếp cận khác dựa trên sự quan sát thấy rằng hầu hết các chương trình không truy cập không gian địa chỉ của chúng đồng đều như nhau mà có khuynh hướng tập trung vào một số ít các trang. Sự truy cập bộ nhớ có thể là lấy một chỉ thị, chỉ thị này có thể lấy dữ liệu hoặc chứa dữ liệu. Tại một thời điểm t nào đó, tạo thành một tập bao gồm tất cả các trang dược sử dung k lần truy cập bộ nhớ gần đó nhất. Người ta gọi tập này là tập làm việc (working set), ký hiệu w (k,t). Bởi vì k+1 sự truy cập bộ nhớ mới đây nhất chắc chắn đã sử dụng tất cả các trang được k lần truy cập bộ nhớ mới