[운영체제] CPU 스케쥴링(Scheduling)

오늘은 CPU스케쥴링에 대해 알아보자

 

하나의 프로세스만 CPU를 독점하고 있으면 어떻게 될까?

지금 우리가 여러개의 프로그램을 동시에 사용하는 것은 불가할 것이다.(사실 어느 시점의 CPU는 하나의 프로세스가 사용하고 있지만 매우 빨리 바뀌기 때문에 우리는 동시에 사용한다고 느끼는 것이다.)

 

그렇다면 여러 프로세스들이 CPU를 번갈아가면서 사용해야 하는데 어떤 기준을 가지고 CPU를 할당 받게 될까?
지금부터 그 기준을 알아보자

 

먼저 CPU 스케쥴링에는 선점(Preemptive)와 비선점(Non-Preemptive)가 있다.

단어만 들어서는 무슨 뜻인지 모르겠다.

선점이란?

선점 방식이란 예를 들어 A프로세스가 실행되고 있는데 특정한 기준에 의해 우선순위가 더 높은 B프로세스가 CPU를 요청하게 되면 A프로세스는 그 즉시 CPU를 사용하지 못하고 뺏기게 되는 방식이다.

쉽게 말해 다른사람이 빼앗을 수 있다! 라는 방식이다.

 

비선점이란?

반대로 비선점은 A프로세스가 CPU를 사용하고 있을때 우선순위가 더 높은 B프로세스가 들어온다고 하더라도 A프로세스의 CPU를 빼앗지 않고 명령이 끝날때까지 기다렸다 할당받는 방식이다.

쉽게 말하면 놀이기구 하이패스를 얻는 느낌이다. 하이패스를 얻는다고 지금 타고 있는 탑승객을 끌어내리고 타지 못하는 것처럼 놀이기구의 사이클이 끝나기 기다렸다 타는 방식이다!!

 

CPU스케쥴링에는 여러가지가 있는데 그전에 이 알고리즘의 성능은 어떻게 평가할까?

관련 용어에 대해 정리하고 넘어가자

• CPU utilization(CPU 이용률)
  • CPU 동작 시간 / 실행 시간 (%)
• Throughput(처리량)
  • 단위 시간당 프로세스가 종료된(완료된) 개수
• Turnaround time(소요시간, 반환시간)
  • Process가 들어온 시간 ~ 실행이 끝날때 까지 시간
• Waiting time(대기시간)
  • CPU버스트 중에 준비큐에서 기다린 시간의 총합
• Response time(응답시간)
  • 프로세스가 CPU 요청 시점부터 처음으로 CPU를 얻을때까지 기다린 시간
  • 사용자 경험과 관련되었기 때문에 따로 체크

위와 같은 용어들로 CPU 스케쥴링 알고리즘의 성능이 평가 된다.

 

 

드디어 CPU스케쥴링 알고리즘이다!

먼저 FCFS(First Come First Serve)이다.

이 방식은 말 그대로 먼저들어온 프로세스가 먼저 CPU를 할당받는 방식이다.

특징으로는 일단 다른 프로세스의 할당을 빼앗지 않는 비선점방식이고 간단한 방법인 만큼 효율이 낮다.

콘보이현상(Convoy Effect)가 나타날 수 있는데 이는 실행시간이 긴 프로세스가 앞순서에 오고 뒷순서에 실행시간이 짧은 프로세스가 오게 되면 전체 프로세스들의 평균 대기시간이 늘어나는 현상이다.

 

다음으로는 SJF(Shortest Job First)가 있다.

SJF는 실행시간이 짧은 프로세스의 우선순위를 높여 먼저 처리되게 하는 방식이다.

이 방식은 비선점과 선점 방식 둘다 구현할 수 있는데 선점형 방식으로 구현한 SJF는 특별히 SRTF(Shortest Remain Time Fisrt)라고 불린다.

비선점 SJF의 특징으로는 전체 대기 시간이 다른 알고리즘에 비해 짧다는 것이다. 하지만 실제로 적용하기엔 무리가 있는 방법이다. 실제 실행시간(CPU burst)를 알 수 없기 때문이다. 또 처리 시간이 짧은 프로세스가 계속 들어오게 되면 뒷순서의 프로세스가 영원히 실행되지 않을 수 있는 Starvation(기아)현상이 나타날 위험을 가지고 있다.

선점형 방식 SRTF는 가장 최소한의 대기시간을 보장해준다.(SJF보다 더)

한편 SJF의 Starvation현상을 방지하기 위해 추가적으로 고안된 방법이 HRN(Highest Response-ratio Next)이다.

HRN은 SJF에 Aging기법을 적용한 방법으로 비선점방식으로 구현된다.

우선순위 = (대기시간+실행시간)/실행시간  으로 구하는 방식으로 대기시간이 Aging역할을 한다고 보면 된다.

 

다음은 Round Robin방식이 있다.

라운드 로빈은 Time Quantum (Time Slice) 로 나눠서 공평하게 실행하고 이를 위해 timer(하드웨어) 사용한다.

하지만 Time Slice가 매우 크다면 FCFS와 비슷하게 되고 Time Slice가 매우 작다면 context switching 오버헤드가 커진다.

라운드로빈의 장점은 Response Time이 줄어든다는 것이다. 어떤 프로세스도 (n-1)*q이상 기다리지 않음을 보장한다.(n=ready queue에 존재하는 프로세스 개수, q = unit time)

하지만 Turnaround Time(어떤 작업의 처음실행~끝날때까지의 시간)은 길어진다는 단점을 가지고 있다.

 

다음은 우선순위 스케쥴링(Priority Scheduling) 방식이다.

우선순위 스케쥴링은 선점,비선점 두가지 방법으로 모두 구현이 가능하다.

하지만 starvation현상이 생길 수 있고 Aging을 통해 해결할 수 있다.

 

멀티레벨큐(다단계큐)

멀티레벨 큐는 작업 종류에 따라서 우선순위를 나누고 큐에 할당하는 방식이다.

최초의 배정된 큐를 벗어나지 못하고, 각각의 큐는 자신만의 스케쥴링 방식을 가지고 있다.

우선순위가 높은 큐에 속하는 경우에는 빠른 응답시간을 가지지만 여러개의 큐를 관리해야 하므로 오버헤드가 발생하고 우선순위가 낮은 큐는 Starvation 현상이 발생할 수 있다.

 

멀티레벨 피드백 큐(다단계 피드백 큐)

멀티레벨 피드백 큐는 큐 사이에 우선순위 변경이 가능한 방식이다.

다단계 큐에 동적인 프로세스 우선순위 변화를 적용해 Turnaround Time을 줄인 방식이다.

그림을 보면 time quantum을 다 채운 경우는 실행시간이 긴 프로세스라고 판단해 아래의 큐로 내려가고 내려가서도 끝나지 않으면 계산위주의 프로세스라고 판단해 FCFS로 내려가게 된다.

 

지금까지 CPU스케쥴링 방식에 대해 알아보았다.

 

끝!