Tag: bộ

[Java Memory 1] Escaping References trong Java, Call-by-value và sử dụng Defensive copying. Biến trong Java lưu thế nào

Trở thành “mồi” của GC (Garbage Collector)

• Ta đã biết, khi một đối tượng không còn tác dụng nữa, thì chúng sẽ bị GC dọn đi để tiết kiệm bộ nhớ, nhưng thế nào là “hết tác dụng” ?
• Có thể tóm gọn bằng một câu cơ bản “Object tại heap sẽ không còn hữu dụng nếu chúng mất kết nối tới stack”
• Object mất kết nối tới stack khi không còn một con trỏ nào chỉ tới chúng nữa cả, hãy xem thử đoạn code sau:

Object o = new Object();
System.out.println(o);
o = null; 

• Ở dòng đầu tiên, ta tạo một đối tượng o, o lúc này thực chất đang chỉ tới giá trị thực sự của đối tượng ta vừa tạo ra trong heap
• Khi in thử đối tượng này ra, ta có output theo mẫu sau

java.lang.Object@4617c264

• Tiếp theo, ta cập nhật o thành null. Lúc này, đối tượng nằm ở heap không còn cái gì trỏ đến nó nữa, và không gì có thể truy cập lại nó nữa, và lúc này nó trở thành mồi của GC

Vấn đề không đơn giản

• Ví dụ trên khá đơn giản do chỉ có 1 object, vấn đề sẽ phức tạp hơn khi ta tiếp cận với nhiều object liên kết với nhau 1 lúc

• Giả sử với 6 dòng lệnh sau, ta sẽ đi qua từng dòng một

• Sau 4 dòng đầu tiên, stack và heap của chúng ta có dạng như sau. Tại stack là các biến giữ con trỏ tới các giá trị thực trong heap.

• Sau dòng thứ 5, ta có hình như sau. Ta thấy, dù sau khi đã cập nhật p1 thành null với mong muốn GC sẽ dọn object này, nhưng thực tế, ta thấy ta vẫn có thể truy cập vào p1 bằng person.get(1) qua list persons, tức là ta vẫn có cách reach đến điểm này

• Chỉ sau khi set cả list thành null, ta mới mất hoàn toàn liên hệ với p1

• => Không khó để đánh giá các phần tử nào sẽ được Garbage Collector dọn khi bạn đã hiểu về quan hệ bên trên. Dễ dàng thấy, sau 6 bước, p1 mất hoàn toàn liên hệ với stack và sẽ được dọn
• Tuy nhiên, đó là ta nhìn thủ công, còn để garbage collector biết cái nào còn kết nối với stack sẽ tốn một lượng thời gian, và nó sẽ làm chậm hệ thống lại (chi tiết ở bên dưới). Có nhiều cách để làm điều này, và ta sẽ thảo luận ở bên dưới

Đánh dấu đệ quy

• Ta sẽ thử đánh dấu các object còn live và object nào có thể bị dọn bởi GC. Dễ dàng, ta thêm 1 bit để dánh dấu xem chúng có còn kết nối với stack hay không. Khi tạo, ta sẽ để bit là 0, và khi ở giai đoạn đánh dấu, object là 0 sẽ bị xoá đi, còn nếu vẫn còn sử dụng, ta sẽ cập nhật nó thành 1
• Tuy nhiên, heap và stack thay đổi liên tục. Cách đánh dấu được triển khai tuỳ thuộc vào phiên bản Java và GC bạn sử dụng, tuy nhiên, ta sẽ thử xem cách hệ thống đánh từ stack, hãy thử xem ví dụ sau

• Đầu tiên toàn bộ phần tử sẽ được để là 0

• Sau đó, toàn bộ các phần tử có kết nối trực tiếp tới stack được đánh thành 1

• Tuy nhiên, do p1 vẫn có thể truy cập từ danh sách persons, và hơn nữa, ta không thể cứ dọn những gì vẫn còn kết nối. Vì vậy ta cần một cách duyệt đơn giản, với điểm khởi đầu từ các điểm đang = 1, sau đó đi đến mọi quan hệ của nó và đánh chúng thành 1, rồi tiếp tục đệ quy.

• Các thuật toán đánh dấu đóng vai trò quan trọng trong giai đoạn đánh dấu, đầu tiên thử đi qua cách stop-the-world

Kĩ thuật Stop-The-World – Dừng thế giới

• Với cách đánh dấu trên, ta nhận thấy. Nếu một phần tử được tạo trong quãng đánh dấu, nó sẽ không còn đúng nữa.
• Vì vây, có một solution đơn giản là ta sẽ dừng mọi luồng khác và chỉ chạy luồng đánh dấu của cả chương trình, điều này sẽ rất ảnh hưởng đến hiệu năng. Ta sẽ thử xem các thuật toán tiếp theo.

Kĩ thuật Reference counting – Đếm liên hệ

• Một cách triển khai khác là đếm số lần một object được trỏ đến. Mỗi object sẽ chứa số lần object được trỏ như một thông số mà nó nắm giữ. Như vậy, GC chỉ việc quét qua và xoá mọi object có 0 lần bị nắm giữ. Cách này sẽ không cần stop-the-world như cách đánh số đệ quy nữa, vì khi object được tạo ra giữa chừng lúc đánh số lần trỏ thì nó vẫn đều là 1 rồi.

• Tuy nhiên, nó có một điểm yếu là sẽ tạo ra island of isolation, hay các vùng, một tập các object tự trỏ nhau nhưng mà thực tế không có kết nối tới stack

Giải phóng bộ nhớ

• Cách thức làm sao để đánh dấu các object sẽ bị xoá sẽ được quyết định khác nhau bởi phiên bản Java và các kiểu GC khác nhau.
• Giả sử ta đã đánh dấu được hết các object sẽ có thể bị xoá, tuy nhiên việc xoá chúng đi cũng không phải một quá trình đơn giản
• Việc xoá object được gọi là sweeping by garbage collector, trong bài viết sẽ mention 3 cách thức sweeping khác nhau
  • Normal sweeping
  • Sweeping with compacting
  • Sweeping with copying

Normal sweeping

• Hình ảnh trên thể hiện các khối bộ nhớ trong ram, các vùng có dấu X là các object đã được đánh dấu và chuẩn bị bị xoá

• Sau khi xoá đi, vùng nhớ của ta có dạng như sau, dễ thấy, điều này dẫn tới một triệu chứng có tên Fragmentation

Fragmentation trong Java Garbage Collector

• Lúc này, vì các vùng trống nằm ở giữa các vùng bị chiếm dụng, nên ta chỉ có thể thêm các bộ nhớ nhỏ hơn hoặc bằng vùng vào các vùng trống. Điều này sẽ dẫn tới 1 vài vấn đề khi ta muốn cấp phát một bộ nhớ lớn hơn

• Giả dụ với trường hợp cấp phát một vùng nhớ lớn hơn các khe trống như ảnh trên, khi cấp phát vào, ta chỉ có thể xếp như sau:

• Dù tổng thể bộ nhớ còn trống ta vẫn đủ để xếp vùng nhớ, nhưng thực tế thì ta không có một vùng nhớ liên tiếp nào chứa đủ vùng nhớ mới này. Và việc này sẽ throw ra 1 runtime exception là OutOfMemoryError.

Ưu nhược điểm của Normal sweeping

• Normal Sweeping là một kĩ thuật giải phóng vùng nhớ ngây thơ, khá tiện dụng và đơn giản. Tuy nhiên sẽ dẫn tới các vùng nhớ bị phân mảnh. Quá trình này phù hợp khi ta có nhiều bộ nhớ, và ta chỉ cần nhanh chóng dọn bộ nhớ đi. Khi mà lượng vùng nhớ còn trống nhỏ hơn, ta sẽ prefer các kĩ thuật khác

Sweeping with compacting

• Sweeping with compacting là một quá trình 2 bước. Đầu tiên, chúng vẫn giải phóng bộ nhớ, nhưng sau đó ta sẽ thực hiện thêm 1 bước gọi là compacting (thu gọn), ta sẽ dời toàn bộ vùng nhớ về phía đầu để đảm bảo không có bất kì khoảng trống nào ở giữa

Ưu nhược điểm Sweeping with compacting

• Cách làm này giúp bộ nhớ không còn bị phân mảnh như thông thường, tuy nhiên việc di chuyển các vùng nhớ về đầu là một quá trình tốn kém, vì gần như với lượng vùng nhớ nhỏ và trải dài nhiều, ta sẽ phải copy và di chuyển khá nhiều trên vùng nhớ.

Sweeping with copying

• Ở cách làm này, ta sẽ cần 2 vùng nhớ khác nhau. Ta sẽ không trực tiếp xoá các vùng nhớ bị đánh dấu là xoá đi, mà ta sẽ copy các vùng nhớ k bị xoá vào vùng nhớ mới

• Sau đó mới thực hiện xoá toàn bộ vùng nhớ ở vùng nhớ cũ

Ưu nhược điểm của Sweeping with copying

• Dữ liệu không bị phân mảnh
• Về hiệu năng thì nhanh hơn compacting, do không phải thực hiện nhiều công đoạn tính toán khi di chuyển, mà chỉ copy nhanh chóng sang vùng mới đang trống hoàn toàn (ở compacting ta ví dụ di chuyển vùng 30-50 sang vùng 0-10, đầu tiên ta phải di 30-40, sau đó lại di vùng 10-20 đi, …. và khó khăn hơn nhiều)
• Tuy nhiên cần nhiều bộ nhớ hơn vào cùng 1 thời điểm, cần lượng bộ nhớ trữ còn lại đủ nhiều để di chuyển.