4 (2). 프로세스 스케줄링 : 스케줄링 기법

프로세스 스케줄링 기법

---

지난 글에서는 프로세스 스케줄링의 개념, 대표적인 성능 지표, 스케줄링 기준, 스케줄링 레벨에 대해 설명하였습니다.

지난 글에 이어 이번 글에서는 프로세스 스케줄링 기법에 대해 알아보겠습니다.

 

---

프로세스 스케줄링 기법

• 프로세스 스케줄링 기법의 필요성 

프로세스들은 컴퓨터 하드웨어 자원을 이용하여 작업을 처리합니다. 컴퓨터 시스템에 하나의 프로세스만 존재한다면 하드웨어 자원은 계속 사용가능한 상태일테니 CPU를 사용하기 위해 대기하거나 입출력 장치에서 입출력 요청을 하고, 응답을 받은 뒤 다시 CPU를 사용할 때에도 기다릴 필요가 없을 것입니다.

 

하지만 컴퓨터 시스템에 하나의 프로세스만 있는 경우는 거의 없고, 대부분은 프로세스의 개수가 CPU 개수보다 많기 때문에 프로세스간 CPU 사용을 위한 경쟁이 발생하고, 이를 효율적인 방법으로 하드웨어 자원을 할당하기 위해 도입하는 것이 프로세스 스케줄링 기법입니다. 

 

이러한 프로세스 스케줄링 기법은 더 효율적으로 프로세스를 처리할 수 있는 방법을 찾기위해 계속해서 연구되어 왔고, 다양한 종류들이 존재하고 있습니다. 그럼 지금부터 그 종류에 대해 알아보겠습니다.  

---

FSFS (First Come First Service)

• 가장 기본적인 스케줄링 기법인 FCFS는 이름에서 알 수 있듯이 먼저 온 프로세스 먼저 서비스 해주는 스케줄링 기법입니다. 
• Non-preemptive이기 때문에 CPU를 할당받은 프로세스가 CPU burst 가 끝날 때까지 CPU를 사용할 수 있습니다. 간단히 말해 CPU를 사용하고 있는 프로세스에게서 CPU를 빼앗을 수 없고, CPU를 사용할 만큼 사용한 후 CPU를 반납하게 하는 것입니다.
• 가장 먼저 온 프로세스에게 우선적으로 할당하는 기법이므로 Arrival time (도착 시간) 기준으로 프로세스 스케줄링을 합니다.
• (장점) context switching이 적게 발생하기 때문에 자원 활용도 (특히 CPU 활용도) 가 높습니다. 
  • preemptive하다면 CPU 를 할당받은 프로세스가 CPU burst가 끝나지 않은 상황에서도 할당받은 time quantum을 다 사용하면 뺏기게 됩니다. 그런데 만약 이때 남은 CPU burst이 아주 작아서 그 보다 context switching에 드는 비용이 더 크다면 그 작은 CPU burst를 위해 그보다 비용이 큰 context switching이 두번이나 더 발생하게 됩니다. 이런 경우는 아주 비효율적일 수 있습니다. non-preemptive라면 이런 불필요한 context switching 비용을 줄일 수 있습니다. 
• (단점) 하나의 프로세스가 CPU를 독점할 가능성이 있기 때문에 interactive 시스템에 적합하지 않습니다.
  • 만약 CPU burst가 아주 긴 프로세스가 CPU를 할당 받은 채 CPU burst를 완료할 때까지 돌려주지 않는 상황에서 바로 뒤에 아주 짧은 CPU burst 뒤에 I/O burst를 가진 프로세스가 있다면 뒤에 있는 프로세스가 먼저 CPU를 사용할 수 있도록 하고, I/O 처리를 위해 asleep 상태로 가서 CPU를 반납하면 이때 CPU burst 가 긴 프로세스가 CPU를 할당받는게 더 효율적이겠지요? 

---

RR (Rond-Robin)

• 이 기법은 위 FCFS에 Preemptive 특징으로 바꾼 것입니다. 
• Preemptive하기 때문에 Time quantum을 지정해 CPU 사용 시간을 제한합니다.
  • 이때 time quantum은 시스템마다 파라미터로 지정할 수 있습니다.
  • time quantum이 길수록 한 프로세스가 CPU burst가 끝나기 전에 preemptive될 확률이 적겠죠? 그래서 time quantum이 길수록 FCFS와 비슷해집니다.
  • 반면에 time quantum이 아주 작아지면 preemption이 아주 자주 발생하여 context-switching이 자주 발생할 것입니다. context switching은 커널이 수행하는 것으로 커널이 context switching을 위해 CPU를 거의 다 점유하게 되어 CPU sharing이 발생합니다.
• Time quantum 내에 CPU-burst를 모두 끝내지 못한 프로세스는 다시 대기 큐로 들어가 CPU 할당받기를 기다리고, 이 과정을 burst time이 끝날 때까지 반복합니다.
• (장점) interactive system에 적합합니다.
• (단점) context switching이 많이 일어나 커널 개입 횟수가 많아지고 이는 성능 저하의 원인이 됩니다. 

---

SPN (Short Process Next)

• Burst time이 가장 짧은 프로세스부터 먼저 스케줄링하는 기법입니다.
• 그렇다면 현재 시스템 상에 존재하는 모든 프로세스의 burst time에 대한 정보를 가지고 있어야 하는데 이는 실제로 불가능하기 때문에 정확하게는 구현할 수 없습니다.
• 그래서 이 기법은 burst time을 산술평균, 회귀분석, exponential average* 등으로 통계적 추정을 하여 사용할 수밖에 없습니다. 
  • exponential average : 여기서 T는 가장 최근에 사용한 프로세스의 CPU burst time 이고, 최근에서 멀어질 수록 그 프로세스의 영향을 작게 설정합니다. 

• Non-preemptive
• 대부분 CPU 사용 시간이 짧은 I/O-bound 프로세스를 먼저 스케줄링하겠다는 의도와 같습니다. 
• (장점) 프로세스들이 CPU 할당을 대기하는 시간이 가장 최소화됩니다. 그렇기 때문에 대기 큐에 들어가있는 프로세스의 개수가 적어 ready queue의 사이즈도 작고 시스템 내부에 프로세스의 총 개수도 최소화할 수 있습니다. 그래서 메모리를 적게 사용할 수 있습니다.
• (단점) CPU burst가 긴 프로세스는 계속 짧은 프로세스들에게 밀려 무기한으로 지연되는 starvation (=indefinite postponement, blocking) 현상이 발생할 수 있습니다. 
  • starvation 현상은 뒤에서 설명할 HRRN의 aging 기법으로 해결할 수 있습니다. 

---

SRTN (Shortest Remaining Time Next)

• 위에서 설명한 SPN에 time quantum을 도입해 preemptive로 만든 것입니다.
• 프로세스가 가진 전체 CPU burst time이 아니라 남아 있는 CPU burst time을 기준으로 그 시간이 작은 프로세스부터 스케줄링합니다.
• Ready queue에 도착한 프로세스의 남은 CPU burst time이 현재 CPU를 사용하고 있는 프로세스보다 짧은 경우 Preemption이 일어납니다.
  • 예를 들어 현재 실행 중인 프로세스의 CPU burst time이 7 인데 ready queu에 남은 CPU burst time이 4인 프로세스가 들어오면 preemption이 발생하고 context switching이 일어나 CPU burst time이 4인 프로세스가 스케줄링됩니다. 
• (장점) 빨리 끝낼 수 있는 작업은 빨리 처리할 수 있기 때문에 interactive system에 적합합니다.
• (단점) preemptive 기법의 특징의 공통점으로, context switching이 많이 발생할 수 있으며, burst time을 추정하는 오버헤드가 발생합니다. 

---

HRRN (High Response Ratio Next)

• SRN에서 CPU-burst time이 긴 프로세스가 계속해서 CPU-burst time이 짧은 프로세스들에게 우선순위가 밀려 starvation 현상이 발생할 수 있다고 했는데 이때 너무 대기 시간이 긴 프로세스는 먼저 스케줄링 할 수 있도록 하는 Aging 기법을 사용합니다.
• response ratio로 프로세스의 aging을 측정하며 이 값이 높을수록 먼저 스케줄링하는 것입니다. 

response ratio = (waiting time + burst time) / burst time 

• waintg time이 클수록, burst time이 작을수록 우선순위가 높아지는 것으로 실제로 CPU를 사용할 시간 대비 기다리는 시간이 너무 긴 프로세스의 우선순위를 높여 starvation을 방지하는 것입니다. 마트에서 카트에 한가득 계산할 물품을 실은 사람들보다 컴 한통만 계산하면 되는 사람을 먼저 계산해서 보내는 것과 같은 원리입니다.
• (장점) aging 기법으로 starvation을 예방할 수 있습니다. 
• 나머지는 SPN과 동일하고, (단점) 이 역시 response ratio 등의 계산을 위한 오버헤드가 존재합니다.

---

MLQ (Multi Level Queue)

• 위에서 설명한 기법들은 모두 하나의 Ready Queue에 우선순위에 따라 프로세스들을 나열했습니다. 
• 이 기법은 Ready Queue를 여러 개로 분리하여 사용하는 것이 가장 큰 특징입니다. 
• 위 사진의 예시처럼 system 프로세스, interactive 프로세스 등으로 프로세스를 카테고리마다 나눠 프로세스는 자신의 속성에 해당하는 큐에 진입합니다. 그리고 각 큐에 우선순위를 부여하는 기법입니다.
• 프로세스가 한번 해당 큐에 할당되면 입출력을 위해 나갔다 들어와도 영구적으로 해당 큐에만 진입할 수 있습니다. 
• 각 큐마다 우선순위도 다를 뿐만 아니라 각자 자신만의 스케줄링 매커니즘을 가지고 운영됩니다. 
  • 큐 간 스케줄링은 일반적으로 fixed priority preemptive 스케줄링을 합니다. 즉, 시스템에 지정된 스케줄링 기법에 따라 큐에 우선순위를 부여하고 preemptive가 가능한 형태입니다.
  • 큐 내부의 스케줄링은 각 큐마다 따로 설정이 가능합니다. 

---

MFQ (Multi Level Feedback Queue)

• 현재 대부분의 운영체제에 적용 중인 기법입니다. 그러니까 현재까지는 가장 실용적인 스케줄링 기법이라 할 수 있습니다.
• 여러 개의 Ready Queue를 두는 MLQ 에서 한 번 나갔다 들어와도 영원히 같은 큐에만 진입할 수 있지만 MFQ는 CPU를 사용하다 time quantum이 끝나 preemption 당해 다시 ready queue로 들어오거나 I/O를 하고 다시 들어오면서 피드백을 가지고 들어와 기존에 있던 큐보다 더 적합한 큐로 할당됩니다. 
  • 여기서 피드백은 프로세스가 CPU를 어떻게 사용했는지에 대한 정보입니다.
  • 그 정보는 time quantum 초과 여부이기 때분에 time quantum이 필요한 preemptive 기법임을 알 수 있습니다.
  • 프로세스가 time quantum을 다 사용하여 Preemption 당한 경우 CPU-burst time > time quantum이기 때문에 CPU-bound 프로세스라고 판단하여 기존에 있던 큐보다 우선순위가 낮은 큐로 들어갑니다.
  • time quantum이 끝나기도 전에 I/O 요청을 하여 asleep 을 하다가 wakeup 하여 다시 ready queue로 들어가는 경우 I/O-bound 프로세스라고 판단하여 기준의 우선순위를 가진 큐로 다시 들어갑니다.
  • 이러한 방식으로 I/O-bound 프로세스와 CPU-bound 프로세스를 점진적으로 구분하게 됩니다. 
• 우선순위가 아주 낮은 큐에 들어 있는 프로세스들에 starvation이 발생할 수도 있는데 이를 해결하기 위해 우선순위가 낮은 큐에서도 waiting time이 길면 우선순위가 높은 큐로 승격시키는 aging 기법을 도입하기도 합니다.
• 또는 I/O를 계속하면 우선순위가 유지되지만 그러다가 CPU를 오래 사용하게 되면 우선순위가 낮아지기 때문에 구조적으로 우선순위가 다시 높아질 수 없는 문제가 있어 I/O를 많이 하고 오면 우선순위가 높은 큐로 가게 하거나 우선순위가 낮은 큐에 있는 프로세스일수록 CPU 사용량이 길다는 것을 의미하기 때문에 이에 대해 time quamtum 자체를 늘려주기도 하는 변형이 있기도 합니다. 
• MFQ 구현을 위해 결정해야 할 조건 사항
  1. 큐의 개수
  2. 각 큐에 적용할 스케줄링 기법
  3. 프로세스를 우선순위가 높은 큐로 승격시킬 시기 결정 방법
  4. 프로세스를 우선순위가 낮은 큐로 격하시킬 시기 결정 방법
  5. 프로세스가 진입할 때 어떤 큐로 진입할지 결정하는 방법 

---

 

이번 글에서는 스케줄링 기법에 대해 알아보았습니다.

분량을 보시면 눈치채셨겠지만 MFQ가 가장 많이 사용되고, 구현이 복잡한 스케줄링 기법입니다. 

추후에 기회가 된다면 실제로 구현해봐도 좋을 것 같네요 ㅎㅎ

감사합니다 :)

---

References

• 성균관대학교 소프트웨어대학 엄영익 교수님 <운영체제> 수업