CPU 스케줄링

스케줄링이란?

여러 프로세스가 있고, 이 프로세스들이 자원(CPU 등)을 동시에 요구하는데 제한된 자원들을 어떻게 (순서 할당 등) 나눠줄 것인가에 대한 정책

---

CPU 스케줄링이란?

CPU 하나는 동시에 여러 개의 프로세스를 처리할 수 없기 때문에, 한 번에 하나의 프로세스에 CPU를 할당할지 결정하는 작업

즉, 레디 큐(Ready Queue)에 있는 프로세스 중, CPU를 할당할 프로세스를 선택하는 알고리즘

 

---

CPU 스케줄링은 언제 발생하는가? 

• 실행상태에서 대기상태로 전환될 때 (ex: 입출력 요청) - Non preemptive (비선점)
• 실행상태에서 준비상태로 전환될 때 (ex: 인터럽트 발생) - preemptive (선점)
• 대기상태에서 준비상태로 전환될 때 (ex: 입출력 완료)
• 종료될 때 (Terminated)

---

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

• 프로세스가 CPU를 할당받으면 해당 프로세스가 완료될 때까지 CPU를 사용
• 이미 할당된 CPU를 다른 프로세스가 강제로 빼앗아 사용할 수 없는 스케줄링
• 일괄 처리 방식의 스케줄링에 적합 (공정하지만 빠른 응답을 요구하는 작업에는 적합하지 X)
• 필요한 문맥 교환(context switching)이 일어나기 때문에 오버헤드(Overhead)가 상대적으로 적음

오버헤드(Overhead) 란? 
어떤 일을 처리할 때 소모되는 시간과 자원 

---

FCFS (First Come First Served) - 선입 선처리 알고리즘

가장 먼저 온 것을 가장 먼저 처리하는 알고리즘 (레디 큐에 도착한 순서에 따라 CPU를 할당하는 기법)

• 장점
  • 도착 순서에 따라 공평하게 할당
• 단점
  • 응답 시간이 길어질 수 있다. (대화식 시스템에 부적합)
  • 최악의 경우 오래 걸리는 작업이 가장 먼저 들어올 수 있음
  • Convoy Effect (호위 효과)가 발생할 수 있음

Convoy 효과 (콘보이 효과 / 호위 효과)
짧은 작업들이 긴 작업 뒤에서 오래 기다리는 현상
시스템 효율을 저하시킴 

---

SJF (Short Job First)

실행시간이 가장 짧은 프로세스에 CPU를 먼저 할당하는 방식 

• 장점
  • 평균 대기 시간이 가장 짧음 
• 단점
  • 실행시간이 긴 프로세스는 CPU를 할당받지 못하고 무한히 대기하는 현상 발생 (기아현상-starvation)

---

HRN (Highest Response-ratio Next)

SJF 알고리즘에서 발생하는 기아 현상을 방지하기 위해 오랫동안 대기한 프로세스에게 우선순위를 부여하는 것.

대기시간이 길수록 결과 값이 높음

우선순위 = ((대기시간 + 서비스시간)/서비스시간)

이를 aging 기법이라고 함

---

선점형(Preemptive) 스케줄링

• 하나의 프로세스가 CPU를 할당받아 실행하고 있을 때 우선순위가 높은 프로세스가 CPU를 강제로 빼앗아 사용할 수 있는 스케줄링 기법
• 시분할 시스템에 적합 (빠른 응답 요구하는 시스템, 우선순위를 갖는 시분할 처리, 실시간 처리에 유용)
• 높은 우선 순위를 가진 프로세스들만 들어오는 경우 많은 오버헤드가 발생
• 선점을 위해 시간 배당을 위한 인터럽트용 타이머 clock이 필요 

---

RR (Round Robin)

모든 프로세스에게 동일한 시간(time quantum)을 할당하고 그 시간 안에 끝내지 못하면 다시 준비큐(ready queue)의 뒤로 가는 알고리즘 

• 장점
  • 시분할 시스템에 적합
  • 모든 프로세스가 일정 시간 내에 CPU를 할당받을 수 있어, 응답 시간이 짧다. 
• 특징
  • 할당 시간이 너무 크면 FCFS와 같아지고
  • 할당 시간이 작을 경우 문맥 교환이 자주 일어나 오버헤드가 자주 발생

---

SRTF (Shortest Remaining Time First)

남은 실행시간이 가장 짧은 프로세스에게 먼저 CPU를 할당하는 알고리즘

전체 실행시간이 아닌 남은 실행시간을 기준으로 우선순위를 결정 

• 장점
  • 평균 응답 시간 단축
• 단점
  • 잦은 문맥 교환으로 오버헤드 증가 
  • 기아 현상 발생 가능성 

---

MLQ (Multi Level Queue) - 다단계 큐 

우선순위에 따른 준비 큐를 여러 개 사용하고, 큐마다 다른 스케줄링 알고리즘을 적용한 것

큐 간의 프로세스 이동이 불가능하여 스케줄링 부담은 적지만 유연성이 떨어짐

상위 우선 순위 큐가 Empty면 하위 우선순위의 큐의 프로세스가 수행됨 

---

MLFQ (Multi Level Feedback Queue) - 다단계 피드백 큐

각 단계마다 하나의 큐를 두고, 큐 시간 할당량 내에 처리하지 못하면 다음 큐로 보내는 방식

기아 상태를 예방하는 Aging 방법

 

---

질문 List > 

Q1. 기아 (starvation) 란? 

특정 프로세스의 우선순위가 낮아 원하는 자원을 계속 할당받지 못하고 계속 대기하는 상태 

 

Q2. 에이징(Aging)이란? 

오랫동안 기다린 프로세스에게 우선순위를 높여줌으로써, 모든 프로세스가 공정하게 자원을 할당 받을 수 있도록 하는 것

기아 현상을 보완할 수 있는 기법

- HRN, MLFQ 로 Aging 기법을 구현할 수 있음

 

Q3. 라운드로빈(RR) 활용될 수 있는 예시 

라운드 로빈은 로드밸런서에서도 널리 사용되는 트래픽 분산 알고리즘
- 로드밸런서는 여러 서버에 걸쳐 들어오는 트래픽을 분산시켜 각 서버의 부하를 줄이고 시스템 전체의 성능을 향상시키는 장치

 

[라운드 로빈 알고리즘 사용 시 장점]
- 모든 서버에 고르게 트래픽을 분산시켜 각 서버의 부하를 비슷하게 유지할 수 있음
- 알고리즘이 간단하여 구현하기 쉽고 시스템에 부담을 적게 줌

[로드밸런서에서의 라운드 로빈 작동 방식]
1. 순환 방식 
 - 들어오는 요청을 순서대로 서버에 할당
2. 순환 반복
 - 모든 서버에 요청을 할당하고 나면 다시 처음 서버부터 시작
3. 가중치 부여
 - 서버의 성능이나 용량에 따라 가중치를 부여하여 특정 서버로 더 많은 요청을 할당 할 수 있음

 

질문 참고 링크 
https://eunsun-zizone-zzang.tistory.com/48

 

참고 링크 
https://github.com/devSquad-study/2023-CS-Study