Tại sao lại có Stack và Heap ạ?
Người ta không đặt cái Stack và Heap mà hiện tại em biết lên bàn, rồi sau đó làm chúng vào trong máy tính. Sự thật là ngược lại, người ta gặp một vấn đề, người ta tìm ra cách giải quyết, cách giải quyết đó tốt và được dùng rộng rãi, rồi cách đó cần một cái tên. Stack và Heap thế là ra đời.
OK ý thầy là sẽ dài dòng, em sẵn sàng rồi đây ạ.
Chúng ta biết rằng đặc điểm chung của các đơn vị tính toán, như là một cái máy tính, một chương trình, một hàm… nằm ở cách chúng hoạt động. Dù bằng cách nào đi chăng nữa, chúng đều sẽ nhận thông tin từ bên ngoài chúng, lưu trữ vào bên trong, xử lý, và rồi lại xuất kết quả ra bên ngoài.
Vâng, một thiết bị phần cứng phải có đủ bốn yếu tố đó thì mới được gọi là một cái máy tính. Các chương trình và ứng dụng cũng tương tự.
Stack và Heap là nói đến cách mà chương trình lưu trữ các dữ liệu dùng để xử lý của nó.
Dữ liệu dùng để xử lý?
Dữ liệu đựng trong database thì cũng là dữ liệu, nhưng chỉ khi dữ liệu trong database được chương trình nạp lên để làm việc gì đó thì ta gọi là dữ liệu dùng để xử lý.
À vâng, ý là dữ liệu nằm trong memory của chương trình.
Chuẩn, chương trình được hệ điều hành cấp cho một không gian nhớ, ta gọi là memory. Thường thì memory nằm ở trên RAM nhưng cũng có thể là ở swap hay tương tự, việc này nói chung chương trình không biết được. Ta có thể coi memory như một mảng các byte.
Mảng ạ?
Đúng vậy, về cơ bản memory là một mảng. Mỗi phần tử trong mảng là một ô nhớ, mỗi ô nhớ có 8 bit. Các ô nhớ được đánh thứ tự, máy tính sẽ quản lý các ô nhớ thông qua thứ tự của chúng. Nếu con từng nghe tới khái niệm hệ điều hành 32-bits hay 64-bits thì chính là đang nói tới việc nó dùng bao nhiêu bit để đánh số thứ tự ô nhớ.
Xem nào, 32 bit thì sẽ quản lý được (2 ^ 32 - 1) / 1024 / 1024 /1024 = 3.9 (GB), đúng thế nhỉ, giới hạn RAM hiệu dụng của các hệ điều hành 32-bits là dưới 4GB.
Ừm, đúng đấy. Quay lại, khi chương trình cần lưu dữ liệu của, chẳng hạn câu trả lời cho câu hỏi Nhập năm sinh của bạn:_, nó sẽ tìm một số ô nhớ nào đó chưa dùng đến trên memory để ghi chứa.
Vậy thì khi tạo một biến, biến đó sẽ gắn với một vị trí của ô nhớ của nó trên mảng ô nhớ?
Đúng thế, kết hợp các vị trí của các biến với độ rộng bit của chúng, chương trình sẽ biết được những ô nhớ nào trong memory đã được sử dụng.
Độ rộng bit?
Kiểu dữ liệu ký tự cần 8 bit, kiểu số nguyên cần 32 bit, chẳng hạn vậy.
À vâng. Vậy là khi ta khai báo một biến, trình thông dịch sẽ đánh dấu một số ô nhớ nào đó là đã được sử dụng. Nhưng sau đó làm thế nào nó biết ô nhớ nào không còn được sử dụng nhỉ. Cứ tạo mãi chả mấy chốc mà hết.
Trên thực tế, trong những ngày đầu của khoa học máy tính, các trình thông dịch không biết được việc ấy, các lập trình viên phải tự quản lý lấy.
Bằng cách nào ạ?
Ngôn ngữ lập trình cung cấp một số từ khóa để giải phóng bộ nhớ cho một số biến nào đó.
Còn bao giờ sử dụng thì lập trình viên tự suy nghĩ lấy ạ?
Đúng thế!
Vất vả nhỉ?
Vất lắm. Đặc biệt là khi có nhiều subroutine, hay còn gọi là hàm và thủ tục ấy, ra đời.
Tại sao lại “đặc biệt là…”?
Cứ thử tưởng tượng một biến tạo ở trong subroutine sẽ cần phải được giải phóng khi kết thúc. Nếu quên giải phóng là sẽ tràn memory hoặc tệ hơn là ghi đè vào một ô nhớ của một biến khác. Có trời mới biết chuyện gì sẽ xảy ra.
Đấy là vấn đề cho Stack và Heap thầy nói lúc nãy đúng không ạ?
Đúng vậy, ở đây là cơ chế Stack. Stack ở đây chính là cấu trúc dữ liệu stack mà con vẫn biết, vào cuối cùng, ra đầu tiên. Trình thông dịch sẽ tạo ra một stack trong memory, và dùng stack đó để lưu chứa dữ liệu trong khi hoạt động của chương trình.
Là như thế nào?
Mỗi khi lập trình viên tạo một biến, biến đó sẽ được cho vào stack.
Rồi sao nữa ạ?
Khi kết thúc một hàm, tất cả các biến được tạo ra bởi hàm đó sẽ cần được giải phóng. Với stack thì việc này vô cùng đơn giản.
À, một cách giải phóng bộ nhớ tự động.
Đúng vậy, cách này rất đẹp. Tất cả các giá trị mà các chỉ lệnh của một hàm có thể đọc được đều nằm trên stack, trên những ô nhớ nằm dưới hàm đó trong stack. Điều này được phát biểu thành khái niệm “phạm vi hoạt động của biến”.
À, hàm cha gọi hàm con thì biến của hàm con sẽ nằm trên, nên hàm cha không đọc được. Nhưng hàm con thì ngược lại.
Đúng vậy.
Chỉ thế thôi ạ?
Về Stack chỉ có thế thôi. Một cấu trúc dữ liệu phù hợp đã giải quyết được một núi vấn đề. Nhưng vấn đề vẫn chưa hết.
Chưa hết?
Do bản chất của mình, Stack sẽ là một vùng nhớ liên tục trong memory.
Các ô nhớ của Stack nằm liên tục nhau trong memory, như thế máy tính sẽ giải phóng ô nhớ một cách rất dễ dàng, đơn giản bằng cách lùi con trỏ lại, chuyện này dễ hiểu. Nhưng vấn đề ở đây là gì ạ?
Dầu tiên sẽ là dung lượng của Stack cần phải được cấp phát ngay từ đầu.
Đúng thật vậy, nếu không thì sẽ gặp phải trường hợp một chương trình nào đó khác ghi dữ liệu vào ô nhớ nằm ngay trên Stack, và chương trình sẽ rất dễ bị tràn bộ nhớ ngay sau đó.
Lượng bộ nhớ cấp phát này có thể phụ thuộc vào hệ điều hành, cũng có thể phụ thuộc vào cấu hình của chương trình, nhưng nói chung là nó cần được tính toán cẩn thận. Ngoài ra còn vấn đề thứ hai nghiêm trọng hơn đó là không thể “nở” hay “co” một biến dữ liệu đã cấp phát được.
Nở, co?
Hãy nghĩ đến việc phép cộng chuỗi.
À con hiểu rồi, nếu một chuỗi được tạo ra trên Stack, những chỉ lệnh sau đó sẽ không thể tăng hay giảm chiều dài của chuỗi một cách dễ dàng được, sẽ phải sắp xếp lại tất cả các biến nằm phía trên chuỗi trong Stack. Thế thì hiệu năng thấp lắm.
Stack được thiết kế sử dụng với hiệu năng phải thật là cao, nên phương án đó không được lựa chọn, kết quả là biến string, hay cụ thể hơn là các dữ liệu mà có độ dài có khả năng thay đổi trong tương lai, sẽ không được đặt tại stack. Stack chỉ chứa những dữ liệu có độ dài vĩnh viễn không thay đổi, chẳng hạn bool, int, double…
Những kiểu nguyên thủy?
Đúng vậy, những dữ liệu của kiểu nguyên thủy sẽ được đặt tại Stack, Stack chỉ chứa các dữ liệu của các kiểu nguyên thủy.
Thế còn các dữ liệu của các kiểu dữ liệu khác?
Chúng được đặt tại một vùng nhớ khác, hỗn độn, vô định, người ta đặt tên gọi là Heap (đống). Bởi vô định hình nên dữ liệu trên Heap có thể nở bất kỳ lúc nào mà không gây ra ảnh hưởng quá nhiều đến hiệu năng tổng thể.
Nằm ngoài Stack, trong một vùng nhớ vô định hình, thế bài toán về giải phóng bộ nhớ lại trở lại ạ?
Đúng một nửa. Vẫn có một biến được tạo ra tại Stack, nhưng thay vì chứa dữ liệu giá trị thì nó chứa dữ liệu về vị trí của dữ liệu giá trị. Thông qua vị trí này mà hàm tìm đến được dữ liệu đang nằm trên Heap để sử dụng cho xử lý. Nếu các hàm cần chuyển dữ liệu cho nhau, chúng chỉ cần chuyển dữ liệu về vị trí. Chúng ta thường gọi dữ liệu trên Stack là tham trị, và dữ liệu về vị trí của một khối dữ liệu nằm trên Heap là tham chiếu.
Có phải liên quan đến truyền tham trị và truyền tham chiếu không ạ?
Chính là nó. Khi các hàm truyền tham số cho nhau, chúng luôn truyền giá trị trên Stack, và hàm nhận tham số sẽ luôn tạo ra một bản sao của giá trị đó vào một biến mới. Chẳng hạn một hàm f1 truyền một biến x cho hàm f2, f2 sẽ luôn tạo ra một bản sao cho giá trị trên Stack của x. Nếu x là kiểu nguyên thủy thì giá trị của x là tham trị, nếu x không phải kiểu nguyên thủy, thì giá trị của x là một tham chiếu. Trong cả hai trường hợp thì f2 đều sao chép giá trị trên Stack đó để dùng.
Trong cả hai trường hợp, giá trị mà f2 tạo ra đều sẽ được giải phóng sau khi f2 chạy xong, và điều đó không ảnh hưởng gì đến x cả.
Đúng vậy, chính xác hơn thì không ảnh hưởng gì đến giá trị tham chiếu nằm trên Stack. Nhưng nếu f2 có thông qua tham chiếu để chỉnh sửa gì đó đến giá trị nằm trên Heap thì tất cả các chỉ lệnh đang dùng cùng một tham chiếu này đều sẽ nhận được ảnh hưởng.
Con đang liên tưởng đến truyền object vào hàm.
Chính thế. Các object không phải là dữ liệu nguyên thủy, tất cả chúng đều được đặt tại Heap. Chúng ta luôn truy cập tới object thông qua tham chiếu.
Nếu mà đặt object trên Stack, chưa kể đến vấn đề co hay nở, chỉ riêng chuyện object đó sẽ bị giải phóng khi hàm chạy xong và khiến tất cả các tham chiếu trỏ đến nó sẽ hỏng hết thôi cũng đủ sợ rồi.
Đúng vậy. Không bao giờ có chuyện tham chiếu đến thứ gì đó trên Stack, việc đó rất nguy hiểm. Tham chiếu đến Heap thì không sao.
Phải ha, tham chiếu trên Stack giống như tấm bản đồ, giá trị trên Heap là địa phương. Bỏ tấm bản đồ đi thì cũng không làm địa phương biến mất được. Nhưng mà bài toán về việc giải phóng bộ nhớ lại quay lại rồi thầy nhỉ.
Đúng vậy, các object nằm trên Heap không thể được giải phóng một cách dễ dàng như với Stack được. Một số ngôn ngữ lập trình, ví dụ C, sẽ yêu cầu lập trình viên tự quản lý Heap lấy.
Nghĩa ra cứ bao giờ tạo dữ liệu trên Heap thì sẽ phải thiết kế một lúc nào đó giải phóng nó đi.
Đúng vậy, và nếu giải phóng thất bại thì sẽ tạo thành thứ được gọi là memory leak.
Rò rỉ bộ nhớ, là thế ấy ạ?
Ô nhớ đó không được chương trình dùng đến nữa, nhưng cứ như là vẫn đang được dùng, trông cứ như là dữ liệu của chương trình “rỉ” ra ngoài. Nhiều chuyện phết đấy, bộ nhớ có thể bị tràn mà không làm gì được.
Khó nhỉ, về cơ bản thì dữ liệu trên Heap rất là global, như vậy thì rất khó mà nghĩ ra được lúc nào thì nó mới không được dùng.
Đúng là rất khó, đặc biệt là khi lập trình hướng đối tượng, bởi luồng thực thi của chương trình không còn tuyến tính một chiều nữa. Phương pháp khả thi nhất là liên tục để ý xem có bộ phận dữ liệu nào trên Heap mà không còn có tham chiếu nào trên Stack chỉ đến nó nữa không.
Ah, không còn tham chiếu nào chỉ đến thì chương trình không có cách nào dùng được, vậy thì bỏ đi. Nhưng “bộ phận” là sao ạ?
Có thể có những dữ liệu nào đó trên Heap mà chúng tham chiếu đến nhau. Nhưng tổng thể thì không có tham thiếu nào trên Stack đi đến chúng cả. Chúng ta gọi tham chiếu lẫn nhau trên Heap là tham chiếu vòng.
Ok đại loại là lâu lâu lại quét Heap một lần.
Đúng vậy, việc này có thể tự động hóa được vào cho trình thông dịch. Và những chương trình làm sạch Heap như thế được gọi là Garbage Collection.
Ahhhh.
Vấn đề thứ ba của Stack là nó là nó không đáp ứng được cho tính toán đồng thời. Con có thể đoán xem tại sao.
Nếu một Stack cùng được sử dụng bởi hai hàm cùng một lúc thì tính năng của nó sẽ mất hết. Sẽ không thể giải phóng bộ nhớ ngay khi một hàm kết thúc (phải chờ hàm đang giữ những ô nhớ phía trên làm xong đã). Sẽ không thể có hiệu năng cao.
Đúng thế, cho nên cứ mỗi thread của chương trình sẽ được cấp phát một Stack…
Và sẽ không thể tạo ra các biến hoàn toàn toàn cục được. Sẽ là thảm họa nếu muốn làm thư gì đó như là lập trình hướng đối tượng. Cơ mà vấn đề này Heap cũng đã giải quyết được luôn rồi.
Con hiểu nhanh đấy.
