3. CPU 스케줄링

 

이전 "프로세스 관리" 편에서 다루었던 프로세스 상태는 CPU 스케줄링과 관련이 있다.

 

2. 프로세스 관리

 

 

CPU 스케줄링과 디스패처

 

 

그렇다면, 아래처럼 프로세스의 전반적인 작업 상태를 관리하고 어떠한 프로세스에게 CPU를 할당해줄지를 결정해주는 CPU 스케줄링이 필요한 이유는 무엇인가? 이를 알기위해 CPU, I/O 버스트에 대해 알아보자.

 

 

 

CPU 버스트 : CPU를 통해 프로세스의 기계어를 실행 중인 주기
I/O 버스트 : 입력, 출력이 이뤄지는 주기

CPU가 사용되는 시간 단위가 길다면 CPU bound job(계산 위주의 작업)이라 하며, CPU에서 기계어를 실행하는 시간이 짧고 I/O 버스트가 많다면 I/O bound job(CPU를 잡고 계산하는 시간보다 입출력에 많은 시간이 필요한 작업)이라 한다.

 

 이처럼, 여러 종류의 작업(process)들이 섞여 있기에 CPU 스케줄링이 필요하며, 이를 통해 활발한 상호작용이 필요한 작업에게 적절한 응답 제공을 해준다. 또한, CPU, 입출력 장치 등의 시스템 자원을 고르게 효율적으로 사용할 수 있다.

 

CPU 스케줄러는 준비 상태의 프로세스 중 어떤 프로세스에게 CPU를 할당할지 말지 선택하는 역할을 한다. CPU 스케줄러가 해주는 스케줄링은 실행 상태에서 강제로 CPU를 뺏지 않는 비선점형과 강제로 빼앗는 선점형으로 구분된다.

준비 상태에서 실행 상태로 프로세스가 옮겨질 때 디스패칭이라는 과정이 수행되는데 디스패칭은 CPU의 제어권을 CPU 스케줄러에 의해 준비 큐에서 선택된 프로세스에게 넘기고 문맥교환이 이뤄져 해당 프로세스를 실행상태로 옮기는 작업을 말하며 이 작업을 수행해주는 것이 디스패처이다.

 

CPU 스케줄링이 필요한 경우에는 프로세스에게 다음과 같은 상태 변화가 있다.

 - Running -> Blocked (I/O 요청)
 - Running -> Ready (타임아웃에 의한 타이머 인터럽트)
 - Blocked -> Ready (I/O 완료 후 인터럽트)
 - Terminate

 

 

스케줄링 성능을 결정하는 기준

 

- 이용률(CPU Utilization) : 전체 시간 중 CPU가 작업하는 시간의 비율을 의미

- 처리량(Throughput) : 단위 시간 당 처리할 수 있는 프로세스의 양

- 반환 시간(Turnaround Time) : 특정 프로세스가 실행되는 시간의 양으로, 총 대기시간과 실행시간을 더함

- 대기 시간(Waiting Time) : 준비 큐에서 프로세스가 실행 상태로 오기 전까지 대기하는 시간의 양

- 응답 시간(Response Time) : 작업을 요청한 프로세스에 대해 최초로 CPU가 응답하기까지 걸리는 시간의 양. 즉, 가장 처음 CPU 버스트가 일어나기까지 걸리는 시간과 같음

 

 

CPU 스케줄링 알고리즘

 

 

실행 상태에 놓여있는 프로세스의 CPU를 강제로 빼앗는 스케줄링 알고리즘을 비선점형, 상황에 따라 CPU를 빼앗을 수 있는 선점형 스케줄링 알고리즘으로 구분된다 하였다. 

 

 

비선점형 알고리즘

 

FCFS(First Come First Served) :  준비 큐에 도착한 순서대로 CPU를 할당하는 비선점형 방식. 

 

한 번 실행되면 프로세스가 끝나야만 다음 프로세스를 실행할 수 있다. 따라서, 처리 시간이 긴 프로세스가 CPU를 앞에서 차지하면 다른 프로세스들은 계속 기다리기에 효율성이 떨어져서 콘보이 효과가 발생할 수 있다.

 

또한, 실행 중인 프로세스가 입출력 작업을 요청하는 경우 CPU가 작업하지 않고 쉬는 시간이 많아져 효율이 떨어진다.     

SJF(Shortest Job First) : 준비 큐에 있는 프로세스 중에서 실행 시간이 가장 짧은 작업부터 CPU를 할당하는 비선점형 방식. 

 

콘보이 효과를 해결할 수 있으나 현대의 운영체제에서 프로세스의 작업 시간을 예측하는 게 어렵기에 사용하기 힘들고, 짧은 작업이 계속 들어온다면 긴 작업은 끝없이 대기하는 아사 현상(starvation)이 발생해 공평성 위배가 생긴다. 에이징과 같은 방법으로 해결할 수 있지만 기준을 정하기가 애매하므로 잘 사용하지 않는다.

CPU를 잡으면 해당 CPU burst가 완료될 때가지 CPU를 선점당하지 않는 비선점형 SJF가 있고 SJF에서 더 확장하여 현재 수행중인 프로세스의 남은 CPU burst time보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗기는 선점형 SRTF(Shortest Remaining Time First) 알고리즘이 존재한다.

 

우선순위 스케줄링 : 프로세스 중요도에 따라 우선순위를 갖는데, 이러한 우선순위를 반영해 높은 우선순위를 가진 프로세스에게 먼저 CPU를 할당하는 스케줄링 알고리즘.

 

SJF 또한 일종의 우선순위 스케줄링이며, 낮은 우선순위를 가진 프로세스는 영원히 실행하지 못하여 아사 현상이 발생할 수 있다. 이 또한, 프로세스의 우선순위를 하나씩 증가시켜 에이징 방법으로 해결은 가능하다.

 

 

선점형 알고리즘

 

RR(Round Robin) : 프로세스가 할당받은 동일한 크기의 시간(타임 슬라이스) 동안 작업을 하다가 작업을 완료하지 못하면 준비 큐의 맨 뒤로 가서 자기 차례를 기다리는 선점형 방식. 

 

프로세스들이 작업을 완료할 때까지 계속 순환하면서 실행되기에 콘보이 효과는 완화시킬 수 있다.

 

문맥 교환에 따른 추가 시간을 고려하여 타임 슬라이스를 적절히 설정해야 한다. 타임 슬라이스가 너무 크다면 FCFS와 다름없을 것이고, 너무 작다면 문맥 교환 오버헤드가 커져 비효율적이다. 평균 반환 시간(대기+실행시간)은 길지만 응답시간은 짧다. CPU brust time이 짧은 것과 긴 프로세스가 섞여있을 때 효율적이다.

 

다단계 큐 스케줄링 : 우선순위에 따라 준비 큐를 여러 개 사용하는 방식으로 프로세스는 운영체제로부터 부여받은 우선순위에 따라 해당 우선순위의 큐에 삽입. 라운드 로빈 방식으로 운영되는 큐이므로 선점형 알고리즘이다. 

 

 

고정형 우선순위로 우선순위가 높은 프로세스 때문에 우선순위가 낮은 프로세스의 작업이 지속적으로 연기되는 아사 현상 문제가 생길 수 있다.

 

다단계 피드백 큐 스케줄링 : 우선순위가 낮은 프로세스에 불리한 다단계 큐 스케줄링의 문제점을 보완한 스케줄링 알고리즘이다.

 

 

CPU를 사용하고 난 프로세스의 우선순위가 낮아지고 원래의 큐로 되돌아가지 않고, 우선순위가 하나 낮은 큐의 끝으로 들어간다. 우선순위에 따라 타임 슬라이스의 크기가 다르고(위에서 아래로 갈수록 커짐), 변동형 우선순위 알고리즘이며 일반적으로 사용하는 방식이다.

 

공평성 문제를 해결하기 위해 우선순위가 가장 낮은 큐에서의 타임 슬라이스는 FCFS 스케줄링과 같은 방식으로 해당 큐에 있는 프로세스에 CPU가 할당되면 완료될 때까지 다음 프로세스를 실행시킬 수 없다.

 

알고리즘 평가 방식

 

- Queueing model : CPU를 쓰고자하는 요청들이 큐에 도착하는데, 얼마나 빠른 빈도로 도착하는지에 대한 arrival rate와 CPU의 처리율에 관한 service rate를 통해 확률분포로 각 perfomance index(처리량, 대기시간) 값을 계산한다.

- 구현 및 성능 측정 : 실제 시스템에 알고리즘을 구현하여 실제 작업에 대해서 성능을 측정하고 비교한다.

- 시뮬레이션 : 알고리즘을 모의 프로그램으로 작성 후 주어진 작업(trace)에 대해서 입력으로 하여 결과를 비교한다.