[운영체제]스케줄링

가장 먼저 프로세스에 대하여 몇가지 가정을 할 것이다. 일련의 프로세스들이 실행하는 상황을 워크로드라고 부르기로 한다. 워크로드를 결정하는 것은 정책 개발에 매우 중요한 부분이다. 

 

우리는 시스템에서 실행 중인 프로세스 혹은 작업에 대해 다음의 가정을 설립한다.

1.모든 작업은 같은 시간 동안 실행한다.

2.모든 작업은 동시에 도착한다.

3.각 작업은 시작되면 완료될 때까지 실행한다.

4.모든 작업은 CPU에서만 실행한다.(I/O X)

5.각 작업의 실행 시간은 사전에 알려져 있다.

 

가정들이 굉장히 비현실적이다. 스케줄링을 살펴보면서 가정들을 해제해 보자.

 

 

 

스케줄링 평가항목 

1.선입선출

작업 반환 시간은 작업이 완료된 시각에서 작업이 시스템에 도착한 시간을 뺀 시간이다.

반환 시간은 성능 측면에서의 평가 기준이다. 다른 평가 기준은 공정성이다. 성능과 공정성은 스케줄링에서는 서로 상충되는 목표이다. 예를들어 스케줄러는 성능을 극대화 하기 위해 몇몇 작업의 실행을 중지할 수 있다. 즉, 공정성이 낮아진다는 것이다.

 

가장 기초적인 스케줄링 알고리즘은 선입선출이다. 이는 구현이 쉽고 위의 가정하에서 매우 잘 동작한다.

 

위 사진처럼 A가 제일 먼저 도착해 실행되고, b,c가 실행될 때, 평균 반환 시간은 어떻게 될까?(여기서 반환 시간이란 프레스가 반환되기 까지 걸리는 시간이다.)

A 10초, B 20초, C 30초 해서 (10+20+30)/3 = 20초이다.

하지만 1번 가정을 완화해 동작 시간이 다를 수 있다 해보자.

 

 

이런 경우 평균 반환 시간은 A 100초, B 110초, C 120초 해서 (100+110+120)/3 = 110초이다.

이런 문제점은 호위 효과(convoy effect)라고 한다. 동작 시간이 긴 프로세스 때문에 다른 프로세스들이 기다리는 현상이다.

 

2.최단 작업 우선(SJF)

FIFO의 문제를 해결하는 방법은 작업시간이 짧은 것 먼저 처리하는 방법이다.

 

위와 같이 작업시간이 짧은 작업 먼저 처리하게 되면 반환 시간은 (10+20+120)/3 = 50이 된다.

2번 가정에 의해 모든 작업이 동시에 도착한다면 SJF가 좋은 방법일 수 있다.

그럼 2번 가정을 삭제해 A가 먼저 도착, B,C 순서로 도착했다 해보자.

 

위 처럼 다시 A가 먼저오게 되어 반환시간이 길어지게 된다.

B,C가 10초에 도착했다 하면 (100+(110-10)+(120-10))/3 = 103.33이 된다.

 

3.최소 잔여시간 우선(STCF)

3번가정을 삭제해보자. 타이머 인터럽트와 문맥 교환을 고려하면 B와 C가 도착했을 때 스케줄러는 다른 일을 할 수 있다. 스케줄러는 현재 실행중인 A를 중지하고 B,C를 실행 시킬 수 있지만 SJF는 비선점형이기 때문에 그럴 수 없다.

그러면 최단 잔여시간 우선 방법을 사용한다. 새로운 작업이 들어오면 현재 실행중인 작업의 잔여시간과 새로운 작업의 잔여 시간을 비교해 짧은 작업 먼저 실행한다.

 

위 사진 처럼 A 동작 도중 B,C 도착, B 실행, C 실행 후 다시 A가 실행된다.

그럼 반환 시간이 (120+(20-10)+(30-10))/3 = 50이 된다.

 

이번엔 응답 시간을 기준으로 평가를 해보자.

시분할 컴퓨터가 등장하면서 시스템에게 상호작용을 얼마나 원활히 할 수 있는가가 평가 기준이 되었다.

응답 시간은 작업이 도착할 때부터 처음 스케줄 될 때까지의 시간으로 정의된다.

응답시간 = 첫 동작 시간 - 도착시간

위 사진처럼 A의 도착시간 = 0 B,C의 도착시간 = 10 인 경우에

응답 시간은 A : 0 , B : 0 C : 10 이 되고 평균 3.33이다.

 

 

4.라운드 로빈(RR)

RR은 작업이 끝날 때까지 기다리는 것이 아니다. 일정 시간 동안 실행한 후 실행 큐의 다음 작업으로 전환한다. 이때 작업이 실행되는 일정 시간을 타임 슬라이스라고 한다.

타임 슬라이스의 길이는 타이머 인터럽트 주기의 배수여야 한다. 타이머가 10msec마다 인터럽트를 발생시킨다고 한다면 타임 슬라이스는 10,20,30 과 같이 10의 배수여야 한다.

 

 

A,B,C가 동시에 도착했다 가정했을 때, SJF의 경우 위와 같고 응답시간은 (0+5+10)/3 = 5이고,

 

 

RR은 (0+1+2)/3 = 1이 된다.

그러나 타임 슬라이스를 너무 짧게하면 문제가 생긴다. 짧게 지정하면 문맥 교환 비용이 전체 성능에 큰 영향을 미친다.

문맥 교환 비용에는 레지스터를 저장/복원하는 단계만 있는게 아니다. CPU 캐시,TLB, 분기 예측 등을 비롯해 다른 하드웨어에도 프로그램들과 관련된 다양한 작업이 있다.

하지만 RR의 평균 반환 시간을 보면 (13+14+15)/3 = 14로 굉장히 좋지 않다.

 

여기까지 1,2,3의 가정을 해제 했다.

 

입출력 연산의 고려

가정 4를 해제하자. 모든 프로그램이 I/O과정을 수행한다. 

I/O 인터럽트가 들어온 경우, 스케줄러는 어떤 작업을 수행할지 결정한다. 현재 실행 중인 작업은 I/O 인터럽트 때문에 동작을 수행하지 않고 I/O 작업이 완료될 때까지 대기한다. 그 시간동안 스케줄러는 다른 작업을 수행한다.

 

입출력이 완료되면 인터럽트가 다시 발생하고 운영체제게 실행되어 입출력을 요청한 프로세스르 대기 상태에서 준비 상태로 만든다. 

작업 시간이 50msec인 A,B작업이 있다 가정해보자. A작업은 10msec 마다 입출력을 받는다.

 

 최소 잔여시간 우선(STCF)로 스케줄러가 작동한다 할 때, A는 10msec로 분할되고 B는 50msec 통으로 동작한다. 이럴 경우 위 사진과 같이 A를 실행한 후에 B를 실행하게 된다. 반환시간은 (90+140)/2 = 115가 된다. 

 

하지만 여기에 시분할을 같이 적용해 A가 CPU를 사용하지 않는 시간동안 B를 적용한다면?

 

위 사진처럼 반환시간은 (90+100)/2 = 95로 줄어든다.

 

첫번째 부류는 남아 있는 작업 중 실행 시간이 제일 짧은 작업을 수행하고, 반환 시간을 최소화 한다.

두번째 부류는 모든 작업을 번갈아 실행하고 응답 시간을 최소화 한다.

이렇게 4번까지의 가정을 해결했지만 5번가정은 해결하지 못했다.

멀티 레벨 큐를 이용해 5번 가정을 해결해 보자.