프로세스 스케줄링(Process scheduling)

Scheduler?

기본적으로 모든 프로세스는 크게 두 가지 단계로 이루어져 있다. 하나는 CPU만 사용하는 CPU burst 단계, 다른 하나는 I/O(input/output) 작업만 하는 I/O burst 단계이다.

 

각 프로세스는 CPU에 할당되어 작업을 하게 되고, 해당 CPU의 자원을 점유하여 하고자 하는 동작을 실행한다. 문제는 I/O busrt 단계에서는 CPU가 놀게 된다는 점이다.

 

CPU가 노는 시간을 줄이기 위해 고안된 방법이 바로 스케줄링, 이러한 동작을 하는 모듈을 스케줄러라고 한다.

 

목적

프로세스 스케줄링은 다음 두 가지 목적을 위해 존재한다.

1. CPU의 성능을 높인다
2. 프로그램의 성능을 높인다

CPU 입장에서의 성능이란? 다음과 같이 나타낼 수 있다.

• CPU 이용율: 전체 시간 중 쉬지 않고 CPU가 일한 시간
• 처리량: 시간당 수행 완료한 프로세스의 수

즉, CPU는 이용률과 처리량이 높아야 성능이 높다고 할 수 있다.

 

 

프로세스 혹은 프로그램 입장에서의 성능이란 무엇일까?

• 소요 시간: 프로세스가 대기 큐 > 작업 완료까지 걸리는 시간
• 대기 시간: 프로세스가 대기 큐에서 대기한 시간
• 응답 시간: 프로세스가 CPU를 할당받는 데까지 걸린 시간

즉, 소요시간, 대기시간, 응답시간이 낮아야 프로그램의 성능이 높다고 할 수 있다.

 

알고리즘

일단 아래와 같은 가정을 하고 살펴보자

1. 모든 프로세스가 동일한 런타임(수행시간) 가진다
2. 모든 프로세스는 동일하게 도착한다
3. 모든 프로세스가 CPU burst만 한다
4. 이미 프로세스의 런타임이 정해져 있고 cpu가 알고 있다

 

FCFS Scheduling (First Come First Served)

CPU에 오는 순서대로 할당하는 방식. (매우 심플)

FIFO 방식의 큐(Queue)와 동일한 방식이라고 이해해도 좋다.

 

사실 위의 전제조건에서는 어떤 방식을 사용하던 성능상의 차이가 없다.

여기서 1번 전제조건인 모든 프로세스가 동일한 수행시간을 가진다 는 조건이 변경된다면?

 

P1는 즉시 실행, P2, P3은 각각 20,25의 대기 시간을 갖게 되므로 평균 대기 시간이 15가 되어버린다.

어떻게 하면 효율적으로 배치할 수 있을까?

 

 

런타임이 짧은 P2, P3를 앞에 배치했더니 쨔잔! 평균 대기시간이 5로 짧아졌다.

 

위에서 본 바와 같이 하나의 긴 런타임을 가진 프로세스(P1)로 인해 CPU효율성이 낮아지는 문제는 Convoy Effect라고 한다.

이런 문제가 생길 수 있기 때문에 딱 봐도 FIFO 방식의 스케줄러는 한계가 명확하게 드러난다.

 

SJF Scheduling (Shortest Job First)

위에서 본 런타임이 짧은 프로세스를 앞에 배치해서 먼저 실행하는 방식이 바로 SJF 스케줄링이다.

 

이 방식의 장점은, 항상 주어진 프로세스에 대해 최소의 평균 대기 시간을 보장한다는 것이다.

최고의 알고리즘이고 항상 이 방식을 쓰면 좋겠지만… 두 가지 문제가 있다.

1. 런타임이 긴 프로세스(P1)는 계속 뒤로 밀려나는 문제가 생긴다. 마치 백로그에 있는 우선순위(중) 태스크처럼… 이러한 현상을 기아(starvation) 현상이라고 한다.
2. 앞서 했던 4번 전제조건 ‘이미 프로세스의 런타임이 정해져 있고 cpu가 알고 있다’는 상황은 이상적인 상황으로, 일반적으로는 과거의 런타임을 통한 추정만 가능하다.

SJF 스케줄링을 자세히 쪼개보면 두 가지 방식이 있다.

 

Non-preemptive SJF (비선점 방식)

2번 전제조건 ‘모든 프로세스는 동일하게 도착한다’의 조건이 만족되지 않는다면 무슨 일이 일어날까?

도착 시간이 다르다면, 현재 도착한 프로세스 중 가장 런타임이 짧은 프로세스(P1)가 CPU에 할당된다.

한 번 프로세스가 실행되면 완료까지 CPU를 점유하기 때문에 평균 대기시간은 4가 된다.

 

Preemptive SJF(선점 방식)

프로세스를 나누어서 실행할 권한이 CPU에게 있다면 다른 방식을 사용할 수 있는데, 이 방식이 바로 선점 방식이다.

이렇게 프로세스를 잘게 쪼개서 실행할 경우 평균 대기 시간은 3이 된다.

 

도착 시간 0에 실행 가능한 가장 짧은 런타임을 가진 프로세스 P1을 실행하다가, 시간 2가 되었을 때 더 짧은 남은 런타임을 가진 P2를 실행한다. (이 시점에 P1의 남은 런타임은 5) 시간 4가 되었을 때 도착한 P3을 실행한다. (이 시점에 P2의 남은 런타임은 2)

 

이 방식을 SRTF(Shortest Remaining Time First) 혹은 STCF(Shortest Time-to-Completion First)라고도 부른다.

눈치챘을지도 모르지만, P1는 가장 먼저 도착하고 7의 런타임을 가졌으나 가장 마지막에 완료된다. 앞서 말했던 기아 현상이 발생한 것이다.

 

Round Robin (RR) scheduling

세 번째 방식은 각 프로세스가 언제 끝나는지보다 언제 시작되는지를 중요하게 여기는 방식이다.

각 프로세스가 동일한 할당 시간(Time quantum)을 갖고 실행되며, 할당 시간이 끝나면 다시 Ready queue의 뒤로 가서 줄을 선다.

 

이미지로 보면 이해가 바로 된다.

 

도착 순서대로 할당 순서를 돌려가며 큐에 다시 넣기 때문에 기아 현상이 발생하지 않으며, 응답 속도가 빠르다. 다만 평균 소요 시간(Average Turnaround Time)은 길어지는데, 무슨 말인가 하니 P1는 13에, P2는 14에, P3은 15에 끝나는 것이다.

 

FCFS(FIFO) 혹은 SJF 방식이라면 각각 5,10,15 시점에 끝날 동작이 평균적으로 엄청 늦게 끝나게 된다.

 

이 문제는 할당 시간(프로세스를 쪼개는 시간 단위)을 늘려서 보완할 수 있으나 할당 시간의 크기가 커질수록 FCFS 방식과의 차이점이 사라지고, 할당 시간의 단위가 작아질수록 컨텍스트 스위칭의 오버헤드가 커지기 때문에 적절한(?) 할당 시간 배분이 매우 중요해진다.

 

Priority Scheduling

특정 기준으로 프로세스에 우선순위를 부여하고, 우선순위가 높은 프로세스를 CPU 할당하는 방식이다.

역시 우선순위가 낮은 프로세스는 계속 기다리기만 하는 기아 문제가 생길 수 있는데, 이를 방지하기 위해 오래 대기한 프로세스일수록 점점 우선순위를 올려주는 에이징 기법을 사용한다.

 

에이징 기법은 백로그에 쌓인 우선순위 Low 태스크들이 쌓이는 일을 방지하기 위해 적용해 보면 좋은 방법이지 않을까...?

 

독자적인 스케줄링 방식보다는 다른 스케줄링 알고리즘과 결합하여 사용하는 경우가 많다.

 

Multi-Level Queue Scheduling

Multi-Level Queue는 Ready Queue를 여러 개로 분할한 것이다. 각 큐는 독립적인 스케줄링 알고리즘을 가진다.

 

예를 들어, foreground에서 돌아가는 프로그램(메모장 + 그림판)은 응답 시간이 중요하기 때문에 Round Robin 스케줄링으로 동작시키고, background에서 돌아가는 batch task(업데이트, 다운로드 등) 등의 프로그램은 총 소요시간이 중요하기 때문에 FCFS(FIFO) 스케쥴링을 사용하는 것이다.

 

당연한 말이지만 이렇게 만들어진 각 큐에 대해서도 스케줄링이 필요하다.

 

유저가 당장 상호작용하는 foreground 큐의 우선순위를 항상 먼저 둘 수도 있고(이 경우 background 태스크에 대한 기아 현상 발생), Time Slice 방식을 통해 80%는 foreground, 20%는 background에 할당할 수도 있다.

 

프로세스 스케줄러를 보면서 얻은 인사이트

자바스크립트는 단일 스레드이다.(자바스크립트 런타임을 총괄한다면 멀티 쓰레드이지만 콜 스택 자체만 놓고 본다는 전제 하에)

 

React에서는 자바스크립트를 힘들게 쓰는 동작이 있는데, 바로 가상 돔(VDOM)의 diff를 계산하는 작업이다. React 화면 렌더링의 핵심 개념이며 모든 리액트 개발자들은 이 diff를 계산하는 한 사이클이 16ms를 넘지 않게 하기 위해 렌더링 최적화를 한다.

 

diff를 계산하는 로직이 무거워져 16ms를 넘기는 순간, 60 프레임을 보장할 수 없으며 브라우저에서 유저에게 버벅거림을 야기하기 때문이다.

 

무거운 프로젝트일수록 이러한 버벅거림이 심해질 위험성도 늘어나고, 개발자들이 신경 써야 하는 포인트도 늘어난다. React에서도 이러한 문제점을 인지하고 있고, 그래서 React18에서는 내부 구현체를 거의 새로 개발하는 수준의 변경사항을 통해 diff 비교에 사용되는 알고리즘을 스케줄링 방식으로 바꿨다.

 

변경이 즉시 필요하지 않은 일부 상태 변경에 대해서는 별도의 훅(useTransition, useDeferredValue)을 사용해 업데이트에 들어가는 계산을 마치 우선순위 스케줄링 방식과 같이 미룰 수 있다.

 

react18의 소스코드 변경사항 중 가장 큰 변경사항은 기존에 없던 Lane이라는 개념이 추가된 것인데, 이 Lane은 실제 차선을 예시로 들어 만들어진 개념이다.

 

(1차선은 추월차선으로 제일 빠른 속도이며, 2,3차선 순으로 속도가 느려진다.)

리액트는 몇 개의 Lane을 가지고 있을까?

export const TotalLanes = 31;

export const NoLanes: Lanes = /*                        */ 0b0000000000000000000000000000000;
export const NoLane: Lane = /*                          */ 0b0000000000000000000000000000000;

export const SyncHydrationLane: Lane = /*               */ 0b0000000000000000000000000000001;
export const SyncLane: Lane = /*                        */ 0b0000000000000000000000000000010;

export const InputContinuousHydrationLane: Lane = /*    */ 0b0000000000000000000000000000100;
export const InputContinuousLane: Lane = /*             */ 0b0000000000000000000000000001000;

export const DefaultHydrationLane: Lane = /*            */ 0b0000000000000000000000000010000;
export const DefaultLane: Lane = /*                     */ 0b0000000000000000000000000100000;

export const SyncUpdateLanes: Lane = /*                */ 0b0000000000000000000000000101010;

const TransitionHydrationLane: Lane = /*                */ 0b0000000000000000000000001000000;
const TransitionLanes: Lanes = /*                       */ 0b0000000011111111111111110000000;
const TransitionLane1: Lane = /*                        */ 0b0000000000000000000000010000000;
const TransitionLane2: Lane = /*                        */ 0b0000000000000000000000100000000;
const TransitionLane3: Lane = /*                        */ 0b0000000000000000000001000000000;
const TransitionLane4: Lane = /*                        */ 0b0000000000000000000010000000000;
const TransitionLane5: Lane = /*                        */ 0b0000000000000000000100000000000;
const TransitionLane6: Lane = /*                        */ 0b0000000000000000001000000000000;
const TransitionLane7: Lane = /*                        */ 0b0000000000000000010000000000000;
const TransitionLane8: Lane = /*                        */ 0b0000000000000000100000000000000;
const TransitionLane9: Lane = /*                        */ 0b0000000000000001000000000000000;
const TransitionLane10: Lane = /*                       */ 0b0000000000000010000000000000000;
const TransitionLane11: Lane = /*                       */ 0b0000000000000100000000000000000;
const TransitionLane12: Lane = /*                       */ 0b0000000000001000000000000000000;
const TransitionLane13: Lane = /*                       */ 0b0000000000010000000000000000000;
const TransitionLane14: Lane = /*                       */ 0b0000000000100000000000000000000;
const TransitionLane15: Lane = /*                       */ 0b0000000001000000000000000000000;
const TransitionLane16: Lane = /*                       */ 0b0000000010000000000000000000000;

const RetryLanes: Lanes = /*                            */ 0b0000111100000000000000000000000;
const RetryLane1: Lane = /*                             */ 0b0000000100000000000000000000000;
const RetryLane2: Lane = /*                             */ 0b0000001000000000000000000000000;
const RetryLane3: Lane = /*                             */ 0b0000010000000000000000000000000;
const RetryLane4: Lane = /*                             */ 0b0000100000000000000000000000000;

export const SomeRetryLane: Lane = RetryLane1;

export const SelectiveHydrationLane: Lane = /*          */ 0b0001000000000000000000000000000;

const NonIdleLanes: Lanes = /*                          */ 0b0001111111111111111111111111111;

export const IdleHydrationLane: Lane = /*               */ 0b0010000000000000000000000000000;
export const IdleLane: Lane = /*                        */ 0b0100000000000000000000000000000;

export const OffscreenLane: Lane = /*

리액트 내부에는 총 31개의 Lane을 가지고 있으며 각 Lane은 비트 연산을 통해 실제 로직에서 활용된다.

export function getHighestPriorityLane(lanes: Lanes): Lane {
  return lanes & -lanes;
}

export function pickArbitraryLane(lanes: Lanes): Lane {
  return getHighestPriorityLane(lanes);
}

function pickArbitraryLaneIndex(lanes: Lanes) {
  return 31 - clz32(lanes);
}

function laneToIndex(lane: Lane) {
  return pickArbitraryLaneIndex(lane);
}

export function includesSomeLane(a: Lanes | Lane, b: Lanes | Lane): boolean {
  return (a & b) !== NoLanes;
}

export function isSubsetOfLanes(set: Lanes, subset: Lanes | Lane): boolean {
  return (set & subset) === subset;
}

export function mergeLanes(a: Lanes | Lane, b: Lanes | Lane): Lanes {
  return a | b;
}

export function removeLanes(set: Lanes, subset: Lanes | Lane): Lanes {
  return set & ~subset;
}

export function intersectLanes(a: Lanes | Lane, b: Lanes | Lane): Lanes {
  return a & b;
}

 

useTransition 등의 훅을 활용해서 특정 동작을 동시성 렌더링(Concurrency Feature Render)으로 바꾸게 된다면, 해당 동작은 TransitionLane으로 들어가게 된다.

 

리액트의 내부 구현체에서 렌더링을 하며 TransitionLane은 늘 SyncLane 내부에 스케줄링된 업데이트 동작이 끝난 이후에 실행되게 된다.

 

사실 React18 구현에 대한 코드를 예전에 본 적이 있는데, Lane 개념에 대해서 와닿지 않는 부분이 있었다. 그런데 프로세스 스케줄링에 대해 학습을 하는 과정에서 React 개발자들이 어떤 콘셉트에서 영감을 받았는지 짐작할 수 있었다. 각 Lane은 결국 이름만 다른 하나의 Queue로, Multi-Level Queue Scheduling에서 영감을 받아 동시성 기능을 구현했다고 생각한다.

 

참조

https://johngrib.github.io/wiki/jargon/convoy-effect/

Convoy effect

https://www.tutorialspoint.com/operating_system/os_process_scheduling.htm

Operating System - Process Scheduling

https://zoomkoding.github.io/os/2019/04/28/os-5.html

줌코딩의 코딩일기

https://rebro.kr/175

[운영체제(OS)] 5. 프로세스 스케줄링(Process Scheduling)