[운영체제] CPU 스케줄링 알고리즘

✔️ CPU 스케줄링이란?

CPU를 잘 사용하기 위해 프로세스를 잘 배정하는 것이다.

CPU 스케줄러는 CPU 스케줄링 알고리즘에 따라 프로세스에서 해야 하는 일을 
스레드 단위로 CPU에 할당한다.

 

CPU 스케줄링 알고르즘

 

 

프로그램이 실행될 때는 CPU 스케줄링 알고리즘이 어떤 프로그램에 CPU 소유권을 줄 것인지 결정한다.

 

 

 

✔️ CPU 알고리즘의 조건과 목표

• 조건
  • 오버헤드 ↓
  • 이용률 ↑
  • 기아 현상 ↓

 

• 목표
  • 가능하면 많은 일을 수행. 시간(time)보단 처리량(throughtout)이 중요
  • 빠른 응답 시간. 적은 대기 시간.
  • 기한(deadline) 맞추기

 

 

 

✔️ 선점 / 비선점 스케줄링

• 선점(preemptive)
  
  • 지금 사용하고 있는 프로세스를 알고리즘에 의해 중단시켜 버리고, 다른 프로세스에 CPU 소유권을 할당하는 방식
  • 현대 운영체제가 쓰는 방식
  • 우선순위가 높은 프로세스에 빠른 응답시간 보장
  • 프로세스간 문맥교환이 자주 발생
  • 처리시간 예측 어려움
• 비선점(nonpreemptive)
  • 프로세스가 스스로 CPU 소유권을 포기하는 방식, 강제로 프로세스를 중지하지 않음
  • 컨텍스트 스위칭으로 인한 부하가 적음
  • 모든 프로세스에 대한 공정한 처리
  • 처리시간 예측 용이함

 

 

 

✔️ CPU 스케줄링의 종류

💡 비선점 스케줄링

• FCFS (First Come First Served)
  
  • 큐에 도착한 순서대로 CPU 할당
  • 실행 시간이 짧은 게 뒤로 가면, 평균 대기 시간이 길어짐

 

• SJF (Shortest Job First)
  • 실행 시간이 가장 짧은 프로세스를 가장 먼저 실행
  • FCFS보다 평균 대기 시간 감소, 짧은 작업에 유리

 

• 우선순위
  • 기존 SJF 스케줄링의 경우, 긴 시간을 가진 프로세스가 실행되지 않는다는 현상이 있다.
  • 따라서 이는 오래된 작업일수록 'aging(우선순위를 높이는 방법)'을 콩해 단점을 보완한 알고리즘.

 

💡 선점 스케줄링

• Priority Scheduling
  • 정적/동적으로 우선순위를 부여하여 우선순위가 높은 순서대로 처리
  • 우선순위가 낮은 프로세스가 무한정 기다리는 Starvation이 생길 수 있음
  • Aging 방법으로 Starvation 문제 해결 가능

 

• Round Robin (라운드 로빈)
  • 현대 컴퓨터가 쓰는 스케줄링인 우선순위 스케줄링(priority scheduling)의 일종
  • 각 프로세스는 동일한 할당 시간을 주고, 그 시간 안에 끝나지 않으면 다시 준비 큐(ready queue)의 뒤로 간다.
  • 할단 시간이 크면 FCFS와 같게 되고, 작으면 문맥 교환(Context Switching)이 잦아져 오버헤드 증가
  • 전체 작업 시간은 길어지지만, 평균 응답 시간은 짧아짐

 

• 다단계 큐
  • 우선순위에 따른 준비 큐를 여러 개 사용하고, 큐마다 라운드 로빈이나 FCFS 등 다른 스케줄링 알고리즘을 적용한 것
  • 큐 간의 프로세스 이동이 안 되므로, 스케줄링 부담이 적음 → 유연성이 떨어짐

다단계 큐

 

 

 

✔️ CPU 스케줄링 척도

1. Response Time : 작업이 처음 실행되기까지 걸린 시간
2. Turnaround Time : 실행 시간과 대기 시간을 모두 합한 시간으로, 작업이 완료될 때까지 걸린 시간