3.4 CPU 스케쥴링 알고리즘

CPU 스케쥴링 알고리즘은 CPU 이용률은 높게 ,
주어진 시간에 많은 일을 하게 ,
준비 큐 (ready queue)에 있는 프로세스는 적게 ,
응답 시간을 짧게 설정하는 것을 목표로 함

 

3.4.1 비선점형 방식 (non - preemptive)

프로세스가 스스로 CPU 소유권을 포기하는 방식 , 강제로 프로세스를 중지하지 않으므로 컨텍스트 스위칭으로 인한 부하가 적음

 

FCFS (First Come , First Served)

• 가장 먼저 온 것을 가장 먼저 처리하는 알고리즘
• 준비 큐에서 오래기다리는 현상(convoy effect)이 발생하는 단점이 있음

 

SJF (Shortest Job First)

• 실행 시간이 가장 짧은 프로세스를 가장 먼저 실행하는 알고리즘
• Starvation(기아 상태) 발생할 수 있다 : 긴 시간을 요구하는 프로세스가 실행되지 않는 현상
• 평균 대기 시간이 가장 짧음
• 프로세스들의 도착시간이 다르다면 비효율적인 방법
• 실제 실행 시간을 알 수 없기 때문에 과거의 실행했던 시간을 토대로 추측해서 사용

SJF를 보완하기 위해 Shortest Time to Completion First(STCF) 가 나옴

 

우선순위

• 준비 큐에 프로세스가 도착하면, 도착한 프로세스의 우선순위와 현재 실행 중인 프로세스의 우선순위를 비교하여 우선순위가 가장 높은 프로세스에 프로세서를 할당하는 방식
• Starvation이 일어나는 현상을 보완하는 알고리즘
• 오래된 작업일수록 우선순위를 높이는 방법(align) 을 사용함

우선순위 결정법

• 내부적 우선순위 결정 : 제한 시간 , 기억장소 요청량 , 사용 파일 수 , 평균 입출력 버스트 / 평균 프로세서 버스트
  • (평균 입출력 버스트 / 평균 프로세서 버스트)가 높으면 프로세스가 CPU에서 실행되는 시간이 상대적으로 길고, 입출력 작업은 적게 필요로 한다는 의미
  • (평균 입출력 버스트 / 평균 프로세서 버스트)가 낮으면 프로세스가 입출력 작업에 더 많은 시간을 사용하며, CPU에서 실행되는 시간은 짧다는 의미
• 외부적 우선순위 결정 : 프로세스의 중요성 , 사용료를 많이 낸 사용자 , 작업을 지원하는 부서 , 정책적 요인

문제점

• 무한 정지와 Starvation이 또 발생할 수 있음 → 에이징으로 해결
• 에이징 : 매 분마다 대기 중인 프로세스의 우선순위를 1씩 증가시킴

 

3.4.2 선점형 방식 (preemptive)

현대 운영체제가 쓰는 방식

지금 사용하고 있는 프로세스를 알고리즘에 의해 중단시켜 버리고 강제로 다른 프로세스에 CPU 소유권을 할당하는 방식

 

라운드 로빈(RR , Round Robin)

• 현대 컴퓨터가 쓰는 선점형 알고리즘 스케쥴링 방법
• 각 프로세스는 동일한 할당 시간을 주고 그 시간 안에 끝나지 않으면 다시 준비 큐의 뒤로 가는 알고리즘
• 성능은 평균 CPU 소요시간에 대한 시간 간격의 길이에 따라 달라짐
  • 간격이 너무 큰 경우 FCFS 정도로 성능이 낮아짐
  • 간격이 너무 작다면 잦은 문맥 교환이 작업 수행을 방해하여 오버헤드 증가

 

SRF (Shortest Remaining Time First)

• 작업 중간에 더 짧은 작업이 들어오면 수행하던 프로세스를 중지하고 해당 프로세스를 수행하는 알고리즘
• Starvation 발생할 수 있음

 

다단계 큐

• 우선순위마다의 별도 준비 큐를 형성하여 스케줄링 하는 방법
• 프로세스의 특성에 따라 우선순위가 부여되어 한 개의 큐에 영구적으로 할당되고 각 큐는 그 성격에 맞는 스케줄링 알고리즘을 별도로 적용할 수 있음
• 항상 가장 높은 우선순위 큐의 프로세스에게 CPU를 먼저 할당해준다
• 인터럽트를 처리한 후 다시 스케줄링을 하려고 할 때 :
  • 기존 수행 중이었던 프로세스가 있는 큐보다 높은 단계의 큐에 새로운 프로세스가 하나라도 있다면 바로 그 프로세스에 CPU를 할당해주어야 한다