Bài giảng Hệ điều hành - Huỳnh Triệu Vỹ - Chương 2: Quản lý bộ nhớ

phân vùng nào đó có kích thước vừa đủ, không chứa tiến trình đang ở trạng thái ready hoặc running và không có quan hệ với tiến trình đang ở trạng thái running khác để nạp tiến trình vừa có yêu cầu 2.1 Kỹ thuật phân vùng cố định(tt) Phân vùng kích thước bằng nhau Phân vùng kích thước không bằng nhau Hình 3.1 Ví dụ về phân vùng cố định của bộ nhớ 64MByte 2.1 Kỹ thuật phân vùng cố định(tt) Có 2 khó khăn với việc dùng phân vùng cố định có kích thước bằng nhau Thứ 1: Nếu chương trình có kích thước quá lớn so với 1 kích thước của phân vùng, để giải quyết việc này thì: Người lập trình phải thiết kế chương trình theo cấu trúc overlay Chỉ 1 phần cần thiết của chương trình mới được nạp vào bộ nhớ lúc nạp chương trình. Khi cần mudun nào đó mà không sẵn có trong bộ nhớ người sử dụng phải nạp nó vào đúng phân vùng của chương trình và sẽ ghi đè lên bất kỳ chương trình hoặc dữ liệu ở trong đó 2.1 Kỹ thuật phân vùng cố định(tt) Thứ 2: Khi kích thước của chương trình nhỏ hơn kích thước của 1 phân vùng hoặc lớn hơn kích thước của phân vùng nhưng không phải là bội số của kích thước phân vùng. Điều này gây ra sự phân mảnh nội vi, lãng phí bộ nhớ 2.1 Kỹ thuật phân vùng cố định(tt) Để khắc phục nhược điểm này có thể sử dụng phân vùng cố định có kích thước không bằng nhau Có 2 lựa chọn để đưa tiến trình vào dạng phân vùng này 2.1 Kỹ thuật phân vùng cố định(tt) Lựa chọn 1: Mỗi phân vùng có một hàng đợi tương ứng Khi 1 tiến trình cần được nạp vào bộ nhớ sẽ đưa vào hàng đợi của phân vùng có kích thước vừa đủ để chứa nó để được đưa vào phân vùng Nhược điểm: Có thể có phân vùng đang trống nhưng lại có nhiều tiến trình đang chờ để vào phân vùng khác Tiến trình mới 2.1 Kỹ thuật phân vùng cố định(tt) Lựa chọn 2: Dùng 1 hàng đời chung cho tất cả các phân vùng Khi có tiến trình muốn nạp vào bộ nhớ nhưng chưa được nạp sẽ được đưa vào hàng đợi Khi có phân vùng trống, HĐH sẽ chọn tiến trình có kích thước vừa đủ để đưa vào phân vùng Phương pháp này gây khó khăn trong việc lựa chọn tiến trình để nạp vào phân vùng Tiến trình mới 2.2 Kỹ thuật phân vùng động Vùng nhớ user program không được phân chia trước Khi có tiến trình nạp vào bộ nhớ, HĐH cấp cho nó không gian nhớ đúng kích thước của nó Khi tiến trình kết thúc, vùng nhớ của nó sẽ được thu hồi để HĐH cấp cho tiến trình khác, kể cả tiến trình mới có kích thước nhỏ hơn vùng nhớ của tiến trình đã giải phóng 2.2 Kỹ thuật phân vùng động(tt) OS- 128k Process1 64k Process2 128k Process3 32k Process4 128k Process5 120k Process6 65k Tiến trình 1,2,3,4 lần lượt được nạp vào bộ nhớ Tiến trình 2 kết thúc, vùng nhớ được giải phóng Tiến trình 5 được nạp vào vùng nhớ của tiến trình 2 vừa giải phóng 4. Tiến trình 6 yêu cầu được nạp vào bộ nhớ nhưng không thể vì không có vùng nhớ trống phù hợp để nạp trong khi tổng dung lượng nhớ còn trống lớn hơn kích thước mà tiến trình yêu cầu 2.2 Kỹ thuật phân vùng động(tt) Cơ chế quản lý phân vùng trống Trong kỹ thuật phân vùng động, HĐH phải đưa ra các cơ chế thích hợp để quản lý các khối nhớ đã cấp phát hay còn trống trên bộ nhớ. HĐH sử dụng cơ chế Bản đồ bít và Danh sách liên kết. Cả hai cơ chế HĐH đề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 1 khối nhớ, HĐH cấp phát các khối nhớ này cho các tiến trình 2.2 Kỹ thuật phân vùng động(tt) Cơ chế bản đồ Bit: Mỗi đơn vị cấp phát được đại diện bởi một Bit trong bản đồ bit. Đơn vị cấp phát còn trống đại diện bằng bit 0, ngược lại đại diện bằng bit 1 Bản đồ bit 2.2 Kỹ thuật phân vùng động(tt) Cơ chế danh sách liên kết: Mỗi khối 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ử gồm 3 trường chính: Trường đầu tiên: cho biết khối nhớ đã cấp phát (kí hiệu P) hay còn trống (kí hiệu H) Trường thứ 2: cho biết thư tự của đơn vị cấp phát đầu tiên trong khối Trường thứ 3: cho biết tổng số đơn vị cấp phát trong khối 2.2 Kỹ thuật phân vùng động(tt) 2.2 Kỹ thuật phân vùng động(tt) Qui tắc chọn phân vùng trống Khi có một tiến trình cần được nạp vào bộ nhớ, HĐH phải quyết định chọn một khối nhớ phù hợp để nạp tiến trình 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. Có 3 thuật toán mà HĐH sử dụng trong trường hợp này: Best-fit, First-fit, và Next-fit 2.2 Kỹ thuật phân vùng động(tt) Best-fit: 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: HĐH sẽ bắt đầu quét qua các khối nhớ trống bắt đầu từ khối nhớ trống đầu tiên 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: tương tự như First-fit nhưng ở đây 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 2.3 Kỹ thuật phân trang đơn Bộ nhớ chính được chia thành các phần bằng nhau và cố định, được đánh số bắt đầu từ 0 và được gọi là các khung trang 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 kích thước của một khung trang được gọi là các trang Khi tiến trình nạp vào bộ nhớ thì các trang được nạp vào các khung trang bất kỳ còn trống có thể không liên tiếp nhau 2.3 Kỹ thuật phân trang đơn(tt) HĐH sử dụng các bảng trang(PCT) để theo dõi vị trí các trang của tiến trình trên bộ nhớ. Mỗi tiến trình có bảng trang riêng 2.3 Kỹ thuật phân trang đơn(tt) Sự phân mảnh trong cơ chế này? Sự phân mảnh sẽ xảy ra trong kỹ thuật này khi: Kích thước của tiến trình nhỏ hơn kích thước của 1 khung trang Kích thước của tiến trình lớn hơn kích thước khung trang nhưng không phải là bội số của 1 khung trang 2.4 Kỹ thuật phân đoạn đơn Bộ nhớ chính được chia thành các phần cố định có kích thước không bằng nhau, được đánh số bắt đầu từ 0 được gọi là các phân đoạn Mỗi phân đoạn bao gồm số hiệu phân đoạn và kích thước của nó Không gian địa chỉ của các tiến trình kể cả các dữ liệu liên quan cũng được chia thành các đoạn có kích thước không nhất thiết phải bằng nhau 2.4 Kỹ thuật phân đoạn đơn(tt) Khi tiến trình được nạp vào bộ nhớ, các đoạn được nạp vào các phân đoạn còn trống trên bộ nhớ, các phân đoạn này có thể không liên tục nhau Để theo dõi các đoạn của các tiến trình khác nhau trên bộ nhớ HĐH sử dụng các bảng phân đoạn (SCT), thông thường mỗi tiến trình có 1 bảng phân đoạn riêng 2.4 Kỹ thuật phân đoạn đơn(tt) Mỗi phần tử trong bảng phân đoạn tối thiểu gồm 2 trường Trường thứ nhất: cho biết địa chỉ cơ sở của phân đoạn mà đoạn chương trình tương ứng được nạp Trường thứ 2: cho biết độ dài của phân đoạn 2.4 Kỹ thuật phân đoạn đơn(tt) Code 100k Data 64k Stack 150 base limit 64 0 64 164 228 356 478 100 164 64 356 150 3. KỸ THUẬT BỘ NHỚ ẢO 3.1 Khái niệm nhớ ảo Để thực thi chương trình có kích thước lớn hơn bộ nhớ vật lý cấp phát cho nó cần xây dựng chương trình theo cấu trúc Overlay gây khó khăn cho người lập trình Để khắc phục khó khăn cho người lập trình, ý tưởng sử dụng bộ nhớ ảo ra đời Kỹ thuật bộ nhớ ảo cho phép xử lý một tiến trình không được nạp toàn bộ vào bộ nhớ vật lý 3.1 Khái niệm nhớ ảo(tt) Bộ nhớ ảo mô hình hoá bộ nhớ như một bảng lưu trữ rất lớn và đồng nhất, tách biệt hẳn khái niệm không gian địa chỉ và không gian vật lý Người sử dụng chỉ nhìn thấy và làm việc trong không gian địa chỉ ảo, chuyển đổi sang không gian vật lý do hệ điều hành thực hiện với sự trợ giúp của các cơ chế phần cứng 3.2 Cài đặt bộ nhớ ảo Có thể cài đặt bộ nhớ ảo theo 2 kỹ thuật Phân trang theo yêu cầu: Sử dụng kỹ thuật phân trang kết hợp với kỹ thuật swap Phân đoạn theo yêu cầu: sử dụng kỹ thuật phân đoạn kết hợp với kỹ thuật swap 3.2.1 Phân trang theo yêu cầu Sử dụng kỹ thuật phân trang kết hợp với kỹ thuật swap Một chương trình được xem như 1 tập hợp các trang thường trú trên bộ nhớ ngoài Khi thực thi hệ thống không nạp toàn bộ chương trình vào bộ nhớ trong mà chỉ nạp những trang cần thiết trong thời điểm hiện tại Một trang chỉ được nạp vào bộ nhớ trong khi cần thiết 3.2.1 Phân trang theo yêu cầu(tt) Cần có cơ chế phần cứng để phân biệt các trang đang ở bộ nhớ trong và các trang đang ở bộ nhớ ngoài Tổ chức bảng trang như kỹ thuật phân trang đơn nhưng 1 phần tử trong bảng trang chứa nhiều thông tin phức tạp hơn Cần có 1 bit cho biết trang tương ứng của tiến trình có hay không trong bộ nhớ chinh và 1 bit cho biết trang có bị sửa đổi hay không so với lần nạp gần nhất Hiện tượng lỗi trang Khi hệ thống truy xuất tới 1 trang được đánh dấu là bất hợp lệ sẽ làm phát sinh lỗi trang, HĐH xử lý lỗi trang như sau: Bước 1: Kiểm tra truy xuất đến bộ nhớ là hợp lệ hay bất hợp lệ 	- Nếu truy xuất bất hợp lệ : kết thúc tiến trình 	- Ngược lại : đến bước 2 Bước 2: Tìm vị trí chứa trang muốn truy xuất trên đĩa. Bước 3: Tìm một khung trang trống trong bộ nhớ chính 	- Nếu tìm thấy: đến bước 4 	- Ngược lại, thực hiện cơ chế swap out 1 trang thích 	hợp trên bộ nhớ chính sau đó cập nhật bảng trang 	tương ứng rồi đến bước 4 Hiện tượng lỗi trang(tt) Bước 4: - Chuyển trang muốn truy xuất từ bộ nhớ phụ vào bộ nhớ chính tại khung trang đã xác định được - Cập nhật nội dung bảng trang tương ứng. - Tái kích hoạt tiến trình người sử dụng Thay thế trang Khi các khung đã đầy mà cần nạp thêm trang thì phải thay thế một trang đang có trên khung Nếu trang bị thay thế có thay đổi nội dung thì cần phải đưa ra đĩa Có các phương pháp chọn phần tử thay thế: Optimal: Thay thế trang sẽ lâu được sử dụng nhất trong tương lai FIFO: trang ở trong bộ nhớ lâu nhất sẽ được chọn thay thế LRU (Least Recently Used ): trang được chọn để thay thế sẽ là trang lâu nhất chưa được truy xuất 3.2.2 Phân đoạn đoạn theo yêu cầu Bộ nhớ ảo bao gồm các đoạn (segment) có kích thuớc không cố định Khi nạp đoạn vào bộ nhớ thì hệ điều hành tìm khoảng trống đủ để nạp đoạn Có bảng đoạn quản lý các đoạn 3.2.3 Phân đoạn kết hợp phân trang Kết hợp các ưu điểm của phân đoạn và phân trang Bộ nhớ ảo bao gồm các đoạn Trong mỗi đoạn thực hiện phân trang Tài liệu tham khảo Trần Hạnh Nhi, Giáo trình HĐH nâng cao, ĐH Khoa học Tự nhiên Tp.HCM, 1998 Nguyễn Gia Định-Nguyễn Kim Tuấn, Nguyên Lý HĐH, NXB Khoa học kỹ thuật, 2005 William Stallting, Operating Systems, Prentice Hall, 1995