새싹프로그래머의 이야기

운영체제의 핵심은 바로 Virtualization(가상화) 입니다.

그렇다면 가상화란 무엇일까요?

가상화란?

"물리적인 컴퓨터 리소스의 특징을 다른 시스템, 응용프로그램, 최종 사용자들이 리소스와 상호 작용하는 방식으로부터 감추는 기술" - 위키피디아

만약 가상화 되지 않는 컴퓨터를 사용한다면, 하나의 작업을 하기 위해서 한 대의 컴퓨터와 서버가 필요합니다. 실제로 컴퓨터 기능의 10% ~ 15% 정도 밖에 사용하지 못한다고 합니다. 보다 효율적으로 활용하기 위해 "가상화"란 기술이 나왔습니다.

가상화란, 컴퓨터 리소스를 물리적으로 활용하는 것이 아닌 논리적으로 활용하도록 하는 기술입니다.

물리적으로 활용한다면 하나의 리소스를  A라는 작업을 차지하는 반면 논리적으로 활용한다면 하나의 리소스에 A라는 작업이 차지 하지 않는 부분을 B라는 작업이 활용할 수 있게 하는 기술 입니다.

가상화의 장점은?

1. 비용 절감: 1개의 OS에서 1개의 TASK를 수행하기 위해서는 1개의 물리적 서버가 필요합니다. 하지만 가상화를 하게 되면, 1개의 서버로 여러 개의 TASK를 수행할 수 있으므로 비용을 감소 시키는 효과가 있습니다.
2. 효율성: Resource를 abstract하여 사용함으로써, resource 자체를 효율적으로 사용할 수 있습니다. 또한, 하나의 물리적 시스템을 논리적으로 분리하여 여러 OS를 사용할 수 있습니다.
3. 재해 복구 능력 향상 및 연속성 유지: 자연 재해, 사이버 공격 등으로 인해 물리적 시스템이 손상된다면 복구하는데 많은 자원과 시간이 필요합니다. 하지만 가상화된 횐경은 몇 분내로 복구가 가능합니다. 빠른 복구가 가능할 뿐더러 물리적 시스템으로부터 분리된 환경을 제공함으로써 물리적 시스템을 보호하는 효과도 있습니다.

가상화의 종류?

Host OS형

Host OS형 가상화는 VMware, VirtualBox등의 가상화 기술을 통해  Host OS 위에서 가상화 소프트웨어와 가상 머신을 동작시키는 방법입니다. 일반적으로 물리적 소프트웨어 위에 있는 OS를 Host OS 라고 부르며, 가상머신에 설치되어 동작하는 OS를 Guest OS라고 부릅니다.

Host OS 위에서 별도의 OS를 구동시키는 방법이라 Host OS에는 별 다른 제약이 없으나, 같은 이유로 오버헤드가 클 수 있습니다.

하이퍼바이저형

하이퍼바이저형은 크게 전가상화 방식(Full Virtualization)과 반가상화 방식(Para Virtualization)으로 나뉩니다.

[전가상화 방식]

전가상화 방식은 말 그대로 하드웨어 전체를 가상화하여 활용하는 방식입니다. 하드웨어를 완전히 가상화 한다는 것은 CPU가 가상화 지원이 가능해야합니다.  뿐만 아니라, Guest OS는 자신이 가상화된 OS인지 모릅니다.   여기서 두 가지 문제점이 발생합니다.

첫번째, Guest OS는 자신이 가상화 된 OS인지 모르므로, 자신의 OS에서 사용하는 하드웨어 동작 명령을 전달하려고 하는 문제.

두번째, 같은 이유로 특권 명령(previleged Instruction)과 같이 Root 모드에서만 가능한 동작을 실행하려 할 때 발생하는 문제.

위 두가지 문제는 모두 하이퍼바이저(HyperVisor)가 해결합니다.

첫번째 문제의 경우, HyperVisor가 각 Guest OS로부터 명령을 전달 받아 Host OS에 맞게 번역하여 전달합니다.

두번째 문제의 경우, HyperVisor가 Trap&Emulate 방식으로 문제점을 해결합니다.

Trap & Emulate 방식이란?

• Guest OS은 기본적으로 non-root 모드로 동작합니다. 따라서, 특권 명령 등이 발생하면 Guest OS의 Kernel은 Trap을 발생시켜 하이퍼바이저에게 제어권을 넘겨줍니다.
• 하이퍼바이저는 Root 모드 동작이 가능하므로, 해당 동작들을 모두 처리 합니다.
• 처리가 완료되면 다시 kernel로 제어권을 넘겨줍니다.

Guest OS에서 별다른 수정 없이 활용할 수 있는 방식이지만, 하이퍼바이저가 모든 것을 처리해야하고 특히나 Trap이 엄청난 오버헤드를 유발하기 때문에 단점이 큰 방식입니다.

Trap의 오버헤드를 줄이기 위해 Binary Translation이라는 방식이 등장하였습니다.

• Binary Translation이란, Guest OS에서 특권 명령을 실행할 때 이를 하이퍼바이저가 하드웨어가 인식할 수 있는 명령으로 변환해주는 방식입니다.
• CPU가 명령에 대한 동작을 실행하는 방식이지만, 중간에 하이퍼 바이저가 번역하는 과정이 있습니다.

하지만 여전히 하이퍼바이저 단에서 많은 처리를 해주어야 하는 단점이 존재합니다.

이러한 전가상화의 성능적인 문제를 해결하기 위해 반가상화 방식이 등장하였습니다.

[반가상화 방식]

반가상화 방식은 Guest OS가 스스로가 Guest 임을 인지하는 가상화방식으로 Hyper call이라는 인터페이스 기술을 활용합니다.

Hyper call이란?

• Hyper call이란, Guest OS가 하드웨어가 인식할 수 있는 명령을 직접 전송하는 방식입니다.
• 하드웨어로 직접 전송하는 것은 아니지만 하이퍼바이저는 해당 명령을 전달하는 역할만 수행하므로 처리과정에서 발생하는 오버헤드가 없습니다.

이러한 동작이 되기 위해서는 Guest OS 커널의 수정이 필요합니다. 하지만, 하이퍼바이저는 각 Guest들의 리소스만 관리해주면 되므로 전가상화 방식보다 빠른 처리가 가능합니다.

[컨테이너형]

컨테이너는 호스트 OS에 논리적인 파티션을 만들어 애플리케이션이 구동하는데 있어 필요한 라이브러리, 자원 등을 사용할 수 있게 하는 기술 입니다.

기존 가상화 방식은 가상머신 이미지마다 별도의 OS가 필요했습니다. 하지만, 컨테이너 가상화는 이러한 컨테이너를 이용하여 OS를 가상화하여 여러 개의 컨테이너를 Host OS 위에서 동작시킵니다. 

따라서, 기존 가상화 방식보다 빠르고, 메모리를 적게 차지하며, Host OS 커널을 공유하기 때문에 오버헤드가 확연히 적은 방식입니다.

Reference

https://mangkyu.tistory.com/87

https://velog.io/@jiti/%EC%A0%84%EA%B0%80%EC%83%81%ED%99%94-VS-%EB%B0%98%EA%B0%80%EC%83%81%ED%99%94

https://suyeon96.tistory.com/53#Para%--Virtualization%---%EB%B-%--%EA%B-%--%EC%--%--%ED%--%---

https://tech.ktcloud.com/77

http://wiki.hash.kr/index.php/%EC%84%9C%EB%B2%84_%EA%B0%80%EC%83%81%ED%99%94#.ED.95.98.EC.9D.B4.ED.8D.BC.EB.B0.94.EC.9D.B4.EC.A0.80

https://kr.linkedin.com/pulse/container%EC%99%80-kubernetes-%EA%B8%B0%EC%88%A0-%EC%86%8C%EA%B0%9C-jun-hee-shin

Interrupt란?

CPU가 동작하고 있을 때, 입출력 연산과 같이 CPU가 대기해야하는 작업이 끝났을 때 또는 소프트웨어적 예외 상황이 발생하여 처리가 필요할 때 보내는 신호 입니다.

Interrupt를 사용하는 이유?

• I/O 이벤트 상황의 처리 : 입출력 연산이 CPU의 연산 속도 보다 현저히 느릴 뿐만 아니라 모종의 이유로 CPU가 대기해야하는 상황에서 CPU가 아무 일도 하지 않고 있을 수 없기 때문입니다. 예를 들어, 사람의 입력이 필요한 상황이 발생하면 running 중이던 process를 wait/ready 상태로 바꾸고 다른 작업을 수행하며 다시 running 시킬 때 interrupt를 통해 상황이 완료되었음을 CPU에게 알려주는 역할을 수행합니다.                                                                             

• 예외상황의 처리: 우선순위가 앞서는 예외상황이 발생하였을 때 현재 작업을 멈추고 예외상황을 처리하게 하기 위함도 있습니다.

• 선점형 스케쥴링 구현: 선점형 스케쥴링이란, 우선 순위가 높은 process를 먼저 동작 시키는 것입니다. 즉, 기존에 CPU가 하던 작업이 있다면 이를 중단시킨 후 우선 순위가 높은 process를 동작 시키기 위함입니다.

Interrupt 동작과정

• CPU가 어떠한 작업 중에 system call을 통해 인터럽트가 발생합니다.
• CPU는 현재 진행 중인 기계어 코드를 완료하고, 현재 수행 중이던 process의 상태를 PCB(Process Control Block)에 저장합니다. (수행 중이던 Memory 주소, 레지스터 값 등등)
• PC에 다음에 실행할 명령어 주소를 저장합니다.
• 인터럽트 벡터를 읽고 ISR 주소를 얻어 ISR(Interrupt Service Routine)으로 점프하여 작업을 수행합니다.
• 이때 발생한 인터럽트 번호를 토대로 IDT(Interrupt Descriptor Table)에서 인터럽트 번호에 해당하는 함수를 호출하여 작업을 처리합니다.
• 작업이 완료되면 PCB에서 수행중이던 process 상태를 복원하고, 인터럽트가 해제되면 PC에 저장된 주소로 다시 점프해 하던 작업을 수행합니다.

Reference

https://velog.io/@tnddls2ek/OS-%EC%9D%B8%ED%84%B0%EB%9F%BD%ED%8A%B8-Interrupt

컴퓨터 시스템은 다음과 같은 구성요소를 갖고 있습니다.

• CPU(프로세서)
• 메모리(Memory)
• 레지스터(Register)
• 버스(Bus)
• 주변장치

CPU란?

컴퓨터의 중앙처리장치(Central Processing Unit, CPU)이며, 프로세서라고도 불립니다.

연산장치, 제어장치 그리고 레지스터로 구성되어 있으며 이를 통해 명령어를 해석하고 동작을 제어하며 연산을 수행합니다.

그래픽에 특화된 GPU(Graphic Processing Unit), 머신러닝에 특화된 (Tensor Processing Unit)이 있습니다.

*CPU가 유일하게 사용할 수 있는 데이터는 Memory에 존재하는 데이터 입니다.

따라서, 모든 프로그램은 Memory에 적재되어야 실행할 수 있습니다.

*CPU는 각 device controller에 "Command"만 전송 가능합니다.

각 장치로부터 데이터를 읽어올 수는 없습니다.

 메모리(Memory)란?

메모리는 데이터를 저장하는 공간입니다. 

크게 메인 메모리와 캐시로 구분됩니다.

• 메인 메모리
  • CPU가 접근할 수 있는 유일한 저장 장치 입니다.
  • 저장된 데이터를 순차적으로 접근하는 것이 아닌 임의로 접근할 수 있습니다(Random access).
  • 저장된 데이터는 0과 1로 이루어져 있으며, 바이트 단위로 접근할 수 있습니다.
• 캐시(Cache)
  • CPU의 처리 속도는 매우 빠른데 매번 메모리에 접근하여 데이터를 가져오는 것은 많은 시간을 소요할 수 있습니다. 이러한 간극을 해소하기 위해 나온 장치입니다.
  • 데이터 지역성(Locality)을 기반으로 동작합니다. (추후, 자세히 포스팅 하겠습니다.)
  • 메인 메모리의 일부 데이터를 미리 복사해두어서 프로세서가 빠르게 워드 단위의 데이터를 이용할 수 있습니다.

레지스터(Register)란?

CPU에 내장된 가장 작은 저장 장치입니다. CPU가 직접 접근할 수 있는 저장 장치이며, 캐시와 마찬가지로 CPU의 처리 속도 향상에 큰 영향을 미칩니다. 

저장 장치 중에 가장 빠른 속도를 지녔지만, 저장할 수 있는 용량은 32bit에서 64bit 사이의 작은 용량의 데이터만 저장할 수 있습니다.

*레지스터와 메모리의 가장 큰 차이점은, 레지스터는 CPU가 현재 처리하는 데이터를 가지고 있는 장치이고 메모리는 CPU가 필요한 데이터를 저장하고 있는 장치라는 점입니다.

버스(BUS)란?

CPU와 각 장치가 서로 데이터를 주고 받는 장치입니다.

위치와 기능에 따라 분류됩니다.

• 위치에 따른 분류
  • 내부 버스: 프로세서 내부에서 연산장치 - 제어장치- 메모리 인터페이스 등을 연결해주는 장치입니다.
  • 외부 버스: 시스템 버스라고도 불립니다. 프로세서와 메모리, 프로세서와 외부 장치 등을 연결해주는 장치입니다.
• 기능에 따른 분류
  • 제어 버스: 작업을 지시하는 신호가 오고 가는 장치로, 프로세서와 메모리 그리고 주변 장치에서 단방향으로 신호가 전송됩니다.
  • 데이터 버스: 데이터, 명령어 등을 전송하는 장치로, 프로세서와 메모리 그리고 주변 장치에서 양방향으로 신호가 전송됩니다. 일반적으로 데이터 버스의 신호선은 워드의 길이로 결정되며, 성능을 결정짓는 요소입니다.
  • 주소 버스: 작업을 수행할 때(메모리에 데이터 적재 등) 작업할 위치 정보를 전송하는 장치입니다.

주변 장치란?

모니터, 프린터, 스피커와 같이 입출력 장치등 컴퓨터에 연결되어 프로세서의 제어를 통해 동작하는 장치들을 총칭하는 단어입니다.

*컴퓨터 구조 및 설계 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 어셈블리언어 기반으로 작성되었습니다.

논리연산 명령어

초기의 컴퓨터는 워드 전체에 대한 처리에만 관심을 가졌습니다. 하지만 곧 워드 내 일부 비트에 대한 연산 , 심지어는 개개 비트에 대한 연산도 필요하다는 것이 명백해졌습니다. 이를 위해 만들어진 명령어들을 논리연산 명령어 라고 부릅니다.

• 자리이동(shift)

$$0000\,0000\,0000\,0000\,0000\,0000\,0000\,1001_{two} = 9_{ten}$$

위와 같은 값이 있을 때 왼쪽으로 4번 shift 시키는 명령어를 실행하면 다음과 같이 됩니다.

$$0000\,0000\,0000\,0000\,0000\,0000\,1001\,0000_{two} = 14_{ten}$$

이렇게 왼쪽으로 자리이동을 하는 명령어를 sll(shift left logical)이라고 하며, 반대로 오른쪽으로 자리이동하는 명령어를 srl(shift right logical) 이라고 부릅니다. R 형식의 명령어와 기계어 형식으로 표현하면 다음과 같습니다.

$$ sll \quad \$t2,\$s0,4$$

*shamt필드는 shift amount를 나타내는 것으로 자리이동 명령어에서 사용됩니다. 

sll 명령은 또 다른 용도로 사용될 수 있는데 왼쪽으로 $i$비트 자리이동을 하면 $2^i$을 곱한 것과 같은 결과가 됩니다.

• AND

AND 연산은 비트대 비트 연산자로서 두 비트 값이 모두 1일 경우에만 결과가 1이 되는 연산입니다.

$$0000\,0000\,0000\,0000\,0000\,1101\,1100\,0000_{two} $$

$$0000\,0000\,0000\,0000\,0011\,1100\,0000\,0000_{two} $$

위와 같은 t1, t2 값이 있을 때, 다음과 같은 MIPS 명령어를 실행하고 나면

$$and \quad \$t0,\$t1,\$t2$$

t0 레지스터의 값은 다음과 같이 됩니다.

$$0000\,0000\,0000\,0000\,0000\,1100\,0000\,0000_{two}$$

• OR

OR 연산은 AND와 대칭되는 연산으로 두 비트 중 하나만 1이면 결과가 1이 되는 연산자입니다. 

$$or \quad \$t0,\$t1,\$t2$$

위와 같은 명령어를 수행하면 t0 레지스터 값은 다음과 같이 됩니다.

$$0000\,0000\,0000\,0000\,0011\,1101\,1100\,0000_{two}$$

• NOT

NOT연산은 0을 1로, 1을 0으로 바꾸는 연산입니다.

판단을 위한 명령어

컴퓨터가 단순한 계산기와 다른 점은 판단 기능이 있다는 점입니다. 프로그래밍 언어에서는 보통 if 문으로 판단 기능을 표현하는데, MIPS의 경우 beq, bne 명령어를 통해 표현합니다.

• beq: branch if equal

$$beq\quad\,register1\,,register2\,,L1$$

예를 들면 위와 같은 명령어는 'register1과 register2가 같다면 L1에 해당하는 문장으로 이동.' 이라는 뜻입니다.

• bne: branch if not equal

$$bne\quad\,register1\,,register2\,,L1$$

register1과 register2가 다르다면 L1으로 이동하라는 뜻입니다.

*beq, bne 두 명령어를 조건부 분기(conditional branch) 라고 부릅니다.

*어셈블러가 컴파일러나 어셈블리 언어 프로그래머가 지겨운 분기 주소 계산을 하지 않도록 해줍니다.

*컴파일러가 소스 프로그램에는 없는 분기 명령이나 레이블을 만들어 내는 경우가 많이 있습니다. 이를 통해, 필요한 레이블과 분기 명령을 일일이 표시하지 않아도 되는 것이 상위 수준 프로그래밍 언어의 장점 중 하나이며, 코딩이 더 빨라지는 이유이기도 합니다.

• Loop

판단 기능은 둘 중 하나를 선택(if 문장 사용)하는 것도 중요하지만, 계산의 반복(순환문 사용)에도 중요합니다.

• slt, slti: set on less than

비교 명령은 부호 있는 수와 부호 없는 수 사이의 이분법도 다루어야 한다. 어떤 때는 MSB가 1인 수가 음수를 나타내며, 이때는 MSB가 0인 어떤 양수보다도 작으며, 부호가 없는 정수의 경우에는 MSB가 1인 수가 MSB가 0인 어떤 양수보다도 더 큽니다. MIPS는 이 두가지 경우를 처리할 수 있도록 set on less than의 두가지 유형의 명령어를 제공합니다. 

*slt, slti는 부호 있는 수에, sltu, sltiu는 부호없는 정수에 사용합니다.

*blt(branch on less than) 명령어는 제외되었습니다. 이 명령어는 구현하게되면 클럭 속도가 느려지거나 이 명령 실행에 별도의 클럭 사이클이 더 필요하게 되므로 하드웨어는 간단해야 좋다는 von Neumann의 경고를 준수하여 MIPS 구조에서는 제외되었습니다.

MIPS에서는 부호 있는 수와 부호 없는 수에 대하여 MSB의 이중적 의미를 이용하여 배열 경계 검사 비용을 줄이는 방법이 있습니다. 부호 있는 정수를 부호없는 정수처럼 다루면 $0 <= x < y$ 검사비용을 낮출 수 있는데, 이 검사는 인덱스가 배열의 한계를 벗어났는지 확인하는 검사에 딱 맞습니다. 핵심은 2의 보수로 표현된 음수가 부호없는 정수에서의 큰 수 처럼 보인다는 것입니다. 

* 여기서 말하는 배열의 한계란 다음과 같습니다. 배열의 index는 배열의 length를 벗어날 수 없다. 즉, length보다 큰 index를 갖거나 음수인 index를 가질 수 없다는 것입니다.

$$ sltu \quad \, $t0\,,$s1\,,$t2$$

$$beq \, $t0\,,$zero\,,IndexOutOfBounds$$

위 명령어는 경계를 검사하는 명령어로 부호없는 정수 연산을 이용하여 한번에 두 가지 모두 검사하는 명령어입니다.

s1은 index를 t2는 배열 사이즈를 의미합니다. 

$sltu\quad \, \$t0\,,\$s1\,,\$t2$ 를 보면 s1(index) >= length or s1(index) < 0이라면 t0 = 0 가 되는 명령어 입니다.

$beq\quad \, \$t0\,,\$zero\,,IndexOutOfBounds$를 보면 t0 == 0 일 경우, Error를 발생시키도록 되어 있죠.

이렇게 MSB의 이중적 의미를 통해 한 명령어로 경계 검사를 한번에 수행할 수 있습니다.

• case/switch 문장

대부분의 프로그래밍 언어는 특정 변수의 값에 따라 여러가지 중 하나를 선택하는 case나 switch 문장을 갖고 있습니다. 가장 간단한 방법은 계속적인 조건 검사를 통해 switch를 if-then-else의 연속으로 변환하는 것입니다.

다만, 여러 코드의 시작주소를 표로 만들면 더 효율적으로 구현할 수 있기 때문에, 프로그램은 점프 주소 테이블(jump address table) 또는 점프 테이블(jump table)의 인덱스만 계산해서 해당 루틴으로 점프할 수 있습니다.

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

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

명령어는 컴퓨터 내부에서 높고 낮은 전기 신호의 연속으로 저장되므로 숫자로 표현할 수 있습니다. 실제로 명령어의 각 부분을 숫자로 볼 수 있으며, 이 숫자들을 나란히 늘어놓으면 명령어가 됩니다.

예를 들어, 다음 어셈블리 명령어의 실제 MIPS의 언어 버전을 십진수와 이진수의 형태로 표현하면 다음과 같습니다.

$$add \, \$t0,\$s1,\$s2$$

<십진수 표현법>

<이진수 표현법>

*세부 설명은 MIPS 명령어 필드 설명 부분에서 진행하겠습니다.

위 예제에서 보인 레이아웃을 명령어 형식(instruction format)이라고 합니다. MIPS 명령어 길이는 데이터 워드와 마찬가지로 32비트이며, "간단하게 하기 위해서는 규칙적인 것이 좋다" 라는 설계 원칙에 따라 모든 MIPS 명령어는 32비트 입니다.

어셈블리 언어와 구별하기 위하여 명령어를 숫자로 표현한 것을 기계어(machine language)라고 하고, 이런 명령어들의 시퀀스를 기계 코드(machine code)라 합니다.

모든 컴퓨터의 데이터 길이는 4의 배수이므로 16진수(hexadecimal)가 많이 사용됩니다. 기수 16은 2의 멱승이므로 이진수 4비트를 16진수 숫자 하나로 쉽게 바꿀 수 있으며, 그 반대도 마찬가지 입니다. 

MIPS 명령어 필드

• op: 명령어가 실행할 연산의 종류로서, 연산자(opcode)라고 부릅니다.
• rs: 첫 번째 근원지(source) 피연산자 레지스터를 의미합니다.
• rt: 두 번째 근원지 피연산자 레지스터를 의미합니다.
• td: 목적지(destination) 레지스터를 의미합니다. 연산 결과가 기억됩니다.
• shamt: 자리이동(shift)량을 의미합니다.
• funct: 기능(function)을 의미합니다. op 필드에서 연산의 종류를 표시하고 funct 필드에서 연산을 구체적으로 지정합니다.

5비트 필드로는 부족한 경우가 있을 수 있습니다. 설계원칙 4번 "좋은 설계에는 적당한 철충이 필요하다." 라는 원칙에 의거하여 MIPS 설계자들이 택한 절충안은 모든 명령어의 길이를 같게 하되, 명령어 종류에 따라 형식은 다르게 하는 것이었습니다. 위와 같은 명령어 형식을 R타입 또는 R 형식(R은 Register를 의미합니다.)이라 하며, 이것만으로는 불충분하기 때문에 I 타입 또는 I 형식(I는 immediate)라는 명령어 형식을 만들었습니다. I 타입은 수치 연산과 데이터 전송 명령어에서 사용되며 그 모양은 다음과 같습니다.

각 필드는 6bits, 5bits, 5bits, 16bits입니다. I - 형식의 명령어에서는 rt필드의 의미가 바뀌어 적재 결과가 들어갈 목적지 레지스터 번호를 표시하는 것으로 바뀌었습니다.

명령어 형식이 여러가지가 되면서 하드웨어는 복잡해지지만 모든 형식을 유사하게 함으로써 복잡도를 낮출 수 있었습니다.

*컴퓨터 구조 및 설계 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}$$

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

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

하드웨어 설계의 3대 원칙

1. 간단하게 하기 위해서는 규칙적인 것이 좋다.

덧셈 같은 연산의 피연산자(operand)는 더해질 숫자 두 개와 합을 기억할 장소 하나, 총 3개인 것이 자연스럽다. 이렇듯 모든 명령어가 피연산자를 반드시 세 개씩 갖도록 제한하는 것은 하드웨어를 간단하게 할 수 있는 방법이다. 

반대로 피연산자(operand)에 대한 변수 갯수가 가변적이라면 하드웨어가 매우 복잡해질 것이다. 

이런 관점에서 하드웨어 설계의 3대 원칙 중 첫번째를 도출할 수 있다. 

2. 작은 것이 더 빠르다.

MIPS는 보통 32개의 레지스터를 사용한다. 레지스터가 아주 많아지면 전기신호가 더 멀리까지 전달되어야 하므로 클럭 사이클 시간이 길어진다. 

물론 32개가 아닌 31개로 구성하면 빨라진다는 것이 아니다. 

따라서, 컴퓨터 설계자는 더 많은 레지스터를 원하는 프로그램의 갈망과 클럭 사이클을 빠르게 하고 싶은 본인의 바람 사이에서 적절한 타협점을 찾아야 할 것이다.

*레지스터가 메모리보다 작으면서 속도는 더 빠른데 여기에도 해당이 되는 원칙이다.

3. 자주 생기는 일을 빠르게 하라.

프로그램의 연산에서 상수를 사용하는 경우는 많이 있다. SPEC CPU2006 벤치마크를 실행해보면 MIPS의 산술 명령의 절반 이상이 상수를 피연산자로 사용함을 알 수 있다. 상수를 메모리에서 읽는 방식이 아니라, 상수 필드를 갖는 산술 명령어를 통해 사용하면 연산이 훨씬 빨리지고 에너지를 덜 소모하게 된다.

*update(2022.09.29)

4. 좋은 설계에는 적당한 절충이 필요하다. 

예를 들어, MIPS 명령어 필드에서 5비트 필드 중 하나를 주소로 쓴다면 $2^5 = 32$ 보다 작은 값만을 사용할 수 있다. 이 필드는 큰 배열이나 자료구조에서 한 원소를 선택하는데 사용되므로 32보다 큰 값이 필요한 경우가 많아 5bit 필드로는 부족하다.  이러한 문제 때문에 모든 명령어의 길이를 같게 하고 싶은 생각과 명령어 형식을 한가지로 통일하고 싶은 생각 사이에서 충돌이 생긴다. 

이와 같은 상황에서, 컴퓨터 설계자는 적당한 절충안을 통해 설계를 진행하여야 한다.

피연산자

상위 수준 언어 프로그램과는 달리 산술 명령어의 피연산자에는 제약이 있습니다. 레지스터(register)라고 하는 하드웨어로 직접 구현된 특수 위치만 사용할 수 있다는 것입니다. 또한, 프로그래밍 언어에서 사용하는 변수와 하드웨어 레지스터의 큰 차이점 하나는 레지스터는 개수가 한정되어 있다는 점입니다. 보통 32개의 레지스터로 구성되어 있는데, 이는 산술 명령어의 각 피연산자는 32개의 32비트 레지스터 중 하나이어야 한다는 제약이 추가됩니다. 

*MIPS 구조에서 레지스터의 크기는 32bit 이며, 워드(word)라고 부른다. 

프로그래밍 언어에는 값 하나만 기억하는 단순 변수 외에 배열(array)나 구조체(structure) 같은 복잡한 자료구조가 있습니다.

이러한 구조는 메모리(memory)에 보관합니다.

다만, 위에서 설명한 바와 같이 MIPS의 산술연산은 레지스터에서만 실행되므로 메모리와 레지스터간의 데이터를 주고받은 명령어가 있어야 합니다. 이러한 명령어를 데이터 전송 명령어(data transfer instruction)이라고 합니다.

메모리에 기억된 데이터 워드는 주소(Address)를 통해 접근하게 됩니다.

*적재(load): 메모리에서 레지스터로 데이터를 복사해 오는 데이터 전송 명령. 적재 명령은 연산자 이름, 메모리에서 읽어 온 값을 저장할 레지스터, 메모리  접근에 사용할 상수와 레지스터로 구성된다.

*저장(store): 레지스터에서 메모리로 데이터를 보내는 데이터 전송 명령. 저장 명령은 연산자 이름, 저장할 데이터를 갖고 있는 레지스터, 배열 원소 선택에 사용할 변위, 베이스 레지스터로 구성된다. 

변수를 레지스터와 연관 짓는 일 뿐만 아니라 배열이나 구조체 같은 자료구조를 메모리에 할당하는 것은 컴파일러의 임무입니다. 이러한 작업이 진행되어야 컴파일러가 자료구조의 시작 주소를 데이터 전송 명령에 넣을 수 있게 됩니다.

주소는 프로그램에서 8bit로 구성된 바이트(Byte)를 많이 사용하므로, 대부분의 컴퓨터는 바이트 단위로 주소를 지정합니다. 

워드 주소는 워드를 구성하는 4바이트 중 하나를 사용하므로, 연속된 워드의 주소는 4씩 차이나게 됩니다. 

컴퓨터 별로 워드 주소를 사용하는 방법은 두가지가 있습니다. 제일 왼쪽, 즉 최상위(big end) 바이트 주소를 워드 주소로 사용하는 방식과 제일 오른쪽, 즉 최하위(little end) 바이트 주소를 워드 주소로 사용하는 방법이 있습니다.

컴퓨터가 갖고 있는 레지스터보다 프로그램에서 사용하는 변수가 더 많은 경우가 자주 있습니다. 레지스터의 개수는 제한되어 있으므로 컴파일러는 자주 사용되는 변수를 가능한 한 많이 레지스터에 담고 나머지 변수는 메모리에 저장했다가 필요할 때 꺼내서 레지스터에 넣습니다. 

*이때 활용되는 기법으로, 자주 사용하지 않는(또는 한참 후에 사용할) 변수를 메모리에 넣는 일을 레지스터 스필링(Register spilling)이라고 한다.

"작을 수록 빠르다 라는 원칙에 의하면 레지스터가 더 작으므로 메모리보다 속도가 느려야한다. 실제로 레지스터가 더 빠르며, 데이터가 레지스터에 있으면 더 빠르게 접근할 수 있다. 

레지스터는 메보리보다 접근시간이 짧고 처리량도 많으므로, 레지스터에 저장된 데이터를 사용하면 시간이 절약되고 사용하기도 간편하다. 뿐만 아니라, 에너지도 절약된다.

따라서, 좋은 성능을 얻고 에너지를 절약하기 위해서는 컴파일러가 레지스터를 효율적으로 사용하여야한다.