뒤돌아보기

이 글은 책 컴퓨터 밑바닥의 비밀 chapter 4.7 의 내용을 읽고 요약한 글입니다. 

4.7.1 복잡함을 단순함으로

• 마이크로코드의 설계 아이디어: 복잡한 기계 명령어를 CPU 내부에서 비교적 간단한 기계 명령어로 변환하는것으로 컴파일러는 이 프로세스를 알지 못함
• 마이크로코드에 버그가 있으면 컴파일러는 이를 피하기 위해 할 수 있는 일이 없음

또한 복잡한 기계명령어 하나가 같은 일을 하는 간단한 명령어 여러개보다 느리게 실행된다는 사실을 발견

4.7.2 축소 명령어 집합의 철학

• 복잡 명령어 집합(Complex Instruction Set Computer, CISC) 에 대한 반성으로 축소 명령어(Reduced instruction Set Computer, RISC) 집합의 철학이 탄생

3가지 측면을 주로 반영

1. 명령어 자체의 복잡성

• 복잡한 명령어를 제거하고 간단한 명령어 여러개로 대체
• 마이크로코드 설계가 필요없으며 컴파일러에서 생성된 기계 명령어의 CPU 제어 능력이 크게 향상됨
• 명령어 집합을 줄인다는 아이디어는 명령어 집합의 명령어 개수를 줄이다는 의미가 아니라, 하나의 명령어당 들여야 하는 연산이 더 간단하다는 의미

2. 컴파일러

MULT A B

a = a * b; // 고급 언어와 매우 유사. 이런 설계는 고급 언어와 기계 명령어 사이의 차이를 줄임

(2) RISC의 경우

1. 메모리 주소 A의 데이터를 읽어 레지스터에 저장
2. B의 데이터를 읽어 레지스터에 저장
3. ALU가 레지스터 값을 이용하여 곱셈 연산 수행
4. 곱셈 결과를 다시 메모리에 씀

• RISC에서는 LOAD, PROD, STORE 명령어를 사용하여 작업을 단계별로 완료해야 함
  • LOAD: 메모리에서 레지스터로 데이터를 적재
  • PROD: 두 레지스터에 저장된 숫자의 곱셈 연산을 수행
  • STORE: 레지스터의 데이터를 다시 메모리에 씀

어셈블리어 코드

LOAD RA, A
LOAD RB, B
PROD RA, RB
STORE A, RA

• 복잡 명령어 집합을 사용하는 프로그램보다 기계 명령어를 더 많이 사용
• RISC의 의도는 프로그래머가 직접 어셈블리어로 코드를 작성하는 것이 아니라, 이 작업을 컴파일러에게 맡기고 컴파일러가 구체적인 기계 명령어를 자동으로 생성하게 하는 것

4.7.4 명령어 파이프라인

• 위 어셈블리어 코드는 각 명령어가 매우 간단하여 실행 시간이 모두 거의 동일하여 파이프라인 기술을 통해 실행 효율을 높일 수 있음

4.7.5 천하에 명성을 떨치다

• 1980년대 중반 RISC 기반의 CPU가 CISC 기반 CPU를 압도

이 글은 책 컴퓨터 밑바닥의 비밀 chapter 4.6 의 내용을 읽고 요약한 글입니다. 

4.6.1 프로그래머의 눈에 보이는 CPU

• CPU는 단순하게 메모리에서 명령어를 읽어 실행하기만 하면 됨
• 어떤 프로그램이든 컴파일러에 의해 기계 명령어로 변환될 뿐

4.6.2 CPU의 능력 범위: 명령어 집합

• 명령어 집합은 우리에게 CPU가 할 수 있는 일을 알려줌
• 서로 다른 형태의 CPU는 다른 유형의 명령어 집합을 가지고 있음

4.6.3 추상화: 적을수록 좋다

• 1970년까지 컴파일러가 성숙하지 못해 신뢰도 낮았음
• 많은 프로그램이 어셈블리어로 작성되었는데 명령어 집합이 더욱더 풍부해야되고 명령어 자체 기능도 더 강력해야 한다고 여겼음

4.6.4 코드도 저장 공간을 차지한다

• 실행파일은 기게 명령어와 데이터를 모두 포함하며 디스크 저장 공간을 차지하고, 실행시에는 메모리에 적재 되어 메모리 저장 공간을 차지
• 옛날 컴퓨터는 메모리의 크기가 몇 KB로 작았는데 더 많은 프로그램을 적재하려면 기계 명령어는 더 세밀하게 설계해서 프로그램이 차지하는 저장공간을 줄였어야 함

아래 3가지 요구 사항을 만족해야 함

1. 하나의 기계 명령어로 더 많은 작업을 완료할 수 있도록
2. 기계 명령어 길이 가변적 (간단한 명령어는 짧고, 복잡한 명령어는 길게)
3. 밀도를 높여 공간을 절약하기ㅇ 위해 고도로 인코딩

4.6.5 필연적인 복잡 명령어 집합의 탄생

당시 산업계의 요구사항을 충분히 만족시켰지만 새로운 문제가 발생

• CPU명령어 집합은 모두 hardwired (직접 연결) 방식으로 효율적이지만 유연성이 떨어짐

하드웨어를 변경하는 것은 번거롭지만 소프트웨어를 통해 대체 가능 → microcode 등장

단일 복잡 명령어 → 마이크로코드 ROM → 간단한 명령어들

• 더 많은 명령어를 추가할 때 주요 작업은 마이크로 코드 수정에 집중되며 하드웨어 수정은 거의 필요하지 않기에 CPU 설계 복잡도를 낮출 수 있음

4.6.6 마이크로코드 설계의 문제점

• 버그 수정이 훨씬 어렵고 마이크로코드 설계가 트랜지스터를 매우 많이 소모

이 글은 책 컴퓨터 밑바닥의 비밀 chapter 4.2 의 내용을 읽고 요약한 글입니다. 

4.2.1 컴퓨터의 CPU 사용률은 얼마인가?

• 게임, 영상 편집, 이미지처리 같은 일을 하지 않는 한 대부분 컴퓨터의 CPU 사용률은 낮음(7~8%)
• Windows 경우 아래와 같이 Task Manager 의 Details 탭의 CPU 컬럼에서 확인할 수 있다.
• 근데 System Idle Process 항목은 뭐길래 96%를 차지하고 있는걸까?

4.2.2 프로세스 관리와 스케쥴링

• OS는 프로세스에 우선순위를 할당하고 이에 따라 스케쥴러가 스케쥴링할 수 있도록 대기열에 프로세스를 넣음

4.2.3 대기열 상태 확인: 더 나은 설계

• 준비 완료 대기열이 비어있다면 OS가 스케쥴링해야 할 프로세스가 없고 CPU는 유휴상태임을 의미

if(queue.empty())
{
    do_something();
}

• 위처럼 코드를 작성할 수도 있지만 커널은 if 같은 예외처리 구문으로 가득하기 때문에 코드가 번잡해보일 수 있음 → 항상 실행할 수 있는 프로세스를 찾을 수 있도록 하면 됨
  • linked list에서 sentinel 노드를 사용하는 이유
• NULL판단 로직이 제거되어 코드 오류가능성이 줄고 구조가 깔끔하게 됨

*System Idle Process가 유휴 작업이라는 프로세스 by 커널 설계자. 항상 준비완료 상태이며 우선순위가 가장 낮음

• 유휴 프로세스는 무엇을 하나? 이를 설명하기 위해서 CPU를 이야기 해야한다.

4.2.4 모든 것은 CPU로 돌아온다

• halt 명령어를 통해 CPU 내부의 일부 모듈을 절전 상태로 전환하여 전력 소비를 크게 줄임
  • 커널 상태에서 CPU로만 실행할 수 있음

참고) 일시중지(suspend) vs halt
- sleep같은 함수는 일시 중지로 해당 함수를 호출한 프로세스만 일시 중지
- CPU가 halt 명령어를 실행하는 것은 시스템 내 더 이상 실행할 준비가 완료된 프로세스가 없다는 의미

4.2.5 유휴 프로세스와 CPU의 저전력 상태

• halt 명령어를 지속적으로 실행해주는 순환이 있어 CPU는 저전력 상태로 진입하기 시작

while (1)
{
    while (!need_resched())
    {
        cpuidle_idle_call(); // halt 명령어 실행
    }
}

4.2.6 무한 순환 탈출: 인터럽트

위 코드의 이상한점들

1. 위 코드를 보면 무한 while loop 구조 내부에 break/return 문이 없는데 어떻게 빠져나올까?
2. 무한 loop이 있어서 프로그램이 CPU 독점하는 것으로 보이지 않음

• OS는 일정 시간마다 타이머 인터럽트를 생성하고, CPU는 인터럽트 신호를 감지해 인터럽트 처리 프로그램을 실행함
• 인터럽트 처리함수에는 프로세스의 상태를 파악해 준비완료된 프로세스가 있으면 기존 프로세스를 중단하고 준비완료된 프로세스를 실행

이 글은 책 컴퓨터 밑바닥의 비밀 chapter 4.1 의 내용을 읽고 요약한 글입니다. 

트랜지스터의 기능은 단자 한쪽에 전류를 흘리면 나머지 단자 두 개에 전류가 흐르게/흐르지 못하게 할 수 있는데 본질은 스위치와 동일하다.

트랜지스터를 이용해 아래의 3가지 회로를 만들 수 있다.

• 논리곱 게이트(AND 게이트): 스위치기 두개가 동시에 켜질 때만 전류가 흐르고 등이 켜짐
• 논리합 게이트(OR 게이트): 두 스위치 중 하나라도 켜져 있으면 전류가 흐를 수 있으며 등이 켜짐
• 논리부정 게이트(NOT 게이트): 스위치를 닫으면 전류가 흘러 등이 켜지지만, 스위치를 열면 전류가 흐르지 않고 등이 꺼짐

연산 능력은 어디에서 나올까?

CPU의 가장 중요한 능력인 연산중 덧셈을 예로 들면, 0과 1만 아는 2진법을 사용

• 0 + 0 의 결과(result)는 0이며, 자리올림수(carry)도 0
• 0 + 1 의 결과는 1, 자리올림수 0
• 1 + 0 의 결과는 1, 자리올림수 0
• 1 + 1 의 결과는 0, 자리올림수 1

먼저 자리올림수는 두 입력 값 두개가 모두 1일 때만 1 ⇒ AND 게이트를 사용하면 된다.

그렇다면 결과는? 두 입력값이 다를 때만 1이고 같으면 0이다. → 배타적 논리합 게이트 (XOR) 을 사용하는데 이도 AND, OR, NOT 게이트로 구성할 수 있다.

⇒ 즉 2진법 덧셈을 AND 게이트 1개, XOR 게이트 1개를 조합해 구현할 수 있다.

배타적 논리 합 게이트 예시

더보기

 

신기한 기억 능력

정보를 기억하는 회로란?

• S=1, R=0인 경우 Q는 항상 1을 출력
• S=0, R=1인 경우 Q는 항상 0을 출력하는데 이때 회로에 해당 값이 저장되었다고 할 수 있다.

위는 정보를 저장하기 위해 S, R 단자 값을 동시에 설정해야 하는데 아래처럼 하면 실제로 저장하는데 필요한 입력은 D의 비트 하나이다.

* EN 은 저장 여부를 선택하는데 사용되는 단자

• D단자가 0이면 전체 회로가 저장하는 값은 0
• D단자가 1이면 전체 회로가 저장하는 값은 1

레지스터와 메모리의 탄생

여러비트를 저장하기 위해서는 위의 회로를 복제하여 붙여 넣기만 하면 된다. → 이 조합회로를 레지스터(Register)라고 부른다

전원이 연결되어있는 한 이 회로는 정보를 저장할 수 있지만 전원이 끊기면 정보는 사라짐 → 메모리가 전원이 꺼지면 더이상 데이터를 저장할 수 없는 이유이다.

하드웨어의 기본 기술: 기계 명령

하나하나의 명령어에는 수많은 조합이 있을 수 있으므로 모든 경우를 기계 명령어로 설계하는 것은 불가능하다

⇒ CPU는 작동 방식이나 기능이고, 프로그래머는 명령어 집합을 이용해 전략을 제시하면 된다

소프트웨어와 하드웨어 간 인터페이스: 명령어 집합(Instruction set)

• 명령어 집합: CPU가 실행할 수 있는 명령어와 피연산자를 묶은 것
• 고급 프로그래밍 언어는 컴파일러를 통해 기계 명령어로 변환되는데, 이 집합을 명령어 집합이라 함

이 글은 책 컴퓨터 밑바닥의 비밀 chapter 3.4의 내용을 읽고 요약한 글입니다. 

3.4.1 힙 영역이 필요한 이유

• 프로그래머가 수명 주기를 포함하여 완전히 직접 제어할 수 있는 매우 큰 메모리 영역
• 어떻게 힙 영역에 메모리를 할당하고 해제하는지 구현

3.4.2 malloc 메모리 할당자 직접 구현하기

• 메모리 할당자는 적절한 크기의 메모리 영역을 제공하기만 하고 무엇을 저장할지 신경쓰지 않음
  • integer, floating number 등 신경쓰지 않고 단순한 바이트의 연속에 지나지 않음
  • 커다란 배열 형태

힙 영역 위에서 두가지 문제 해결

1. malloc 함수 구현
   1. 메모리 영역을 요쳥하면 힙 영역에 가능한 메모리 영역 찾아 요청자에게 반환
2. free 함수 구현
   1. 메모리 영역의 사용이 완료되었을 때 메모리 영역을 반환하는 방법 구현

3.4.3 주차장에서 메모리 관리까지

주차장에 비유하여 표현하면 2가지 목표를 만족시켜야 함

1. 주차할 위치를 빠르게 찾음. 요청된 크기를 만족하는 여유메모리를 빨리 찾음
2. 주차장 사용률 극대화. 메모리를 요청할 때 가능한 많은 메모리 할당 요청을 만족시켜야 함

4가지 문제점

1. 메모리 조각의 할당 상태 추적
2. 단일 메모리 할당 요청의 요구사항을 만족하는 사용 가능한 메모리 조작이 매우 많을 때 할당 기준
   1. 6바이트 요청했는데 여유 메모리 공간이 16, 32, 8 바이트 일때
3. 16바이트 메모리를 요청해야 하는데 여유 메모리 조각의 크기가 32바이트라서 16바이트가 남는 경우
4. 사용 반환된 메모리를 어떻게 처리해야 하나?

3.4.4 여유 메모리 조각 관리하기

• 위의 4가지 문제점들 중 1번 해결을 위한 방법으로 linked list로 메모리 사용정보를 기록하는 방식

2가지 정보를 기록

• 메모리 조각의 크기를 기록한 숫자 - header라고 하며 32비트
  • 메모리 조각이 비어있는지 알려주는 설정값(flag) - 1비트
• 할당 가능한 메모리 조각을 payload라고 함 (메모리 주소)

3.4.5 메모리 할당 상태 추적하기

한조각은 4바이트

• 16/1: 할당된 메모리 조각 크기가 16바이트를 의미
• 32/0 : 여유 메모리 조각이 32 바이트
• 0/1: 끝을 표시하는 특수한 표시로 4바이트

이 방식으로 메모리 조각의 여유/할당 상태 파악 및 추적할 수 있음

3.4.6 어떻게 여유 메모리 조각을 선택할 것인가: 할당 전략

• 4바이트 메모리를 요청받을 때 요구사항을 충족하는 여유 메모리가 두조각이 있음
  • 8/0, 32/0 중 어떤것을 반환할 것인가? 다양한 할당 전략 방식이 있음

메모리 할당 전략 방식

1. 최초 적합 방식

• 제일 앞부터 탐색하다가 가장 먼저 발견된 요구사항을 만족하는 항목을 반환
• 단순하지만, 처음부터 사용가능한 메모리 조각을 찾으므로 앞부분에 작은 메모리 조각이 많이 남을 가능성이 높음

2. 다음 적합 방식

• 최초 적합 방식과 유사하지만 메모리를 요청할 때 처음부터 검색하는 대신 적합한 여유 메모리 조각이 마지막으로 발견된 위치에서 시작한다는 점이 다름
• 탐색 시작 위치가 달라져, 더 빠르게 여유 메모리 조각을 탐색할 수 있음
• 단점: 메모리 사용률은 최초 적합 방식에 미치지 못한다는 것이 연구로 밝혀짐

3. 최적 적합 방식

• 사용 가능한 메모리 조각을 모두 찾은 후 요구 사항을 모두 만족하면서 크기가 가장 작은 조각 반환
• 메모리를 더 잘 활용한다는 장점이 있음
• 사용가능한 모든 메모리 조각을 탐색하기 때문에 빠르지 않음

실제로는 더 복잡한 원리로 적합한 방식을 찾아 할당

3.4.7 메모리 할당하기

• 12바이트 메모리를 요청했을 때 적절한 여유 메모리 조각이 12 바이트라고 가정
  • 헤더인 4바이트를 제외한 나머지 크기

• 할당된 것으로 표시하고 머리 정보 뒤에 따라오는 메모리 조각의 주소를 요청자에게 반환하면 됨

• 위는 이상적인 경우로 12바이트 메모리를 요청했을 때 찾아낸 여유 메모리 조각의 크기가 더 큰 경우가 대부분
• 아래와 같이 찾아낸 메모리 조각이 32바이트라면? 메모리가 낭비되고 내부 단편화(fragmentation) 발생함

• 이 문제를 해결하기 위해 여유 메모리 조각을 두개로 분할하여 앞부분은 할당한 후 반환하고 뒷부분은 좀 더 작은 크기의 새로운 여유 메모리 조각으로 만듦

3.4.8 메모리 해제하기

• 사용자가 메모리를 요청할 때 얻은 주소를 ADDR이라고 가정
• free(ADDR)을 호출하면 매개변수인 ADDR에서 머리 정보 크기인 4바이트를 빼는 것으로 메모리 조각의 머리 정보 얻을 수 있음
• 머리 정보에서 얻은 할당 설정값을 여유 메모리로 바꾸면 해제가 완료됨

메모리 해제 시 중요한 점 하나

• 해제되는 메모리 조각과 인접한 메모리 조각이 여유 메모리 조각일 때 단순히 해제 여부만 기록하면 아래 상황 발생

• 해제된 메모리 조각에 인접한 아래쪽 메모리 조각도 비어있음
• 메모리를 해제 할 때 둘을 합치는게 나을까? 그대로 두는게 나을까?

그대로 두는 경우

• 20 바이트 요청이 오는 경우 두 조각 중 어느 것도 요구사항을 만족시키지 못함

메모리를 해제 할 때 메모리 조각을 병합할 때

1. 즉시: 비교적 간단하지만 부담이 발생. 하지만 간단해서 여전히 이 전략을 많이 선택
2. 요구사항을 충족하는 여유 블록을 찾을 수 없을 때: 실제 메모리 할당자가 선택하는 전략

3.4.9 여유 메모리 조각을 효율적으로 병합하기

• 해제하는 메모리 조각의 위 아래가 모두 비어있다면? 아래는 헤더 정보로 알 수 있지만 위의 정보는 어떻게 알 수 있나?

• 메모리 조각 끝에 footer 정보를 추가

• 조각의 꼬리 정보는 그 다음에 위치한 조각의 머리 정보와 인접해 있어 현재 조각의 머리 정보에서 4바이트를 빼면 이전 조각의 꼬리 정보를 획득할 수 있음

• header와 footer 정보는 메모리 조각을 doubly linked list로 만듦