CPU 스케줄링 (Scheduling) 개념

단계

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

 

장기 스케줄링

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

 

중기 스케줄링

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

 

단기 스케줄링

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

목적과 기준

스케줄링의 목적

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

 

스케줄링의 기준

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

알고리즘

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

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

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

선점형 스케줄링 (Preemptive)

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

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

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

SRT(Shortest Remaining Time) 스케줄링

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

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

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

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

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

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

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

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

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

HRRN(Highest Response Ratio Nest) 스케줄링

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

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

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

Fair-Share 스케줄링

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

실시간 Realtime 스케줄링

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

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

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

RM (Rate Monotonic) 알고리즘

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

EDF (Earliest Deadline Frist) 알고리즘

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

https://chaengstory.tistory.com/26