CPU Scheduling

• 현재 cpu 자원을 수행중인 process들 중에서 누구한테 줄 것인지 결정하는 것
• short term schedular
• process scheduling
  - process 상태를 변화하는 것
  • cpu scheduling가 어떤 process를 running 상태로 바꿀지 결정한다
• 사용자 만족도에 영향
  - avg waiting + response time

Alternating sequence of CPU and IO Bursts

• 현 시점에서 어떤 process에게 cpu 자원을 할당할지 결정할때 프로그램의 동작 형태를 알아야한다
• 보통 CPU -> IO -> CPU -> IO .. 반복한다
• 프로그램마다 번갈아서 발생하는 빈도가 다르다!

History of CPU burst Times

• Hyperexponential distribution
• x축: 한번 cpu를 잡으면 사용하는 시간
• y축: cpu를 잡는 빈도
• ex) 사용시간과 빈도의 관계
  - cpu를 길게 32 ms 사용하는 빈도는 낮다 -> CPU bound -> 계산 위주
  • cpu를 짧게 8 ms 미만 사용하는 빈도는 높다 -> IO bound -> 입출력 위주

카톡 보내려고 키보드를 누르는데 화면에 늦게 나타나면 매우 불편 -> IO bound job에 CPU를 먼저 주자!

Process Scheduler

• 현재 실행중인 process의 상태 전이를 관리함
• new, ready, run, terminate

• ready queue, blocked queue, blocked+suspend queue, ready+suspend queue

• Long term schedular가 new 상태인 process를 ready queue로 push한다
  - ready 상태에서 suspend되면 ready, suspend queue로 push한다

• Short term scheudlar가 ready 상태인 process에게 CPU를 할당한다
  - run 상태에서 IO가 발생하면 blocked queue로 간다
  - event가 발생하면 다시 ready queue로 간다

  • run 상태에서 마지막 명령어가 실행되면 terminate 상태가 된다

• Medium term schedular는 suspend queue와 관련된 process 상태를 전이시킨다
  - blocked queued에서 event waiting중인 process를 suspend하면 event가 발생하더라도 cpu를 잡아서는 안된다
  - event 발생 전 suspend되면 blocked,suspend queue로 push한다
  - event 발생 후 ready,suspend queue로 push한다
  - suspend queue에 있는 process가 main memory에서 쫒겨날 가장 좋은 후보다
  

CPU Scheduler

• 멀티프로그래밍 환경
• ready queue에 있는 process를 고르는 작업
• 동작하는 세가지 상황
  - 1) running -> waiting: IO가 발생하여 running process가 blocked queue로 가면 ready process에게 새로 cpu를 할당한다
  • 2) running -> ready: running process가 timeout되면 ready process에게 새로 cpu를 할당한다
  • 3) waiting -> ready: IO finished interrupt CPU랑 뭔 상관???? -> 현재 process와 상관없는 interrupt가 발생해도 ready 상태로 전이되고 ready queue에서 새로 가져올 수 있다 -> 누구를 선택하든 동일한 context switch overhead가 발생하기 때문!
  • 4) terminate: running process의 마지막 명령어가 실행되면 ready process에게 새로 cpu를 할당한다
• 1,4) -> nonpreemptive scheduling 비강제적
  - 1) 자발적으로 IO 발생
• 2,3) -> preemptive scheduling 강제적

Dispatacher

• cpu scheduling으로 process를 골랐다면 dispatcher module이 그 process에게 cpu를 할당하기 위해 세가지 동작을 수행한다
• context switching: 현재 process 상태를 저장하고 선택된 process의 예전 상태를 복원
• switching to user mode
• jumping to the proper location in user program to restart the program
• dispatch latency
  - 현재 프로세스를 멈추고 다른 프로세스를 run하는 작업이 제일 오래 걸림 (multipgramming을 위한 context switch overhead)

Scheduling criteria

• max cpu utilization: cpu를 가급적 바쁘게하기
• max throughput: 단위 시간당 끝이나는 process 개수
• min turnaround time: 어떤 프로세스가 시작하고 끝나기까지 걸리는 시간
• min waiting time: suspend queue가 아닌 ready queue에서 기다리는 시간의 합
• min response time: 첫번째 응답이 오기까지 걸리는 시간. 상호작용성을 느끼게 해주는 시간. ex) ㄱ 누르면 화면에 나오기까지 걸리는 시간

7 Scheduling Algorithms

• First come first served FCFS
• Shortest job first SJF
• Shortest Remaining Time First SRTF
• Priority Scheduling
• Round robin
• Multilevel Queue
• Multilevel Feedback Queue

FCFS

• 먼저 온 process에 CPU 할당 -> 공평 fairness
• 간트 차트
  - 각각의 프로세스가 CPU를 사용하는 시간을 나타냄
  • nonpreemptive
• waiting time (ready queue에서 기다린 시간)은 0, 24, 27 -> 평균 17

• P2,P3,P1 순서로 왔다면?
• waiting time 6,0,3 -> 평균 3 <<< 17!
• FCFS는 waiting time이 안좋다!
  convoy effect: 짧은 프로세스가 긴 프로세스 뒤에 있으면 waiting time이 늘어진다
• 순서만 바꾸면 많이 좋아진다

convoy effect 때문에 waiting time이 늘어나는 것을 방지하기 위한 방법을 생각해보자 -> side effect으로 IO bound 먼저

Shortest Job First SJF

• cpu burst (사용시간)이 가장 짧은 프로세스를 먼저
• SJF는 최소 평균 waiting time을 보장한다 OPTIMAL!

Nonpreemptive

• 현재 running중인 프로세스의 cpu burst보다 짧은 프로세스가 들어왔을 때 안뺏기

• P1 실행중에 P2,P3,P4 순서로 도착
• non preemptive이기 때문에 P1 끝까지 실행
• P3 < P2이므로 P3먼저 실행

Preemptive

• 현재 running중인 프로세스의 cpu burst보다 짧은 프로세스가 들어왔을 때 뺏기
• preemptive sjf == shortest remainting time first SRTF

• P1 실행중에 더 짧은 P2 도착
• preemptive는 cpu를 뺏기 때문에 P1 5초 남기고 P2 실행
• 뺏으면서 시간 최신화하고 현재 cpu burst 가장 짧은 process 선택하기
• P1 waiting 시간은 첫번째로 끝낸시간 ~ 두번째 시작시간

CPU Burst를 알아내야 SJF를 사용할 수 있다 -> 절대 모름.. -> 예측해보기!

Estimate CPU Burst

• 과거 데이터로 예측해보기
• exponential averaging

• tn = n번째 cpu를 잡았을때 사용시간 (과거 데이터)

• Tn+1 = 다음 cpu burst 예측 사용시간 (예측 데이터)

• 가중치 alpha, 0<=alpha<=1

• Tn+1 = alpha*tn + (1-alpha)Tn
  - n번째 cpu burst에 alpha 가중치 + 예측한 n번째 cpu burst에 (1-alpha) 가중치

• alpha = 0 -> Tn+1 = Tn
  - 항상 똑같은 cpu burst == 직전 실제값 t 무시 == 과거 전체의 평균 T를 보겠다

  • 미래를 예측할 때 process 행동이 일관되는지 봐야한다 -> 가장 신뢰하기 좋은 데이터는 직전 예측값

• alpha = 1 -> Tn+1 = tn
  - 직전 실제값 t만 고려
  

• 뒤로 갈수록 계수가 점점 작아짐 -> 오래된 데이터의 가중치가 줄어든다

Exponential Averaging

• 오래된 데이터의 가중치가 줄어든다

• alpha가 클수록 실제값에 근접한다

• 마찬가지로 alpha가 클수록 실제값에 근접한다

CPU burst가 변화한다면 직전값에 가충치를 높이는것이 중요하다 -> 모든 case가 그런것은 아니다..
그렇다면 직전값에 의존하면 잘못되는 경우는??

Priority Scheduling

• 알고리즘이 아닌 정책 -> 알고리즘을 만들기 위한 틀

• 우선순위가 높은 process에게 cpu를 먼저 주기

• 배정된 int 낮을 수록 높은 우선순위 -> 이건 알고리즘

• 독자적으로 쓰기 보다는 다른 방식과 혼합해서 쓴다

• SJF: cpu burst가 우선순위

• priority 방식 알고리즘은 preemptive, nonpreemptive로 나뉜다

• 문제: starvation -> low priority는 절대 실행 안될수도

• 해결: aging -> 시간이 지날수록 priority를 높인다

Round Robin (RR)

• 우선순위 없이 시간단위로 CPU를 할당 -> 모든 process가 조금씩 진도를 나감 -> multiprogramming을 위해서!
• time quantum q: CPU 사용 시간 한계 10~100ms, 지나면 ready queue로
• q가 있으면 ready queue 대기 시간 upper bound가 생긴다
  - 최대 (n-1)q 보장
• upper bound 보장되면 좋은 알고리즘이다 -> 계획적인 일을 할 수 있다 -> 없으면 가치가 내려간다!
• q가 너무 크면 -> 끝날때까지 cpu를 안놓음 == FIFO
• q가 너무 작으면 -> context switch overhead가 너무 커짐

적당한 time quantum이 필요하다

• overhead가 큼
• 무조건 최대 20 -> 20 안걸리면 그전에 끝
• 남은 시간 최신화하고 다음 프로세스 실행 (1->2->3->4 순서)
• SJF보다 avg wait이 높지만 더 responsive하다! -> 대기 시간 짧아 IO bound에 더 좋다
• IO bound 우선순위가 어느정도 보장됨
• turn around time이 큼 -> 체감은 안남

overhead 줄이기 위한 노력이 필요함 -> hyperthreading

• 서버처럼 프로세스가 많은경우 RR에 IO bound 우선순위 추가

Multilevel Queue

• foreground -> io bound
• background -> cpu bound
• 구현 불가능 -> 어떤게 io인지 cpu인지 모름

Multilevel Feedback Queue

• 알고리즘을 만들어내는 framework