[운영체제] KOCW 반효경 교수님 강의 - 10. CPU Scheduling 1

• CPU 스케줄링에서 중요한 2가지 이슈
  
  • CPU bust에 들어온 여러 프로세스들 중 누구에게 CPU를 줄것인가?
  • CPU를 할당한 후에 점유한 프로세스가 CPU를 계속 사용하도록 둘 것인가 뺏을 것인가?

• CPU를 뺏지 않는 경우
  • CPU bound job이 CPU를 할당하면
  • CPU를 잠깐 사용하고 반납할 I/O bound job들이
  • 긴 시간 동안 줄서서 기다려야함

• CPU 스케줄링의 종류
  • 1. Non-preemptive 스케줄링
    • CPU를 가진 프로세스가 자진 반납할 때까지 CPU를 점유
    • 비선점형
  • 2. Preemptive 스케줄링
    • 현대 스케줄링 방식
    • 강제로 CPU를 가져올 수 있는 방식
    • 선점형

• 좋은 스케줄링 평가 (성능 척도, Performe-ance Idex, Performeance Measure)
  • 1. 시스템 입장에서의 성능 척도 -> 중국집의 주방장
    • CPU가 일을 많이 할수록 좋음
    • CPU utilization
      - 전체 시간 중 CPU가 놀지 않고 일한 시간의 비율
    • Throughput
      - 주어진 시간에 처리한 작업의 양
  • 2. 프로그램 입장에서의 성능 척도 -> 중국집의 손님
    • CPU를 빨리 얻어서 빨리 끝날수록 좋음 (시간)
    • Turnaround time -> 음식을 먹고 나간 시간 (짜장면/코스요리)
      - CPU를 점유 후 다 쓰고 나갈 때까지 걸린 시간
      - CPU를 기다리는 시간(Waiting time)까지 포함
      - 프로세스가 실행되고 완전히 종료되는 시간이 아니라, Ready queue에 들어와서 I/O하러 나가는 시간까지를 의미
    • Waiting time -> 밥을 먹지 않고 기다린 시간
      - Ready queue에서 CPU를 기다린 모든 시간
      - CPU 점유 후 뺏겼다가 다시 기다리는 모든 시간 포함
    • Response time -> 첫 번째 음식이 나올 때까지 기다린 시간
      - Ready queue에 들어와서 처음으로 CPU를 쓰기까지 걸린 시간

 

• FCFS
  
  • 먼저 온 순서대로 처리
  • Non-preemptive
  • 먼저 들어온 job이 오래걸릴수록 효율이 좋지 않음
    - Convoy effect (호의 효과) : 긴 프로세스가 먼저 들어와서 짧은 프로세스가 오래 기다려야 하는 현상
  • interactive한 job에 좋지 않음

•  SJF
  • 가장 짧은 프로세스를 제일 먼저 할당
  • Convoy effect가 없음
    - 전체적으로 queue가 짧아짐
  • 평균 waiting time이 최소가 되는 것을 보장
  • Non-preemptive
    - 더 짧은 프로세스가 도착해도 현재 프로세스가 끝날 때까지 CPU를 점유
    - 현재 CPU를 점유중인 프로세스 작업이 끝나면 스케줄링
  • Preemptive
    - CPU를 점유했어도 더 짧은 프로세스가 도착하면 CPU를 빼앗김
    - Shortest-Remaining-Time-First(SRTF)
    - 프로세스가 도착했을 때 스케줄링
  • 문제점
    • 1. Starvation
      - 긴 프로세스가 평생 CPU를 점유하지 못하는 현상
    • 2. CPU 사용 시간을 미리 알 수 없음
      - 짧은 프로세스, 긴 프로세스를 알 수 없음
      - 예측은 할 수 있음 : CPU bound job, I/O bound job
      - 과거에 얼마나 썼는지를 통해 앞으로 어떻게 쓸지 예측

• 다음 CPU burst time 예측 (Exponential Averaging)
  
  • t_n = n번째 실제 CPU 사용 시간
  • τ_n+1 = n+1번째 CPU 사용을 예측한 시간
  • τ_n+1 = αt_n + (1-α)τ_n   (0<=α<1)
  • n번째 실제 CPU 사용시간과 n번째 예측 사용 시간에 일정 비율을 곱해서 합한 값
  • 가장 최근의 값을 가장 크게 반영, 오래될수록 적게 반영
    • n자리에 n-1을 넣으면 타우n을 알파와 t, 타우 식으로 만들 수 있음
    • 이 타우n을 타우n+1 식에 대입
    • 알파의 거듭제곱식으로 만들 수 있음 (알파가 거듭제곱될수록 값이 작아짐)

• Priority Scheduling
  • 우선순위가 높은 순서대로 CPU 할당
  • 보통 작은 숫자가 높은 우선순위
  • SJF도 일종의 priority scheduling
    - prioirty = 예측된 다음 CPU burst 시간
  • Preemptive / Non-preemptive
  • 문제점
    • Starvation
  • 해결
    • Aging(노화)
      - 낮은 우선순위더라도 오래되면 우선순위를 높여줌

• Round Robin
  • 할당 시간만큼 CPU를 점유(Preemptive)
  • 할당 시간이 끝나면 timer interrupt로 Ready queue로 옮겨지고, 다음 프로세스가 CPU를 점유
  • 응답시간이 빠름
    - n개 프로세스가 ready queue에 있음
    - 할당 시간이 q time unit
    - (n-1)q time unit이 지나면 한 번은 CPU를 점유할 수 있음
  • CPU 사용시간을 예측할 필요없이 짧은 프로세스가 빨리 Ready queue에서 나갈 수 있게 해줌
  • CPU를 사용하는 시간과 기다리는 시간이 비례
    - CPU를 길게 사용하면 오래 기다림
    - CPU를 짧게 사용하면 잠깐 기다림
  • 시간에 따른 성능
    • time quantum이 커지면 FCFS와 같아짐
    • time quantum이 작아지면 context switching으로 인한 오버헤드가 커짐
    • 일반적으로 10~100ms
  • SJF보다 turnaround time이나 waiting time이 길어질 수 있지만, response time은 짧아짐
  • 안좋은 케이스 : 비슷한 시간의 job들로 구성되어 있을 때
    • 100초짜리 job 100개가 들어옴
    • SJF는 100초가 지나면 1개 끝나고, 100초 지나면 1개 끝나고를 반복
    • RR은 1초씩 쪼개서 쓸 때, 100 * 100초가 될 때까지 어떤 job도 끝나지 않음
  • 그러나 일반적으로 다양한 시간의 job이 섞여있으므로 효과가 좋음