CPU 스케줄링 알고리즘

CPU 스케줄링 알고리즘

• CPU 스케줄링은 다중 프로그램 환경에서 CPU의 사용 시간을 효율적으로 분배하기 위한 방법이다.
• 이를 통해 시스템의 성능을 최적화하고, 대기시간을 최소화하며, CPU 사용률을 극대화하는 것이 목표다.

알고리즘 종류

• 선입선출 스케줄링(FCFS : First-Come, First-Served Scheduling)
  • 이 알고리즘은 먼저 도착한 프로세스부터 처리하는 알고리즘이다.
  • 프로세스 실행 시간을 예측하기 쉽고 단순하고 공평하지만 CPU 버스트 시간이 긴 프로세스가 먼저 도착하면 다른 프로세스들은 긴 대기 시간을 감수해야 하는 호흡성문제가 발생할 수 있다.
• 최단 작업 우선 스케줄링(SJF : Shortest Job First Scheduling)
  • CPU 버스트 시간이 가장 짧은 프로세스부터 처리하는 알고리즘
  • 평균 대기 시간을 최소화 할 순 있지만, CPU버스트 시간을 미리 알 수 없기 때문에 예측에 의존하게 된다.
• 우선 순위 스케줄링(Priority Scheduling)
  • 각 프로세스에 우선순위를 부여하고, 우선 순위가 높은 프로세스부터 처리한다.
  • 우선순위가 낮은 프로세스가 계속 대기 상태에 머무르는 기아 상태가 발생할 수 있다.
• 라운드 로빈 스케줄링(RR : Round Robin Scheduling)
  • 각 프로세스에게 동일한 시간 할당량(타임 퀀텀)을 부여하고, 그 시간 동안만 CPU를 사용하도록 한다.
  • 모든 프로세스가 공평하게 CPU를 사용할 수 있어 멀티 프로그래밍 환경에 적합하다.
• 다단계 큐 스케줄링(Multilevel Queue Scheduling)
  • 프로세스를 여러 대기열로 분류하고, 각 대기열에 다른 스케줄링 알고리즘을 적용한다.
  • 프로세스가 시스템에 도착하면 우선적으로 가장 높은 우선순위를 가진 큐 대기열에 배치된다. 그리고 주어진 시간동안 작업을 완료하지 못했을 시 한 단계 낮은 우선순위의 대기열로 이동하게 된다.
• 최단 잔여 시간 우선 스케줄링(STCF : Shortest Time-to-Completion First ,SRT : Shortest Remaining Time First)
  • SJN 방식을 선점 스케줄링 방식으로 변경한 기법
  • 실행중인 프로세스보다 남은 처리 시간이 짧은 프로세스가 들어오면 실행 중인 프로세스를 중단하고 교체한다.
  • 평균 대기 시간이 가장 짧은 알고리즘이지만, 기본적으로 선점형 방식이기 때문에 잦은 문맥교환이 일어나고 그에 따른 오버헤드가 커진다.
    • 기아 현상도 더 심하게 발생할 수 있다.

버스트(Burst)

• CPU 스케줄링에서 중요한 개념이며 CPU 버스트와 I/O 버스트 두 가지 주요 형태가 있다.
• CPU 버스트
  • 프로세스가 CPU를 연속적으로 사용하는 시간을 의미하며, 연산이나 명령 실행과 같은 작업을 수행하는데 필요한 시간을 나타낸다.
  • CPU 버스트의 길이는 프로세스마다 다르며, 이를 기반으로 CPU 스케줄링 알고리즘이 작업 순서를 결정하게 된다.
• I/O 버스트
  • 프로세스가 입출력 작업을 수행하는 데 걸리는 시간을 의미하며, 디스크 액세스, 네트워크 통신과 같은 I/O 작업을 수행하는데 필요한 시간을 나타낸다.
  • I/O 버스트 동안에는 CPU가 다른 프로세스를 실행할 수 있으므로, 다른 프로세스에서 CPU버스트를 처리할 수 있다.

호흡성 문제(Convoy effect)

• 특히 선입선출 알고리즘에서 주로 발생하는 CPU 스케줄링 문제이다.
• CPU 버스트 시간이 긴 프로세스가 먼저 CPU를 점유하게 되면, 그 뒤에 대기하고 있는 CPU 버스트 시간이 짧은 프로세스들이 불필요하게 오랫동안 대기해야 하는 상황을 말한다.
  • 이로 인해 전체적인 시스템 효율이 저하되며, 평균 대기 시간이 증가하게 된다.

기아 상태(Starvation)

• 운영체제에서 특정 프로세스가 필요한 자원을 무한정 기다리고 있지만, 다른 프로세스들이 계속해서 그 자원을 점유하고 있어서 원하는 작업을 수행할 수 없게 되는 상태를 말한다.
• 기아 상태는 특히 우선순위 스케줄링에서 발생할 수 있으며, 우선순위가 높은 프로세스가 계속 도착하게 되면, 낮은 우선순위를 가진 프로세스는 CPU를 사용할 기회를 얻지 못하고 무한히 기다리게 될 수 도 있다.
  • 기아 상태를 해결하기 위한 방법 중 하나는 에이징(Aging)이 있다.

에이징(Aging)

• 프로세스가 시스템에서 대기하는 시간이 길어질수록 그 프로세스의 우선순위를 점차 높여주는 방법이다.
• 이를 통해 모든 프로세스가 언젠가는 CPU를 사용할 수 있는 기회를 얻게 되어 기아 상태를 방지할 수 있다.

타임퀀텀(Time Quantum)

• 운영체제에서 프로세스 스케줄링에 사용되는 시간 단위를 의미하며, 특히 라운드 로빈 스케줄링에서 중요한 역할을 한다.
• 타임 퀀텀의 길이는 너무 짧으면, 프로세스 간에 자주 전환되어 오버헤드가 증가하게 되고, 반대로 너무 길면, 특정 프로세스가 CPU를 오랫동안 점유하게 되어 다른 프로세스들이 불필요하게 대기하는 상황이 발생할 수 있다.