[OS] Process Scheduling (프로세스 스케줄링)

운영체제는 프로세스를 효율적으로 가동시켜 작업 효율을 늘리기 위해 스케줄링 기법을 사용한다. 스케줄링이 무엇인지 알아보자.

---

배경

Multiprogramming (멀티 프로그래밍)

시스템에는 소수의 프로세서에 다수의 프로세스가 존재한다. 시스템은 많은 양의 프로세스를 최대한 효율적으로 프로세서에 할당하려고 하고, 결국 프로세서의 사용률을 최대한 증가시켜야 한다. 2가지 자원을 관리하는 측면에서 이를 살펴보자.

 

자원 관리

• 시간 자원 공유 (Resources for time sharing)
  • 다수의 프로세스가 프로세서를 시간을 할당 받아 사용한다. (이 할당 받은 시간 단위를 time quantum 또는 time slice라고 한다.)
  • 프로세스 스케줄링의 핵심이다.
• 공간 자원 공유 (Resources for space sharing)
  • 자원을 나누고 각 프로세스가 나눠진 자원을 사용한다.
  • 메모리 관리 기법의 핵심이다.

 

점점 다뤄야 하는 프로세스의 양이 많아지면서, 운영체제에서의 스케줄링 기법은 필연적이게 되었고, 위에 나와있듯이 시간 자원을 얼마나 프로세스 별로 잘 할당하느냐가 중요한 과제다.

 

Process Scheduling (프로세스 스케줄링)

스케줄링이란, 프로세스가 생성되어 실행될 때 필요한 시스템의 여러 자원을 해당 프로세스에게 할당하는 작업을 의미하며, 여러가지 기준에 대해 공평하게 잘 분배하고 대기 시간을 최소화해야 최고의 성능 결과를 얻을 수 있다.

 

Goals of Scheduling (스케줄링 목표)

위에서 언급했듯이, 결국에는 각 프로세스를 잘 케어해 시스템 전체적인 성능을 높이는 것이 스케줄링의 궁극적인 목표다. 그러면 무엇을 기준으로 스케줄링이 잘 이루어졌다고 판단할 수 있을까?

 

일반적인 스케줄링 지표

• Mean Response time
  • 사용자가 어떤 요청을 submission하는 시점부터 첫 번째 response가 돌아올 때까지의 시간이다. 간단히 말해서, 응답을 얻을 때까지 걸리는 시간이다. 일반적으로 프로세스가 동시에 여러 개 실행되기 때문에 mean을 사용한다.
  • interactive system에서 중요한 지표이다.
• Throughput
  • 단위 시간당 종료하고 나가는 프로세스 개수로, 단순하게 생각해서 작업 처리량이다.
  • batch system에서 중요한 지표이다.
• Resource utilization
  • 주어진 구간동안 특정 자원이 얼마나 사용되었는 지에 대한 지표이다.
  • 마찬가지로 batch system에서 중요한 지표이다.
• Turnaround time
  • 어떤 요청이 submission된 후에 실행을 완전히 마칠 때까지의 시간이다.
  • response time과 혼동하기 쉬운 개념이므로 주의해야 한다.
• Waiting time
  • 프로세스가 ready queue에서 대기한 시간의 총합이다.
• Predictability
  • 예측을 통해 response time을 줄이고, 얼마나 분산을 시킬 수 있는지에 대한 지표이다.
• Fairness
  • 얼마나 프로세스들에게 자원을 공평하게 할당했는지에 대한 지표이다. 특정 CPU를 편애해서는 안된다.

 

Scheduling Criteria (스케줄링 기준)

그러면 스케줄링은 어떤 기준으로 해야 효율적일지에 대해서도 알아보자.

• Process characteristics
  • I/O-bound인지 compute-bound인지 구분한다. 일반적으로는 I/O-bound 프로세스를 먼저 스케줄링 해주는데, 왜냐하면 먼저 스케줄링 된 I/O-bound 프로세스는 CPU를 할당받고 time quantum을 아주 조금 사용한다.
    즉, running 상태에서 얼마 지나지 않아 I/O 요청을 받고 CPU를 반납하기 때문에 compute-bound가 이어서 CPU를 할당받을 수 있다. I/O-bound는 I/O device를 활용하고 compute-bound는 CPU를 병렬적으로 사용하게 되므로 일반적으로 선호되는 것이다.
  • 또 batch system인지 interactive system인지에 따라서도 다르다.
• Urgency of the process
  • Hard real-time (정확히 시간을 맞춰야 한다.), soft real-time, non-real-time (deadline이 없다.)
• Process type and importance
  • 애플리케이션의 중요성을 고려한다.
• Service time of the process
  • CPU burst time
  • 일반적으로 burst time이 짧은 프로세스를 먼저 처리하면 좋다.
• Process priority
  • Priority-based scheduling에서 사용된다.

 

Scheduling Level (스케줄링 수준)

스케줄링을 어느 관점에서 바라보느냐에 따라 엄밀한 의미가 달라지게 된다. Long-term, Medium-term, Short-term scheduling으로 나눌 수 있다. 현재까지 다루는 내용은 주로 Short-term scheduling에 관한 내용이다.

• Long-term scheduling
  • Job scheduling, admission scheduling, high-level scheduling으로도 불린다.
  • 여러 Job들 중에서 어떤 것을 먼저 커널에 등록시켜 프로세스로 생성시킬 지 정하는 것이다.
    • 따라서 multiprogramming degree를 통제할 수 있다.
    • I/O-bound 프로세스와 compute-bound 프로세스를 적절하게 섞어 비율을 조정해야 한다.
  • 대부분의 time-sharing systems에서는 job이나 command가 곧바로 프로세스로 등록된다.
• Medium-term scheduling
  • Intermediate-level scheduling으로도 불린다.
  • 메모리 할당에 관여한다.
    • Swapping (swap-in/swap-out)
  • 운영체제의 메모리 관리 기법에 의존적이다.
• Short-term scheduling
  • Process scheduling, low-level scheduling으로도 불린다.
  • 프로세스 사이에서 어떤 프로세스에 CPU를 할당해 ready 상태에서 execute 상태로 바꿀 것인지 선택한다.
  • interrupt, system call으로 인한 context switching이 일어나는 것과 밀접한 관련이 있다.
  • CPU 빈도수가 높기 때문에 스케줄링을 빠르게 진행해야 한다.

 

Scheduling Policies (스케줄링 정책)

Preemptive / non-preemptive scheduling (선점형 / 비선점형 스케줄링)

• Preemptive scheduling (선점형 스케줄링)
  • 현재 실행중인 프로세스의 의도와 상관없이 쫓아내고 다른 프로세스에게 CPU를 할당한다.
    • 따라서 유연하고, 성능 면에서 유리하다.
  • time-sharing systems과 real-time systems에서 사용된다.
  • 높은 context switching overhead가 발생한다.

• Non-preemptive scheduling (비선점형 스케줄링)
  • 프로세스는 CPU를 원하는 만큼 사용한다. 즉, 주도권이 프로세스에게 있다.
    • 운영체제의 관여가 낮아지는만큼 context switching overhead도 낮다는 장점이 있다.
    • 하지만 priority inversions(우선순위 역전)이 발생한다.
    • 따라서 mean response time도 길어지게 된다.

 

Priority (우선순위)

• Static priority (external priority)
  • 고정된 우선순위로, 프로세스의 생애동안 우선순위가 바뀌지 않는다.
  • 외부에서 주어지는 경우가 많다.
  • 환경에 따라 적응하는 것이 아닌 만큼 간단하고 overhead가 낮다.
• Dynamic Priority (internal priority)
  
  • 프로세스가 생성될 때 처음 우선순위가 주어지고, 프로세스와 시스템의 상태(상황)이 변할 때마다 바뀔 수 있다.
  • 적응을 위한 유동적인 우선순위로 복잡하고 높은 overhead가 발생한다.
  • 일반적으로 많이 사용된다.