He dieu hanh 6
Chia sẻ bởi Mr Quân |
Ngày 29/04/2019 |
44
Chia sẻ tài liệu: He dieu hanh 6 thuộc Bài giảng khác
Nội dung tài liệu:
Chương 6: Quản lý bộ nhớ
Giới thiệu
Quản lý bộ nhớ không phân trang
Quản lý bộ nhớ với phân đoạn cố định
Quản lý bộ nhớ với phân đoạn động
Giới thiệu
Bộ nhớ chính là thiết bị lưu trữ duy nhất thông qua đó CPU có thể trao đổi thông tn với môi trường ngoài.
Nhu cầu tổ chức quản lý bộ nhớ là nhiệm vụ hàng đầu của hệ điều hành.
Bộ nhớ chính được tổ chức như một mảng một chiều các ô nhớ. Việc trao đổi thông tin với môi trường ngoài được thực hiện thông qua các thao tác đọc ghidữ liệu vào địa chỉ cụ thể của bộ nhớ.
Hầu hết các hệ điều hành hiện đại đều cho phép chế độ đa nhiệm nhằm nâng cao hiệu quả sử dụng CPU.
Quản lý bộ nhớ không phân trang, không Swapping
Bộ nhớ chỉ được chia sẻ cho hệ điều hành và một chương trình duy nhất của người sử dụng. Tức tại một thời điểm một phần bộ nhớ sẽ do HĐH chiếm giữ và phần còn lại thuộc về một tiến trình người sử dụng, ctiến trình này có toàn quyền sử dụng vùng nhớ dành cho nó.
Mô hình
Để bảo vệ vùng nhớ của HĐH khỏi sự xâm phạm của tiến trình người dùng cần phải tổ chức thanh ghi giới hạn.
Địa chỉ cao nhất của vùng nhớ được cấp phát cho HĐH sẽ được nạp vào thanh ghi giới hạn.
Tiến trình người sử dụng
Hệ điều hành
Quản lý bộ nhớ không phân trang, không Swapping (tt)
Tất cả các địa chỉ được tiến trình người dùng truy xuất đến sẽ được so sánh với nội dung thanh ghi giới hạn, nếu địa chỉ lớn hơn nội dung thanh ghi giới hạn thì đây là một địa chỉ hợp lệ, ngược lại một ngắt được phát sinh để thông báo cho hệ thống về một truy xuất bất hợp lệ.
Với tổ chức như vậy thì chỉ có thể xử lý một chương trình duy nhất tại một thời điểm.
Trong thực tế có rất nhiều tiến trình phải trải qua phần lớn thời gian chờ thao tác nhập xuất hoàn thành suốt thời gian này CPU nhàn rỗi để nâng cao hiệu suất sử dụng CPU cần cho phép chế độ đa chương.
Quản lý bộ nhớ với những phân đọan cố định
Hệ điều hành chia bộ nhớ thành n vùng nhớ cố định( có thể không bằng nhau)
Việc phân chia này được thực hiện vào lúc khởi động hệ thống và không thay đổi suốt quá trình chạy.
Với tổ chức như vậy cần duy trì một hàng đợi duy nhất để lưu trữ những tiến trình chưa được cấp phát bộ nhớ.
Quản lý bộ nhớ với những phân đọan cố định (tt)
Tất cả tiến trình được đặt trong một hàng đợi duy nhất. Khi có một phân vùng tự do , tiến trình đầu tiên trong hàng đợi có kích thước phù hợp sẽ được đặt vào phân vùng này và cho xử lý.
Nếu kích thước của tiến trình không vừa đúng bằng kích thước phân vùng chứa nó, phần bộ nhớ không sử dụng đến trong phân vùng sẽ bị lãng phí.
xảy ra hiện tượng phân mảnh nội vi.
Mức độ đa chương của hệ thống bị giới hạn bởi số lượng phân vùng
Vấn đề bảo vệ giữa các phân vùng: Để bảo vệ cần tổ chức hai thanh ghi : thanh ghi nền và thanh ghi giới hạn.
Khi tiến trình được tạo lập, nạp vào thanh ghi nền địa chỉ bắt đầu của phân vùng được cấp phát cho tiến trìnhvà nạp vào thanh ghi giới hạn kích thước của tiến trình
Sau đó mỗi đị chỉ bộ nhớ được phát sinh sẽ tự động được cộng với địa chỉ chứa trong thanh ghi nền để cho ra địa chỉ tuyệt đối trong bộ nhớ và các địa chỉ được đối chiếu với thanh ghi giới hạn để bảo đảm tiến trình không truy xuất ngoài phạm vi được cấp phát cho nó.
Quản lý bộ nhớ với những phân đọan động
Như tổ chức quản lý bộ nhớ trên gây ra lãng phí bộ nhớ vì vậy một phương pháp mới được đề xuất là cấp pháp cho tiến trình vùng nhớ vừa đủ kích thước của tiến trình.
Khi một tiến trình kết thúc vùng nhớ đã đã cấp cho nó sẽ được giải phóng và được cấp pháp cho tiến trình khác.
Với giải pháp này không còn hiện tượng phân mảnh nội vi nhưng lại xuất hiện phân mảng ngoại vi. Khi các tiến trình lần lượt vào ra khỏi hệ thống, dần dần xuất hiện các khe hở giữa các tiến trình có thể dẫn đến tình huống tổng vùng nhớ còn trống đủ để thỏa mãn yêu cầu nhưng các vùng nhớ này không liên tục.
Có thể áp dụng kỹ thuật dồn bộ nhớ để kết hợp các mảnh bộ nhớ rời rạc thành một vùng nhớ lớn liên tục.
Một vấn đề khác nảy sinh khi kích thước của tiến trình tăng trưởng trong quá trình xử lý mà không còn vùng nhớ còn trông gần kề để mở rộng vùng nhớ cho tiến trình.
Quản lý bộ nhớ với những phân đọan động (tt)
Quản lý các ô nhớ còn trống: Cần phải lưu trữ thông tin các ô nhớ cò trống để cấp phát cho các tiến trình, Có hai phương pháp chính: Bitmap và danh sách liên kết.
Phương pháp Bitmap:
Chia bộ nhớ thành từng đơn vị nhỏ (vài bytes) . Xây dựng bitmap, ứng với mỗi bit trong bitmap là một đơn vị bộ nhớ.
Bit được đánh dấu là 1 khi đơn vị bộ nhớ tương ứng đã được cấp phát
Bit được đánh dấu 0 khi đơn vị bộ nhớ tương ứng chưa được cấp phát.
Thao tác cấp phát bộ nhớ là : Giả sử tiến trình cần k đơn vị bộ nhớ, HĐH duyệt bitmap và tìm ra k bit liên tiếp bằng 0
Quản lý bộ nhớ với những phân đọan động
Quản lý bộ nhớ với những phân đọan động (tt)
Quản vùng nhớ còn trống bằng danh sách liên kết
Tổ chức một danh sách liên kết, mỗi phần tử tương ứng với một tiến trình hay lỗ hổng. Mỗi phần tử trong danh sách có 4 trường :
cờ biểu thị tiến trình (P) hay lỗ hổng (H)
Địa chỉ bắt đầu của vùng nhớ tương ứng
Kích thước của vùng nhớ
Con trỏ Next
Quản lý bộ nhớ với những phân đọan động (tt)
Thao tác cấp phát bộ nhớ
First Fit : Xác định lỗ hổng đầu tiên trong danh sách có kích thước đủ lớn để cấp phát cho tiến trình và lỗ hổng này được chia làm 2 phần : 1 phần cho tiến trình và phần kia là lỗ hổng mới.
Best Fit : xác định lỗ hổng bé nhất có kích thước đủ lớn để cấp phát cho tiến trình.
Worst Fit : Cấp phát phân đoạn tự do lớn nhất đủ lớn để cấp phát cho riến trình.
Có thể làm tăng tốc độ bcho cả 3 thuật toán trên bằng cách tổ chức 2 danh sách : 1 cho tiến trình và một cho lỗ hổng. Tuy nhiên lại làm chậm thao tác giải phóng bộ nhớ.
Quản lý bộ nhớ với những phân đọan động (tt)
Thao tác giải phóng bộ nhớ
Khi thực hiện thao tác giải phóng chú ý cần xem xét các trường hợp khác nhau của 2 phần tử kề nhau. Nhờ đó thực hiện thao tác kết hợp hai lỗ hổng kề nhau một cách phù hợp:
Trước giải phóng Sau giải phóng
Quản lý bộ nhớ với những phân đọan động (tt)
Quá trình Swapping
Trong hệ thống đa nhiệm nhiều người dùng thường là bộ nhớ không đủ chỗ để lưu trữ tất cả các tiến trình vì thế hệ thống dùng DSLK để lưu trữ tạm thời một số tiến trình nào đó chưa thật sự chạy, khi được cấp phát CPU thì hệ thống phải mang nó vào bộ nhớ chính . Việc di chuyển tiến trình từ bộ nhớ vào đĩa và ngược lại gọi là quá trình swapping.
Bộ nhớ ảo
Bộ nhớ ảo được đưa ra nhằm khắc phục tình trạng kích thước chương trình vượt quá kích thước bộ nhớ vật lý.
Hệ điều hành chia chương trình thành nhiều phần và giữa lại nhừng phần chương trình đang chạy hiện thời vừa đủ chứa trong bộ nhớ , phần còn lại lưu trữ trên đĩa. HĐH theo dõi và quản lý tất cả công việc swapping giữa đĩa và bộ nhớ . Dĩ nhiên bộ nhớ ảo vẫn có thể thiết kế cho hệ thống đa nhiệm.
Quản lý bộ nhớ với những phân đọan động (tt)
Sự phân trang (paging)
Hầu hết những hệ thống có sử dụng bộ nhớ ảo đều sử dụng kỹ thuật phâh trang. Địa chỉ ảo là địa chỉ tham khảo từ chương trình . Tập tất cả địa chỉ ảo gọi là vùng địa chỉ ảo, đối với những hệ thống không dùng bộ nhớ ảo , địa chỉ ảo cũng là địa chỉ vật lý.
Vùng địa chỉ ảo được chi thành nhiều trang (page) có kích thước bằng nhau tướng ứng với những khung trang (Page frame) trong bộ nhớ vật lý. Trang và khung trang luôn có kích thước bằng nhau.
Ví dụ: có 32K bộ nhớ vật lý chia thành 8 khung trang có kích thước 4K và 64K bộ nhớ ảo chia thành 16 trang kích thước 4K. Trong bất kỳ thời điểm nào chỉ có 8 trang từ bộ nhớ ảo ánh xạ vào bộ nhớ vật lý như sau:
Quản lý bộ nhớ với những phân đọan động
Quản lý bộ nhớ với những phân đọan động (tt)
Nếu lệnh nào đó trong chương trình tham khảo đến địa chỉ ảo không thuộc về bất kỳ trang nào đang được ánh xạ hiện thời gọi là lỗi trang. Trong trường hợp này HĐH tìm ra một khung trang nào ít sử dụng nhất trục xuất khỏi bộ nhớ và tìm kiếm trên đĩa trang nào chứa địa chỉ mà chương trình muốn tham khảo đến để chuyển vào bộ nhớ vật lý. Tiếp đến hệ thống cập nhật ánh xạ bộ nhớ cho trang mới.
Bảng trang
Hệ thống phải duy trì một bảng trang thể hiện ánh xạ từ bộ nhớ ảo vào bộ nhớ vật lý và chứa thông tin trang nào hiện thời đang dược ánh xạ.
Quản lý bộ nhớ với những phân đọan động (tt)
Quản lý bộ nhớ với những phân đọan động
Các thuật toán thay thế trang
Mỗi khi gặp lỗi trang HĐH phải chọn 1 trong các trang náo đó trục xuất ra khỏi bộ nhớ. Nếu nội dung trang đó bị thay đổi yhì phải ghi nội dung mới của trang lên đĩa. Vấn đề là chọn trang nào để trục xuất để giảm tổn phí.
Xét ví dụ một tiến trình truy xuất đến một dãy các trang sau:
7, 0,1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
giả sử có 3 khung trang và ban đầu cả 3 khung trang đều rỗng.
Quản lý bộ nhớ với những phân đọan động (tt)
Thuật toán FIFO
Ghi nhận thời điểm 1 trang được mang vào bộ nhớ chính khi cần thay thế trang , thì trang lâu nhất sẽ được chọn để trục xuất.
Với thuật toán này có thể có trang được chọn để thay thế có thể chứa nhiều dữ liệu cần thiết thường xuyên được nạp vào sớm , do vậy khi bị chuyển ra bộ nhớ phụ sẽ nhanh chóng gây ra lỗi trang.
Quản lý bộ nhớ với những phân đọan động (tt)
Thuật toán tối ưu
Thay thế trang sẽ lâu nhất được sử dụng trong tương lai
Thuật toán này bảo đảm lỗi trang là ít nhất tuy nhiên thuật toán này không khả thi vì không thể biết trước dãy các trang được truy xuất theo thứ tự.
Quản lý bộ nhớ với những phân đọan động (tt)
Thuật toán lâu nhất chưa sử dụng (LRU)
Với mỗi trang ghi nhận thời điểm cuối cùng trang được truy cập, trang được thay thế là trang lâu nhất chưa sử dụng.
Thuật toán đài hỏi một cơ chế xác định thứ tự các trang theo thời điểm truy xuất cuối cùng. Dùng stack
Cần tổ chức một stack lưu trữ số hiệu các trang
Mỗi khi thực hiện một truy xuất đến 1 trang , số hiệu của trang sẽ được xóa khỏi vị trí hiện hành trong stack và đưa lên đỉnh stack.
Trang ở đỉnh stack là trang được chọn để thay thế.
Quản lý bộ nhớ với những phân đọan động (tt)
Thuật toán Not Recently Used (NRU)
Thuật toán dựa trên sự tồn tại 2 bit gắn liền với mỗi trang để chỉ ra trang đó có vừa mới được tham khảo hay là được ghi lên hay không. Những bit này chứa trong bảng trang
Bit R =1: nếu trang đó truy cập ngược lại chưa được truy cập
Bit M =1 : Trang đó đã bị thay đổi ngược lại chưa bị thay đổi
Cứ mỗi lần truy cập bộ nhớ cần phải cập nhật lại các bit này
Khi một tiến trình bắt đầu cả 2 bit trong tất cả các trang được đặt bằng 0. theo một chu kỳ thời gian bit R được đặt lại bằng 0 để phân biệt những trang mới được truy cập với trang đã truy cập trước đó.
Khi xuất hiện một lỗi trang HĐH duyệt toàn bộ bảng trang và chia chúng thành 4 lớp dựa vào các bit R, M như sau:
Quản lý bộ nhớ với những phân đọan động (tt)
Class 0 : R=0, M=0
Class 1: R=0, M=1
Class 2: R=1, M=0
Class 3: R=1, M=1
Sau đó thuật toán chọn ra một trang để thay thế thuộc thuộc lớp thấp nhất khác rỗng.
Giới thiệu
Quản lý bộ nhớ không phân trang
Quản lý bộ nhớ với phân đoạn cố định
Quản lý bộ nhớ với phân đoạn động
Giới thiệu
Bộ nhớ chính là thiết bị lưu trữ duy nhất thông qua đó CPU có thể trao đổi thông tn với môi trường ngoài.
Nhu cầu tổ chức quản lý bộ nhớ là nhiệm vụ hàng đầu của hệ điều hành.
Bộ nhớ chính được tổ chức như một mảng một chiều các ô nhớ. Việc trao đổi thông tin với môi trường ngoài được thực hiện thông qua các thao tác đọc ghidữ liệu vào địa chỉ cụ thể của bộ nhớ.
Hầu hết các hệ điều hành hiện đại đều cho phép chế độ đa nhiệm nhằm nâng cao hiệu quả sử dụng CPU.
Quản lý bộ nhớ không phân trang, không Swapping
Bộ nhớ chỉ được chia sẻ cho hệ điều hành và một chương trình duy nhất của người sử dụng. Tức tại một thời điểm một phần bộ nhớ sẽ do HĐH chiếm giữ và phần còn lại thuộc về một tiến trình người sử dụng, ctiến trình này có toàn quyền sử dụng vùng nhớ dành cho nó.
Mô hình
Để bảo vệ vùng nhớ của HĐH khỏi sự xâm phạm của tiến trình người dùng cần phải tổ chức thanh ghi giới hạn.
Địa chỉ cao nhất của vùng nhớ được cấp phát cho HĐH sẽ được nạp vào thanh ghi giới hạn.
Tiến trình người sử dụng
Hệ điều hành
Quản lý bộ nhớ không phân trang, không Swapping (tt)
Tất cả các địa chỉ được tiến trình người dùng truy xuất đến sẽ được so sánh với nội dung thanh ghi giới hạn, nếu địa chỉ lớn hơn nội dung thanh ghi giới hạn thì đây là một địa chỉ hợp lệ, ngược lại một ngắt được phát sinh để thông báo cho hệ thống về một truy xuất bất hợp lệ.
Với tổ chức như vậy thì chỉ có thể xử lý một chương trình duy nhất tại một thời điểm.
Trong thực tế có rất nhiều tiến trình phải trải qua phần lớn thời gian chờ thao tác nhập xuất hoàn thành suốt thời gian này CPU nhàn rỗi để nâng cao hiệu suất sử dụng CPU cần cho phép chế độ đa chương.
Quản lý bộ nhớ với những phân đọan cố định
Hệ điều hành chia bộ nhớ thành n vùng nhớ cố định( có thể không bằng nhau)
Việc phân chia này được thực hiện vào lúc khởi động hệ thống và không thay đổi suốt quá trình chạy.
Với tổ chức như vậy cần duy trì một hàng đợi duy nhất để lưu trữ những tiến trình chưa được cấp phát bộ nhớ.
Quản lý bộ nhớ với những phân đọan cố định (tt)
Tất cả tiến trình được đặt trong một hàng đợi duy nhất. Khi có một phân vùng tự do , tiến trình đầu tiên trong hàng đợi có kích thước phù hợp sẽ được đặt vào phân vùng này và cho xử lý.
Nếu kích thước của tiến trình không vừa đúng bằng kích thước phân vùng chứa nó, phần bộ nhớ không sử dụng đến trong phân vùng sẽ bị lãng phí.
xảy ra hiện tượng phân mảnh nội vi.
Mức độ đa chương của hệ thống bị giới hạn bởi số lượng phân vùng
Vấn đề bảo vệ giữa các phân vùng: Để bảo vệ cần tổ chức hai thanh ghi : thanh ghi nền và thanh ghi giới hạn.
Khi tiến trình được tạo lập, nạp vào thanh ghi nền địa chỉ bắt đầu của phân vùng được cấp phát cho tiến trìnhvà nạp vào thanh ghi giới hạn kích thước của tiến trình
Sau đó mỗi đị chỉ bộ nhớ được phát sinh sẽ tự động được cộng với địa chỉ chứa trong thanh ghi nền để cho ra địa chỉ tuyệt đối trong bộ nhớ và các địa chỉ được đối chiếu với thanh ghi giới hạn để bảo đảm tiến trình không truy xuất ngoài phạm vi được cấp phát cho nó.
Quản lý bộ nhớ với những phân đọan động
Như tổ chức quản lý bộ nhớ trên gây ra lãng phí bộ nhớ vì vậy một phương pháp mới được đề xuất là cấp pháp cho tiến trình vùng nhớ vừa đủ kích thước của tiến trình.
Khi một tiến trình kết thúc vùng nhớ đã đã cấp cho nó sẽ được giải phóng và được cấp pháp cho tiến trình khác.
Với giải pháp này không còn hiện tượng phân mảnh nội vi nhưng lại xuất hiện phân mảng ngoại vi. Khi các tiến trình lần lượt vào ra khỏi hệ thống, dần dần xuất hiện các khe hở giữa các tiến trình có thể dẫn đến tình huống tổng vùng nhớ còn trống đủ để thỏa mãn yêu cầu nhưng các vùng nhớ này không liên tục.
Có thể áp dụng kỹ thuật dồn bộ nhớ để kết hợp các mảnh bộ nhớ rời rạc thành một vùng nhớ lớn liên tục.
Một vấn đề khác nảy sinh khi kích thước của tiến trình tăng trưởng trong quá trình xử lý mà không còn vùng nhớ còn trông gần kề để mở rộng vùng nhớ cho tiến trình.
Quản lý bộ nhớ với những phân đọan động (tt)
Quản lý các ô nhớ còn trống: Cần phải lưu trữ thông tin các ô nhớ cò trống để cấp phát cho các tiến trình, Có hai phương pháp chính: Bitmap và danh sách liên kết.
Phương pháp Bitmap:
Chia bộ nhớ thành từng đơn vị nhỏ (vài bytes) . Xây dựng bitmap, ứng với mỗi bit trong bitmap là một đơn vị bộ nhớ.
Bit được đánh dấu là 1 khi đơn vị bộ nhớ tương ứng đã được cấp phát
Bit được đánh dấu 0 khi đơn vị bộ nhớ tương ứng chưa được cấp phát.
Thao tác cấp phát bộ nhớ là : Giả sử tiến trình cần k đơn vị bộ nhớ, HĐH duyệt bitmap và tìm ra k bit liên tiếp bằng 0
Quản lý bộ nhớ với những phân đọan động
Quản lý bộ nhớ với những phân đọan động (tt)
Quản vùng nhớ còn trống bằng danh sách liên kết
Tổ chức một danh sách liên kết, mỗi phần tử tương ứng với một tiến trình hay lỗ hổng. Mỗi phần tử trong danh sách có 4 trường :
cờ biểu thị tiến trình (P) hay lỗ hổng (H)
Địa chỉ bắt đầu của vùng nhớ tương ứng
Kích thước của vùng nhớ
Con trỏ Next
Quản lý bộ nhớ với những phân đọan động (tt)
Thao tác cấp phát bộ nhớ
First Fit : Xác định lỗ hổng đầu tiên trong danh sách có kích thước đủ lớn để cấp phát cho tiến trình và lỗ hổng này được chia làm 2 phần : 1 phần cho tiến trình và phần kia là lỗ hổng mới.
Best Fit : xác định lỗ hổng bé nhất có kích thước đủ lớn để cấp phát cho tiến trình.
Worst Fit : Cấp phát phân đoạn tự do lớn nhất đủ lớn để cấp phát cho riến trình.
Có thể làm tăng tốc độ bcho cả 3 thuật toán trên bằng cách tổ chức 2 danh sách : 1 cho tiến trình và một cho lỗ hổng. Tuy nhiên lại làm chậm thao tác giải phóng bộ nhớ.
Quản lý bộ nhớ với những phân đọan động (tt)
Thao tác giải phóng bộ nhớ
Khi thực hiện thao tác giải phóng chú ý cần xem xét các trường hợp khác nhau của 2 phần tử kề nhau. Nhờ đó thực hiện thao tác kết hợp hai lỗ hổng kề nhau một cách phù hợp:
Trước giải phóng Sau giải phóng
Quản lý bộ nhớ với những phân đọan động (tt)
Quá trình Swapping
Trong hệ thống đa nhiệm nhiều người dùng thường là bộ nhớ không đủ chỗ để lưu trữ tất cả các tiến trình vì thế hệ thống dùng DSLK để lưu trữ tạm thời một số tiến trình nào đó chưa thật sự chạy, khi được cấp phát CPU thì hệ thống phải mang nó vào bộ nhớ chính . Việc di chuyển tiến trình từ bộ nhớ vào đĩa và ngược lại gọi là quá trình swapping.
Bộ nhớ ảo
Bộ nhớ ảo được đưa ra nhằm khắc phục tình trạng kích thước chương trình vượt quá kích thước bộ nhớ vật lý.
Hệ điều hành chia chương trình thành nhiều phần và giữa lại nhừng phần chương trình đang chạy hiện thời vừa đủ chứa trong bộ nhớ , phần còn lại lưu trữ trên đĩa. HĐH theo dõi và quản lý tất cả công việc swapping giữa đĩa và bộ nhớ . Dĩ nhiên bộ nhớ ảo vẫn có thể thiết kế cho hệ thống đa nhiệm.
Quản lý bộ nhớ với những phân đọan động (tt)
Sự phân trang (paging)
Hầu hết những hệ thống có sử dụng bộ nhớ ảo đều sử dụng kỹ thuật phâh trang. Địa chỉ ảo là địa chỉ tham khảo từ chương trình . Tập tất cả địa chỉ ảo gọi là vùng địa chỉ ảo, đối với những hệ thống không dùng bộ nhớ ảo , địa chỉ ảo cũng là địa chỉ vật lý.
Vùng địa chỉ ảo được chi thành nhiều trang (page) có kích thước bằng nhau tướng ứng với những khung trang (Page frame) trong bộ nhớ vật lý. Trang và khung trang luôn có kích thước bằng nhau.
Ví dụ: có 32K bộ nhớ vật lý chia thành 8 khung trang có kích thước 4K và 64K bộ nhớ ảo chia thành 16 trang kích thước 4K. Trong bất kỳ thời điểm nào chỉ có 8 trang từ bộ nhớ ảo ánh xạ vào bộ nhớ vật lý như sau:
Quản lý bộ nhớ với những phân đọan động
Quản lý bộ nhớ với những phân đọan động (tt)
Nếu lệnh nào đó trong chương trình tham khảo đến địa chỉ ảo không thuộc về bất kỳ trang nào đang được ánh xạ hiện thời gọi là lỗi trang. Trong trường hợp này HĐH tìm ra một khung trang nào ít sử dụng nhất trục xuất khỏi bộ nhớ và tìm kiếm trên đĩa trang nào chứa địa chỉ mà chương trình muốn tham khảo đến để chuyển vào bộ nhớ vật lý. Tiếp đến hệ thống cập nhật ánh xạ bộ nhớ cho trang mới.
Bảng trang
Hệ thống phải duy trì một bảng trang thể hiện ánh xạ từ bộ nhớ ảo vào bộ nhớ vật lý và chứa thông tin trang nào hiện thời đang dược ánh xạ.
Quản lý bộ nhớ với những phân đọan động (tt)
Quản lý bộ nhớ với những phân đọan động
Các thuật toán thay thế trang
Mỗi khi gặp lỗi trang HĐH phải chọn 1 trong các trang náo đó trục xuất ra khỏi bộ nhớ. Nếu nội dung trang đó bị thay đổi yhì phải ghi nội dung mới của trang lên đĩa. Vấn đề là chọn trang nào để trục xuất để giảm tổn phí.
Xét ví dụ một tiến trình truy xuất đến một dãy các trang sau:
7, 0,1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
giả sử có 3 khung trang và ban đầu cả 3 khung trang đều rỗng.
Quản lý bộ nhớ với những phân đọan động (tt)
Thuật toán FIFO
Ghi nhận thời điểm 1 trang được mang vào bộ nhớ chính khi cần thay thế trang , thì trang lâu nhất sẽ được chọn để trục xuất.
Với thuật toán này có thể có trang được chọn để thay thế có thể chứa nhiều dữ liệu cần thiết thường xuyên được nạp vào sớm , do vậy khi bị chuyển ra bộ nhớ phụ sẽ nhanh chóng gây ra lỗi trang.
Quản lý bộ nhớ với những phân đọan động (tt)
Thuật toán tối ưu
Thay thế trang sẽ lâu nhất được sử dụng trong tương lai
Thuật toán này bảo đảm lỗi trang là ít nhất tuy nhiên thuật toán này không khả thi vì không thể biết trước dãy các trang được truy xuất theo thứ tự.
Quản lý bộ nhớ với những phân đọan động (tt)
Thuật toán lâu nhất chưa sử dụng (LRU)
Với mỗi trang ghi nhận thời điểm cuối cùng trang được truy cập, trang được thay thế là trang lâu nhất chưa sử dụng.
Thuật toán đài hỏi một cơ chế xác định thứ tự các trang theo thời điểm truy xuất cuối cùng. Dùng stack
Cần tổ chức một stack lưu trữ số hiệu các trang
Mỗi khi thực hiện một truy xuất đến 1 trang , số hiệu của trang sẽ được xóa khỏi vị trí hiện hành trong stack và đưa lên đỉnh stack.
Trang ở đỉnh stack là trang được chọn để thay thế.
Quản lý bộ nhớ với những phân đọan động (tt)
Thuật toán Not Recently Used (NRU)
Thuật toán dựa trên sự tồn tại 2 bit gắn liền với mỗi trang để chỉ ra trang đó có vừa mới được tham khảo hay là được ghi lên hay không. Những bit này chứa trong bảng trang
Bit R =1: nếu trang đó truy cập ngược lại chưa được truy cập
Bit M =1 : Trang đó đã bị thay đổi ngược lại chưa bị thay đổi
Cứ mỗi lần truy cập bộ nhớ cần phải cập nhật lại các bit này
Khi một tiến trình bắt đầu cả 2 bit trong tất cả các trang được đặt bằng 0. theo một chu kỳ thời gian bit R được đặt lại bằng 0 để phân biệt những trang mới được truy cập với trang đã truy cập trước đó.
Khi xuất hiện một lỗi trang HĐH duyệt toàn bộ bảng trang và chia chúng thành 4 lớp dựa vào các bit R, M như sau:
Quản lý bộ nhớ với những phân đọan động (tt)
Class 0 : R=0, M=0
Class 1: R=0, M=1
Class 2: R=1, M=0
Class 3: R=1, M=1
Sau đó thuật toán chọn ra một trang để thay thế thuộc thuộc lớp thấp nhất khác rỗng.
* Một số tài liệu cũ có thể bị lỗi font khi hiển thị do dùng bộ mã không phải Unikey ...
Người chia sẻ: Mr Quân
Dung lượng: |
Lượt tài: 1
Loại file:
Nguồn : Chưa rõ
(Tài liệu chưa được thẩm định)