Giáo trình Hệ điều hành - Chương 3: Quản lý lưu trữ

HỆ ĐIỀU HÀNH

Chương 3

QUẢN LÝ LƯU TRỮ

9. Quản lý bộ nhớ

9.1. Tổng quan

Như chúng ta đã thấy ở chương trước, bộ nhớ là trung tâm để thực

hiện của các máy tính hiện đại. Bộ nhớ bao gồm một mảng lớn các từ

(words) hoặc bytes nhớ, mỗi phần tử đều có địa chỉ riêng mình. CPU nhận

các lệnh từ bộ nhớ tuỳ theo giá trị của bộ đếm lệnh. Các lệnh này được

nạp từ thiết bị lưu trữ vào một địa chỉ xác định trong bộ nhớ.

Một chu kỳ thực hiện lệnh thông thường, chỉ thị lệnh được nhận từ

bộ nhớ, sau đó được giải mã và lấy các toán từ từ bộ nhớ. Sau khi chỉ thị

lệnh được thực hiện, kết quả lại được nạp trở lại bộ nhớ.

Sự liên kết địa chỉ

Thông thường, chương trình được lưu trữ trên đĩa như một file thi

hành. Chương trình phải được nạp vào bộ nhớ và đặt trong một tiến trình

để được thực hiện. Tuỳ thuộc vào cách quản lý bộ nhớ được sử dụng, các

tiến trình có thể chuyển qua lại giữa bộ nhớ và đĩa. Tập hợp các tiến trình

trên đĩa là đang chờ đợi để được nạp vào bộ nhớ để thực hiện ở hàng đợi

vào (input queue).

Thủ tục thông thường lựa chọn một tiến trình trong hàng đợi vào

và nạp tiến trình đó vào bộ nhớ. Trong khi tiến trình được thực hiện, nó

truy nhập các lệnh và dữ liệu từ bộ nhớ. Khi tiến trình kết thúc, vùng nhớ

của nó được giải phóng và có thể đáp ứng cho tiến trình khác.

Hầu hết các hệ thống đều cho phép các tiến trình người dùng được

lưu trú trong một phần bất kỳ của bộ nhớ vật lý. Mặc dù không gian địa

chỉ được bắt đầu từ 00000, địa chỉ đầu tiên tiến trình người dùng không

được từ 00000. Sự sắp xếp này có ảnh hưởng tới địa chỉ mà chương trình

người dùng có thể sử dụng. Trong hều hết các trường hợp, chương trình

người dùng phải trải qua một số bước trước khi có thể được thực hiện.

Địa chỉ có thể được biểu diễn theo nhiều cách khác nhau ở mỗi bước. Địa

chỉ trong chương trình nguồn được biểu diễn bằng các ký tự (dưới dạng

Phạm Ngọc Hưng

95

Quản lý lưu trữ

một cái tên). Một chương trình dịch sẽ tiến hành liên kết các địa chỉ ký tự

này thành các địa chỉ tương đối (tính từ đầu chương trình, đầu module).

Bộ liên kết hay bộ nạp sẽ chuyển các địa chỉ tương đối này thành các địa

chỉ tuyệt đối. Mỗi sự liên kết địa chỉ là một sự ánh xạ từ không gian địa

chỉ này sang một không gian địa chỉ khác.

Sự liên kết các lệnh và dữ liệu vào địa chỉ bộ nhớ có thể hoàn tất

qua các bước sau:

- Thời điểm dịch: Trong thời điểm này, tiến trình được nạp vào bộ

nhớ và các mã lệnh tuyệt đối được tạo ra. Các mã lệnh được phát triển và

tham chiếu tính từ vị trí bắt đầu nạp. Nếu sau này vị trí bắt đầu nạp bị

thay đổi thì các lệnh cần phải được dịch lại.

- Thời điểm nạp: trong thời điểm dịch, tiến trình được nạp vào bộ

nhớ và các mã lệnh tương đối được tạo ra. Việc liên địa chỉ được để dành

lại cho thời điểm nạp. nếu địa chỉ bắt đầu nạp thay đổi chỉ cần nạp lại các

mã lệnh người dùng kết hợp với giá trị thay đổi này.

- Thời điểm thực hiện: Nếu tiến trình có thể chuyển đổi quá lại giữa

đoạn này sang đoạn khác trong quá trình thực hiện thì việc liên kết địa chỉ

có thể để dành cho thời điểm thực hiện. Phần cứng đặc biệt sẽ phải được

chuẩn bị sẵn cho cách làm việc này. Hầu hết các hệ điều hành mục tiêu

chung đều sử dụng phương pháp này.

Không gian địa chỉ logic và không gian địa chỉ vật lý

Một địa chỉ được sinh bởi CPU thường là một địa chỉ logic:

Địa chỉ logic - còn gọi là địa chỉ ảo, là tất cả các đị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ỉ logic - 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 địa chỉ 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.

96

Phạm Ngọc Hưng

HỆ ĐIỀU HÀNH

Địa chỉ ảo và địa chỉ vật lý là như nhau trong phương thức liên kết

đị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ý.

9.2. Các phương pháp nạp chương trình

Nạp một lần

Toàn bộ mã lệnh và dữ liệu của chương trình được nạp vào bộ nhớ

một lần. Đây là một phương pháp đơn giản để nạp chương trình.

Theo cách này, thời gian thực sự để nạp chương trình là nhỏ nhất

có thể và tốc độ thực hiện chương trình cũng cao nhất vì tất cả các mã

lệnh và dữ liệu đã sẵn sàng trong bộ nhớ. Do nạp một lần tất cả mã lệnh

và dữ liệu của chương trình nên đòi hỏi bộ nhớ phải có đủ theo yêu cầu

của chương trình trong một thời điểm. Đây là một yêu cầu không phải lúc

nào cũng thoả mãn được vì không gian nhớ vật lý của máy thường là rất

nhỏ. Vì lý do này nên chỉ những chương trình có kích thước cũng như yêu

cầu vẹ bộ nhớ không lớn mới nạp đợc.

Nạp động

Toàn bộ chương trình và dữ liệu phải được nạp vào bộ nhớ để các

tiến trình thực hiện. Kích thước của bộ nhớ bị giới hạn bởi kích thước bộ

nhớ vật lý. Để khai thác tốt hơn không gian còn trống của bộ nhớ, ta có

thể sử dụng phương pháp nạp động. Với phương pháp này, một chương

trình con sẽ chỉ được nạp vào khi nó được gọi. Tất cả các chương trình

con đều được lưu trên đĩa theo. Khi cần, một chương trình con gọi đến

một chương trình con khác, trước hết nó sẽ kiểm tra xem chương trình đó

đã được nạp vào bộ nhớ hay chưa. Nếu chưa thì bộ nạp sẽ tiến hành nạp

chương trình con đó vào bộ nhớ và cập nhật vào bảng địa chỉ những thay

đổi. Sau khi chương trình con đã được nạp vào bộ nhớ thì quyền điều

khiển mới được trao cho nó.

Phương pháp này có nhiều ưu điểm: các chương trình con không

được thực hiện thì sẽ không bao giờ được nạp vào bộ nhớ. Toàn bộ mã

lệnh của chương trình có thể rất lớn nhưng nó lại được thực hiện trong

không gian nhớ nhỏ hơn rất nhiều.

Phạm Ngọc Hưng

97

Quản lý lưu trữ

Phương pháp nạp động này không đòi hỏi sự hỗ trợ đặc biệt nào

của hệ điều hành.

Thư viện chia sẻ và liên kết động

Trong phương pháp nạp một lần hay nạp động, các chương trình

được liên kết từ trước. Trong các chương trình có thể chứa những đoạn

mã giống nhau cùng thực hiện một số chức năng nào đó. Các đoạn mã

này có thể được tập hợp thành các thư viện. Khi liên kết, các đoạn mã

trong thư viện chương trình có sử dụng đến sẽ được sao chép và liên kết

có định ngay từ đầu vào chương trình. Việc này làm cho kích thước

chương trình lớn lên. Trong hệ thống có thể có nhiều chương trình đang

thực hiện với nhiều bản sao của cùng một đoạn mã.

Thay vì liên kết cố định các đoạn mã trong thư viện tĩnh vào

chương trình thì người ta có thể tổ chức các đoạn mã này trong một thư

viện liên kết động. Những đoạn mã này không được ghép ngay trong

chương trình mà chỉ khi chương trình được thực hiện thì đoạn mã mới

được tham khảo đến và liên kết với chương trình. Các chương trình khác

nhau cùng tham khảo đến một đoạn mã có thể tạo ra một bản sao riêng

cho mình hoặc sử dụng chung đoạn mã đã được nạp trong bộ nhớ.

Với các thư viện liên kết động, người ta có thể dễ dàng cập nhật,

nâng cấp lên phiên bản mới mà không phải thay đổi chương trình sử dụng

thư viện. Tất cả các chương trình có tham chiếu đến thư viện này đều

được tự động cập nhật phiên bản mới. Nếu nâng cấp thư viện tĩnh thì tất

cả các chương trình đã tham chiếu đến thư viện này trước kia đều phải

liên kết lại thì mới có thể sử dụng được phiên bản mới đó. Các thư viện

liên kết động có thể tồn tại nhiều phiên bản khác nhau và chúng có thể

cùng được nạp trong bộ nhớ. Tuỳ nhu cầu sử dụng, chương trình có thể

lựa chọn phiên bản cũ hoặc mới dựa vào các thông tin mô ta cho mỗi

phiên bản (thông tin này sẽ cho biết phiên bản mới thay đổi những gì).

Các thư viện liên kết động còn được gọi là các thư viện chia sẻ.

Không giống như nạp động, thư viện liên kết động cần tới sự hỗ trợ

của hệ điều hành. Nếu các tiến trình được bảo vệ khỏi sự xâm phạm của

98

Phạm Ngọc Hưng

HỆ ĐIỀU HÀNH

các tiến trình khác thì hệ điều hành cần can thiệp để cho phép một tiến

trình có thể tham chiếu đến một đoạn lệnh của tiến trình khác hoặc tất cả

các tiến trình đều được phép truy nhập vào một không gian địa chỉ.

Nạp kiểu Overlay

Để một chương trình lớn có thể được thực hiện trong một không

gian nhớ vật lý nhỏ ta có thể sử dụng cấu trúc overlay. Trong cấu trúc

này, chỉ những đoạn mã hiện đang sử dụng mới được nạp vào bộ nhớ để

thực hiện, các đoạn mã khác vẫn được lưu trữ trên đĩa. Khi cần đến đoạn

mã nào mà nó hiện chưa có trong bộ nhớ thì sẽ được tìm trên đĩa và nạp

vào bộ nhớ sau đó được thực hiện.

9.3. Các cấu trúc chương trình

Cấu trúc đơn giản (cấu trúc tuyến tính)

Toàn bộ chương trình được dịch và biên tập thành một module duy

nhất. Khi thực hiện, toàn bộ mã lệnh, dữ liệu của chương trình được nạp

vào bộ nhớ một lần.

Ưu điểm của cấu trúc này là chương trình chạy nhanh hơn. Chi phí

cho nạp chương trình thấp nhất. Để tổ chức chương trình

Nhược điểm là đòi hỏi bộ nhớ phải thoả mãn yều cầu của chương

trình trong cùng thời điểm. Với không gian bộ nhớ để thực thi chương

trình hạn chế, cấu trúc này chỉ cho phép phát triển các chương trình có

nhu cầu bộ nhớ ít. Phù hợp cho các bài toán nhỏ.

Cấu trúc động

Chương trình được chia thành nhiều module có thể được nạp chạy

độc lập. Mỗi module thường có cấu trúc logic hoàn chỉnh. Có hai phương

pháp để nạp chương trình.

Phương pháp thứ nhất, trong các module của chương trình có một

module chính. Module này sẽ được nạp chạy từ đầu và nằm cố định trong

bộ nhớ cho đến khi chương trình kết thúc. Module chính có nhiệm vụ điều

khiển nạp các module còn lại và cho thực thi các module đó. Bộ phần

mềm tiện ích NC chạy trên môi trường DOS là một ví dụ cho chương trình

có cấu trúc động.

Phạm Ngọc Hưng

99

Quản lý lưu trữ

Phương pháp thứ hai là coi tất cả các module như nhau, module

nào cũng có nhiệm vụ nạp module kế tiếp (nếu có) trước khi tự giải

phóng. Trong số các module, chỉ cần xác định module được nạp đầu tiên.

Trong bộ nhớ thường chỉ tồn tại module hiện đang thi hành. Khi một

module mới được nạp, nó sẽ thay thế cho module đã được nạp trước.

Phương pháp tổ chức chương trình này đòi hỏi người lập trình phải tự tổ

chức nạp các module. Mỗi module phải có khả năng tự giải phóng và nạp

các module khác.

Cấu trúc phủ (Overlay)

Một chương trình được viết theo cấu trúc overlay bao gồm các

thành phần sau:

- Bộ điều khiển overlay

- Bảng điều khiển overlay

- Các đoạn mã được gọi overlay

- Các đoạn mã dùng chung được nạp một lần

Bộ điều khiển overlay sẽ điều khiển việc nạp các đoạn mã gọi

overlay từ trên đĩa dựa trên bảng điều khiển overlay theo yêu cầu của

đoạn mã đang thực hiện.

Chương trình viết theo cấu trúc này thường được biên tập thành

hai phần. Một phần được thực thi ban đầu và nằm cố định trong bộ nhớ.

Phần còn lại chứa các module overlay. Các module này sẽ được nạp vào

bộ nhớ và thực hiện khi nó được tham chiếu đến.

Bộ nhớ để chạy chương trình overlay được chia thành các mức

được gọi là các mức overlay.

Các module được chia thành các nhóm tương ứng với các mức

overlay. Mỗi mức overlay yêu cầu bộ nhớ có độ lớn bằng kích thước bộ

nhớ của module lớn nhất trong mức. Mức 0 là mức dành cho các module

được nạp từ đầu và nằm cố định trong bộ nhớ suốt quá trình chương trình

thi hành. Các lớp còn lại sẽ được để dành sẵn không gian nhớ. Một

module thuộc mức nào thì sẽ được nạp vào vùng nhớ tương ứng với mức

đó. Module nạp sau sẽ ghi đè lên mã lệnh và dữ liệu của module được

100

Phạm Ngọc Hưng

HỆ ĐIỀU HÀNH

nạp trước đó (tính chất phủ). Các lời gọi đồng mức cần được tránh sử

dụng để không gây lỗi khi trở về địa chỉ đã bị thay đổi bởi module nạp

sau.

Mức 0 (9Kb)

Mức 1 (35Kb)

Mức 2 (48Kb)

M₃(32Kb)

M₄(40Kb)

M₂(28Kb)

M₁(35Kb)

M₅(48Kb)

M₆(25Kb)

M₀

(9Kb)

Hình 9.1: Chương trình cấu trúc overlay

Quan sát trên hình 9.1, ta thấy chương trình có tổng số 7 module

(M₀đến M₆) với tổng bộ nhớ các module là 217 Kb. Với cấu trúc overlay,

chương trình yêu cầu 3 vùng nhớ để thực hiện với tổng kích thước chỉ cần

92 Kb, nhở hơn nhiều so với kích thước của chương trình.

9.4. Tráo đổi bộ nhớ

Trong quá trình thực hiện, tiến trình phải được nạp vào bộ nhớ

nhưng chúng cũng có thể được lưu tạm ra bộ nhớ ngoài để rồi lại được

nạp từ bộ nhớ ngoài vào thực hiện ở phiên tiếp theo. Quantum (khoảng

thời gian nhỏ dành cho mỗi tiến trình) phải được lựa chọn sao cho đủ lớn

để có đủ thời gian cho việc tráo đổi các tiến trình giữa bộ nhớ trong và bộ

nhớ lưu trữ tạm thời bên ngoài.

9.5. Phương pháp cấp phát bộ nhớ liên tục

Bảo vệ bộ nhớ:

Bảo vệ bộ nhớ phải đảm bảo để các tiến trình không xâm phạm

vào vùng nhớ của hệ thống, bảo vệ các tiến trình sao cho vùng nhớ của

chúng không bị xâm phạm bởi các tiến trình khác.

Phạm Ngọc Hưng

101

Quản lý lưu trữ

Để thực hiện bảo vệ bộ nhớ người ta sử dụng hai thanh ghi: thanh

ghi giới hạn (limit register) và thanh ghi định lại địa chỉ (relocation

register).

Một địa chỉ logic được đưa ra từ CPU trước hết phải được kiểm tra

giới hạn theo thanh ghi limit register. Nếu địa chỉ không vượt giới hạn so

với thanh ghi này thì tiến hành cộng địa chỉ logic này với một số gia chứa

trong thanh ghi relocation register cho ra một địa chỉ vật lý của ô cần truy

nhập.

Cấp phát bộ nhớ:

Phân chia tĩnh: theo cách này, bộ nhớ được chia thành nhiều

phần (partition) cố định ngay từ đầu có kích thước không nhất thiết phải

bằng nhau. Mỗi một partition sẽ chỉ đáp ứng yêu cầu của duy nhất một

tiến trình.

Mức độ đa chương trình (hệ số song song) của hệ thống lệ thuộc

vào số lượng các phần. Mỗi phần chia sẽ phục vụ cho một tiến trình.

Khi một tiến trình vào hệ thống, nó được đưa vào hàng đợi vào và

để tiến trình có thể thực hiện nó phải được cấp phát bộ nhớ. Hệ thống

tiến hành tìm xem có phần nào còn trống hay không, nếu có thì tiến hành

cấp phát cho tiến trình. Khi một tiến trình kết thúc, phần nhớ do nó

chiếm dụng sẽ được giải phóng và sẵn sàng cho tiến trình khác.

Việc lựa chọn một phần trống để cấp phát cho tiến trình có thể

được thực hiện theo nhiều cách khác nhau:

First fit: Tiến hành cấp phát cho tiến trình ngay khi tìm thấy phần

bộ nhớ còn trống đầu tiên có kích thước đủ để đáp ứng yêu cầu tiến trình.

Best fit: Tìm và cấp phát cho tiến trình phần nhớ còn trống có kích

thước nhỏ nhất thoả mãn yêu cầu của tiến trình.

Worst fit: Tìm và cấp phát cho tiến trình vùng nhớ còn trống lớn

nhất thoả mã yêu cầu của tiến trình.

Sự phân mảnh:

Khi bộ nhớ được chia thành các phần cố định và cấp phát cho các

tiến trình, sau khi tiến trình hoàn tất công việc, nó trả lại vùng nhớ đã

được cấp phát. Cách quản lý này có thể dẫn đến hiện tượng phân mảnh

102

Phạm Ngọc Hưng

HỆ ĐIỀU HÀNH

bộ nhớ. Mỗi một tiến trình được cấp phát một phần đã được chia từ trước.

Tiến trình có thể không dùng hết phần bộ nhớ được cấp phát nhưng phần

còn thừa lại không thể dùng cho tiến trình khác. Điều này khiến cho hệ

thống có thể rơi vào tình trạng thiếu bộ nhớ giả tạo (thực sự bố nhớ còn

trống nhưng lại không thể sử dụng và các tiến trình nhận được thống báo

là hết bộ nhớ). Sự thiếu bộ nhớ giải tạo có thể rơi vào một trong hai

trường hợp sau:

- Tất cả vùng nhớ đều chưa dùng, nhưng kích thước của vùng lớn

nhất vẫn nhỏ hơn kích thước bộ nhớ tiến trình yêu cầu. Khi đó tiến trình

sẽ không được cấp phát bộ nhớ và nhận được trả lời là hết bộ nhớ, nhưng

thực sự toàn bộ không gian nhớ đều tự do

- Tổng kích thước các vùng còn thừa của mỗi phần nhớ đã chia cho

các tiến trình lớn hơn kích thước vùng nhớ tiến trình mới yêu cầu nhưng

không thể đáp ứng yêu cầu của tiến trình này vì các vùng nhớ bị phân

mảnh, nằm rải rác nhiều nơi.

Phân chia động: theo cách này, bộ nhớ không được chia sẵn từ

đầu mà chỉ khi tiến trình có yêu cầu thì bộ nhớ mới được chia và cấp cho

tiến trình với kích thước vừa đủ kích thước mà tiến trình yêu cầu.

Phương pháp phân chia động hạn chế được tình trạng các vùng

nhớ còn dư thừa cuối mỗi partition khi tiến trình dùng không hết như

trong phương pháp phân chia tĩnh. Tuy nhiên vấn đề phân mảnh bộ nhớ

vẫn xảy ra. Ta xem xet tình huống sau khi một số tiến trình hoàn tất công

việc và kết thúc. Bộ nhớ do chúng chiếm dụng sẽ được trả lại và các vùng

nhớ này có thể đang nằm xem giữa các vùng nhớ đã được cấp phát và

chưa trả lại. Như vậy hiện tượng phân mảnh đã xuất hiện và trong trường

hợp đó có thể dẫn đến tình huống thiếu bộ nhớ giả tạo như trong phân

chia tĩnh.

9.5. Kỹ thuật phân trang

Phân trang là lược đồ quản lý bộ nhớ cho phép không gian địa chỉ

vật lý của một tiến trình không liền kề nhau.

Phạm Ngọc Hưng

103

Quản lý lưu trữ

Theo truyền thống thì việc phân trang được hỗ trợ bởi phần cứng.

Với các thiết kế gần đây, việc phân trang có thể được thực hiện bằng sự

phối hợp giữa phần cứng và hệ điều hành.

Phương pháp:

Bộ nhớ vật lý được chia thành các khối có kích thước cố định, đều

nhau được gọi là các khung (frame). Bộ nhớ logic cũng được chia thành

các khối có cùng kích thước tương tự được gọi là trang (page).

Khi một tiến trình thực hiện, các trang của nó được nạp vào một số

khung còn trống từ thiết bị lưu trữ ngoài. Thiết bị lưu trữ ngoài cũng chia

thành các khối có cùng kích thước với frame.

Khi một địa chỉ được tạo ra bởi CPU nó chứa hai thành phần thông

tin và số hiệu trang (p) và độ lệch (d). Số hiệu trang được dùng làm chỉ số

truy nhập vào bảng trang (page table). Bảng trang chứa địa chỉ cơ sở của

mỗi trang trong bộ nhớ vật lý. Địa chỉ cơ sở này kết hợp với độ lệch xác

định định địa chỉ vật lý của ô nhớ cần truy nhập. Hình 9.2 thể hiện sự

phân trang với hỗ trợ của phần cứng.

F000...0000

Địa chỉ logic

Địa chỉ vậ

t lý

CPU

p d

f d

F111..1111

p

f

Bộ nhớ vật lý

Bảng trang

Hình 9.2: Phân trang bằng phần cứng

104

Phạm Ngọc Hưng

HỆ ĐIỀU HÀNH

Kích thước của page hay frame được định nghĩa bởi phần cứng.

Thông thường nó là 2ⁿ, thay đổi trong khoảng 512 bytes đến 16 Mb. Nếu

kích thước không gian địa chỉ logic là 2^m, và kích thước một trang là 2ⁿ

đơn vị địa chỉ (bytes hoặc words) thì m-n bit cao xác định chỉ số trang, n

bits thấp lưu địa chỉ độ lệch trong trang.

page number

page offset

p

d

n

m-n

Hình 9.3 (trang sau) minh hoạ cho kỹ thuật phân trang với kích

thước mỗi trang là 4 byte, không gian nhớ logic (logical memory) 16 byte

và không gian nhớ vật lý (physical memory) 32 byte.

Hỗ trợ của phần cứng:

Mỗi hệ điều hành có phương pháp riêng để lưu trữ các bảng trang.

Hầu hết là cấp phát cho mỗi tiến trình một bảng trang. Một con trỏ để trỏ

đến bảng trang được lưu cùng các giá trị của thanh ghi trong bảng điều

khiển tiến trình (PCB).

Sự cài đặt về phần cứng của bảng trang có thể được tiến hành

theo nhiều các khác nhau. Cách đơn giản nhất là bảng trang được cải đặt

như một tập các thanh ghi riêng. Việc sử dụng các thanh ghi để lưu bảng

trang là một giải pháp đơn giản, có tốc độ truy cập cao tuy nhiên chỉ thích

hợp cho các bảng trang có kích thước nhỏ. Trong thực tế, bảng trang

thường có kích thước khá lớn, vì vậy nó thường được lưu trong bộ nhớ và

truy cập đến thông qua PTBR (page-table base register). Để thay đổi địa

chỉ bảng trang chỉ cần thay đổi nội dung thanh ghi này.

Vấn đề xảy ra đối với phương phương pháp lưu bảng trang trong

bộ nhớ đó là thời gian truy cập. Để truy cập đến một vị trí trong bộ nhớ

phải mất 2 lần truy cập bộ nhớ. Lần thứ nhất là truy cập bản trang để xác

định địa chỉ ô nhớ, lần thứ hai truy cập nội dung ô nhớ. Quá trình truy cập

như vậy tiêu tốn thời gian đáng kể.

Phạm Ngọc Hưng

105

Quản lý lưu trữ

Một phương pháp chuẩn để giải quyết vấn đề nêu trên là sử dụng

một bộ đệm phần cứng (hardware cache) có kích thước nhỏ nhưng tốc

độ truy cập cao được gọi là TLB (translation lock-aside buffer). Mỗi đề

mục trong TLB chứa hai thành phần là chỉ số và một giá trị.

Địa Dữ

frame

chỉ liệu

Địa

chỉ

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

Dữ

liệu

a

b

c

d

e

page

0

1

2

3

4

5

6

7

8

0

1

2

3

4

5

6

7

page

frame

0

1

2

3

5

6

2

3

0

f

1

2

3

g

h

i

j

k

m

l

o

p

q

page table

i

j

k

m

l

o

p

q

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

logical momory

a

b

c

d

e

f

g

h

physical memory

Hình 9.3: Minh hoạ sự phân trang

Sự bảo vệ:

Việc bảo vệ bộ nhớ trong môi trường phân trang được thực hiện

bởi các bit bảo vệ được cấp phát tương ứng với mỗi frame. Thông thường

các bit này được lưu trong bảng trang. Một bit này có thể xác định được

106

Phạm Ngọc Hưng

HỆ ĐIỀU HÀNH

trang có thể ghi-đọc hay chỉ đọc. Mỗi khi tham chiếu đến bộ nhớ đều

thông qua bảng trang để xác định một số hiệu trang đúng. Trong khi đó,

địa chỉ vật lý sẽ được tính toán, các bit bảo vệ sẽ được đánh dấu để kiểm

tra sao cho không xảy ra việc ghi vào trang chỉ đọc.

Để tận dụng các đoạn code đã được nạp, tiết kiệm bộ nhớ, các

chương trình có thể chia sẻ cùng một số trang nhớ.

Cấu trúc của bảng trang

Trong các hệ thống máy tính hiện đại hỗ trợ không gian địa chỉ

logic rất lớn (từ 2³²đến 2⁶⁴). Điều này dẫn đến kich thước cần thiết của

bảng trang cũng phải lớn. Ví dụ trong hệ thống với không gian địa chỉ

logic 32 bit. Nếu kích thước của trang là 4 KB (2¹²) thì bảng trang có thể

lên đến một triệu đề mục (2³²/2¹²=2²⁰). Mỗi đề mục tương ứng 4 byte thì

mỗi tiến trình cần đến 4 MB để chứa một bảng trang. Để có thể cấp phát

bộ nhớ một cách liên tục, thuận tiện cho việc quản lý bảng trang, ta có

thể chia bảng trang thành các phần nhỏ hơn và đợc quản lý bởi một bảng

phân trang ngoài (outer-page table) hay một thư mục trang (page

directory). Một địa chỉ tuyến tính 32 bit bây giờ được chia thành 2 phần:

phần thứ nhất là số hiệu trang (20 bit), phần thứ hai là độ lệch trong

trang (12 bit). Trong đó số hiệu trang lại được chia thành hai phần: 10 bit

đầu trỏ đến một đề mục trong bảng phân trang ngoài (hay thư mục

trang), 10 bit tiếp là chỉ số của trang trong bảng trang xác định đợc từ thư

mục trang. Cấu trúc của địa chỉ tuyến tính này đợc thể hiện ở hình sau:

page number

p1

10

page offset

p2

10

d

12

Ở hình trên, p1 trỏ đến một đề mục trong bảng phân trang ngoài,

p2 là độ lệch của trang trong bảng trang ngoài.

Quá trình để chuyển đổi một địa chỉ tuyến tính thành địa chỉ vật lý

được thực hiện qua các bước thể hiện ở hình 9.4.

Phạm Ngọc Hưng

107

Quản lý lưu trữ

logic address

p1 p2

d

p1

p2

outer-table

d

page

Hình 9.4: Quá trình chuyển đổi địa chỉ hai mức, kiến trúc phân trang 32 bit

9.5. Phân đoạn

Phương pháp cơ bản:

Phân đoạn là một lược đồ quản lý bộ nhớ mà không gian nhớ logic

được chia thành các đoạn. Mỗi đoạn có một tên và độ dài. Địa chỉ được

xác định bao gồm cả tên đoạn và độ lệch (offset) trong đoạn. Một chương

trình người dùng khi được dịch thành cũng bao gồm nhiều đoạn, mỗi

đoạn chứa một loại dữ liệu mang ý nghĩa riêng. Ví dụ một chương trình

pascal có thể gồm các đoạn sau:

- Các biến toàn cục

- Ngăn xếp gọi chương trình con, truyền các tham số và địa chỉ trở

về

- Đoạn mã chứa mã chính và các chương tình con

- Các biến cục bộ của mỗi chương trình con

108

Phạm Ngọc Hưng

HỆ ĐIỀU HÀNH

Phân đoạn bằng phần cứng:

Mặc dù người dùng có thể tham chiếu đến các đối tượng thông qua

địa chỉ gồm 2 thành phần segment và offset, địa chỉ vật lý vẫn cần để truy

cập vào không gian nhớ vật lý. Địa chỉ vật lý chỉ là địa chỉ một chiều, gồm

một chuỗi các byte. Vì vậy chúng ta phải cạt đặt một ánh xạ các địa chỉ

hai chiều do người dùng tạo ra vào địa chỉ một chiều trong không gian địa

chỉ vật lý, việc này được thực hiện bởi bảng đoạn (segment table). Mỗi đề

mục (entry) trong bảng đoạn chứa một địa chỉ cơ sở của đoạn và giới hạn

đoạn. Địa chỉ cơ sở đoạn là địa chỉ vật lý bắt đầu đoạn trong bộ nhớ vật

lý. Giới hạn đoạn chính là độ dài của đoạn.

0

seg0

200

300

Subroutine

stack

seg0

segment limit base

seg1

seg2

0

1

2

3

100 200

200 1200

250 700

300 400

400

symbol

table

seg3

seg2

page table

700

seg3

main

proram

950

1200

1400

logical address space

seg1

physical memory

Hình 9.5: Minh hoạ sự phân đoạn

Phạm Ngọc Hưng

109

Quản lý lưu trữ

Sự phân mảnh:

Phương pháp quản lý bộ nhớ theo kiểu phân đoạn có thể làm xảy

ra hiện tượng phân mảnh ngoài. Phân mảnh ngoài là hiện tượng các vùng

nhớ còn trống và các vùng nhớ đã cấp phát nằm xen kẽ nhau. Phân mảnh

trong là hiện tượng vùng nhớ đã cấp phát còn trống một phần. Sự phân

mảnh dẫn đến hiện tượng thiếu bộ nhớ giả tạo (không thể đáp ứng được

yêu cầu các chương trình mặc dù bộ nhớ còn trống thực sự). Thiếu bộ

nhớ giả tạo có thể xảy ra ở hai tình huống sau:

-

Toàn bộ bộ nhớ còn trống nhưng các đoạn có kích thước nhỏ,

không đủ đáp đáp ứng yêu cầu của bất kỳ chương trình nào (do

phân mảnh ngoài).

-

Các vùng nhớ đã được cấp phát nhưng sử dụng không hết, tổng

các vùng trống còn lại đủ để dáp ứng yêu cầu chương trình mới

nhưng do nằm rải rác trong các đoạn đã cấp phát nên không

thể cấp phát cho chương trình mới (do phân mảnh trong).

9.6. Kết hợp phân trang-phân đoạn

Cả hai kỹ thuật phân trang và phân đoạn đều có nhưng ưu điểm và

nhược điểm riêng. Trong thực tế cả hai kỹ thuật này đều được áp dụng

trong các bộ vi xử lý đang được sử dụng phổ biến hiện nay.

Hệ điều hành OS/2 cảu IBM phiên bản 32 bit chạy trên kiến trúc

Intel 386 sử dụng cả kỹ thuật phân đoạn và phân trang để quản lý bộ

nhớ. Số lượng tối đa các đoạn cho mỗi tiến trình là 16 và kích thước mỗi

đoạn có thể lên đến 4 Gb. Kích thước trang là 4 Kb.

Trong kỹ thuật quản lý phối hợp phân đoạn và phân trang, không

gian địa chỉ logic của chương trình được chia thành 2 phần. Phần thứ nhất

bao gồm các đoạn 8KB dành riêng cho mỗi tiến trình. Phần thứ hai bao

gồm các đoạn 8KB được chia sẻ cho các tiến trình. Thông tin về phần thứ

nhất được chứa trong bảng LDT (Local Descriptor Table), thông tin về

đoạn thứ hai chứa trong bảng GDT (Global Descriptor Table). Mỗi đề mục

trong LDT và GDL có kích thước 8 bytes chứa thông tin chi tiết về mỗi

đoạn bao gồm địa chỉ cơ sở đoạn, độ lớn mỗi đoạn.

110

Phạm Ngọc Hưng

HỆ ĐIỀU HÀNH

Địa chỉ logic là một cặp bộ chọn (selector) và độ lệch (offset). Bộ

chọn là một số có độ dài 16 bit, được chia thành 3 phần s, g, p:

s

g

1

p

2

13

Trong đó s (13 bit) là chỉ số đoạn, g (1 bit) cho biết đoạn trong

LDT hay GDT và p (2 bit) được dùng cho mục đích bảo vệ.

Độ lệch (offset) là một số 32 bit xác định vị trí của byte trong đoạn.

Máy có 6 thanh ghi cho phép 6 đoạn có thể được đánh định chỉ bởi

một tiến trình bất cứ lúc nào. Nó có 6 thanh ghi chương trình nhỏ 8 byte

chứa các mô tả tương ứng trong LDT và GDT. Bộ nhớ cache này cho phép

386 bỏ qua việc đọc bộ mô tả từ bộ nhớ mỗi khi tham chiếu đến bộ nhớ.

Địa chỉ vật lý của 386 là một số có độ dài 32 bit được định dạng

như sau: Thanh ghi đoạn trỏ đến một đề mục trong LDT hay GDT. Thông

tin về địa chỉ cơ sở đoạn, giới hạn đoạn được dùng để tạo ra một địa chỉ

tuyến tính. Trước tiên, giới hạn đoạn được sử dụng để kiểm giới hạn

được phép của địa chỉ truy cập. Nếu địa chỉ truy cập nằm ngoài giới hạn

thì một lỗi truy cập bộ nhớ sẽ phát sinh và yêu cầu truy cập sẽ bị từ chối.

Nếu địa chỉ nằm trong giới hạn cho phép thì địa chỉ độ lệch (offset) sẽ

được cộng với địa chỉ cơ sở đoạn tạo ra địa chỉ tuyến tính. Địa chỉ này sau

đó sẽ được chuyển thành địa chỉ vật lý.

Như đã đề cập ở phần đầu, mỗi đoạn lại được chia thành các trang

(áp dụng kỹ thuật phân trang cho từng đoạn), mỗi trang có kích thước

4KB. Mỗi bảng trang có thể chứa đến 1 triệu đề mục vì mỗi đề mục chỉ

chứa có 4 byte. Mỗi tiến trình vì vậy có thể phải cần đến 4MB bộ nhớ vật

lý để chứa một bảng trang. Và rõ rànglà chúng ta mong muốn rằng bảng

trang sẽ được cấp phát bộ nhớ một cách liên tục. Vấn đề này được đáp

ứng ở 386 bằng cách sử dụng lược đồ phân trang 2 cấp. Địa chỉ tuyến

tính được chia thành các phần trong đó có một số hiệu trang với độ dài 20

bit và độ lệch trong trang với độ dài 12 bit. Bảng trang lại được quản lý

theo thư mục vì vậy mà số hiệu trang 20 bit lại đợc chia thành hai phần.

Phạm Ngọc Hưng

111

Quản lý lưu trữ

Trong đó, phần thứ nhất 10 bit trỏ đến thư mục trang, 10 bit tiếp theo trỏ

đến một đề mục trong bảng trang.

p1

10

p2

10

d

12

Lược đồ chuyển đổi địa chỉ cũng tương tự lược đồ chuyển đổi địa

chỉ đã giới hiệu hình 9.4. Quá trình chuyển đổi địa chỉ của 386 áp dụng kỹ

thuật kết hợp phân đoạn với phân trang có thể được mô tả chi tiết ở hình

9.6 dưới đây:

Selector

offset

descriptor table

+

segment descriptor

Giáo trình Hệ điều hành - Chương 3: Quản lý lưu trữ - Phạm Ngọc Hưng