BÀI TẬP LỚN
NGUYÊN LÝ HỆ ĐIỀU HÀNH
ĐỀ TÀI: NGHIÊN CỨU TÌM HIỂU VỀ QUẢN LÝ BỘ NHỚ TRONG
TRONG HỆ ĐIỀU HÀNH LINUX

GIÁO VIÊN HƯỚNG DẪN: NGUYỄN TUẤN TÚ
LỚP: KHOA HỌC MÁY TÍNH 4 – K9
NHÓM SỐ 4
SINH VIÊN THỰC HIỆN:
1.
2.
3.
4.
5.

NGUYỄN THỊ DỊU
ĐỖ TUẤN ANH
TRẦN THỊ KIỀU HOA
VI THÙY DƯƠNG
LÊ THỊ CẨM LINH

Hà Nội, ngày 21 tháng 03năm 2016.


MỤC LỤC
MỤC LỤC................................................................................................................................................2
LỜI NÓI ĐẦU...........................................................................................................................................1
CHƯƠNG I: TỔNG QUAN VỀ BỘ NHỚ TRONG CỦA HỆ ĐIỀU HÀNH CỦA LINUX......................................2
1.1.GIỚI THIỆU VỀ HỆ ĐIỀU HÀNH LINUX...........................................................................................2
1.2.: TỔNG QUAN VỀ BỘ NHỚ TRONG LINUX.....................................................................................3
CHƯƠNG II: CƠ CHẾ QUẢN LÝ BỘ NHỚ ẢO............................................................................................4

hành và cac chương trình trên Linux là tài liệu vô giá để chúng ta học hỏi về kỹ
thuật lập trình vốn là những tài liệu không được công bố đối với các ứng dụng
Windows. Trong đồ án này, chúng ta sẽ tìm hiểu một phần rất quan trọng trong
hệ điều hành Linux đó là: quản lý bộ nhớ trong Linux. Một hệ điều hành muốn
chạy ổn định thì phải có một cơ chế quản lý bộ nhớ hiệu quả. Cơ chế này sẽ
được trình bày một cách chi tiết trong đồ án và có kèm theo các chương trình
minh họa.
Trong quá trình tìm bài tuy có nhiều cố gắng nhưng không thể tránh được những
sai sót, nhóm em hy vọng nhận được những nhận xét của thầy để đề tài được
hoàn thành tốt hơn.

13


CHƯƠNG I: TỔNG QUAN VỀ BỘ NHỚ TRONG CỦA HỆ ĐIỀU HÀNH
CỦA LINUX.
1.1.GIỚI THIỆU VỀ HỆ ĐIỀU HÀNH LINUX
Linux là một hệ điều hành dạng Unix (Unix – Like Operating System) chạy
trên máy PC với bộ vi điều khiển trung tâm Intel 80386 trở lên hay các bộ vi xử
lý trung tâm tương thích AMD, Cyric. Phiên bản Linux đầu tiên do Linus
Torvalds viết vào năm 1991, phiên bản Linux 1.0 ra đời vào 3 năm sau, năm
1994. Bộ phần chủ yếu này được phát triển và tung ra trên thị trường dưới bản
quyền GNU General Public License. Do đó mà bất cứ ai cũng có thể tải và xem
mã nguồn của Linux.
Khởi đầu, Linux được phát triển cho dòng vi xử lý 386, hiện nay hệ điều
hành hỗ trợ một số lượng lớn các kiến trúc vi xử lý, và được sử dụng trong nhiều
ứng dụng khác nhau, từ máy tính cá nhân cho đến các siêu máy tính, netbook và
các thiết bị nhúng ví dụ như: máy điện thoại di động.

Hình 1.1: Các thuộc tính và các phân khúc của Linux được tập trung vào

của người sử dụng. Các máy tính c nhân hiện nay đã trang bị ít nhất 1GB bộ
nhớ. Các máy chủ server có thể lên đến hàng GB bộ nhớ. Thế nhưng nhu cầu bộ
nhớ vẫn được thỏa mãn.
Linux có cách tiếp cận vào quản lý bộ nhớ rất rõ ràng. Các ứng dụng trên
Linux không bao giờ được phép truy cập trực tiếp vào địa chỉ vật lý của bộ nhớ.
Linux cung cấp cho các chương trình chạy dưới hệ điều hành – còn gọi là tiến
trình – một mô hình đánh địa chỉ phẳng không phân đoạn segment: offset như
DOS. Mỗi tiến trình chỉ thấy được một vùng không gian địa chỉ của riêng nó.
Hầu hết tất cả các phiên bản Unix đều cung cấp cách bảo vệ bộ nhớ theo cơ chế
bảo đảm không có tiến trình nào có thể ghi đè lên vùng nhớ của tiến trình khác
đang hoạt động hoặc vùng nhớ của hệ thống. Nói chung, bộ nhớ mà hệ thống
cấp phát cho một tiến trình không thể nào đọc hoặc ghi bởi một tiến trình khác.
Trong hầu hết các hệ thống Linux và Unix, con trỏ được sử dụng là một số
32 bit trở lên đến một ô nhớ cụ thể. Với 32 bit, hệ thống có thể đánh địa chỉ lên
đến 4GB bộ nhớ. Mô hình bộ nhớ phẳng này dễ truy xuất và xử lý hơn bộ nhớ
phân đoạn segment: offset.
Ngoài ra, một vài hệ thống còn sử dụng mô hình địa chỉ 64 bit, như vậy,
không gian địa chỉ có thể mở rộng ra đến tearabyte.
Các sơ đồ quản lý bộ nhớ trong là: sơ đồ phân hoạch cố định, sơ đồ phân
hoạch động, sơ đồ hoán đổi (swapping), sơ đồ phân trang, sơ đồ phân đoạn, sơ
đồ kết hợp phân trang phân đoạn. Trong đó, Linux sử dụng sơ đồ hoán đổi
(swapping), phân trang, phân đoạn và bộ nhớ ảo để quản lý bộ nhớ trong. Chúng
ta sẽ tìm hiểu những cơ chế đó trong những chương sau để hiểu rõ hơn quá trình
quản lý bộ nhớ trong trong hệ điều hành Linux.

13


CHƯƠNG II: CƠ CHẾ QUẢN LÝ BỘ NHỚ ẢO
2.1.: CÁC KHÁI NIỆM BỘ NHỚ ẢO, KHÔNG GIAN HOÁN ĐỔI.



Hình 2.2.1: Mô hình trừu tượng của sự ánh xạ từ địa chỉ ảo đến địa chỉ vật lý.
Trong mô hình này, một địa chỉ ảo bao gồm 2 phần: địa chỉ offset và số
khung trang ảo. Nếu kích thước trang là 4KB (tương ứng địa chỉ offset từ
0→4095) thì từ bit 11 đến bit 0 của chỉ ảo chứa địa chỉ offset, còn từ bit 12 trở
lên là số khung trang ảo. Mỗi lần bộ xử lý bắt gặp một địa chỉ ảo, nó sẽ lấy địa
chỉ offset và số khung trang ảo ra. Bộ xử lý phải chuyển từ số khung trang ảo
sang số khung trang vật lý và sau đó truy cập vào địa chỉ offset trong trang vật lý
đó. Để làm được điều này thì bộ xử lý xử dụng bảng trang.
Bộ xử lý số khung trang ảo như là chỉ mục vào bảng trang các tiến trình để
truy xuất vào từng mục của bảng trang. Nếu mục của bảng trang tại địa chỉ
offset đó là hợp lệ thì bộ xử lý sẽ lấy số khung trang vật lý từ mục này. Nếu mục
này không hợp lệ thì tiến trình sẽ truy cập vào một vùng không tồn tại của bộ
nhớ ảo. Trong trường hợp này, bộ xử lý sẽ không thể làm việc với địa chỉ này
mà chuyển điều khiển cho hệ điều hành để khắc phục lỗi đó.
Bằng cách ánh xạ địa chỉ ảo và địa chỉ vật lý như thế này, bộ nhớ ảo có thể
được ánh xạ vào bộ nhớ vật lý của hệ thống theo bất kỳ thứ tự nào. Ví dụ: trong
hình 2.2.1 ở trên.
2.2.: TẠO KHÔNG GIAN HOÁN ĐỔI ( CƠ CHẾ Swapping )
Khi máy tính cần chạy những chương trình lớn hơn bộ nhớ vật lý (RAM) có
sẵn, hầu hết các hệ điều hành ngày nay sử dụng công nghệ hoán đổi có tên gọi là
swapping. Đây là công nghệ mà trong đó một phần bộ nhớ tạm thời được lưu
trên ở cứng (đĩa cứng) trong khi các dữ liệu khác vẫn được chuyển vào trong
không gian bộ nhớ vật lý (RAM). Công nghệ này giúp ta quản lý việc hoán đổi
(swapping) tốt hơn cũng như tăng hiệu năng sử dụng.
Linux chia bộ nhớ vật lý (RAM) thành cac pages. Swapping là một tiến trình
thực hiện việc copy một page của bộ nhớ đến một không gian đã được cấu hình
13


rất chậm. Tốc độ bộ nhớ có thể được đo bằng nano giây (ns) trong khi tốc độ ổ
bằng mili giây (ms), do đó truy cập chậm hơn hàng chục nghìn lần truy cập vào
bộ nhớ vật lý (RAM). Càng thực hiện hoán đổi nhiều thì hệ thống càng chậm.
Đôi khi hoán đổi quá mức hoặc nhiều lần liên tiếp sẽ xảy ra ở một trang được
chuyển ra rồi ngay lập tức lại được chuyển vào rồi lại chuyển ra cứ thế tiếp tục.
Trong mỗi trường hợp thì hệ thống sẽ tìm ra các vùng nhớ trống và cùng lúc đưa
vào chạy ứng dụng. Trường hợp này chỉ cần thêm RAM.
Ta nên cẩn thận khi sử dụng hàm mkswap() bởi vì nó không kiểm tra file hay
phân vùng này sử dụng chưa. Ta có thể dễ dàng ghi đè lên file hay phân vùng
quan trọng với hàm mkswap(). Tốt hơn hết là ta chỉ nên sử dụng hàm này khi cài
đặt hệ thống của bạn.

13


2.3.: SỬ DỤNG KHÔNG GIAN HOÁN ĐỔI
Linux sử dụng hai loại không gian hoán đổi là partition hoán đổi và tập tin
hoán đổi.
a : Partition hoán đổi.
Partition hoán đổi là môt phần đọc lập của ổ cứng được sử dụng chỉ để hoán
đổi không một tập tin nào khác được lưu trữ ở đây.
Để biết được dung lượng không gian hoán đổi mà ta có, ta sử dụng lệnh
swapon-s. Ta thực hiện kết quả như sau:
Filename
/dev/sda5

Type
Partition

Size

Blocks

Id

/dev/hdb1

2328

2434

859446 82

System
Linux swap/Solaris

Nếu Partition chưa được đánh dấu thì ta phải sửa lại nó bằng cách chay fdisk
và dùng tùy chọn ‘t’. Hãy cẩn thận khi làm việc với các Partition. Ta không
muốn xóa đi những Partittion quan trọng bởi bị lỗi hay thay đổi ID của Partition
khi hệ thống mắc lỗi trong việc hoán đổi. Tất cả các dữ liệu trên một Partition
hoán đổi sẽ bị mất do đó hãy kiểm tra lại thay đổi ta tạo ra. Đồng thời chú ý rằng
Solaris sử dụng cùng ID giống không gian hoán đổi Linux, phải cẩn thận để
không xóa các Partition Solaris đó.

13


Ngay khi Partition được đánh dấu hoán đổi, ta hãy dùng lệnh mkswap (make
swap) như sau:
Mkswap /dev/hdb1
Nếu không có lỗi xảy ra thì hoán đổi của bạn đã sẵn sàng được sử dụng. Để

đổi đã được tự động cài đặt mà không cần phải khởi động lại thì bạn có thể dùng
lệnh: swapoff – a (tắt các không gian hoán đổi) rồi sau đó dùng lênh : swapon –
a (cài đặt tất cả mọi không gian hoán đổi liệt kê tại tập tin /etc/fstab) rồi kiểm tra
lại bằng lệnh swapon – s.
Một không gian hoán đổi đã khởi tạo sẽ lấy được để sử dụng nhờ lệnh
swapon. Lệnh này bào cho kernel bằng không gian hoán đổi có thể sử dụng.
Đường dẫn đến không gian hoán đổi được cấp như là đổi số, vì vậy để bắt đầu
hoán đổi trên một file swap tạm thời, ta có thể sử dụng đoạn lệnh sau:
$ swapon/extra-swap $
Không gian hoán đổi có thể được sử dụng tự động bằng cách liệt kê chũng
trong file /etc/fstab.
/dev/hda5 none swap sw 0 0
/swapfile none swap sw 0 0
Đoạn mã khởi động sẽ chạy lệnh swapon – a, lệnh này sẽ bắt đầu thực hiện
hoán đổi trên tất cả các không gian hoán đổi được liệt kê trong file /etc/fstab. Do
đó lệnh swapon chỉ thường được sử dụng khi cần hoán đổi thêm.
13


b : Tập tin hoán đổi
Cũng giống như Partition hoán đổi, Linux hỗ trợ cho bạn tạo được một tập
tin hoán đổi, chuẩn bị và lắp đặt cùng kiểu với Partition hoán đổi. Lợi ích của
các tập tin hoán đổi đó là ta không cần phải tìm kiếm một Partititon trống hay
phân chia lại ổ để thêm vào các không gian hoán đổi.
Để tạo một tập tin hoán đổi, trước tiên hãy dùng lệnh dd để tạo một tập tin
rỗng. Ví dụ, tạo một tập tin 1GB, nhập:
dd if=/dev/zero of=/swapfile bs=1024 count=1048576
/swapfile là tên của tập tin hoán đổi và 1048576 là kích cỡ tính bằng kilobyte
(ví dụ 1GB).
Chuẩn bị tập tin hoán đổi ta dùng mkswap như khi tạo Partition, nhưng ở đây

13


CHƯƠNG III: CƠ CHẾ PHÂN TRANG PHÂN ĐOẠN
3.1.: CƠ CHẾ PHÂN ĐOẠN
Quan niệm 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 quan 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.
∗ Linux sử dụng cơ chê phân đoạn để phân tách các vùng nhớ đã cấp phát cho
hạt nhân và các tiên trình. Hai phân đoạn liên quan đến 3GB đầu tiên (từ
0→0xBFFF FFFF) của không gian địa chỉ tiến trình và các nội dung của chúng
có thể được đọc và chỉnh sửa trong chế độ người dùng và trong chế độ kernel.
Hai phân đoạn liên quan đến GB thứ 4 (từ 0xC000 0000 → 0xFFFF FFFF) của
không gian địa chỉ tiến trình và nội dung của nó có thể được đọc và chỉnh sửa
duy nhất trong chế độ kernel. Theo cách này, dữ liệu và mã kernel được bảo vệ
khỏi sự truy cập không hợp lý của các tiến trình chế độ người dùng.

Hình 3.1.1: Kernel/Used Linear addresses
3.2.: CƠ CHẾ PHÂN TRANG
• NHU CẦU PHÂN TRANG
Vì có quá ít bộ nhớ vật lý so với bộ nhớ ảo nên HĐH phải chú trọng làm sao
để không lãng phí bộ nhớ vật lý. Để tiết kiệm bộ nhớ vật lý thì chỉ load những
trang ảo mà đang được sử dụng bởi một chương trình đang thực thi. Việc mà chỉ
load những trang ảo vào bộ nhớ khi chúng được truy cập dẫn đến nhu cầu phân
trang.
13


• TRANG LƯU TRỮ (PAGE CACHE)
Cache là tầng nằm giữa phần quản lý bộ nhớ kernel và phần vào ra của đĩa.

 Trang P được ghi bởi các tiến trình do đó có chứa dữ liệu (dirty). Lúc này
trang P vẫn ở trên active_list.

13


 Trang P không được sử dụng trong một thời gian. Sự kích hoạt định kỳ của
hàm kswap() (kernel swap daemon) sẽ giảm dần biến đếm page → age. Hàm
kswapd() sẽ hoạt động nhiều hơn khi nhu cầu về bộ nhớ tăng. Thời gian tồn tại
trang P sẽ giảm dần xuống 0 (age == 0) nếu nó không còn được tham chiếu, dẫn
đến sự kích hoạt của hàm re_fill inactive().
 Nếu bộ nhớ đầy, hàm swap_out sẽ được gọi bởi hàm kswaps() để cố gằng lấy
lại các trang từ không gian địa chỉ ảo của tiến trình A. Vì trang P không còn
được tham chiếu và có age == 0, nên các mục trong bảng trang sẽ bị xóa. Nhờ
vào page cache và cơ chế swap mà trang sẽ đảm bảo được ghi lên đĩa khi cần.
 Thời gian xử lý ít hay nhiều là tùy thuộc vào nhu cầu sử dụng bộ nhớ.
 Tiếp theo, hàm refill_inactive_scan() tìm các trang mà có thể đưa đến
inactive_dirty list. Từ khi trang P không được ánh xạ bởi một tiến trình nào và
có age == 0 thì nó được đưa từ active_list đến inactive_dirty list.
 Tiến trình A truy cập vào trang P, nhưng nó hiện không có trong bộ nhớ ảo
tiến trình các mục trong bảng trang đã bị xóa bởi hàm swap_out(). Trình điều
chỉnh lỗi gọi hàm find_page_nolock() để xác định địa chỉ trang P trong page
cache. sau khi tìm thấy, các mục trong bảng trang sẽ được phục hồi ngay lập tức
và trang P được đưa đến active_list.
 Quá trình này mất nhiều thời gian do hàm swap_out() xóa các mục trong
bảng trang của tiến trình A, hàm refill_inactive_scan() vô hiệu hóa trang P, nó
đưa đến inactive_dirty list. Việc tốn nhiều thời gian sẽ làm cho bộ nhớ trở lên
chậm.
 Hàm page_launder() được kích hoạt để làm sạch các trang dirty và thực hiện
để tìm các trang không sử dụng và clean, đưa chúng đến inactive_clean_list. Khi

các khối của trang. Đoạn đã định vị trang xác định một khối của một hay nhiều
trang vật lý. Những trang được định vị trong khối có kích thước là lũy thừa của
13


2. Khi có đủ số trang trống trong hệ thống để cấp cho một yêu cầu, đoạn mã
định vị sẽ tìm trong free_area một khối các trang có kích thước như yêu cầu.
Mỗi phần tử của free_area ánh xạ đến các khối trang trống có kích thước tương
ứng. Ví dụ, phần tử thứ 2 của ánh xạ đến các khổi gồm 4 trang trống đã được
định vị/

Hình 3.2.2: Cấu trúc dữ liệu của free-area.
Ví dụ, trong hình 3.2.2 , nếu một hình khối gồm 2 trang được yêu cầu thì 4 khối
trang thứ nhất (bắt đầu ở khung trang số 4) sẽ được chia thành 2 khối 2 trang. Khối thứ
nhất (bắt đầu ở khung trang số 4) sẽ được cung cấp cho lời gọi và khối thứ 2 (bắt đầu ở
khung trang số 6) sẽ được đưa vào hàng đợi như là một khối 2 trang trống ở phần tử
thứ nhất của mảng free_area.
 Giải phóng trang
Việc định vị các khối trang làm cho bộ nhớ bị phân mảnh do các khối trang lớn bị
chia nhỏ. Đoạn mã giải phóng trang kết hợp các trang lại thành một khối lớn các trang
trống bất kỳ khi nào có thể. Khi có một khối trang trống thì các khối lân cận có cùng
kích thước được kiểm tra xem có trống không. Nếu có thì chúng được kết hợp với
nhau để tạo ra một khối trang có kích thước gấp đôi. Đoạn mã giải phóng trang lại tìm
cách kết hợp khối mới này với một khối khác. Theo cách này, khối khác các trang
trống sẽ lớn dần.

13


CHƯƠNG IV: CƠ CHẾ QUẢN LÝ BỘ NHỚ VẬT LÝ, ÁNH XẠ BỘ NHỚ

những sự khác nhau như vậy bằng cách chia bộ nhớ thành các vùng và xem mỗi
vùng là một đơn vị cho sự định vị.
Cấu trúc dữ liệu root được quản lý bởi bộ định vùng là zone_struct, gồm tập
hợp tất cả dữ liệu liên quan đến việc quản lý một vùng cụ thế. Zonelist_struct
bao gồm một mảng các con trỏ zone_struct và một gfp_mask chỉ ra cơ chế định
13


vị nào có thể sử dụng zone_list. Zone_struct offset chỉ ra địa chỉ offset của nơi
bắt đầu 1 vùng trong bộ nhớ vật lý.

13