#3 - 2) 스케줄링 기법 및 종류와 Aging(에이징) 기법

※ 이 글을 작성하기 전에 본인은 이 분야의 전문성을 가진 전문가가 아님을 미리 밝힙니다. ※

#1. 선점형 기법과 비 선점형 기법

스케줄링은 크게 2가지 기법으로 나눌 수 있다.

1. 비선점형 스케줄링 기법

2. 선점형 스케줄링 기법

 

#1 - 2) 비선점형 스케줄링 기법

비선점형 스케줄링 기법이라는 것은, 이미 할당된 CPU를 다른 프로세스가 중간에 강제로 빼앗을 수 없는 기법을 비선점형 기법이라고 한다.

먼저 실행된 프로세스가 먼저 처리되기 때문에 공정한 처리가 가능하다고 볼 수 있으며, 일괄적인 처리 방식에는 적합하다.

하지만, "짧지만 중요한 작업이 길지만 중요하지 않은 작업에 밀려서 긴 시간동안 기다려야 하는 경우가 발생" 할 수도 있다.

#1 - 3) 선점형 스케줄링 기법

선점형 스케줄링 기법이라는 것은, 준비 상태(=Ready Queue)에 있는(실행을 대기하고 있는) 프로세스들 중에서 우선순위가

가장 높은 프로세스에게 먼저 CPU를 할당하는 기법이다.

즉 ! 우선순위에 따라서 실행중인 프로세스가 실행을 멈추고 다른 프로세스에게 CPU를 빼앗길 수 있는 기법이다.

 

#2. 비선점형 스케줄링 기법 종류

#1. FIFO(First In First Out) = FCFS(First Come First Serve)

- 먼저 도착한 프로세스가 먼저 CPU를 할당하는 방식이다.

- 공평성이 유지되지만, 중요한 작업이 중요치 않은 작업에 밀려서 늦게 처리되는 문제점이 발생할 수 있다.

- 또한, "Convoy Effect" 현상이 발생할 수 있다. 실행시간이 긴 프로세스가 먼저 도착하게 되면,

  효율성이 떨어지는 현상이 발생한다.

#2. SJF(Shortest Job First)

- 준비상태에 누가 먼저 도착했는지와 상관없이, 실행시간(CPU Burst Time)이 가장 짧은 프로세스에게 CPU를 할당하는 방식.

- 짧은 작업들을 우선적으로 처리하다 보니, 평균 대기시간이 가장 적은 최적의 스케줄링 기법이다.

- 하지만 ! "Starvation(기아현상)" 이 발생할 수 있다. 실행시간이 상대적으로 긴 프로세스의 경우, 실행시간이 짧은 프로세스들

   에게 밀리고 밀려서 거의 영원히 CPU를 할당받을 수 없게되는 현상이 발생한다.

#3. HRN / HRRN (Highest Response Ratio Next)

- SJF 기법에서 비교적 실행시간이 긴 프로세스가 가질 수 있는 불리함을 보완한 스케줄링 방식이다.

- "우선순위"를 계산해서 프로세스들에게 순서를 부여 하는 방식이다.

- "우선순위 = (대기시간 + 실행시간) / 실행시간" 을 통해서 계산되어진다.

- 위의 공식에서, "대기시간"이 길어질 수록, 더 큰 값을 가지게 되므로, "실행시간이 길다는 이유로, 실행시간이 짧은 프로세스에

   게 밀려서 오랫동안 기다린 프로세스가 더 높은 우선순위를 가지게 만든다".

- ex)

위와 같이 3개의 프로세스가 존재한다고 생각해보자.

SJF 기법에 의하면, 실행시간이 가장 긴, P2가 무조건 가장 마지막에 실행되어야 할 것이다.

하지만, HRRN 기법에 의해서 위의 프로세스들의 우선순위를 구해보면 다음과 같다.

P1 = (5 + 10) / 10 = 1.5

P2 = (20 + 20) / 20 = 2

P3 = (15 + 5) / 5 = 4

더 높은 값부터 차례대로 우선순위를 부여하게 되면, P3 - P2 - P1 순으로 실행되어 질 것이다.

P2의 입장에서 보면, P1보다 실행시간이 훨씬 길지만, P1보다 먼저 실행되는 것을 확인할 수 있다.

#4. 우선순위(Priority)

- 프로세스들에게 특정 우선순위를 부여하여서, 상대적으로 더 높은 우선순위를 가지는 프로세스를 대기상태의 가장 첫 번째에

   넣는 방식이다.

- "비선점 스케줄링 우선순위 기법"은 실행되고 있는 프로세스는 제외하고, 대기상태에 있는 프로세스들 끼리 우선순위를

   비교하게 되고, 우선순위가 가장 높은 프로세스를 대기 상태의 첫 번째로 배치하게 된다.

- 즉, 현재 실행되고 있는 프로세스가 끝난다면, 그 다음으로 우선순위가 가장 높은 프로세스가 진행되어 진다.

- 하지만 ! "Starvation(기아현상)" 이 발생할 수 있다. 상대적으로 높은 우선순위를 갖지 못하는 프로세스가 계속해서 높은

   우선 순위를 갖지 못해서 거의 영원히 실행되지 못하는 현상이 발생한다.

#5. 기한부(Deadline)

- 프로세스가 사용할 수 있는 CPU의 시간을 정해주고, 그 시간 안에 프로세스를 완료하도록 하는 기법이다.

- 주어진 시간 내에 완료되지 못할 경우, 해당 프로세스는 제거되거나 처음부터 다시 실행되어야 하므로 부담이 매우 큰 기법이다.

- 시스템은 프로세스에게 정확한 시간을 할당해 주어야 하며, 사용자는 시스템이 요구한 프로세스에 대해서 정확한 정보를

   제공해줘야 하는 기법이다.

 

#3. 선점형 스케줄링 기법

#1. RR(Round-Robin)

- 비선점 기법인 FIFO(FCFS)를 선점형 기법으로 변환한 스케줄링 기법이다.

- FIFO와 같이 먼저 들어온 프로세스가 먼저 CPU를 할당받게 되지만, 각 프로세스들은 할당된 시간만큼만 CPU를 사용할 수

  있게 된다. 만약, 해당 시간내로 완료하지 못했다면, 대기 상태의 가장 마지막으로 들어가게 된다.

- 시분할 시스템을 위해서 고안된 기법이다.

- CPU 사용시간이 랜덤한 프로세스들이 섞여 있을 때 효율적인 기법이다.

- 응답시간이 매우 최적화 되어있는 공정한 스케쥴링 기법이다.

- 하지만 ! 프로세스에게 할당되는 CPU 시간이 너무 길다면, FIFO와 같아지는 현상이 발생하고, CPU시간이 너무 짧아진다면,

  Context-Switching이 자주 일어나서 오버헤드가 발생할 가능성이 있다.

  [ Context-Switching에서 오버헤드가 발생하는 이유 알아보기(Click) ]

 

#2. SRT(Shortest Remaining Time)

- 비선점 기법인 SJF 스케쥴링 기법을 선점형 기법으로 변환한 스케줄링 기법이다.

- 현재 실행준인 프로세스의 남은 시간과 준비상태 대기열에 새로 도착한 프로세스의 실행시간을 비교하여 가장 짧은 실행 시간을

   요구하는 프로세스에게 CPU를 할당하는 기법이다.

 

#3. MLQ(Multi Level Queue) (다단계 큐 스케줄링)

- 프로세스들을 특정 그룹으로 분리하여, 각 그룹마다 독자적인 Queue를 이용해서 스케줄링 하는 기법이다.

- "특정 그룹으로 분리" 한다 라는 것은, 여러 단계로 분할할 수가 있지만, 크게 본다면 사용자와 상호작용하는

   전면작업(Foreground Task)와 그렇지 않은 후면작업(Background Task)로 분리할 수 있다.

   (실제로, 이렇게 2가지로만 나눠서 사용하지는 않습니다. 프로세스의 특성 및 종류에 따라서 여러개로 나뉘어 집니다.)

- 전면작업은 상대적으로 우선순위가 더 높다고 판단하고, 후면작업은 상대적으로 덜 중요하다고 판단할 수 있다.

- 이 때, 전면작업 Queue에 들어 있는 프로세스들에 대해서는 Round-Robin과 같이 효율적이 빠르게 실행될 수 있는

  기법을 사용하게 되고, 후면작업 Queue에 들어있는 프로세스들은 FIFO 기법으로 진행되어 진다.

- 중요도에 따라서 1차적으로 어떤 Qqueue에 저장할지 우선순위를 정하고, 두 번째로 각 Queue에서는 서로 다른 알고리즘

  혹은 다른 스케줄링 기법들을 통해서 Queue에 저장된 프로세스들의 우선순위를 정하게 된다.

  이러한 구조 때문에 프로세스의 우선순위 처리에 대한 효율성을 높일 수 있다.

- 하지만 ! 한번 특정 Queue에 들어가는 순간, 다른 Queue로 이동되거나 변경되는 것은 불가능하기 때문에 스케줄링에 대한

   오버헤드가 낮다는 장점이 있는 반면, 유연하지 못하다는 단점이 존재한다.

- MLQ의 구조를 그림으로 간단하게 표현하면 다음과 같다.

 

 

#4. MLFQ(Multi Level Feedback Queue) (다단계 피드백 큐 스케줄링)

- 특정 그룹의 Queue에 들어간 프로세스가 다른 Queue로 이동하거나 변경이 불가능한 MLQ 기법을, 서로 다른 Queue로도

   이동할 수 있도록 개선한 기법이다.

- MLQ 방식과 달리, 처음부터 특정 그룹으로 분리한 후, 적합한 Queue에 들어가는 방식이 아닌, 무조건 1차적으로는 "가장 중요

   한 작업이라고 판단되는 프로세스들이 모이는 Queue"로 들어가게 된다.

- 위에서 들어간 Queue에서는 "Round-Robin"기법을 이용해서 스케줄링 되어지는데, 만약 이 때, 프로세스가 실행을 완료하지

   못한다면 그 다음 Queue로 넘어가게 된다.

- 이 다음 Queue에서는 이전의 Queue에 비해서 할당시간을 2배 더 큰 값을 할당해준다.

- 위와 같은 방시긍로 프로세스가 주어진 Queue에서 모두 처리되지 못한다면, 가장 중요도가 낮다고 판단되는 Queue로

  최종적으로 들어가게 되고, 이 Queue에서는 FIFO(FCFS) 기법으로 처리하게 된다.

- 즉 ! RoundRobin기법의 할당시간을 보고 우선순위를 예측하고 변경하면서 사용하는 기법이다.

- MLFQ의 구조를 그림으로 간단하게 나타내면  다음과 같다.

 

 

#5. 우선순위(Priority)

- 우선순위 기법에 대해서 이야기 하기 전에 ! 우선순위 기법은 위에서 "비선점형 스케줄링 기법" 이라고 이야기 했었다.

- 하지만 ! 우선순위 기법은 선점형으로도 사용이 가능하다.

- 비선점형 우선순위 기법에서는, 대기 상태에 있는 프로세스들간의 우선순위를 비교하였지만, 선점형 우선순위 기법에서는

  현재 실행중인 프로세스까지 함께 비교하여서, 만약 현재 실행중인 프로세스보다 우선순위가 더 높은 프로세스가

  대기열에 들어오게 된다면, 실행중인 프로세스를 멈추고 더 높은 우선순위인 프로세스를 진행하게 된다.

- 이 또한, 마찬가지로 우선순위가 상대적으로 낮은 프로세스가 거의 영원히 CPU를 할당받지 못하는 문제가 발생한다.

 

#4. Aging(에이징) 기법

- 에이징 기법은 시스템에서 특정 프로세스의 우선순위가 낮아서 무한정 기다리는 경우를 방지하기 위해서 기다린 시간에

  비례해서 일정 시간이 지나면 우선순위를 한 단계식 높여주는 방법이다.

- "무한연기 or 기아상태를 예방" 하기 위한 기법이다.

- SJF 기법에서 상대적으로 실행시간이 긴 프로세스들이 거의 영원히 CPU를 할당받지 못하는 상황을 예방하기 위해서

  Aging기법을 도입해 HRN(HRRN) 기법으로 사용하는 것.

- MLQ 기법에서 높은 우선순위를 먼저 처리 및 유연한 방법으로 처리하기 위해서 Aging 기법을 도입해 MLFQ 기법으로

  사용하는 것.