새싹프로그래머의 이야기

*컴퓨터 구조 및 설계 5th Edition (저자 David A. Patterson 과 John L. Hennessy)를 기반으로 작성되었습니다.

*MIPS 어셈블리언어 기반으로 작성되었습니다.

프로시저(procedure)와 함수(Function)는 이해하기 쉽고 재사용이 가능하도록 프로그램을 구조화하는 방법 중 하나입니다. 프로시저는 프로그래머가 한 번에 한 부분씩 집중하여 처리할 수 있게 도와줍니다. 그리고 프로시저는 소프트웨어에서 추상화를 하는 구현 방법입니다.

프로그램이 프로시저를 실행하는 방법은 다음과 같습니다.

1. 프로시저가 접근할 수 있는 곳에 인수를 넣습니다.
2. 프로시저로 제어를 넘깁니다.
3. 프로시저가 필요로 하는 메모리 자원을 획득합니다.
4. 필요한 작업을 수행합니다
5. 호출한 프로그램이 접근할 수 있는 장소에 결과 값을 넣습니다.
6. 프로시저는 프로그램 내의 여러 곳에서 호출될 수 있으므로 원래 자리로 되돌려줍니다.

*프로시저(procedure): 제공되는 인수에 따라서 특정 작업을 수행하는 서브루틴.

*인수(parameter)는 프로시저에 값을 보내고 결과를 받아오는 일을 처리하므로, 프로그램의 다른 부분 및 데이터와 프로시저 사이의 인터페이스(interface)역할을 수행합니다. 

레지스터는 데이터를 저장하는 가장 빠른 장소이므로 많이 사용하는 것이 바람직합니다. 따라서, MIPS 소프트웨어는 다음의 프로시저 호출 관례에 따라 레지스터 32개를 할당합니다.

MIPS 어셈블리 언어는 레지스터를 할당할 뿐만 아니라 프로시저를 위한 명령어도 제공합니다. 지정된 주소로 점프하면서 동시에 다음 명령어의 주소를 $ra 레지스터에 저장하는 명령으로 jal 명령어(jump-and-link instruction)이라 부른다.

link란, 프로시저 종료 후 올바른 주소로 되돌아올 수 있도록 호출한 곳과 프로시저 사이에 주소 또는 링크를 형성한다는 뜻입니다. 동작 과정을 보면, 먼저 호출 프로그램(caller)은 $a0 - $a3에 전달할 인수 값을 넣은 후 jal X 명령을 이용해서 프로시저 X[피호출 프로그램(callee)라고 부릅니다.] 로 점프 합니다. 그렇게 되면, 피호출 프로그램은 계산을 끝낸 후, 계산 결과를 $v0 - $v1에 넣은 후 jr $ra 명령을 실행하여 복귀합니다.

* 현재 수행 중인 명령어의 주소를 기억하는 레지스터를 프로그램 카운터(program counter)라고 부릅니다. jal 명령은 프로시저에서 복귀할 때 다음 명령어부터 실행하도록 PC+4를 레지스터 $ra에 저장합니다.

컴파일러가 프로시저를 번역하는거에 있어서 인수 레지스터 4개, 결과 값 레지스터 2개만으로는 부족한 경우가 있을 수 있습니다. 프로시저 호출이 다른 부분에 영향을 미쳐서는 안되므로 호출 프로그램이 사용하는 모든 레지스터는 복귀하기 전에 프로시저 호출 전의 상태로 되돌려 놓아야합니다. 데이터 복원을 위해 메모리에 데이터(기존 레지스터 값)를 저장한 후 사용합니다. 즉, '레지스터 스필링'이 필요한 경우입니다. 이를 위해서 자료구조로는 스택(stack)을 사용합니다. 또한 스택을 사용하려면 다음 프로시저가 스필할 레지스터를 저장할 장소나 레지스터의 옛날 값이 저장된 장소를 표시하기 위해 최근에 할당된 주소를 가르키는 포인터가 필요합니다. 이를 스택 포인터(stack pointer)라고 하며, 레지스터 29번을 할당해놓고 있습니다. 스택에 데이터를 넣는 작업을 푸시(push), 꺼내는 작업을(pop)이라고 합니다. 그리고 역사적 선례에 따라서 스택은 높은 주소에서 낮은 주소쪽으로 공간을 할당합니다.

int leaf_example(int g, int h, int i, int j)
{
    int f;

    f = (g + h) - (i + j);
    return f;
}

예를 들어 위와 같은 코드가 있을 때, 임시 레지스터를 통하여 레지스터 스필링을 줄일 수 있습니다. 

첫번째로 t0, t1 레지스터를 원상복구해야한다고 가정했을 때 MIPS 어셈블리 코드는 다음과 같습니다.

leaf_example:

$\qquad addi \quad \$sp\,,\$sp\,,-12$     # 향후 사용할 $t0, $t1, $s0가 사용할 스택 공간 할당

$\qquad sw \quad \$t1\,,8(\$sp)$    # 원상 복구 하기 위해 스택에 레지스터 저장

$\qquad sw \quad \$t0\,,4(\$sp)$   # 원상 복구 하기 위해 스택에 레지스터 저장

$\qquad sw \quad \$s0\,,0(\$sp)$   # 원상 복구 하기 위해 스택에 레지스터 저장

$\qquad add \quad \$t0\,,\$a0\,,\$a1 $     # t0 = g + h

$\qquad add \quad \$t1\,,\$a2\,,\$a3 $     # t1 = i + j

$\qquad sub \quad \$s0\,,\$t0\,,\$t1 $     # f = $t0 - $t1  => (g + h) - (i  + j)

결과 f를 보내주기 위해 결과 값 레지스터에 f를 복사합니다.

$\qquad add \quad \$v0\,,\$s0\,,\$zero$     # return f

호출 프로그램으로 되돌아가기 전에 저장해 두었던 값을 스택에서 꺼내 레지스터를 원상 복구 합니다.

$\qquad lw \quad \$s0\,,0(\$sp) $     # 레지스터 복구

$\qquad lw \quad \$t0\,,4(\$sp) $     # 레지스터 복구 

$\qquad lw \quad \$t1\,,8(\$sp) $     # 레지스터 복구

$\qquad addi \quad \$sp\,,\$sp\,,12$     # stack에 할당한 공간 삭제

프로시저는 복귀 주소를 사용하는 jr 명령으로 끝납니다.

$\qquad jr \quad \$ra$   #복귀 주소를 기반으로 복귀합니다.

하지만 임시 레지스터와 같이 간단한 관례를 정함으로써 레지스터 스필링을 많이 줄일 수 있습니다. 실제로 t0, t1 값은 호출 전후로 같은 값을 유지할 필요가 없기 때문에 저장 명령 두 개와 적재 명령 두 개를 없앨 수 있습니다.

새 데이터를 위한 스택 공간의 할당

레지스터에 들어가지 못할 만큼 큰 배열이나 구조체 같은 지역 변수를 저장하는 데에도 스택이 사용되기 때문에 보다 복잡해집니다. 프로시저의 저장된 레지스터와 지역 변수를 가지고 있는 스택 영역을 프로시저 프레임(procedure frame) 또는 액티베이션 레코드(activation record)라고 부릅니다.

MIPS 소프트웨어 중에는 프레임 포인터(frame pointer, $fp)가 프로시저 프레임의 첫 번째 워드를 가리키도록 하는 것이 있습니다.  즉, 스택을 사용하는데 있어서 베이스 레지스터 역할을 수행하여 지역 변수를 간단하게 참조할 수 있도록 하는 역할을 합니다. (그림 1 참조)

*별도의 프레임 포인터 사용 여부와 상관 없이 액티베이션 레코드는 항상 스택에 존재합니다.

새 데이터를 위한 힙 공간의 할당

C 프로그래머는 프로시저에만 국한되는 자동 변수 외에도 정적 변수와 동적 자료구조를 위한 메모리 공간이 필요합니다. 정적 데이터 세그먼트(static data segment)라는 부분이 있는데, 상수와 기타 정적 변수들이 저장됩니다(그림 1 참조). 배열은 그 크기가 고정되어 있어 정적 세크 먼트에 잘 맞습니다. 다만 링크드 리스트(linked list)와 같은 자료 구조는 늘어났다 줄어들었다 합니다. 이러한 자료구조를 위한 세그먼트를 전통적으로 힙(heap)이라고 합니다. 

*스택과 힙이 서로 마주보면서 자라도록 할당하기 때문에 공간을 효율적으로 사용합니다.

*C언어의 경우, 함수를 통해 힙 공간을 할당받고 반환하는데 사용이 끝난 공간을 반납하는 것을 잊어버리면 '메모리 누출(memory leak)'이 발생하여 메모리 부족으로 운영체제가 붕괴될 수 있습니다.

*반대로 공간을 너무 일찍 반납하면 프로그램의 의도와 상관없이 엉뚱한 것을 가리키는 '매달린 포인터(dangling pointer)'가 발생합니다.

*Java에서는 이러한 버그를 피하기 위해 자동 메모리 할당과 가비지 컬렉션(garbage collection)을 사용합니다.

*컴퓨터 구조 및 설계 5th Edition (저자 David A. Patterson 과 John L. Hennessy)를 기반으로 작성되었습니다.

*MIPS 어셈블리언어 기반으로 작성되었습니다.

컴퓨터 내에서는 일련의 높고 낮은 전기 신호의 형태로 숫자를 저장하므로, 결국 기수 2인 수로 볼 수 있습니다. 모든 정보는 이진 자리 수(binary digit), 즉 비트(bit)로 구성되므로 비트가 계산의 기본 단위가 됩니다. 어떤 기수(Base)의 숫자에서 $i$번째 숫자 $d$의 값은 다음과 같습니다.

$$d*Base^i$$

예를 들어, $11_{ten}$은 $1011_{two}$와 같이 나타낼 수 있습니다. 그리고 워드는 수평으로뿐만 아니라 수직으로도 그릴 수 있기 때문에, 가장 오른쪽 혹은 가장 왼쪽 비트라고 말하면 애매할 수 있습니다. 그렇기에, 가장 오른쪽 비트를 LSB(Least significant bit) 가장 왼쪽 비트를 MSB(Most significant bit)라고 합니다. 이러한 이진 비트 패턴을 연산하는 하드웨어를 설계 할 수 있는데, 연산의 결과가 하드웨어 구현된 비트들만으로 표현이 불가능하면 오버플로우(overflow)가 발생했다고 말합니다. 

*다만, 오버플로우가 발생했을시 어떻게 해야 할지는 프로그래밍 언어와 운영체제 및 프로그램의 몫입니다.

컴퓨터 프로그램은 양수와 음수를 모두 계산합니다. 가장 확실한 방법은 별도의 부호를 한 비트로 표현하여 덧붙이는 방법입니다.

*이 방법의 이름은 부호와 크기(sign and magnitude)표현법 입니다.

그러나 부호와 크기 표현법에는 몇 가지 단점이 있었습니다.

• 첫째로 부호가 붙는 위치가 명확하지 않습니다.
• 두번째로 부호와 크기 표현법의 덧셈기는 부호를 결정하기 위해 한 단계가 더 필요합니다. 왜냐하면 최종 부호가 무엇이 될지를 미리 알 수 없기 때문입니다.
• 마지막으로, 비트가 따로 붙기 때문에 양의 0과 음의 0을 갖는다는 점입니다. 

이러한 단점으로 인하여 2의 보수(two's complement)표현법을 사용하게 되었습니다. 2의 보수 표현에서 모든 음수는 MSB가 1이라는 장점이 있습니다. 따라서, 하드웨어가 양수인지 음수인지 알아보려면 MSB만 검사하며 됩니다.

*MSB를 부호 비트(sign bit)라고 부릅니다. 

다만 부호없는 수의 연산결과가 오버플로우를 발생시킬 수 있는 것처럼 2의 보수 연산에서도 MSB가 부호에 맞지 않는 경우 오버플로우가 발생할 수 있습니다. 

*부호있는 수와 부호 없는 수는 산술 연산뿐만 아니라 적재 명령어와도 상관이 있습니다. 

부호 있는 적재의 경우, 레지스터의 남는 곳을 채우기 위해 부호를  반복하여 복사하는 부호 확장(sign extension)을 하게 됩니다.

2의 보수(two's complement) 연산 계산법

2의 보수 연산에서 사용할 수 있는 계산법은 두 가지가 있습니다.

첫번째로, 모든 0을 1로, 1은 0으로 바꾸고 그 수에 1을 더하는 방법이 있습니다.

이 방식은 원래 수와 모든 비트를 역전시킨 수의 합은 $111...111_{two}$가 -1이라는 것에 기초하고 있습니다.

예를 들어, $2_{ten}$을 역부호화 해보겠습니다.

$$2_{ten} = 0000\,0000\,0000\,0000\,0000\,0000\,0000\,0010_{two}$$

여기서 0은 1로, 1은 0으로 변환하면 다음과 같습니다.

$$1111\,1111\,1111\,1111\,1111\,1111\,1111\,1101_{two}$$

그런 다음, 1을 더해주면 다음과 같습니다.

$$-2_{ten} = 1111\,1111\,1111\,1111\,1111\,1111\,1111\,1110_{two}$$ 

두번째로, n비트로 표현된 이진수를 n비트보다 큰 수로 바꾸는 방법입니다. load, store, branch, add 그리고 set on less than 명령어의 수치 필드에는 2의 보수 16비트 이진수가 들어갑니다. 빠른 방법은 16비트의 이진수의 최상위 비트(부호 비트)를 취해서 비어있는 왼쪽 부분에 채우고, 원래의 16비트 값은 32 비트 수의 오른쪽 부분에 그대로 복사하는 것입니다. 

*이러한 방법은 부호확장(sign extension)이라고 합니다.

$$0000\,0000\,0000\,0010_{two} = 2_{ten}$$

최상위 비트(0)를 취해서 왼쪽 부분에 16번 복사하고, 워드의 오른쪽 부분에는 원래의 값을 그대로 복사하여 32비트 이진수를 만들 수 있습니다.

$$0000\,0000\,0000\,0000\,0000\,0000\,0000\,0010_{two} = 2_{ten}$$