🚦 CPU 스케줄링 알고리즘

CPU 스케줄러는 CPU 스케줄링 알고리즘에 따라, 어떤 프로세스(의 스레드)에게 CPU를 할당할지 결정합니다. 프로그램이 실행될 때, CPU 스케줄링 알고리즘은 어떤 프로그램에 CPU 소유권을 줄 것인지 결정합니다. 이 알고리즘의 목표는 다음과 같습니다.

• CPU 이용률은 높게
• 처리량 (주어진 시간에 많은 일을 처리)은 많게
• 대기 시간 (준비 큐에서 기다리는 시간)은 짧게
• 응답 시간 (작업 요청 후 첫 반응까지의 시간)은 짧게

---

✋ 비선점형 방식(non-preemptive)

프로세스가 스스로 CPU 소유권을 포기할 때까지 (예: I/O 작업 요청) 기다리는 방식입니다. 운영체제가 강제로 프로세스를 중지시키지 않습니다. 따라서 문맥 교환(Context Switching)으로 인한 부하가 적습니다.

🚶➡️ FCFS(First Come, First Served)

가장 먼저 준비 큐(Ready Queue)에 도착한 순서대로 처리하는 알고리즘입니다. (일명 '선착순') 하지만 아주 긴 작업이 CPU를 독점하면, 그 뒤에 있는 짧은 작업들이 하염없이 기다려야 하는 '호위 효과(Convoy Effect)'라는 심각한 단점이 있습니다.

⚡ SJF(Shortest Job First)

실행 시간이 가장 짧을 것으로 예상되는 프로세스를 가장 먼저 실행하는 알고리즘입니다. 평균 대기 시간을 가장 짧게 만드는 최적의 알고리즘이지만, 실행 시간이 긴 프로세스는 자신보다 짧은 작업들에게 계속 밀려 영원히 실행되지 못하는 현상(기아 상태, starvation)이 일어날 수 있습니다.

현실적 한계: 실제로는 실행 시간을 미리 알 수 없기 때문에, 과거의 실행 시간을 토대로 추측해서 사용합니다.

👑 우선순위(Priority)

프로세스마다 '우선순위'라는 등급을 부여하고, 우선순위가 가장 높은 프로세스에게 CPU를 할당하는 알고리즘입니다. (SJF도 '실행 시간이 짧은 것'을 가장 높은 우선순위로 본다고 할 수 있습니다.)

단점: SJF와 마찬가지로, 우선순위가 낮은 프로세스는 기아 상태(starvation)에 빠질 수 있습니다.

해결책: 이를 보완하기 위해, 오래 기다린 프로세스의 우선순위를 점점 높여주는 '에이징(Aging)' 기법을 함께 사용하기도 합니다.

---

🚦 선점형 방식(preemptive)

현대 운영체제가 주로 쓰는 방식으로, 지금 사용하고 있는 프로세스를 (시간 만료, 우선순위 등) 알고리즘에 의해 강제로 중단시키고 다른 프로세스에 CPU 소유권을 할당하는 방식입니다.

🔄 라운드 로빈(RR, Round Robin)

현대 컴퓨터가 쓰는 대표적인 선점형 스케줄링 방법입니다. 각 프로세스는 '타임 슬라이스(q)'라는 동일한 할당 시간을 받습니다. 만약 그 시간 안에 작업이 끝나지 않으면, 프로세스는 준비 큐(Ready Queue)의 맨 뒤로 보내집니다. (모든 프로세스가 공평하게 돌아가며 기회를 얻음)

• 예를 들어 q만큼의 할당 시간이 부여되었고 N개의 프로세스가 운영된다고 하면, (N-1) * q 시간이 지나면 자기 차례가 오게 됩니다.
• 특징: 할당 시간(q)이 너무 크면 FCFS처럼 동작하고, 너무 짧으면 문맥 교환(Context Switching)이 잦아져 오버헤드(비용)가 커집니다.
• 장점: 전체 작업 시간은 길어질 수 있지만, 평균 응답 시간은 짧아진다는 큰 장점이 있습니다. (짧은 작업들이 긴 작업 뒤에서 기다릴 필요가 없음)
• 활용: 이 알고리즘은 로드밸런서에서 트래픽을 분산하는 알고리즘으로도 쓰입니다.

🔬 SRF(Shortest Remaining Time First)

(SJF는 비선점형이라 일단 시작하면 끝나야 합니다.) SRF는 현재 실행 중인 작업의 '남은 시간'보다 '더 짧은' 작업이 준비 큐에 새로 들어오면, 즉시 수행하던 프로세스를 중지(선점)하고 그 더 짧은 작업을 수행하는 알고리즘입니다.

📊 다단계 큐(Multilevel Queue)

우선순위별로 준비 큐(Ready Queue)를 여러 개 사용하는 방식입니다. 예를 들어, '실시간 작업 큐', '일반 작업 큐', '백그라운드 작업 큐' 등으로 나눕니다.

• 각 큐는 서로 다른 스케줄링 알고리즘(예: 실시간 큐는 FCFS, 일반 큐는 라운드 로빈)을 적용할 수 있습니다.
• 특징: 큐 간의 프로세스 이동이 안 된다는 규칙이 있어 스케줄링 부담이 적지만, 작업의 성격이 바뀌어도 큐를 옮길 수 없어 유연성이 떨어지는 특징이 있습니다.

---

1. 선점형 스케줄링과 비선점형 스케줄링의 차이에 대해 설명하세요.

선점형 스케줄링은 운영체제가 강제로 CPU를 빼앗아 다른 프로세스에 할당할 수 있는 방식으로, 라운드 로빈이 대표적입니다. 긴급한 작업을 빠르게 처리할 수 있어 현대 운영체제 대부분이 이 방식을 사용합니다. 반면 비선점형 스케줄링은 프로세스가 작업을 마치거나 대기 상태가 되기 전까지는 CPU를 놓지 않는 방식입니다. FCFS가 대표적이며, 문맥 교환 오버헤드는 적지만 긴급한 작업이 늦어질 수 있다는 단점이 있습니다.