Nguyễn Mạnh Hà – CB111398 - SPKTTH
LỜI MỞ ĐẦU
Thế kỷ 21 mở ra một thời đại mới , thời đại khoa học công nghệ đòi hỏi con
người luôn luôn không ngừng tìm tòi học tập để tiến bộ .Với sự nhảy vọt của khoa
học, các kỹ thuật thực hiện trong ngành Công nghệ thông tin ngày càng phát triển
chỉ trong thời gian ngắn nó đã đạt được những thành tựu to lớn ở hầu hết các lĩnh
vực khác nhau trong đời sống xã hội. Kỹ thuật dọn rác (Garbage Collector) là một
tiến trình đặc biệt có nhiệm vụ duyệt qua các vùng nhớ đã được cấp phát và kiểm
tra xem vùng nhớ nào không còn được sử dụng nữa (không còn tham chiếu tới nó
nữa) thì sẽ thực hiện thu hồi một cách tự động để có thể cấp phát cho các yêu cầu
tiếp theo. Vấn đề chúng ta cần biết ở đây là, “làm thế nào Garbage Collector có thể
biết được rằng vùng nhớ đó không còn được sử dụng nữa để mà thu hồi?”
Trong bài tiểu luận này, em xin trình bày về “Kỹ thuật Garbage
Collection”
Em xin trân thành cảm ơn thầy TS.Nguyễn Hữu Đức đã hướng dẫn và tạo
mọi điều kiện tốt nhất để em hoàn thành tốt bài tiểu luận này.
Tiểu luận: Nguyên lý các ngôn ngữ lập trình
1
Nguyễn Mạnh Hà – CB111398 - SPKTTH
MỤC LỤC
1. Các khái niệm về Garbage Collection (GC- bộ dọn rác) 3
2. Biến đếm trong GC 5
3. Mark-Sweep Collection - [McCarthy 1960] 8
4. Mark-Compact Collection (Nén sau khi đánh dấu) 10
5. Copying Garbage Collection 11
6. Non-Copying Implicit Collection 13
LỜI KẾT 13
TÀI LIỆU THAM KHẢO 14
Tiểu luận: Nguyên lý các ngôn ngữ lập trình
2
Nguyễn Mạnh Hà – CB111398 - SPKTTH

Nếu tiến trình không giải phóng bộ nhớ đã sử dụng, khoảng trống không sử
dụng sẽ ngày càng tăng cho đến khi tiến trình chấm dứt hoặc việc trao đổi không
gian nhớ sẽ không còn.
*Rào cản trong quản lý bộ nhớ
- Lỗi lập trình có thể dẫn đến lỗi trong quản lý bộ nhớ:
+ Có thể giải phóng vùng nhớ sớm hơn khi cần.
+ Có thể không giải phóng hết vùng nhớ có thể, là nguyên nhân gây ra
thiếu bộ nhớ.
- Những lỗi này đặc biệt nguy hiểm vì thường xuất hiện sau khi phân bổ, rất
khó gỡ rối.
- Nhiều lập trình viên cấp phát object tĩnh, tránh cấp phát trên heap để khỏi
quan tâm khi nào giải phóng chúng
- Trong nhiều hệ thống lớn, GC được thực thi trong những đối tượng hệ
thống (system’s objects).
- GC thì không được hỗ trợ bởi ngôn ngữ lập trình.
- Gây ra lỗi và không tin cậy, những bộ dọn rác riêng lẻ thường không được
sử dụng bởi những ứng dụng khác.
Vì vậy mục đích của GC là giải quyết những các vấn đề trên
* Tính phức tạp của GC
- GC đôi khi được xem là có chi phí rẻ hơn việc giải phóng tường minh
- Một GC tốt làm chương trình chậm 10%.
- Dù có vẻ nhiều nhưng đó là một cái giá thấp để trả cho:
Tiểu luận: Nguyên lý các ngôn ngữ lập trình
4
Nguyễn Mạnh Hà – CB111398 - SPKTTH
+ Sự tiện lợi (Convenience);
+ Thời gian phát triển (Development time);
+ Độ tin cậy (Reliability).
* Hai phase chính của GC
- Dò tìm rác (garbage detection):

thực, đảm bảo các thao tác quản lý bộ nhớ sẽ không trì hoãn chương trình khi
Tiểu luận: Nguyên lý các ngôn ngữ lập trình
6
Nguyễn Mạnh Hà – CB111398 - SPKTTH
chương trình thực thi. Điều này có thể hỗ trợ chương trình khi mà việc đảm bảo về
thời gian là then chốt. Đồng thời việc thu gom tăng cường cũng đảm bảo cho
chương trình thực thi 1 cách hiệu quả thông qua việc giảm bớt số lượng các công
việc mà người lập trình cần phải làm(thu gom rác).
* Vấn đề cấu trúc vòng
Biến đếm thất bại khi giải phóng cấu trúc vòng, nguyên nhân từ việc xác
định rác. Cấu trúc vòng không hiếm trong các chương trình ngày nay(Cây,Cấu trúc
dữ liệu vòng). Khi đó giải pháp được chuyển về cho lập trình viên
* Hiệu quả của biến đếm
- Khi một con trỏ được tạo, biến đếm tham chiếu của đối tượng mà nó trỏ
đến phải được điều chỉnh.
+ Nếu giá trị của biến con trỏ được chuyển từ con trỏ này đến con trỏ
khác(phép gán), thì hai biến đếm của cả hai con trỏ phải được cập nhật, một biến
RC của 1 đối tượng sẽ tăng còn biến kia sẽ giảm.
+Sau đó phải kiểm tra biến đếm=0 hay không
- Những biến ngăn xếp mà có thời gian sống ngắn sẽ phải chịu chi phí lớn
cho mô hình biến đếm. Trong trường hợp này biến đếm tham chiếu được tăng lên
và giảm trở lại nhanh chóng.
*Biến đếm cục bộ
- Phần lớn chi phí có thể tối ưu bằng cách sử dụng biến cục bộ
- Tham chiếu từ biến cục bộ không cần giữ lại. Chúng ta chỉ cần điều chỉnh
biến đếm trong heap.
Tuy nhiên chúng ta không thể bỏ qua hoàn toàn các con trỏ trong stack. Vì
vậy stack được quét trước khi đối tượng được giải phóng và chỉ khi biến đếm của
con trỏ=0 thì nó được giải phóng.
Tiểu luận: Nguyên lý các ngôn ngữ lập trình

if free_list is empty
return (“out-of-memory”)
pointer = allocate(A)
return (pointer)
if mark_bit(Obj) == unmarked
mark_bit(Obj)=marked
for C in Children(Obj)
mark(C)
mark_sweep()=
for Ptr in Roots
mark(Ptr)
sweep()
Sweep()=
p = Heap_bottom
while (p < Heap_top)
if (mark_bit(p) == unmarked) then free(p)
else mark_bit(p) = unmarked; p=p+size(p)
* Tính chất của Mark & Sweep
- Phân mảnh:
+ Khó cấp phát những đối tượng lớn.
+ Vài đối tượng nhỏ có thể lấy nhiều khoảng trống kế tiếp.
- Chi phí:
+ Tỉ lệ với kích thước heap, gồm cả đối tượng sống và rác.
- Locality of reference:
+ Không di chuyển đối tượng
+ Đối tượng được đặt lẫn lộn là nguyên nhân nhiều page swaps
(Thông thường thì những đối tượng trong cluster thường được active cùng
lúc).
*Ưu điểm:
- Không cần cấp thêm vùng nhớ để lưu trữ trường count.

- Có một vài phương thức cho copying GC, “Stop and-Copy” là một ví dụ.
*Stop-and-Copy Collector
- Bộ nhớ heap được chia làm 2 phần.
- Khi chương trình đang chạy yêu cầu cấp phát mà không còn đủ vùng nhớ
chưa sử dụng.
- Chương trình sẽ dừng và copying GC Được gọi để thu hồi khoảng trống.
* Thuật toán
Init()=
Tospace=Heap_bottom
space_size=Heap_size/2
top_of_space=Tospace+space_size
Fromspace=top_of_space+1
New(n)=
If free+n>top_of_space
Collect()
if free+n>top_of_space
Tiểu luận: Nguyên lý các ngôn ngữ lập trình
11
Nguyễn Mạnh Hà – CB111398 - SPKTTH
free=Tospace abort“Memoryexhausted”
new-object=free
free=free+n
return(new-object)
collect()=
from-space,to-space=
to-space,from-space//swap
scan=free=Tospace
top_of_space=Tospace+space_size
forRinRoots
R=copy(R)

- Chương trình phải tạm dừng khi bộ thu gom rác thực thi.
6. Non-Copying Implicit Collection
- Cần thêm 2 trường con trỏ và một trường màu cho mỗi đối tượng. Những
trường này phục vụ cho việc liên kết giữa các vùng nhớ trong một danh sách liên
kết đôi. Trường màu xác định đối tượng thuộc về tập live objects hay tập rác
- Duyệt tất cả các đối tượng trong vùng nhớ heap Các đối tượng live object
sẽ linking đến tập toset, và màu chuyển sang màu khác. Sau khi di chuyển các live
object từ fromset sang thì các object còn lại trong fromset là garbage và có thể sử
dụng như một free list. Sau đó tập hợp fromset sẽ hoán đổi thành toset(giống như
fromspace và tospace trong copying collector)
- Trong hầu hết trường hợp thì chi phí nhỏ hơn copying collector nhưng
trong vài trường hợp thì chi phí phân mảnh có thể quá nặng.
*Ưu điểm:
- Chi phí dò tìm(duyệt- tracing processing) không cao
- Vùng nhớ không cần phải chia đôi, nhưng tốn thêm vùng nhớ để lưu trữ 2
biến con trỏ và trường field color.
-
LỜI KẾT
Tiểu luận: Nguyên lý các ngôn ngữ lập trình
13
Nguyễn Mạnh Hà – CB111398 - SPKTTH
Quá trình thực hiện dọn dẹp bộ nhớ của kỹ thuật Garbage Collector thật sự
khiến cho chương trình của chúng ta sẽ chạy chậm hơn so với các chương trình viết
bằng C/C++. Tuy nhiên, năng suất mà chúng ta đạt được là rất đáng kể bởi vì
chúng ta không phải tập trung giải quyết những công việc đòi hỏi sự tỉ mỉ, cẩn thận
với ngôn ngữ lập trình mà chỉ cần tập trung vào giải quyết các vấn đề của khách
hàng đưa ra.
Một lần nữa, chúng em xin chân thành cảm ơn thầy TS. Nguyễn Hữu Đức
đã tạo mọi điều kiện tốt nhất để chúng em hoàn thành tốt bài tiểu luận này.
TÀI LIỆU THAM KHẢO