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

0,468  phaân maûnh noäi ôû frame 9 
(chöùa page 5), caùc ñòa chæ aûo > 12287 laø caùc ñòa chæ invalid.
 kieåm tra truy xuaát ñeán baûng phaân trang coù naèm trong baûng hay 
khoâng.
00000
10468
12287
2 v
3 v
4 v
7 v
8 v
9 v
0 i
0 i
frame
number
valid/
invalid bit
0
1
2
3
4
5
6
7
0
1
2 page 0
3 page 1
4 page 2
5
6
7 page 3
8 page 4
9 page 5
...
page n
16383
14 bit
Chia sẻ bộ nhớ trong cơ chế phân trang
52
Cho phép chia sẻ các trang giữa các tiến trình ánh
xạ nhiều địa chỉ logic vào một địa chỉ vật lý duy nhất.
HĐH kiểm tra các thao tác truy xuất trên khung trang
tương ứng có hợp lệ với thuộc tính bảo vệ của nó
không.
53
 Loại bỏ được hiện tượng phân mảnh ngoại vi nhưng vẫn
còn hiện tượng nội vi Nếu kích thước của tiến trình không
phải là bội số của kích thước 1 khung trang.
Có sự phân biệt rạch ròi giữa góc nhìn của người
dùng và bộ phận quản lý bộ nhớ:
Góc nhìn của người sử dụng: Tiến trình của người dùng
nhìn bộ nhớ như là một không gian liên tục, đồng nhất
và chỉ chứa duy nhất bản thân tiến trình này.
Góc nhìn của bộ nhớ vật lý: Tiến trình của người sử
dụng được lưu trữ phân tán khắp bộ nhớ, trong bộ nhớ
đồng thời cũng chứa những tiến trình khác.
Phần cứng đảm nhiệm việc chuyển đổi địa chỉ logic
thành địa chỉ vật lý. Sự chuyển đổi này là trong suốt
đối với người sử dụng.
2.4 Kỹ thuật phân đoạ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
 Không gian địa chỉ là một tập các phân đoạn
(segments).
 Các phân đoạn là những phần bộ nhớ kích thước
khác nhau và có liên hệ logic với nhau. Mỗi phân
đoạn có một tên gọi (số hiệu phân đoạn) và một độ
dài.
 Người dùng sẽ thiết lập mỗi địa chỉ với hai giá trị:
.
54
55
Cơ chế MMU trong kỹ thuật phân đoạn
56
 Cần phải xây dựng một ánh xạ để chuyển đổi các
địa chỉ 2 chiều được người dùng định nghĩa
thành địa chỉ vật lý một chiều. Sự chuyển đổi
này được thực hiện qua một bảng phân đoạn.
 Mỗi thành phần trong bảng phân đoạn bao gồm
một thanh ghi nền và một thanh ghi giới hạn:
 Thanh ghi nền lưu trữ địa chỉ vật lý nơi bắt đầu phân
đoạn trong bộ nhớ
 Thanh ghi giới hạn đặc tả chiều dài của phân đoạn.
2.4 Kỹ thuật phân đoạn
Chuyển đổi địa chỉ:
 Mỗi địa chỉ ảo là một bộ 
 Số hiệu phân đoạn s : được sử dụng như chỉ mục đến
bảng phân đoạn (địa chỉ cơ sở của phân đoạn mà
đoạn chương trình tương ứng được nạp)
 địa chỉ tương đối d : có giá trị trong khoảng từ 0 đến
giới hạn chiều dài của phân đoạn. Nếu địa chỉ
tương đối hợp lệ, nó sẽ được cộng với giá trị chứa
trong thanh ghi nền để phát sinh địa chỉ vật lý tương
ứng (cho biết độ dài của phân đoạn)
57
58
9.59
VD
Chia sẻ phân đoạn
60
 Một ưu điểm khác của kỹ thuật phân đoạn là khả
năng chia sẻ ở mức độ phân đoạn. Nhờ khả năng
này, các tiến trình có thể chia sẻ với nhau từng
phần chương trình (ví dụ các thủ tục, hàm), không
nhất thiết phải chia sẻ toàn bộ chương trình như
trường hợp phân trang
 Mỗi tiến trình có một bảng phân đoạn riêng, một
phân đoạn được chia sẻ khi các phần tử trong
bảng phân đoạn của hai tiến trình khác nhau cùng
chỉ đến một vị trí vật lý duy nhất
Chia sẻ code trong hệ phân đoạn
61
2.4 Kỹ thuật phân đoạn
 Khi tiến trình được nạp vào bộ nhớ thì tất cả các
đoạn của 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
62
63
Trong hệ thống sử dụng kỹ thuật phân đoạn , hiện
tượng phân mảnh ngoại vi lại xuất hiện khi các khối
nhớ tự do đều quá nhỏ, không đủ để chứa một
phân đoạn.
Tường minh với người sử dụng, cung cấp một sự
thuận lợi để người lập trình tổ chức chương trình
và dữ liệu.
Kỹ thuật này cũng phải giải quyết vấn đề cấp phát
động
Kỹ thuật phân đoạn phải cấp phát các khối nhớ có
kích thước khác nhau cho các phân đoạn trên bộ
nhớ vật lý kết hợp phân trang với phân đoạn.
2.5. Phân đoạn kết hợp phân trang 
(Paged segmentation)
64
Không gian địa chỉ là một tập các phân đoạn, mỗi
phân đoạn được chia thành nhiều trang. Khi một tiến
trình được đưa vào hệ thống, hệ điều hành sẽ cấp
phát cho tiến trình các trang cần thiết để chứa đủ
các phân đoạn của tiến trình.
Cơ chế MMU trong kỹ thuật phân đoạn kết 
hợp phân trang
65
Không gian địa chỉ là một tập các phân đoạn, mỗi
phân đoạn được chia thành nhiều trang.
Khi một tiến trình được đưa vào hệ thống, hệ điều
hành sẽ cấp phát cho tiến trình các trang cần thiết
để chứa đủ các phân đoạn của tiến trình.
Cơ chế MMU: Để hỗ trợ kỹ thuật phân đoạn, cần có
một bảng phân đoạn, nhưng giờ đây mỗi phân
đoạn cần có một bảng trang phân biệt.
Chuyển đổi địa chỉ
66
Mỗi địa chỉ logic là một bộ ba: 
 số hiệu phân đoạn (s): sử dụng như chỉ
mục đến phần tử tương ứng trong bảng phân
đoạn.
 số hiệu trang (p): sử dụng như chỉ mục đến
phần tử tương ứng trong bảng trang của
phânđoạn.
 đị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.
Mô hình phân đoạn kế hợp phân trang
67
68
Tóm tắt
69
 Có nhiều cách tiếp cận khác nhau để tổ chức quãn lý bộ nhớ, nhưng
tựu chung mong đạt đến các mục tiêu sau :
 Có thể đáp ứng được đầy đủ các nhu cầu bộ nhớ của chương trình
với một bộ nhớ vật lý giới hạn
 Quá trình chuyển đổi địa chỉ, tổ chức cấp phát bộ nhớ là trong suốt
với người dùng, và có khả năng tái định vị.
 Tận dụng hiệu quả bộ nhớ ( ít có vùng nhớ không sử dụng được)
 Bộ nhớ được bảo vệ tốt
 Có khả năng chia sẻ bộ nhớ giữa các tiến trình
 Một số cách tiếp cận tổ chức bộ nhớ chính
 Cấp phát liên tục : có thể cấp phát các vùng nhớ liên tục cho các tiến
trình trong những phân vùng có kích thước cố định hay biến động.
Điểm yếu của cách tiếp cận này là kích thước các chương trình có thể
dược xử lý bị giới hạn bởi các kích thước của khối nhớ liên tục có thể
sử dụng. Các hiện tượng phân mảnh ngoại vi, nội vi đều có thể xuất
hiện
 Cấp phát không liên tục : có thể cấp phát các vùng nhớ không liên tục
cho một tiến trình. Hai kỹ thuật thường được áp dụng là phân trang và
phân đoạn. Kỹ thuật phân trang cho phép loại bõ hiện tượng phân
mảnh ngoại vi, kỹ thuật phân đoạn loại bỏ hiện tượng phân mảnh nội
vi, nhưng phải giải quyết vấn đề cấp phát động.
3. KỸ THUẬT BỘ NHỚ ẢO
3.1 Khái niệm nhớ ảo (virtual memory)
 Để 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ý
71
Bộ nhớ ảo là một kỹ thuật hiện đại giúp cho người 
dùng được giải phóng hoàn toàn khỏi mối bận tâm 
về giới hạn bộ nhớ
3.1 Khái niệm nhớ ảo
 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
72
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 (demand paging): 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
73
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
74
3.2.1 Phân trang theo yêu cầu
Với mô hình này, cần cung cấp một cơ chế phần
cứng giúp phân biệt các trang đang ở trong bộ nhớ
chính và các trang trên đĩa. Có thể sử dụng lại
bit valid-invalid nhưng với ngữ nghĩa mới:
 valid : trang tương ứng là hợp lệ và đang ở trong bộ
nhớ chính .
 invalid : hoặc trang bất hợp lệ (không thuộc về không
gian địa chỉ của tiến trình) hoặc trang hợp lệ
nhưng đang được lưu trên bộ nhớ phụ.
Một phần tử trong bảng trang mộ tả cho một trang
không nằm trong bộ nhớ chính, sẽ được đánh dấu
invalid và chứa địa chỉ của trang trên bộ nhớ phụ.
75
Cơ chế phần cứng
76
Cơ chế phần cứng hỗ trợ kỹ thuật phân trang theo
yêu cầu là sự kết hợp của cơ chế hỗ trợ kỹ thuật
phân trang và kỹ thuật swapping:
 Bảng trang: Cấu trúc bảng trang phải cho phép phản
ánh tình trạng của một trang là đang nằm trong bộ nhớ
chính hay bộ nhớ phụ.
 Bộ nhớ phụ: Bộ nhớ phụ lưu trữ những trang
không được nạp vào bộ nhớ chính. Bộ nhớ phụ
thường được sử dụng là đĩa, và vùng không gian đĩa
dùng để lưu trữ tạm các trang trong kỹ thuật
swapping được gọi là không gian swapping.
Thay thế trang
Thuật toán thay thế trang: Thuật toán lựa một trang
“nạn nhân” để chuyển ra bộ nhớ phụ với chung một
mục tiêu: Chọn trang “nạn nhân” là trang mà sau khi
thay thế sẽ gây ra ít lỗi trang nhất.
Chúng ta đánh giá một giải thuật bằng cách chạy nó
trên một chuỗi các tham chiếu bộ nhớ cụ thể và tính
số lượng lỗi trang.
 Giải thuật thay thế tối ưu.
 Giải thuật thay thế NRU (Not-Recently-Used).
 Giải thuật thay thế FIFO.
 Giải thuật thay thế Second Chance.
 Giải thuật thay thế vòng tròn.
 Giải thuật thay thế LRU (Least Recently Used).
77
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
78
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
79