[CS] 운영체제 - CPU 스케줄링

CPU 스케줄링

 

CPU and I/O burst ( 하나의 프로세스의 일생 ) 

• CPU bound job
  • CPU를 길게 쓰는 프로그램
  • 예) 계산을 오래 하는 작업
• I/O bound job
  • CPU를 비교적 짧게 사용
  • 예) 주로 사람과 인터렉션하는 프로그램
• 여러 종류의 job이 섞여 있기때문에 CPU 스케줄링이 필요하다
• I/O bound job을 먼저 CPU를 주면 짧게 쓰고 I/O 장치를 사용하러 가지만 CPU bound job을 먼저 주면 I/O 장치까지 놀게 될 수 있다.

CPU Scheduler & Dispatcher

• CPU Scheduler
  • 여러 작업이 존재하기에 스케줄링이 필요
  • Ready 상태의 프로세스 중 CPU를 줄 프로세스를 고른다.
• Dispatcher
  • CPU의 제어권을 CPU Scheduler에 의해 선택된 프로세스에게 넘김
  • 이 과정을 context switch라고 한다.
• CPU 스케줄링이 필요한 경우는 프로세스에게 다음과 같은 상태 변화가 있는 경우
• nonpreemptive(자진 반납)
  • Running -> Blocked (ex: I/O System call)
  • Terminate
• preemptive(강제로 반납)
  • Running -> Ready(ex: time out timer interrupt)
  • Blocked -> Ready(ex: interrupt after I/O Complete)

스케줄링 성능 척도( Scheduling Criteria)

• CPU utilization(이용료)
  • 높을수록 좋음
• Throughput(처리량)
  • 많을수록 좋음
• Turnaroind time( 소요시간, 반환 시간)
  • 사용시간과 대기시간 전부
  • 빠를수록 좋음
• Waiting time(대기시간)
  • CPU를 사용하려고 와서 기다린 시간의 합
  • 큐에서 줄 선 모든 시간
  • 빠를수록 좋음
• Response time(응답 시간)
  • 최초로 CPU를 얻기까지 시간(CPU를 사용하려고 하는 순간부터 최초로 CPU를 얻기까지)
  • 빠를 수록 좋음

CPU 스케줄링 알고리즘

• FCFS(First Come First Served)
  • nonpreemptive
  • 선착순으로 처리
  • 사용시간이 긴 프로세스에게 먼저 CPU를 주면 비효율적
  • Convoy effect
    • 1차 세계대전 때 잘 싸우는 사람이 앞에서 오래 싸워주면 뒤에 사람들이 오래 살아남는 효과에서 유래
• SJF(Shortest Job First)
  • 각 프로세스의 다음번 CPU burst time을 가지고 스케줄링에 활용
  • CPU burst time이 가장 짧은 프로세스에게 먼저 CPU를 줌
  • nonpreemptive
    • 일단 CPU를 잡으면 CPU burst가 완료될 때까지 CPU를 선점당하지 않는다.
  • preemptive
    • 현재 수행 중인 프로세스의 CPU burst time보가 짧은 프로세스가 오면 CPU를 빼앗김(남은 시간 기준)
• SRTF(Shortest Remaining Time First)
  • 가장 적은 평균 대기 시간을 보장 가능
  • 기아 현상이 발생
    • CPU burst time가 긴 프로세스가 CPU를 얻지 못하는 상황 발생
  • 다음 프로세스의 CPU burst를 미리 알 수 없음
  • 과거를 보고 예측해서 판단

    

    • 1에 가까울수록 직전 값을 사용
• Priority 스케줄링
  • 우선순위로 CPU를 줌
  • SJF도 일종의 Priority 스케줄링이다.
  • nonpreemptive, preemptive로 구현 가능
  • Aging
    • 오래 기다릴 경우 우선순위를 높여준다 
• RR(Round Robin)
  • Timer에 시간을 세팅해서 시간이 지나면 인터럽트를 걸어서 CPU를 뺏음
  • 보통 10 ~ 100m/s
  • 기아 현상 예방 가능
  • 할당 시간이 너무 길거나 짧으면 문제가 됨
  • 평균 turnaround 시간이 길어짐
  • 짧은 job과 긴 job이 섞여있어야 효율적
  • 똑같은 job이 계속 올 경우 다 같이 기다리다가 다 같이 종료될 수 있음
• Multilevel Queue
  • Ready queue를 여러 개로 분할
    • foreground에 인터렉티브 한 Job
    • background에 인터렉티브 하지 않은 Job
  • 각 큐는 독립적인 스케줄링 알고리즘을 가짐
    • foreground - RR
      • 응답이 빨라야 함
    • background - FCFS
      • 시간이 긴 Job들은 차례로 처리하는 게 나음
  • 큐에 대한 스케줄링이 필요
    • Fixed priority 스케줄링
      • 모든 foreground 큐가 해결되면 background 큐를 처리
    • Time slice
      • 각 큐에 CPU time을 적절한 비율로 할당
      • foreground 80%, background 20%
• Multilevel Feedback Queue
  • 큐 간에 이동이 가능
  • 각 큐에 스케줄링 알고리즘 존재
    • 상위 큐로 보내는 기준
    • 하위 큐로 보내는 기준
• Multiple Processor 스케줄링
  • CPU가 여러 개인 경우 더 복잡
  • Homogeneous(균질한) processor 
    • Queue에 한 줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있다.
    • 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우는 복잡
  • Load sharing
    • 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘 필요
    • 별개의 큐를 두는 방법, 공동 큐를 사용
  • Symmetric Multiprocessing(SMP)
    • 모든 CPU가 대등
    • 각 프로세서가 각자 알아서 스케줄링
  • Asymmetric multiprocessing
    • 하나의 프로세서가 시스템에 데이터의 접근과 공유를 책임
• Real Time 스케줄링
  • 데드라인이 있는 경우에 사용
    • Hard real time systems
      • 정해진 시간 안에 반드시 끝내야 함
      • 오프라인으로 스케줄링하는 경우도 있음
        • 오프라인은 미리 프로세스들의 도착시간을 알고 하는 것
    • Soft real time systems
      • 일반 프로세스보다 우선순위가 높아야 함 (예: 영상)
      • 데드라인을 반드시 지켜야 하는 것은 아님
• Thread 스케줄링
  • Local 스케줄링
    • User level thread(운영체제가 모름)
    • 사용자 수준의 thread library에 의해 스케줄링
  • Global 스케줄링
    • Kenel level(운영체제가 알도 있음)
    • 일반 프로세스처럼 커널의 단기 스케줄러가 결정
• Algorithm Evaluation
  • Queueing models

    

    • 확률 분포로 job의 도착률과 처리율이 주어짐
    • 수식을 통해 처리량, 대기 시간이 반환
• implementation(구현) & Measurement(성능 측정)
  • 실제 시스템에 알고리즘을 구현
  • 실제 작업에 대해서 성능 측정(실제로 구현한 후 테스트해본다)
  • 리눅스 내부 코드를 수정해야 해서 난도가 높다
• Simulation(시뮬레이션)
  • 모의 프로그램으로 작성하고 테스트
  • input data(trace)가 신빙성이 있어야 함
  • trace
    • 실제 프로그램에서 추출
    • 제작