Lập trình

Lập trình

Thứ Ba, 22 tháng 12, 2015

Con trỏ và bộ nhớ [2] - Bộ nhớ heap

Lần trước chúng ta đã tìm hiểu các khái niệm về local memory trong bộ nhớ Tìm hiểu con trỏ và bộ nhớ [1] . Bên cạnh các điểm mạnh thì nó cũng có các điểm yếu, để khắc phục ta sẽ tìm hiểu một vùng nhớ rất quan trọng trong programming là HEAP MEMORY , hôm nay ta tìm hiểu một vài khái niệm đơn giản và cách sử dụng của heap.

[HEAP MEMORY]


Bộ nhớ heap , cũng được biết đến như là bộ nhớ động, nó thay thế cho bộ nhớ local. Local memory đã bàn ở phần trước, nó khá tự động - Nó được cấp phát tự động trên lời gọi function và nó được deallocated tự động khi function kết thúc. Heap memory khác trên mọi phương diện. Lập trình viên bắt buộc phait yêu cầu một cách rõ ràng cho việc cấp phát bộ nhớ với một size cụ thể, và khối đó vẫn được ấp phát cho đến khi lập trình viên yêu cầu deallocate một cách rõ ràng. Không có thứ gì xảy ra một cách tự động. Vì vậy lập trình viên điều khiển bộ nhớ nhiều hơn, nhưng trách nhiệm của lập trình viên nhiều hơn bởi vì bộ nhớ lúc này phải được quản lý tích cực. 
  

  * Lợi ích của heap memory rất nhiều ...



    # Vòng đời(lifetime) Bởi vì lập trình viên bây giờ điều khiển chính xác khi bộ nhớ được phân bổ và bị deallocated, nó có thể khả năng xây dựng một cấu trúc dữ liệu ở bộ nhớ và trả về cấu trúc dữ liệu đó cho caller (hàm gọi - như đã nói ở bài trước). Điều này không bao giờ là có thể đối với local memory , điều này là vì nó tự động deallocated khi function kết thúc


    # Kích cỡ (Size) Kích cỡ của bộ nhớ được cấp phát có thể được điều khiển một cách chi tiết hơn. Ví dụ một chuỗi có thể được allocated tại thời gian chạy , nó phải là một kích cỡ chính xác phù hợp để tổ chức một chuỗi cụ thể. Với local memory thì code giống như khai báo một bộ đếm có kích cỡ là 1000 và hi vọng nó phù hợp nhất .

  * Khuyết điểm của việc sử dụng bộ nhớ heap.


    # Làm nhiều việc hơn. Cấp phát với bộ nhớ heap cần phải bố trí một cách rõ ràng trong code, điều này chỉ làm nhiều việc hơn.

    # Nhiều bug. Bởi vì nó bây giờ được làm một cách rõ ràng trong code, cấp phát có thể sẽ thực hiện không đúng dẫn đến memory bugs. Mặc dù local memory giới hạn nhưng nó không bao giờ sai.

Dù sao thì có rất nhiều vẫn đề có thể chỉ được giải quyết với heap memory. Trong nhiều ngôn ngữ với thùng thu gom rác như Perl , LISP, Java thì khuyết điểm trên của heap phần lớn được loại bỏ. Thúng thu gom rác chiếm phần lớn trách nhiệm cho việc quản lý heap , với chi phí thêm một chút thời gian trong thời gian chương trình chạy (run-time).

Vậy heap hoạt động như thế nào ?


Trước khi xem chi tiết ta cùng xem một vài ví dụ về việc cấp phát và thu hồi trong heap...

. Allocation


Heap là một vùng nhớ rất rộng có sẵn để chương trình sử dụng. Chương trình có thể yêu cầu vùng hoặc khối nhớ để nó sử dụng ở trong heap. Để cấp phát một khối nhớ, chương trình làm yêu cầu minh bạch gọi hàm cấp phát của heap. Hàm cấp phát sẽ để riêng một khối nhớ vừa được yêu cầu kích cở trong heap và trả về con trỏ trỏ vào nó. Giả sủ chương trình làm ba cấp phát yêu cầu cấp phát động , tổ chức nó riêng biệt để lưu trữ ảnh GIF trong heap , mỗi kích cỡ là 1024 bytes. Sau khi yêu cầu cấp phát, bộ nhớ được nhìn như thế này :

 

 Mỗi cấp phát yêu cầu dành riêng một vùng nhớ liên tục với kích cỡ được yêu cầu trong heap và trả về con trỏ trỏ đến khỗi nhớ đó cho chương trình. Bởi vì khỗi này luôn được trỏ bởi con trỏ, nên khối này luôn có vai trò như "pointee - đã nhắc ở phần 1" và chương trình luôn dùng khối bộ nhớ thông qua con trỏ. Con trỏ của khối nhớ heap thỉnh thoảng được biết đến như địa chỉ cơ sở bởi vì theo hiệp ước chúng chỉ tới địa chỉ cơ sở của khối (chính là byte địa chỉ thấp nhất).

Trong ví dụ trên, ba khối được cấp phát LIÊN TỤC TỪ PHÍA DƯỚI của bộ nhớ heap và mỗi khối là 1024 byte như kích cỡ được yêu cầu. Trên thực tế quản lý heap "heap manager" có thể cấp phát khối nhớ bất cứ nơi nào nó muốn trong heap miễn là những khối không chồng chéo lên nhau và có ít nhất một yêu cầu có kích cỡ. Tại một vài thời điểm cụ thể, một vài vùng trong heap đã được cấp phát cho chương trình , vì vậy nó được coi là đang sử dụng "in use". Vài vùng khác chưa được ủy thác nên nó được coi là tự do "free" và có sãn để đáp ứng cho yêu cầu cấp phát. Quản lý vùng nhớ heap tự có riêng của mình câu trúc dữ liệu private "private data structures " để ghi lại đâu là vùng nhớ của heap đã được giao phó cho mục đích tại một vài thời điểm. Quản lý heap đáp ứng cho mỗi yêu cầu cấp phát thừ khối bộ nhớ đang tự do "free memory" sau đó cập nhật nó vào private dât structures để ghi nó lại là bộ nhớ đó đang trong sử dụng.


.Thu hồi (deallocation)


Khi chương trình đang sử dụng khối nhớ kết thúc, nó làm một yêu cầu thu hồi (deallocation) minh bạch để chỉ cho heap manager rằng chương trình đó đã kết thúc bây giờ với khối nhớ. Heap manager cập nhất private data structures của nó chỉ ra rằng vùng nhớ đã chiếm đóng đã free trở lại và vì vậy có thể tái sử dụng "re-used" để đáp ứng cho tính năng yêu cầu allocation. Đâu là những gì mà heap muốn thấy nếu chương trình deallocates khối thử hai của ba khối :



Sau khi deallocation, con trỏ tiếp tục trỏ vào khối đã bị deallocated ngay lúc đó. Nhưng chương trình không được truy cập vào vùng nhớ đã bị deallocated. Đó là lý do tại sao con trỏ được vẽ màu xám - CON TRỎ VẪN Ở ĐÓ NHƯNG NÓ KHÔNG ĐƯỢC SỬ DỤNG. Thỉnh thoảng code sẽ đặt con trỏ trỏ tới NULL ngay tức thì sau khi deallocation được làm một cách minh bạch thực tế điều này khồn có giá trị.

. Lập trình với heap (programming the heap)

Lập trình với heap rất giống nhau trogn nhiều ngôn ngữ.  Tính năng căn bản là :

    # Heap là một vùng nhớ có sẵn để cấp phát vùng nhớ cho chương trình

    # Có một vài thư viện quản lý heap, nó quản lý cho chương trình. Lập trình viên cần thực hiện lời yêu cầu đến quản lý heap, nó lần lượt quản lý những thứ bên trong của heap. Trong C, heap được quản lý bởi thư viện hàm ANSI malloc(), free() và realloc().

    # Bộ quản lý Heap sử dụng cấu trúc dữ liệu của chính nó để theo dõi khối nào trong heap là "free" (có thể dùng để sử dụng) và khối nào hiện tại đã sử dụng bởi chương trình và độ rộng của nó như thế nào. Lúc mới cài đặt (hay ban đầu) thì tất và heap đều "free"

    # Heap có lẽ là một bộ nhớ giới hạn, hoặc nó có thể giống như một khối bị giới hạn nhưng kích cỡ cực kì rộng do được hỗ trợ bởi bộ nhớ ảo. Trong cả hai trường hợp, sẽ là có thể nếu heap bị đầy bởi việc cấp phát và vì vậy nó không thể đáp ứng được yêu cầu cấp phát. Hàm cấp phát sẽ thường trả về con trỏ NULL.

    # hàm cấp phát yêu cầu một khối trong heap với một kích cỡ cụ thể. Trình quản lý heap chọn một vùng nhớ để sử dụng cho việc đáp ứng yêu cầu đó, đánh dấu vùng nhớ đó như "in use" trong cấu trúc dữ liệu riêng của nó (private data structures), và trở về một con trỏ trỏ tới khối nhớ heap đó. Caller bây giờ tự do sử dụng vởi tham chiếu của con trỏ. Khối nhớ được đảm bảo là dành riêng quyền sử dụng cho caller - heap sẽ không trao vùng nhớ đó cho bất kì caller nào khác. Khối không di chuyển xung quanh ở trong heap - vị trí của nó và kích cỡ của nó là giới hạn ngay khi nó được cấp phát. Nói chung chung, khi một khối được cấp phát , nội dung của nó là bất kì. Chủ sở hữu mới phải chịu trách nhiệm thiết lập cho bộ nhớ cái gì đó có nghĩa. Thỉnh thoảng hàm cấp phát sẽ thiết lập tất cả khối nhớ là 0 (calloc() trong C).

    # Hàm thu hồi (deallocation function) đối lập với hàm cấp phát. Chương trình cho một lời gọi thu hồi để trả khối nhớ về cho vùng "free" của heap để tái sử dụng "re-use" sau đó. Mỗi một khối chỉ nên deallocated một lần. Chức năng deallocation làm cho tham biến là con trỏ trỏ tới heap mất vùng nhớ mà được cung cấp bởi chức năng allocation trước đó. Sau khi deallocation thì con trỏ phải trỏ chính xác vào khối nhớ giống như con trỏ trước đó đực cung cấp bởi chức năng allocation, mà không phải bất kì con trỏ nào trong block. Sau khi deallocation, chương trình xử lý pointer như "bad pointer" và không được truy cập vào pointee đã bị deallocated.


.Những đặc biệt trong C


Trong ngôn ngữ C, thư viện hàm thực hiên yêu cầu cho heap là malloc() (memory allocate) và free(). Nguyên mẫu cho những hàm trên trong file header <stdlib.h>. Mặc dù là cú pháp khác nhau giữa các ngôn ngữ nhưng chức năng của malloc() và free() trong mọi ngôn ngữ là tương tự nhau:
# void* malloc(unsigned long size); hàm malloc() lấy tham số truyền và là unsigned integer tượng trưng cho yêu cầu về kích thước của khối đo bằng bytes. Malloc() trả về một con trỏ trỏ tới khối nhớ mới trong heap nếu cấp phát thành công, và NULL nếu yêu cầu không đươc đáp ứng bởi vì heap đã đầy. C cung cấp toán tử sizeof() là một các thuận tiện để tính kích cở với byte của kiểu dữ liệu - sizeof(int) là kích cỡ của pointee kiểu int ... 

# void free(void* heapBlockPointer); hàm free() lấy con trỏ trỏ tới khối nhớ heap và trả nó lại vùng free để sau này tái sử dụng "re-use". Con trỏ qua free() phải chính xác là con trỏ trả về do malloc() trước đó, không phải là con trỏ trỏ nơi nào đó trong block. Tức là gọi free() và malloc() thì con trỏ vẫn  thế không thay đổi chỉ khác là pointee không được truy cập vào nữa. Gọi hàm free() với các loại lỗi sai của con trỏ là nổi tiếng đặc biệt kinh khủng với loại crashing mà nó dẫn đến. Lời gọi tới free() không cần cho kích cỡ của khối heap - trình quản lý heap sẽ tự động lưu ý kích cỡ trong private dât structures. Lời gọi tới free() chỉ cần xác định khối nào cần deallocate, bởi con trỏ của nó. Nếu chương trình deallocate đúng tất cả vùng nhớ mà nó allocate, thì sau đó mọi lời gọi đến malloc() sau đó sẽ được xuất hiện bời chính xác một lời gọi free() là một vấn đề thực tế, tuy nhiên nó không phải luôn luôn cần thiết cho một chương trình để dellocate mọi khối mà nó allocate - Hãy xem "Memory Leaks" bên dưới.

.Ví dụ đơn giản về heap


Đây là một ví dụ đơn giản thứ mà nó cấp phát một khối kiểu int trong heap, lưu số 42 vào trong khối đó, và sau đó deallocate nó. Đây là ví dụ đơn giản nhất có thể của heap với ba công đoạn : cấp phát (allocation), sử dụng (use), và giải phóng (deallocation). Ví dụ chỉ ra tình trạng của bộ nhớ tại ba lần khác nhau trong suất thời gian thực thi của code bên dưới. Stack và heap cần phân biệt giữa hai vùng để thật chính xác với vì hai khu vực rất khác nhau. Trong trường hợp đó vòng đời của biến local intPtr hoàn toàn tách biệt với vòng đời của khối nhớ trong heap phân cho nó và hình vẽ vần phản chiếu lại điều khác nhau đó.
 

 Những chú ý cơ bản của heap

  # Sau khi allocation gọi và cấp phát một khối trong heap. Chương trình lưu con trỏ trỏ tới block đó vào trong biến local intPtr. Khối này là pointee và intPtr là con trong của nó (được chỉ trong T2). Trong trạng thái này, con trỏ có lẽ được được dereferenced an toàn để điều khiển pointee."Bộ luật" pointer và pointee trong phần 1 đã được áp dụng, chỉ có một điều khác nhau duy nhất là cách mà pointee được khởi tạo cấp phát ban đầu.

  # Tại T1 trước khi gọi malloc(), intPtr không được khởi tạo không có pointee - tại điểm này inPtr "bad" giống hoàn cảnh như đã bàn ở phần 1. Như trước dereferencing với một con trỏ không được khởi tạo là một phổ biến , nhưng lỗi thàm khốc. Thỉnh thoảng  lỗi này gây crash ngay tức thì (trường hợp này may mắn). Lần khác nó sẽ làm hỏng một cấu trúc dữ liệu bất kì (trường hợp không may mắn.)

  # Lời gọi đến free() giải phóng POINTEE như được chỉ ra tại T3, hãy nhớ đây là giải phóng pointee nên nó được giải phỏng bởi tất cả các pointer đang chỉ vào nó. Sự tham chiếu của pointer sau khi pointee bị deallocated là một lỗi. 
  Thật không may , lỗi này phần lớn không được gắn cờ như một cách trực tiếp nên nó là lỗi run-time, chỉ thấy khi chạy. 99% số lần tham chiếu (sử dụng * truy cập vào vùng nhớ là con trỏ đang trỏ tới) sẽ cho một kết quả hợp lý, 1% còn lại của tham chiếu sẽ cho kết quả sai. Vậy chắc chắn, một lỗi hiếm khi xuất hiện là loại khó nhất để theo dõi.

  # Khi function kết thúc, biến local của nó intPtr sẽ tự động deallocated đi với điều luật thướng thấy ở phần 1 . Vì vậy function này có một hành vi bộ nhớ gọn gàng - Tất cả bộ nhớ của nó allocate trong khi chạy (bieens local của nó và heap block của nó)được deallocated khi nó kết thúc.

Cảm ơn các bạn đã dành thời gian để theo dõi .

Xem phần tiếp theo tại : Con trỏ và bộ nhớ [3] - Bộ nhớ heap - sử dụng và lưu ý .

Không có nhận xét nào:

Đăng nhận xét