03 - CPU Scheduling

📌 CPU bound & I/O bound

• cpu burst
  : cpu에 의해 직접 수행되는 작업의 부분 (I/O 거의 없음)

• I/O burst
  : cpu에 의하지 않고 일어나는 작업의 부분

• 일반적으로 프로세스는 많은 수의 짧은 cpu burst들 혹은 적은 수의 긴 cpu burst 들로 구성되며 이들의 편중에 따라 I/O bound 프로그램과 cpu bound 프로그램으로 나눌수 있다

• I/O bound : 대부분이 I/O, 많은 수의 짧은 CPU burst

• cpu bound : 대부분이 적은 수의 긴 cpu burst

📌 CPU Scheduler

: (short-term scheduler)

• ready queue에서 기다리고 있는 프로세스 중에서 하나를 선택해서 cpu에 할당한다.
• dispatch latency : dispatcher가 하나의 process를 멈추고 다른 process를 run하는데 시간이 걸림

📌🌟 Preemptive vs Nonpreemptive scheduling

* preemptive scheduling

: 강제성을 띄고 있다.
: 해당 프로세스 스스로가 아닌 타의에 의한 강제적인 scheduling을 의미한다.
ex) 도서관에서 현재 좌석을 차지하고 있는 학생에게 시간이 됐으니 물러나라고 하는 경우
ex) 응급실 - 급한 환자가 생기면 먼저 와있는 환자보다 먼저 수술을 들어간다

* nonpreemptive scheduling

: 강제성을 띄고 있지 않다.
: 해당 프로세스 스스로 일을 수항해는 것을 의미함.
: 스스로 그만두기 전까지는 강제로 그만두게 못함.
ex) 도서관 좌석을 차지한 학생이 자리를 비워야만 자리가 생기게 하는 좌석 배정
ex) 은행 - 먼저 온 손님의 용무가 끝나기 전까지는 다음 사람이 일처리를 할 수 없다. / 화장실

• RUNNING -> BLOCKED / Process terminated : nonpreemptive

• RUNNING -> READY / BLCOKED -> READY : preemptive

• preemptive한 스케줄링인 경우 어떠한 문제가 발생할 수 있는가?
  : 2개 이상의 프로세스들이 공유 데이터를 사용하는 경우 문제가 될 수 있다.

  ex) 어떤 프로세스가 kernel mode(system call)에서 중요한 데이터(프로세스 테이블의 수정, 프로세스의 생성)를 사용중일때 preemption 될 경우 문제가 발생할 수 있다.

  ==> process synchronization

  ---

  📌🌟Scheduling Criteria

  (최선의 알고리즘을 결정하는데 사용되는 기준)

  1. CPU utilization (cpu 사용량/ 이용률)

  : 현재 cpu가 얼마나 사용되고 있는지를 나타낸다. cpu utilization이 높을수록 cpu를 잘 활용하고 있다는 것이므로 높을수록 좋은 스케줄링 기법이라고 할 수 있다.

  2. Throughput (처리율)

  : 단위 시간당 완료시키는 프로세스 수
  : 처리율이 높을수록 시간당 많은 프로세스를 수행할 수 있다는 것으로 높을수록 좋다.

  3. Turnaround time (반환 시간)

  : process 시작 ~ 완료 시간
  : 한 프로세스가 new 상태에서 terminated 상태에 도달할때 까지의 시간을 나타낸다.
  반환시간이 짧아야 프로세스를 실행하는데 필요한 시간이 짧다는 것으로 짧을수록 좋다.
  : 메모리에 들어가기 위해 기다리는 시간 + ready queue에서 기다리는 시간 + cpu 실행하는 시간 + I/O 하는 시간

  4. Waiting time (대기 시간)

  : 프로세스가 ready queue에서 대기한 총 시간
  : ready queue에서 대기한 시간이 짧을수록 프로세스들이 대기 없이 빠르게 실행되었다는 것이므로 짧을수록 좋다.

  5. Response time (응답 시간)

  : 요구가 들어갔을 때, 첫번째 응답이 돌아오기까지의 시간
  : 프로세스가 응답을 시작할 때까지 걸리는 시간
  : 실시간 시스템에서 매우 중요한 요소이다. 짧을수록 좋다.

  ---

  📌 Scheduling Algorithms

  1. FCFS (first-come-first-serve scheduling)

  • nonpreemptive scheduling
    : 먼저 들어온 job을 먼저 실행해주기 때문에 먼저 들어온 job이 끝날때까지 다음 job은 기다려야함.
    -> 시분할 시스템에 있어 많은 문제 내포
  • ready queue로써 FIFO를 사용하면 용이하게 관리됨.
  • 평균대기시간이 매우 클 수 있다.

    #### * convoy effect : 먼저 도착한 프로세스가 cpu에서 수행되는 burst time이 매우 길면 그 다음 도착한 프로세스가 첫번째 프로세스가 끝날 때까지 매우 긴 시간을 기다리게 된다.

  -> cpu 이용률이 낮아짐

ex)
* p1 burst time : 24 / p2 : 3 / p3 : 3

---

p1 ----- p2 - p3
0 ------ 24 - 27 - 30
p1, p2, p3 순서로 도착했다면 평균 대기시간 (average waiting time) : (0 + 24 + 27) /3 =17

p2 - p3 -------- p1
0---3--6 ------- 30
p2, p3, p1 순서로 도착했다면 평균 대기시간 (average waiting time) : (0+3+6)/3 = 3

==> 실행시간이 짧은 순으로 하면 좋겠다
:: SJF(shortest job first algorithm)

2. SJF (shortest-job-first scheduling)

• 다음에 수행해야 할 cpu burst들 중에서 가장 작은 수행시간을 가지는 프로세스부터 선택한다.
  만약, 2개 이상의 프로세스가 모두 동일한 수행시간을 가진다면 그들 중에서는 FCFS로 scheduling 한다.

• nonpreemptive scheduling

• 수행될 프로세스 , 프로세스의 수행시간을 알수가 없다.
  = 실제로 실행 전에는 프로세스들의 수행시간을 알 수 없기때문에 비현실적이다.

  ex)
  *p1 : 6 / p2 : 8 / p3 : 7 / p4 : 3

  ---

  p4 -- p1 -- p3 -- p2
  00 -- 03 -- 09 -- 16 -- 24
  평균 대기시간
  (p4:0/ p1:3 / p3:9 / p2: 16 -> (0+3+9+16)/4=7)
  ** 만약 FCFS scheduling 을 한다면?
  (0+6+14+21)/4 = 10.25

  3. SRTF (Shortest-Remaining-Time-First)

• 잔여 cpu burst가 가장 작은 프로세스를 선택한다.

• SJF scheduling 기법의 preemptive version 이다.

• 프로세스의 ready queue에의 도착시간이 명시되어야 한다.

  ex) 🌟계산문제 - 자료 보기 꼭!

  4. Priority Scheduling

• 우선순위가 각 프로세스에 배정된다. 무엇을 운선순위로 줄 것인가가 결정되어야 한다.

• SJF (프로세스의 수행시간이 작을수록) , SRTF (잔여 CPU burst가 작을수록) 도 우선순위 스케쥴링의 한 종류이다.

• FCFS는 모든 프로세스의 우선순위를 동일하게 한 경우이다.

• preemptive 또는 nonpreemptive 하게 운영될 수 있다.

  • 우선순위 스케줄링의 문제점
    : starvation = 오긴오는데, 언제올지 모름
    : 우선순위가 높은 프로세스들이 계속 들어오면 우선순위가 낮은 프로세스는 언제 수행될지 모름.
    -> aging 기법 : 오랫동안 시스템에 남아있는 프로세스에 대해 점진적으로 우선순위를 올려주는 기법

  • 우선순위 반전 현상
    : 높은 우선순위를 가지는 프로세스가 낮은 우선순위를 가지는 프로세스의 작업이 완료될 때까지 기다리는 현상
    : real-time 인 경우 주어진 deadline을 맞추지 못하는 문제가 생길 수 있다.
    
    우선순위 상속 (priority inheritance)
    ex) client가 우선순위를 server에게 넘겨준다.

  5. RR (Round-Robin) scheduling

• 시분할 시스템이다. (원형큐를 ready queue로 사용)

• FCFS와 비슷하지만 preemptive scheduling 이다.

• 한 타임 슬라이스에 한 프로세스를 할당한다.

• 평균 대기 시간이 꽤 길다.

• time slice의 size에 따라 성능이 달라진다
  : infinite(too long) = FCFS와 동일하다
  : too short = 스위칭이 너무 빠르게 일어나서 한 프로세스만 실행하고 있다고 착각함. (process sharing effect)
  / time slice의 크기가 작아질수록 context switch하는 횟수가 증가해 context switch에 대한 overhead가 커져 성능 저하
  : time slice > switching time 이어야 함.

  * turnaround time

  : time slice의 크기가 작아질수록 커진다.
  : time slice 한번에 프로세스가 바로 끝나면 turnaround time이 개선될 수 있다.
  ++ 🌟계산!

  6. MQ (Multilevel Queue) scheduling

• 프로세스를 그룹화 해서 각각의 스케줄링 알고리즘을 가짐.
  : 은행에서 간단한 업무 / 대출 업무를 구분해서 받는 것과 유사함.

• 각 queue들도 스케줄링을 해주어야함.
  : 각각의 queue에 절대적 우선순위가 존재함.

• 각 queue는 독립된 scheduling 정책을 가지고 있음.

• scheduling overhead가 낮은 장점이 있지만 inflexible하다.
  : 한 프로세스는 그룹에 할당되면 고정됨.

  7. MFQ (Multilevel Feedback Queue) scheduling

• queue 간의 프로세스 이동을 허용한다.

• 너무 오래걸리는 process는 lower-priority queue로 이동시킨다.

• starvation 우려시 higher-priority queue로 이동시킨다.

  8. RT (Real-Time) scheduling

• hard real-time
  : 응답시간을 보장해줘야 함.
  : 시간안에 끝나면 시작하고, 그게 아니라면 시작을 안함
  : 특수 목적에 이용됨 (무기 / 핵미사일)

• soft real-time
  : hard real time 보다는 덜 제한적이다.
  : atm 기계, 스트리밍에 이용됨.
  : 우선순위 기반 스케줄링을 이용함