[OS 기초] 09. 단일처리기 스케줄링 (Scheduling)

[ 처리기 스케줄링의 유형 ]

• 처리기 스케줄링의 정의

• 응답 시간이나 처리량, 효율성을 증대시키기 위해 처리기가 다음에 실행할 프로세스를 선택하는 것! → 성능 평가 관련

 
Q. 어떤 정책, 알고리즘 기반으로 다음 프로세스를 선택하는가?
→ 성능을 결정짓는 중요한 요소 : Response Time, Throughput
짧은 응답시간(Response Time), 높은 처리량(Throughput) 달성은 대립됨 (둘 다 만족시키기 어려움)
 
Task Type - I/O Bound, CPU Bound

• I/O Bound
  • 입출력 관련 처리가 위주, 뭔가 요청하지 않으면 가만히 있고 문자열 입력 시 반영(입력 발생하여 화면에 출력하기 위한 부분만 CPU사용)
  • 짧은 Response Time이 목표, 사용자의 요구에 반응속도가 중요, 입출력을 위한 대기를 위해 시간을 더 소비

• CPU Bound
  • 어떤 프로세스가 실행되었을 때 기준 시간(time slice)을 할당 (CPU연산이 중심(의존도)인지를 따짐)
  • 할당받은 시간 내에 많은 Throughput이 목표, 산출량이 많아야 함
  • Time Slice를 CPU Bound에는 길게 주는 게 유리 ↔ I/O Bound는 짧은 게 유리 (대기 시간 누적과 관련)

어떤 Bound인지 알아내는 건 불가능하므로 Time Slice 크기를 결정하기가 어려워짐
길게 하면의 응답시간이 나빠지고, 짧게 만들면 연산을 한다. switching 되는 상황 발생
 
Q. 최상의 성능을 이끌어내기 위해?
스케쥴러의 구성도 복잡해짐 (추후 설명)

 
• 선후 관계에 따른 스케줄링의 유형

스케줄링의 유형

• 장기 스케줄링 : degree of multiprogramming을 결정 (새로운 프로세스 실행 : 얼마나 많은 프로세스를 동시에 실행 가능한 상태로 만들어 놓을 수 있을지 )
• 중기 스케줄링 : swapper의 역할 (swap space 관련한 프로세스 상태 전이를 결정)
• 단기 스케줄링 : CPU 스케줄링에 해당 (일반적으로 아는 스케줄러에 해당)

 

``프로세스 상태, 상태 전이``

장기 : 프로세스 생성 시 CPU에 의해 실행시켜도 되는 상황인지 여부(리소스 포화 여부)
중기 : 메모리 부족 시 ready, block상태의 프로세스는 메모리상 swap in, out에 관여
단기 : Ready 중에서 다음 프로세스를 선택
 
프로세스가 일생 동안 거치는 스케줄링 큐 다이어그램

* 스케쥴러의 호출 빈도에 따라 구분
- 장기 스케줄링 : 호출 빈도 떨어짐, 중기, 단기는 짧은 텀. 빈번하게 호출
 
[장기 스케줄링]
새 프로세스의 시스템 진입 허용 여부를 결정하는 단계
1) 멀티프로그래밍의 정도(Degree of Multiprogramming) 결정
 

• 시스템 내에 얼마나 많은 프로세스를 진입시킬지 결정
• [참고] CPU 점유율이 90%를 넘으면 문제 발생 징후로 봄 (꽉 찼을 때 발생하는 것이 아님)

2) 새로운 프로세스의 진입 허용 시점은? (시스템 부하 조절)

• 시스템이 포화 상태인지 여부를 판단하여 조절함
• [참고] OOM (Out Of Memory) 현상과 리눅스:
  • 메모리 부족 시 새 프로그램을 실행하려 한다면? → 실행 거부(X) 대신 사용자 우선권(범용 OS)을 따름
  • OOM Killer: 가용 메모리 확보를 위해 존재. 점유 중인 메모리에 스코어(Score)를 매김
  • 방출(Kill): 이때 낮은 스코어를 가진 프로세스는 방출 (스코어 계산 시 부하 발생)

3) 어떤 규정으로 작업들을 골라 프로세스로 만들 것인가? (기준)

• FCFS (First-Come-First-Served): FIFO 방식. 구현은 가장 간단하나, I/O Bound인지 CPU Bound인지 전혀 고려하지 않는 환경.
• Priority-based: 우선순위(중요도)가 높음을 의미
• CPU-burst 길이: 수행 시간이 짧은 것 
• 입출력 중심(I/O-bound) 프로세스 우대:
  • [참고] 시간 할당 시 대기하는 데 시간을 씀(낭비처럼 보임) + 요구 시만 CPU 사용.
  • 장점: 다른 프로세스의 성능 저하에 큰 영향을 끼치지 않으면서 시스템 효율을 높임
• 여유 입출력 자원 사용 예정 프로세스 우대:
  • 여유롭지 않은 입출력 자원은 경쟁이 치열함
  • 반면, 여유로운 자원은 즉시 가용 가능하므로 이를 쓰는 프로세스를 바로 실행시키는 것이 유리함.

 
[중기 스케줄링]
스와핑(swapping) 기능의 일부 – 스왑 공간으로 쫓겨나간(swap-out) 프로세스 전체 또는 일부 중 어느 것을 다시 주 메모리로 스왑인(swap-in)할 것인가?
 
[단기 스케줄링]
1)  정의 및 특징

• 디스패쳐 (Dispatcher)라고도 불림
• 실행 빈도: 장기/중기 스케줄러보다 매우 자주 실행됨
• 세밀한 기준으로 다음번에 실행시킬 프로세스를 선정

2) 단기 스케줄러 실행 시점
언제 스케줄러가 개입하는지에 대한 4가지 경우

1. 클럭(타이머) 인터럽트 발생 시
   • 시간 할당량 만료 시
   • [참고] 스케줄러에 의해 다음 프로세스로 교체되는 시점.
2. 입출력(I/O) 인터럽트 발생 시
3. 운영체제 시스템 호출 (System Call)
   • (커널 내 preemption point 또는 사용자 모드로 복귀하기 직전)
   • [참고] 시스템 호출도 엄밀히 따지면 인터럽트 기반으로 처리되는 방식
   • [흐름] 시스템 콜 → 커널에서 처리 → 사용자 수준의 프로세스로 복귀
4. 신호 (Signal)
   • 예: 세마포어 조작 등

I/O 인터럽트 처리 메커니즘
1. 인터럽트 발생: 입출력 요청이나 완료 등의 신호 발생
2. 제어권 이양:
 CPU의 제어권이 운영체제(OS)로 넘어감
3. 상태 전이: 현재 수행 중이던 프로세스는 보류(Block) 상태로 전이
4. 핸들러 분기: 제어권을 받은 OS는 해당 인터럽트를 처리할 핸들러로 분기
(참고) 이때 핸들러는 블록 된 상태의 프로세스와 연관된 입출력이라면, 그 안에 처리 모듈이 포함되어 있음
5. 수행 재개: 입출력 완료 후, 그 결과를 가지고 다음 작업을 수행해야 하는 프로세스가 깨어나서(Ready) 수행을 재개

 

스케줄링 알고리즘

[단기 스케줄링 평가 기준]
기준 1 : 사용자 중심 관점 vs. 시스템 중심 관점 ( CPU vs I/O Bound )
기준 2 : 성능 중심 관점 vs. 성능 외적 관점
성능 중심 : 정량적인 척도 → 측정 용이 (ex. Response time, Throughput)
성능 외적 : 정성적인 척도 → 측정 어려움 (ex. 예측 가능성)

 
[우선순위 기반 스케줄링]
Android : Java → Compiler (c, c++), Interpreter (Python, shell script)
- 자바 언어를 처리하기 위해 Java SDK 필요
- JDK안에 Javc.exe 컴파일러 존재) → 자바 인터프리터(Java Interpreter) 언어인데 왜 compiler가 있지?
javac를 이용하여 컴파일을 해야 함 인터프리터 언어인데?) → 결과물 : 동일한 이름의 class파일이 생성됨 ; class안에는 java Bytecode의 집합으로 이루어짐 → JVM(javaruntime)에서 변환이 이루어짐 → native 기계어 코드로 바뀌고 JVM의 CPU에서 다시 해석
실행단위는 translate, 자바가 인터프리터인 이유는 실행 방식에 있음. 한 줄씩 실행
인터프리터의 기능 때문에 성능 저하(반환 시간의 지연)의 문제가 나타남
 
인터프리터가 컴파일러 언어보다 더 좋은 점은 Response Time이 뛰어나다. (컴파일러는 게임에서 모든 적재가 끝나야 시작이 되는데(응답 시간 길음) 인터프리터는 첫 줄에 대한 결과를 바로 볼 수 있는 것이 유일한 장점이다.)
 

안드로이드 구조

여러 가지 컴포넌트 구성, 애플리케이션 개발하기 위한 클래스들이 컴포넌트화 되어있는 구조
 
Q. Libraries와 Rintume layer는 왜 한 층에 한 개씩 구성이 아니고 같이 묶여 있을까?
성능 문제를 해결하기 위해 Native Code를 도입
native mt func() : 이 함수는 native가 들어가지 않은 함수와 뭐가 다를까
뭔가 처리하기 위해 CPU필요, CPU의 종류에 따라 instruction set을 이용하여 코드가 만들어져야 함 → 호환성, 이식성 문제
장점. JVM은 CPU가 뭐든 간 runtime 성능이 올라갈 있으면 모든 아키텍처 적용이 가능! (자바 바이트 코드로 해석 → JVM이 해당 CPU타입에 대한 기계어(native)로 번역해 줌) 이식성 고민 필요 x
단점. 문제는 인터프리터 형식으로 변환을 한 번 더 해야 한다.
native mt func() 함수라고 했지만 네이티브 키워드이면 인터프리터에서 실행 x, 라이브러리 계층에서 처리
native code가 필요한 경우 잦은 빈도로 호출 → 성능과 큰 연관을 가짐. (미리 기계 코드로 뽑아 놓음)
path가 둘로 나뉘어서 일반 Java Bytecode는 인터프리터 처리, native 키워드를 포함한 함수 호출은 라이브러리에 위치한 함수 호출하여 컴파일러 언어와 같은 특성을 보임
 
Dalvik Virtual Machine : 2.2 ver. JIT Compiler (Just In Time)
JVM에서 처리가 되는 translation들 중 호출 빈도가 높고 낮은 것 중 1000회 이상 반복 호출 되는 건(참조 빈도)
Hot code라고 정의 → Translate cache라는 별도의 위치에 변환된 네이티브 코드를 저장 (컴파일러 언어의 처리 방식과 같아지므로 성능 저하의 문제를 해결 가능)

---

12주차 (p.14~)
[ 스케줄링 알고리즘 : 우선순위 기반 스케줄링 ]

- 우선순위가 높은 프로세스를 먼저 실행
- 낮은 순위의 프로세스는 선점에 의해 강제 중단
- 낮은 순위 프로세스의 무한 대기 (기아 현상, Starvation)
 
[ 스케줄링 알고리즘 : 다양한 스케줄링 정책들 ]
비교 기준 1 : Selection Function

• w : 얼마만큼 시스템에 머물러 있는지 경과 시간
• e : 대기 시간 제외, 실제 소요 시간을 가리킴
• s (turn around time) : 프로세스가 시작해서 종료하기까지 걸린 총 서비스 시간
• max [w] : FCFS  = FIFO와 같은 유형 (가장 오래전 진입이란 건 머문 시간이 가장 오래된 프로세스를 의미) → 구현이 가장 단순함

비교 기준 2 : Decision Mode

선택 함수의 호출 시점은? (비선점 vs 선점)

• 비선점 (nonpreemptive)
  • 프로세스가 일단 실행 상태(Running state)에 진입하면 종료되거나 자발적으로 CPU를 놓을 때까지는 CPU를 빼앗기지 않는다. ( Running → Terminated (종료) )
  • 예시 : 협력형 멀티 태스킹 (시간 할당 받았으면 시간을 모두 소비하거나 중간에 I/O요청에 대해 스스로 CPU사용을 포기할 수 있음. yield() 함수로 구현 Running → Terminated (종료)
• 선점 (preemptive)
  • 현재 실행 중인 프로세스라 할지라도 운영체제에 의해 인터럽트가 걸려 비자발적으로 준비 큐로 이동될 수 있다.
  • (독점 방지) nonpreemptive 모드보다 문맥 교환 횟수가 많아지긴 하지만, 한 프로세스가 처리기 시간을 독점하는 것을 방지할 수 있어 효율적인 스케줄링이 가능함! Running → Blocked/Waiting (I/O 요청)  
  • 비협력형, 실시간성이 매우 중요

 
예를 통한 스케줄링 기법들의 동작 방식 비교

스케줄링 예

 
• First-Come-First-Served (First-Come-First-Served)

• 가장 먼저 도착한 프로세스를 가장 먼저 실행 (FIFO 큐 사용)
• w (대기 시간)가 가장 긴 프로세스, 즉 가장 오래 기다린 프로세스를 선택 (큐 하나로 단순 구현 가능)

3초가 되었을 때 2초에 B가 진입 → B 선택 (비선점 모드 : A의 수행이 완료될 때까지 수행이 이루어짐)
 

• Nonpreemptive 모드로 동작하기 때문에 FCFS는 짧은 프로세스보다는 긴 프로세스에게 유리
• 입출력 중심의 프로세스보다 처리기 중심 프로세스를 우대하는 경향이 나타남
• 비효율적이지만, 우선순위 기반에서 큐 조정 시 성능이 나아질 수 있다. (다른 정책과 융합하여 사용되고 있음)
• FCFS에서 짧은 프로세스가 피해 보는 현상 완화 방법
  • 짧은 프로세스가 피해 보는 현상 : 위의 예시에서 C는 4초에 진입, 9초에 시작 (5초 대기)
  • C프로세스를 시작 (게임을 비유 : 5초 동안 대기 후 인트로 화면이 나타남) : 응답시간이 증가

• 라운드-로빈(Round-Robin)

• 시간을 측정하고 있다가 어떤 긴 프로세스가 일정 시간 이상을 넘어가는 순간 실행을 강제로 중단시키는(preemption) 것
• 프로세스 실행 시간 측정 방법
  • 클럭 인터럽트 : 중간중간 OS가 계속 개입해야 하는 구조

타이머 인터럽트 발생 → 제어권 이양 (OS) → 현재 상태 저장 → 인터럽트 핸들러 호출 → 문맥 교환 (Context Switch)
 

 
select () 프로세스를 선택만 해주는 역할 / 빈번한 호출 시 문맥 교환이 자주 일어나 성능이 떨어짐
 
시간할당량의 크기(q)가 라운드 로빈 성능에 미치는 영향

• 시간할당량이 너무 작다면? → 응답성(Response Time) 향상, 문맥교환 오버헤드가 증가
• 시간할당량이 너무 크다면? → 처리량(Throughput) 향상, FCFS와 비슷해짐 (Round-Robin 장점이 사라짐)

 
시간할당량의 권장 길이

• 프로세스가 사용자와 최소한 한 번 이상 대화(Interaction 발생)하기에 충분하거나
• 프로세스 내의 어떤 한 함수 정도는 실행을 마칠 수 있는 충분한 길이

→ 명확한 기준을 마련하기 쉽지 않다.
 
• 라운드 로빈 방식 단점 : 입출력 중심 프로세스보다 처리기 중심 프로세스를 우대할 수밖에 없는 현상이 나타남! (응답성이 떨어짐)
준비 큐(Ready Queue)에 CPU 중심(CPU-bound)과 I/O 중심(I/O-bound) 프로세스가 섞여 있을 때 문제 발생
 

• CPU 중심: 할당된 시간 할당량(q)을 모두 소진하며 CPU를 독점적으로 사용.
• I/O 중심: 할당량의 극히 일부만 사용하고 I/O 요청을 위해 CPU를 반납.
• I/O 중심 프로세스가 다시 실행되려면, 앞선 CPU 중심 프로세스들이 q를 다 채울 때까지 장시간 대기해야 하는데 잠깐의 실행을 위해 긴 대기 시간을 감수해야 하므로 시스템의 응답성(Response Time)이 현저히 떨어진다.

 
 
• 해소 방법 : 가상 라운드 로빈(VRR) 스케줄링 방식

• 일반 레디큐, 입출력 레디큐를 구분하여 다른 큐에 머물도록 함 (준비큐보다 먼저 입출력 큐에서 대기 중인 프로세스가 우선적으로 선택될 수 있음 → 단점으로 지적한 이유는 큐가 섞여있을 때 자신의 순번이 올 때까지 오랜 시간 대기)

• 계산하던 중 시간할당량을 다 썼다면 그냥 준비 큐로 들어감.
• 입출력 요청으로 CPU를 반납했다면 입출력 대기 큐로 들어감. (응답성이 떨어짐)
• 스케줄러는 입출력 대기 큐에 있는 프로세스를 먼저 스케줄링함

 
[ 일반 RR의 문제점 : I/O 중심 프로세스의 불공정성 예시 ]
1. 가정 상황

• 시간 할당량 (q): 100ms
• 프로세스 A (I/O 중심): 1ms 실행 후 I/O 요청 (CPU 반납)
• 프로세스 B, C, D (CPU 중심): 100ms 꽉 채워서 사용

2. 실행 흐름 및 문제점

• A의 손해: 1ms만 쓰고 CPU를 반납하면서 남은 99ms의 권리 소멸
• 긴 대기: I/O를 마치고 돌아와도 준비 큐 맨 뒤로 이동
• 무한 대기: 앞선 B, C, D가 100ms씩 다 쓸 때까지 기다려야 함
  • 결과: A는 고작 1ms를 실행하기 위해 300ms (B+C+D)를 대기함
  • 응답성(Response Time) 급격히 저하 (I/O 중심 프로세스 차별 발생)

3. 해결책 : VRR (Virtual Round Robin) ]

• 보조 큐(Auxiliary Queue) 도입:
  • A처럼 할당량을 다 못 쓰고 나간 프로세스는 돌아올 때 보조 큐(입출력큐)로 이동
• 우선순위 부여:
  • 스케줄러는 일반 큐보다 보조 큐를 먼저 실행시켜 줌 (새치기 허용)
• 시간 보상:
  • A에게 아까 못 쓴 나머지 시간(99ms)만큼을 보장해 줌.

 
• Shortest-Process-Next(SPN) – 비선점 모드로 동작

• FCFS의 긴 프로세스 우대 편향성 완화 방법 2: 가장 짧은 프로세스를 먼저 실행시키는 정책
  • 종료 시까지 남아 있는 실행시간이 가장 짧은 프로세스를 다음번 프로세스로 선택
• 실행 시간이 짧은 프로세스가 (비록 늦게 도착했더라도) 긴 프로세스들보다 먼저 스케줄링될 수 있음! (E가 선택됨)
• 이때 긴 프로세스가 기아 상태에 빠질 수 있음

SPN 구현 상의 문제점

• 각 프로세스가 요구하는 총 실행 시간을 미리 알아야 한다는 점 (유추 힘듦 : 이론상만 가능한 알고리즘)
• 단순 평균, 지수적 평균(exponential averaging)으로 유추할 수 있는 방법이 존재

 
• Shortest-Remaining-Time (SRT)  – 선점 모드로 동작

• SPN의 중단(preemptive) 모드 버전에 해당
• 예상되는 남아있는 실행 시간이 가장 짧은 프로세스가 다음번프로세스로 선택됨
• SPN 같이 잔여시간 예측 불가 시 이상적 실현 불가

 
단점

• 매 스케줄링 때마다 프로세스들의 남아있는 실행 시간을 평가해야 하는 부담
• 긴 프로세스가 기아 상태에 빠질 가능성이 존재

 
• Highest-Response-Ratio-Next (HRRN)

• 가장 높은 응답 비율(R값)을 다음번 프로세스로 선택
• 대기 시간이 길다 → 수행시간이 길다.

• R = 응답 비율
• w = 처리기를 기다리며 대기한 시간
• s = 예상되는 서비스 시간
R = w +s / s
 

• 서비스 시간이 짧은 프로세스(s)의 R 값이 상대적으로 크기 때문에 짧은 프로세스를 우대
• 대기 시간 때문에 시스템에 오래 머문 긴 프로세스(w)도 오래 머물면 머물수록 R 값이 커지기 때문에 홀대받지는 않는다.

SPN / HRNN의 C, D, E 순서 비교해 보기
 
 
• 피드백 (Feedback) 스케줄링

• 큐가 여러 개, 프로세스 예상 서비스를 알아낼 필요가 없음 (SPN, SRT의 문제가 예상 시간을 평가할 수 없는 것)
• Feedback Queue, Multilevel Feedback Queue 알고리즘이 등장
• 중단점을 만날 때마다 프로 세스는 한 단계 낮은 우선순위의 준비 큐로 강등되어 진입 (우선순위는 뒤의 큐로 갈수록 낮아짐, 큐별로 할당된 타임 슬라이스의 크기가 다르다. 밑으로 갈수록 시간이 길어짐 : 지연을 덜 겪으면서 최대한 많은 연산 수행)
• 새로 도착한 프로세스일수록, 그리고 짧은 프로세스일수록 오래된 프로세스나 긴 프로세스보다 우대받는 정책 (CPU-bound로 간주)

 
변형한 피드백 (Feedback) 스케줄링 예시

• 변형(q=1): 모든 큐에서 고정된 시간 할당량이 있는 라운드 로빈 방식으로 스케줄링
  • 짧은 프로세스가 계속 진입하는 경우 긴 프로세스가 불이익을 받음
• 변형(q=2^i) : 시간 할당량의 크기를 큐 별로 다르게 함 (i가 q의 레벨을 가리킴)

 
[ 스케줄링 알고리즘 : 다양한 스케줄링 정책들 ] 

다양한 스케줄링 정책들의 특징

 
FCFS와 라운드 로빈(RR)의 성능을 수치로 비교

분석 결과 1

종료시각 : 수행이 언제 끝났는지
반환 시간(Ts) : turn aroun time/전체 서비스 시간
Tr/Ts : 대기 시간 + 수행 시간 
 
1. 평균 반환 시간(Tr) 비교

• 결과: FCFS(8.60) < RR q=4(10.00) < RR q=1(10.80)
• 이 예시 데이터에서는 FCFS가 가장 효율적
• 이유: 라운드 로빈(RR)은 모든 프로세스를 조금씩 번갈아 처리하므로, 프로세스가 완전히 끝나는 시간(종료 시간)은 오히려 뒤로 밀리는 경향이 있다. (반환 시간 측면에서는 FCFS가 유리할 때가 많음)

2. 시간 할당량(q)의 크기에 따른 차이

• q=1 (작을 때): 잘게 쪼개서 실행하다 보니 문맥 교환이 잦고, 프로세스들이 종료되지 못하고 시스템에 오래 머물러 평균 반환 시간이 가장 길다 (10.80)
• q=4 (클 때): q=1보다 FCFS에 가까워지며 성능이 개선됨 10.00)
  • 참고: 프로세스 A(서비스 시간 3)는 q=4 안에서 한 번에 끝나므로 FCFS와 똑같이 처리됨

3. 정규화된 반환 시간 (Tr / Ts)

• 의미: "실제 일한 시간 대비 얼마나 기다렸는가?" (1.0이면 대기 없음, 숫자가 클수록 대기 비율 높음)
• 해석: RR은 짧은 프로세스에게 응답성을 좋게 해 주지만, 수치상으로는 모든 프로세스가 질질 끌리는 현상 때문에 비율이 높게 나타남

 

분석 결과 2

SPN (Shortest Process Next)

• 특징: 비선점 모드. 실행 시간이 가장 짧은 프로세스를 먼저 선택.
• 성적 (평균 반환 시간 Tr): 7.60 (매우 우수)
• 분석: 짧은 프로세스(E)를 빨리 처리해 주므로 평균 대기 시간이 확 줄어듦. 단, 긴 프로세스는 뒤로 밀림.

SRT (Shortest Remaining Time)

• 특징: 선점 모드. SPN의 선점형 버전. (남은 시간이 더 짧은 놈이 들어오면 비켜줌)
• 성적 (평균 반환 시간 Tr): 7.20 (가장 빠름)
• 분석:
  • 8초에 도착한 초단기 프로세스 E(2초)가 실행 중이던 프로세스를 선점(Preempt)하고 즉시 실행되어 끝남.
  • 이 덕분에 E의 반환 시간이 획기적으로 줄어들어 전체 평균 점수가 가장 좋음.

HRRN (Highest Response Ratio Next)

• 특징: 비선점. (대기시간 + 서비스시간) / 서비스시간 공식을 사용.
• 성적 (평균 반환 시간 Tr): 8.00
• 분석: SPN의 단점(긴 프로세스의 무한 대기, 기아 현상)을 보완하기 위해 '오래 기다린 놈(Aging)' 점수를 쳐줌. SPN보다는 조금 느리지만 더 공정함.

FB (Feedback) - 피드백 큐

• 특징: 실행 시간을 모를 때 사용하는 현실적인 알고리즘. (시간 많이 쓰면 우선순위 강등)
• q=1 (고정): 평균 반환 시간 10.00
  • 짧게 쪼개서 실행하다 보니 문맥 교환이 많고, 긴 프로세스가 큐 아래로 밀려나며 오래 걸림.
• q=2^i (점진적 증가): 평균 반환 시간 10.60
  • 큐 레벨이 내려갈수록 할당 시간을 2배($1, 2, 4...$)로 늘려줌. 문맥 교환 오버헤드는 줄지만, 여전히 긴 프로세스는 푸대접받음.

---

리눅스 스케줄러

1. 등장 배경 (Linux Kernel 2.4 vs 2.6)

• Linux 2.4 이전 (O(n)):
  • 스케줄링할 때마다 모든 프로세스의 우선순위(Priority + Nice)를 일일이 재계산하고 비교함
  • 문제점: 프로세스 개수(n)가 늘어날수록 비교 연산 시간이 비례해서 늘어남 (느려짐)
• Linux 2.6 이후 (O(1) 도입):
  • 목표: 프로세스가 10개든 10,000개든 항상 일정한 시간(O(1)) 안에 다음 실행할 프로세스를 찾아내기
  • 계산을 줄이고 자료구조(비트맵, 포인터 교체)를 활용하는 방식으로 전환

 

2. O(1) 스케줄러의 핵심 원리
① 비트맵 (Bitmap)
64bit를 기준으로 설명

• 구조: unsigned long bitmap (64비트 정수 하나라고 가정)
• 원리 (0과 1의 마킹):
  • 각 비트(Bit) 위치가 곧 우선순위(Priority)를 의미
  • 우선순위 큐에 실행 가능한 프로세스가 있으면 1, 없으면 0으로 마킹
  • 장점: CPU는 find_first_bit 명령어로 가장 높은 우선순위(1인 비트)를 단번에 찾음 (루프 돌 필요 없음 → 상수 시간)

64bit 예시:

우선순위 3번에 프로세스가 도착함 → 3번째 비트를 1로 켬

• CPU는 전체를 뒤질 필요 없이 "1이 켜진 가장 첫 번째 비트"만 찾으면 됨

 
RTOS vs Linux (우선순위 중복 처리):

• RTOS (엄격함) : 우선순위 중복 불가 (비트가 1이면 프로세스 딱 1개)
• Linux (유연함) : 우선순위 중복 허용
  • 비트맵의 역할: "이 우선순위(예: 10번)에 손님이 있다/없다"만 알려줌 (깃발 역할).
  • 실제 프로세스: 해당 우선순위 큐(Linked List)에 줄을 서 있음. (같은 10번 프로세스가 3개라면 큐에 3개가 매달려 있고, 비트맵은 1로 표시됨)

 
② 두 개의 배열 : Active Array & Expired Array
타임슬라이스(시간 할당량) 관리의 효율성을 위해 두 개의 배열을 사용. 타임슬라이스 재할당 계산(Overhead)을 없애기 위한 구조

1. Active Array (활동 큐): 타임슬라이스가 남아있는 프로세스들이 대기
2. Expired Array (만료 큐): 타임슬라이스를 모두 소진한 프로세스들이 이동
   • 소진했다는 건 종료됐다는 뜻이 아니라, 이번 턴에 쓸 시간을 다 썼다는 뜻
3. 교체
   • Active 큐가 텅 비면? → Active와 Expired의 포인터만 서로 맞바꿈
   • 기존 Expired가 새로운 Active가 되며 즉시 다시 스케줄링 시작
   • 의미: 일일이 타임슬라이스를 다시 채워주는 계산 과정(Overhead)을 없앰

 

3. 우선순위와 정책 (Priority Policies) 
우선순위 범위(0~139)에 따라 적용되는 정책이 다름

구분	우선순위	적용 정책	특징
Real-Time (실시간)	0 ~ 99	SCHED_FIFO	선입선출. 한 번 잡으면 끝날 때까지 (혹은 봉쇄될 때까지) 놓지 않음
		SCHED_RR	같은 우선순위끼리는 라운드 로빈(Time Slice) 적용
Normal	100 ~ 139	SCHED_NORMAL	일반 사용자 프로세스. Nice 값에 따라 타임슬라이스 차등 할당

참고: 실시간 프로세스(0~99)는 타임슬라이스가 사실상 '무제한'에 가까우며, 커널 스레드나 데몬 등이 주로 사용
 
4. 사용자 우선순위와 타임슬라이스 계산
실제 리눅스 구조 (140단계)
64비트 변수 하나로는 140개를 다 표현 못 하므로, 실제로는 배열을 사용
 
일반 프로세스(100~139)는 사용자가 설정한 Nice 값으로 기본 타임슬라이스가 결정됨
① Nice 값 범위: -20 (최고 우선순위) ~ +19 (최저 우선순위)

• 기본값 (Nice 0): 100ms
• Nice -20 (최고 우선순위): 800ms (우선순위 100)
  • 특징: 0을 기준으로 위로는 50ms 단위로  증가.
• Nice +19 (최저 우선순위): 5ms (우선순위 139)
  • 특징: 0을 기준으로 아래로는 5ms 단위로 감소 (최소 실행 보장).

② Fork (자식 생성) 시

• 자식 프로세스는 부모가 가지고 있던 남은 타임슬라이스의 절반을 상속받음. (무한 생성으로 인한 독점 방지)

Nice 값

우선순위

타임슬라이스 (Time Slice)

비고

 
5. I/O vs CPU Bound 튜닝 (동적 우선순위) 
스케줄러는 프로세스의 성향에 따라 우선순위를 동적으로 조정

• I/O Bound (입출력 중심):
  • 잠깐 쓰고 대기(Sleep)하는 빈도가 높음
  • 우선순위 높임 (Bonus) → 응답성(Response Time) 향상
  • 어차피 CPU 길게 줘도 못 씀. 빨리 반응해 주는 게 사용자 경험에 좋음
• CPU Bound (연산 중심):
  • CPU를 독점적으로 길게 사용
  • 우선순위 낮춤 (Penalty) → 대신 타임슬라이스를 길게 줌(Throughput 향상 : 800ms)
  • 문맥 교환 오버헤드를 줄여 전체 처리량을 늘리기 위함

 
6. 스케줄러의 진화와 멀티코어 
 
① O(1) 스케줄러의 한계

• 대화형(Interactive) 프로세스를 판별하는 로직이 복잡함
• 완벽한 공정성(Fairness)을 보장하기 어려워, 특정 상황에서 기아(Starvation) 발생 가능성 존재

② CFS (Completely Fair Scheduler) - Linux 2.6.23~

• 핵심 자료구조: 레드-블랙 트리 (Red-Black Tree)
• 원리:
  • vruntime(가상 실행 시간)을 기록
  • vruntime이 가장 작은 프로세스를 트리의 가장 왼쪽(Left)에 배치하고 우선 실행
• Aging: 실행 못 하고 기다리는 프로세스는 트리의 우선순위를 강제로 높여 (왼쪽으로 이동) 기아 현상 방지

 
7. 멀티코어 / 멀티프로세서 환경

• 개별 런큐 (Per-CPU Runqueue):
  • 은행 창구처럼 CPU(코어)마다 각자의 줄(Queue)을 가짐
• 로드 밸런싱 (Load Balancing):
  • Migration: 한쪽 CPU만 바쁘고 다른 쪽이 놀고 있으면, 작업을 이주(Migration) 시킴
  • 비유: 1번 창구에 10명, 2번 창구에 0명이면 1번 줄 손님을 2번으로 보냄
  • 단, 캐시 친화도(Cache Affinity) 때문에 너무 자주 옮기는 것은 좋지 않음