[OS] CPU 스케줄링 알고리즘

1. CPU 스케줄링이란?

언제 어떤 프로세스에 CPU를 할당할지 결정하는 작업

 

---

 

2. 목적

CPU 스케줄링 알고리즘은 CPU 이용률은 높게, 주어진 시간에 많은 일을 하게, 준비 큐에 있는 프로세스는 적게, 응답시간은 짧게 설정하는 것

따라서 CPU 스케줄러가 스케줄링을 결정할 때는 아래와 같다.

 

CPU 스케줄러가
스케줄링을 결정할 때

• 실행(running) 상태에서 대기(waiting) 상태로 전환(switching)될 때
• 실행(running) 상태에서 준비(ready) 상태로 전환(switching)될 때
• 대기(waiting) 상태에서 준비(ready) 상태로 전환(switching)될 때
• 종료(Terminated)될 때

👉 1, 4번 상황에서만 스케줄링이 발생하는 것을 비선점형(non-preemptive) 스케줄링,

이외의 모든 스케줄링은 선점형(preemptive) 스케줄링이라고 함

 

 

---

 

3. 비선점형 스케줄링

• 정의: 어떤 프로세스가 CPU를 점유하고 있다면 이를 뺏을 수 없는 방식
• 특징: 강제로 프로세스를 중지하지 않음
• 장점: 문맥 교환(Context Switching)으로 인한 부하가 상대적으로 적음
• 단점: 프로세스의 배치에 따라 효율성 차이가 많이 남
• 종류: FCFS, SJF, 우선순위

 

- FCFS (First Come, First Served)

 

• 정의: 가장 먼저 요청한 프로세스에 CPU를 할당해주는 선착순 방식
• 단점: Convoy Effect(호위 효과)가 발생할 수 있음
  👉 몇 개의 시간이 오래 걸리는 프로세스로 인해 전체 OS가 느려지는 현상

 

---

 

- SJF (Shortest Job First)

 

• 정의: 실행 시간이 가장 짧은 프로세스를 먼저 실행하는 알고리즘
• 단점
  • 실제로는 프로세스의 CPU 실행 시간을 예측하는 것이 어려움
  • 기아 현상 발생 가능: 긴 시간을 필요로 하는 프로세스가 우선순위에 계속 밀려 실행되지 못하고 무기한으로 대기하게 되는 현상

 

---

 

- 우선순위

 

• 정의: 각각의 프로세스에 우선순위 번호가 있는 알고리즘
• 장점
  • SJF 알고리즘의 경우 낮은 우선 순위의 프로세스가 절대 실행되지 않는 기아 문제가 발생할 수 있는데
    이를 해결하기 위해서 오래된 작업의 순위를 높여주는 노화(aging)를 사용 가능

 

---

 

4. 선점형 스케줄링

• 정의: 어떤 프로세스가 CPU를 할당받아 실행 중이더라도 운영체제가 이를 강제로 뺏을 수 있는 방식
  알고리즘에 따라 강제로 중단시키고 다른 프로세스에 CPU를 할당하는 방식
• 장점: 처리 시간이 매우 긴 프로세스의 CPU 사용 독점을 막을 수 있어 효율적인 운영 가능
• 단점: 잦은 컨텍스트 스위칭으로 인해 오버헤드가 커질 수 있음
• 종류: 라운드 로빈, SRF, 다단계 큐

 

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

 

• 정의: 각각의 프로세스에 동일한 할당 시간을 부여해서 해당 시간 동안만 CPU를 이용하게 함
• 특징: 할당 시간 내에 처리를 완료하지 못하면 강제 중단 후 다음 작업으로 넘어감
• 장점: 응답 시간을 빠르게 할 수 있음
• 단점
  • 할당 시간이 길면 FCFS처럼 작동함
  • 할당 시간이 너무 짧으면 process sharing이라고 부름
    : n개의 프로세스가 프로세서 속도의 1/n씩으로 작동함

 

---

 

- SRF

 

• 정의: 현재 실행되고 있는 프로세스의 남은 시간보다 더 짧은 프로세스가 들어오면 현재 실행되는 프로세스를 중단하고 짧은 프로세스를 실행하도록 바꾸는 알고리즘. SRTF(Shortest Remaining Time First)라고도 부름
• 장점: 평균 대기 시간을 줄일 수 있음
• 단점: 다음 프로세스의 CPU burst time을 예측하는 것이 어려움

 

---

 

- 다단계 큐

 

• 정의: 우선순위에 따른 준비 큐가 여러 개의 큐들로 나뉘고 각각의 큐는 스케줄링 알고리즘을 가짐
• 단점
  • 우선순위가 높은 큐부터 처리되므로 낮은 큐의 프로세스가 처리가 안 되는 기아 현상이 나타날 수 있음
  • 각 큐 사이에서 프로세스들이 이동할 수 없어서 유연성이 떨어짐

 

---

 

출처

 

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