›
›

Khoa khoa học máy tính - Nguyên lý hệ điều hành

pdf 50 trang vanle 2610
Download
Bạn đang xem 20 trang mẫu của tài liệu "Khoa khoa học máy tính - Nguyên lý hệ điều hành", để 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:

  • pdfkhoa_khoa_hoc_may_tinh_nguyen_ly_he_dieu_hanh.pdf

Nội dung text: Khoa khoa học máy tính - Nguyên lý hệ điều hành

  1. NGUYÊN LÝ HỆ ĐIỀU HÀNH (3 Tín chỉ) GV: Đỗ Công Đức Khoa khoa học máy tính
  2. ChươngChương 3:3: QUQUẢẢNN LÝLÝ BBỘỘ NHNHỚỚ . 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ớ 2
  3. ChươngChương 3:3: QUQUẢẢNN LÝLÝ BBỘỘ NHNHỚỚ 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ớ 3
  4. NHINHIỆỆMM VVỤỤ CCỦỦAA QUQUẢẢNN LÝLÝ BBỘỘ NHNHỚỚ . 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ớ 4
  5. NHINHIỆỆMM VVỤỤ CCỦỦAA QUQUẢẢNN LÝLÝ BBỘỘ NHNHỚỚ 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ớ 5
  6. NHINHIỆỆMM VVỤỤ CCỦỦAA QUQUẢẢNN LÝLÝ BBỘỘ NHNHỚỚ 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ớ 6
  7. NHINHIỆỆMM VVỤỤ CCỦỦAA QUQUẢẢNN LÝLÝ BBỘỘ NHNHỚỚ 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ớ 7
  8. NHINHIỆỆMM VVỤỤ CCỦỦAA QUQUẢẢNN LÝLÝ BBỘỘ NHNHỚỚ 3.1.4 Tổ chức bộ nhớ Logic Đ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 . 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) 6/28/2014 Chương 3. Quản lý bộ nhớ 8
  9. NHINHIỆỆMM VVỤỤ CCỦỦAA QUQUẢẢNN LÝLÝ BBỘỘ NHNHỚỚ 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ớ 9
  10. NHINHIỆỆMM VVỤỤ CCỦỦAA QUQUẢẢNN LÝLÝ BBỘỘ NHNHỚỚ 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ớ 10
  11. CCẤẤUU TRTRÚÚCC CHƯƠNGCHƯƠNG TRTRÌNHÌ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ớ 11
  12. CCẤẤUU TRTRÚÚCC CHƯƠNGCHƯƠNG TRTRÌNHÌ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ớ 12
  13. CCẤẤUU TRTRÚÚCC CHƯƠNGCHƯƠNG TRTRÌNHÌ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ớ 13
  14. CCẤẤUU TRTRÚÚCC CHƯƠNGCHƯƠNG TRTRÌNHÌ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ớ 14
  15. CCẤẤUU TRTRÚÚCC CHƯƠNGCHƯƠNG TRTRÌNHÌ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ớ 15
  16. CCẤẤUU TRTRÚÚCC CHƯƠNGCHƯƠNG TRTRÌNHÌ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ớ 16
  17. CCẤẤUU TRTRÚÚCC CHƯƠNGCHƯƠNG TRTRÌNHÌ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ớ 17
  18. CCẤẤUU TRTRÚÚCC CHƯƠNGCHƯƠNG TRTRÌNHÌ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ớ 18
  19. CCẤẤUU TRTRÚÚCC CHƯƠNGCHƯƠNG TRTRÌNHÌ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ớ 19
  20. CCẤẤUU TRTRÚÚCC CHƯƠNGCHƯƠNG TRTRÌNHÌ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ớ 20
  21. CCẤẤUU TRTRÚÚCC CHƯƠNGCHƯƠNG TRTRÌNHÌ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ớ 21
  22. CCẤẤUU TRTRÚÚCC CHƯƠNGCHƯƠNG TRTRÌNHÌ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ớ 22
  23. KKỸỸ THUTHUẬẬTT CCẤẤPP PHPHÁÁTT BBỘỘ NHNHỚỚ CHCHÍÍNHNH 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ớ 23
  24. KKỸỸ THUTHUẬẬTT CCẤẤPP PHPHÁÁTT BBỘỘ NHNHỚỚ CHCHÍÍNHNH 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ớ 24
  25. KKỸỸ THUTHUẬẬTT CCẤẤPP PHPHÁÁTT BBỘỘ NHNHỚỚ CHCHÍÍNHNH 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ớ 25
  26. KKỸỸ THUTHUẬẬTT CCẤẤPP PHPHÁÁTT BBỘỘ NHNHỚỚ CHCHÍÍNHNH 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: New Process New Process Hệ điều Hệ điều hành hành 6/28/2014 Chương 3. Quản lý bộ nhớ 26
  27. KKỸỸ THUTHUẬẬTT CCẤẤPP PHPHÁÁTT BBỘỘ NHNHỚỚ CHCHÍÍNHNH 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ớ 27
  28. KKỸỸ THUTHUẬẬTT CCẤẤPP PHPHÁÁTT BBỘỘ NHNHỚỚ CHCHÍÍNHNH 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ớ 28
  29. KKỸỸ THUTHUẬẬTT CCẤẤPP PHPHÁÁTT BBỘỘ NHNHỚỚ CHCHÍÍNHNH 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ớ 29
  30. KKỸỸ THUTHUẬẬTT CCẤẤPP PHPHÁÁTT BBỘỘ NHNHỚỚ CHCHÍÍNHNH 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ớ 30
  31. KKỸỸ THUTHUẬẬTT CCẤẤPP PHPHÁÁTT BBỘỘ NHNHỚỚ CHCHÍÍNHNH 3.3.2 Kỹ thuật phân vùng động . Danh sách liên kết H 5 3 H 0 2 P 2 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ớ 31
  32. KKỸỸ THUTHUẬẬTT CCẤẤPP PHPHÁÁTT BBỘỘ NHNHỚỚ CHCHÍÍNHNH 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ớ 32
  33. KKỸỸ THUTHUẬẬTT CCẤẤPP PHPHÁÁTT BBỘỘ NHNHỚỚ CHCHÍÍNHNH 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 khối nhớ vừa được cấp phát 8k 6k 14k 36k 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ớ 33
  34. KKỸỸ THUTHUẬẬTT CCẤẤPP PHPHÁÁTT BBỘỘ NHNHỚỚ CHCHÍÍNHNH 3.3.2 Kỹ thuật phân vùng động . Cá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. Chọn thuật toán nào phụ thuộc vào thứ tự swap và kích thước của tiến trì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 nên, hạn chế được 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 nhớ trống để tìm khối nhớ có 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ỏ 6/28/2014 Chương 3. Quản lý bộ nhớ 34
  35. KKỸỸ THUTHUẬẬTT CCẤẤPP PHPHÁÁTT BBỘỘ NHNHỚỚ CHCHÍÍNHNH 3.3.2 Kỹ thuật phân vùng động . Trong công tác cấp phát bộ nhớ, HĐH có thể Swap out một tiến trình ra ngoài đĩa để dành chỗ cấp phát cho tiến trình có yêu cầu và sau đó swap in vào lại tại thời điểm thích hợp. Khi nạp lại thì có thể 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 khi một tiến trình được nạp vào bộ nhớ lần đầu tiên . Ví dụ chương trình có code truy xuất tại địa chỉ 100K, nếu được nạp vào phân vùng 1 có đị 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ách việc truy xuất đến vùng nhớ của tiến trình khác 6/28/2014 Chương 3. Quản lý bộ nhớ 35
  36. KKỸỸ THUTHUẬẬTT CCẤẤPP PHPHÁÁTT BBỘỘ NHNHỚỚ CHCHÍÍNHNH 3.3.2 Kỹ thuật phân vùng động . Sử 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ớ . Việ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 • Đị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ớ 6/28/2014 Chương 3. Quản lý bộ nhớ 36
  37. KKỸỸ THUTHUẬẬTT CCẤẤPP PHPHÁÁTT BBỘỘ NHNHỚỚ CHCHÍÍNHNH 3.3.2 Kỹ thuật phân vùng động Địa chỉ tương đối Điều khiển tiến trình Base Register Cộng Program < Limit Register So sánh Data Stack Gởi ngắt đến hệ điều hành Tiến trình trong bộ nhớ • Hạ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 6/28/2014 Chương 3. Quản lý bộ nhớ 37
  38. KKỸỸ THUTHUẬẬTT CCẤẤPP PHPHÁÁTT BBỘỘ NHNHỚỚ CHCHÍÍNHNH 3.3.3 Kỹ thuật phân trang đơn 6/28/2014 Chương 3. Quản lý bộ nhớ 38
  39. KKỸỸ THUTHUẬẬTT CCẤẤPP PHPHÁÁTT BBỘỘ NHNHỚỚ CHCHÍÍNHNH 3.3.4 Kỹ thuật phân đoạn đơn 6/28/2014 Chương 3. Quản lý bộ nhớ 39
  40. KKỸỸ THUTHUẬẬTT BBỘỘ NHNHỚỚ ẢẢOO 3.4.1 Bộ nhớ ảo . Kỹ 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ính . Kỹ thuật cấp phát bộ nhớ phân trang/phân đoạn có đặc điểm: • Địa chỉ tham chiếu trong một phạm vi tiến trình là địa chỉ logíc và được chuyển thành địa chỉ vật lý một cách tự động tại thời điểm chạy của tiến trình. 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 6/28/2014 Chương 3. Quản lý bộ nhớ 40
  41. KKỸỸ THUTHUẬẬTT BBỘỘ NHNHỚỚ ẢẢOO 3.4.1 Bộ nhớ ảo . Kỹ thuật này khắc phục được hạn chế của phân vùng cố định, phân vùng động nhưng cò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 . Khắc phục hạn chế này kỹ thuật bộ nhớ ảo ra đời nó vẫn dựa vào kỹ thuật phân trang/đoạn nhưng • Bộ 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 cần bộ nhớ ảo dựa vào bảng PCT, SCT để nạp trang tiếp theo • Nếu nạp mà không còn trang/đoạn trống thì bộ phận quản lý bộ nhớ đư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 6/28/2014 Chương 3. Quản lý bộ nhớ 41
  42. KKỸỸ THUTHUẬẬTT BBỘỘ NHNHỚỚ ẢẢOO 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 6/28/2014 Chương 3. Quản lý bộ nhớ 42
  43. KKỸỸ THUTHUẬẬTT BBỘỘ NHNHỚỚ ẢẢOO 3.4.1 Bộ nhớ ảo . Việc sử dụng bộ nhớ ảo có một số một số lợi ích sau: • Nạp được nhiều tiến trình vào bộ nhớ hơn vì bộ phận quản lý bộ nhớ không nạp tất cả vào bộ nhớ • Có thể nạp vào bộ nhớ một tiến trình có không gian lớn hơn bộ nhớ vật lý với thiết kế chương trình cấu trúc Overlay nhờ có sự hỗ trợ của HĐH và phần cứng. • Không cần nạp tất cả các tiến trình vào bộ nhớ mà chỉ nạp một phần hoặc chỉ nạp vào bộ nhớ các chỉ thị và dữ liệu của chương trình cần thiết cho việc thi hành lệnh ở tại thời điểm đó. • Người sử dụng làm việc với địa chỉ ảo còn việc chuyển đổi sang địa chỉ vật lý do HĐH đảm nhiệm bằng cơ chế phần cứng 6/28/2014 Chương 3. Quản lý bộ nhớ 43
  44. KKỸỸ THUTHUẬẬTT BBỘỘ NHNHỚỚ ẢẢOO 3.4.2 Cài đặt bộ nhớ ảo 6/28/2014 Chương 3. Quản lý bộ nhớ 44
  45. CCÁÁCC THUTHUẬẬTT TOTOÁÁNN THAYTHAY TRANGTRANG 3.5.1 Thuật toán FIFO 6/28/2014 Chương 3. Quản lý bộ nhớ 45
  46. CCÁÁCC THUTHUẬẬTT TOTOÁÁNN THAYTHAY TRANGTRANG 3.5.2 Thuật toán LRU 6/28/2014 Chương 3. Quản lý bộ nhớ 46
  47. CCÁÁCC THUTHUẬẬTT TOTOÁÁNN THAYTHAY TRANGTRANG 3.5.3 Thuật toán Optional 6/28/2014 Chương 3. Quản lý bộ nhớ 47
  48. CCẤẤPP PHPHÁÁTT KHUNGKHUNG TRANGTRANG 3.5.3 Thuật toán Optional 6/28/2014 Chương 3. Quản lý bộ nhớ 48
  49. TTỔỔNGNG KKẾẾTT Trong chương này, chúng ta đã học: 6/28/2014 Chương 3. Quản lý bộ nhớ 49
  50. CÂUCÂU HHỎỎII VVÀÀ BBÀÀII TTẬẬPP VVỀỀ NHNHÀÀ 6/28/2014 Chương 3. Quản lý bộ nhớ 50