Operating Systems Three Easy Pieces
작성자: Remzi H. Arpaci-Dusseau, Andrea C. Arpaci-Dusseau · 2018 번역본을 참고하였습니다.
https://github.com/remzi-arpacidusseau/ostep-translations/tree/master/korean
저번시간에 제한적 직접 실행 시 타이머 인터럽트를 통해 운영체제가 커널 모드 <-> 사용자 모드를 오고가면서 도중에 에러가 발생할 경우 프로세스 전권을 비협조적으로 가져올 수 있게 했었다. 이 때 프로세스 A가 문제가 발생해 중단하고 다음 프로세스를 실행하는 컨텍스트 스위칭을 사용하는데, 어떤 프로세스가 다음 실행할 프로세스로 와야할까?
스케줄링 정책(scheduling policy)
일련의 프로세스들이 실행하는 상황을 워크로드라고 한다. 제대로 동작하는 스케줄링 정책을 만들기 위해 먼저 장치를 걸어둔다.
- 모든 작업은 같은 시간 동안 실행된다.
- 모든 작업은 동시에 도착한다.
- 각 작업은 시작되면 완료될 때까지 실행된다.
- 모든 작업은 CPU만 사용한다. (입출력을 수행하지 않음)
- 각 작업의 실행 시간은 미리 알고 있다.
스케줄링 평가 항목
스케줄링의 평가 항목 중 반환 시간이라는 기준이 있고, 이는 작업이 완료된 시간 - 작업이 시스템에 도착한 시간으로 정의된다. 반환 시간은 성능 측면에서의 평가 기준이다.
- 선입선출(FIFO, FCFS)
프로세스 A, B, C의 시스템에 도착한 시간이 모두 0이다.(근소한 차이로 A-B-C 순 도착) 종료시간은 10, 20, 30 일때 각각의 반환 시간은 10-0, 20-0, 30-0 으로 평균 반환 시간은 (10 + 20 + 30) / 3이다.
여기서 가정 1번 실행시간이 모두 같다는 가정을 빼버리면?
다음과 같이 A, B, C의 실행 시간은 각각 100, 10, 10이다. 이 경우에는 평균 반환 시간이 (100 + 110 + 120) / 3으로 평균 반환시간이 늘어났다.
convoy effect: 짧은 시간 동안 자원을 사용할 프로세스들이 자원을 오랫동안 사용하는 프로세스의 종료를 기다리는 현상
이를 해결하기 위해 최단 작업 우선(SJF) 기법을 사용한다. 가장 짧은 실행 시간을 가진 작업을 먼저 실행함으로써 평균 반환시간을 줄일 수 있다.
여기서 가정 2번 도착시간이 모두 같다는 가정을 빼버리면?
A, B, C는 각각 0, 10, 10초에 도착했다. 실행시간은 B, C가 더 빠르지만 A프로세스가 끝날 때 까지 대기해야 하기에 또다시 convoy effect가 발생한다. 평균 반환 시간도 FIFO 스케줄링의 반환시간과 다를바 없게 되었다.
선점형 스케줄러: FIFO, SJF는 각 작업이 종료될 때까지 기다려야 하는 비선점 스케줄러였다. 다른 프로세스를 실행시키기 위해 현재 프로세스 실행을 중단하여 문맥교환을 수행하고 다른 프로세스를 시작할 수 있는 선점형 스케줄러가 개발됐다.
이를 해결하기 위해 최소 잔여시간 우선(STCF) 기법을 사용한다. 타이머 인터럽트와 문맥 교환을 고려하여 B, C가 도착했을 때 A를 중지하고 도착한 B, C의 작업시간을 비교해 실행할 수 있다.
스케줄링의 평가 항목 중 응답 시간이라는 기준이 있고, 이는 작업 처음 스케쥴되는 시간 - 작업이 시스템에 도착한 시간으로 정의된다. 응답 시간은 공정성 측면에서의 평가 기준이다. STCF는 반환시간은 좋지만, 응답시간이 짧지 않다. 마지막 프로세스는 앞선 프로세스들의 작업이 완료될 때 까지 기다려야 하고 결국 응답시간은 길어진다.
라운드로빈(Round-Robin)은 작업이 끝날때까지 기다리지 않는다. 일정 시간동안 실행한 후 실행 큐의 다음 작업으로 전환한다. 작업이 실행되는 일정 시간을 타임 슬라이스라고 한다. 타임 슬라이스의 길이는 타이머 인터럽트 주기의 배수여야 한다. (타임 슬라이스는 인터럽트의 2배 이상 이어야함) RR은 선점적인 방식이면서 STCF의 Starvation의 문제를 해결한 기법이다.
타임 슬라이스의 길이가 타이머 인터럽트 주기의 배수여야 하는 이유?
타임 슬라이스가 타이머 인터럽트 주기를 넘어가지 않도록 하기 위해서다. 만약 타임 슬라이스의 길이가 타이머 인터럽트 주기보다 짧거나 그에 배수가 아니라면, 타임 슬라이스가 중간에 끊기거나 불규칙한 타이밍으로 인해 인터럽트가 발생할 수 있다. 이러한 경우 CPU 스케줄링이 제대로 이루어지지 않을 수 있고, 프로세스가 원하는 만큼의 시간을 정확하게 할당받지 못하게 된다.
A, B, C가 동시에 도착하고 각각 5초간 실행된다. SJF의 응답시간은 (0 + 5 + 10) / 3, RR의 응답시간은 (0 + 1 + 2) / 3으로 훨씬 빨라졌다.
타임 슬라이스가 짧을 수록, 응답 시간 기준으로 RR의 성능이 좋아지기는 하나 짧게 지정할 수록 컨텍스트 스위칭 비용이 전체 성능에 영향을 미치게 된다. 문맥 교환 비용에는 레지스터 저장/복원 뿐 아니라 CPU 캐시, 분기 예측 등 다양한 작업이 저장된다. 작업이 전환될 때마다 이 정보들은 모두 갱신되어 성능 비용이 커진다.
위의 A, B, C(동시 도착, 작업 시간 5초)의 반환시간을 계산해보자. (작업완료시간 - 도착시간)
((13 - 0) + (14 - 0) + (15 - 0)) / 3으로 최악의 반환시간을 보인다. RR은 공정성 측면에서 모든 프로세스에게 CPU를 골고루 분배하는 기법은 반환시간은 나쁘고 응답시간은 좋다. 이를 위해 trade-off를 적절히 해야한다.
여기서 가정 4번 CPU만을 사용한다는 가정을 빼버리면?
입출력 작업을 요청한 경우 스케줄러는 다음에 어떤 작업을 실행할지에 대한 결정을 한다. 현재 실행 중인 작업은 입출력이 완료될 때까지 CPU를 사용하지 않는 대기상태가 된다. 입출력이 완료되면 인터럽트가 발생하고 운영체제가 실행되어 입출력을 요청한 프로세스를 대기상태에서 준비상태로 다시 이동한다.
입출력 요청(10msec)을 하는 프로세스 A(작업시간 50msec)와 요청하지 않는 프로세스 B(작업시간 50msec)가 있다. 입출력을 수행하는 프로세스A는 입출력이 끝나기를 기다리는 동안 CPU는 다른 프로세스에 의해 사용되어 연산을 중첩할 수 있다.
결론
반환 시간을 최소화 하는 FIFO, SJF, STCF가 있다.
응답 시간을 최소화 하는 Round-Robin이 있다.
하나를 최적화 하려면 나머지는 좋지 않은 특성을 띤다. 절충을 요구하는 상황에 직면했고 이를 해결하기 위한 가정5 각 작업의 실행시간을 미리 알고있다 를 빼버리기 위해 멀티 레벨 피드백 큐를 알아보자.
