[운영체제] 03. Stack and Dynamic Memory Allocation of Local Variables

출처 서울대학교 홍성수 교수님, [K-MOOC] 운영체제의 기초, 3주차 Stack and Dynamic Memory Allocation of Local Variables

03-1. 스택 Stack

하드웨어적으로는 Interrupt가 중요하다면 소프트웨어에서는 Stack이라는 데이터 구조가 중요하다.

프로그래밍 수행을 하기 위해서 스택을 사용하는 것은 현대적인 프로그래밍 언어의 모델에서부터 왔다.

스택의 여러 가지 동작을 조작하는 것이 os를 구현하는 데 있어 굉장히 중요한 테크닉이다. 프로그램이 수행되려면 반드시 스택이 있어야 한다는 것을 이해해야 한다.

스택이 필요한 부분은 로컬 변수가 동적으로 메모리가 할당이 되고 반환될 때이다.

전역 변수와 지역 변수

C 프로그램의 변수를 크게 두 가지로 나눌 수 있다.

전역 변수 global variable

함수 외부에서 선언된 변수를 의미한다.

지역 변수 local variable

함수 내부에서 선언된 변수를 의미한다.

어떤 변수가 전역 변수인지 지역 변수인지에 따라 어떤 차이가 있는가?

1. 공간적인 측면 scope

프로그래밍의 어떤 영역에서 특정 변수에 접근할 수 있는가?

- 전역 변수: 프로그램의 어디에서나 그 변수에 접근이 가능하다. - global scope를 갖는다.

- 지역 변수: 그 변수가 선언된 함수의 block내부에서만 사용 가능하다. - local scope를 갖느나.

2. 시간적인 측면 extant

프로그램의 어느 시점에서 특정 변수에 접근할 수 있는가?

- 전역 변수: 프로그램이 메모리에 적재되어 수행을 시작했을 때부터 그 프로그램이 수행을 종료할 때까지 전체 프로그램 라이프사이클 동안 접근 가능하다. - static extant를 갖는다.

- 지역 변수: 프로그램의 존재와 무관하게 자신이 선언된 함수가 호출돼서 active하게 됐을 때부터 그 함수로부터 return할 때까지 함수가 수행되는 동안에만 접근 가능하다. - dynamic scope를 가진다.

*동일한 함수라도 여러 번 호출될 수 있는데, 이 경우 여러 번 짧게 동적으로 라이프사이클을 가지게 된다.

3. 변수의 메모리 할당 측면

변수의 메모리를 어떻게 할당하는가?

- 전역 변수: 프로그램이 os에 의해 메모리에 적재될 때 그때 글로벌 변수를 할당하고, 프로그램 수행 종료될 때 모든 자원 반환할 때 글로벌 변수의 메모리 공간을 반환하게 하면 된다. - 정적 할당

- 지역 변수: 함수 호출될 때 로컬 변수가 메모리 할당을 받고 함수가 리털할 때 로컬 변수가 가지고 있는 메모리 반환. - 동적 할당

지역 변수의 메모리 할당 문제

C언어 같은 고급 프로그래밍 언어로 프로그래밍할 때, 프로그래머는 코드에서 함수와 변수라는 두 entity에 이름을 부여한다. 이처럼 프로그래머가 프로그램에서 부여한 이름을 symbol이라고 한다.

그런데 고급 언어로 작성된 프로그램이 컴파일러에 의해 컴파일되면 symbol은 더 이상 존재하지 않는다. 프로그램은 바이너리 넘버 시퀀스로 된 실행 파일이 된다.

- 함수: 함수 이름은 함수의 시작 주소로 대체된다. 함수 호출은 함수 시작 주소로 점프하는 인스트럭션이다.

- 변수: 변수를 표현하는 심볼 역시 변수가 메모리에 적재된 위치. 주소로 변하게 된다.

심볼을 주소로 변하게 하는 작업은 컴파일러가 하게 된다. 이때 중요한 전제는 컴파일러가 심볼들의 주소를 미리 알아야 한다는 점이다. 글로벌 변수는 주소를 쉽게 알 수 있다. 프로그램 주소 특정 위치에 할당이 되기 때문이다. 코드의 주소를 알 수 있다.

문제는 지역 변수이다. 지역 변수는 동적으로 임의의 위치에 할당되기 때문에 컴파일러가 컴파일하는 단계에서는 지역 변수의 주소를 알지 못한다. 이 문제는 바로 스택을 통해 해결한다.

로컬 변수의 메모리 동적 할당은 하드웨어적으로 일어날까, 소프트웨어적으로 일어날까?

인텔 프로세서도, OS도 자기 위에서 C 코드가 돌지 어셈블리 코드가 돌지 알지 못한다.
각 언어의 컴파일러가 소프트웨어적으로 로컬 변수에 동적으로 메모리를 할당한다. 이를 위해 컴파일러가 인스트럭션 세트(어셈블리 코드)를 생성한다.

스택이란

스택이란 "나중에 들어간 원소가 먼저 나오는 원칙에 따라 데이터의 삽입과 삭제가 이루어지는 자료 구조"이다.

<예시> 계산기, 컴파일

자료 구조
여러 데이터가 있을 때 데이터를 저장하는 방식.

- FIFO (First in First Out) 큐
데이터 아이템이 나가는 곳과 큐로 새로 진입하는 곳이 서로 다르다. 양쪽 끝이다.
<예시> 은행, 극장에서 줄 서기 등 일상생활에서 많이 사용됨.

- LIFO(Last In First Out) 큐
데이터 아이템이 들어오는 곳과 나가는 곳이 한곳이다. 스택은 LIFO 큐이다.
<예시> 엘레베이터.

스택에 데이터 아이템을 넣고 빼는 동작에 이름을 붙여서 operation으로 만들었다.

- push(): 스택에 한 원소를 삽입

- pop(): 스택에서 한 원소를 삭제

스택의 구분
어느 방향으로 자라는지에 따라 스택은 두 가지로 구분된다.

바닥이 low memory이고 점점 위로 자라는 스택
가장 위에 있는 데이터 아이템을 가리키는 포인터를 스택 포인터라고 한다. 마이크로 프로세서는 스택 포인터 레지스터를 별도로 두고 있다. 그 레지스터를 esp Stack Pointer Register라고 한다.
스택 포인터가 push함에 따라 그 값이 증가된다.

바닥이 high memory이고 점점 아래로 자라는 스택
스택에 데이터 아이템이 쌓이면(push 작업이 이루어지면) 스택 포인터 값은 작아진다.

*스택은 모습은 마이크로 프로세서 설계자가 결정한다. 인텔의 스택은 바닥이 high memory이다.

03-2. 지역 변수의 동적 메모리 할당 Dynamic Memory Allocation of Local Value

C언어 프로그램에 2개의 formal parameter(매개 변수)의 값을 더해서 결과 값을 res라는 변수에 저장하는 add() 함수가 있다고 해 보자. 32-bit 워드 인텔 프로세서( IA-32 프로세서)에서 C코드가 돌아간다.

main()
{
	int a = 2, b = 13;
    int res;
    res = add(a, b);
    
    int add(int x, int y)
    {
    	int r;
        r = x + y;
        return r;
    }

글로벌 변수는 없다. main의 로컬 변수 a, b, res가 있고, add의 로컬 변수 r이 있는 상황이다. C코드에서 int의 사이즈는 타겟 머신의 워드 사이즈로 결정된다. int 변수들은 1워드인 4바이트씩 차지하게 된다.

이 로컬 변수들이 동적으로 메모리 할당되는 것을 보려면 어셈블리 코드를 봐야 한다.

- push: 스택임을 보여 준다.

- L: long이라는 뜻 16비트 시절에 비해 32비트가 길다는 뜻이다. (무시해도 된다.)

- %: CPU의 레지스터를 표현이다. ebp(base pointer register), esp(stack pointer register)

- $: 상수를 표현한다.

- (%~): 그 레지스터가 가지고 있는 값이 주소이고, 그 주소로 메모리 로케이션을 표현하는 것이다.

main 함수

관습상 C 언어에서 main 함수는 진입점 entry point, 처음 수행되는 함수라고 얘기한다.

pushl %ebp
: %ebp 레지스터의 값이 스택에 들어간다. = ebp 레지스터의 값이 뭔지는 모르지만, 스택에 대피시켜 놓는다.
-> 이에 따라 바닥을 가리키는 스택 포인터 레지스터 %esp의 값은 -4가 될 것이다.

*어떤 인스트럭션이 레지스터의 값을 스택에 push했다는 것은 곧, 그 레지스터가 다른 용도로 사용이 돼서 값을 잃어버릴 것임을 의미한다. 레지스터가 원래 가지고 있던 값은 안전한 곳인 스택에 대피시켜 놓고 그 레지스터를 다른 용도로 사용하고자 할 때 스택에 레지스터의 값을 push하게 된다.

movel %esp, %ebp
: esp(stack pointer)의 값을 ebp로 카피한다.
-> 이에 따라 ebp도 esp와 같은 곳을 가리키게 된다.

main 함수의 지역 변수 a, b를 선언(메모리 할당)하고 값을 초기화하기
sub $12, %esp
: esp에서 12만큼 뺀다.

12의 의미는 세 숫자 변수의 크기이다.

* 변수 할당 순서는 함수에서 제일 먼저 나온 변수부터 할당된다. positional allocation

movl $2, -4(%ebp)

movl $13, -8(%ebp)
변수에 값을 넣는다.
-> a변수와 b변수의 주소는 어떻게 알 수 있을까?
a 변수는 ebp에서 -4만큼 떨어진 곳

b 변수는 ebp에서 -8만큼 떨어진 곳이다.

*동적으로 할당되는 지역 변수의 주소는 ebp 레지스터 상대적인 주소로 표현할 수 있다. 이렇게 하면 절대 주소를 몰라도 코드 생성이 가능하다.

*ebp는 베이스 포인터 레지스터이다.

어떤 메모리 청크의 바닥 주소를 가리킨다. 그 메모리 청크란 어떤 함수가 호출됐을 때 그 함수가 수행되기 위해 필요한 스택상 메모리 공간, 청크의 바닥을 가리킨다.

이 청크를 activation record라고 한다. 운영체제에서는 그 함수의 스택 프레임이라고 한다.

add 함수의 매개 변수에 메모리를 할당하고 값 넣기

movl -8(%ebp), %eax
: add 함수의 formal parameter에 actual parameter를 패싱해기 전에 formal parameter의 메모리 할당을 한다.
(%ebp)-8의 값, 다시 말해서 로컬 변수 b의 값 ax 레지스터에 옮긴다.

pushl %eax

: b값이 저장된 ax 레지스터의 값을 스택에 푸시한다.

-> y=b 이렇게 저장된다. add 함수의 두 번째 로컬 변수에 할당된 곳이다.

*ax, dx, 레지스터 등은 general purpose 레지스터이다. 데이터 인터미디어 데이터 값을 저장할 수 있는 임의의 레지스터다.

move -4(%ebp), %eax
: (%ebp)-4, 다시 말해서 로컬 변수 a가 가리키고 있는 메모리 공간에 있는 값을 가져다가 ax에 넣는다.

pushl %eax

: a값이 저장된 ax 레지스터의 값을 스택에 푸시한다.

-> x=a 이렇게 저장된다. add 함수의 첫 번째 로컬 변에 할당된 곳이다.

add 함수 호출하기

call add

: add 함수를 호출한다.

어셈블리 함수에서 함수 호출(function call)이란 점프 인스트럭션과 같다. 단, 다른 점은 함수가 끝나면 resume할 주소를 안전한 곳 저장해놓고 간다.
메인함수의 resume할 주소는 call 인스트럭션 다음 줄이다. 폰 노이먼에서 다음 인스트럭션의 주소는 프로그램 카운터 레지스터에 저장된다.
-> 스택의 top에 return address인 다음 인스트럭션의 주소가 들어있게 된다.

add 함수(main 함수에서 add 함수로 이동함)

pushl %ebp

: 메인 함수와 똑같이 push로 ebp를 저장한다.

add함수의 activation record의 바닥을 가리켜야 하는데 지금 ebp는 메인 함수의 바닥을 가리킨다.
그래서 원래 ebp 값을 저장해놓는다.

movel %esp, %ebp

: esp 주소를 ebp로 카피하여 add함수의 바닥 값을 설정한다.

add 함수의 지역 변수 r을 선언(메모리 할당)하고 값을 초기화하기

sub $4, %esp

: add 함수의 로컬 변수 r의 자리를 할당한다.

add 함수의 매개 변수에 메모리를 할당하고 값 넣기

movl 8(%ebp), %eax

: add 함수의 첫 번째 매개변수 자리를 할당한다.

movl 12(%epb), %eax

: add 함수의 번째 매개변수 자리를 할당한다.

*매개변수 리스트의 역순으로 메모리를 할당한다. 인텔 프로세서용 C 컴파일러의 관습이다.

먼저 나온 매개변수가 더 작은 offset을 가지도록 한 것이다.

add 함수의 더하기 연산 수행하고 변수 r에 결과 값 저장하기

leal (%edx, %eax), %ecx

: eax 레지스터와 edx 레지스터의 값을 더하는 연산 수행하기

*load effective address 인스트럭션은 사실 주소 연산을 할 때 사용하는 것인데, C 컴파일러가 이 인스트럭션을 사용한다.

movl %ecx, -4(%ebp)

: 연산 결과를 지역 변수 r에 복사한다.

리턴할 값을 edx 레지스터에 카피하고, 그 값을 eax 레지스터에 카피하기

mov -4(%ebp), %edx

: (%ebp)-4의 값, 다시 말해서 변수 r의 값을 edx 레지스터에 복사한다.

movl %edx, %eax

: edx의 주소를 eax로 복사한다.

*인텔 프로세서용 C 컴파일러는 관습상 함수의 리턴값을 반드시 ax 레지스터에 넣어서 저장하게 되어 있다.

개선의 여지가 필요한 부분

연산의 결과를 ecx 레지스터에 저장하지 않고 바로 eax에 저장하고, eax의 값을 r의 값인 -4(%ebp)에 카피했다 마지막 두 인스트럭션은 불필요하다.
C 컴파일러가 가지고 있는 한계이다. c컴파일러가 코드 제네레이한 다음에 불필요한 리던던트한 인스트럭션을 제거해준다. 이를 컴파일 최적화라고 하는데 아무리해도 어쩔 수 없이 남아 있는 코드들이 있다. 그런 것의 일종이다.

main 함수로 돌아갈 준비하기

스택 포인터 값을 ebp 값으로 치환시킨다.

-> add함수의 r이라는 지역 변수가 delocate된다.

jmp .L2

.L2:

movl %ebp, %esp

: activation record의 바닥을 가리키는 레지스터 값을 복원하기

-> esp가 스택의 탑을 가리키게 된다.

popl %ebp

: 스택의 탑에 있는 주소를 꺼낸다. 메인 함수에서 수행을 resume할 주소이다.

ret

: 리턴 인스트럭션에 의해 메인으로 돌아온다.

main 함수(add 함수의 리턴 값을 받은 뒤 main 함수로 이동함)

add 함수 매개변수를 위해 할당했던 메모리 반환하기

addl $8, %esp

: esp에 8을 더해서 매개변수 2개의 자리 없애

res 변수에 리턴 받은 값 저장하기

movl %eax, %eax

movl %eax, -12(%ebp)

: add 함수로부터 리턴받은 eax의 값을 res 변수에 카피한다.

main 함수 리턴하기

movl %ebp, %esp

: ebp의 주소를 esp의 주소로 카피한다.

-> esp가 스택의 바닥을 가리키게 된다.