OS 4. CPU Scheduling

출처 : KOCW 운영체제-반효경

Cpu scheduling

여러 종류의 job(=process)이 섞여 있기 때문에 CPU 스케줄링이 필요하다. job은 CPU bound job 과 I/O bound job으로 나뉜다. I/O bound job은 cpu를 잡고 계산하는 시간보다 I/O에 많은 시간이 필요한 job이고 CPU bound job 은 계산 위주의 job이다. CPU scheduling이 필요한 것은 CPU bound job 보다 I/O bound job의 영향이 크다. I/O bound job 은 interactive job이다. 사람과 interaction을 하는 job이기 때문에 response가 느리면 문제가 될 수 있다.(사람이 답답해 할 수 있다?)
CPU 를 공평하게 나눠주는 것 보다 CPU를 효율적으로 사용하는 것, 가능하면 사람과 상호작용하는 job에게 cpu 를 우선적으로 주는 것이 더 중요하다. 이러한 점이 cpu scheduling의 주요 필요성이다.
결국 Cpu scheduling의 주요 문제는 누구에게 cpu 우선순위를 줄 것인가?, cpu를 얼마동안 줄 것인가? 이다.

CPU scheduler & Dispatcher

Cpu scheduler 는 ready 상태의 프로세스 중에 어떤 프로세스에 cpu를 줄지 결정하는 커널 코드이고 Dispatcher는 cpu의 제어권을 cpu scheduler 에게 넘기는 커널 코드이다. 즉, dispatcher 는 context switch를 수행한다.
Cpu scheduling이 필요한 경우는 프로세스 에게 다음과 같은 상태 변화가 있는 경우이다.
1. Running -> blocked(ex : I/O 요청하는 시스템 콜)
2. Running -> ready(ex : timer interrupt)
3. Blocked -> ready(ex : I/O 완료 후 interrupt -> 해당 프로세스가 우선순위가 높을 경우 cpu제어권이 넘어갈 수 있음)
4. Terminate
1, 4 는 nonpreemptive(강제 x 자진 반납) 비선점형
나머지 preemptive(강제로 뺏음) 선점형

Scheduling criteria(=performance index, performance measure)

scheduling의 성능을 측정하는 것은 크게 시스템 입장에서의 성능척도, 프로그램 입장에서의 성능척도로 나눌 수 있다.
시스템 입장에서의 성능척도는 CPU utilization, Throughput 이다. CPU utilization은 말 그대로 cpu를 얼마나 놀지않고 빡빡하게 사용했는지 에 대한 것이고, throughput은 단위시간 당 완료한 process의 개수이다. 여기서 process를 완료한다는 것은 종료를 의미하는 것이 아니라 다음 I/O 요청까지의 process 작업을 의미한다.
프로그램 입장에서의 성능척도는 turnaround time, waiting time, response time 이다. Turnaround time 은 process가 ready queue에 들어와서 완료될때까지 걸린 총 시간이고 waiting time은 turnaround time에서 ready queue에서 기다린 시간의 합이고 response time은 process가 ready queue에 들어와 최초로 cpu를 받는데 까지 걸리는 시간이다. 마찬가지로 process가 완료되었다는 것은 I/O 요청까지의 process 작업을 의미한다.

Scheduling Algorithm

1. FCFS(First-Come First-Served)
   프로세스의 우선순위를 도착순서에 둔 알고리즘이다. 일단 하나의 프로세스가 cpu를 잡으면 완료될때까지 cpu를 놓치 않기때문에 nonpreemptive algorithm으로 분류된다. Waiting time, response time 측면에서 비효율적인 알고리즘이다. 긴 프로세스로 인해 뒤에 온 짧은 프로세스의 waiting time이 늘어나는 것을 Convoy effect라고 한다.

• Convoy effect : short process behind long process

2. SJF(Shortest-Job-First)
   FCFS 의 Convoy effect를 해결한 알고리즘으로 프로세스의 우선순위를 CPU burst time이 가장 짧은 프로세스에게 준다. SJF에서도 2개로 나뉘는데 Nonpreemitive한 방식과 preemitive한 방식이다. nonpreemitive한 방식은 cpu를 일단 잡으면 cpu burst가 완료될 때까지 cpu를 빼앗기지 않는다. 반면에 preemitive한 방식은 현재 수행중인 프로세스의 남은 burst time보다 짧은 cpu burst time을 가진 새로운 프로세스가 도착하면 cpu를 빼앗긴다. 이 방식을 Shortest-Remain-Time-First(SRTF)라고도 불리며 minimum average waiting time을 보장한다.
   SJF는 두 가지 단점이 있다.
   첫번째 단점은 starvation이다. 우선순위가 낮은 프로세스는 waiting time이 굉장히 오래걸리고 극단적인 상황에서 아예 받지 못할 수도 있다. 해결책으로는 Aging을 통해 ready queue에 머문 시간에 따라 priority를 점점 낮춰주는 방법을 들 수 있다.
   두번째 단점은 CPU burst time을 미리 알 수 없다는 것이다. 프로그램이라는 것이 어떤 입력을 받아서 실행되기도 하고 조건문을 만족을 하느냐 안하느냐에 따라 branch가 뻗어나가는 등 수많은 변수가 존재한다. 하지만 프로세스 마다 어느정도의 패턴을 보이기 때문에 어느정도 추정은 가능하다. 과거의 cpu burst time을 exponential averaging 해서 추정하게 된다.
   

• Priority Scheduling
  각 프로세스에 priority number(integer)를 부여하고 highest priority를 가진 process에 cpu를 할당한다. 보통 priority number가 작은 프로세스가 우선순위가 높다. 프로세스가 ready queue에 들어올때마다 우선순위를 통해 프로세스를 교체하는 것을 preemptive, 프로세스가 완료될때마다 우선순위를 판단는 것을 nonpreemptive라고 볼 수 있다. 위의 SJF 또한 priority scheduling의 일종이다. 문제점으로는 우선순위가 낮은 프로세스가 cpu를 할당받지 못하는 문제인 starvation이 일어날 수 있다는 것이고 이에 대한 해결책으로는 대기 시간에 따라 우선순위가 증가하는 aging기법이 있다.

3. RR(Round Robin)
   각 프로세스는 동일한 크기와 할당 시간(time quantum)을 가진다. (일반적으로 10 ~ 100miliseconds) 할당시간이 지나면 프로세스는 선점당하고 ready queue의 제일 뒤에 가서 다시 줄을 선다. n개의 프로세스가 ready queue에 있고 할당시간이 q time unit인 경우 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않는다. q가 커질수록 FCFS 에 가까워지고 q 가 너무 작아지면 context switch에 의한 overhead가 증가하여 문제가 될 수 있다. RR은 waiting time이 cpu burst time에 비례하게 된다는 특징을 가진다. 또한 일반적으로 SJF보다 turnaround time이 길다. 장점으로는 response time이 짧다는 것을 들 수 있다. RR의 경우 cpu burst time이 동일한 homogeneous한 프로그램에서는 turnaround time, average waiting time 이 굉장히 커지는 문제가 발생할 수 있지만 보통의 경우 cpu 사용시간이 다양한 heterogeneous한 프로그램이 마구잡이로 섞여있는 경우 이기때문에 크게 걱정하지 않아도 된다.

Multilevel Queue

기존에는 cpu를 기다리는 줄이 하나만 존재하였는데 cpu를 기다리는 줄을 여러개 둔 것을 multilevel queue라고 한다. 보통 줄에 따라 우선순위를 두게된다. Multilevel queue의 중요한 쟁점은 프로세스를 어떤 queue에 넣을 것인가, queue의 우선순위를 어떻게 둘것인가, 각 queue 내에서는 어떤 scheduling을 둘것인가 와 같은 것들이 있다. 이 중 queue의 우선순위를 두는 방식 두 가지를 들 수 있는데 하나는 고정된 우선순위를 두는 것이다. 이렇게 되면 우선순위가 낮은 queue는 cpu를 할당 받지 못하는 starvation 문제가 발생할 수 있다. 다른 하나는 이를 해결한 방법인 time slice이다. cpu time을 적절한 비율로 각 queue에 할당하는 방법이다. 높은 우선순위의 queue 에 상대적으로 더 많은 비율로 시간을 할당해주게 된다.

Multilevel Feedback Queue

Multilevel Queue 와 다르게 프로세스가 다른 큐로 이동이 가능한 방식이다. 이와 같은 방식을 사용하면 Multilevel Queue 의 starvation 문제를 aging 기법을 통해 해결할 수 있다. Multilevel-feedback-queue scheduler를 정의하는 파라미터는 여러가지가 있다.
1. # of Queue
2. 각 queue의 scheduling algorithm
3. Process를 상위 큐로 보내는 기준
4. process를 하위 큐로 보내는 기준
5. porcess가 cpu 서비스를 받으려 할 때 들어갈 큐를 결정하는 기준

위 와 같은 방식은 CPU burst time 이 짧은 프로세스일 수록 더 높은 우선순위를 주는 알고리즘이다. 또한 CPU burst time을 추정할 필요도 없다.

그 외의 여러가지 scheduling

1. Multiple-Processor Scheduling
   CPU가 여러 개인 경우의 scheduling을 의미한다.

   Homogeneous processor인 경우 Queue에 한줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있다. 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우에는 문제가 더욱 복잡해진다. 이러한 프로세스로 인해 특정 프로세서에 부하가 몰릴 수 있다. 그렇기때문에 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘이 필요하다. 이를 Load sharing이라고한다. 각 cpu마다 queue를 두는 방법, 공동의 queue를 사용하는 방법이 있을 수 있다.
   프로세서가 각자 scheduling 할 수도 있고 하나의 프로세서가 전담해서 scheduling 할 수도 있다. 전자는 Symmetric Multiprocessing(SMP)(모든 프로세서가 대등하다), 후자는 Asymmetric multiprocessing이라고 한다.

2. Real-Time Scheduling
   Real-Time job 의 scheduling은 보통 deadline이 정해져 있기 때문에 수시로 scheduling하지 않고 미리 scheduling하여 deadline을 보장하도록 하는 것이 일반적이다. 반드시 real time이 보장되어야 하는 것이 Hard real-time systems이라고 하고 일반 프로세스에 비해 높은 priority를 갖도록하는 soft real-time computing 이라고 한다.

3. Thread Scheduling
   User level thread 의 경우 어떤 thread에게 cpu를 줄지를 process 내부의 thread library에 의해 결정된다. 이를 Local Scheduling이라고 한다.
   Kernel level thread의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 thread에게 cpu를 줄지 결정한다. 이를 Global Scheduling이라고 한다.

Algorithm Evaluation

1. Queueing models
   
   확률 분포로 주어지는 arrival rate와 service rate 등을 통해 performance index 값을 계산
2. Implementation(구현) & Measurement(측정)
   실제 시스템에 알고리즘을 구현하여 실제 작업(workload)에 대해서 성능을 측정 비교(실측하는 방법)
3. Simulation(모의실험)
   알고리즘을 모의 프로그램으로 작성후 trace를 입력으로 하여 결과 비교