3.4 CPU 스케줄링 알고리즘

'면접을 위한 CS 전공지식 노트' 책을 보며 공부한 내용입니다.

 

CPU 스케줄링 알고리즘이 어떤 프로그램에 CPU 소유권을 줄지 결정한다.

이 알고리즘들은 CPU 이용률은 높게, 주어진 시간에 많은 일을 하게, ready queue에 있는 프로세스는 적게, 응답 시간은 짧게 설정하는 것을 목표로 한다.

 

비선점형

 

프로세스가 스스로 CPU 소유권을 포기하지 않으면 다른 프로세스에게 CPU 소유권이 넘어가지 않는다. 따라서 컨텍스트 스위칭으로 인한 부하가 적다.

• FCFS(First Come, First Serve): 가장 먼저 온 것을 먼저 처리한다. => 길게 수행되는 프로세스 때문에 ready queue에서 오래 기다릴수도 있다.
• SJF(Shortest Job First): 실행 시간이 가장 짧은 프로세스를 가장 먼저 실행하는 알고리즘이다. 긴 시간을 가진 프로세스가 실행되지 않는 현상인 starvation이 일어나며 평균 대기 시간이 가장 짧다. 
  • 하지만, 실제로는 실행 시간을 알 수 없어서 과거 실행 시간을 토대로 추측해서 사용한다.
• Priority: 기존 SJF 스케줄링에서 starvation 문제가 일어나는 것을 보완한 알고리즘이다. SJF와 우선 순위를 말하는 것만이 아니라 FCFS를 활용해서 만들기도 하며, 선점형, 비선점형적인 Priority 스케줄링 알고리즘을 말하기도 한다.

 

선점형

 

현대 운영체제가 쓰는 방식이다. 지금 사용하고 있는 프로세스를 알고리즘에 의해 중단시켜버리고, 강제로 다른 프로세스에게 CPU 소유권을 할당시키는 것이 가능하다.

• Round Robin: 현대 운영체제가 사용하는 알고리즘이다. 각 프로세스는 동일한 시간을 할당받고 그 시간 안에 동작이 끝나지 않으면 다시 ready queue의 뒤로 가는 알고리즘이다.
  • 할당 시간이 너무 크면 FCFS가 되고, 짧으면 컨텍스트 스위칭이 잦아져 오버헤드가 커진다. 
  • 일반적으로 전체 작업 시간은 길어지지만, 응답 시간은 빨라진다.
• SRTF(Shortest Remaining Time First): SJF는 중간에 실행 시간이 더 짧은 작업이 들어와도 하던 작업을 다 끝낸 후에 다음 작업을 수행한다. 하지만 SRTF는 중간에 더 짧은 작업이 들어오면 하던 작업을 멈추고 해당 프로세스를 수행한다. 
• 다단계 큐: 우선 순위에 따른 ready queue를 여러개 사용하는 알고리즘이다. 큐마다 다른 스케줄링 알고리즘을 적용한다. => 큐간 이동이 안되므로 스케줄링 부담이 적지만, 유연성이 떨어진다.