[OS] CPU 스케줄링(Scheduling)

 

스케줄링(Scheduling)은 현재 실행 중인 프로세스로부터 다른 프로세스로 CPU를 넘겨주어야 할 때, 기다리고 있는 여러 프로세스 중에 누구를 선택해야 할지에 대한 방식이나 기준이다.

---

#1. 스케줄링의 단계

 

프로세스 스케줄링은 수행 단계의 따라 장기, 중기, 단기 스케줄링의 세 가지로 나뉘는데 이것은 스케줄링이 요구되는 시점을 기준으로 구분한다.

---

장기 스케줄링

어느 작업을 커널에 등록시켜 프로세스로 만들어 줄 것인가를 결정하는 것으로 작업 스케줄링(Job Scheduling)이라고도 한다. 이 단계는 요청된 일을 프로세스로 만들어 시스템에 알려진 일거리로 추가하느냐를 결정하는 것으로 다중 프로그래밍의 정도를 조절하는 역할을 한다.

중기 스케줄링

보류 상태의 프로세스들 중에서 어느 프로세스에게 메모리를 할당해 줄 것인가를 결정한다. 

단기 스케줄링

준비 상태에 있는 프로세스들 중에서 어느 프로세스에게 CPU를 할당할지를 결정하는 단계이다. 프로세스 스케줄러 또는 디스패처(Dispatcher)라 불리는 것에 의해 수행된다. 대부분의 스케줄링이 단기 스케줄링이다.

---

#2. 스케줄링의 목적과 기준

 

스케줄링의 목적

CPU를 할당받을 프로세스를 잘 골라 실행시켜줌으로써 전체적인 시스템의 성능을 높이는게 목적

---

스케줄링의 기준

• CPU 사용 효율 : 가능한 CPU가 계속 유용한 작업을 하도록 해야 한다.
• 처리율 : 시간당 완료되는 프로세스의 수
• 반환시간 : 하나의 프로세스가 제시된 시점에서 그 프로세스가 종료될 때까지 걸린 시간
• 대기시간 : 한 프로세스가 준비완료 큐에서 대기한 총 시간
• 응답시간 : 서비스를 요청한 후에 그 서비스에 대한 첫 반응이 나오기까지 걸린 시간

위 기준은 사용자 관점 (반환시간, 응답시간 등)과 시스템 관점 (CPU 사용 효율, 처리율)으로 나눌 수 있다.

---

#3. 스케줄링 알고리즘

 

스케줄링이 언제 가동되어야 할까?

• 프로세스가 실행 상태에서 대기 상태로 전환될 때 (입출력 요청)
• 프로세스가 실행 상태에서 준비 상태로 전활될 때 (시간종료와 같은 인터럽트 발생)
• 프로세스가 대기 상태에서 준비 상태로 전환될 때 (입출력의 종료)
• 프로세스가 수행을 마치고 종료될 때

---

스케줄링 기법들은 비선점(Nonpreemptive)과 선점(Preemptive) 스케줄링으로 분류한다.

비선점(Nonpreemptive) 스케줄링

비선점 스케줄링은 한 프로세스가 CPU를 할당받았을 때 CPU를 스스로 반납할 때까지 계속 사용하도록 허용하는 방식

선점(Preemptive) 스케줄링

선점 스케줄링은 cpu를 할당받아 실행 중인 프로세스로부터 CPU를 빼앗아 다른 프로세스에 할당할 수 있는 방식

---

FCFS(First Come First Service) 스케줄링

• FIFO(First in Fist out) 스케줄링이라고도 한다.
• FCFS 알고리즘은 먼저 요청한 프로세스 순으로 스케줄링한다. 
• 비선점 방식이다.

P1의 대기시간은 0ms, P2는 24-1 =23ms, P3는 27-2=25ms 이므로 평균 대기시간은 16ms이다.

만약 도착 순서가 P2, P3, P1 이면 평균 대기 시간은 2ms이다.

• FCFS의 단점은 호위 효과(convoy effect)가 발생할 수 있다는 것이다. 호위 효과란 하나의 큰 프로세스가 CPU를 양보할 때까지 다른 모든 프로세스가 기다리는 현상이다.

---

SJF(Shortest Job First) 스케줄링

• 준비 큐에서 기다리고 있는 프로세스 중에서 가장 짧은 것을 먼저 실행시켜주는 방식
• 비선점 방식이다.
• 이 기법은 처리량에 관한 한 매우 훌륭한 성능을 보이며, FCFS와 비교했을 때 전체적으로 빠른 응답
• 긴 프로세스일수록 그 편차가 커져 예측가능성은 오히려 떨어짐
• 평균 응답시간을 최소화할 수 있으나 실행 시간이 긴 프로세스는 무한 대기 현상이 발생
• 긴 프로세스의 무한 대기 가능성을 낮추는 방법으로는 기다린 시간만큼 우선순위를 높여주는 에이징(Aging) 방법을 사용해 실행 가능성을 높여준다.

평균 대기시간은 (3+16+9+0)/4 = 7ms이다. 만약 P1, P2, P3, P4 순서로 FCFS 알고리즘으로 스케줄링 하였다면 평균 대기 시간은 10.25ms이다. 

SJF 스케줄링은 각 프로세스들의 크기를 실행 전에는 정확히 알 수 없음에도 불구하고 그 크기를 실행 전에 추정해 보는 지수 평균 방법을 동원할 수 있는데 비슷한 환경에서 반복적으로 실행되는 프로세스들에 대해서는 적용할 만하다.

---

SRT(Shortest Remaining Time) 스케줄링

• SRT 스케줄링은 SJF을 선점방식으로 운영
• 준비 큐에서 완료까지 남은 CPU 요구량이 가장 짧은 것을 먼저 실행
• 실행 도중 남은 실행 시간이 더 적은 프로세스가 준비 큐에 들어올 경우 현재 실행 중인 것을 중단하고 새 프로세스에게 CPU를 할당하는 선점 방식
• 남은 실행 시간의 계산, 실행 시간이 짧은 프로세스가 자주 도착할 경우 잦은 선점으로 인한 문맥 교환이 단점

평균 대기시간은 (9+0+15+2)/4 = 6.5ms

평균 반환시간은 (17+4+24+7)/4 = 13ms

---

HRRN(Highest Response Ratio Nest) 스케줄링

• SJF와 SRT 방식의 약점인 수행 시간이 긴 프로세스의 무한 대기 현상을 방지하기 위한 기법
• 준비 큐에 있는 프로세스들 중에서 응답률이 가장 높은 프로세스에게 높은 우선순위
• 비선점 방식
• 응답률이란 프로세스의 크기 즉, CPU 요구량에 대한 대기 시간의 비율

       응답률 = (대기시간 + CPU 요구량) / CPU 요구량

• 프로세스가 기다리는 시간이 길어질수록 우선순위가 높아진다. 

---

라운드 로빈(Round-Robin) 스케줄링

• FCFS 스케줄링을 기반으로 CPU를 하당하되, 각 프로세스는 한 번에 쓸 수 있는 CPU 시간 할당량이 지나면 시간 종료 인터럽트에 의해 CPU를 뺏기게 된다.
• 선점 방식
• FCFC 기법에서처럼 한 프로세스의 CPU 독점을 막을 수 있으나 문맥 교환에 따른 오버헤드 발생
• 대화식 시스템이나 시분활 시스템에 적합한 방식

---

다단계 큐(Multi-level Queue) 스케줄링

• 다단계 큐는 정적 우선순위 (프로세스가 생성될 때 부여된 우선순위가 완료될 때까지 변하지 않는 값이 됨) 를 사용하는 스케줄링을 구현할 때 가장 적합한 자료구조이다.
• 우선순위가 낮은 하위 단계 큐의 작업은 실행 중이더라도 상위 단계 큐에 프로세스가 도착하면 CPU를 뺏기는 선점 방식이다. 
• 정적 우선순위이므로 큐들 간에 프로세스의 이동이 불가능하다.

---

다단계 피드백 큐(Multi-level Feedback Queue , MFQ) 스케줄링

• MFQ는 동적 우선순위를 기반으로 하는 선점 방식
• 우선순위가 높은 단계의 큐일수록 시간 할당량은 작도록 한다. 
• 새로운 프로세스는 최상위 단계의 준비 큐에 들어간 후 FCFS의 순서로 CPU를 할당 받아 실행되다가 크 규의 시간 할당량이 끝나면 한 단계 아래의 준비 큐에 들어감으로써 결과적으로 우선순위가 한 단계 낮아짐
• 마지막 단계에서는 더 내려갈 단계가 없으므로 라운드 로빈 방식으로 실행 됨

• MFQ 기법은 상대적으로 짧은 프로세스들이 하위 큐까지 내려가지 않도록 함으로써 비교적 높은 우선순위를 유지할 수 있도록 한다.
• 입출력 프로세스를 우대함으로써 CPU를 포함한 전체 자원들의 활용도를 높여 시스템 성능을 올림

---

Fair-Share 스케줄링

• 프로세스들의 특성이나 중요도에 따라 그룹으로 나누고 CPU 시간을 일정량 할애하는 기법
• 특정 그룹에 속한 프로세스의 과도한 CPU 사용은 그 그룹 내의 다른 프로세스들에게만 불이익을 줌
• 다른 그룹 프로세스들은 불이익을 받지 않는다.

---

#4. 실시간(Realtime) 스케줄링

 

실시간(Realtime) 시스템이란 실행될 모든 프로세스들이 정해진 시간 내에 완료되어야 하는 시스템이다.

실시간 시스템에서의 스케줄링은 모든 프로세스들이 정해진 마감시한 내에 완료되도록 해야 하는 것이 관건인데 정적과 동적 방법으로 나눌 수 있다.

정적인 방법은 프로세스들의 특징과 개수를 알 수 있는 경우에 유용한 반면 동적인 방법은 프로세스의 생성 시간이나 특성을 알 수 없는 경우에 사용된다.

---

RM (Rate Monotonic) 알고리즘

• 대표적인 정적 스케줄링 방식
• 크기와 개수가 알려진 프로세스들이 각자 주기적으로 발생되는 환경에서 사용
• 낮은 우선순위의 프로세스가 더 높은 우선순위의 프로세스가 도착할 경우 CPU를 뺏기게 되는 선점 방식
• 스케줄링 비용은 적게 들지만 새로운 프로세스가 추가되면 바로 적응하지 못하고 전체 스케줄링을 다시 해야 함

RM 스케줄링

---

EDF (Earliest Deadline Frist) 알고리즘

• 프로세스의 마감시한이 가까울수록 우선순위를 높게 부여하는 선점 방식의 동적 스케줄링
• 동적이란 새로운 프로세스가 도착할 때 바로 대응할 수 있다는 것을 의미
• 한 프로세스의 실행이 완료될 경우에는 마감 시한이 가장 임박한 것을 찾아 스케줄함.

---

 

참고 자료

• OS? Oh Yes! , 김주균 지음