본 글은 책 "혼자 공부하는 컴퓨터 구조+운영체제" 의 Chapter 11. CPU 스케쥴링 부분을 읽고 정리한 내용입니다.

CPU 스케쥴링이란?

• 프로세스들에게 공정하게 합리적으로 CPU 자원을 배분하는 것
• 제대로 안되면 반드시 실행되어야 할 프로세스들이 실행되지 못하거나 당장 급하지 않은 프로세스들만 주로 실행되는 등 무질서한 상태가 발생할 수도 있음

프로세스 우선순위

• 아주 단순하게 생각해 봤을 때 CPU를 사용 요청을 먼저 보낸 프로세스들을 순서대로 CPU 이용하게 하는 방법
• 합리적인 방식같지만 좋은 방식은 아님
  • 단순히 FIFO 형태로 CPU를 이용하면 비효율적으로 대기 시간이 길 수 있음
  • 또한 프로세스 마다 우선순위가 다르기 때문

일반적인 프로세스가 실행되는 과정

• 대부분의 프로세스들은 CPU와 입출력장치를 모두 사용하며 실행됨 → 실행/대기 상태 반복
  • 예를들어 워드 프로세서에서 CPU를 이용해 명령어 실행, 사용자로부터 입력받은 내용을 보조기억장치에 저장, CPU를 사용하여 명령어를 실행, 사용자가 입력한 내용을 화면에 출력

• 프로세스 종류마다 입출력장치를 이용하는 시간과 CPU를 이용하는 시간의 양에 차이가 있음
  • I/O bound process: 비디오 재생이나 디스크 백업 작업을 담당하는 프로세스와 같이 입출력 작업이 많은 프로세스 (실행상태보다 입출력을 위한 대기 상태에 더 많이 머무름)
  • CPU bound process: 복잡한 수학 연산, 컴파일, 그래픽 처리 작업을 담당하는 프로세스와 같이 CPU 작업이 많은 프로세스 (대기 상태보다 실행 상태에 더 많이 머무름)

• I/O bound process와 CPU bound process가 동시에 CPU 자원을 요구한 경우
  • I/O bound process를 빨리 실행시켜 입출력 장치를 끊임없이 작동시켜 대기 상태가 되면 CPU bound process에 집중적으로 CPU를 할당하는 것이 더 효율적
    ⇒ 이를 위해 운영체제는 프로세스마다 priority를 부여 (PCB에 명시)

참고) 프로세스의 우선순위를 확인할 수 있는 명령어

$ ps -el
  UID   PID  PPID        F CPU PRI NI       SZ    RSS WCHAN     S             ADDR TTY           TIME CMD
    0     1     0     4004   0  46  0 411466656  19712 -      Rs                  0 ??        12:30.24 /sbin/launchd
    0   146     1     4004   0  31  0 410161104   1776 -      Ss                  0 ??         0:00.01 /usr/libexec/iou
    0   298     1     4004   0  31  0 410536368  41248 -      Ss                  0 ??        10:18.55 /usr/libexec/log
    0   299     1     4004   0   4  0 410397920   2368 -      Ss                  0 ??         0:00.22 /usr/libexec/smd
    0   300     1     4004   0  31  0 410401168   8080 -      Ss                  0 ??         0:53.46 /usr/libexec/Use
    0   302     1     4004   0  20  0 410160192   1024 -      Ss                  0 ??         0:05.09 /System/Library/
    0   303     1  1004004   0  50  0 410516816   7200 -      Ss                  0 ??         7:27.37 /System/Library/

• PRI 컬럼이 process 의 priority 우선순위를 의미

스케쥴링 큐

• PCB에 우선순위가 적혀 있다고 하지만 CPU를 사용할 다음 프로세스를 찾기 위해 운영체제가 모든 프로세스의 PCB를 순회하는건 비효율적
• 또한 새로운 프로세스들이 언제든 생길 수 있음

⇒ 스케쥴링 큐를 구현해 모든 프로세스들을 줄세워 관리
* 자료 구조 관점에서 큐는 FIFO이지만 스케쥴링 큐는 반드시 FIFO일 필요는 없음

크게 Ready queue와 Waiting queue가 있음

• Ready queue: CPU를 이용하고 싶은 프로세스들이 서는 줄
• Waiting queue: 입출력장치를 이용하기 위해 대기 상태에 접어든 프로세스들이 서는 줄
  
  

• 준비 상태에 있는 프로세스들의 PCB는 준비 큐의 마지막에 삽입 되어 CPU를 사용할 차례를 기다림
• 운영체제는 큐에 삽입된 순서대로 프로세스들을 하나씩 꺼내어 실행하되, 그 중 우선순위가 높은 프로세스를 먼저 실행

• 대기 상태에 있는 프로세스도 같은 장치를 요구한 프로세스들은 같은 대기 큐에서 기다림
• 입출력이 완료되어 완료 인터럽트가 발생하면 운영체제는 대기 큐에서 작업이 완료된 PCB를 찾아 준비 상태로 변경한 뒤 waiting queue에서 제거하고 ready queue로 이동

선점형과 비선점형 스케쥴링

• 선점: ‘남보다 앞서서 차지함’을 의미

선점형 스케쥴링(preemptive scheduling)

• 프로세스가 CPU를 비롯한 자원을 사용하고 있더라도 운영체제가 프로세스로부터 자원을 강제로 빼앗아 다른 프로세스에 할당할 수 있는 스케쥴링 방식
• 프로세스마다 정해진 시간만큼 CPU를 사용하고 정해진 시간을 모두 소비하여 타이머 인터럽트가 발생하면 운영체제가 해당 프로세스로부터 CPU자원을 뺏은 후 다음 프로세스에 할당하는 방식

장점 & 단점

• 장점: 더 급한 프로세스가 언제든 끼어들어 사용할 수 있고 자원을 골고루 배분할 수 있음
• 단점: context switch 과정에서 오버헤드 발생

비선점형 스케쥴링(Non-preemptive scheduling)

• 하나의 프로세스가 자원을 사용하고 있으면 그 프로세스가 종료되거나 스스로 대기 상태에 접어들기 전까지 다른 프로세스가 끼어들 수 없는 스케쥴링 방식을 의미 → 하나의 프로세스가 자원 사용을 독점

대부분의 운영체제는 선점형 스케쥴링 방식을 사용

CPU 스케쥴링 알고리즘

스케쥴링 알고리즘의 종류

선입 선처리 스케쥴링 (FCFS 스케쥴링)

• First Come First Served Scheduling 으로 단순히 준비 큐에 삽입된 순서대로 프로세스들을 처리하는 비선점형 스케쥴링 방식
• 공정해 보이지만 때때로 프로세스들이 기다리는 시간이 매우 길어질 수 있음

프로세스 A, B, C가 순서대로 준비 큐에 삽입된 상태

• 프로세스 C는 2ms동안 CPU에서 실행되기 위해 22ms라는 긴 시간을 기다려야 함 ⇒ convoy effect (호위효과)

convoy effect를 막기 위해서는 단순히 실행시간이 짧은 프로세스를 먼저 실행하면 됨 ⇒ 최단 작업 우선 스케쥴링

최단 작업 우선 스케쥴링 (Shortest Job First Scheduling)

• 기본적으로 비선점형 스케쥴링 알고리즘으로 분류되지만, 선점형으로 구현될 수도 있음

라운드 로빈 스케쥴링(Round robin scheduling)

• 선입 선처리 스케쥴링에 타임 슬라이스라는 개념이 더해진 스케쥴링 방식

* 타임 슬라이스: 각 프로세스가 CPU를 사용할 수 있는 정해진 시간을 의미

• 큐에 삽입된 순서대로 프로세스들을 실행하되 정해진 시간만큼 사용
• 정해진 시간 내에 프로세스가 완료되지 못하면 다시 큐의 맨 뒤로 삽입됨

예시

• ready queue에 process A, B, C 순서로 삽입되어 있는 경우
• 타임슬라이스: 4ms
  
  

• 타임 슬라이스의 크기가 중요
  • 크면 들어온 순서대로 process를 처리하기 때문에 선입 선처리 스케쥴링과 차이가 없음
  • 작으면 context switch가 자주 발생해 CPU에 부담

최소 잔여 시간 우선 스케쥴링 (Shortest Remaining Time)

• 최단 작업 우선 스케쥴링 + 라운드 로빈 스케쥴링
• 정해진 시간만큼 CPU를 이용하되, 다음으로 CPU를 사용할 프로세스는 남은 작업 시간이 가장 적은 프로세스를 선택

우선순위 스케쥴링(Priority scheduling)

• 프로세스들에 우선순위를 부여하고 높은 우선순위를 가진 프로세스부터 실행하는 스케쥴링 알고리즘
  • 우선순위가 같은 프로세스들은 선입 선처리로 스케쥴링

발생할 수 있는 문제

Starvation 현상: 우선순위가 높은 프로세스를 우선하여 처리하는 방식이기에 우선순위가 낮은 프로세스는 ready queue에 먼저 삽입되었음에도 불구하고 계속해서 실행이 연기될 수 있음

⇒ 방지하기 위한 대표적인 기법으로 에이징(aging)이 있음

• 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식

다단계 큐 스케쥴링 (multilevel queue scheduling)

• 우선순위 스케쥴링의 발전된 형태로 우선순위별로 준비 큐를 여러 개 사용하는 스케쥴링 방식
• 우선순위가 가장 높은 큐에 있는 프로세스들을 먼저 처리하고, 우선순위가 가장 높은 큐가 비어있으면 그 다음 우선순위 큐에 있는 프로세스들을 처리

• 큐별로 다양한 스케쥴링을 적용해서 효율적으로 처리 가능
• 단점은 기본적으로 프로세스가 큐 간의 이동이 안되서 우선순위가 낮은 큐에 있는 프로세스는 실행되지 않는 starvation 현상이 발생할 수 있음

다단계 피드백 큐 스케쥴링 (multilevel feedback queue scheduling)

• 큐 간의 이동이 가능한 다단계 큐 스케쥴링
• 우선순위가 가장 높은 큐에 삽입되어 프로세스가 실행되다가 타임 슬라이스 동안 실행을 다 못 끝내면

• 다음 우선순위 큐에 삽입되고, 결국 CPU를 오래 사용해야 하는 프로세스는 점차 우선순위가 낮아짐

• 즉 CPU-bound process는 자연스레 우선순위가 낮아지고, I/O Bound process는 자연스레 우선순위가 높은 큐에서 실행이 끝남
• 낮은 우선순위 큐에서 너무 오래 기다리는 프로세스는 에이징 기법을 적용해 starvation 현상을 예방할 수 있음
• 구현이 복잡하지만 CPU 스케쥴링의 가장 일반적인 알고리즘 형태로 알려짐

참고

1. 책 "혼자 공부하는 컴퓨터 구조+운영체제"
2. 유튜브 "혼자 공부하는 컴퓨터 구조 + 운영체제"

본 글은 책 "혼자 공부하는 컴퓨터 구조+운영체제" 의 "Chapter 9. 운영체제 시작하기"을 읽고 정리한 내용입니다.

09-1 운영체제를 알아야 하는 이유

운영체제란

• 모든 프로그램은 하드웨어가 필요
  • 1+2 계산하는 프로그램은 CPU필요
  • 이미지를 하드 디스크에 저장하는 프로그램은 하드 디스크 필요
• (시스템) 자원: 프로그램 실행에 마땅히 필요한 요소들로 CPU, 메모리, 보조기억 장치 등이 있음
• 운영체제(Operating System): 실행할 프로그램에 필요한 자원을 할당하고 프로그램이 올바르게 실행되도록 돕는 특별한 프로그램
• 운영체제는 매우 특별한 프로그램이기 때문에 항상 컴퓨터가 부팅될 때 메모리 내 커널 영역(kernel space)이라는 공간에 따로 적재되어 실행됨
• 사용자 영역 (user space): 사용자가 이용하는 응용 프로그램이 적재되는 영역

위의 프로그램들은 누가 메모리에 적재했을까? → 운영체제!

응용 프로그램이 실행되려면 CPU가 필요한데 운영체제가 관리함

• 최대한 공정하게 여러 프로그램에 CPU 자원을 할당

⇒ 운영체제는 응용 프로그램과 하드웨어 사이에서 응용 프로그램에 필요한 자원을 할당하고, 응용 프로그램이 올바르게 실행되도록 관리하는 역할

결론적으로 운영체제를 알면 운영체제를 통해 하드웨어의 상태나 코드의 실행 방식을 알 수 있고 결과적으로 하드웨어와 프로그램을 더 깊이 이해할 수 있음

09-2. 운영체제의 큰 그림

운영체제의 심장, 커널

• 운영체제의 핵심 서비스를 담당하는 부분

운영체제에는 속하는데 커널에는 속하지 않는 기능은 User Interface

• GUI
• CLI

이중모드와 시스템 호출

• 사용자가 실행하는 프로그램은 자원에 직접 접근할 수 있을까? NO! 자원에 직접 접근은 위험

• 자원이 무질서하게 관리되고, 응용 프로그램이 조금만 실수해도 컴퓨터 전체에 큰 악영향을 끼칠 수 있음

• 운영체제는 응용 프로그램들이 자원에 접근하려고 할 때 오직 운영체제 자신을 통해서만 접근하도록 하여 자원을 보호

• 응용 프로그램이 자원에 접근하기 위해서 운영체제에 도움을 요청해야 함
  • 도움을 요청한다 → 운영체제 코드를 실행하려고 한다

예를 들어 응용 프로그램이 실행 과정에서 하드 디스크에 접근하여 데이터를 저장하려고 함

• 응용 프로그램이 운영체제에 도움 요청
• 운영체제는 커널 영역 내의 하드 디스크에 데이터를 저장하는 코드를 실행하여 응용 프로그램 대신 작업을 수행

• 이중 모드(Dual model) : CPU가 명령어를 실행하는 모드를 크게 사용자 모드와 커널 모드로 구분하는 방식
  • 사용자모드 : 운영체제 서비스를 제공받을 수 없는 실행 모드 (자원 접근 불가)
  • 커널 모드 : 운영 체제 서비스를 제공받을 수 있는 실행 모드

이중 모드는 플래그 레지스터 내의 슈퍼바이저 플래그에 의해 결정됨

• 응용 프로그램이 운영체제에게 시스템 호출(System call)을 통해 사용자 모드 → 커널 모드로 전환됨
• 일종의 소프트웨어 인터럽트

하드웨어 인터럽트 처리 방식과 유사

1. 시스템 호출을 발생시키는 명령어가 실행되면 CPU는 지금까지의 작업을 백업
2. 커널 영역 내에 시스템 호출을 수행하는 코드(인터럽트 서비스 루틴)을 실행
3. 다시 기존에 실행하던 응용 프로그램으로 복귀하여 실행

일반적으로 응용 프로그램은 실행 과정에서 운영체제 서비스들을 매우 빈번하게 사용

운영체제의 핵심 서비스

크게 3가지

• 프로세스 관리, 자원 접근 및 할당, 파일 시스템 관리

프로세스 관리

• 프로세스 : 실행중인 프로그램
• 일반적으로 하나의 CPU는 한번에 하나의 프로세스만 실행할 수 있기에 CPU는 이 프로세스들을 조금씩 시간을 나눠 번갈아 가며 실행

• 각 프로세스의 상태와 사용하고자 하는 자원도 다양 → 운영체제는 다양한 프로세스를 일목요연하게 관리하고 실행할 수 있어야 함

자원 접근 및 할당

CPU

• 메모리에 여러 프로세스가 적재되고, 하나의 CPU는 한 번에 하나의 프로세스만 실행
• 어떤 프로세스부터 CPU를 이용하게 할지, 얼마나 오래 사용할지 결정해야 함 ⇒ CPU 스케쥴링 (11장)

메모리

• 메모리에 적재된 프로세스들의 크기와 주소도 가지각색이라 운영체제가 어떻게 메모리를 할당하지, 메모리가 부족한 경우에는 어떻게 극복하는지 운영체제가 판단

입출력장치

• 인터럽트 서비스 루틴은 운영체제가 제공하는 기능으로 커널 영역에 있고 하드웨어 인터럽트도 마찬가지
• 입출력장치가 cpu에 하드웨어 인터럽트 요청 신호를 보내면 CPU는 하던 일을 잠시 백업한 뒤 커널 영역에 있는 인터럽트 서비스 루틴을 실행

파일 시스템 관리

• 파일 시스템도 운영체제가 지원하는 핵심 서비스 (15장)

참고

• system call 확인하기위해 linux에서는 strace 명령어 사용

$ strace /bin/ls                                                                                                                                                                                          ok | wschoi@superb-tony | 03:58:16 PM
execve("/bin/ls", ["/bin/ls"], 0x7ffd7c910c40 /* 40 vars */) = 0
brk(NULL)                               = 0x559534620000
arch_prctl(0x3001 /* ARCH_??? */, 0x7ffe470196c0) = -1 EINVAL (Invalid argument)
access("/etc/ld.so.preload", R_OK)      = -1 ENOENT (No such file or directory)
openat(AT_FDCWD, "/etc/ld.so.cache", O_RDONLY|O_CLOEXEC) = 3
fstat(3, {st_mode=S_IFREG|0644, st_size=101547, ...}) = 0
mmap(NULL, 101547, PROT_READ, MAP_PRIVATE, 3, 0) = 0x7f8e83bfb000
close(3)                                = 0
openat(AT_FDCWD, "/lib/x86_64-linux-gnu/libselinux.so.1", O_RDONLY|O_CLOEXEC) = 3
read(3, "\\177ELF\\2\\1\\1\\0\\0\\0\\0\\0\\0\\0\\0\\0\\3\\0>\\0\\1\\0\\0\\0@p\\0\\0\\0\\0\\0\\0"..., 832) = 832
fstat(3, {st_mode=S_IFREG|0644, st_size=163200, ...}) = 0
mmap(NULL, 8192, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f8e83bf9000
mmap(NULL, 174600, PROT_READ, MAP_PRIVATE|MAP_DENYWRITE, 3, 0) = 0x7f8e83bce000
mprotect(0x7f8e83bd4000, 135168, PROT_NONE) = 0
mmap(0x7f8e83bd4000, 102400, PROT_READ|PROT_EXEC, MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE, 3, 0x6000) = 0x7f8e83bd4000
mmap(0x7f8e83bed000, 28672, PROT_READ, MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE, 3, 0x1f000) = 0x7f8e83bed000
mmap(0x7f8e83bf5000, 8192, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE, 3, 0x26000) = 0x7f8e83bf5000
mmap(0x7f8e83bf7000, 6664, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_ANONYMOUS, -1, 0) = 0x7f8e83bf7000
close(3)                                = 0

참고

1. 책 "혼자 공부하는 컴퓨터 구조+운영체제"
2. 유튜브 "혼자 공부하는 컴퓨터 구조 + 운영체제"
 

본 글은 책 "혼자 공부하는 컴퓨터 구조+운영체제" 의 Chapter 5를 읽고 정리한 내용입니다.

05-1 빠른 CPU를 위한 설계 기법

클럭(Clock)

• 컴퓨터 부품들은 ‘클럭 신호’에 맞춰 움직이는데 실제로 클럭 속도가 높은 CPU는 일반적으로 성능이 좋음
• 단위: Hz 로 초당 반복되는 클럭 수
  • 실제 CPU 클럭 속도 표현 예시: Base 2.5GHz, Max 4.9GHz 등으로 표시되어있음
  • 의미: 초당 25억번, 순간적으로 최대 49억번 반복된다는 의미

오버클럭킹(Overclocking) : 최대 클럭 속도를 강제로 끌어올리는 기법

Q. 클럭 속도를 무지막지하게 높이면 무조건 CPU가 빨라질까?
A. 발열 문제가 심해지고,클럭 속도만으로 cpu의 성능을 올리는 것에는 한계가 있음

코어와 멀티코어

코어란?

• 명령어를 실행하는 부품으로, CPU가 기술적으로 많은 발전을 거듭하면서 단순히 “명령어를 실행하는 부품” → “명령어를 실행하는 부품을 여러 개 포함하는 부품”으로 확장됨

• 코어를 여러개 포함하고 있는 CPU를 멀티코어 CPU 또는 멀티코어 프로세서라고 부름
• 코어의 개수가 연산 처리 속도와 연관이 있지만 코어마다 처리할 명령어들을 얼마나 적절하게 분배하느냐에 따라 연산 속도가 크게 달라짐

스레드와 멀티스레드

• 스레드: “실행 흐름의 단위”라는 사전적 의미를 가지고 2가지로 나뉨
  • 하드웨어적 스레드
  • 소프트웨어적 스레드

하드웨어적 스레드

• 하나의 코어가 동시에 처리하는 명령어 단위
• 여러 스레드를 지원하는 CPU는 하나의 코어로도 여러 개의 명령어를 동시에 실행할 수 있음
  • 2코어 4스레드 CPU: 아래 그림처럼 명령어를 실행하는 부품 2개, 한번에 4개의 명령어를 처리할 수 있는 CPU를 의미 (멀티스레드 프로세서, 멀티스레드 CPU)

*하이퍼스레딩: 인텔의 멀티스레드 기술을 의미

소프트웨어적 스레드

• 하나의 프로그램에서 독립적으로 실행하는 단위
• 아래의 기능들을 동시에 수행되길 원할 때 각각의 스레드로 만들어 동시 실행할 수 있음

멀티스레드 프로세서

• 하나의 코어로 여러 명령어를 동시에 처리하도록 만들려면 프로그램 카운터, 스택 포인터, 메모리 버퍼 레지스터, 메모리 주소 레지스터와 같이 하나의 명령어를 처리하기 위해 꼭 필요한 레지스터를 여러개 가지고 있으면 됨

• 레지스터세트: 하나의 명령어를 실행하기 위해 꼭 필요한 레지스터들을 편의상 부르기 위한 세트
• 레지스터 세트가 2개인 CPU는 두 개의 명령어를 처리하기 위한 정보들을 기억할 수 있음

• 하드웨어 스레드를 이용해 하나의 코어로도 여러 명령어를 동시에 처리할 수 있다고 했음
• 그러나 메모리 속 프로그램 입장에서는 하드웨어 스레드는 마치 ‘한번에 하나의 명령어를 처리하는 CPU’나 다름 없음 ⇒ 하드웨어 스레드를 논리 프로세서(logical processor)라고 부르기도 함

05-2 명령어 병렬처리 기법

• 빠른 CPU를 만들려면 높은 클럭 속도, 멀티코어, 멀티 쓰레드를 지원하는 CPU를 만드는 것도 중요하지만 CPU가 놀지 않고 시간을 알뜰하게 쓰며 작동하게 만드는 것도 중요

명령어 병렬 처리 기법(ILP: Instruction-Level Parallelism)

• 명령어를 동시에 처리하여 CPU를 한시도 쉬지 않고 작동시키는 기법
  • 명령어 파이프 라이닝
  • 슈퍼스칼라
  • 비순차적 명령어 처리

명령어 파이프라인

하나의 명령어가 처리되는 전체 과정을 클럭 단위로 나누면

1. 명령어 인출 (Instruction Fetch)
2. 명령어 해석 (Instruction Decode)
3. 명령어 실행 (Execute Instruction)
4. 결과 저장 (Write Back)

같은 단계가 겹치지만 않는다면 CPU는 ‘각 단계를 동시에 실행할 수 있다’
⇒ 명령어 파이프라인에 넣고 동시에 처리하는 기법을 명령어 파이프라이닝이라고 함

명령어 파이프라인을 사용하지 않고 모든 명령어를 순차적으로만 처리하면 아래와 같이 비효율적으로 처리됨

파이프라이닝이 높은 성능을 가져오기는 하지만, 성능 향상에 실패하는 경우도 있음 → 파이프라인 위험

파이프라인 위험 3가지 종류

• 데이터 위험 (Data hazard)
• 제어 위험 (Control hazard)
• 구조적 위험

데이터 위험

• 명령어 간의 의존성때문에 발생하는 위험
• 모든 명령어를 동시에 처리할 수 없는 경우도 있기 때문

명령어 1: R1 <- R2 + R3
명령어 2: R4 <- R1 + R5 

명령어 1을 실행 후에 명령어 2에서 명령어 1의 결과를 인출해야 하기때문에 병렬적으로 처리할 수 없음

제어 위험

• 기본적으로 프로그램 카운터는 ‘현재 실행 중인 명령어의 다음 주소’로 갱신됨
• 분기 등으로 인한 프로그램 카운터의 갑작스러운 변화가 생기면 명령어 파이프라인에 가지고 와서 처리 중(ex) 인출, 해석)이던 명령어들이 쓸모 없어짐

⇒ 분기 예측을 통해 프로그램이 어디로 분기할지 미리 예측한 후 그 주소를 인출하는 기술을 사용

구조적 위험

• 명령어들을 겹쳐 실행하는 과정에서 서로 다른 명령어가 동시에 ALU, 레지스터 등과 같은 CPU 부품을 사용하려고 할 때 발생 ⇒ 자원 위험이라고도 부름

슈퍼스칼라

• 여러개의 파이프라인을 이용해서 한번에 두가지의 명령어를 인출/해석/실행/저장

• 이론적으로는 파이프라인 개수에 비례하여 처리속도 증가, but 파이프라인 위험도 증가하기 때문에 고도로 설계 되어야 함

비순차적 명령어 처리

• OoOE: Out-of-order execution

• M(N): N 번지의 메모리
• M(N) ← 100: N 번지에 100을 저장

3번째 명령어 (M(102) <- M(100) + M(101)) 에서 1, 2번째 명령어의 결과가 필요하기 때문에 이상적인 성능 향상을 이끌 수 없음

여기서 의존성이 없는 명령어의 순서를 바꿔본다면?

• 순차적으로 명령어를 처리할 때 보다 더 효율적으로 처리될 수 있고 이렇게 명령어 파이프라인을 멈추는 것을 방지하는 기법을 비순차적 명령어 처리 기법이라고 함

* 물론 아무 명령어나 순서를 바꿔서 수행할 수는 없고 최적화 필요

05-3 CISC 와 RISC

• CPU 성능을 향상시키기 위해서 명령어 파이프라이닝, 슈퍼 스칼라 기법등을 적용하기 위해서는 명령어가 파이프라이닝 하기 쉽게 생겨야 함

CPU는 명령어를 실행한다 ⇒ 모든 CPU가 똑같이 생긴 명령어를 실행할까? NO!

명령어의 세세한 생김새, 연산, 주소 지정 방식은 CPU마다 다름

명령어 집합 (Instruction set, Instruction set architecture, ISA)

• CPU가 이해할 수 있는 명령어들의 모음
• 인텔의 CPU가 이해할 수 있는 명령어 집합과 아이폰의 CPU가 이해할 수 있는 명령어 집합은 다름

명령어 병렬 처리 기법들을 도입하기 유리한 ISA는 크게 2가지가 있음

• CISC
• RISC

CISC

• Complex Instruction Set Computer
• 복잡한 명령어 집합을 활용하는 컴퓨터(CPU)
• Intel, AMD 기반 cpu (x64, x86-64)

• 복잡하고 다양한 명령어 활용
• 명령어의 형태와 크기가 다양한 가변 길이 명령어 활용

• 상대적으로 적은 수의 명령어로도 프로그램을 실행할 수 있음 ⇒메모리를 최대한 아끼며 개발해야했던 시절에 인기가 높았음
• 명령어 파이프라이닝이 불리하다는 치명적인 단점이 있음
  • 명령어가 워낙 복잡하고 다양한 기능을 제공해 명령어의 크기와 실행되기까지의 시간이 일정하지 않음
  • 명령어 실행하는데 여러 클럭 주기 필요

⇒ CISC 명령어 집합은 복잡하고 다양한 기능을 제공하기에 적은 수의 명령어로 프로그램을 동작시키고 메모리를 절약할 수 있지만, 명령어의 규격화가 어려워 파이프라이닝이 어려움

RISC

• Reduced Instruction Set Computer
• 명령어의 종류가 적고, 짧고 규격화된 명령어 사용 (되도록 1클럭 내외로 실행되는 명령어를 지향) ⇒ 고정 길이 명령어 사용
• 메모리에 직접 접근 명령어를 load, store 두개로 제한할 만큼 메모리 접근을 단순화 및 최소화
  • 레지스터를 십분 활용 → 범용 레지스터 수가 더 많음
• 다만 명령어 종류가 CISC 보다 적기에 더 많은 명령어로 프로그램을 동작시킴

참고

1. 책 "혼자 공부하는 컴퓨터 구조+운영체제"
2. 유튜브 "혼자 공부하는 컴퓨터 구조 + 운영체제"

본 글은 책 "혼자 공부하는 컴퓨터 구조+운영체제" 의 Chapter 3를 읽고 정리한 내용입니다.

컴파일 언어

컴파일러에 의해 소스 코드 전체가 저급 언어로 변환되어 실행되는 고급 언어 (C언어)

소스 코드를 처음부터 끝까지 저급 언어로 컴파일하고 이 과정에서 오류를 하나라도 발견하면 해당 소스 코드는 컴파일에 실패

03-2 명령어의 구조

연산 코드와 오퍼랜드

명령어는 연산 코드와 오퍼랜드(operand)로 구성되어 있음

• 연산 코드 : 명령어가 수행할 연산 (연산자)
• 오퍼랜드 : 연산에 사용할 데이터가 저장된 위치 (피연산자)

명령어 예시

연산코드 오퍼랜드
push rbp
mov rbp, rsp
mov DWORD PTR [rbp-4], 1

오퍼랜드(주소 필드)

연산에 사용할 데이터 또는 데이터가 저장된 위치

주로 메모리 주소나 레지스터 이름이 담김

mov eax, 0 ---> 오퍼랜드가 두 개인 경우
pop rbp    ---> 오퍼랜드가 한 개인 경우
ret        ---> 오퍼랜드가 없는 경우

• 2-주소 명령어: 오퍼랜드가 두 개인 명령어
• 1-주소 명령어: 오퍼랜드가 한 개인 명령어
• 0-주소 명령어: 오퍼랜드가 하나도 없는 경우

연산 코드

명령어가 수행할 연산을 의미하고 크게 4가지 유형이 있음

1. 데이터 전송: MOVE, STORE, LOAD(FETCH), PUSH, POP
2. 산술/논리 연산: ADD/SUBTRACT, INCREMENT, AND, COMPARE
3. 제어 흐름 변경: JUMP, HALT, CALL
4. 입출력 제어: READ, WRITE, START IO, TETS IO

주소 지정 방식

오퍼랜드 필드에 데이터를 담게 되면 오퍼랜드 필드로 표현할 수 있는 정보의 크기가 제한되기 때문에 메모리 주소를 주로 사용

EX) 명령어(연산코드+오퍼랜드)의 크기가 16비트일 때, 연산 코드 필드가 4비트인 2-주소 명령어

• 연산코드 4비트
• 오퍼랜드는 필드당 (16-4)/2 = 6비트, 표현할 수 있는 정보의 가짓수가 $2^6$=64밖에 되지 않음

오퍼랜드 필드 안에 메모리 주소가 담긴다면, (예를 들어 한 주소에 16비트를 저장) 표현할 수 있는 정보는 $2^{16}$으로 확 커짐

• 유효주소 : 연산 코드에 사용할 데이터가 저장된 위치
• 주소 지정 방식: 오퍼랜드 필드에 데이터가 저장된 위치를 명시할 때 연산에 사용할 데이터 위치를 찾는 방법으로 5가지 방법 소개

즉시 주소 지정 방식

연산에 사용할 데이터를 오퍼랜드 필드에 직접 명시하는 방식

표현할 수 있는 데이터의 크기는 작아지지만 데이터를 메모리나 레지스터에서 찾는 과정이 없기때문에 빠름

직접 주소 지정 방식

오퍼랜드 필드에 유효 주소를 직접적으로 명시하는 방식

유효 주소를 표현할 수 있는 범위가 연산 코드의 비트 수 만큼 줄어듦

간접 주소 지정 방식

유효 주소의 주소를 필드에 명시

직접 주소 지정 방식보다 표현할 수 있는 유효 주소의 범위가 넓어짐

다만 두 번의 메모리 접근이 필요하기 때문에 좀 더 느림

레지스터 주소 지정 방식

연산에 사용할 데이터를 저장한 레지스터를 오퍼랜드 필드에 직접 명시 (직접 주소 지정 방식과 비슷)

CPU 내부에 있는 레지스터에 접근하므로 직접 주소 지정 방식보다 빠름

레지스터 간접 주소 지정 방식

연산에 사용할 데이터를 메모리에 저장하고 그 주소를 저장한 레지스터를 오퍼랜드 필드에 명시

메모리 접근하는 횟수가 한번으로 줄어듬

참고

1. 책 "혼자 공부하는 컴퓨터 구조+운영체제"
2. 유튜브 "혼자 공부하는 컴퓨터 구조 + 운영체제"

본 글은 책 "혼자 공부하는 컴퓨터 구조+운영체제" 의 Chapter 2를 읽고 정리한 내용입니다.

02-1 0과 1로 숫자를 표현하는 방법

정보 단위

• bit: 0과 1을 나타내는 가장 작은 정보 단위
• byte: 8개의 bit를 묶은 단위 ($2^8=256$ 개의 정보를 표현)
• 1 kilobyte: 1000bytes
• 1 gigabyte: 1000 kilobytes

1kB는 1024byte라고 표현하는 것은 잘못된 관습. 1024개를 묶어 표현한 단위는 KiB(키비), MiB, GiB

워드(word) : CPU가 한번에 처리할 수 있는 데이터 크기

• CPU마다 다르지만 워드 크기는 대부분 32비트 아니면 64비트
• 인텔이 x86 CPU는 32비트 워드 CPU, x64 CPU는 64비트 워드 CPU

이진법

수학에서 0과 1만으로 모든 숫자를 표현하는 방법

일상에서 우리는 십진수를 사용하지만 컴퓨터는 2진수를 이해할 수 있기 때문에 변환해서 알려줘야 함

2진수 표기법

ex) 10진수에서 8을 2진수로 표기

• ${1000}_{(2)}$
• 0b1000

이진수의 음수 표현

컴퓨터는 0과 1만 이해할 수 있기 때문에 마이너스 부호를 사용하지 않고 0과 1만으로 음수를 표현해야 함

⇒ 2의 보수를 구해 이 값을 음수로 간주하는 방법 사용

2의 보수 구하는 방법

• 모든 0과 1을 뒤집고 거기에 1을 더한 값
• 예)
  • $11_{(2)}$의 보수는 $01_{(2)}$
  • $11_{(2)}$ → $00_{(2)}$ → $01_{(2)}$

실제로 2진수 자체만 봐서는 음수인지 양수인지 구별하기 어려워서 컴퓨터 내부에서는 플래그(Flag)라는 부가정보를 사용

16진법

2진수만으로 숫자를 표현하기에 숫자의 길이가 너무 길어진다는 단점이 있음.

⇒ 16진법 사용

표기법 (10진수 15을 16진수로 표기)

• ${15}_{(16)}$
• 0x15

굳이 16진수를 사용하는 이유는 2진수와 16진수 간의 변환이 쉽기 때문

16진수 → 2진수

$1A2B_{(16)}$

⇒ 0001 1010 0010 1011

2진수 → 16진수

$11010101_{(2)}$

⇒ $D5_{(16)}$

02-2. 0과 1로 문자를 표현하는 방법

문자 집합과 인코딩

문자집합 : 컴퓨터가 인식하고 표현할 수 있는 문자의 모음

문자 인코딩 : 문자 집합에 속한 문자를 0과 1로 변환하는 과정

문자 디코딩 : 0과 1로 이루어진 문자 코드를 사람이 이해할 수 있는 문자로 변환하는 과정

아스키코드

• ASCII: American Standard Code for Information Interchange
• 문자집합 중 하나로 영어 알파벳과 아라비아 숫자, 일부 특수 문자를 포함
• 문자들은 각각 7비트로 표현되는데 $2^7=128$ 개의 문자 표현 가능
  • 실제로는 8비트로 표현되지만 1비트는 parity bit 라고 불리는 오류 검출을 위해 사용됨

아스키 코드 표

더보기

 

아스키 코드표를 이용해 표현하고자 하는 문자를 0과 1로 표현할 수 있음

하지만 128개의 문자밖에 표현하지 못하고 특히 한글을 포함한 영어권 외의 나라들은 자신들의 언어를 0과 1로 표현할 수 없음

⇒ EUC-KR 인코딩 등장

EUC-KR

한글은 초성, 중성, 종성의 조합으로 이루어져 있어 2가지 인코딩 방식 존재

1. 한글 완성형 인코딩: 초성, 중성, 종성의 조합으로 이루어진 완성된 하나의 글자에 고유한 코드를 부여하는 인코딩 방식
2. 한글 조합형 인코딩: 초성, 중성, 종성 각각을 위한 비트열을 할당하여 조합으로 하나의 글자 코드를 완성하는 인코딩 방식

EUC-KR은 완성형 인코딩 방식으로 2바이트 크기의 코드를 부여
EX) ‘가’ 는 b0a0으로 표현되는데 2진수로 변환해보면 1011 0000 1010 0000 으로 16bits → 2바이트

더보기

EUC-KR 코드표 (일부)

총 2350개 정도의 한글 단어를 표현할 수 있음

• 아스키 코드보다 표현할 수 있는 문자가 많아졌지만 모든 한글 조합을 표현할 수 있을 정도로 많은 양은 아님
• 쀍, 쀓 믜 같은 글자는 EUC-KR로 표현할 수 없음

⇒ EUC-KR의 확장된 버전으로 CP949 가 등장했고 8822자가 추가됨

유니코드와 UTF-8

유니코드 : EUC-KR보다 훨씬 다양한 한글을 포함하며 대부분 나라의 문자, 특수 문자, 이모티콘까지도 코드로 표현할 수 있는 통일된 문자집합

유니코드 문자집합

https://www.unicode.org/charts/PDF/UAC00.pdf

“한”과 “글”이라는 단어를 찾아보면,

• 한: $D55C_{(16)}$
• 글: $AE00_{(16)}$

아스키코드나 EUC-KR과 다르게 문자집합에서 찾은 고유한 값을 다시 인코딩

• UTF-8, UTF-16, UTF-32등이 있음 (Unicode Transformation Format)
• UTF-8 이 가장 대중적

UTF-8

• 통상 1바이트에서 4바이트까지의 인코딩 결과를 만들어냄

• 첫 코드 포인트와 마지막 코드 포인트 값의 범위를 통해 인코딩된 글자가 몇바이트로 구성되는지 알 수 있음
• “한”과 “글”의 유니코드 값은 각각 D55C, AE00으로 0800~FFFF 사이에 속한다. 그러므로 각각 3바이트로 표현될 수 있음

• D55C는 1101 0101 0101 1100 으로 이를 위에 X로 표시된 자리수에 순차적으로 넣어주면 된다
• 한: 11101101 10010101 10011100

본 글은 책 "혼자 공부하는 컴퓨터 구조+운영체제" 을 읽고 정리한 내용입니다.

컴퓨터 구조를 공부해야 하는 이유가 뭘까?

• 컴퓨터 구조를 이해하면 문제 해결 능력이 향상됨
• 프로그래밍 언어 문법만으로 알기 어려운 성능/용량/비용을 고려하며 개발할 수 있음

컴퓨터 구조의 큰 그림

컴퓨터 구조 지식은 크게 2가지

• 컴퓨터가 이해하는 정보
• 컴퓨터의 4가지 핵심 부품

컴퓨터가 이해하는 정보

• 0과 1로 표현된 정보만을 이해하는데 크게 2가지 종류
  • 데이터
  • 명령어

컴퓨터의 4가지 핵심 부품

• 중앙처리장치 (CPU: Central Processing Unit)
• 주기억장치 (Main memory, RAM)
• 보조기억장치 (Secondary storage)
• 입출력장치(input/output(I/O) device)

1. 가장 큰 사각형이 메인보드
2. 메인 보드 안에 시스템 버스(양방항 수직 화살표)가 있음
3. CPU 내부에는 산술논리연산 장치(ALU), 제어장치 와 여러 레지스터가 있음
   • CPU는 메인보드 내 시스템 버스와 연결되어 있음
4. 메모리는 메인보드 내 시스템 버스와 연결되어 있음
5. 보조기억장치는 메인 보드 내 시스템 버스와 연결되어 있음
6. 모니터, 키보드, 마우스 등은 메인보드 내 시스템 버스와 연결되어있고 이들을 입출력장치라고 부름

⇒ 컴퓨터의 4가지 핵심 부품은 메인보드 내의 시스템 버스를 통해 모두 연결되어 있음

메모리

• 현재 실행되는 명령어와 데이터를 저장하는 부품
  • 프로그램이 실행되려면 반드시 메모리에 저장되어 있어야 함
• 컴퓨터가 빠르게 작동하기 위해서는 메모리 속 명령어와 데이터가 중구난방으로 저장되어 있으면 안되고 정돈되어있어야 함

→ 주소라는 개념이 사용됨

• 1/2번지에 명령어
• 3/4번지에 데이터
• 5/6번지에 아무것도 저장되어 있지 않음

CPU

• 메모리에 저장된 명령어를 읽어 들이고, 해석하고 실행
• 내부 구성요소는 크게 3가지
  • 산술논리연산장치(ALU, Arithmetic Logic Unit) : 쉽게 말해 계산기
  • 레지스터 (Register): 내부의 작은 임시 저장 장치
  • 제어장치 (CU, Control Unit)
    • Control signal이라는 전기 신호를 내보고 명령어를 해석하는 장치
    ex) CPU가 메모리에 저장된 값을 읽고 싶을 때 메모리를 향해 메모리 읽기라는 제어 신호를 보냄
    ex) CPU가 메모리에 어떤 값을 저장하고 싶을 땐 메모리를 향해 메모리 쓰기라는 제어 신호를 보냄

예시를 통한 CPU를 구성하는 세가지 부품의 역할

1. 제어장치는 1번지에 저장된 명령어를 읽어 들이기 위해 메모리에 “메모리 읽기” 제어 신호 전송

2. 메모리는 1번지에 저장된 명령어를 CPU에 건네주고 이 명령어는 레지스터에 저장됨.
제어 장치는 읽어 들인 명령어를 해석한 뒤 3번지와 4번지에 저장된 데이터가 필요하다고 판단.
제어장치는 3/4번지에 저장된 데이터를 읽어 들이기 위해 메모리에 “메모리 읽기” 제어 진호를 전송

3. 메모리는 3/4 번지에 저장된 데이터를 CPU에 건내주고 각각 다른 레지스터에 저장됨.
ALU는 읽어 들인 데이터로 연산을 수행. 계산의 결과값을 레지스터에 저장. 계산이 끝났다면 첫번째 명령어의 실행은 끝남

4. 제어장치는 2번지에 저장된 다음 명령어를 읽어 들이기 위해 메모리에 “메모리 읽기”제어 신호를 보냄

5. 메모리는 2번지에 저장된 명령어를 CPU에 건네주고, 이 명령어는 레지스터에 저장됨. 제어장치는 이 명령어를 해석한 뒤 메모리에 계산 결과를 저장해야 한다고 판단

6. 제어 장치는 계산 결과를 저장하기 위해 메모리에 “메모리 쓰기” 제어 신호와 함께 220을 보냄. 메모리가 계산 결과를 저장하면 두번째 명령어의 실행도 끝남.

정리

• CPU는 메모리에 저장된 값을 읽고/해석/실행하는 장치
• CPU 내부에는 ALU, 레지스터, Control Unit이 있음
  • ALU : 계산하는 장치
  • 레지스터 : 임시 저장 자잋
  • Control Unit: 제어 신호를 발생시키고 명령어를 해석하는 장치

보조기억장치

• 메모리는 프로그램의 명령어와 데이터를 저장하지만 2가지 치명적인 단점 존재
  • 가격이 비싸 저장 용량이 적음
  • 전원이 꺼지면 저장된 내용을 잃음

⇒ 보조기억장치의 필요. 보관할 프로그램을 저장

종류

• SSD, HDD, USB 메모리

입출력장치

• 마이크, 스피커, 프린터, 마우스, 키보드 처럼 컴퓨터 외부에 연결되어 내부와 정보를 교환

메인보드와 시스템 버스

메인보드

• 컴퓨터의 핵심 부품들은 모두 메인보드 판에 연결됨
• 여러 컴퓨터 부품을 부착할 수 있는 슬롯과 연결단자가 있음

시스템버스

• 메인보드에 연결된 부품들은 버스라는 통로를 통해 정보를 주고 받음
• 컴퓨터의 4가지 핵심 부품을 연결하는 가장 중요한 버스

시스템버스 구성

• 주소 버스: 주소를 주고 받는 통로
• 데이터 버스: 명령어와 데이터를 주고 받는 통로
• 제어 버스: 제어 신호를 주고 받는 통로
  • CPU 구성요소 중 제어 장치(Control Unit)는 제어 버스를 통해 제어 신호를 보냄

CPU 작동 예시를 통한 시스템 버스 이해

• CPU가 메모리 속 명령어를 읽어 들이기 위해 제어장치에서 “메모리 읽기”라는 신호를 보낼 때
  • 실제로는 제어버스로 “메모리 읽기” 제어 신호
  • 주소 버스로 읽고자 하는 주소를 보냄
  ⇒ 메모리는 데이터 버스로 CPU가 요청한 주소에 있는 내용을 보내줌

메모리에 어떤 값을 저장하는 경우

• CPU는 데이터 버스를 통해 메모리에 저장할 값
• 주소버스를 통해 저장할 주소
• 제어 버스를 통해 “메모리 쓰기” 제어 신호를 보냄

참고

1. 책 "혼자 공부하는 컴퓨터 구조+운영체제"
2. 유튜브 "혼자 공부하는 컴퓨터 구조 + 운영체제"