[운영체제] CPU Scheduling

• 현재 CPU 자원을 수행 중인 process 중 누구에게 줄 것인가를 결정하는 것
• process 상태를 변화시키는 process scheduling 과는 구별됨
• short-term scheduler에 해당됨

 

• CPU scheduler의 중요한 원칙

CPU를 ㅃㄹㅃㄹ 줘서 사용자가 직접적으로 interactive하다고 느끼게 만들어 줄 필요가 있음

=> I/O bound job에 먼저 CPU를 줘야 되겠다

 

CPU Scheduler

• Multiprogramming 환경에서 동작
• ready 상태의 프로세스에서 하나를 골라 CPU 할당해줌
• 언제 발생하는가?
  1. 어떤 프로세스가 cpu를 잡아서 돌다가 waiting 상태로 갔을 때 (I/O request)
  2. running 상태에서 ready 상태로 갈 때 (멀티 프로그래밍 상태에서 시간이 너무 오래 걸려 강제로 뺏어서)
  3. waiting 상태에서 ready 상태로 갈 때 (I/O finished interrupt)
  4. 종료 시

1,4 -> nonpreemptive(비강제적)

2,3 -> preemptive(강제적)

 

Dispatcher

• 어떤 놈한테 CPU를 줄 것인지 결정이 되면 그러기 위한 과정이 수행
• 선택된 프로세스한테 CPU를 넘겨주는 일
  • context switching - 대부분의 시간 걸림, overhead
  • user mode로 전환
  • 프로그램이 중단됐던 위치에서 다시 시작하는 행위

 

성능 지표 (알고리즘 평가)

• CPU utilization
  • CPU가 놀게 만들어서는 안됨
  • 높아져야 함
• Throughput
  • 단위시간 당 종료시키는 프로세스의 개수
  • 많을수록 굳
• Turnaround time
  • 어떤 프로세스가 시작 한 다음 끝날 때까지 걸리는 시간
  • 짧을수록 굳
• Waiting time
  • 어떤 프로그램이 ready 상태, ready queue에서 기다리는 시간
  • 짧을수록 굳
• Response time
  • 사용자가 어떤 프로그램을 시작했을 때 첫번째 응답이 나올때까지 걸리는 시간
  • 짧을수록 굳

Scheduling Algorithm

• FCFS (First-Come First-Served)
  • 먼저 온 놈을 먼저 CPU 주겠다
  • 티켓팅, 수강신청 등 => 공평성
  • 공평성 외에는 단점이 많음
    • waiting time에 있어서 매우 나쁜 경우가 생김
    • P1의 burst time 24, P2- 3, P3 -3 일 경우 P1-P2-P3 순서로 프로세스를 실행하면 P1 waiting time 0, P2-24, P3-27 로 평균 waiting time이 17이 됨
    • 순서가 P2-P3-P1으로만 바뀌어도 평균 waiting time이 3으로 줄어듦
  • Convoy Effect(호위병 효과): 호위병은 왕을 앞질러서 갈 수 없듯이, 앞의 큰 프로세스가 있으면 아무리 짧은 프로세스라도 오랫동안 기다릴 수밖에 없음
• SJF (Shortest-Job-First)
  • convoy effect를 발생하지 않게 하기 위해서, 짧은 놈들을 앞으로 보내
  • 새로운 프로세스의 burst time이 현재 프로세스보다 짧을 경우
    • Nonpreemptive 방식: 그래도 한번 CPU 준 거 안 뺏음
    • Preemptive 방식: CPU 뺏어서 짧은 놈한테 줌, 이 방식을 SRTF (Shortest-Remaining-Time-First)라고 부름
  • 평균 waiting time 측면에서 optimal

 

Gantt chart

 

 Nonpreemptive: 평균 waiting time 4                                       Preemptive: 평균 waiting time 3

 

• 근데 프로세스를 보고 burst time을 어떻게 알아? => 모르지 신만 알지
• 그렇다고 waiting time을 최소화할 알고리즘 버리긴 아까움
• 과거의 burst로 추정하기 => exponential averaging

• 가중치가 0이면 과거 값 아예 무시, 가중치가 1이면 과거값 그대로 예측값 사용
• Priority Scheduling(알고리즘은 아니고 어떤 정책 같은 거): 우선순위가 높은 프로세스에게 CPU를 먼저 주겠다는 기본적인 틀
  • SJF가 next CPU burst time을 priority로 잡는 알고리즘임
  • Starvation 문제: 우선순위가 낮은 프로세스는, ready queue의 뒤쪽에 있는 놈들은 CPU를 잡을 일이 없어짐
    • Solution=>aging: 오랫동안 대기하면 우선순위를 쫌씩 높여줌
• Round Robin(RR): 각 프로세스가 CPU를 잡았을 때 사용할 수 있는 시간의 한계, time quantum 를 정해둠
  • 어떤 프로세스도 (n-1)q 보다 긴 시간 기다리지 않음 => upper bound
  • 왜 RR이 생겼을까? -> 멀티프로그래밍 때문에, 모든 프로그램이 진도가 나가는 것처럼 보여야 하니까
  • q large => time quantum이 없는 거나 마찬가지, FIFO, CPU 한번 잡으면 오래 잡으니까
  • q small => context switch를 너무 많이 해야 돼서 오버헤드가 커짐
  • SJF와 비교했을 때
    • 평균 turnaround(어떤 프로세스가 시작해서 끝이 날 때까지의 시간)은 크지만
    • response time(나한테 다시 CPU가 올 때까지의 시간)이 더 나음, 사용자 interaction
  • Time Quantum = 20 일 때

Gantt chart

 

• Multilevel Queue
  • interactive한 job에게는 CPU를 빨리 줘야 함
  • FCFS는 그런 걸 고려하지 않음, 공평성을 제외한 나머지 대부분에서는 안 좋음
  • SJF, SRTF는 저절로 그렇게 됨
  • RR도 공평하게 돌아감
  • => 이것저것 결합해서 사용
  • 그래서 탄생한 게 Multilevel queue
    • foreground에는 interactive job
    • back ground에는 batch - no human interaction
  • queue간 스케줄링
    • Fixed priority scheduling: foreground 다 끝나면 background 프로세스에 CPU 줌 => starvation
    • Time slice: CPU의 많은 부분을 foreground에 주고 남은 부분을 background
• Multilevel Feedback Queue
  • 어떤 프로세스가 I/O bound job인지, CPU job인지 모름
  • 처음엔 제일 첫번째 큐에 넣고 CPU 사용 형태에 대한 피드백을 받아 큐 간 이동을 가능하게 함
  • queue 개수, 큐 내부 알고리즘, 하위<->상위 큐 간 이동 조건, 최초 프로세스가 만들어지면 어느 큐에 넣을 지 정책 필요
• Real-Time scheduling
  • 실시간 시스템은 데드라인 존재
  • Hard real-time systems: 모든 프로세스는 반드시 데드라인 이전에 종료되어야 함 
    • 미사일, 핵폭발
  • Soft real-time systems: 데드라인을 반드시 보장하는 건 아니지만 웬만하면~
    • 동영상 재생

한양대학교 강수용 교수님 운영체제 강의 내용 정리