CPU Scheduling

CPU 스케줄링은 컴퓨터 운영체제(OS) 가 CPU 를 여러 프로세스에 효율적으로 할당하는 과정임. 멀티태스킹 환경에서 CPU 는 하나의 프로세스만 실행할 수 있기 때문에, 여러 프로세스가 동시에 실행 되는 것처럼 보이도록 스케줄링이 필요하다.

---

목적

• CPU 이용율(CPU Utilization) 극대화 : CPU가 가능한 한 지속적으로 작업을 처리하도록 하여 유휴 시간을 최소화함.

• 처리량(Throughput) 증가 : 단위 시간 당 완료되는 프로세스의 수를 늘림.

• 대기 시간(Waiting Time) 최소화 : 프로세스가 준비 큐에서 대기하는 시간을 줄임.

• 응답 시간(Response Time) 단축 : 사용자의 요청에 대한 시스템의 반응 시간을 최소화 함.

• 반환 시간(Turnaround Time) 감소 : 프로세스가 시작부터 완료까지 걸리는 총 시간을 줄임.

---

유형

1. 비선점형 스케줄링(Non-Preeemptive Scheduling)

• 특징 : 한 번 CPU 를 할당받은 프로세스는 작업이 완료되거나 대기 상태로 전환될 때까지 CPU 를 점유함.

• 장점 : 문맥 교환(Context Switching) 으로 인한 오버헤드가 적음.

• 단점 : 긴 작업이 앞에 있을 경우, 짧은 작업들이 오래 대기하는 호위 효과(Convoy Effect) 가 발생할 수 있음.

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

• 특징 : 운영체제가 필요에 따라 현재 실행 중인 프로세스의 CPU 점유를 중단하고 다른 프로세스에 할당할 수 있음.

• 장점 : 긴 작업이 CPU를 독점하는 것을 방지하여 시스템의 응답성을 향상시킴.

• 단점 : 잦은 문맥 교화으로 인해 오버헤드가 증가할 수 있음.

---

주요 스케줄링 알고리즘

1. 선입선출 스케줄링(First Come First Served, FCFS)

• 방식 : 프로세스가 도착한 순서대로 CPU를 할당함.

• 특징 : 구현이 간단하지만, 긴 작업이 앞에 있을 경우 호위 효과로 인해 평균 대기 시간이 증가할 수 있음.

2. 최단 작업 우선 스케줄링(Shortest Job First, SJF)

• 방식 : 실행 시간이 가장 짧은 프로세스에 우선적으로 CPU를 할당함.

• 특징 : 이론적으로 평균 대기 시간을 최소화하지만, 각 프로세스의 실행 시간을 사전에 정확히 알기 어려움. 또한, 긴 작업이 계속해서 뒤로 밀려 기아(Starvation) 상태에 빠질 수 있음.

3. 라운드 로빈 스케줄링(Round Robin, RR)

• 방식 : 각 프로세스에 동일한 시간 할당량(Time Quantum) 을 부여하고, 이를 순환하며 CPU를 할당함.

• 특징 : 응답 시간이 일정하게 유지되며, 타임 슬라이스의 크기에 따라 성능이 크게 좌우됨. 타임 슬라이스가 너무 짧으면 문맥 교환 오버헤드가 증가하고, 너무 길면 FCFS 와 유사하게 동작함.

4. 우선순위 스케줄링(Priority Scheduling)

• 방식 : 각 프로세스에 우선순위를 부여하고, 높은 우선순위를 가진 프로세스에 먼저 CPU 를 할당함.

• 특징 : 우선순위가 낮은 프로세스는 기아 상태에 빠질 수 있으며, 이를 방지하기 위해 에이징(Aging) 기법을 사용하여 오랜 시간 대기한 프로세스의 우선순위를 점진적으로 높임.

5. 다단계 큐 스케줄링(Multilevel Queue Scheduling)

• 방식 : 프로세스를 우선순위나 특성에 따라 여러 개의 큐로 분류하고, 각 큐에 대해 별도의 스케줄링 알고리즘을 적용함.

• 특징 : 프로세스의 특성에 맞게 스케줄링할 수 있지만, 큐 간 이동이 불가능하여 유연성이 떨어질 수 있음.

6. 다단계 피드백 큐 스케줄링(Multilevel Feedback Queue Scheduling)

• 방식 : 프로세스가 실행되면서 다른 큐로 이동할 수 있도록 허용하여, 우선순위를 동적으로 조정함.

• 특징 : 기아 상태를 방지하고 다양한 프로세스를 효율적으로 처리할 수 있지미나, 구현이 복잡함.