CPU 스케줄링 알고리즘(FCFS, SJF, Priority Queue, Round Robin, SRTF, MLQ, MLFQ), 4BSD,nice

CPU 스케줄링 알고리즘

CPU 스케줄러는 CPU 스케줄링 알고리즘에 따라 프로세스에서 해야하는 일을 스레드 단위로 CPU에 할당한다.

프로그램이 실행될 때는 CPU 스케줄링 알고리즘이 어떤 프로그램에 CPU 소유권을 줄 것인지를 결정한다.

즉,  CPU 스케줄링은 언제 어떤 프로세스에 CPU를 할당할지 결정하는 작업 을 한다.

 

CPU 이용률은 높게, 주어진 시간에 많은 일을 하게, 준비 큐(ready queue)에 있는 프로세스는 적게, 응답시간을 짧게 설정하는 것을 목표로 한다.

 

1) 비선점형 방식(non-preemptive)

프로세스가 스스로 CPU 소유권을 포기하는 방식(어떤 프로세스가 CPU를 점유하고 있다면 이를 뺏을 수 없는 방식)

강제로 프로세스를 중지하지 않는다.

-> 문맥교환(Context Switching)으로 인한 부하가 상대적으로 적지만 프로세스의 배치에 따라 효율성 차이가 많이 나게 된다.

 

👉 문맥교환(Context Switching)

- 여러 개의 프로세스가 실행되고 있을 때 기존에 실행되던 프로세스를 중단하고 다른 프로세스 실행

 

비선점형 방식 종류

FCFS(First Come, First Served)

https://blog.naver.com/ehdrjsdlzzz/220969631489

 

• 가장 먼저 온 것을 가장 먼저 처리한다.(선착순)
• 길게 수행되는 프로세스 때문에 ' 준비 큐에서 오래 기다리는 현상(convoy effect , 호위 효과)' 가 발생하는 단점이 있다.

 

SJF(Shortest Job First)

https://blog.naver.com/ehdrjsdlzzz/220969631489

 

• 실행시간이 가장 짧은 프로세스를 가장 먼저 실행한다.
• 긴 시간을 가진 프로세스가 우선순위에 계속 밀려 실행되지 않고 무기한으로 대기하게 되는 현상(starvation, 기아) 발생한다.
• 평균 대기 시간이 가장 짧다. 하지만 실제로는 실행 시간을 알 수 없어서, 과거의 실행했던 시간을 토대로 추측해야한다.

 

Priority(우선순위)

https://blog.naver.com/ehdrjsdlzzz/220969631489

 

• 각각의 프로세스에 우선순위가 있는 알고리즘으로 우선순위가 높은 순 먼저 실행한다.
• 기존 SJF 스케줄링의 경우 긴 시간을 가진 프로세스는 실행되지 않는 기아 문제가 발생할 수 있는데, 이를 해결하기 위해 오래된 작업일수록 우선순위를 높이는 노화(aging) 방법을 통해 단점을 보완한다.

 

2) 선점형 방식(preemptive)

현대 운영체제가 쓰는 방식으로,  지금 사용하고 있는 프로세스를 알고리즘에 의해 중단시키고 강제로 다른 프로세스에 CPU 소유권을 할당하는 방식 이다.

처리 시간이 매우 긴 프로세스의 CPU 사용 독점을 막을 수 있어 효율적인 운영이 가능하지만 잦은 컨텍스트 스위칭으로 인해 오버헤드가 커질 수 있다.

 

🤔오버헤드 - 어떤 처리를 하기 위해 들어가는 간접적인 처리 시간 · 메모리 등

 

선점형 방식 종류

라운드로빈(RR, Round Robin)

https://blog.naver.com/ehdrjsdlzzz/220969631489

 

• 현대 컴퓨터가 쓰는 스케줄링인 우선순위 스케줄링의 일종으로, 각각의 프로세스에  동일한 할당 시간을 부여해서 해당 시간 동안만 CPU를 이용 하게 된다.
• 할당 시간 내에 처리를 완료하지 못하면 강제 중단 후 다음 작업으로 넘어간다.
• 할당 시간이 너무 크면 FCFS가 되고 짧으면 컨텍스트 스위칭이 잦아져서 오버헤드가 발생한다.
• CPU 사용시간이 랜덤한 프로세스들이 섞여 있을 때 효율적인 기법이다.

 

SRTF (Shortest Remaining Time First)

• 실행되고 있는 프로세스는 중단없이 끝까지 실행되는 비선점형 SJF와 다르게, SRTF는  중간에 더 짧은 작업의 프로세스가 들어오면 현재 실행되는 프로세스를 중단하고 해당 프로세스를 실행 하도록 바꾼다.

                                                                                    

다단계 큐(Multilevel Queue)

 

https://blog.naver.com/ehdrjsdlzzz/220969631489

 

• 우선순위에 따른 준비 큐가 여러 개의 큐들로 나뉘고 각각의 큐마다 각자의 스케줄링 알고리즘 을 적용한 것이다.
• 우선순위가 높은 큐부터 처리되기 때문에 낮은 큐의 프로세스 처리가 안되는 기아 현상이 나타날 수 있다.
• 큐 간의 프로세스 이동이 안되므로 스케줄링 부담이 적지만 유연성이 떨어지는 특징이 있다.         

여러 단계로 분할할 수가 있지만, 크게 본다면 사용자와 상호작용하는 전면작업(Foreground Task)과 그렇지 않은 후면작업(Background Task)으로 분리할 수 있다. (프로세스의 특성 및 종류에 따라 나뉨)

 

전면 작업 - 사용자의 입력 -> 문서 편집, 웹 브라우징 등

후면 작업 - 시스템 유지 보수, 데이터 처리 , 갱신 등 담당 -> 백업, 바이러스 스캔, 업데이트 등

 

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

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

후면 작업 Queue에 들어있는 프로세스들은 FCFS 기법 진행한다.

 

 

MLFQ(Multilevel Feedback Queue)

 

https://blog.naver.com/ehdrjsdlzzz/220969631489

 

• 특정 그룹의 Queue에 들어간 프로세스가 다른 Queue로 이동하거나 변경이 불가능한 MLQ 기법을, 서로 다른 Queue로도 이동할 수 있도록 개선한 기법이다.
• 다양한 우선순위를 가진 여러 개의 큐를 사용하여 프로세스를 관리하는 기법이다.
• 이 방식의 핵심은 프로세스의 행동에 따라 그 프로세스가 속한 큐(즉, 그 프로세스의 우선순위)를 동적으로 변경한다는 것이다.
• 예를 들어 CPU를 많이 사용하는 프로세스는 우선순위를 낮추어 다른 프로세스에게도 CPU를 공평하게 할당하도록 할 수 있다.
• 이런 방식으로, MLFQ는 CPU 사용을 공평하게 분배하면서도, 중요한 작업에는 더 많은 CPU 시간을 할당하는 것을 가능하게 한다. 이는 공유 시스템에서 특히 중요한데, 사용자 프로세스와 시스템 프로세스 간에 적절한 균형을 맞추어야 하기 때문이다.

 

4BSD , nice     

                          

4BSD는 유닉스 운영체제의 한 형태로, 그 중에서도 스케줄러는 MLFQ 방식을 기반으로 하고 있다.

4BSD 스케줄러는 프로세스의 nice 값(우선순위를 결정하는 값)과 최근 CPU 사용량을 고려하여 프로세스의 우선순위를 동적으로 조정한다.         

                                                                                                                                                                                                                     

nice 명령어는 특정 프로세스가 실행될 때 우선순위를 지정할 수 있는 것으로 실행속도를 높일 수 있도록 한다.

이미 실행중인 프로세스에 대한 우선순위를 재설정할 수 있는 것은 renice 명령어

 

우선순위 값은 0(가장 높은 우선순위, 가장 빠르게 실행됨)부터 39(가장 낮은 우선순위, 가장 느리게 실행됨)까지 가능하며 NICE값은 -20부터 19까지 가능

 

결론적으로 우리는 NICE값을 -20부터 19까지 조절하면서 각각의 프로세스의 우선순위 값을 0부터 39까지 조절할 수 있다.

 

 

 

---

참조

CPU 스케줄링 알고리즘 요약정리