6일차 - CPU Scheduling

오늘은 CPU 스케쥴링에 대해서 배웠다. 앞에서 배운 내용은 CPU와 프로세스에 대한 간단한 개념을 배웠는데

프로세스가 CPU를 할당받는다고 했다.

할당받을 때 규칙이 존재하고 오늘은 그 규칙에 대해 배울 수 있었다.

 

 

 

1. CPU 스케쥴링의 필요성

운영체제는 왜 CPU 스케쥴링이 필요할까?

우선, 필요한 이유를 설명하기 전에 필요한 개념부터 말하려고 한다.

프로그램이 실행(execution) 된다는 것은 CPU burst와 I/O burst의 연속을 의미한다.

CPU burst는 CPU를 사용하여 무언가는 하는 시간이고 I/O burst는 I/O의 결과를 기다리는 시간이다.

이러한 점에서 우리는 프로세스를 2가지로 특성 분류할 수 있다.

 

1) I/O bound process

CPU를 잡고 계산하는 시간보다 I/O에 많은 시간이 필요한 job

(CPU burst가 짧지만 빈번한 process)

 

2) CPU bound process

계산위주의 job

(CPU burst가 길지만 빈도가 적은 process)

 

이렇게 여러 종류의 job(process)이 섞여서 존재하고 있기 때문에 CPU스케쥴링이 필요한 것이다.

CPU를 오랫동안 잡고 있는 프로세스가 있다면 다음 프로세스가 실행될 때까지 기다리는 시간이 길어지므로 비효율적이고 유저와의 상호작용적으로 동작하기 위해서 CPU 스케쥴링을 통해 제어를 한다고 생각하면 된다.

 

 

2. CPU 스케쥴링 알고리즘

CPU 스케쥴링을 하기 위해서는 여러 알고리즘이 존재한다.

먼저, 스케쥴링 알고리즘은 nonpreemtive와 preemtive로 나뉜다.

- nonpreemtive는 프로세스가 CPU를 선점했을 때 CPU를 강제로 뺐지 않는 알고리즘이다.

- preemtive는 프로세스가 CPU를 선점했어도 CPU를 강제로 뺐는 알고리즘이다.

 

현대에서는 거의 preemtive한 스케쥴링만 사용하고 있다.

 

스케쥴링 알고리즘을 하나씩 알아보기 전에 어떠한 알고리즘이 좋은지를 판단하기위한 척도를 나타내는 scheduling Criteria(성능척도)를 알아보자.

1) CPU utilization(이용률)

CPU utilization은 전체시간 중에 CPU가 일한 시간을 %로 나타내는 척도로 값이 높을수록 좋은 알고리즘이다.

 

2) Throughout(처리량)

Throughout은 주어진 시간(단위시간)중에 처리한 일의 양을 나타낸 척도로 값이 높을수록 좋은 알고리즘이다.

 

3) Turnaround time(소요시간)

turnaround time은 프로세스가 CPU를 사용하기위해 ready queue에 들어온 시간부터 다 쓰고 나간 시간을 의미한다.

프로세스가 CPU를 선점하기까지 기다리는 시간도 포함이 된다.

 

4) Waiting time(대기시간)

waiting time은 CPU를 사용하기 위해 ready queue에서 기다릴 시간을 의미한다.

프로세스가 여러 번 CPU를 기다렸다면 기다린 시간의 총합이다.

 

5) Response time(응답시간)

response time은 처음으로 CPU를 사용하기까지 걸린 시간을 의미한다.

 

이렇게 5가지의 성능척도가 존재하고 1번과 2번은 시스템입장에서 성능척도이고 3, 4, 5번은 프로세스입장에서 성능척도이다.

 

 

3. FCFS(First Come First Served)

FCFS는 풀네임을 그대로 해석하면 처음으로 들어온 것이 처음으로 CPU를 받는다는 것이다.

즉, ready queue에 들어온 순서대로 CPU를 사용할 수 있게 되고 한번 CPU를 얻으면 그 프로세스가 완료될 떄까지 CPU를 놓지않는다.

즉, 강제로 CPU를 빼았지 않으므로 비선점형 스케쥴링에 속한다.

이 알고리즘은 그다지 효율적이지 않다.

그 이유는 만약 CPU burst 시간이 긴 프로세스가 CPU를 선점한다면 늦게 왔지만 CPU burst 시간이 짧은 프로세스가 오랫동안 기다려야한다.

이렇게 되면 대기시간이 전체적으로 길어지게 되므로 효율적이지 않다.

이러한 현상을 convoy effect라고 한다.

 

 

4. SJF(Shortest-Job First)

SJF는 CPU burst시간이 짧은 프로세스에게 먼저 CPU를 주는 방식이다.

이렇게 되면 주어진 프로세스들에 대해 최소 평균 대기시간을 보장할 수 있다.

SJF는 선점형과 비선점형으로 나누어 동작한다.

1) 비선점형

비선점형 SJF를 보면 CPU burst 시간이 가장 짧은 프로세스가 CPU를 선점하고 있을 때 더 짧ㅅ은 프로세스가 ready queue에 도착했더라도 현재 CPU를 선점하고 있는 프로세스는 강제로 빼았기지 않는다.

 

2) 선점형

선점형 SJF를 보면 현재 CPU를 선점하고 있는 프로세스가 있는데 그 프로세스보다 짧은 CPU burst time을 가진 프로세스가 도착한다면 CPU를 내주는 방식이다.

이러한 스케쥴링을 다른말로 SRTF(Shortest Remaining Time First)라고도 한다.

즉, CPU를 내어줄 경우가 발생했을 때 시간이 짧다는 개념이 앞으로 남은 CPU burst 시간이 누가 더 짧은지를 의미하는 것이다.

 

이러한 SJF도 2가지의 문제점이 존재한다.

1) Starvation

첫 번째 문제점은 starvation으로 CPU burst time이 긴 프로세스는 하염없이 기다리는 경우가 발생할 수 있다.

아무리 일찍 도착했더라도 자신보다 짧은 프로세스가 ready queue에 들어온다면 CPU 우선순위를 내주어야한다.

 

2. CPU사용시간을 미리알 수 없다.

어느 시간에 들어왔어도 우선순위가 뒤로 밀릴 수 있고 CPU를 선점했어도 강제로 빼았길 수 있기 때문에 CPU 사용시간을 미리알 수 없다.

CPU 사용시간을 예측하기 위해서는 과거에 얼마나 사용했는지를 통해 예측해야한다.

보통 exponential averaging을 활용한다.

 

 

5. Priority Schduling

Prioirty Schduling은 우선순위가 높은 프로세스에게 CPU를 주는 방식이다.

이 스케줄링도 비선점형과 선점형으로 나누어 동작할 수 있고 SJF내용과 유사한 설명이므로 생략하겠다.

우선순위는 우선순위를 나타내는 숫자가 정해지고 보통 정수 값을 사용한다.

우선순위가 높으면 낮은 숫자이다.

여기서 SJF도 Priority Schduling중 하나인데 SJF는 우선순위를 CPU burst time을 가지고 한 것이라고 보면 된다.

 

이 스케쥴링도 Starvation 문제점이 발생하는데 Aging을 통해 해결이 가능하다.

Aging은 오래기다렸다는 것을 인정해주고 우선순위를 높여주는 것이다.

스케쥴링은 전체적으로 보았을 때 효율성이 높아야하지만 특정 부분에서 손해보는 일도 막아야한다.

 

 

6. Round Robin(RR)

Round Robin은 프로세스가 CPU를 사용하는 시간을 동일하게 하는 것이다.

즉, 주어진 시간이 끝나면 CPU를 강제로 빼았게 되므로 선점형 스케쥴링이다.

이 스케쥴링의 장점은 응답시간이 빨라진다는 것이다.

어떠한 프로세스도 (n-1)q 시간 이상 기다리지 않는다.

(n: ready queue에 존재하는 프로세스 갯수, q: 운영체제가 정한 할당되는 시간)

 

특징으로는 CPU를 길게 쓰는 프로세스는 대기시간이 길어지고 CPU를 짧게 쓰는 프로세스는대기시간이 짧아진다.

이 스케쥴링에서 가장 중요한 점은 할당되는 시간(q)를 잘 설정해야하는 것이다.

q를 너무 크게 설정한다면 FCFS와 별 다를게 없게 된다.

q를 너무 작게 설정한다면 CPU를 선점하는 프로세스가 자주 바뀌어 context switch가 자주 발생하여 오버헤드가 많아지므로 시스템에 부담이 된다.

 

Round Robin은 일반적으로 SJF보다 average turnaround time이 길지만 response time은 짧다.