NandToTetris : 운영체제 (밑바닥부터 만드는 컴퓨팅 시스템)

이 책의 마지막 장인 운영체제입니다.

OS는 컴퓨터에서 실행되는 모든 프로그램을 지원해야하기에 효율이 매우 좋아야합니다.

OS의 시간 및 공간 효율성이 높을수록 응용프로그램의 성능 또한 올라갑니다.

운영체제는 보통 고수준언어로 작성되어 바이너리 형식으로 컴파일됩니다.

let n = Keyboard.readInt("Enter a number : ")

 

위와 같은 명령어가 실행되면, 프롬프트에 Enter a number: 라는 문자열이 표시됩니다.

그러려면 String 객체가 생성되고 각 글자를 char 값 배열로 초기화합니다.

이후 문자열을 스크린에 한 번에 하나씩 렌더링하며, 다음 문자가 물리적으로 표시되어야하는 커서 위치를 업데이트합니다.

또한 사용자가 키보드의 특정키를 누를때까지 기다리는 루프 또한 준비되어야하고 이를 위해서는 키 입력 감지, 문자 입력, 문자열에 해당 문자 추가, 문자열을 정수로 반환하는 등 여러 작업이 필요합니다.

 

즉 let n = Keyboard.readInt("Enter a number : ") 과 같은 명령이 실행되면 객체 사용을 위한 메모리 할당, 입력 작업, 출력 작업, 문자열 처리와 같은 다양한 os함수들이 호출됩니다.

 

문자열 처리뿐만 아니라 아래 그림 처럼 수학연산, I/O 드라이버, 네트워크 등 운영체제가 하는일들은 많고 다양합니다.

Jack OS

Jack OS에서 지원하는 서비스들입니다.

 

Math : 수학관련 클래스

Memory : Memory 클래스 (peek, alloc 등)

Screen : 화면에 도형을 그릴 수 있는 클래스

Output : 화면에 text를 출력하는 클래스

Keyboard : 사용자의 입력을 받는 클래스

String : 문자열 관련 클래스

Array : Jack에서 사용되는 배열 클래스

Sys : 몇가지 유용한 함수가 들어있는 클래스 입니다. (halt, error, wait)

Jack OS : Math

곱셈

먼저 jack의 word size는 16bit입니다.

x는 27, y는 9이고 두 숫자를 곱하는 연산을 한다고 하면

먼저 이진수로 27과 9을 만들고 남는 크기는 모두 0으로 채웁니다.

 

이제 연산을 시작하는데 아래와 같은 방법으로 연산한다고 생각하면 조금 이해가 쉽습니다.

356 * 73 = (356 * 70) + (356 * 3)

 

먼저 x를 왼쪽으로 옮기고 (shift) 계속해서 한번씩 왼쪽으로 옮깁니다. 

위에 예시에서는 y의 bit(4)만큼 x에 대해 shift가 실행되었습니다.

shift가 완료되었다면 y의 값을 세로로 적은다음, y값의 bit가 1인 행들끼리만 더합니다.

위 예시에서는 첫줄과 마지막줄을 더하면 됩니다.

나눗셈

나누기는 우리가 어릴때 배웠던 나눗셈 방법 '정제법'을 사용합니다.

조금 다른점은 2진수를 사용한다는건데

예를들어 10(1010)를 3(0011)으로 나눈다면 먼저 몫을 담을 비트와 나머지를 담을 비트를 0으로 초기화 합니다.

 

나눠지는수 '1010'에서 각 bit를 하나씩 왼쪽으로 shift하여 나머지 bit에 추가합니다.

그 후 나머지에서 나누는 수(0011)을 뺍니다. 그 결과가 0 이상이면 몫비트에 1을 넣고 음수라면 몫 비트에 0을 널습니다.

이 과정을 비트수만큼 반복합니다.

제곱근

제곱근은 수학문제 풀듯이 풀어서 찾을 수 있습니다.

제곱근(√)을 구하는 방법은 이진 탐색(Binary Search), 제곱근의 역함수 y = x², 

제곱근 함수와 역함수는 모두 단조 증가함수기에 감소하지 않고 계속 커진다는 특성 이 3가지를 이용해 구할 수 있습니다.

 

y = √x을 구하는 것은 y² ≤ x < (y + 1)²인 값을 찾는 것과 같습니다.

그래서 제곱근을 찾는 문제는 결국 역함수의 값을 찾는 문제가 됩니다.
그리고 함수다 양의 방향으로만 증가하는 함수기에, 중간값(mid)을 기준으로 범위를 절반씩 줄여갈 수 있습니다. (이진 탐색)

Jack OS : String

String은 Jack OS 표준 라이브러리입니다.

컴퓨터는 숫자를 내부적으로 2진 코드로 표현하지만 사람이 숫자를 읽거나 입력해야할 때는 10진수로 변환(cast)되어야합니다.

String -> int 형변환

int2String()은 숫자를 재귀적으로 문자열로 변환하고,

string2Int()는 각 문자를 숫자로 변환하며 왼쪽에서 오른쪽으로 조합하는 방식으로 동작합니다.

Jack OS : Memory

os에서 메모리를 관련 클래스의 메소드는 peek, poke, alloc, deAlloc이라는 함수가 있습니다.

이 메서드들은 컴파일러에서 생성자 및 소멸자를 처리할 때 저수준 코드에 포함되거나, 아니면 고수준언어에서 직접 호출되기도 합니다.

heap의 자원 관리는 os에서 하며 os가 실행되면 heapBase라는 포인터를 RAM에서 heap의 시작주소로 초기화 합니다.

jack에서는 스택에 끝에 위치하며 heapBase는 2048입니다.

peek & poke

프로그램은 계속해서 RAM에 접근합니다.

운영체제는 고수준 프로그램와 RAM의 인터페이스입니다.

peek & poke는 RAM의 주소에 대한 함수입니다.

Memory.peek(addr)은 RAM의 주소 addr을 반환하고 Memory.poke(addr, value)는 RAM주소와 value를 받아서 해당 주소의 RAM을 value로 설정합니다.

peek & poke를 구현하기 위해서는 RAM에 주소에 직접 접근해야합니다.

메모리 클래스에서 먼저 init 함수를 이용해서 array ram을 0으로 초기화합니다.

변수를 0으로 초기화 함으로서 인덱스를 이용해 ram의 주소 어디든 접근할 수 있게됩니다.

그 뒤에 peek & poke를 사용해서 메모의 값을 조회하거나 변경 할 수 있습니다.

alloc & dealloc

운영체제에서 동작하는 프로그램들은 수많은 객체들과 배열을 생성하고 참조합니다.

생성된 객체와 배열들은 heap에 저장되고 stack은 데이터가 저장된 heap주소를 가지고있습니다.

 

alloc함수는 argument에 지정한 사이즈만큼의 메모리를 사용할 수 있는 메모리 주소를 반환합니다.

dealloc은 argument지정한 객체나 배열의 주소를 가져와서 재활용 할 수 있도록 해제합니다.

록

클래스의 생성자가 실행되면 alloc(argument 수)명령어가 실행되는데

argument의 수 만큼 heap에서 공간을 할당하고 stack에 그 시작 주소를 저장합니다.

객체가 필요없을때는 deAlloc 메서드를 사용해 그 객체를 제거할 수 있습니다.

 

자바나 c++에서 gc는 생성되는 모든 객체에 대한 모든 참조를 추적합니다.

프로그램이 동작하면서 그 객체에 대한 온갖 종류의 역참조가 발생하게 됩니다.

계속 동작하면서 특정 포인터를 가리키는 참조 수가 감소되어 결국 0이되면 gc가 동작해서 deAlloc 함수를 실행합니다.

 

하지만 jack은 gc를 사용하지 않고 명시적으로 제거하는 방법을 선택했습니다.

heap management

os가 heap을 관리하는 방법에 대해 알아보겠습니다.

init()함수에서 heapBase의 주소를 freeList라는 LinkedList에 저장합니다.

LinkedList에는 크기(size)와 다음 빈 블록을 가리키는 포인터(next)가 저장됩니다.

alloc heap management

alloc함수가 실행되면 적절한 block을 찾은 뒤 FreeList에서 제거하고 호출자에게 제공합니다.

alloc(3)함수가 실행되었을 때 세그먼트의 크기가 size+2보다 크면 해당 세그먼트를 제공합니다.

size+2인 이유는 2만큼의 필수 필드값(size, next)을 넣어야하기 때문입니다.

 

적합한 세그먼트를 찾는 방법은 best-fit, first-fit 두가지가 있습니다.

first-fit은 freeList를 탐색하면서 최초로 찾은 적합한 세그먼트를 사용하는 방식입니다.

best-fit은 가능한 작은 세그먼트를 찾는 방법입니다.

 

추가로 최초의 freeList의 크기는 heap 전체입니다.

deAlloc heap management

dealloc이 하는일은 객체로 사용되고있는 block을 다시 freeList의 뒤에 붙이는 작업입니다.

그렇기에 dealloc이 많이 실행될수록 freeList는 더 많이 파편화됩니다.

하지만 freeList가 많이 파편화되면 alloc이 적합한 size의 블록을 찾기 점점 어려워집니다.

그래서 defrag라는 알고리즘을 통해 파편화된 freeList들을 합치는 작업이 필요합니다.

(실제로 모든 os에서 defrag가 가끔식 실행됩니다.)

Jack OS : Array

Array 클래스의 new는 생성자가 아니라 함수입니다.

os함수인 Memory.alloc을 호출하여 배열을 위한 메모리를 할당합니다.

그리고 dispose()를 통해 Memory.deAlloc을 호출하여 해제합니다.

 

Jack OS : Graphics

jack의 Screen클래스는 기본적인 그래픽 그리기 알고리즘만을 제공합니다.

우리는 맨 왼쪽 상단의 좌표가 (0,0)인 흑백스크린에 연결되어있다고 가정합니다.

스크린은 전용 RAM의 메모리맵 영역과 연결됩니다.

컴퓨터 외부의 프로게스가 1초당 한번씩 메모리 맵에 따라 스크린을 새로고침합니다.

vector graphics, bitmap graphics 

jack에서는 vector, bitmap 두가지 방식으로 그래픽 구현이 가능합니다.

벡터 그래픽은 수학적 도형(선, 사각형, 원 등)의 명령어를 기반으로 그래픽을 표현하는 방식이고

비트맵 그래픽은 픽셀 하나하나를 직접 지정하여 저장하는 방식입니다.

화면을 2D 배열의 형태(0과 1)로 표현하며, 각 픽셀이 켜짐(1) 또는 꺼짐(0) 상태를 가집니다.

 

vector 그래픽은 이미지를 픽셀이 아닌 수학적 개념으로 저장하며, 크기를 확대해도 깨지지 않으나

bitmap은 픽셀 단위로 저장되므로, 확대하면 깨지는 문제가 발생할 수 있습니다.

픽셀 그리기 (bitmap)

drawPixcel 함수를 통해 메모리맵을 조작하며 픽셀을 그리게됩니다.

한 개의 RAM 주소는 16개의 픽셀을 저장하기에 픽셀 좌표 (x, y)를 RAM 주소로 변환해서 위치를 찾습니다.

 

y 좌표 찾기

화면은 512(16*32) 픽셀의 가로 해상도를 가지고 있습니다. 즉 한 줄에 32개의 word size(16bit)가 존재합니다

따라서 y 번째 줄의 시작 RAM 주소는 16384 + (y * 32)로 계산합니다.

 

x 좌표 찾기

픽셀 x 좌표는 16픽셀 단위로 저장되므로, x가 0~15이면 첫 번째 RAM 단어(16384), x가 16~31이면 두 번째 RAM 단어(16385)

이기에 x / 16계산을 통해 좌표를 찾습니다.

 

즉 메모리맵의 주소는 address = 16384 + (y * 32) + (x / 16);이 됩니다.

bitMask (픽셀 on/off)

이후 bitMask 연산("1 << (15 - (x % 16))")을 통해 픽셀의 on/off를 설정할수 있습니다.

and연산으로 픽셀을 끄고 or 연산으로 픽셀을 킵니다.

// 픽셀 키기
Memory.poke(address, Memory.peek(address) | bitMask);
// 픽셀 끄기
Memory.poke(address, Memory.peek(address) & (~bitMask));

선 그리기 (vector)

선은 픽셀들을 지그제그로 그려나가는 모양입니다.

아래 그림처럼 선을 그리는 함수 drawLine은 결국 drawPixel의 연속입니다.

 

x1,y1에서 x2,y2까지 선을 그리는 함수 drawLine(x1,y1,x2,y2) 가 있을때 drawLine함수에는 좌표값(x1, y1)의 이동을 위한 a,b 지역변수가 존재합니다. (a는 오른쪽으로 몇 픽셀이동했는지 알려주고 b는 위로 몇 픽셀 이동했는지 알려줍니다.)

 

drawLine함수가 실행되면 먼저 x1,y2를 그립니다.

이제 픽셀이 오른쪽으로 이동할지 위쪽으로 이동할지 결정합니다.

b/a가 dy/dx보다 크다면 오른쪽으로 아니라면 위쪽으로 이동합니다.

두 값을 비교를 위해 diff라는 변수를 사용합니다.

 

어디로 이동할지 정해졌다면 이제 이동을 시작합니다.

오른쪽으로 가야한다면 a를 증가시킵니다. 그 후 while로 다시 돌아와서 변경된 좌표(x+1, y)에 픽셀을 그립니다.

위로 가야한다면 위로 한칸(x+1, y+1) 이동해서 픽셀을 그립니다. (대각선으로 이동하는 경우는 없습니다)

원 그리기 (vector)

원을 그리는 메서드 drawCircle또한 원의 근사치를 만드는 방향으로 구현합니다.

중심의 좌표 x,y와 원의 반지름 r을 argument로 받고, y+dy, x를 지나는 선들을 이용해 원을 그립니다.

x좌표는 반지름과 dy를 이용한 피타고라스의 정리를 통해 구할 수 있습니다.

 

그렇게 drawCircle에 대한 메소드를 만들 수 있습니다.

Jack OS : Output

문자집합은 출력 가능한것과 불가능한것으로 나뉩니다.

출력 가능한 문자들은 모두 화면에 표시되는 bitmap이미지가 있어야하고 그 이미지들을 font라고 합니다.

(jack에서는 11*8 픽셀을 사용합니다.)

jack os의 Output 클래스에서는 initMap이라는 init시 발생하는 함수를 통해 font에 대한 bitmap들을 저장합니다.

font를 만드는 작업은 사용할때마다 처리하지 않고 최초 Init시에만 설정합니다.

Jack OS : Keyboard

jack에서는 keyboard를 위해 단일 16bit 레지스터를 할당합니다.

키보드에 어떤 키도 누르지 않으면 레지스터의 값은 0입니다.

 

키보드 클래스는 4가지 메소드로 만들어집니다.

keyPressed() : 키보드에서 눌린 내용이 반환됩니다.

readChar() : 사용자가 마지막으로 누른키를 반환합니다.

readLine() : 문자를 입력하면 enter, return 키를 눌렀을때 입력이 완료

readInt() : readLine과 유사하지만 숫자만 허용

아래 표는 keyboard에서 사용하는 아스키코드값입니다.

Jack OS : Sys

부트스트래핑은 전원을 키거나 전반적인 재설정이 일어날때 컴퓨터의 메모리에 기본적인 소프트웨어를 로드하는 과정입니다.

특히 os가 필요에 따라 소프트웨어를 로드하게됩니다.

 

부트스트래핑이 일어나기 위해 jack 플랫폼에서는 몇가지 약속이 필요합니다.

1. 컴퓨터가 실행되거나 재설정될 때 ROM[0]에 위치한 명령어가 실행되어야합니다.

2. vm번역기에서 프로그램을 변환할떄 항상 ROM[0]에 sp=256, call Sys.init

3. 실행되는 프로그램은 반드시 Main이라는 클래스가 있어야하고 클래스 내에 main이라는 함수가 필요합니다.

4. Sys init은 os를 초기화하고 반드시 Main.main()을 호출합니다.

 

Sys클래스의 init함수는 필요한 각 클래스들을 초기화 하고 Main.main을 호출합니다.

동일하게 Sys에 있는 halt, wait함수도 있는데

wait함수는 주어진 밀리초 동안 기다렸다가 반환하는 함수이고

halt는 프로그램 실행을 중단합니다. (while루프로 구현)

 

---

NandToTetris 후기

어느 시점부터 과제를 안했는데, 그러다보니 책의 내용 그대로만 작성만하게 된 것 같다.

나중에(2026년쯤) 다시 처음부터 개선부분까지 과제를 진행하며 git에 올려봐야겠다는 생각이 강하게 들었다.

지금은 내 기록용 포스팅들이 되어버렸지만 다시 리마스터해서는 조금 더 좋은 내용들을 담아서 리마스터 하고싶다.