[SW 정글 61일차] Scheduling (스케쥴링)

오늘은 pintos Project 1 과제를 완료하고 조금 더 운영체제에 대한 지식을 나의 것으로 만드는 시간을 가졌다.

아직, Advanced scheduling 구현을 하지는 못했지만 일단은 옵션이고 지금 내가 알고 싶은 것을 공부하고 싶었다.

공부 자료는 권영진 교수님이 추천해준 three easy peices이다.

일단은 CPU Scheduling까지 읽었는데 정말 이해하기 쉽게 써지기도 했고 OS라는 과목에서 자주 나오는 개념을 조금 다른 시각에서 해석해주는 것이 좋았다.

오늘 배운 것중에서 그래도 project 1과 가장 연관이 많은 scheduling에 대해 정리하려고 한다.

 

 

 

 

1. 선점형(preemptive) vs 비선점형(non-preemptive) 스케쥴링

먼저, 스케쥴링 하나하나를 정리하기 전에 스케쥴링을 크게 두 분류로 나누는데 그것에 대해 정리해보려고 한다.

 

비선점형 스케쥴링이란 어떠한 프로세스(스레드)가 CPU를 할당받으면 해당 프로세스(스레드)가 종료되거나 입출력 요구, 이벤트 등이 발생하여 자발적으로 중지될 때까지 계속 CPU를 점유하는 것을 보장하는 스케쥴링이다.

 

선점형 스케쥴링이란 하나의 프로세스(스레드)가 CPU를 점유하고 있을 때, 다른 프로세스가 CPU를 빼앗아 차지할 수 있는 스케쥴링이다.

선점이라는 말은 컴퓨터의 자원, 여기서는 프로세서(CPU)라고 생각하면 되는데 이 CPU를 우선적으로 차지할 수 있는 권한이라고 생각하면 된다.

여기서 선점권을 가지고 있는 대상은 현재 실행 중인 프로세스(스레드)가 아닌 실행 대기 중인 프로세스(스레드)이다.

 

 

선점형 스케쥴링과 비선점형 스케쥴링의 차이점은 아래와 같다.

1) 선점형 스케쥴링은 프로세스(스레드)에게 CPU가 제한된 시간동안 할당되어 프로세스(스레드)가 작업을 수행하는 도중에 자원을 반납하고 대기 상태에 진입할 수 있다. 하지만 비선점형 스케쥴링은 프로세스(스레드)가 종료되거나 I/O를 수행하기 위해 자발적으로 대기상태에 들어가지 않는 한 자원을 반납하지 않는다.

 

2) 선점형 스케쥴링은 프로세스(스레드)가 실행되는 중에 인터럽트를 허용하지만 비선점형 스케쥴링은 인터럽트를 허용하지 않는다.

 

3) 선점형 스케쥴링은 미리 정의된 프로세스(스레드)의 우선순위에 따라 스케쥴링을 하게되어 우선순위가 낮은 프로세스(스레드)가 자원을 할당받지 못하게 되는 기아 현상(starvation)이 발생할 수 있다. 비선점형 스케쥴링은 수행시간이 긴 프로세스(스레드)가 자원을 점유하게 되면 그 이후에 실행되어야 할 프로세스(스레드)들이 기아 상태에 빠지게 된다.

 

4) 선점형 스케쥴링은 문맥 교환(context switching)이 자주 일어나기 때문에 오버헤드가 발생할 수 있다. 비선점형 스케쥴링은 필수적인 문맥교환(한 프로세스가 작업을 완전히 종료한 경우) 외에 추가적인 오버헤드가 없다.

 

5) 선점형 스케쥴링은 공유 자원에 접근하고 있는 프로세스(스레드)가 여러개 존재할 수 있기 때문에 이를 적절히 관리하는 비용이 많이 소요되지만 비선점형 스케쥴링은 비교적 그런 부분에서 적다.

 

 

이제 아래서부터 각각의 스케쥴링에 대해 알아볼 것이다.

각각의 스케쥴링의 예시로 실행 중인 프로세스 혹은 작업에 대해 다음과 같은 가정을 한다.

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

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

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

4. 모든 작업은 CPU만 사용한다. (I/O 요청이 없다는 가정임)

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

 

 

 

 

2. 선도착선처리(First Come First Served, FCFS)

FCFS는 말 그대로 먼저 도착한(ready 상태가 된) 프로세스(스레드)를 먼저 CPU 점유권을 주어 처리하는 것이다.

FCFS는 비선점형 스케쥴링이다.

먼저, 프로세스(스레드) A, B, C가 거의 동시에 ready 상태가 되었다고 가정하고 작업시간은 10초라고 생각하자.

각 프로세스의 실행기간을 도식화하면 아래와 같다.

평균 반환 시간(반환 시간 = 완료 시간 - 도착 시간)은 (10 + 20 + 30) / 3 = 20이다.

나름 괜찮은 스케쥴링이라고 생각이 드는데 작업시간이 각각 다르다고 생각해보자.

A = 100초, B, C = 10초가 작업시간이고 도착 시간은 거의 같다고 생각하면 아래와 같은 그림이 나온다.

위와 같은 상황이 발생하면 FCFS의 단점을 볼 수 있다.

짧은 시간동안 자원을 사용할 프로세스들이 자원을 오랫동안 사용하는 프로세스의 종료를 기다리는 현상인 convoy effect가 발생하는 것이 FCFS의 단점이다. 

또한, 평균 반환 시간이 (100 + 110 + 120) / 3 = 110으로 좋지 못한 성능지표를 가지고 있다.

FCFS의 장점을 말해보면 보다시피 단순하고 구현도 쉽다는 것이다.

 

 

 

 

3. 최단 작업 우선(Shortest Job First, SJF)

SJF는 평균 반환 시간이 강조되는 모든 시스템에 적용될 수 있는 일반적인 스케쥴링으로 가장 짧은 실행 시간을 가진 작업을 실행시키는 스케쥴링이다.

SJF는 비섬점형 스케쥴링이다.

FCFS에서 사용한 두번째 예시를 SJF 스케쥴링으로 돌리면 어떻게 될지 생각해보자.

결과를 도식화해보면 아래와 같이 나올 것이다.

평균 반환 시간을 구해보면 (10 + 20 + 120) / 3 = 50으로 FCFS에 비해 2배이상 좋아진 것을 볼 수 있다.

모든 작업이 동시에 도착한다는 가정 하에는 SJF가 최적의 알고리즘이라는 생각이 든다.

 

하지만, 모든 작업이 동시에 도착한다는 가정이 없어지고 임의의 시간에 도착한다고 가정해보자.

A가 0초에 도착을 하고 B, C는 거의 동시에 10초에 도착한다고 생각해보자.

SJF는 비선점형 스케쥴링이기 때문에 아래와 같은 결과가 나온다.

평균 반환 시간은 (100 + (110 - 10) + (120 - 10)) / 3 = 103.33으로 나쁜 지표를 가지고 있다.

그리고 FCFS에서 보았던 것처럼 convoy effect가 발생하는 것을 볼 수 있다.

 

 

 

 

 

4. 최소 잔여시간 우선(Shortest Time-to-Completion First, STCF)

최소 잔여시간 우선은 위에서 본 SJF의 convoy effect 문제를 해결하기 위해 나온 선점형 스케쥴링이다.

위 문제를 해결하기 위해서는 '각 작업은 시작되면 완료될 때까지 실행된다.'라는 가정을 없애고 선점당할 수 있도록 해주어야한다.

STCF는 새로운 작업이 시스템에 들어왔을 때, 남아 있는 작업과 새로운 작업의 잔여 실행 시간을 비교하여 가장 적은 잔여 실행 시간을 가진 작업이 CPU를 선점할 수 있도록 하는 스케쥴링이다.

그러면 이제 A가 0초에 도착하고 B, C가 10초에 거의 같은 시간에 도착한다는 예시를 STCF로 스케쥴링해보자.

평균 반환 시간을 구해보면 (120 + (20 - 10) + (30 - 10)) / 3 = 50이 되어 SJF보다 좋은 성능을 보이고 convoy effect도 해결이 되었다.

즉, STCF는 서론에서 언급한 4, 5번 가정이 있다는 전제 하에는 최적의 알고리즘이다.

하지만, 반환 시간이외에 응답 시간을 고려하면 그리 좋지 않은 스케쥴링이다.

응답 시간은 작업이 도착할 때부터 처음 스케쥴 될 때까지의 시간을 말한다.

그러면 세 개의 작업이 거의 같은 시간에 도착했다고 가정하고 작업 실행 시간같다면 세번째 작업은 다른 프로세스와 거의 같은 시간에 도착했지만 2개의 작업이 모두 끝날 때까지 기다려야하므로 응답 시간이 길어지는 단점을 가진다.

이 문제를 해결하기 위해 나온 스케쥴러가 다음에 설명할 라운드 로빈이다.

 

 

 

 

5. 라운드 로빈(Round-Robin) 

라운드 로빈 스케쥴링은 선점형 스케쥴링으로 일정 시간(타임 슬라이스, 스케쥴링 퀀텀)동안 실행한 후 실행 큐의 다음 작업으로 전환하는 스케쥴링이다.

타임 슬라이스의 길이는 타이머 인터럽트 주기의 배수여야 한다.

즉, 타이머가 5msec마다 인터럽트를 발생시키면 타임 슬라이스는 5, 10, 15등 5msec의 배수가 될 수 있다.

A, B, C 작업이 거의 동시에 들어오고 각각은 5초의 실행 시간을 가지고 있다는 가정으로 STCF와 RR의 결과를 보자.

먼저, STCF는 아래와 같다.

평균 응답 시간은 (0 + 5 + 10) / 3 = 5이다.

 

다음으로 타임 슬라이스를 1sec로 둔 RR으로 스케쥴링으로 하면 아래와 같다.

평균 응답 시간은 (0 + 1 + 2) / 3 = 1로 STCF에 비해 좋은 지표를 가지고 있는 것을 볼 수 있다.

RR의 최대 고려사항은 타임슬라이스의 길이이다.

너무 길게 하면 평균 응답 시간이 좋지 않고 그렇다고 너무 짧게 하면 그만큼 컨텍스트 스위칭이 자주 발생하여 비용이 증가한다.

또한, 반환시간만을 생각해본다면 RR은 FCFS보다 안좋은 스케쥴링이라고 할 수 있다.

---

[오늘의 나는 어땠을까?]

pintos의 시작을 알리는 발제가 월요일이였는데 벌써 토요일이다...

내일이면 첫 주차가 끝나는데 최대한의 효율과 자원이용으로 많은 것을 얻었는가에 대한 의문이 든다.

목표와 계획이 너무 높았던 것일까 아니면 진짜 내가 열심히 안할 것일까

그래도 내일 하루가 남았으니까 이번 주를 정리하면서 내가 배운 것들을 확실히 나의 것으로 만드는 것을 목표로 해야겠다.

조금 더 집중을 해보려고 노력해서 확실하게 행동하자

진짜 시간이 빨리 간다고 느껴지고 이제 정말 얼마 안남았다고 생각한다.

수료 후 목표를 기억하며 꼭 이루도록 하자.