Nội dung

CHƯƠNG 3 :QUẢN LÝ BỘ NHỚ Bộ nhớ chính là thiết bị lưu trữ duy nhất thông qua đó CPU có thể trao đổi thông tin với môi trường ngoài, do vậy nhu cầu tổ chức, quản lý bộ nhớ là một trong những nhiệm vụ trọng tâm hàng đầu của hệ điều hành . Bộ nhớ chính được tổ chức như một mảng một chiều các từ nhớ (word), mỗi từ nhớ có một địa chỉ . Việc trao đổi thông tin với môi trường ngoài được thực hiện thông qua các thao tác đọc hoặc ghi dữ liệu vào một địa chỉ cụ thể nào đó trong bộ nhớ. Hầu hết các hệ điều hành hiện đại đều cho phép chế độ đa nhiệm nhằm nâng cao hiệu suất sử dụng CPU. Tuy nhiên kỹ thuật này lại làm nảy sinh nhu cầu chia sẻ bộ nhớ giữa các tiến trình khác nhau . Vấn đề nằm ở chỗ : « bộ nhớ thì hữu hạn và các yêu cầu bộ nhớ thì vô hạn ». 3.1 Tổ chức vùng nhớ Tốc độ nhanh Dung lượng nhỏ Register Cache1 SRAM Cache2 Main memory Tốc độ chậm DRAM Disk Dung lượng lớn Hình 3.1 3.2 Mục tiêu của việc quản lý vùng nhớ Cấp phát vùng nhớ cho các tiến trình có yêu cầu và thu hồi vùng nhớ khi tiến trình thực hiện xong. Quản lý được vùng nhớ rỗi, vùng nhớ bận. - Tại một thời điểm có thể lưu giữ được nhiều tiến trình đồng thời. - Chuyển đổi giữa địa chỉ logic và địa chỉ vật lý (physic) 75 - Chia sẻ thông tin: làm thế nào để cho phép hai tiến trình có thể chia sẻ thông tin trong bộ nhớ? - Ngăn chặn các tiến trình xâm phạm đến vùng nhớ được cấp phát cho tiến trình khác 3.3 Không gian địa chỉ và không gian vật lý Một trong những hướng tiếp cận trung tâm nhằm tổ chức quản lý bộ nhớ một cách hiệu qủa là đưa ra khái niệm không gian địa chỉ được xây dựng trên không gian nhớ vật lý, việc tách rời hai không gian này giúp hệ điều hành dễ dàng xây dựng các cơ chế và chiến lược quản lý bộ nhớ hữu hiệu : Địa chỉ logic – còn gọi là địa chỉ ảo , là địa chỉ do bộ xử lý tạo ra. Địa chỉ vật lý - là địa chỉ thực tế mà trình quản lý bộ nhớ nhìn thấy và thao tác. Không gian địa chỉ – là tập hợp tất cả các địa chỉ ảo phát sinh bởi một chương trình. Không gian vật lý – là tập hợp tất cả các địa chỉ vật lý tương ứng với các địa chỉ ảo. Địa chỉ ảo và địa chỉ vật lý là như nhau trong phương thức kết buộc địa chỉ vào thời điểm biên dịch cũng như vào thời điểm nạp. Nhưng có sự khác biệt giữa địa chỉ ảo và địa chỉ vật lý trong phương thức kết buộc vào thời điểm xử lý. MMU (memory-management unit) là một cơ chế phần cứng được sử dụng để thực hiện chuyển đổi địa chỉ ảo thành địa chỉ vật lý vào thời điểm xử lý. Chương trình của người sử dụng chỉ thao tác trên các địa chỉ ảo, không bao giờ nhìn thấy các địa chỉ vật lý . Địa chỉ thật sự ứng với vị trí của dữ liệu trong bô nhớ chỉ được xác định khi thực hiện truy xuất đến dữ liệu. 3.4. Cấp phát liên tục Tiến trình được nạp vào một vùng nhớ liên tục đủ lớn để chứa toàn bộ tiến trình. Không cho phép chương trình khác sử dụng vùng nhớ dành cho chương trình 3.4.1 Hệ đơn chương 76 Trong phương pháp này bộ nhớ được chia sẻ cho hệ điều hành và một tiến trình duy nhất của người sử dụng. Tại một thời điểm, một phần của bộ nhớ sẽ do hệ điều hành chiếm giữ, phần còn lại thuộc về tiến trình người dùng duy nhất trong hệ thống. Tiến trình này được toàn quyền sử dụng bộ nhớ dành cho nó. Hình 3.2 Tổ chức bộ nhớ trong hệ thống đơn chương Để bảo vệ hệ điều hành khỏi sự xâm phạm tác động của chương trình người dung, sử dụng một thanh ghi giới hạn lưu địa chỉ cao nhất của vùng nhớ được cấp cho hệ điều hành. Tất cả các địa chỉ được tiến trình người dung truy xuất sẽ được so sánh với nội dung thanh ghi giới hạn, nếu địa chỉ này lớn hơn giới hạn cho phép thì là hợp lệ, ngược lại một ngắt sẽ được phát sinh để báo cho hệ thống về một truy xuất bất hợp lệ. Khi bộ nhớ được tổ chức theo cách thức này, chỉ có thể xử lý một tiến trình tại một thời điểm. Quan sát hoạt động của các tiến trình, có thể nhận thấy rất nhiều tiến trình trải qua phần lớn thời gian để chờ các thao tác nhập/xuất hoàn thành. Trong suốt thời gian này, CPU ở trạng thái rỗi. Trong trường hợp như thế, hệ thống đơn chương không cho phép sử dụng hiệu quả CPU. Ngoài ra, sự đơn chương không cho phép nhiều người sử dụng làm việc đồng thời theo cơ chế tương tác. Để nâng cao hiệu suất sử dụng CPU, cần cho phép chế độ đa chương mà trong đó các tiến trình chia sẻ CPU với nhau để hoạt động đồng hành. 3.4.2 Hệ thống đa chương với phân vùng cố định Một trong những phương pháp đơn giản nhất để cấp phát bộ nhớ là chia bộ nhớ thành những phân vùng có kích thước cố định. Các phân vùng khác nhau có thể có kích thước khác nhau hay bằng nhau. Mỗi phân vùng chỉ có thể chứa một tiến trình. Do đó, cấp độ đa chương được giới hạn bởi số lượng phân vùng. Trong phương pháp đa phân vùng, khi một phân vùng rảnh, một tiến trình được chọn từ hàng đợi nhập và 77 được nạp vào phân vùng trống. Khi tiến trình kết thúc, phân vùng trở nên sẳn dùng cho một tiến trình khác. Có hai tiếp cận để tổ chức hàng đợi: • Sử dụng nhiều hàng đợi: mỗi phân vùng sẽ có một hàng đợi tương ứng. Khi một tiến trình mới được tạo lập sẽ được đưa vào hàng đợi của phân vùng có kích thước nhỏ nhất đủ lớn để chứa tiến trình. Cách tổ chức này có khuyết điểm trong trường hợp các hàng đợi của một số phân vùng lớn thì trống trong khi các hàng đợi của các phân vùng nhỏ lại đầy, buộc các tiến trình trong những hàng đợi này phải chờ được cấp phát bộ nhớ, do vậy sử dụng không hiệu quả bộ nhớ. • Sử dụng một hàng đợi: tất cả các tiến trình được đặt trong hàng đợi duy nhất. Khi có một phân vùng trống, tiến trình đầu tiên trong hàng đợi có kích thước phù hợp sẽ được đặt vào phân vùng và cho xử lý. Hình 3.3 Cấp phát đa vùng với phân vùng cố định Trong trường hợp tiến trình đầu tiên có kích thước nhỏ trong khi phân vùng tự do là lớn sẽ dẫn tới lãng phí bộ nhớ. Giải pháp: Khi có một phân vùng rỗi thì tìm trên toàn bộ hàng đợi này tiến trình lớn nhất đặt vừa rong phân vùng này, nạp tiến trình vào bộ nhớ chính. 78 Xuất hiện hiện tượng phân mảnh nội vi (internal fragmentation): do kích thước tiến trình được nạp nhỏ hơn kích thước của phân vùng chứa tiến trình, phần bộ nhớ không được sử dụng đến trong phân vùng này gọi là phân mảnh nội vi. Nhận xét: -Mức độ đa chương của hệ thống bị giới hạn bởi số lượng phân vùng. - Sử dụng bộ nhớ không hiệu quả: Tổng bộ nhớ nhỏ tự do, rời rạc còn lớn nhưng không thể sử dụng để nạp tiến trình khác. Tiến trình có kích thước lớn hơn phân vùng lớn nhất sẽ không bao giờ được thực hiện. - Ưu điểm: đơn giản, dễ tổ chức bảo vệ, giảm thời gian tìm kiếm. 3.4.3 Hệ thống đa chương với phân vùng động Hệ điều hành giữ một bảng hiển thị những phần nào của bộ nhớ là rỗi và phần nào đang bận. Ban đầu, tất cả bộ nhớ là sẵn dùng cho tiến trình người dùng, và được xem như một khối lớn bộ nhớ sẵn dùng. Khi một tiến trình đến và cần bộ nhớ, hệ điều hành tìm kiếm một vùng trống đủ lớn cho tiến trình này. Nếu tìm thấy, hệ điều hành sẽ cấp phát cho tiến trình phần bộ nhớvừa đúng với kích thước của tiến trình, phần bộ nhớ còn lại dành cho các tiến trình khác. Hình 3.4 Cấp phát đa vùng với phân vùng động 79 Thông thường, một tập hợp các vùng trống có kích thước khác nhau được phân tán khắp bộ nhớ tại bất cứ thời điểm được cho. Khi một tiến trình đến và yêu cầu bộ nhớ, hệ thống tìm tập hợp này một vùng trống đủ lớn cho tiến trình này. Nếu vùng trống quá lớn, nó được chia làm hai: một phần được cấp cho tiến trình đến; phần còn lại được trả về tập hợp các vùng trống. Nếu vùng trống mới nằm kề với các vùng trống khác, các vùng trống nằm kề này được gom lại để tạo thành một vùng trống lớn hơn. Xuất hiện hiện tượng phân mảnh ngoại vi( external fragmentation ) : khi các tiến trình lần lượt vào và ra khỏi hệ thống, dần dần xuất hiện các khe hở giữa các tiến trình. Đây là các khe hở được tạo ra do kích thước của tiến trình mới được nạp nhỏ hơn kích thước vùng nhớ mới được giải phóng bởi một tiến trình đã kết thúc và ra khỏi hệ thống. , không gian bộ nhớ trống bị phân rã thành những mảnh nhớ nhỏ. Hiện tượng này có thể dẫn đến tình huống tổng vùng nhớ trống đủ để thoả mãn yêu cầu, nhưng các vùng nhớ này lại không liên tục ! Người ta có thể áp dụng kỹ thuật « dồn bộ nhớ » (memory compaction ) để kết hợp các mảnh bộ nhớ nhỏ rời rạc thành một vùng nhớ lớn liên tục. Tuy nhiên, kỹ thuật này đòi hỏi nhiều thời gian xử lý, ngoài ra, sự kết buộc địa chỉ phải thực hiện vào thời điểm xử lý, vì các tiến trình có thể bị di chuyển trong quá trình dồn bộ nhớ. Thuật toán đơn giản là dịch chuyển các tiến trình về phía đầu của bộ nhớ. Ví dụ: 0 300K HDH 0 300K HDH 0 300K HDH 0 300K HDH 500K P1 500K P1 500K P1 500K P1 600K P2 600K P2 600K P2 600K P2 1000K 1200K 1500K 800K P3 P3 P3 P4 1200K P4 P4 Cấp phát gốc 1000K 1200K P4 1900K 2100K P4 P3 2100K P3 P3 P4 P3 1500K 1900K 1900K 2100K 2100K Dịch chuyển 600K Dịch chuyển 400K P4 P4 P3 Dịch chuyển 200K Hình 3.5 Vấn đề cấp phát động 80 Lựa chọn vùng nhớ tự do trong danh sách các vùng nhớ tự do để cấp phát cho tiến trình. Có 3 chiến lược phổ biến nhất được dùng: • First-fit: cấp phát vùng nhớ tự do đầu tiên đủ lớn. Tìm kiếm có thể bắt đầu tại đầu từ danh sách tập hợp các vùng trống hay tại điểm kết thúc của tìm kiếm first-fit trước đó. Chúng ta dừng tìm kiếm ngay khi chúng ta tìm thấy một vùng trống đủ lớn. • Best-fit: cấp phát vùng nhớ tự do nhỏ nhất đủ lớn. Chúng ta phải tìm toàn bộ danh sách, trừ khi danh sách được xếp thứ tự theo kích thước. Worst-fit: cấp phát vùng nhớ tự do lớn nhất đủ lớn để chứa tiến trình. Chúng ta phải tìm toàn bộ danh sách trừ khi nó được xếp theo thứ tự kích thước. Quản lý các khối rỗi bận - Quản lý bằng bản đồ bit: Bộ nhớ được chia thành các đơn vị cấp phát, mỗi đơn vị được ánh xạ tới một bit trong bản đồ bit. Giá trị bit này xác định trạng thái của đơn vị bộ nhớ đó: 0 đang tự do, 1 đã được cấp phát. Khi cần nạp một tiến trình có kích thước k đơn vị, hệ thống sẽ tìm trong bản đồ bit một dãy k bit có giá trị 0. Kích thước của đơn vị cấp phát là vấn đề lớn trong thiết kế. Nếu kích thước đơn vị cấp phát nhỏ sẽ làm tăng kích thước của bản đồ bit. Ngược lại, nếu kích thước đơn vị cấp phát lớn có thể gây hao phí cho đơn vị cấp phát sau cùng. Đây là giải pháp đơn giản nhưng thực hiện chậm nên ít được dùng. Hình 3.6 Quản lý bộ nhớ bằng bản đồ bit 81 - Quản lý bằng danh sách liên kết: Dùng một danh sách liên kết để quản lý các phân đoạn bộ nhớ đã cấp phát và phân đoạn tự do.Danh sách liên kết gồm nhiều nút liên tiếp. Mỗi nút gồm 1 bit đầu để xác định phân đoạn đó là vùng trống (H) hay một tiến trình (P), sau đó là 3 từ để chỉ địa chỉ bắt đầu, chiều dài và chỉ điểm tới mục kế tiếp. Việc sắp xếp các phân đoạn theo địa chỉ hay theo kích thước tuỳ thuộc vào giải thuật quản lý bộ nhớ. Hình 3.7 Quản lý bộ nhớ bằng danh sách liên kết 3.5. Cấp phát không liên tục Cấp phát không liên tục là một chương trình có thể được phân chia thành mộ số đoạn, các đoạn này nằm ở các vùng nhớ rời rạc nhau, giữa các vùng nhớ này có thể có các vùng nhớ được phân phối cho chương trình khác. 3.5.1 Phân trang ( Paging) Ý tưởng: Hình 3.8 Mô hình bộ nhớ phân trang 82 Phân bộ nhớ vật lý thành các khối (block) có kích thước cố định và bằng nhau, gọi là khung trang (page frame). Không gian địa chỉ cũng được chia thành các khối có cùng kích thước với khung trang, và được gọi là trang (page). Khi cần nạp một tiến trình để xử lý, các trang của tiến trìnhsẽ được nạp vào những khung trang còn trống. Một tiến trình kích thước N trang sẽ yêu cầu N khung trang tự do. Cơ chế MMU trong kỹ thuật phân trang: Hình 3.9 Cơ chế phần cứng hỗ trợ phân trang Cơ chế phần cứng hỗ trợ thực hiện chuyển đổi địa chỉ trong cơ chế phân trang là bảng trang (pages table): Mỗi tiến trình có một bảng trang. Số phần tử của bảng trang=số trang trong không gian địa chỉ của tiến trình. Mỗi phần tử trong bảng trang mô tả một trang cho biết địa chỉ bắt đầu của vị trí lưu trữ trang tương ứng trong bộ nhớ vật lý ( số hiệu khung trang trong bộ nhớ vật lý đang chứa trang ). 83 Hình 3.10 Chuyển đổi địa chỉ: Địa chỉ logic Địa chỉ vật lý số hiệu trang (p): sử dụng như chỉ mục đến phần tử tương ứng trong bảng trang. địa chỉ tương đối trong trang (d): kết hợp với địa chỉ bắt đầu của trang để tạo ra địa chỉ vật lý mà trình quản lý bộ nhớ sử dụng. Số hiệu khung trang (f):địa chỉ bắt đầu của khung trang trong bộ nhớ vật lý. Kích thước của trang do phần cứng qui định. Để dễ phân tích địa chỉ ảo thành số hiệu trang và địa chỉ tương đối, kích thước của một trang thông thường là một lũy thừa của 2 (biến đổi trong phạm vi 512 bytes và 8192 bytes). Nếu kích thước của không gian địa chỉ là 2m và kích thước trang là 2 n, thì m-n bits cao của địa chỉ ảo sẽ biễu diễn số hiệu trang, và n bits thấp cho biết địa chỉ tương đối trong trang. Cài đặt bảng trang: - Với các bảng trang có kích thước nhỏ, trong trường hợp đơn giản nhất, bảng trang được cài đặt trongmột tập các thanh ghi 84