Sơ Đồ Chuyển Địa Chỉ Trong Hệ Thống Phân Đoạn

trang cho tham khảo bộ nhớ. Ngoài ra, nếu định địa chỉ gián tiếp cấp 1 được phép (thí dụ, một chỉ thị load trên trang 16 có thể tham khảo tới một địa chỉ bộ nhớ trên trang 0, mà nó tham khảo gián tiếp tới trang 23), thì phân trang yêu cầu ít nhất 3 khung trên quá trình. Điều gì có thể xảy ra nếu một quá trình chỉ có hai khung trang.

- Các giải thuật cấp phát trang

Có hai tiếp cận:

a) Cấp phát cố định

- Cấp phát công bằng: nếu có m khung trang và n quá trình, mỗi quá trình được cấp m/n khung trang

- Cấp phát theo tỉ lệ: dựa vào kích thước của tiến trình để cấp phát số khung

trang:

i. Gọi si = kích thước của bộ nhớ ảo cho quá trình pi

ii. S = Σ si

iii. m = tổng số khung trang có thể sử dụng

iv. Cấp phát ai khung trang tới quá trình pi: ai = (si / S) m

b) Cấp phát theo độ ưu tiên

Sử dụng ý tưởng cấp phát theo tỷ lệ, nhưng lượng khung trang cấp cho quá trình phụ thuộc vào độ ưu tiên của quá trình hơn là phụ thuộc kích thước quá trình

Nếu quá trình pi phát sinh lỗi trang, chọn một trong các khung trang của nó để thay thế, hoặc chọn một khung trang của quá trình khác với độ ưu tiên thấp hơn để thay thế.

- Thay thế trang toàn cục hay cục bộ

Có thể phân các thuật toán thay thế trang thành hai lớp chính:

i. Thay thế toàn cục: khi lỗi trang xảy ra với một quá trình, chọn trang “nạn nhân” từ tập tất cả các khung trang trong hệ thống, bất kể khung trang đó đang được cấp phát cho một quá trình khác.

ii. Thay thế cục bộ: yêu cầu chỉ được chọn trang thay thế trong tập các khung trang được cấp cho quá trình phát sinh lỗi trang

Một khuyết điểm của giải thuật thay thế toàn cục là các quá trình không thể kiểm soát được tỷ lệ phát sinh lỗi trang của mình. Vì thế, tuy giải thuật thay thế toàn

cục nhìn chung cho phép hệ thống có nhiều khả năng xử lý hơn, nhưng nó có thể dẫn hệ thống đến tình trạng trì trệ toàn bộ hệ thống (thrashing).

3.2.7 Thrashing

Nếu một quá trình không có đủ các khung trang để chứa những trang cần thiết cho xử lý thì nó sẽ thường xuyên phát sinh lỗi trang và vì thế phải dùng đến rất nhiều thời gian sử dụng CPU để thực hiện thay thế trang. Một hoạt động phân trang như thế được gọi là sự trì trệ (thrashing). Một quá trình lâm vào trạng thái trì trệ nếu nó sử dụng nhiều thời gian để thay thế hơn là để xử lý.

Hiện tượng này ảnh hưởng nghiêm trọng đến hoạt động hệ thống, xét tình huống sau:

1) Hệ điều hành giám sát việc sử dụng CPU

2) Nếu hiệu suất sử dụng CPU quá thấp, hệ điều hành sẽ nâng mức độ đa chương bằng cách đưa thêm một quá trình mới vào hệ thống.

3) Hệ thống có thể sử dụng giải thuật thay thế toàn cục để chọn các trang nạn nhân thuộc một tiến trình bất kỳ để có chỗ nạp quá trình mới, có thể sẽ thay thế cả các trang của tiến trình đang xử lý hiện hành.

4) Khi có nhiều quá trình trong hệ thống hơn, thì một quá trình sẽ được cấp ít khung trang hơn và do đó phát sinh nhiều lỗi trang hơn.

5) Khi các quá trình phát sinh nhiều lỗi trang, chúng phải trải qua nhiều thời gian chờ các thao tác thay thế trang hoàn tất, lúc đó hiệu suất sử dụng CPU lại giảm.

6) Hệ điều hành lại quay trở lại bước 1.

Theo kịch bản trên đây, hệ thống sẽ lâm vào tình trạng luẩn quẩn của việc giải phóng các trang để cấp phát thêm khung trang cho một quá trình, và các quá trình khác lại thiếu khung trang..và các quá trình không thể tiếp tục xử lý. Đây chính là tình trạng trì trệ toàn bộ hệ thống. Khi tình trạng trì trệ này xảy ra, hệ thống gần như mất khả năng xử lý, tốc độ phát sinh lỗi trang tăng rất cao không công việc nào có thể kết thúc vì tất cả quá trình đều bận rộn với việc phân trang.

Để ngăn cản tình trạng trì trệ này xảy ra, cần phải cấp cho quá trình đủ các khung trang cần thiết để hoạt động. Vấn đề cần giải quyết là làm sao biết được quá trình cần bao nhiêu trang?

1) Mô hình cục bộ

Theo lý thuyết cục bộ thì khi một quá trình xử lý nó có khuynh hướng di chuyển từ nhóm trang cục bộ này đến nhóm trang cục bộ khác. Một nhóm trang cục bộ là một tập các trang đang được quá trình dùng đến trong một khoảng thời gian. Một chương trình thường bao gồm nhiều nhóm trang cục bộ khác nhau và chúng có thể giao nhau.

2) Mô hình tập làm việc

Mô hình tập làm việc (working set model) này dựa trên cơ sở lý thuyết cục bộ. Mô hình này sử dụng tham số Δ để định nghĩa cửa sổ cho tập làm việc. Giả sử, khảo sát Δ đơn vị thời gian (lần truy xuất trang) cuối cùng, tập các trang được quá trình truy xuất đến trong Δ lần truy cập cuối cùng được gọi là tập làm việc của quá trình tại thời điểm hiện tại. Nếu một trang đang được quá trình truy xuất tới, nó sẽ nằm trong tập làm việc nếu nó không sử dụng nữa, nó sẽ bị loại khỏi tập làm việc của quá trình sau Δ đơn vị thời gian kể từ lần truy xuất cuối cùng đến nó. Như vậy, tập làm việc chính là sự xấp xỉ của khái niệm nhóm trang cục bộ.

Hình 3.41 Mô hình tập làm việc

Thuộc tính rất quan trọng của tập làm việc là kích thước của nó. Nếu tính toán kích thước tập làm việc WSSi, cho mỗi tiến trình trong hệ thống thì có thể xem:

D = Σ WSSi

Với D là tổng số khung trang yêu cầu cho toàn hệ thống. Mỗi quá trình sử dụng các trang trong tập làm việc của nó, nghĩa là quá trình i yêu cầu WSSi khung trang. Nếu tổng số trang yêu cầu vượt quá tổng số trang có thể sử dụng trong hệ thống (D > m), thì sẽ xảy ra tình trạng trì trệ toàn bộ.

Dùng mô hình tập làm việc là đơn giản. Hệ điều hành kiểm soát tập làm việc của mỗi quá trình và cấp phát cho quá trình tối thiểu các khung trang để chứa đủ tập làm việc của nó. Nếu có đủ khung trang bổ sung thì quá trình khác có thể được khởi tạo. Nếu tổng kích thước tập làm việc gia tăng vượt quá tổng số khung sẳn có, hệ điều

hành chọn một quá trình để tạm dừng. Những trang của quá trình này được viết ra đĩa và các khung trang của nó được cấp phát lại cho quá trình khác. Quá trình được tạm dừng có thể khởi động lại sau đó.

Chiến lược tập làm việc ngăn chặn sự trì trệ trong khi giữ cấp độ đa chương cao nhất có thể. Do đó, nó tối ưu việc sử dụng CPU.

Khó khăn với mô hình tập làm việc này là giữ vết của tập làm việc. Cửa sổ tập làm việc là một cửa sổ di chuyển. Tại mỗi tham khảo bộ nhớ, một tham khảo mới xuất hiện khi một tham khảo trước đó kết thúc và tham khảo cũ nhất trở thành điểm kết thúc khác. Một trang ở trong tập làm việc nếu nó được tham khảo bất cứ nơi nào trong cửa sổ tập làm việc. Chúng ta có thể xem mô hình tập làm việc gần xấp xỉ với ngắt đồng hồ sau từng chu kỳ cố định và bit tham khảo.

3) Tần suất lỗi trang

Tần suất lỗi trang rất cao khiến tình trạng trì trệ hệ thống xảy ra. Khi tần suất lỗi trang quá cao, quá trình cần thêm một số khung trang. Ngược lại, khi tần suất quá thấp, quá trình có thể sở hữu nhiều khung trang hơn mức cần thiết. Có thể thiết lập một giá trị cận trên và cận dưới cho tần suất xảy ra lỗi trang và trực tiếp ước lượng và kiểm soát tần suất lỗi trang để ngăn chặn tình trạng trì trệ xảy ra:

- Nếu tần suất lỗi trang vượt quá cận trên, cấp cho quá trình thêm một khung

trang trình.

- Khi tần suất lỗi trang thấp hơn cận dưới, thu hồi bớt một khung trang từ quá Với chiến lược tập làm việc, chúng ta có thể có phải tạm dừng một quá trình.

Nếu tỉ lệ lỗi trang tăng và không có trang nào trống, chúng ta phải chọn một số quá trình và tạm dừng nó. Sau đó, những khung trang được giải phóng sẽ được phân phối lại cho các quá trình với tỉ lệ lỗi trang cao.

3.2.8 Các vấn đề khác

1) Kích thước trang

Kích thước trang thông thường được xác định bởi phần cứng. Không có sự chọn lựa lý tưởng cho kích thước trang:

- Kích thước trang càng lớn thì kích thước bảng trang càng giảm

- Kích thước trang càng nhỏ thì cho phép tổ chức nhóm trang cục bộ tốt hơn và giảm sự phân mảnh trong

- Thời gian nhập xuất nhỏ khi kích thước trang lớn

- Kích thước trang nhỏ thì có thể giảm số lượng thao tác nhập xuất cần thiết vì có thể xác định các nhóm trang cục bộ chính xác hơn

- Kích thước trang lớn sẽ giảm tần xuất lỗi trang Đa số các hệ thống chọn kích thước trang là 4 KB.

2) Cấu trúc chương trình

Về nguyên tắc, kỹ thuật phân trang theo yêu cầu được thiết kế nhằm giúp người dùng khỏi bận tâm đến việc sử dụng bộ nhớ một cách hiệu quả. Tuy nhiên, nếu hiểu rò tổ chức bộ nhớ trong kỹ thuật phân trang, lập trình viên có thể giúp cho hoạt động của hệ thống tốt hơn với chương trình được xây dựng phù hợp.

Thí dụ, giả sử 1 trang có kích thước 128 bytes, một chương trình khởi tạo và gán giá trị mảng có kích thước 128x128 như sau:

Var A: array[1..128] of array [1..128] of byte; For i:= 1 to 128 do

For j:=1 to 128 do A[i][j]:=0;

Trong Pascal, C, PL/I, mảng trên đây được lưu trữ theo thứ tự dòng, mỗi dòng mảng chiếm một trang bộ nhớ, do đó tổng số lỗi trang phát sinh sẽ là 128.

Trong Fortran, mảng trên đây lại được lưu trữ theo thứ tự cột, do đó tổng số lỗi trang phát sinh sẽ là 128x128 = 1638.

3) Neo các trang trong bộ nhớ chính

Khi áp dụng kỹ thuật phân trang đôi lúc có nhu cầu “neo” trong bộ nhớ chính một số trang quan trọng hoặc thường được sử dụng hoặc không thể chuyển ra bộ nhớ phụ để bảo toàn dữ liệu.

Khi đó sử dụng thêm một bit khoá gán tương ứng cho từng khung trang. Một khung trang có bit khoá được đặt sẽ không bị chọn để thay thế.

3.2.9 Phân đoạn theo yêu cầu

Sự phân đoạn cho phép người lập trình xem bộ nhớ như bao gồm một tập các không gian nhớ hoặc các đoạn (segment) có địa chỉ được xác định. Với bộ nhớ ảo

người lập trình không cần quan tâm đến giới hạn bộ nhớ được đưa ra bởi bộ nhớ chính. Các segment có thể có kích thước không bằng nhau và được ấn định một cách động. Địa chỉ tham chiếu bộ nhớ trong trường hợp này bao gồm: Segment Number và Offset.

Đối với người lập trình thì sự phân đoạn không gian địa chỉ có một số thuận lợi sau đây so với trường hợp không phân đoạn không gian địa chỉ:

1) Nó đơn giản để điều khiển các cấu trúc dữ liệu lớn dần (growing) trong quá trình hoạt động của hệ thống. Nếu người lập trình không biết trước dữ liệu sẽ lớn đến chừng nào tại thời điểm chạy thì việc ấn định kích thước của động cho segment mang lại nhiều thuận lợi cho người lập trình.

2) Nó cho phép các chương trình không phụ thuộc vào sự thay đổi vào sự biên dịch lại. Nó không yêu cầu thiết lập lại toàn bộ chương trình khi chương trình được liên kết hoặc được nạp trở lại. Việc này chỉ có thể thực hiện bằng cách sử dụng nhiều phân đoạn (Multiple Segment).

3) Nó thích hợp với chiến lược chia sẻ segment giữa các tiến trình. Người lập trình có thể đặt một chương trình tiện ích hoặc một bảng dữ liệu thường sử dụng vào một segment mà có thể được tham chiếu bởi nhiều tiến trình khác nhau.

4) Nó thích hợp với chiến lược bảo vệ bộ nhớ. Bởi vì một segment có thể được sinh ra để chứa một tập xác định các thủ tục hoặc dữ liệu, sau đó người lập trình hoặc người quản trị hệ thống có thể gán quyền truy cập với các độ ưu tiên thích hợp nào đó.

- Tổ chức của hệ thống phân đoạn

Trong kỹ thuật phân đoạn đơn, mỗi tiến trình sở hữu một bảng đoạn riêng, khi tất cả các đoạn của tiến trình được nạp vào bộ nhớ chính thì bảng đoạn của tiến trình được tạo ra và cũng được nạp vào bộ nhớ, mỗi phần tử trong bảng đoạn chứa địa chỉ bắt đầu của đoạn tương ứng trong bộ nhớ chính và độ dài của đoạn. Trong kỹ thuật bộ nhớ ảo cũng vậy, nhưng một phần tử trong bảng đoạn sẽ chứa nhiều thông tin phức tạp hơn. Bởi vì trong kỹ thuật bộ nhớ ảo chỉ có một vài segment của tiến trình được nạp vào bộ nhớ chính, do đó cần phải có một bít để cho biết một đoạn tương ứng của tiến trình là có hay không trên bộ nhớ chính và một bít cho biết đoạn có bị thay đổi

hay không so với lần nạp gần đây nhất. Cụ thể là nó phải có thêm các bít điều khiển:

+ Bít M (Modify): Cho biết nội dung của đoạn tương ứng có bị thay đổi hay không so với lần nạp gần đây nhất. Nếu nó không bị thay đổi thì việc phải ghi lại nội dung của một đoạn khi cần phải đưa một đoạn ra lại bộ nhớ ngoài là không cần thiết, điều này giúp tăng tốc độ trong các thao tác thay thế đoạn.

Offset

Virtual Address

Segment Number

Các bít điều khiển

Length

Segment Base