CPU Scheduling

CPU가 어떤 프로세스를 언제 실행할지를 결정하는 과정
여러 프로세스가 CPU를 효율적으로 사용할 수 있도록 순서를 정하는 작업

CPU는 한 번에 하나의 프로세스만 처리할 수 있으므로, 여러 프로세스가 있을 경우 어떤 프로세스를 먼저 실행할지를 결정해야 함

목적

• 제한된 CPU 자원을 공정하고 효율적으로 분배하여 빠르게 처리하기 위해서
• 응답 시간 최소화
• 처리량 최대화
• 대기 시간 최소화
• 공정성 보장

선점형 스케줄링/비선점형 스케줄링

선점형 스케줄링(Preemptive Scheduling)

• 프로세스가 CPU를 사용하고 있더라도 운영체제가 자원을 강제로 뺏어 다른 프로세스에 할당할 수 있는 방식
• 응답 시간이 낮고 효율적이나 컨텍스트 스위칭 오버헤드 발생 가능
• 경쟁 상태 발생 가능

비선점형 스케줄링(Non-preemptive Scheduling)

• 하나의 프로세스가 자원을 사용하고 있다면 끝날 때까지 기다림
• 컨텍스트 스위칭 비용이 상대적으로 적으나 응답 시간이 오래 걸릴 수 있음

대표적인 스케줄링 방법

FCFS (First-Come First-Served)

• 먼저 도착한 프로세스를 먼저 실행함
• 프로세스를 큐에 도착한 순서대로 처리

• 구현이 간단함
• 공정한 방법으로 보임
• Convoy Effect: 긴 작업이 앞에 오면 짧은 시간이 오래 대기함
• 평균 대기 시간이 길어질 수 있음

SJF (Shortest Job First)

• 실행 시간이 가장 짧은 프로세스를 먼저 실행
• 준비 큐에 있는 프로세스 중 CPU 버스트 시간이 가장 짧은 것부터 실행
• 비선점/선점(SRTF) 두 방법 모두 존재

• 이론적으로 평균 대기 시간 최소화
• 실행 시간 (버스트 타임) 예측이 어려움
• 기아 상태(starvation): 긴 작업이 계속 뒤로 밀릴 수 있음

Priority Scheduling

• 우선순위가 높은 프로세스를 먼저 실행
• 각 프로세스에 우선순위를 부여, 낮은 숫자가 높은 우선순위로 간주하는 경우가 많음
• 선점형/비선점형 가능

• 중요 작업을 빠르게 처리 가능
• 우선순위 낮은 프로세스가 무한 대기 가능(기아) -> aging 기법으로 우선순위를 점점 높여주는 방법으로 해결 가능

Round Robin (RR)

• 정해진 시간(Time Quantum) 만큼 번갈아가며 실행
• 프로세스를 시간 단위로 잘라서 실행
• time quantum이 지나면 다음 프로세스로 전환(선점형)

• 응답 시간이 균형잡힘
• 인터렉티브 시스템에 적합(사용자 경험 개선)
• 타임 슬라이스 조정이 중요함(너무 작으면 오버헤드, 너무 크면 FCFS처럼 될 수 있음)
• context switching 증가 가능

MLFQ (Multi-Level Feedback Queue)

• 여러 개의 우선순위 큐를 만들고, 동적으로 프로세스를 이동시키는 방식
• 새로운 프로세스는 높은 우선순위 큐에서 시작
• CPU를 많이 쓰면 낮은 큐로 이동, 입출력 등 대기 많으면 높은 큐로 복귀
• 우선순위와 time quantum이 큐마다 다름

• SJF, RR, Priority 등의 장점을 모두 활용
• 다양한 작업 패턴에 적용 가능(유연함)
• 설계가 복잡함
• 튜닝이 어렵고 정책 결정이 까다로움