[운영체제] 스케줄링 (Scheduling)

Scheduling

보다 효율적인 자원의 활용을 위해 어떤 작업을 메모리에 올리고 어떤 작업에게 자원을 할당 해야하는 지 결정

• CPU-burst : CPU 자원을 많이 요구하는 작업

• I/O-burst : I/O 사용이 많은 작업

• Non-preemptive : 프로세스가 스스로 자원을 반납하는 방식

• Preemptive : 프로세스가 스스로 자원을 반납하기 전에 강제로 회수할 수 있는 방식

• 스케줄링 알고리즘 성능 판단 기준

  • CPU Utilization - cpu를 최대한 바쁘게
  • Throughput - 시가 단위안에 실행이 완료되는 프로세스의 수
  • Turnaround Time - 하나의 프로세스가 시작에서 종료까지 걸리는 시간
  • Waiting Time - 하나의 프로세스가 레디큐에서 기다린 총 시간
  • Response Time - 프로세스가 첫 아웃풋을 내는데 걸리는 시간

스케줄링 알고리즘

• 하나의 ready Queue 이용하는 방식
  • FCFS (First-Come, First-Served)
    • convoy effect : 실행시간이 긴 작업이 먼저 오게 됨에 따라 전체적인 waiting time이 증가하는 것
  • SJF (Shortest-Job-First) : cpu-busrt time이 적은 프로세스부터 수행
    • cpu burst time 을 예측할 수 있어야함 (불가능)
  • Prriority Scheduling
    • starvation : 우선순위가 계속 밀려 cpu를 할당 받지 못하는 상태
    • aging : 오래기다린 작업의 우선순위를 올려주는 것
  • RR (Round Robin) : 시간을 나눠 할당
• 다수의 ready queue를 사용하는 방식
  • Multilevel Queue
    • 각 큐에 용 도에 맞는 작업이 들어감, 한번 큐가 배정되면 바뀌지 않음
    • 각 큐에는 서로다른 스케줄링 알고리즘
    • 각 큐의 우선순위에 따라 수행 -> starvation 문제 -> aging
  • Multilevel feedback Queue
    • 큐를 옮겨다닐 수 있음

다중 처리기 스케줄링

• Asymmetric multiprocessing : 하나의 프로세서만 시스템 자료 구조에 접근할 수 있음
• Symmetric multiprocessing(SMP)
  • 각각의 프로세서가 공통의 데이터 구조에 접근하고 그를 업데이트함
  • 대부분의 멀티프로세서 스케줄링에 쓰임
• load balancing : 모든 프로세서에 workload가 고루 분배되도록 함
  • push migration : 외부에서 주기적으로 프로세스의 로드를 확인하고 고루 분배
  • pull migration : 한가한 프로세서가 바쁜 프로세서에서 대기 중일 일을 당겨옴
• Multicore Processors
  • memory stall : 메모리에 접근하여 기다리는 동안 프로세서가 계산을 멈춰 낭비됨
  • simultaneous multithreading (SMT) : memory stall의 해결

실시간 CPU 스케줄링

• soft real-time system : 우선순위가 높은 프로세스가 먼저 실행되도록 보장
• hard real-time system : 각 task가 반드시 정해진 deadline 안으로 작업이 끝나는 것을 보장
• 스케줄링은 각 프로세스의 latency를 줄이기 위함
  • latency : 어떤 이벤트가 발생하고 그에 맞는 서비스가 수행되기 까지의 시간
    • Interupt latency : 인터럽트가 발생하고 ISR이 시작되기 까지의 지연시간
    • Dispatch Latency : dispatcher가 하나의 프로세스를 block하고 다른 프로세스를 시작하기 까지의 지연 시간
• Priority-Based Scheduling
• Rate Montonic Scheduling
• Earlist Deadline First Scheduling

알고리즘 평가

• deterministic evaluation : 미리 정해놓은 workload를 통해 성능 측정
• queueing models : 프로세스의 도착시간, cpu와 I/O 버스트 들을 확률적인 분포로 기술
• little's formula : 큐 사이즈길이 = (평균 도착시간) X (평균 대기시간)