1

TỔNG LIÊN ĐOÀN LAO ĐỘNG VIỆT NAM
TRƯỜNG ĐẠI HỌC TÔN ĐỨC THẮNG
KHOA CÔNG NGHỆ THÔNG TIN

BÀI TẬP LỚN / ĐỒ ÁN CUỐI KÌ MÔN
TỔ CHỨC MÁY TÍNH

Virtual Memory

Người hướng dẫn: TS Mai Ngọc Thắng
Người thực hiện: Thái Trung Tín - 51503315
Lớp : 15050301
Khóa : 19

THÀNH PHỐ HỒ CHÍ MINH, NĂM 2016


2

TỔNG LIÊN ĐOÀN LAO ĐỘNG VIỆT NAM
TRƯỜNG ĐẠI HỌC TÔN ĐỨC THẮNG
KHOA CÔNG NGHỆ THÔNG TIN

BÀI TẬP LỚN / ĐỒ ÁN CUỐI KÌ MÔN
TỔ CHỨC MÁY TÍNH

Virtual Memory

Người hướng dẫn: TS Mai Ngọc Thắng

Người thực hiện: Thái Trung Tín - 51503315
Lớp : 15050301
Khóa : 19

THÀNH PHỐ HỒ CHÍ MINH, NĂM 2016


3

LỜI CẢM ƠN
Trong suốt quá trình nghiên cứu về đề tài Bộ nhớ ảo
(Virtual Memory), em đã gặp rất nhiều khó khăn từ cách tiếp
cận và trình bày ý tưởng nhưng nhờ có TS. Mai Ngọc Thắng
- Khoa Công nghệ thông tiin - Trường đại học Tôn Đức
Thắng - đã tận tình hướng dẫn đã giúp em nhìn nhận vấn đề
cụ thể, tiếp cận đề tài dễ dàng.
Em xin chân thành cảm ơn thầy vì những lời chỉ bảo
vô cùng quý báu của thầy đã giúp em có những thu hoạch
quý giá để hoàn thành quá trình nghiên cứu này.
Bài thu hoạch này được thực hiện trong khoảng thời
gian gần 3 tuần. Bước đầu đi vào thực tế, tìm hiểu về lĩnh
vực sáng tạo trong nghiên cứu khoa học, kiến thức của em
còn hạn chế và còn nhiều bỡ ngỡ. Do vậy, không tránh khỏi
những thiếu sót là điều chắc chắn, em rất mong nhận được
những ý kiến đóng góp quý báu của quý Thầy Cô và các bạn
học cùng lớp để kiến thức của em trong lĩnh vực này được
hoàn thiện hơn.
Một lần nữa em xin chân thành cảm ơn.

TP.Hồ Chí Minh,ngày 20 tháng 04 năm 2016

Thái Trung Tín


4

ĐỒ ÁN ĐƯỢC HOÀN THÀNH
TẠI TRƯỜNG ĐẠI HỌC TÔN ĐỨC
THẮNG
Tôi xin cam đoan đây là sản phẩm đồ án của
riêng tôi và được sự hướng dẫn của TS Mai Ngọc
Thắng. Các nội dung nghiên cứu, kết quả trong đề
tài này là trung thực và chưa công bố dưới bất kỳ
hình thức nào trước đây. Những số liệu trong các
bảng biểu phục vụ cho việc phân tích, nhận xét,
đánh giá được chính tác giả thu thập từ các nguồn
khác nhau có ghi rõ trong phần tài liệu tham khảo.
Ngoài ra, trong đồ án còn sử dụng một số
nhận xét, đánh giá cũng như số liệu của các tác giả
khác, cơ quan tổ chức khác đều có trích dẫn và chú
thích nguồn gốc.
Nếu phát hiện có bất kỳ sự gian lận
nào tôi xin hoàn toàn chịu trách nhiệm về
nội dung đồ án của mình. Trường đại học Tôn
Đức Thắng không liên quan đến những vi phạm tác
quyền, bản quyền do tôi gây ra trong quá trình thực
hiện (nếu có).
TP.Hồ Chí Minh,ngày 20 tháng 04 năm 2016
Tác giả
Thái Trung Tín



5

PHẦN XÁC NHẬN VÀ ĐÁNH GIÁ
CỦA GIẢNG VIÊN
Phần xác nhận của giáo viên hướng
dẫn

TP.Hồ Chí Minh,ngày 20 tháng 04 năm 2016
Thái Trung Tín
Phần đánh giá của giáo viên chấm
bài

TP.Hồ Chí Minh,ngày 20 tháng 04 năm 2016
Thái Trung Tín


6

TÓM TẮT
Để nghiên cứu vè sự quan trọng của bộ nhớ ảo, một
số vấn đề đã đặt ra để tiếp cận vấn đề. Tại sao chúng
ta có thể chạy một chương trình nặng hơn RAM của
máy tính chúng ta hiện có? Tại sao có những lúc truy
xuất dữ liệu nhanh chậm khác nhau? Cách xử lý địa
chỉ trong bộ nhớ ảo? Tại sao các hệ điều hành đều lập
trình bộ nhớ ảo trên các sản phẩm của mình? Một số
kết quả thu được là bộ nhớ ảo là trung gian giữa địa
chỉ ảo và địa chỉ vật lý, nó sẽ dịch từ địa chỉ ảo sang
địa chỉ vật lý, tốc độ sẽ phụ thuộc vào vi trí của dữ

liệu có trên bộ nhớ chính hay chưa và còn phụ thuộc
vào một số tính năng như Memory Management Unit
hay Translation Lookaside Buffer, ngoài ra chúng ta
còn biết thêm về công thức và cơ chế để biên dịch một
địa chỉ ảo. Bộ nhớ ảo thực chất là "double RAM", nếu
ta có bao nhiêu RAM thực thì sẽ có bấy nhiêu RAM
ảo (trên hệ điều hành Windows).


7

MỤC LỤC

LỜI CẢM ƠN........................................................................................3

PHẦN XÁC NHẬN VÀ ĐÁNH GIÁ CỦA GIẢNG VIÊN......................5

TÓM TẮT.............................................................................................6

MỤC LỤC.............................................................................................7

DANH MỤC CÁC BẢNG BIỂU, HÌNH VẼ..........................................11

CHƯƠNG 1 - MỞ ĐẦU.........................................................................13


8

0.1


Bộ nhớ ảo ..........................................................13

0.1.1

Định nghĩa.......................................................................13

0.1.2

Đặc điểm..........................................................................13

0.1.3

Mục tiêu thiết lập bộ nhớ ảo.............................................14

0.1.4

Phân loại..........................................................................14

0.1.5

Cơ chế bộ nhớ ảo..............................................................14

0.2

Lỗi trang ...........................................................16

0.3

Bảng trang........................................................18


0.3.1

Bảng trang.....................................................................18

0.3.2

Giám sát trang...............................................................19

0.3.3

Trang ghim....................................................................20

0.3.4

Thrashing.......................................................................20

0.3.5 Truyền dịch địa chỉ trong bảng trang : Thay thế
và ghi.........................................................................................22

0.4 Translation Lookaside Buffer(TLB)-Bộ đệm
chuyển đổi..................................................................24
0.4.1

Định nghĩa .....................................................................24

0.4.2

Cơ chế của TLB..............................................................24

0.4.3


Lỗi TLB.........................................................................25

0.4.4

Xử lý lỗi TLB.................................................................25

0.4.5

Xử lý lỗi trang................................................................26

0.4.6

Sự tương tác giữa TLB và Cache.....................................26

0.5

Bảo vệ bộ nhớ (Memory Protection).................28

CHƯƠNG 2. TỔNG QUAN...........................................................29


0.6. CÔNG THỨC....................................................................29

9

0.6

Công thức....................................................................29


0.7

Vấn đề đặt ra...............................................................29

0.8

Tài liệu tham khảo.......................................................30


10

DANH MỤC KÝ HIỆU VÀ CHỮ VIẾT TẮT
CÁC KÝ HIỆU
CÁC CHỮ VIẾT TẮT

• TLB : Translation Lookaside Buffer (Bộ đệm chuyển
đổi)
• PTE : Page Table Entry
• MMU : Memory Management Unit (đơn vị quản
lý vùng nhớ)
• LRU: Least-recently using
• OS: Operating System


0.8. TÀI LIỆU THAM KHẢO.......................................................30

11

DANH MỤC CÁC BẢNG BIỂU HÌNH VẼ
DANH MỤC HÌNH

Hình 1.1: Bộ nhớ ảo
Hình 1.2: Cơ chế bộ nhớ ảo
Hình 1.3: Dịch địa chỉ
Hình 1.4 TLB và Cache trong cơ chế dịch địa chỉ
Hình 1.5: Sơ đồ truy xuất khi gặp trang lỗi
Hình 1.6: MMU trong bộ nhớ ảo
Hình 1.7: Bảng trang với một số trang không nằm trong
bộ nhớ
Hình 1.8: Thrashing 1
Hình 1.9: Thrashing 2
Hình 1.10: Truyền dịch trong bảng trang
Hình 1.11: Sơ đồ hoạt động TLB
Hình 1.12: Using the TLB
Hình 1.13: Xử lý lỗi trang
Hình 1.14: TLB và Cache


12


Chương 1

MỞ ĐẦU
1.1

Bộ nhớ ảo

1.1.1

Định nghĩa


Bộ nhớ ảo (Virtual Memory) là bộ nhớ hệ thống được
tạo ra từ hệ điều hành và nằm trong ổ cứng. Nó sẽ liên kết địa
chỉ ô nhớ được dùng bởi phần mềm, gọi là địa chỉ ảo, tới địa
chỉ vật lý trong bộ nhớ máy tính.

Hình 1.1: Bộ nhớ ảo

1.1.2

Đặc điểm

-"Sử dụng bộ nhớ chính như một bộ đệm cho bộ nhớ thứ cấp"
trích Mr Aaron Tan Tuck Choy, Slides School of Computing, National University of Singapore
13


14

CHƯƠNG 1. MỞ ĐẦU

• An toàn trong việc chia sẻ thông tin và đạt hiệu quả

cao giữ bộ nhớ và các chương trình.
• Giúp máy tính chạy nhanh giống như bộ đệm.
• Cho phép chạy các chương trình có kích thước lớn hơn
bộ nhớ vậy lý nhờ việc tách biệt bộ nhớ ảo và bộ nhớ
vật lý.
• Đơn giản hóa việc nạp chương trình


-Trong thời gian chạy, địa chỉ ảo được dịch thành địa chỉ vật lý.
-Mỗi chương trình sử dụng một không gian địa chỉ riêng biệt
– không gian địa chỉ ảo.
-Không gian địa chỉ ảo của chương trình được chia thành các
trang (kích thước cố định) hoặc các đoạn (kích thước thay
đổi).
1.1.3

Phân loại

1. Bộ nhớ ảo phân trang
2. Bộ nhớ ảo phân đoạn
3. Bộ nhớ ảo dạng phân đoạn có phân trang
1.1.4

Mục tiêu thiết lập bộ nhớ ảo

-Không cần quan tâm đến bộ nhớ vậy lý.
-"Mở rộng" dung lượng bộ nhớ vật lý.
-Tận dụng bộ nhớ phụ trong việc xử lý tiến trình.
1.1.5

Cơ chế của bộ nhớ ảo

Không gian bộ nhớ riêng sẽ chia nhỏ thành các trang
nhớ có kích thước là 4KB (tương ứng địa chỉ offset từ 0 ->
4095) ,mỗi trang nhớ sẽ được ánh xạ nhưng không nhất thiết
toàn bộ chúng phải nằm trên trang nhớ.
Khi truy xuất nếu trang đã nằm trong bộ nhớ chính
thì địa chỉ bộ nhớ ảo sẽ được ánh xạ lên bộ nhớ chính còn nếu

không thì sẽ sinh ra hiện tượng lỗi trang , khối MMU sẽ báo


1.1. BỘ NHỚ ẢO

15

cho hệ điều hành tiến hành nạp trang từ bộ nhớ ngoài và tiến
hành thực thi lại lệnh trước đó.

Hình 1.2: Cơ chế bộ nhớ ảo


16

CHƯƠNG 1. MỞ ĐẦU

Hình 1.3: Dịch địa chỉ. Nguồn: Mr.Aaron Tan Tuck Choy, slides School of Computing, National University of Singapore

1.2

Lỗi trang

Truy xuất đến một trang được đánh dấu bất hợp lệ
sẽ làm phát sinh một lỗi trang . Khi dò tìm trong bảng trang
để lấy các thông tin cần thiết cho việc chuyển đổi địa chỉ, nếu
nhận thấy trang đang được yêu cầu truy xuất là bất hợp lệ, cơ
chế phần cứng sẽ phát sinh một ngắt để báo cho hệ điều hành.
Hệ điều hành sẽ xử lý lỗi trang như sau:
-B1: Kiểm tra truy xuất đến bộ nhớ là hợp lệ hay bất hợp lệ.



1.2. LỖI TRANG

17

Hình 1.4: TLB và Cache trong cơ chế dịch địa chỉ

• Nếu truy xuất bất hợp lệ: kết thúc tiến trình.
• Ngược lại: đến bước 2.

-B2: Tìm vị trí chứa trang muốn truy xuất trên đĩa.
-B3: Tìm một khung trang trống trong bộ nhớ chính:
• Nếu tìm thấy: đến bước 4.
• Nếu không còn khung trang trống, chọn một khung

trang “nạn nhân” và chuyển trang “nạn nhân” ra bộ
nhớ phụ (lưu nội dung của trang đang chiếm giữ khung
trang này lên đĩa), cập nhật bảng trang tương ứng rồi
đến bước 4.
-B4: Chuyển trang muốn truy xuất từ bộ nhớ phụ vào bộ nhớ
chính: nạp trang cần truy xuất vào khung trang trống đã
chọn (hay vừa mới làm trống), cập nhật nội dung bảng
trang, bảng khung trang tương ứng.
-B5: Tái kích hoạt tiến trình người sử dụng.


18

CHƯƠNG 1. MỞ ĐẦU


Hình 1.5: Sơ đồ truy xuất khi gặp lỗi trang

1.3

Bảng trang

1.3.1

Bảng trang

-Không gian địa chỉ ảo chia thành nhiều trang nhớ. Bảng trang
là nơi lưu trữ các trang ,địa chỉ thông tin, cũng là nơi biên
dịch địa chỉ ảo, sự biên dịch này được quản lý bằng thiết
bị phần cứng gọi là “đơn vị quản lý vùng nhớ” (Memmory
Management Unit - MMU).

Hình 1.6: MMU trong bộ nhớ ảo


1.3. BẢNG TRANG

19

-Khi lập trình, các lệnh truy xuất dùng lượng không gian lớn.
Không gian này được gọi là luận lý (ảo). Nếu ít truy xuất
trong không gian này thì dù RAM nhỏ hơn nhưng hệ điều
hành vẫn chạy tốt. Để quản lý việc nạp và ghi ra bộ nhớ
ảo, hệ điều hành chia bộ nhớ ảo thành các trang ảo có
kích thước bằng 2i (256, 512, 1K, 2K, 4K, 8K, ...). Bộ nhớ

RAM cũng được chia thành nhiều trang thật có kích thước
thật bằng kích thước ảo.
-Nếu trang đa hiện diện sẵn thì cổng vào của "trang bảng" sẽ
chứa địa chỉ của vùng nhớ thật đó nơi mà trang đó được
lưu.
-Còn nếu trang không hiện diện thì sẽ sinh ra một khái niệm
mới là giám sát trang.

Hình 1.7: Bảng trang với một số trang không nằm trong bộ nhớ

1.3.2

Giám sát trang

-”Nếu hiện tượng “trang lỗi” xuất hiện từ phần cứng, hệ thống
giám sát trang sẽ truy cập vào ổ lưu trữ phụ, trả về một
trang có lưu địa chỉ ảo nơi trang lỗi xuất hiện, sau đó sẽ
cập nhật "trang bảng" để phản chiếu vị trí vật lí của bộ


20

CHƯƠNG 1. MỞ ĐẦU

nhớ ảo và báo bộ biên dịch thực hiện lại yêu lại.”(Trích:
Wikipedia-Bộ nhớ ảo)
-Nếu tràn bộ nhớ, “giám sát trang” bắt buộc phải giải phóng
một trang trong bộ nhớ chính để lưu giữ một trang thay
thế. Least-recently using (LRU - ít sử dụng nhất”) để loại
bỏ trang ít sử dụng.

1.3.3

Trang ghim

”Các tên gọi khác: trang khóa, trang cố định hay trang
kết nối. Hệ điều hành có các khu vực bộ nhớ được ghim (không
bao giờ trao đổi để lưu trữ thứ cấp)”.(Trích: Wikipedia-Bộ nhớ
ảo)
1.3.4

Thrashing

Thrashing làm lãng phí thời gian khi chuyển trang đến
và đi đến nơi sao lưu -> làm chậm công việc có ích.
Nguyên nhân: Do tiến trình không có đủ trang, hệ điều hành
tang mức độ đa chương trình.
Thời điểm: Tỷ lệ fault page cao hoặc tràn bộ nhớ

Hình 1.8: Thrashing 1

Hình 1.9: Thrashing 2

Cách khắc phục:
1. Sử dụng thuật toán thay thế trang cục bộ hoặc thay thế
trang ưu tiên để hạn chế thrashing
2. Sử dụng mô hình cục bộ: mô hình working-set
( />

1.3. BẢNG TRANG


3. Thêm bộ nhớ thực
4. Giảm số lượng nhiệm vụ hoạt động trên hệ thống.

21


22

CHƯƠNG 1. MỞ ĐẦU

1.3.5

Truyền dịch địa chỉ trong Page Table: Thay thế và
ghi

1. Thay thế
Khi xảy ra một lỗi trang, nếu không có một khung
trang nào trống, hệ điều hành cần thực hiện công việc thay
thế trang – chọn một trang đang nằm trong bộ nhớ mà
không được sử dụng tại thời điểm hiện tại và chuyển nó ra
không gian trên đĩa để giải phóng một khung trang dành
chỗ nạp trang cần truy xuất vào bộ nhớ.
- Nếu có lỗi trang thì phải thực hiện chuyển một

Hình 1.10: Truyền dịch trong bảng trang. Nguồn: Mr.Aaron Tan Tuck Choy,
slides School of Computing, National University of Singapore

trang ra bộ nhớ phụ và nạp một trang khác vào bộ nhớ
chính. Bit cập nhật (dirty bit) dung để giảm bớt số lần
chuyển trang.

- Bit này nằm ở valid để kiểm tra trang có được cập nhật
hay không :
• Giá trị 1: trang đã được cập nhật và lưu trên đĩa
• Giá trị 0: trang không bị thay đổi

2. Ghi


1.3. BẢNG TRANG

23

- Ghi xuyên : Thông tin sẽ được ghi ở hai mức bộ kế liền
nhau.
- Ghi sau: Thông tin chỉ được ghi ở mức bộ nhớ hiện tại.
- Ưu điểm
- Ghi xuyên: : đơn giản, dễ triển khai.
- Ghi sau: ghi được cùng tốc độ của bộ đệm.


24

1.4
1.4.1

CHƯƠNG 1. MỞ ĐẦU

Translation Lookaside Buffer (TLB) - Bộ đệm
chuyển đổi
Định nghĩa


-Do bảng trên nằm trên bộ nhớ chính nên khi truy xuất bảng
trang thì cần một khoảng thời gian nhất định để truy xuất
đến bộ nhớ chính.
-TLB – bộ đệm chuyển đổi làm nhiệm vụ tang tốc quá trình
tìm kiếm bảng trang trong bộ nhớ chính.
-TLB thực chất là một cache, làm tăng tốc đọ truy cập bộ
nhớ chính.
-TLB biên dịch địa chỉ ảo sang địa chỉ thật, TLB lưu trữ song
song các cặp địa chỉ ảo/thực, xử lý các trang lỗi trên đĩa
thay vì bộ nhớ chính.
1.4.2

Cơ chế của TLB

Hình 1.11: Sơ đồ hoạt động của TLB

Khi quá trình truyền tải dữ liệu từ địa chỉ ảo đến địa chỉ
vật lý được yêu cầu, TLB sẽ thực hiện:


1.4. TRANSLATION LOOKASIDE BUFFER (TLB) - BỘ ĐỆM CHUYỂN ĐỔI 25

-Tìm trang có offset (chữ d trên hình) từ địa chỉ ảo
-Tìm trang ảo trên TLB
-Nếu thấy thì điền offset vào khung trang vật lý và truy xuất
vùng nhớ
-Nếu không thấy thì qua bảng trang tìm kiếm trên bộ nhớ
chính, nếu trang không tồn tại trên bộ nhớ chính thì tạo
trang lỗi và khởi động lại khi trang đó được tìm thấy.

1.4.3

Lỗi TLB

-Nếu trang có trên bộ nhớ
• Nạp PTE từ bộ nhớ và thử lại
• Có thể xử lý bằng phần cứng và cả phần mềm:

1. Nếu là xử lý bằng phần cứng: có thể gây phức tạp
cho các cấu trúc bảng trang
2. Nếu là xử lý bằng phần mềm: đưa ra một ngoại lệ
đặc biệt, với môt cách xử lý tích cực.
-Trang không có trên bộ nhớ
• Cập nhật bảng trang
• Khởi tạo lại các hướng dẫn bị đứt gãy

Trích: Mr. Aaron Tan Tuck Choy, Slides School of
Computing, National University of Singapore
1.4.4

Xử lý lỗi TLB

Lỗi TLB biểu thị khi
• Trang hiện diện nhưng PTE không có trong TLB
• Trang không hiện diện

Phải xác nhận lỗi TLB trước khi ghi đè địa chỉ
Xử lý bằng cách sao chép PTE từ bộ nhớ sang TLB
• Sau đó khởi tạo lai đường dẫn
• Nếu trang không hiện diện thì lỗi trang sẽ xảy ra


Trích: Mr. Aaron Tan Tuck Choy, Slides School of
Computing, National University of Singapore