CPU 스케줄링

스터디 Stacked-Book에서 실습과 그림으로 배우는 리눅스 구조 책을 참고하여 학습 후 정리한 글입니다.

작업 스케줄링은 준비 대기열로 가져와야 하는 프로세스를 선택하는 메커니즘 CPU 스케줄링은 다음에 실행할 프로세스를 선택하고 해당 프로세스에 CPU를 할당하는 메커니즘

CPU 스케줄링

• 다중 프로그래밍의 목적은 CPU 이용률을 최대화하는 것이다. 가능한 CPU가 항상 실행 중인 프로세스를 가지게 한다.
• 운영체제가 레디 큐(Ready queue)에 있는 프로세스들 중에서 어떤 프로세스를 디스패치할 것인가 정하는 것을 뜻한다.
• 운영체제가 프로세스를 프로세서에 할당하는 것을 디스패치라고 한다.

CPU 스케줄링 평가 항목

• CPU 이용률 : CPU를 얼마나 사용하고 있는가
• 처리량 : 단위 시간 당 완료된 프로세스의 개수
• 총 처리 시간 : 프로세스의 제출 시간과 완료 시간의 간격 (ready queue에서의 프로세스의 대기 시간 + CPU 실행 시간 + I/O 시간)
• 대기 시간 : (ready queue에서의) 프로세스의 대기 시간
• 응답 시간 : 요구한 후, 첫 응답이 나올 때 까지의 시간

CPU 이용률, 처리량을 최대화하고 총처리 시간, 대기 시간, 응답 시간을 최소화하는 것이 바람직하다.

CPU 스케줄링의 종류

비선점 스케줄링

• 이미 할당된 CPU를 다른 프로세스가 강제로 빼앗아 사용할수 없는 스케줄링 기법이다.
• 종류 : FCFS, SJF, 우선순위, HRN, 기한부 …

선점 스케줄링

• 하나의 프로세스가 CPU를 할당받아 실행하고 있을 때 우선순위가 높은 다른 프로세스가 CPU를 강제로 빼앗아 사용할 수 있는 스케줄링 기법이다.
• 선점으로 인한 오버헤드가 발생할 수 있다.
• 종류 : SRT, 선점 우선순위, RR, 다단계 큐, 다단계 피드백 큐 …

CPU 스케줄링 알고리즘

FCFS (First Come First Served)

• 먼저 들어온 프로세스를 먼저 프로세서에 할당하는 방식이다.
• Queue의 FIFO와 동일하다.
• 수행 시간이 큰 프로세스가 먼저 들어올 경우 그 뒤의 다른 프로세스들이 하나의 긴 CPU 실행 시간을 갖는 프로세스를 기다리는 상황(콘보이 효과)이 발생한다.
• 먼저 온 프로세스가 끝날 때까지 운영체제가 개입하지 않는 비선점 스케줄링 방식이다.

SJF (Shortest Job First)

• 프로세스의 수행 시간이 짧은 순서에 따라 프로세서에 할당한다.
• 수행 시간을 정확히 알 수 없다. 앞서 처리한 프로세스들의 기록을 보고 추측한다.
• 수행 시간이 큰 프로세스는 계속 뒤로 밀려나는 기아(Starvation)가 발생한다.
  • 이 문제점은 프로세스가 순서를 양보할 때마다 카운트하여 양보의 한계점까지만 양보하게 하는 에이징 기법으로 해결 가능하다.
• SJF는 비선점형 방식(SRF()) 과 선점형 방식(SRTF(Shortest Remaining Time First)) 으로 구현될 수 있다.

SRTF (Shortest Remaining Time First)

• SJF의 선점형 방식이다.
• 프로세스의 남은 수행 시간이 짧은 순서에 따라 프로세서에 할당한다.
• 수행 중 다른 프로세스보다 남은 수행 시간이 적어지면 운영체제가 개입해 자리를 바꾸는 선점 스케줄링 방식이다.

우선순위 (priority scheduling)

• 준비 큐에서 기다리는 프로세스 중 우선순위가 가장 높은 프로세스에게 제일 먼저 CPU를 할당한다.
• 우선순위 값이 작을 수록 높은 우선순위를 가지는 것으로 가정한다.
• 우선순위 결정 방식은 여러가지가 있을 수 있다.
  • CPU 버스트 시간을 우선순위 값으로 정의하면 우선 순위 스케줄링은 SJF 알고리즘과 동일한 의미를 가지게 된다.
  • 시스템 관련 중요한 작업을 수행하는 프로세스의 우선순위를 높게 부여할 수도 있다.
• 우선순위 스케줄링은 비선점형 방식과 선점형 방식으로 구현할 수 있다.
• 수행 시간이 큰 프로세스는 계속 뒤로 밀려나는 기아(Starvation)가 발생한다.
  • 이 문제점은 프로세스가 순서를 양보할 때마다 카운트하여 양보의 한계점까지만 양보하게 하는 에이징 기법으로 해결 가능하다.

RR (Round Robin)

• 일정 시간 할당량(Time quantum) 단위로 여러 프로세스를 번갈아가며 프로세서에 할당한다.
• 시스템의 time-sharing과 같은 방식이다. (앞선 스케줄링 방식과 달리 시분할 시스템의 성질을 가장 잘 활용한다.)
• 주로 우선순위 스케줄링(Priority scheduling)과 결합해 프로세스의 시간 할당량을 조절하는 방식으로 활용한다.
• 시간 할당량에 따라 운영체제가 계속 개입하는 선점 스케줄링 방식이다.

멀티레벨 큐

• 준비 큐를 여러 개로 분할해 관리하는 스케줄링 기법이다.
• 일반적으로 성격이 다른 프로세스들을 별도로 관리하고 프로세스 성격에 맞는 스케줄링 적용을 위해 준비 큐를 별도로 둔다.
  • 예를 들어 빠른 응답을 필요로 하는 대화형 작업과 그렇지 않은 작업을 별도의 큐에 세우고 대화형 작업이 기다리고 있다면 이들에게 우선적으로 CPU를 할당한다.
• 일반적으로 멀티레벨 큐에서는 대화형 작업을 담기위한 준비 큐와 계산 위주의 작업을 담기 위한 후위 큐로 분할하여 운영한다.
  • 전위큐에서는 응답시간을 짧게 하기 위해 라운드로빈 스케줄링을 사용하는 반면 계산 위주의 작업을 위한 후위큐에서는 응답 시간이 큰 의미를 가지지 않으므로 FCFS 스케줄링 기법을 사용해 문맥 교환 오버헤드를 줄인다.
• 멀티레벨 큐에서는 여러개 준비 큐에 대해 어느 큐에 CPU를 먼저 할당할지 결정하는 큐 자체에 대한 스케줄링이 필요하다.

멀티레벨 피드백 큐

• 멀티레벨 큐에 프로세스가 하나의 큐에서 다른 큐로 이동이 가능한 방식이다.
• 우선순위 스케줄링에서 에이징 기법을 멀티레벨 큐 방식으로 구현할 수 있다.
  • 우선순위가 낮은 큐에서 오래 기다리면 우선순위가 높은 큐로 이동시키는 방식