[TIL 38일차] OS의 스케줄링

전에 적었던 운영체제에 가상화에 제한적 직접 실행원리를 어느정도 이해했다면 이제 스케줄링을 봐보자.

스케줄링은 정책에 의해서 돌아가는데 여기서 말하는 정책 -> 원칙(discipline)이라고도 표현가능하다.

스케줄링의 기원은 컴퓨터의 등장 이전으로 간다.

이거는 생산 관리분야에서 나온 개발방법이다.

생산 공정이나 기타 많은 인간의 행동에서 스케줄링이 필요하고 효율성 향사등, 공통된 문제가 존재한다.

워크로드에 대한 가정

먼저 프로세스 동작에 대한 몇 가지 가정을 하고 시작하는데  프로세스가 동작하는 일련의 행위를 워크로드라 한다.

이는 매우 중요한 부분이다. 알고가자.

스케줄링의 평가항목

1. 반환 시간(turnaround time)이라는 스케줄러를 평가하는 기준

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

즉 turnaround time = completion - arrival 이다.

모든 작업은 동시에 도착한다고 가정했고, arrival = 0이라고 가정할 수 있다.

선입 선출

가장 기본적인 알고리즘으로 FIFO(First in FIrst out) 또는 선도착선처리 스케줄링이다.(First come First Served) 이라고도 불린다.

이는 많은 장점을 가지고 있는데, 단순하고 구현이 쉽다는 것, 그리고 동작하기 쉽다는 것.

근데 그렇게 좋다고는 못하는 이유는 A = 100 , B= 10 , C = 10이라고 하면

A가 먼저 들어왔으니 B,C는 빨리 끝낼수도 있는데 A의 100초를 강제로 기다려야한다.

그러면 반환시간은 = (100 + 110 + 120) / 3 = 110이 된다.

이 현상을 convoy effect라 부른다.  => CPU를 오랫동안 사용하는 프로세스가 끝나기를 기다리는 현상

그렇다면 더 좋은 알고리즘은 뭐가 있을까?

최단 작업 우선

이는 가장 짧은 작업을 가장 먼저 처리하는 것이다.

이는 선입선출보다는 A = 100 , B = 10 , C = 10 와 같은 상황에서 더 나은 성능이 나올것이다.

B , C ,A 순으로 처리하니 

(10 + 20 + 120) / 3 => 50 이 나온다.

이는 모든 작업이 **동시에** 도착한다고 하면 최적의 알고리즘임을 증명 할 수 있다.

근데 이 가정 자체가 컴퓨터 세계에서는 불가능 한 가정이다.

A가 먼저 시작된 후에 B,C가 들어온다고 하면 의미가 없어지니.....

예전 일괄처리 시절에는 이처럼 비선점(non-preemptive) 스케줄러가 개발되었다.

현대는 선점 방식을 사용하고 선점 방식을 사용하는것을 알수있다.

문맥 교환을 통해서....

최소 잔여시간 우선

최단 잔여 시간 우선(Shortest Time - to - Completion FIrst)STCF 또는 최단 작업 우선(PSJF)라 한다.

이는 작업이 중단 될 수 있다는 가정을 하면(문맥 교환이 가능) 중간에 작업이 스위치가 가능하다.

좀전에 예시에서는 A의 실행을 중지하고 B와 C를 실행이 끝날 때 까지 대기 시킨다.

그러면 이 또한 위의 가정에서는 최적의 알고리즘이라고 판단할 수 있다.

근데 여기서 새로운 평가 기준을 넣어보자

새로운 평가 기준 : 응답시간

작업의 길이를 미리 알고 있고, 작업이 오직 CPU만 사용하며, 평가 기준이 반환 시간 하나라면 STCF는 매우 훌륭한 알고리즘이다. 초기 일괄처리 시스템에서는 이러한 스케줄링 알고리즘이 의미가 있었으나 시분할 시스템의 등장이 모든 것을 바꾸어 놓았다.

시스템에게 상호작용을 원활히 하기 위한 성능이 요구되었다.

응답시간(response time)이라는 새로운 평가 기준이 태어나게 된다.

이는 작업이 도착하는 시점부터 처음 스케줄 될 떄까지의 시간을 정의한다.

그러면 response = firsturn - arrival 이된다.

그러면 좀전 같은 경우 A가 작업이 계속 밀리게 된다.

B,C와 같은 짧은애들이 들어오면....

라운드 로빈 

응답 시간의 문제를 해결하기 위해 라운드 로빈 스케줄링이 도입된다.

RR은 작업이 끝날때 까지 기다리지 않는다.

일정 시간 동안 실행한 후 실행 큐의 다음 작업으로 이동한다.

이때 작업이 실행 되는 일정 시간을 타임 슬라이스(time slice) 또는 스케줄링 퀀텀(scheduling quantum) 이라 불린다.

작업이 완료 할 때 까지 계속 진행 되서 타임 슬라이싱(time slicing)이라 불리기도 함.

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

10 mec 마다 인터럽트를 발생 시킨다면 타임 슬라이스는 10 ,20 등 배수가 되어야한다.

그렇게 모두에게 공평하게 응답시간을 줄수있는데 이 타임 슬라이스 길이를 잘 계산 해야한다. 그렇지 않으면 문맥전환에 비용이 더 크게 들어가기 때문에 이 문맥 전환 비용을 상쇄할 정도로 잘 짜야한다. 그렇다고 길어서는 안된다. 문맥 전환 비용에는 레지스터 저장 / 복원 만이 있는것이 아니라 CPU 캐시 , TLB, 분기 예측 등을 비롯해 하드웨어에도 프로그램 관련된 다양한 작업 정보들이 저장되어있다.

즉 RR은 공정한 정책을 내놔야한다.

작은 시간 단위로 CPU를 분배하는 정책은 반환 시간과 같은 평가 기준에서는 성능이 나쁘다. 그리고 불공정하게 한다면 하나의 작업을 끝까지 실행하고 종료할 수 있지만 나머지 작업들에 대한 응답 시간은 포기해야한다.

이는 케이크를 먹으면서 보존 하는것과 같은 상황이다.

입출력 연산의 고려

모든 프로그램은 입출력 작업을 수행한다. 아무런 입력도 받아들이지 않는 프로그램을 생각해보자.

매번 동일한 내용이 출력될 것이다.

아무도 보는 이 없는 숲에서 나무가 쓰러지는 것과 같다. 프로그램 실행의 의미가 없다.

현재 실행중인 프로세스가 입출력 작업을 요청한 경우 스케줄러는 다음에 어떤 작업을 실행할지를 결정한다.

현재 실행 중인 작업은 입출력이 완료될 때까지 CPU를 사용하지 않을 것이기 떄문이다.(I/O장치를 사용)

입출력 요청을 발생시킨 작업은 입출력 완료를 기다리며 대기 상태가 된다.

입출력 요청이 하드 디스크 드라이브에 보내진 경우, 프로세스는 드라이브의 현재 입출력 워크로드에 따라 몇 초 또는 좀 더 긴 시간동안 블록 될 것이다.

입출력이 완료되면 인터럽트를 발생시켜 해당 프로세스가 실행 큐로 들어간다.

만약 A,B의 프로세스가 있고 A는 입출력이 있다면 A가 입출력이 들어갔을떄 B를 사용하지 않으면 비효율적이기 때문에 입출력을 고려하여 중첩을 통해 자원을 효율적으로 사용해야한다.

만병 통치약은 없다.(No More Oracle)

입출력을 고려한 기본적인 접근 방식에 대해 논의했으며, 마지막 가정에 대해 생각해보자. 스케줄러가 각 작업의 실행 시간을 알고 있다는 가정이다.

우릭 사용한 가정중 가장 현실과 거리가 있는 가정이다.

일반적인 운영체제에서 작업의 길이를 미리 알 수 있는 방법은 없다.

SJF,STCF 처럼 행동하는 알고리즘과 RR 스케줄러의 아이디어를 도입하는 방법을 생각해보자.

요약

스케줄링의 기본적인 접근법을 알아보았다.

첫 번째는 남아있는 작업 중 실행 시간이 제일 짧은 작업을 수행하고 ,평균 반환 시간을 최소화 해야한다.
두 번째는 모든 작업을 번갈아 가면서 실행해야하고 응답시간을 최소화 해야한다. 반환 시간과 응답 시간 중 하나를 최적화하면 나머지 하나는 좋지 않는 특성이 나타난다. 이는 적절한 절충이 필요하다.

멀티 레벨 피드백 큐(multi-level feedback queue)와 같은 특정 레벨을 부스팅 하고 강등하는 과정을 가지는 스케줄링도 따로 공부해보는 것도 좋을 것 같다.