CPU Scheduling은 왜 필요할까? 사실, 이제까지는 cpu scheduling을 전제로 이야기를 쭉 해와서, 너무 당연하게 느껴졌을 수 있다. 하지만 process하나가 cpu를 잡으면 종료될 때 까지 cpu를 놓지 않게 할 수도 있는 것이다.

앞에서 언급했듯이 실제로는 cpu scheduling을 fifo 방식으로 하지 않는다. 하나의 process가 종료되고 그제서야 다른 process가 실행되는 방식이라거나, io가 완료될 때 까지 그냥 process가 blocked되어버린 상태로 cpu가 놀면 사람 입장에서는 답답한 것도 있고, 또 효율적이지 않다.

따라서 cpu를 더 효율적으로 놀리기 위해 scheduling이 필요하다.

용어 정리를 하고 가자

• CPU Schedulier
  • ready 상태의 process 중에서 이번에 cpu를 줄 process를 고른다
  • 얘는 운영체제 안에 있는 코드이다
• Dispatcher
  • CPU를 줄 process가 결정된 상태에서, 실제로 그 친구한테 넘겨준다.
  • context switch를 발생시키는 것
• 적절한 분류인지는 모르겠지만, cpu scheduling이 필요한 경우는 process에 다음과 같은 상태 변화가 있는 경우이다.
  1. running → blocked (ex) io 요청의 경우)
  2. running → ready (ex) timer에 의한 interrupt)
  3. blocked → ready (ex) io 완료에 따른 interrupt)
  4. terminate
  1, 4 : nonpreemptive = 강제로 빼앗지 않고, 자진 반납하는 경우
  2, 3 : preemptive = 강제로 빼앗는 경우
  분류보다는 preemptive라는 단어에 조금 더 집중하라고 한다. 자주 등장하니까

CPU burst, IO burst
모든 Process들은 CPU를 돌리는 구간과, io요청을 날리고 이를 기다리는 구간으로 나뉜다.
전자를 cpu burst, 후자를 io burst라고 한다.

1. CPU Scheduling

cpu scheduling에서는 cpu를 누구에게 줄 것인지, 줬다면 얼마동안 쓸 수 있게 해줄지를 결정하는 것이 관건이다.

보통 선점형, 비선점형(preemptive, non-preemptive)으로 나뉜다.

1) 성능 측정법

시스템 입장에서의 성능 척도

가능하면 많이 cpu를 놀릴 수록 좋은 것

cpu utilization

• 전체 시간 중, cpu가 놀지 않고 일한 시간
• 가능한 바쁘게 일을 시킬 수록 좋은 것

throughput

• # of processes that complete their execution per time unit
• 시간 당 처리한 일의 양

프로그램 입장에서의 성능 척도

빨리 얻어서 빨리 끝나면 좋은 것일 것

turnaround time

• process를 실행하는데 걸린 시간. cpu를 돌리는 시간과 기다리는 시간의 합

waiting time

• cpu를 쓰기 위해 기다리는 시간

response time

• ready queue에 들어온 후, 처음으로 cpu를 얻기까지 걸리는 시간
• 처음으로 cpu를 얻는 시간이 사용자 응답과 관련해서 중요한 요소라 별도로 도입

2) Scheduling 기법

FCFS (First Come First Served)

말 그대로 먼저 온 것을 먼저 처리하는 방법이다.

진짜 별거 없다. 말 그대로 선착순

• nonpreemptive이다.
• 별로 효율적이지는 않다. 오래 걸리는 친구가 먼저 cpu를 잡으면 cpu를 짧게 짧게 쓰는 친구들은 마냥 기다리기만 해야할 것

1, 3, 5000초의 실행 시간을 요구하는 processe들이 있다고 하자.

P3-P2-P1순으로 실행되는 경우 waiting time W3=0, W2=5000, W1=5003초,

P1-P2-P3순으로 실행되는 경우 waiting time W1=0, W2=1, W3=4초로

극명하게 큰 차이가 난다.

❕이렇게 긴 process가 먼저 cpu를 잡아 뒤의 짧은 process들이 다뤄지지 못하는 것을 convoy effect라고 한다.

SJF (Shortest Job First)

CPU 사용시간이 가장 짧은 process를 먼저 처리하는 방법이다.

전체적으로 꽤 행복한 결과가 나오는 방법

✅ 두 가지로 나뉜다.

Nonpreemptive

• 일단 cpu를 잡으면, 완료될 때까지 반환하지 않는다.
• CPU를 쓰고 반환하는 시점에 다음에 실행할 process를 결정할 것

Preemptive

• 현재 수행중인 process의 남은 burst time보다 더 짧은 cpu burst time을 갖는 process가 들어오면 cpu를 빼앗긴다.
• 이 방법은 SRTF(Shortest Remaining Time First)라고도 한다.
• average waiting time이 가장 짧은 방법
• ready queue에 새로운 process가 들어오는 시점에 다음에 실행할 process를 결정할 것

✅ 다음과 같은 문제점이 있다.

• starvation
  • 실행 시간이 긴 것들은 영원히 실행되지 못할 수도 있다. 계속해서 더 실행시간이 짧은 것들이 들어올 수 있기 때문이다.
• cpu burst time은 미리 알 수 없다.
  • 조건문으로 분기되는 것도 있고, 유저 요청도 그 때 그 때 다를 것이기 때문이다.

✅ 두번째 문제점은 추정을 통해 극복 가능하다.

Exponential Averaging 기법으로 추정한다. 미래 추정을 위해 과거를 일정 비율로 반영하는 기법이다.

$\tau_{n+1} = \alpha t_n + (1-\alpha)\tau_n$

$t_n, \space \tau_n$ : n번째 cpu burst, n번째 cpu burst 추정시간

위 식은 재귀적으로 풀어진다. $\tau_{n+1}, \tau_n$이 좌, 우변에 있는 것만 봐도 알 수 있다. 직접 써내려가보면 쉽게 확인 가능할 것

결론적으로는 n번째 실제 cpu burst에 가장 큰 가중치를 두고, 과거의 cpu burst들에 조금 더 낮은 가중치를 둬가며 그 것들을 모두 합쳐 n+1번째 cpu burst를 추정하게 된다. 물론 $\alpha$를 잘 구해야 정확하게 추정되겠지만 ㅋㅋㅋ..

Priority Scheduling

우선순위가 가장 높은 process에게 cpu를 주는 방법

✅ 마찬가지로, Preemptive와 nonpreemptive가 다르다.

preemptive인 경우, 새로 ready queue에 들어온 process 중 더 우선순위가 높은 것이 있다면 cpu를 내어주고, nonpreemptive인 경우 일단 쭉 cpu를 가져간 후 해당 process가 종료되면 다음에 실행할 process를 물색한다.

✅ 우선순위는

보통 정수로 표현하고, 작은게 더 우선순위를 높게 가져간다. 물론 설계하기 나름

사실 SJF도 우선순위 스케쥴링으 종류 중 하나이다. 실행시간을 우선순위로 설정하면 그게 바로 SJF가 된다.

✅ 다음과 같은 문제점이 있다.

• Stavation
  • 역시 SJF처럼 우선순위가 더 높은 친구들이 계속 들어오면 우선순위가 낮은 친구는 실행되지 않을 수도 있다.

✅ 우선순위 수정해가며 극복 가능하다.

Aging이라는 기법이 있다. 물론 여기서만 쓰는 기법은 아니고, 경험상 이런 애들은 무언가 추정을 할 때 시간 도메인이 달려있으면 자주 쓰는 기법인거 같더라

다양한 방법이 있을 수도 있겠는데, 간단하게는 그냥 특정 상수를 매 차례마다 곱해줌으로써 우선순위를 낮추면 된다.

Round Robin

Process에 cpu를 줄 때, 할당 시간(time quantum)을 함께 주며, 할당 시간이 채워지면 cpu를 빼앗는다. 당연히 preemptive 방식

• Response time이 빨라진다는 장점이 있다.
• 다른 친구들이 어떤 친구들이든간에 상관없이 조금 기다리면 내 차례가 오기 때문
  • n개의 process가 있고, 할당 시간이 각 q초라면, 무슨 일이 있어도 q*(n-1)초 이상 기다리는 경우는 없다.

✅ 다음과 같은 특징이 있다.

• 할당 시간이 크면 FIFO와 비슷해진다.
• 할당 시간이 짧으면 context switch가 매우 빈번하게 일어나 비효율적이다.
• waiting time이 해당 process의 실행 시간에 비례하게 된다.
  • 할당 시간은 일정하다고 해보자. 실행 시간이 긴 만큼 여러번 cpu에 올라가야하게 되므로, 당연히 queue에서 기다리는 waiting time도 늘어난다.

할당 시간은 10~100ms정도가 적당하다고 알려져있다고 한다.

실행 시간이 동일한 process들이 여러개 들어오면, 모두 waiting time을 길게 가져가다가, 마지막에 한꺼번에 종료되는 상황이 발생한다. 한꺼번에 종료되는 것, 혹은 하나라도 종료되는 것 중 무엇이 좋느냐에 대한 대답은 애매하다. 경우에 따라 다를 것. 어쨋든 이런 상황도 발생한다는 것이다.
결국 Round Robin의 최대 장점은 reponse time이 빠르다는 것

Multilevel Queue

multilevel queue의 예시

ready queue를 여러개로 분할해서 우선순위가 다른 queue를 여러개 두는 방법

✅ 다음과 같은 것들을 고려해야할 것이다.

• Process를 queue에 넣는 기준
• 각 queue에 들어있는 process들에게 cpu를 배정하는 기준
• queue들에 대한 scheduling 기준

✅ 아래와 같은 방법으로 설계해볼 수 있겠다. 물론 설계하기 나름이다. 정말 다양한 조합이 있을 수 있겠다. 아래는 예시일 뿐

• Ready Queue를 여러개로 분할
  • foreground : interactive한 process들을 넣는다.
  • background : batch(no interaction) process들을 넣는다.
• 각 Queue에 scheduling 기법을 지정한다.
  • foreground : RR
    • interactive하니까 response time을 짧게 가져가기 위해!
  • Background : FCFS
    • 어떻게 처리되든 별 상관 없으니!
• Queue의 scheduling을 선정한다.
  • Fixed Priority Scheduling
    • foreground먼저 모두 실행하고 background 실행
    • 너무 당연하게도 starvation이 생길 수 있을 것
  • Time slice
    • queue끼리의 starvation이 발생할 수 있다는 것을 고려하자!
    • 전체 CPU time의 80% 정도는 foreground에, 20%는 background에 할당

Multilevel Feedback Queue

ready queue를 여러개로 분할해서 우선순위가 다른 queue를 여러개 두며, process가 한 queue에 종속되지 않고, 서로 다른 queue에 배정될 수 있도록 하는 방법

✅ 다음과 같은 것들을 고려해야할 것이다.

• Process를 queue에 넣는 기준
• 각 queue에 들어있는 process들에게 cpu를 배정하는 기준
• queue들에 대한 scheduling 기준
• process를 상위/하위 queue로 보내는 기준

여러 방법이 있을 수 있겠지만 보통 위와 같은 방법을 쓴다고 한다.

• 처음 들어오게된 process는 RR로 처리하며 할당 시간을 짧게 준다.
• 그래도 끝나지 않으면 아래 queue로 배정하며, 여기서는 RR로 처리하며 할당 시간을 더 길게 준다.
• 그렇게 쭉 내려가다 마지막 queue에서는 FCFS로 처리한다.

CPU 사용시간이 짧은 친구들한테 우선순위를 크게 주는 알고리즘이다.

CPU 사용시간이 긴지 짧은지 예측할 필요 없이 짧은게 우대받는다.

3) 다양한 상황에서의 scheduling

위에서는 processor가 하나인 상황, 별다른 제약 조건이 없는 상황에서 process들을 처리하는 방법을 때에 따라 preemptive, nonpreemptive 정도로만 나눠 다뤘다. 그 외의 경우에서는 scheduling해야할 대상이 또 어떤게 있고, 어떻게 scheduling할 수 있는지 간략하게 알아보자

Multi-Procesesor Scheduling

CPU가 여러개 있다면?

• Homogeneous processor인 경우
  • 그냥 queue에 한줄로 세워서 processor가 알아서 꺼내가게 한다.
  • 반드시 특정 processor에 수행되어야하는 경우 복잡해질 것이다.
• Load sharing
  • 일부 processor에 몰리지 않도록 하는 메커니즘이 필요할 것이다.
  • 공동 queue를 둘 수도 있고, 별개의 queue를 둘 수도 있을 것이다.
• Symmetric Multiprocessing(SMP)
  • 모든 processor이 대등한 것. 각 processor이 알아서 스케쥴링하는 것이다.
• Asymmetric Multiprocessing
  • 하나의 processor가 시스템 데이터 접근, 공유등을 책임지고, 나머지 processor는 그 것을 따르는 방법이다.

Real-Time Scheduling

Deadline이 있는 job, 정해진 시간 안에 꼭 실행되어야만 하는 job을 real-time job이라고 한다. 이런 친구들을 scheduling하려면?

보통 이런 친구들은 그때그때 scheduling하는게 아니라,

미리 offline등에서 scheduling해서 deadline이 보장되도록 적재적소에 배치하는 것처럼, 상황과 특성에 맞게 먼저 구성을 마친 후 돌리는 방법을 쓴다.

• Hard real-time scheduling
  • 정해진 시간 안에 반드시 끝내도록 scheduling해야하는 것들은, 꼭 그렇게 해야할 것
  • 원자로, 반도체 관리/생성과 관련된 애들은 이러겠지
• Soft real-time scheduling
  • 일반 process들이랑 같이 돌리는 경우. 꼭 deadline에 맞게 실행되어야하는 것은 아니다
  • 그냥 우선순위만 좀 높게 설정해서 같이 돌리면 될 것

Thread Scheduling

생각나는가? user level thread와 kernel level thread가 있었다.

user level thread의 경우 kernel 입장에서 thread가 존재하는지 모른다. 그냥 라이브러리의 도움을 받아 만든 thread이다.

• Local Scheduling
  • User level thread의 경우 OS에 의해 process가 cpu를 받으면, process가 어떤 thread를 돌릴지 결정한다.
• Global Scheduling
  • Kernel level thread의 경우 process scheduling하듯이, OS가 어떤 thread를 돌릴지 결정한다.

4) Algorithm Evaluation

알고리즘 성능을 평가하는 방법을 간략하게 알아보자.

개인적으로 이런건 간략하게 알아보는 정도로는 의미가 없다고 생각한다. 있다는 것은 인지하고, 필요할 때 잘 공부해서 잘 성능평가 해봐야하는거지. 근데 잘 하려면 잘 알아야한다 ㅠ

Queueing Models

이론적으로 많이 쓰는 방법. 요즘에는 그냥 직접 만들어 돌려본다고

• queueing model에서는 server라고 하지만, 여기서 server는 cpu로 생각하자
• job들이 도착하는 arrival rate이 있을 것이고(rate이니 # of jobs / sec 정도 일 것 같다), 처리해내는 service rate이 있을 것이다.
• 위 둘이 확률 분포로 주어진다고 할 때, 얘들을 가지고 performance index들을 계산해낸다.

Implementation & Measurement

• 실제 시스템에 알고리즘을 구현하고, 돌려보고, 성능을 측정하는 방법
  • 뭐 커널 수정해서 컴파일하고, 돌려보고, 측정해보고
• 당연히 쉬운 일이 전혀 아니다ㅠㅠ

Simulation

위 방법이 쉽지 않으니 시뮬레이션 돌려보는 것이다. factor들을 잘 캐치해야 신빙성있는 시뮬레이션이 될 것

• 알고리즘을 모의 프로그램으로 작성 후, trace를 입력으로 하여 결과를 비교한다.
  • 실제 시스템에서 cpu 사용패턴을 뽑아온 데이터들과 같이, 실제 상황에서 가져온 것들을 trace라고 한다. 얘를 input으로 넣어야 더 정확하겠지. 물론 임의로 만들 수도 있을 것이고
• 커널 뜯어고치는게 아니라 프로그램으로써 상황을 만들어서 돌려보는 것