도커에서 프로세스 스케줄링 하다가 이전에 정처기에서 학습했던 선점/비선점 스케줄링에 대한 이해도 떨어지는 것 같아 정리할 겸 글을 남긴다.
여기서 스케줄링이란 프로세스가 생성되어 실행될 떄 필요한 시스템의 여러자원을 해당 프로세스에게 할당하는 작업을 뜻 하며, 대기 시간은 최소화 하고 최대한 공평하게 처리하는 것을 목적으로한다. 메모리에 여러개의 프로세스를 올려놓고(=다중 프로그래밍), CPU의 가동시간을 적절히 나누어(=시분할) 각각의 프로세스에게 분배하여 실행되도록한다.
스케줄링에서는 아래와 같이 장기, 중기, 단기 단위가 있다.
프로세스는 아래 5가지의 상태 중 하나를 가진다.
여기서 준비 큐는 준비 상태에 있는 프로세스들을 모아놓은 큐(Queue)이다.
운영체제는 CPU 스케줄러(CPU Scheduler)를 통해 준비 큐에 있는 프로세스 중 한 프로세스를 골라 다음에 실행시킨다.
운영체제가 프로세스를 프로세서에 할당하는 것을 디스패치(Dispatch)라고 한다.
스케쥴링 알고리즘 평가기준은 아래와 같다.
프로세서 스케줄링의 기법에는 크게 아래와 같이 선점(preemptive)/비선점(non-preemptive) 형태가 있다.
먼저, 비선점(non-preemptive) 은 이미 할당된 CPU 를 다른 프로세스가 강제로 빼앗아 사용할 수 없는 스케줄링 기법이다.
프로세스가 CPUS 를 할당 받으면 해당 프로세스가 완료될 때 까지 CPU 를 사용하지 않는다. RDS 로 따지면 테이블에 Lock 을 걸어둔다 이해하면 편하다. 매우 공정한 방법이지만 priority 가 높은 프로세스에 대응하기에는 비효율적인 기법이다.
비선점 기법에 종류로는 크게 아래 종류들이 존재한다.
FCFS 스케줄링 (First Come First Serve Scheduling)
CPU 를 먼저 요청한 프로세스가 먼저 CPU 를 배정 받는 스케줄링 방법이다.
P1(24ms), P2(3ms), P3(3ms) 프로세스가 있다 가정하면, CPU 스케줄링의 결과는 다음과 같이 표현된다.
가장 간단한 방식이지만, 평균 대기 시간(average waiting time) 을 생각해보자, (p1(0) + p2(24) + p3(27)) / 3 = 17ms.
p3 가 priority 가 가장 높은 프로세스였다면, 의미 없는 대기 시간을 기다려야만한다.
p3 가 가장 먼저들어와 먼저 실행될 수 있으나, 이러한 확률에 의존할 필요는 없다.
이런 식으로 다른 모든 프로세스들이 커다란 한 프로세스가 끝날때까지 계속 기다리는 현상을 convey effect 라 한다. convey effect는 CPU와 장치들의 사용률을 낮추기 때문에 되도록이면 지양해야 한다.
SPN(Shortest Process Next) 혹은 Shortest Job First
준비 큐에서 기다리고 있는 프로세스 중에서 가장 CPU 요구량이 적은 것을 먼저 실행시켜 주는 방식이다. 평균 응답 시간을 최소화할 수 있으나, 실행 시간이 긴 프로세스가 CPU를 할당받지 못하고 계속해서 대기하는 무한 대기 현상이 발생할 수 있다.
HRRN(Highest Response Ratio Next)
준비 큐에 있는 프로세스들 중에서 응답률(Response Ratio = (대기시간 + CPU 요구량) / CPU 요구량)이 가장 높은 프로세스에게 높은 우선순위를 주는 방식이다. SPN과 SRT 방식의 약점인 수행 시간이 긴 프로세스의 무한 대기 현상을 방지하기 위한 기법이다
선점(preemptive) 은 CPU 사용권을 선점
한다고 생각하면 이해가 쉽다. 특정 요건에 따라 각 프로세스의 요청이 있을 때 프로세스에게 분배하는 방식이다. 가장 자원을 필요로하는 프로세스에게 CPU 를 분배하며 상황에 따라 강제로 회수할 수 도 있다. 따라서 빠른 응답신을 요하는 대화식 시분할 시스템에 적합하며 긴급한 프로세스를 제어할 수 있다.
라운드 로빈(Round-Robin/RR) 스케줄링
FCFS 스케줄링을 기반으로 하여 CPU를 할당하되, 각 프로세스는 한 번에 쓸 수 있는 CPU 시간 크기(시간 할당량)이 지나면 시간 종료 인터럽트에 의해 CPU를 뺏기게 되는 방식이다. 주로 우선순위 스케줄링(Priority scheduling)과 결합해 프로세스의 시간 할당량을 조절하는 방식으로 활용한다.
단, FCFS에서 프로세스 하나가 CPU를 독점하는 단점을 방지하지만 Context Switch의 오버헤드를 감수해야한다.
SRT(Shortest Remaining Time) 스케줄링
준비 큐에서 완료까지 남은 CPU 요구량이 가장 짧은 것을 먼저 실행시켜주는 방식이다. 실행 도중 남은 실행 시간이 더 적은 프로세스가 준비 큐에 들어올 경우, 현재 실행 중인 것을 중단하고 새 프로세스에게 CPU를 할당한다.
다단계 큐(Multi-level Queue) 스케줄링
프로세스들의 우선순위 개수만큼의 큐가 필요하다. 프로세스들은 자신의 우선순위 값에 해당하는 큐에 들어가게 되며, 우선순위가 낮은 하위 단계 큐의 작업은 실행 중이더라도 상위 단계 큐에 프로세스가 도착하면 CPU를 뺏긴다.