CPU Scheduling: CPU 스케줄링 (2/2)

<Scheduling Algorithm>

1) FCFS (First Come First Served)

프로세스가 준비 큐에 도착한 시간 순서대로 cpu를 할당하는 방식. 비선점형이라 cpu를 차지한 프로세스가 내놓기 전까지는 cpu를 선점당하지 않는다. 효율적이지 않은 알고리즘임

FCFS

cpu 버스트가 긴 프로세스 하나가 cpu 버스트가 짧은 여러개보다 먼저 도착했다고 한다면 cpu 버스트가 짧은 프로세스들이 cpu 버스트가 긴 프로세스 하나 때문에 오래 기다려야 해서 평균 대기 시간(average waiting time)이 길어진다. 

FCFS 스케줄링에서는 먼저 도착한 프로세스의 성격에 따라 평균 대기시간이 크게 달라진다. 즉 CPU 버스트가 긴 프로세스가 먼저 도착한 경우 평균 대기 시간이 길어지는 반면, CPU 버스트가 짧은 프로세스가 먼저 도착하게 되면 대기시간은 짧아진다. CPU burst가 짧은 프로세스가 CPU burst 가 긴 프로세스보다 나중에 도착해 긴 놈이 먼저 끝날 때까지 오랜 시간을 기다려야 하는 현상을 convoy effect라고 한다. 

 

2) SJF (Short Job First)

각 프로세스와 다음번 cpu burst time을 가지고 스케줄링에 활용함 cpu burst time이 가장 짧은 프로세스를 제일 ㅁ너저 스케줄링한다. SJF IS OPTIMAL 퍙군 대기시간 가장 짧게 해서 OPTIMAL 알고리즘이라고 함 -> 주어진 프로세스들에 대해 minimum average waiting time 보장

- 비선점형 방식

일단 cpu를 잡으면 이번 cpu burst 완료될 때까지 cpu를 선점(preemption) 당하지 않음

 

- 선점형 방식

현재 수행중인 프로세스의 남은 burst time 보다 더 짧은 cpu burst time을 가지는 새로운 프로세스가 도착하면 cpu를 빼앗김. 이 방법을 shortest remaing time first(SRTF)라고 한다.

 

SJF의 문제점

1) Starvation(기아현상): cpu 사용사긴이 긴 프로세스는 영원히 cpu 사용이 불가능할지도?

2) cpu 사용 시간을 미리 알 수 없다. -> 추청은 가능함(과거의 흔적을 통해서 예측함... 정확하진 x)

-> 다음 cpu burst time의 예측

다음번 cpu burst time을 어떻게 알수 있는가? 추정만이 가능하다

1. tn - 실제 n 번째 cpu 사용 시간

2. n + 1번째 cpu 사용 예측 시간

4. n+1번째 cpu 사용 예측 시간은 n번쩨 실제 cpu 사용시간과 n번째 예측했던 cpu 사용 시간을 일정 비율씩 곱해서 더한 것이다.!

알파와 1-알파는 둘 다 1 이하이므로 후속 term은 선행 term보다 적은 가중치의 값을 가진다. 최근의 과거 가중치가 올라가고 예전 과거는 가중치를 적게 반영하는 것이다. 

만약 알파가 0이라면 recent history doesn't count, 1이라면 only the actual last cpu burst counts.

 

3) Priority Scheduling

준비 큐에서 가장 높은 우선순위를 가진 프로세스에서 cpu를 할당해주는 것이다. 

- 선점형 방식

프로세스가 실행하다가 더 높은 우선순위의 프로세스가 들어오면 cpu 제어권이 그 프로세스에게 넘어간다(선점당한다).

- 비선점형 방식

프로세스가 실행하다가 더 높은 우선순위의 프로세스가 들어와도 cpu를 선점 당하지 않는다.

 

SJF도 일종의 priority scheduling 방식이라고 볼 수 있음 (priority = predicted next cpu burst time)

 

priority scheduling의 문제점

- 기아현상 : 낮은 우선순위의 프로세스는 영원히 실행되지 못할 수도 있다. -> 해결 방법: aging (노화): as time progress increase the priority of the process( 우선순위가 낮아도, 준비 큐에 오래 있었으면 우선순위를 높여주자~)

 

4) Round Robin (RR)

현대적 시분할 시스템의 성질을 가장 잘 이용한 방법. 각 프로세스는 동일한 크기와 할당 시간(time quantum)을 가진다. 일반적으로 10-100밀레세컨드임. 여러 프로세스가 동시에 수행되는 환경에서 대화형 프로세스가 cpu를 한 번 할당 받기까지 지나치게 오래 기다리지 않을 시간 규모이기 때문이다. 할당 시간이 지나면, 프로세스는 선점(preempted)당하고 ready queue의 제일 뒤에 가서 다시 줄을 선다. n개의 프로세스가 ready queue에 있고 할당 시간이 q time unit인 경우 각 프로세스는 최대 q time unit 단위로 cpu 시간의 1/n을 얻는다. => 어떠한 프로세스도 (n-1)q time unit 이상 기다리지 않는다. 대기시간이 cpu의 사용시간과 비례한다. 왜냐면 한번 짧게 쓰고 나가면 되니까. 길게 쓰면 또 기다려야해. 만약에 q가 크다면 fcfs performance이고, q가 작다면 context switch 오버헤드가 커질 것이다. 

일반적으로 SJF 보다 average turnaround time이 길지만 response time은 더 짧다. SJF는 cpu 버스트 시간이 짧은 프로세스에게만 유리하고 긴 프로세스는 오래 기다려야 한다(희생). 이것은 효율성을 높이느라 형평성을 간과하는 결과를 초래한다. RR은 공정한 스케줄링 방식이다. 일단 어쨋든 한번씩 cpu를 잡고, 내가 cpu를 쓰고자 하는 양이 적으면 소요시간이 짧아지고, 반대로 양이 많으면 소요시간도 길어진다. 또한 대기시간도 cpu 버스트 시간에 비례하여 증가한다. 

5) Multilevel Queue

준비큐를 여러개로 분할하여 관리하는 기법을 말한다. 프로세스들이 줄을 한줄로 서는 것이 아니라 여러 줄에 나누어서 선다. cpu는 어떤 줄에 서 있는 프로세스를 우선적으로 스케줄링 할 것인지? 프로세스가 도착했을 때 어느 줄에 세울지 결정해야 한다. 멀티레벨 큐는 일반적으로 성격이 다른 프로세스들을 별도로 관리하고, 프로세스의 성격에 맞는 스케줄링을 적용하기 위해 준비 큐를 별도로 두게 된다. 각 큐는 독립적인 스케줄링 알고리즘을 가진다. (줄의 특정에 맞는 알고리즘을 선택해야 한다.)

foreground queue(전위 큐) - interactive 대화형 - RR

background queue(후위 큐) - batch: no human interaction(계산 위주의 작업) -FCFS(cpu만 오래 쓰고 응답시간 빨라도 뭐... 오버헤드 적은 fcfs)

 

큐 자체에 대한 스케줄링은 어떻게 할 것인가?

Fixed priority scheduling(고정 우선순위 방식)

큐에 고정적인 우선순위를 부여하여 cpu 주기 (전위 다해야 후위 줌)

starvation의 가능성이 있다 (우선순위 높은 큐에 계속 프로세스가 들어오면 우선순위 낮은 애는 계속 굶음ㅜ)

 

Time Slice (starvation 예방)

각 큐에 cpu 타임을 적절한 비율로 할당한다. 예를 들어 전위에 80퍼 RR, 후위에 20퍼 FCFS, 이런 식으로,. 

 

6) Multilevel Feedback Queue

얘는 신분 극복이 가능한 방식이다.

cpu를 기다리는 프로세스를 여러 큐에 줄 세운다는 측면에서 멀티레벨 큐와 동일하나, 프로세스가 하나의 큐에서 다른 큐로 이동 가능하다는 점이 다르다. aging을 이런 방식으로 구현할 수 있다. 

멀티레벨 피드백큐의 스케줄러를 정의하는 파라미터들에는

• 큐의 수
• 각 큐의 스케줄링 알고리즘
• 프로세스를 상위 큐로 보내는 기준
• 프로세스를 하위 큐로 보내는 기준
• 프로세스가 cpu서비스를 받으려 할 때 들어갈 큐를 결정하는 기준

일단 프로세스는 우선순위가 가장 높은 큐에 줄을 먼저 선다. quantum = 8인 큐로 들어갔다가 할당시간 끝나면 2인 퀀텀 16 큐로 이동하고 상위 큐 빌 때까지 기다리고 cpu를 얻는다. 그니까 내가 1단계에서 끝났으면 그냥 나가면 되고 남았으면 2단계로 이동해서 위의 1단계 큐 빌 떄까지 기다리고 이런 식 cpu 사용시간이 짧은 프로세스에게 우선순위를 많이 주는 방식이다. cpu는 높은 우선순위부터 가기 때문에 낮은 우선순위 큐 프로세스라면 우선순위 높은 큐 빌 때까지 기다려야 함. 라운드 로빈 스케줄링을 한층 더 발전시켜 프로세스의 cpu 작업 시간을 다단계로 분류함으로써 작업시간이 짧은 프로세스일수록 더욱 빠른 서비스가 가능하도록 하고, 작업시간이 긴 프로세스에 대해서는 문맥교환 없이 cpu 작업에만 열중할 수 있는 fcfs 방식을 채택할 수 있도록 해준다. 

 

 

7) Multi-Processor Scheduling

cpu가 여러 개인 경우 스케줄링은 더욱 복잡해짐. 이러한 환경에서는 프로세스를 준비큐에 한 줄로 세워서 각 cpu가 알아서 다음 프로세스를 꺼내어가도록 할 수 있다. 그러나 반드시 특정 cpu에서 수행되어야 하는 프로세스가 있는 경우에는 어떻게 해야할까? 각 cpu별로 줄세우기를 할 수도 있다. 

한편 여러 줄로 줄세우기를 하는 경우 일부 cpu에 작업이 편중되는 현상이 발생할 수 있다. 

 

Load Sharing (부하 균형)

일부 프로세스에서 프로세스가 몰리지 않도록 부하를 적절히 공유하는 메커니즘 필요

별개의 큐를 두는 방법 vs 공동 큐를 사용하는 방법 (한줄서기, 여러 줄 서기)

 

Symmetric Multiprocessing(SMP) 모든 cpu가 대등하며 대칭형 다중처리 각 프로세스가 각자 알아서 스케줄링 결정

Asymmetric Multiprocessing(AMP) 하나의 프로세서(cpu)가 시스템 데이터의 접근과 공유를 책임지고, 나머지 프로세서(cpu)도 거기에 따름

 

8) Real-time Scheduling

* Hard real-time systems

hard real-time task는 정해진 안에 반드시 끝내도록 스케줄링 해야함 데드라인 존재, 미리 스케줄링해 계획

* Soft real-time computing

soft real-time task는 다른 일반 프로세스들이랑 섰어서 실행함. 데드라인 보장안되도 괜찮으나 보장하는게 좋음 cpu 먼저 얻을 수 있게 일반 프로세스들에 비해 높은 priority를 갖도록 해야함

 

따라서 실시간 환경에서는 먼저 온 요청을 처리하기 보다는 데드라인이 얼마 남지 않은 요청을 먼저 처리하는 EDF(Earlist Deadline First) 스케줄링을 널리 사용하게 된다.

9) Thread Scheduling

* Local Scheduling

user level thread (사용자 프로세스가 직접 스레드를 관리하고 os는 스레드의 존재를 모르는)의 경우 사용자 수준의 thread library에 의해 어떤 thread를 스케줄할지 결정한다 -> os가 하는 것 x 사용자 프로세스가 직접 (내부에서 결정) 어떤 스레드에게 cpu를 줄까

 

* Global Scheduling 

kernel level thread (os가 스레드의 존재 앎) 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 스레드를 스케줄할지 결정함 -> 프로세스 스케줄링 하듯이 os가 함

 

<Algorithm Evaluation>

Queueing Models

이론가들이 주로 함 이론적임 

확률분포로 주어지는 arrival rate, service rate 등을 통해 각종 performance index 값을 계산

 

Implementation(구현) & Measurement(성능 측정) 

실제 시스템에 알고리즘을 구현하여 실제 작업(workload)에 대해서 성능을 측정, 비교 ex)리눅스 실제 커널 vs 내가 만든 스케줄러 돌린 커널

 

Simulation(모의 실험) 

알고리즘을 모의 프로그램으로 작성 후 trace(시뮬레이션 프로그램에 input으로 들어갈 data)를 입력으로 하여 결과 비교한번 해선 모르니까 여러번 해봐야 앎