운영체제 5편 - CPU 스케줄링

이 글은 학부 운영체제 수업을 듣고 정리한 글입니다.
맥락없이 운영체제에 대한 내용들이 불쑥 등장하니 양해부탁드립니다.

이번 편은 CPU 스케줄링에 대한 내용입니다.

CPU Scheduling

CPU 스케줄링은 어떻게 프로세스들에게 CPU의 사용을 분배할 것인가에 대한 내용이다. 메모리 내에 ready queue에 있는 실행이 준비된 상태인 프로세스들 가운데 하나를 선택하여 CPU를 할당한다.
여기서 어떤 프로세스를 다음차례로 선택할 것인가에 대해 많은 알고리즘이 존재하는데 밑에서 살짝만 보고 넘어갈 것이다.
결국 CPU의 idel 시간을 최소로하고 CPU를 최대한 효율적으로 사용하기 위해서 CPU 스케줄링이 존재하는 것이다.

CPU 스케줄링의 결정은 다음 2가지 상태변화일때 일어난다.

• I/O로 인해 Process가 Running 상태에서 Waiting 상태로 가는경우
• Time quantum을 전부 소진하여 Process가 Running 상태에서 Ready 상태로 가는경우

스케줄링은 크게 비선점형 스케줄링(Non-preemptive scheduling)과 선점형 스케줄링(Preemptive scheduling)으로 나뉜다.

• 비선점형 스케줄링
  OS가 강제로 프로세스의 CPU사용을 중단시키지 않는다. 프로세스 스스로 CPU 사용을 중단하거나 I/O를 하는 상황에서만 스케줄링 된다.
• 선점형 스케줄링
  OS가 현재 수행중인 프로세스를 강제로 중단시킨다. 보통 프로세스의 Time quantum을 다 소진한 상황에서 스케줄링을 한다.

각 스케줄링들의 특성을 비교하기 위해서는 기준이 필요하다. 여기서의 기준을 몇가지 소개하겠다.

• CPU Utilization
  전체 CPU 사용중에서 user process들이 작업을 처리하는 시간을 CPU Utilization이라고 한다.
• Throughput
  단위시간동안 처리하는 프로세스 개수이다. 즉 얼마나 많은 양을 처리할 수 있는가이다.
• Response Time
  하나의 프로세스 관점에서 입출력을 시작해서 첫 결과가 나오기까지 나오는 시간이다.
• Waiting Time
  프로세스가 얼만큼 queue에서 대기를 하고있느냐이다.
• Turnaround Time
  프로세스가 시작해서 끝날때까지의 시간이다.

만약 Dos(Denial Of Service)공격을 받으면 패킷도착에 대한 interrupt가 미친듯이 발생한다. 그러면 대부분의 CPU 시간은 Kernel에서 ISR을 처리하는데 보내게 된다. 그러면 CPU utilization이 극도로 낮아지게 된다.
가장 이상적인 스케줄링은 CPU utilization이 높을수록 좋고, Throughput은 높을수록 좋고 Response Time은 낮을수록 좋다. 하지만 이런 이상적인 스케줄러를 설계하는 것은 현실상 불가능하다.
그래서 각 컴퓨터의 사용종류에 따라 특정 기준을 극대화하는 방식을 사용하는데 예를들어 슈퍼컴퓨터의 경우에는 CPU utilization을 극대화 한다. 그리고 우리가 보통 사용하는 서버를 포함한 일반 컴퓨터는 Response Time을 줄이는 것에 초점을 두게된다.

일반적인 프로세스는 CPU Burst(CPU로 연산하는 시간)과 I/O Burst(I/O 처리를 위해 기다리는 시간)을 번갈아 가며 수행한다.
이 두가지 특성에 따라 긴 CPU burst를 가진 프로세스를 CPU-bound 프로세스라고 하고 짧은 CPU burst를 가지고 I/O 시간이 많은 프로세스를 I/O-bound 프로세스라고 한다.
어떤 종류의 프로세스들이 많은지에 따라 CPU 스케줄링 기법의 효율성이 달라진다.

선점형(Preemptive) 스케줄링

선점형 스케줄링은 어떻게 구현할 수 있을까?
어떻게 preemption이 일어날 수 있을까? user program을 돌리고 있을때 kernel이 다시 제어권을 얻어야지만 현재 수행중인 프로세스를 멈추고 스케줄링을 할 수 있을 것이다. 현재 수행중인 프로세스를 멈추고 kernel이 제어권을 가지고 와야한다.
어떻게 하면 kernel이 제어권을 가져올 수 있을까? 두가지가 있다. 바로 interrupt와 시스템콜이다.
timer interrupt가 발생하면 그에맞는 ISR이 수행되면서 수행되고 있는 프로세스를 멈추고 다음 프로세스로 스케줄링을 해줄 수 있을 것이다.

다만 timer interrupt가 발생한다고 해서 그때마다 스케줄링을 하는 것은 아니다. 커널에서는 interrupt를 받지않도록 구간을 코드로 설정할 수가 있다. 예전의 커널에서 멀티스레드를 지원하지는 않았을때에는 현재 수행중인 프로세스가 시스템 콜을 통해 Kernel에 들어가게 되면 그때에는 아예 interrupt를 disable 시켰다. 그러므로 Kernel에서 나와 user mode로 나오는 순간 그때 모두 처리되었다.
지금은 이렇게 동작하지는 않고 preemption point라고 하여 나중에 동기화 쪽에서도 살펴보겠지만 kernel 에서는 많은 state를 관리하는데 동기화의 문제로 코드의 특정 구간에서는 scheduling이 되지 않도록 설정할 수 있다. 이 경우에도 interrupt 자체는 발생한다. 이것이 무슨말이냐면 해당 코드 구간에 들어갈때에는 preemptive disable flag를 ON 해놓고 들어가게되면, timer interrupt가 발생했을때 그에 맞는 ISR을 수행하게 되는데 이때 preemptive disable flag가 설정이 되어있다면 스케줄링 하지 않는다.

CPU Scheduling 알고리즘

여러가지 CPU Scheduling 알고리즘이 존재한다. 어떤 알고리즘들이 있는지만 간단하게 짚고 넘어가겠다.

FCFS (First-Come First-Serve) Scheduling

FCFS는 ready 큐에 있는 순서대로 CPU를 할당한다. FIFO 큐로 간단하게 구현이 가능하다.

Shortest Job First Scheduling

CPU Burst 시간이 가장 짧은 프로세스에게 CPU를 할당한다. 그러므로 최소의 평균대기시간을 제공한다.
다만 프로세스들의 CPU Burst 시간을 미리 알 수 없기때문에 대략적으로 CPU Burst 시간이 짧은 프로세스를 선택하여 time quantum 만큼 수행하는 방식으로 구현하기도 한다.

Priority Scheduling

프로세스에 priority를 두고 priority에 따라 CPU를 할당한다. 예를들어 time quantum마다 현재 프로세스보다 높은 priority를 가진 프로세스를 찾아 다음에 수행하는 방식으로 구현할 수 있다.
다만 priority가 낮은 프로세스들에게 기아현상(starvation)이 발생할 수 있고 이를 극복하기 위해 waiting 시간에 따라 프로세스의 priority를 높여주는 Aging 기법을 같이 사용하기도 한다.

RoundRobin Scheduling

선점형 스케줄링 방식으로 RoundRobin으로 동작한다. 보통 time quantum을 10ms 밑으로 두고 time quantum이 소진된 프로세스는 ready queue의 맨 끝에 들어가 다시 CPU 할당을 기다린다.
이 방식은 Response Time이 짧은 이점이 있다.

RoundRobin 방식과 context switching을 연결하여 조금 더 살펴보도록 하자.
Time quantum이 소진되면 다음 ready queue의 헤드에 있는 프로세스를 다음에 실행을 시키게 될텐데 time quantum은 어떻게 측정할 수 있을까?
Kernel은 time quantum을 하나하나 정확하게 측정해서 scheduling을 하지 않는다. 그리고 Linux 또한 고정된 Time quantum을 상수로 가지지 않고 매 프로세스마다 다르도록 varaible 한 값을 가지고 있다. timer interrupt가 발생하면 대략적으로만 시간을 approximate 하여 스케줄링 한다.

RoundRobin 방식에서는 time quantum이 너무 작으면 너무 많은 Context switching이 일어날 수 있는데 이렇게 CPU는 바쁜데 user process는 CPU를 할당받지 못한 상황을 Thrashing 현상이라고 한다.
나중에도 다루겠지만 Virtual Memory에서도 메모리가 너무 작아지면 Thrashing 현상이 일어날 수 있다.

Multi-Level queue Scheduling

큐를 한개만 두지말고 여러개를 두는 방식이다.
예를들어, Foreground queue와 Background queue를 두고 Foreground queue는 roundRobin 방식으로 Background queue는 FCFS 스케줄링 방식으로 구현할 수 있겠다. 그래서 Realtime process는 foreground queue에 할당하고, batch job process는 background queue에 할당할 수 있다.

Multi core Scheduling

여러개의 코어를 사용하는 시스템의 경우 스케줄링은 더욱 복잡해진다.
여러개의 코어를 사용하는 경우 ready queue를 어떻게 설계하는 것이 좋을까?

• global queue 한개를 두고 이 queue를 바라보고 모든 코어들에게 프로세스를 할당해주는 방식
• 각 코어마다 queue를 두고 프로세스를 할당해주는 방식

위의 두가지가 대표적인 설계방식일 수 있겠다.
다만 전자의 global queue를 두는 방식은 scalable 하지 않아 사용하지 않는다. 왜냐하면 queue라는 것은 kernel의 메모리에 있는 data structure이다. 커널에서 한개의 큐를 바라보고 여러개의 코어에 할당하는 방식으로 구현하게 되면 동기화 이슈를 해결하기 힘들기 때문이다. 그리고 후자의 코어마다 queue를 두게되면 얻게되는 이점이 있다.
각 코어마다 queue를 두게되면 프로세스는 계속 같은 코어에 할당이 되는데 CPU Cache의 hit rate를 높일 수 있기때문에 더 효율적으로 작동할 수 있다.

Affinity 라고 특정 코어에 프로세스를 할당할 수 있는 방법이 있다.

In current linux

현재 Linux Kernel 에서는 2.6.23 버전부터 CFS(Completely Fair Scheduler) 라고 불리는 CPU scheduling 알고리즘을 기본값으로 사용한다.
이는 각 task마다 고정된 CPU time을 가지는 것이 아닌, 각 task의 weight 정도에 따라 서로 다른 CPU time을 할당한다.