CPU 스케줄링

• CPU 스케줄러는 멀티 프로그램 운영체제의 기본이다.

• CPU 이용률을 최대화 하기 위해 멀티 프로그래밍이 필요하고, 이때 CPU core가 한개라면 한번에 하나의 프로세스만 실행 가능하기 때문에 CPU 스케줄링이 필요하다. → 다수의 작업을 수행하기 위해!

• 어떤 프로세스에 CPU를 할당할지 결정하는 작업이 CPU 스케줄링이다.

CPU 스케줄러(CPU Scheduler)

• CPU 스케줄러는 메모리에 있는 프로세스들 중 어떤 프로세스를 실행할지 선택하고 CPU를 할당해주는 역할을 한다. (마치 식당매니저와 같은 역할)

• CPU 스케줄러는 프로세스들이 다음 같은 상황에 있을 때 스케줄링을 결정한다.



1. 한 프로세스가 실행 상태에서 대기 상태로 전환될 때 (I/O 발생)
2. 프로세스가 실행 상태에서 준비 완료 상태로 전환될 때 (인터럽트 발생)
3. 프로세스가 대기 상태에서 준비 완료 상태로 전환될 때 (I/O 종료)
4. 프로세스가 종료할 때

• 비선점 스케줄링(nonpreemptive)하에서는, 일단 CPU가 한 프로세스에 할당되면 프로세스가 종료하든지, 또는 대기 상태로 전환해 CPU를 방출할 때까지 점유한다. 

• 선점 스케줄링(preemptive)은 시분할 시스템에서 타임 슬라이스가 소진되었거나, 인터럽트나 시스템 호출 종료시에 더 높은 우선 순위 프로세스가 발생 되었음을 알았을 때, 현재 실행중인 프로세스로부터 강제로 CPU를 회수하는 것을 말한다.

선점 및 비선점 스케줄링

CPU 스케줄링 평가 기준(선택의 기준)

1. CPU 이용률(CPU utilization)
• 시간당 CPU를 사용한 시간의 비율
• 프로세서를 실행 상태로 항상 유지하려고 해야 한다.

2. 처리율(Throughput)
• 시간당 CPU가 처리한 작업의 비율
• 단위 시간당 완료되는 작업 수가 많도록 해야 한다.

3. 반환시간(Turnaround Time)
• 프로세스가 생성된 후 종료되어 사용하던 자원을 모두 반환하는 데까지 걸리는 시간
• 작업이 준비 큐(ready queue)에서 기다린 시간부터 CPU에서 실행된 시간, I/O 작업 시간의 합이다.

4. 대기시간(Waiting Time)
• 준비 큐에서 기다린 시간의 총합
• 대기열에 들어와 CPU를 할당받기 까지 기다린 시간

5. 응답시간(Response Time)
• 준비 큐에 도착한 후 첫 번째 출력 또는 반응이 나올 때까지 걸리는 시간
• 사용자의 요구에 얼마 만에 반응하는지를 나타내는 중요한 지표

• CPU 알고리즘의 효율성을 평가할 때 사용률과 처리량을 계산하기가 어렵기 때문에 주로 대기 시간, 응답 시간, 반환 시간을 계산한다.

• 스케줄링 알고리즘의 성능을 비교할 때는 주로 평균 대기 시간을 본다.
• 평균 대기 시간 = 모든 프로세스 대기 시간의 합 / 프로세스의 수

비선점형 스케줄링

1. FCFS(first come first served) 스케줄링

• 준비 큐에 도착한 순서대로 프로세스에 CPU를 할당해주는 방식이다. (영화관 줄서기 처럼)

• 작성이 간단하고 이해하기 쉽다.

• 모든 프로세스의 우선순위가 동일하다. Starvation 이슈가 발생하지 않는다.

• Convoy Effect(호위 효과)가 발생할 수 있다.
• 소요 시간이 긴 프로세스가 먼저 도달할 경우 다른 프로세스가 하염없이 기다려서 효율성이 낮아진다.
• 실행 시간이 짧은 작업이어도 뒤로 가면 대기 시간이 길어진다.

• 평균 대기 시간(Average Waiting Time)이 길어질 수 있다.

• 응답 시간(Response Time)이 길어질 수 있다.

• 반환 시간(Turnaround Time) 면에서는 좋을 수 있다.

2. SJF(Shortest-Job-First) 스케줄링

• 준비 큐에 있는 프로세스 중 실행 시간이 가장 짧은 작업부터 CPU를 할당하는 방식

• 시간이 오래 걸리는 작업이 앞에 있고 간단한 작업이 뒤에 있으면 그 순서를 바꾸어 실행한다.

• 콘보이 효과를 완화하여 시스템의 효율성을 높인다.

• 큰 작업으로 인해 작은 작업이 지연되는 FCFS 보다 SJF 스케줄링은 평균 대기 시간을 줄일 수 있어 효율성이 높아진다.

• 현대의 운영체제에서는 프로세스의 작업 길이를 추정하는 것이 어려워서 SJF 스케줄링 사용이 힘들다.

• 공평성을 위배한다 → 작은 작업만 먼저 실행 → 큰 작업은 계속 밀려 → 기아 현상이 발생할 수 있다. (이런 문제들로 사용되지 않는다.)

3. HRN 스케줄링(Highest Response ratio Next)

• SJF 스케줄링에서 발생할 수 있는 기아 현상을 해결하기 위해 만들어진 알고리즘

• 최고 응답률 우선 스케줄링이라고도 한다.

• SJF는 프로세스 실행 시간이 판단 기준이라 적은 시간을 사용하는 프로세스에게 우선권이 주어지지만 HRN은 대기 시간과, 실행 시간을 모두 고려하여 스케줄링을 한다.
우선 순위 = (대기 시간 + CPU 사용 시간) / CPU 사용 시간

• 우선 순위 정할 때 대기시간을 고려함으로써 기아 현상을 완화한다.

• 그러나 여전히 공평성이 위배되어 많이 사용되지 않는다.

선점형 스케줄링

1. Round Robin(RR) 스케줄링

• 각각의 프로세스에 동일한 CPU 할당 시간을 부여해서 해당 시간 동안만 CPU를 이용하게 한다.

• 할당 시간 내에 처리를 완료하지 못하면 프로세스는 Ready Queue의 제일 뒤에 삽입되어 기다려야 하고, 다음 프로세스로 넘어가므로 선점형 방식이다.

• FCFS와 비슷한데 차이점은 프로세스마다 CPU를 사용할 수 있는 최대 시간인 타임 슬라이스가 있다는 것이다.

• 우선순위가 적용되지 않는 가장 단순한 선점형 방식이다.

• 타임 슬라이스가 큰 경우 마치 FCFS처럼 작동한다.

• 타임 슬라이스가 작은 경우 시스템의 전반적인 성능이 떨어진다. 문맥 교환 하는데도 시간이 걸리기 때문에 잦은 문맥 교환에 시간을 낭비하여 실제 작업을 제대로 처리하지 못하는 문제가 발생한다.

• 타임 슬라이스는 되도록 작게 설정하되 문맥 교환에 걸리는 시간을 고려해 적당한 크기로 설정해야 한다. e.g) 유닉스의 타임 슬라이스는 대략 100밀리초

2. SRT(Shortest Remaining Time)

• SJF와 라운드 로빈을 혼합한 방식

• 기본적으로 라운드 로빈 방식이지만 CPU를 할당 받을 프로세스를 선택할 때 남아 있는 작업 시간이 적은 프로세스를 선택한다.

• SJF와 비교했을 때 평균 대기 시간이 짧아지지만 프로세스의 남은 시간을 주기적으로 계산하고 문맥 교환이 추가적으로 필요하기 때문에 훨씬 효율적이라고 할 수 없다.

• 또한 운영체제가 프로세스의 종료 시간을 예측하기 어렵고 기아 현상이 발생하기 때문에 잘 사용하지 않는다.

3. Multilevel Queue (다단계 큐) 스케줄링

• 우선순위에 따라 준비 큐를 여러 개 사용하는 방식이다.

• 프로세스는 운영체제로부터 부여 받은 우선순위에 따라 해당 우선순위의 큐에 삽입된다.
• 커널 프로세스 > 일반 프로세스 처럼 중요도에 따라 순서가 정해진다.
• 각각의 큐 사이에서 프로세스들이 이동할 수 없다.

• 각각의 큐는 각자의 스케줄링 알고리즘을 가지고 있다.

• 프로세스의 우선순위와 작업 형태를 고려해 스케줄링을 선택할 수 있다.

• 일반적으로 Foreground 프로세스들은 Round Robin 방식을 사용하고, Background 프로세스는 FCFS를 사용한다.

• 보통 CPU 시간의 80%는 Foreground의 RR, 20%는 Background의 FCFS에 할당된다.

• 우선 순위가 낮은 큐들이 실행 못하는 것을 방지하고자 큐마다 다른 타임슬라이스를 설정해 준다. 우선 순위가 높은 큐에는 작은 타임슬라이스를, 낮은 큐에는 큰 타임슬라이스를 할당한다.

• 상위 큐 작업이 끝나기 전까지 하위 큐의 프로세스는 작업이 실행될 수 없다. 우선순위 낮은 애는 계속 기다리게 된다. → 기아(Starvation) 문제 발생

4. Multilevel Feedback Queue (다단계 피드백 큐) 스케줄링

• 우선순위가 낮은 프로세스에 불리한 다단계 큐 스케줄링의 문제점을 보완한 방식이다.

• 다단계 큐와 기본적인 형태가 같다 → 우선순위를 가진 여러개의 큐가 있다.

• 다단계 큐는 각 큐마다 라운드 로빈 방식을 사용, 우선순위에는 변화가 없지만

• 다단계 피드백 큐는 CPU를 사용하고 난 프로세스의 우선 순위가 낮아진다.
• CPU 사용하고 난 프로세스는 원래의 큐 자리로 돌아가지 않고 우선순위가 하나 낮은 큐의 맨끝에 삽입된다.
• 즉, 각 큐 간에 프로세스들이 이동할 수 있다.
• 따라서 우선순위가 낮은 프로세스의 실행이 연기되는 문제(기아현상)을 완화한다.

• 다단계 큐와 동일하게 각 큐마다 타임 슬라이스의 크기를 다르게 설정한다.
• 우선순위가 낮은 큐일수록 타임 슬라이스 크게 (어렵게 본인 기회가 왔을 때 작업을 모두 완료할 수 있도록)
• 마지막 큐는 무한대의 타임 슬라이스

• 현재 운영체제가 CPU스케줄링을 위해 일반적으로 사용하는 방식