CPU scheduling

https://core.ewha.ac.kr/publicview/C0101020140325134428879622?vmode=f 

반효경 [운영체제] 9. Process Management 2

 

어떤 프로그램이던 간에 위와 같은 path를 실행하며 진행된다.  

 

CPU Burst : CPU만 연속적으로 쓰는 단계

IO Burst : IO만 하는 단계 

 

즉 프로그램은 CPU burst와 IO burst를 반복하며 실행된다 

물론 프로그램의 종류에 따라 빈도는 다르다.

주로 사람이 interaction을 하는 프로그램이 IO Burst가 자주 끼어드는 프로그램이다. 

반면, 과학 계산용 프로그램 등은 CPU Burst가 주된 프로그램이다. 

 

CPU burst가 짧은 프로그램이 많고 CPU burst가 긴 프로그램이 적다 

CPU burst가 짧고 중간에 IO burst가 많이 끼어드는 프로그램을 IO bound job이라 한다. 

CPU만 오랫동안 사용하는 프로그램을 CPU bound job이라 부른다.  

CPU bound Job과 IO Bound Job이 섞여 있어 CPU 스케쥴링 이라는 것이 필요하다. 

 

IO Bound job은 CPU를 짧게 쓰는 대신 빈도가 잦고, 

CPU Bound job은 CPU를 길게 쓰는 대신 빈도가 드물다 

 

CPU Bound job이 CPU를 잡고 놓지 않게 되면 IO Bound job이 CPU를 못 잡고 오래 기다리게 된다. 

IO Bound job은 사람과 interaction 하는 job이다. 따라서 사람이 답답하게 느끼게 된다. 

CPU bound job은 계산 위주의 job이다. 

 

CPU를 공평하게 주는 것이 아니라 사람과 상호작용하는 IO Bound job에게 CPU를 먼저 주는 것이 CPU scheduling의 필요성이다. 

 

누구한테 우선해서 줄 것인가? 언제 뺏을 것이냐? 등이 CPU 스케쥴링의 중요한 이슈다. 

 

CPU Scheduler & Dispatcher

CPU Scheduler

ready 상태인 프로세스 중 누구에게 CPU를 줄지 결정한다.

운영체제 안에서 CPU 스케쥴링을 하는 코드가 있고 그 부분을 CPU 스케쥴러라고 부른다

 

Dispatcher

 

CPU를 누구한테 줄지 결정했으면, CPU를 실제 넘겨주는 역할을 하는 커널 코드다.

넘겨주는 과정을 문맥 교환이라고 한다.

 

CPU 스케쥴링이 언제 필요한가? 

1. Running -> Blocked : IO 요청하는 시스템 콜 (CPU 자진 반납)

2. Running -> Ready : 할당시간 만료로 timer interrupt (CPU를 빼앗음)

3. Blocked -> Ready : IO 완료 후 인터럽트 : 우선순위에 따른 스케쥴링을 할 때 IO를 완료한 프로세스가 현재 프로세스보다 우선순위가 높을 경우 

4. Terminate 

 

1,4번은 CPU를 자진 반납하는 경우. nonpreemptive : 비선정형

2,3번은 CPU를 강제로 빼앗기는 경우. (timer interrupt) preemptive : 선졍형 

 

---

CPU 스케쥴링에는  2가지 issue가 있다.

1. CPU를 어떤 프로세스에게 줄 것인가

2. CPU를 줬다면 언제 뺏을 것인가 

 

Scheduling Criteria 

스케쥴링 성능 측정을 위한 방법 , 성능 척도

• 시스템 입장에서의 성능 척도 
  • CPU utilization : 이용률
    
    • 전체 시간 중 CPU가 놀지 않고 일한 시간의 비율 
    • CPU는 비싼 자원. 가능한 한 일을 많이 시켜라
  • Throughput : 처리량 
    • 주어진 시간 동안 몇 개의 작업을 완료했는가 
• 프로세스 입장에서의 성능 척도 
  • Turnaround time : 소요시간 
    • CPU를 사용하러 들어와서 다 쓰고 나갈 때 까지 걸린 시간 
    • CPU burst가 다 끝나고 IO burst를 하러 나갈 때 까지의 시간 
    • 기다리는 시간 + 사용한 시간 
  • Waiting time : 대기시간 
    • CPU를 쓰기 위해 ready queue에 줄서서 기다리는 시간 
  • Response time : 응답시간 
    • ready queue에 줄서서 처음으로 CPU를 얻기까지 걸린 시간 

Waiting time과 Response time은 어떻게 다른가? 

preemitive scheduling에서 프로세스는 CPU를 한번 얻었다고 끝까지 쓰는 것이 아니다. 

한번의 CPU burst 동안에도 CPU를 얻었다 뺏겼다를 반복하며 줄 서서 기다리는 시간이 여러 차례 발생하고 이것들을 다 합친 것이 waiting time이다.

 

주의 : 프로세스 생애주기를 통틀어 계산하는 값들이 아니다. 하나의 CPU burst에 대해 계산하는 것이다. 

ready queue에 있는 프로세스 들만 스케쥴링의 대상이 되기 때문이다. 

 

 

응답 시간이 있는 이유?

응답 시간은 사용자 응답과 관련해 중요한 시간의 개념이다 

중국집에서 단무지라도 먼저 내주는 것처럼 .. 

 

FCFS

first come first served 

먼저 온 고객을 먼저 서비스해주는 방식 

 

비선정형 scheduling으로 일단 프로세스가 cpu를 얻으면 자진해서 내놓을 때 까지는 빼앗기지 않는다.

비효율적이다. 

 

앞에 어떤 프로세스가 있느냐에 따라 wating time의 평균이 크게 달라진다 

긴 프로세스 때문에 짧은 프로세스들이 오래 기다려야 하는 것을 Convoy effect라 부른다. 

 

SJF

Shortest Job First

CPU를 사용하고자 하는 시간이 , 즉 cpu burst가 가장 짧은 프로그램에게 CPU를 주는 스케쥴링 

 

큐가 전체적으로 짧아짐. average waiting time이 가장 짧아진다. 

즉 minimum average waiting time을 보장하는 optimal 한 스케쥴링 방식이다. (preemtive 방식)

 

SJF도 두가지 방식으로 나눌 수 있다. preemtive, nonpreemtive 

 

nonpreemtive SJF 

더 짧은 프로세스가 도착하더라도 현재 사용중인 프로세스가 CPU를 반납하기 전 까지는 사용 보장 

preemtive SJF 

더 짧은 프로세스가 도착하면 CPU를 뺏어서 넘겨준다 

이 방식은 shortest remaining time first라고도 부른다

CPU를 쓰고 있던 CPU의 남은 사용 시간 remaining time을 가지고 비교하기 때문이다 (중간에 뺏을 수 있으니까)

optimal 한 방식이다. 평균 대기 시간이 가장 짧은

 

non-preemtive SJF

preemtive SJF

2초 시점에서 P1은 5초가 남았고 P2는 4초가 남았다. P1이 사용중이지만 preemtive SJF이므로 P2에게 CPU를 넘겨준다 

평균 대기 시간이 non preemtive SJF에 비해 짧다 

preemtive SJF로 얻은 average waiting time 3초보다 짧게 scheduling을 할 수는 없다 

 

scheduling을 어느 시점에 하는가?

non preemtive SJF는 프로세스가 CPU를 쓰고 나가는 시점에 스케줄링을 하게 된다 

preemtive 버전은 새로운 프로세스가 도착하면 언제든지 스케쥴링이 이루어진다 

 

SJF는 두가지 문제점이 있다.

 

Starvation 기아 

SJF는 극단적으로 CPU 사용시간이 짧은 job 선호

CPU 사용시간이 긴 프로세스는 영원히 CPU를 못 받을 수도 있다. 

 

CPU 사용 시간을 미리 알 수 없다

그때 그때 상황에 따라 CPU 사용 시간이 다를 수 있다.

CPU 사용 시간을 미리 알 수가 없다는게 문제! 

실제로 SJF를 사용할 수가 없다! 

그런데 추정은 할 수 있다. IO Bound Job은 CPU 사용시간이 짧고 CPU Bound Job은 CPU 사용시간이 길다 

과거에 CPU 사용을 한 흔적.. 과거에 얼마나 썼는가.. 이런 것들로 추정이 가능하다. 

 

추정은 어떻게 ? exponential averaging 

t : 실제 CPU 사용 시간 

tau : CPU 사용을 예측한 시간 

아래첨자는 몇번째로 CPU를 사용하는 것인지 나타낸다.

즉 tau n+1을 예측하는 시점에는 tn 까지는 전부 주어진 상황이다. 

n+1번쨰 CPU 사용 예측 시간은 n번째 실제 CPU 사용 시간과 n번째 예측했던

CPU 사용 시간을 일정 비율씩(alpha, 1-alpha) 곱해서 더해서 구한다.

 

더 이전의 CPU 사용 시간은 더 적게 반영한다. 

즉 최근 걸 더 크게 반영, 이전 걸 더 작게 반영

 

Priority Scheduling 

우선순위 스케쥴링 

우선순위가 가장 높은 프로세스에게 CPU를 준다 

마찬가지로 preemptive 버전과 nonpreemtive 버전 두가지가 있다. 

우선순위는 다양한 방법으로 정의할 수 있다. 

각 프로세스마다 우선순위를 나타내는 숫자가 주어진다 (정수값)

이 때, 작은 숫자가 높은 우선순위를 나타낸다. 

 

SJF도 next CPU burst time이 우선순위인 우선순위 스케쥴링의 일종이다.

 

우선순위 스케쥴링의 문제점 : Starvation 

SJF에서 설명한 것 처럼 우선순위가 낮은 프로세스가 영영 CPU를 얻지 못할 수도 있다 

 

Aging 노화

Starvation을 해결하기 위한 방법이다. 

우선순위가 아무리 낮아도 오래 기다린 프로세스는 우선순위를 조금씩 높혀주자. 

이러한 방식으로 언젠가는 CPU를 얻게 해줘서 Starvation을 막을 수 있다. 

 

Round Robin  (RR)

현대적인 컴퓨터의 CPU 스케쥴링은 RR에 기반한다 

preemtive 한 스케쥴링 방식이다. 

 

CPU를 줄 때 동일한 크기의 할당 시간을 세팅해서 준다 

그 시간이 끝나면 timer interrupt를 걸어서 ready queue의 제일 뒤에 줄을 서게 된다.

그럼 다음 프로세스가 CPU를 잡게 되고.. 반복 .. 

 

RR의 장점 

CPU를 최초로 얻게 되는 시간, 즉 response time 응답 시간이 빨라진다. 

누가 CPU를 오래 쓸지 모르는 상황에서 굳이 예측할 필요가 없다.

 

ready queue에 n개의 프로세스가 있고 할당 시간이 q라면 어떤 프로세스도 (n-1)q 이상의 시간을 기다리지는 않는다

 

CPU를 짧게 쓰는 프로세스는 한번의 할당 시간 만에 CPU 사용을 완료하고 빠져나가고, 길게 쓰는 CPU는 q 시간이 끝나면 뺏기고..  따라서

RR 스케쥴링은 CPU를 길게 쓰는 프로세스는 기다리는 시간이 길어지고 짧게 쓰는 프로그램은 기다리는 시간이 짧아진다 

즉 대기시간이 프로세스가 CPU를 사용하려는 시간에 비례하게 된다.  

 

RR은 

q를 아주 크게 잡으면 FCFS랑 같은 스케쥴링 알고리즘이 된다 

q를 아주 짧게 잡으면 문맥 교환이 자주 일어나 overhead가 커진다 

 

보통 10~100밀리세컨드가 적절한 q라고 알려져 있다.

 

q=20인 경우 RR 예시

RR은 일반적으로 SJF보다 average turnaround time은 길어질 수 있지만, response time은 더 짧다. 

 

특수한 상황(프로세스들의 CPU 사용시간이 같은 상황)에서는 RR이 구릴 수도 있다.

CPU 사용시간이 100초인 프로세스가 여러개 있을 때, FCFS로 처리하면 0초, 100초, 200초 씩 기다리게 된다 

RR을 사용하면 q=1초일 때 다같이 1000초가 지난 시점에 빠져나가게 된다. 

오히려 RR을 쓰면 waiting time이 길어져 안좋다. 

 

RR은 CPU 사용 시간이 짧은 프로세스와 긴 프로세스가 얼마나 CPU를 사용할 지 모르는 상태에서 마구잡이로 섞여 있을때 사용하기 좋은 스케쥴링이다.

 

RR은 context를 기억할 수 있기 때문에 가능한 것이다. 

 

Multilevel Queue

여러 줄을 사용한다 

맨 위가 우선순위가 가장 높다

Ready Queue를 여러 줄로 분할한 것이다. 

줄마다 우선순위가 있고, 맨 위 줄이 우선순위가 가장 높다.

무조건 우선순위 순서대로 CPU를 쓴다. 

 

두가지 큐로 사용할 수도 있다. 

foreground queue = interactive -> RR 

background = batch-no human interaction -> FCFS 

사람과 상호작용 하는지 여부로 우선순위를 달리 해 줄을 구분한다. 

 

각 줄마다 독립적인 스케쥴링 방식을 갖는다. foreground는 RR, background는 FCFS를 사용한다. 

batch는 CPU만 오래 쓰는 job이므로 응답시간이 빠르다고 좋을 것이 없어 FCFS를 사용하는 것이다.

줄의 특성에 맞는 스케쥴링 방식을 채택할 수 있다. 

 

큐에 대한 스케쥴링도 필요하다

Fixed priority scheduling에서는 foreground 큐가 비어야 background queue에게 차례가 간다. 

이럴 경우 background queue에 starvation이 발생할 수 있다. 

Time Slice에서는 각 queue 별로 나눠서 할당하는 것이다.

전체 CPU 시간의 80%는 우선순위가 높은 큐에, 20%는 우선순위가 낮은 큐에 주는 것이다. 

Starvation을 방지할 수 있다. 

Multilevel feedback queue

여러줄로 줄서기를 하지만, 프로세스가 경우에 따라 줄 간 이동을 할 수 있다. 

큐를 몇개 줄지, 큐별로 어떤 스케쥴링을 사용할 지, 

큐에서 강등, 승격 기준은 뭔지, 처음에 프로세스를 어떤 큐로 넣을지 등의 기준을 정해야 한다. 

 

보통은 처음 들어오는 process는 우선순위가 가장 높은 큐에 넣는다. 

우선순위가 가장 높은 큐는 RR에서 q를 짧게 준다. 

아래 큐로 갈수록 RR의 q를 길게 준다. 

제일 아래 큐는 FCFS를 사용한다. 

할당시간이 맨 위 큐에서 끝나면 그 아래 큐로 강등되고, 그 아래 큐에서도 할당시간이 끝나면 강등되는 식이다.

 

CPU burst가 짧은 프로세스는 도착하자 마자 최우선 큐에 배치되므로 바로 작업을 끝내고 나갈 수 있다.

CPU burst가 긴 프로세스는 점점 아래 큐로 이동하며 queue 간의 우선순위에서 밀리게 된다. 

 

CPU 사용시간이 긴지, 짧은 지 예측이 필요 없다. 

 

Multiple processor Scheduling 

CPU가 여러개 있는 상황에서의 스케쥴링이다. 

 

Homogeneous 동일한 Processor 인 경우 

큐에 한줄로 세우고 각 프로세서가 알아서 꺼내가게 한다. 

특정 프로세스는 특정 프로세서가 수행해야 한다면 더 복잡하다 

 

Load Sharing

일부 프로세스에 job이 몰리지 않도록 하는 것이다. 

각각의 CPU마다 큐를 둘 수도 있고, 공동 큐를 사용할 수도 있다. 

 

Symmetric Multiprocessing SMP

모든 CPU가 대등해서 각 CPU가 알아서 스케쥴링을 한다 

 

Asymmetric Multiprocessing 

CPU가 여러개 있는데 하나의 CPU가 전체적인 제어를 담당한다. (데이터 접근, 공유)

나머지 CPU는 거기에 따른다 

 

Real time scheduling 

Real time job은 deadline이 있는 job이다. 

보통은 미리 스케쥴링을 해서 deadline이 보장되도록 한다 

 

Hard real time systems 

반드시 deadline 안에 보장되어야 함

 

Soft real time computing 

일반적인 time sharing system에서 다른 프로세스들과 섞여서 실행됨 

deadline은 존재하지만 반드시 지켜야 하는 것은 아님 

다른 프로세스에 비해 우선순위를 높여준다 

 

Thread Scheduling 

프로세스 하나 안에 CPU 수행 단위가 여러개 있는 것을 스레드라고 한다 

User level thread(운영체제가 스레드를 모름), Kernel level thread(운영체제가 스레드를 암) 두가지가 있었다.

 

Local Scheduling 

User level thread에서는 프로세스 내에서 어떤 스레드가 CPU를 잡을지 스케쥴링한다

즉 사용자 프로세스가 스케쥴링 하는 것이다 

Global Scheduling 

Kernel level thread의 경우 프로세스 스케쥴링 하듯이 커널의 단기 스케쥴러가 스레드 스케쥴링을 한다. 

 

Algorithm Evaluation 

어떤 스케쥴링 알고리즘이 좋은지 평가할 수 있는 방법은 크게 3가지로 나뉜다 

 

Queueing Model

여기서 server = CPU

 

도착율과 처리율을 통해 performance index를 계산 

 

Implementation & measurement 

실제 시스템에 알고리즘을 구현해서 실제 작업에 대해 성능 측정을 비교한다 

 

Simulation

실제로 돌리는 게 아닌 모의 실험 알고리즘을 모의 프로그램으로 작성 trace를 입력으로 하여 결과 비교 , trace는 시뮬레이션 프로그램의 input으로 들어갈 데이터 실제 프로그램을 돌리면서 trace를 얻을 수도 있다.