● Scheduling Algorithms 종류
- FCFS (First-Come First-Served)
- SJF (Shortest-Job-First), SRTF (Shortest-Remaining-Time-First)
- Priority Scheduling
- RR (Round Robin, 라운드 로빈)
- Multilevel Queue
- Multilevel Feedback Queue
스케줄링 알고리즘은 크게 두 가지로 나눌 수 있다. nonpreemptive(비선점형)한 스케줄링과 preemptive(선점형)한 스케줄링이다. 선점형은 CPU 제어권을 한 번 줬으면 그 프로그램이 다 쓰고 나갈 때까지 CPU 제어권을 강제로 다시 빼앗지 않는다. 비선점형 스케줄링은 Timer Interrupt와 같이 CPU 제어권을 강제로 빼앗을 수 있다. 거의 대부분 선점형 스케줄링을 사용한다.
- nonpreemptive : 특정한 프로세스의 작업이 끝날 때까지 CPU를 독점한다.
- preemptive : 하나의 프로세스가 CPU를 점유하고 있을 때 다른 프로세스가 CPU를 빼앗을 수 없다.
● Scheduling Criteria
- CPU Utilization (이용률)
- Throughput (처리량)
- Turnaround Time (소요 시간, 반환 시간)
- Waiting Time (대기 시간)
- Response Time (응답 시간)
스케줄링에는 여러 가지 알고리즘이 있다. 그렇다면 어떤 알고리즘이 좋은지 평가할 수 있어야 하는데 그 기준을 Scheduling Criteria(성능척도)라고 한다. CPU Utilization (이용률)과 Throughput (처리량)은 시스템 입장에서의 성능 척도이며, Turnaround Time (소요 시간, 반환 시간), Waiting Time (대기 시간), Response Time (응답 시간)은 프로세스 입장에서의 성능 척도이다.
시스템 입장에서는 CPU 하나 가지고 최대한 일을 많이 시킬수록 좋고, 프로세스 입장에서의 성능 척도란 시간과 관련된 성능 척도이다.
- 시스템 입장에서의 성능 척도 : 이용률, 처리량
- 프로세스 입장에서의 성능 척도 : 소요 시간, 대기 시간, 응답 시간
CPU Utilization (이용률)
전체 시간 중에서 CPU가 놀지 않고 일한 시간을 나타낸다. CPU는 굉장히 비싼 자원이기 때문에 가능한 바쁘게 일을 시켜야 한다.
Throughput (처리량)
주어진 시간 동안에 몇 개의 작업을 완료했는지를 나타낸다. 주어진 CPU를 가지고 주어진 일을 많이 해야 한다.
Turnaraound Time (소요 시간, 반환 시간) 중요
CPU를 사용하러 들어와서 다 쓰고 I/O를 하러 빠져나갈 때까지의 시간이다.
Waiting Time(대기 시간)
CPU를 쓰고자 하더라도 CPU가 하나밖에 없어서 Ready Queue에서 기다린 시간이다.
Response Time (응답 시간)
CPU를 쓰겠다고 Reqdy Queue에 들어와서 처음 CPU를 얻을 때까지 걸린 시간이다.
그럼 여기서!! 대기 시간이랑 응답 시간이랑 뭐가 다르지?라고 한다면... 선점형인 경우에 한 번의 CPU burst 동안에도 CPU를 얻었다/뺏겼다를 반복할 수 있다. CPU 제어권을 뺏겼을 때, Ready Queue에 들어가서 기다렸다가 CPU 제어권을 얻는 과정을 계속 반복한다. 이때, 기다린 시간을 다 포함한 게 대기 시간이고, 처음 CPU를 얻을 때까지 기다린 시간이 응답 시간이다. (소요 시간은 기다린 시간과 CPU 사용 시간을 모두 다 포함한 총 시간) 응답 시간은 CPU 제어권을 얻었다가 빼앗기는 Time Sharing 환경에서는 처음 CPU를 얻는 시간이 사용자 응답과 관련해서 중요한 시간 개념이다.
예를 들어, 내가 중국집을 운영한다고 했을 때, 주방장을 고용해 주방장에게 일을 많이 시켜야 한다. 전체 시간 중에서 주방장이 놀지 않고 일한 비율이 Utilization (이용률)이고, 중국집에서 단위 시간당 손님을 얼마나 받고 내보냈는지가 Throughput (처리량)이다. 나머지 세 가지의 factor는 내가 고객일 때의 입장으로 생각해 보면, 내가 중국집에 들어와서 주문 후 식사를 다 하고 나갈 때까지 걸린 시간이 소요 시간이며 내가 밥을 먹은 시간 말고 기다린 시간들이 대기 시간, 첫 번째 음식이 나올 때까지 기다린 시간이 응답시간이다. 단무지라도 하나 먼저 주면(응답시간이 빠르면) 그걸로 허기를 달래겠지.. 응답시간 중요해....!!!
● FCFS (First-Come First-Served)
먼저 온 순서대로 먼저 처리하는 알고리즘이다. 예를 들면 은행에 가서 번호표를 뽑는다거나, 화장실에 줄을 선다거나 하는 것이다. 그다지 뭐 효율적이지는 않다. CPU를 굉장히 오래 쓰는 프로세스가 먼저 도착해서 CPU 제어권을 먼저 잡게 된다면 CPU를 짧게 쓰는 프로그램(Interactive 한 Job)들이 들어와도 오래 기다려야 한다.
예를 들어, 위 그림과 같이 프로세스 1, 프로세스 2, 프로세스 3이 거의 동시에 들어왔는데 아주 간발의 차이로 P1, P2, P3 순으로 들어왔다고 가정해 보자. 프로세스 1번이 먼저 CPU를 잡고 24초 동안 CPU 제어권을 잡고 실행을 한 후, 그다음 프로세스 2가 CPU를 얻어서 3초 사용 후 놓게 되면 프로세스 3은 총 27초를 기다린 후에야 CPU를 얻을 수 있다. 간발의 차이로 늦었지만 프로세스 3은 결국 27초나 기다리게 되는 것이다. 이는 Time Sharing 시스템에서 Interactive의 응답 시간이 매우 길어지기 때문에 그다지 좋은 방법이 아니다.
똑같은 Burst Time을 가진다고 했을 때, 이번에는 P2, P3, P1 순으로 도착했다고 가정해 보자.
프로세스 2번이 먼저 CPU를 잡고 3초 동안 CPU 제어권을 잡고 실행을 한 후, 그다음 프로세스 3이 CPU를 얻어서 3초 사용 후 놓게 되면 프로세스 1은 6초를 기다린 후 실행을 한다. 첫 번째 예시와 평균 대기 시간을 비교해 보았을 때, 14초나 빨라졌다. 도착 순서에 따라 평균 대기 시간이 차이가 많이 나는 것을 볼 수 있다.
FCFS는 비선점형 스케줄링으로 일단 CPU를 얻으면 내놓을 때까지 뺏기지 않는다. 따라서 먼저 온 프로세스가 CPU를 사용하는 시간이 길면 매우 비효율적이다. 이렇게 먼저 도착한 긴 프로세스 때문에 나중에 도착한 다른 프로세스가 CPU를 오래 기다리는 상황을 Convoy effect라 한다.
● SJF (Shortest-Job-First)
CPU를 사용하고자 하는 시간이 가장 짧은 프로세스에게 CPU 제어권을 넘겨주는 것이다. Burst Time이 짧은 프로세스는 CPU를 빨리 사용하고 빨리 넘겨줄 것이기 때문에 Queue가 전체적으로 짧아지며 평균 대기 시간이 가장 작다. SJF는 선점형과 비선점형 방식으로 나누어 볼 수 있다.
- Non-preemptive(비선점형) 방식
현재 기다리는 프로세스 중에서 가장 짧게 실행이 되는 프로세스에게 CPU를 넘겨줬을 때, 더 짧은 프로세스가 도착하더라도 CPU를 내놓지 않고, 완료될 때까지 기다렸다가 CPU 제어권을 얻어야 한다.
0초 시점에 CPU를 어떤 프로세스에게 줄 건지 결정을 해야 한다. 근데 도착해있는 프로세스는 1번밖에 없기 때문에 프로세스 1이 CPU를 얻는다. 프로세스 1은 원하는 만큼 CPU를 사용한 후, 7초에 CPU를 반납한다. 7초에 해당하는 시점에 도착한 프로세스를 보니 P2, P3, P4가 모두 도착해 있다. 그중에서 프로세스 3의 실행 시간이 제일 짧으니 프로세스 3을 실행한다. 같은 방식으로 P2 실행 → P4를 실행한다. 이와 같이 비선점형 스케줄링은 프로세스의 작업이 끝나면 다음 스케줄링을 결정한다.
- Preemptive(선점형) 방식
다른 프로세스에게 CPU를 넘겨줬어도 더 짧은 프로세스가 오면 CPU 제어권을 빼앗을 수 있다. 앞으로 남은 시간이 짧은 CPU에게 주며, 비선점형 방식보다 대기 시간이 더 짧다.
0초 시점에는 역시 1번을 실행한다. 실행하다가 프로세스 2가 도착했는데 남은 실행 시간이 더 짧은 프로세스 2에게 CPU가 넘어간다. (프로세스 1은 7-2=5초, 프로세스 2는 4초) 프로세스 2가 실행하다가 마찬가지로 4초에 해당하는 시점에 프로세스 3이 도착하는데 남은 사용 시간이 1초로 가장 짧기 때문에 프로세스 3이 실행된다. 1초 후, 다시 가장 짧은 프로세스 2 실행 → 4번 실행 → 1번 실행한다. 선점형 스케줄링은 프로세스가 도착할 때 다음 스케줄링을 결정한다.
● SJF 스케줄링의 문제점
- Starvation. SJF는 극단적으로 CPU 사용시간이 짧은 프로세스에게 먼저 CPU 제어권을 넘겨 주기 때문에 사용 시간이 긴 프로세스는 사용 시간이 짧은 프로세스가 도착할 때마다 기다릴 수 밖에 없다. 무한정 기다리는 상태가 될 수도 있는 것이다.
- CPU 사용 시간은 미리 알 수 없다. 프로그램이 실행 되다 보면, Input을 받기도 하고 If문의 조건을 타기도 하는데, 내가 CPU를 얼만큼 쓰고 나가는지 정확히 알지 못한다. 실제 시스템에서는 SJF를 사용할 수 없다. (사실 사용할 수 있기는 하다. 프로그램에 따라 과거 CPU burst Time을 이용해서 예측하면 된다. 추정하는 방법으로는 Exponential averaging이 있다.
근데 별로 알고싶지 않다 ....)
● Priority Scheduling
Priority Scheduling은 우선순위가 높은 프로세스에게 CPU 제어권을 넘겨준다. 중간에 CPU를 뺏으면 선점형 스케줄링이며, 빼앗지 못하면 비선점형 스케줄링이다. 보통 정수값으로 우선순위를 표현하고, 작은 숫자일수록 우선순위가 높다.
SJF 스케줄링도 우선순위 스케줄링의 일부라고 할 수 있다. SJF 스케줄링의 경우 CPU 사용 사긴에 따라 우선순위를 정하기 때문이다. Priority Scheduling은 SJF 스케줄링과 같이 우선순위가 낮은 프로세스는 영원히 실행할 수 없을지도 모르는 Starvation 문제가 있다. 이러한 문제를 막기 위해 aging을 해준다. 우선순위가 낮은 프로세스라고 하더라도 오래 기다리게 되면 우선순위를 조금씩 높여주는 것이다. 그렇게 되면 언젠가는 CPU를 얻게 된다.(경로사상... ㅋㅋㅋ)
● RR (Round Robin)
현대적인 시스템에서 사용하는 스케줄링은 Round Robin 기반이다. CPU를 넘겨주기 전에 CPU 할당시간을 정하고 그 시간이 끝나면 Timer Interrupt에 의해 CPU 제어권을 빼앗기고 Ready Queue에 줄을 선다. 장점은 CPU 제어권을 최초로 얻는 시간인 응답 시간이 빨라진다. 어떤 프로세스던지 아주 짧은 시간만 기다리면 적어도 한 번은 CPU를 사용할 수 있다. 어떤 프로세스가 CPU를 오래 쓰는지 모르는 상황에서 굳이 예측할 필요가 없다. 현재 Queue에 n개의 프로세스가 있다고 할 때, 각 프로세스에 주어지는 시간이 q라고 하면 내가 많이 기다려봐야 (n-1) q 만큼의 시간만 기다리면 CPU를 쓸 수 있다. 또 다른 특징은 CPU를 길게 쓰는 프로세스는 기다리는 시간도 길어지고 CPU를 짧게 쓰는 프로세스는 기다리는 시간도 짧아진다. 기다리는 시간은 각 프로세스가 CPU를 사용하려는 시간에 비례하게 된다. 단점은 할당시간을 매우 크게 잡으면 FCFS와 같은 스케줄링 알고리즘이 되어버린다. 지나치게 작은 할당시간이면 계속 CPU를 얻었다가 뺏기는 걸 반복하게 되는데, 이렇게 되면 Context Switchingㄸ 때문에 overhead가 커진다. 따라서 적당한 규모의 Time Quantum(10~100ms)을 주는 것이 좋다.
위 그림은 할당 시간이 20일 때 Round Robin의 구조이다. 프로세스 1→2→3→4→1→2... 반복하다가 burst time을 만족한 프로세스 2가 빨리 빠져나가는 것을 볼 수 있다. Round Robin 스케줄링은 SJF 스케줄링보다 Turn aruond나 waiting time은 길 수도 있으나, Response Time은 짧다.
Round Robin은 기본적으로 CPU 사용시간이 짧은 프로세스와 긴 프로세스가 마구잡이로 섞여있을 때에는 사용하기 좋은 스케줄러이지만, CPU 사용 시간이 비슷하다면 Round Robin에서는 좋은 알고리즘이 아니다. 예를 들어, CPU 사용시간은 100초, Quantum Time은 1초, 프로세스는 4개라고 했을 때 400초가 되는 시점에 거의 동시에 우르르 나가게 될 것이다. Round Robin을 쓰지 않으면 굳이 모든 프로세스가 기다렸다가 한 번에 나갈 필요 없이 하나의 프로세스는 빨리 CPU를 쓰고 나갈 수 있다. 일반적으로 실행시간이 짧은 프로세스랑 긴 프로세스가 섞여있어서 실제로는 Round Robin이 더 효과를 발휘한다.
RR은 Turnaround Time이 아니라 응답 속도가 빠르다는 게 중요한 장점!!
● Multilevel Queue (멀티 레벨 큐)
지금까지의 스케줄링 알고리즘에서는 Ready Queue에 한 줄로 세웠는데 Multilevel Queue나 Multilevel feedback Queue에서는 여러 줄로 줄을 세운다. Ready Queue를 여러 개로 분할하여 foregruond에는 interactive 한 job을 넣고, background에는 no human interactive 한 job을 넣는다.
위에 있을수록 우선순위가 높고 아래 줄에 있을수록 우선순위가 낮다. 시스템과 관련된 프로세스가 가장 우선순위가 높으며 우선순위가 낮은 프로세스들은 starvation이 일어날 수 있다.
어떤 줄한테 CPU를 주며, 그 줄의 Ready Queue의 어떤 프로세스에게 줄 건지 결정해야 한다.
첫 번째는 각 Queue는 독립적인 스케줄링 알고리즘을 가진다. Foreground는 응답 시간을 짧게 해야 하기 때문에 Round Robin 스케줄링을 하고 어차피 CPU만 오랫동안 사용하는 프로세스인 background는 응답 시간이 FCFS 스케줄링을 한다. 응답 시간이 빠르다고 좋은 건 아니며 Context Switch Overhead를 줄이는 게 더 효율적이기 때문이다.
두 번째는 Queue에 대한 스케줄링이 필요하다. 우선순위를 고정하는 방법이 있다. Foreground의 우선순위를 극단적으로 높여 Foreground Queue가 빌 때, Background에 있는 Queue가 돌아가는 스케줄링이다. Foreground Queue가 비지 않으면 Starvation이 발생할 확률이 크다. Starvation의 위험을 방지하기 위한 다른 방법은 시간 단위로 분배하는 것이다. CPU time을 적절한 비율로 각 Queue에 할당한다. 보통 Foreground에 80%, Background에 20%로 보통 Foreground에 더 많은 시간을 투자한다.
- 각 큐는 독립적인 스케줄링 알고리즘
- Foreground : RR
- Background : FCFS
- 큐에 대한 스케줄링이 필요
- Fixed Priority Scheduling (우선순위 고정)
Foreground의 Priority를 극단적으로 높여 Foreground큐가 비면 Background가 돌아가는 스케줄링
Starvation이 발생할 확률이 매우 크다.
- Time slice (시간 단위로 분배)
Fixed Priority 경우 Starvation위험이 있다. 이를 방지해 CPU time을 적절한 비율로 각 큐에 할당한다
예로 Foreground에 80%, Background에 20%. 보통 Foreground에 더 많은 투자를 한다.
● Multilevel feedback Queue
보통은 처음 들어오는 프로세스는 우선순위가 가장 높은 Queue에 집어넣고, 우선순위가 가장 높은 Queue는 Round Robin으로 Time Quantum을 굉장히 짧게 준다. 밑으로 갈수록 Time Quantum을 점점 길게 주며 제일 아래 Queue는 FCFS방식을 사용한다. 맨 위에 있는 Queue에서 할당시간이 끝나게 되면 아래 Queue로 넘어가고 해당 Queue 또 할당 시간이 끝나면 그 아래 Queue로 강등시키는 방식이다. CPU 사용시간이 짧은 프로세스는 도착하자마자 CPU를 써서 바로 빠져나갈 수 있고 CPU 사용시간이 긴 프로세스는 점점 밑으로 이동하게 된다. 아래에 있는 Queue로 갈수록 할당 시간은 더 받게 되지만, Queue 간의 우선순위에서는 위의 Queue의 작업이 끝나야 밑에 있는 Queue가 실행할 수 있다. 멀티 레벨 피드백 큐에서는 CPU 사용 시간이 긴지 빠른지 알 필요가 없으며, 실행 시간이 짧은 프로세스가 우대를 받는다.
지금까지의 스케줄링은 CPU가 한 개였을 때를 말한 것이었다. 다음 포스팅에서는 CPU가 여러 개 있거나, 시간에 대한 Deadlock 제약 조건이 있거나, Thread의 제약 조건이 있을 때의 스케줄링을 다뤄보도록 하겠다.
