Nội dung

MÔN HỆ ĐIỀU HÀNH Chương 5 QUẢN LÝ BỘ NHỚ 5.1 Tổng quát về quản lý bộ nhớ 5.2 Quản lý bộ nhớ thật 5.3 Quản lý bộ nhớ ảo 5.4 Quản lý bộ nhớ ảo phân trang 5.5 Quản lý bộ nhớ ảo phân đoạn 5.6 Quản lý bộ nhớ ảo phân đoạn và phân trang 5.7 Quản lý bộ nhớ của CPU Intel 80x86 Tài liệu tham khảo : chương 4, sách "Modern Operating Systems", Andrew S. Tanenbaum: , 2nd ed, Prentice Hall Khoa Công nghệ Thông tin Trường ĐH Bách Khoa Tp.HCM Môn : Hệ điều hành Chương 5 : Quản lý bộ nhớ Slide 1 5.1 Tổng quát về quản lý bộ nhớ ‰ ‰ ‰ Thường người lập trình muốn bộ nhớ mà chương trình truy xuất được có các tính chất : ƒ dung lượng lớn ƒ chạy nhanh ƒ không bị mất thông tin. Thường máy tính sử dụng 3 loại bộ nhớ : ƒ Cache : giá cao, dung lượng hạn chế, tốc độ cao ƒ bộ nhớ chính DRAM : dung lượng trung bình, giá trung bình, tốc độ trung bình. ƒ đĩa cứng : dung lượng rất lớn, chậm, giá rẻ. Module quản lý bộ nhớ phải tận dụng các ưu/khuyết điểm của các loại bộ nhớ máy tính để cung cấp cho người lập trình không gian làm việc thoả mãn càng nhiều yêu cầu càng tốt. Khoa Công nghệ Thông tin Trường ĐH Bách Khoa Tp.HCM Môn : Hệ điều hành Chương 5 : Quản lý bộ nhớ Slide 2 1 5.2 Quản lý bộ nhớ thật trên hệ đơn chương 0xFFFF.. 0xFFFF.. 0xFFFF.. Driver, I/O HĐH Application Application Application HĐH HĐH 0 0 0 Một số vấn đề cần giải quyết : ƒ Tái định lại địa chỉ chương trình khi nạp fiel khả thi từ đĩa vào RAM. ƒ Bảo vệ bộ nhớ của HĐH từ việc truy xuất không hợp pháp của chương trình ứng dụng. ƒ Vấn đề không đủ chỗ cho chương trình lớn → sử dụng kỹ thuật Overlay để chia ứng dụng ra nhiều file overlay liên tiếp. Môn : Hệ điều hành Chương 5 : Quản lý bộ nhớ Slide 3 Khoa Công nghệ Thông tin Trường ĐH Bách Khoa Tp.HCM 5.2 Quản lý bộ nhớ thật trên hệ đơn chương //phần mềm viết bằng C int i; ... i = 5; nạp vào, chưa tái định base //mã máy move ax, 5 mov [0], ax ... i HĐH Khoa Công nghệ Thông tin Trường ĐH Bách Khoa Tp.HCM //mã máy dịch được move ax, 5 mov [0], ax ... 0 i base code static data //mã máy move ax, 5 mov [0+base], ax ... i HĐH Môn : Hệ điều hành Chương 5 : Quản lý bộ nhớ Slide 4 2 5.3 Quản lý bộ nhớ thật trên hệ đa chương Khoa Công nghệ Thông tin Trường ĐH Bách Khoa Tp.HCM Môn : Hệ điều hành Chương 5 : Quản lý bộ nhớ Slide 5 5.3 Quản lý bộ nhớ thật trên hệ đa chương Trong bối cảnh máy có dung lượng RAM khá lớn (512KB), còn các phần mềm cần chạy có kích thước khá nhỏ (10-100KB), ta có thể dùng 1 trong 3 kỹ thuật quản lý bộ nhớ : 1. Kỹ thuật phân vùng tĩnh dùng nhiều hàng chờ độc lập (hình a slide trước) : ƒ HĐH được load vào vùng bộ nhớ thấp của RAM. ƒ phần trống còn lại của RAM sẽ được chia làm nhiều phân vùng có kích thước tăng dần (10, 20, 40, 80, 160KB,...). ƒ mỗi phân vùng có 1 hàng chờ các ứng dụng cần chạy trên phân vùng tương ứng. ƒ khi cần chạy ứng dụng, người chạy ứng dụng phải chọn phân vùng có kích thước nhỏ nhất nhưng >= kích thước ứng dụng và sắp hàng ở hàng chờ tương ứng. ƒ HĐH sẽ phục vụ các ứng dụng trong từng hàng chờ theo thứ tự ai đến trước phục vụ trước. Khoa Công nghệ Thông tin Trường ĐH Bách Khoa Tp.HCM Môn : Hệ điều hành Chương 5 : Quản lý bộ nhớ Slide 6 3 Quản lý bộ nhớ thật trên hệ đa chương Kỹ thuật dùng nhiều hàng chờ độc lập có 2 khuyết điểm chính : 1. Kích thước các phân vùng tĩnh thường không khớp với kích thước ứng dụng nên bị lãng phí. 2. sử dụng các phân vùng thường không đều gây ra lãng phí : nhiều phần mềm sắp hàng chạy trên phân vùng kích thước nhỏ, trong lúc phân vùng kích thước lớn không có ứng dụng chạy. Để khắc phục khuyết điểm 2 ở trên, ta có thể dùng kỹ thuật sau : 2. Kỹ thuật phân vùng tĩnh dùng 1 hàng chờ duy nhất (hình b slide trước) : ƒ HĐH được load vào vùng bộ nhớ thấp của RAM. ƒ phần trống còn lại của RAM sẽ được chia làm nhiều phân vùng có kích thước tăng dần (10, 20, 40, 80, 160KB,...). ƒ chỉ có 1 hàng chờ các ứng dụng cần chạy trên các phân vùng. ƒ khi 1 phân vùng rãnh, HĐH sẽ dò trong hàng chờ 1 ứng dụng có kích thước lớn nhất nhưng <= kích thước phân vùng và cho phép ứng dụng này chạy. Môn : Hệ điều hành Chương 5 : Quản lý bộ nhớ Slide 7 Khoa Công nghệ Thông tin Trường ĐH Bách Khoa Tp.HCM Quản lý bộ nhớ thật trên hệ đa chương Để khắc phục khuyết điểm 1 ở silde trước, ta có thể dùng kỹ thuật sau : 3. Kỹ thuật phân vùng động : E B C C C B B B C B A A A HĐH HĐH HĐH a. b. c. Khoa Công nghệ Thông tin Trường ĐH Bách Khoa Tp.HCM D D HĐH HĐH HĐH d. e. f. Môn : Hệ điều hành Chương 5 : Quản lý bộ nhớ Slide 8 4 Quản lý bộ nhớ thật trên hệ đa chương 3. Kỹ thuật phân vùng động : a. HĐH được load vào vùng bộ nhớ thấp của RAM. Khi ứng dụng A cần chạy, HĐH tạo phần vùng động vừa đúng kích thước của phần mềm A và nạp A vào phân vùng vừa tạo. Phân bộ nhớ trống còn lại để dành cho các phần mềm khác sau này. b. tương tự tạo phân vùng cho B chạy. c. tương tự tạo phân vùng cho C chạy. d. A kết thúc và trả lại phân vùng mình đã chiếm. e. khi D chạy, HĐH tạo phần vùng động vừa đúng kích thước cho D. f. khi E chạy, HĐH không tìm được vùng trống nào đủ lớn cho E cả. Trong trường hợp này, HĐH sẽ dời các phân vùng đang dùng bởi các ứng dụng lại kề nhau để tạo phân vùng trống duy nhất. Nếu kích thước của nó đủ chạy cho E thì sẽ tạo phân vùng động cho E chạy. Khoa Công nghệ Thông tin Trường ĐH Bách Khoa Tp.HCM Môn : Hệ điều hành Chương 5 : Quản lý bộ nhớ Slide 9 5.3 Quản lý bộ nhớ ảo trên hệ đa chương Tất cả các phương pháp quản lý bộ nhớ đã trình bày trước đây đều có nhược điểm là dựa vào ý tưởng : nạp toàn bộ file phần mềm vào bộ nhớ trước khi chạy ứng dụng tương ứng. Trong bối cảnh sử dụng máy hiện nay, máy chỉ có RAM kích thước vừa phải (<=4GB), nhưng phải chạy đồng thời nhiều ứng dụng, mỗi ứng dụng lại có nhu cầu bộ nhớ rất lớn, nhiều khi lớn hơn cả kích thước của RAM. Như vậy, các phương pháp trước đây đều thất bại không giải quyết nổi yêu cầu mới này. Người ta đã tìm được phương pháp quản lý bộ nhớ đáp ứng được yêu cầu mới, đó là phương pháp quản lý bộ nhớ ảo. Ý tưởng nền tảng của phương pháp này là : không cần nạp hết chương trình vào bộ nhớ trước khi chạy mà khi ứng dụng chạy tới lệnh nào và truy xuất dữ liệu nào thì HĐH mới nạp phần chương trình chứa lệnh và dữ liệu cần chạy, sau đó khi cần thì giải phóng vùng nhớ để chứa phần code và dữ liệu khác. Khoa Công nghệ Thông tin Trường ĐH Bách Khoa Tp.HCM Môn : Hệ điều hành Chương 5 : Quản lý bộ nhớ Slide 10 5 5.3 Quản lý bộ nhớ ảo trên hệ đa chương Có 3 phương pháp quản lý bộ nhớ ảo khác nhau : ƒ Quản lý bộ nhớ phân trang (Paging) ƒ Quản lý bộ nhớ phân đoạn (Segmentation) ƒ Quản lý bộ nhớ phân đoạn và phân trang (Segmentation & Paging) Để đạt được tốc độ cần thiết, người ta phải hiện thực các phương pháp quản lý bộ nhớ ảo bằng phần cứng. Đơn vị phần cứng quản lý bộ nhớ ảo được gọi là MMU (Memory Management Unit). Đơn vị MMU thường trong trong CPU. Khoa Công nghệ Thông tin Trường ĐH Bách Khoa Tp.HCM Môn : Hệ điều hành Chương 5 : Quản lý bộ nhớ Slide 11 Quản lý bộ nhớ ảo trên hệ đa chương Khoa Công nghệ Thông tin Trường ĐH Bách Khoa Tp.HCM Môn : Hệ điều hành Chương 5 : Quản lý bộ nhớ Slide 12 6 5.4 Quản lý bộ nhớ ảo phân trang Nguyên lý hoạt động : ƒ khi lập trình, các lệnh truy xuất các địa chỉ trong không gian phẳng có dùng lượng rất lớn (4GB). Không gian này được gọi là luận lý (ảo). Nếu phần mềm hạn chế truy xuất trong không gian này thì HĐH sẽ đảm bảo nó chạy tốt cho dù kích thước thật của RAM nhỏ hơn nhiều. ƒ Để quản lý việc swap (nạp vào/ghi ra) bộ nhớ ảo, HĐH chia bộ nhớ ảo của ứng dụng ra thành nhiều đơn vị quản lý có kích thước đồng nhất, mỗi đơn vị được gọi là trang ảo. Kích thước trang ảo = 2i (256, 512, 1K, 2K, 4K, 8K,...). ƒ Bộ nhớ RAM cũng được chia thành nhiều đơn vị quản lý, mỗi đơn vị được gọi là trang thật (page frame). Kích thước thật = kích thước trang ảo. Môn : Hệ điều hành Chương 5 : Quản lý bộ nhớ Slide 13 Khoa Công nghệ Thông tin Trường ĐH Bách Khoa Tp.HCM Quản lý bộ nhớ ảo phân trang Nguyên lý hoạt động (tt) : ƒ Trang thật là nơi chứa trang ảo khi cần thiết, tại từng thời điểm, mỗi trang thật chứa tốt đa 1 trang ảo, nhưng theo thời gian nó có thể chứa nhiều trang ảo khác nhau. ƒ Khi ứng dụng truy xuất 1 ô nhớ theo địa chỉ tuyến tính số nguyên, HĐH biết ngay ô nhớ đó thuộc trang ảo nào, nằm ở Offset nào trong trang ảo. ƒ ô ở địa chỉ 8196 = 0010 0000 0000 0100 phần còn lại bên trái là chỉ số trang ảo (=2) Khoa Công nghệ Thông tin Trường ĐH Bách Khoa Tp.HCM i bit bên phải là offset của ô nhớ (=4) Môn : Hệ điều hành Chương 5 : Quản lý bộ nhớ Slide 14 7 Quản lý bộ nhớ ảo phân trang Nguyên lý hoạt động (tt) : ƒ Để quản lý quá trình ánh xạ các trang ảo của chương trình vào các trang thật, HĐH dùng 1 bảng đặc tả trang ảo cho mỗi chương trình, bảng này có số phần tử = số trang ảo của chương trình tương ứng, mỗi phần tử của bảng là 1 record chứa các thông số quản lý trang ảo tương ứng : Protection Modified Address in disk Chỉ số trang thật (page frame) inRAM Môn : Hệ điều hành Chương 5 : Quản lý bộ nhớ Slide 15 Khoa Công nghệ Thông tin Trường ĐH Bách Khoa Tp.HCM Quản lý bộ nhớ ảo phân trang Qui trình đổi địa chỉ ảo sang địa chỉ thật : 1. từ địa chỉ mà chương trình truy xuất (addr), hệ thống tách thành 2 thành phần : page (i) và offset. 2. Truy xuất record quản lý trang ảo i trong bảng đặc tả trang. Nếu field inRAM=1 thì địa chỉ thật tương ứng là : page frame Offset và qui trình kết thúc. 3. Nếu inRAM =0, hệ thống sẽ tìm 1 trang thật rãnh (k), nếu không có phải tìm cách giải phóng 1 trang thật ít gây phiền hà nhất (k), dựa vào thông tin trong field "inDisk" để mở file và đọc trang ảo vào trang thật k. 4. Hiệu chỉnh lại field inRAM = 1 và field page frame = k rồi quay lại bước 2. Khoa Công nghệ Thông tin Trường ĐH Bách Khoa Tp.HCM Môn : Hệ điều hành Chương 5 : Quản lý bộ nhớ Slide 16 8 Quản lý bộ nhớ ảo phân trang Thí dụ về trạng thái hệ thống, RAM có 32KB được chia làm 8 trang thật chỉ số từ 0 -7, mỗi trang 4KB. Chương trình dài 64KB được chia làm 16 trảng ảo, chỉ số từ 0 -15. Hiện có 8 trang ảo được nạp vào và chiếm hết RAM. Khoa Công nghệ Thông tin Trường ĐH Bách Khoa Tp.HCM Môn : Hệ điều hành Chương 5 : Quản lý bộ nhớ Slide 17 Quản lý bộ nhớ ảo phân trang Thí dụ về bảng đặc tả trang và qui trình đỗi địa chỉ ảo sang địa chỉ thật. Theo hình bên, phần mềm truy xuất ô nhớ ảo ở địa chỉ 8196 thì máy truy xuất RAm ở địa chỉ 24580. Khoa Công nghệ Thông tin Trường ĐH Bách Khoa Tp.HCM Môn : Hệ điều hành Chương 5 : Quản lý bộ nhớ Slide 18 9 Các phương pháp giải phóng trang thật Trong qui trình đổi địa chỉ ảo sang địa chỉ thật ở các slide trước, ta thấy mỗi khi cần nạp trang ảo mới, máy sẽ tìm trang thật trống, nhưng ít khi tìm được, do đó máy sẽ phải tìm 1 trang thật đang dùng nào đó và giải phóng nó. Có nhiều phương pháp giải phóng trang thật khác nhau, mỗi phương pháp có giá/kết quả khác nhau, tùy thuộc vào mục tiêu xây dựng HĐH cụ thể, ta có thể chọn 1 trong các phương pháp này hay kết hợp chúng lại. 1. Phương pháp FIFO : dùng 1 danh sách liên kết chứa các trang thật được dùng, trang nào được dùng mới nhất sẽ được đưa vào cuối danh sách → đầu danh sách là trang được dùng cũ nhất → chọn nó để giải phóng khi cần. Khoa Công nghệ Thông tin Trường ĐH Bách Khoa Tp.HCM Môn : Hệ điều hành Chương 5 : Quản lý bộ nhớ Slide 19 Các phương pháp giải phóng trang thật Phương pháp FIFO có nhược điểm là thường giải phóng nhằm các trang chứa HĐH (vì các module chức năng của HĐH được nạp vào RAM đầu tiên). Để khắc phục nhược điểm này, ta có thể dùng phương pháp sau : 2. Phương pháp cho cơ hội lần 2 : kết hợp mỗi trang thật 1 bit trạng thái, bit R = 0/1 (Recent). Định kỳ bit R của các trang sẽ bí xóa về 0, mỗi khi trang bị truy xuất thì set R = 1. Khi cần giải phóng trang, chọn phần tử đầu danh sách. Nếu bit R = 0 thì giải phóng nó, còn nếu R = 1 thì set lại R=0, tha nó và đưa nó về đuôi danh sách để xử lý sau. Như vậy, với phương pháp này, ta chỉ giải phóng trang được dùng cũ nhất và không được truy xuất lại trong quá khứ gần đây. Khoa Công nghệ Thông tin Trường ĐH Bách Khoa Tp.HCM Môn : Hệ điều hành Chương 5 : Quản lý bộ nhớ Slide 20 10