NandToTetris : 가상머신1-프로세싱 (밑바닥부터 만드는 컴퓨팅 시스템)

가상 머신 패러다임

프로그램들은 컴퓨터에서 실행되려면 기계어로 번역되어야 합니다.

많은 고수준 언어들이 생겨남에따라, 동일하게 컴파일러들도 생겨났고 이러한 컴파일러들은 원본언어에 종속적이게 되었습니다.

 

현대에는 이 종속성을 분리하기 위해 전체 컴파일 과정을 두 단계로 나누었습니다.

첫 단계는 고수준 언어의 구문을 분석(parse)하여 그 명령들을 중간처리단계로 번역합니다.  (컴파일러)

두 번째 단계에서는 이 중간 단계를 다시 대상 하드웨어의 기계어로 번역합니다. (VM번역기)

 

두 단계(컴파일러, vm번역기)를 이어주는 인터페이스를 가상 머신 (virtual machine)이라고 합니다.

 

고수준 언어가 기계어로 번역되는  과정

1. 컴파일러가 고수준 코드를 중간 VM 명령으로 번역
2. vm 변역기가 중간 vm 명령을 기계 명령어로 번역

java로 예시를 들면 컴파일러인 javac가 .class코드를 생성합니다.

가상머신 jvm은 .class코드를 읽어 직접 기계어로 변환합니다.

(jvm은 어셈블리없이 바로 바이트코드 -> jvm에서 어셈블리어 변환 후 다시 기계어 변환)

 

vm방식으로 생성된 기계코드는 c에서 사용하는 고전적인 1단계 컴파일러에 비해 장황하고 복잡한 코드가 되어 다소 효율성이 저하됩니다.

하지만 프로세서가 최적화 되고 vm구현이 최적화 되어 크게 눈에 띄지는 않습니다.

물론 고성능이 필요한 응용프로그램이나 임베디드 시스템에서는 항상 보다 효율적인 코드가 필요합니다.

vm 추상화와 스택 머신

vm 명령은 고수준언어와 저수준언어의 인터페이스이기에 컴파일러가 적절히 구조화된 vm 코드를 생성할 수 있도록

충분히 '고수준'이면서 동시에 vm번역기가 효율적인 기계어 코드를 생성할 수 있도록 충분히 '저수준'이기도 해야합니다.

고수준, 저수준 언어를 인터페이스 하기 위해 가상환경을 제공해야하는데 이를 vm추상화라고 합니다.

 

vm추상화는 메모리 세그먼트와 스택 두가지 방법이 존재합니다.

vm추상화를 달성하기 위한 방법 중 하나로 스택을 사용하게 되면, 스택 머신이라는 추상적인 아키텍처를 중간 vm 언어의 기반으로 사용합니다.

 

두 방법의 차이는 아래와 같습니다.

• 메모리 : 모든값에 인덱스가 존재하며 접근 가능, 값을 읽을 때는 메모리 상태가 아무런 영향을 받지 않음, 메모리 주소에 값을 쓰기에 그 주소에 값이 덮혀쓰여짐
• 스택 : 최상단만 접근 가능, 최상단 값을 읽으려면 해당 값을 스택에서 삭제해야함, 최상단에만 값을 추가하며 나머지 값들은 변화 X

참고로 스택에 최상단 값 바로 아래 위치는 sp (stack pointer)라는 이름으로 참조합니다.

스택 머신

스택머신은 사실 우리에게 익숙한 자료구조 스택 그 자체입니다. 즉 컴퓨터에서의 추상적인 설계일 뿐입니다.

스택머신이 어떻게 메모리의 데이터와 관계되어 있는지 알아보겠습니다.

 

위에 그림과 같이 constant 17, 즉 상수 17을 스택에 넣는다면 스택에서는 값 17이 들어가고 sp는 스택의 다음 자리를 가리키게 됩니다.

 

이제 실제 메모리에서는 어떻게 스택머신이 구현되는지 알아보겠습니다.

메모리에서는 스택머신을 위한 몇가지 초기 설정들이 되어있습니다.

• sp (stack pointer)는 RAM[0]를 의미합니다.
• 스택에 들어가는 데이터는 RAM[256]부터 시작합니다.

먼저 위에 그럼의 스택에는 이미 12, 5 두 데이터가 들어가 있기에 현재 스택포인터는 256 + 2 즉 258을 가리키고 있습니다.

여기 새로운 값 17이 추가되면 sp가 가리키는 위치 258에 17이 추가되고 sp의 값, RAM[0]의 값은 259로 업데이트 됩니다.

스택 산술

스택 머신에서 x op y와 같은 연산들은 아래와 같이 수행됩니다. (op는 +, - 등등)

 

1. 피연산자 x,y를 스택 최상단에서 꺼냅니다. (pop)

2. x op y를 계산합니다.

3. 계산된 값이 스택 최상단에 들어갑니다. (push)

 

스택 머신은 산술 및 논리 표현식이 아무리 복잡하더라도 스택 위에서의 단순한 연산들로 체계적으로 변환하고 계산할 수 있습니다.

따라서 고수준 산술 및 논리 표현식을 순차적인 스택 명령들로 번역하는 컴파일러를 만들 수 있다.

 

덧셈(add)과 부호반전(neg)을 처리하는 스택산술 과정

 

d = (2-x) + (y+9)의 스택 산술 과정

( x < 7 ) or (y == 8) 을 처리하는 논리 표현식 과정

가상 메모리 세그먼트

고수준 언어는 x,y,sum 같은 기호 변수를 지원합니다.
이러한 기호 변수들은 클래스 레벨에선 정적 변수, 인스턴스 레벨에서는 객체 필드 변수, 메서드 레벨에서는 지역 변수 또는 인수가 될 것 입니다.

하지만 가상 머신에서는 기호 변수가 존재하지 않습니다.

대신 변수들은 static, this, local, argument 같은 이름의 가상 메모리 세그먼트 내 항목들로 표현된다.

특히 컴파일러는 고수준 프로그램에서 나오는 첫번쨰 두번째 세번째 정적 변수들을
static 0, static 1, static 2 같은 식으로 매핑합니다.

그리고 다른 종류의 변수들도 비슷하게 this, local, argument 세그먼트로 매핑됩니다.

예를 들어 지역 변수 x와 필드 y가 각각 local 1과 this 3에 매핑된 경우, 컴파일러는 let x = y 같은 고수준 명령문을 push this 3, pop local 1로 번역합니다.

 

추가로 핵 vm 모델은 아래와 같은 8개의 메모리 세그먼트를 지원합니다.

vm 명령은 세그먼트 이름 다음에 인덱스(음수 X)를 사용하는 방법을 사용해 메모리 세그먼트에 접근합니다.

포인터 조작

핵 컴퓨터에서 메모리 세그먼트를 사용할때는 포인터를 이용한 조작이 많습니다.

D = *p라는 vm명령어는 핵 어셈블리어에서 아래와 같이 표현됩니다.

@p    // p는 0와 동일합니다. 즉 A레지스터에 0값을 설정합니다.

A=M  // RAM[0]의 값 257이 다시 A레지스터에 설정됩니다.

D=M  // RAM[257]의 데이터 23을 D에 지정합니다.

 

핵 vm모델의 메모리 세그먼트 종류

총 8개의 메모리 세그먼트가 존재하며,

각각 세그먼트들의 정의와 주소는 아래 표와 같습니다.

• argument : 함수의 인수를 나타냅니다.
• local : 함수의 지역 변수를 나타냅니다.
• static : 함수에서 볼 수 있는 정적 변수를 나타냅니다.
• constant : 상수 변수 0,1,...,32767을 나타냅니다.
• this, that, pointer, temp : 우리가 익숙한 그것들,,

핵 컴퓨터에서 RAM은 0~15는 레지스터, 16~255는 정적 변수, 256~2047은 스택 영역으로 사용됩니다.

이름	위치	내용
SP	RAM[0]	스택 포인터 주소, 최초 256으로 초기화
LCL	RAM[1]	local 메모리 세그먼트 기본주소
ARG	RAM[2]	argment 메모리 세그먼트 기본주소
THIS	RAM[3]	this segment의 기본주소
THAT	RAM[4]	that segment의 기본주소
TEMP	RAM[5-12]	temp segment를 저장
R13, R14, R15	RAM[13-15]	VM 번역기가 생성한 어셈블리 코드에서 별도의 변수가 필요할 때 사용하는 레지스터

 

각 메모리 세그먼트간 데이터 입출력 예시

stack머신은 아래와 같이 각 세그먼트들과 데이터를 전달받고 전달합니다.

예를들어 위와 같은 상황에서 let static 2 = argument 1과 같은 vm 명령을 작업을 해야한다면

스택에 push argument 1, pop static 2와 같은 명령이 필요합니다.

Local 세그먼트

로컬 세그먼트의 기본 주소(LCL)는 1015입니다.

LCL은 SP와 다르게 스택의 값이 변경되어도 값이 변하지 않습니다.

즉 LCL의 계속해서 최초주소 1015를 가지고 있습니다.

대신 pop/push local i 가 실행되면 addr=LCL + i를 하여 로컬 세그먼트 기본주소(1015)에 해당 로컬 변수의 번호를 더한 주소에 값을 넣거나 가져옵니다.

이후 *SP = *LCL+i, SP++/-- 연산을 진행합니다.

즉 RAM[LCL+i]의 값을 스택 포인터가 가리키고 있는 위치에다가 대입하고, SP를 ++/--합니다.

 

추가로 Argument, This, That 세그먼트들도 Local 세그먼트와 동일하게 동작합니다.

 

만약 위와 같이 pop local 2 명령이 실행되면

메모리 관점에서는 스택의 최상단 값(*SP-1)을 꺼내(pop) RAM[LCL+2]에 저장시키고 SP를 1 감소시킵니다.

 

 

local pop 2 핵 어셈블리어로는 아래와 같이 동작 할 것 같습니다.. (R[13]~R[15]를 이렇게 쓰는지 확신이 없습니다 ㅠㅠ) 

@LCL    // A = LCL
D=M     // D = RAM[1015]
@1      // A = 1
D=D+A   // D = 1015 + 2 = 1017

@R13    // 임시 저장소 사용 (RAM[13]에 local 2 주소 저장)
M=D     // RAM[13] = 1017

@SP     // A = SP
M=M-1   // SP--
A=M     // A = SP
D=M     // D = RAM[SP]

@R13    // A = R13 (저장된 local 2 주소 1017)
A=M     // A = 1017
M=D     // RAM[1017] = 스택에서 꺼낸 값

local push 1 는 아래와 같이 동작 할 것 같습니다.

@LCL    // A = LCL
D=M     // D = RAM[1015]
@1      // A = 1
A=D+A   // A = 1015 + 1 = 1016
D=M     // D = RAM[1016]

@SP     // A = SP
A=M     // A = RAM[0]
M=D     // RAM[256] = RAM[1016] (local 1 값 복사)

@SP     // A = SP
M=M+1   // SP++

 

Constant 세그먼트

Constant 세그먼트에서는 pop명령이 따로 존재하지 않습니다

 

Static 세그먼트

foo.vm 파일에 저장된 vm프로그램 내에 static i변수가 있다면, 어셈블리 기호 Foo.i로 변환합니다.

그 후 static 변수들은 RAM[16] ~ RAM[255] 사이에 vm명령이 들어오는 순서대로 매핑됩니다.

 

Temp 세그먼트

Temp 세그먼트는 RAM[5] ~ RAM[12] 사이에 매핑됩니다.

temp i에 대한 접근은 RAM[5+i]와 같은 방식으로 진행됩니다.

Pointer 세그먼트

this와 that의 주소를 저장하는 특수한 세그먼트입니다.
RAM[3]에 this의 주소, RAM[4]에 that의 주소가 저장됩니다.
this와 that이 가리키는 메모리 위치를 바꿀 때 사용됩니다.

즉, pointer 0 = this, pointer 1 = that이 됩니다.

 

this : 현재 객체(혹은 특정 메모리 영역)를 가리킬 때 사용

that : 다른 메모리 공간(배열 등)을 가리킬 때 사용

예를 들어 push pointer 0 (THIS의 주소를 스택에 저장)

라는 명령은 아래와 같이 처리 될 수 있고

// push pointer 0
@3     // A = pointer 0 (THIS)
D=M    // D = RAM[3] (THIS의 주소)

@SP    // A = 스택 포인터
A=M    // A = RAM[SP] (현재 스택의 위치)
M=D    // RAM[SP] = THIS의 주소 (스택에 저장)

@SP    // A = 스택 포인터
M=M+1  // SP++

push pointer 1 (스택에서 값을 꺼내 THAT의 주소로 저장) 은 아래와 같이 처리됩니다.

@SP    // A = 스택 포인터
M=M-1  // SP--
A=M    // A = RAM[SP] (스택의 최상단)
D=M    // D = RAM[SP] (스택에서 꺼낸 값)

@4     // A = pointer 1 (THAT)
M=D    // RAM[4] = 스택에서 꺼낸 값 (THAT이 가리키는 주소 변경)