Cấp phát khung trang

Vấn đề đặt ra là làm thế nào để cấp phát một vùng nhớ tự do có kích thước cố định cho các tiến trình khác nhau?Trong trường hợp đơn giản nhất của bộ nhớ ảo là hệ đơn nhiệm, có thể cấp phát cho tiến trình duy nhất của người dùng tất cả các khung trang trống
Nội dung trích xuất từ tài liệu:
Cấp phát khung trangIII. Cấp phát khung trangNguồn:3c.com.vnVấn đề đặt ra là làm thế nào để cấp phát một vùng nhớ tự do có kích thước cố định chocác tiến trình khác nhau?Trong trường hợp đơn giản nhất của bộ nhớ ảo là hệ đơn nhiệm, có thể cấp phát cho tiếntrình duy nhất của người dùng tất cả các khung trang trống.Vấn đề nảy sinh khi kết hợp kỹ thuật phân trang theo yêu cầu với sự đa chương : cần phảiduy trì nhiều tiến trình trong bộ nhớ cùng lúc, vậy mỗi tiến trình sẽ được cấp bao nhiêukhung trang. Số khung trang tối thiểu:Với mỗi tiến trình, cần phải cấp phát một số khung trang tối thiểu nào đó để tiến trình cóthể hoạt động. Số khung trang tối thiểu này được quy định bởi kiến trúc của của một chỉthị.Khi một lỗi trang xảy ra trước khi chỉ thị hiện hành hoàn tất, chỉ thị đó cần được táikhởi động, lúc đó cần có đủ các khung trang để nạp tất cả các trang mà một chỉ thị duynhất có thể truy xuất.Số khung trang tối thiểu được qui định bởi kiến trúc máy tính, trong khi số khung trangtối đa được xác định bởi dung lượng bộ nhớ vật lý có thể sử dụng. Các thuật toán cấp phát khung trangCó hai hướng tiếp cận: Cấp phát cố định:Cấp phát công bằng: nếu có m khung trang và n tiến trình, mỗi tiến trình được cấp m /nkhung trang.Cấp phát theo tỷ lệ: tùy vào kích thước của tiến trình để cấp phát số khung trang :si = kích thước của bộ nhớ ảo cho tiến trình piS = Σ sim = số lượng tổng cộng khung trang có thể sử dụngCấp phát ai khung trang cho tiến trình pi : ai = (si / S) m Cấp phát theo độ ưu tiên : sử dụng ý tưởng cấp phát theo tỷ lệ, nhưng nhưng số lượngkhung trang cấp cho tiến trình phụ thuộc vào độ ưu tiên của tiến trình, hơn là phụ thuộckích thước tiến trình:Nếu tiến trình pi phát sinh một lỗi trang, chọn một trong các khung trang của nó để thaythế, hoặc chọn một khung trang của tiến 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: Thay thế toàn cục: khi lỗi trang xảy ra với một tiến trình , chọn trang « nạn nhân » từ tậptất cả các khung trang trong hệ thống, bất kể khung trang đó đang được cấp phát cho mộttiến trình khác. Thay thế cục bộ: yêu cầu chỉ được chọn trang thay thế trong tập các khung trang đượccấp cho tiến trình phát sinh lỗi trang.Một khuyết điểm của thuật toán thay thế toàn cục là các tiến 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 thuật toán thay thế toàn cục nhìnchung 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 đếntình trạng trì trệ toàn bộ (thrashing). III.1. Trì trệ toàn bộ hệ thống (Thrashing)Nếu một tiến 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 các lỗi trang , và vì thế phải dùng đến rất nhiều thời giansử 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 tiến trình lâm vào trạng thái trì trệ nếu nó sử dụng nhiều thờigian để thay thế trang hơn là để xử lý !Hiện tượng trì trệ này ảnh hưởng nghiêm trọng đến hoạt động hệ thống, xét tình huốngsau : Hệ điều hành giám sát việc sử dụng CPU. 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ằngcách đưa thêm một tiến trình mới vào hệ thống. Hệ thống có thể sử dụng thuật toán thay thế toàn cục để chọn các trang nạn nhân thuộcmột tiến trình bất kỳ để có chỗ nạp tiến trình mới, có thể sẽ thay thế cả các trang của tiếntrình đang xử lý hiện hành. Khi có nhiều tiến trình trong hệ thống hơn, thì một tiến trình sẽ được cấp ít khung tranghơn, và do đó phát sinh nhiều lỗi trang hơn. Khi các tiến trình phát sinh nhiều lỗi trang , chúng phải trải qua nhiều thời gian chờ cácthao tác thay thế trang hoàn tất, lúc đó hiệu suất sử dụng CPU lại giảm 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áctrang để cấp phát thêm khung trang cho một tiến trình, và các tiến trình khác lại thiếukhung trang...và các tiến trình không thể tiếp tục xử lý. Đây chính là tình t ạng trì trệ trtoà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 cao khủng khiếp, không công việc nào có thể kết thúc vì tấtcả các tiến 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 tiến t ình đủ các khung trang trcần thiết để hoạt động. Vấn đề cần giải quyết là làm sao biết được tiến trình cần baonhiêu trang?Mô hình cục bộ ( Locality) : theo lý thuyết cục bộ, thì khi một tiến 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ộtnhóm trang cục bộ là một tập các trang đang được tiến ...