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

1 Chương 3 – QUẢN LÝ BỘ NHỚ • Bộ nhớ tác động nhiều lên độ phức tạp của giải thuật, • Phải giải quyết 2 v/đ trái ngược nhau: • Tiết kiệm bộ nhớ, • Tận dụng tối đa bộ nhớ cho phép. • Phần lớn các chương trình: viết trên ngôn ngữ lập trình: Assembler, VB, JAVA, VC++, . . . • Với người lập trình: CT và thực hiên CT là ánh xạ từ tên sang giá trị. 2 QUẢN LÝ BỘ NHỚ • Với hệ thống: Tên biến Giá trị Địa chỉ Quản lý bộ nhớ Quản lý tiến trình Quản lý Processor 3 $1 – CÁC BƯỚC XỬ LÝ CT • I + J • A + B • A + I CT Tên user’s Tên trong Mô đun đích Hàm tên Hàm địa chỉ .OBJ Lý thuyết chương trình dịch Ph.tích cú pháp + ph. tích ngữ nghĩa + Sinh mã + Tối ưu hoá 4 CÁC BƯỚC XỬ LÝ CT • Vai trò của Biên tập (Input/Output), • Khái niệm bộ nhớ lô gíc. Mô đun đích Mô đun thực hiện CT thực hiện Thực hiện KQ Biên tập (Link) Nạp và định vị (Fetch) Quản lý bộ nhớ QL Tiến trình QL Processor .COM .EXE 5 CÁC BƯỚC XỬ LÝ CT Khô ng tên gian Tê n us er ’s Hàm tên Tên trong Bộ nhớ Lô gíc H àm đ ịa c hỉ M od ul đ íc h M od ul th ực hi ện LIN K A FE TC H Bộ nhớ vật lý Chương trình thực hiện Tổ chức bộ nhớ lô gíc? Tổ chức bộ nhớ vật lý? Xác lập quan hệ: Như thế nào? Khi nào? 6 $2 – CẤU TRÚC CHƯƠNG TRÌNH • Bộ nhớ lô gíc: – Không gắn với máy tính cụ thể, – Không giới hạn về kích thước, – Chỉ chứa 1 mô đun hoặc 1 CT, – Chỉ phục vụ lưu trữ, không thực hiện. • Quản lý bộ nhớ lô gíc ~ tổ chức chương trình, • Mỗi cách tổ chức CT  cấu trúc CT, • Mọi cấu trúc: đều được sử dụng trong thực tế. 7 CẤU TRÚC CHƯƠNG TRÌNH • Đặc trưng mô đun đích (Object Modul): chứa thông tin về các moduls khác liên quan (các móc nối)  kích thước lớn. • Nhiệm vụ biên tập (Linked): Giải quyết các móc nối. • Các loại cấu trúc chính: – Cấu trúc tuyến tính, – Cấu trúc động (Dynamic Structure), – Cấu trúc Overlay, – Cấu trúc mô đun, – Cấu trúc phân trang. • Một chương trình thực hiện có thể chứa nhiều cấu trúc khác nhau. 8 CẤU TRÚC CHƯƠNG TRÌNH • A) Cấu trúc tuyến tính: CT biên tập tìm và lắp ráp các mô đun thành một mô đun duy nhất, chứa đầy đủ thông tin để thực hiện CT, m0 m1 m2 . . . . . . mn l 9 Cấu trúc tuyến tính • Đặc điểm: – Đơn giản, – Thời gian thực hiện: min, – Lưu động (mobilable) cao, – Tốn bộ nhớ: với mỗi bộ dữ liệu chỉ có 13% - 17% câu lệnh đóng vai trò tích cực. – Không dùng chung mô đun CT. 10 B) CẤU TRÚC ĐỘNG • Trong CT nguồn: phải dùng các lệnh macro hệ thống để nạp, móc nối, xoá (Load, Attach, Delete) . . . các mô đun khi cần thiết, m0 m0 m0 m0 m0 m2 m2 m2 m1 11 CẤU TRÚC ĐỘNG • Đặc điểm: – Đòi hỏi user phải biết cơ chế và công cụ quản lý bộ nhớ, – Thời gian thực hiện lớn: song song thực hiện với tìm kiếm, nạp và định vị, – Tiết kiệm bộ nhớ, – Kém lưu động  khó nạp, cập nhật, xoá. • Được sử dụng rộng rãi những năm 60-70 và từ 90 đến nay. • Thích hợp cho các CT hệ thống. 12 CẤU TRÚC ĐỘNG • Các mô đun nạp trong quá trình thực hiện  vào các files .DLL ( dynamic Link Library) • WIDOWS 98, WINDOWS XP – thư mục SYSTEM, SYSTEM32, • Biên bản cài đặt, uninstall. • Winword, Excel, Vietkey . . . • Các ngôn ngữ lập trình:  công cụ tổ chức DLL. m0 m0 m0 m0 m0 m2 m2 m2 m1 .DLL 13 C) CẤU TRÚC OVERLAY • Moduls  các lớp, lớp = {các moduls không tồn tại đồng thời} • Moduls lớp i được gọi bởi moduls lớp i-1, • Thông tin về các lớp: Sơ đồ tổ chức overlay, do user cung cấp cho Link, • Link tạo sơ đồ quản lý overlay, • Supervisor Overlay tổ chức thực hiện. • Đặc điểm: – Phân phối bộ nhớ theo sơ đồ tĩnh, – Files .OVL • Ví dụ: FOXPRO, PCSHELL. . . . 14 80 KB 100 KB 60 KB 110 KB 80 KB 100 KB 90 KB 80 KB 60 KB 60 KB 40 KB 110 KB 40 KB 70 KB Moduls mức 1 Moduls mức 2 Moduls mức 3 MỨC 0 MỨC 1 MỨC 2 MỨC 3 RAM Tổng cộng: 270 KB 730 KB .OVL 15 D) CẤU TRÚC MODULS • Biên tập riêng từng mô đun, • Tạo bảng quản lý mô đun để điều khiển thực hiện, • Đặc điểm: – Tự động hoàn toàn, – Không cần phân phối bộ nhớ liên tục, – Hiệu quả phụ thuộc vào cấu trúc ban đầu của CT nguồn, – Dễ dàng sử dụng chung mô đun. m0 m1 m2 m3 m0 m1 RAM 16 E) CẤU TRÚC PHÂN TRANG • CT biên tập như cấu trúc tuyến tính, • Chia thành các phần bằng nhau – trang, • Tạo bảng quản lý trang. • Đặc điểm: • Tiết kiệm bộ nhớ, • Hiệu quả không phụ thuộc và cấu trúc ban đầu của CT nguồn. p0 p1 p2 p3 p4 p5 p6 RAM p0 p2 17 $3 - QUẢN LÝ BỘ NHỚ VẬT LÝ • Đặc điểm: – Có kích thước cụ thể, – Có cấu hình sử dụng cụ thể. • Phục vụ giai đoạn thực hiện CT: – Bảo vệ thông tin, – Bộ nhớ cho dữ liệu. • Vấn đề: – Cách tổ chức? – Xác lập quan hệ với bộ nhớ lô gíc: như thế nào và khi nào? – Tình huống thiếu bộ nhớ? 18 QUẢN LÝ BỘ NHỚ VẬT LÝ • Các chế độ quản lý bộ nhớ vật lý: – Chế độ phân vùng cố định, – Chế độ phân vùng động, – Chế độ mô đun, – Chế phân trang, • Chế độ kết hợp mô đun và phân trang. • Mọi chế độ: đều đang được sử dụng. 19 a) Chế độ phân vùng cố định • Bộ nhớ  n phần, mỗi phần có kích thước cố định (không nhất thiết bằng nhau), sử dụng như một bộ nhớ độc lập, phục vụ thực hiện 1 CT. 4 0 K B 4 0 0 K B 2 0 0 K B 5 KB 6 4 0 K B A B C,B L ớ p C T p h ụ c v ụ 20 Chế độ phân vùng cố định • Đặc điểm: – Mỗi vùng có một danh sách quản lý bộ nhớ tự do, – Mỗi vùng: thực hiện một CT ứng dụng, – Sơ đồ bảo vệ thông tin: theo toàn vùng. – Một số CT điều khiển phải dược copy vào từng vùng. • Phân lớp CT phục vụ để hạn chế lãng phí bộ nhớ, • Mô hình: Tổ chức đĩa cứng. 21 Chế độ phân vùng cố định • Công cụ phân bố lại bộ nhớ (SWAPPING): – Lệnh OP, – Do OP thực hiện, – Những vùng nào biên thay đổi: mất thông tin. Lý do: làm lại DSQL bộ nhó tự do. • Ví dụ: với đĩa cứng: FDISK. • CT điều khiển hệ thống: đơn giản. • Hệ số song song cố định. 22 b) CHẾ ĐỘ PHÂN VÙNG ĐỘNG • CT  Phân phối vùng bộ nhớ liên tục đủ thực hiện và quản lý như bộ nhớ độc lập. •  một danh sách QL bộ nhớ tự do duy nhất. 1 2 3 4 5 6 23 CHẾ ĐỘ PHÂN VÙNG ĐỘNG • Đặc điểm: – Hệ số song song biến thiên, –  hiện tượng phân đoạn ngoài (External Fragmentation)  SWAPPING, • Công cụ SWAPPING: – Lệnh OP, – Do OP thực hiện, – Không mất thông tin. • Nội dung SWAPPING. • Phức tạp của Swapping. • Mô hình quản lý đĩa từ SUBST, DRVSPACE 24 CHẾ ĐỘ PHÂN VÙNG ĐỘNG 2 4 6 2 4 6 B ộ n h ớ tự d o 25 C) CHẾ ĐỘ QUẢN LÝ THEO MÔ ĐUN • CT – cấu trúc mô đun, m0 m1 m2 m3 SCB (Segment Control Block) SCB = {Phần tử} D A l Dấu hiệu nạp mô đun: 0 - Chưa nạp, 1 - đã nạp. Địa chỉ nạp mô đun Độ dài mô đun - Cấp phát bộ nhớ, - Bảo vệ, 26 CHẾ ĐỘ QUẢN LÝ THEO MÔ ĐUN • Thực hiện CT: địa chỉ dữ liệu phải biểu diễn dưới dạng một cặp • SCB  RAM, địa chỉ đầu của SCB  Rs- Segment Register. • Để đọc /ghi dữ liệu: cần 2 lần truy nhập tới bộ nhớ: * (Rs) + s  truy nhập tới phần tử thứ s SCB, ** Khi D = 1: A+d  truy nhập tới dữ liệu. (s, d) № Mô đun offset 27 1 . . . . . . 300 314 315 300Rs = 15 4532 s d + 12352 12352 1000 + 16884 1 0 0 0 Mô đun 15 RAM RAM 28 CHẾ ĐỘ QUẢN LÝ THEO MÔ ĐUN • Đặc điểm: – Không cần phân phối bộ nhớ liên tục, – Không đòi hỏi công cụ đặc biệt  có thể áp dụng cho mọi MTĐT, – Dễ dàng sử dụng chung mô đun giữa các CT, – Hiệu quả phụ thuộc vào cấu trúc CT nguồn, – Tồn tại hiện tượng phân đoạn ngoài (External Fragmentation). • Thiếu bộ nhớ, phận đoạn ngoài  Swapping 29 CHẾ ĐỘ QUẢN LÝ THEO MÔ ĐUN • SWAPPING: – Do hệ thống đảm nhiệm, – Không mất thông tin, – Nội dung swapping: đưa một hoặc một số mô đun ra bộ nhớ ngoài, giải phóng chổ nạp mô đun mới. • Cách chọn mô đun đưa ra: Option – Mô đun tồn tại lâu nhất trong bộ nhớ, – Mô đun có lần sử dụng cuối cùngcách đây lâu nhất, – Mô đun có tần xuất sử dùng thấp nhất. • IBM PC 286 trở lên: – Một trong 2 chế độ của 286 và một trong 3 chế độ của 386 trở lên, – Swapping - ngầm định – tiêu chuẩn 2. 30 D) CHẾ ĐỘ PHÂN TRANG • Bộ nhớ được chia thành các phần bằng nhau – các trang (Pages), • Các trang – đánh số 0, 1, 2, . . . - địa chỉ trang. Page 0 Kích thước trang: 256B 512B 1 KB 2 KB 4 KB 1 2 3 4 5 6 7 Địa chỉ trang 31 CHẾ ĐỘ PHÂN TRANG • CT - cấu trúc phân trang, • Bảng quản lý trang PCB (Page Control Block), PCB = {Phần tử} DP AP Dấu hiệu nạp trang: 0 - Chưa nạp, 1 - đã nạp. Địa chỉ nạp trang 32 CHẾ ĐỘ PHÂN TRANG • Thực hiện CT: địa chỉ dữ liệu phải biểu diễn dưới dạng một cặp • PCB  RAM, địa chỉ đầu của PCB  RP- Page Register. • Để đọc /ghi dữ liệu: cần 2 lần truy nhập tới bộ nhớ: * (RP) + p  truy nhập tới phần tử thứ p PCB, ** Khi Dp = 1: A  d  truy nhập tới dữ liệu. (p, d) № trang offset 33 1 . . . . . . 400 480 481 400Rp = 81 532 p d + 123 123000 123532 Trang 81RAM RAM 34 CHẾ ĐỘ PHÂN TRANG • Đặc điểm: – Không cần phân phối bộ nhớ liên tục, – Phải có công cụ kỹ thuật hõ trợ định vị trang, – Không sử dụng chung mô đun giữa các CT, – Hiệu quả không phụ thuộc vào cấu trúc CT nguồn, – Bảng PCB có thể rất lớn, – Không bị phân đoạn ngoài. • Thiếu bộ nhớ (mọi trang đều đã được sử dụng)  Swapping 35 CHẾ ĐỘ PHÂN TRANG • SWAPPING: – Do hệ thống đảm nhiệm, – Không mất thông tin, – Nội dung swapping: đưa một trang ra bộ nhớ ngoài, giải phóng chổ nạp trang mới. • Cách chọn trang đưa ra: Option – Trang tồn tại lâu nhất trong bộ nhớ, – Trang có lần sử dụng cuối cùngcách đây lâu nhất, – Trang có tần xuất sử dùng thấp nhất. • IBM PC 386 trở lên: ngầm định – tiêu chuẩn 2. 36 E) CHẾ ĐỘ KẾT HỢP MÔ ĐUN – PHÂN TRANG • Bộ nhớ vật lý – phân trang, • CT – cấu trúc mô đun, • Mỗi mô đun – phân trang: m0 m1 m2 m3 PCB0 PCB1 PCB2 PCB3 SCB – quản lý các PCB 37 CHẾ ĐỘ KẾT HỢP MÔ ĐUN – PHÂN TRANG Dấu hiệu nạp PCB: 0 - Chưa nạp, 1 - đã nạp. SCB = {Phần tử} D A l Địa chỉ nạp PCB Độ dài PCB - Cấp phát bộ nhớ, - Bảo vệ, 38 CHẾ ĐỘ KẾT HỢP MÔ ĐUN – PHÂN TRANG • Thực hiện CT: địa chỉ dữ liệu phải biểu diễn dưới dạng một nhóm 3: • SCB  RAM, địa chỉ đầu của SCB  Rs- Segment Register. • Để đọc /ghi dữ liệu: cần 3 lần truy nhập tới bộ nhớ: * (Rs) + s  truy nhập tới phần tử thứ s SCB, ** Khi D = 1: A+d  truy nhập tới PCBs  SCB, *** Khi Dp = 1: A  d  truy nhập tới dữ liệu. (s, p,d) № Mô đun offset № trang 39 1 . . . . . . 300 314 315 300Rs = 15 s + 12314 12314 150 + 12395 1 5 0 PCB 81 RAM RAM 81 532 p d 1 . . . . . . 405 405000 405532 Trang 81 RAM 40 $4 - QUẢN LÝ BỘ NHỚ TRONG IBM PC • Bốn mức ưu tiên (Privilege Levels) thực hiện CT: 0  3, cao nhất – 0, thấp nhất – 3. • Nguyên tắc tuy nhập: một CT chỉ được quyền truy nhập tới CT và dữ liệu của CT bằng hoặc kém ưu tiên hơn. 3 0 1 2 Nhân QL Files T h iế t b ị và Phục vụ H ệ thống CT ứng dụng M ứ c ư u tiê n 41 IBM PC • Bộ nhớ phân phối cho CT - 2 loại: bộ nhớ chung (G) và bộ nhớ riêng (L). G L1 L2 L3 I II III 42 IBM PC • 2 chế độ: Chế độ thực (XT) và chế độ bảo vệ (AT). • Chế độ Real Mode: F E D C B A 1 0 9 R O M A M B Ộ N H Ớ C Ơ S Ở 64 KB 43 Chế độ Protected Mode MCB Bộ nhớ vật lý 0 1 2 k 3FFF Index 44 Chế độ Protected Mode • Mỗi khối  MCB (Memory Control Block) • Bộ nhớ chung {MCB}  GDT (Global Descriptor Table). • Bộ nhớ riêng {MCB}  LDT (Local Descriptor Table). • MCB: 8 Bytes/phần tử. • Thực hiện CT: GDT  RAM, GDTR LDT  RAM, LDTR Lệnh: LGDTR, SGDTR, LLDTR, SLDTR 45 MCB 286 MCB lADự trữ cho 386 Thuộc tính D A l P DPL S E ED W A Present Descriptor Privilege Level System Executable Expansion direction Writable Accessed E D = 0 E D = 1 d = 1 d = 1 46 80286 • Địa chỉ tuyến tính: 32 bits. • Khả năng: – Vật lý: AR – 24 bits – Vph= 2 24 – = 16MB – Lô gic: Vlg=2 1321216 – =230 – =1 GB Index dTI RPL 13 1 2 16 Table Indicator Requested Privilege level 47 MCB 386 MCB 20 bits l 4 Bytes A Thuộc tính D A l P DPL S E ED W A Present Descriptor Privilege Level System Executable Expansion direction Writable Accessed E D = 0 E D = 1 d = 1 d = 1 G D 0 0 48 80386 - PENTUM • G = 0 - Chế độ mô đun, đơn vị tính kích thước khối – Byte  L = 220 = 1 MB. • G = 1 - Chế độ phân trang, đơn vị tính kích thước khối – trang (4 KB)  L = 220 P = 220212 = 232 = 4 GB. • D = 0 - Chế độ dữ liệu 16 bit, • D = 1 - Chế độ dữ liệu 32 bit. 49 Index dTI RPL 13 1 2 32 Table Indicator Requested Privilege level 80386 - PENTUM • Địa chỉ tuyến tính: 48 bits. • Khả năng: – Vật lý: AR – 32 bits – Vph= 2 32 – = 4GB – Lô gic: Vlg=2 1321232 – =246 – = 26240 – = 64 TB 50 80386 - PENTUM • Chế độ kết hợp mô đun – phân trang: • Phân phối bộ nhớ: Page Index AVL 0 D A P C D P W T U / S R / W P0 20 3 12 Page Directory Page Tables P P P P . . . . . P . . . . . I II III RAM TLB 1 2