[OStudy] 3주차 - 스케줄링(1)

 이제 본격적인 컴퓨터의 동작 과정에 들어왔습니다. 여러 파트로 나눠지지만, 우선 스케줄링(Scheduling)을 먼저 시작해보죠. 이 스케줄링은 처음 생산관리 분야에서 활용되는 기법이었습니다. 그러다 컴퓨터 시스템이 개발되면서 해당 분야의 스케줄링 기법을 채택하여 적용한 형태죠. 이번 학기에서 막 생산 관리 쪽을 수강하기 시작한 상황이라.. 자세한 내용은 아직 모릅니다. 기회가 되면 향후 보충 하는 쪽으로...

 

워크로드에 대한 가정

 프로세스가 동작하는 일련의 과정을 워크로드(Workload)라고 합니다. 그리고 스케줄링 정책의 고안운, 이 워크로드의 선정에서 시작합니다. 적절한 이해를 위해, 우선은 비현실적이나 간단한 워크로드 가정을 내리고 시작하겠습니다. 해당 내용을 토대로 스케줄링 정책을 구현합니다.

 

 1. 모든 작업의 실행 시간은 동일하다. 

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

 3. 각 작업은 한번 시작되면 중간에 중단되지 않고, 완료될 때까지 실행된다.

 4. 모든 작업은 오직 CPU 자원만 사용한다.

 5. 각 작업의 실행 시간은 스케줄러가 미리 알고 있다.

 

한눈에 봐도, 현실의 컴퓨터와는 상당히 거리가 먼, 매우 단순화된 형태의 워크로드 가정입니다. 물론, 이렇게 단순화를 시켰음에도, 상당한 난이도를 보입니다. 

 

스케줄링 평가

 스케줄링 알고리즘을 구현한다면, 그에 맞는 효율성 평가 근거 자료가 작성 가능해야겠죠. 스케줄링 알고리즘을 평가하기 위한 척도는 여러 기준이 존재하나, 이번 포스팅에서는 반환시간(turnaround time)의 척도만 고려하겠습니다. 이 반환 시간은, 어떤 작업이 시스템에 도착한 시점부터, 완료되는 시점까지 걸린 총 시간을 의미합니다.(반환시간 = 완료시간 - 도착시간) 그리고, 위의 가정 2번, 모든 작업은 동시에 시스템에 도착한다는 가정에 따라, 도착시간은 0으로 설정할 수 있습니다. 즉, 반환시간 = 완료시간 - 0이니 반환시간 = 완료시간, 따라서 작업이 종료된 시간을 기준으로 효율 척도를 정할 수 있습니다. 

 

선입선출(FIFO)

 대표적인 스케줄링 알고리즘 기법에는 선입선출(First In First Out)이 있습니다. 작업의 종류나 중요성 등은 고려하지 않고, 오직 도착한 순서대로 실행하는 방식입니다. 가장 간단하며, 시간적으로 공평한 알고리즘이죠. 하지만 단순한 알고리즘인 만큼, 그 단점 또한 명확합니다. 먼저 도착한 작업이 수행 시간이 매우 긴 경우, 타 작업은 이를 기다려야 하는데, 이러한 부류의 호위 효과(convoy effect)가 선입 선출 기법에서 강한 편입니다. 또한, 비선점형(nonpreemptive) 방식의 스케줄링이기에, 한 프로세스가 CPU를 점유하고 있을 시, 타 프로세스는 이를 차지할 수 없습니다. 그리고 이는 CPU 사용률 감소와 I/O 바운드 프로세스의 대기시간 증가 등의 효과를 일으킵니다. 예를 들어, 작업 A, B, C가 존재하고, C의 경우에는 작업량이 각각 60 100 40이라고 가정한다면,  FIFO 사용 시, 0에서 시작하여 , A가 가장 먼저들어왔으니, 먼저 실행해보겠습니다. 그리고 A의 작업이 종료되면서, 시간은 기존 0에서 90까지 증가했습니다. 그리고 그 다음은 B, 마지막으로 C를 넣습니다. 이후 B가 100~110까지 C가 110~120까지 진행됩니다. C가 가장 작업이 적은데도, 가장 마지막에 완수되는 것을 확인할 수 있습니다. 

 

최단 작업 우선(SJF)

 위의 FIFO가 보여주는 단점을 개선할 수 있는 기법 중 하나입니다. 최단 작업 우선(Shortest Job First)의 경우, 실행시간이 짧은 작업 순으로 업무를 처리합니다.(이 또한 운영연구 분야에서 기초되었습니다.) 가정 2, 모든 작업은 동시에 도착해 가정한다는 기준 하에서는 이 SJF가 가장 최적 알고리즘이기도 합니다. 이 SJF 기법은, 기존 FIFO와 비슷한 복잡성을 보이면서 동시에, FIFO에서는 존재했던 호위효과를 상당 줄여주는 기법입니다. 호위효과가 발생될 가능성이 높을 수록(=시간 비용이 크다는 뜻이니) 후순위에 배치되기 때문에, 어느 정도의 해결이 가능합니다. 물론 완전히 없어지는 것도 아니며, 이것 또한 작업의 중요성보단, 시간적 속도에 치중을 둔 기법이기에 장단점이 뚜렷한 편입니다. 위와 같은 예시로 진행한다면, C 또는 B를 우선으로 0~10, 나머지 하나가 10~20, 그리고 마지막으로 A를 실행합니다. 그리고 해당 내용은 마찬가지로 작업의 질을 따지지 않기 때문에, 간단한 스케줄링 구현 과정에서는 사용할 수 있으나, SJF 만으로 실제 전략을 대체하는건 무리가 있습니다.

 

최소잔여시간 우선(CTCF)

 SJF에서 조금 변형된 버전입니다. 최소 잔여시간 우선(Shortest Time to Completion First) 기법의 경우, SJF와는 다르게, 남아있는 실행 시간을 기준으로 우선순위를 판단합니다. 즉, SJF는 전체 작업의 시간을 판단하며, CTCF는 현재 작업의 남은 시간을 판단합니다. 물론 일종의 변형 형태이기 때문에 호위 효과 등의 문제를 완전히 해소하진 못한 모습입니다. 작업 완료 전까지 교체가 아예 존재하지 않는 방식으로 진행한다면 SJF와 큰 차이를 보이지 않습니다.

 

라운드 로빈(RR)

 응답 시간 문제를 해결하기 위한 알고리즘으로는 라운드 로빈(Round Robin)이 있습니다. 해당 기법에서는, 타임 슬라이싱(time slice)을 이용하여, 각 작업을 쪼개고, 모든 작업이 끝날때까지 이를 반복하는 기법입니다. 물론 이 작업을 슬라이싱 하는 빈도는 초기에 확실하게 잡고 가야 합니다. 문맥 교환에 드는 비용 등이 존재하기 때문에, 무조건 슬라이싱 한다고 해서 정답이 되진 않습니다. 라운드 로빈 기법의 가장 큰 특징은, 모든 작업에 대해 CPU 자원을 동등히 분배함을 의미합니다. 단위를 5 정도로 잡는다면, A B C가 번갈아가며, 5씩 작업을 진행시키고, 5씩 진행될 때마다 다음 작업에게 차례를 넘기는 방식으로 진행할 수 있습니다. A B C 순이라 가정한다면, A 0~5, B 5~10, C 10~15, A 15~20, B 20~25, c 25~30... 이 되며, B와 C가 상당히 빠른 작업 시간 이내에 작업이 완수됨을 확인할 수 있습니다. 물론 이는 문맥 교환 비용 등이 생략되어 있기도합니다. 또한 작업 자체의 질 또한 고려되어야 효과적인 스케줄링 정책을 고안할 수 있습니다. 이는 향후 포스팅에서 다루도록 하겠습니다.