CPU 스케줄러

공부하면서 적는 글입니다! 정확하지 않을 수 있습니다.

CPU 스케줄러?

CPU 스케줄러는 Ready Queue에 존재하는 프로세스들을 특정한 우선순위를 기반으로 CPU를 할당받게 해주는 역할을 한다.

일단 우선순위를 따지려면 3가지의 목표를 알아봐야한다.

• CPU 활용을 최대화 하자.
• 평균 대기시간을 최소화 하자.
• 처리량을 최대화 하자.

이 목표를 따지며 생긴 여러 알고리즘이 존재한다.

FCFS(First Come First Served)

특징

• 먼저 온 프로세스를 처리해주는 방식
• 비선점형 스케줄링
  (일단 CPU를 잡으면 CPU사용을 완료 할 때까지는 반환하지 않는다.)

문제점

• convoy effect(호위효과) 발생
  호위효과란 앞의 프로세스가 실행시간이 길면 실행시간이 짧은 프로세스가 있다고 해도 뒤에서 끝날 때까지 기다리는 것을 가리키는 효과이다.

SJF(Shortest-Job- First)

특징

• 다른 프로세스가 먼저 도착했어도, CPU 사용시간이 짧은 프로세스에게 선 할당을 해준다.
• 비선점형 스케줄링

문제점

• starvation(기아현상)
  효율성을 추구하는 것은 좋지만, 특정 프로세스가 지나치게 차별을 받아선 안된다.
  SJF 스케줄링은 CPU 사용시간이 짧은 작업들을 선호하기 때문에 사용이 긴 프로세스는 잘못하다가 영원히 CPU를 할당받을 수가 없게 된다.

SRTF(Shortest Remaining Time First)

특징

• 새로운 프로세스가 도착할 때마다 새로운 스케줄링이 이루어진다.
• 선점형 스케줄링
  (현재 수행중인 프로세스의 남은 사용시간 보다 더 짧은 사용시간의 작업이 들어왔을 경우 CPU를 뺏기는 방식)

문제점

• starvation(기아현상)
  계속 더 짧은 것들이 들어오게 되면 상대적으로 긴 프로세스는 CPU를 할당받을 수 없다.
• 새로운 프로세스가 도달할 때마다 스케줄링을 다시 하기 때문에 CPU 사용시간을 측정할 수 없다.

Priority Scheduling

특징

• 우선순위가 가장 높은 프로세스에게 CPU를 할당하는 스케줄링이다.
• 우선순위는 정수로 표현하게 되고, 작은 숫자가 우선순위가 높다.

• 선점형 스케줄링 방식
  더 높은 우선순위의 프로세스가 도착하면 실행중인 프로세스를 멈추고 CPU를 선점하게 된다.

• 비선점형 스케줄링 방식
  더 높은 우선순위의 프로세스가 도착하면 Ready Queue의 Head에 넣는다. (맨 앞쪽으로 빼주는 느낌이다.)

문제점

• starvation
• 무기한 봉쇄(Indefinite blocking)
  실행준비는 되어있으나 CPU를 사용하지 못하는 프로세스를 CPU가 무기한 대기하는 상태

해결책

• aging
  아무리 우선순위가 낮은 프로세스라도 오래 기다리면 우선순위를 높여준다.

Round Robin

특징

• 현대적인 CPU 스케줄링
• 각 프로세스는 동일한 크기의 할당 시간을 갖게 된다.
• 할당 시간이 지나면 프로세스는 선점당하고 ready queue의 제일 뒤에 가서 다시 줄을 선다.
• RR은 CPU 사용시간이 랜덤한 프로세스들이 섞여 있을 때 효율적이다.
• RR이 가능한 이유는 프로세스의 context를 저장할 수 있기 때문이다.

장점

• 응답시간이 빨라진다.
  n개의 프로세스들이 각각 1/n 시간을 얻게 된다. 어떤 프로세스도 그 이상의 시간을 기다리지 않는다.
• 프로세스가 기다리는 시간이 CPU를 사용할 만큼 증가한다.
  공정한 스케줄링이라고 할 수 있다.

주의점

설정한 시간 텀이 너무 커지면 FCFS와 같아진다. 또 너무 작아지면 스케줄링 알고리즘의 목적에는 이상적이지만 잦은 context switch로 오버헤드가 발생한다.
그래서 적당한 텀을 설정하는게 중요하다.