CPU 스케줄링 알고리즘 및 관련된 여러 주제

1. CPU 스케줄링이란

CPU는 한번에 단 하나의 프로그램만 수행할 수 있다. 여러 프로그램이 동시에 실행되려면, CPU가 여러 프로그램을 빠르게 번갈아가면서 수행해 동시에 동작하는 것처럼 보여야 한다.  CPU 스케줄링이란 대기하고 있는 프로세스 중에 어떤 프로세스를 다음으로 실행할지를 결정하는 것이다. CPU 상에서 동작하는 프로그램이 있으면 다른 프로그램들은 대기해야한다.

동시에 실행되는 여러개의 프로그램을 어떤 순서로 실행하느냐가 시스템의 전체 성능에 직접적인 영향을 미친다. CPU 스케줄링에 따라서 프로세스의 대기시간(waiting time), 응답시간(turn around), CPU 이용률에 영향을 미치며 CPU 스케줄링에 따라서 시스템 성능이 좌우된다.

프로세스의 상태

NEW: 프로세스가 생성되고 초기화. 필요한 메모리 및 자원 할당을 기다리고 있음.

READY: 실행될 준비가 완료된 상태. 필요한 모든 자원을 할당받았으며 CPU 실행을 위해 대기. 

RUNNING: 프로세스가 CPU를 할당받아 명령어를 실행하고 있는 상태.

WAITING(SLEEP): 특정 이벤트의 발생이나, 자원의 가용성을 기다리는 상태

• 정해진 시간이 경과하는 것을 기다림.
• 사용자 입력 처리: 키보드나 마우스 같은 사용자의 입력이 발생하면, 인터럽트가 발생하여 현재 실행 중인 서비스는 일시 중단되고, 운영체제가 입력을 처리한다.
• 디스크 입출력: 파일에 읽고 쓰기의 종료를 기다림
• 네트워크 요청: 네트워크를 통해 응답을 기다림

TERMINATED: 프로세스가 실행을 마치고 시스템에서 제거된 상태

[참고] Context Switching이 일어나는 경우

1. 현재 실행중인 프로세스가 실행을 완료하였을때 되었을때
2. 현재 실행중인 프로세스가 WAITING 상태가 되었을때
3. 우선순위 큐 스케줄링에서 큐에 더 높은 우선순위의 작업이 들어왔을때
4. 라운드-로빈 스케줄링에서 현재 실행중인 프로세스가 시간 할당량을 소진했을때

2. CPU 스케줄링 성능 평가 기준

CPU 스케줄링 알고리즘의 성능을 평가하기 위해 주로 사용되는 지표는 다음과 같다. 각 시스템에서 중요한 지표가 다를 수 있다. 각 CPU 스케줄링의 지표를 확인해 CPU 스케줄링 성능을 평가하고 상황에 따라 적절한 알고리즘을 선택할 수 있다.

 

1. CPU 이용률이 높은가? CPU가 사용되지 않고 idle 상태로 남아있을 수록 CPU 이용률이 낮아진다.

2. 처리량 (Throughput)이 높은가? 단위시간당 완료한 프로세스의 수를 말한다. CPU 이용률이 높을수록 처리량이 높아진다. CPU 이용률이 100% 인 상태에서 프로세스가 추가적으로 실행되면 컨텍스트 스위치 오버헤드 증가로 인해 오히려 처리량이 작아진다.

3. 처리 완료 시간(Turnaround Time)이 짧은가? 요청을 시작한 시점부터 프로세스 실행을 완료할때까지 걸리는 시간을 말한다.

4. 응답 시간(Response Time)이 짧은가? latency라고도 함. 요청을 시작한 시점부터 CPU가 처음으로 처리를 시작할 때까지 걸리는 시간을 말한다.

5. 대기 시간(WAITING TIME)이 짧은가? : 프로세스가 준비 큐에서 대기하며 보낸 총 시간을 대기 시간이라고 한다. 일반적으로 입출력 작업으로 인한 대기시간은 대기 시간에 직접 포함되지 않는다. 대기시간이 짧으면 더 빨리 처리가 완료될 수 있다는 의미다.

 

[참고] 대기하고 있는 프로세스들이 있는데도 CPU가 사용되지 않는 경우

1. 순환 대기: 다음으로 실행될 프로세스가 그 다음 프로세스의 자원을 기다리는 경우 순환 대기가 형성되며 프로세스들이 계속 대기 상태가 되어 아무런 프로세스도 실행되지 않으면서 CPU 이용률이 떨어진다.
2. 페이지 교체: 프로세스가 빈번하게 전환되는 환경에서는 페이지 폴드의 발생 빈도가 높아질 수 있다. CPU가 실행하는 프로그램이 자주 변경되면, 각 프로세스의 페이지가 메모리에 로드되고 교체되는 과정이 빈번하게 발생할 수 있다. 페이지 교체를 기다리는 작업이 많아지면 CPU는 idle상태가 될 수 있다.

[참고] 응답시간(response time)의 두가지 의미

1. 첫번째 요청부터 응답이 도착할때까지 걸리는 시간: 사용자가 시스템에서 처음으로 반응을 얻는데 소요된 시간
2. 요청이 완전히 처리될 때까지 걸리는 시간: 서버에서 해당 요청을 완전히 처리하고 응답을 완료하는데 소요된 시간.

• 사용되는 맥락과 목적에 따라 다르게 해석하므로 정확한 의미를 파악할 수 있어야 한다.

3. CPU 스케줄링 알고리즘

• 각 CPU 스케줄링의 의미와 장점과 단점에 대해 알아본다.
• CPU 스케줄링 알고리즘은 단지 CPU 스케줄링에만 사용되는 것이 아니라, 한정된 자원을 배분해야 하는 여러 곳에서 활용될 수 있다. 각 알고리즘을 어떤 상황에 적용할 수 있을지도 살펴본다.

FCFS(First Come First Served Scheduling)

가장 먼저 큐에 추가된 프로세스를 실행하는 알고리즘이다. CPU 실행 대기 상태(READY) 상태의 프로세스들을 Queue로 관리한다. 비선점형 알고리즘으로 프로세스가 종료되거나 SLEEP 상태가 될대까지 CPU를 점유한다.

장점은 가장 간단하고 공정하다. 하지만 다음과 같은 단점이 있다. 1) 긴 작업들이 먼저 실행될 경우 다른 작업들이 이를 기다려야 하므로 시스템의 평균 Response Time, Turnaround Time, Waiting Time이 길어져 성능이 저하될 수있다. 2) 프로세스가 언제 실행될지 예측하기 어렵다.

 

다음과 같은 상황에서 FCFS가 활용될 수 있다.

1. 선착순 쿠폰 발행: 여러 사람이 동시에 선착순 쿠폰을 발급받기 위해 접속할때 먼저 큐에 추가된 요청부터 처리한다. 모든 사람의 요청의 우선순위가 동일하게 처리되어 공정하다.
2. 배치 프로그램의 작업 스케줄링: 배치 프로그램은 일괄 처리 작업을 수행하는 프로그램인데 보통 사용자의 요청 없이 백그라운드에서 일련의 작업을 자동으로 수행한다. 이때 응답을 기다리는 사용자가 없기 때문에 대기시간이 오래 걸려도 상관 없고, 작업 순서가 중요하지 않기 때문에 간단한 FCFS를 사용할 수 있다.

SJF(Shortest Job first Scheduling)

가장 짧은 실행 시간을 가진 프로세스를 우선적으로 실행하는 방식이다. 짧은 프로세스를 먼저 처리함으로써 평균 대기시간을 최소화할 수 있다는 장점이 있다. 실행 시간이 짧은 작업이 계속 추가될 경우 실행 시간이 긴 프로세스가 계속 뒤로 밀려 실행되지 못하는 기아(Starvation)현상이 발생할 수 있다는 단점이 있다. 무엇보다도 각 프로세스의 실행 시간을 실행 전에 알기 어려워 현실적으로 적용하기 어렵다.

RR(Round Robin Scheduling)

임의의 프로세스가 종료될 때까지 CPU를 점유하는 것이 아니라, 여러 프로세스들이 CPU를 조금씩 돌아가면서 차지하는 방식이다. 각 프로세스는 일정한 크기의 time slice동안 CPU를 점유하고 실행하다가 time slice가 끝나면 다시 준비 큐에 들어간다. 프로세스를 원형 큐로 관리할 수 있다.

모든 프로세스에게 공평한 기회를 제공하기 때문에 여러 프로세스의 대기시간, 응답시간을 일관되게 유지할 수 있다. 모든 하지만 time slice가 매우 크면 FCFS와 같아 평균 대기 시간이 길어질 수 있고, time slice가 매우 작으면 context switching이 자주 일어나 성능이 저하된다는 단점이 있다.

[참고] 로드밸런서의 Round Robin

로드밸런서의 RR은 요청을 서버에 균등하게 분산하는 방식을 말한다. 요청이 들어올 때마다 서버 목록을 순환하면서 각 서버에 요청을 번갈아 할당함으로써 각 서버의 부하를 균형있게 분산한다.

라운드 로빈은 원형으로 목록을 순환하면서 처리하는 방식을 나타내는 일반적인 용어이다. CPU 스케줄링은 프로세스 목록을 순환하고 로드밸런서는 서버 목록을 순환한다. CPU 스케줄링에서의 라운드 로빈과 로드 밸런서에서의 라운드 로빈의 구체적인 알고리즘은 다르지만 순환하면서 처리한다는 점에서 공통되기 때문에 라운드 로빈이라는 이름을 사용한다.

우선순위 스케줄링(Priority Scheduling)

각 프로세스들을 우선순위에 따라서 스케줄링하는 방식이다. 우선순위 스케줄링은 선점형과 비선점형 두 가지 방식으로 구현될 수 있다. 선점형 방식에서는 우선순위가 더 높은 프로세스가 도착할때마다 CPU를 빼앗아 할당하는 방식이고, 비선점형 방식은 대기 큐에서 우선순위가 높은 프로세스가 먼저 실행되고 실행 중인 프로세스가 완료되고 나서 다음프로세스가 실행되는 방식이다. 대기 큐를 Heap을 사용해서 구현할 수 있다.

특정 프로세스의 빠른 실행을 보장하고 싶을때 사용할 수 있다. 하지만 우선순위 역전, 기아상태로 인해서 무한 봉쇄에 빠질 수 있다.

• 우선순위 역전으로 인한 무한봉쇄: 우선순위가 높은 프로세스가 우선순위가 낮은 프로세스가 보유한 자원을 필요로 해서 프로세스가 실행되지 못할때 우선순위 역전이라고도 한다. 이때, 1) 우선순위가 높은 프로세스가 대기상태로 들어가지 않거나 2)순환 대기가 발생하거나 3) 프로세스가 필요한 자원을 반납하지 않을때 무한 봉쇄가 발생할 수 있다.
• 기아 상태로 인한 무한 봉쇄: 높은 우선순위의 프로세스들이 꾸준히 들어와서 낮은 우선순위의 프로세스들이 영원히 실행되지 못하는 상태를 말한다. 오랫동안 시스템에서 대기하는 프로세스들의 우선순위를 점진적으로 증가시키는 aging을 통해서 해결할 수 있다.

우선순위 스케줄링은 특정 프로세스의 빠른 실행을 보장하기 위해서 사용할 수 있다. 예를 들어 사용자의 입력에 대한 즉각적인 피드백이 중요한 웹 브라우저나 텍스트 편집기 와 같은 대화형 프로세스 혹은 긴급하게 처리해야 프로세스에 높은 우선순위를 부여해서 응답시간 및 대기시간을 줄일 수 있다.

다단계 큐 스케줄링(MultiLevelQueue Scheduling)

프로세스를 우선순위에 따라서 여러개의 큐로 분류하고, 큐는 고유한 스케줄링 알고리즘을 가지도록 한다. 이때 큐들 사이의 스케쥴링과 각 큐의 스케쥴링이 필요하다. 다단계 큐 스케줄링의 구현은 시스템의 구성에 따라서 달라진다.

 

큐의 분류: 보통 프로세스의 종류(real-time process, system-process, interactive-process, batch-process)에 따라서 우선순위를 구분한다. real-time process의 경우 빠른 응답시간이 중요하기 때문에 우선순위가 높고, batch-process의 경우 응답 시간이 특별히 중요하지 않기 때문에 낮은 우선순위를 가진다.

 

큐 사이의 스케쥴링: 보통 높은 우선순위의 큐를 우선적으로 처리하고 높은 우선순위의 큐에 프로세스가 없거나 모두 WAITING 상태일때 낮은 우선순위의 큐를 실행한다.

 

각 큐의 스케쥴링: 각 큐는 다른 스케쥴링 알고리즘을 적용한다. 각 우선순위에 따라 다른 요구사항이 있을 수 있기 때문이다. 예를 들어 높은 우선순위의 큐에는 라운드 로빈 방식을 적용해 각 프로세스들이 자주 조금씩 실행되도록 해 빠른 응답이 가능하도록 한다. 낮은 우선순위 큐에는 간단하고 한번에 하나씩 처리를 완료하는 FCFS 방식을 적용한다.

 

다단계 큐 스케줄링은 높은 우선순위의 작업이 빠르게 처리될 수 있게 하면서, 각 큐를 서로 다른 방법으로 관리할 수 있다는 장점이 있다. 하지만 구현 및 관리가 복잡하고, 스케줄링 오버헤드가 발생할 수 있다.

다단계 피드백 큐 스케줄링(MultiLevel Feedback Queue Scheduling)

다단계 큐 스케줄링에 피드백을 추가한 것이다. 피드백에 따라서 프로세스가 큐들 사이를 이동할 수 있도록 해 우선순위를 적응적으로 조정할 수 있게 한다. 현대에 가장 일반적인 CPU 알고리즘이다.

프로세스 실행 중에 프로세스가 CPU와 I/O 자원을 사용하는 방식을 살핀 후 그에 따라 프로세스의 우선순위를 조정한다. 예를들어, 예상보다 더많은 CPU 시간을 필요로 하는 경우 낮은 우선순위 큐로 내려 다른 우선순위가 높은 작업들을 더 우선적으로 처리할 수 있다. 반면에, 짧은 시간안에 완료될 것으로 예상되는 프로세스는 높은 우선순위 큐로 올려 빠르게 처리할 수 있다.

또한, 만약 기아 상태의 프로세스가 있다면 높은 우선순위 큐로 올린다.

다단계 큐 스케줄링은 피드백을 통해 우선순위를 조정하면서 우선순위가 높거나 짧은 작업을 우선적으로 처리하고, 기아 상태를 예방하여 시스템의 반응성을 향상시킨다.

3. CPU 스케줄링과 관련된 여러 주제

3-1. 멀티코어 CPU에서의 CPU 스케줄링

동시성: 싱글 코어인 CPU는 한번에 하나의 프로그램만 실행가능하다. 여러 프로그램을 실행하려면 빠르게 번갈아가면서 수행해 동시에 동작하는 것처럼 보이게 해야 한다. 이를 동시성이라고 한다.

병렬성: 멀티 코어인 CPU 는 각 프로세서가 하나의 프로그램을 실행해 여러개의 프로그램을 실제로 동시에 실행이 가능하다. 이를 병렬성이라고 한다.

 

멀티 코어 환경에서 CPU 스케줄링은 다음과 같은 두가지 관점에서 일어난다.

- 여러 개의 논리 CPU 에 프로세스를 어떻게 분배할 것인가.

- 각 CPU에서 분배받은 프로세스들을 어떤 순서로 실행할 것인가.

각 관점에서 사용되는 알고리즘의 종류는 다르다. 일반적으로 CPU 스케줄링이라고 하면 2)의 관점에서 사용되는 알고리즘을 의미한다.

3-2. 스레싱: 프로세스 스케줄링과 메모리 페이지 교체

프로세스는 운영체제로부터 메모리를 할당받는다. 이때 메모리는 가상 메모리를 사용한다. 따라서 프로그램 코드의 일부는 실제 메모리에 올라와 있으며 일부는 실행을 위해서는 디스크에서 로드하는 페이지 교체가 필요하다.

컨텍스트 스위칭이 자주 일어나면 페이지 폴트가 발생할 확률이 높아진다. 현재 실행 중인 데이터가 실제 메모리에 존재하고 있을 가능성이 높지만, 컨텍스트가 바뀌어서 다른 프로세스를 위한 데이터로 교체될 수 있기 때문이다.

사용하는 프로세스가 많아질 때 어느 한계점까지는 CPU 이용률이 증가하다가 한계점 이상부터는 오히려 CPU 이용률이 떨어지게 되는데 이유 중 하나가 스레싱 때문이다. 동시에 실행되는 프로세스가 많아질수록 각 프로세스의 메모리 페이지들은 더욱 작아지게 되고, 너무 적은 페이지를 할당받은 프로세스들은 페이지 폴트가 증가하게 되어 Swapping이 증가하고 결국 CPU 이용률이 떨어지게 된다. 이때, CPU 스케줄링은 우선순위를 조정하여 특정 프로세스에 더 많은 CPU 시간을 할당하여 스와핑 빈도를 낮출 수 있다.

3-3. 프로세스의 상태와 쓰레드의 상태

프로세스가 실행중일때 스레드에도 스케줄링이 적용된다. 프로세스와 마찬가지로 스레드 간의 스케줄링도 운영체제에 의해서 스케줄링 된다. 이때 프로세스 스케줄링과 스레드 스케줄링은 독립적으로 다뤄지며 서로 다른 알고리즘이 적용될 수 있다. 스레드 스케줄링은 보통 우선순위 기반 스케줄링이나, 다중 큐 스케줄링과 같은 알고리즘을 사용한다.

프로세스는 Created, Ready, Running, Waiting, Terminated의 상태를 가질 수 있다. 반면에, 스레드는 Created, Runnable, Running, Waiting, Blocked, Terminated의 상태를 가질 수 있다. 스레드는 Waiting 상태와 Blocked 상태를 구분해서 다룬다. 스레드는 특정 이벤트가 발생하기를 기다리는 Waiting과 외부적인 요인으로 인해서 막힌(다른 스레드가 실행중인 synchronized block에 대해 대기하고 있는 상황) 을 구분해서 다룬다. 이는, 스레드의 상태변화를 정확하게 추적하고 스레드 간의 동기화를 효과적으로 관리하기 위한 것이다. 프로세스는 서로 독립된 공간을 가지고 있기 때문에 메모리 공유가 자동으로 이루어지지 않고 운영체제를 통한다. 따라서 프로세스 간의 상태 관리에 있어서는 Waiting과 Blocked 상태를 명확히 구분할 필요가 없다.

3-4. 서블릿 컨테이너와 프로세스

서블릿 컨테이너(tomcat)은 다수의 http 요청을 동시에 처리하기 위해서 내부적으로 스레드 풀을 사용하여 http 요청을 관리한다. 클라이언트로부터 요청이 들어오면, 스레드 풀에서 사용 가능한 스레드가 요청을 받아 처리하고, 요청 처리가 끝난 스레드는 다시 스레드 풀로 돌아가 다음 요청을 처리할 준비를 한다. 만약 모든 스레드가 사용 중이라면 추가 요청들은 대기 큐에서 대기하게 된다. tomcat의 스레드 스케줄링은 주로 운영체제의 스케줄링 정책에 의존한다. 스레드에 우선순위를 할당할 수있지만(thread.setPriority()) 실제 우선순위의 효과는 운영 체제의 스케줄링 정책에 크게 의존적이다.