[CS / CA] CPU Scheduling

CPU 스케쥴링

CPU는 한 번에 하나의 프로세스만 실행 가능하므로 CPU 이용률을 극대화하기 위해 어떤 프로세스에 CPU를 할당할지 결정하는 작업

 

 

CPU 스케쥴러

CPU스케쥴러는 메모리에 있는 프로세스들 중 어떤 프로세스를 실행할지 선택하고 CPU에 할당해주는 역할을 함

 

 

스케쥴링 발생 상황

1. 실행(running) 상태에서 대기(waiting) 상태로 전환
2. 실행(running) 상태에서 준비(ready) 상태로 전환
3. 대기(waiting) 상태에서 준비(ready) 상태로 전환
4. 종료(terminated)될 때

스케쥴링 종류

• 비선점형 스케쥴링 (non-preemption)
  • 필요한 문맥 교환만 일어나므로 오버 헤드가 상대적으로 적지만 프로세스 배치에 따라 효율성 차이가 크게 남
  • 프로세스가 CPU를 점유하고 있다면 뺏을 수 없는 방식
• 선점형 스케쥴링 (preemption)
  • CPU 처리 시간이 매우 긴 프로세스의 CPU 사용 독점을 막을 수 있어 효율적인 운영이 가능하지만 잦은 문맥 교환으로 오버헤드가 커질 수 있음
  • 프로세스가 CPU를 할당받아 실행 중이더라도 운영체제가 이를 강제를 뺏을 수 있는 방식

 

스케쥴링 기준

• 대기시간
  • 프로세스가 생성된 후 실행되기 전까지 대기하는 시간 (준비 큐에서 대기하는 시간)
• 평균 대기 시간
  • 모든 프로세스의 대기 시간을 합한 후 프로세스의 수로 나눈 값
• 응답 시간
  • 첫 작업을 시작한 후 첫 번째 반응이 나오기 전까지 시간
• 실행 시간
  • 프로세스 작업이 시작된 후 종료되기 전까지 시간
• 반환 시간
  • 대기 시간을 포함하여 실행이 종료될 때까지 시간

 

CPU 스케쥴링 알고리즘

• FCFS (Fist Come First Served)
  • 가장 먼저 요청한 프로세스에 CPU 할당
  • 비선점형 알고리즘
  • 가장 먼저 요청한 프로세스에 CPU 할당
  • 단순하고 많이 사용하는 방식
  • 평균 대기 시간, 응답 시간이 길어질 수 있음
  • Convey Effect(호위병 효과) 발생가능 → 사용시간이 짦은 프로세스들이 사용시간이 긴 프로세스에 의해 오래 기다리는 현상
• SJF (Shortest Job First)
  • 수행 시간(burst time)이 가장 짧은 작업에 먼저 CPU 할당
  • 비선점형 알고리즘
  • FCFS보다 평균 대기시간 감소
  • 프로세스의 CPU 점유시간(burst time)을 아는 것은 현실적으로 불가능
• Priority
  • 가장 높은 우선순의의 프르세스에 CPU 할당
  • starvation(기아) 발생가능 → 우선순위가 낮은 프로세스는 하염없이 기다림
• RR (Round Robin)
  • 각각의 프로세스에 동일한 CPU 할당 시간(Time Quantum)을 부여해 해당 시간 동안만 CPU 할당
  • 선점형 알고리즘
• MQ (Multilevel Queue)
  • 프로세스 그룹에 따라 큐를 여러개로 분할
  • 큐의 우선순위를 나누어주고 각 큐마다 다른 Time Quantum설정
  • 각 큐의 알고리즘은 각각 다름
• MFQ (Multilevel Feedback Queue)
  • Time Quantum을 채운 프로세스는 밑으로 내려가고 그렇지 못한 프로세스는 원래 큐에 있음