⚙️ 운영체제 - 스케줄링 정책 (알고리즘)⚙️

< 기본적인 CPU 스케줄링 알고리즘들 >
FCFS (비선점) 
: 도착한 순서대로 스케줄링
 
SJF Shortest Job First(비선점 스케줄링)
: 가장 짧은 스레드 우선 처리
SRTF Shortest Remaining Time First(선점 스케줄링) 
: 남은 시간이 짧은 스레드가 준비 큐에 들어오면 이를 우선 처리
 
RR Round-Robin(선점 스케줄링)
: 스레드들을 돌아가면서 할당된 시간(타임 슬라이스)만큼 실행
 
Priority (선점/비선점 스케줄링 둘 다 구현 가능)
: 우선 순위를 기반으로 하는 스케줄링. 가장 높은 순위의 스레드 먼저 실행
 
MLQ: Multilevel queue (선점/비선점 스케줄링 둘 다 구현 가능)
: 스레드와 큐 모두 n개의 우선순위 레벨로 할당, 스레드는 자신의 레벨과 동일한 큐에 삽입
: 높은 순위의 큐에서 스레드 스케줄링, 높은 순위의 큐가 빌 때 아래 순위의 큐에서 스케줄링
: 스레드가 낮은 레벨의 큐에 오래 있어도 높은 레벨의 큐로 이동
 
MLFQ: Multilevel feedback queue (선점/비선점  스케줄링 둘 다 구현 가능)
: 큐만 n개의 우선순위 레벨을 둠. 스레드는 동일한 우선순위
: 스레드는 제일 높은 순위의 큐에 진입하고 큐타임슬라이스가 다하면 아래 레벨의 큐로 이동
: 낮은 레벨의 큐에 오래 있으면 높은 레벨의 큐로 이동

---

FCFS (First Come First Served) 스케줄링
: 비선점 방법
: 프로세서 스케줄링 알고리즘 중 가장 단순 프로세서 요청하는 순서대로 프로세서 할당,
: 선입선출(FIFO) 큐로 구현
➡️ 일괄 처리 시스템👍에서는 매우 효율적이나 빠른 응답을 요청하는 대화식 시스템🚨에는 bad
(느린 프로세스가 앞에 있으면 빠른 응답 불가능)

장단점

👍 구현 단순

👍 기아가 없음

👍 처리율 높음

🚨 비선점식으로 대화식 프로세스에는 부적합

🚨 장기 실행 프로세스가 앞에 잇다면 평균 대기시간이 길어져 최악의 대기시간 됨

---

 

SFJ (Shortest Job First) 스케줄링

: 프로세서가 사용 가능할때 실행시간이 가장 짧은 작업(프로세스)에 할당하는 방법 

- SFJ는 평균 대기 시간을 최소화하는 최적의 스케줄링 방식

- BUT  각 프로세스의 실행 시간을 미리 알아야 한다.. 

 

** 선점형은 간트 차트 그려서 반환시간과 대기시간 적길 바람 **

 

장단점

👍 평균 대기시간이 짧음

🚨 초기 긴 작업을 다음 짧은 작업이 끝날때까지 대기 시켜야 해서 기아 발생

🚨 불공정한 작업

🚨 실행시간 예측하기 어렵

---

 

Priority 스케줄링

: 우선순위 순, 우선순위가 동일한 프로세스들은 선입선처리 순서로 결정

: ** 우선순위의 숫자가 클수록 우선순위 높은 것임~!! **

 

장단점

👍 각 프로세스의 상대적 중요성을 정확히 정의 가능

👍 실시간 시스템에 사용 가능

🚨 무한정지와 기아 -> 👍 Aging 으로 해결

** Aging? : 시스템에서 오래 대기하는 프로세스들의 우선순위를 점진적으로 증가시키기

 

---

 

RoundRobin 스케줄링

- 시분할 시스템 ( 공평한 시간 공유가 필요한 시스템 ) 을 위해 설계된됨

- 시간 할당량(Time Quantum): 이 스케줄링 방식에서는 시간 할당량 또는 타임 슬라이스라고 불리는 작은 고정된 단위의 시간이 정의됩니다. 각 작업은 이 시간 동안만 실행됩니다. 일반적인 시간 할당량은 10~100 밀리초 범위입니다.

- 순환 큐(Circular Queue): 준비 큐는 순환 큐 형태로 구성됩니다. 스케줄러는 큐를 순서대로 돌면서 각 프로세스에 정해진 시간만큼 실행 기회를 제공합니다. 시간이 다 되면 다음 프로세스로 넘어가고, 이전 프로세스는 큐의 끝으로 이동합니다.

 

- ** 규정시간량이 작으면 문맥 교환을 많이 하므로 평균 반환시간이 더 길어짐 **

        ( 많이 쪼갠다해서 평균 터널 Runtime이 줄어드는게 아니다!!)

장단점

👍 공정하며 기아 발생 X

👍 최악의 응답시간을 알수 있음 

👍 평균 대기 시간 짧음

🚨 미완성 작업은 평균 처리시간이 높음

---

 

MLQ(Multi Level Queue) 스케줄링 (다단계 큐)

: 각 작업을 서로다른 묶음으로 (서로 비슷한 애들끼리) 분류할 수 있을 때 사용

- 준비 상태 큐를 종류별로 여러 단계로 분할,

- 작업을 메모리의 크기나 프로세스의 형태에 따라 특정 큐에 지정

- 각 큐는 자신만의 독자적인 스케줄링 가짐

 

장단점

👍 응답이 빠름

🚨 여러 개의 준비큐 & 여러개의 스케줄링 알고리즘 땜시 추가 오버헤드 발생

🚨 우선순위가 낮은 큐의 프로세스는 무한 대기하는 기아 발생 가능

 

---

 

MLFQ 스케줄링 (다단계 피드백 큐)

작업이 큐 사이 이동 (프로세서 버스트에 따른 이동)

• MLFQ에서는 프로세서 중심 프로세스와 입출력 중심 프로세스의 특성에 따라 프로세스가 큐를 이동할 수 있습니다.
  • 프로세서 중심 프로세스: CPU를 많이 사용하는 작업으로, 낮은 우선순위 큐로 내려갈 가능성이 큽니다.
  • 입출력 중심 프로세스: I/O를 자주 요청하는 작업으로, 높은 우선순위 큐에 배치되거나 빠르게 재배치될 가능성이 높습니다.

예를 들어, I/O 작업이 많은 프로세스는 높은 우선순위 큐에 남아 빠르게 처리되고, CPU를 많이 사용하는 프로세스는 점점 낮은 우선순위 큐로 이동해 CPU 자원을 효율적으로 사용하게 됩니다

 

장단점

👍 매우 유연 ( 특정 시스템에 맞게 스케줄러 구성 가능)

👍 자동분류 (입출력 중심과 프로세서 중심 작업을 자동으로 분류)

👍 적응성이 좋음 (프로세스의 사전 정보가 없어도 작업의 특성에 따라 우선순위를 조정하여 최소 작업을 우선적으로 처리하는 효과)

🚨 설계와 구현의 복잡성

 

---

 

+ 기아란?

기아(Starvation) 현상은 운영체제의 스케줄링에서 특정 프로세스가 자원을 할당받지 못해 무기한 대기하게 되는 상황을 의미합니다. 즉, 어떤 프로세스가 계속해서 CPU나 메모리 같은 자원을 사용하지 못하고 기다리기만 하다가 실행되지 못하는 문제입니다.

 

기아 현상이 발생하는 주된 이유는 우선순위가 낮은 프로세스가 계속해서 높은 우선순위의 프로세스에게 밀리기 때문입니다. 예를 들어, 우선순위 기반 스케줄링에서는 우선순위가 높은 프로세스가 계속해서 CPU를 차지하게 되어 우선순위가 낮은 프로세스는 오랫동안 실행되지 못할 수 있습니다.