• 2024.06.07: 복습 및 글 다듬기

Operating Systems : Three Easy Pieces를 보고 번역 및 정리한 내용들입니다.

OS 스케줄러가 사용하는 높은 수준의 정책들에 대해서 이해해보자.

1. Workload Assumptions

정책을 설계할 때에는 워크로드에 대해 잘 알아야 한다.

여기서는 워크로드에 대해 다음과 같이 가정한다. 단, 지금 사용하는 이 가정들이 사실 현실적인 것은 아니기 때문에, 이 가정들을 점차 고치면서 최종적으로는 완전히 잘 작동하는 정책으로 발전시켜 나가자.

가정
1. 각 작업은 같은 시간 동안 실행되어야 한다.
2. 모든 작업은 동시에 시스템에 도달한다.
3. 각 작업은 한 번 시작되면 완료될 때까지 실행된다.
4. 모든 작업은 CPU만을 사용한다.
5. 각 작업의 실행 시간이 미리 알려져있다.

2. Scheduling Metrics

여러 스케줄링 정책들을 서로 비교하기 위해서는 평가의 척도가 필요하다. 스케줄링의 평가에서 쓰일 수 있는 지표에는 여러 가지가 있을 수 있다.

성능 (performance)

스케줄러의 성능에 대한 지표로 쓰이는 것 중 하나는 반환 시간(turnaround time) 으로, 작업이 시스템에 도달하고나서 완료되기 까지의 시간이다.

위에서 가정하기로, 모든 작업이 같은 시간에 시스템에 도달한다고 했기 때문에 $T_{arrival}$은 0이고, 따라서 $T_{turnaround} = T_{completion}$이다.

공정성 (fairness)

또 비교해볼 만한 것에는 얼마나 프로세스들이 공정하게 처리하게 되고 있는지에 대한 것이 있다. 이는 Jain's Fairness Index와 같은 지표를 이용해 평가될 수 있다.

3. First In, First Out (FIFO)

스케줄링 알고리즘 중 가장 기본적인 것은 FIFO(First In First Out) 또는 FCFS(First Come First Served) 로 불리는 것으로, 프로세스를 시스템에 도달하는 순서대로 처리하는 것이다. 이는 간단하고 구현하기도 쉽다.

앞으로 사용할 두 가지의 케이스를 먼저 생각해보자.

case 1)

프로세스 A, B, C가 순서대로, 거의 동시에 시스템에 도달한다. 각 프로세스를 처리하는 데에 걸리는 시간은 10으로 동일하다.
FIFO를 이용할 경우, A는 10, B는 20, C는 30에 완료되므로. 평균 반환 시간은 (10 + 20 + 30) / 3 = 20이다.

case 2)

위 case 1의 경우 '각 작업이 같은 시간 동안 실행되어야 한다'는 가정 1을 사용하고 있다. 그렇다면 이번에는 프로세스 A를 처리하는 데에는 100의 시간이, B, C를 처리하는 데에는 10의 시간이 걸린다고 해보자.

가정
1. 각 작업은 같은 시간 동안 실행되어야 한다.
2. 모든 작업은 동시에 시스템에 도달한다.
3. 각 작업은 한 번 시작되면 완료될 때까지 실행된다.
4. 모든 작업은 CPU만을 사용한다.
5. 각 작업의 실행 시간이 미리 알려져있다.

FIFO를 사용할 경우 A는 100, B는 110, C는 120에 완료되므로 평균 반환 시간은 110이다.

Convoy Effect
이와 같이 처리하는 데에 걸리는 시간이 상대적으로 짧을 가능성이 있는 자원 소비자가, 보다 무거운 것 뒤에 위치해 전체적인 성능이 하락하는 현상을 convoy effect라 한다.

4. Shortest Job First (SJF)

SJF는 실행 시간이 짧은 작업을 우선으로 처리한다. 위 case 2를 다시 보면, 프로세스들은 실행 시간에 따라 B, C, A의 순으로 처리되게 된다. 이때 B는 10, C는 20, A는 120에 완료되므로 평균 반환 시간은 (10 + 20 + 120) / 3 = 50이 된다.

모든 작업들이 같은 시간에 시스템에 도달한다는 가정 아래, SJF는 최적의 스케줄링 알고리즘이다. 하지만 현실에서는 이런 가정은 성립하지 않는다. 프로세스 B, C가 A가 스케줄링 되고 실행된 직후 시스템에 도달하는 경우, convoy effect가 똑같이 발생하게 된다.

가정
1. 각 작업은 같은 시간 동안 실행되어야 한다.
2. 모든 작업은 동시에 시스템에 도달한다.
3. 각 작업은 한 번 시작되면 완료될 때까지 실행된다.
4. 모든 작업은 CPU만을 사용한다.
5. 각 작업의 실행 시간이 미리 알려져있다.

5. Shortest Time-to-Completion First (STCF)

STCF는 위와 같은 문제를 해결하기 위해 한 프로세스가 실행 중이더라도 더 실행 시간이 더 짧은 프로세스들이 들어오면 해당 프로세스에 CPU 제어권을 넘거주는 방법이다. 이는 프로세스가 자발적으로 CPU 제어권을 내놓는 방식이 아니라 외부에서 프로세스가 가진 제어권을 빼앗는 방법이기 때문에, 선점적(preemptive) 이라고 한다.

Shortest Time-to-Completion First(STCF), 또는 Preemptive Shortest Job First(PSJF) 스케줄러는 새로운 작업이 시스템에 들어왔을 때, 스케줄러는 큐에 있는 모든 작업들의 남은 시간을 계산하고 가장 짧은 것을 고른다.

프로세스 B, C가 시점 10에 시스템에 도달한다고 하자. 시점 10에 작업 A는 90이 남아있으므로, 남아있는 작업 시간이 더 짧은 B, C를 먼저 처리해야 한다. B는 20에, C는 30에 끝나고, A는 120에 끝난다. 평균 반환 시간은 (10 + 10 + 120)/3 = 50이 된다.

모든 프로세스가 동시에 들어온다는 가정을 제외하는 경우, STCF는 최적이다.

6. A New Metric : Response Time

반환 시간만을 신경쓰는 경우에는 STCF는 좋은 정책이 될 수 있지만, 현대의 time-sharing 시스템에서는 다른 척도도 사용된다.

응답 시간 (response time)

응답시간은 시스템에 도달한 작업이 처음으로 스케줄되는 시간이다.

case 1의 경우를 다시 봤을 때, B는 10, C는 20에 스케줄되므로 평균 응답 시간은 은 (0 + 10 + 20)/ 3 = 10이다. 응답 시간을 줄일 수 있는 스케줄링 알고리즘에는 무엇이 있을까?

7. Round Robin

RR은 작업들을 완료될 때까지 통으로 실행하지 않고, 각 작업을 시간 단위(time slice, 또는 scheduling quantum)으로 나눠 모든 작업들이 종료될 때까지 다른 작업으로 반복해서 전환하는 방식이다.

가정
1. 각 작업은 같은 시간 동안 실행되어야 한다.
2. 모든 작업은 동시에 시스템에 도달한다.
3. 각 작업은 한 번 시작되면 완료될 때까지 실행된다.
4. 모든 작업은 CPU만을 사용한다.
5. 각 작업의 실행 시간이 미리 알려져있다.

case 1의 작업들을 1의 시간 단위로 나눈다고 하자. RR을 사용할 때 A는 0, B는 1, C는 2에 가장 먼저 스케줄되므로평균 응답 시간은 1이 된다.

다만 RR을 사용할 때에는 그 시간 단위를 정하는 게 중요하다. 작업을 나누는 시간 단위가 짧으면 응답 시간도 짧아진다. 하지만 작업을 전환을 할 때에는 컨텍스트 스위칭을 위한 비용이 들기 때문에, 시간이 너무 짧으면 오버헤드가 커져 전체적인 성능 하락이 발생한다. 반대로 단위를 너무 길게 하면 응답 시간이 그만큼 길어지기 때문에 문제가 된다.

시간 단위를 잘 정할 때, 응답 시간의 측면에서 RR은 좋은 선택이 될 수 있다. 반환 시간의 측면에서 RR은, 심지어는 FIFO보다도 안 좋은 최악의 정책이다. 일반적으로 공정성에 관심을 두는 정책들은 반환 시간에 있어서는 좋지 않다.

8. Incorporating I / O

가정에서는 CPU만을 사용한다고 했다. 그런데 디스크와 같은 I/O 장치들도 사용해야하는 경우에는 어떨까?

가정
1. 각 작업은 같은 시간 동안 실행되어야 한다.
2. 모든 작업은 동시에 시스템에 도달한다.
3. 각 작업은 한 번 시작되면 완료될 때까지 실행된다.
4. 모든 작업은 CPU만을 사용한다.
5. 각 작업의 실행 시간이 미리 알려져있다.

작업에서 I/O요청이 일어나는 경우, 해당 프로세스는 blocked 상태가 되어 I/O 작업이 마치기를 대기한다. 이때 CPU는 사용하지 않게 되므로, 이렇게 CPU가 남는 시간에 다른 프로세스가 CPU를 사용하게 할 수 있다면 시스템 자원을 조금 더 효율적으로 사용할 수 있을 것이다.

9. No more Oracle

지금까지 스케줄러는 각 작업의 길이를 알고 있었다. 하지만 사실 범용 OS에서 OS는 각 작업이 얼마나 걸릴지는 거의 알지 못한다.

가정
1. 각 작업은 같은 시간 동안 실행되어야 한다.
2. 모든 작업은 동시에 시스템에 도달한다.
3. 각 작업은 한 번 시작되면 완료될 때까지 실행된다.
4. 모든 작업은 CPU만을 사용한다.
5. 각 작업의 실행 시간이 미리 알려져있다.

10. Summary

• STCF
  + 남은 실행 시간이 가장 짧은 작업을 먼저 수행한다.
  + 반환 시간을 최적화할 수 있다.
• RR
  + 작업을 시간 단위로 나누어 계속해서 전환한다.
  + 응답 시간을 최적화할 수 있다
• 반환 시간과 응답 시간은 서로 trade-off다.
• 지금까지의 이상적인 가정 아래에서는 스케줄러가 각 작업에 소요되는 시간을 알고 있지만, 실제로는 그렇지 않다.
  + 이 문제는 과거의 실행 이력을 바탕으로 미래를 예측하는 multi-level feedback queue 스케줄러로 해결된다. 이는 다음 챕터에서 다룬다.