[운영체제] CPU 스케줄러

CPU 스케줄러란?

• 프로세스가 생성된 후 종료될 때까지 모든 상태 변화를 조정하는 일을 한다.
• 모든 프로세스가 공평하게 작업할 수 있도록 하는 것이 본 목적이다.
• 하지만, 안정성과 효율성을 높이기 위해서 공평성의 일부분을 희생하는 경우도 있다.

스케줄링이 추구하는 목적

• 공평성: 모든 프로세스가 자원을 공평하게 배정받아야 한다. 특정 프로세스가 배제되어서는 안된다.
• 효율성: 시스템 자원을 늘리는 시간 없이 스케줄링 해야한다.
• 안정성: 우선순위를 사용하여 중요한 프로세스가 먼저 처리되도록 해야한다.
• 반응 시간 보장: 응답이 없는 경우, 사용자는 시스템이 멈춘 것으로 가정하기 때문에 시스템은 적절한 시간 안에 프로세스의 요구에 반응해야 한다.
• 무한 연기 방지: 특정 프로세스의 작업이 무한이 연기되면 안된다.

 

스케줄링 알고리즘 평가기준

• CPU 입장
  • CPU utilization: 시스템 동장 시간 중, CPU가 작업을 처리하는 시간의 비율. 최대한 CPU를 바쁘게 만드는 것. 가장 이상적인 수치는 100%
  • 처리 량(Throughput): CPU가 단위 시간당 처리하는 프로세스 개수. CPU 버스트를 처리한 수
• 프로세스 입장
  • 반환시간: 프로세스가 생성된 후 종료되어 사용하던 자원을 모두 반환하는데까지 걸린 시간. 대기시간 + 실행시간
  • 대기시간: 프로세스가 CPU를 할당받아 실행되기 전 대기상태일 때의 시간. 보통 준비 큐에서 대기하는 시간.
  • 응답시간: 프로세스가 대기 상태에 들어와 CPU를 최초로 얻기까지 걸리는 시간. 대기시간은 여러번 있을 수 있고, 그 총합이 대기시간인데 응답 시간은 최초의 한번이다.

 

 

preemptive(선점형) vs non-preemptive(비선점형)

preemptive

• CPU를 할당받아 실행중인 프로세스로부터 운영체제가 CPU를 강제로 빼앗을 수 있는 방식
• CPU 처리 시간이 매우 긴 프로세스의 CPU 독점을 막을 수 있다.
• 잦은 문맥 교환으로 오버헤드가 많이 발생한다.

non-preemptive

• CPU를 할당받아 실행중인 프로세스로부터 운영체제가 CPU를 빼앗을 수 없는 방식
• 필요한 문맥 교환만 일어나기 때문에 오버헤드가 상대적으로 적다.
• 프로세스의 배치에 따라서 효율성의 차이가 많이 난다.

 

CPU bound vs I/O bound

프로세스가 대기 상태에 있다가 CPU를 할당받아서 실행하면 **CPU burst**,

입출력 작업하면 **I/O burst** 라고 한다.

CPU bound process(CPU 집중 프로세스)

• CPU를 많이 사용하여 CPU burst가 많은 프로세스

I/O bound process(입출력 집중 프로세스)

• 입출력을 많이 사용해 IO burst가 많은 프로세스

 

전면 프로세스 vs 후면 프로세스

전면 프로세스

• GUI를 사용하는 os에서 화면의 맨 앞에 놓여 현재 입출력이 사용되고, 사용자와 상호작용이 가능해 상호작용 프로세스라고도 불린다.

후면 프로세스

• 사용자의 입력 없이 작동하여 일괄 작업 프로세스라고 불린다.

 

 

스케줄링 알고리즘 종류

 

FCFS(First Come First Served)

• 선입선출 방식
• 준비 큐에 도착한 순서대로 CPU를 할당하는 비선점형 방식
• 모든 프로세스의 우선순위가 동일
• CPU 처리 시간이 긴 프로세스가 앞에 올 경우, 뒤의 프로세스가 한없이 기다려야 하기 때문에 비효율적이게 된다. (콘보이효과)

SJF(Shortest Job First)

• 준비 큐에 있는 프로세스 중 실행 시간이 가장 짧은 프로세스부터 CPU를 할당하는 비선점형 방식
• 장점
  • FCFS보다 효율성이 매우 높다.
  • 늦게 도착하더라도 CPU 처리시간이 앞에 대기중인 프로세스보다 짧으면 먼저 CPU를 할당받을 수 있다. (콘보이효과 완화)
• 단점
  • 비선점형 방식이기 때문에 CPU를 사용중인 프로세스보다 처리 시간이 짧더라도 빼앗지는 못한다.
  • 처리 시간이 긴 프로세스 경우에 처리 시간이 짧은 프로세스가 계속해서 들어올 경우 대기 큐에서 영엉 CPU를 할당받지 못할 수 있다.(starvation 현상)

HRN(Highest Response Ratio Next)

• SJF 스케쥴링에 **Aging** 기법을 합친 비선점형 알고리즘
  • Aging: starvation을 해결하기 위해 대기 시간이 길어지면 우선순위를 높여주는 방법
• 실행 시간이 적은 프로세스의 우선 순위가 높지만 대기시간이 너무 길어지면 실행 시간이 길더라도 CPU를 할당받을 수 있다.

SRTF (Shortest Remaning Time First)

• SJF의 선점형 방식
• 먼저 온 프로세스가 CPU를 할당받고 있어도 처리시간이 짧은 프로세스가 오면 CPU를 빼앗긴다.
• 장점
  • 어떤 알고리즘보다 평균 대기 시간이 가장 짧다.
• 단점
  • 선점형 방식이기 때문에 잦은 문맥교환이 일어나고, 그에 따른 오버헤드가 커진다.
  • starvation 현상이 더 심각하게 발생할 수 있다.

Priority Scheduling

• 프로세스의 중요도에 따라 매긴 우선순위를 반영한 알고리즘

RR(Round Robin)

• 프로세스에게 각각 동일한 CPU 할당 시간(quantum)을 부여해서 이 시간 동안만 CPU를 이용하게 한다. -> 할당 시간동안 처리를 다 못할경우, CPU를 빼앗기기 때문에 선점형 방식이다.
• CPU 처리시간을 계산하지 않아도 돼서 선점형 방식의 가장 단순하고 대표적인 방법이다.