Khoa Công Nghệ Thông Tin & Truyền Thông
Đại học Cần Thơ
Giảng viên: Hà Duy An


1.Tổng quan
2.Hoán vị (Swapping)
3.Cấp phát bộ nhớ liên tục
4.Phân đoạn (Segmentation)
5.Phân trang (Paging)
6.Cấu trúc bảng trang

10/28/2013

2

Chương 7: Main Memory



• Chương trình phải được mang vào bộ nhớ và được đặt vào một
tiến trình để thực thi.
• Bộ nhớ chính và các thanh ghi là hai thiết bị lưu trữ mà CPU
có thể truy cập trực tiếp
• Đơn vị bộ nhớ (memory unit) chỉ nhìn thấy một luồng địa chỉ
+ yêu cầu đọc, hay địa chỉ + dữ liệu và u cầu ghi
• Các thanh ghi có thể được truy cập chỉ với một chu kỳ CPU
(hay ít hơn)
• Truy cập bộ nhớ chính cần nhiều chu kỳ CPU hơn
• Cache nằm ở giữa bộ nhớ chính và các thanh ghi
• Các thao tác trên bộ nhớ cần được đảm bảo chính xác

10/28/2013

4

Chương 7: Main Memory


• Một cặp thanh ghi nền
(base) và giới hạn (limit)
xác định khơng gian địa chỉ
của tiến trình trên bộ nhớ
• CPU phải kiểm tra tất cả
truy cập bộ nhớ từ không
gian người dùng nằm trong
khoảng giới hạn của thanh
ghi nền và giới hạn

10/28/2013

5

Chương 7: Main Memory


10/28/2013

6

Chương 7: Main Memory



• Tập hợp các chương trình trên đĩa, sẵn sàng được mang vào bộ
nhớ để thực thi hình thành một hàng đợi nhập (input queue)
o Nếu khơng có sự hỗ trợ nào, chương trình phải được nạp vào từ
địa chỉ: 0000

• Hầu hết các hệ thống máy tính cho phép các tiến trình có thể
nằm ở bất kỳ phần nào trong bộ nhớ vật lý
• Các địa chỉ ở trong các dạng thức khác nhau tại mỗi giai đoạn
khác nhau của chương trình:
o Các địa chỉ tượng trưng trong chương trình nguồn.
o Các địa chỉ tái định vị khi biên dịch.
o Các địa chỉ tuyệt đối khi nạp (loading) hoặc nối kết (linking).
=> Mỗi giai đoạn, việc gắng kết sẽ ánh xạ từ một không gian địa chỉ này sang một
không gian địa chỉ khác.

10/28/2013

7

Chương 7: Main Memory


• Việc gắn kết địa chỉ (address binding) của các chỉ thị và dữ liệu vào
địa chỉ bộ nhớ có thể diễn ra tại 3 giai đoạn khác nhau:
o Thời điểm biên dịch (compile time): Nếu vị trí vùng nhớ được biết
trước, thì có thể sinh ra mã lệnh tuyệt đối (absolute code); tuy nhiên
chương trình phải được biên dịch lại nếu vị trí bắt đầu của vùng nhớ
thay đổi.
o Thời điểm nạp (load time): trình biên dịch phải sinh ra mã lệnh có thể

tái định vị (relocatable code) nếu khơng thể biết được vị trí vùng nhớ
tại thời điểm biên dịch. Trong trường hợp này việc gắng kết bị trì hỗn
cho đến thời điểm nạp. Chương trình phải được nạp lại nếu vị trí bắt
đầu của vùng nhớ thay đổi
o Thời điểm thực thi (execution time): Việc gắn địa chỉ bị trì hỗn cho
đến thời điểm thực thi nếu tiến trình có thể phải di chuyển được từ phân
đoạn bộ nhớ (segment) này đến phân đoạn bộ nhớ khác khi thực thi.
Cần thêm sự hỗ trợ của phần cứng để ánh xạ địa chỉ(ví dụ như các
thanh ghi cơ sở (base) và giới hạn (limit)).
10/28/2013

8

Chương 7: Main Memory


10/28/2013

9

Chương 7: Main Memory


• Cơ chế cho phép không gian địa chỉ luận lý tách biệt khỏi
khơng gian địa chỉ vật lý, chính là trọng tâm của cơ chế quản
lý bộ nhớ.
o Địa chỉ luận lý (logical address): được sinh ra bởi CPU, cũng
được xem là địa chỉ ảo (virtual address).
o Địa chỉ vật lý (physical address): địa chỉ được nhìn thấy bởi bộ
quản lý bộ nhớ.


• Địa chỉ luận lý và vật lý là như nhau trong sơ đồ gắn kết địa
chỉ tại thời điểm biên dịch và nạp chương trình.
• Địa chỉ luận lý và địa chỉ vật lý sẽ khác nhau trong sơ đồ gắn
kết địa chỉ tại thời điểm thực thi.

10/28/2013

10

Chương 7: Main Memory


• Bộ quản lý bộ nhớ (Memory management Unit – MMU): thiết
bị phần cứng làm nhiệm vụ ánh xạ địa chỉ ảo sang địa chỉ vật
lý => nhiều phương thức có thể được sử dụng
• Một sơ đồ ánh xạ đơn giản là dùng thanh ghi tái định vị
(relocation/base register): giá trị của thanh ghi tái định vị được
cộng vào bất cứ địa chỉ nào sinh ra bởi tiến trình người dùng
vào thời điểm nó được gửi đến bộ nhớ
o MS-DOS trên Intel 80x86 sử dụng 4 thanh ghi tái định vị

• Chương trình người dùng thực thi với các địa chỉ luận lý; nó
khơng bao giờ thấy được địa chỉ vật lý thật sự

10/28/2013

11

Chương 7: Main Memory



10/28/2013

12

Chương 7: Main Memory


•
•

Nạp tĩnh (static loading): tồn bộ chương trình và dữ liệu được nạp một lần
vào bộ nhớ vật lý cho tiến trình để chạy.
Nạp động (dynamic loading): thường trình (routine) chỉ được nạp khi nó được
gọi.
o Tất cả các thường trình được lưu trên đĩa theo định dạng nạp có thể tái định vị.
o Bộ nạp liên kết tái định vị (relocatable linking loader) được dùng để nạp các thường
trình mong muốn.

•
•
•

Điều này làm tăng hiệu năng sử dụng bộ nhớ; các thường trình khơng được sử
dụng sẽ khơng bao giờ được nạp.
Hữu ích khi một số lượng lớn các mã lệnh được cần để giải quyết các tình
huống khơng thường xuất hiện.
Không cần sự hỗ trợ đặc biệt của hệ điều hành:
o Nạp động được cài đặt thông qua cách thiết kế chương trình.

o HĐH có thể hỗ trợ bằng cách cung cấp các thư viện để cài đặt nạp động

10/28/2013

13

Chương 7: Main Memory


• Liên kết tĩnh (static linking): các thư viện hệ thống và mã chương
trình được kết hợp với nhau bởi bộ nạp (loader) thành một chương
trình nhị phân có thể thực thi (executable image).
• Liên kết động (dynamic linking): việc liên kết bị hỗn lại đến tận
thời điểm thực thi.
• Một đoạn mã lệnh nhỏ, stub, được sử dụng để định vị thường trình
thư viện thường trú (memory-resident library routine) tương ứng
hay cách thức nạp thư viện cần thiết vào nếu thường trình cần tham
chiếu chưa được nạp vào bộ nhớ.
• Stub thay thế chính nó bằng địa chỉ của thường trình và thực thi
thường trình đó
• Hệ điều hành cần phải kiểm tra thường trình có nằm trong khơng
gian địa chỉ của các tiến trình hay khơng.
•

o Nếu khơng, thêm nó vào
Liên kết động hữu ích đặc biệt cho các thư viện chia sẻ (shared libraries).

10/28/2013

14


Chương 7: Main Memory


• Một tiến trình có thể được hốn vị tạm thời ra khỏi bộ nhớ, đến
vùng lưu trữ phụ (backing store) và rồi lại được mang trở lại bộ nhớ
để tiếp tục thực thi.
• Vùng lưu trữ phụ: đĩa tốc độ cao, đủ lớn để sao chép tất cả ảnh bộ
nhớ (memory image) cho tất cả người dùng; phải cho phép truy cập
trực tiếp đến các ảnh này.
• Hàng đợi sẳn sàng bao gồm tất cả các tiến trình sẳn sàng để thực thi
nằm trong bộ nhớ và nằm trong vùng lưu trữ phụ
• Nếu tiến trình kế tiếp được cấp CPU khơng nằm trong bộ nhớ =>
cần phải hốn vị một tiến trình ra, và mang tiến trình cần thiết vào
bộ nhớ
• Thời gian chuyển ngữ cảnh trường hợp này là rất cao
• Giả sử tiến trình 100MB hốn vị ra đĩa với tốc độ 50MB/sec
o Thời gian hoán vị ra: 2000ms
o Cộng thời gian hoán vị vào một tiến trình có cùng kích thước
o Tổng thời gian chuyển đổi ngữ cảnh: 4000ms
10/28/2013

15

Chương 7: Main Memory


10/28/2013

16


Chương 7: Main Memory


• Phần chính của thời gian hốn vị là thời gian chuyển dữ liệu; tổng
thời gian chuyển dữ liệu tỷ lệ thuận với lượng bộ nhớ được hoán vị.
o Giảm kích thước dữ liệu cần hốn vị – nếu biết chính xác dung lượng
bộ nhớ thật sự cần dùng

• Các ràng buộc khác:
o Có cần hốn vị tiến trình vào chính xác vùng nhớ trước đó hay khơng?
o Khi tiến trình đang thực hiện tao tác I/O

• Phiên bản chuẩn của hốn vị khơng được dùng trong HĐH hiện đại.
Tuy nhiên, các phiên bản cải tiến của kỹ thuật này được dùng trong
nhiểu hệ thống (như: Unix, Linux, và Windows):
o Hốn vị thơng thường được vơ hiệu hóa
o Chỉ bắt đầu khi số lượng bộ nhớ đã cấp phát lớn hơn một ngưỡng nào
đó
10/28/2013

17

Chương 7: Main Memory


18
10/28/2013

Chương 7: Main Memory



• Là một trong các phương pháp cấp phát bộ nhớ được dùng đầu tiên
• Bộ nhớ chính thường được chia làm 2 phần:
o Phần thường trú của hệ điều hành: thường được tổ chức trong vùng nhớ
thấp với các vector ngắt.
o Các tiến trình người dùng được tổ chức trong vùng nhớ cao;
 mỗi tiến trình được cấp phát duy nhất một vùng nhớ liên tục trong bộ
nhớ

• Sơ đồ thanh ghi tái định vị được sử dụng để bảo vệ các tiến trình
người dùng với nhau, và để chống việc thay đổi mã lệnh và dữ liệu
của hệ điều hành:
o Thanh ghi tái định vị (relocation register) chứa giá trị của địa chỉ vật lý
nhỏ nhất
o Thanh ghi giới hạn (limit register) chỉ ra phạm vi cho phép của các địa
chỉ luận lý - mỗi địa chỉ luận lý phải nhỏ hơn giá trị trong thanh ghi
giới hạn.
o MMU ánh xạ động địa chỉ luận lý > vật lý
10/28/2013

19

Chương 7: Main Memory


10/28/2013

20


Chương 7: Main Memory


•

Cấp phát đa phân khu:
o Mức độ đa chương được xác định bởi số lượng phân khu
o Kích thước phân khu thay đổi tùy thuộc vào nhu cầu của tiến trình
o Lỗ hổng (hole): các lỗ hổng với kích thước khác nhau nằm rải rác trong bộ nhớ.
o Khi một tiến trình xuất hiện, nó được cấp cho lỗ hổng đủ chứa nó.
o Khi tiến trình kết thúc vùng nhớ tương ứng được giải phóng, và được kết hợp với lỗ
hổng lân cận (nếu có)
o Hệ điều hành duy trì thông tin về:
a) Những phân khu đã được cấp
b) Các lỗ hổng
OS

OS

OS

OS

process 5

process 5

process 5

process 5


process 9

process 9

process 8
process 2
10/28/2013

process 10
process 2

process 2
21

process 2
Chương 7: Main Memory


Làm thế nào để thỏa mãn yêu cầu bộ nhớ có kích thước n từ số các lỗ
hổng hiện tại?
• First-fit: cấp lỗ hổng đầu tiên đủ lớn.
• Best-fit: cấp lỗ hổng nhỏ nhất nhưng đủ lớn; phải tìm kiếm toàn bộ
danh sách các lỗ hổng, trừ khi danh sách này được sắp thứ tự theo
kích thước lỗ hổng. Chiến lược này sinh ra lỗ hổng cịn lại nhỏ nhất.
• Worst-fit: cấp lỗ hổng lớn nhất; cũng phải tìm cho ra lỗ hổng có
kích thước lớn nhất trong tồn bộ danh sách. Chiến lược này sinh ra
lỗ hổng còn lại lớn nhất
First-fit và best-fit thì tốt hơn worst-fit khi ta quan tâm đến tốc độ và
hiệu quả sử dụng bộ nhớ. Hiệu quả sử dụng bộ nhớ là như nhau với

First-fit và best-fit, tuy nhiên first-fit nhìn chung nhanh hơn.

10/28/2013

22

Chương 7: Main Memory


• Phân mảnh ngồi: tổng khơng gian bộ nhớ cịn đủ để thỏa
mãn yêu cầu nhưng chúng không nằm liền nhau.
• Phân mảnh trong: phần bộ nhớ cấp cho tiến trình lớn hơn bộ
nhớ u cầu một ít. Phần sai khác này nằm bên trong của phân
khu và không được sử dụng.
• Khử phân mảnh ngồi bằng cách cơ đặc bộ nhớ
o Sắp xếp lại nội dung bộ nhớ để gom các lỗ hổng lại thành một lỗ
hổng duy nhất lớn hơn.
o Sự khử phân mảnh chỉ có thể làm được khi việc tái định vị là
động

• Cách tiếp cận khác để khử phân mảnh ngoài là cho phép vùng
nhớ của tiến trình nằm khơng liên tục trong bộ nhớ => cấp
phát không liên tục.
10/28/2013

23

Chương 7: Main Memory




• Sơ đồ quản lý bộ nhớ hỗ trợ việc phân chia bộ nhớ theo góc độ
người dùng.
• Một chương trình bao gồm một tập hợp các đoạn (segment).
o Một đoạn là một đơn vị luận lý, ví dụ như:

main program,
procedure,
function,
method,
object,
local variables, global variables,
common block,
stack,
symbol table
arrays
10/28/2013

25

Chương 7: Main Memory