[운영체제] 현대 컴퓨팅은 왜 라운드 로빈을 쓸까?(feat.CPU 스케쥴링 알고리즘 정리)

본격 취준 프로세스에 들어서니 확실히 블로그에 글쓰기가 게을러진다. 블로그에 정리할 시간에 하나라도 더 공부해야되지 않나 하는 조급함이 앞서서인데, 사실 다 핑계다. 이전처럼 매일은 아니더라도 1주일에 한 편은 쓰는 식으로 루틴을 확립해야 할 듯.

 

공부한 내용은 노션에 총 집대성하는 식으로 정리하고 있지만 그와 별개로 공개하는 글을 쓰는 건 확실히 더 큰 배움을 준다. 나 혼자만 이해하는 내용이 아니라 남에게도 이해를 시켜야 하기 때문이다. (갑자기 든 생각인데 노션에 글을 쓰면 티스토리에 자동 배포할 수 있는 오픈소스가 있다면 진짜 어메이징하겠다 싶네..함 찾아봐야겠다.)

 

오늘은 다음주 있을 기술면접에 대비해 개념 총정리를 진행하고 있다. 그 중에서도 운영체제에 집중하고 있는데, CPU 스케쥴링에 대해서 간략하게 정리해볼까 한다.

 

목차

• Performance Index
  • System view
    • CPU utilization(CPU 이용률: 전체 시간 중 CPU를 사용한 시간의 비중)
    • Throughput(처리량: 주어진 시간 동안 얼마나 많은 프로세스를 처리했는가?)
  • Process view
    • Turn-around time(프로세스가 CPU 자원을 받아서 사용하고 반환하기까지 걸린 시간)
    • Waiting time(프로세스가 CPU를 쓰기 위해 ready queue에서 기다리는 전체 시간)
    • Response time(프로세스가 ready queue에 진입해서부터 시작해 맨 처음으로 CPU를 사용하기까지 기다린 시간)
• CPU 스케쥴링 알고리즘
  • FCFS(First-Come First-Served)
  • SJF(Shortest Job First)
  • Priority Scheduling
  • Round Robin(RR)
• 왜 현대 컴퓨팅에서는 스케쥴링 알고리즘으로 RR을 사용할까?

 

Performance Index

퍼포먼스를 측정하는 지표를 뜻한다. 여기서 퍼포먼스는 다양하게 바라볼 수 있는데, 컴퓨터 시스템 전체 관점(숲)에서 볼 수도 있고 프로그램에 한정해서(나무) 볼 수도 있다. 무엇이 정답이라고는 할 수 없으며 각 지표 간에는 tradeoff 해야 하는 관계가 발생할 수 있음을 유념하자.

 

시스템 입장에서 성능 척도

1. CPU utilization(CPU 이용률)

전체 시간 중 CPU가 놀지 않고 일한 시간에 대한 비율을 뜻한다. CPU는 비싼 자원이므로 가능한 일을 많이 시킬 수록 효율이 좋다.

 

2. Throughput(처리량)

주어진 시간 동안 몇 개의 프로세스를 완료했는지 측정하는 지표. 전체 시스템 관점에서는 당연히 최대한 많이 처리할수록 좋다.

 

 

프로세스 입장에서 성능 척도

단일 프로세스 입장에서는 CPU를 최대한 빨리 얻어서 빨리 작업하고 끝내는 게 좋다. 따라서 시간 관련 척도가 많다.

1. Turn-around time(소요시간, 반환시간)

프로세스가 CPU를 쓰러 와서 다 쓰고 나갈 때까지 걸린 시간을 뜻한다. 보다 엄밀하게는 "CPU burst를 시작해서 I/O wait하기 까지 걸린 시간"을 말한다. 여기서 주의해야 할 점은 전체 프로세스 스케쥴 관점이 아니라 특정한 하나의 프로세스가 CPU를 잡고 놓을 때까지라는 점이다.

 

2. Waiting time(대기 시간)

하나의 프로세스가 처음 ready queue에 들어왔을 때부터 작업을 완료하고 queue를 빠져나가는 사이에 CPU를 쓰기 위해 ready queue에서 기다리는 전체 시간을 말한다. 이렇게 주절주절 적은 이유는 아래 설명할 response time과 혼동하지 않기 위해서다.

 

3. Response time(응답 시간)

어떤 프로세스가 처음 ready queue에 들어와서 처음으로 CPU 자원을 얻기까지 걸린 시간을 말한다. waiting time과 다른 점은, waiting time의 경우 중간에 CPU를 빼앗겼다가(선점 가능한 경우) 또 다시 줄서서 기다리는 등 CPU burst time 동안에도 CPU를 반납하고 다시 ready queue에 줄서서 기다리기를 반복한다. 즉, ready queue에 상주하는 total time이 waiting time인 것. 반면, response time은 토탈이 아닌 프로세스가 처음으로 CPU를 잡기까지 걸린 시간을 뜻한다. 이 개념을 잘 알아둬야 뒤에 설명할 CPU 스케쥴링 알고리즘 간 tradeoff에 대해 보다 명확히 이해할 수 있을 것이다.

 

 

CPU 스케쥴링 알고리즘

1. FCFS(First-Come First-Served)

먼저 온 프로세스 순서대로 스케쥴링하는 알고리즘으로, 구현하기는 간단하나 실행 시간이 긴 프로세스가 먼저 배정되면 waiting time이 길어지는 문제가 발생한다.

 

큐(queue)에서 배운 것처럼 FIFO(First In First Out)과 동일한 로직으로, 먼저 들어간 프로세스가 먼저 CPU 자원을 얻는다. 무조건 줄 선 순으로 자원을 얻는 것이 포인트. 여기서 FCFS는 비선점 방식에 해당하는데, 프로세스가 한 번 CPU를 할당받으면 작업이 끝나기 전까지는 그 누구도 CPU 자원을 뺏을 수 없다.

 

이 알고리즘은 구현이 간단하다는 장점 외에는 단점이 훨씬 많은 알고리즘이다. 대표적인 단점으로는 convoy effect가 있다. convoy effect란, 실행 시간이 긴 프로세스가 짧은 프로세스보다 먼저 할당되면 기다리는 시간이 길어져 효율성이 떨어지는 효과를 말한다. 작업 시간이 1초짜리인 프로세스와 100초짜리인 프로세스가 있다고 하자. 스케쥴링 순서에는 두 가지 방식이 있다.

 

1) 1-> 100

2) 100 -> 1

 

1)번의 경우, 1초짜리 프로세스가 먼저 오고 다음에 100초짜리가 작업하므로 각 프로세스의 waiting time은 0초, 1초이다. 반면 2)를 보자. 100초짜리가 먼저 CPU를 할당받았고 해당 알고리즘은 비선점 방식이므로 100초짜리가 끝나기 전까지는 1초짜리가 CPU를 얻을 수 없다. 따라서 각 프로세스의 waiting time은 0, 100초에 해당한다. 즉, 1)과 2)의 total waiting time 차이는 100배에 달한다. 이를 보완하고자 등장한 것이 바로 아래의 SJF(Shortest Job First), 작업 시간이 짧은 애가 먼저 진행하는 알고리즘이다.

 

2. SJF(Shortest Job First)

CPU burst time이 가장 짧은 프로세스를 가장 먼저 스케쥴링하는 알고리즘으로, 가장 최소한의 average waiting time을 보장한다.

 

CPU time이고 뭐고 그냥 먼저 온 사람부터 차례로 자원을 할당하는 FCFS에서 발생하는 convoy effect 문제를 해결하기 위해, 줄 선 것과 상관없이 CPU 사용 시간(CPU burst time)이 가장 짧은 프로세스한테 가장 먼저 CPU 자원을 배정한다. 이렇게 처리하면 queue가 전체적으로 더 빠르게 줄어든다. 이를 통해 주어진 프로세스에 대해 가장 최소한의 average waiting time을 보장하는 알고리즘이다.(가장 최소한의 average waiting time을 보장하는 것은 수학적으로 증명된 사실임!) 

 

SJF를 구현하는 방식에는 두 가지(비선점, 선점)가 존재한다.

 

1. 비선점(Non-Preemptive)

 

비선점 방식의 경우, 프로세스가 일단 CPU를 잡고 나면 cpu burst가 완료될 때까지 다른 프로세스에게 cpu를 빼앗기지 않는 방식이다. 이 경우 CPU 스케쥴링은 언제 일어날까? 하나의 프로세스가 작업을 마치고 CPU를 반환하는 시점에 탐색을 진행해 ready queue에 있던 애들 중 줄 순서와 상관없이 cpu burst time이 가장 짧은 애를 꺼내 CPU를 제공한다.

 

2. 선점(Preemptive)

 

현재 수행 중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 갖는 새로운 프로세스가 도착하면 수행 중인 프로세스로부터 CPU를 빼앗아 새로운 프로세스가 선점할 수 있도록 한다. 빼앗긴 프로세스는 ready queue의 맨 뒤로 가서 줄을 선다. CPU 스케쥴링 시점은 하나의 프로세스가 끝나는 시점(이건 Non-Preemptive)이 아니라 프로세스가 진행되는 중간에도 새로운 프로세스가 ready queue에 진입하는 시점에 탐색을 진행해 스케쥴링한다. 따라서 비선점 방식에 비해 더욱 최적화된 average waiting time을 보장한다.

 

좋은 말만 주루룩 있는데, 그럼 이 알고리즘의 단점은 없을까? 있다.

 

1. Starvation: 이 알고리즘은 CPU burst time이 극단적으로 짧은 애를 선호하기 때문에(일종의 greedy) cpu time이 긴 애들은 마냥 손가락 빨며 기다려야 하는 문제가 발생한다. 최악의 경우, CPU time이 짧은 애들이 쉬지 않고 계속해서 들어오면 상대적으로 time이 긴 작업은 평생 CPU 근처에도 가보지 못하게 된다.

 

2. CPU burst time을 예측할 수 없음: 프로세스는 자기가 CPU 얼마 정도 쓰고 갈게요~라고 명시해놓지 않는다. 따라서 운영체제는 해당 프로세스가 CPU를 얼마나 쓰고 갈 것인지 사전에 알 수 없다. 아니, 그러면 애초에 SJF 자체가 돌아갈 수 없는 것 아닌가? 싶은데 정확히는 추정한다고 한다. 과거에 해당 프로세스가 CPU를 얼마나 사용했는지 기록해두고 이를 바탕으로 추정한다.

 

 

3. Priority Scheduling

우선순위가 가장 높은 프로세스에게 CPU를 먼저 배정한다.

 

운영체제는 각 프로세스에게 우선순위를 나타내는 integer 값을 배정한다. 이 값이 작을수록 높은 우선순위를 갖는다. 사실 위의 1, 2도 priority scheduling의 일부라고 볼 수 있는데, 각각의 우선순위 기준이 1) 먼저 왔는가 2) CPU burst time이 짧은가 로 정해져있을 뿐이다. 하지만 여기서는 약간 다른 점이 있다.

 

Priority Scheduling을 구현하는 방식 역시 두 가지(비선점, 선점)가 존재한다.

 

1. 선점(Preemptive)

 

수행 중인 프로세스보다 우선순위가 더 높은 프로세스가 들어오면 해당 프로세스에게 CPU를 넘겨준다.

 

2. 비선점(Non-Preemptive)

 

우선순위가 더 높은 프로세스가 들어오더라도 해당 작업이 끝나기 전까지는 CPU를 넘겨주지 않는다.

 

결국 2랑 차이가 그닥 없는데? 맞다. 따라서 문제점 역시 starvation이 동일하다. 또한 SJF에서 CPU burst time을 예측할 수 없었던 것처럼, 어떤 걸 우선순위로 두냐에 따라 특정 기준에 해당하는 문제 역시 발생할 것이다.

 

하지만 우선순위가 밀리는 것이 문제라면 이 역시 해결책이 있다. 바로 Aging으로, 아무리 우선순위가 낮은 프로세스더라도 기다리는 시간이 길어질 때마다 우선순위를 높여 우선순위가 낮은 프로세스가 작업을 못하고 마냥 기다려야 하는 문제를 해결한다.

 

지금까지 길게 설명했으나, 아이러니하게도 현대 컴퓨팅에서 쓰는 스케쥴링 방식은 위 셋 어느 것도 포함하지 않는다. 바로 아래 알고리즘이다.

4. RR(Round Robin)

각 프로세스는 동일한 크기의 할당 시간(time quantum)을 갖는다. 할당 시간이 지나면 진행 중이던 프로세스는 CPU를 다음 프로세스에 선점당하고 ready queue의 맨 뒤로 가서 줄을 선다.

 

어라, 다시 맨 처음으로 돌아갔다. 일종의 FCFS인데, 다만 FCFS와 차이점은 선점형이라는 점, 또한 priority scheduling과 같이 특정 우선순위가 있는 게 아니라 모든 프로세스에 대해 동일하게 시간 조각을 배분한다는 점이 다르다. 즉, n개의 프로세스가 ready queue에 있고 할당 시간이 q time unit인 경우 각 프로세스는 최대 q time unit 단위로 CPU 전체 시간의 1/n을 얻는다.

 

이렇게 알고리즘을 구현할 경우, 장점은 무엇일까?

 

장점: 응답 시간(Response time)이 짧아진다

 

위의 Index 설명에서 응답 시간은 프로세스가 queue에 진입해서 맨 처음으로 CPU 잡기까지 기다리는 시간이라고 했다. 만약 n개의 프로세스가 ready queue에 줄 서있고, 각 프로세스 당 q 만큼의 time quantum이 배정된다고 하면, 제일 마지막 n번째 프로세스조차도 (n-1)q 이상 기다리지 않아도 된다. 즉, 모든 프로세스의 응답 시간이 (n-1)q를 넘지 않는다.

 

근데 이게 왜 좋지? 응답 시간이 짧으면 뭐가 좋을까? 사용자 경험이 좋아진다. 생각해보자. 멀티프로그래밍에서 사용자는 동시에 여러 개의 프로그램을 돌리고 있다. 이때, 특정 하나의 프로그램만 잘되고 나머지는 먹통이라 엄청 오래 기다려야 한다면 어떨까? 속이 터질 것이다. 결국 멀티프로그래밍에서 최적의 사용자 경험을 제공하기 위해서는 각 프로그램이 조금씩, 하지만 모두 다 프로세스가 동작할 수 있도록 CPU를 골고루 배분할 필요가 있다. 즉, 현대 컴퓨팅에서 RR을 쓰는 이유는 멀티프로그래밍 환경에서 최적의 사용자 경험을 제공하기 위해서이다.

 

이 RR 알고리즘의 퍼포먼스는 time quantum q의 크기에 따라 좌우된다. 만약 q가 매우 크다면 어떨까? 사실상 FCFS와 다를 바가 없어진다. 반대로 q가 작다면? 서로 다른 프로세스에 대해 CPU를 계속 갈아끼워야 하므로 context switch가 매우 빈번하게 일어나 오버헤드가 커진다. 따라서 둘 사이의 적당한 q가 필요할 것이다. 그러면 이 RR 알고리즘 역시 무조건 좋을까? 그렇지 않다.

 

단점: CPU burst time이 긴 프로세스만 queue에 들어오면 효율이 떨어진다.

 

일반적으로 Response time이 짧아지는 이점이 있으나 SJF보다는 Turn-around time, Waiting time이 길어진다. 그러면 무슨 문제가 발생할까? 엣지 케이스를 하나 살펴보자.

 

만약 CPU burst time이 100초인 애들이 ready queue에 100개 들어와있고 time quantum q는 1초이다. 이 경우, RR로 돌리면 어떤 일이 일어날까?

 

FCFS의 경우 한 번에 하나씩 처리하므로 100초 단위로 완료된 작업이 하나씩 나올 것이다. 반면, RR은 100개의 작업에 대해 1초씩 게속해서 돌면서 작업한다. 위 작업의 경우 10000초면 모두 끝날 것이다. 그런데 FCFS와 달리 9900초까지 아무 일도 일어나지 않다가 9900초가 되는 시점부터 1초에 하나씩 작업이 완료되어 마지막 100초 때 모든 작업이 완료된다. 즉, RR은 CPU burst time이 긴 프로세스만 queue에 들어오면 효율이 떨어진다.

 

왜 현대 컴퓨팅에서는 RR을 스케쥴링 알고리즘으로 사용할까?

 

그럼에도 RR을 쓰는 이유가 한 가지 더 있다. 실제 컴퓨팅 환경에서 CPU-burst time의 분포를 살펴보자.

 

 위 그래프를 보면 x축이 burst duration(CPU 작업에 걸리는 시간), y축이 빈도를 뜻한다. CPU bound job에서는 CPU를 많이 쓰는 대신 빈도수가 낮고 I/O bound job에서는 CPU를 짧게 쓰는 대신 CPU를 사용하는 빈도가 높다. 즉, time이 긴 job과 짧은 job이 여러 개로 섞여있다는 것! 이 중에서도 I/O bound job은 대개 사람과 인터랙션하는 성격을 띄고 있어 빠르게 해결해줄 수록 사용자 경험이 좋아진다. 이러한 특성이 있기 때문에 현대 컴퓨팅에서 RR을 쓰는 것이라고까지 이해하면 100점!