Bài 14.2: Stack frame và bộ nhớ ngăn xếp trong C++

Chào mừng các bạn quay trở lại với chuỗi bài blog của chúng ta về C++! Hôm nay, chúng ta sẽ đi sâu vào một khía cạnh cực kỳ nền tảng của cách chương trình C++ (và nhiều ngôn ngữ khác) hoạt động dưới "mũ", đó là bộ nhớ ngăn xếp (the stack) và cấu trúc cốt lõi của nó: stack frame. Hiểu được hai khái niệm này sẽ giúp bạn nắm vững hơn về cách các hàm được gọi, các biến cục bộ tồn tại như thế nào, và tại sao một số lỗi lại xảy ra (như stack overflow).

Hãy cùng bắt đầu hành trình khám phá "sân khấu" nơi các hàm của bạn biểu diễn nhé!

Bộ nhớ ngăn xếp (The Stack) là gì?

Trong bộ nhớ của một chương trình đang chạy, có nhiều khu vực khác nhau được dùng cho các mục đích cụ thể. Hai khu vực quan trọng nhất mà chúng ta thường nhắc đến là stack và heap. Trong bài này, chúng ta tập trung hoàn toàn vào stack.

Stack là một khu vực bộ nhớ được quản lý tự động bởi hệ điều hành và trình biên dịch. Nó tuân theo nguyên tắc LIFO (Last-In, First-Out) – phần tử nào được đặt vào cuối cùng sẽ là phần tử được lấy ra đầu tiên. Hãy tưởng tượng một chồng đĩa: bạn chỉ có thể đặt đĩa mới lên trên cùng và lấy đĩa từ trên cùng xuống.

Mục đích chính của bộ nhớ ngăn xếp là để quản lý:

Các lệnh gọi hàm (Function Calls): Mỗi khi một hàm được gọi, thông tin cần thiết cho hàm đó hoạt động và quay trở lại điểm gọi sẽ được đẩy lên stack.
Các biến cục bộ (Local Variables): Các biến được khai báo bên trong một hàm (không phải biến toàn cục hay biến static) sẽ được cấp phát bộ nhớ trên stack.
Các tham số của hàm (Function Parameters): Các giá trị hoặc địa chỉ của tham số truyền vào hàm cũng thường được đặt trên stack.

Bộ nhớ ngăn xếp có kích thước cố định (do hệ điều hành hoặc trình biên dịch đặt ra, thường là vài MB), và nó được quản lý một cách rất hiệu quả và nhanh chóng. Khi một hàm được gọi, stack "tăng trưởng" lên; khi hàm kết thúc, stack "thu hẹp" lại.

Stack Frame (Khung ngăn xếp) là gì?

Mỗi khi một hàm được gọi trong chương trình của bạn, một cấu trúc dữ liệu cụ thể sẽ được tạo ra trên đỉnh của stack. Cấu trúc này được gọi là stack frame, hay còn gọi là activation record. Có thể hình dung stack frame như một "ngôi nhà" tạm thời cho một lần gọi cụ thể của một hàm.

Mỗi stack frame chứa đựng những thông tin quan trọng sau cho lần gọi hàm đó:

Địa chỉ trả về (Return Address): Đây là địa chỉ trong mã lệnh mà chương trình cần quay trở lại sau khi hàm hiện tại kết thúc thực thi. Khi hàm trả về, bộ xử lý sẽ lấy địa chỉ này từ đỉnh stack frame và nhảy về đó để tiếp tục thực thi mã lệnh ngay sau điểm gọi hàm.
Các tham số của hàm (Function Parameters): Các giá trị hoặc địa chỉ của các tham số được truyền vào hàm.
Các biến cục bộ (Local Variables): Bộ nhớ cho tất cả các biến được khai báo bên trong thân hàm, chỉ tồn tại trong suốt quá trình hàm đó thực thi.
Con trỏ khung (Frame Pointer - FP) hoặc Base Pointer (BP): Một con trỏ trỏ đến đầu hoặc cuối của stack frame hiện tại. Nó giúp hàm dễ dàng truy cập các biến cục bộ và tham số của mình thông qua các offset cố định so với con trỏ này.
Con trỏ ngăn xếp (Stack Pointer - SP): Một con trỏ luôn trỏ đến đỉnh hiện tại của toàn bộ stack. Khi một stack frame mới được tạo, SP di chuyển lên; khi một frame bị loại bỏ, SP di chuyển xuống.
Các thanh ghi (Registers) đã lưu (Saved Registers): Trước khi nhảy vào hàm mới, giá trị của một số thanh ghi quan trọng có thể được lưu lại trong stack frame để phục hồi sau khi hàm kết thúc, đảm bảo trạng thái của hàm gọi không bị ảnh hưởng.

Khi một hàm được gọi, một stack frame mới được tạo và đẩy lên đỉnh stack. Stack Pointer (SP) được cập nhật để trỏ đến đỉnh mới này. Khi hàm kết thúc (trả về hoặc gặp lỗi ngoại lệ), stack frame tương ứng sẽ bị "bỏ" (pop) khỏi stack, SP được di chuyển xuống, giải phóng bộ nhớ đã dùng cho frame đó.

Cách các hàm sử dụng Stack và Stack Frame

Hãy xem xét luồng thực thi của một vài hàm lồng nhau để hiểu rõ hơn cách stack và stack frame hoạt động.

Ví dụ 1: Luồng gọi hàm đơn giản

#include <iostream>

// Hàm thứ ba
void thirdFunction(int z) {
    int local_c = z + 3;
    cout << "      Trong thirdFunction: local_c = " << local_c << endl;
    // Khi thirdFunction kết thúc, stack frame của nó sẽ bị hủy
}

// Hàm thứ hai
void secondFunction(int y) {
    int local_b = y * 2;
    cout << "    Trong secondFunction: local_b = " << local_b << endl;
    thirdFunction(local_b); // Gọi hàm thứ ba
    cout << "    Quay lại secondFunction." << endl;
    // Khi secondFunction kết thúc, stack frame của nó sẽ bị hủy
}

// Hàm đầu tiên
void firstFunction(int x) {
    int local_a = x - 1;
    cout << "  Trong firstFunction: local_a = " << local_a << endl;
    secondFunction(local_a); // Gọi hàm thứ hai
    cout << "  Quay lại firstFunction." << endl;
    // Khi firstFunction kết thúc, stack frame của nó sẽ bị hủy
}

// Hàm chính
int main() {
    int main_var = 10;
    cout << "Trong main: Bat dau." << endl;
    firstFunction(main_var); // Gọi hàm đầu tiên
    cout << "Trong main: Ket thuc." << endl;
    return 0;
    // Khi main kết thúc, stack frame của nó sẽ bị hủy (chương trình kết thúc)
}

Giải thích:

Khi chương trình bắt đầu, hệ điều hành tạo một tiến trình và cấp phát bộ nhớ, bao gồm cả khu vực stack.
Hàm main được gọi. Một stack frame cho main được tạo và đẩy lên stack. Biến cục bộ main_var (giá trị 10) được cấp phát trong frame này.
Bên trong main, hàm firstFunction được gọi với tham số là giá trị của main_var (là 10).
Một stack frame mới cho firstFunction được tạo và đẩy lên đỉnh stack, phía trên frame của main. Tham số x (giá trị 10) và biến cục bộ local_a được cấp phát trong frame của firstFunction. Địa chỉ trả về (trong main) cũng được lưu lại trong frame này.
Bên trong firstFunction, hàm secondFunction được gọi với tham số là giá trị của local_a.
Một stack frame mới cho secondFunction được tạo và đẩy lên đỉnh stack, phía trên frame của firstFunction. Tham số y và biến cục bộ local_b được cấp phát trong frame của secondFunction. Địa chỉ trả về (trong firstFunction) được lưu lại.
Bên trong secondFunction, hàm thirdFunction được gọi với tham số là giá trị của local_b.
Một stack frame mới cho thirdFunction được tạo và đẩy lên đỉnh stack, phía trên frame của secondFunction. Tham số z và biến cục bộ local_c được cấp phát trong frame của thirdFunction. Địa chỉ trả về (trong secondFunction) được lưu lại.
Hàm thirdFunction kết thúc. Stack frame của thirdFunction bị loại bỏ khỏi stack. Con trỏ ngăn xếp (SP) di chuyển xuống. Chương trình sử dụng địa chỉ trả về đã lưu để quay về secondFunction.
Hàm secondFunction tiếp tục thực thi (in "Quay lại secondFunction."). Sau đó kết thúc. Stack frame của secondFunction bị loại bỏ khỏi stack. SP di chuyển xuống. Chương trình sử dụng địa chỉ trả về đã lưu để quay về firstFunction.
Hàm firstFunction tiếp tục thực thi (in "Quay lại firstFunction."). Sau đó kết thúc. Stack frame của firstFunction bị loại bỏ khỏi stack. SP di chuyển xuống. Chương trình sử dụng địa chỉ trả về đã lưu để quay về main.
Hàm main tiếp tục thực thi (in "Trong main: Ket thuc."). Sau đó kết thúc. Stack frame của main bị loại bỏ khỏi stack. SP di chuyển xuống. Chương trình kết thúc.

Lưu ý rằng các biến cục bộ (local_a, local_b, local_c, main_var) chỉ tồn tại trong suốt quá trình tồn tại của stack frame chứa chúng. Khi stack frame bị hủy, các biến cục bộ đó cũng "biến mất" và bộ nhớ được giải phóng. Đây là lý do tại sao bạn không thể truy cập trực tiếp biến cục bộ của một hàm sau khi hàm đó đã trả về.

Ví dụ 2: Biến cục bộ với cùng tên

Stack frame giải thích tại sao hai hàm khác nhau có thể có biến cục bộ cùng tên mà không gây xung đột.

#include <iostream>

void functionA() {
    int counter = 10; // 'counter' này thuộc về stack frame của functionA
    cout << "Trong functionA, counter = " << counter << endl;
} // stack frame của functionA và biến 'counter' bị hủy tại đây

void functionB() {
    int counter = 25; // 'counter' này thuộc về stack frame của functionB (một vùng nhớ khác)
    cout << "Trong functionB, counter = " << counter << endl;
} // stack frame của functionB và biến 'counter' bị hủy tại đây

int main() {
    functionA();
    functionB();
    return 0;
}

Giải thích:

Khi main gọi functionA, một stack frame cho functionA được tạo và biến counter được cấp phát bên trong frame đó. Khi functionA kết thúc, frame này bị hủy.

Khi main gọi functionB, một stack frame mới cho functionB được tạo (tại vị trí mà frame functionA vừa giải phóng, hoặc cao hơn). Biến counter trong functionB được cấp phát bên trong frame mới này. Do đó, hai biến counter này nằm ở hai vị trí bộ nhớ hoàn toàn khác nhau và không ảnh hưởng lẫn nhau.

Ví dụ 3: Đệ quy (Recursion) và sự phát triển của Stack

Đệ quy là một ví dụ điển hình cho thấy stack phát triển như thế nào khi có nhiều lần gọi hàm lồng nhau (mặc dù là cùng một hàm). Mỗi lần gọi đệ quy tạo ra một stack frame mới.

#include <iostream>

void recursiveCountdown(int n) {
    // In ra giá trị n trong lần gọi hiện tại
    cout << "  Goi countdown voi n = " << n << endl;

    // Điều kiện dừng đệ quy
    if (n > 0) {
        // Gọi đệ quy: Tạo stack frame mới cho recursiveCountdown(n-1)
        recursiveCountdown(n - 1);
    }

    // Mã lệnh sau lời gọi đệ quy (chỉ thực thi khi các lời gọi lồng trong nó đã trả về)
    cout << "  Tra ve tu countdown voi n = " << n << endl;
    // Khi hàm kết thúc, stack frame cho lần gọi n hiện tại bị hủy
}

int main() {
    cout << "Bat dau dem nguoc:" << endl;
    recursiveCountdown(3); // Bat dau de quy
    cout << "Ket thuc dem nguoc." << endl;
    return 0;
}

Giải thích:

main gọi recursiveCountdown(3). Frame cho countdown(3) được tạo. n=3 được lưu.
Bên trong countdown(3), nó gọi countdown(2). Frame cho countdown(2) được tạo trên đỉnh frame countdown(3). n=2 được lưu.
Bên trong countdown(2), nó gọi countdown(1). Frame cho countdown(1) được tạo trên đỉnh frame countdown(2). n=1 được lưu.
Bên trong countdown(1), nó gọi countdown(0). Frame cho countdown(0) được tạo trên đỉnh frame countdown(1). n=0 được lưu.
Bên trong countdown(0), điều kiện n > 0 là sai. Hàm không gọi đệ quy nữa mà tiếp tục in ra "Tra ve tu countdown voi n = 0".
countdown(0) kết thúc. Stack frame của nó bị hủy. Chương trình quay lại điểm gọi trong countdown(1).
Bên trong countdown(1), nó tiếp tục sau lời gọi đệ quy, in ra "Tra ve tu countdown voi n = 1".
countdown(1) kết thúc. Stack frame của nó bị hủy. Chương trình quay lại điểm gọi trong countdown(2).
Quá trình này tiếp tục cho đến khi countdown(3) kết thúc và chương trình quay trở lại main.

Bạn có thể thấy stack liên tục "phình to" ra với mỗi lần gọi đệ quy và sau đó "xẹp lại" khi các hàm bắt đầu trả về.

Các vấn đề liên quan đến Stack

Vấn đề phổ biến nhất liên quan đến stack là Stack Overflow (Tràn ngăn xếp). Điều này xảy ra khi chương trình cố gắng sử dụng nhiều không gian trên stack hơn mức đã được cấp phát.

Các nguyên nhân chính gây ra Stack Overflow:

Đệ quy quá sâu: Nếu một hàm đệ quy không có điều kiện dừng hợp lý, hoặc dữ liệu đầu vào khiến nó gọi đệ quy quá nhiều lần, stack sẽ liên tục tăng trưởng và cuối cùng vượt quá giới hạn kích thước của nó.
Khai báo các biến cục bộ quá lớn: Mặc dù ít phổ biến hơn với các kiểu dữ liệu cơ bản, việc khai báo các mảng cục bộ (local arrays) có kích thước rất lớn bên trong một hàm có thể nhanh chóng tiêu tốn không gian stack và gây tràn.

Khi stack overflow xảy ra, chương trình thường bị crash với một lỗi runtime, đôi khi kèm theo thông báo "Stack overflow" hoặc "Segmentation fault".

Bài tập ví dụ: C++ Bài 14.A2: Khoảng cách trên bàn cờ

Khoảng cách trên bàn cờ

FullHouse Dev đang nghiên cứu về khoảng cách trên bàn cờ. Khoảng cách trên bàn cờ giữa hai điểm (X₁, Y₁) và (X₂, Y₂) trên mặt phẳng Descartes được định nghĩa là max(|X₁ - X₂|, |Y₁ - Y₂|).

Bạn được cho hai điểm (X₁, Y₁) và (X₂, Y₂). Hãy tính khoảng cách trên bàn cờ giữa chúng.

Lưu ý rằng |P| biểu thị giá trị tuyệt đối của số nguyên P. Ví dụ, |-4| = 4 và |7| = 7.

INPUT FORMAT

Dòng đầu tiên chứa số nguyên T — số lượng bộ test.
Mỗi bộ test gồm một dòng chứa 4 số nguyên cách nhau bởi dấu cách - X₁, Y₁, X₂, Y₂ - như đã định nghĩa trong đề bài.

OUTPUT FORMAT

Với mỗi bộ test, in ra một dòng duy nhất chứa khoảng cách trên bàn cờ giữa (X₁, Y₁) và (X₂, Y₂).

CONSTRAINTS

1 ≤ T ≤ 1000
1 ≤ X₁, Y₁, X₂, Y₂ ≤ 10⁵

Ví dụ

Input

Output

3
2
2

Giải thích:

Test 1: Khoảng cách giữa (2,4) và (5,1) là max(|2-5|, |4-1|) = max(|-3|, |3|) = 3.
Test 2: Khoảng cách giữa (5,5) và (5,3) là max(|5-5|, |5-3|) = max(|0|, |2|) = 2.
Test 3: Khoảng cách giữa (1,4) và (3,3) là max(|1-3|, |4-3|) = max(|-2|, |1|) = 2.

Làm thêm nhiều bài tập miễn phí tại đây

Comments

There are no comments at the moment.