Bài giảng Hệ điều hành - Chương 3: Quản lý bộ nhớ - Phạm Đăng Hải

245 trang phuongnguyen 5780

Download

Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Hệ điều hành - Chương 3: Quản lý bộ nhớ - Phạm Đăng Hải", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

bai_giang_he_dieu_hanh_chuong_3_quan_ly_bo_nho_pham_dang_hai.pdf

Nội dung text: Bài giảng Hệ điều hành - Chương 3: Quản lý bộ nhớ - Phạm Đăng Hải

Hệ điều hành HỆ ĐIỀU HÀNH Phạm Đăng Hải haipd-fit@mail.hut.edu.vn Bộ môn Khoa học Máy tính Viện Công nghệ Thông tin & Truyền Thông Ngày 22 tháng 3 năm 2012 1 / 92
Chương 3: Quản lý bộ nhớ Chương 3 Quản lý bộ nhớ 2 / 92
Để s/d CPU hiệu quả và tăng tốc độ đáp ứng của hệ thống: Cần luân chuyển CPU thường xuyên giữa các tiến trình Điều phối CPU (Phần 3- Chương 2) Cần nhiều tiến trình sẵn sàng trong bộ nhớ Hệ số song song của hệ thống: Số tiến trình đồng thời tồn tại trong hệ thống Tồn tại nhiều sơ đồ quản lý bộ nhớ khác nhau Nhiều sơ đồ đòi hỏi trợ giúp từ phần cứng Thiết kế phần cứng có thể được tích hợp chặt chẽ với HDH Chương 3: Quản lý bộ nhớ Giới thiệu Mục đích của hệ thống máy tính: thực hiện chương trình Chương trình và dữ liệu (toàn bộ hoặc một phần) phải nằm trong bộ nhớ chính trong khi thực hiện Byte tích cực:Những byte nội dung đang được thực hiện tại thời điểm quan sát: Phần chương trình chưa đưa vào bộ nhớ chính được lưu trên bộ nhớ thứ cấp (VD: đĩa cứng)⇒ Bộ nhớ ảo Cho phép lập trình viên không lo lắng về giới hạn bộ nhớ vật lý 3 / 92
Tồn tại nhiều sơ đồ quản lý bộ nhớ khác nhau Nhiều sơ đồ đòi hỏi trợ giúp từ phần cứng Thiết kế phần cứng có thể được tích hợp chặt chẽ với HDH Chương 3: Quản lý bộ nhớ Giới thiệu Mục đích của hệ thống máy tính: thực hiện chương trình Chương trình và dữ liệu (toàn bộ hoặc một phần) phải nằm trong bộ nhớ chính trong khi thực hiện Byte tích cực:Những byte nội dung đang được thực hiện tại thời điểm quan sát: Phần chương trình chưa đưa vào bộ nhớ chính được lưu trên bộ nhớ thứ cấp (VD: đĩa cứng)⇒ Bộ nhớ ảo Cho phép lập trình viên không lo lắng về giới hạn bộ nhớ vật lý Để s/d CPU hiệu quả và tăng tốc độ đáp ứng của hệ thống: Cần luân chuyển CPU thường xuyên giữa các tiến trình Điều phối CPU (Phần 3- Chương 2) Cần nhiều tiến trình sẵn sàng trong bộ nhớ Hệ số song song của hệ thống: Số tiến trình đồng thời tồn tại trong hệ thống 3 / 92
Chương 3: Quản lý bộ nhớ Giới thiệu Mục đích của hệ thống máy tính: thực hiện chương trình Chương trình và dữ liệu (toàn bộ hoặc một phần) phải nằm trong bộ nhớ chính trong khi thực hiện Byte tích cực:Những byte nội dung đang được thực hiện tại thời điểm quan sát: Phần chương trình chưa đưa vào bộ nhớ chính được lưu trên bộ nhớ thứ cấp (VD: đĩa cứng)⇒ Bộ nhớ ảo Cho phép lập trình viên không lo lắng về giới hạn bộ nhớ vật lý Để s/d CPU hiệu quả và tăng tốc độ đáp ứng của hệ thống: Cần luân chuyển CPU thường xuyên giữa các tiến trình Điều phối CPU (Phần 3- Chương 2) Cần nhiều tiến trình sẵn sàng trong bộ nhớ Hệ số song song của hệ thống: Số tiến trình đồng thời tồn tại trong hệ thống Tồn tại nhiều sơ đồ quản lý bộ nhớ khác nhau Nhiều sơ đồ đòi hỏi trợ giúp từ phần cứng Thiết kế phần cứng có thể được tích hợp chặt chẽ với HDH 3 / 92
Chương 3: Quản lý bộ nhớ Nội dung chính 4 / 92
Chương 3: Quản lý bộ nhớ 1. Tổng quan Nội dung chính 1 Tổng quan 2 Các chiến lược quản lý bộ nhớ 3 Bộ nhớ ảo 5 / 92
Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.1 Ví dụ 1 Tổng quan Ví dụ Bộ nhớ và chương trình Liên kết địa chỉ Các cấu trúc chương trình 6 / 92
Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.1 Ví dụ 1 Tạo file thực thi dùng ngôn ngữ máy 2 Tạo file thực thi từ nhiều modul 7 / 92
Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.1 Ví dụ Ví dụ 1: Tạo chương trình thực thi dùng ngôn ngữ máy #include char buf[19]={ 0xEB,0x08,0x48,0x65,0x6C, 0x6C,0x6F,0x21,0x24,0x90, 0xB4,0x09,0xBA,0x02,0x01,0xCD,0x21,0xCD,0x20}; int main(int argc, char *argv[]){ int i; FILE * f = fopen("Toto.com","w+"); for(i= 0; i < 19;i++) fprintf(f,"%c",buf[i]); fclose(f); return 0; } 8 / 92
Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.1 Ví dụ Ví dụ 1: Kết quả File toto.com có kích thước 19 bytes Nội dung các câu lệnh trong chương trình thực thi toto.com? 9 / 92
Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.1 Ví dụ Ví dụ 1: Nội dung file Dùng debug xem nội dung file và dịch ngược ra hợp ngữ 10 / 92
Hello! terminated CS:0000 PSP: Program Dịch ngược Segment Prefix JMP 010A CS:0100 JMP 010A DB ’Hello!$’ CS:0102 ’Hello!$’ NOP CS:0109 NOP MOV AH, 9 CS:010A MOV AH, 9 MOV DX, 0102 CS:010C MOV DX, 0102 INT 21 CS:010F INT 21 INT 20 CS:0111 INT 20 CS:0113 Khi thực hiện, nạp toto.com vào bộ nhớ tại địa chỉ CS:0100 Các thanh ghi đoạn CS, ES, DS,SS cùng trỏ tới PSP Thanh ghi IP có giá trị 100 (CS:IP trỏ đến lệnh đầu tiên) SP trỏ tới cuối đoạn; Các thanh ghi thông dụng bị xóa (0) Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.1 Ví dụ Ví dụ 1: Thực hiện file toto.com Nội dung file Toto.com (19 bytes) EB 08 48 65 6C 6C 6F 21 24 90 B4 09 BA 02 01 CD 21 CD 20 11 / 92
Hello! terminated CS:0000 PSP: Program Segment Prefix CS:0100 JMP 010A CS:0102 ’Hello!$’ CS:0109 NOP CS:010A MOV AH, 9 CS:010C MOV DX, 0102 CS:010F INT 21 CS:0111 INT 20 CS:0113 Khi thực hiện, nạp toto.com vào bộ nhớ tại địa chỉ CS:0100 Các thanh ghi đoạn CS, ES, DS,SS cùng trỏ tới PSP Thanh ghi IP có giá trị 100 (CS:IP trỏ đến lệnh đầu tiên) SP trỏ tới cuối đoạn; Các thanh ghi thông dụng bị xóa (0) Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.1 Ví dụ Ví dụ 1: Thực hiện file toto.com Nội dung file Toto.com (19 bytes) EB 08 48 65 6C 6C 6F 21 24 90 B4 09 BA 02 01 CD 21 CD 20 Dịch ngược JMP 010A DB ’Hello!$’ NOP MOV AH, 9 MOV DX, 0102 INT 21 INT 20 11 / 92
Hello! terminated Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.1 Ví dụ Ví dụ 1: Thực hiện file toto.com Nội dung file Toto.com (19 bytes) EB 08 48 65 6C 6C 6F 21 24 90 B4 09 BA 02 01 CD 21 CD 20 CS:0000 PSP: Program Dịch ngược Segment Prefix JMP 010A CS:0100 JMP 010A ⇐CS:IP DB ’Hello!$’ CS:0102 ’Hello!$’ NOP CS:0109 NOP MOV AH, 9 CS:010A MOV AH, 9 MOV DX, 0102 CS:010C MOV DX, 0102 INT 21 CS:010F INT 21 INT 20 CS:0111 INT 20 CS:0113 Khi thực hiện, nạp toto.com vào bộ nhớ tại địa chỉ CS:0100 Các thanh ghi đoạn CS, ES, DS,SS cùng trỏ tới PSP Thanh ghi IP có giá trị 100 (CS:IP trỏ đến lệnh đầu tiên) 11 / 92 SP trỏ tới cuối đoạn; Các thanh ghi thông dụng bị xóa (0)
Hello! terminated Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.1 Ví dụ Ví dụ 1: Thực hiện file toto.com Nội dung file Toto.com (19 bytes) EB 08 48 65 6C 6C 6F 21 24 90 B4 09 BA 02 01 CD 21 CD 20 CS:0000 PSP: Program Dịch ngược Segment Prefix JMP 010A CS:0100 JMP 010A DB ’Hello!$’ CS:0102 ’Hello!$’ NOP CS:0109 NOP MOV AH, 9 CS:010A MOV AH, 9 ⇐CS:IP MOV DX, 0102 CS:010C MOV DX, 0102 INT 21 CS:010F INT 21 INT 20 CS:0111 INT 20 CS:0113 Khi thực hiện, nạp toto.com vào bộ nhớ tại địa chỉ CS:0100 Các thanh ghi đoạn CS, ES, DS,SS cùng trỏ tới PSP Thanh ghi IP có giá trị 100 (CS:IP trỏ đến lệnh đầu tiên) 11 / 92 SP trỏ tới cuối đoạn; Các thanh ghi thông dụng bị xóa (0)
Hello! terminated Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.1 Ví dụ Ví dụ 1: Thực hiện file toto.com Nội dung file Toto.com (19 bytes) EB 08 48 65 6C 6C 6F 21 24 90 B4 09 BA 02 01 CD 21 CD 20 CS:0000 PSP: Program Dịch ngược Segment Prefix JMP 010A CS:0100 JMP 010A DB ’Hello!$’ CS:0102 ’Hello!$’ NOP CS:0109 NOP MOV AH, 9 CS:010A MOV AH, 9 MOV DX, 0102 CS:010C MOV DX, 0102 ⇐CS:IP INT 21 CS:010F INT 21 INT 20 CS:0111 INT 20 CS:0113 Khi thực hiện, nạp toto.com vào bộ nhớ tại địa chỉ CS:0100 Các thanh ghi đoạn CS, ES, DS,SS cùng trỏ tới PSP Thanh ghi IP có giá trị 100 (CS:IP trỏ đến lệnh đầu tiên) 11 / 92 SP trỏ tới cuối đoạn; Các thanh ghi thông dụng bị xóa (0)
Hello! terminated Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.1 Ví dụ Ví dụ 1: Thực hiện file toto.com Nội dung file Toto.com (19 bytes) EB 08 48 65 6C 6C 6F 21 24 90 B4 09 BA 02 01 CD 21 CD 20 CS:0000 PSP: Program Dịch ngược Segment Prefix JMP 010A CS:0100 JMP 010A DB ’Hello!$’ CS:0102 ’Hello!$’ NOP CS:0109 NOP MOV AH, 9 CS:010A MOV AH, 9 MOV DX, 0102 CS:010C MOV DX, 0102 INT 21 CS:010F INT 21 ⇐CS:IP INT 20 CS:0111 INT 20 CS:0113 Khi thực hiện, nạp toto.com vào bộ nhớ tại địa chỉ CS:0100 Các thanh ghi đoạn CS, ES, DS,SS cùng trỏ tới PSP Thanh ghi IP có giá trị 100 (CS:IP trỏ đến lệnh đầu tiên) 11 / 92 SP trỏ tới cuối đoạn; Các thanh ghi thông dụng bị xóa (0)
terminated Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.1 Ví dụ Ví dụ 1: Thực hiện file toto.com Nội dung file Toto.com (19 bytes) EB 08 48 65 6C 6C 6F 21 24 90 B4 09 BA 02 01 CD 21 CD 20 CS:0000 PSP: Program Hello! Dịch ngược Segment Prefix JMP 010A CS:0100 JMP 010A DB ’Hello!$’ CS:0102 ’Hello!$’ NOP CS:0109 NOP MOV AH, 9 CS:010A MOV AH, 9 MOV DX, 0102 CS:010C MOV DX, 0102 INT 21 CS:010F INT 21 INT 20 CS:0111 INT 20 ⇐CS:IP CS:0113 Khi thực hiện, nạp toto.com vào bộ nhớ tại địa chỉ CS:0100 Các thanh ghi đoạn CS, ES, DS,SS cùng trỏ tới PSP Thanh ghi IP có giá trị 100 (CS:IP trỏ đến lệnh đầu tiên) 11 / 92 SP trỏ tới cuối đoạn; Các thanh ghi thông dụng bị xóa (0)
Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.1 Ví dụ Ví dụ 1: Thực hiện file toto.com Nội dung file Toto.com (19 bytes) EB 08 48 65 6C 6C 6F 21 24 90 B4 09 BA 02 01 CD 21 CD 20 CS:0000 PSP: Program Hello! Dịch ngược Segment Prefix terminated JMP 010A CS:0100 JMP 010A DB ’Hello!$’ CS:0102 ’Hello!$’ NOP CS:0109 NOP MOV AH, 9 CS:010A MOV AH, 9 MOV DX, 0102 CS:010C MOV DX, 0102 INT 21 CS:010F INT 21 INT 20 CS:0111 INT 20 CS:0113 Khi thực hiện, nạp toto.com vào bộ nhớ tại địa chỉ CS:0100 Các thanh ghi đoạn CS, ES, DS,SS cùng trỏ tới PSP Thanh ghi IP có giá trị 100 (CS:IP trỏ đến lệnh đầu tiên) 11 / 92 SP trỏ tới cuối đoạn; Các thanh ghi thông dụng bị xóa (0)
Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.1 Ví dụ Ví dụ 2: Tạo file thực thi từ nhiều modul Toto project file main.c file M1.c #include int y = 10; extern int x, y; extern void toto(); file M2.c int main(int argc, char *argv[]){ int x; toto(); extern int y; printf("KQ: %d \n",x * y); void toto(){ return 0; x = 10 * y; } } Ket qua KQ: 1000 12 / 92
Thư viện Header [printf] [y←10] [y←10] M1.o [x] x y [printf] Link - toto (tlink) - [toto] printf x main.o y toto [x] printf y x [toto] y M2.o toto.exe Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.1 Ví dụ Ví dụ 2: Quá trình xử lý toto project int y=10; M1.c extern int x,y; extern void toto(); int main(){ Compiler toto() (tcc -c) printf() } main.c int x; extern int y; toto() M2.c 13 / 92
Thư viện Header [printf] [y←10] [x] [printf] Link - (tlink) - [toto] x y toto printf x y toto.exe Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.1 Ví dụ Ví dụ 2: Quá trình xử lý toto project int y=10; [y←10] M1.c M1.o extern int x,y; x extern void toto(); y int main(){ Compiler toto() (tcc -c) toto printf() printf } main.o main.c int x; [x] extern int y; y toto() [toto] M2.c M2.o 13 / 92
Header [y←10] [x] [printf] - - [toto] x y toto printf x y toto.exe Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.1 Ví dụ Ví dụ 2: Quá trình xử lý toto project Thư viện [printf] int y=10; [y←10] M1.c M1.o extern int x,y; x extern void toto(); y int main(){ Compiler Link toto() (tcc -c) toto (tlink) printf() printf } main.o main.c int x; [x] extern int y; y toto() [toto] M2.c M2.o 13 / 92
Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.1 Ví dụ Ví dụ 2: Quá trình xử lý toto project Thư viện Header [printf] int y=10; [y←10] [y←10] M1.c M1.o [x] extern int x,y; x extern void toto(); y [printf] int main(){ Compiler Link - toto() (tcc -c) toto (tlink) - [toto] printf() printf x } main.o y main.c toto int x; [x] printf extern int y; y x toto() [toto] y M2.c M2.o toto.exe 13 / 92
Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.2 Bộ nhớ và chương trình 1 Tổng quan Ví dụ Bộ nhớ và chương trình Liên kết địa chỉ Các cấu trúc chương trình 14 / 92
Bộ nhớ được đặc trưng bởi kích thước và tốc độ truy nhập Bộ nhớ được phân cấp theo tốc độ truy nhập Loại bộ nhớ Kích thước Tốc độ Thanh ghi (Registers) bytes Tốc độ CPU(ηs) Cache trên VXL Kilo Bytes 10 nano seconds Cache mức 2 KiloByte-MegaByte 100 nanoseconds Bộ nhớ chính MegaByte-GigaByte Micro-seconds Bộ nhớ lưu trữ (Disk) GigaByte-Terabytes Mili-Seconds Băng từ, đĩa quang Không giới hạn 10 Seconds Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.2 Bộ nhớ và chương trình Phân cấp bộ nhớ Bộ nhớ là tài nguyên quan trọng của hệ thống Chương trình phải nằm trong bộ nhớ trong để thực hiện 15 / 92
Bộ nhớ được phân cấp theo tốc độ truy nhập Loại bộ nhớ Kích thước Tốc độ Thanh ghi (Registers) bytes Tốc độ CPU(ηs) Cache trên VXL Kilo Bytes 10 nano seconds Cache mức 2 KiloByte-MegaByte 100 nanoseconds Bộ nhớ chính MegaByte-GigaByte Micro-seconds Bộ nhớ lưu trữ (Disk) GigaByte-Terabytes Mili-Seconds Băng từ, đĩa quang Không giới hạn 10 Seconds Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.2 Bộ nhớ và chương trình Phân cấp bộ nhớ Bộ nhớ là tài nguyên quan trọng của hệ thống Chương trình phải nằm trong bộ nhớ trong để thực hiện Bộ nhớ được đặc trưng bởi kích thước và tốc độ truy nhập 15 / 92
Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.2 Bộ nhớ và chương trình Phân cấp bộ nhớ Bộ nhớ là tài nguyên quan trọng của hệ thống Chương trình phải nằm trong bộ nhớ trong để thực hiện Bộ nhớ được đặc trưng bởi kích thước và tốc độ truy nhập Bộ nhớ được phân cấp theo tốc độ truy nhập Loại bộ nhớ Kích thước Tốc độ Thanh ghi (Registers) bytes Tốc độ CPU(ηs) Cache trên VXL Kilo Bytes 10 nano seconds Cache mức 2 KiloByte-MegaByte 100 nanoseconds Bộ nhớ chính MegaByte-GigaByte Micro-seconds Bộ nhớ lưu trữ (Disk) GigaByte-Terabytes Mili-Seconds Băng từ, đĩa quang Không giới hạn 10 Seconds 15 / 92
Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.2 Bộ nhớ và chương trình Bộ nhớ chính 00000 00001 Memory Dùng lưu trữ dữ liệu và chương trình Là mảng các ô nhớ kiểu bytes, words FFFFE Mỗi ô nhớ có một địa chỉ riêng FFFFF Địa chỉ vật lý: địa chỉ x/hiện ở chân VXL 16 / 92
Phải được đưa vào bộ nhớ trong và được đặt trong một tiến trình để thực hiện (tiến trình thực hiện chương trình) Hàng đợi vào (input queue) Tập các tiến trình ở bộ nhớ ngoài (thông thường disk) Đợi để được đưa vào bộ nhớ trong và thực hiên Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.2 Bộ nhớ và chương trình Chương trình Tồn tại trên thiết bị lưu trữ ngoài Là các file nhị phân thực thi được Vùng tham số file Lệnh máy (mã nhị phân), Vùng dữ liệu (biến toàn cục), 17 / 92
Hàng đợi vào (input queue) Tập các tiến trình ở bộ nhớ ngoài (thông thường disk) Đợi để được đưa vào bộ nhớ trong và thực hiên Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.2 Bộ nhớ và chương trình Chương trình Tồn tại trên thiết bị lưu trữ ngoài Là các file nhị phân thực thi được Vùng tham số file Lệnh máy (mã nhị phân), Vùng dữ liệu (biến toàn cục), Phải được đưa vào bộ nhớ trong và được đặt trong một tiến trình để thực hiện (tiến trình thực hiện chương trình) 17 / 92
Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.2 Bộ nhớ và chương trình Chương trình Tồn tại trên thiết bị lưu trữ ngoài Là các file nhị phân thực thi được Vùng tham số file Lệnh máy (mã nhị phân), Vùng dữ liệu (biến toàn cục), Phải được đưa vào bộ nhớ trong và được đặt trong một tiến trình để thực hiện (tiến trình thực hiện chương trình) Hàng đợi vào (input queue) Tập các tiến trình ở bộ nhớ ngoài (thông thường disk) Đợi để được đưa vào bộ nhớ trong và thực hiên 17 / 92
Thực thi chương trình CPU lấy các lệnh trong bộ nhớ tại vị trí được xác định bởi bộ đếm chương trình (Program counter) Cặp thanh ghi CS:IP với VXL họ Intel (Ví dụ : 80x86) CPU giải mã lệnh Có thể lấy thêm toán hạng từ bộ nhớ Thực hiện lệnh với toán hạng Nếu cần thiết, lưu kết quả vào bộ nhớ tại một địa chỉ xác định Thực hiện xong Giải phóng vùng không gian nhớ dành cho chương trình Vấn đề Chương trình có thể được nạp vào vị trí bất kỳ trong bộ nhớ Khi thực hiện chương trình sinh ra chuỗi địa chỉ bộ nhớ Truy nhập địa chỉ bộ nhớ như thế nào? Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.2 Bộ nhớ và chương trình Thực hiện chương trình Nạp chương trình vào bộ nhớ Đọc và phân tích (dịch) file thực thi (VD file *.com, file *.exe) Xin vùng nhớ để nạp chương trình từ file trên đĩa Thiết lập các tham số, các thanh ghi tới giá trị thích hợp 18 / 92
Thực hiện xong Giải phóng vùng không gian nhớ dành cho chương trình Vấn đề Chương trình có thể được nạp vào vị trí bất kỳ trong bộ nhớ Khi thực hiện chương trình sinh ra chuỗi địa chỉ bộ nhớ Truy nhập địa chỉ bộ nhớ như thế nào? Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.2 Bộ nhớ và chương trình Thực hiện chương trình Nạp chương trình vào bộ nhớ Đọc và phân tích (dịch) file thực thi (VD file *.com, file *.exe) Xin vùng nhớ để nạp chương trình từ file trên đĩa Thiết lập các tham số, các thanh ghi tới giá trị thích hợp Thực thi chương trình CPU lấy các lệnh trong bộ nhớ tại vị trí được xác định bởi bộ đếm chương trình (Program counter) Cặp thanh ghi CS:IP với VXL họ Intel (Ví dụ : 80x86) CPU giải mã lệnh Có thể lấy thêm toán hạng từ bộ nhớ Thực hiện lệnh với toán hạng Nếu cần thiết, lưu kết quả vào bộ nhớ tại một địa chỉ xác định 18 / 92
Vấn đề Chương trình có thể được nạp vào vị trí bất kỳ trong bộ nhớ Khi thực hiện chương trình sinh ra chuỗi địa chỉ bộ nhớ Truy nhập địa chỉ bộ nhớ như thế nào? Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.2 Bộ nhớ và chương trình Thực hiện chương trình Nạp chương trình vào bộ nhớ Đọc và phân tích (dịch) file thực thi (VD file *.com, file *.exe) Xin vùng nhớ để nạp chương trình từ file trên đĩa Thiết lập các tham số, các thanh ghi tới giá trị thích hợp Thực thi chương trình CPU lấy các lệnh trong bộ nhớ tại vị trí được xác định bởi bộ đếm chương trình (Program counter) Cặp thanh ghi CS:IP với VXL họ Intel (Ví dụ : 80x86) CPU giải mã lệnh Có thể lấy thêm toán hạng từ bộ nhớ Thực hiện lệnh với toán hạng Nếu cần thiết, lưu kết quả vào bộ nhớ tại một địa chỉ xác định Thực hiện xong Giải phóng vùng không gian nhớ dành cho chương trình 18 / 92
Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.2 Bộ nhớ và chương trình Thực hiện chương trình Nạp chương trình vào bộ nhớ Đọc và phân tích (dịch) file thực thi (VD file *.com, file *.exe) Xin vùng nhớ để nạp chương trình từ file trên đĩa Thiết lập các tham số, các thanh ghi tới giá trị thích hợp Thực thi chương trình CPU lấy các lệnh trong bộ nhớ tại vị trí được xác định bởi bộ đếm chương trình (Program counter) Cặp thanh ghi CS:IP với VXL họ Intel (Ví dụ : 80x86) CPU giải mã lệnh Có thể lấy thêm toán hạng từ bộ nhớ Thực hiện lệnh với toán hạng Nếu cần thiết, lưu kết quả vào bộ nhớ tại một địa chỉ xác định Thực hiện xong Giải phóng vùng không gian nhớ dành cho chương trình Vấn đề Chương trình có thể được nạp vào vị trí bất kỳ trong bộ nhớ Khi thực hiện chương trình sinh ra chuỗi địa chỉ bộ nhớ Truy nhập địa chỉ bộ nhớ như thế nào? 18 / 92
Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.3 Liên kết địa chỉ 1 Tổng quan Ví dụ Bộ nhớ và chương trình Liên kết địa chỉ Các cấu trúc chương trình 19 / 92
Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.3 Liên kết địa chỉ Các bước xử lý chương trình ứng dụng Chương trình Các modul đối Thư viện hệ nguồn tượng khác thống được nạp động inktđộng kết Liên Modul đối Dịch Liên tượng kết Modul thực Chương trình Nạp hiện trong bộ nhớ Thư viện hệ thống Bộ nhớ trong 20 / 92
Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.3 Liên kết địa chỉ Các kiểu địa chỉ Địa chỉ biểu tượng (symbolic) Là tên của đối tượng trong chương trình nguồn Ví du: counter, x, y, Địa chỉ tương đối Sinh ra từ địa chỉ biểu tượng trong giai đoạn dịch (compiler) Là vị trí tương đối của đối tượng kể từ đầu modul Byte thứ 10 kể từ đầu modul EB08 ⇒ JMP +08: Nhảy tới vị trí cách vị trí hiện tại 8 ô Địa chỉ tuyệt đối Sinh ra từ địa chỉ tương đối trong giai đoạn nạp chương trình thực thi vào bộ nhớ để thực hiện Với PC: địa chỉ tương đối → Seg * 16+Ofs Là địa chỉ của đối tượng trong bộ nhớ vật lý-địa chỉ vật lý Ví du: JMP 010A⇒ Nhảy tới ô nhớ có vị trí 010Ah tại cùng đoạn mã lệnh (CS) Nếu CS=1555h, sẽ đi tới vị trí: 1555h*10h+010Ah =1560Ah 21 / 92
Giai đoạn dịch: Sử dụng khi biết chương trình sẽ nằm ở đâu trong bộ nhớ Khi dịch sẽ sinh ra mã (địa chỉ ) tuyệt đối Phải dịch lại khi vị trí bắt đầu thay đổi Thời điểm nạp: Sử dụng khi không biết c/trình sẽ nằm ở đâu trong bộ nhớ Các đối tượng được dịch ra sẽ mang địa chỉ tương đối Xác định địa chỉ được hoãn lại tới khi khi nạp chương trình vào bộ nhớ Trong khi thực hiện: S/dụng khi các tiến trình có thể thay đổi vị trí trong khi t/hiện Xác định địa chỉ được hoãn lại tới khi thực thi chương trình Thường đòi hỏi trợ giúp từ phần cứng Được sử dụng trong nhiều hệ điều hành Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.3 Liên kết địa chỉ Xác định địa chỉ Xác định địa chỉ câu lệnh và dữ liệu trong bộ nhớ có thể thực hiện tại các giai đoạn khác nhau khi xử lý chương trình ứng dung 22 / 92
Thời điểm nạp: Sử dụng khi không biết c/trình sẽ nằm ở đâu trong bộ nhớ Các đối tượng được dịch ra sẽ mang địa chỉ tương đối Xác định địa chỉ được hoãn lại tới khi khi nạp chương trình vào bộ nhớ Trong khi thực hiện: S/dụng khi các tiến trình có thể thay đổi vị trí trong khi t/hiện Xác định địa chỉ được hoãn lại tới khi thực thi chương trình Thường đòi hỏi trợ giúp từ phần cứng Được sử dụng trong nhiều hệ điều hành Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.3 Liên kết địa chỉ Xác định địa chỉ Xác định địa chỉ câu lệnh và dữ liệu trong bộ nhớ có thể thực hiện tại các giai đoạn khác nhau khi xử lý chương trình ứng dung Giai đoạn dịch: Sử dụng khi biết chương trình sẽ nằm ở đâu trong bộ nhớ Khi dịch sẽ sinh ra mã (địa chỉ ) tuyệt đối Phải dịch lại khi vị trí bắt đầu thay đổi 22 / 92
Trong khi thực hiện: S/dụng khi các tiến trình có thể thay đổi vị trí trong khi t/hiện Xác định địa chỉ được hoãn lại tới khi thực thi chương trình Thường đòi hỏi trợ giúp từ phần cứng Được sử dụng trong nhiều hệ điều hành Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.3 Liên kết địa chỉ Xác định địa chỉ Xác định địa chỉ câu lệnh và dữ liệu trong bộ nhớ có thể thực hiện tại các giai đoạn khác nhau khi xử lý chương trình ứng dung Giai đoạn dịch: Sử dụng khi biết chương trình sẽ nằm ở đâu trong bộ nhớ Khi dịch sẽ sinh ra mã (địa chỉ ) tuyệt đối Phải dịch lại khi vị trí bắt đầu thay đổi Thời điểm nạp: Sử dụng khi không biết c/trình sẽ nằm ở đâu trong bộ nhớ Các đối tượng được dịch ra sẽ mang địa chỉ tương đối Xác định địa chỉ được hoãn lại tới khi khi nạp chương trình vào bộ nhớ 22 / 92
Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.3 Liên kết địa chỉ Xác định địa chỉ Xác định địa chỉ câu lệnh và dữ liệu trong bộ nhớ có thể thực hiện tại các giai đoạn khác nhau khi xử lý chương trình ứng dung Giai đoạn dịch: Sử dụng khi biết chương trình sẽ nằm ở đâu trong bộ nhớ Khi dịch sẽ sinh ra mã (địa chỉ ) tuyệt đối Phải dịch lại khi vị trí bắt đầu thay đổi Thời điểm nạp: Sử dụng khi không biết c/trình sẽ nằm ở đâu trong bộ nhớ Các đối tượng được dịch ra sẽ mang địa chỉ tương đối Xác định địa chỉ được hoãn lại tới khi khi nạp chương trình vào bộ nhớ Trong khi thực hiện: S/dụng khi các tiến trình có thể thay đổi vị trí trong khi t/hiện Xác định địa chỉ được hoãn lại tới khi thực thi chương trình Thường đòi hỏi trợ giúp từ phần cứng Được sử dụng trong nhiều hệ điều hành 22 / 92
Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.3 Liên kết địa chỉ Địa chỉ vật lý-địa chỉ logic Địa chỉ logic (địa chỉ ảo) Được sinh ra trong tiến trình, (CPU đưa ra) Được khối quản lý bộ nhớ (MMU) chuyển sang địa chỉ vật lý khi truy nhập tới đối tượng trong chương trình Địa chỉ vật lý Địa chỉ của một phần tử (byte/word) của bộ nhớ Tương ứng với địa chỉ logic được CPU đưa ra Chương trình làm việc với địa chỉ logic 23 / 92
Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.4 Các cấu trúc chương trình 1 Tổng quan Ví dụ Bộ nhớ và chương trình Liên kết địa chỉ Các cấu trúc chương trình 24 / 92
Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.4 Các cấu trúc chương trình Các cấu trúc chương trình 1 Cấu trúc tuyến tính 2 Cấu trúc nạp động 3 Cấu trúc liên kết động 4 Cấu truc Overlays 25 / 92
Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.4 Các cấu trúc chương trình Cấu trúc tuyến tínhI M0 M1 Biên tập M0 M1 M2 M3 M2 M3 Sau khi biên tập, các modul được tập hợp thành một chương trình hoàn thiện Chứa đầy đủ các thông tin để có thể thực hiện được Các biến trỏ ngoài đã thay bằng giá trị cụ thể Để thực hiện, chỉ cần định vị một lần trong bộ nhớ 26 / 92
Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.4 Các cấu trúc chương trình Cấu trúc tuyến tính II Ưu điểm Đơn giản, dễ tổ chức biên tập và định vị chương trình Thời gian thực hiện nhanh Tính lưu động cao Nhược điểm Lãng phí nhớ Không phải toàn bộ chương trình đều cần thiết cho thực hiện chương trình Không thực hiện được chương trình có kích thước lớn hơn kích thước bộ nhớ vật lý 27 / 92
M0 M1 M3 M1 M2 M2 Khi thực hiện, hệ thống sẽ định vị modul gốc Cần tới modul nào se xin bộ nhớ và giải nạp modul vào Khi sử dụng xong một modul, hoặc khi thiếu vùng nhớ sẽ đưa nhưng modul không cần thiết ra ngoài Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.4 Các cấu trúc chương trình Cấu trúc nạp động M0 Hệ điều hành M1 M2 M3 Mỗi modul được biên tập riêng 28 / 92
M1 M3 M1 M2 M2 Cần tới modul nào se xin bộ nhớ và giải nạp modul vào Khi sử dụng xong một modul, hoặc khi thiếu vùng nhớ sẽ đưa nhưng modul không cần thiết ra ngoài Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.4 Các cấu trúc chương trình Cấu trúc nạp động M0 Hệ điều hành M1 M0 M2 M3 Mỗi modul được biên tập riêng Khi thực hiện, hệ thống sẽ định vị modul gốc 28 / 92
M3 M1 M2 M2 Khi sử dụng xong một modul, hoặc khi thiếu vùng nhớ sẽ đưa nhưng modul không cần thiết ra ngoài Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.4 Các cấu trúc chương trình Cấu trúc nạp động M0 Hệ điều hành M1 M0 M2 M1 M3 Mỗi modul được biên tập riêng Khi thực hiện, hệ thống sẽ định vị modul gốc Cần tới modul nào se xin bộ nhớ và giải nạp modul vào 28 / 92
M3 M1 M2 Khi sử dụng xong một modul, hoặc khi thiếu vùng nhớ sẽ đưa nhưng modul không cần thiết ra ngoài Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.4 Các cấu trúc chương trình Cấu trúc nạp động M0 Hệ điều hành M1 M0 M2 M1 M2 M3 Mỗi modul được biên tập riêng Khi thực hiện, hệ thống sẽ định vị modul gốc Cần tới modul nào se xin bộ nhớ và giải nạp modul vào 28 / 92
M1 M3 M2 Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.4 Các cấu trúc chương trình Cấu trúc nạp động M0 Hệ điều hành M1 M0 M2 M1 M2 M3 Mỗi modul được biên tập riêng Khi thực hiện, hệ thống sẽ định vị modul gốc Cần tới modul nào se xin bộ nhớ và giải nạp modul vào Khi sử dụng xong một modul, hoặc khi thiếu vùng nhớ sẽ đưa nhưng modul không cần thiết ra ngoài 28 / 92
M1 M1 M2 M2 Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.4 Các cấu trúc chương trình Cấu trúc nạp động M0 Hệ điều hành M1 M0 M2 M3 M3 Mỗi modul được biên tập riêng Khi thực hiện, hệ thống sẽ định vị modul gốc Cần tới modul nào se xin bộ nhớ và giải nạp modul vào Khi sử dụng xong một modul, hoặc khi thiếu vùng nhớ sẽ đưa nhưng modul không cần thiết ra ngoài 28 / 92
Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.4 Các cấu trúc chương trình Cấu trúc nạp động (tiếp) Có thể sử dụng vùng nhớ nhiều hơn phần dành cho chương trình Hiệu quả sử dụng bộ nhớ cao nếu quản lý tốt Sai lầm sẽ dẫn tới lãng phí bộ nhớ và tăng thời gian thực hiện Tốc độ thực hiện chậm Yêu cầu người sử dụng phải nạp và xóa các modul Người dùng phải nắm rõ hệ thống Giảm tính lưu động 29 / 92
Khi tìm thấy, stub sẽ được thay thế với địa chỉ của thủ tục và thực hiện thủ tục toto Hữu ích cho xây dựng thư viện M Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.4 Các cấu trúc chương trình Cấu trúc liên kết động (DLL:Dynamic-link library) toto() Các liên kết sẽ hoãn lại cho tới khi M thực hiện chương trình Một phần của đoạn mã (stub) được sử dụng để tìm kiếm thủ tục tương Hệ điều hành ứng trong thư viện trong bộ nhớ toto() 30 / 92
Hữu ích cho xây dựng thư viện Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.4 Các cấu trúc chương trình Cấu trúc liên kết động (DLL:Dynamic-link library) toto() Các liên kết sẽ hoãn lại cho tới khi M thực hiện chương trình Một phần của đoạn mã (stub) được sử dụng để tìm kiếm thủ tục tương Hệ điều hành ứng trong thư viện trong bộ nhớ toto() Khi tìm thấy, stub sẽ được thay thế với địa chỉ của thủ tục và thực hiện thủ tục toto M 30 / 92
Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.4 Các cấu trúc chương trình Cấu trúc liên kết động (DLL:Dynamic-link library) toto() Các liên kết sẽ hoãn lại cho tới khi M thực hiện chương trình Một phần của đoạn mã (stub) được sử dụng để tìm kiếm thủ tục tương Hệ điều hành ứng trong thư viện trong bộ nhớ toto() Khi tìm thấy, stub sẽ được thay thế với địa chỉ của thủ tục và thực hiện thủ tục toto Hữu ích cho xây dựng thư viện M 30 / 92
Bộ nhớ cũng được chia thành mức ứng với mức chương trình Kích thước bằng kích thước của modul lớn nhất cùng mức Để có cấu trúc Overlay, cần cung cấp thêm các thông tin Chương trình bao nhiêu mức, mỗi mức gồm những modul nào Thông tin cung cấp lưu trong file (sơ đồ overlay) Modul mức 0 được biên tập thành file thực thi riêng Khi thực hiện chương trình Nạp modul mức 0 như chương trình tuyến tính Cần tới modul khác, sẽ nạp modul vào mức bộ nhớ tương ứng Nếu có modul đồng mức tồn tại, đưa ra bên ngoài Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.4 Các cấu trúc chương trình Cấu truc Overlays Modul được chia thành các mức Mức 0 chứa modul gốc, nạp và định vị chương trình Mức 1 chứa các Modul được gọi từ những modul ở mức 0 và không đồng thời tồn tại 31 / 92
Để có cấu trúc Overlay, cần cung cấp thêm các thông tin Chương trình bao nhiêu mức, mỗi mức gồm những modul nào Thông tin cung cấp lưu trong file (sơ đồ overlay) Modul mức 0 được biên tập thành file thực thi riêng Khi thực hiện chương trình Nạp modul mức 0 như chương trình tuyến tính Cần tới modul khác, sẽ nạp modul vào mức bộ nhớ tương ứng Nếu có modul đồng mức tồn tại, đưa ra bên ngoài Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.4 Các cấu trúc chương trình Cấu truc Overlays Modul được chia thành các mức Mức 0 chứa modul gốc, nạp và định vị chương trình Mức 1 chứa các Modul được gọi từ những modul ở mức 0 và không đồng thời tồn tại Bộ nhớ cũng được chia thành mức ứng với mức chương trình Kích thước bằng kích thước của modul lớn nhất cùng mức 31 / 92
Modul mức 0 được biên tập thành file thực thi riêng Khi thực hiện chương trình Nạp modul mức 0 như chương trình tuyến tính Cần tới modul khác, sẽ nạp modul vào mức bộ nhớ tương ứng Nếu có modul đồng mức tồn tại, đưa ra bên ngoài Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.4 Các cấu trúc chương trình Cấu truc Overlays Modul được chia thành các mức Mức 0 chứa modul gốc, nạp và định vị chương trình Mức 1 chứa các Modul được gọi từ những modul ở mức 0 và không đồng thời tồn tại Bộ nhớ cũng được chia thành mức ứng với mức chương trình Kích thước bằng kích thước của modul lớn nhất cùng mức Để có cấu trúc Overlay, cần cung cấp thêm các thông tin Chương trình bao nhiêu mức, mỗi mức gồm những modul nào Thông tin cung cấp lưu trong file (sơ đồ overlay) 31 / 92
Khi thực hiện chương trình Nạp modul mức 0 như chương trình tuyến tính Cần tới modul khác, sẽ nạp modul vào mức bộ nhớ tương ứng Nếu có modul đồng mức tồn tại, đưa ra bên ngoài Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.4 Các cấu trúc chương trình Cấu truc Overlays Modul được chia thành các mức Mức 0 chứa modul gốc, nạp và định vị chương trình Mức 1 chứa các Modul được gọi từ những modul ở mức 0 và không đồng thời tồn tại Bộ nhớ cũng được chia thành mức ứng với mức chương trình Kích thước bằng kích thước của modul lớn nhất cùng mức Để có cấu trúc Overlay, cần cung cấp thêm các thông tin Chương trình bao nhiêu mức, mỗi mức gồm những modul nào Thông tin cung cấp lưu trong file (sơ đồ overlay) Modul mức 0 được biên tập thành file thực thi riêng 31 / 92
Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.4 Các cấu trúc chương trình Cấu truc Overlays Modul được chia thành các mức Mức 0 chứa modul gốc, nạp và định vị chương trình Mức 1 chứa các Modul được gọi từ những modul ở mức 0 và không đồng thời tồn tại Bộ nhớ cũng được chia thành mức ứng với mức chương trình Kích thước bằng kích thước của modul lớn nhất cùng mức Để có cấu trúc Overlay, cần cung cấp thêm các thông tin Chương trình bao nhiêu mức, mỗi mức gồm những modul nào Thông tin cung cấp lưu trong file (sơ đồ overlay) Modul mức 0 được biên tập thành file thực thi riêng Khi thực hiện chương trình Nạp modul mức 0 như chương trình tuyến tính Cần tới modul khác, sẽ nạp modul vào mức bộ nhớ tương ứng Nếu có modul đồng mức tồn tại, đưa ra bên ngoài 31 / 92
M0 M1 M2 M11 M12 MM111 Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.4 Các cấu trúc chương trình Cấu trúc Overlays: Ví dụ 80K 80K 120K Bộ nhớ trong 32 / 92
M1 M2 M11 M12 MM111 Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.4 Các cấu trúc chương trình Cấu trúc Overlays: Ví dụ M0 80K 80K 120K Bộ nhớ trong 32 / 92
M2 M11 M12 MM111 Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.4 Các cấu trúc chương trình Cấu trúc Overlays: Ví dụ M0 80K M1 80K 120K Bộ nhớ trong 32 / 92
M2 M12 MM111 Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.4 Các cấu trúc chương trình Cấu trúc Overlays: Ví dụ M0 80K M1 80K M11 120K Bộ nhớ trong 32 / 92
M2 M12 M1 Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.4 Các cấu trúc chương trình Cấu trúc Overlays: Ví dụ M0 80K M1 80K M11 120K M11 Bộ nhớ trong 32 / 92
M2 M11 MM111 Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.4 Các cấu trúc chương trình Cấu trúc Overlays: Ví dụ M0 80K M1 80K M12 120K Bộ nhớ trong 32 / 92
M2 M11 M11 Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.4 Các cấu trúc chương trình Cấu trúc Overlays: Ví dụ M0 80K M1 80K M12 120K M1 Bộ nhớ trong 32 / 92
M11 MM111 Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.4 Các cấu trúc chương trình Cấu trúc Overlays: Ví dụ M0 80K M1 M2 80K M12 120K Bộ nhớ trong 32 / 92
Yêu cầu người sử dụng cung cấp các thông tin phụ Hiệu quả sử dụng phụ thuộc vào các thông tin được cung cấp Hiệu quả sử dụng bộ nhớ phụ thuộc cách tổ chức các modul trong chương trình Nếu tồn tại một modul có kích thước lớn hơn các modul khác cùng mức rất nhiều ⇒Hiệu quả giảm rõ rệt Quá trình nạp các modul là động, nhưng chương trình có tính chất tĩnh ⇒Không thay đổi trong các lần thực hiện Cung cấp thêm bộ nhớ tự do, hiệu quả vẫn không đổi Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.4 Các cấu trúc chương trình Cấu trúc Overlays: Nhận xét Cho phép dùng chương trình có kích thước lớn hơn kích thước hệ điều hành danh cho 33 / 92
Hiệu quả sử dụng bộ nhớ phụ thuộc cách tổ chức các modul trong chương trình Nếu tồn tại một modul có kích thước lớn hơn các modul khác cùng mức rất nhiều ⇒Hiệu quả giảm rõ rệt Quá trình nạp các modul là động, nhưng chương trình có tính chất tĩnh ⇒Không thay đổi trong các lần thực hiện Cung cấp thêm bộ nhớ tự do, hiệu quả vẫn không đổi Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.4 Các cấu trúc chương trình Cấu trúc Overlays: Nhận xét Cho phép dùng chương trình có kích thước lớn hơn kích thước hệ điều hành danh cho Yêu cầu người sử dụng cung cấp các thông tin phụ Hiệu quả sử dụng phụ thuộc vào các thông tin được cung cấp 33 / 92
Quá trình nạp các modul là động, nhưng chương trình có tính chất tĩnh ⇒Không thay đổi trong các lần thực hiện Cung cấp thêm bộ nhớ tự do, hiệu quả vẫn không đổi Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.4 Các cấu trúc chương trình Cấu trúc Overlays: Nhận xét Cho phép dùng chương trình có kích thước lớn hơn kích thước hệ điều hành danh cho Yêu cầu người sử dụng cung cấp các thông tin phụ Hiệu quả sử dụng phụ thuộc vào các thông tin được cung cấp Hiệu quả sử dụng bộ nhớ phụ thuộc cách tổ chức các modul trong chương trình Nếu tồn tại một modul có kích thước lớn hơn các modul khác cùng mức rất nhiều ⇒Hiệu quả giảm rõ rệt 33 / 92
Cung cấp thêm bộ nhớ tự do, hiệu quả vẫn không đổi Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.4 Các cấu trúc chương trình Cấu trúc Overlays: Nhận xét Cho phép dùng chương trình có kích thước lớn hơn kích thước hệ điều hành danh cho Yêu cầu người sử dụng cung cấp các thông tin phụ Hiệu quả sử dụng phụ thuộc vào các thông tin được cung cấp Hiệu quả sử dụng bộ nhớ phụ thuộc cách tổ chức các modul trong chương trình Nếu tồn tại một modul có kích thước lớn hơn các modul khác cùng mức rất nhiều ⇒Hiệu quả giảm rõ rệt Quá trình nạp các modul là động, nhưng chương trình có tính chất tĩnh ⇒Không thay đổi trong các lần thực hiện 33 / 92
Chương 3: Quản lý bộ nhớ 1. Tổng quan 1.4 Các cấu trúc chương trình Cấu trúc Overlays: Nhận xét Cho phép dùng chương trình có kích thước lớn hơn kích thước hệ điều hành danh cho Yêu cầu người sử dụng cung cấp các thông tin phụ Hiệu quả sử dụng phụ thuộc vào các thông tin được cung cấp Hiệu quả sử dụng bộ nhớ phụ thuộc cách tổ chức các modul trong chương trình Nếu tồn tại một modul có kích thước lớn hơn các modul khác cùng mức rất nhiều ⇒Hiệu quả giảm rõ rệt Quá trình nạp các modul là động, nhưng chương trình có tính chất tĩnh ⇒Không thay đổi trong các lần thực hiện Cung cấp thêm bộ nhớ tự do, hiệu quả vẫn không đổi 33 / 92
Chương 3: Quản lý bộ nhớ 1. Tổng quan Kết luận 34 / 92
Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ Nội dung chính 1 Tổng quan 2 Các chiến lược quản lý bộ nhớ 3 Bộ nhớ ảo 35 / 92
Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.1 Chiến lược phân chương cố định 2 Các chiến lược quản lý bộ nhớ Chiến lược phân chương cố định Chiến lược phân chương động Chiến lược phân đoạn Chiến lược phân trang Chiến lược kết hợp phân đoạn-phân trang 36 / 92
Ví dụ: Xét hệ thống: 0 Hệ điều hành Process Size time 150 P1 120 20 Chương 1 P2 80 15 300 P3 70 5 Chương 2 P4 50 5 P5 140 12 500 Hàng đợi Chương 3 600 Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.1 Chiến lược phân chương cố định Nguyên tắc Bộ nhớ được chia thành n phần Mỗi phần gọi là một chương (partition) Chương không nhất thiết có kích thước bằng nhau Chương được sử dụng như một vùng nhớ độc lập Tại một thời điểm chỉ cho phép một chương trình tồn tại Các chương trình nằm trong vùng nhớ cho tới khi kết thúc 37 / 92
Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.1 Chiến lược phân chương cố định Nguyên tắc Bộ nhớ được chia thành n phần Mỗi phần gọi là một chương (partition) Chương không nhất thiết có kích thước bằng nhau Chương được sử dụng như một vùng nhớ độc lập Tại một thời điểm chỉ cho phép một chương trình tồn tại Các chương trình nằm trong vùng nhớ cho tới khi kết thúc Ví dụ: Xét hệ thống: 0 Hệ điều hành Process Size time 150 P1 120 20 Chương 1 P2 80 15 300 P3 70 5 Chương 2 P4 50 5 P5 140 12 500 Hàng đợi Chương 3 600 37 / 92
Giảm thời gian tìm kiếm Phải sao các modul điều khiển ra làm nhiều bản và lưu ở nhiều nơi Hệ số song song không thể vượt quá n Bị phân đoạn bộ nhớ Kích thước chương trình lớn hơn kích thước chương lớn nhất Tổng bộ nhớ tự do còn lớn, nhưng không dùng để nạp các chương trình khác ⇒Sửa lại cấu trúc chương, kết hợp một số chương kề nhau Áp dụng Thường dùng cho quản lý các đĩa dung lượng lớn Hệ điều hành OS/360 của IBM Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.1 Chiến lược phân chương cố định Nhận xét Đơn giản, dễ tổ chức bảo vệ Chương trình và vùng nhớ có một khóa bảo vệ So sánh 2 khóa với nhau khi nạp chương trình 38 / 92
Phải sao các modul điều khiển ra làm nhiều bản và lưu ở nhiều nơi Hệ số song song không thể vượt quá n Bị phân đoạn bộ nhớ Kích thước chương trình lớn hơn kích thước chương lớn nhất Tổng bộ nhớ tự do còn lớn, nhưng không dùng để nạp các chương trình khác ⇒Sửa lại cấu trúc chương, kết hợp một số chương kề nhau Áp dụng Thường dùng cho quản lý các đĩa dung lượng lớn Hệ điều hành OS/360 của IBM Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.1 Chiến lược phân chương cố định Nhận xét Đơn giản, dễ tổ chức bảo vệ Chương trình và vùng nhớ có một khóa bảo vệ So sánh 2 khóa với nhau khi nạp chương trình Giảm thời gian tìm kiếm 38 / 92
Hệ số song song không thể vượt quá n Bị phân đoạn bộ nhớ Kích thước chương trình lớn hơn kích thước chương lớn nhất Tổng bộ nhớ tự do còn lớn, nhưng không dùng để nạp các chương trình khác ⇒Sửa lại cấu trúc chương, kết hợp một số chương kề nhau Áp dụng Thường dùng cho quản lý các đĩa dung lượng lớn Hệ điều hành OS/360 của IBM Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.1 Chiến lược phân chương cố định Nhận xét Đơn giản, dễ tổ chức bảo vệ Chương trình và vùng nhớ có một khóa bảo vệ So sánh 2 khóa với nhau khi nạp chương trình Giảm thời gian tìm kiếm Phải sao các modul điều khiển ra làm nhiều bản và lưu ở nhiều nơi 38 / 92
Bị phân đoạn bộ nhớ Kích thước chương trình lớn hơn kích thước chương lớn nhất Tổng bộ nhớ tự do còn lớn, nhưng không dùng để nạp các chương trình khác ⇒Sửa lại cấu trúc chương, kết hợp một số chương kề nhau Áp dụng Thường dùng cho quản lý các đĩa dung lượng lớn Hệ điều hành OS/360 của IBM Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.1 Chiến lược phân chương cố định Nhận xét Đơn giản, dễ tổ chức bảo vệ Chương trình và vùng nhớ có một khóa bảo vệ So sánh 2 khóa với nhau khi nạp chương trình Giảm thời gian tìm kiếm Phải sao các modul điều khiển ra làm nhiều bản và lưu ở nhiều nơi Hệ số song song không thể vượt quá n 38 / 92
Áp dụng Thường dùng cho quản lý các đĩa dung lượng lớn Hệ điều hành OS/360 của IBM Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.1 Chiến lược phân chương cố định Nhận xét Đơn giản, dễ tổ chức bảo vệ Chương trình và vùng nhớ có một khóa bảo vệ So sánh 2 khóa với nhau khi nạp chương trình Giảm thời gian tìm kiếm Phải sao các modul điều khiển ra làm nhiều bản và lưu ở nhiều nơi Hệ số song song không thể vượt quá n Bị phân đoạn bộ nhớ Kích thước chương trình lớn hơn kích thước chương lớn nhất Tổng bộ nhớ tự do còn lớn, nhưng không dùng để nạp các chương trình khác ⇒Sửa lại cấu trúc chương, kết hợp một số chương kề nhau 38 / 92
Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.1 Chiến lược phân chương cố định Nhận xét Đơn giản, dễ tổ chức bảo vệ Chương trình và vùng nhớ có một khóa bảo vệ So sánh 2 khóa với nhau khi nạp chương trình Giảm thời gian tìm kiếm Phải sao các modul điều khiển ra làm nhiều bản và lưu ở nhiều nơi Hệ số song song không thể vượt quá n Bị phân đoạn bộ nhớ Kích thước chương trình lớn hơn kích thước chương lớn nhất Tổng bộ nhớ tự do còn lớn, nhưng không dùng để nạp các chương trình khác ⇒Sửa lại cấu trúc chương, kết hợp một số chương kề nhau Áp dụng Thường dùng cho quản lý các đĩa dung lượng lớn Hệ điều hành OS/360 của IBM 38 / 92
Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.2 Chiến lược phân chương động 2 Các chiến lược quản lý bộ nhớ Chiến lược phân chương cố định Chiến lược phân chương động Chiến lược phân đoạn Chiến lược phân trang Chiến lược kết hợp phân đoạn-phân trang 39 / 92
Khi một tiến trình yêu cầu bộ nhớ Tìm trong DS vùng trống một phần tử đủ lớn cho yêu cầu Nếu tìm thấy Vùng trống được chia thành 2 phần Một phần cung cấp theo uêu cầu Một phần trả lại danh sách vùng trống tự do Nếu không tìm thấy Phải chờ tới khi có được một vùng trống thỏa mãn Cho phép tiến trình khác trong hàng đợi thực hiện (nếu độ ưu tiên đảm bảo) Khi một tiến trình kết thúc Vùng nhớ chiếm được trả về DS quản lý vùng trống tự do Kết hợp với các vùng trống khác liên kề nếu cần thiết Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.2 Chiến lược phân chương động Nguyên tắc Chỉ có một danh sách quản lý bộ nhớ tự do Thời điểm ban đầu toàn bộ bộ nhớ là tự do với các tiến trình ⇒ vùng trống lớn nhất (hole) 40 / 92
Khi một tiến trình kết thúc Vùng nhớ chiếm được trả về DS quản lý vùng trống tự do Kết hợp với các vùng trống khác liên kề nếu cần thiết Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.2 Chiến lược phân chương động Nguyên tắc Chỉ có một danh sách quản lý bộ nhớ tự do Thời điểm ban đầu toàn bộ bộ nhớ là tự do với các tiến trình ⇒ vùng trống lớn nhất (hole) Khi một tiến trình yêu cầu bộ nhớ Tìm trong DS vùng trống một phần tử đủ lớn cho yêu cầu Nếu tìm thấy Vùng trống được chia thành 2 phần Một phần cung cấp theo uêu cầu Một phần trả lại danh sách vùng trống tự do Nếu không tìm thấy Phải chờ tới khi có được một vùng trống thỏa mãn Cho phép tiến trình khác trong hàng đợi thực hiện (nếu độ ưu tiên đảm bảo) 40 / 92
Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.2 Chiến lược phân chương động Nguyên tắc Chỉ có một danh sách quản lý bộ nhớ tự do Thời điểm ban đầu toàn bộ bộ nhớ là tự do với các tiến trình ⇒ vùng trống lớn nhất (hole) Khi một tiến trình yêu cầu bộ nhớ Tìm trong DS vùng trống một phần tử đủ lớn cho yêu cầu Nếu tìm thấy Vùng trống được chia thành 2 phần Một phần cung cấp theo uêu cầu Một phần trả lại danh sách vùng trống tự do Nếu không tìm thấy Phải chờ tới khi có được một vùng trống thỏa mãn Cho phép tiến trình khác trong hàng đợi thực hiện (nếu độ ưu tiên đảm bảo) Khi một tiến trình kết thúc Vùng nhớ chiếm được trả về DS quản lý vùng trống tự do Kết hợp với các vùng trống khác liên kề nếu cần thiết 40 / 92
Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.2 Chiến lược phân chương động Ví dụ 0 0 Hệ điều hành Hệ điều hành 400 400 Process Size time P1 600 10 P2 1000 5 P3 300 20 P4 700 8 P5 500 15 File đợi Vùng trống tự do ? 2560 2560 41 / 92
Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.2 Chiến lược phân chương động Chiến lược lựa chọn vùng trống tự do Có nhiều chiến lược lựa chọn vùng trống cho yêu cầu First Fit : Vùng trống đầu tiên thỏa mãn Best Fit : Vùng trống vừa vặn nhất Worst Fit : Vùng trống kích thước lớn nhất 42 / 92
Cung cấp cho yêu cầu n bytes 2K1K bytes Chia vùng trống tìm được thành 2 khối 4K1K bytes 2K bytes bằng nhau (gọi là buddies) 8K bytes Tiếp tục chia vùng trống phía trên thành 4K bytes 2 phần cho tới khi đạt vùng trống nhỏ nhất kích thước lớn hơn n 16K Ví dụ Vùng trống 16K Bytes 8K bytes Yêu cầu 735 Bytes Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.2 Chiến lược phân chương động Buddy Allocation: Cung cấp nhớ Nguyên tắc: Chia đôi liên tiếp vùng trống tự do cho tới khi thu được vùng trống nhỏ nhất thỏa mãn 43 / 92
2K1K bytes 4K1K bytes 2K bytes 8K bytes 4K bytes 16K Ví dụ Vùng trống 16K Bytes 8K bytes Yêu cầu 735 Bytes Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.2 Chiến lược phân chương động Buddy Allocation: Cung cấp nhớ Nguyên tắc: Chia đôi liên tiếp vùng trống tự do cho tới khi thu được vùng trống nhỏ nhất thỏa mãn Cung cấp cho yêu cầu n bytes Chia vùng trống tìm được thành 2 khối bằng nhau (gọi là buddies) Tiếp tục chia vùng trống phía trên thành 2 phần cho tới khi đạt vùng trống nhỏ nhất kích thước lớn hơn n 43 / 92
2K1K bytes 4K1K bytes 2K bytes 8K bytes 4K bytes 8K bytes Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.2 Chiến lược phân chương động Buddy Allocation: Cung cấp nhớ Nguyên tắc: Chia đôi liên tiếp vùng trống tự do cho tới khi thu được vùng trống nhỏ nhất thỏa mãn Cung cấp cho yêu cầu n bytes Chia vùng trống tìm được thành 2 khối bằng nhau (gọi là buddies) Tiếp tục chia vùng trống phía trên thành 2 phần cho tới khi đạt vùng trống nhỏ nhất kích thước lớn hơn n 16K Ví dụ Vùng trống 16K Bytes Yêu cầu 735 Bytes 43 / 92
2K1K bytes 4K1K bytes 2K bytes 4K bytes 16K Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.2 Chiến lược phân chương động Buddy Allocation: Cung cấp nhớ Nguyên tắc: Chia đôi liên tiếp vùng trống tự do cho tới khi thu được vùng trống nhỏ nhất thỏa mãn Cung cấp cho yêu cầu n bytes Chia vùng trống tìm được thành 2 khối bằng nhau (gọi là buddies) 8K bytes Tiếp tục chia vùng trống phía trên thành 2 phần cho tới khi đạt vùng trống nhỏ nhất kích thước lớn hơn n Ví dụ Vùng trống 16K Bytes 8K bytes Yêu cầu 735 Bytes 43 / 92
1K bytes 2K1K bytes 2K bytes 8K bytes 16K Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.2 Chiến lược phân chương động Buddy Allocation: Cung cấp nhớ Nguyên tắc: Chia đôi liên tiếp vùng trống tự do cho tới khi thu được vùng trống nhỏ nhất thỏa mãn Cung cấp cho yêu cầu n bytes Chia vùng trống tìm được thành 2 khối 4K bytes bằng nhau (gọi là buddies) Tiếp tục chia vùng trống phía trên thành 4K bytes 2 phần cho tới khi đạt vùng trống nhỏ nhất kích thước lớn hơn n Ví dụ Vùng trống 16K Bytes 8K bytes Yêu cầu 735 Bytes 43 / 92
1K bytes 4K1K bytes 8K bytes 16K Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.2 Chiến lược phân chương động Buddy Allocation: Cung cấp nhớ Nguyên tắc: Chia đôi liên tiếp vùng trống tự do cho tới khi thu được vùng trống nhỏ nhất thỏa mãn Cung cấp cho yêu cầu n bytes 2K bytes Chia vùng trống tìm được thành 2 khối bằng nhau (gọi là buddies) 2K bytes Tiếp tục chia vùng trống phía trên thành 4K bytes 2 phần cho tới khi đạt vùng trống nhỏ nhất kích thước lớn hơn n Ví dụ Vùng trống 16K Bytes 8K bytes Yêu cầu 735 Bytes 43 / 92
2K1K bytes 4K bytes 8K bytes 16K Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.2 Chiến lược phân chương động Buddy Allocation: Cung cấp nhớ Nguyên tắc: Chia đôi liên tiếp vùng trống tự do cho tới khi thu được vùng trống nhỏ nhất thỏa mãn Cung cấp cho yêu cầu n bytes 1K bytes Chia vùng trống tìm được thành 2 khối 1K bytes bằng nhau (gọi là buddies) 2K bytes Tiếp tục chia vùng trống phía trên thành 4K bytes 2 phần cho tới khi đạt vùng trống nhỏ nhất kích thước lớn hơn n Ví dụ Vùng trống 16K Bytes 8K bytes Yêu cầu 735 Bytes 43 / 92
2K bytes 4K bytes 8K bytes 16K Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.2 Chiến lược phân chương động Buddy Allocation: Cung cấp nhớ Nguyên tắc: Chia đôi liên tiếp vùng trống tự do cho tới khi thu được vùng trống nhỏ nhất thỏa mãn Cung cấp cho yêu cầu n bytes 1K bytes Chia vùng trống tìm được thành 2 khối 1K bytes bằng nhau (gọi là buddies) 2K bytes Tiếp tục chia vùng trống phía trên thành 4K bytes 2 phần cho tới khi đạt vùng trống nhỏ nhất kích thước lớn hơn n Ví dụ Vùng trống 16K Bytes 8K bytes Yêu cầu 735 Bytes 43 / 92
1K bytes 1K bytes 2K2K bytes 2K bytes 4K bytes 2K bytes 16K Ví dụ bộ nhớ 16K bytes 8K bytes Yêu cầu 735 bytes Yêu cầu 1205 bytes Yêu cầu 2010 bytes Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.2 Chiến lược phân chương động Buddy Allocation: Cung cấp nhớ nhanh Hệ thống duy trì các danh sách vùng trống kích thước 1, 2, , 2n bytes Với yêu cầu K, tìm phần tử nhỏ nhất kích thước lớn hơn K Nếu phần tử nhỏ nhất lớn hơn 2K, chia liên tiếp tới khi được vùng nhỏ nhất kích thước lớn hơn K Nhận xét: Với bộ nhớ kích thước n, cần duyệt log2n danh sách ⇒ Nhanh 44 / 92
1K bytes 1K bytes 2K2K bytes 2K bytes 4K bytes 2K bytes 8K bytes Yêu cầu 735 bytes Yêu cầu 1205 bytes Yêu cầu 2010 bytes Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.2 Chiến lược phân chương động Buddy Allocation: Cung cấp nhớ nhanh Hệ thống duy trì các danh sách vùng trống kích thước 1, 2, , 2n bytes Với yêu cầu K, tìm phần tử nhỏ nhất kích thước lớn hơn K Nếu phần tử nhỏ nhất lớn hơn 2K, chia liên tiếp tới khi được vùng nhỏ nhất kích thước lớn hơn K 16K Nhận xét: Với bộ nhớ kích thước n, cần duyệt log2n danh sách ⇒ Nhanh Ví dụ bộ nhớ 16K bytes 44 / 92
2K bytes 2K bytes 2K bytes 16K Yêu cầu 1205 bytes Yêu cầu 2010 bytes Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.2 Chiến lược phân chương động Buddy Allocation: Cung cấp nhớ nhanh Hệ thống duy trì các danh sách vùng trống kích thước 1, 2, , 2n bytes 1K bytes 1K bytes Với yêu cầu K, tìm phần tử nhỏ nhất kích thước lớn hơn K 2K bytes Nếu phần tử nhỏ nhất lớn hơn 2K, chia liên tiếp tới khi được vùng nhỏ nhất kích 4K bytes thước lớn hơn K Nhận xét: Với bộ nhớ kích thước n, cần duyệt log2n danh sách ⇒ Nhanh Ví dụ bộ nhớ 16K bytes 8K bytes Yêu cầu 735 bytes 44 / 92
2K bytes 2K bytes 16K Yêu cầu 2010 bytes Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.2 Chiến lược phân chương động Buddy Allocation: Cung cấp nhớ nhanh Hệ thống duy trì các danh sách vùng trống kích thước 1, 2, , 2n bytes 1K bytes 1K bytes Với yêu cầu K, tìm phần tử nhỏ nhất kích thước lớn hơn K 2K2K bytes Nếu phần tử nhỏ nhất lớn hơn 2K, chia liên tiếp tới khi được vùng nhỏ nhất kích 4K bytes thước lớn hơn K Nhận xét: Với bộ nhớ kích thước n, cần duyệt log2n danh sách ⇒ Nhanh Ví dụ bộ nhớ 16K bytes 8K bytes Yêu cầu 735 bytes Yêu cầu 1205 bytes 44 / 92
16K Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.2 Chiến lược phân chương động Buddy Allocation: Cung cấp nhớ nhanh Hệ thống duy trì các danh sách vùng trống kích thước 1, 2, , 2n bytes 1K bytes 1K bytes Với yêu cầu K, tìm phần tử nhỏ nhất kích thước lớn hơn K 2K2K bytes Nếu phần tử nhỏ nhất lớn hơn 2K, chia 2K bytes liên tiếp tới khi được vùng nhỏ nhất kích 4K bytes thước lớn hơn K 2K bytes Nhận xét: Với bộ nhớ kích thước n, cần duyệt log2n danh sách ⇒ Nhanh Ví dụ bộ nhớ 16K bytes 8K bytes Yêu cầu 735 bytes Yêu cầu 1205 bytes Yêu cầu 2010 bytes 44 / 92
Kết hợp 2 vùng 1K thành vùng 2K Kết hợp 2 vùng 2K thành vùng 4K Kết hợp 2 vùng 2K thành vùng 4K Kết hợp 2 vùng 4K thành vùng 8K Kết hợp 2 vùng 8K thành vùng 16K 1K bytes 2K bytes 1K bytes 4K bytes 2K bytes 8K bytes Ví dụ 2K bytes 4K bytes Giải phóng vùng nhớ thứ nhất (1K) 2K bytes 16K Giải phóng vùng nhớ thứ hai (2K) Giải phóng vùng nhớ thứ ba (2K) 8K bytes Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.2 Chiến lược phân chương động Buddy Allocation : Thu hồi vùng nhớ Có thể kết hợp 2 vùng kề nhau có cùng kích thước Tiếp tục kết hợp liên tiếp cho tới khi tạo ra vùng trống lớn nhất có thể 45 / 92
Kết hợp 2 vùng 1K thành vùng 2K Kết hợp 2 vùng 2K thành vùng 4K Kết hợp 2 vùng 2K thành vùng 4K Kết hợp 2 vùng 4K thành vùng 8K Kết hợp 2 vùng 8K thành vùng 16K 1K bytes 2K bytes 4K bytes 2K bytes 8K bytes 2K bytes 4K bytes Giải phóng vùng nhớ thứ nhất (1K) 16K Giải phóng vùng nhớ thứ hai (2K) Giải phóng vùng nhớ thứ ba (2K) Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.2 Chiến lược phân chương động Buddy Allocation : Thu hồi vùng nhớ Có thể kết hợp 2 vùng kề nhau có cùng 1K bytes kích thước 1K bytes Tiếp tục kết hợp liên tiếp cho tới khi tạo 2K bytes ra vùng trống lớn nhất có thể Ví dụ 2K bytes 2K bytes 8K bytes 45 / 92
Kết hợp 2 vùng 2K thành vùng 4K Kết hợp 2 vùng 2K thành vùng 4K Kết hợp 2 vùng 4K thành vùng 8K Kết hợp 2 vùng 8K thành vùng 16K 1K bytes 2K bytes 4K bytes 2K bytes 8K bytes 2K bytes 4K bytes Kết hợp 2 vùng 1K thành vùng 2K 16K Giải phóng vùng nhớ thứ hai (2K) Giải phóng vùng nhớ thứ ba (2K) Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.2 Chiến lược phân chương động Buddy Allocation : Thu hồi vùng nhớ Có thể kết hợp 2 vùng kề nhau có cùng 1K bytes kích thước 1K bytes Tiếp tục kết hợp liên tiếp cho tới khi tạo 2K bytes ra vùng trống lớn nhất có thể Ví dụ 2K bytes Giải phóng vùng nhớ thứ nhất (1K) 2K bytes 8K bytes 45 / 92
Kết hợp 2 vùng 2K thành vùng 4K Kết hợp 2 vùng 2K thành vùng 4K Kết hợp 2 vùng 4K thành vùng 8K Kết hợp 2 vùng 8K thành vùng 16K 1K bytes 1K bytes 4K bytes 2K bytes 8K bytes 2K bytes 4K bytes 16K Giải phóng vùng nhớ thứ hai (2K) Giải phóng vùng nhớ thứ ba (2K) Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.2 Chiến lược phân chương động Buddy Allocation : Thu hồi vùng nhớ Có thể kết hợp 2 vùng kề nhau có cùng kích thước 2K bytes Tiếp tục kết hợp liên tiếp cho tới khi tạo 2K bytes ra vùng trống lớn nhất có thể Ví dụ 2K bytes Giải phóng vùng nhớ thứ nhất (1K) 2K bytes Kết hợp 2 vùng 1K thành vùng 2K 8K bytes 45 / 92
Kết hợp 2 vùng 2K thành vùng 4K Kết hợp 2 vùng 4K thành vùng 8K Kết hợp 2 vùng 8K thành vùng 16K 1K bytes 1K bytes 4K bytes 2K bytes 8K bytes 2K bytes 4K bytes 16K Kết hợp 2 vùng 2K thành vùng 4K Giải phóng vùng nhớ thứ ba (2K) Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.2 Chiến lược phân chương động Buddy Allocation : Thu hồi vùng nhớ Có thể kết hợp 2 vùng kề nhau có cùng kích thước 2K bytes Tiếp tục kết hợp liên tiếp cho tới khi tạo 2K bytes ra vùng trống lớn nhất có thể Ví dụ 2K bytes Giải phóng vùng nhớ thứ nhất (1K) 2K bytes Kết hợp 2 vùng 1K thành vùng 2K Giải phóng vùng nhớ thứ hai (2K) 8K bytes 45 / 92
Kết hợp 2 vùng 2K thành vùng 4K Kết hợp 2 vùng 4K thành vùng 8K Kết hợp 2 vùng 8K thành vùng 16K 1K bytes 2K bytes 1K bytes 2K bytes 8K bytes 2K bytes 4K bytes 16K Giải phóng vùng nhớ thứ ba (2K) Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.2 Chiến lược phân chương động Buddy Allocation : Thu hồi vùng nhớ Có thể kết hợp 2 vùng kề nhau có cùng kích thước 4K bytes Tiếp tục kết hợp liên tiếp cho tới khi tạo ra vùng trống lớn nhất có thể Ví dụ 2K bytes Giải phóng vùng nhớ thứ nhất (1K) 2K bytes Kết hợp 2 vùng 1K thành vùng 2K Giải phóng vùng nhớ thứ hai (2K) Kết hợp 2 vùng 2K thành vùng 4K 8K bytes 45 / 92
1K bytes 2K bytes 1K bytes 2K bytes 8K bytes 2K bytes 4K bytes 16K Kết hợp 2 vùng 2K thành vùng 4K Kết hợp 2 vùng 4K thành vùng 8K Kết hợp 2 vùng 8K thành vùng 16K Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.2 Chiến lược phân chương động Buddy Allocation : Thu hồi vùng nhớ Có thể kết hợp 2 vùng kề nhau có cùng kích thước 4K bytes Tiếp tục kết hợp liên tiếp cho tới khi tạo ra vùng trống lớn nhất có thể Ví dụ 2K bytes Giải phóng vùng nhớ thứ nhất (1K) 2K bytes Kết hợp 2 vùng 1K thành vùng 2K Giải phóng vùng nhớ thứ hai (2K) Kết hợp 2 vùng 2K thành vùng 4K Giải phóng vùng nhớ thứ ba (2K) 8K bytes 45 / 92
1K bytes 2K bytes 1K bytes 2K bytes 8K bytes 2K bytes 2K bytes 16K Kết hợp 2 vùng 4K thành vùng 8K Kết hợp 2 vùng 8K thành vùng 16K Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.2 Chiến lược phân chương động Buddy Allocation : Thu hồi vùng nhớ Có thể kết hợp 2 vùng kề nhau có cùng kích thước 4K bytes Tiếp tục kết hợp liên tiếp cho tới khi tạo ra vùng trống lớn nhất có thể Ví dụ 4K bytes Giải phóng vùng nhớ thứ nhất (1K) Kết hợp 2 vùng 1K thành vùng 2K Giải phóng vùng nhớ thứ hai (2K) Kết hợp 2 vùng 2K thành vùng 4K Giải phóng vùng nhớ thứ ba (2K) 8K bytes Kết hợp 2 vùng 2K thành vùng 4K 45 / 92
1K bytes 2K bytes 1K bytes 4K bytes 2K bytes 2K bytes 4K bytes 2K bytes 16K Kết hợp 2 vùng 8K thành vùng 16K Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.2 Chiến lược phân chương động Buddy Allocation : Thu hồi vùng nhớ Có thể kết hợp 2 vùng kề nhau có cùng kích thước Tiếp tục kết hợp liên tiếp cho tới khi tạo ra vùng trống lớn nhất có thể 8K bytes Ví dụ Giải phóng vùng nhớ thứ nhất (1K) Kết hợp 2 vùng 1K thành vùng 2K Giải phóng vùng nhớ thứ hai (2K) Kết hợp 2 vùng 2K thành vùng 4K Giải phóng vùng nhớ thứ ba (2K) 8K bytes Kết hợp 2 vùng 2K thành vùng 4K Kết hợp 2 vùng 4K thành vùng 8K 45 / 92
1K bytes 2K bytes 1K bytes 4K bytes 2K bytes 8K bytes 2K bytes 4K bytes 2K bytes 8K bytes Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.2 Chiến lược phân chương động Buddy Allocation : Thu hồi vùng nhớ Có thể kết hợp 2 vùng kề nhau có cùng kích thước Tiếp tục kết hợp liên tiếp cho tới khi tạo ra vùng trống lớn nhất có thể Ví dụ Giải phóng vùng nhớ thứ nhất (1K) Kết hợp 2 vùng 1K thành vùng 2K 16K Giải phóng vùng nhớ thứ hai (2K) Kết hợp 2 vùng 2K thành vùng 4K Giải phóng vùng nhớ thứ ba (2K) Kết hợp 2 vùng 2K thành vùng 4K Kết hợp 2 vùng 4K thành vùng 8K Kết hợp 2 vùng 8K thành vùng 16K 45 / 92
Dịch chuyển các tiến trình Vấn đề không đơn giản vì các đối tượng bên trong khi chuyển sang vị trí mới sẽ mang địa chỉ khác đi Sử dụng thanh ghi dịch chuyển (relocation register) chứa giá trị bằng độ dịch chuyển của tiến trình Vấn đề lựa chọn phương pháp để chi phí nhỏ nhất Dịch chuyển tất cả về một phía ⇒ vùng trống lớn nhất Dịch chuyển để tạo ra ngay lập tức một vùng trống vừa vặn Phương pháp tráo đổi (swapping) Lựa chọn thời điểm dừng tiến trình đang thực hiện Đưa tiến trình và trạng thái tương ứng ra bên ngoài Giải phóng vùng nhớ để kết hợp với các phần tử liền kề Tái định vị vào vị trí cũ và khôi phục trạng thái cũ Dùng thanh ghi dịch chuyển nếu đưa vào vị trí khác Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.2 Chiến lược phân chương động Vấn đề bố trí lại bộ nhớ Sau một thời gian hoạt động, các vùng trống nằm rải rác khắp nơi gây ra hiện tượng thiếu bộ nhớ. ⇒Cần phải bố trí lại bộ nhớ 46 / 92
Phương pháp tráo đổi (swapping) Lựa chọn thời điểm dừng tiến trình đang thực hiện Đưa tiến trình và trạng thái tương ứng ra bên ngoài Giải phóng vùng nhớ để kết hợp với các phần tử liền kề Tái định vị vào vị trí cũ và khôi phục trạng thái cũ Dùng thanh ghi dịch chuyển nếu đưa vào vị trí khác Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.2 Chiến lược phân chương động Vấn đề bố trí lại bộ nhớ Sau một thời gian hoạt động, các vùng trống nằm rải rác khắp nơi gây ra hiện tượng thiếu bộ nhớ. ⇒Cần phải bố trí lại bộ nhớ Dịch chuyển các tiến trình Vấn đề không đơn giản vì các đối tượng bên trong khi chuyển sang vị trí mới sẽ mang địa chỉ khác đi Sử dụng thanh ghi dịch chuyển (relocation register) chứa giá trị bằng độ dịch chuyển của tiến trình Vấn đề lựa chọn phương pháp để chi phí nhỏ nhất Dịch chuyển tất cả về một phía ⇒ vùng trống lớn nhất Dịch chuyển để tạo ra ngay lập tức một vùng trống vừa vặn 46 / 92
Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.2 Chiến lược phân chương động Vấn đề bố trí lại bộ nhớ Sau một thời gian hoạt động, các vùng trống nằm rải rác khắp nơi gây ra hiện tượng thiếu bộ nhớ. ⇒Cần phải bố trí lại bộ nhớ Dịch chuyển các tiến trình Vấn đề không đơn giản vì các đối tượng bên trong khi chuyển sang vị trí mới sẽ mang địa chỉ khác đi Sử dụng thanh ghi dịch chuyển (relocation register) chứa giá trị bằng độ dịch chuyển của tiến trình Vấn đề lựa chọn phương pháp để chi phí nhỏ nhất Dịch chuyển tất cả về một phía ⇒ vùng trống lớn nhất Dịch chuyển để tạo ra ngay lập tức một vùng trống vừa vặn Phương pháp tráo đổi (swapping) Lựa chọn thời điểm dừng tiến trình đang thực hiện Đưa tiến trình và trạng thái tương ứng ra bên ngoài Giải phóng vùng nhớ để kết hợp với các phần tử liền kề Tái định vị vào vị trí cũ và khôi phục trạng thái cũ Dùng thanh ghi dịch chuyển nếu đưa vào vị trí khác 46 / 92
Tăng/giảm hệ số song song tùy theo số lượng và kích thước chương trình Không thực hiện được chương trình có kích thước lớn hơn kích thước bộ nhớ vật lý Gây ra hiện tượng rác Bộ nhớ không được sử dụng, nhưng cũng không nằm trong DS quản lý bộ nhớ tự do Do lỗi hệ điều hành Do phần mềm phá hoại Gây ra hiện tượng phân đoạn ngoài Vùng nhớ tự do được quản lý đầy đủ, nhưng nằm rải rác nên không sử dụng được Gây ra hiện tượng phân đoạn trong Vùng nhớ dành cho chương trình nhưng không được chương trình sử dụng tới Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.2 Chiến lược phân chương động Nhận xét Không phải sao lưu modul điều khiển ra nhiều nơi 47 / 92
Không thực hiện được chương trình có kích thước lớn hơn kích thước bộ nhớ vật lý Gây ra hiện tượng rác Bộ nhớ không được sử dụng, nhưng cũng không nằm trong DS quản lý bộ nhớ tự do Do lỗi hệ điều hành Do phần mềm phá hoại Gây ra hiện tượng phân đoạn ngoài Vùng nhớ tự do được quản lý đầy đủ, nhưng nằm rải rác nên không sử dụng được Gây ra hiện tượng phân đoạn trong Vùng nhớ dành cho chương trình nhưng không được chương trình sử dụng tới Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.2 Chiến lược phân chương động Nhận xét Không phải sao lưu modul điều khiển ra nhiều nơi Tăng/giảm hệ số song song tùy theo số lượng và kích thước chương trình 47 / 92
Gây ra hiện tượng rác Bộ nhớ không được sử dụng, nhưng cũng không nằm trong DS quản lý bộ nhớ tự do Do lỗi hệ điều hành Do phần mềm phá hoại Gây ra hiện tượng phân đoạn ngoài Vùng nhớ tự do được quản lý đầy đủ, nhưng nằm rải rác nên không sử dụng được Gây ra hiện tượng phân đoạn trong Vùng nhớ dành cho chương trình nhưng không được chương trình sử dụng tới Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.2 Chiến lược phân chương động Nhận xét Không phải sao lưu modul điều khiển ra nhiều nơi Tăng/giảm hệ số song song tùy theo số lượng và kích thước chương trình Không thực hiện được chương trình có kích thước lớn hơn kích thước bộ nhớ vật lý 47 / 92
Gây ra hiện tượng phân đoạn ngoài Vùng nhớ tự do được quản lý đầy đủ, nhưng nằm rải rác nên không sử dụng được Gây ra hiện tượng phân đoạn trong Vùng nhớ dành cho chương trình nhưng không được chương trình sử dụng tới Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.2 Chiến lược phân chương động Nhận xét Không phải sao lưu modul điều khiển ra nhiều nơi Tăng/giảm hệ số song song tùy theo số lượng và kích thước chương trình Không thực hiện được chương trình có kích thước lớn hơn kích thước bộ nhớ vật lý Gây ra hiện tượng rác Bộ nhớ không được sử dụng, nhưng cũng không nằm trong DS quản lý bộ nhớ tự do Do lỗi hệ điều hành Do phần mềm phá hoại 47 / 92
Gây ra hiện tượng phân đoạn trong Vùng nhớ dành cho chương trình nhưng không được chương trình sử dụng tới Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.2 Chiến lược phân chương động Nhận xét Không phải sao lưu modul điều khiển ra nhiều nơi Tăng/giảm hệ số song song tùy theo số lượng và kích thước chương trình Không thực hiện được chương trình có kích thước lớn hơn kích thước bộ nhớ vật lý Gây ra hiện tượng rác Bộ nhớ không được sử dụng, nhưng cũng không nằm trong DS quản lý bộ nhớ tự do Do lỗi hệ điều hành Do phần mềm phá hoại Gây ra hiện tượng phân đoạn ngoài Vùng nhớ tự do được quản lý đầy đủ, nhưng nằm rải rác nên không sử dụng được 47 / 92
Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.2 Chiến lược phân chương động Nhận xét Không phải sao lưu modul điều khiển ra nhiều nơi Tăng/giảm hệ số song song tùy theo số lượng và kích thước chương trình Không thực hiện được chương trình có kích thước lớn hơn kích thước bộ nhớ vật lý Gây ra hiện tượng rác Bộ nhớ không được sử dụng, nhưng cũng không nằm trong DS quản lý bộ nhớ tự do Do lỗi hệ điều hành Do phần mềm phá hoại Gây ra hiện tượng phân đoạn ngoài Vùng nhớ tự do được quản lý đầy đủ, nhưng nằm rải rác nên không sử dụng được Gây ra hiện tượng phân đoạn trong Vùng nhớ dành cho chương trình nhưng không được chương trình sử dụng tới 47 / 92
Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.3 Chiến lược phân đoạn 2 Các chiến lược quản lý bộ nhớ Chiến lược phân chương cố định Chiến lược phân chương động Chiến lược phân đoạn Chiến lược phân trang Chiến lược kết hợp phân đoạn-phân trang 48 / 92
Các modul, đối tượng trong c/trình được xác định bằng tên Hàm sqrt(), thủ tục printf() x, y, counter, Buffer Các p/tử trong modul được x/định theo độ lệch với vị trí đầu Câu lệnh thư 10 của hàm sqrt() Phần tử thứ 2 của mảng Buffer Chương trình được tổ chức như thế nào trong bộ nhớ? Stack nằm trên hay Data nằm trên trong bộ nhớ? Địa chỉ vật lý các đối tượng ? ⇒Không quan tâm Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.3 Chiến lược phân đoạn Chương trình Chương trình thường gồm các modul Một chương trình chính (main program) Tập các chương trình con Các biến, các cấu trúc dữ liệu, 49 / 92
Các p/tử trong modul được x/định theo độ lệch với vị trí đầu Câu lệnh thư 10 của hàm sqrt() Phần tử thứ 2 của mảng Buffer Chương trình được tổ chức như thế nào trong bộ nhớ? Stack nằm trên hay Data nằm trên trong bộ nhớ? Địa chỉ vật lý các đối tượng ? ⇒Không quan tâm Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.3 Chiến lược phân đoạn Chương trình Chương trình thường gồm các modul Một chương trình chính (main program) Tập các chương trình con Các biến, các cấu trúc dữ liệu, Các modul, đối tượng trong c/trình được xác định bằng tên Hàm sqrt(), thủ tục printf() x, y, counter, Buffer 49 / 92
Chương trình được tổ chức như thế nào trong bộ nhớ? Stack nằm trên hay Data nằm trên trong bộ nhớ? Địa chỉ vật lý các đối tượng ? ⇒Không quan tâm Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.3 Chiến lược phân đoạn Chương trình Chương trình thường gồm các modul Một chương trình chính (main program) Tập các chương trình con Các biến, các cấu trúc dữ liệu, Các modul, đối tượng trong c/trình được xác định bằng tên Hàm sqrt(), thủ tục printf() x, y, counter, Buffer Các p/tử trong modul được x/định theo độ lệch với vị trí đầu Câu lệnh thư 10 của hàm sqrt() Phần tử thứ 2 của mảng Buffer 49 / 92
Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.3 Chiến lược phân đoạn Chương trình Chương trình thường gồm các modul Một chương trình chính (main program) Tập các chương trình con Các biến, các cấu trúc dữ liệu, Các modul, đối tượng trong c/trình được xác định bằng tên Hàm sqrt(), thủ tục printf() x, y, counter, Buffer Các p/tử trong modul được x/định theo độ lệch với vị trí đầu Câu lệnh thư 10 của hàm sqrt() Phần tử thứ 2 của mảng Buffer Chương trình được tổ chức như thế nào trong bộ nhớ? Stack nằm trên hay Data nằm trên trong bộ nhớ? Địa chỉ vật lý các đối tượng ? ⇒Không quan tâm 49 / 92
P/tử thứ 11 Mỗi đoạn chiếm một vùng liên tục Có vị trí bắt đầu và kích thước Lệnh thứ 5 Có thể nằm tại bất cứ đâu trong bộ nhớ Đối tượng trong đoạn được xác định bởi Phần tử đầu vị trí tương đối so với đầu đoạn Lệnh thứ 5 của chương trình chính Phần tử đầu tiên của stack Vị trí các đối tượng trong bộ nhớ? Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.3 Chiến lược phân đoạn Quan điểm người dùng Khi đưa c/trình vào bộ nhớ để thực hiện C/trình gồm nhiều đoạn khác nhau Không gian Mỗi đoạn là một khối logic, ứng với một địa chỉ logic modul Mã lệnh: main(), thủ tục, hàm subroutines array Dữ liệu: Đối tượng toàn cục, cục bộ Các đoạn khác: stack, mảng main program data stack 50 / 92
P/tử thứ 11 Lệnh thứ 5 Đối tượng trong đoạn được xác định bởi Phần tử đầu vị trí tương đối so với đầu đoạn Lệnh thứ 5 của chương trình chính Phần tử đầu tiên của stack Vị trí các đối tượng trong bộ nhớ? Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.3 Chiến lược phân đoạn Quan điểm người dùng Khi đưa c/trình vào bộ nhớ để thực hiện C/trình gồm nhiều đoạn khác nhau Không gian Mỗi đoạn là một khối logic, ứng với một địa chỉ logic modul Mã lệnh: main(), thủ tục, hàm subroutines array Dữ liệu: Đối tượng toàn cục, cục bộ Các đoạn khác: stack, mảng Mỗi đoạn chiếm một vùng liên tục main program Có vị trí bắt đầu và kích thước data Có thể nằm tại bất cứ đâu trong bộ nhớ stack 50 / 92
Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.3 Chiến lược phân đoạn Quan điểm người dùng Khi đưa c/trình vào bộ nhớ để thực hiện C/trình gồm nhiều đoạn khác nhau Không gian Mỗi đoạn là một khối logic, ứng với một địa chỉ logic modul Mã lệnh: main(), thủ tục, hàm subroutines array Dữ liệu: Đối tượng toàn cục, cục bộ Các đoạn khác: stack, mảng P/tử thứ 11 Mỗi đoạn chiếm một vùng liên tục main program Có vị trí bắt đầu và kích thước Lệnh thứ 5 data Có thể nằm tại bất cứ đâu trong bộ nhớ Đối tượng trong đoạn được xác định bởi Phần tử đầu vị trí tương đối so với đầu đoạn stack Lệnh thứ 5 của chương trình chính Phần tử đầu tiên của stack Vị trí các đối tượng trong bộ nhớ? 50 / 92
1400 5x4 Lệnh thứ 5 1420 P/tử thứ 11 Lệnh thứ 5 Đoạn 0 4300 11x2 P/tử thứ 11 4322 Đoạn 3 Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.3 Chiến lược phân đoạn Ví dụ HĐH Không gian địa chỉ logic subroutine array Đoạn 2 Đoạn 3 main program data Đoạn 0 stack Đoạn 4 Đoạn 1 Bộ nhớ 51 / 92
5x4 Lệnh thứ 5 1420 P/tử thứ 11 Lệnh thứ 5 11x2 P/tử thứ 11 4322 Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.3 Chiến lược phân đoạn Ví dụ HĐH Không gian địa chỉ logic 1400 subroutine array Đoạn 2 Đoạn 3 main program Đoạn 0 data Đoạn 0 stack Đoạn 4 Đoạn 1 4300 Đoạn 3 Bộ nhớ 51 / 92
5x4 Lệnh thứ 5 1420 11x2 P/tử thứ 11 4322 Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.3 Chiến lược phân đoạn Ví dụ HĐH Không gian địa chỉ logic 1400 subroutine array Đoạn 2 P/tử thứ 11 Đoạn 3 main program Đoạn 0 Lệnh thứ 5 data Đoạn 0 stack Đoạn 4 Đoạn 1 4300 Đoạn 3 Bộ nhớ 51 / 92
Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.3 Chiến lược phân đoạn Ví dụ HĐH Không gian địa chỉ logic 1400 subroutine array 5x4 Lệnh thứ 5 1420 Đoạn 2 P/tử thứ 11 Đoạn 3 main program Đoạn 0 Lệnh thứ 5 data Đoạn 0 stack Đoạn 4 Đoạn 1 4300 11x2 P/tử thứ 11 4322 Đoạn 3 Bộ nhớ 51 / 92
Dịch và biên tập chương trình tạo ra bảng quản lý đoạn (SCB: Segement Control Block) Mỗi phần tử của bảng ứng với một đoạn của chương trình Mark Address Length 0 . . n Dấu hiệu (Mark (0/1)): Đoạn đã tồn tại trong bộ nhớ Địa chỉ (Address): Vị trí cơ sở (base) của đoạn trong bộ nhớ Độ dài (Length): Độ dài của đoạn Địa chỉ truy nhập: tên (số hiệu) đoạn và độ lệch trong đoạn §Vấn đề: Chuyển đổi từ địa chỉ 2 chiều ⇒ địa chỉ một chiều ¤ ¦ ¥ Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.3 Chiến lược phân đoạn Cấu trúc phân đoạn Chương trình là tập hợp các đoạn (modul,segment) Tên đoạn (số hiệu đoạn), độ dài của đoạn Mỗi đoạn có thể được biên tập riêng. 52 / 92
Địa chỉ truy nhập: tên (số hiệu) đoạn và độ lệch trong đoạn §Vấn đề: Chuyển đổi từ địa chỉ 2 chiều ⇒ địa chỉ một chiều ¤ ¦ ¥ Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.3 Chiến lược phân đoạn Cấu trúc phân đoạn Chương trình là tập hợp các đoạn (modul,segment) Tên đoạn (số hiệu đoạn), độ dài của đoạn Mỗi đoạn có thể được biên tập riêng. Dịch và biên tập chương trình tạo ra bảng quản lý đoạn (SCB: Segement Control Block) Mỗi phần tử của bảng ứng với một đoạn của chương trình Mark Address Length 0 . . n Dấu hiệu (Mark (0/1)): Đoạn đã tồn tại trong bộ nhớ Địa chỉ (Address): Vị trí cơ sở (base) của đoạn trong bộ nhớ Độ dài (Length): Độ dài của đoạn 52 / 92
§Vấn đề: Chuyển đổi từ địa chỉ 2 chiều ⇒ địa chỉ một chiều ¤ ¦ ¥ Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.3 Chiến lược phân đoạn Cấu trúc phân đoạn Chương trình là tập hợp các đoạn (modul,segment) Tên đoạn (số hiệu đoạn), độ dài của đoạn Mỗi đoạn có thể được biên tập riêng. Dịch và biên tập chương trình tạo ra bảng quản lý đoạn (SCB: Segement Control Block) Mỗi phần tử của bảng ứng với một đoạn của chương trình Mark Address Length 0 . . n Dấu hiệu (Mark (0/1)): Đoạn đã tồn tại trong bộ nhớ Địa chỉ (Address): Vị trí cơ sở (base) của đoạn trong bộ nhớ Độ dài (Length): Độ dài của đoạn Địa chỉ truy nhập: tên (số hiệu) đoạn và độ lệch trong đoạn 52 / 92
Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.3 Chiến lược phân đoạn Cấu trúc phân đoạn Chương trình là tập hợp các đoạn (modul,segment) Tên đoạn (số hiệu đoạn), độ dài của đoạn Mỗi đoạn có thể được biên tập riêng. Dịch và biên tập chương trình tạo ra bảng quản lý đoạn (SCB: Segement Control Block) Mỗi phần tử của bảng ứng với một đoạn của chương trình Mark Address Length 0 . . n Dấu hiệu (Mark (0/1)): Đoạn đã tồn tại trong bộ nhớ Địa chỉ (Address): Vị trí cơ sở (base) của đoạn trong bộ nhớ Độ dài (Length): Độ dài của đoạn Địa chỉ truy nhập: tên (số hiệu) đoạn và độ lệch trong đoạn §Vấn đề: Chuyển đổi từ địa chỉ 2 chiều ⇒ địa chỉ một chiều ¤ 52 / 92 ¦ ¥
Địa chỉ = ?354565404420 Đoạn 3 bắtLỗi đầu truy tại nhập! 3200 1400 Đoạn 0 2400 P/tử 345 3200 Jmp Offset 345 3545 Đoạn 3 4300 4420 Đoạn 2 4700 Đoạn 4 5700 6300 Đoạn 1 6700 Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.3 Chiến lược phân đoạn Ví dụ HĐH Không gian địa chỉ logic subroutine array Đoạn 2 Đoạn 3 main program data Đoạn 0 M A L 0 - 1000 stack 0 - 400 Đoạn 4 Đoạn 1 0 - 400 0 - 1100 0 - 1000 SCB Bộ nhớ 53 / 92
Địa chỉ = ?354565404420 Đoạn 3 bắtLỗi đầu truy tại nhập! 3200 1400 Đoạn 0 2400 P/tử 345 3200 Jmp Offset 345 3545 Đoạn 3 4300 4420 Đoạn 2 4700 Đoạn 4 5700 6300 Đoạn 1 6700 Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.3 Chiến lược phân đoạn Ví dụ HĐH Không gian địa chỉ logic subroutine array Đoạn 2 Đoạn 3 main program data Đoạn 0 M A L 1 1400 1000 stack 1 6300 400 Đoạn 4 Đoạn 1 0 - 400 1 3200 1100 1 4700 1000 SCB Bộ nhớ 53 / 92
Địa chỉ = ?354565404420 Đoạn 3 bắtLỗi đầu truy tại nhập! 3200 P/tử 345 Jmp Offset 345 3545 Đoạn 2 4420 Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.3 Chiến lược phân đoạn Ví dụ HĐH Không gian địa chỉ logic 1400 subroutine array Đoạn 0 2400 Đoạn 2 Đoạn 3 3200 main program data Đoạn 0 M A L Đoạn 3 4300 1 1400 1000 4700 stack 1 6300 400 Đoạn 4 0 - 400 Đoạn 4 Đoạn 1 5700 1 3200 1100 1 4700 1000 6300 SCB Đoạn 1 6700 Bộ nhớ 53 / 92
Địa chỉ = 3545?65404420 Đoạn 3 bắtLỗi đầu truy tại nhập! 3200 P/tử 345 Jmp Offset 345 3545 Đoạn 2 4420 Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.3 Chiến lược phân đoạn Ví dụ Địa chỉ = ? HĐH Không gian địa chỉ logic 1400 subroutine array Đoạn 0 2400 Đoạn 2 Đoạn 3 3200 main program data Đoạn 0 M A L Đoạn 3 4300 1 1400 1000 4700 stack 1 6300 400 Đoạn 4 0 - 400 Đoạn 4 Đoạn 1 5700 1 3200 1100 1 4700 1000 6300 SCB Đoạn 1 6700 Bộ nhớ 53 / 92
Địa chỉ = 3545?65404420 Lỗi truy nhập! Jmp Offset 345 3545 Đoạn 2 4420 Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.3 Chiến lược phân đoạn Ví dụ Địa chỉ = ? HĐH Không gian địa chỉ logic Đoạn 3 bắt đầu tại 3200 1400 subroutine array Đoạn 0 2400 Đoạn 2 P/tử 345 Đoạn 3 3200 main program data Đoạn 0 M A L Đoạn 3 4300 1 1400 1000 4700 stack 1 6300 400 Đoạn 4 0 - 400 Đoạn 4 Đoạn 1 5700 1 3200 1100 1 4700 1000 6300 SCB Đoạn 1 6700 Bộ nhớ 53 / 92
Địa chỉ = ?65404420 Lỗi truy nhập! Jmp Đoạn 2 4420 Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.3 Chiến lược phân đoạn Ví dụ Địa chỉ = 3545 HĐH Không gian địa chỉ logic Đoạn 3 bắt đầu tại 3200 1400 subroutine array Đoạn 0 2400 Đoạn 2 P/tử 345 Đoạn 3 3200 main program 3545 data Offset 345 Đoạn 0 M A L Đoạn 3 4300 1 1400 1000 4700 stack 1 6300 400 Đoạn 4 0 - 400 Đoạn 4 Đoạn 1 5700 1 3200 1100 1 4700 1000 6300 SCB Đoạn 1 6700 Bộ nhớ 53 / 92
Địa chỉ = ?354565404420 Đoạn 3 bắtLỗi đầu truy tại nhập! 3200 P/tử 345 Jmp Offset 345 3545 Đoạn 2 4420 Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.3 Chiến lược phân đoạn Ví dụ Địa chỉ = ? HĐH Không gian địa chỉ logic 1400 subroutine array Đoạn 0 2400 Đoạn 2 Đoạn 3 3200 main program data Đoạn 0 M A L Đoạn 3 4300 1 1400 1000 4700 stack 1 6300 400 Đoạn 4 0 - 400 Đoạn 4 Đoạn 1 5700 1 3200 1100 1 4700 1000 6300 SCB Đoạn 1 6700 Bộ nhớ 53 / 92
Địa chỉ = ?35454420 Đoạn 3 bắtLỗi đầu truy tại nhập! 3200 P/tử 345 Jmp Offset 345 3545 Đoạn 2 4420 Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.3 Chiến lược phân đoạn Ví dụ Địa chỉ = 6540 HĐH Không gian địa chỉ logic 1400 subroutine array Đoạn 0 2400 Đoạn 2 Đoạn 3 3200 main program data Đoạn 0 M A L Đoạn 3 4300 1 1400 1000 4700 stack 1 6300 400 Đoạn 4 0 - 400 Đoạn 4 Đoạn 1 5700 1 3200 1100 1 4700 1000 6300 SCB Đoạn 1 6700 Bộ nhớ 53 / 92
Địa chỉ = ?354565404420 Đoạn 3 bắtLỗi đầu truy tại nhập! 3200 P/tử 345 Offset 345 3545 Đoạn 2 4420 Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.3 Chiến lược phân đoạn Ví dụ Địa chỉ = ? HĐH Không gian địa chỉ logic 1400 subroutine array Đoạn 0 2400 Đoạn 2 Đoạn 3 3200 main program Jmp data Đoạn 0 M A L Đoạn 3 4300 1 1400 1000 4700 stack 1 6300 400 Đoạn 4 0 - 400 Đoạn 4 Đoạn 1 5700 1 3200 1100 1 4700 1000 6300 SCB Đoạn 1 6700 Bộ nhớ 53 / 92
Địa chỉ = ?354565404420 Đoạn 3 bắtLỗi đầu truy tại nhập! 3200 P/tử 345 Offset 345 3545 4420 Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.3 Chiến lược phân đoạn Ví dụ Địa chỉ = ? HĐH Không gian địa chỉ logic 1400 subroutine array Đoạn 0 2400 Đoạn 2 Đoạn 3 3200 main program Jmp data Đoạn 0 M A L Đoạn 3 4300 1 1400 1000 Đoạn 2 4700 stack 1 6300 400 Đoạn 4 0 - 400 Đoạn 4 Đoạn 1 5700 1 3200 1100 1 4700 1000 6300 SCB Đoạn 1 6700 Bộ nhớ 53 / 92
Địa chỉ = ?354565404420 Đoạn 3 bắtLỗi đầu truy tại nhập! 3200 P/tử 345 Offset 345 3545 4420 Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.3 Chiến lược phân đoạn Ví dụ Địa chỉ = ? HĐH Không gian địa chỉ logic 1400 subroutine array Đoạn 0 2400 Đoạn 2 Đoạn 3 3200 main program Jmp data Đoạn 0 M A L Đoạn 3 4300 1 1400 1000 Đoạn 2 4700 stack 1 6300 400 Đoạn 4 1 4300 400 Đoạn 4 Đoạn 1 5700 1 3200 1100 1 4700 1000 6300 Đoạn 1 SCB 6700 Bộ nhớ 53 / 92
Địa chỉ = ?35456540 Đoạn 3 bắtLỗi đầu truy tại nhập! 3200 P/tử 345 Offset 345 3545 Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.3 Chiến lược phân đoạn Ví dụ Địa chỉ = 4420 HĐH Không gian địa chỉ logic 1400 subroutine array Đoạn 0 2400 Đoạn 2 Đoạn 3 3200 main program Jmp data Đoạn 0 M A L Đoạn 3 4300 4420 1 1400 1000 Đoạn 2 4700 stack 1 6300 400 Đoạn 4 1 4300 400 Đoạn 4 Đoạn 1 5700 1 3200 1100 1 4700 1000 6300 SCB Đoạn 1 6700 Bộ nhớ 53 / 92
Địa chỉ = ?354565404420 Đoạn 3 bắtLỗi đầu truy tại nhập! 3200 P/tử 345 Jmp Offset 345 3545 4420 Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.3 Chiến lược phân đoạn Ví dụ Địa chỉ = ? HĐH Không gian địa chỉ logic 1400 subroutine array Đoạn 0 2400 Đoạn 2 Đoạn 3 3200 main program data Đoạn 0 M A L Đoạn 3 4300 1 1400 1000 Đoạn 2 4700 stack 1 6300 400 Đoạn 4 1 4300 400 Đoạn 4 Đoạn 1 5700 1 3200 1100 1 4700 1000 6300 SCB Đoạn 1 6700 Bộ nhớ 53 / 92
Địa chỉ = ?354565404420 Đoạn 3 bắt đầu tại 3200 P/tử 345 Jmp Offset 345 3545 4420 Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.3 Chiến lược phân đoạn Ví dụ Địa chỉ = ? HĐH Không gian địa chỉ logic Lỗi truy nhập! 1400 subroutine array Đoạn 0 2400 Đoạn 2 Đoạn 3 3200 main program data Đoạn 0 M A L Đoạn 3 4300 1 1400 1000 Đoạn 2 4700 stack 1 6300 400 Đoạn 4 1 4300 400 Đoạn 4 Đoạn 1 5700 1 3200 1100 1 4700 1000 6300 SCB Đoạn 1 6700 Bộ nhớ 53 / 92
Truy nhập tới địa chỉ logic 1 s ≥ STLR : Lỗi 2 STBR + s : Vị trí phần tử s trong SCB 3 Kiểm tra trường dấu hiệu M của phần tử SCBs M = 0: Đoạn s chưa tồn tại trong bộ nhớ ⇒ Lỗi truy nhập ⇒ Hệ điều hành phải nạp đoạn 1 Xin vùng nhớ có kích thước được ghi trong trường L 2 Tìm modul tương ứng ở bộ nhớ ngoài và nạp và định vị vào vùng nhớ xin được 3 Sửa lại trường địa chỉ A và trường dấu hiệu M(M = 1) 4 Truy nhập bộ nhớ như trường hợp không gặp lỗi truy nhập M = 1 :Đoạn s đã tồn tại trong bộ nhớ 1 d ≥ Ls : Lỗi truy nhập (vượt quá kích thước đoạn) 2 d + As : Địa chỉ vật lý cần tìm Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.3 Chiến lược phân đoạn Chuyển đổi địa chỉ Khi thực hiện chương trình Bảng quản lý đoạn được nạp vào bộ nhớ STBR (Segment-table base register): Vị trí SCB trong bộ nhớ STLR (Segment-table length register): Số phần tử của SCB 54 / 92
Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.3 Chiến lược phân đoạn Chuyển đổi địa chỉ Khi thực hiện chương trình Bảng quản lý đoạn được nạp vào bộ nhớ STBR (Segment-table base register): Vị trí SCB trong bộ nhớ STLR (Segment-table length register): Số phần tử của SCB Truy nhập tới địa chỉ logic 1 s ≥ STLR : Lỗi 2 STBR + s : Vị trí phần tử s trong SCB 3 Kiểm tra trường dấu hiệu M của phần tử SCBs M = 0: Đoạn s chưa tồn tại trong bộ nhớ ⇒ Lỗi truy nhập ⇒ Hệ điều hành phải nạp đoạn 1 Xin vùng nhớ có kích thước được ghi trong trường L 2 Tìm modul tương ứng ở bộ nhớ ngoài và nạp và định vị vào vùng nhớ xin được 3 Sửa lại trường địa chỉ A và trường dấu hiệu M(M = 1) 4 Truy nhập bộ nhớ như trường hợp không gặp lỗi truy nhập M = 1 :Đoạn s đã tồn tại trong bộ nhớ 1 d ≥ Ls : Lỗi truy nhập (vượt quá kích thước đoạn) 2 d + A : Địa chỉ vật lý cần tìm 54 / 92 s
Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.3 Chiến lược phân đoạn Chuyển đổi địa chỉ: Sơ đồ truy nhập 55 / 92
Dễ dàng thực hiện nhiệm vụ bảo vệ đoạn Kiểm tra lỗi truy nhập bộ nhớ Địa chỉ không hợp lệ :vươt quá kích thước đoạn Kiểm tra tính chất truy nhập Đoạn mã: chỉ đọc Viết vào đoạn mã: lỗi truy nhập Kiểm tra quyền truy nhập modul Thêm trường quyền truy nhập(user/system) vào SCB Cho phép sử dụng chung đoạn (VD Soạn thảo văn bản) Tiến trình 2 Data S3 (Read only) S0 sqrt() S0 Tiến trình 1 Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.3 Chiến lược phân đoạn Nhận xét: ưu điểm Sơ đồ nạp modul không cần sự tham gia của người sử dụng 56 / 92
Cho phép sử dụng chung đoạn (VD Soạn thảo văn bản) Tiến trình 2 Data S3 (Read only) S0 sqrt() S0 Tiến trình 1 Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.3 Chiến lược phân đoạn Nhận xét: ưu điểm Sơ đồ nạp modul không cần sự tham gia của người sử dụng Dễ dàng thực hiện nhiệm vụ bảo vệ đoạn Kiểm tra lỗi truy nhập bộ nhớ Địa chỉ không hợp lệ :vươt quá kích thước đoạn Kiểm tra tính chất truy nhập Đoạn mã: chỉ đọc Viết vào đoạn mã: lỗi truy nhập Kiểm tra quyền truy nhập modul Thêm trường quyền truy nhập(user/system) vào SCB 56 / 92
Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.3 Chiến lược phân đoạn Nhận xét: ưu điểm Sơ đồ nạp modul không cần sự tham gia của người sử dụng Dễ dàng thực hiện nhiệm vụ bảo vệ đoạn Kiểm tra lỗi truy nhập bộ nhớ Địa chỉ không hợp lệ :vươt quá kích thước đoạn Kiểm tra tính chất truy nhập Đoạn mã: chỉ đọc Viết vào đoạn mã: lỗi truy nhập Kiểm tra quyền truy nhập modul Thêm trường quyền truy nhập(user/system) vào SCB Cho phép sử dụng chung đoạn (VD Soạn thảo văn bản) Tiến trình 2 Data S3 (Read only) S0 sqrt() S0 Tiến trình 1 56 / 92
Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.3 Chiến lược phân đoạn Dùng chung đoạn : Vấn đề chính Đoạn dùng chung phải cùng số hiệu trong SCB Call (0, 120) ? Read (1, 245) ? Giải quyết bằng cách truy nhập gián tiếp JMP + 08 Thanh ghi đoạn chứa số hiệu đoạn (ES:BX) 57 / 92
Bị phân mảnh bộ nhớ Phân phối vùng nhớ theo các chiến lược first fit /best fit Cần phải bố trí lại bộ nhớ (dịch chuyển, swapping) Có thể dựa vào bảng SCB • M ← 0 : Đoạn chưa được nạp vào • Vùng nhớ được xác định bởi A và L được trả về DS tự do Vấn đề lựa chọn modul cần đưa ra • Đưa ra modul tồn tại lâu nhất • Đưa ra modul có lần sử dụng cuối cách xa nhất • Đưa ra modul có tần xuất sử dụng thấp nhất ⇒Cần phương tiên ghi lại số lần và thời điểm truy nhập đoạn Giải pháp: phân phối bộ nhớ theo các đoạn bằng nhau (page)? Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.3 Chiến lược phân đoạn Nhận xét : Nhược điểm Hiệu quả sử dụng phụ thuộc vào cấu trúc chương trình 58 / 92
Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.3 Chiến lược phân đoạn Nhận xét : Nhược điểm Hiệu quả sử dụng phụ thuộc vào cấu trúc chương trình Bị phân mảnh bộ nhớ Phân phối vùng nhớ theo các chiến lược first fit /best fit Cần phải bố trí lại bộ nhớ (dịch chuyển, swapping) Có thể dựa vào bảng SCB • M ← 0 : Đoạn chưa được nạp vào • Vùng nhớ được xác định bởi A và L được trả về DS tự do Vấn đề lựa chọn modul cần đưa ra • Đưa ra modul tồn tại lâu nhất • Đưa ra modul có lần sử dụng cuối cách xa nhất • Đưa ra modul có tần xuất sử dụng thấp nhất ⇒Cần phương tiên ghi lại số lần và thời điểm truy nhập đoạn Giải pháp: phân phối bộ nhớ theo các đoạn bằng nhau (page)? 58 / 92
Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.4 Chiến lược phân trang 2 Các chiến lược quản lý bộ nhớ Chiến lược phân chương cố định Chiến lược phân chương động Chiến lược phân đoạn Chiến lược phân trang Chiến lược kết hợp phân đoạn-phân trang 59 / 92
Bộ nhớ logic (chương trình) được chia thành từng trang có kích thước bằng trang vật lý: trang logic (pages) Khi thực hiện chương trình Nạp trang logic (từ bộ nhớ ngoài) vào trang vật lý Xây dựng một bảng quản lý trang (PCB: Page Control Block) dùng để xác định mối quan hệ giữa trang vật lý và trang logic Mỗi phần tử của PCB ứng với một trang chương trình Cho biêt biết trang vật lý chứa trang logic tương ứng Ví dụ PCB[8] = 4 ⇒ ? Địa chỉ truy nhập: Số hiệu trang (p) : Chỉ số trong PCB để tìm đ/chỉ cơ sở trang Độ lệch trong trang (d): Kết hợp địa chỉ cơ sở của trang để tìm ra đ/chỉ vật lý Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.4 Chiến lược phân trang Nguyên tắc Bộ nhớ vật lý được chia thành từng khối có kích thước bằng nhau: trang vật lý (frames) Trang vật lý được đánh số 0, 1, 2, : địa chỉ vật lý của trang Trang được dùng làm đơn vị phân phối nhớ 60 / 92
Khi thực hiện chương trình Nạp trang logic (từ bộ nhớ ngoài) vào trang vật lý Xây dựng một bảng quản lý trang (PCB: Page Control Block) dùng để xác định mối quan hệ giữa trang vật lý và trang logic Mỗi phần tử của PCB ứng với một trang chương trình Cho biêt biết trang vật lý chứa trang logic tương ứng Ví dụ PCB[8] = 4 ⇒ ? Địa chỉ truy nhập: Số hiệu trang (p) : Chỉ số trong PCB để tìm đ/chỉ cơ sở trang Độ lệch trong trang (d): Kết hợp địa chỉ cơ sở của trang để tìm ra đ/chỉ vật lý Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.4 Chiến lược phân trang Nguyên tắc Bộ nhớ vật lý được chia thành từng khối có kích thước bằng nhau: trang vật lý (frames) Trang vật lý được đánh số 0, 1, 2, : địa chỉ vật lý của trang Trang được dùng làm đơn vị phân phối nhớ Bộ nhớ logic (chương trình) được chia thành từng trang có kích thước bằng trang vật lý: trang logic (pages) 60 / 92
Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.4 Chiến lược phân trang Nguyên tắc Bộ nhớ vật lý được chia thành từng khối có kích thước bằng nhau: trang vật lý (frames) Trang vật lý được đánh số 0, 1, 2, : địa chỉ vật lý của trang Trang được dùng làm đơn vị phân phối nhớ Bộ nhớ logic (chương trình) được chia thành từng trang có kích thước bằng trang vật lý: trang logic (pages) Khi thực hiện chương trình Nạp trang logic (từ bộ nhớ ngoài) vào trang vật lý Xây dựng một bảng quản lý trang (PCB: Page Control Block) dùng để xác định mối quan hệ giữa trang vật lý và trang logic Mỗi phần tử của PCB ứng với một trang chương trình Cho biêt biết trang vật lý chứa trang logic tương ứng Ví dụ PCB[8] = 4 ⇒ ? Địa chỉ truy nhập: Số hiệu trang (p) : Chỉ số trong PCB để tìm đ/chỉ cơ sở trang Độ lệch trong trang (d): Kết hợp địa chỉ cơ sở của trang để tìm ra đ/chỉ vật lý 60 / 92
a b c i d j Trangk 2 e l f 0 5 m g Trangnp 3 h 1 6 q i 2 1 j k 3 2 l m PCB n a p Trangb 0 q c e d Trangfg 1 h Địa chỉ trang 1 độ lệch 2 = ? Địa chỉ = 6*4 + 2 = 26 (624) Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.4 Chiến lược phân trang Ví dụ 0 0 Trang 0 1 1 Trang 1 2 3 2 Trang 2 4 3 Trang 3 5 Bộ nhớ logic 6 7 Bộ nhớ vật lý 61 / 92
a b c i d j Trangk 2 e l f m g Trangnp 3 h q i j k l m n a p Trangb 0 q c e d Trangfg 1 h Địa chỉ trang 1 độ lệch 2 = ? Địa chỉ = 6*4 + 2 = 26 (624) Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.4 Chiến lược phân trang Ví dụ 0 0 Trang 0 1 0 5 1 Trang 1 1 6 2 2 1 3 2 Trang 2 3 2 PCB 4 3 Trang 3 5 Bộ nhớ logic 6 7 Bộ nhớ vật lý 61 / 92
a b c i d j Trangk 2 e l f m g Trangnp 3 h q i j k l m n a p b q c e d Trangfg 1 h Địa chỉ trang 1 độ lệch 2 = ? Địa chỉ = 6*4 + 2 = 26 (624) Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.4 Chiến lược phân trang Ví dụ 0 0 Trang 0 1 0 5 1 Trang 1 1 6 2 2 1 3 2 Trang 2 3 2 PCB 4 3 Trang 3 Trang 0 5 Bộ nhớ logic 6 7 Bộ nhớ vật lý 61 / 92
a b c i d j Trangk 2 e l f m g Trangnp 3 h q i j k l m n a p Trangb 0 q c e d fg h Địa chỉ trang 1 độ lệch 2 = ? Địa chỉ = 6*4 + 2 = 26 (624) Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.4 Chiến lược phân trang Ví dụ 0 0 Trang 0 1 0 5 1 Trang 1 1 6 2 2 1 3 2 Trang 2 3 2 PCB 4 3 Trang 3 5 Bộ nhớ logic Trang 1 6 7 Bộ nhớ vật lý 61 / 92
a b c i d j k e l f m g Trangnp 3 h q i j k l m n a p Trangb 0 q c e d Trangfg 1 h Địa chỉ trang 1 độ lệch 2 = ? Địa chỉ = 6*4 + 2 = 26 (624) Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.4 Chiến lược phân trang Ví dụ 0 0 Trang 0 Trang 2 1 0 5 1 Trang 1 1 6 2 2 1 3 2 Trang 2 3 2 PCB 4 3 Trang 3 5 Bộ nhớ logic 6 7 Bộ nhớ vật lý 61 / 92
a b c i d j Trangk 2 e l f m g np h q i j k l m n a p Trangb 0 q c e d Trangfg 1 h Địa chỉ trang 1 độ lệch 2 = ? Địa chỉ = 6*4 + 2 = 26 (624) Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.4 Chiến lược phân trang Ví dụ 0 0 Trang 0 1 0 5 1 Trang 1 1 6 Trang 3 2 2 1 3 2 Trang 2 3 2 PCB 4 3 Trang 3 5 Bộ nhớ logic 6 7 Bộ nhớ vật lý 61 / 92
Trang 0 i j Trangk 2 m l Trangg 1 Trangnp 3 q Trang 2 a Trang 3 Trangbc 0 e d Trangfg 1 h Địa chỉ trang 1 độ lệch 2 = ? Địa chỉ = 6*4 + 2 = 26 (624) Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.4 Chiến lược phân trang Ví dụ a b 0 0 c d e 1 f 0 5 1 g 2 h 1 6 i 2 1 j 3 2 k 3 2 l m PCB 4 n 3 p 5 q Bộ nhớ logic 6 7 Bộ nhớ vật lý 61 / 92
Trang 0 Trang 2 Trangg 1 Trang 3 Trang 2 Trang 3 Trang 0 Trangg 1 Địa chỉ trang 1 độ lệch 2 = ? Địa chỉ = 6*4 + 2 = 26 (624) Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.4 Chiến lược phân trang Ví dụ a 0 0 b c i d j k 1 e l f 0 5 m 1 g np 2 h 1 6 q i 2 1 j 3 2 k 3 2 l m PCB 4 n a 3 p b 5 q c e d Bộ nhớ logic fg 6 h 7 Bộ nhớ vật lý 61 / 92
Trang 0 Trang 2 Trang 1 Trang 3 Trang 2 Trang 3 Trang 0 Trangg 1 Địa chỉ = 6*4 + 2 = 26 (624) Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.4 Chiến lược phân trang Ví dụ a 0 0 b c i d j k 1 e l f 0 5 m 1 g np 2 h 1 6 q i 2 1 j 3 2 k 3 2 l m PCB 4 n a 3 p b 5 q c e d Bộ nhớ logic fg 6 h 7 Địa chỉ trang 1 độ lệch 2 = ? Bộ nhớ vật lý 61 / 92
Trang 0 Trang 2 Trang 1 Trang 3 Trang 2 Trang 3 Trang 0 Trang 1 Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.4 Chiến lược phân trang Ví dụ a 0 0 b c i d j k 1 e l f 0 5 m 1 g np 2 h 1 6 q i 2 1 j 3 2 k 3 2 l m PCB 4 n a 3 p b 5 q c e d Bộ nhớ logic fg 6 h 7 Địa chỉ trang 1 độ lệch 2 = ? Bộ nhớ vật lý Địa chỉ = 6*4 + 2 = 26 (624) 61 / 92
Không cần thiết nạp toàn bộ trang logic vào Số trang vật lý phụ thuộc k/thước bộ nhớ, số trang logic tùy ý PCB cần trường dấu hiệu (Mark) cho biết trang đã được nạp vào bộ nhớ chưa M = 0 Trang chưa tồn tại M = 1 Trang đã được đưa vào bộ nhớ vật lý Phân biệt chiến lược phân trang - phân đoạn Chiến lược phân đoạn Các modul phụ thuộc cấu trúc logic của chương trình Chiến lược phân trang Các khối có kích thước độc lập kích thước chương trình Kích thước khối phụ thuộc phần cứng (VD: 29 → 213 bytes) Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.4 Chiến lược phân trang Ghi chú Dung lượng trang luôn là lũy thừa của 2 Cho phép ghép giữa số hiệu trang vật lý và độ lệch trong trang Ví dụ: Bộ nhớ n bit, kích thước trang 2k số hiệu trang độ lệch n − k k 62 / 92
Phân biệt chiến lược phân trang - phân đoạn Chiến lược phân đoạn Các modul phụ thuộc cấu trúc logic của chương trình Chiến lược phân trang Các khối có kích thước độc lập kích thước chương trình Kích thước khối phụ thuộc phần cứng (VD: 29 → 213 bytes) Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.4 Chiến lược phân trang Ghi chú Dung lượng trang luôn là lũy thừa của 2 Cho phép ghép giữa số hiệu trang vật lý và độ lệch trong trang Ví dụ: Bộ nhớ n bit, kích thước trang 2k số hiệu trang độ lệch n − k k Không cần thiết nạp toàn bộ trang logic vào Số trang vật lý phụ thuộc k/thước bộ nhớ, số trang logic tùy ý PCB cần trường dấu hiệu (Mark) cho biết trang đã được nạp vào bộ nhớ chưa M = 0 Trang chưa tồn tại M = 1 Trang đã được đưa vào bộ nhớ vật lý 62 / 92
Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.4 Chiến lược phân trang Ghi chú Dung lượng trang luôn là lũy thừa của 2 Cho phép ghép giữa số hiệu trang vật lý và độ lệch trong trang Ví dụ: Bộ nhớ n bit, kích thước trang 2k số hiệu trang độ lệch n − k k Không cần thiết nạp toàn bộ trang logic vào Số trang vật lý phụ thuộc k/thước bộ nhớ, số trang logic tùy ý PCB cần trường dấu hiệu (Mark) cho biết trang đã được nạp vào bộ nhớ chưa M = 0 Trang chưa tồn tại M = 1 Trang đã được đưa vào bộ nhớ vật lý Phân biệt chiến lược phân trang - phân đoạn Chiến lược phân đoạn Các modul phụ thuộc cấu trúc logic của chương trình Chiến lược phân trang Các khối có kích thước độc lập kích thước chương trình Kích thước khối phụ thuộc phần cứng (VD: 29 → 213 bytes) 62 / 92
Xây dựng bảng quản lý trang và luôn giữ trong bộ nhớ PTBR (Page-table base register) trỏ tới PCB. PTLR(Page-table length register) kích thước PCB. Địa chỉ truy nhập dạng Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.4 Chiến lược phân trang Thực hiện chương trình Nạp chương trình vào bộ nhớ Nếu đủ trang vật lý tự do ⇒ nạp toàn bộ Nếu không đủ trang vật lý tự do ⇒ nạp từng phần 63 / 92
Địa chỉ truy nhập dạng Chương 3: Quản lý bộ nhớ 2. Các chiến lược quản lý bộ nhớ 2.4 Chiến lược phân trang Thực hiện chương trình Nạp chương trình vào bộ nhớ Nếu đủ trang vật lý tự do ⇒ nạp toàn bộ Nếu không đủ trang vật lý tự do ⇒ nạp từng phần Xây dựng bảng quản lý trang và luôn giữ trong bộ nhớ PTBR (Page-table base register) trỏ tới PCB. PTLR(Page-table length register) kích thước PCB. 63 / 92