프로세스 스케줄링

이전 글에서 OS가 CPU를 가상화하는 방법 중 메커니즘에 해당하는 Context Switch에 대해서 알아보았다.
Context Switch를 통해 한정된 CPU에서 많은 프로세스를 짧은 시간 간격으로 번갈아 가면서 실행시킴으로써 우리는 한번에 여러 프로세스가 실행되는 것처럼 느낄 수 있다.
이 글에서는 프로세스가 전환될 때 어떤 프로세스를 선택하는지를 결정하는 프로세스 스케줄링에 대해서 알아보자.

프로세스 스케줄링

어떤 스케줄링 기법이 좋은지 판단하기 위해서는 측정 방법(metric)이 필요하다.

• Turnaround time : 프로세스가 시스템에 도착하여 완료될 때까지 걸린 시간
• Response time : 프로세스가 시스템에 도착하여 처음 실행될 때까지 걸린 시간
• Fairness : 프로세스들의 완료 시간이 비슷한지

여러 metric을 가지고 스케줄링 정책들을 비교할 수 있다.

FIFO

• First In, First Out
• 매우 간단하다
• 문제점
  - 실행 시간이 매우 긴 프로세스가 간발의 차이로 제일 먼저 시스템에 들어온다면?
  - 실행 시간이 짧은 프로세스들은 이전 프로세스가 완료될 때까지 기다려야함 -> 평균 Turnaround time 증가!!
  - 이를 Convoy Effect라고도 한다.
  

SJF

• FIFO의 Turnaround time을 개선하기 위해서 어떻게 하면 좋을까?
  -> 가장 짧은 실행 시간을 가지는 프로세스부터 처리
• 문제점
  - 매우 긴 실행시간을 가지는 프로세스가 가장 먼저 들어오고, 시간이 조금 흐른 뒤에 실행시간이 짧은 프로세스들이 시스템에 들어온다면?
  - 결국 뒤에 들어온 프로세스들은 이전 프로세스가 완료될 때까지 기다려야함
  - Turnaround Time이 개선되었다고 보기 힘들다!

STCF

• SJF의 문제점을 개선하려면 어떻게 하면 좋을까?
  -> SJF에 preemption개념을 추가하자!
• 프로세스가 시스템에 들어올 때, 실행 시간이 가장 적게 남은 프로세스를 실행 시킨다.
• 이렇게 되면 SJF가 Turnaround time을 개선하지 못하는 상황에서도 STCF는 Turnaround time을 개선할 수 있다!
• 문제점
  - STCF는 batch computing에는 좋은 정책이다. (batch computing : 예전에는 매우 큰 job을 할당하고, 다음 날 결과를 확인헀다.)
  - 하지만 interactive한 컴퓨팅 환경에서는 좋다고 보기 힘들다.
  - 사용자는 interactive한 결과를 얻기를 원하기 때문에 Turnaround time이 의미가 없다.
  - 이에 새로운 metric이 등장한다. => response time

Round Robin

• 큐에 프로세스들을 넣어 놓는다.
• 프로세스를 일정 시간(time slice)동안 실행시키고, 시간이 지나면, 큐 안에 있는 다음 프로세스를 실행 -> 이를 반복
  -response time은 엄청나게 좋지만, turnaround time은 좋지 못하다.

Issue : Length of time slice

• time slice의 길이를 줄이면
  • response time은 좋아진다!
  • context switch가 자주 발생하기 때문에 -> 성능 저하
• time slice의 길이를 늘리면
  • response time은 안좋아진다!
  • context switch가 덜 발생함
• trade-off 관계

컴퓨터를 사용할 때 다양한 타입의 Workload가 발생한다.
이에 따른 다양한 policy가 필요하다!
-> batch computing : turnaround time을 줄여야 한다.
-> interactive computing : response time을 줄여야 한다.

위 방법 중에 두 computing 환경에 모두 적합한 정책이 없다.

Multi-Level Feedback Queue (MLFQ)

실제 상황에서는 작업이 batch, interactive한 job들이 섞여 있다!
또한 프로세스가 어떤 타입에 해당하는지도 알 수가 없다!
MLFQ의 목표 : batch -> turnaround time 최적화, interactive -> response time 최적화

MLFQ 기본 규칙

1. 다수의 큐를 가지고 있다. 이 큐는 서로 다른 priority level이다.
2. 높은 큐에 있는 프로세스가 실행됨
3. 같은 큐 안에서는 Round Robin 방식 사용
4. 처음 프로세스가 들어오면 가장 높은 큐에 배정
5. time slice안에 실행 완료되고, CPU 제어권을 내놓으면, 해당 큐에 머무름 -> interactive job
6. time slice안에 완료되지 못하면, priority 내림 -> batch job

MLFQ가 어떻게 job을 구별하나

• MLFQ는 들어온 job의 실행 시간이 짧은지 긴지 알 수가 없다. 그렇기 때문에 가장 높은 priority를 부여한다.
• 높은 큐 일수록 해당 큐에 부여된 time slice가 짧다!
• 그러므로 높은 큐에서 time slice안에 실행이 완료되었다는 것은 interactive한 job일 가능성이 높다
• time slice안에 실행이 완료되지 않았다는 것은 batch한 job일 가능성이 높다. 그러므로 우선 순위를 내린다.
• 이렇게 되면, interactive한 job은 우선 순위가 높은 큐에 존재하게 되고, batch한 job은 낮은 큐에 존재하게 된다.

MLFQ의 문제점

• 매우 많은 interactive한 job이 있다면 -> 실행시간이 긴 job들은 CPU 제어권을 영영 받지 못할 수도 있다. -> starvation
• 그리고 job의 성격이 바뀔 수도 있다. 하지만 한 번 낮은 큐에 간 job은 그 위로는 올라오지 못한다.
• 이를 해결하기 위해 Priority Boost라는 개념이 도입된다.
• Priority Boost : 일정 시간이 흐르면, 모든 job을 가장 위의 queue로 올린다.

MLFQ를 사용하기 위해서는 time slice, priority boost가 실행되는 시간 등 많은 변수들을 조작해야하는데 여기에 쉬운 정답은 존재하지 않는다고 한다.

Proportional-Share Scheduling

turnaround time이나 response time에 최적화되는 스케줄링 기법이 아니라,
각 job들이 CPU의 제어권을 특정 퍼센티지 이상 가질 수 있도록 보장하는 기법이다.
이 기법들은 fairness 로 평가한다.

기본 규칙

• ticket : CPU를 쓸 수 있는 티켓이라고 생각하자. process의 중요도에 따라서 ticket을 배분한다.
• 이 ticket을 어떤 식으로 배분하는지에 따라 스케줄링 정책이 나뉜다.

Lottery Scheduling

• 말그대로 랜덤이다.
• 프로세스에게 티켓을 랜덤으로 배정한다.
• 매우 단순하다.
• 그러나 randomness에 의존하므로 fair하다고 볼수 없다!

Stride Schduling

• Lottery 방식이 randomness에 의존하는 문제점을 해결하기 위해 등장
• 각 프로세스는 stride를 갖는다. stride = ticket 비율의 역수
• 또한 각 프로세스는 pass value를 갖는다. 이는 0으로 초기화되며, 프로세스가 실행될 때마다 stride만큼 증가한다.
• 스케줄러는 가장 낮은 pass value를 갖는 프로세스를 실행한다.
• 티켓을 많이 가지고 있는 프로세스(중요한 프로세스)는 실행될 때마다 작은 stride가 증가하기 때문에 다음 실행에서 우선 순위를 가질 확률이 높다!
• 문제점
  - 스케줄링 도중에 새로운 프로세스가 들어오면?
  - pass value를 0으로 설정하면, 새로 들어온 프로세스가 CPU를 독점할 수도 있다!
  - 이를 방지하기 위해 프로세스가 새로 들어오면 pass value를 최솟값으로 설정한다.

Completely Fair Scheduler (CFS)

CFS에서는 고정된 time slice 개념을 사용하지 않는다.
대신에 vruntime(virtual runtime)이라는 개념을 사용한다.
프로세스가 실행되면, vruntime이 일정 크기만큼 증가하고, 스케줄러는 가장 낮은 vruntime을 갖는 프로세스를 스케줄한다.

고정된 time slice없이 어떻게?

• sched_latency, min_granuality 같은 매개변수를 사용해서 스케줄한다.

• sched_latency : 최소한 process가 한번은 실행될 수 있도록 하는 구간의 길이

• CFS는 sched_latency를 이용하여 time slice를 동적으로 결정한다.

• time slice = sched_latency / 실행중인 프로세스 수
  ex) sched_latency가 48m이고, 4개의 프로세스가 실행되고 있다면, 각 프로세스는 12ms의 time slice를 갖게 된다.

• min_granulairy : time slice의 최솟값을 보장한다

• CFS에서 min_granuality보다 작은 time slice를 배정할 수는 없다!

• 프로세스 수가 너무 많아져, time slice가 작아지면 context switch가 많이 발생해서 성능 저하가 오기 때문에 이를 방지하기 위해!

• vruntime을 증가시킬 때, CFS에서는 nice_value라는 개념을 사용한다

• 프로세스 별로 nice_value값이 정해진다. (-20~ 19)

• CFS는 이 nice_value를 weight에 매핑한다.

• 우선순위에 비례하여 weight값이 커지는 형태다

vruntime_i = vruntime_i + (1024 / weight_i) * runtime_i

(1024 = weight_0)
(runtime_i = 프로세스i가 실제 실행된 시간)
(vruntime_i = 프로세스i의 vruntime)

• 위와 같은 식으로 vruntime이 증가된다.
• CFS는 vruntime을 key로 하는 red-black tree를 사용하여 다음 실행될 프로세스를 O(logN)에 찾는다.
• CFS는 I/O 처리를 따로 하지 않지만, 자연스럽게 I/O에 잘 대응한다.
• I/O로 프로세스가 blocked 상태라면, vruntime이 증가하지 않기 때문에!
• stride scheduling과 비슷하게 starvation을 막기 위해 vruntime을 red-black tree에 있는 vruntime의 최솟값으로 설정한다.
• CFS는 MLFQ보다 조작해야할 parameter 수가 훨씬 작다!