운영체제(OS)-WEEK3(1) 스케줄링(Scheduling)

 **'CPU Scheduling'**

이 파트는 앞서 배운 CPU 가상화를 실현하기 위해 OS가 어떤 '정책(Policy)'을 가지고 프로세스들을 줄 세우는지 다룬다.

---

## 1부: 스케줄링의 기초와 지표 (2~6페이지)

• 2페이지: CPU 스케줄링의 정의

핵심: 실행 가능한 프로세스들 중 다음에 무엇을 실행할지 결정하는 정책입니다.

관점: 스케줄링은 매우 빈번하게 일어나므로 매우 빨라야 합니다.

'CPU와 I/O 장치 모두 놀지 않게 만드는 것'

 

CPU는 계산의 천재지만 데이터를 가져오거나 내보내는 일은 직접 못하고 다른 "주변 장치(I/O Devices)"에게 시킨다.

 

I/O 장치 종류: 디스크(파일 읽기/쓰기), 키보드(입력 대기), 네트워크 카드(데이터 패킷 수신), 모니터 등

 

BLOCKED 상태, 기다림의 실체: CPU 속도는 빛의 속도라면 디스크가 돌아가서 데이터를 찾는 속도는 거북이 걸음이다... CPU가 파일 읽어오라고 명령 후 디스크가 답을 줄 때까지 수백만 번의 CPU 사이클이 낭비될 수 있음. 이 때 프로세스가 CPU를 잡고 멍하니 기다리면 시스템 전체가 느려진다. 그래서 OS는 이 프로세스를 Blocked 상태 (잠시 휴면)로 빼버리고, 그동안 일을 할 수 있는 다른 프로세스(Ready 상태)에게 CPU 를 넘겨준다.

 

I/O 완료: 데이터가 다 준비되면 하드웨어가 '인터럽트(interrupt)'라는 벨을 울려 OS에게 알리고, OS는 해당 프로세스를 다시 Ready 상태로 깨워준다.

 

상단: CPU만 신경 씀. 하단: I/O 장치까지 고려

I/O 대기 시간까지 고려해서 프로세스 A가 DISK(I/O)를 쓰는 동안 프로세스 B가 CPU를 쓰게 하면, 전체 작업 시간이 획기적으로 줄어드는 것을 볼 수 있다! (중첩! Overlap~)

 

 

• 3페이지: 스케줄링의 두 가지 방식
  
  • 비선점형(Non-preemptive): 프로세스가 스스로 CPU를 양보할 때까지 기다립니다.
  • 선점형(Preemptive): 현대 OS의 방식으로, 스케줄러가 실행 중인 프로세스를 강제로 멈추고 다른 프로세스로 교체할 수 있습니다.

 

 

• 4~6페이지: 평가 지표 (Metrics)
  
  • 반환 시간(Turnaround Time): 작업 완료 시간에서 도착 시간을 뺀 전체 시간(T_{completion} - T_{arrival})입니다
  • 응답 시간(Response Time): 작업이 도착해서 처음으로 실행될 때까지 걸린 시간입니다.
  • 공정성(Fairness): 모든 프로세스에 CPU를 골고루 나눠주는 정도를 말하며, 성능과 공정성은 대개 충돌(Trade-off) 관계에 있습니다.

 

스케줄러의 5개 가정

 

이 가정들을 하나씩 제거하면서 스케줄링이 어떻게 변화하는지 보자!

ex) 1번 가정 제거 (실행 시간 제각각?) -> FIFO보다는 SJF가 유리해짐

2번 가정 제거 (도착 시간 제각각?) -> 비선점형보다는 STCF 같은 선점형이 필요해짐.

4번 가정 제거 (I/O도 고려하면?) -> CPU와 I/O 중첩시키는 전략 필요해짐.

 

+ '도착'의 구체적인 의미

 

스케줄링 알고리즘에서 말하는 **도착(Arrival)**은 프로세스가 Ready 상태가 되어 Ready 큐(Ready Queue)에 들어가는 순간을 의미한다.

1. PCB 생성 및 등록: OS가 해당 프로세스의 관리 장부인 **PCB(Process Control Block)**를 생성합니다.
   
    
2. 정보 수신: OS가 이 프로세스의 PID, 우선순위, 초기 상태 정보 등을 PCB에 기록하고 파악합니다.
3. Ready 큐 진입: OS가 "이제 이 프로세스는 언제든 CPU를 쓸 준비가 되었다"고 판단하여 Ready 큐라는 줄 서기 목록에 프로세스의 PCB를 연결(Link)합니다

 

---

 

## 2부: 기초 스케줄링 알고리즘 (7~14페이지)

 

• 7~9페이지: FIFO (First In, First Out)
  • 먼저 온 순서대로 처리하는 비선점형 방식입니다.
  • 문제점 (Convoy Effect): 실행 시간이 긴 작업이 앞에 오면 뒤에 있는 짧은 작업들이 오래 기다려야 하는 현상이 발생합니다.

FIFO의 단점: 1번 가정(실행 시간 동일) 제거하면 다음 프로세스 실행까지 오래걸림

 

 

• 10~11페이지: SJF (Shortest Job First)
  • 실행 시간이 가장 짧은 작업을 먼저 실행합니다.
  • 한계: 작업 도중에 더 짧은 작업이 들어와도 기존 작업을 끝내야 하는 비선점형의 한계가 있습니다.

+가정 2번도(도착 시간 동일)제거: A 실행도중 더 짧은 프로세스들이 와도 하던 작업 끝까지 해야함..!

 

 

 

• 12~13페이지: STCF (Shortest Time-to-Completion First)
  • SJF에 **선점(Preemption)**을 추가한 방식입니다. 
  • 새 작업이 들어왔을 때 남은 시간이 가장 짧은 작업을 선택해 실행하므로 반환 시간(turnaround time) 최적화에 유리합니다.

 

3번 가정(실행 중이던 작업은 끝까지!) 제거: 짧은 작업 생기면 그것부터 먼저!

 

 

• 14페이지: 응답 시간의 중요성
  • STCF는 전체적인 반환 시간은 좋지만, 대화형(Interactive) 작업의 초기 응답 시간은 보장하기 어렵다는 단점이 있습니다.

 

---

## 3부: 현대적 스케줄링 - Round Robin & I/O (15~20페이지)

 

• 15~17페이지: Round Robin (RR)
  • 타임 슬라이스(Time Slice) 단위로 프로세스를 번갈아 실행합니다. = 스케줄링 퀀텀 이라고도 함.
  • 응답 시간은 매우 좋고 공정하지만, 문맥 교환 오버헤드가 발생하며 반환 시간은 나쁠 수 있습니다.
  • Trade-off: 타임 슬라이스가 너무 짧으면 오버헤드가 크고, 너무 길면 응답 시간이 나빠집니다.

 

오버헤드(Overhead)는 어떤 처리(작업)를 수행하는 데 드는 간접적인 처리 시간, 메모리, 네트워크 자원 등 부가적인 비용을 의미합니다. 주된 목적 외에 시스템 안정성이나 기능 구현을 위해 추가로 발생하는 자원 낭비 요인이므로, 일반적으로 오버헤드가 작을수록 시스템 효율이 좋습니다. 

 

 

 

 

time slice 도입 후 response time은 좋아졌으나 turnaround time이 오히려 나빠짐(끝나는 시간이 길어짐)..

 

trade off 관계...!

짧은 time slice = 응답 시간 개선, 문맥 교환 비용 증가

긴 time slice = 응답 시간 악화, 문맥 교환 비용 개선

 

• 18~20페이지: I/O의 통합 (4번 가정(cpu만 고려) 제거)
  • 실제 프로세스는 CPU만 쓰는 게 아니라 I/O 작업을 병행합니다.
  • 프로세스가 I/O를 요청해 Blocked 되면, OS는 CPU를 놀리지 않고 즉시 다른 프로세스에 할당하여 자원 활용률을 높여야 합니다.

---

## 4부: 완성형 모델 - MLFQ (21~34페이지)

• 21~25페이지: MLFQ (Multi-Level Feedback Queue)의 규칙

목표: 반환 시간 최적화 + 응답 시간 최소화 + 정보가 없는 상태(5번 가정(실행시간 알고있음)제거) 에서 학습.

• Rule 3: 시스템에 작업 들어왔을 때, 높은 우선순위를 부여한다.
• 원래 규칙 (Rule 4a): 프로세스가 자신에게 주어진 시간(Time Slice)을 끝까지 다 써버리면, OS는 이 녀석을 "CPU를 많이 쓰는 무거운 작업"으로 판단하여 우선순위를 한 단계 낮춥니다.
• Rule 4b (The Exception): 만약 프로세스가 할당된 시간을 다 쓰기 전에 **스스로 CPU를 양보(Yield)**하면(보통 I/O를 하기 위해), OS는 이 프로세스의 우선순위를 그대로 유지시켜 줍니다.

• 기본 규칙: 우선순위가 높은 큐의 작업을 먼저 실행하고, 같은 우선순위면 RR을 수행합니다.
• 새 작업은 일단 최고 우선순위로 시작하여(Rule 3), CPU를 다 쓰면 우선순위를 낮추고(Rule 4a)(강등!!), I/O를 자주 하면 높은 순위를 유지합니다(Rule 4b).

싱글 프로세스>>>

 

 

프로세스 두 개일 때! >>>

 

 

악질적 사용의 예시>>  우선순위에서 안내려옴..

 

 

• 26~29페이지: MLFQ의 문제점
  
  • 기아 현상(Starvation): 짧은 작업이 계속 오면 긴 작업이 CPU를 아예 못 받을 수 있습니다.
  • 스케줄러 속이기(Gaming): 타임 슬라이스 직전에 I/O를 일으켜 높은 우선순위를 유지하는 얌체 작업이 생길 수 있습니다. (EX: 10초 슬라이스에 9초만 쓰고 I/O 일으켜서 우선순위 계속 유지하는 악질 작업?)

 

 

• 30~31페이지: 악질 작업 문제 해결!! (Priority Boost & Accounting)
• • Priority Boost: 일정 시간(S)마다 모든 작업을 최고 큐로 올려 기아 현상을 해결합니다.
  • Accounting: 프로세스가 해당 큐에서 사용한 전체 시간을 측정하여, I/O를 섞어 써도 총량이 다 차면 우선순위를 낮춥니다.(악질 예방으로 시간 얼마나 썼는지 기록한다!)

 

• 32~34페이지: 튜닝 및 요약
  • 상위 큐는 짧은 타임 슬라이스(응답성), 하위 큐는 긴 타임 슬라이스(효율성)를 부여하여 튜닝합니다.
  • 최종적으로 5가지 규칙을 통해 현대적인 스케줄링 시스템이 완성됩니다.

 

MLFQ 요약:

 

RULE 1: 우선순위 높은 것 우선 수행

RULE 2: 우선 순위 동등하면 ROUND ROBIN!

RULE 3: 작업이 새로 들어오면 가장 높은 우선순위 배치

RULE 4: 주어진 할당 시간을 소진한 작업은 우선 순위 밀려남

RULE 5: S(일정 시간) 후에 시스템의 작업들을 최상단 큐로 올린다.