운영체제 시리즈 6. CPU Scheduling

CPU-burst time

CPU-burst 분포

• I/O bound process(I/O bound job) : I/O 작업을 많이 하는 프로세스로 사용자로부터 인터렉션(interaction)을 자주 받아가며 프로그램을 수행하는 대화형 프로그램(interactive program)을 의미한다.
• CPU bound process(CPU bound job) : I/O 작업은 거의 하지 않고 CPU를 가지고 빠른 명령을 수행하는 프로그램을 의미한다.

사용자에 대한 빠른 응답이 중요하기 때문에 CPU 스케줄링을 할 때 CPU 버스트가 짧은 I/O bound 프로세스에게 CPU를 우선적으로 사용할 수 있게 하는 스케줄링이 필요하다. 이것은 빠른 응답성 제공과 함께 I/O 장치의 효율성을 높이는 효과가 있다. 

CPU Scheduler

운영체제 안에서 CPU를 스케줄링하는 코드이다. ready 상태의 프로세스 중에서 CPU를 할당할 프로세스를 고른다.

CPU 스케줄링에는 두가지 이슈는 1. 누구에게 우선해서 CPU를 줄 것인지 2. 언제까지 CPU를 사용하게 할 것인지(CPU 사용권을 언제 뺐을 것인지)이다.

CPU 스케줄링이 필요한 경우

1. running -> blocked
2. running -> ready
3. blocked -> ready
4. terminate

1,4의 경우는 사용이 종료되어 자진반납하는 비선점형(nonpreemptive)의 경우이고, 2,3의 경우는 할당시간을 부여한 후 타이머 인터럽트를 발생하는 방법이 대표적은 선점형(preemptive)의 경우이다.

Dispatcher

운영체제에 있는 특정한 코드이다. CPU 제어권을 줄 프로세스를 CPU 스케줄링을 통해서 선정했다면, 선정된 프로세스에게 CPU를 넘겨주는 작업을 하는 코드를 의미한다. 디스패쳐가 하나의 프로세스를 중지하고 다른 프로세스에게 넘기는데 걸리는 시간을 디스패치 지연시간(dispatch latency)라고 하며 문맥교환의 오버헤드에 해당한다.

스케줄링 성능평가

• CPU utilization (이용률) : 전체시간 중 CPU가 일한 시간을 비율로 나타낸 것을 의미한다. CPU를 idle(휴면시간) 상태의 머무르는 것을 최소한으로 하는 것이 중요 목표이다.
• Throughput (처리량) : 주어진 시간에 완료한 일의 양을 뜻한다. 주어진 시간 동안 준비 큐에서 완료한 프로세스를 나타낸다.
• Turnaround time (소요시간, 반환시간) : CPU를 요청하고부터 다 쓰고 나간 시간을 의미한다. (준비 큐에서 기다린 시간 + CPU 사용시간)
• Waiting time (대기시간) : 준비 큐에서 CPU를 사용하기 위해 기다린 시간의 총합을 의미한다.
• Response time (응답시간) : 준비 큐에서 처음으로 CPU를 사용할 때까지 걸린 시간을 의미한다.

CPU 스케줄링 알고리즘

선입선출, FCFS(First-Come First-Served)

프로세스가 준비큐에 들어온 순서대로 할당해주는 방식이다. 먼저 도착한 프로세스의 성격에 따라 평균 대기시간이 달라지는 현상이 발생한다. CPU 버스트가 긴 프로세스가 먼저 들어온다면 평균 대기시간이 길어지게 된다. 이것은 콘보이 현상(Convoy effect)라고 하며 FCFS의 대표적인 단점이다. 

최단작업 우선, SJF(Shortest-Job First)

CPU 버스트가 짧은 프로세스에게 먼저 CPU를 할당하는 방식이다. preemptive인 경우, 가장 짧은 평균 대기시간을 확보할 수 있다. 

 

• Nonpreemptive인 경우 : CPU를 확보하면 더 짧은 프로세스가 들어오더라도 완료될 때까지 보장한다.
• Preemptive인 경우 : CPU를 확보했다고 하더라도 더 짧은 프로세스가 들어오면 CPU를 뺐기게 된다. 이것을 SRTF(Shortest Remaining Time First)라고 한다. CPU 버스트가 긴 프로세스의 경우, 짧은 프로세스가 계속 들어오면 CPU를 사용하지 못하고 무한정 기다리게 될 수도 있다. 이것을 기아현상(Starvation)이라고 한다. 더불어 과거를 통해 예측은 가능하지만 본인이 언제 완료하고 나갈 수 있을지 미리 예측할 수 없다.

우선순위, Priority Scheduling

준비큐에서 기다리는 프로세스 중에서 우선순위가 가장 높은 프로세스에게 CPU를 할당하는 방식이다. 우선순위 값(priority number)을 표기하여 우선순위를 나타내며, 값이 작을수록 우선순위가 높다. CPU 버스트 값으로 우선순위를 매긴다면 SJF 알고리즘과 동일하다. nonpreemptive 경우와 preemptive 경우를 나눌 수 있다. preemptive 경우에 우선순위가 높은 프로세스가 들어온다면 starvation이 발생할 수 있다. 이 문제를 해결하기 위해 노화(aging) 기법을 사용할 수 있다. 노화기법이란 오래 기다리면 우선순위를 조금씩 높여주는 것을 의미한다.  

라운드 로빈, RR(Round Robin)✨

현대적 컴퓨터 시스템은 라운드 로빈에 기반한다고 한다. 라운드 로빈은 각 프로세스가 CPU를 사용할 수 있는 시간을 제한하여 그 시간이 경과하면 CPU를 회수해 다른 프로세스에게 넘겨준다. CPU를 뺐긴 프로세스는 준비큐의 마지막으로 들어가게 된다. 프로세스마다 할당된 최대 시간(time quantum)이 너무 길면 FCFS와 같아지고, 너무 짧으면 문맥교환의 오버헤드가 커져 전체적인 성능이 떨어지게 된다. 

 

응답시간이 빠르며, 어떤 프로세스가 CPU를 오래 사용할지 모르는 상황에서 CPU 버스트가 짧은 프로세스는 빠르게 사용하고 나갈 수 있다. 반면 CPU 버스트가 긴 프로세스는 대기시간이 길어지게 된다. 즉, 대기시간은 본인의 CPU 사용시간에 비례하게 된다. 정리하자면 전체적인 응답시간이 빠르지만, 프로세스의 CPU 사용량이 많으면 소요시간, 대기시간이 길어진다.

SJF 보다 평균 소요시간은 길지만, 응답시간은 짧다. CPU 사용시간이 모두 동일하다면 마지막까지 CPU 사용시간을 쪼개서 사용하기 때문에 소요시간이 모두 길어진다. 하지만 일반적으로 CPU 버스트가 다른 작업들이 섞여있기 때문에 장점이 크게 작용한다.

멀티레벨 큐(Multilevel queue)

준비큐를 여러개로 분할하여 관리하는 스케줄링 기법을 의미한다. 프로세스의 특성에 따라 다른큐를 사용하고 큐마다 성격에 맞는 CPU 스케줄링 기법을 적용할 수 있다. 멀티레벨 큐에서는 어떤 큐에게 먼저 CPU를 할당할지 결정하는 스케줄링이 필요하다. 상위 큐일수록 우선순위가 높고 interactive한 프로세스가 들어가고 라운드 로빈 알고리즘을 사용한다. 하위 큐로 갈수록 CPU 버스트가 긴 프로세스들이 있고 FCFS 알고리즘을 사용한다. 고정순위방식(큐에 고정적으로 우선순위를 두어 진행)이나 타임슬라이싱(각 큐에 CPU를 적절한 비율로 배정) 방식을 사용한다. 다만 고정순위방식을 사용하면 하위 큐에는 CPU가 할당되지 못하는 기아현상이 발생할 수 있다. 

멀티레벨 피드백 큐(Multilevel feedback queue)

여러 개의 준비큐를 둔다는 것은 멀티레벨 큐와 같으나 프로세스가 큐 간의 이동이 가능하다는 점에서 다르다. 다양한 프로세스의 성격을 반영하여 큐의 수, 각 큐의 스케줄링 알고리즘, 프로세스를 상위 큐로 승격 및 하위 큐로 강등시키는 기준, 프로세스가 들어갈 큐를 결정하는 기준 등으로 멀티레벨 피드백 큐를 정의한다. 처음 들어오는 프로세스는 상위 큐에 넣고 할당시간을 짧게 준다. 할당시간에 작업이 끝나지 않으면 더 낮은 우선순위를 가진 큐로 내려가고 할당시간이 좀 더 늘어난다. 작업시간이 짧은 프로세스일수록 우대받는 시스템이다.

---

Mutil-Processor Scheduling

위에서 정리한 스케줄링은 단일 프로세서인 경우이다. CPU가 여러개인 시스템을 다중처리 시스템이라고 한다. 다중처리 시스템 스케줄링은 더 복잡하다. 일부 프로세서에게 일이 몰리지 않도록 부하균형(load sharing)이 필요하다. 프로세서 마다 별개의 큐를 둘 수도 있고, 공동 큐를 지정해 사용할 수도 있다. 각 프로세서가 알아서 스케줄링을 결정하는 대칭형 다중처리(SMP:Symmentric Multi-Processor)와 하나의 CPU가 모든 CPU 스케줄링과 데이터 접근을 책임지고 관리하는 비대칭형 다중처리(Asymmentric Multi-Processor)로 구분된다.

Real-Time Scheduling

실시간 시스템에서는 주어진 데드라인에 정해진 작업을 완료해야 한다. 경성 실시간 시스템(hard real-time system)과 연성 실시간 시스템(soft real-time system)으로 나뉜다. hard real-time system은 정해진 시간안에 반드시 작업이 완료되도록 스케줄링해야 한다. 예를 들면 미사일 발사, 원자로 제어 시스템이 있다. soft real-time system은 데드라인이 존재하기는 하지만 지켜지지 않아도 위험한 상황이 발생하지는 않는 경우로 일반 프로세스에 비해 높은 우선순위를 갖도록 한다. 그 예로는 영화 스트리밍 시스템이 있다.  

Thread Scheduling

Local과 Global로 나눠볼 수 있다. local scheduling은 사용자 수준에서 thread 간의 스케줄링을 하는 것이고, global scheduling의 경우는 커널 레벨에서 커널의 단기 스케줄러가 thread 간의 스케줄링을 하는 것을 의미한다.

알고리즘 평가

큐잉 모델(Queueing model)

이론적인 모델로 확률분포를 통해 프로세스들의 도착률과 처리율을 통해 수학적으로 계산하여 성능지표를 구하는 방식이다.

구현 및 실측(Implementation & measurement)

큐잉모델과 반대로 실제 시스템 알고리즘을 구현하여 수행하고 실제 작업에 대한 성능을 측정하여 비교하여 알고리즘에 대한 성능을 측정하는 방식이다.

시뮬레이션(Simulation)

실제 시스템에 구현하여 실행시켜보는 것이 아니라 가상으로 모의 프로그램을 작성 후 CPU 요청을 입력값으로 넣어 결과를 가지고 알고리즘 성능을 측정하는 방식이다. 입력값은 가상으로 생성할 수도 있고 실제 시스템에서의 CPU 요청내역을 추출하여 사용할 수도 있다. 실제 시스템에서 추출한 입력값을 트레이스(trace)라고 부른다.

정리

CPU를 다양한 프로세스에게 할당하여 효율적으로 관리하기 위해서는 CPU 스케줄링이 필요하다. 보통 CPU 버스트(CPU 사용시간)에 따라 관리한다. CPU 스케줄링에서 현대 가장 많이 사용되는 것은 라운드 로빈이다. CPU 사용에 제한시간을 두어 CPU 버스트가 짧은 프로세스를 우선하되 긴 프로세스도 기아현상이 발생하지 않도록 관리한다. 전체적으로 짧은 응답시간을 가지고 프로세스의 CPU 사용시간이 길수록 더 오래 기다리게 되고 소요시간이 길어진다. 여러개의 준비큐를 두어(멀티레벨 큐) 큐 간에 다른 스케줄링으로 CPU를 관리하기도 한다. 

 

운영체제 시리즈는 반효경 교수님의 운영체제 강의 와 "운영체제와 정보기술의 원리"라는 책을 바탕으로 정리한 내용입니다.