[OSTEP] 스터디 3주차 - 스케줄링 1

이번 주차에는 다양한 스케줄링 정책(Scheduling Policy)을 이해하는데 집중한다. 이러한 정책은 스케줄링 기법(Scheduling Discipline)이라고 불린다. 초기의 스케줄링 방법들은 생산 관리 분야에서 개발되었고, 이후 컴퓨터 시스템에 적용되었다.

우리가 이번에 배울 스케줄링에 대한 핵심 질문은 다음과 같다.

1. 스케줄링 정책은 어떻게 개발할 수 있을까?
2. 스케줄링 정책을 설계하기 위한 기본적인 프레임워크는 무엇일까?
3. 정책 개발에 필요한 핵심 가정은 무엇일까?
4. 어떤 평가 기준이 중요할까?
5. 컴퓨터 시스템 초창기에 사용된 기본 접근 방식은 무엇일까?

---

워크로드에 대한 가정

스케줄링 정책을 알아보기 전에 몇 가지 가정을 하겠다. 이 가정을 통해 시스템에서 실행되는 프로세스들의 집합인 워크로드(Workload)를 정의하는데 도움이 될 것이다.

1. 모든 작업의 실행 시간은 동일하다. - 예를 들어, 모든 작업이 정확히 10초 동안 실행됨.
2. 모든 작업은 동시에 시스템에 도착한다. - 즉, 모든 작업이 시작 시점에 한꺼번에 도착한다.
3. 각 작업은 한 번 시작되면 중간에 중단되지 않고 완료될 때까지 실행됨. - 작업이 실행되는 동안 다른 작업으로 전환되지 않음.
4. 모든 작업은 오직 CPU 자원만 사용한다. - 작업 실행 중에는 입출력(I/O) 작업이 발생하지 않는다고 가정.
5. 각 작업의 실행 시간은 스케줄러가 미리 알고 있다. - 스케줄러는 작업의 실행 시간을 사전에 파악하고 있다고 가정.

물론 작업의 실행 시간을 미리 알고 있다는 가정은 비현실적이다. 이러한 가정은 스케줄링 정책을 단순화하여 이해하기 쉽게 하기 위함이다. 실제 시스템에서는 현실적인 제약 사항들을 고려해야 한다.

---

스케줄링 평가 항목

스케줄링 알고리즘을 평가하기 위해 워크로드에 대한 가정외에도 평가 기준을 정해야 한다. 다양한 평가 기준이 사용되지만 일단 반환 시간(Turnaround Time)이라는 하나의 척도만 살펴보겠다.

$$T_{turnaround} = T_{completion} - T_{arrival}$$

여기서 $T_{turnaround}$ 은 반환 시간, $T_{completion}$은 작업 완료 시각, $T_{arrival}$은 작업 도착 시간이다.

지금은 모든 작업이 동시에 도착한다고 가정하기 때문에 $T_{arrival} = 0$이라 할 수 있다. 따라서 반환 시간은 곧 작업 완료 시각과 같아진다.

반환 시간은 시스템의 성능 측면에서 본 척도라는 점에 주목해야 한다. 또 중요한 기준으로 공정성(fairness)이 있는데 이는 Jain's Fairness Index 와 같은 지표로 측정 가능하다.

스케줄링에서 성능과 공정성은 종종 상충되는 목표가 된다. 예를 들어 스케줄러가 시스템 성능을 극대화 하기 위해 일부 작업을 오랫동안 미루게 되면, 그만큼 공정성은 나빠지게 된다.

---

선입선출(FCFS)

선입선출(First-Come, First-Served)은 가장 간단한 스케줄링 알고리즘 중 하나다. 이 알고리즘은 작업이 도착한 순서대로 실행되는 방식으로, 먼저 도착한 작업이 먼저 실행되고, 그 다음으로 도착한 작업이 실행된다.

선입선출 스케줄링은 비선점형 스케줄링이므로 프로세스가 자발적으로 CPU를 반납할 때 까지 CPU를 빼앗지 않는다.

예를 들어, 프로세스 A,B,C가 각각 3, 5, 2초의 서비스 시간을 가지고 있고, A, B, C 순으로 도착하면 다음과 같은 프로세스를 실행한다.

프로세스	서비스 시간	대기 시간	응답 시간	반환 시간
A	3초	0초	0초	3초
B	5초	3초	3초	8초
C	2초	8초	8초	10초

이렇게 되면 평균 대기 시간은 (0 + 3 + 8) / 3 = 3.67초, 평균 응답 시간은 (0 + 3 + 8) / 3 = 3.67초, 평균 반환 시간은 (3 + 8 + 10) / 3 = 7초가 된다.

장점

• 구현이 쉽다.
• 선착순으로 처리하기 때문에 프로세스를 공평하게 처리할 수 있다.

단점

• 짧은 작업이 긴 작업보다 늦게 도착하면 긴 작업을 기다려야 하므로 평균 대기 시간이 증가할 수 있다. 이를 호위 효과(convoy effect)라고 한다.
• FCFS 스케줄링은 비선점형(nonpreemptive) 방식이므로 한 프로세스가 CPU를 점유하고 있으면 다른 프로세스는 CPU를 빼앗을 수 없다. 이는 CPU 사용률을 낮추고 I/O 바운드 프로세스의 대기 시간을 증가시킬 수 있다.

---

최단 작업 우선(SJF)

최단 작업 우선(Shortest Job First)는 실행 시간이 가장 짧은 작업을 가장 먼저 처리하는 방식이다.

이미지와 같은 예를 SJF로 스케줄 해보면 SJF의 평균 반환 시간은 50초이다. $ \frac{(10 + 20 + 30)}{3} = 50$ SJF는 장점이 많은 스케쥴링 기법이지만, 여전히 비현실적인 가정을 하고 있다. 만약 가정 2를 바꿔 모든 작업은 동시에 도착하는 것이 아니라 랜덤 하게 도착한다고 하면 어떻게 될까? 만약 A 작업이 t = 0에 도착하고 이후에 B, C 작업이 t = 10에 도착한다고 하면

결국 평균 반환 시간은 $\frac{100 + (110 - 10) + (120 - 10)}{3} = 103.33$이 된다.

---

최소 잔여시간 우선(STCF)

위와 같은 문제를 해결하기 위해 최소 잔여시간 우선(Shortest Time-to completion First) 스케줄링 기법을 적용해 보겠다. 이 기법은 SJF를 조금 변형한 것으로 작업의 총 실행 시간이 아니라 남아있는 실행시간, 즉 잔여 실행 시간을 기준으로 삼는다.

위와 같은 예에서 A의 경우 120초 라는 실행시간을 가지는데 A가 t=0에서 B, C가 t=10에 도착할 때 A를 실행하고 있다가 B, C가 도착하는 순간 잔여 실행 시간을 비교해 더 빨리 끝이 나는 B, C를 실행하도록 하는 것이다. 이후 B, C 작업이 끝이 나면 A작업을 다시 진행한다.

이 결과 평균 반환 시간이 단축되어 50초가 $\frac{(120 - 0) + (20 - 10) + (30-10)}{3}$ 된다. 모든 작업이 동시에 도착하는 특별한 경우에는 SJF 가 최적의 스케줄을 보장한다면 이렇게 작업이 서로 다른 시간에 도착하는 일반적인 상황에서는 STCF가 최적이 될 것이라는 것을 이해할 수 있다. STCF는 작업이 도착할 때마다 잔여 작업량을 재평가하여 가장 적절한 프로세스를 선택하기 때문이다.

---

새로운 평가 기준 : 응답 시간

STCF는 작업의 실행 시간을 미리 알고, CPU만을 사용하며, 반환 시간이라는 단일 평가 기준을 가정할 때는 매우 효과적인 스케줄링 정책이다. 초기의 일괄 처리(Batch Processing)시스템에서는 이런 알고리즘이 적절했으나 시분할(Time-Sharing) 시스템의 등장으로 상황이 달라졌다.

사용자들은 터미널을 통해 컴퓨터와 상호작용을 하게 되었고 이에 따라 시스템의 응답성(responsiveness)이 중요한 성능 지표로 부상했다. 이를 반영하기 위해 응답 시간(response time)이라는 새로운 평가 기준이 도입되었는데, 이는 작업이 도착한 시점부터 실제로 처음 실행되기 시작할 때까지 걸린 시간을 말한다.

예를 들어 세 개의 작업 A, B, C가 동시에 도착했다고 한다. STCF 스케줄링을 적용하면 실행 시간이 가장 긴 작업, 가령 C는 나머지 두 작업이 모두 끝날 때까지 기다려야 비로소 CPU를 할당받을 수 있다. 반환 시간 측면에서는 최적일 수 있지만, 응답 시간 측면에서 보면 형편없는 결과라 할 수 있다.

사용자와의 상호작용이 중요해진 상황에서 STCF는 더 이상 적절한 스케줄링 기법이 아니다. 응답 시간을 개선하면서도 시스템의 전반적인 성능을 높일 수 있는 새로운 스케줄링 알고리즘이 필요해진 것이다.

---

라운드 로빈(RR)

응답 시간 문제를 해결하기 위해 라운드 로빈(Round Robin) 스케줄링이라는 새로운 알고리즘이 도입되었다. RR에서는 각 작업이 완료될 때까지 기다리지 않고, 대신 정해진 시간 동안만 실행한 수 다음 작업으로 전환한다. 이때 각 작업에 할당되는 실행 시간을 타임 슬라이스(time slice) 또는 스케줄링 퀀텀(scheduling quantum)이라고 부른다. 이 과정은 모든 작업이 끝날 때까지 계속 반복되는데 이런 특성 때문에 RR을 타임 슬라이싱(time slicing)이라고도 한다.

타임 슬라이스의 길이는 타이머 인터럽트 주기의 배수로 설정해야 한다. 예를 들어 타이머 인터럽트가 10밀리초마다 발생한다면, 타임 슬라이스는 10, 20, 30 등 10의 배수로 정해질 수 있다.

RR스케줄링에서 타임 슬라이스의 길이는 매우 중요하다. 일반적으로 타임 슬라이스가 짧을 수록 응답 시간 측면에서의 성능은 좋아진다. 그러나 너무 짧게 설정하면 문맥 교환 오버헤드가 전체 성능에 부정적인 영향을 미칠 수 있다.

따라서 시스템 설계자는 문맥 교환에 드는 비용과 응답 시간 개선 효과를 고려하여 최적의 타임 슬라이스 길이를 결정해야 한다. 이는 해당 시스템의 특성과 워크로드에 따라 달라질 수 있는 중요한 튜닝 포인트 중 하나다.

---

입출력 연산의 고려

지금까지는 CPU 작업만 고려했지만, 실제 시스템에서는 입출력(I/O) 작업도 빈번하게 발생한다. 이는 스케줄링에 또 다른 도전 과제를 제기한다.

어떤 프로세스가 I/O 작업을 요청하면, 그 프로세스는 I/O가 완료될 때까지 CPU를 사용하지 않는다. 대신 I/O 작업이 끝나기를 기다리면서 대기(blocked) 상태로 전환된다. 특히 하드 디스크 드라이브 같은 장치에 I/O 요청을 보냈다면, 현재의 I/O 부하에 따라 몇 초 또는 그 이상 블록 상태로 남아있게 된다.

이때 스케줄러의 역할은 블록된 프로세스 대신 실행할 다른 프로세스를 선택하는 것이다. 이를 통해 CPU가 쉬지 않고 일할 수 있도록 해야 한다.

반대로, I/O 작업이 완료되면 스케줄러는 또 다른 결정을 내려야 한다. I/O 완료는 인터럽트를 발생시키고, 이를 처리하기 위해 운영체제가 실행된다. 운영체제는 I/O를 요청했던 프로세스를 대기 상태에서 준비(ready) 상태로 전환시킨다. 여기서 스케줄러는 해당 프로세스를 바로 실행할 것인지, 아니면 다른 프로세스에게 CPU를 할당할 것인지 결정한다.

이렇듯 I/O 작업은 스케줄링 문제를 더욱 복잡하게 만든다. 스케줄러는 CPU 사용 패턴뿐만 아니라 I/O 특성까지 고려하여 적절한 프로세스를 선택해야 한다. 이를 통해 전체 시스템의 CPU 활용도와 응답성을 높이는 것이 목표다.

---

만병통치약은 없다.(No More Oracle)

이제 입출력을 고려한 기본적인 스케줄링 접근 방식에 대해 살펴보았으니, 마지막으로 남은 가정에 대해 생각해 보겠다. 바로 스케줄러가 각 작업의 실행 시간을 미리 알고 있다는 가정인데, 앞서 언급했듯이 이는 아마도 우리가 할 수 있는 가정 중 가장 비현실적인 것이다.

사실 범용 운영체제에서는 개별 작업의 실행 시간을 정확히 예측하는 것이 거의 불가능하다. 프로세스의 행동은 입력 데이터, 사용자 상호작용, 외부 이벤트 등 다양한 요인에 따라 달라지기 때문이다.

그렇다면 작업의 실행 시간에 대한 사전 지식 없이도 SJF나 STCF처럼 동작하는 스케줄링 알고리즘을 만들 수 있을까? 나아가 이런 알고리즘에 라운드 로빈에서 봤던 것처럼 응답 시간을 개선하는 아이디어도 접목시킬 수 있을까?

안타깝게도 이 모든 조건을 완벽히 만족시키는 만병통치약 같은 솔루션은 존재하지 않다. 스케줄러가 완벽한 정보를 가질 수 없는 상황에서는 어떤 알고리즘을 사용하더라도 트레이드오프가 발생할 수밖에 없다.

하지만 현대의 스케줄러들은 과거의 실행 이력, 휴리스틱, 피드백 등을 활용하여 이 문제에 대한 나름의 해법을 모색하고 있다. 비록 최적해는 아닐지라도, 주어진 환경에서 최선의 성능을 끌어내기 위해 노력하고 있는 것이다.

---

3주 차 숙제

Q1. SJF와 FIFO 스케줄러로 길이가 200인 세 개의 작업을 실행할 때의 응답 시간과 반환 시간을 계산하시오.

FIFO

작업	시작 시간	종료 시간	응답 시간	반환 시간
A	0	200	0	200
B	200	400	200	400
C	400	600	400	600

 

SJF

작업	시작 시간	종료 시간	응답 시간	반환 시간
A	0	200	0	200
B	200	400	200	400
C	400	600	400	600

Q2. 이제 작업의 길이를 다르게 하여 동일한 작업을 수행해 보시오: 100, 200, 300.

FIFO

작업	시작 시간	종료 시간	응답 시간	반환 시간
A	0	100	0	100
B	100	300	100	300
C	300	600	300	600

SJF

작업	시작 시간	종료 시간	응답 시간	반환 시간
A	0	100	0	100
B	100	300	100	300
C	300	600	300	600

Q3. 이제 RR 스케줄러와 시간 할당량(time-slice)을 1로 하여 동일한 작업을 수행해 보시오.

작업은 순서대로 A → B → C → A → B → C... 형태로 반복 수행된다.

• A는 100번
• B는 200번
• C는 300번
• 전체 수행 시간은: 600

Q4. 어떤 유형의 워크로드에 대해 SJF가 FIFO와 동일한 반환 시간을 제공하는가?

A : 모든 작업의 실행 시간이 동일할 때, 모든 작업의 실행 시간이 다르더라도 도착 순서가 실행 시간 순서와 같을 때

Q5. 어떤 유형의 워크로드와 시간 할당량에 대해 SJF가 RR과 동일한 응답 시간을 제공하는가?

A : 작업 개수가 1개인 경우, 모든 작업의 실행 시간이 동일 + 동시에 도착, 짧은 작업이 먼저 도착

Q6. 작업 길이가 증가함에 따라 SJF에서 응답 시간은 어떻게 되는가? 시뮬레이터를 사용하여 이 추세를 보여줄 수 있는가?

https://cpu-scheduling-sim.netlify.app/?utm_source=chatgpt.com

응답 시간이 비선형적으로 증가한다. 왜냐하면 긴 작업은 짧은 작업들이 모두 끝난 뒤에야 시작되기 때문

Q7. 시간 할당량이 증가함에 따라 RR에서 응답 시간은 어떻게 되는가? N개의 작업이 주어졌을 때 최악의 응답 시간을 제공하는 수식을 작성할 수 있는가?

A : 시간 할당량 Q가 커질수록, RR의 최악 응답 시간은 선형적으로 증가 RR에서 각 작업은 한 번씩 순서대로 CPU를 받기 때문에,
마지막 작업의 응답 시간이 가장 늦고, 그것이 최악의 응답 시간.

$$(N - 1) × Q$$ 

N = 작업 수 Q = 시간 할당량

예시) N = 5, Q = 20
→ 최악 응답 시간 = (5 - 1) × 20 = 80

Q (time-slice)	최악 응답 시간 (N=5)
1	4
10	40
20	80
50	200
100	400