CPU[algorithm]

CPU 스케쥴링 알고리즘

CPU의 스케쥴링 알고리즘은 매우 다양하기 때문에 이번 포스터에서는 대표적인 7가지의 알고리즘에 대해서 설명하겠습니다.

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

선입 선처리 스케쥴링 알고리즘은 이름 그대로 먼저 들어온 프로세스부터 처리하는 알고리즘 방식입니다.

선입 선처리 스케쥴링 알고리즘은 먼저 들어온 순서대로 처리하기 때문에 실행시간이 긴 알고리즘이 많으면 프로세스들이 대기해야하는 대기 시간이 길어지는 단점이 존재합니다.

이런 현상을 호위 효과라고 합니다.

최단 작업 우선 스케쥴링(SJF 스케쥴링)

최단 작업 우선 스케쥴링 알고리즘은 호위 효과를 방지할 수 있는 알고리즘입니다.

준비 큐에 삽입된 프로세스들 중, 실행시간이 가장 적은 프로세스부터 실행하는 방식입니다.

최단 작업우선 스케쥴링 알고리즘은 기본적으로 비선점형 스케쥴링 알고리즘으로 분류됩니다.

라운드 로빈 스케쥴링

라운드 로빈 스케쥴링은 선입 선처리 스케쥴링을 바탕으로 타임 슬라이스라는 개념이 더해진 스케쥴링 방식입니다.

여기서 타임 슬라이스는, 정해진 시간입니다.

즉, 라운드 로빈 스케쥴링은 정해진 시간을 두고 CPU를 이용하는 선점형 스케쥴링입니다.

큐에 삽입된 프로세스들은 삽인된 순서대로 CPU를 이용하지만, 타임 슬라이스가 끝났음에도 프로세스가 완료 되지 않았으면, 큐의 맨뒤로 다시 삽입이되는 원리입니다.

이때, 문맥교환이 발생하게 됩니다.

라운드 로빈 스케쥴링은 타임 슬라이스의 크기가 매우 중요합니다.

지나치게 그면 선입 선처리 스케쥴링과 다를바가 없어 호위 효과가 발생하고, 너무 작으면 문맥교환이 자주 발생하는 비용이 커 CPU는 프로세스를 처리하는 일보다 프로세스를 전환하는데 힘을 쏟기 때문입니다.

최소 잔여 시간 우선 스케쥴링

최소 잔여 시간 우선 스케쥴링은 최단 작업 우선 스케쥴링과 라운드 로빈 스케쥴링이 합쳐진 방식입니다.

최소 잔여 시간 우선 스케쥴링 하에서 프로세스들은 정해진 타임 슬라이스 만큼 CPU를 사용하되, CPU를 사용할 다음 프로세스로는 남아있는 작업 시간이 가장 작은 프로세스가 선택되는 방식입니다.

우선순위 스케쥴링

우선순위 스케쥴링은 프로세스들에 우선순위를 부여하고 가장 높은 우선순위를 가진 프로세스부터 실행하는 스케쥴링 입니다.

하지만 우선순위 스케쥴링은 근본적인 문제가 있습니다.

우선순위 스케쥴링은 우선순위가 높은 프로세스부터 처리하기 때문에 우선순위가 낮은 프로세스는 우선순위가 높은 프로세스에 의해 실행이 계속해서 연기될 수 있습니다.

이를 기아현상이라고합니다.

하지만 이런 현상을 해결하는 방법이 있습니다. 바로 에이징 기법입니다.

에이징 기법은 우선순위가 낮아 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식입니다.

다단계 큐 스케쥴링

우선순위 스케쥴링의 발전된 형태가 다단계 큐 스케쥴링 방식입니다.

다단계 큐 스케쥴링은 우선순위 별로 준비 큐를 여러개 사용하는 스케쥴링 방식입니다.

우선순위가가장 높은 큐에있는 프로세스들을 먼저 처리하고, 우선순위가 가장 높은 큐가 비어있다면, 다음 우선순위의 큐에 있는 프로세스들을 처리하는 방식입니다.

이렇게 우선순위 별로 큐를 만들어서 사용하면, 큐마다 우선순위를 구분하여 큐마다 특정 프로세스들만 삽입하여 사용할 수 있습니다.

또한 큐별로 타임 슬라이스를 여러 개 지정할 수 있고, 큐마다 다른 스케쥴링 알고리즘을 사용할 수 있습니다.

하지만 다단계 큐 스케쥴링은 프로세스들이 큐 사이를 이동할수 없다는 단점이 존재합니다.

이런 단점은 우선순위가 낮은 프로세스가 계속 연기될 여지가 있어 기아 현상이 발생할 수 있습니다.

다단계 피드백 큐 스케쥴링

다단계 큐 스케쥴링의 기아현상을 보완한 스케쥴링이 다단계 피드백 큐 스케쥴링입니다.

기본적인 원리는 다단계 큐 스케쥴링과 비슷하게 동작하지만, 프로세스들이 큐 사이를 이동할 수 있다는 점이 다릅니다.

다단계 피드백 큐 스케쥴링의 동작과정은 새로 준비 상태가 된 프로세스가 있다면 우선 우선순위를 가장 높은 큐에 삽입하고 슬라이스 시간동안 실행됩니다.

프로세스가 끝난다면 이상없지만, 슬라이스 시간이 끝나고 나서도 프로세스가 끝나지 않았다면 다음 우선순위 큐에 다시 프로세스를 삽입합니다.

즉, CPU를 비교적 오래 사용해야 하는 CPU 집중 프로세스들은 점차 우선순위가 낮아지고, 비교적 CPU를 적게 사용하는 입/출력 집중 프로세스들은 자연스레 우선순위가 높은 큐에서 실행이 끝납니다.

다단계 피드백 큐 스케쥴링은 프로세스들이 큐 사이를 자유롭게 움직일 수 있는 방식이기 때문에 낮은 우선순위의 큐에서 오랫동안 기다리고 있었다면 점차 우선순위가 높은 큐로 이동시키는 방식인 에이징 기법을 통해 기아 현상을 예방할 수 있습니다.

즉, 다단계 큐 피드백 스케쥴링 알고리즘은 어떤 프로세스의 CPU이용 시간이 길면 낮은 우선순위 큐로 이동시키고, 어떤 프로세스가 낮은 우선순위 큐에서 오랫동안 기다린다면 우선순위를 점차 높은 우선순위 큐로 이동시킬 수 있는 알고리즘 입니다.