스케줄링 : 개요

스케줄링을 공부하기 위해서는 context swtiching 같은 low-level 기법에 대해서는 알고있어야한다.

모른다면, 이전 글을 참고하여 다시 공부하자.

스케줄링 정책은 원칙이라고도 불립니다.

high-levle 기법으로, 운영체제 관리 분야에서 비롯되었음.

워크로드에 대한 가정

워크로드(Workload)는 프로세스가 동작하는 일련의 행위이다.

스케줄링 정책을 배우기 전에, 쉬운 이해를 위해 몇가지 가정을하고 가자.

일단 가정은 비현실적이며, 하나하나 배워가면서 가정을 제거할 것이다.

• 모든 작업은 같은 시간동안 실행된다.
• 모든 작업이 스케줄러에 도착하는 시간은 같다.
• 작업이 시작되면, 끝날 때까지 실행한다.
• 모든 작업은 CPU에서만 작동한다. 즉, I/O를 발생시키지 않는다.
• 모든 작업의 실행시간은 사전에 이미 알려져있다.

스케줄링 정책 평가 항목

• Turnaround Time ( 반환 시간 )

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

  • 작업 반환 시간은 작업이 완료된 시간에서 작업이 도착한 시간을 뺀 시간.

• Response Time ( 응답 시간 )

  $T_{response} = T_{firstrun} - T_{arrival}$

  • 응답 시간은 작업이 처음으로 시작된 시간에서 작업이 도착한 시간을 뺀 시간.

• Fairness ( 공정성, 형평성 )

  • 여러 개의 프로세들의 완료 시간이 얼마나 비슷한지 비교하는 기준

FIFO ( 선입 선출 )

선입 선출 , 선도착 선처리 ( First Come First Served, FCFS ) 스케줄링은 가장 기본적인 알고리즘입니다.

어떠한 작업이 있더라도, 먼저 스케줄러에 도착한 작업을 먼저 실행합니다.

A,B,C 가 동시에 도착했지만, 간발에 차로 A,B,C가 순서대로 들어왔다고 가정합시다.

이 스케줄러에서 평균 반환 시간과 평균 응답시간은 어떻게 될까?

• A는 0초 도착, 시작 0초, 10초 끝 → 반환시간 10초, 응답 시간 0초
• B는 0초 도착, 시작 10초, 20초 끝 → 반환시간 20초, 응답 시간 10초
• C는 0초 도착, 시작 20초, 30초 끝 → 반환시간 30초, 응답 시간 20초

→ 평균 반환 시간 = 20초

→ 평균 응답 시간 = 10초

아직 예제를 하나밖에 안봤으니, FIFO가 좋은지 안좋은지 모르겠음.

가정을 하나 제거하고 새로운 예시를 보자.

작업시간이 동일하다는 가정을 제외하겠음.

A,B,C 가 동시에 도착했지만, 간발에 차로 A,B,C가 순서대로 들어왔다고 가정합시다.

이 스케줄러에서 평균 반환 시간과 평균 응답시간은 어떻게 될까?

• A는 0초 도착, 시작 0초, 100초 끝 → 반환시간 10초, 응답 시간 0초
• B는 0초 도착, 시작 100초, 110초 끝 → 반환시간 110초, 응답 시간 100초
• C는 0초 도착, 시작 110초, 120초 끝 → 반환시간 120초, 응답 시간 110초

→ 평균 반환 시간 = 110초

→ 평균 응답 시간 = 70초

여기서 보이는 FIFO의 단점

• 시간이 많이 필요로하는 작업이 먼저 수행 된다면, 뒤에 도착하는 빨리 끝나는 작업이 계속 기다리게 됨
• 이런 단점을 convoy effect라고 함.

이걸 어떻게 해결할까?

SJF ( 최단 작업 우선 )

최단 작업 우선 스케줄링 기법( Shortest Job First )은 가장 짧은 실행 시간을 가진 작업을 먼저 실행시킴.

A,B,C 가 동시에 도착. SJF 가정에 따라 B,C가 실행되고 A가 실행

이 스케줄러에서 평균 반환 시간과 평균 응답시간은 어떻게 될까?

• A는 0초 도착, 시작 20초, 120초 끝 → 반환시간 120초, 응답 시간 20초
• B는 0초 도착, 시작 0초, 10초 끝 → 반환시간 10초, 응답 시간 0초
• C는 0초 도착, 시작 10초, 20초 끝 → 반환시간 20초, 응답 시간 10초

→ 평균 반환 시간 = 50초

→ 평균 응답 시간 = 10초

위의 FIFO를 진행했을 때 보다, 반환 시간과 응답 시간이 나아짐.

SJF는 가장 짧은 시간이 걸리는 프로세스를 먼저 실행하기 때문에, 반환 시간의 평균이 줄어들 수 밖에 없음.

그리고 모든 프로세스가 동시에 도착한다는 가정하에 최적의 알고리즘임.

하지만, 다른 예제를 보면 이것이 단점을 크게 가지고 있다는 것을 알 수 있음.

이 예제를 보기전에, 모든 작업이 항상 동시에 도착한다는 가정을 제외하겠음.

A 가 먼저 도착하고, B와 C가 그 뒤에 동시에 도착한다고 해보자.

이 스케줄러에서 평균 반환 시간과 평균 응답시간은 어떻게 될까?

• A는 0초 도착, 시작 0초, 100초 끝 → 반환시간 100초, 응답 시간 0초
• B는 10초 도착, 시작 100초, 110초 끝 → 반환시간 100초, 응답 시간 90초
• C는 10초 도착, 시작 110초, 120초 끝 → 반환시간 110초, 응답 시간 100초

→ 평균 반환 시간 = 103.33초

→ 평균 응답 시간 = 60.33초

이제 단점이 보이게 된다.

뒤늦게 도착한 작업이 먼저 도착한 작업보다 짧어도, 늦게 도착했으니 수행되기 위해 먼저 시작한 작업이 끝날 때까지 기다려야 함.

→ 다시 convoy effect 발생.

이걸 어떻게 해결할까?

STCF ( 최소 잔여시간 우선 )

최소 잔여시간 우선 스케줄링 기법( Shortest Time-to-Completion First )은 현재 실행중인 작업의 잔여 실행 시간과 새로운 작업의 잔여 실행 시간을 비교하여, 잔여 실행 시간이 가장 작은 작업을 스케줄한다.

이 스케줄러는 선점 스케줄러로, 어떤 작업을 수행하는 도중에 다른 작업을 수행할 수 있도록 스케줄하는 스케줄러를 말함.

이제 예시를 보기위해, 하나의 가정을 또 제외하자. 이번에는 작업이 끝날때까지 실행된다는 가정을 제외하자.

이제는 작업이 중간에 중단될 수 있다.

A 가 먼저 도착하고, B와 C가 그 뒤에 동시에 도착한다고 해보자.

이 스케줄러에서 평균 반환 시간과 평균 응답시간은 어떻게 될까?

• A는 0초 도착, 시작 0초, 120초 끝 → 반환시간 120초, 응답 시간 0초
• B는 10초 도착, 시작 10초, 20초 끝 → 반환시간 10초, 응답 시간 0초
• C는 10초 도착, 시작 20초, 30초 끝 → 반환시간 20초, 응답 시간 10초

→ 평균 반환 시간 = 50초

→ 평균 응답 시간 = 3.33초

이제 SJF보다 훨씬 나아진 것을 볼 수 있다.

여태까지는 반환시간에 초점을 맞추어서 알고리즘을 개선해나갔다.

하지만 여기서도 단점이 있으니, SJF 예제를 하나 더 보자.

A, B, C가 동시에 도착한다고 가정해보자.

이 스케줄러에서 각각의 반환시간과 응답시간은 어떻게 될까?

• A는 0초 도착, 시작 0초, 5초 끝 → 반환시간 5초, 응답 시간 0초
• B는 0초 도착, 시작 5초, 10초 끝 → 반환시간 10초, 응답 시간 5초
• C는 0초 도착, 시작 10초, 15초 끝 → 반환시간 15초, 응답 시간 10초

→ 평균 반환 시간 10초

→ 평균 응답 시간 5초

여기서 볼 수 있는 단점

• 모두 동시에 도착했고, 같은 작업시간을 가지고있기 때문에 C는 앞선 두 작업이 모두 끝날 때까지 무작정 기다려야한다.
• 단지 다른 작업이 먼저 스케줄 되었다고, 무작정 10초를 기다려야하는 것은 사용자 입장에서 좋지않다.

→ 응답시간에서 문제가 생겼다.

이것을 어떻게 해결할까?

Round Robin ( 라운드 로빈 )

라운드 로빈은 작업을 일정 시간 실행한 후 실행 큐의 다른 작업으로 전환한다.

이때 작업이 실행되는 일정 시간을 타임 슬라이스 또는 스케줄링 퀀텀이라고 부른다.

라운드 로빈은 작업이 완료될 때까지 이 방법을 계속 반복한다.

타임 슬라이스는 타이머 인터럽트의 배수로 정해져야한다.

→ 그래야 OS가 인터럽트를 통해 제어권을 가져올 수 있기 때문.

예제를 하나 보자. 타임슬라이스가 1초인 라운드 로빈 방식의 예제이다.

A, B, C가 동시에 도착한다고 가정해보자.

이 스케줄러에서 평균 반환시간과 평균응답시간은 어떻게 될까?

• A는 0초 도착, 시작 0초, 끝 13초 → 반환시간 13초, 응답 시간 0초
• B는 0초 도착, 시작 1초, 끝 14초 → 반환시간 14초, 응답 시간 1초
• C는 0초 도착, 시작 2초, 끝 15초 → 반환시간 15초, 응답 시간 2초

→ 평균 반환 시간 14초

→ 평균 응답 시간 1초

아까 평균적으로 5초의 응답시간이 걸리던 SJF( 그림 7.6 )보다 훨씬 좋아졌다.

쉽게 알 수 있듯이, 타임슬라이스가 짧아지면 응답시간을 성능 측정 기준으로했을 때 RR의 성능은 좋아진다.

하지만, 너무 짧아지면 문제가 생김.

→ context switching이 자주 발생하기 때문에 전체적으로 성능에 저하가 발생.

→ context switching의 비용을 상쇄할 수 있을 만큼의 타임 슬라이스를 지정해야한다.

하지만, 반환시간을 유일한 측정 기준으로 둔다면 RR은 좋지않다.

SJF를 사용했을 때 평균 반환시간은 10초였지만, RR은 14초이다.

FIFO로 스케줄했을 때보다 안좋은 결과가 나온 것.

여태까지 알아본 방법은 두 가지의 경우라 나뉨

• SJF, STCF는 Turnaround Time을 최적화하지만 Response Time이 좋지않음.
• RR은 Response Time을 최적화하지만 Turnaround Time이 좋지 않음.

따라서 두 경우의 관계는 반비례.

사실상 어느 것을 선택하면 한가지는 포기해야한다.

여태까지 우리는 가정을 하나씩 없애면서 예시를 봐왔다.

현재 남은 가정은 두 가지. 이것들도 하나씩 제외하면서 보자.

입출력 연산을 고려하기

이제는 모든 작업이 입출력을 수행하지 않는다는 가정을 제외하겠음.

스케줄러는 어떤 작업이 I/O를 실행중일 때 결정을 내릴 수 있다.

I/O는 CPU를 사용하지 않기 때문.

I/O 작업중에 CPU를 차단하는 방식은 Busy Waiting이라고 함.

예를 들어 하드디스크에 어떤 데이터를 저장하려고 할 때 데이터의 크기가 커서 오래 걸리게 된다면 CPU가 오랜 시간 일을 하지 않는 상태가 될 수 있음.

이렇게 I/O 작업동안 다른 작업을 못하면 Blocked 된다고 함.

스케줄러는 I/O가 끝났을 때도 결정을 내려야함.

인터럽트가 발생하고, I/O를 발생시킨 작업은 Ready 상태가 되어야하기 때문.

이렇게 I/O 작업시 스케줄러는 어떻게 처리를 해야할까?

A와 B 작업이 있다고 가정을하자.

A 작업과 B 작업은 모두 50초의 수행 시간을 가지고 있다.

그리고 A 작업은 10초마다 I/O를 발생시킨다.

B 작업은 I/O를 하지않는다.

스케줄러는 A를 먼저 실행시키고, B를 다음에 실행시킨다.

그런데 이때, 스케줄러가 I/O 작업시 CPU를 다른작업에게 넘겨주지 않고 Busy Waiting 방법을 사용한다면, I/O 작업을 수행하는 동안 CPU가 아무것도 안하게 된다.

이것을 어떻게 해결할까.

I/O를 수행하는 동안 A 작업이 CPU를 포기하고, B에게 CPU를 할당해주는 방식을 택하는 것.

이렇게하면, 남는 시간동안 CPU가 아무것도 하는 경우가 존재하지 않고 아까보다 바르게 작업이 끝나게 된다.

이제 마지막 가정에 대해 생각해봅시다

No More Oracle

스케줄러가 각 작업의 실행 시간을 알고있다는 가정을 제외하자.

이런 상황일 때 프로세스의 수행시간을 OS에게 어떻게 예측하여 알려줄 수 있을까.

예측은 exponential moving average(지수 이동 평균)을 사용한다.

위 방법은 나중에 찾아보도록 하자.

요약

우리는 Turaround time을 최적화하는 방법과 Response Time을 최적화하는 방법을 가진 스케줄러를 알아보았다.

그리고 I/O가 같이 있을 때 어떻게 스케줄러를 작동시켜야하는지도 알아보았다.

하지만 아직 프로세스의 미래동작을 예측하는 법은 모른다.

이런 미래동작을 예측하는 방법은 과거의 프로세스 동작이력을 반영하는 방식으로 문제를 해결한다.

이 방법은 다음장에서 알아보자.