OS 운영체제: 스케줄링(Scheduling)

1. 스케줄링이란?

2. 스케줄링의 목표

3. 스케줄링의 종류와 알고리즘

4. 스케줄링의 기준(Scheduling Criteria)

CPU스케줄링이란?

CPU를 프로세스에게 효율적이고, 공정하게 사용하기 위해 우선순위를 배정하는 알고리즘, 방법을 의미합니다.

(Ready queue에 있는 프로세스를 스케줄링하고 dispatch 하는 것)

 

스케줄링의 목표

1. Batch System: 가능한 많은 일을 처리하는 것(throughput이 중요)

2.Interactive System: 빠른 응담과 적은 대기

3.Realtime System: 기한(Deadline) 맞추기

스케줄링의 종류와 알고리즘

1. 선점 스케줄링(Preemptive Scheduling)

OS가 CPU의 사용권을 선점하여 특정 알고리즘에 따라 각 프로세스에게 CPU 분배하거나 강제로 회수할 수 있는 방식입니다.

 

장점: 빠른 응답, 시분할 시스템에 적합

단점: 오버헤드 발생(Context Switching)

#오버헤드란 어떤 처리를 위해 사용되는 간접적인 시간, 메모리 등을 말함.

 

Round Robin

각 프로세스가 같은 크기의 CPU 시간을 할당받는 순환 할당 방식이다. RR은 할당 시간이 중요하다. 그 이유는 할당 시간이 너무 크면 FCFS에 가까워지고, 너무 작으면 잦은 문맥 교환 때문에 오버헤드가 발생한다.

 

SRT(Short Remaining Time)

짧은 시간 순서대로 프로세스를 선택하는 방식이다. 남은 처리 시간이 더 짧은 프로세스가 Ready queue에 들어오면 그 프로세스가 바로 선점된다. 새로운 프로세스가 도착할 때마다 스케줄링을 다시 하기 때문에 CPU 사용시간을 측정할 수 없다.

 

Multi Level Queue(다단계 큐)

Ready queue를 여러 개 사용하는 기법으로  각각의 큐는 자신의 스케줄링 알고리즘을 수행하며, 큐와 큐 사이에도 우선순위를 부여한다.

 

Multi Level Feed Queue(다단계 피드백 큐)

여러 개의 큐를 두고 큐마다 다른 시간 할당량을 부여하는 방식이다. 프로세스들이 큐를 이동할 수 있으며, 짧은 작업이 유리하고, 입출력 작업에 우선권을 부여한다.

 

2. 비선점 스케줄링(Non-Preemptive Scheduling)

OS가 CPU 사용권을 선점하지 않아 프로세스가 자율적으로 반납하도록 하는 방식입니다. 따라서 어떤 프로세스가 CPU를 선점하면 그 프로세스의 작업이 완료될 때까지 다른 프로세스들은 기다려야 합니다.

 

장점: 응답시간 예상 가능, 공정한 처리

단점: 짧은 작업도 긴 대기 발생 (호위 효과 convoy effect)

 

FCFS(First Come First Served)

도착한 순서대로 처리하는 방식이다. 일괄 처리 시스템에 적합하여 Batch 작업에 주로 사용된다.

 

SJF(Shortest Job First)

Ready queue에서 가장 짧은 소요시간의 프로세스를 실행하는 방식이다. 평균 대기 시간을 감소시키지만 긴 프로세스가 ㅉ랍은 프로세스에게 계속 작업 순위가 밀려 실행되지 못하는 기아 현상(Starvation)이 발생한다.

 

Priority(우선순위)

우선순위가 가장 높은 프로세스에게 CPU를 할당하는 방식이다. 선점형 방식으로는 우선순위가 더 높은 프로세스가 도착하면 실행중이던 프로세스를 멈추고 CPU를 선점하고, 비선점형 방식은 더 높은 프로세스가 도착하면 Ready queue의 head에 넣는다. 

문제점으로는 우선순위를 동적으로 부여할 경우 구현이 복잡하고 오버헤드가 많으며, 무기한 봉쇄나 기아 현상이 발생한다. 따라서 aging 방법을 통해 우선순위가 낮은 경우에도 대기시간이 길면 우선순위를 높이는 방식으로 해결한다.  

 

Deadline(기한부)

작업을 명시된 시간이나 기한 내에 완료하도록 하는 방식이다. 

 

HRN(Highest Response Next)

긴 작업과 짧은 작업의 공정성을 고려한 방식이다. 수행시간과 대기 시간을 모두 고려해 우선순위를 정한다. SJF의 단점을 보완하여 짧은 작업이나 대기시간이 긴 작업은 우선순위를 높여 기아 현상을 방지했다.

HRN 우선순위 공식 = (대기시간 + 처리시간) / 처리시간

 

스케줄링의 기준(Scheduling Criteria)

//system 성능 측면

1. CPU utilization(CPU 사용률)

CPU를 얼마나 바쁘게 사용하는가?

 

2. Throughtput(처리량)

단위시간당 처리하는 일의 양(instructions per second)

(네트워크에서는 단위 시간당 전송한 양)

 

//프로세스 성능 측면

3. Turnaround time

어떤 일을 수행하는 데 걸린 시간

 

4. Waiting time

프로세스가 Ready queue에서 대기한 시간

 

5. Response time

어떤 요청을 했을 때 시스템이 응답하는 데 걸리는 시간

 

결론, CPU utilization & Throughput은 클수록 좋고 나머지 time들은 작을 수록 좋음