Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0
III.5 Phủ lắp
Để cho phép một quá trình lớn hơn lượng bộ nhớ được cấp phát cho nó, chúng
ta sử dụng cơ chế phủ lắp (overlays). Ý tưởng phủ lắp là giữ trong bộ nhớ những chỉ
thị và dữ liệu được yêu cầu tại bất kỳ thời điểm nào được cho. Khi những chỉ thị đó
được yêu cầu, chúng được nạp vào không gian được chiếm trước đó bởi các chỉ thị
mà chúng không còn cần nữa.
Thí dụ, xét trình dịch hợp ngữ hai lần (two-pass assembler). Trong suốt lần thứ
1, nó xây dựng bảng danh biểu; sau đó, trong lần thứ 2, nó tạo ra mã máy. Chúng ta
có thể phân chia trình dịch hợp ngữ thành mã lần 1, mã lần 2, bảng danh biểu, và
những thủ tục hỗ trợ chung được dùng bởi lần 1 và lần 2. Giả sử kích thước của các
thành phần này như sau:
Lần 1 70 KB
Lần 2 80 KB
Bảng danh biểu 20 KB
Các thủ tục chung 30 KB
Để nạp mọi thứ một lần, chúng ta cần 200KB bộ nhớ. Nếu chỉ có 150KB sẳn
có, chúng ta không thể chạy quá trình của chúng ta. Tuy nhiên, chú ý rằng lần 1 và lần
2 không cần ở trong bộ nhớ cùng một lúc. Do đó, chúng ta định nghĩa hai phủ lắp.
Phủ lắp A là bảng danh biểu, các thủ tục chung, lần 1, và phủ lắp B là bảng biểu
tượng, các thủ tục chung và lần 2.
Chúng ta bổ sung trình điều khiển phủ lắp (10 KB) và bắt đầu với phủ lắp A
trong bộ nhớ. Khi chúng ta kết thúc lần 1, chúng ta nhảy tới trình điều khiển phủ lắp,
trình điều khiển này sẽ đọc phủ lắp B vào trong bộ nhớ, viết chồng lên phủ lắp B và
sau đó chuyển điều khiển tới lần 2. Phủ lắp A chỉ cần 120KB, ngược lại phủ lắp B cần
130KB (hình VII-3). Bây giờ chúng ta có thể chạy trình hợp ngữ trong 150KB bộ
nhớ. Nó sẽ nạp nhanh hơn vì rất ít dữ liệu cần được chuyển trước khi việc thực thi bắt
đầu. Tuy nhiên, nó sẽ chạy chậm hơn do nhập/xuất phụ đọc mã mã cho phủ lắp A qua
mã cho phủ lắp B.
Hình 0-3- Các phủ lắp cho một bộ hợp ngữ dịch hai lần
Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang
141
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0
Mã cho phủ lắp A và mã cho phủ lắp B được giữ trên đĩa như những hình ảnh
bộ nhớ tuyệt đối, và được đọc bởi trình điều khiển phủ lắp khi cần. Tái định vị đặc
biệt và các giải thuật liên kết được yêu cầu xây dựng các phủ lắp.
IV Hoán vị
Một quá trình cần ở trong bộ nhớ để được thực thi. Tuy nhiên, một quá trình có
thể được hoán vị (swapped) tạm thời khỏi bộ nhớ tới vùng lưu trữ phụ backing store,
sau đó mang trở lại bộ nhớ để việc thực thi được tiếp tục. Thí dụ, giả sử một môi
trường đa chương với giải thuật lập thời biểu CPU round-robin. Khi định mức thời
gian hết, bộ quản lý bộ nhớ sẽ bắt đầu hoán vị ra (swap out) vùng lưu trữ phụ quá
trình vừa mới kết thúc và hoán vị vào (swap in) một quá trình khác tới không gian bộ
nhớ được trống (hình VII-4). Do đó, bộ định thời biểu CPU sẽ cấp những phần thời
gian tới những quá trình khác trong bộ nhớ. Lý tưởng, bộ quản lý sẽ hoán vị các quá
trình đủ nhanh để một vài quá trình sẽ ở trong bộ nhớ, sẳn sàng thực thi, khi bộ định
thời CPU muốn định thời lại CPU. Định mức cũng phải đủ lớn để phù hợp lượng tính
toán được thực hiện giữa các hoán vị.
Hình 0-4- Hoán vị hai quá trình dùng đĩa như là backing store
Một biến thể của chính sách hoán vị này được dùng cho các giải thuật định
thời trên cơ sở ưu tiên. Nếu một quá trình có độ ưu tiên cao hơn đến và muốn phụ vụ,
bộ quản lý bộ nhớ có thể hoán vị ra quá trình có độ ưu tiên thấp hơn để mà nó có thể
nạp và thực thi quá trình có độ ưu tiên cao hơn. Khi quá trình có độ ưu tiên cao hơn
kết thúc, quá trình có độ ưu tiên thấp hơn có thể được hoán vị vào trở lại và được tiếp
tục. Biến thể của hoán vị này thường được gọi là cuộn ra (roll out), và cuộn vào (roll
in).
Thông thường, một quá trình được hoán vị ra sẽ được hoán vị trở lại vào cùng
không gian bộ nhớ mà nó đã chiếm trước đó. Sự giới hạn này được sai khiến bởi
phương pháp liên kết địa chỉ. Nếu liên kết địa chỉ được thực hiện tại thời điểm hợp
dịch hay nạp thì quá trình không thể được di chuyển vào không gian bộ nhớ khác vì
các địa chỉ vật lý được tính trong thời gian thực thi.
Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang
142
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0
Hoán vị yêu cầu một vùng lưu trữ phụ (backing store). Vùng lưu trữ phụ này
thường là một đĩa tốc độ cao. Nó phải đủ lớn để chứa các bản sao của tất cả hình ảnh
bộ nhớ cho tất cả người dùng, và nó phải cung cấp truy xuất trực tiếp tới các hình ảnh
bộ nhớ này. Hệ thống này duy trì một hàng đợi sẳn sàng chứa tất cả quá trình mà các
hình ảnh bộ nhớ của nó ở trong vùng lưu trữ phụ hay trong bộ nhớ và sẳn sàng để
thực thi. Bất cứ khi nào bộ định thời CPU quyết định thực thi một quá trình, nó gọi bộ
phân phát (dispacher). Bộ phân phát kiểm tra để thấy quá trình tiếp theo trong hàng
đợi ở trong bộ nhớ không. Nếu không, và không có vùng bộ nhớ trống, bộ phân phát
hoán vị ra một quá trình hiện hành trong bộ nhớ và hoán vị vào một quá trình mong
muốn. Sau đó, nó nạp lại các thanh ghi và chuyển điều khiển tới quá trình được chọn.
Trong các hệ hoán vị, thời gian chuyển đổi giữa các tác vụ cần được quan tâm. Mỗi
quá trình cần được phân chia một khoảng thời gian sử dụng CPU đủ lớn để không
thấy rõ sự chậm trễ do các thao tác hoán vị gây ra. Nếu không, hệ thống sẽ dùng phần
lớn thời gian để hoán vị các quá trình vào ra bộ nhớ chính, CPU như vậy sẽ không sử
dụng hiệu quả.
Hoán vị cũng bị ràng buộc bởi yếu tố khác. Nếu chúng ta muốn hoán vị một
quá trình, chúng ta phải đảm bảo rằng nó hoàn toàn rỗi. Quan tâm đặc biệt là việc chờ
nhập/xuất. Một quá trình có thể đang chờ thao tác nhập/xuất khi chúng ta hoán vị quá
trình đó tới nơi trống bộ nhớ của nó. Tuy nhiên, nếu nhập/xuất đang truy xuất không
đồng bộ bộ nhớ người dùng cho nhập/xuất vùng đệm, thì quá trình không thể được
hoán vị. Giả sử rằng thao tác nhập/xuất đang xếp hàng chờ vì thiết bị đang bận. Sau
đó, nếu chúng ta hoán vị quá trình P
1
ra và hoán vị P
2
vào thì thao tác nhập/xuất có
thể cố gắng sử dụng bộ nhớ hiện thuộc về quá trình P
2
. Hai giải pháp chủ yếu cho quá
trình này là không bao giờ hoán vị quá trình đang chờ nhập/xuất hay thực thi các thao
tác nhập/xuất chỉ ở trong vùng đệm của hệ điều hành. Chuyển giữa các vùng đệm của
hệ điều hành và bộ nhớ quá trình thì chỉ xảy ra khi quá trình được hoán vị vào.
V Cấp phát bộ nhớ liên tục
Bộ nhớ chính phải cung cấp cho cả hệ điều hành và các quá trình người dùng
khác nhau. Do đó, chúng ta cần cấp phát những phần khác nhau của bộ nhớ chính
trong những cách hiệu quả nhất có thể. Phần này chúng ta giải thích một phương pháp
thông dụng, cấp phát bộ nhớ liên tục.
Bộ nhớ thường được phân chia thành hai phân khu, một cho hệ điều hành định
vị và một cho các quá trình người dùng. Chúng ta có thể đặt hệ điều hành ở bộ nhớ
cao hay bộ nhớ thấp. Yếu tố quan trọng ảnh hưởng tới quyết định này là vị trí của
vector ngắt. Vì vector ngắt thường ở trong bộ nhớ thấp nên các lập trình viên thường
cũng đặt hệ điều hành trong bộ nhớ thấp. Do đó, trong giáo trình này chúng ta sẽ thảo
luận chỉ trường hợp hệ điều hành định vị trong bộ nhớ thấp. Phát triển của trường hợp
khác là tương tự.
Chúng ta thường muốn nhiều quá trình người dùng định vị trong bộ nhớ tại
cùng thời điểm. Do đó, chúng ta cần xem xét cách cấp phát bộ nhớ trống tới những
quá trình ở trong hàng đợi nhập đang chờ được mang vào bộ nhớ. Trong cấp phát bộ
nhớ liên tục, mỗi quá trình được chứa trong một phần bộ nhớ liên tục.
V.1 Bảo vệ bộ nhớ
Trước khi thảo luận cấp phát bộ nhớ chúng ta phải thảo luận vấn đề bảo vệ bộ
nhớ-bảo vệ hệ điều hành từ quá trình người dùng, và bảo vệ các quá trình từ một quá
trình khác. Chúng ta có thể cung cấp bảo vệ này bằng cách dùng thanh ghi tái định vị.
Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang
143
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0
Thanh ghi tái định vị chứa giá trị địa chỉ vật lý nhỏ nhất; thanh ghi giới hạn chứa dãy
các định chỉ luận lý (thí dụ: tái định vị = 100040 và giới hạn = 74600). Với các thanh
ghi tái định vị và giới hạn, mỗi địa chỉ luận lý phải ít hơn thanh ghi giới hạn; MMU
ánh xạ địa chỉ luận lý động bằng cách cộng giá trị trong thanh ghi tái định vị. Địa chỉ
được tái định vị này được gửi tới bộ nhớ (như hình VII-5).
Hình 0-5 Hỗ trợ phần cứng cho các thanh ghi tái định vị và các giới hạn
Khi bộ định thời CPU chọn một quá trình thực thi, bộ phân phát nạp thanh ghi
tái định vị và giới hạn với các giá trị đúng như một phần của chuyển đổi ngữ cảnh. Vì
mọi địa chỉ được phát sinh bởi CPU được kiểm tra dựa trên các thanh ghi này, chúng
ta có thể bảo vệ hệ điều hành và các chương trình và dữ liệu người dùng khác từ việc
sửa đổi bởi quá trình đang chạy này.
Cơ chế dùng thanh ghi tái định vị cung cấp một cách hiệu quả để cho phép kích
thước hệ điều hành thay đổi động. Khả năng mềm dẽo này có thể mong muốn trong
nhiều trường hợp. Thí dụ, hệ điều hành chứa mã và không gian vùng đệm cho trình
điều khiển thiết bị. Nếu một trình điều khiển thiết bị (hay dịch vụ hệ điều hành khác)
không được dùng phổ biến, nó không muốn giữ mã và dữ liệu trong bộ nhớ, khi
chúng ta có thể dùng không gian đó cho mục đích khác. Những mã như thế thường
được gọi là mã hệ điều hành tạm thời (transient operating system code); nó đến và đi
khi được yêu cầu. Do đó, dùng mã này thay đổi kích thước của hệ điều hành trong khi
thực thi chương trình.
Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang
144
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0
V.2 Hệ thống đơn chương
Trong phương pháp này bộ nhớ được chia sẻ cho hệ điều hành và một chương
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ề quá trình người dùng duy nhất trong hệ
thống (Hình VII-6). Quá trình này được toàn quyền sử dụng bộ nhớ dành cho nó.
User process
Operating
system
0xFFF…
0
Hình 0-6 Tổ chức bộ nhớ trong hệ thống đơn chương
Khi bộ nhớ được tổ chức theo cách thức này, chỉ có thể xử lý một chương
trình tại một thời điểm. Quan sát hoạt động của các quá 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 quá trình
chia sẻ CPU với nhau để hoạt động đồng hành.
V.3 Hệ thống đa chương với phân khu 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 khu có kích thước cố định. Mỗi phân khu có thể chứa chính
xác một quá trình. Do đó, cấp độ đa chương được giới hạn bởi số lượng phân khu.
Trong phương pháp đa phân khu, khi một phân khu rảnh, một quá trình được chọn từ
hàng đợi nhập và được nạp vào phân khu trống. Khi quá trình kết thúc, phân khu trở
nên sẳn dùng cho một quá 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 khu sẽ có một hàng đợi tương ứng
(hình VII-7a). Khi một quá trình mới được tạo ra, nó được đưa vào hàng
đợi của phân khu có kích thước nhỏ nhất thoả nhu cầu chứa nó. 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
khu trống trong khi các hàng đợi của các phân khu khác lại đầy, buộc các
quá trình trong những hàng đợi này phải chờ được cấp phát bộ nhớ.
• Sử dụng một hàng đợi: tất cả các quá trình được đặt trong hàng đợi duy
nhất (hình VII-7b). Khi có một phân khu trống, quá trình đầu tiên trong
hàng đợi có kích thước phù hợp sẽ được đặt vào phân khu và cho xử lý.
Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang
145
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0
a. Sử dụng nhiều hàng đợi b. Sử dụng một hàng đợi
Hình 0-7 Cấp phát phân khu có kích thước cố định
Khi sử dụng giải thuật này người ta muốn tránh sự hao phí một phân khu lớn
cho một công việc nhỏ, nhưng lại xảy ra bất bình đẳng, bất lợi đối với các công việc
nhỏ. Để giải quyết người ta thêm vào qui luật là một công việc sẽ không bị bỏ qua
nữa nếu nó đã bị bỏ qua k lần qui định. Mỗi lần một công việc bị bỏ qua nó được
đánh dấu một điểm. Khi đạt được số điểm qui định, nó sẽ không bị bỏ qua nữa, sẽ
được nạp vào và thực hiện mặc dầu có thể trên một phân khu lớn hơn.
Phương pháp này ban đầu được sử dụng bởi hệ điều hành IBM OS/360, nó
được gọi là MFT (Multiprogramming with Fixed number of Tasks). Hiện nay nó
không còn sử dụng nữa.
V.4 Hệ thống đa chương với phân khu động
Cơ chế này là tổng quát của cơ chế phân khu cố định. Nó được dùng chủ yếu
trong môi trường xử lý theo lô. Nhiều ý tưởng được trình bày ở đây cũng có thể áp
dụng tới môi trường chia thời mà trong đó phân đoạn thuần được dùng cho việc quản
lý bộ nhớ.
Hệ điều hành giữ một bảng hiển thị những phần nào của bộ nhớ là sẳn dùng và
phần nào đang bận. Ban đầu, tất cả bộ nhớ là sẳn dùng cho quá trình người dùng, và
được xem như một khối lớn bộ nhớ sẳn dùng hay một lỗ. Khi một quá trình đến và
cần bộ nhớ, chúng ta tìm kiếm một lỗ trống đủ lớn cho quá trình này. Nếu chúng ta
tìm thấy, chúng ta cấp phát chỉ phần bộ nhớ nhiều bằng lượng được yêu cầu, phần còn
lại sẳn dùng để thoả mãn những yêu cầu tương lai (Hình VII-8).
Partition 3
200K
600K
400K
Operating
system
Partition 1
Partition 4
Partition 3
Partition 4
Partition 1
Operating
system
Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang
146
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0
Thời gian
D
C
B
OS
OS
B
C
A
OS
B
C
B
OS
A
D
C
OS
D
C
E
OS
A
OS
Hình VIII-8 Cấp phát các phân khu có kích thước thay đổi
Khi các quá trình đi vào hệ thống, chúng được đặt vào hàng đợi nhập. Hệ điều
hành xem xét yêu cầu bộ nhớ của mỗi quá trình và lượng không gian bộ nhớ sẳn có để
xác định các quá trình nào được cấp phát bộ nhớ. Khi một quá trình được cấp không
gian, nó được nạp vào bộ nhớ và sau đó nó có thể cạnh tranh CPU. Khi một quá trình
kết thúc, nó giải phóng bộ nhớ của nó, sau đó hệ điều hành có thể đặt một quá trình
khác từ hàng đợi nhập.
Tại bất cứ thời điểm được cho, chúng ta có một danh sách kích thước khối
trống và hàng đợi nhập. Hệ điều hành có thể xếp hàng đợi nhập dựa theo giải thuật
định thời. Bộ nhớ được cấp phát tới quá trình cho đến khi các yêu cầu bộ nhớ của quá
trình kế tiếp không thể được thoả; không có khối bộ nhớ trống (hay lỗ) đủ lớn để quản
lý quá trình đó. Sau đó, hệ điều hành có thể chờ cho đến khi khối đủ lớn sẳn dùng hay
nó có thể di chuyển xuống hàng đợi nhập để xem các yêu cầu bộ nhớ nhỏ hơn của các
quá trình khác có thể được thoả hay không.
Thông thường, một tập hợp các lỗ 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 quá trình đến và yêu cầu bộ nhớ,
hệ thống tìm tập hợp này một lỗ trống đủ lớn cho quá trình này. Nếu lỗ trống quá lớn,
nó được chia làm hai: một phần được cấp tới quá trình đến; phần còn lại được trả về
tập hợp các lỗ. Nếu lỗ mới nằm kề với các lỗ khác, các lỗ nằm kề này được gom lại để
tạo thành một lỗ lớn hơn. Tại thời điểm này, hệ thống cần kiểm tra có quá trình nào
đang chờ bộ nhớ và bộ nhớ trống mới hay bộ nhớ vừa được kết hợp lại có thể thoả
yêu cầu của bất cứ quá trình đang chờ này không.
Thủ tục này là một trường hợp đặc biệt của vấn đề cấp phát lưu trữ động là làm
cách nào để thoả mãn một yêu cầu có kích thước n từ danh sách lỗ trống. Có hai giải
pháp chủ yếu cho vấn đề này.
1) 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 (Hình VII-9). 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 quá 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ạ, nếu kích thước đơn
Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang
147
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0
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.
11111000
11111111
11001111
11111000
ABCDE
b
a
)
)
Bộ nhớ có 5 quá trình và 3 lỗ trống
Bản đồ bit tương ứng
Hình 0-9 Quản lý bộ nhớ bằng bản đồ bit
2) 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, một phân đoạn có thể là
một quá trình hay một vùng nhớ trống giữa hai quá trình. Danh sách liên kết
gồm nhiều mục từ liên tiếp. Mỗi mục từ gồm 1 bit đầu để xác định phân đoạn
đó là lỗ trống (H) hay một quá 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ớ. Sơ đồ quản lý
bằng danh sách liên kết tương ứng với sơ đồ quản lý bằng bản đồ bit được
minh hoạ trong hình VII-10.
3)
Hình 0-10 Quản lý bộ nhớ bằng danh sách liên kết
Tập hợp các lỗ trống được tìm thấy để xác định lỗ nào là tốt nhất để cấp phát.
Các chiến lược first-fit, best-fit, worst-fit là những chiến lược phổ biến nhất được
dùng để chọn một lỗ trống từ tập hợp các lỗ trống.
• First-fit: cấp phát lỗ trống đầu tiên đủ lớn. Tìm kiếm có thể bắt đầu tại đầu
tập hợp các lỗ 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 lỗ trống đủ lớn.
• Best-fit: cấp phát lỗ trống 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. Chiến lược này
tạo ra lỗ trống nhỏ nhất còn thừa lại.
Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang
148
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0
• Worst-fit: cấp phát lỗ trống lớn nhất. Chúng ta phải tìm toàn danh sách trừ
khi nó được xếp theo thứ tự kích thước. Chiến lược này tạo ra lỗ trống còn
lại lớn nhất mà có thể có ích hơn lỗ trống nhỏ từ tiếp cận best-fit.
Các mô phỏng hiển thị rằng cả first-fit và best-fit là tốt hơn worst-fit về việc
giảm thời gian và sử dụng lưu trữ. Giữa first-fit và best-fit không thể xác định rõ
chiến lược nào tốt hơn về sử dụng lưu trữ, nhưng first-fit có tốc độ nhanh hơn.
Tuy nhiên, các giải thuật này gặp phải vấn đề phân mãnh ngoài (external
fragmentation). Khi các quá trình được nạp và được xoá khỏi bộ nhớ, không gian bộ
nhớ trống bị phân rã thành những mãnh nhỏ. Phân mãnh ngoài tồn tại khi tổng không
gian bộ nhớ đủ để thoả mãn một yêu cầu, nhưng nó không liên tục; vùng lưu trữ bị
phân mãnh thành một số lượng lớn các lỗ nhỏ. Vấn đề phân mãnh này có thể rất lớn.
Trong trường hợp xấu nhất, chúng có thể có một khối bộ nhớ trống nằm giữa mỗi hai
quá trình. Nếu tất cả bộ nhớ này nằm trong một khối trống lớn, chúng ta có thể chạy
nhiều quá trình hơn.
Chọn lựa first-fit so với best-fit có thể ảnh hưởng tới lượng phân mãnh. (First-
fit là tốt hơn đối với một số hệ thống, ngược lại best fit là tốt hơn cho một số hệ thống
khác). Một yếu tố khác là phần cuối của khối trống nào được cấp phát. (phần còn dư
nào-phần trên đỉnh, hay phần ở dưới đáy?). Vấn đề không do giải thuật nào được dùng
mà do phân mãnh ngoài.
V.5 Quản lý bộ nhớ với hệ thống bạn thân
Như ta đã thấy trong phần trước, việc quản lý các lỗ hổng trên những bảng liệt
kê được sắp xếp theo kích thước làm cho việc cấp phát bộ nhớ rất nhanh, nhưng lại
làm chậm cho việc ngưng cấp phát bởi vì ta phải chú ý đến các láng giềng. Hệ thống
bạn thân (Buddy System) là một giải thuật quản lý bộ nhớ tận dụng thuận lợi của
việc máy tính dùng những số nhị phân cho việc đánh địa chỉ để tăng tốc độ kết hợp
những lỗ hổng sát nhau khi một quá trình hoàn thành hoặc được hoán vị ra ngoài.
Với phương pháp này, bộ quản lý bộ nhớ sẽ có một bảng liệt kê những khối
còn tự do có kích thước 1, 2, 4, 16 bytes đến kích thước của bộ nhớ, tức là có kích
thước bằng lũy thừa của 2. Khi có một quá trình cần cấp phát bộ nhớ, một lỗ hổng có
kích thước bằng luỹ thừa của 2 đủ chứa quá trình sẽ được cấp phát. Nếu không có lỗ
hổng yêu cầu, các lỗ hổng sẽ được phân đôi cho đến khi có được lỗ hỗng cần thiết.
Khi một quá trình chấm dứt, các lỗ hổng kế nhau có kích thước bằng nhau sẽ được
nhập lại để tạo thành lỗ hổng lớn hơn. Do đó, giải thuật này được gọi là hệ thống bạn
thân.
Thí du: với bộ nhớ 1M, cần phải có 21 bảng liệt kê như thế sắp từ 1 bytes (2
0
)
đến 1 byte (2
20
). Khởi đầu toàn bộ bộ nhớ còn tự do và bảng liệt kê 1M có một mục từ
độc nhất chứa đựng một lỗ hổng 1M, tất cả các bảng liệt kê khác đều rỗng. Cấu hình
bộ nhớ lúc khởi đầu được chỉ ra trong hình VII-11.
Memory
0
128 K
256 K
384 K
512K
640 K 768 K 896 K 1M
Initially 1 Hole
request 70
A 128 256 512 3
request 35
A B 64 256 512 3
request 80
A B 64 C 128 512 3
return A
128 B 64 C 128 512 4
Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang
149
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0
request 60
128 B D C 128 512 4
return B
128 64 D C 128 512 4
return D
256 C 128 512 3
return C
1024 1
Hình 0-11Hệ thống bạn thân với kích thước 1M
Bây giờ chúng ta hãy xem cách hệ thống buddy làm việc khi một quá trình
70K được hoán vị vào bộ nhớ trống 1M. Do những lỗ hổng chỉ có thể có kích thước là
lũy thừa của 2, 128K sẽ được yêu cầu, bởi vì đó chính là lũy thừa nhỏ nhất của 2 đủ
lớn. Không có khối 128K sẵn, cũng không có các khối 256K và 512K. Vì vậy khối
1M sẽ được chia làm hai khối 512K, được gọi là những bạn thân; một tại địa chỉ 0 và
một tại địa chỉ 512K. Sau đó khối tại địa chỉ thấp hơn, chính là khối tại 0 lại được
phân làm hai khối bạn thân 256K, một tại 0 và một tại 256K. Cái thấp hơn của chúng
lại được phân làm hai khối 128K, và khối tại 0, đánh dấu là A trong hình được cấp
phát cho quá trình.
Kế đến, một quá trình 35K được hoán vị vào. Khi đó ta cần khối 64K, nhưng
cũng không có sẵn, vì thế phải phân phối khối 128K thành hai khối bạn thân 64K, một
tại địa chỉ 128K, một tại 192K. Khối tại 128K được cấp cho quá trình, trong hình là B.
Yêu cầu thứ ba là 80K.
Bây giờ ta hãy xem những gì xảy ra khi một khối được trả lại. Giả sử tại thời
điểm này khối 128K (mà chỉ dùng có 70K) được tự do. Khi đó khối 128K sẽ được
đưa vào bảng tự do. Bây giờ cần một khối 60K. Sau khi kiểm tra, khối 64K tại 192K
được cấp phát và nó được đánh dấu là C.
Bây giờ khối B được trả lại. Tại thời điểm này có hai khối 128K tự do nhưng
chúng không được kết hợp lại. Chú ý rằng ngay cả khi khối 128K tại 0 được phân ra
làm 2, khối tại 9 được dùng và khối tại 84K còn tự do, sự kết hợp cũng không xãy ra.
Khi D được trả lại, sẽ có sự kết hợp lại thành khối 256K tại 0. Cuối cùng, khi C được
trả lại, sẽ có kết hợp tạo thành 1 lỗ hổng 1M như ban đầu.
Hệ thống bạn thân có sự thuận lợi so với những giải thuật cùng sắp xếp theo
kích thước của khối. Sự thuận lợi này là khi có một khối 2
k
bytes tự do, bộ quản lý bộ
nhớ chỉ cần tìm trong bảng liệt kê lỗ hổng có kích thước 2
k
để xem chúng có khả năng
kết hợp được hay không. Với những giải thuật khác mà trong đó cho phép các khối bộ
nhớ được phân chia một cách tùy ý, việc tìm kiếm phải diễn ra trên tất cả các bảng liệt
kê. Do dó, hệ thống bạn thân làm việc nhanh hơn.
Đáng tiếc, nó lại cực kỳ kém hiệu quả trong việc sử dụng bộ nhớ. Một quá
trình 35K phải được cấp phát đến 64K, hao phí đến 29K. Sự hao phí này được gọi là
sự phân mảnh trong (internal fragmentation), bởi vì phần bộ nhớ hao phí nằm bên
trong đoạn được cấp phát. Còn trong các phần trước ta thấy những lỗ hổng ở giữa các
đoạn, nhưng không có sự hao phí bên trong các đoạn, do đó kiểu này được coi là sự
phân mảnh ngoài.
Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang
150
Không có nhận xét nào:
Đăng nhận xét