Bài giảng Hệ điều hành - Chương 6: Quản lý bộ nhớ

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ớ.Partition 3Partition 2Partition 1OSQuả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ùngVấ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ìnhSau đó 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 độngNhư 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átBit đượ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 0Quản lý bộ nhớ với những phân đọan độngABCD.1 1 1 1 1 1 0 0 01 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 11 1 1 1 1 1 0 0 0..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 ứngKích thước của vùng nhớ Con trỏ NextP05H53P85H132Quả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óngXBABABAXBAXXQuả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ớ ảoBộ 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 0-4K24-8K18-12K612-16K016-20K420-24K324-28KX28-32KX32-36KX36-40K540-44KX44-48K748-52KX52-56KX56-60KX60-64KX0-4K4-8K8-12K12-16K16-20K20-24K24-28K28-32KQuả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)001000000000010001010011110100011001011100000000000010110000111100000000000000000110000000000100110Quản lý bộ nhớ với những phân đọan độngCác thuật toán thay thế trangMỗ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, 1giả 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 FIFOGhi 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.70120304230321201701777222244400000007770000333222211111100111100033333222221***************Quản lý bộ nhớ với những phân đọan động (tt)Thuật toán tối ưuThay thế trang sẽ lâu nhất được sử dụng trong tương laiThuậ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ự.70120304230321201701777222222222222227770000004440000000000111333333331111111*********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 stackCần tổ chức một stack lưu trữ số hiệu các trangMỗ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ế.70120304230321201701777222244400011111110000000033333300000111333222222222777***********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 trangBit R =1: nếu trang đó truy cập ngược lại chưa được truy cậpBit M =1 : Trang đó đã bị thay đổi ngược lại chưa bị thay đổiCứ mỗi lần truy cập bộ nhớ cần phải cập nhật lại các bit nàyKhi 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=1Sau đó 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.