1 HTMT 25/06/2020 QUẢN LY BỘ NHỚ 2 ❑ Quản lý bộ nhớ là một trong những nhiệm vụ quan trọng và phức tạp nhất của hệ điều hành. ❑ Bộ phận quản lý bộ nhớ xem bộ nhớ chính như là một tài nguyên của hệ thống dùng để cấp phát và chia sẻ cho nhiều tiến trình đang ở trong trạng thái active. ❑ Các hệ điều hành đều mong muốn có nhiều các tiến trình trên bộ nhớ chính. Công cụ cơ bản của quản lý bộ nhớ là sự phân trang (paging) và sự phân đoạn (segmentation) HTMT 25/06/2020 Nhiệm vụ của quản lý bộ nhớ 3 ❑ Trong các hệ thống đơn chương trình (uniprogramming), trên bộ nhớ chính ngoài hệ điều hành, chỉ có một chương trình đang thực hiện ❑ Trong các hệ thống đa chương (multiprogramming) trên bộ nhớ chính ngoài hệ điều hành, có thể có nhiều tiến trình đang hoạt động.
◼ Trong hệ thống đa chương bộ phận quản lý bộ nhớ phải có nhiệm vụ đưa bất kỳ một tiến trình nào đó vào bộ nhớ khi nó có yêu cầu, kể cả khi trên bộ nhớ không còn không gian trống. Nó phải bảo vệ chính hệ điều hành 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. HTMT 25/06/2020 Nhiệm vụ của quản lý bộ nhớ 4 Bộ phận quản lý bộ nhớ phải thực hiện các nhiệm vụ sau đây: • Sự tái định vị (Relocation): Trong các hệ thống đa chương, không gian bộ nhớ chính thường được chia sẻ cho nhiều tiến trình khác nhau và yêu cầu bộ nhớ của các tiến trình luôn lớn hơn không gian bộ nhớ vật lý mà hệ thống có được. • Bảo vệ bộ nhớ (Protection): Mỗi tiến trình phải được bảo vệ để chống lại sự truy xuất bất hợp lệ vô tình hay có chủ ý của các tiến trình khác.
HTMT 25/06/2020 Nhiệm vụ của quản lý bộ nhớ 5 • Chia sẻ bộ nhớ (Sharing): Bất kỳ một chiến lược nào được cài đặt đều phải có tính mềm dẻo để cho phép nhiều tiến trình có thể truy cập đến cùng một địa chỉ trên bộ nhớ chính. VD: khi có nhiều tiến trình cùng thực hiện một chương trình thì việc cho phép mỗi tiến trình cùng truy cập đế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. HTMT 25/06/2020 Nhiệm vụ của quản lý bộ nhớ 6 • Tổ chức bộ nhớ logic (Logical organization): Bộ nhớ chính của hệ thống máy tính được tổ chức như là một dòng hoặc một mảng, không gian địa chỉ bao gồm một dãy có thứ tự các byte hoặc các word. • Tổ chức bộ nhớ vật lý (Physical organization): Như chúng ta đã biết bộ nhớ máy tính được tổ chức theo 2 cấp: - Bộ nhớ chính cung cấp một tốc độ truy cập dữ liệu cao.
- Bộ nhớ phụ có tốc độ truy xuất chậm và rẻ tiền hơn so với bộ nhớ chính. HTMT 25/06/2020 Kỹ thuật cấp phát bộ nhớ (nạp chương trình vào bộ nhớ chính) 7 1. Kỹ thuật phân vùng cố định (Fixed Partitioning) 2. Kỹ thuật phân vùng động (Dynamic Partitioning) HTMT 25/06/2020 Kỹ thuật cấp phát bộ nhớ (nạp chương trình vào bộ nhớ chính) 8 1.
Kỹ thuật phân vùng cố định (Fixed Partitioning) Trong kỹ thuật này không gian địa chỉ của bộ nhớ chính đượ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ệ điều hành, phần còn lại, tạm gọi là phần user program, là sẵn sàng cho việc sử dụng của các tiến trình khi các tiến trình được nạp vào bộ nhớ chính HTMT 25/06/2020 Kỹ thuật cấp phát bộ nhớ (nạp chương trình vào bộ nhớ chính) 9 Có hai trở ngại trong việc sử dụng các phân vùng cố định với kích thước bằng nhau: - Thứ nhất: khi kích thước của một chương trình là quá lớn so với kích thước của một partition thì người lập trình phải thiết kế chương trình theo cấu trúc overlay, theo đó chỉ những phần chia cần thiết của chương trình mới được nạp vào bộ nhớ chính khi khởi tạo chương trình, sau đó người lập trình phải nạp tiếp các modun cần thiết khác 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 đó. Cấu trúc chương trình overlay tiết kiệm được bộ nhớ nhưng yêu cầu cao ở người lập trình HTMT 25/06/2020 Kỹ thuật cấp phát bộ nhớ (nạp chương trình vào bộ nhớ chính) 10 - Thứ hai: khi kích thước của một chương trình nhỏ hơn kích thước của một partition hoặc quá lớn so với kích thước của một partition nhưng không phải là bội số của kích thước một partition thì dễ xảy ra hiện tượng phân mảnh bên trong (internal fragmentation) bộ nhớ, gây lãng phí bộ nhớ. Ví dụ: nếu có 3 không gian trống kích thước 30K nằm rãi rác trên bộ nhớ, thì cũng sẽ không nạp được một modun chương trình có kích thước 12K, hiện tượng này được gọi là hiện tượng phân mảnh bên trong. → Cả hai vấn đề trên có thể được khắc phục bằng cách sử dụng các phân vùng có kích thước không bằng nhau.
HTMT 25/06/2020 Kỹ thuật cấp phát bộ nhớ (nạp chương trình vào bộ nhớ chính) 11 Với các partition có kích thước không bằng nhau thì có hai cách để lựa chọn khi đưa một tiến trình vào partition: 1. Mỗi phân vùng có một hàng đợi tương ứng, theo đó mỗi tiến trình khi cần được nạp vào bộ nhớ nó sẽ được đưa đến hành đợi của phân vùng có kích thước vừa đủ để chứa nó, để vào/để đợi được vào phân vùng 2. Hệ thống dùng một hàng đợi chung cho tất cả các phân vùng, theo đó tất cả 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 này HTMT 25/06/2020 Kỹ thuật cấp phát bộ nhớ (nạp chương trình vào bộ nhớ chính) 12 → Sự phân vùng cố định ít được sử dụng trong các hệ điều hành hiện nay. HTMT 25/06/2020 Kỹ thuật cấp phát bộ nhớ (nạp chương trình vào bộ nhớ chính) 13 2.
Kỹ thuật phân vùng động (Dynamic Partitioning) Để khắc phục một vài hạn chế của kỹ thuật phân vùng cố định, kỹ thuật phân vùng động ra đời. - Trong 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 là có thể thay đổi. - Khi có một tiến trình được nạp vào bộ nhớ nó được hệ điều hành cấp cho nó 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. HTMT 25/06/2020 Kỹ thuật cấp phát bộ nhớ (nạp chương trình vào bộ nhớ chính) 14 - Khi một tiến trình kết thúc nó được đưa ra ngoài và phần không gian bộ nhớ mà tiến trình này trả lại cho hệ điều hành sẽ được hệ điều hành cấp cho tiến trình khác HTMT 25/06/2020 Kỹ thuật cấp phát bộ nhớ (nạp chương trình vào bộ nhớ chính) 15 trên đây minh họa cho quá trình nạp/kết thúc các tiến trình theo thứ tự: nạp process1, nạp process2, nạp process3, kết thúc process2, nạp process4, kết thúc process1, nạp process2 vào lại, trong hệ thống phân vùng động HTMT 25/06/2020 Kỹ thuật cấp phát bộ nhớ (nạp chương trình vào bộ nhớ chính) 16 Hệ điều hành sử dụng 2 cơ chế: Bản đồ bít và Danh sách liên kết.
Trong cả 2 cơ chế này hệ điều hành đều chia không gian nhớ thành các đơn vị cấp phát có kích thước bằng nhau, các đơn vị cấp phát liên tiếp nhau tạo thành một khối nhớ (block), hệ điều hành cấp phát các block này cho các tiến trình khi nạp tiến trình vào bộ nhớ. A B C D 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 Một đoạn nhớ bao gồm 22 đơn vị cấp phát, tạo thành 9 block, trong đó có 4 block đã cấp phát (tô đậm, kí hiệu là P) cho các tiến trình: A, B, C, D và 5 block chưa được cấp phát (để trắng, kí hiệu là H) HTMT 25/06/2020 Kỹ thuật cấp phát bộ nhớ (nạp chương trình vào bộ nhớ chính) 17 - Trong cơ chế bản đồ bít: mỗi đơn vị cấp phát được đại diện bởi một bít trong bản đồ bít. Đơn vị cấp phát còn trống được đại diện bằng bít 0, ngược lại đơn vị cấp phát được đại diện bằng bít 1 quản lý các đơn vị cấp phát bằng bản đồ bít. HTMT 25/06/2020 Kỹ thuật cấp phát bộ nhớ (nạp chương trình vào bộ nhớ chính) 18 Trong cơ chế danh sách liên kết: Mỗi block trên bộ nhớ được đại diện bởi một phần tử trong danh sách liên kết, mỗi phần tử này gồm có 3 trường chính: trường thứ nhất cho biết khối nhớ đã cấp phát (P: process) hay đang còn trống (H: Hole), trường thứ hai cho biết thứ tự của đơn vị cấp phát đầu tiên trong block, trường thứ ba cho biết block gồm bao nhiêu đơn vị cấp phát → Như vậy khi cần nạp một tiến trình vào bộ nhớ thì hệ điều hành phải dựa vào bản đồ bit hoặc danh sách liên kết để tìm ra một block có kích thước đủ để nạp tiến trình.
HTMT 25/06/2020 Kỹ thuật phân trang đơn (Simple Paging) 19 Trong kỹ thuật này không gian địa chỉ bộ nhớ vật lý được chia thành các phần có kích thước cố định bằng nhau, được đánh số địa chỉ bắt đầu từ 0 và được gọi là các khung trang (page frame). Không gian địa chỉ của các tiến trình cũng được chia thành các phần có kích thước bằng nhau và bằng kích thước của một khung trang, được gọi là các trang (page) của tiến trình HTMT 25/06/2020 Kỹ thuật phân trang đơn (Simple Paging) 20 Các trang của 2 tiến trình process 1 và process 2 (a), được nạp vào bộ nhớ (b), và 2 bảng trang tương ứng của nó (c). HTMT 25/06/2020 Kỹ thuật phân trang đơn (Simple Paging) 21 ❑ Kích thước của mỗi trang hay khung trang do phần cứng quy định và thường là lũy thừa của 2, biến đổi từ 512 byte đến 8192 byte. Nếu kích thước của không gian địa chỉ là 2m và kích thước của trang là 2n thì m-n bít của địa chỉ logic là số hiệu trang (page) và n bít còn lại là địa chỉ tương đối trong trang (offset).
HTMT 25/06/2020 Kỹ thuật phân trang đơn (Simple Paging) 22 Ví dụ: nếu địa chỉ logic gồm 16 bit, kích thước của mỗi trang là 1K = 1024byte (210), thì có 6 bít dành cho số hiệu trang, như vậy một chương trình có thể có tối đa 26 = 64 trang mỗi trang 1KB. Trong trường hợp này nếu CPU phát ra một giá trị địa chỉ 16 bít là: 0000010111011110 = 1502, thì thành phần số hiệu trang là 000001 = 1, thành phần offset là 0111011110 = 478.