3.4 CPU 스케줄링 알고리즘

CPU 스케줄링

준비큐에 있는 프로세스에 대해서 CPU를 할당하는 방법입니다. 크게 다섯가지가 있는데요. FCFS, SJF, SRF, Priority Scheduling, 그리고 Round Robin이 있습니다.

• 준비 큐에 있는 프로세스에 대해 CPU 할당하는 방법
• 선점 vs 비선점
• 비선점
  FCFS
  SJF : 짧은 프로세스부터
• 선점 스케줄링
  SRT : 최단 잔여시간을 우선
  RR: 모든 프로세스가 같은 우선순위
  -> TIME slice, 타임 컨텀 : time slice가 심하게 크다면 FCFS와 다를게 없다 time slice가 너무 작다면 불필요한 context switch가 많이 일어난다.

3.4.1 비선점형 방식

프로세스가 스스로 CPU 소유권을 포기하는 방식

• 강제로 프로세스 중지 X
• 컨텍스트 스위치으로 인한 부하가 적음

FCFS (First Come, First Served)

가장 먼저 온 것을 가장 먼저 처리

• 길게 수행되는 프로세스로 '준비 큐에서 오래 기다리는 현상(convoy effect)'이 발생한다는 단점

SJF (Shortest Job First)

실행 시간이 가장 짧은 프로세스부터 실행

• 긴 시간을 가진 프로세스가 실행되지 않는 현상(starvation) 발생
• 평균 대기 시간이 가장 짧음
• 실제로 실행 시간을 알 수 없기 때문에 과거의 실행했던 시간을 토대로 추측해서 사용

우선순위

우선순위가 높은 프로세스를 먼저 실행

• 우선순위 정하는 방식

  내부적 - 시간 제한, 메모리 요구량, 열린 파일의 수 등을 확인하여 종합적으로 측정
  외부적 - 운영체제 스스로 정하는게 아니라 바깥에 이미 설정된 기준을 따르는 것

• 선점방식과 비선점 방식 두 방법 모두 가능
• 우선순위 알고리즘 문제 starvation 해결 방법
  : 오래된 작업일수록 '우선순위를 높이는 방법(aging)'을 통해 단점 보완

3.4.2 선점형 방식

사용하고 있는 프로세스를 알고리즘에 의해 중단시켜 버리고 강제로 다른 프로세스에 CPU 소유권을 할당하는 방식

라운드 로빈 (RR, Round Roubin)

각 프로세스에 동일한 할당 시간을 주고 그 시간 안에 끝나지 않으면 다시 준비 큐의 뒤로 가는 알고리즘

• 현대 컴퓨터가 쓰는 우선순위 스케줄링
• 할당 시간이 너무 크면 FCFS가 되고 짧으면 컨텍스트 스위칭이 잦아져 오버헤드, 즉 비용이 커짐
• 전체 작업 시간은 길어지지만 평균 응답 시간은 짧아짐
• 로드밸런서에서 트래픽 분산 알고리즘으로도 사용됨

오버헤드

어떤 처리를 하기 위해 들어가는 간접적인 처리 시간, 메모리 등

SRF (Shortest Remaining Time First)

프로세스의 남은 수행 시간이 짧은 순서에 따라 CPU 소유권 할당

• 중간에 더 짧은 작업이 들어오면 수행하던 프로세스를 중지하고 해당 프로세스를 수행하는 알고리즘

다단계 큐

우선순위에 따른 준비 큐를 여러 개 사용하고, 큐마다 다른 스케줄링 알고리즘을 적용

• 스케줄링 부담이 적지만 유연성이 떨어짐

참고

• 면접을 위한 CS 전공지식 노트(2022, 주홍철)