스케줄링(Scheduling)

CPU가 처리해야 할 일은 산더미인데 주어진 자원은 한계가 있다. 따라서 한정된 자원으로 최대한의 성능을 만들어내기 위해 자원을 효율적으로 사용해야 한다.이를 위해 CPU가 스케줄링 알고리즘을 이용하여 프로세스에게 사용시간을 적절히 배정하게 된다.

스케줄링 종류

선점 스케줄링

운영체제가 현재 실행되고 있는 프로세스를 강제로 종료하고 다른 프로세스에게 우선적으로 CPU를 할당할 수 있는 방식이다.

1. Priority Scheduling(우선순위 스케줄링)

• 미리 주어진 프로세스의 우선순위에 따라 스케줄링한다.
• 우선순위가 낮은 프로세스는 할당되지 않는 기아(Starvation)현상이 발생할 수 있다.
• 시간에 따라 우선순위를 증가시키는 노화(Aging)방식을 사용하여 기아를 방지할 수 있다.

2. Round Robin(라운드로빈)

• 각 프로세스에 동일한 시간을 할당한 후 작업이 끝난 프로세스는 준비완료 큐의 마지막으로 가서 재할당을 기다리는 방식이다.
• 시간 할당량이 너무 길면 FCFS와 같아지고, 너무 짧으면 문맥 전환(Context Switching)이 자주 발생하여 성능이 저하된다.

3. Multilevel-Queue(다단계 큐)

• 준비완료 큐를 여러개의 큐로 분류하고 각각 다른 스케줄링 알고리즘을 가지고 있다.
• 각 큐 사이에서 프로세스가 이동될 수 없기 때문에 큐와 큐 사이에도 스케줄링이 필요하다.

비선점 스케줄링

다른 프로세스가 할당받은 CPU를 그 프로세스가 종료되거나 중지되기 전까지 가져올 수 없는 방식이다.

1. FCFS (First Come , First Serve)

• 선입선출, 큐에 도착한 순서대로 CPU를 할당한다.
• 긴 실행시간을 가진 프로세스가 큐의 앞에 있게 되면 나머지 프로세스들이 계속 기다리게 되는 Convoy Effect(호위효과)가 발생하여 전체 속도가 느려지게 된다.
• 먼저 도착한 프로세스의 처리시간에 따라 평균 대기시간의 편차가 크다.

2. SJF(Shorted Job First)

• 가장 짧은 실행시간을 가진 프로세스을 우선적으로 할당하는 방식이다.
• 실행시간을 예측하는것이 어렵다는 문제가 있다.
• 긴 실행기간을 가진 프로세스가 CPU를 할당받지 못하는 기아현상이 발생할 수 있다.

3. HRN (Highest Response-ratio Next)

• 우선순위를 계산하여 점유 불평등을 개선한다.
• 우선순위 = (대기시간 + 실행시간)/실행시간