[Operating System] Process Scheduling (5/5 수정)

Process Scheduling

• CPU를 사용하려고 하는 Process들 사이의 우선 순위를 관리하는 일
• 처리율/CPU 이용율 증가, 오버헤드/응답시간/반환시간/대기시간 최소화
• 장기 스케줄링 - 어떤 process를 커널에 등록할 것인가를 정함
• 중기 스케줄링 - 어떤 process에게 메모리를 할당할 것인가를 정함
• 단기 스케줄링 - 어떤 process에게 CPU를 할당할 것인가를 정함.
• Process state에 변화가 있을 때 작동함.

 

Preemptive / Non-preemptive 

• Preemptive, 선점형
  • Scheduler가 절대적인 권한으로 사용중인 CPU를 뺏을 수 있음.
  • 빠른 응답시간을 요하는 대화식 시스템에 적합함.
  • SRT(Shortest Reamining Time), RR(Round Robin), MLQ(Multi-Level Queue), MFQ(Multi-Level Feedback Queue)
    • RR(Round Robin)
      • Time quantum, 점유시간을 정하는 것이 이슈
    • MLQ (Multi-Level Queue)
      • Ready Queue를 여러 개(통상 5개)로 나누어 queue마다 다른 priority를 부여함.
      • 낮은 priority를 가진 queue의 process가 실행되고 있다가 높은 priority의 queue에 속하는 process가 들어오면 preemption 됨.
    • MFQ (Multi-Level Feedback Queue)
      • 특정 time quantum을 가진 queue에서 quantum만큼 CPU 사용.
      • process가 끝나지 않으면 그보다 큰 time quantume을 가진 queue에서 qunatum만큼 CPU 사용
• Non-preemptive, 비선점형
  • 특정 process의 cpu 사용이 완료될 때까지 보장되는 형태
  • 순서대로 처리되는 공정성, 응답시간을 예상할 수 있음
  • preemptive에 비해 호출빈도가 낮고 context switching에 의한 overhead가 적음.
  • FCFS(First Come First Service), FIFO(First In First Out), SJF(Shortest Job First), HRN(Highest Response-ratio Next)
    • SJF(Shortest Job First)
      • 최소 average waiting time 실현 / starvation 발생 가능성 있음.
        • 해결책 - Aging (Ready Queue에 있는 프로세스에 나이를 부여하는 방법)
    • HRN(Highest Response Ratio Next)
      • (waiting time + burst time) / burst time 의 값을 priority로 함.