Giáo trình Hệ điều hành - Chương 5: Quản lý bộ nhớ - Khoa Công nghệ Thông tin - Trường ĐH Bách Khoa TP. HCM

Nội dung text: Giáo trình Hệ điều hành - Chương 5: Quản lý bộ nhớ - Khoa Công nghệ Thông tin - Trường ĐH Bách Khoa TP. HCM

1. 5.2 Quản lý bộ nhớ thật trên hệ đơn chương 0xFFFF 0xFFFF 0xFFFF Một số vấn đề cần giải quyết : HĐH Driver, I/O ƒ Tái định lại địa chỉ chương trình khi nạp fiel khả thi từ đĩa vào RAM. Application ƒ Bảo vệ bộ nhớ của Application HĐH từ việc truy xuất không hợp pháp của chương trình ứng dụng. Application ƒ Vấn đề không đủ chỗ cho chương trình lớn → sử dụng kỹ thuật HĐH Overlay để chia ứng HĐH dụng ra nhiều file 0 0 0 overlay liên tiếp. Môn : Hệ điều hành Khoa Công nghệ Thông tin Chương 5 : Quản lý bộ nhớ Trường ĐH Bách Khoa Tp.HCM Slide 3 5.2 Quản lý bộ nhớ thật trên hệ đơn chương //phần mềm viết bằng C //mã máy dịch được code int i; move ax, 5 mov [0], ax i = 5; nạp vào, static data chưa tái định 0 i //mã máy //mã máy move ax, 5 move ax, 5 mov [0], ax mov [0+base], ax base i base i HĐH HĐH Môn : Hệ điều hành Khoa Công nghệ Thông tin Chương 5 : Quản lý bộ nhớ Trường ĐH Bách Khoa Tp.HCM Slide 4 2
2. 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 Khoa Công nghệ Thông tin Chương 5 : Quản lý bộ nhớ Trường ĐH Bách Khoa Tp.HCM Slide 7 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 C CC C B BB B B A A A D D HĐH HĐH HĐHHĐH HĐH HĐH a. b. c. d. e. f. Môn : Hệ điều hành Khoa Công nghệ Thông tin Chương 5 : Quản lý bộ nhớ Trường ĐH Bách Khoa Tp.HCM Slide 8 4
3. 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. Môn : Hệ điều hành Khoa Công nghệ Thông tin Chương 5 : Quản lý bộ nhớ Trường ĐH Bách Khoa Tp.HCM Slide 11 Quản lý bộ nhớảo trên hệ đa chương Môn : Hệ điều hành Khoa Công nghệ Thông tin Chương 5 : Quản lý bộ nhớ Trường ĐH Bách Khoa Tp.HCM Slide 12 6
4. 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 Khoa Công nghệ Thông tin Chương 5 : Quản lý bộ nhớ Trường ĐH Bách Khoa Tp.HCM Slide 15 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. Môn : Hệ điều hành Khoa Công nghệ Thông tin Chương 5 : Quản lý bộ nhớ Trường ĐH Bách Khoa Tp.HCM Slide 16 8
5. 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. Môn : Hệ điều hành Khoa Công nghệ Thông tin Chương 5 : Quản lý bộ nhớ Trường ĐH Bách Khoa Tp.HCM 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. Môn : Hệ điều hành Khoa Công nghệ Thông tin Chương 5 : Quản lý bộ nhớ Trường ĐH Bách Khoa Tp.HCM Slide 20 10
6. Các phương pháp giải phóng trang thật 4. Phương pháp “Not Recently-Used” - NRU : Để giải phóng trang ít gây phiền hà hơn, ta sẽ kết hợp mỗi trang thật 1 bit trạng thái nữa. Cụ thể ta có 2 bit miêu tả trạng thái của từng trang thật như sau : ƒ 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. ƒ bit M = 0/1(Modified). Mỗi lần nạp trang ảo, bit M của trang thật được xóa 0. Mỗi lần bị thay đổi nội dung, bit M được set lên 1. Như vậy mỗi trang sẽở1 trong 1 trạng thái sau : 1. S0 : R = M = 0 : trong quá khứ gần, trang chưa được truy xuất và trang chưa bị thay đổi nội dung. 2. S1 : R = 0, M = 1 : trong quá khứ gần, trang chưa được truy xuất nhưng trang đã bị thay đổi nội dung. 3. S2 : R = 1, M = 0 : trong quá khứ gần, trang được truy xuất, nhưng trang chưa bị thay đổi nội dung. 4. S3 : R = 1, M = 1 : trong quá khứ gần, trang được truy xuất và trang đã bị thay đổi nội dung. Khi cần giải phóng trang, ta chọn trang theo thứ tự ưu tiên từ S0 -> S3. Môn : Hệ điều hành Khoa Công nghệ Thông tin Chương 5 : Quản lý bộ nhớ Trường ĐH Bách Khoa Tp.HCM Slide 23 Các phương pháp giải phóng trang thật Trong phương pháp NRU ở slide trước, nếu có nhiều trang S0 thì ta phải dùng cơ chế ngẫu nhiên để chọn 1 trong các trang đó chưa chính xác lắm. Để khắc phục ngược điểm này, ta dùng phương pháp sau : 5. Phương pháp “Least Recently-Used” - LRU : kết hợp mỗi trang 1 vùng thông tin miêu tả mộc thời gian. Mỗi lần trang được truy xuất, ta ghi thời điểm truy xuất vào mộc thời gian của trang. Mỗi khi cần giải phóng trang, ta chọn trang có mộc thời gian nhỏ nhất (trang được truy xuất lần cuối lâu nhất). Môn : Hệ điều hành Khoa Công nghệ Thông tin Chương 5 : Quản lý bộ nhớ Trường ĐH Bách Khoa Tp.HCM Slide 24 12
7. Tối ưu hóa qui trình đổi địa chỉảo sang thật nằm trong RAM Môn : Hệ điều hành Khoa Công nghệ Thông tin Chương 5 : Quản lý bộ nhớ Trường ĐH Bách Khoa Tp.HCM Slide 27 Tối ưu hóa qui trình đổi địa chỉảo sang thật Để khắc phục nhược điểm 2 trong slide trước, thay vì dùng giải pháp phần mềm để đổi địa chỉ, ta dùng phương pháp phần cứng dựa vào bộ nhớ kết hợp : địa chỉảo cần truy xuất nằm trong thanh ghi địa chỉ của CPU i Offset Comparator g z Comparator h y Comparator i j j Offset Comparator p l Comparator q m Working set của bảng đặc tả Comparator s n trang Toàn bộ các mạch điện tử trên đều là mạch tổ hợp nên thời gian đổi địa chỉảo sang thật hầu như = 0, quá tốt! Môn : Hệ điều hành Khoa Công nghệ Thông tin Chương 5 : Quản lý bộ nhớ Trường ĐH Bách Khoa Tp.HCM Slide 28 14
8. 5.5 Quản lý bộ nhớảo phân đoạn Nguyên lý hoạt động : ƒ khi lập trình, chương trình được phép truy xuất dữ liệu trong nhiều không gian khác nhau, mỗi không gian được gọi là segment. Mỗi segment có kích thước thay đổi được theo thời gian, ô nhớ đầu tiên của mỗi segment luôn bắt đầu từ 0. ƒ Bộ nhớ RAM có kích thước nhỏ nào đó. Các segment của chương trình thường nắm trên đĩa cứng, khi cần thiết segment sẽ được nạp vào 1 vùng thích hợp trong RAM. ƒ Tại từng thời điểm, 1 vùng nhớ RAM thật chứa tốt đa 1 segment ảo, nhưng theo thời gian nó có thể chứa nhiều segment ảo khác nhau. ƒ Khi ứng dụng truy xuất 1 ô nhớ, nó xác định địa chỉ ô nhớ dạng phân cấp : segment + offset. Môn : Hệ điều hành Khoa Công nghệ Thông tin Chương 5 : Quản lý bộ nhớ Trường ĐH Bách Khoa Tp.HCM Slide 31 Quản lý bộ nhớảo phân đoạn Nguyên lý hoạt động (tt) : ƒ Để quản lý quá trình ánh xạ các segement ảo của chương trình vào các vùng RAM, HĐH dùng 1 bảng đặc tả sgement cho mỗi chương trình, bảng này có số phần tử = số segement 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ý segement tương ứng : Protection Modified Address in disk địa chỉ thật trong RAM (start_addr) inRAM Môn : Hệ điều hành Khoa Công nghệ Thông tin Chương 5 : Quản lý bộ nhớ Trường ĐH Bách Khoa Tp.HCM Slide 32 16
9. 5.6 Quản lý bộ nhớảo phân đoạn và phân trang Qui trình đổi địa chỉảo sang địa chỉ thật ở slide trước có khuyết điểm trong trường hợp quản lý segemnt có kích thước lớn : ta khó/không tìm được vùng RAM trống chứa nó. Vì lý do này, trong thực tế, người ta phải kết hợp 2 phương pháp quản lý phân trang và phân đoạn lại, đây là phương pháp mạnh nhất hiện nay. ý tưởng là hệ thống sẽ quản lý mỗi segment phần mềm như là 1 không gian ảo gồm nhiều trang ảo, mỗi lần chương trình truy xuất ô nhớ nằm trong trang ảo nào của segment nào, hệ thống sẽ tìm cách nạp nó vào RAM. Môn : Hệ điều hành Khoa Công nghệ Thông tin Chương 5 : Quản lý bộ nhớ Trường ĐH Bách Khoa Tp.HCM Slide 35 Quản lý bộ nhớảo phân đoạn và 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 gồm 2 thành phần : segement (s) và offset, hệ thống sẽ tách offset ra thành 2 thành phần page (p) + offset1. 2. Truy xuất record quản lý segement s trong bảng đặc tả segement. Nếu field inRAM=1 thì bản đặc tả trang cho segement s đã có trong RAM. Nếu không thì tìm cách nạp nó vào RAM. 3. Truy xuất record quản lý trang ảo p 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. 4. 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. 5. Hiệu chỉnh lại field inRAM = 1 và field page frame = k rồi quay lại bước 3. Môn : Hệ điều hành Khoa Công nghệ Thông tin Chương 5 : Quản lý bộ nhớ Trường ĐH Bách Khoa Tp.HCM Slide 36 18
10. Quản lý bộ nhớ Real mode Nguyên lý hoạt động : ƒ không gian bộ nhớ của chương trình là 1 tập các segment, ƒ mỗi địa chỉ truy xuất được xác định bởi chương trình gồm 2 tham số : chỉ số segment + offset, mỗi tham số dài 16 bit. Ở góc nhìn lập trình, mỗi phần mềm có 216 segment, mỗi segment có 216 byte → mỗi chương trình dài maximum 4GB! ƒ Thường thì chương trình sẽ truy xuất tuần tự các ô nhớ nên tham số segment sẽ được chứa vào 1 trong các thanh ghi segment (CS, DS, ES, SS), mỗi lệnh máy chỉ cần miêu tả offset của ô nhớ cần truy xuất. ƒ Máy sẽ đổi địa chỉảo sang địa chỉ thật theo công thức sau : physical address = segment * 16 + offset, Môn : Hệ điều hành Khoa Công nghệ Thông tin Chương 5 : Quản lý bộ nhớ Trường ĐH Bách Khoa Tp.HCM Slide 39 Quản lý bộ nhớ Real mode Nguyên lý hoạt động (tt) : ƒ bit A20 của kết quả hoặc bị bỏ đi (trong chế độ A20 disable), hoặc được giữ lại và dùng (trong chế độ A20 enable). Chế độ A20 được thiết lập trong ROM BIOS. ƒ Theo cách đổi địa chỉảo như trên, ta thấy các segment phần mềm khác nhau có thể giao nhau, độ lệch tối thiểu của 2 segment là 16 ô nhớ (1 paragraph). ƒ Thí dụ các ô nhớ 0:80H ≡1:70H ≡ 2:60H ≡ 3:50H ≡ 4:40H ≡ 5:30H 6:20H ≡ 7:10H ≡ 8:0H đều chiếm cùng 1 ô nhớ RAM. ƒ không gian RAM mà chương trình truy xuất được thực tế là 1MB (A20 disable) hay 1MB + 65520 B (A20 enable). Ta gọi phần trên 1MB là HIGH MEMORY. Môn : Hệ điều hành Khoa Công nghệ Thông tin Chương 5 : Quản lý bộ nhớ Trường ĐH Bách Khoa Tp.HCM Slide 40 20
11. Cấu trúc record quản lý segment của Intel ƒ Base0-31 : địa chỉ RAM chứa segment Limit 0-7 ƒ Limit0-19 : độ lớn segment (đơn vị tính là byte/page) Limit 8-15 ƒ D = 0 : Limit tính theo byte / D = 1 : Base 0-7 tính theo page 4KB ƒ G = 0 : segment 16-bit / G = 1 : Base 8-15 segment 32-bit Base 16-23 ƒ P = 0 : segment chưa nạp vào RAM / P P DPL S Type = 1 : nạp vào RAM rồi ƒ S = 0 : System / S = 1 : Application G D Limit 16-19 ƒ DPL : mức độ phân quyền từ 0 - 3 Base 24-31 ƒ Type : kiểu segment và bảo vệ segment Môn : Hệ điều hành Khoa Công nghệ Thông tin Chương 5 : Quản lý bộ nhớ Trường ĐH Bách Khoa Tp.HCM Slide 43 Qui trình đổi địa chỉảo sang địa chỉ thật Địa chỉ luận lý có dạng segment:Offset, địa chỉ thật tương ứng là địa chỉ 32 bit, kết quả của phép cộng số học trong hình sau : Môn : Hệ điều hành Khoa Công nghệ Thông tin Chương 5 : Quản lý bộ nhớ Trường ĐH Bách Khoa Tp.HCM Slide 44 22
12. Cấu trúc record quản lý segment của Intel ƒ Base0-31 : địa chỉ RAM chứa segment Limit 0-7 ƒ Limit0-19 : độ lớn segment (đơn vị tính là byte/page) Limit 8-15 ƒ D = 0 : Limit tính theo byte / D = 1 : Base 0-7 tính theo page 4KB ƒ G = 0 : segment 16-bit / G = 1 : Base 8-15 segment 32-bit Base 16-23 ƒ P = 0 : segment chưa nạp vào RAM / P P DPL S Type = 1 : nạp vào RAM rồi ƒ S = 0 : System / S = 1 : Application G D Limit 16-19 ƒ DPL : mức độ phân quyền từ 0 - 3 Base 24-31 ƒ Type : kiểu segment và bảo vệ segment Môn : Hệ điều hành Khoa Công nghệ Thông tin Chương 5 : Quản lý bộ nhớ Trường ĐH Bách Khoa Tp.HCM Slide 47 Qui trình đổi địa chỉảo sang địa chỉ thật Địa chỉ luận lý có dạng segment:Offset, địa chỉảo tương ứng là địa chỉ 32 bit, kết quả của phép cộng số học trong hình sau : Môn : Hệ điều hành Khoa Công nghệ Thông tin Chương 5 : Quản lý bộ nhớ Trường ĐH Bách Khoa Tp.HCM Slide 48 24