Scheduling

운영체제가 프로세스를 프로세서에 할당하는 것을 디스패치(Dispatch)라고 한다. (이때 프로세스 상태가 ready 에서 running 으로 바뀐다.) 그리고 운영체제가 레디 큐(Ready queue)에 있는 프로세스들 중에서 어떤 프로세스를 디스패치할것인가 정하는 것이 프로세스 스케줄링이다.

스케줄링의 목적으 I/O 대기, Memory stall처럼 CPU 유휴 시간을 최소화 시켜 CPU 자원 활요을 극대화 하기 위함이다.

Memory stall : 프로세서가 메모리에 접근할 때, 데이터가 사용 가능할 때까지 많은 시간이 소모된다.(ex: 컨텍스트 스위칭)

스케줄링 알고리즘 평가 기준

• Burst time : 수행시간
• CPU utilization : CPU 사용량
• throughput : 단위 시간 당 끝마친 프로세스의 수
• Tunrnaround time : 하나의 프로세스가 레디 큐에서 대기한 시간부터 작업을 마칠 때까지 걸리는 시간
• Wating time : 프로세스가 레디 큐에서 대기한 시간
• Response time : 프로세스가 처음으로 CPU를 할당 받기까지 걸린 시간

선점(Preemptive) 과 비선점(Non-preemptive)

선점(Preemptive) : 선점 스케줄링은 운영체제가 강제로 프로세스의 사용권을 통제하는 방식

비선점(Non-preemptive) : 비선점 스케줄링은 프로세스가 스스로 다음 프로세스에게 자리를 넘겨주는 방식

즉 선점 스케줄링 방식에서는 CPU에 프로세스가 할당되어 있을 때도 운영체제가 개입해 다른 프로세스에게 CPU 를 할당할 수 있다.

FCFS(First-Come, First-Served)

먼저 들어온 프로세스를 먼저 프로세서에 할당하는 방식으로 Queue의 FIFO와 동일하다. 구현이 쉬워서 간단한 시스템에 자주 사용되고 프로세스 처리 순서에 따라 성능이 크게 달라질 수 있다.

먼저 온 프로세스가 끝날 떄까지 운영체제가 개입하지 않는 비선점 스케줄링방식이다.

장점

• 스케줄링의 구현이 쉽다.
• Ready Queue에 있는 모든 프로세스가 실행될 수 있으므로 Starvation이 없다.
• 프로세스가 지속적으로 프로세스를 처리하므로 처리율이 높다.

단점

• 비선점식이라 대화식 프로세스에는 부적합하다.
• 수행 시간이 큰 프로세스가 먼저 들어오면 그 뒤에 들어온 프로세스들이 불필요하게 오랜 시간을 기다리게 되는 콘보이효과(Convoy effect)가 발생한다.

SJF(Shortest Job First)

프로세스의 수행 시간이 짧은 순서에 따라 프로세서에 할당한다. FCFS의 방법과는 같지만 실행 시간이 작은 순서대로 우선순위 큐를 이용한다.

버스트 시간이 짧은 프로세스가 끝날 때까지 운영체제가 개입하지 않는 비선점 스케줄링방식이다.

장점

• 항상 실행 시간이 짧은 작업을 가장 먼저 실행하므로 평균 대기시간이 가장 짧다.
• FCFS에서 발생하는 콘보이 효과를 해결할 수 있다.

단점

• 버스트 시간이 큰 프로세스는 계속 뒤로 밀려나는 기아(Starvation)현상이 발생한다.
• 최적 알고리즘이지만 수행 시간을 정확히 알 수 없다.(앞서 처리한 프로세스들의 기록을 보고 추측)

SRF(Shortest Remaining Time First)

프로세스의 남은 수행 시간이 짧은 순서에 따라 프로세서에 할당한다.

수행 중 다른 프로세스보다 남은 수행 시간이 적어지면 운영체제가 개입해 자리르 바꾸는 선점 스케줄링방식이다.

장점

• SJF에서 발생하는 기아 문제를 해결할 수 있다.
• 대화형 운영체제에 유용하다.

단점

• 프로세스 생성 시 총 실행 시간 추정 작업이 필요하다.
• 잦은 선점으로 컨텍스트 스위칭이 자주 일어나 오버헤드가 증가한다.
• 실행 시간이 긴 프로세스들의 평균 응답 시간이 길어진다.

Priority Scheduling

특정 기준으로 프로세스에게 우선순위를 부여해 우선순위에 따라 프로세서에 할당한다.

프로세스를 에이징(Aging)해서 오래 대기한 프로세스의 우선순위를 높이는 방식으로 사용된다. SRF의 경우 남은 수행 시간을 기준으로 우선순위를 부여한다고 할 수 있다.

다른 스케줄링 알고리즘과 결합해 사용할 수 있으므로 선점, 비선점모두 가능하다.

장점

• 각 프로세스의 상대적 중요도를 명시할 수 있다.
• 실시간 시스템에 유리하다.

단점

• 높은 우선순위 프로세스가 계속 오면 우선순위가 낮은 프로세스는 기아현상을 겪을 수 있다.

RR(Round Robin)

일정 시간 할당량(Time quantum)단위로 여러 프로세스를 번갈아가며 프로세서에 할당한다.

시스템의 time-sharing과 같은 방식으로 반응성이 좋다. 주로 우선순위 스케줄링(Priority Scheduling)과 결합해 프로세스의 시간 할당량을 조 절하는 방식으로 활용한다.

시간 할당량에 따라 운영체제가 계속 개입하는 선점 스케줄링 방식이다.

장점

• 모든 프로세스가 공정하게 시간을 할당받기에 기아현상이 발생하지 않는다.
• 프로세스 최악의 응답시간을 아는데 용이하다.

단점

• 하드웨어 타이머가 필요하다.
• 작업 시간 할당을 너무 짧게 하면 컨텍스트 스위칭이 자주 일어나 오버헤드가 일어난다.

출처:

https://parksb.github.io/ [공룡책으로 정리하는 운영체제]

https://www.crocus.co.kr/1375 [Crocus]