CS Study : 10주차 - 스케줄러(Scheduler) / CPU 스케줄러

스케줄러(Scheduler)

• 한정적인 메모리를 여러 프로세스가 효율적으로 사용할 수 있도록 다음 실행 시간에 실행할 수 있는 프로세스 중에
  하나를 선택하는 역할을 수행한다.
• 프로세스를 스케줄링을하기 위한 Queue는 세 가지 종류가 존재 한다.
  • Job Queue - 시스템 안의 모든 프로세스의 집합
  • Ready Queue - 현재 메모리 내에 있으면서 CPU를 잡아서 실행되기를 기다리는 프로세스의 집합
  • Device Queue - Device I/O 작업을 대기하고 있는 프로세스의 집합

스케줄러 종류

• 장기 스케줄러(Long-term scheduler or job scheduler)
  • 디스크와 메모리 사이의 스케줄링을 담당
  • 몇개의 프로그램이 올라갈 것인지를 제어 - degree of Multiprogramming 제어
  • 어떤 프로세스에 메모리를 할당하여 ready queue로 보낼지 결정하는 역할
  • 프로세스의 상태
    • new -> ready
• 단기 스케줄러(Short-term scheduler or CPU scheduler)
  • CPU와 메모리 사이의 스케줄링을 담당
  • Ready Queue에 존재하는 프로세스 중 어떤 프로세스를 running 시킬지를 결정
  • 프로세스에 CPU를 할당
  • 프로세스의 상태
    • ready -> running -> waiting -> ready
• 중기 스케줄러(Medium-term scheduler or Swapper)
  • 여유 공간 마련을 위해 프로세스를 통째로 메모리에서 디스크로 쫒아냄(swapping)
  • 프로세스에게서 메모리 할당 해제
  • degree of Multiprogramming 제어
  • 현 시스템에서 메모리에 너무 많은 프로그램이 동시에 올라가는 것을 조절
  • 프로세스의 상태
    • ready - suspended(외부적인 이유로 프로세스의 수행이 정지된 상태로 메모리에서 내려간 상태)

 

CPU 스케줄러

• CPU 스케줄링은 언제 어떤 프로세스에 CPU를 할당할지 결정하는 작업이다.
• CPU 스케줄러는 메모리에 있는 프로세스들 중 어떤 프로세스를 실행할지 선택하고 CPU를 할당해주는 역할을 한다.
• CPU 스케줄러는 프로세스들이 네 종류의 상황에 있을 때 스케줄링을 결정한다.
  1,4 번 상황에서 스케줄링이 발생하는 것을 비선점형 스케줄링, 나머지는 선점현 스케줄링이라 한다.
  
  1. 실행(running) 상태에서 대기(waiting) 상태로 전환 될 때
  2. 실행(running) 상태에서 준비(ready) 상태로 전환될 때
  3. 대기(waiting) 상태에서 준비(ready) 상태로 전환될 때
  4. 종료(Terminated)될 때

 

비선점형(Non-preemptive) 스케줄링

• 프로세스가 CPU를 점유하고 있으면 이를 뺐을 수 없는 방식
• 필요한 문맥 교환만 일어나기 때문에 오버헤드가 상대적으로 적지만, 프로세스의 배차에 따라
  효율성 차이가 많이 난다.
• 모든 프로세스에 대한 공정한 처리가 가능하다.
• 실행시간이 긴 프로세스에 의해 실행시간이 짧은 프로세스가 기다리는 현상이 생길 수 있다.

선점형(preemptive) 스케줄링

• 프로세스가 CPU를 할당받아 실행중이더라도 운영체제가 이를 강제로 뺐을 수 있는 방식
• CPU 처리시간이 매우 긴 프로세스의 CPU 사용 독점을 막을 수 있어 효율적으로 운영 가능
• 잦은 문맥 교환으로 오버헤드가 커질 수 있다.
• 기아 현상이 발생할 수 있다.
  • 기아 현상 - 계속해서 우선순위가 높은 프로세스가 먼저 실행되어 먼저 도착했어도 우선수위가 낮은 프로세스가
    계속해서 CPU를 할당받지 못하는 현상

 

CPU 스케줄링 평가 기준

• CPU 이용율(CPU Utilization)
  • 시간당 CPU를 사용한 시간의 비율
  • 프로세서를 실행상태로 항상 유지하려고 해야 한다.
• 처리율(Throughput)
  • 시간당 처리한 작업의 비율
  • 단위 시간당 완료되는 작업 수가 많도록 해야 한다.
• 반환시간(Tunraround Time)
  • 프로세스가 생성된 후 종료되어 사용하던 자원을 모두 반환하는데까지 걸리는 시간
  • 작업이 준비 큐에서 기다린 시간부터 CPU에서 실행된 시간, I/O 작업시간의 합이다.
• 대기시간(Waiting Time)
  • 대기열에 들어와 CPU를 할당받기 까지 걸린 시간
  • 준비 큐에서 기다린 시간의 총합
• 반응시간(Response Time)
  • 대기열에서 처음으로 CPU를 얻을 때까지 걸린 시간
  • 대기시간과 비슷하지만, 대기시간은 준비 큐에서 기다린 모든 시간을 합친 것이지만
    반응 시간은 CPU를 할당받은 최초의 순간까지 기다린 시간 한번만 측정한다.

 

CPU 스케줄링 알고리즘

FCFS(First Come First Served) 스케줄링

• 가장 먼저 요청한 프로세스에 CPU를 할당해주는 방식이다.
• 비선점형 스케줄링이다.
• 평균 대기 시간이 길어질 수 있다.
• 응답 시간이 길어질 수 있다.
• 반환 시간이 길어질 수 있다.
• 콘보이 효과가 발생할 수 있다.
  • 실행 시간이 긴 프로세스가 먼저 도착해 다른 프로세스의 실행 시간이 전부 늦춰져 효율을 떨어트리는 현상         

SJF(Shortest-Job-First) 스케줄링

• 다음 CPU의 실행 시간의 길이를 고려해서 스케줄링을 결정하는 알고리즘이다.
• 비선점형과 선점형이 따로 존재한다.
• 비선점형에서는 실행되고 있는 프로세스는 끝까지 실행한다.
• 선점형에서는 현재 실행되고 있는 프로세스의 남은 시간보다 도착한 다음 프로세스가 더 빨리 끝낼 수 있는
  프로세스라면 다음 프로세스를 실행하도록 바꾸게 된다. -> SRT(Shortest Remaining Time First)라고도 한다.
• 평균 대기 시간을 줄일 수 있다.
• 다음 프로세스의 CPU 실행 시간을 예측하는 것이 어렵다는 문제가 존재한다.

비선점형 SJF 예시

선점형 SJF 예시

Priority(우선순위) 스케줄링

• 각가의 프로세스에 우선순위 넘버가 있다.
• 가정 높은 우선순위의 프로세스에 CPU를 할당한다.
• 선점형과 비선점형이 나뉜다.
• SJF도 Priority 스케줄링이라고 할 수 있다.
• 기아 문제가 발생할 수 있다.
• 기아문제를 해결하기 위해서 aging 기법을 사용할 수 있다.
  • aging(노화) 기법 - 먼저 도착한 프로세스의 시간이 지날수록 우선순위를 높여주는 기법

 

Round Robin(RR) 스케줄링

• 각각의 프로세스에 동일한 CPU 할당 시간을 부여해서 해당 시간 동안만 CPU를 이용하게 한다.
• 할당 시간 내에 처리를 완료하지 못하면 다음 프로세스로 넘어가므로 선점형 방식이다.
• n개의 프로세스가 있을 때 할당 시간을 q라 한다면 모든 프로세스가 (n-1)q 시간 이상 기다리지 않아도 된다.
• 응답 시간을 빠르게 할 수 있다는 장점이 있다
• 할당 시간이 커지면 FCFS처럼 작동한다.
• 할당 시간이 매우 작아지만 process sharing 이라고 부른다.
  • process sharing - n개의 프로세스가 프로세서 속도의 1/n 씩으로 작동함을 의미

 

Multilevel Queue / Multilevel Feedback Queue(MFQ)

Mutlilevel Queue

• 준비 큐가 여러 개의 큐들로 나뉜다.
• 각 큐는 각자의 스케줄링 알고리즘을 가지고 있다.
• 각 큐 사이에서 프로세스들이 이동할 수 없다.
• 일반적으로 Foreground 프로세스들은 Round Robin 방식을 사용하고, Background 프로세스는 FCFS를 사용한다.
• 기아 현상이 발생할 수 있다.
• 보통 CPU 시간의 80%는 RR, 20%는 FCFS에 할당된다.
• MFQ는 Multilevel Queue와 비슷하지만 각 큐 간에 프로세스들이 이동할 수 있다.

MFQ

 

---

참고 블로그

[운영체제] CPU 스케줄링 알고리즘 정리 및 요약 | FCFS, SJF, Round Robin

[OS] 스케줄러(scheduler) 란?

[운영체제] 스케줄러(Scheduler)