CPU의 동시성과 병렬성

현대의 CPU에는 동시성(Concurrency)과 병렬성(Parallelism)이라는 2가지 중요한 개념이 있다.
첫 번째로 동시성(Concurrency)은 여러 개의 독립적인 작업들을 시간 분할 방식으로 쪼개서 문맥 교환(Context Switching)을 반복하며 실행하여 마치 여러 작업이 동시에 실행되는 듯이 보이게 하는 것이다. 이렇게 작업을 잘게 쪼개서 돌아가며 수행하는 이유는 CPU의 유휴 시간을 최소화하기 위해서이다. 한 작업이 I/O를 기다리느라 wait 상태에 들어가도 CPU가 쉬는 일이 없도록, 그리고 실행 시간이 긴 작업과 짧은 작업이 혼재되어 ready queue에 들어가 있더라도 짧은 작업이 긴 작업에 밀려 오랫동안 처리되지 않는 호위 효과(Convoy Effect) 문제 등이 발생하지 않도록 하는 것이 동시성의 의의이다.
두 번째로 병렬성(Parallelism)은 동시에 여러 작업을 CPU의 멀티 코어, 멀티 스레드 등을 이용하여 연산하는 것을 뜻한다. 단일 작업을 여러 개로 쪼개서 연산하는 것도, 여러 독립된 작업을 여러 군데에서 동시에 처리하는 것도 모두 병렬성이다. 병렬성의 의의 또한 모든 리소스를 최대한으로 활용하는 것에 있다. CPU의 여러 파트 중 하나가 작업 A를 완수하더라도 바로 작업 B를 할당하여 유휴 시간을 최소화하는 것이다.

CPU의 스케줄링

위에서 설명한 동시성과 병렬성을 구현하기 위해서 CPU는 계속해서 문맥 교환을 반복한다. 그런데 현재 수행하던 작업이 CPU에서 나갔을 때 다음으로 수행할 작업은 어떤 기준으로 선택되는 것인가? 그 방법이 바로 CPU의 스케줄링 알고리즘이다.
CPU가 다음 작업을 선택하는 시기는 다음과 같다.
1) 작업이 실행(Running) 상태에서 대기(Wait) 상태로 전환될 때 (e.g. : I/O 발생)
2) 작업이 실행(Running) 상태에서 준비(Ready) 상태로 전환될 때 (e.g. : Interrupt 발생)
3) 작업이 대기(Wait) 상태에서 준비(Ready) 상태로 전환될 때 (e.g. : I/O 완료)
4) 작업이 종료(Terminated)되었을 때

1,4번 상황에서만 문맥 교환이 일어나는 것을 비-선점형 스케줄링(non-preemptive scheduling)이라고 하고, 모든 상황에서 문맥 교환이 일어나는 것을 선점형 스케줄링(preemptive scheduling)이라고 한다.

비-선점형 스케줄링

비-선점형 스케줄링은 어떤 작업이 CPU를 이미 사용하는 중이라면 그것을 중지시키고 CPU를 뺏어올 수 없는 스케줄링 방식을 말한다. 문맥 교환이 상대적으로 적게 일어나지만 작업의 배치에 따라 기아(Starvation) 등의 문제가 생길 수 있다.

• FCFS(First Come, First Served) : 프로세스가 요청한 순서에 따라 CPU가 할당되는 선착순 방식이다. 실행 시간이 긴 작업들에 밀려 짧은 작업들이 처리되지 않고 밀리는 호위 효과(Convoy Effect)가 발생할 수 있다.
• SJF(Shortest Job First) : 실행 시간이 가장 짧은 프로세스를 가장 먼저 처리하는 방식이다. 하지만 모든 프로세스의 실행 시간을 예측하는 것은 어려우므로 현실성이 부족하다. 실행 시간이 긴 프로세스가 계속해서 들어오는 짧은 프로세스에 밀려 무기한으로 대기하게 되는 기아(Starvation) 문제가 존재한다.
• 우선 순위(Priority) : 각각의 프로세스에 우선 순위 넘버가 달려있는 알고리즘. 위의 기아 문제를 오랫동안 대기한 프로세스는 우선 순위를 높여주는 노화(Aging) 기법을 사용하여 해결할 수 있다.

선점형 스케줄링

현대 OS가 사용 중인 방식으로 어떤 프로세스가 CPU를 점유하고 있더라도 OS에서 작업을 중지시킨 후 다른 작업을 할당해줄 수 있다. CPU의 독점과 무기한 대기 문제를 해결할 수 있지만 잦은 문맥 교환으로 인해 오버헤드가 커질 수 있는 문제점이 있다.

• RR(Round Robin) : 각각의 프로세스마다 정해진 시간동안만 CPU를 사용하게 한다. 효율적인 방식이지만 할당 시간이 너무 길면 FCFS와 같이 동작하게 되고, 할당 시간이 너무 짧으면 문맥 교환이 그만큼 잦아져 오버헤드가 커지는 문제가 있다.
• SRF(Shortest Remaining time First) : 현재 실행중인 프로세스의 남은 수행 시간보다 수행 시간이 짧은 프로세스가 있다면 교체해주는 알고리즘이다. 평균 대기 시간을 줄일 수 있지만 SJF와 같이 프로세스의 남은 수행 시간을 예측하기가 어렵다는 문제가 존재한다.
• Multilevel Queue : CPU의 ready queue가 여러 개의 queue로 나뉘어서 각 queue가 각자의 스케줄링 알고리즘을 갖게 하는 방식이다. queue들은 각각 우선 순위가 다르다. 우선 순위가 높은 queue에는 주로 OS의 화면에 보이는 프로세스들인 전면 프로세스(Foreground process)가 RR 방식으로, 우선 순위가 낮은 queue에는 주로 OS의 화면에 보이지 않는 후면 프로세스(Background process)들이 FCFS를 활용하여 작동하게 된다. 각 queue들간에 프로세스의 이동이 불가능하고, 이를 가능하게 만든 MFQ(Multilevel Feedback Queue)도 존재한다.

지금까지 CPU의 스케줄링 알고리즘들에 대해 알아보았다. 다음 포스팅에서는 각 스레드 간의 동기화(Synchronize)에 대해 알아보도록 하겠다.