SchedulingAlgorithms.md

CPU 스케줄링 알고리즘

운영체제에서 CPU를 어떤 순서로 할당할지 결정하는 방법입니다.
시스템 성능을 최적화하고 프로세스들이 적절한 시간에 CPU를 사용할 수 있도록 합니다.

💡스케줄링 알고리즘 평가 기준

항목	설명
CPU 사용률(CPU Utilization)	전체 시스템 시간 중 CPU가 작업을 처리하는 시간의 비율입니다.
처리량(Throughput)	단위 시간당 완료되는 작업의 수입니다. 처리량이 많을수록 시스템의 성능이 좋다고 판단할 수 있습니다.
대기 시간(Waiting Time)	프로세스가 CPU를 할당받기 위해 기다리는 시간입니다. 대기 시간이 짧을수록 프로세스의 응답 시간이 단축됩니다.
응답 시간(Response Time)	프로세스가 처음으로 CPU를 할당받아서 처음 출력이 나타날 때까지 걸리는 시간입니다.
반환 시간(Turnaround Time)	프로세스가 시스템에 진입한 시점부터 실행이 종료되어 시스템에서 빠져나가는 시점까지 걸리는 시간입니다.

참고

문맥교환 : 프로세스가 사용중이던 CPU를 다른 프로세스에게 넘겨줄 때 이전의 프로세스 상태(문맥)을 보관하고 새로운 프로세스 상태를 적재하는 작업입니다. 프로세스의 문맥은 그 프로세스의 PCB(프로세스 제어 블럭)에 기록됩니다.

오버헤드 : 문맥교환이 일어나는 동안 다른 작업을 할 수 없는데 그 시간을 일종의 오버헤드라고 할 수 있습니다.

💡비선점형 스케줄링

CPU가 한 번 할당된 프로세스는 진행 중에 다른 프로세스가 강제로 그 자리를 뺏을 수 없으며, 해당 프로세스가 스스로 실행을 완료하거나 대기 상태로 전환되어야만 다른 프로세스에게 CPU가 할당됩니다.

특징

• 간단하고 구현이 쉬워서, 작은 규모의 시스템에서 많이 사용됩니다.
• 실행 시간이 긴 프로세스가 먼저 할당될 경우, 다른 프로세스들이 대기하는 시간이 길어져 전체 시스템의 성능이 저하될 수 있습니다.
• 대규모 시스템에서는 보다 효율적인 선점형 스케줄링 방식이 사용됩니다.

❗FCFS(First-Come, First-Served) 알고리즘

• 선입선출 방식으로 가장 먼저 도착한 프로세스부터 CPU를 할당합니다.
• 대기 시간이 길어질 수 있고, 실행 시간이 긴 프로세스가 먼저 도착하면 전체 실행 시간이 길어져 다른 프로세스들의 대기 시간이 더욱 길어질 수 있습니다.

❗SJF(Shortest Job First) 알고리즘

• 실행 시간이 가장 짧은 프로세스부터 CPU를 할당합니다.
• 실행 시간을 예측하는 것이 어렵기 때문에, 프로세스가 도착할 때마다 예상 실행 시간을 계산하고 이를 기반으로 CPU를 할당합니다.

❗HRN( Highest Response Ratio Next) 알고리즘

• 프로세스 처리의 우선 순위를 CPU 처리 기간과 해당 프로세스의 대기 시간을 동시에 고려해 선정합니다.
• 운선순위는 대기 시간과 서비스 시간을 이용하여 결정합니다.

우선순위 값 = (대기 시간 + 서비스 시간) / 서비스 시간

• HRN 알고리즘은 일반적으로 시스템의 평균 대기 시간과 평균 반환 시간을 줄이는 데 효과적입니다.
• 대기 시간이 0인 프로세스는 우선순위를 갖지 못하고 계속 대기하게 되므로, 이를 해결하기 위한 방법이 필요합니다.
• 대기 시간을 고려하므로 오버헤드가 크고 구현이 복잡합니다.

💡선점형 스케줄링

CPU가 현재 실행 중인 프로세스를 강제로 중단시키고, 우선순위가 높은 다른 프로세스에게 CPU를 할당하는 방식입니다.

특징

• 실행 시간이 긴 프로세스에게 CPU가 오랫동안 할당되는 것을 방지하고, 시스템의 응답 시간과 처리율을 향상시킬 수 있습니다.
• 실행 중인 프로세스가 강제로 중단되어 자원 낭비가 발생할 수 있습니다.
• 프로세스 전환에 필요한 오버헤드가 추가되기 때문에 비선점형 방식보다는 구현이 복잡하고 오버헤드가 큰 경향이 있습니다.

❗Round Robin 알고리즘

시분할 시스템을 위한 선점형 스케줄링 방식. 프로세스들 사이에 우선순위를 두지 않고, 순서대로 시간단위(Time Quantum)로 CPU를 할당하는 방식의 CPU 스케줄링 알고리즘입니다.

• 시간 단위 동안 프로세스를 수행한 후, 완료되지 않았을 경우 준비 큐의 끝으로 밀려납니다.
• 시간 할당량이 적절하게 설정되어야 하며, 프로세스의 실행 시간이 모두 동일하지 않을 경우, 대기 시간이 길어질 수 있습니다.

❗SRT(Shortest Remaining Time) 알고리즘

• SJF 스케줄링을 선점 형태로 수정한 방식입니다.
• 현재 작업 중인 프로세스를 중단시키고 최단 잔여시간 프로세스의 처리를 시작하는 방식입니다.
• 선점형 SJF 스케줄링 또는 SRTF (Shortest Remaining Time First) 스케줄링이라고도 합니다.

❗Multilevel Feedback Queue 알고리즘

• 여러 개의 큐를 이용하여 프로세스를 스케줄링하는 알고리즘입니다.
• 각 큐는 서로 다른 우선순위를 갖고 있으며, 우선순위가 높은 큐부터 스케줄링이 이루어집니다.
• 큐마다 할당된 우선순위와 스케줄링 알고리즘을 다르게 적용할 수 있으므로, 각 프로세스의 특성에 따라 적절한 큐에 할당하여 처리할 수 있습니다.