[CS 개념] 프로세스 스케줄링 알고리즘

프로세스 스케쥴링 알고리즘에 대해 설명해주세요.

프로세스 스케쥴링 알고리즘은 운영체제가 CPU와 같은 컴퓨터 자원을 효율적으로 사용할 수 있도록 프로세스의 실행 순서를 정하는 방법입니다.
프로세스의 우선순위, 실행 시간, 대기 시간 등을 고려하여 시스템 응답 시간 단축이나 처리량 극대화 등의 목표를 달성하려 합니다.

스케쥴링 알고리즘 종류

1. 비선점형 스케쥴링 (Non-preemptive Scheduling)

   • 한번 CPU를 점유한 프로세스는 작업이 끝날 때까지 CPU를 사용.
   • 대표 알고리즘:
     • FCFS (First-Come, First-Served)
       • 프로세스가 도착한 순서대로 실행.
       • 긴 프로세스가 먼저 도착하면 다른 프로세스가 오래 기다릴 수 있는 컨보이 효과(Convoy Effect) 발생.
     • SJF (Shortest Job First)
       • 실행시간이 짧은 프로세스부터 실행
       • 평균 대기시간이 줄어들지만, 긴 프로세스가 무한히 대기할 가능성이 있음

2. 선점형 스케쥴링 (Preemptive Scheduling)

   • 실행 중인 프로세스를 강제로 중단하고 다른 프로세스 실행 가능
   • 대표 알고리즘:
     • SRTF (Shortest Remaining Time First)
       • 남은 실행 시간이 가장 짧은 프로세스부터 실행
       • SJF의 선점형 버전, 평균 대기 시간을 줄일 수 있음
     • RR (Round Robin)
       • 모든 프로세스가 동일한 시간 단위를 할당받아 순환 실행
       • 공정성을 유지하며 응답시간을 개선
     • Priority Scheduling
       • 우선순위가 높은 프로세스가 먼저 실행.
       • 우선순위가 낮은 프로세스가 오랫동안 실행되지 못할 수 있는 기아 상태 발생 가능.

3. 다단계 큐 스케쥴링

   • 프로세스를 우선순위 별 큐로 분리하고 각 큐에 별도의 스케쥴링 알고리즘을 적용.

4. 다단계 피드백 큐 스케쥴링

   • 다단계 큐 스케쥴링의 개선 버전으로, 프로세스가 특정 조건에 따라 다른 큐로 이동 가능.
   • 대기 시간이 긴 프로세스는 우선순위를 높이는 방식으로 기아 상태를 방지.

---

reference

• https://velog.io/@qq7455/CPU-%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%9A%94%EC%95%BD%EC%A0%95%EB%A6%AC