프로세스 스케줄링

• 어떤 프로세스에게 CPU를 할당할지 결정하는 작업
• 프로세스의 작업 처리율과 CPU 사용률을 증가시키고 오버헤드와 기아 현상을 낮춰 시스템 성능 향상을 목적으로 한다.
  • 즉, CPU가 노는 거 없이 효율적으로 일을 계속 할 수 있도록 하는 것
• CPU 스케줄링의 척도
  • 응답 시간(Response Time)
    • 작업이 실행되기까지 걸린 시간
  • 반환 시간(Turn Around Time)
    • 실행시간과 대기시간을 모두 합한 완료까지 걸린 시간
• 선점 스케줄링
  
  • 운영체제가 프로세스에 할당된 CPU 제어권 뺏을 수 있는 방식
  • 각 프로세스에 빠른 응답 지원하지만 ContextSwitching이 빈번하게 일어나 오버헤드가 증가
  • 종류
    • SRT(Shortest Remaining Time First)
      • 새로운 프로세스 요청이 들어온 시점에서 현재 남은 작업 시간이 짧은 프로세스에게 CPU 할당
      • 기아현상 발생할 수 있음
    • Round Robin
      • FCFS처럼 큐의 순서대로 CPU를 할당하지만 각 프로세스가 동일한 Time Quantum 만큼 CPU를 할당 받아 사용하고 CPU를 반환하고 작업이 남았다면 큐에 맨뒤에 추가
        • Time Quantum / Time Slice : CPU 할당 시간
      • Time Quantum이 크다면 FCFS처럼 동작하고, 너무 작다면 ContextSwitching이 자주 발생해 오버헤드 증가
      • 응답 시간이 빠르고 같은 Time Quantum 만큼 CPU를 사용하기 때문에 공정한 스케줄링이다.
    • Priority Scheduling
      • 프로세스마다 우선순위를 배정하여 우선순위에 따라 CPU를 할당하는 방식
      • 숫자가 작을수록 우선순위가 높다
      • 우선순위가 더 높은가 오면 CPU를 뺏어 우선적으로 할당
      • 기아 현상이 발생할 수 있어 Aging을 통해 해결함
      • Aging
        • 우선순위가 낮은 프로세스라도 대기 시간에 따라 우선순위를 높여줌
    • Multilevel-Queue
      • 우선 순위가 다른 큐를 여러개 사용하는 방식으로 우선순위가 높을 수록 CPU를 먼저 할당 받는다.
      • 각각의 큐마다 다른 스케줄링 방식을 사용하고 보통 상위는 Round Robin 방식으로 하며 순위가 높을 수록 Time Quantum이 짧고, 하위는 FCFS방식으로 처리
      • 기아 현상과 공평성 문제가 있음
• 비선점 스케줄링
  • 운영체제가 프로세스에 할당된 CPU 제어권을 강제로 뺏을 수 없는 방식
  • 필요한 ContextSwitching만 일어나기 때문에 상대적으로 오버헤드가 적지만, 프로세스 배치에 따라 효율성이 떨어짐
  • 종류
    • FCFS(First Come First Served)
      • 선입 선출 방식으로 큐에 들어온 프로세스에 CPU 할당
      • 실행시간이 긴 작업이 들어오면 효율성이 떨어진다.
        • 짧은 실행시간이 있는 프로세스가 먼저 들어온 긴 작업때문에 오래 기다리게 됨
    • SJF(Shortest Job First)
      • 도착한 순서에 상관없이 실행시간이 가장 짧은 프로세스에게 CPU를 할당
      • 실행시간이 긴 프로세스이 경우 무기한 대기할 가능성이 있다(기아 현상)
        • 계속 짧은 실행시간의 프로세스가 들어오면 계속 기다리게 된다.
    • HRN(Highest Response-ratio Next)
      • 우선순위를 계산하여 CPU를 할당(SJF의 단점을 보완)
      • 우선 순위 = (대기시간 + 실행시간)/실행시간