3. 스택(Stack)

운영체제에서 작성된 유저 프로그램이 수행되기 위해서는 반드시 스택이 필요합니다. 스택의 여러 동작을 조절하는 것이 OS를 구현하는 중요한 테크닉이 됩니다. 프로그램 수행에 있어 스택이 필요한 이유는 현대적인 의미의 프로그래밍 언어 모델 때문입니다.

 

variable에 관련이 있는데 우리가 C 프로그램을 할 때 변수는 크게 2가지로 나누어집니다. global variable과 local variable 이렇게 두 변수로 나뉘는데 이 두 변수는 어떤 차이를 가질까요?

 

공간적인 측면과 시간적인 측면에서 차이점을 가지게 됩니다. 공간적인 측면에서는 프로그램의 어떤 영역에서 변수에 접근할 수 있는지입니다. local variable의 경우 함수 block 내부에서만 access 할 수 있으며 global variable의 경우 어느 곳에서나 그 변수를 access 할 수 있습니다.

 

시간적으로는 global variable의 경우 프로그램이 메모리에 적재되어 수행을 시작했을 때 부터 프로그램이 끝날 때까지 access 할 수 있습니다. local variable의 경우 프로그램의 존재와 무관하게 자기가 선언된 함수가 호출된 후 리턴 될 때까지 access 할 수 있습니다. 함수가 실행되는 동안 접근 가능한 dynamic scope를 갖는 것입니다.

 

또 다른 관점으로는 변수의 메모리 할당에 대해서 생각해 볼 수 있습니다. global variable이 global scope와 global extant를 갖게되는 경우는 OS에 의해 메모리에 적재 될때 입니다. 이후 프로그램이 종료될 때 global variable의 메모리 공간을 반환하게 하면 됩니다. local variable의 경우 함수가 호출되었을 때 메모리를 할당받고 함수가 리턴될 때 반환받으면 됩니다.

 

C나 다른 고급 언어로 프로그래밍할 때 변수나 함수의 이름을 짓게 되는데 실행파일이 되면 이 이름들은 변수가 적재된 메모리 주소나 함수의 시작 주소로 바뀌게 됩니다. 주소로 변경하는 작업은 컴파일러가 실행 전에 수행합니다. 이때 컴파일러는 수행 전에 미리 변수나 함수의 주소들을 전부 알고 있어야 합니다. global variable 같은 경우 특정 위치에 미리 할당되기 때문에 주소를 알 수 있지만 local variable 같은 경우 동적으로 임의의 장소에 할당되기 때문에 컴파일 단계에는 알 수 없습니다.

 

 

 

이런 문제를 해결해 주는 것이 스택입니다. 스택은 데이터를 저장하는 방법 중 하나로 데이터가 나가는 곳과 들어오는 곳이 공유되는 구조를 가집니다. (큐 같은 경우 나가는 곳과 들어가는 곳이 다름)

 

main(){

    int a=2;b=3;
    int res;
    res = add(a, b);

}

// main의 local variable은 a, b, res

int add(int x, int y){

    int r;
    r = x+y;
    return r;

}

// add의 local variable은 r

 

다음과 같이 C++로 코드를 작성해 봤습니다. 이 코드에서는 local variable만 존재하며 int로 4byte를 차지하게 됩니다. 이 변수들의 메모리 할당의 경우 프로세서나 OS는 어떤 언어로 작성된 코드인지 모르기 때문에 컴파일러가 할당하게 됩니다.(소프트웨어적으로 동작)

 

 

어떻게 할당이 이루어지는지 알기 위해서 컴파일러가 생성하는 instruction을 살펴보겠습니다. 위 사진은 main, add 함수의 IA-32 instruction을 따르는 어셈블리 코드입니다. push와 pop instruction이 존재하는데 이를 통해서 스택을 사용한다는 것을 알 수 있습니다.

 

스택은 어느 방향으로 쌓이냐에 따라 두 가지로 나눌 수 있습니다. 첫 번째는 스택의 바닥이 Low 메모리에 있어서 push가 될수록 스택에 데이터가 쌓여 스택 포인터의 값이 증가하게 됩니다. 반면에 두 번째는 스택의 바닥이 High 메모리에 있고 쌓이는 방향이 Low 메모리인 경우 push가 일어날 경우 스택 포인터의 값이 감소하게 됩니다.

 

    - 스택 포인터란 스택의 가장 위쪽 아이템을 가리키는 포인터입니다.

    - 대부분의 CPU에서는 Stack Pointer Register, esp라는 별도의 레지스터에 스택 포인터 값을 저장합니다.

 

 

 

코드에서 push가 진행됨에 따라 초록색 화살표와 같은 순서로 스택 포인터가 감소하게 됩니다. (예제에서 쓰이는 스택은 high 메모리에서 low 메모리로 쌓입니다.) 레지스터의 값을 안전한 곳으로 옮기고자 할 때 스택으로 push를 진행하게 됩니다. 3개의 word가 할당이 되고 각 word는 a, b, res 용으로 사용이 됩니다. 할당 순서는 각각 순서대로 할당되는 positional allocation이 일어납니다.

 

그다음 a와 b의 치환이 일어나는데 치환을 하려면 주소를 알아야 합니다. a의 경우 ebp에서 -4만큼 b의 경우 -8만큼 떨어져 있기 때문에 이를 통해 주소를 알아낼 수 있습니다. 이렇게 동적 할당되는 local variable의 주소를 컴파일 단계에서 결정하지 못하지만 그것을 ebp 레지스터에 relative 한 주소로 표현할 수 있습니다. 

 

    - ebp 레지스터의 주소만 안다면 그 주소를 통해서 local variable의 주소를 알아낼 수 있습니다. (상대 주소)

    - ebp 레지스터는 Base Pointer Register로 스택 프레임의 바닥을 가리킵니다. 

 

 

 

어셈블리 코드에서 function call 이란 call로 함수의 resume 해야 될 주소를 스택에 저장하고 그리고 function으로 점프하는 것입니다. 여기서는 add 함수를 호출하는 시점에서 main 함수의 resume해야 될 주소는 Promgram Counter가 가지고 있습니다. 여기서는 call을 한 순간 add 함수로 점프해야 하기 때문에 스택의 top에 add instruction의 주소가 들어가게 됩니다.

 

 

 

이 스택의 경우 main 함수의 스택 프레임 바닥을 가리키는 ebp는 존재하지만 add 함수의 스택 프레임 바닥을 가르키는 ebp는 존재하지 않습니다. 그래서 다음과 같이 add 함수의 스택 프레임 바닥을 가르키는 ebp를 push 하여 추가합니다.

    - 함수들은 각자의 local variables을 설정하기 위해서 개별적인  ebp를 가집니다.