7. 스케줄링 알고리즘

알고리즘 평가 기준

 - 평균 대기 시간 : 프로세스가 준비 큐에서 대기하는 시간의 합의 평균

 - 평균 반환 시간 : 프로세스가 시작해서 끝날 때 까지 걸리는 시간의 평균

 - 처리량 : CPU가 단위 시간당 처리하는 프로세스의 개수

 등...

 

1. FCFS ( First come, First Served )

 - 먼저 도착한 스레드를 먼저 스케줄링한다. ( Queue와 같음 )

 - 비선점 알고리즘, 우선순위 없음, 일반적으로 기아 발생 없음

  -> 앞 스레드의 무한루프 등이 기아를 발생시킬 수는 있음.

 - 호위효과 (긴 스레드가 오래 사용해, 늦게 도착한 스레드가 오래 대기)등이 일어날 수 있다. 처리율 낮음.

 

2. SJF ( Shortest Job First )

 - 스레드가 도착할 때, 예상 실행시간이 가장 짧은 순으로 큐에 삽입.

 - 비선점 알고리즘, 우선순위 없음, 기아 발생 가능 ( 지속적으로 짧은게 오면, 긴 스레드는 실행기회가 없다. )

 - 평균 대기시간이 최소화 되지만, 실행시간의 예측이 현실적으로 불가능해 사용되지 않는다.

 SRTF ( Shortest Remaining Time First ) : SJF의 선점 알고리즘 버전

 

3. Round-Robin ( RR )

 - 스레드들에게 공평한 기회를 주기 위해, 큐에 대기중인 스레드들을 타임슬라이스 주기로 돌아가며 선택

 - 도착하는대로 큐에 삽입, 타임슬라이스가 지나면 큐 끝으로 이동.

 - 타임슬라이스가 짧을수록 대기시간은 줄어들지만, Context Swtiching이 잦아 오버헤드가 커진다.

 - 선점 알고리즘, 우선순위 없음, 기아 발생 없음

 타임슬라이스가 작을수록 SJF에 가깝고, 클수록 FCFS에 가깝다

 

4. Priority ( 우선순위 )

 - 우선순위에 따라 스레드를 실행시킴. 가장 높은 순위의 스레드 선택

 - 선점,비선점 둘다 가능, 우선순위 없음, 기아 발생 가능 ( Aging 기법으로 해결 가능 )

 - 높은 우선순위의 스레드일수록 대기시간이 짧음

  -> Real time OS에서 유리하다.

 

5. HRN ( Highest Response Ratio Next )

 - SJF의 기아 현상을 완화하기 위한 변형으로, 대기시간과 CPU 사용시간을 고려해 스케줄링한다.

 - 우선순위 : (대기시간 + CPU 사용시간) / CPU 사용시간

 - 비선점 알고리즘, 우선순위 있음, 기아 발생 가능성 낮음

 - 대기시간이 길수록 우선순위가 높아진다.

 

 6. MLQ / MLFQ ( Multi-Level Feedback Queue )

 - 스레드들을 N개의 우선순위 레벨로 구분한 후, 우선순위 레벨이 높은 스레드 큐를 먼저 처리한다.

 - 기아를 없애기 위해, 여러 레벨의 큐 사이에 스레드 이동이 가능하도록 설계한다.

  -> 큐에 있는 시간이 길어질수록 하나 위 레벨의 큐로 이동한다. ( Feedback )

 

 

※ 스케줄링 기법은 섞여 사용될 수 있으며, 꼭 스케줄링이 Queue만 사용되는 것은 아님.

   우선순위마다 다른 스케줄링 기법을 사용하기도 한다. ( 1~100은 이거, 101~500은 저거... 이런 느낌 )