스케줄링(Scheduling)

Goal

• 스케줄링 시 어떤 것들을 고려해야 하는지 이해
• 스케줄링 알고리즘 평가 기준에 대한 이해
• 여러가지 스케줄링 기법과 그 특징에 대한 이해

---

스케줄링(Scheduling)이란?

컴퓨터 분야에서 스케줄링이란 컴퓨터 시스템 자원(CPU등)을 어떤 작업(task)에 할당할지 결정하는 것을 의미한다.

ex) network scheduling, I/O scheduling, Job scheduling etc

 

• CPU 스케줄링 : CPU를 어떤 작업(프로세스 또는 스레드 등)에 할당할지 결정
• 스케줄링은 작업 단위나 관리 범위 등에 따라 구분할 수 있다.
  • ex) 고수준 스케줄링, 중간 수준 스케줄링, 저수준 스케줄링

 

선점형 스케줄링과 비선점형 스케줄링

CPU를 강제로 빼앗을 수 있는지에 따라 선점(preemptive)형, 비선점(non-preemptive)형 스케줄링으로 나눌 수 있다.

 

• 선점형 스케줄링 : 어떤 프로세스가 CPU를 할당받아 실행 중에 있어도 다른 프로세스가 실행 중인 프로세스를 중지하고 CPU를 강제로 점유할 수 있다. 
• 비선점형 스케줄링 : 어떤 프로세스가 CPU를 할당 받으면 그 프로세스가 종료되거나 입출력 요구가 발생하여 자발적으로 중지될 때까지 계속 실행되도록 보장한다.

선점형 vs 비선점형

선점형 스케줄링(Preemptive Scheduling)

• 작업 방식 : CPU를 강제로 점유할 수 있다.
• 사용 용도 : 빠른 응답을 요구하는 대화식 시분할 시스템에 적합
• 특징
  • context switching에 의한 overhead가 많다.
  • 응답이 빠르므로 실시간 응답을 요구하는 시스템에 적합

 

비선점형 스케줄링(Non-preemptive Scheduling)

• 작업 방식 : 작업이 완료될 때까지 다른 task가 CPU를 점유할 수 없다. (독점)
• 사용 용도 : 일괄 처리 시스템에 적합
• 특징
  • 순서대로 처리 보장
  • 응답 시간 예측이 가능
  • 선점형 방식에 비해 context switching으로 인한 overhead가 적다.
  • 작업이 끝날 때 까지 다른 프로세스(or 스레드)들은 대기해야 하므로 처리율이 떨어질 수 있다.

---

스케줄링 알고리즘

스케줄링 평가 기준

스케줄링 알고리즘은 다음과 같은 기준을 통해 평가할 수 있다.

• CPU 사용률(CPU Utilization) : 전체 시스템 시간 중 CPU가 작업을 처리하는 시간의 비율
• 처리량(Throughput) : CPU가 단위 시간당 처리하는 프로세스의 개수
• 응답 시간(Response Time) : 대화식 시스템에서 요청 후 응답이 오기 시작할 때까지의 시간
• 대기 시간(Waiting Time) : 프로세스가 준비 큐 내에서 대기하는 시간의 총합
• 반환 시간(Turnaround Time) : 프로세스가 시작해서 끝날 때까지 걸리는 시간 (대기 + 실행 시간)

CPU 사용률은 클수록 좋다. 이상적인 수치는 100%이지만 여러가지 이유로 90%에도 못 미친다.

처리량은 클수록, 응답 시간, 대기 시간, 반환 시간은 짧을수록 좋다.

 

스케줄링 알고리즘 종류

• FCFS 스케줄링(First Come First Served Scheduling)
• SJF 스케줄링(Shortest Job First Scheduling)
• HRRN 스케줄링(Highest Response Ratio Next Scheduling)
• 라운드 로빈 스케줄링(Round Robin Scheduling)
• 다단계 큐 스케줄링(Multilevel Queue Scheduling)
• 다단계 피드백 큐 스케줄링(Multilevel Feedback Queue Scheduling)

FCFS를 제외하고 나머지 스케줄링은 선점형 스케줄링이 가능하거나 선점형 스케줄링이다.

 

FCFS(First Come Fisrt Served)

먼저 들어온 작업을 먼저 처리하는 방식

 

비선점형 방식으로 선입 선출(FIFO, First In First Out)이라고도 한다.

 

평가

• 알고리즘이 단순하고 구현이 간단 (큐로 구현 가능)
• CPU를 점유할 때까지 다른 프로세스들은 대기 해야 한다.
  •  이로인해 convoy effect가 발생할 수 있다. 

*convoy effect란?

처리 시간이 긴 프로세스가 CPU를 점유하여 다른 프로세스들의 대기 시간이 길어져 시스템 효율이 떨어지는 것을 말한다.

 

SJF(Shortest Job First)

실행 시간이 짧은 작업부터 먼저 처리 하는 방식 (실행 시간이 스케줄링 판단 기준)

 

최단 작업 우선 스케줄링이라고도 한다.

선점형, 비선점형 모두에 적용될 수 있는데, 선점형에 적용되는 SJF 스케줄링을 특별히 SRTF 스케줄링이라 한다.

 

평가

• 평균 대기 시간을 최소화 할 수 있다. (평균 시간을 최적으로 두고 있는 알고리즘이다)
• 하지만 현실적으로 다음과 같은 이유로 사용되기 어렵다.
  • 프로세스 작업 길이를 추정하는 것이 힘들다.
  • 특정 프로세스가 기아(starvation) 상태에 빠질 수 있다.

*기아(starvation) : 요구 시간이 긴 프로세스가 요구 시간이 짧은 프로세스에게 항상 양보되어 계속 연기되는 현상

 

SJF는 작업 시간이 긴 프로세스가 계속 양보되기 때문에 공평성이 떨어지고 기아 현상이 발생할 수 있다.

 

 

HRRN(Highest Response Ratio Next)

준비 큐에 있는 프로세스들 중에서 응답률이 가장 높은 프로세스에게 높은 우선순위를 주는 방식

*응답률(우선순위) = (대기 시간 + CPU 사용 시간) / CPU 사용 시간

 

CPU 사용 시간과, 대기 시간을 고려하여 우선순위를 정하는 스케줄링 알고리즘으로, SJF문제점(기아 현상)을 보완하기 위해 개발 되었다. 

HRRN은 에이징(aging)을 통해 기아 현상을 해결한다.

 

*aging : 대기 시간에 따라 우선순위를 증가시켜주는 방법이다. 오래 기다린만큼 우선순위를 높여주어 결국에는 실행될 수 있도록 하는 것이다.

 

평가

• 실행 시간이 높은 짧은 프로세스를 우선순위를 높게 설정하면서도 대기 시간을 고려하여 기아(starvation)현상을 완화 시킨다.
• 그러나 여전히 공평성은 떨어진다. (처리 시간이 긴 프로세스의 경우 대기 시간이 길어지기 전까지는 CPU를 점유할 수 없음)

 

Round Robin(RR)

프로세스들 사이에 우선순위를 두지 않고, 순서대로 시간 단위(time slice/quantum)로 CPU를 할당하는 방식

대표적인 선점형 방식이다.

 

*time slice : 선점형 스케줄링에서 cpu를 점유하도록 허용된 시간

 

<참고> Round-Robin 유래

Round : 1라운으 2라운드와 같이 한번 도는 것을 의미

Robin : 'robin'이라는 새 이름에서 유래

 

robin이라는 새는 새끼한테 모이를 줄 때, 10마리가 있으면 조금씩 조금씩 나누어서 분배해주고 다시 한 바퀴(round) 돌면서 나누어 주는 것을 반복한다고 한다. 그래서 스케줄링 방식이 이와 유사하여 round-robin이라 부른다.

 

또한, round-robin은 '리그전', '여러 사람이 돌려 가며 만들거나 쓴 것'의 의미를 가지고 있다.

 

라운드 로빈 방식은 타임 슬라이스를 적당한 크기로 설정하는 것이 중요하다.

타임 슬라이스가 너무 클 경우 : 응답 시간이 느려진다.

타임 슬라이스가 너무 작을 경우 : context swiching으로 인한 overhead가 커진다.

 

평가

• 대표적인 선점형 스케줄링으로, 순차적으로 time slice 만큼 CPU를 할당하기 때문에 기아(starvation)현상이 발생하지 않는다. 대신 context switching으로 인한 overhead가 발생한다.
• 우선순위가 따로 없기 때문에 중요도에 따라 우선순위를 다르게 두고 CPU를 할당하고 싶을 경우 우선순위 스케줄링 방식과 함께 사용해야한다.
  • ex) 사용자 스레드보다 커널 스레드의 우선순위를 더 높게 둔다.
  • ex) 백그라운드 프로세스보다 포그라운드 프로세스의 우선순위를 더 높게 둔다.

 

Multilevel Queue(MQ, MLQ)

우선순위에 따라 준비 큐를 여러 개 사용하는 방식

(단순히 큐를 여러개 사용하는 멀티 큐가 아니라 큐에 우선순위가 부여된 멀티 레벨 큐이다)

 

각각의 큐에 서로 다른 방식의 스케줄링 알고리즘이 적용시킬 수 있다.

 

 

 

평가

• 우선순위가 높은 프로세스가 낮은 프로세스보다 먼저 동작하게 할 수 있다. (우선 순위에 따라 순서 제어 가능)
• 우선순위에 따라 타임 슬라이스를 조절하여 작업 효율을 높일 수 있다. (작업 형태를 고려하여 우선순위 부여)
  
  • ex) 백그라운드 프로세스보다 포그라운드 프로세스가 더 많은 타임 슬라이스를 부여받는다.
• 우선 순위가 높은 프로세스에 의해 우선순위가 낮은 프로세스의 작업이 연기될 수 있다.
• 프로세스가 하나의 큐에 영구적으로 할당되는 방식이기 때문에 상황에 맞게 큐를 갈아탈 수 없다.

 

Multilevel Feedback Queue(MFQ, MLFQ)

우선순위를 변경할 수 없는 Multilevel Queue에서 한단계 발전한 알고리즘으로, 프로세스의 우선순위의 변경이 가능한 방식이다.

 

• CPU를 사용하고 난 프로세스는 한단계 낮은 큐로 다시 삽입된다.
  • 물론 우선순위가 낮아진다고 해도 커널 프로세스가 일반 프로세스 큐에 삽입되지는 않는다.
• MLFQ는 우선순위에 따라 타입 타임 슬라이스 크기가 다르다. (우선순위가 낮을수록 타임 슬라이스 크기가 증가)
• 우선순위가 낮은 프로세스는 우선순위가 높은 프로세스보다 CPU를 얻을 기회가 더 적기 때문에 타임 슬라이스를 크게 설정하여 더 오랫동안 CPU를 점유할 수 있도록 한다. (마지막 큐는 time slice가 크기 때문에 FCFS처럼 동작)

 

<참고> 개인적인 생각

위 내용을 보고 처음 의아한 점이 있었다. 우선순위는 왜 낮아지기만 하는가? 언제 끝날지 모르는 프로세스가 FCFS 큐에 들어가면 어떻게 되는가?에 대한 의문이었다.

깃헙 C++ 코드와 유튜브 영상을 보고 이 의문점을 해결하였다.

 

CPU burst time, time slice에 대한 구분이 안되서 헷갈린 문제였다.

예를 들어 A프로세스의 CPU Burst Time이 20초라고 한다면, A 프로세스는 위 그림에서 1번 째 큐에서 8초만큼의 작업을 하고 두번 째 큐에 들어가서 나머지 12초 만큼의 CPU를 점유하고 작업이 끝난다. 그리고 다시 cpu burst time 만큼 큐에 삽입되어 cpu를 점유하는 방식이다.

 

또한, CPU burst time 만큼의 작업을 마친 프로세스들은 어떻게 처리하는지 그 부분이 없어서 헷갈렸다. MLFQ 스케줄링을 한다면, 이부분에 대한 처리도 해야 하지 않나 싶다.

 

또한, 작업 유형에 따라 우선 순위의 상한과 하한을 지정할 수 있도록 해야 할 것 같다.

시작 큐 위치와 CPU burst time을 적절히 선택하면 우선순위의 상한과 하한을 제어할 수 있을 듯 하다.

 

설계 방침

• 짧은 작업에 우선권을 준다.
• 입출력 관련 프로세스에 우선권을 준다.
• 프로세서 사용량에 따라 프로세스를 분류한다.

 

평가

• 오늘날의 운영체제가 CPU 스케줄링을 위해 일반적으로 사용하는 방식이다. (변동 우선순위 알고리즘)
• 구현이 어렵다.
• 우선순위가 변동되기 때문에 기아(stavation)현상으로 인한 문제를 해소할 수 있다.

 

References

jhnyang.tistory.com/158