[CS]스케줄링의 종류-1

이정우·2024년 1월 7일

CS MLFQ priority scheduling 프로세스스케줄링

CS지식

목록 보기

4/5

오늘은 지난시간에 이어서 스케줄링의 종류에 대해서 알아보겠습니다.

이번에 알아볼 스케줄링은 바로 Priority스케줄링 입니다.

1. Priority Scheduling

Priority scheduling은 특정 기준으로 프로세스에게 우선순위를 부여해 우선순위가 제일 높은 프로세스에게 CPU를 할당하는 방식을 의미하고 있습니다.

이 Priority scheduling은 batch system에서 가장 흔한 알고리즘 중 하나입니다.

각각의 process들이 우선순위에 따라 나열되어있고 높은 우선순위를 가지고 있는 프로세스가 우선적으로 실행이 됩니다.

만약 같은 우선순위를 가지고있는 경우에는 FCFS scheduling과 같이 우선적으로 예약된 프로세스가 실행이 되게 됩니다.

프로세스에게 우선순위를 부여하는 기준은
메모리 요청량, 시간 요청량 또는 다른 어떤 자원요청량에 따라 우선순위를 부여하는 기준을 나눌수도 있습니다.
심지어 이 scheduling은 평균 I/O시간 이나 평균 CPU burst Time에 따라 기준을 세울수도 있습니다.

이렇게 우선순위 스케줄링이 어떤거인지 또한 어떻게 실행되는지 알아보았는데 이번에는
장점과 단점에 대해서 알아보겠습니다

1-1. 장점

Priority scheduling의 장점은

Priority 기반 스케줄링은 높은 우선순위의 프로세스가 우선적으로 실행되는것을 보장합니다.
이를 통해서 중요한 task를 빠르게 완료할 수 있습니다.
Priority 스케줄링은 프로세스가 strict timing 제약조건을 충족해야하는 실시간 시스템에서도 유용합니다.
실시간 시스템에서는 작업들이 정해진 시간내에 완료되어야합니다. 그렇기에 높은 우선순위를 가진 작업들은 낮은 우선순위를 가진 작업들보다 우선적으로 수행되므로, timing constraint를 만족시키기에 유용합니다.
Priority 스케줄링은 많은 양의 CPU time이 필요한 프로세스들의 평균 수행시간을 줄여줄 수 있습니다.
Priority가 높은 프로세스는 빠르게 CPU를 할당받아 수행됨으로 응답시간이 감소하게 됩니다. 특히, 많은 양의 CPU time이 필요한 프로세스의 경우, 빠른 응답이 해당 작업을 더 효율적으로 수행할 수 있도록 만들어 줍니다.

특정 기준으로 우선순위를 설정하여 프로세스들을 관리 할 수 있습니다.
하지만 이러한 스케쥴링에도 단점이 존재할 수 밖에 없습니다.

1-2. 단점

우선순위 역전
우선순위 스케줄링을 사용할 때에는 우선순위 역전이 일어날 수 있습니다.
낮은 우선순위의 프로세스가 높은 우선순위를 가지고 있는 프로세스가 필요로 하는 자원을 가지고 있을때 발생합니다.
이러한 우선순위 역전은 높은 우선순위를 가지고 있는 프로세스의 실행을 늦출 수 있습니다.
Starvation
Starvation은 시스템에 우선순위가 높은 프로세스가 과도하게 로드될때 발생 할 수 있습니다.
우선순위가 높은 프로세스가 과도하게 로드되면, 우선순위가 낮은 프로세스가 실행되지못하고 지속적으로 뒤로 밀리게 되어 메모리를 할당받지 못할 수 있습니다.

우선순위 역전 방지를 위한 기술들
(ex. 우선순위 상속, 우선순위 상한 프로토콜)
이 시스템에 추가적인 복잡성을 가져올 수 있습니다.
우선순위를 설정하는것이 어려운 작업이 될 때도 있습니다. 특히 우선순위가 서로다른 프로세스가 많을때 더욱 그렇습니다.

이러한 단점들을 해결하기 위해서는 다양한 방법들이 존재합니다.
가장 대표적으로 starvation을 해결하기 위해서 사용되는 방법인 aging기법이 존재합니다.

aging기법은 시간이 지날수록 오래 대기한 프로세스의 우선순위를 높이는 방식입니다.

우선순위 스케줄링은 다른 스케줄링 알고리즘과 결합해서 사용할 수 있어 선점, 비선점방식 모두 사용가능 합니다.

2. MLFQ(Multi Level Feedback Queue)

MLFQ는 프로세스 실행을 관리하기 위해 우선순위가 다양한 여러 큐를 사용하는 CPU scheduling 알고리즘 입니다.
MLFQ의 동작원리로는 프로세스의 동작에따라서 우선순위를 동적으로 조정하여 큐 사이의 프로세스를 승격하거나 강등합니다.

MLFQ는 작업을 효율적으로 관리하여, 반응성과 리소스 활용도의 우선순위를 지정하고 이를 통해 starvation을 줄이는데 도움을 줍니다.
이러한 동적관리를 함으로 다양한 프로세스들을 관리하는데 적합하고 전반적인 스케줄링의 성능과 유저 경험(UX)을 향상시킵니다.

그럼 MLFQ의 특징은 어떤것이 있을까요??

2-1.MLFQ의 특징

MLFQ는 일반적으로 계층적으로 배열된 서로 다른 우선순위를 가진 여러 대기열을 사용합니다.
이를 통해 우선 순위가 낮은 프로세스가 여전히 CPU 시간을 공정하게 분배받도록 하면서 시간이 중요한 작업을 보다 유리하게 처리할 수 있습니다

다중 큐
MLFQ는 다중 큐를 사용하며 각각의 큐가 다른 스케줄링을 사용하여 우선순위를 각각 다르게 적용 시킬 수 있습니다.
피드백 메커니즘
MLFQ에서의 피드백 매커니즘은 프로세스의 우선순위를 각각의 프로세스의 과거 동작을 기반으로 조정할 수 있습니다. 프로세스가 우선순위가 낮은 대기열에서 해당 time slice를 소진하면 더 많은 CPU시간을 받기 위해서 우선순위가 높은 대기열로 승격될 수 있습니다.

time slicing
각각의 프로세스는 현재 큐에서 실행할 특정시간 할당량이 할당됩니다.
동적 우선순위 조정
피드백 메커니즘은 프로세스의 우선순위를 시간경과에 따른 동작을 기반으로 조정 할 수 있습니다.
선점형 스케줄링
우선순위가 높은 프로세스가 필요한 CPU시간을 확보할 수 있도록 우선순위가 낮은 프로세스를 중단하고 우선순위를 갖도록 합니다 .

그럼 이번에는 MLFQ스케줄링의 기능에 대해서 알아보겠습니다

2-2.MLFQ의 기능

MLFQ스케줄링은 큐의 숫자, 시간의 양, 그리고 우선순위 조정등의 파라미터에 대한 이해를 필요로 합니다.
왜 그럴까요?

이러한 파라미터들은 효율적인 자원의 사용과 공평한 프로세스 실행을 보장될수 있게 해줍니다.

MLFQ가 프로세스를 어떻게 처리하는지 한번 보겠습니다

업로드중..

위 다이어그램은 MLFQ의 구조를 보여주고 있습니다.
실행과정은
새로운 프로세스가 1번큐에 들어오게 되고 프로세스가 실행기간동안 작업을 끝내지 못하면은 2번 큐로 이동이되게 됩니다. 즉 일단 프로세스가 실행기간을 마치게 되면 큐에서 제거된다는 의미입니다.
게다가 MLFQ스케줄링은 부스팅을 활용하여 낮은 단계에 있는 프로세스를 더 높은단계에 있는 큐로 올려서 실행시킬수있습니다.

실행과정을 step별로 분류해 보겠습니다.

프로세스가 시스템에 입력되면, 가장높은 우선순위를 가진 큐에 할당되게 됩니다.
프로세스는 특정할당된 시간동안 현재 있는 큐에서 자원을 할당받아 실행됩니다.
만약 프로세스가 특정할당된 시간에 작업을 끝내게 되면 프로세스는 시스템에서 제거 됩니다.
만약 프로세스가 특정할당된 시간안에 작업을 끝내지 못하게되면, 해당 프로세스는 낮은 우선순위를 가지고 있는 큐로 내려가게되고 기존에 할당된 시간보다 더 적은시간을 할당받고 실행되게 됩니다.
이러한 승급과 강등과정은 프로세스의 행동에 기반하여 실행되게 됩니다.
우선순위가 높은 큐는 우선순위가 낮은 큐보다 우선순위가 높으므로, 우선순위가 높은 큐가 비어있는 경우에만 후자의 프로세스가 실행될 수 있습니다.
feedback매커니즘은 각각의 프로세스가 실행된 것을 기반으로 큐사이에 프로세스를 옮기게 됩니다.
이러한 과정들의 반복은 모든 큐에 있는 모든프로세스가 실행되고 제거될때까지 실행됩니다.

또한 MLFQ 스케줄링은 다른 큐에 각각 다른 스케쥴링 알고리즘을 적용시킬수 있기때문에 각각의 큐에 담긴프로세스들이 각각의 다른 스케줄링에 의해 관리됩니다.

마지막으로 MLFQ를 도입했을때의 장단점에 설명을 드리고 마무리 하겠습니다.