[운영체제 OS] CPU 스케쥴링 주요 알고리즘 익히기(FCFS, SJF, Priority, RR)

포스팅을 읽기 전 CPU 스케쥴링에 대한 기본 개념을 정리한 이전 포스팅이 있다.

미리 참고하고 보면 좋을 듯하다.

 

[운영체제 OS] CPU 스케쥴링 기본 및 선점형 비선점형 알고 가기

 

선입 선처리 스케쥴링(FCFS, First-come First-served)

방식은 단순하다. CPU를 먼저 요청한 프로세스가 먼저 할당받는 선착순 방식이다.

한 마디로 FIFO 큐 방식인 것이다.

간단하며, 쉽게 이해할 수 있다는 장점이 있지만, 순서에 따라서 대기 시간의 갭 차이가 크며, 하나의 긴 프로세스 때문에 다른 프로세스들의 처리가 미뤄지는 비효율성이 발생할 수 있다.

 

아래 내용을 이해하기 위해 반드시 알고 있어야 할 평균 대기시간을 알아보자.  

 

평균 대기 시간은 프로세스들의 각 대기 시간을 평균치로 매긴 것으로 아래 그림을 예시로 들자면

 

프로세스 1은 바로 CPU로 이동하므로 대기 시간이 없어서 0이다.

프로세스 2는 프로세스 1이 끝난 뒤이므로 1의 소요시간인 20만큼의 대기 시간이 필요하다.

프로세스 3은 프로세스 1과 2가 끝난 뒤에야 CPU로 이동할 수 있는데,

프로세스 1의 소요 시간 20과 프로세스 2의 소요 시간 5를 합쳐 총 25의 대기 시간이 필요하다.

이제 구해진 프로세스 1,2,3의 대기 시간을 평균치로 합산하면 15가 나오게 된다.

 

프로세스 별 소요시간을 살짝 바꿔보자.

프로세스 1이 20 → 5가 되고, 프로세스 3이 5 → 20이 되었다.

평균 대기시간이 이번엔 5가 나왔다. 이를 통해 배치에 따라 평균대기시간의 차이가 크다는 것이 특징이자 선입 선처리 스케쥴링의 단점이라고 할 수 있다.

 

최단작업 우선 스케쥴링(SJF, Shortest-Job-First, SJF)

처리해야 할 작업량이 가장 적은 순으로 CPU를 할당하는 방법이다.

짧은 작업일수록 더 좋은 서비스를 받도록 하고 있기 때문에 오버헤드 측면에서 볼 때 SJF는 긴 작업보다 짧은 작업 프로세스에 더 유리하다고 할 수 있다.

대기하고 있는 작업들의 수를 줄이고, 특히 큰 작업 뒤에서 기다리게 될 작업의 수를 줄이기 때문에 평균 대기시간을 최소화할 수 있다.

 

소요시간은 작은 순으로 차례대로 진행되었다.

우선순위 스케쥴링(Priority)

각 프로세스마다 우선순위가 부여되며, 그중 가장 먼저인 1순위부터 차례대로 중앙처리장치에 할당하는 방법이다.

우선순위가 같은 경우가 간혹 생길 수 있는데, 이럴 때에는 FCFS 방법을 통해 순위를 가른다.

우선순위는 크게 내부적 요인과 외부적 요인 2가지로 매겨진다.

 

내부적 요인

제한 시간, 메모리 공간 요구량, 사용되는 파일 수, 평균적인 CPU활용량에 대한 평균 입출력(I/O) 부하의 비율

 

외부적 요인

컴퓨터 사용을 위해 필요한 물질적 비용의 양 혹은 타입, 정책적인 변수, 운영체제의 외적 요소

 

위와 같이 여러 합당한 요인을 통해 정해진 우선순위는 대개 신뢰할 수 있으며, 합리적인 작업 진행을 할 수 있다는 장점이 있다. 하지만 여기서 변수가 있다. 바로 새로운 프로세스가 추가되었을 때의 문제이다.

이 새로운 프로세스가 우선순위가 높게 정해지면서 기존 프로세스가 밀려날 것이며, 이렇게 점차적으로 우선순위가 낮게 되는 기아 상태에 빠질 수도 있다는 단점이 있다. 이때에는 에이징(Aging) 기법을 통해 기아상태를 방지할 수 있다.

 

기아 상태

우선순위가 높은 프로세스가 지속적으로 들어오는 바람에 끊임없이 순위가 뒤로 밀리는 현상

 

에이징 기법

기아상태에 봉착한 프로세스를 구할 수 있는 방법으로 지속적으로 순위가 밀리는 프로세스를 구별하여 이를 우선순위 앞으로 변경시키는 방법

 

우선순위에 따라서 진행되었다.

 

라운드 로빈 스케쥴링( Round - Robin Scheduling)

한 프로세스가 종료될 때까지 한 중앙처리장치를 차지하는 비선점 방식과는 달리 선정 스케쥴링에는 시간 할당량이 주어진다. 이 시간 할당량동안 작업을 완료하지 못한 프로세스는 준비 상태로 밀려나고, 바로 뒤에 준비 상태인 다른 프로세스가 중앙처리장치를 차지한다. FIFO스케쥴링 방법을 선점형 기법을 적용하여 구현한 스케쥴링 기법을 라운드 로빈 스케쥴링이라고 하며, 주어진 시간 할당량 내로 작업을 마치는 것이 좋으며, 시간 내 미완료된 프로세스는 다시 대기 중인 프로세스 중 제일 뒷 순서로 돌아가는 데 이를 대화식 시분할 시스템에 적합하도고 할 수 있다.

 

아래 그림 예시를 보자. 시간 할당량(Time Quantum)은 4를 주었다.

즉, 소요시간 4 이내로 프로세스가 완료되지 않으면 무조건 다음 프로세스에 CPU 자리를 양보해주어야 한다.

물론 프로세스 2를 자세히 보면 알겠지만 4 이내 조기에 완료되면 바로 다음 프로세스로 넘어가는 걸 확인할 수 있다.

 

프로세스 2,3이 종료되고 프로세스 1만 진행되는 뒷구간의 경우는 시간 할당량에 따라 쪼개어는 지지만

대기 구간이라고 할 수 없으므로 평균대기시간 계산에 세 제외된다.

 

따라서 각 다른 프로세스들 간의 맞물리는 구간 내에서의 대기 시간을 통해 평균대기시간을 계산하면 된다.

 

여기까지만 읽고 감이 온다면, 시간 할당향을 어떻게 조절할 것인지가 정말 중요하다는 것을 알 수 있을 것이다.

시간 할당량이 너무 클 경우 CPU 내 프로세스는 작업을 끝낼 수 있는 충분한 시간을 가지게 되므로 FIFO방법과 동일하게 되어버려 선점형 방식의 장점이 사라져 버린다고 해도 과언이 아니다.

 

시간 할당량이 매우 크면 비선점형 방식과 같아진다.

 

반대로 할당량이 너무 작을 경우 프로세스 교체로 인한 과도한 문맥 교환(Context Switching)의 영향으로 오버헤드가 매우 커지게 되어 이로 인해 프로세스의 처리 속도는 상대적으로 매우 낮아질 것이다.

 

시간 할당량이 매우 작으면 과도한 프로세스 교체로 인한 문제가 발생할 수 있다.