[CS스터디] CPU 스케줄러

--목차--

CPU 스케줄러

--------

 

1. CPU 스케줄러

Ready Queue에 있는 프로세스 대상으로 스케줄링을 진행함.

 

 

 

1) FCFS(First Come First Served)

ㄱ. 정의

먼저 온 순서대로 처리.

 

ㄴ. 목적

도착한 순서에 따라 처리하기 때문에 반응형보다 배치형(일괄처리형) 시스템에 적합하다.

 

ㄷ. 특징

비선점형(Non-Preemptive) 스케줄링

CPU burst가 완료될 때까지 CPU를 반환하지 않는다.(할당된 CPU가 반환될 때만 스케줄링)

오버헤드가 낮다.

 

ㄹ. 기타 정보

• 문제점
  • convoy effect(소요시간이 긴 프로세스가 먼저 도달해 효율성을 낮추는 현상 발생)
  • 한번에 하나의 프로세스만 처리해서 프로세스가 병렬처리되는 현대 운영체제에는 맞지 않음.
    

 

 

 

2) SJF(Shortest Job First)

ㄱ. 정의

다른 프로세스가 먼저 도착했어도 CPU burst time이 짧은 프로세스에게 선할당.

 

ㄴ. 목적

평균 대기 시간에 있어 최적의 알고리즘.

 

ㄷ. 특징

비선점형(Non-Preemptive) 스케줄링

 

ㄹ. 기타 정보

• 문제점
  • Starvation(효율성을 추구하다보니 CPU 사용량이 낮은 job을 선호해 사용시간이 긴 프로세스는 차별받아 프로세스를 할당받지 못한다.)
  • 프로세스의 실행 시간을 예측하는 것이 어려움. (해결방안으로 이전 Burst Time의 지수적 평균으로 간주하여 예측.)
  • 프로세스의 시간을 기준으로 계속 정렬하기 때문에 자원낭비가 발생함.

 

 

 

3) HRN(Highest Response Ratio Next)

ㄱ. 정의

CPU의 사용 시간과 기다린 시간을 고려하여 스케줄링 우선순위를 정하는 방법

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

 

ㄴ. 목적

SJF에서 Starvation현상 해결 위함.

 

ㄷ. 특징

에이징 기법(대기시간이 길수록 우선순위 높아지는 기법) 사용.

비선점형 스케줄링

 

ㄹ. 기타 정보

• 문제점
  • 공정성이 위반되고 사용되기 어렵다.

 

 

 

 

 

4) SRT(Shortest Remaining Time First)

ㄱ. 정의

새로운 프로세스가 도착할 때마다 새로운 스케줄링 진행

 

ㄴ. 목적

시분할 시스템에 유용. (가장 짧은 시간이 소요된다고 판단하는 프로세스를 먼저 수행됨.)

 

ㄷ. 특징

SJF의 선점형(Preemptive) 스케줄링

(SRT(실행 중인 프로세스 선점 가능), SJF(한 번 작업의 처리가 시작되면 완료될 때까지 계속 실행))

현재 수행중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 뺏긴다.

 

ㄹ. 기타 정보

• 문제점
  • Starvation
  • 새 프로세스가 도착할 때마다 스케줄링을 다시해서 CPU burst time(CPU 사용시간)을 측정할 수가 없다.

 

 

 

 

4) Priority Scheduling

ㄱ. 정의

우선순위가 가장 높은 프로세스에게 CPU 할당하는 스케줄링.

(우선순위: 정수, 오름차순 순위)

 

ㄴ. 특징

선점형(Preemptive) 스케줄링

더 높은 우선순위의 프로세스가 도착하면 Ready Queue의 Head에 넣는다.

 

ㄷ. 기타 정보

• 문제점
  • Starvation
  • 무기한 봉쇄(Indefinite blocking): 실행 준비는 되어 있으나 CPU를 사용 못하는 프로세스를 CPU가 무기한 대기시키는 상태
    • 해결책
      • aging: 우선순위가 낮아도 기다리는 시간만큼 우선순위 높여주는 방법

 

 

 

5) Round Robin

ㄱ. 정의

프로세스들에게 동일한 할당 시간(time quantum)을 제공한 뒤, 할당 시간이 지나면 프로세스는 선점당하고 ready queue의 가장 뒤로 가서 줄을 서게 만드는 스케줄링.

 

ㄴ. 특징

• CPU 사용시간이 랜덤한 프로세스들이 섞여있을 경우 효율적.
• 프로젝트의 Context Save가 가능하기 때문에 해당 스케줄링 가능.
• 장점
  • Response time이 빨라짐.
    • n개의 프로세스가 ready queue에 있고 할당시간이 q(time quantum)인 경우, 각 프로세스는 q 단위로 CPU 시간의 1/n을 얻는다.
    • 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않는다.
    • 프로세스가 기다리는 시간이 CPU를 사용할 만큼 증가해 공정한 방법이라고 볼 수 있다.

 

ㄹ. 기타 정보

• 주의점
  • 설정한 time quantum이 너무 커지면 FCFS와 동일하고, 너무 작아지면 스케줄링 알고리즘의 목적에는 부합하지만 잦은 context switch로 overhead가 발생한다.

 

 

https://wonit.tistory.com/108

https://m.blog.naver.com/skout123/50156091912

https://cocoon1787.tistory.com/123

https://velog.io/@dbstjrwnekd/CPU-스케줄링-2

https://hyunah030.tistory.com/4

https://taesung1993.tistory.com/94