운영체제 - CPU 스케줄링 알고리즘

CPU 스케줄링 알고리즘

---

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

CPU가 유후 상태가 될 때마다 운영 체제에서 준비 큐에 있는 프로세스 중 하나를 선택해서 실행하게 되는데 이때 CPU 스케줄러에 의해서 실행된다.

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

 

CPU 스케줄링 알고리즘의 목표

• CPU 활용도를 최대 수준으로 유지한다.
• 모든 프로세스에 CPU를 공정하게 할당한다.
• 단위 시간당 실행을 완료하는 프로세스 수가 최대여야 한다.
• 프로세스가 완료하는 데 걸리는 시간이 최소여야 한다.
• 프로세스가 준비 큐에서 대기하는 시간이 최소여야 한다.
• 프로세스가 응답을 생성하는 시간이 짧아야 한다.

 

CPU 스케줄링에 사용되는 용어

• 도착 시간(Arrival Time): 프로세스가 준비 큐에 도착하는 시간을 의미한다.
• 완료 시간(Completion Time): 프로세스가 실행을 완료하는 시간을 의미한다.
• 버스트 시간(Burst Time): CPU 실행을 위해 프로세스에 필요한 시간을 의미한다.
• 처리 시간(Turn Arround Time): 프로세스 완료 시간과 도착 시간의 차이를 의미한다.
• 대기 시간(Waiting Time): 프로세스 처리 시간과 버스트 시간의 차이를 의미한다.

 

CPU 스케줄링의 방식

• 선점형 방식

1. 프로세스가 실행 상태에서 준비 완료 상태로 전환될 때 (인터럽트 발생할 때)
2. 프로세스가 대기 상태에서 준비 완료 상태로 전환될 때 (I/O 종료할 때)

• 비선점형 방식

1. 한 프로세스가 실행 상태에서 대기 상태로 전환될 때 (I/O 발생할 때)
2. 프로세스가 종료될 때

 

비선점형 방식

---

프로세스가 스스로 CPU 소유권을 포기하는 방식이며 강제로 프로세스를 중지하지 않는다. 따라서 컨택스트 스위칭으로 인한 부하가 적다.

 

FCFS(First Come First Service)

먼저 요청한 프로세스에 CPU를 할당하고 FIFO 대기열을 사용하여 구현되는 방식으로 가장 먼저 온 것을 가장 먼저 처리하는 알고리즘이다.

 

FCFS의 특징

• 작업은 항상 먼저 온 순서대로 실행하게 된다.
• 구현 및 사용이 쉽다.
• 길게 수행되는 프로세스 때문에 준비 큐에서 오래 기다리는 현상이 발생하여 성능면에서 그다지 효율적이지 않으며 대기 시간이 높다는 단점이 있다.

 

SJF(Shortest Job First)

SJF는 대기하고 있는 프로세스 중에서 실행 시간이 가장 짧은 프로세스를 선택하여 다음 작업을 수행하는 방식이다.

 

SJF 특징

• 모든 스케줄링 알고리즘 중 평균 대기 시간이 가장 짧다.
• 긴 시간을 가진 프로세스가 실행되지 않는 현상(기아 현상)이 발생할 수 있다.
• 실제로는 실행 시간을 알 수 없기 때문에 프로세스 별 CPU 버스트를 예측해서 스케줄링을 구현해야 한다.

 

우선순위(Priority Scheduling)

기존 SJF 스케줄링 방식을 보완한 알고리즘으로 오래된 작업일수록 우선순위를 높이는 방법(aging)이다.

우선 순위 스케줄링을 사용하게 되면 무한 봉쇄나 기아 상태 문제가 발생할 수 있다.

 

• 무한 봉쇄(Blocking)

실행 준비는 되어 있으나 CPU를 사용하지 못하는 프로세스는 CPU를 기다리면서 봉쇄된 것으로 간주할 수 있다.

• 기아 상태(Stravation)

부하가 과중한 컴퓨터 시스템에는 높은 우선순위의 프로세스들이 꾸준히 들어와서 낮은 우선순위의 프로세스들이 CPU를 얻지 못하게 될 수도 있다.

이러한 문제를 해결하기 위해서 노화(aging)을 사용하여 오랫동안 시스템에서 대기하는 프로세스들의 우선순위를 점진적으로 증가시켜 해결한다.

 

우선순위의 특징

• 가장 우선순위가 높은 프로세스가 먼저 수행되어야 한다.
• 동일한 우선순위를 가진 프로세서가 두 개 이상으로 존재하여 충돌이 발생할 경우 FCFS 알고리즘을 기반으로 작동하게 된다.
• 우선순위가 낮은 작업이 실행되는 동안 우선순위가 높은 작업이 도착하면 높은 작업을 먼저 실행하게 된다.
• 평균 대기 시간이 FCFS 보다 짧다.

 

선점형 방식

---

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

 

라운드 로빈(Round robin)

현대 컴퓨터가 쓰는 스케줄링인 우선순위 스케줄링의 일종으로 각 프로세스는 동일한 할당 시간을 주고 그 시간 안에 끝나지 않으면 다시 준비 큐의 뒤로 가는 알고리즘이다.

 

라운드 로빈의 특징

• FCFS 알고리즘의 선점형 버전으로 일반적으로 시간 공유 기술에 중점을 둔다.
• 모든 프로세스가 균형 잡힌 CPU 할당을 받기 때문에 간단하고 사용하기 쉬우며 기아 현상이 없다.
• 로드밸런서에서 트래픽 분산 알고리즘으로도 쓰인다.

 

SRF(Shortest Remaining Time First)

중간에 더 짧은 작업이 들어오면 수행하던 프로세스를 중지하고 해당 프로세스를 수행하는 알고리즘이다.

 

SRF의 특징

• 오버헤드를 고려하지 않기 때문에 SJF 알고리즘보다 작업 처리 속도가 빠르다.
• 가장 짧은 작업을 먼저 수행하기 때문에 기아 현상이 발생할 수 있다.
• 시스템은 프로세스가 완료되거나 새 프로세스가 추가될 때만 결정을 내리기 때문에 오버헤드가 거의 필요하지 않다.

 

다단계 큐(Multilevel Queue Scheduling)

우선순위에 따른 준비 큐를 여러 개 사용하고, 큐마다 라운드 로빈이나 FCFS 등 다른 스케줄링 알고리즘을 적용한 것을 말한다.

 

다단계 큐의 특징

• 프로세스가 해당 큐에 영구적으로 할당되므로 스케줄러가 실행을 하기 위해 적절한 큐만 선택하면 된다. 따라서, 스케줄링 오버헤드가 낮다.
• 큐 간의 프로세스 이동이 안 되므로 스케줄링 부담이 적지만 유연성이 떨어지는 특징이 있다.

 

다단계 피드백 큐

다단계 큐 알고리즘은 일반적으로 프로세스들이 시스템 진입 시에 영구적으로 하나의 큐에 할당된다. 그러므로 유연성이 떨어진다는 단점을 지니고 있는데 이를 개선한 알고리즘이 다단계 피드백 큐 알고리즘이다.

다단계 피드백 큐는 프로세스가 큐 간 이동하는 것을 허용하게 된다. 이를 통해서 Aging과 Stravation을 예방할 수 있게 된다.

 

다단계 피드백 큐의 특징

• 특정 시스템에 부합하도록 구성할 수 있어 현대 사용되는 CPU 스케줄링 알고리즘 중 가장 일반적인 CPU 스케줄링 알고리즘이다.
• 가장 좋은 스케줄러로 동작하기 위해서는 모든 매개변수 값들을 선정하는 특정 방법이 필요하기 때문에 가장 복잡한 알고리즘이라는 단점을 가지고 있다.

 

 

참고 자료

---

- CS전공지식노트(주홍철)
- https://www.geeksforgeeks.org/operating-systems/?ref=ghm

Operating System Tutorial - GeeksforGeeks