[OSTEP] 07. 스케줄링: 개요(Scheduling: Introduction)

2.1 반환 시간 (Turnaround Time)#

• 작업이 시스템에 도착해서 끝날 때까지 걸린 시간입니다.
• 성능(Performance) 위주의 지표입니다.
• $T_{turnaround} = T_{completion} - T_{arrival}$

2.2 응답 시간 (Response Time)#

• 작업이 도착해서 처음으로 스케줄 될 때까지 걸린 시간입니다.
• 대화형 시스템(터미널, UI)에서의 반응성(Interactivity) 지표입니다.
• $T_{response} = T_{firstrun} - T_{arrival}$

3.1 FIFO (First In, First Out)#

가장 단순한 선착순 방식입니다.

• 장점: 단순하고 구현이 쉽습니다.
• 문제점: Convoy Effect (호위 효과)
  • 만약 100초 걸리는 작업 A가 먼저 오고, 10초 걸리는 B, C가 바로 뒤에 왔다면?
  • B와 C는 A가 끝날 때까지 하염없이 기다려야 합니다. 평균 반환 시간이 급격히 나빠집니다.
  • 마치 마트 계산대에서 카트 가득 채운 사람 뒤에, 우유 하나 든 사람이 서 있는 꼴입니다.

3.2 SJF (Shortest Job First)#

“가장 짧은 작업을 먼저 실행하자”는 아이디어입니다. (가정 1 완화: 실행 시간이 다름)

• 해결: A(100초), B(10초), C(10초)가 동시에 도착하면, SJF는 B -> C -> A 순서로 실행합니다. Convoy Effect를 해결하고 평균 반환 시간을 최적화합니다.
• 문제점: 늦은 도착 (Late Arrival)
  • A(100초)가 $t=0$에 도착해서 이미 실행 중인데, $t=10$에 B(10초)가 도착한다면?
  • SJF는 비선점(Non-preemptive) 방식이므로 A가 끝날 때까지 B는 기다려야 합니다. 다시 Convoy Effect가 발생합니다.

3.3 STCF (Shortest Time-to-Completion First)#

SJF에 선점(Preemption) 기능을 추가합니다. (가정 3 완화: 중간에 멈출 수 있음) 새로운 작업이 도착하면, “현재 실행 중인 작업의 남은 시간”과 “새 작업의 시간”을 비교해서 더 짧은 것을 선택합니다.

• 해결: A가 실행 중이어도 B가 도착하면, B가 더 짧으므로 A를 잠시 멈추고(Context Switch) B를 먼저 실행합니다.
• 성과: 반환 시간(Turnaround Time) 측면에서는 거의 최적(Optimal)에 가깝습니다.
• 새로운 문제점: 응답 시간(Response Time)이 최악입니다.
  • 작업 3개가 동시에 도착했다면, 세 번째 작업은 앞의 두 개가 다 끝날 때까지 한 번도 실행되지 못합니다. 타자기를 치는데 글자가 10초 뒤에 뜬다면 아무도 그 컴퓨터를 쓰지 않을 것입니다.

3.4 Round Robin (RR)#

응답 시간을 해결하기 위해 타임 슬라이스(Time Slice) 개념을 도입합니다. 작업을 끝까지 실행하는 게 아니라, 일정 시간(Quantum)만큼만 실행하고 다음 작업으로 넘어갑니다.

• 특징: 타임 슬라이스가 10ms라면, A(10ms) -> B(10ms) -> C(10ms) -> A… 순으로 돕니다.
• 장점: 모든 작업이 짧은 시간 안에 한 번씩은 CPU를 맛볼 수 있어 응답 시간이 획기적으로 개선됩니다.
• 단점: 반환 시간은 최악이 됩니다.
  • A, B, C가 각각 5초씩 걸린다면, RR은 이들을 조금씩 번갈아 실행하므로 셋 다 거의 15초가 되어서야 동시에 끝납니다. (차라리 하나씩 끝내는 게 반환 시간엔 유리합니다)
• Trade-off: 타임 슬라이스가 너무 짧으면 문맥 교환(Context Switch) 오버헤드가 커지고, 너무 길면 응답성이 떨어집니다.