Scheduling: Scheduling Processes: Algorithms

What are some well known scheduling algorithms?

아래의 모든 예에서 

Process 1: Runtime 1000ms

Process 2: Runtime 2000ms

Process 3: Runtime 3000ms

Process 4: Runtime 4000ms

Process 5: Runtime 5000ms

라고 가정합니다.

Shortest Job First(SJF)

• P1: 0ms에 도착
  
• P2: 0ms에 도착
  
• P3: 0ms에 도착
  
• P4: 0ms에 도착
  
• P5: 0ms에 도착
  

모든 프로세스들은 동시에 도착하고  Scheduler는 가장 짧은 CPU time을 사용하는 프로세스를 먼저 처리합니다. 눈에 띄는 문제점은 프로그램이 동작하기 전에 run time이 얼마나 될지 미리 알고 있어야 할 필요가 있다는 것입니다.

기술적인 메모: 현실적인 SJF의 구현은 총 실행 시간을 사용하는 대신 burst time(프로그램이 더 이상 동작할 준비가 되지 않을 때까지 미래의 계산 실행을 포함한 총 CPU시간)을 사용해 이루어집니다. burst time의 예상은 이번 burst time을 기반으로 하는 기하급수적으로 감소하는 가중 평균을 사용합니다.  여기서는 설명을 위해 대신 프로세스의 총 실행 시간을 사용했습니다.

장점

짧은 작업이 먼저 실행됩니다.

단점

전지전능한 알고리즘이 필요합니다(미래의 상황을 먼저 알아야합니다).

Preemptive Shortest Job First(PSJF)

PSJF는 SJF와 유사하지만, 현재 job의 총 running time보다 더 짧은 runtime을 가지는 프로세스가 ready queue에 들어온다면 대체되어서 실행됩니다.(아래의 예처럼 그 시간이 같다면 알고리즘에 따라 선택이 가능합니다) 스케쥴러는 프로세스의 총 runtime을 사용합니다. 만약 reamining time을 최소화하고 싶다면, PSJF의 변종인 Shortest Remaining Time First(SRTF)를 사용합니다.

• P2: 0ms에 도착
  
• P1: 1000ms에 도착
  
• P5: 3000ms에 도착
  
• P4: 4000ms에 도착
  
• P3: 5000ms에 도착

위 그래프는 알고리즘이 어떻게 동작하는지 보여줍니다. 가장 먼저 P2가 도착했으므로 P2가 먼저 실행됩니다. 그리고 나서 P1이 1000ms에 도착하면 P2sms 2000ms동안 동작하므로 스케쥴러는 선점적으로 P2를 정지시키고 P1을 수행합니다(이것은 순전히 알고리즘에 달렸습니다 - 남은 시간이 똑같으므로!) 그리고 나서 P2도 모두 수행되고 나면 P5가 도착합니다. 현재 동작하는 프로세스가 없으므로 P5가 동작하고 P4가 도착했을 때 P5의 runtime과 같으므로 P4가 수행됩니다. 마지막으로 P3가 도착했을때 P4 대신 선점해서 동작하고 P3가 끝나면 P4가, 마지막으로 P5가 동작합니다.

장점

짧은 작업이 먼저 수행되는 것을 보장합니다.

단점

여전히 전지전능한 알고리즘이 필요합니다(미래의 상황을 먼저 알아야합니다).

First Come First Served(FCFS)

• P2: 0ms에 도착
  
• P1: 1000ms에 도착
  
• P5: 3000ms에 도착
  
• P4: 4000ms에 도착
  
• P3: 5000ms에 도착

프로세스들은 도착한 순서대로 스케쥴된다. FCFS의 장점 중 하나는 알고리즘이 단순하다는 것이다. ready queue는 단순한 FIFO(First In First Out) 큐입니다. FCFS는 Convoy Effect의 부작용이 있습니다.

위의 예에서는 P2가 도착하고, P1이 도착하고, P5가 도착하고, P4가 도착한 후 P3가 도착합니다. P5에서 Convoy effect가 발생하는 것을 알 수 있습니다.

장점

구현이 단순합니다.

단점

오랫동안 동작하는 프로세스가 다른 프로세스들을 블록합니다.

Round Robin(RR)

• P1: 0ms에 도착
  
• P2: 0ms에 도착
  
• P3: 0ms에 도착
  
• P4: 0ms에 도착
  
• P5: 0ms에 도착

Quantum = 1000ms

모든 프로세스들은 동시에 도착합니다.

P1이 1퀀텀을 사용해 종료됩니다. P2도 1퀀텀을 사용한 후 정지되어 P3가 동작합니다. 나머지 모든 프로세스들이 1퀀텀씩 사용해 동작 후 다시 P2로 돌아갑니다. 이 동작들은 모든 프로세스가 종료될 때까지 반복됩니다.

장점

공정성을 보장합니다.

단점

프로세스 수가 증가할 수록 스위칭의 횟수가 증가합니다.

Priority

프로세스들은 우선 순위 값에 따라 스케쥴됩니다. 예를 들어 네비게이션 프로세스는 로그를 남기는 프로세스보다 더 높은 우선 순위로 동작할 것입니다.