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

GV: Đỗ Công ĐứcKhoa khoa học máy tínhNGUYÊN LÝ HỆ ĐIỀU HÀNH (3 Tín chỉ)Date1Chương 3. Quản lý bộ nhớ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ể.Date2Chương 3. Quản lý bộ nhớChương 3: QUẢN LÝ BỘ NHỚ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ý.Date3Chương 3. Quản lý bộ nhớ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ớ ảo3.5. Các thuật toán thay trang3.6. Cấp phát khung trangDate4Chương 3. Quản lý bộ nhớNHIỆM VỤ CỦA QUẢN LÝ BỘ NHỚ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.Bộ phận quản lý bộ nhớ phải thực hiện. Date5Chương 3. Quản lý bộ nhớNHIỆM VỤ CỦA QUẢN LÝ BỘ NHỚ 3.1.1 Sự tái định vị (Relocation)Bộ nhớ được chia sẻ cho nhiều tiến trình 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 đủ bộ nhớ chính để nạp thì chương trình đang chạy thì có thể Swap out ra đĩa và được Swap in vào thời điểm thích hợp nhưng phải swap in đúng vị trí đã nạp trước đó.Đô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 đó.Date6Chương 3. Quản lý bộ nhớNHIỆM VỤ CỦA QUẢN LÝ BỘ NHỚ 3.1.2 Bảo vệ bộ nhớ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.Phải biết địa chỉ không gian của các tiến trình khác, kiểm tra các địa chỉ truy xuất 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ĐH, ngoại trừ vùng dữ liệu mà HĐH cung cấp cho chương trình người sử dụng. Date7Chương 3. Quản lý bộ nhớNHIỆM VỤ CỦA QUẢN LÝ BỘ NHỚ 3.1.3 Chia sẻ bộ nhớ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. Date8Chương 3. Quản lý bộ nhớNHIỆM VỤ CỦA QUẢN LÝ BỘ NHỚ 3.1.4 Tổ chức bộ nhớ LogicCác modul có thể được viết và biên dịch độc lập và có thể tham chiếu đến các modul khác. 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.Đa số các chương trình đều được chia thành các modul:Date9Chương 3. Quản lý bộ nhớ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.Date10Chương 3. Quản lý bộ nhớ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.Bộ nhớ chính dành cho chương trình cùng với dữ liệu của nó thường là không đủ, 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ể xác định không gian nhớ còn trống hoặc khi nào thì không gian nhớ sẽ trống mà việc này do bộ phận quản lý bộ nhớ thực hiện.Date11Chương 3. Quản lý bộ nhớCẤU TRÚC CHƯƠNG TRÌNHChương trình khi thực hiện phải nạp vào bộ nhớ chính, processor đọ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.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 bộ nhớ chính không đủ cũng có thể nạp được. Người lập trình viết, dịch chương trình theo đúng cấu trúc chuẩn có sự hỗ trợ của trình biên dịch và các ngôn ngữ.Các cấu trúc chương trình như tuyến tính, động, overlay, phân trang, phân đoạn.Date12Chương 3. Quản lý bộ nhớCẤU TRÚC CHƯƠNG TRÌNH 3.2.1 Cấu trúc chương trình tuyến tínhCác modul, thư viện dịch thành một modul chứa các thông tin cần thiết để chương trình có thể chạy độc lập.Chương trình viết bằ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 .EXEMang file EXE đến máy bất kỳ cũng chạy được không cần phải cài pascal.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.Date13Chương 3. Quản lý bộ nhớCẤU TRÚC CHƯƠNG TRÌNH 3.2.1 Cấu trúc chương trình tuyến tínhHạ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ĐH 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.Date14Chương 3. Quản lý bộ nhớCẤU TRÚC CHƯƠNG TRÌNH3.2.2 Cấu trúc chương trình độngChươ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.Date15Chương 3. Quản lý bộ nhớCẤU TRÚC CHƯƠNG TRÌNH 3.2.2 Cấu trúc chương trình độngCấ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 tạo, 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. Date16Chương 3. Quản lý bộ nhớCẤU TRÚC CHƯƠNG TRÌNH3.2.2 Cấu trúc chương trình độngNạp 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.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 (Object Component eXtension), DLL (Dynamic Link Library) . Windows có nhiều DLL chứa một nhóm các thủ tục dịch vụ, DLL sinh ra trong cài đặt một ứng dụng, các DLL bị xóa, hỏng thì ứng dụng không hoạt động được, vì lời gọi thủ tục không được đáp ứng.Date17Chương 3. Quản lý bộ nhớCẤU TRÚC CHƯƠNG TRÌNH3.2.2 Cấu trúc chương trình độngTậ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ó. 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.Date18Chương 3. Quản lý bộ nhớCẤU TRÚC CHƯƠNG TRÌNH 3.2.3 Cấu trúc chương trình OverlayCấu trúc Overlay, chương trình được biên dịch thành các modul riêng lẽ và được phân thành các lớp, 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,3vào bộ nhớ, modul trong cùng lớp không được gọi lẫn nhau.Cấu trúc Overlay cần biết thông tin như: chương trình gồm modul, modul gồm thủ tục, thư viện nào, kích thước, có bao nhiêu lớp để cung cấp khi 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.Date19Chương 3. Quản lý bộ nhớCẤU TRÚC CHƯƠNG TRÌNH 3.2.3 Cấu trúc chương trình OverlayHĐH dùng Overlay để điều khiển thực thi chương trình.Các sơ đồ Overlay chứa trong một tập tin gọi là tập tin sơ đồ Overlay và nó được nạp đầu tiên khi HĐH thực hiện.Với 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.Date20Chương 3. Quản lý bộ nhớCẤU TRÚC CHƯƠNG TRÌNH 3.2.3 Cấu trúc chương trình OverlayCấ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 lớp có modul 5Kb và 50Kb mất đoạn nhớ 50Kb cho lớp này, 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.Date21Chương 3. Quản lý bộ nhớCẤU TRÚC CHƯƠNG TRÌNH 3.2.4 Cấu trúc chương trình phân trangPhân trang các modul được biên dịch thành một modul duy nhất, chia thành các phần có kích thước bằng nhau. Cấu trúc phân trang HĐH phải phân trang 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, HĐH nạp 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 xây dựng 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ý.Date22Chương 3. Quản lý bộ nhớCẤU TRÚC CHƯƠNG TRÌNH 3.2.5 Cấu trúc chương trình phân đoạnPhâ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. Bộ nhớ phải được phân đoạn, có kích thước không 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, HĐH nạp 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ớ.Date23Chương 3. Quản lý bộ nhớCẤU TRÚC CHƯƠNG TRÌNH 3.2.5 Cấu trúc chương trình phân đoạnHĐH xây dựng SCT: segment control table, để biết đoạn đã được nạp vào bộ nhớ hay chưa và ở phân đoạn nào. Ưu điểm của phân trang và phân đoạn:Có hỗ trợ từ chương trình biên dịch, tiết kiệm bộ nhớ.HĐH đa nhiệm, hỗ trợ nhiều cho 2 cấu trúc này 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, làm chậm tốc độ truy xuất dữ liệu trên bộ nhớ vì phải thông qua PCT, SCT.Date24Chương 3. Quản lý bộ nhớKỸ THUẬT CẤP PHÁT BỘ NHỚ CHÍNH 3.3.1 Kỹ thuật phân vùng cố địnhKhông gian địa chỉ được chia thành 2 phần cố định: Phần 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ớ.Phần user program đối với:HĐH đơn nhiệm: kiểm soát được sự truy xuất, bằng thanh ghi giới hạn địa chỉ. Khi truy xuất vào một địa chỉ thì HĐH so sánh đị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. Date25Chương 3. Quản lý bộ nhớKỸ THUẬT CẤP PHÁT BỘ NHỚ CHÍNH 3.3.1 Kỹ thuật phân vùng cố địnhHĐH đa nhiệm: user program phân ra thành nhiều phân vùng. 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 trống thì HĐH phải chuyển một tiến trình (Swap out) ra ngoài: - 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.Date26Chương 3. Quản lý bộ nhớKỸ THUẬT CẤP PHÁT BỘ NHỚ CHÍNH 3.3.1 Kỹ thuật phân vùng cố địnhCó hạn chế đối với partition có kích thước bằng nhau:CT 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, 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ớ.Date27Chương 3. Quản lý bộ nhớKỸ THUẬT CẤP PHÁT BỘ NHỚ CHÍNH 3.3.1 Kỹ thuật phân vùng cố địnhKhắ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ànhNewProcessHệ điều hànhNewProcessDate28Chương 3. Quản lý bộ nhớKỸ THUẬT CẤP PHÁT BỘ NHỚ CHÍNH 3.3.1 Kỹ thuật phân vùng cố địnhMỗi phân vùng có một hàng đợi.Hệ thống dùng hàng đợi chung cho tất cả các phân vùng.Hạn chế của phân vùng cố định Số lượng các tiến trình phụ thuộc vào số lượng các phân vùng cố định trên bộ nhớ. Kích thước 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ớ. Date29Chương 3. Quản lý bộ nhớKỸ THUẬT CẤP PHÁT BỘ NHỚ CHÍNH 3.3.2 Kỹ thuật phân vùng độngSố lượng, kích thước của mỗi phân vùng thay đổi. Phần user program không được phân chia trước mà khi có tiến trình được nạp 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. Date30Chương 3. Quản lý bộ nhớKỸ THUẬT CẤP PHÁT BỘ NHỚ CHÍNH 3.3.2 Kỹ thuật phân vùng độngKhi 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ì: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ơ đồ bit và danh sách liên kết. Một phần được cấp cho tiến trình. Phần còn lại là trả lại hoặc tìm các vùng nhớ còn trống để kết hợp thành một vùng nhớ lớn hơn để đáp ứng cho tiến trình có yêu cầu. Date31Chương 3. Quản lý bộ nhớKỸ THUẬT CẤP PHÁT BỘ NHỚ CHÍNH 3.3.2 Kỹ thuật phân vùng độngBảng đồ bitMỗi đơn vị cấp phát đại diện 1bit, 0 là trạng thái đang tự do, 1 là trạng thái đã cấp phát. Khi nạp tiến trình k đơn vị cấp phát thì hệ thống tìm k bit có đơn vị là 0. Date32Chương 3. Quản lý bộ nhớKỸ THUẬT CẤP PHÁT BỘ NHỚ CHÍNH 3.3.2 Kỹ thuật phân vùng độngDanh sách liên kếtH 0 2P 2 3H 5 3P 8 2H 10 4P 14 3H 17 1P 18 2 20 2Bít đầu tiên cho biết đã được cấp hay chưa, P đã cấp, H chưa cấp. Bít thứ 2 cho biết thứ tự của đơn vị cấp phátBít thứ 3 cho biết block gồm bao nhiêu đơn vị cấp phát. Date33Chương 3. Quản lý bộ nhớKỸ THUẬT CẤP PHÁT BỘ NHỚ CHÍNH 3.3.2 Kỹ thuật phân vùng độngTiến trình đượ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. 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.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.Next-fit: HĐH 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. Date34Chương 3. Quản lý bộ nhớKỸ THUẬT CẤP PHÁT BỘ NHỚ CHÍNH 3.3.2 Kỹ thuật phân vùng độngVí 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ớ. 8k12k22k18k8k6k14k36kkhối nhớ vừađược cấp phátcuối cùngKhố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 Date35Chương 3. Quản lý bộ nhớKỸ THUẬT CẤP PHÁT BỘ NHỚ CHÍNH 3.3.2 Kỹ thuật phân vùng độngCác HĐH không cài đặt trước một thuật toán nào cả mà tùy vào trường hợp mà chọn thuật toán cấp phát sao cho hạn chế sự phân mảnh. First-fit: Đơn giản, dễ cài đặt, tốc độ, có hiệu quả cao nhất Next-fit:Thường sử dụng được các khối nhớ trống ở cuối vùng nhớ thường có kích thước lớn, hạn chế sự phân mảnh Best-fit: Hiệu suất thấp vì phải duyệt qua hết tất cả các khối tìm khối nhớ bằng kích thước của tiến trình yêu cầu, giảm hiệu suất và chọn khối nhớ vừ đủ nên dẫn đến sự phân mảnh lớn vì có nhiều khối nhớ quá nhỏ Date36Chương 3. Quản lý bộ nhớKỸ THUẬT CẤP PHÁT BỘ NHỚ CHÍNH 3.3.2 Kỹ thuật phân vùng độngThiếu bộ nhớ HĐH Swap out tiến trình ra ngoài sau đó swap in. Khi nạp lại thì có thể đúng hoặc không đúng với phân vùng nạp đầu tiên. Sự thay đổi này làm ảnh hưởng đến việc truy xuất dữ liệu.Ví dụ CT có code tại địa chỉ 100K, nếu được nạp vào phân vùng 1 có địa chỉ 100k thì truy xuất là 200K.Nếu nạp tại phân vùng 2 có địa chỉ 200k thì truy xuất 300k. Để giải quyết vấn đề này HĐH phải thực hiện công tác tái định vị tiến trình vào bộ nhớ nhưng tránh việc truy xuất đến vùng nhớ của tiến trình khác.Date37Chương 3. Quản lý bộ nhớKỸ THUẬT CẤP PHÁT BỘ NHỚ CHÍNH 3.3.2 Kỹ thuật phân vùng độngSử dụng 2 thanh ghi đặc biệt.Thanh ghi cơ sở (base register): Dùng để ghi địa chỉ cơ sở của tiến trình tiến trình được nạp vào bộ nhớ.Thanh ghi giới hạn (limit register): Dùng để ghi địa chỉ cuối cùng của tiến trình trong bộ nhớ. Date38Chương 3. Quản lý bộ nhớKỸ THUẬT CẤP PHÁT BỘ NHỚ CHÍNH 3.3.2 Kỹ thuật phân vùng độngViệc thiết lập giá trị của các thanh ghi này được thực hiện cả khi tiến trình lần đầu tiên được nạp và swap in vào lại bộ nhớ. Thứ nhất: cộng địa chỉ ô nhớ với giá trị địa chỉ trong thanh ghi cơ sở để có được địa chỉ tuyệt đối của ô nhớ cần truy xuất. Thứ hai: địa chỉ được so sánh với thanh ghi giới hạn: nếu nằm trong giới hạn cho truy xuất, ngược lại thì ngắt lỗi truy xuất bộ nhớ.Date39Chương 3. Quản lý bộ nhớKỸ THUẬT CẤP PHÁT BỘ NHỚ CHÍNH 3.3.2 Kỹ thuật phân vùng độngHạn chế của kỹ thuật này là phân mảnh bộ nhớ và lãng phí bộ nhớ. Để khắc phục HĐH sử dụng phân trang/phân đoạnĐịa chỉ tương đốiBase RegisterLimit RegisterCộngStackĐiều khiểntiến trìnhSo sánhProgramDataGởi ngắt đến hệ điều hànhTiến trình trong bộ nhớ Date40Chương 3. Quản lý bộ nhớKỸ THUẬT CẤP PHÁT BỘ NHỚ CHÍNH 3.3.3 Kỹ thuật phân trang đơnKhông gian địa chỉ được chia thành các phần có kích thước cố định bằng nhau gọi là khung trang (Frame page).Không gian địa chỉ của tiến trình được chia bằng với khung trang gọi là trang (page)Khi tiến trình nạp vào bộ nhớ thì nạp vào các khung trang trống. HĐH theo dõi các khung trang còn trống hay đã cấp phát vào một danh sách và danh sách này được update thường xuyên.Date41Chương 3. Quản lý bộ nhớKỸ THUẬT CẤP PHÁT BỘ NHỚ CHÍNH 3.3.3 Kỹ thuật phân trang đơnHĐH dùng PCT Page control table để theo dõi các trang trên bộ nhớPCTDate42Chương 3. Quản lý bộ nhớKỸ THUẬT CẤP PHÁT BỘ NHỚ CHÍNH 3.3.3 Kỹ thuật phân trang đơnCác bảng trang có kích thước nhỏ chứa trong thanh ghi, ngược lại chứa trong bộ nhớ chính dùng thanh ghi để lưu trữ địa chỉ bắt đầu nơi lưu trữ bảng trang gọi là PTBR: page table base register. Khi cần truy xuất bộ nhớ CPU phát ra địa chỉ logic gồm:Số hiệu trang (page): Số hiệu trang cần truy xuất.Địa chỉ tương đối trong trang (offset): kết hợp với địa chỉ bắt đầu của trang để xác định địa chỉ vật lý của ô nhớ cần truy xuất. Date43Chương 3. Quản lý bộ nhớKỸ THUẬT CẤP PHÁT BỘ NHỚ CHÍNH 3.3.4 Kỹ thuật phân đoạn đơnKhông gian địa chỉ bộ nhớ vật lý được chia thành các phần có kích thước cố định không bằng nhau gọi là phân đoạn (Segment). Mỗi phân đoạn bao gồm số hiệu phân đoạn và kích thước của nó. Khi một tiến trình được nạp vào bộ nhớ thì tất cả các đoạn của nó sẽ được nạp vào các phân đoạn còn trống khác nhau trên bộ nhớ. Date44Chương 3. Quản lý bộ nhớKỸ THUẬT CẤP PHÁT BỘ NHỚ CHÍNH 3.3.4 Kỹ thuật phân đoạn đơnHĐH sử dụng bảng SCT (Segment control table) để theo dõi các đoạn tiến trình khác nhau trên bộ nhớ. Bảng này có 2 trường: Trường thứ nhất: Địa chỉ cơ sở (base) của phân đoạn mà đoạn chương trình tương ứng được nạp. Trường thứ hai: Cho biết độ dài, giới hạn (length/limit) của phân đoạn và có tác dụng dùng để kiểm soát sự truy xuấtCác bảng phân đoạn có kích thước nhỏ chứa trong các thanh ghi, ngược lại được chứa trong bộ nhớ chính, HĐH dùng thanh ghi lưu trữ địa chỉ bắt đầu nơi lưu trữ bảng phân đoạn gọi là thanh ghi STBR: Segment table base register. Date45Chương 3. Quản lý bộ nhớKỸ THUẬT BỘ NHỚ ẢO 3.4.1 Bộ nhớ ảoKỹ thuật bộ nhớ ảo là kỹ thuật hiện đại giải quyết sự giới hạn bộ nhớ chính của máy tínhKỹ thuật cấp phát bộ nhớ phân trang/phân đoạn có đặc điểm:Địa chỉ tham chiếu là địa chỉ logíc và được chuyển thành địa chỉ vật lý một cách tự động. Như vậy một tiến trình swap out và swap in lại không cần phải đúng địa chỉ đã swap out.Một tiến trình có thể chia thành nhiều trang đoạn khác nhau và có thể nạp vào các vị trí liên tục trong bộ nhớ trong quá trình thực hiện tiến trình.Date46Chương 3. Quản lý bộ nhớKỸ THUẬT BỘ NHỚ ẢO 3.4.1 Bộ nhớ ảoCòn hạn chế là phải nạp tất cả các trang/đoạn vào bộ nhớ vì thế kích thước chương trình ngày càng lớn. Kỹ thuật bộ nhớ ảo vẫn dựa vào kỹ thuật phân trang/đoạnBộ nhớ ảo không nạp tất cả các trang/đoạn vào bộ nhớ mà chỉ nạp những trang/đoạn cần thiết.Khi nạp không còn trang/đoạn trống thì đưa các trang/đoạn swap out ra ngoài để lấy không gian nạp bộ nhớ cho các tiến trình khác yêu cầu. Các tiến trình bị swap out sẽ swap in vào thời điểm thích hợp. Date47Chương 3. Quản lý bộ nhớKỸ THUẬT BỘ NHỚ ẢO 3.4.1 Bộ nhớ ảoĐể cài đặt bộ nhớ ảo thì HĐH phải:Không gian bộ nhớ phụ cần thiết chứa các trang/đoạn không gian để swap out, không gian đĩa này gọi là không gian swap.Theo dõi không gian các trang/đoạn nằm trên bộ nhớ chính/phụ bằng một bít present vào PCT, SCT.Dựa vào tiêu chuẩn để lựa chọn một trang/đoạn nào đó trên bộ nhớ chính swap out ra ngoài đĩa.Sử dụng bộ nhớ ảo có lợi ích sau: HĐH được nạp nhiều bộ nhớ hơn vào trong bộ nhớ, ít xảy ra trường hợp thiếu bộ nhớ vì không nạp hết tất cả hoặc swap out.Nạp bộ nhớ của tiến trình lớn hơn địa chỉ của bộ nhớ vật lý. Date48Chương 3. Quản lý bộ nhớKỸ THUẬT BỘ NHỚ ẢO 3.4.1 Bộ nhớ ảoBộ nhớ ảo là một kỹ thuật không cần nạp tất cả tiến trình vào bộ nhớ. Các trang (đoạn) của một tiến trình ở trên bộ nhớ phụ, gọi là bộ nhớ ảo của tiến trình. Bộ nhớ ảo đã mở rộng được không gian bộ nhớ vật lý của hệ thống, chuyển đổi từ địa chỉ ảo sang địa chỉ vật lý thực do bộ phận quản lý bộ nhớ của HĐH và processor thực hiện. Date49Chương 3. Quản lý bộ nhớKỸ THUẬT BỘ NHỚ ẢO 3.4.2 Cài đặt bộ nhớ ảo3.4.2.1 Sự phân trang: Mỗi trang sở hữu một bảng trang riêng theo dõi việc các tiến trình Khi nạp chỉ nạp vài trang nên phải có: Bít thứ nhất để biết trang tương của tiến trình có trên bộ nhớ. Bít thứ 2 để biết page có sự thay đổi hay không so với lần nạp gần đây nhất hay không. Date50Chương 3. Quản lý bộ nhớKỸ THUẬT BỘ NHỚ ẢO 3.4.2 Cài đặt bộ nhớ ảo3.4.2.1 Sự phân trang: Bit P (present): cho biết trang tương ứng ở trên bộ nhớ chính P=1, phụ P=0 Bit M (Modify): cho biết có thay đổi hay không, nếu không thay đổi thì không ghi lại nội dung khi đưa ra bộ nhớ ngoài.Date51Chương 3. Quản lý bộ nhớKỸ THUẬT BỘ NHỚ ẢO 3.4.2 Cài đặt bộ nhớ ảo3.4.2.2 Sự phân đoạn: Sự phân đoạn cho phép ta xem như nó là một tập không gian nhớ hoặc các đoạn có địa chỉ được xác định. Trong phân đoạn mỗi tiến trình sở hữu một bảng đoạn riêng, theo dõi các tiến trình nạp vào các đoạn. Trong bảng đoạn sẽ chứa nhiều thông tin phức tạp hơn nên cũng có bit P và M. Date52Chương 3. Quản lý bộ nhớKỸ THUẬT BỘ NHỚ ẢO 3.4.2 Cài đặt bộ nhớ ảo3.4.2.2 Sự phân đoạn: Bit P (Present): Cho biết đoạn tương ứng đang ở trên bộ nhớ chính P=1, phụ P=0. Bit M (Modify): Cho biết nội dung của đoạn tương ứng có bị thay đổi hay không so với lần nạp gần đây nhất. Date53Chương 3. Quản lý bộ nhớKỸ THUẬT BỘ NHỚ ẢO 3.4.2 Cài đặt bộ nhớ ảo3.4.2.3 Kết hợp sự phân trang và phân đoạn: Phân trang loại bỏ được hiện tượng phân mảnh nội vi. Phân đoạn có khả năng điều khiển các cấu trúc dữ liệu lớn dần và hỗ trợ chia sẻ và bảo vệ bộ nhớ. HĐH hiện nay kết hợp với sự hỗ trợ phần cứng processor và phần mềm để cài đặt kết hợp cả hai kỹ thuật phân trang và phân đoạn. Kết hợp phân trang và phân đoạn là không gian địa chỉ bộ nhớ được chia thành các đoạn, mỗi đoạn chia thành các trang có kích thước cố định bằng nhau. Date54Chương 3. Quản lý bộ nhớKỸ THUẬT BỘ NHỚ ẢO 3.4.2 Cài đặt bộ nhớ ảo3.4.2.4 Bộ nhớ ảo và lỗi page: Sự khác nhau giữa kỹ thuật phân trang đơn và kỹ thuật bộ nhớ ảo theo kiểu phân trang. Trường hợp a: nạp tất cả cá page của các tiến trình vào bộ nhớ. Chỉ nạp page 0 và page 2 vào bộ nhớ. Date55Chương 3. Quản lý bộ nhớCÁC THUẬT TOÁN THAY TRANGKhi lỗi trang HĐH tìm page trên bộ nhớ chính đưa ra đĩa, lấy Frame trống để xử lý lỗi trang.Khi chọn page ra đĩa phải chọn phải đảm bảo:Không ảnh hưởng đến tiến trình khác.Ít có nguy có xảy ra lỗi trang trở lại nhất. Không làm cho hệ thống trì trệ.Các thuật toán khác nhau sẽ có các tiêu chí swap out các trang khác nhau nhưng phải đơn giản và phải ít xảy ra lỗi trang nhất.Để so sánh các thuật toán lỗi trang thì ta phải xét trong cùng một điều kiện: số lượng frame, các trang cần nạp. Date56Chương 3. Quản lý bộ nhớCẤP PHÁT KHUNG TRANGKỹ thuật bộ nhớ ảo không nạp tất cả các trang vào bộ nhớ chính. Vì vậy HĐH phải quyết định nạp bao nhiêu tiến trình vào bộ nhớ thì phải lựa chọn.Nạp một số lượng nhỏ các page của tiến trình vào bộ nhớ thì HĐH có thể được nạp nhiều tiến trình vào một thời điểm làm tăng sự đa chương.Date57Chương 3. Quản lý bộ nhớ