CPU 스케줄링(CPU Scheduling)

스케줄링(Scheduling)

• 여러 프로세스가 번갈아 사용하는 자원을 어떤 시점에 어떤 프로세스에 할당할지 결정하는 것을 의미한다.

---

스케줄링의 목적

• 자원할당의 공정성을 보장
• 단위시간당 처리량 최대화
• 적절한 반환시간을 보장
• 예측 가능성 보장과 오버헤드 최소화 등이 있다.

프로세스에 프로세서가 할당되면 다음 사항중 하나가 일어나게 된다.

1. 프로세스가 입출력 요청을 보내고 입출력 큐에 들어간다
2. 프로세스가 새로운 프로세스를 생성(fork)하고 생성한 프로세스의 종료를 기다린다.
3. 프로세스가 시간 할당량을 초과(시간 종료 time out)하면 준비큐에 들어간다.
4. 인터럽트로 프로세서에서 제거된 프로세스는 다시 준비큐에 들어간다.

비선점 & 선점 스케줄링

• 비선점 스케줄링(Non Preemptive Scheduling)
  • 한 프로세스가 자원을 선택했을 때 다른 프로세스가 해당 자원을 빼앗을 수 없다.
  • 실행 시간이 짧은 프로세스가 실행 시간이 긴 프로세스를 기다리는 대신 모든 프로세스를 공정하게 관리한다.
  • 우선 순위가 높은 프로세스를 중간에 입력해도 대기중인 프로세스는 영향을 받지 않으므로 응답시간을 예측하기 쉽다.

• 선입 선처리 알고리즘(FCFS, First Come First Served)
  • 비선점 스케줄링(Non Preemptive Scheduling)
  • 일괄 처리 시스템에서는 매우 효율적이나 빠른 응답을 요청하는 대화식 시스템에는 적합하지 않다.
  • 프로세서를 점유한 프로세스가 종료하든지 입출력을 요청하여 자신의 프로세서를 해제하기 전까지는 프로세서를 계속 점유하므로 시분할 시스템에서는 사용하기가 곤란하다.
  • 시분할 시스템은 프로세서를 정기적으로 공유해야 하기 때문이다.
  • 장점
    • 스케줄링의 이해와 구현이 단순하다.
      • 준비 큐에 있는 모든 프로세스가 결국 실행되므로 기아 없는 공정한 정책이다.
      • 프로세서가 지속적으로 유용한 프로세스를 수행하여 처리율이 높다.
  • 단점
    • 비선점식이므로 대화식 프로세스에는 부적합하다.
      • 장기 실행 프로세스가 뒤의 프로세스를 모두 지연시켜 평균 대기시간이 길어져 최악의 대기시간이 된다.
      • 긴 프로세스가 실행되는 동안 짧은 프로세스가 긴 대기시간으로 호위 효과가 발생할 수 있다.
• HRN 스케줄링
  • 비선점 스케줄링(Non Preemptive Scheduling)
  • SJF의 약점이었던 긴 작업과 짧은 작업 간의 지나친 불평 등을 어느 정도 보완했다.
  • 우선순위 = 서비스를 받을 시간 + 대기한 시간 / 서비스를 받을 시간 으로 우선순위를 구한다.
  • 서비스를 받을 시간이 분모에 있으므로 이 시간이 짧은 작업일수록 우선순위가 높다.
  • 대기한 시간이 분자에 있으므로 이 시간이 긴 작업일수록 우선순위가 높다.
  • 장점
    • 자원을 효율적으로 활용한다.
    • 기아가 발생하지 않는다.
  • 단점
    • 오버헤드가 높을 수 있다(메모리와 프로세서 낭비)

• 선점 스케줄링(Preemptive Scheduling)
  • 현재 실행 중인 프로세스를 인터럽트 할 수 있거나 준비 상태로 이동할 수 있다.
  • 프로세스 하나가 장시간 동안 프로세서를 독점하는 것을 방지하기 때문에 모든 프로세스에 프로세서를 서비스할 기회를 늘릴 수 있다.
  • 우선순위가 높은 프로세스들이 긴급 처리를 요청할 때 유용하다.
  • 시분할 시스템, 실시간 시스템에서 빠른 응답 시간을 유지하는데 선점 스케줄링은 필수이다.
  • 오버 헤드가 커질 수 있어 이를 효과적으로 이용하기 위해 메모리에 프로세스가 많이 적재되어 있어야 한다.
  • 프로세서를 사용 가능할 때마다 실행할 수 있는 프로세스들이 준비 상태에 있어야 효과적이다.
  • 문맥교환 시간이 소요되므로 반드시 비선점보다 유리하다고 할 수 없다.
• 라운드 로빈(Round Robin)
  • 선점스케줄링(Preemptive)
  • 작은 단위의 시간인 규정 시간량(time quantum) 또는 시간 할당량(time slice)을 정의 한다.
  • 대화식 프로세스에 비교적 빠르게 반응할 수 있다.
  • 장점
    • 모든 프로세스가 프로세서의 동일한 점유율과 제한된 대기시간으로 공정하며 기아가 발생하지 않는다.
    • 실행 큐에 프로세스 수를 알고 있을 때 구현이 용이하다.
    • 강한 상호작용과 프로세스의 짧은 응답시간, 특히 프로세스 최악의 응답시간을 알 수 있다.
    • 작업 길이가 다양할 때는 이전 작업을 마친 후보다 규정 시간량을 마치고 다음 작업으로 이동하기 때문에 평균 대기시간이 선입선처리와 최소작업 우선 스케줄링보다 적다.
  • 단점
    • 성능은 규정 시간량의 길이에 따라 달리지므로 작업이 비슷한 길이가 좋다. 너무 길면 선입선처리로 변하고, 너무 짧으면 많은 문맥 교환으로 비용 부담이 크다.
    • 하드웨어 타이머가 필요하다.
    • 미완성 작업은 각 규정 시간량을 마친 후 프로세서를 기다리므로 평균 처리 시간이 높다.

선점 비선점 둘다 가능

• 최소작업 우선 스케줄링(SJF, Shortest Job First)
  • 실행 시간이 가장 짧은 작업에 할당하는 방법이다.
  • 선점, 비선점이 가능하다.
  • 장점
    • 항상 실행 시간이 짧은 작업을 신속하게 실행하므로 평균 대기시간이 가장 짧다.
  • 단점
    • 초기의 긴 작업을 짧은 작업을 종료할 때까지 대기시켜 기아가 발생한다.
    • 기본적으로 짧은 작업이 항상 실행되도록 설정, 불공정한 작업을 실행한다.
    • 실행 시간을 예측하기가 어려워 실용적이지 못하다.
• 우선순위 스케줄링(Priority scheduling)
  • 우선순위가 가장 높은 프로세스에 프로세서를 할당한다.
  • 우선순위가 동일한 프로세스들은 선입선처리 순서로 스케줄링한다.
  • 선점,비선점이 가능하다.
  • 무한정지와 기아가 발생할 수 있다.
  • 실행 준비는 했으나 우선순위가 높은 프로세스가 계속 들어오면 우선순위가 낮은 프로세스는 무한정 기다려야 한다.
  • 에이징이란 오래 대기하는 프로세스들의 우선순위를 점진적으로 증가시키는 방법으로, 시간이 지나면 점차 프로세스의 우선순위가 높아진다.
  • 장점
    • 각 프로세스의 상대적 중요성을 정확히 정의할 수 있어 좋다.
    • 다양한 반응으로 실시간 시스템에 사용 가능하다.
  • 단점
    • 높은 우선순위 프로세스가 프로세서를 많이 사용하면 우선순위가 낮은 프로세스는 무한정 연기되는 기아가 발생할 수 있다.

스케줄링 알고리즘의 선택 기준

• 프로세서 사용률
  • 프로세서를 항상 실행 상태로 유지하여 유휴 상태가 되지 않도록 한다. 따라서 입출력 중심 작업보다는 프로세서 중심 작업을 실행한다.
• 처리율
  • 단위시간당 완료하는 작업 수가 많도록 짧은 작업을 우선 처리하거나 인터럽트 없이 작업을 실행한다.
• 반환 시간
  • 작업이 메모리에 들어가기까지 걸린 시간, 준비 큐에 모무는 시간, 실행 시간, 입출력 시간 등 작업을 완료하는 데 소요되는 시간을 최소화하도록 일괄 처리 작업을 우선 처리 한다.
• 대기 시간
  • 작업의 실행 시간이나 입출력 시간은 영향을 줄 수 없으므로 준비 큐에서 기다리는 시간을 최소화하도록 사용자 수를 제한한다.
• 반응시간
  • 작업을 요청한 시간부터 반응을 시작하는 시간(첫 번째 응답)까지 간격으로, 대화형 시스템에서 중요한 사항이다. 따라서 대화식 작업을 우선 처리하고 일괄 처리 작업은 대화식 작업을 요청하지 않을 때 처리한다.