들어가기 전

이번 블로깅에 대해선 CPU 스케줄링 알고리즘 에 대해 넓고 얕게 알아보자.

전 프로세스와 스레드 에 대한 블로깅에서 CPU 스케줄러에 대한 이야기가 많이 나왔다.
CPU 스케줄러 는 CPU 스케줄링 알고리즘에 따라 프로세스에서 해야 하는 일을 스레드 단위로 CPU에 할당한다.

프로그램이 실행될 때는 CPU 스케줄링 알고리즘이 어떤 프로그램에 CPU 소유권을 줄 것인지 결정한다. 이 알고리즘은 CPU 이용률은 높게, 주어진 시간에 많은 일을 하게, 준비 큐에 있는 프로세스는 적게, 응답 시간을 짧게 설정하는 것을 목표로 한다.

위에 사진은 CPU 스케줄링에 종류에 대해 정리한 표이다. 이제 이것을 하나씩 자세히 봐보자.

비선점형 방식

이는 프로세스 스스로 CPU 소유권을 포기하는 방식이며, 강제로 프로세스를 중지하지 않는다. 이 때문에 컨텍스트 스위칭으로 인한 부하가 적다.

1. FCFS

이는 First Come, First Served 로 가장 먼저 온 것을 가장 먼저 처리하는 알고리즘이다. 길게 수행되는 포르세스 때문에 Convoy effect가 발생할 수 있다.

• Convoy effect

  준비 큐에서 오래 기달리는 현상

2. SJF

이는 Shortest Job First로 실행 시간이 가장 짧은 것을 가장 먼저 실행하는 알고리즘이다.

이는 Starvation이 발생할 수 있다.

• Starvation

  긴 시간을 가진 프로세스가 실행되는 않는 현상

평균 대기 시간이 가장 짧은 알고리즘이다. 하지만 실제로는 실행 시간을 알 수 없기 때문에 과거에 실행했던 시간을 가지고 추측해서 사용했다.

3. 우선순위

기존 SJF 스케줄링의 경우 긴 시간을 가진 프로세스가 실행되지 않는 현상이 있었다. 이는 오래된 작업일수록 우선 순위를 높이는 방식을 통해 위에 알고리즘에 단점을 보완한 방식이다.

선점형 방식

이는 현대 운영체제가 쓰는 방식으로 지금 사용하고 있는 프로세스를 알고리즘에 의해 중단 시켜 버리고, 강제로 다른 프로세스에 CPU 소유권을 할당하는 방식을 말한다.

1. 라운드 로빈

이는 현대 컴퓨터가 쓰고 있는 스케줄링인 우선순위 스케줄링의 일종으로 각 프로세스는 동일한 할당 시간을 주고 그 시간 안에 끝나지 못하면 다시 준비 큐 뒤로 가는 알고리즘이다.

일반적으로 전체 작업 시간은 길어지지만 평균 응답 시간은 짧아진다는 특징이 있다.

2. SRF

SJK는 실행 시간이 더 짧은게 들어와도 기존 작업을 모두 수행하고 그 다음 짧은 작업을 이어간다. 하지만 SRF(Shortest Remaining Time First)는 중간에 더 짧은 작업이 들어오면 수행하던 프로세스를 중지하고 해당 프로세스를 수행하는 알고리즘이다.

3. 다단계 큐

이는 우선순위에 따른 준비 큐를 여러 개 사용하고, 큐마다 라운드 로빈이나 FCFS 등 다른 스케줄링 알고리즘을 적용한 것을 말한다. 큐 간의 프로세스 이동이 안되므로 스케줄링 부담이 적지만 유연성이 그만큼 떨어진다.

마무리

이번 블로깅에선 CPU 스케줄링 알고리즘 에 대해 알아보았다. 이 블로깅의 목적은 깊게 배우는 것이 아니라 개발자 대회에 낄 정도의 넒고 얕은 지식을 목표로 하고 있다. 이 블로깅을 통해서 전체적인 CPU 스케줄링 알고리즘 에 대해 잡았으면 좋겠다. 그리고 감을 잡았고 좀 더 깊게 배우고 싶다면 이 블로깅의 키워드를 길로 잡아서 하나씩 공부해 나간다면 매우 도움이 될 것이라고 생각한다.