20. CPU Scheduling(1)

안녕하세요. 오늘은 CPU Scheduling(스케쥴링)에 대해 알아보겠습니다. 프로세스 포스팅에서 스케쥴링에 대해 언급한 바 있습니다.(제 기억상으로는 context switching관련 issue를 다루면서 언급했던 것 같군요.) 다룰 content부터 소개하겠습니다.

 

Basic Concepts

• Scheduling

 

Scheduling Criteria

 

Scheduling Algorithms

 

Multiple Processor Scheduling

 

이번 포스팅에서는 Basic concepts와 scheduling criteria정도만 살펴보고 다른 내용은 다음 포스팅에서 이어 소개하겠습니다.

 

 

20.01. Basic concepts

어떻게 프로세스에게 CPU 자원을 분배할 것인지에 대한 고민으로부터 시작합니다. Time sharing과 multiprogramming에 대해 배웠었는데요. 이때

 

어떻게 또는 어떤 프로세스(ready 상태의 프로세스)에게 CPU를 allocation할 것인가

 

에 대한 답을 찾기 위해 CPU 스케쥴링은 연구되었습니다. CPU 스케쥴링은 multiprogramming과 time sharing의 목표가 그러했듯

 

CPU 자원을 쉬게(idle) 하지 않고 최대한 활용하는 것

 

입니다. 실제 개인 PC의 CPU는 많이 쉬고(? : 비싼 돈 주고 샀건만...) 있습니다만 클라우드처럼 바쁜 시스템도 있습니다. 공유된 컴퓨팅 차원에서의 CPU 스케쥴링도 아주 훌륭한 연구 주제가 되겠죠. 클라우드 서비스를 이용해보신 분들이라면 CPU Steal에 대해 들어보셨을 겁니다. CPU Steal time은 클라우드 서비스와 물리 서버의 환경 차이에서 발생하는 지표 중 하나인데 가상화된 자원을 분배하는 과정에서 CPU의 자원을 얼마나 빼앗기는지 알려주죠.(CPU Steal time이 높으면 클라우드 서비스에 장애를 유발할 수 있습니다.)

 

CPU Steal time(Interesting topic to study)

 

또한 여러가지 고민해볼 거리를 제공합니다. 커널이 사용하는 CPU시간을 어떻게 고려할지, multi core에서는 어떻게 할지 등이 있겠죠.(물론 이 포스팅에서는 기초적인 내용을 독학하는 수준이라 single cpu, single core를 가정할 것입니다.)

 

20.01.1. 스케쥴링의 종류

CPU의 자원을 누구에게 allocation할지 선택할 때, 즉 CPU 스케쥴링의 결정이 일어나야 할 시점이 언제인지는 process state에 대한 포스팅에서 답을 찾을 수 있습니다. Running하고 있는 프로세스가 다른 state로 바뀌는 경우만 고려해보면 되겠죠.

2021.11.15 - [학부공부/OS_운영체제] - 12. Process(2)

12. Process(2)

[1]I/O를 할 때와 같이 Running에서 Waiting 상태로 바뀔 때, [2]Timer interrput에 의해 Running에서 Ready상태로 바뀔 때 이 2가지 경우에서 스케쥴링의 결정은 이루어져야 합니다.(Wait queue와 Sleep queue는 동의어입니다.)

 

추가로 single cpu, single core를 가정한다고 했는데 run queue가 필요한지 궁금하실 수도 있습니다. 사실 굳이 필요하지는 않지만 ready와 sleep queue가 존재해서 parallel하게 설명하기 위해 설정하는 경우도 있습니다.

 

 

이때 우리는 자발적이냐 비자발적이냐라는 중요한 차이를 알 수 있습니다.

Non-preemptive scheduling

비선점형 스케쥴링은 프로세스가 I/O를 하는 상황에서만 수행되는 스케쥴링입니다. Multiprogramming은 기본적으로 비선점형 스케쥴링이라 OS가 강제로 CPU 사용을 중단시키지 않습니다.

 

Preemptive scheduling

선점형 스케쥴링은 반대로 OS가 CPU를 사용하고 있는 프로세스의 수행을 강제적으로 정지할 수 있는 스케쥴링입니다. Timesharing에서 time quantum을 모두 사용한 경우라면 스케쥴링의 결정이 필요하겠죠. 현재 대부분의 OS는 선점형 스케쥴링입니다. 

 

Non-preemptive scheduling VS Preemptive scheduling

선점형 스케쥴링의 경우 강제적으로 프로세스 context swtiching이 일어나기 때문에 당연히 떠올릴 수 밖에 없는 질문이 있습니다. 바로 공유 data의 consistence 문제입니다. 변경된 data를 저장하기 전에 CPU를 내놓게 될 수도 있습니다.(그럼 data를 저장하고 CPU를 내놓으면 안되냐고요? Data를 저장하는 것과 관련된 instruction이 어디까지 있는지 어떻게 알 수 있는거죠? Decoding되기 이전에 알기는 어렵습니다.) 이는 동기화 이슈로 연결되고 공유 data 접근에 대한 제어가 필요하다는 것을 알 수 있습니다. User mode에서의 preemption은 사용자 프로그램이 OS가 제공하는 동기화 방식을 사용하여 data 일관성 문제가 발생하지 않도록 합니다. Kernel mode에서는 모든 kernel routin이 커널 data를 공유하는데 system call을 통하여 요청된 프로세스의 작업을 처리할 수 있으며 공유 data를 접근하는 kernel routin이 수행되는 와중에 인터럽트로 인해서 다른 kernel routin이 선점되면 data 일관성 유지가 되지 않을 수 있습니다. Kernel mode에서의 문제 발생은 User mode에서의 문제 발생보다 더 큰 영향을 줄 수 있기 때문에 아주 위험합니다. 비선점형 커널에서는 커널 내의 preemption을 허용하지 않기때문에 system call이 완료되거나 I/O Block이 발생할 때까지 기다린 후에 context switching을 수행합니다. 따라서 실시간 컴퓨팅을 지원하는데 부적합합니다. 선점형 커널은 커널 내에서 공유 data 접근에 대한 동기화를 커널에 작성해야 합니다. 즉, kernel은 동기화를 처리하는 최종 종착지라고 할 수 있습니다.

 

 

Dispatcher 이야기를 잠깐하고 가겠습니다. 저번 포스팅에서도 어디선가 이야기한 적 있는데 디스패처는 CPU의 제어권을 CPU 스케쥴러가 택한 프로세스에게 주는 module입니다. Context switching 담당, User mode로 전환을 수행합니다.  이때도 latency가 있기 때문에 context switching이 과도하게 일어나는 것이 좋은 것만은 아닙니다.

 

인터럽트 이야기도 잠깐하고 가자면 인터럽트가 들어오면 handler가 동작하고 handler의 수행이 종료되면 return한다고 설명하였습니다. 사실 이는 2단계로 나뉘는데 인터럽트가 들어오면 handler는 굉장히 짧게 수행되고 나머지 처리는 별도의 task를 만듭니다. 그것도 스케쥴링이 되겠죠. 이를 소프트웨어 인터럽트라고 부릅니다. 이렇게 나누는 이유는 인터럽트 서비스 루틴(ISR)이 처리해야 할 일이 굉장히 많기 때문입니다. 처리할 일이 많으니까 굉장히 짧게 수행하고 나머지는 buttom에서 별도의 task를 만들어 수행하는 방식이죠.

 

I/O를 하게되면 polling을 하던지 DMA를 하던지 인터럽트가 날아오는데요. I/O 시스템 콜 자체는 trap으로 그냥 넘어가지면 만약 sleep으로 넘어가게되면 자발적으로 sleep하게 되고 context switch를 하게 됩니다. I/O가 종료되는 것은 인터럽트에 의해 끝나죠. 그렇다면 I/O를 하는데 context switch가 없을 수도 있을까요?

I/O를 하는데 sleep할 때 문맥교환이 발생합니다. Read할 때 패킷이 안들어오면 sleep하겠죠. 하지만 만약 패킷이 들어와 있으면 그냥 읽고 나갈 수도 있습니다. 

 

 

20.02. Scheduling Criteria

스케쥴링의 목표는 CPU 자원을 최대한 활용하는 것이였습니다. 목표 자체는 그렇지만 기준은 시스템의 요구사항에 따라 달라질 수 있습니다.

 

CPU utilization, Throughput, Response time, Waiting time, Turnaround time, Fairness

 

CPU 활용률은 전체 시스템 시간 중 CPU가 작업을 처리하는 시간의 비율, 처리량은 CPU가 단위시간당 처리하는 프로세스의 수입니다. 응답시간은 프로세스가 입출력을 시작하여 첫 결과가 나오는데까지 걸리는 시간이고 대기시간은 프로세스가 Ready queue에서 대기하는 시간의 총합입니다. Turnaround time은 말 그대로 프로세스가 시작해서 종료될 때까지 걸리는 시간입니다.(ready와 sleep queue에서 기다리는 것 모두 응답시간이고 응답시간은 결과가 나오기 전까지 computation 시간도 포함합니다.)

 

20.02.1. Scheduler design

그럼 위에서 5개의 기준에 대해 살펴보았는데요. 최대의 CPU 사용률, 최대의 처리량, 최소의 응답시간, 최소의 대기시간을 제공한다면 이상적인 스케쥴러일 겁니다. 하지만 모든 조건을 만족시키는 스케쥴러를 만드는 것은 현실적으로 불가능합니다. 이때문에 시스템의 용도에 따라 요구사항에 맞게끔 스케쥴러를 제공하는데요. 개인용 컴퓨터에서는 응답시간, 슈퍼컴퓨터는 CPU 사용률, Workstation과 GPU는 처리량을 중점적으로 요구합니다.(GPU는 원래 렌더링을 많이 하려고 했는데 최근에는 Deep learning processing에도 많이 사용되고 있습니다. 후에 Linux에서 응답시간을 최소화하기 위해 설계된 스케쥴링을 다룰 예정입니다.) 대화형 시스템은 응답시간의 variance를 최소화하는데 이는 합리적이고 예측 가능한 응답시간을 제공하기 위함입니다.

 

20.02.2. Process running cycle

스케쥴링의 종류에 대해서는 다음 포스팅에서 본격적으로 알아보도록하고 프로세스 수행 사이클이 어떻게 되는지에 대해서만 마지막으로 짚고 넘어가겠습니다. 프로세스 수행 사이클은 CPU Burst와 I/O Burst cycle로 나눌 수 있습니다. CPU Burst는 CPU로 연산을 수행하는 것이고 I/O Burst는 I/O처리를 위해 기다리는 것입니다. CPU Burst의 특징에 따라 프로세스를 구별하기도 하는데 CPU burst가 긴 프로세스는 CPU-bound 프로세스 짧은 프로세스는 I/O-bound 프로세스라고 합니다. 어떤 종류의 프로세스가 많은 지에 따라 스케쥴링 기법의 효율성이 달라지겠죠.(결국은 시스템의 용도에 따라 요구사항에 맞게끔 스케쥴러를 제공해야 한다는 말의 반복입니다.)

 

그럼 고려해야 할 사항이 한가지 더 늘어난 것이라 걱정되실수도 있겠지만 다행히도 서로 다른 프로세스, 시스템에도 불구하고 CPU-burst time이 특정한 경향을 보인다는 것이 이미 알려져 있습니다.

참고자료에 graph가 있어 가져와 보았습니다. 즉 대부분 burst duration이 8 millisecond 안이라는 거죠. Time quantum을 실제적으로 얼마 정도로 잡아야할지 정할때 참고할 data로 사용할 수 있습니다. Graph를 보고 CPU burst를 대부분 만족하는 duration을 잡는거죠.(1개의 quantum안에 끝나도록 만들면 ready로 가서 기다렸다가 다시 실행되고를 반복할 필요가 없습니다. 이런 부분은 응답시간 면에서 도움이 됩니다. 이왕이면 한번만에 처리하는 것이 좋겠죠.) 물론 time quantum을 실제로 고정하지는 않습니다.(이 부분에 대해서는 여러분이 생각해보시는 걸 추천드립니다.)

 

한가지만 덧붙이자면 참고자료에서 이 자료가 어느시점에 측정된 자료인지를 알수가 없는데 실제 duration은 기술의 발전에 따라 CPU속도가 빨라지면 차이가 날 수 있습니다. 하지만 분포는 푸아송 분포와 유사한 꼴을 띌테니 한번 들여다 볼 필요가 있는 자료이긴 합니다.

 

 

오늘은 CPU 스케쥴링에 대한 기초적인 내용에 대해서 살펴보았습니다. 스케쥴링이 왜 필요한지, 어떠한 기준이 있는지 소개해드렸는데요. 다음 포스팅에서 스케쥴링 알고리즘에 대해 소개해드리고 각 알고리즘은 어떠한 장단점을 가지는지 살펴보도록 하겠습니다. 궁금하신 부분이나 오류 지적, 감상문(?)은 댓글로 남겨주시면 감사하겠습니다.