스케줄링 알고리즘

1. FIFO

가장 단순하다!

프로세서를 요청하는 순서대로 할당해준다.

비선점 방법이다.

딱봐도 성능이 안좋아보인다 좀 더 자세히 말하면 호위효과가 발생할 여지가 있다

호위효과 : 긴 프로세스가 실행하는 동안 짧은 프로세스가 길게 대기하는 현상

 

 

2. SJF (Shortest Job First)

각 작업 중에서 실행 시간이 가장 짧은 프로세스에 할당하는 방법이다.

 

평균 대기 시간이 가장 짧지만, 긴 작업은 기아 상태가 발생할 수 있다. 

SJF에서 선점이 가능한 알고리즘을 SRTF(Shortest Remaining time first) 스케줄링이라고 한다. 

 

3. 우선순위 스케줄링

프로세스 중에 우선순위가 가장 높은 프로세스를 할당하는 스케줄링이다.

우선순위 별로 실행 큐를 다르게 설정한다.

우선순위는 제한 시간, 자원 요청량, 중요도 등 다양한 요소로 설정 가능하다.

 

순위가 높은 프로세스가 계쏙 들어오면 우선순위가 낮은 프로세스는 기아상태에 빠진다

이러한 문제는 에이징 방식을 통해 해결할 수 있다.

에이징 : 대기시간이 질어질수록 우선순위가 높아지는 방식

 

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

일정 규정 시간동안 할당하고, 시간이 지나면 인터럽트를 발생시키는 방식이다.

 

 

모든 프로세서가 균등하게 실행하기 떄문에 기아가 발생하지 않는 것이 특징이다.

 

클론 타이머가 너무 짧으면 컨텍스트 스위칭이 많이 발생하여 오버헤드가 커지고,

시간이 너무 길면 FIFO와 길어지는 문제가 발생한다.

따라서 경우에 따라 적절한 시간을 조정해야 한다.

 

5. 다단계 큐 스케줄링(MultiLevel Queue)

각 작업을 서로 다른 묶음으로 분류할 때 사용한다.

전면작업(포그라운드)와 후면 작업(백그라운드)가 분류가 가능할 떄 즉, 우선순위 별로 분할 시에 용이하다.

각 큐는 독자적인 스케줄링을 가지면서, 가장 높은 우선순위 큐부터 실행한다

6. 다단계 피드백 큐 스케줄링(MultiLevel Feedback Queue)

다단계 큐 스케줄링은 한 큐에서만 고정되어 실행한다. 즉, 다른 작업을 큐로 옮기지 않는다. 

반면, MLFQ는 프로세서 실행 시간이 너무 길면 낮은 단계 큐로 옮긴다.

 

그리하여 하래 큐로 내려갈수록, 프로세서다 거 오래 작업할 수 있도록 해서 규정 시간을 더 얻는 방식으로 동작한다.

MLFQ가 프로세서 스케줄링 중 가장 일반적인 알고리즘이다.

매우 유연하여 시스템에 맞게 구성할 수 있는 것이 장점이다.

 

7. HRN 스케줄링

가변적으로 우선순위를 계산해서 적용하는 알고리즘이다.

실행시간이 짧을수록, 대기시간이 길 수록 우선순위가 높다.

8. 다중 프로세서 스케줄링

각 프로세서에서 독자적인 큐와 스케줄링을 가지는 것을 의미한다. 

허나, 하나의 시스템에 종류가 같은 프로세서가 여러 개이면 부하 공유가 발생한다.

이것은 각 프로세서에서 서로 독립된 큐를 제공하여 방지할 수 있다. 

이렇게 하면 모든 프로세서를 프로세스에 한 번만 할당하기 떄문에 오버헤드가 적으나, 병렬성이 떨어질 수 있다.

 

병렬성을 위해 공용 준비큐를 사용해서 프로세서 큐로 가도록 스케줄링 할 수도 있다. 

공용 준비큐를 사용하는 경우도 여러 가지가 있는데, 프로세서 자신이 공용 큐에서 직접 뽑아서 스스로 스케줄링할 수도 있고,

비대칭 다중 처리(Asymmetric MultiProccessing)을 할 수도 있다.

한 프로세서가 다른 모든 프로세서 스케줄링을 지정하는 방식인 것이다.