[운영체제] 스케줄링 종류와 기아상태

 

 

CPU 스케줄링(CPU Scheduling)

다중 프로그래밍의 목적은 CPU 이용률을 최대화하는 것입니다. 이를 위해 프로세스가 작업이 끝나거나 대기 상태로 전환되어 CPU가 유휴 상태가 될 때마다, 운영체제는 스케줄링 기법에 따라 CPU를 회수하여 대기 큐에 있는 다른(우선순위가 높은) 프로세스에 할당합니다.

 

 

 

선점 스케줄링 vs 비선점 스케줄링

스케줄링 기법은 실행중인 작업의 자원을 선점할 수 있는가 여부에 따라 크게 두가지로 나눌 수 있습니다. 

 

선점 스케줄링(Preemptive Scheduling)

현재 실행 중인 작업보다 우선순위가 더 높은 작업이 대기큐에 들어왔을 때 강제로 CPU를 회수하여 높은 우선 순위의 작업을 먼저 실행하도록 하는 방법입니다. 

 

비선점 스케줄링(Nonpreemptive Scheduling)

현재 실행 중인 작업보다 우선 순위가 더 높은 작업이 대기큐에 들어오더라도 실행 중인 작업을 모두 마치거나 타임 인터럽트가 발생하여 CPU를 반환할 때까지 우선 순위가 높은 작업이 큐에서 대기하도록 하는 방법입니다.

 

 

 

 

기아 상태(Lived lock)

기아 상태란 우선순위 스케줄링에서 우선순위가 낮은 프로세스가 먼저 대기 큐에 추가되었음에도 자원을 할당 받지 못하고 무기한으로 기다리는 상태를 의미합니다. 

 

에이징

시스템에서 오랫동안 대기하는 프로세스의 우선순위를 점진적으로 높이는 기법입니다.

 

장점

• 이 방법으로 기아 상태를 방지할 수 있다.

단점

• 대기 프로세스의 우선순위를 주기적으로 조정하기 위한 추가 오버헤드가 발생한다.
• 스케줄링 알고리즘의 복잡도 증가한다.
• 에이징 속도가 너무 느리면 우선 순위가 낮은 프로세스가 필요한 리소스를 받는 데 오랜 시간이 걸릴 수 있다. 반면에 노화 속도가 너무 빠르면 우선 순위가 높은 프로세스가 중단될 수 있습니다.

 

 

 

 

스케줄링 종류

 

선입선출 스케줄링(FCFS: First-Come-First-Serve)

큐에 들어온 순서 대로 작업을 처리하는 스케줄링 방법으로 비선점 스케줄링 방법 중 하나입니다.

 

 

 

장점

• 간단한 알고리즘 및 구현
• Context Switching 빈도 수가 낮음

단점

• 작업시간이 긴 작업이 먼저 시작될 경우 짧은 작업들이 모두 기다려야하기 때문에 응답시간이 길어질 수 있음
• 총 대기 시간이 길어질 수 있고 서비스 시간을 예측하기 어려움
• 평균 대기 시간과 평균 응답 시간 측면에서 다른 스케줄링 알고리즘에 비해 효율성이 낮음

 

 

 

최단 작업 우선 스케줄링(SJF: Shortest Job First)

총 CPU 이용 시간이 가장 짧은 작업을 먼저 실행하도록 하는 스케줄링 방법으로 일반적으로 비선점 스케줄링으로 구현되지만 선점 스케줄링으로도 구현 가능합니다.

 

 

 

장점

• 평균 대기 시간과 응답 시간이 짧음
• 자원을 효율적으로 사용되어 시스템 성능이 향상됨

단점

• 프로세스의 작업 실행 시간을 추정하는 것은 매우 어렵기 때문에 작업 실행 시간을 정확히 예측하기 어려움
• 짧은 작업이 계속 들어오는 경우 긴 작업이 무한정 대기하는 상황이 발생할 수 있음 (기아 상태)

 

 

 

최소 잔류 시간 우선 스케줄링(SRTF: Shortest Remaining Time First)

현재 실행 중인 프로세스의 남은 실행 시간과 대기 중인 프로세스들의 예상 시간을 비교하여 가장 짧은 시간을 가진 프로세르를 먼저 실행하도록 하는 스케줄링 방법입니다. 이 스케줄링 방법은 선점 스케줄링에 해당됩니다.

 

장점

• 평균 대기 시간 감소
• 빠른 응답 시간

단점

• 짧은 작업이 계속 들어오는 경우 긴 작업이 무한정 대기하는 상황이 발생할 수 있음 (기아 상태)
• 프로세스를 중단하고 새로운 프로세스를 실행하는 과정에서 선점 비용이 발생함

 

 

 

우선순위 스케줄링(Priority Based Scheduling)

프로세스에 우선순위를 부여하여 높은 우선순위를 가진 프로세스가 낮은 우선순위를 가진 프로세스 보다 먼저 실행하는 스케줄링 방법으로 선점형과 비선점형 모두 구현이 가능합니다.

 

 

장점

• 프로세스의 중요도에 따라 우선순위를 부여하고 먼저 수행할 수 있음

단점

• 우선순위가 낮은 프로세스는 계속해서 실행되지 않는 기아상태가 발생할 수 있음
• 높은 우선순위를 가진 프로세스가 낮은 우선순위를 가진 프로세스와 협력해야할 때, 높은 우선 순위 프로세스가 낮은 우선순위 프로세스의 완료를 기다리는 우선순위 역전이 발생할 수 있음

 

 

 

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

각 프로세스에 균일하게 시간을 할당하여 번갈아 작업을 수행할 수 있도록 하는 스케줄링 방법입니다. 대화형 시스템에서 응답 시간이 중요한 경우 사용하기에 적합합니다. 

 

 

 

장점

• 모든 프로세스가 공평하게 실행됨
• 빠른 응답 시간
• 구현이 간단함

단점

• 시간 할당이 너무 크면 응답 시간이 증가하고 너무 작으면 Context Switching 과정에서 오버헤드가 발생함

 

 

 

멀티 레벨 큐 스케줄링(multi-level queue scheduling)

프로세스를 여러 개의 큐로 분할하고 각 큐에 서로 다른 우선순위를 부여하는 스케줄링 방식입니다. 각 큐는 각각 다른 스케줄링 알고리즘을 적용하여 프로세스를 유형별로 처리할 수 있습니다.

 

 

장점

• 각 큐에 다른 스케줄링 알고리즘을 적용하여 프로세스를 유형별로 처리할 수 있음
• CPU 시간을 효율적으로 할당할 수 있음
• 프로세스가 큐에 영구적으로 할당되어 스케줄링 오버헤드가 낮음 
• 선점을 허용하여 우선순위가 높은 프로세스가 먼저 실행될 수 있도록 보장함

단점

• 우선순위가 높은 대기열의 작업이 모두 완료되지 않으면 일부 프로세스는 CPU를 사용할 수 없음
• 여러 대기열과 스케줄링 알고리즘을 유지 관리하는 데 복잡도가 증가함

 

 

 

멀티 레벨 피드백 큐 스케줄링

큐 간의 이동이 가능한 멀티 레벨 큐 스케줄링으로 프로세스의 실행 이력, 응답시간, CPU 사용량에 따라 우선순위를 변경할 수 있습니다.

 

 

장점

• 다른 스케줄링 방식에 비해 유연함
• 낮은 우선순위 큐에서 너무 오래 대기하는 프로세스를 높은 우선순위 큐로 이동시켜 기아 상태를 방지할 수 있음

단점

• 우선순위를 변경하는 과정에서 CPU 오버헤드가 발생함
• 너무 많은 큐로 나눌 경우 복잡성이 증가함

 

 

 

 

---

 

https://www.geeksforgeeks.org/multilevel-feedback-queue-scheduling-mlfq-cpu-scheduling/

http://cs341.cs.illinois.edu/coursebook/Scheduling#priority