Chương 3: Quản lý bộ nhớ

GV: Đỗ Công Đức Khoa khoa học máy tính NGUYÊN LÝ HỆ ĐIỀU HÀNH (3 Tín chỉ) 6/28/2014 Chương 3. Quản lý bộ nhớ 2 Chương 3: QUẢN LÝ BỘ NHỚ  Bộ nhớ là thiết bị lưu trữ dữ liệu của máy tính thông qua đó CPU có thể trao đổi thông tin với môi trường ngoài  Bộ nhớ chính được tổ chức như một mảng một chiều các từ nhớ (word) và mỗi từ có một địa chỉ  Việc trao đổi thông tin với môi trường ngoài là thao tác đọc ghi dữ liệu vào bộ nhớ tại một địa chỉ cụ thể  Bộ nhớ gồm có: bộ nhớ trong (chính) và bộ nhớ ngoài (phụ). Nhưng bộ nhớ thì có hạn mà yêu cầu bộ nhớ thì vô hạn.  Bộ nhớ là tài nguyên dùng để cấp phát và chia sẻ cho nhiều tiến trình đang ở trong trạng thái kích hoạt.  Công cụ quản lý bộ nhớ là phân trang (paging) và phân đoạn (Segmentation). HĐH kết hợp phân trang và phân đoạn để quản lý 6/28/2014 Chương 3. Quản lý bộ nhớ 3 Chương 3: QUẢN LÝ BỘ NHỚ 3.1. Nhiệm vụ của quản lý bộ nhớ 3.2. Các cấu trúc chương trình 3.3. Kỹ thuật cấp phát bộ nhớ chính 3.4. Kỹ thuật cấp phát bộ nhớ ảo 3.5. Các thuật toán thay trang 3.6. Cấp phát khung trang 6/28/2014 Chương 3. Quản lý bộ nhớ 4 NHIỆM VỤ CỦA QUẢN LÝ BỘ NHỚ  Trong hệ thống đa chương thì việc quản lý ộ nhớ là rất phức tạp. Bộ phận quản lý bộ nhớ có nhiệm vụ đưa các tiến trình vào bộ nhớ để hoạt động  Giải quyết các trường hợp trên bộ nhớ không còn không gian trống để nạp các tiến trình  Bảo về các tiến trình trên bộ nhớ tránh các trường hợp truy xuất bất hợp lệ xảy ra  Cấp các vùng nhớ cho các tiến trình có yêu cầu Để làm tốt nhiệm vụ này bộ phận quản lý bộ nhớ phải thực hiện 6/28/2014 Chương 3. Quản lý bộ nhớ 5 NHIỆM VỤ CỦA QUẢN LÝ BỘ NHỚ 3.1.1 Sự tái định vị (Relocation)  Trong hệ thống đa chương bộ nhớ được chia sẻ cho nhiều tiến trình nên và bộ nhớ của các tiến trình yêu cầu thì luôn luôn lớn hơn bộ nhớ vật lý của hệ thống.  Khi không còn không gian bộ nhớ chính để nạp thì một chương trình đang chạy trên bộ nhớ có thể Swap out ra đĩa và được Swap in vào lại vào thời điểm thích hợp  HĐH phải lưu lại tất cả các thông tin Swap out để khi Swap in vào lại phải đúng vị trí đã được nạp trước đó để tiếp tục hoạt động  Sau khi thực hiện xong thì HĐH phải tổ chức lại bộ nhớ để chuẩn bị nạp các tiến trình khác có yêu cầu. Đôi khi chương trình swap out có thể được swap in vào lại nhưng không đứng vị trí mà nó được nạp trước đó 6/28/2014 Chương 3. Quản lý bộ nhớ 6 NHIỆM VỤ CỦA QUẢN LÝ BỘ NHỚ 3.1.2 Bảo vệ bộ nhớ  Bảo vệ để chống lại việc truy xuất bất hợp lệ, không được tham chiếu đến các vùng nhớ đã dành cho một tiến trình khác để thực hiện các thao tác đọc/ghi mà không được phép mà nó chỉ được truy xuất đến không gian địa chỉ bộ nhớ mà HĐH đã cấp cho nó  Phải biết địa chỉ không gian địa chỉ của các tiến trình khác, kiểm tra tất cảc các địa chỉ truy xuất tất cả các yêu cầu truy xuất bộ nhớ của mỗi tiến trình khi tiến trình đưa ra địa chỉ truy xuất  Hệ thống quản lý bộ nhớ phải thực hiện không cho các tiến trình của người sử dụng truy cập đến bất kỳ một vị trí nào của chính hệ điều hành, ngoại trừ vùng dữ liệu mà hệ điều hành cung cấp cho chương trình người sử dụng 6/28/2014 Chương 3. Quản lý bộ nhớ 7 NHIỆM VỤ CỦA QUẢN LÝ BỘ NHỚ 3.1.3 Chia sẻ bộ nhớ  Khi nhiều tiến trình thực hiện một chương trình thì việc truy xuất của tiến trình đến một bản copy của chương trình sẽ thuận lợi hơn khi cho phép mỗi tiến trình truy cập đến một bản copy sở hữu riêng  Hệ thống quản lý bộ nhớ phải điều khiển việc truy cập đến không gian bộ nhớ được chia sẻ mà không vi phạm đến các yêu cầu bảo vệ bộ nhớ. Ngoài ra HĐH đa nhiệm phải chia sẻ không gian nhớ cho các tiến trình để HĐH có thể nạp được nhiều tiến trình vào bộ nhớ và tiến trình này có thể hoạt động đồng thời với nhau 6/28/2014 Chương 3. Quản lý bộ nhớ 8 NHIỆM VỤ CỦA QUẢN LÝ BỘ NHỚ 3.1.4 Tổ chức bộ nhớ Logic  Các modul có thể được viết và biên dịch độc lập, với tất cả các tham chiếu từ một modul đến modul khác được giải quyết bởi hệ thống tại thời điểm chạy  Các mức độ khác nhau của sự bảo vệ, read-only, execute-only, có thể cho ra các modul khác nhau  Nó có thể đưa ra các cơ chế để các modul có thể được chia sẻ giữa các tiến trình  Công cụ đáp ứng cho yêu cầu này là sự phân đoạn (segmentation) Đa số các chương trình đều được chia thành các modul, một vài trong số đó là không thể thay đổi (read only, execute only). Nếu HĐH và phần cứng giao dịch với các chương trình của người sử dụng, dữ liệu trong các modul thì một số thuận lợi có thể thấy rõ sau đây 6/28/2014 Chương 3. Quản lý bộ nhớ 9 NHIỆM VỤ CỦA QUẢN LÝ BỘ NHỚ 3.1.5 Tổ chức bộ nhớ vật lý Bộ nhớ của máy tính gồm bộ nhớ chính và bộ nhớ phụ  Bộ nhớ chính: truy cập nhanh dữ liệu và chương trình chỉ giữ một khối lượng nhỏ, chỉ sử dụng tại thời điểm hiện tại không lưu trữ lâu dài trên nó và phải thường xuyên làm tươi.  Bộ nhớ phụ: truy cập chậm, nó lưu trữ lớn và cho phép lưu trữ chương trình và dữ liệu trong một khoảng thời gian dài. 6/28/2014 Chương 3. Quản lý bộ nhớ 10 NHIỆM VỤ CỦA QUẢN LÝ BỘ NHỚ 3.1.5 Tổ chức bộ nhớ vật lý Thông tin giữa bộ nhớ chính và bộ nhớ phụ là do hệ thống, người lập trình không thực hiện việc này vì nguyên nhân sau:  Không gian bộ nhớ chính dành cho các chương trình cùng với dữ liệu của nó thường là không đủ, người lập trình phải tiến hành thao tác như là Overlaying, chương trình và dữ liệu phải tổ chức thành modul và gán trong cùng một vùng của bộ nhớ. Trong đó chương trình chính chịu trách nhiệm chuyển modul vào ra khi cần thiết  Người lập trình không thể biết tại một thời điểm xác định có bao nhiêu không gian nhớ còn trống hoặc khi nào thì không gian nhớ sẽ trống 6/28/2014 Chương 3. Quản lý bộ nhớ 11 CẤU TRÚC CHƯƠNG TRÌNH  Một chương trình được thực hiện phải được nạp vào bộ nhớ chính, sau đó procssor đọc các lệnh từ bộ nhớ vào bên trong thanh ghi và giải mã và tổ cức thực hiện  Để nạp chương trình vào bộ nhớ thì bộ nhớ chính phải còn không gian trống lớn hơn kích thước chương trình  Nếu kích thước bộ nhớ chính không đủ cũng có thể nạp được nhiều chương trình có kích thước lớn hơn không gian bộ nhớ vào bộ nhớ. Yêu cầu người lập trình biết cách viết chương trình, dịch chương trình theo đúng cấu trúc chương trình chuẩn. Điều này phải có sự hỗ trợ của của trình biên dịch và các ngôn ngữ lập trình.  Các cấu trúc chương trình như tuyến tính, động, overlay, phân trang, phân đoạn 6/28/2014 Chương 3. Quản lý bộ nhớ 12 CẤU TRÚC CHƯƠNG TRÌNH 3.2.1 Cấu trúc chương trình tuyến tính  Cấu trúc này thì các modul, các thư viện đều được dịch thành một modul duy nhất chứa các thông tin cần thiết để chương trình có thể chạy độc lập  Một chương trình được viết bằng ngôn ngữ Pascal, có sử dụng thư viện chuẩn hoặc đồ họa. Sau khi biên dịch ta được một file . EXE  Khi mang file chương trình này đến một máy khác không cần phải cài chương trình pascal nhưng chương trình vẫn thực hiện được vì các thư viện mà chương trình sử dụng đã được tích hợp đầy đủ trong file chương trình EXE  Tập tin thực thi (.EXE) có tính độc lập cao, có tốc độ thực hiện chương trình cao vì chỉ cần nạp một lần 6/28/2014 Chương 3. Quản lý bộ nhớ 13 CẤU TRÚC CHƯƠNG TRÌNH 3.2.1 Cấu trúc chương trình tuyến tính Hạn chế của của chương trình dịch theo cấu trúc tuyến tính  Tốn bộ nhớ vì sau mỗi lần biên dịch thì kích thước chương trình tăng lên  Các modul, thư viện được sử dụng một lần nhưng lại chiếm bộ nhớ từ khi chương trình được nạp vào cho đến khi kết thúc  Hệ điều hành windows không hỗ trợ cấu trúc này vì nó không tiết kiệm được bộ nhớ, tốn bộ nhớ và làm cho sự đa chương giảm xuống 6/28/2014 Chương 3. Quản lý bộ nhớ 14 CẤU TRÚC CHƯƠNG TRÌNH 3.2.2 Cấu trúc chương trình động  Chương trình được viết dưới các modul riêng lẽ, mỗi modul thực hiện một chức năng nào đó  Cấu trúc động chương trình được biên dịch thành các modul riêng lẽ, các thư viện không được tích hợp vào trong modul chính. Như vậy với một chương trình nhưng dịch theo cấu trúc động thì nó tốn bộ nhớ nhỏ hơn nhưng tính độc lập của nó kém hơn tuyến tính  Cấu trúc động chương trình gồm modul chính và các modul khác. Modul chính có thể gọi modul khác của chương trình vào bộ nhớ  HĐH chỉ nạp modul chính vào bộ nhớ, modul chính chỉ chứa chủ yếu là các dữ liệu dùng chung, các thủ tục khởi, các lời gọi thủ tục, thư viện. Khi cần thì modul chính mới gọi các modul khác 6/28/2014 Chương 3. Quản lý bộ nhớ 15 CẤU TRÚC CHƯƠNG TRÌNH 3.2.2 Cấu trúc chương trình động  Khi nạp thêm modul vào bộ nhớ thì chỉ nạp một modul mà có thủ tục hay thư viên có sử dụng. Khi thực hiện xong thì nó có thể giải phóng bộ nhớ để cấp cho cho modul khác Như vậy cấu trúc động đáp ứng được mục tiêu tiết kiệm bộ nhớ của HĐH và sự đa chương của HĐH được tăng lên  Một chương trình viết bằng Visual basic dịch theo cấu trúc động thành các file EXE không thể chạy trên một máy khác nếu thiếu các tập tin OCX, DDL  Windows cung cấp nhiều DLL, mỗi DLL chứa một nhóm các thủ tục dịch vụ, DLL có thể sinh ra trong quá trình cài đặt một ứng dụng, các DLL này bị xóa, hỏng thì các ứng dụng không hoạt động được, vì lời gọi thủ tục không được đáp ứng 6/28/2014 Chương 3. Quản lý bộ nhớ 16 CẤU TRÚC CHƯƠNG TRÌNH 3.2.2 Cấu trúc chương trình động  Tập tin DLL hỗ trợ rất nhiều cho windows trong việc thực thi chương trình cấu trúc động, DLL chứa các thủ tục dịch vụ mà hầu hết các ứng dụng đều sử dụng nó. DLL không được nạp vào trong quá trình khởi động mà nó chỉ được nạp khi có một thủ tục dịch vụ gọi nó. Có nhiều chương trình, tiến trình sử dụng đồng thời các thủ tục DLL. HĐH giải phóng ngay DLL khi không còn chương trình, tiến trình nào sử dụng nữa  Việc thực thi chương trình cấu trúc động có hạn chế là chậm vì nó không được nạp vào tất cả vào bộ nhớ  Cấu trúc động tiết kiệm được bộ nhớ nên làm cho sư đa chương của HĐH tăng lên 6/28/2014 Chương 3. Quản lý bộ nhớ 17 CẤU TRÚC CHƯƠNG TRÌNH 3.2.3 Cấu trúc chương trình Overlay  Cấu trúc Overlay chương trình cũng được biên dịch thành các modul riêng lẽ và được phân thành các lớp, các modul trong cùng một lớp có thể khác nhau, kích thước của modul lớn nhất là kích thước của lớp  Modul của lớp 0 có thể nạp modul của lớp 1,2,3…vào bộ nhớ modul trong cùng lớp không được gọi lẫn nhau  Cấu trúc Overlay đòi người lập trình cung cấp đầy đủ các thông tin cần thiết như: chương trình gồm modul nào, modul gồm có thủ tục, thư viện nào, kích thước của modul và chương trình chia bao nhiêu lớp modul để cung cấp cho chương trình biên dịch xây dựng sơ đồ biên dịch và thực thi. Sơ đồ này gọi là sơ đồ Overlay 6/28/2014 Chương 3. Quản lý bộ nhớ 18 CẤU TRÚC CHƯƠNG TRÌNH 3.2.3 Cấu trúc chương trình Overlay  HĐH dùng sơ đồ Overlay để điều khiển thực thi chương trình  Các sơ đồ Overlay chứa trong chương trình, chứa trong một tập tin riêng và gọi là tập tin sơ đồ Overlay và nó được nạp đầu tiên khi HĐH thực hiện chương trình  Khi thực hiện chương trình Overlay HĐH chia không gian nhớ thành các đoạn nhớ có kích thước bằng với kích thước của các lớp modul chương trình và nạp sơ đồ overlay vào bộ nhớ, nạp modul ở lớp 0 và dùng sơ đồ Overlay để nạp các modul khác • Các modul phải nạp vào đúng đoạn bộ nhớ dành cho lớp • Modul được gọi nạp vào sau được quyền ghi đè lên modul cùng lớp đã nạp vào 6/28/2014 Chương 3. Quản lý bộ nhớ 19 CẤU TRÚC CHƯƠNG TRÌNH 3.2.3 Cấu trúc chương trình Overlay  Cấu trúc Overlay chỉ cần đủ bộ nhớ để nạp sơ đồ overlay và các modul lớn nhất trong lớp  Cấu trúc này có hạn chế là vừa tốn bộ nhớ để chứa sơ đồ overlay, vừa tốn bộ nhớ của các modul trong một lớp có sự chênh lệch lớn về kích thước  Ví dụ: Trong một lớp có một modul 5Kb và một modul 50Kb thì hệ điều hành phải dành ra một đoạn nhớ 50Kb cho lớp này, rõ ràng sẽ lãng phí 45Kb khi trong đoạn nhớ 50Kb chỉ chứa một modul 5Kb  Cấu trúc overlay đòi hỏi cao ở người lập trình, nên ít HĐH sử dụng 6/28/2014 Chương 3. Quản lý bộ nhớ 20 CẤU TRÚC CHƯƠNG TRÌNH 3.2.4 Cấu trúc chương trình phân trang  Cấu trúc phân trang các modul được biên dịch thành một modul duy nhất và được chia thành các phần có kích thước bằng nhau  Để thực hiện chương trình cấu trúc phân trang HĐH phải được phân trang gồm các không gian có kích thước bằng nhau, bằng với kích thước các trang chương trình gọi là các khung trang (Frame)  Khi thực hiện chương trình, HĐH có thể nạp tất cả các trang của chương trình vào tại các khung trang liên tiếp hoặc không liên tiếp trên bộ nhớ  HĐH phải xây dựng các bảng điều khiển trang (PCT: page control table) để biết được một trang đã được nạp vào bộ nhớ, nếu nạp rồi thì được chứa ở khung trang nào để xử lý 6/28/2014 Chương 3. Quản lý bộ nhớ 21 CẤU TRÚC CHƯƠNG TRÌNH 3.2.5 Cấu trúc chương trình phân đoạn  Cấu trúc phân đoạn các modul được biên dịch thành các modul riêng lẻ và gọi là các đoạn chương trình  Ví dụ: Nếu một chương trình EXE nào đó có 3 đoạn chương trình chính là code, data, stack và có một thủ tục gọi 2 thư viện thì chương trình này biên dịch thành 5 segment, 3code, 1data, 1stack  Để thực hiện các chương trình này bộ nhớ phải được phân đoạn, gồm các không gian nhớ có kích thước không thể bằng nhau, tương ứng với kích thước của các đoạn chương trình, gọi là các phân đoạn bộ nhớ  Khi thực hiện chương trình thì HĐH có thể nạp tất cả các đoạn của chương trình tại các phân đoạn liên tiếp hoặc không liên tiếp trên bộ nhớ 6/28/2014 Chương 3. Quản lý bộ nhớ 22 CẤU TRÚC CHƯƠNG TRÌNH 3.2.5 Cấu trúc chương trình phân đoạn  HĐH phải xây dựng các bảng điều khiển đoạn (SCT: segment control table), để biết được một đoạn đã được nạp vào bộ nhớ hay chưa, nếu đã nạp rồi thì được chứa ở phân đoạn nào Ưu điểm của phân trang và phân đoạn  Không yêu cầu cao ở người lập trình, được hỗ trợ từ các chương trình biên dịch, tiết kiệm được bộ nhớ  Hai cấu trúc này được các HĐH đa nhiệm, đa chương hỗ trợ nhiều và đặc biệt là HĐH có cài đặt sử dụng máy ảo  Ít xảy ra việc thiếu bộ nhớ vì chương trình có thể được đưa ra khỏi đĩa và đưa vào lại thời điểm thích hợp Hạn chế: tốn bộ nhớ để chứa PCT, SCT của chương trình, làm chậm tốc độ truy xuất dữ liệu trên bộ nhớ vì phải thông qua PCT, SCT 6/28/2014 Chương 3. Quản lý bộ nhớ 23 KỸ THUẬT CẤP PHÁT BỘ NHỚ CHÍNH 3.3.1 Kỹ thuật phân vùng cố định  Không gian địa chỉ được chia thành 2 phần cố định: • Phần nằm ở vùng địa chỉ thấp dùng để chứa chính HĐH • Phần còn lại là phần user program, sẵn sàng cho việc sử dụng của các tiến trình khi được nạp vào bộ nhớ chính.  Phần user progaram đối với: • HĐH đơn nhiệm: chỉ cấp cho 1 chương trình duy nhất, đơn giản, kiểm soát được sự truy xuất của người sử dụng. Bằng cách tạo ra một thanh ghi giới hạn địa chỉ. Khi truy xuất vào một địa chỉ nào đó thì HĐH so sanh với địa chỉ đã ghi trong thanh ghi giới hạn. Nếu nhỏ hơn không cho truy xuất, ngược lại cho truy xuất. Việc này có sự hỗ trợ phần cứng. 6/28/2014 Chương 3. Quản lý bộ nhớ 24 KỸ THUẬT CẤP PHÁT BỘ NHỚ CHÍNH 3.3.1 Kỹ thuật phân vùng cố định • HĐH đa nhiệm: cấp cho nhiều chương trình nên user program lại được phân ra thành nhiều phân vùng có kích thước bằng nhau hoặc không bằng nhau. Khi tiến trình nạp vào thì kích thước của nó phải nhỏ hơn kích thước của partition còn trống. Nếu không còn Partition còn trống thì HĐH phải chuyển một tiến trình (Swap out) nào đó ra ngoài, phải thỏa mãn: - Tiến trình đó có kích thước vừa đủ - Không ở trạng thái ready, running - Không có liên quan đến tiến trình running khác Lấy partition này nạp cho tiến trình vừa có yêu cầu 6/28/2014 Chương 3. Quản lý bộ nhớ 25 KỸ THUẬT CẤP PHÁT BỘ NHỚ CHÍNH 3.3.1 Kỹ thuật phân vùng cố định  Có 2 trở ngại đối với partition có kích thước bằng nhau: • Thứ nhất: chương trình có kích thước quá lớn với partition thì phải theo cấu trúc Overlay, chỉ nạp những phần cần thiết của chương trình vào trong bộ nhớ chính, khi có yêu cầu thì mới nạp các modul vào đúng partition của chương trình và sẽ ghi đè lên bất kỳ chương trình hoặc dữ liệu ở trong đó • Thứ hai: chương trình có kích thước nhỏ hơn với partition thì xảy ra hiện tượng phân mảnh bên trong bộ nhớ, gây lãng phí bộ nhớ. Ví dụ: có 3 không gian trống là 30KB nằm rãi rác trên bộ nhớ, khi nạp một modul có kích thước 12KB cũng không thực hiện được, hiện tượng này gọi là phân mảnh bộ nhớ. 6/28/2014 Chương 3. Quản lý bộ nhớ 26 KỸ THUẬT CẤP PHÁT BỘ NHỚ CHÍNH 3.3.1 Kỹ thuật phân vùng cố định  Khắc phục điều này sử dụng phân vùng có kích thước không bằng nhau bằng cách: Hệ điều hành New Process Hệ điều hành New Process 6/28/2014 Chương 3. Quản lý bộ nhớ 27 KỸ THUẬT CẤP PHÁT BỘ NHỚ CHÍNH 3.3.1 Kỹ thuật phân vùng cố định  Mỗi phân vùng có một hàng đợi: khi tiến trình cần nạp vào bộ nhớ thì nó đưa đến hàng đợi của phân vùng có kích thước vừa đủ với nó đưa nó vào hàng đợi  Hệ thống dùng hàng đợi chung cho tất cả các phân vùng: các tiến trình muốn được nạp vào phân vùng nhưng chưa được vào sẽ được đưa vào hàng đợi chung. Khi có phân vùng trống, hệ thống sẽ chọn một tiến trình có kích thước vừa đủ đưa vào phân vùng trống đó Hạn chế của phân vùng cố định  Số lượng các tiến trình có thể hoạt động trong hệ thống tại một thời điểm phụ thuộc vào số lượng các phân vùng cố định trên bộ nhớ  Kích thước của tiến trình nhỏ hơn kích thước của một phân vùng thì phân mảnh nội vi gây lãng phí trong việc sử dụng bộ nhớ 6/28/2014 Chương 3. Quản lý bộ nhớ 28 KỸ THUẬT CẤP PHÁT BỘ NHỚ CHÍNH 3.3.2 Kỹ thuật phân vùng động  Số lượng các phân vùng trên bộ nhớ và kích thước của mỗi phân vùng có thể thay đổi. Phần user program trên bộ nhớ không được phân chia trước mà khi có một tiến trình được nạp vào bộ nhớ thì HĐH cấp cho nó một không gian vừa đủ để chứa tiến trình, phần còn lại để sẵn sàng cấp cho tiến trình khác sau này 6/28/2014 Chương 3. Quản lý bộ nhớ 29 KỸ THUẬT CẤP PHÁT BỘ NHỚ CHÍNH 3.3.2 Kỹ thuật phân vùng động  Khi tiến trình yêu cầu thì nó tìm vùng nhớ vừa đủ, nếu phân vùng lớn thì một phần được cấp cho tiến trình, phần còn lại tìm và kết hợp với các tiến trình khác để tạo thành vùng lớn hơn cấp cho các tiến trình có yêu cầu. Điều này làm giảm tốc độ hệ thống, hơn nữa khi tiến trình Swap out và phải swap in vào lại để hoạt động  Kỹ thuật phân vùng động HĐH quản lý các khối nhớ đã cấp phát hay còn trống bằng sử dụng sơ đồ bit và danh sách liên kết: 6/28/2014 Chương 3. Quản lý bộ nhớ 30 KỸ THUẬT CẤP PHÁT BỘ NHỚ CHÍNH 3.3.2 Kỹ thuật phân vùng động  Bảng đồ bit 6/28/2014 Chương 3. Quản lý bộ nhớ 31 KỸ THUẬT CẤP PHÁT BỘ NHỚ CHÍNH 3.3.2 Kỹ thuật phân vùng động  Danh sách liên kết H 0 2 P 2 3 H 5 3 P 8 2 H 10 4 P 14 3 H 17 1 P 18 2 20 2 6/28/2014 Chương 3. Quản lý bộ nhớ 32 KỸ THUẬT CẤP PHÁT BỘ NHỚ CHÍNH 3.3.2 Kỹ thuật phân vùng động  Khi tiến trình cần được nạp vào bộ nhớ thì HĐH phải lựa chọn khối nhớ trống phù hợp nạp vào sao cho việc lựa chọn này dẫn đến việc sử dụng bộ nhớ chính là hiệu quả nhất • Best-fit: duyệt tất cả để chọn khối nhớ có kích thước vừa đúng bằng kích thước của tiến trình cần được nạp vào bộ nhớ • First-fit: duyệt tất cả các khối nhớ trống trong bộ nhớ và sẽ chọn khối nhớ trống đầu tiên có kích thước đủ lớn để nạp tiến trình • Next-fit: hệ điều hành bắt đầu quét từ khối nhớ trống kế sau khối nhớ vừa được cấp phát và chọn khối nhớ trống kế tiếp đủ lớn để nạp tiến trình 6/28/2014 Chương 3. Quản lý bộ nhớ 33 KỸ THUẬT CẤP PHÁT BỘ NHỚ CHÍNH 3.3.2 Kỹ thuật phân vùng động Ví dụ: giả sử có các khối nhớ như hình sau và có 1 tiến trình 16K cần được nạp vào bộ nhớ 8k 12k 22k 18k 8k 6k 14k 36k khối nhớ vừa được cấp phát cuối cùng  Khối nhớ 22k nếu theo thuật toán First-fit, phân mảnh 6k  Khối nhớ 18k nếu theo thuật toán Best-fit, phân mảnh 2k  Khối nhớ 36k nếu theo thuật toán Next-fit, phân mảnh 20k 6/28/2014 Chương 3. Quản lý bộ nhớ 34 KỸ THUẬT CẤP PHÁT BỘ NHỚ CHÍNH 3.