11. CPU 스케줄링

1. CPU 스케줄링 개요

모든 프로세스는 CPU 를 필요로 하고 모든 프로세스는 먼저 CPU 를 사용하고 싶어 한다. 이러한 프로세스들에게 공정하고 합리적으로 CPU 자원을 할당하기 위해서 운영체제는 어떤 프로세스에 CPU 를 할당할지, 어떤 프로세스를 기다리게 할지를 결정한다.

이렇게 운영체제가 프로세스들에게 공정하고 합리적으로 CPU 자원을 배분하는 것을 "CPU 스케줄링(CPU Scheduling)" 이라고 한다.

1.2 프로세스 우선순위

프로세스 우선순위를 아주 단순하게 생각했을 때 CPU 를 사용하고 싶어 하는 프로세스들이 차례로 돌아가며 CPU 를 이용하게 하는 방법이 있다. 하지만 이는 좋은 방법이 아니다..

그 이유는 프로세스마다 "우선순위" 가 다르기 때문이다. 우선순위가 높은 프로세스란 빨리 처리해야 하는 프로세스들을 의미한다. 우선순위가 높은 프로세스에는 대표적으로 입출력 작업이 많은 프로세스가 있다. 입출력 작업이 많은 프로세스를 먼저 실행하는 것이 왜 더 효율적일까?

이를 이해하려면 일반적인 프로세스가 어떤 과정을 거치며 실행되는지 생각해 보아야 한다. 대부분의 프로세스들은 CPU 와 입출력장치를 모두 사용하며 실행된다. 달리 말하면 프로세스는 실행 상태와 대기 상태를 반복하며 실행된다.

그런데 프로세스 종류마다 입출력장치를 이용하는 시간과 CPU 를 이용하는 시간의 양에는 차이가 있다. 비디오 재생이나 디스크 백업 작업을 담당하는 프로세스와 같이 입출력 작업이 많은 프로세스도 있고, 복잡한 수학 연산, 컴파일, 그래픽 처리 작업을 담당하는 프로세스와 같이 CPU 작업이 많은 프로세스도 있다. 전자를 "입출력 집중 프로세스(I/O bound process)" 후자를 "CPU 집중 프로세스(CPU bound process)" 라고 한다. 입출력 집충 프로세스는 실행 상태보다는 입출력을 위한 대기 상태에 더 많이 머무르게 된다.

CPU 집중 프로세스는 CPU 를 많이 사용해야 하는 프로세스이고, 입출력 집중 프로세스는 그렇지 않은 프로세스인데, CPU 집중 프로세스와 입출력 집중 프로세스가 모두 동일한 빈도로 CPU 를 사용하는 것은 비합리적이다. (입출력 집중 프로세스가 먼저 CPU 를 사용하고 대기 상태로 들어가면 CPU 집중 프로세스가 바로 CPU 를 사용할 수 있다)

이렇듯 모든 프로세스가 CPU 를 차례대로 돌아가며 사용하는 것보다 각각의 상황에 맞게 CPU 를 배분하는 것이 더 효율적이다.

그리고 프로세스 중요도에 맞게 프로세스가 CPU 를 이용할 수 있도록 하기 위해 운영체제는 프로세스마다 "우선순위(priority)" 를 부여한다. 우선순위가 높은 프로세스가 자연스레 CPU 를 더 빨리, 더 자주 실행된다.

1.3 스케줄링 큐

PCB 에 우선순위가 적혀 있다고는 하지만, CPU 를 사용할 다음 프로세스를 찾기 위해 운영체제가 일일이 모든 프로세스의 PCB 를 뒤적거리는 것은 비효율적이다. CPU 를 원하는 프로세스들은 한 두개가 아니고, CPU 를 요구하는 새로운 프로세스들은 언제든 생길 수 있기 때문이다.

그래서 운영체제는 프로세스들에 '줄을 서서 기다릴 것' 을 요구한다. CPU 를 사용하고 싶은 프로세스들, 메모리에 적재되고 싶은 프로세스들, 특정 입출력장치를 사용하고 싶은 프로세스들을 모두 줄 세우는 것이다. 그리고 운영체제는 이 줄을 "스케줄링 큐(scheduling queue)" 로 구현하고 관리한다.

즉, 운영체제는 메모리로 적재되고 싶은 프로세스들을 큐에 삽입하여 줄을 세우고, CPU 를 이용하고 싶은 프로세스들 또한 큐에 삽입하여 줄을 세우고, 특정 입출력장치를 이용하고 싶은 프로세스들 역시 큐에 삽입하여 줄을 세운다.

운영체제가 관리하는 대부분의 자원들은 이렇듯 큐로 관리된다. 그래서 운영체제가 관리하는 줄, 즉 큐에는 다양한 종류가 있다. 대표적인 큐로 준비 큐와 대기 큐가 있다. "준비 큐(ready queue)" 는 CPU 를 이용하고 싶은 프로세스들이 서는 줄을 의미하고, "대기 큐(waiting queue)" 는 입출력장치를 이용하기 위해 대기 상태에 접어든 프로세스들이 서는 줄을 의미한다.

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

우선순위가 낮은 프로세스들이 먼저 큐에 삽입되어 줄을 섰다고 할지라도 우선순위가 높은 프로세스는 그들보다 먼저 처리될 수 있다. 이런 점에서 봤을 때 높은 우선순위를 가진 프로세스는 마치 VIP 와 같다.

대기 상태에 있는 프로세스도 마찬가지이다. 같은 장치를 요구한 프로세스들은 같은 대기 큐에서 기다린다. 입출력이 완료되어 완료 인터럽트가 발생하면 운영체제는 대기 큐에서 작업이 완료된 PCB 를 찾고, 이 PCB 를 준비 상태로 변경한 뒤 대기 큐에서 제거한다. 당연히 해당 PCB 는 준비 큐로 이동한다.

1.4 선점형과 비선점형 스케줄링

우리가 운영체제라고 가정했을 때, 프로세스에 CPU 를 사용하도록 허락하여, 해당 프로세스는 CPU 를 잘 사용하고 있다고 가정하자. 그런데 갑자기 다른 급한 프로세스가 CPU 를 지금 당장 사용하기를 요청한다면 이런 상황에서 선택할 수 있는 방법은 2가지이다.

• "선점형 스케줄링(preemotive scheduling)" : 지금 CPU 를 사용 중인 프로세스로부터 CPU 자원을 빼았아 다른 프로세스에 할당한다.

  • "context swiching" 오버헤드 발생 가능성

• "비선점형 스케줄링(non-preemotive scheduling)" : CPU 를 사용중인 프로레스의 작업이 끝날때까지 다른 급한 프로세스를 기다리게 한다.

  • 아무리 급한 작업이어도 기존 작업이 끝나기 전까지 실행하지 못한다.

2. CPU 스케줄링 알고리즘

2.1 선입 선처리 스케줄링

"선입 선처리 스케줄링" 은 "FCFS 스케줄링(first come first served scheduling)" 이라고도 부른다. 이는 단순히 준비 큐에 삽입된 순서대로 프로세스들을 처리하는 비선점형 스케줄링 방식이다. 언뜻 보기에는 가장 공정해 보이지만, 때때로 프로세스들이 기다리는 시간이 매우 길어길 수 있다는 점에서 부작용이 있는 방식이다.

2.2 최단 작업 우선 스케줄링

선입 선처리 스케줄링의 프로세스 지연을 방지하기 위해서는, 단순하게 생각해보면 CPU 사용 시간이 긴 프로세스는 나중에 실행하고, CPU 사용 시간이 짧은 간단한 프로세스를 먼저 실행하면 된다.

이렇듯 준비 큐에 삽입된 프로세스들 중 CPU 이용 시간의 길이가 가장 짧은 프로세스부터 실행하는 스케줄링 방식을 "최단 작업 우선 스케줄링" 혹은 "SJF 스케줄링(shorted job first scheduling)" 이라고 부른다. 최단 작업 우선 스케줄링은 기본적으로 비선점형 스케줄링 알고리즘으로 분류되지만, 선점형으로 구현될 수도 있다. "선점형 최단 작업 우선 스케줄링"이 뒤에 언급할 최소 잔여 시간 우선 스케줄링이다.

2.3 라운드 로빈 스케줄링

"라운드 로빈 스케줄링(round robin scheduling)" 은 선입 선처리 스케줄링에 타임 슬라이스라는 개념이 더해진 스케줄링 방식이다. "타임 슬라이스" 란 각 프로세스가 CPU 를 사용할 수 있는 정해진 시간을 의미한다. 즉, 라운드 로빈 스케줄링은 정해신 타임 슬라이스만큼의 시간 동안 돌아가며 CPU 를 이용하는 선점형 스케줄링이다.

큐에 삽입된 프로세스들은 삽입된 순서대로 CPU 를 사용하되 정해진 시간만큼만 CPU 를 이용하고, 정해진 시간을 모두 이용하였음에도 아직 프로세스가 완료되지 않았다면 다시 큐의 맨 뒤에 삽입된다. 이때 context switching 이 발생한다.

라운드 로빈 방식에서는 타임 슬라이스가 매우 중요하다. 타임 슬라이스가 지나치게 크다면 선입 선처리 스케줄링과 다를 바 없어 호위 효과가 발생할 수 있고, 타임 슬라이스가 지나치게 작으면 문맥 교환에 발생하는 비용이 커 CPU 는 프로세스를 처리하는 일보다 프로세스를 전환하는데, 온 힘을 다 쓸 여지가 있기 때문이다.

결론적으로 상황에 알맞은 타임 슬라이스 크기가 중요하겠지?

2.4 최소 잔여 시간 우선 스케줄링

"최소 잔여 시간 우선 스케줄링" 혹은 "SRT 스케줄링(shorted remaining time)" 은 최단 작업 우선 스케줄링 알고리즘과 운드 로빈 알고리즘을 합친 스케줄링 방식이다.

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

2.5 우선순위 스케줄링

"우선순위 스케줄링(priority scheduling)" 은 프로세스들에 우선순위를 부여하고, 가장 높은 우선순위를 가진 프로세스부터 실행하는 스케줄링 알고리즘이다.

앞서 설명한 "최단 작업 우선 스케줄링", "최소 잔여 시간 우선 스케줄링" 은 넓은 의미에서 "우선순위 스케줄링"의 일종으로 볼 수 있다.

다만, 우선순위 스케줄링은 근본적인 문제를 내포하고 있다. 우선순위가 높은 프로세스를 우선하여 처리하는 방식이기에 우선순위가 낮은 프로세스는(준비 큐에 먼저 삽입되었더라도..) 우선순위가 높은 프로세스들에 의해 실행이 계속해서 연기될 수 있다. 이를 "기아" 현상이라고 부른다.

이를 방지하기 위한 대표적인 기법으로 "에이징" 이 있다. 이는 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식이다.

2.6 다단계 큐 스케줄링

다단계 큐 스케줄링은 앞서 설명한 우선순위 스케줄링의 발전된 형태이다. "다단계 큐 스케줄링(multilevel queue scheduling)" 은 우선순위별로 준비 큐를 여러 개 사용하는 스케줄링 방식이다. 다단계 큐 스케줄링 하에서 우선순위가 가장 높은 큐에 있는 프로세스들을 먼저 사용하고, 우선순위가 가장 높은 큐가 비어있으면 그 다음 큐에 있는 프로세스들을 사용한다.

이렇게 큐를 여러개 두면 프로세스 유형별로 우선순위를 구분하여 실행하는 것이 편리해진다.

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

2.7 다단계 피드백 큐 스케줄링

다단계 피드백 큐 스케줄링 방식은 다단계 큐 스케줄링의 발전된 형태이다. 앞서 설명한 다단계 큐 스케줄링에서는 프로세스들이 큐 사이를 이동할 수 없다. 그러나 이런 방식대로라면 우선순위가 낮은 프로세스는 계속 연기될 여지가 있다. 즉, 다시 한번 기아 현상이 발생할 수 있다. 이를 보완한 스케줄링 방식이 "다단계 피드백 큐 스케줄링(multilevel feedback queue scheduling)" 이다.

다단계 큐 스케쥴링과 비슷하지만 한가지가 다르다. 바로 프로세스들이 큐 사이를 이동할 수 있다는 것이다. 다단계 피드백 큐 스케줄링에서 새로 준비 상태가 된 프로세스가 있다면 우선 우선순위가 가장 높은 우선순위 큐에 삽입되고 일정 시간 동안 실행된다.

그리고 만약 프로세스가 해당 큐에서 실행이 끝나지 않는다면 다음 우선순위 큐에 삽입되어 실행된다. 그리고 또 해당 큐에서 실행이 끝나지 않는다면 프로세스는 또 다음 우선순위 큐에 삽입되고, 결국 CPU 를 오래 사용해야 하는 프로세스는 점차 우선순위가 낮아진다.

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

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

다단계 피드백 큐 스케줄링은 구현이 복잡하지만, 가장 일반적인 CPU 스케줄링 알고리즘으로 알려져 있다.