[운영체제] 스케줄링 알고리즘

ChatGPT가 생성한 이미지 파일.

스케줄링 개념

스케줄링은 프로세스가 CPU를 사용할 수 있도록 할당하는 방법을 의미합니다. 스케줄링의 목표는 CPU의 효율성을 높이고, 응답 시간을 최소화하며, 처리율을 극대화하는 것입니다. 스케줄러는 어떤 프로세스가 언제 CPU를 사용할지 결정하는 중요한 역할을 합니다.

스케줄링 용어

• Turnaround Time (처리 시간): 프로그램이 실행을 시작해 완료되기까지 걸린 전체 시간.
• Response Time (응답 시간): 사용자가 요청을 제출하고, 첫 번째 응답을 받을 때까지 걸린 시간.
• Throughput (처리율): 단위 시간당 처리된 프로세스의 수.
• Processor Utilization (CPU 이용률): CPU가 실제로 사용된 시간의 비율을 의미합니다​.

스케줄링 알고리즘

1. FCFS (First-Come, First-Served):
   • 도착한 순서대로 프로세스를 실행합니다. 비선점형 방식으로, 한 프로세스가 CPU를 점유하면 끝날 때까지 CPU를 계속 사용합니다. 긴 작업이 먼저 도착하면 짧은 작업은 오랫동안 기다려야 하는 단점이 있습니다.
   • 장점: 구현이 쉽고 간단합니다.
   • 단점: 긴 작업이 짧은 작업의 응답 시간을 지연시킬 수 있습니다.
2. Round Robin (RR):
   • 각 프로세스에 일정한 타임 슬라이스 (time slice)를 할당하고, 그 시간이 지나면 다른 프로세스로 전환하는 방식입니다. 선점형 방식이므로, CPU 사용 시간을 나누어줍니다.
   • 장점: 짧은 응답 시간을 제공합니다.
   • 단점: 타임 슬라이스가 너무 크면 FCFS와 비슷해지고, 너무 작으면 문맥 교환이 빈번해져 오버헤드가 증가할 수 있습니다.
3. SPN (Shortest Process Next):
   • 실행 시간이 가장 짧은 프로세스를 먼저 실행하는 비선점형 알고리즘입니다. 응답 시간이 짧아지지만, 긴 프로세스는 계속해서 대기할 수 있는 기아 현상 (Starvation)이 발생할 수 있습니다.
4. SRT (Shortest Remaining Time):
   • SPN의 선점형 버전으로, 남은 실행 시간이 가장 짧은 프로세스를 먼저 실행합니다. 새로 들어온 프로세스가 현재 실행 중인 프로세스보다 남은 시간이 짧다면, 스케줄러는 새로운 프로세스로 전환합니다.
5. HRRN (Highest Response Ratio Next):
   • 응답 비율이 가장 높은 프로세스를 우선적으로 실행하는 비선점형 알고리즘입니다. 응답 비율은 다음과 같이 계산됩니다.​

     

     
     기다린 시간이 길거나 서비스 시간이 짧을수록 우선순위가 높아집니다.
6. Feedback 스케줄링:
   • 실행 시간이 긴 프로세스에게 패널티를 부여하는 방식입니다. 한 프로세스가 CPU를 계속 독점하는 것을 방지하며, 프로세스가 오래 실행될수록 우선순위를 낮추어 다른 프로세스들이 CPU를 사용할 수 있도록 합니다.