[오퍼레이팅 시스템] Scheduling

Scheduling

 

[ Non-preemption & Preemption ]

  · Non-preemption
    : Process가 수행 중일 시 Priority가 높은 것이 들어와도 끝날 때 까지 Context Switch를 하지 않는 방식. (System Call)
    : ~Linux 2.4 버전까지는 이러한 방식으로 Kernel이 구성되었다.
 
  · Preemption
    : Process가 수행 중일 시 Priority가 높은 것이 들어오면 중간에 Context Switch를 하는 방식. (System Call)
    : Linux 2.6 버전부터 이러한 방식으로 Kernel이 구성되었다.
    : Real-Time 응용을 위해 도입.
 

[ Dispatcher ]

  : Scheduler에 의해 선택된 Process 또는 Thread에게 CPU를 할당하기 위해 Context 저장과 복원을 담당하는 모듈.
  : Context Switch를 통한 Process State 전환의 역할을 가짐.
 

[ Scheduling Criteria ]

  · CPU Utilization : CPU 활용률
  · Throughput : 단위 시간당 완료되는 Process의 수
  · Turnaround Time : Process가 완료될 때 까지 걸린 시간
  · Waiting Time : Process가 Ready Queue에서 대기한 시간
  · Response Time : Process가 작업을 요청한 후, 최초의 응답을 받기까지 걸린 시간
 
  ※ 보통 Average Waiting Time을 최소화하는 Algorithm 작성.
 

[ Scheduling Algorithm ]

  · FCFS (First-Come, First-Served)
    : 가장 먼저 들어온 프로세스를 가장 먼저 실행.
    : 다음 수행 시간을 예측할 수 없음. → Convoy Effect

       ( I/O-Bound보다 CPU-Bound 작업이 먼저 실행된 경우, CPU를 계속 점유해 I/O-Bound 작업이 Starvation에 빠질 수 있음 )

  · SJF (Shortest-Job-First)
    : Average Waiting Time을 최소화.
    : 실용적인 알고리즘.
    : Exponential Averaging Function을 통해 수행 시간을 예측할 수 있다. 아래와 같은 점화식을 따른다.

  · Priority Scheduling
    - Static Priority : 고정 우선 순위를 통한 Scheduling 방식. Starvation 가능성이 큼.
    - Dynamic Priority : 가변 우선순위를 통한 Scheduling 방식.
  · Round-Robin
    : 일정 Time Quantum만큼 번갈아가면서 수행.
    : Response Time 측에서는 나쁘지 않으나, Overhead가 클 수 있음.
 

[ Multi-Processor Scheduling ]

  : 어떤 Procesor에 할당할 것인지에 대한 Issue.

     1) Process Affinity : 프로세스 친밀도. 친밀한 프로세스에 할당.
     2) Load Balancing : 적절하게 작업을 분산.

 
  · Affinity
    - Soft Affinity : Task가 많으면 Affinity가 없는 곳에 할당할 수 있음. → Affinity 훼손 가능
    - Hard Affinity : Affinity를 절대 보장. 프로그래머가 System Call을 통해 요청한 경우. sched_setaffinit- y
  · Load Balancing
    - Push Migration : 전체 Task가 어떻게 할당된지 확인하여 재분배를 해주는 작업. Work Load를 보는 Process 존재.
    - Pull Migration : 각각의 CPU가 자신을 모니터링하여 다른 CPU의 Task를 가져옴. (Linux 채택 방식)
 
  · Multi-level Queue
    : 여러 level의 Queue로 구성된 Scheduling 방식.
    : Task 생성 시 들어갈 Queue가 정해짐.
    : Queue 간 Scheduling 방식은 Priority 방식이다.
    : Linux에서 사용 중인 Scheduling 방식.
    - Real-Time Class : Priority Scheduling 방식을 이용하며, 동일한 Priority인 경우 FIFO와 Round Robin을 결합해 사용.
    - Conventional Class : Completely-Fair-Scheduling 방식을 이용.

       ( CFS : Fair을 유지하는 것을 목표로 하며, Fair는 특정 시점에서 가능한 한 비율을 유지하는 것을 의미한다.
                   이때 비율은 Weight(Priority)에 의거하여 결정되며, 이를 위해 Virtual Time Mechanism이 이용된다.
                   vruntime이 적을수록 높은 priority로 보며, 이는 Red-Black Tree로 구현되어 있다.
                   vruntime += (NICE_0_LOAD / se -> load.weight) * delta_exec의 수식으로 이루어짐.
                   vruntime이 동일한 경우, 이전에 수행되지 않은 Process 선택.