이학균 |
광운대학교 전자공학부에서 정보통신공학을 전공하고 있다. 마이크로 컨트롤러와 시스템 프로그래밍에 관심이 많으며 자신이 개발한 OS를 마이크로 컨트롤러에 이식하기 위해 노력 중이다. 시간이 날 때마다 인라인을 즐기는 인라인 마니아이기도 하다.
============================================================================================================
지난 호에서 CPU를 추상화하여 실행하는 방식의 문제점인 속도 저하를 없애기 위해 TVM 인스트럭션을 인텔 x86 기계 코드로 포팅하는 과정과 인터럽트 처리 및 간단한 디버거를 구현해 보았다. 이로써 TVM의 전반적인 부분을 모두 구현했는데 이번 호에서는 사용자가 TVM 인스트럭션으로 코딩한 소스 파일을 TVM에서 실행할 수 있는 TEF 파일로 생성하는 어셈블러를 개발해 보려고 한다.
하나의 시스템을 컴퓨터 아키텍처 관점에서 구현해 보는 일은 매우 흥미로우면서도 시스템 전반을 알 수 있는 좋은 기회가 된다. 지난 호까지 가상 머신의 전반적인 부분을 구현해 보았고 이번 호에서는 설계한 인스트럭션으로 코딩된 소스 파일을 어셈블링하여 실행파일을 만들어 내는 과정을 다루려고 한다. 이번 호에서 구현할 TVM 어셈블러는 2 패스 어셈블러인데, 우선 어셈블러를 구현하기 위해 필요한 데이터 구조를 간략히 살펴보고, 각 과정에서 필요한 일들을 직접 구현하려 한다.
컴퓨터는 모든 데이터를 0과 1로만 인식하기 때문에 모든 데이터를 수치로 바꿔줘야 한다. 어셈블링 과정을 간략히 설명하면 소스코드에 작성된 인스트럭션을 정의된 수치로 바꾸고 변수는 데이터 세그먼트의 오프셋으로, 함수는 코드 세그먼트의 오프셋으로 치환하는 과정이다.
어셈블링 과정
어셈블러는 사람이 이해할 수 있는 어셈블리 언어를 컴퓨터가 인식할 수 있는 기계 코드로 바꿔주는 프로그램을 말한다. 일반적으로 어셈블러는 구현 방식에 따라 단일 패스 어셈블러와 이중 패스 어셈블러로 구분된다. 단일 패스 어셈블러는 소스코드에서 한 인스트럭션을 읽는 즉시 기계 코드를 생성하는 방식이고, 이중 패스 어셈블러는 소스코드를 전체적으로 한번 읽어 필요한 정보를 수집하여 테이블에 저장하고 다시 읽으면서 기계 코드를 생성하는 방식이다. 단일 패스 어셈블러는 소형 컴퓨터 등 기억 장치의 속도가 느릴 때는 효과적이지만 별도로 어셈블된 다른 코드와 결합할 수 없다는 치명적인 단점이 있다. 반면 이중 패스 어셈블러는 단일 패스 어셈블러에 비해 속도는 느리지만 별도의 다른 코드와 결합할 수 있는 장점이 있다. TVM 어셈블러는 이중 패스 어셈블러이고 실행파일을 생성하는 링커의 기능을 포함한다. <그림 1>은 TVM 어셈블러가 TEF 파일을 생성하는 과정을 나타낸 것이다.
패스 1에서 어휘 분석기를 통해 사용자가 입력한 소스코드의 각 토큰을 얻고, 변수 및 프로시저의 오프셋을 테이블에 저장하고, 지시어를 처리한다. 패스 2에서는 소스코드의 인스트럭션을 지정된 값으로 변환하고 변수와 프로시저는 패스 1에서 저장한 테이블의 값을 참조하여 오프셋으로 그 자리를 대체한다. 마지막으로 빌드 단계에서는 프로그램 헤더, 변수와 프로시저의 정보, 바이트 코드, 디버그 정보를 합쳐서 순차적으로 저장하여 TEF 파일을 생성하게 된다.
필요한 데이터 구조
패스 1 과정에서 변수와 프로시저의 정보를 저장하기 위해 링크드(linked) 리스트, 배열을 합한 확장 배열(extendable array), 해시 테이블(hash table)이 사용되었다. 확장 배열은 다음과 같은 변수와 프로시저의 정보를 저장하고 디버그 세그먼트에 저장할 변수와 프로시저의 라벨을 저장하는 데 사용하고, 해시 테이블은 그 정보에 빠르게 접근하기 위해 그 정보가 저장된 확장 배열의 인덱스를 저장하기 위해 사용된다.
typedef struct tagGlobalVariableHeader {
UWORD uwLabelAddress; // 라벨이 위치한 디버그 세그먼트의 상대 주소
UBYTE ubType; // 변수 타입
UWORD uwValueAddress; // 값이 저장된 디버그 세그먼트의 상대 주소
UWORD uwAsmLine; // 선언된 Asm 파일의 라인 번호
UWORD uwInitOffset; // 초기 값이 저장된 Var init table의 오프셋
} STGLOBALVARIABLEHEADER;
typedef struct tagProcedureHeader {
UWORD uwLabelAddress; // 라벨이 위치한 디버그 세그먼트의 상대주소
UWORD uwProcedureEntry; // 코드 세그먼트 내의 엔트리 포인트
UWORD uwAsmLine; // 선언된 Asm 파일의 라인 번호
} STPROCEDUREHEADER;
링크드 리스트는 동적으로 생성할 수 있어서 데이터의 수가 가변적일 때 유용하지만 액세스 속도가 느리다는 단점이 있고, 배열은 액세스 속도가 빠르지만 저장할 수 있는 데이터의 수가 한정된다는 단점이 있다. 확장 배열은 이 둘의 장점을 합친 것으로 <그림 2>와 같이 데이터가 저장 한도를 넘으면 배열을 확장하여 저장하는 방법을 사용한다.
<리스트 1>은 확장 배열에서 데이터를 추가하는 함수의 내용이다. 저장할 데이터의 종류가 다양하므로 편의상 템플릿을 사용하였다.
패스 2 과정에서 저장된 심벌 정보를 빠르게 얻기 위해 패스 1에서 확장 배열에 저장된 심벌 정보의 인덱스를 해시 테이블에 저장한다. 해싱은 데이터의 개수에 영향을 거의 받지 않는 특성이 있어서 빠른 검색을 위해 사용하는 자료구조로서 찾고자 하는 문자열을 해시 함수(hash function)를 통해 얻은 키 값으로 데이터의 위치를 찾는 방법이다. <그림 3>은 해시 테이블에 데이터가 저장되는 한 예를 보인 것이다.
예를 들어 한 반의 국어 성적을 저장하고 빠르게 찾기 위해 해시 테이블을 사용한다고 가정하자. <그림 3>과 같이 ‘홍길동’이라는 학생의 85점이라는 성적을 해시 테이블에 저장할 때, 해시 함수 h에 ‘홍길동’이라는 인자를 넣어 3이라는 키 값을 받는다. 그 키 값으로 해당 버킷에 저장하는데 <그림 3>과 같이 미리 데이터가 저장되어 있으면 그 버킷에서 이진 트리를 만들어 저장하는 구조이다. 해싱의 성능은 해시 함수가 좌우하는데, 최대한 겹치지 않게 모든 버킷에 골고루 데이터를 분배할 수 있는 키 값을 계산하는 것이 중요하다. 자료구조에 대한 자세한 사항은 이달의 디스켓에 포함된 소스와 자료구조 관련 서적을 참고하기 바란다.
Posted by Dual
