OS - 02. Processes and Threads (2)

Scheduling

다음에 실행할 프로세스 또는 쓰레드를 선택하는 과정

스케줄링 시점

• 프로세스가 생성될 때
• 프로세스가 종료할 때
• 프로세스가 I/O, Semaphore, 또는 다른 무언가로 대기할 때
• I/O interrupt가 발생할 때
• 선점 스케줄링 알고리즘(preemptive scheduling)의 경우 Clock Interrupt가 발생할 때

스케줄링 오버헤드(문맥교환비용)

• 모드 변경 비용(사용자 > 커널 > 사용자)
• 프로세스 문맥 저장, 복구
• 메모리 맵 저장, 복구
• CPU 캐시 무효화
• 기타

Process Behavior - 프로세스의 실행 형태

• CPU-bound process : 한번실행하면 I/O요청 거의없이 계속 계산만 하는 프로세스.
• I/O-bound process : 잠깐 계산하고 I/O를 요구하는 프로세스. 대부분의 프로그램이 이에 해당한다.(word, chrome, exel, ...)

a: CPU-bound process, b: I/O-bound process

• 프로세스의 우선순위는 CPU-bound < I/O-bound이다! (자원의 활용도를 높이기 위함)

Type of Scheduling

• Long-term scheduling : 사용자가 요구할 때, 즉 프로세스 실행시 바로 실행할지 delay해서 실행할지 등을 결정한다.
• Medium-term scheduling : 현재 실행중인 프로세스가 많을 때(threashing) suspend상태로 변경한다.
• Short-term scheduling : 굉장히 자주 실행되며, 어떤 프로세스를 실행할지 짧은 시간안에 결정한다.
• I/O scheduling : 5장에서..

Queing for Scheduling

Long-term scheduling으로 실행 할 프로세스를 필요한 자원(process Id 등)을 세팅한 다음 Ready Queue에 하나씩 할당한다.

이후 프로세스 실행 과정에서 입출력 요구시 프로세스를 block상태로 만들고 Blocked Queue에 할당한다. Block상태 프로세스는 suspend상태나 ready상태가 될 수 있다.

만약 시스템의 메모리 부족 등을 이유로 Medium-term scheduling이 block, ready중인 프로세스 몇개를 suspend상태로 변경할 수 있다.

Categories of Scheduling Algorithms

• Batch - 하나씩 가져가며 쭉 실행
• Interactive - 번갈아가며 실행
• Real time - 실시간으로 실행. 정해지 시간 내에 응답해야함

각 알고리즘의 주요 목표

• Batch: Throughput(시간당 몇개의 작업을 끝냈는가), Turnaround time(작업이 시작하고 끝날때까지 걸리는시간), CPU utilization이 높아야한다.
• Interactive: Response time이 높아야한다.
• Real-time: 데드라인을 만족하고, 예측가능해야한다.

Scheduling in Batch Systems

• First-come first-served
• Shortest job first
• Shortest remaining time next

First-come first-served

프로세스를 온 순서대로 실행한다. 실행시간이 작은 E의 waiting time이 높다.

Shortest job first

Time:8일때 도착한 프로세스는 C, D, E이기 때문에 가장 수행시간이 짧은 E 먼저 수행된다.

프로세스가 종료될 때 남은 프로세스 중 실행시간이 가장 짧은 프로세스부터 수행한다.

Shortest remaining time next

Time:4일 때 B의 남은 작업시간은 5이고, C의 작업시간은 4이므로 C가먼저 실행된다.

Shortest Job First의 선점(Preemptive)한 스케줄링. 실행하던 작업을 중단한 후에 실행한다.

하지만 긴 작업은 계속 밀려서 서비스가 안되는 starvation이 발생할 수 있다.

Highest Response Ratio Next(HRRN)

프로세스별로 비율을 계산(오른쪽그림)하여 계산 값이 가장 큰 프로세스가 먼저 수행된다. 앞선 알고리즘의 starvation문제를 해결할 수 있다.

Scheduling in Interactive Systems

• Round-robin scheduling
• Priority scheduling
• Multiple queues
• Shortest process next
• Guaranteed scheduling 
• Lottery scheduling
• Fair-share scheduling

Round-robin Scheduling

프로세스가 같은 우선순위일때, 번갈아가며 실행하는 스케줄링 방법. B는 실행되다 자신의 quantum을 다 쓰면 뒤로간다.

a: time quantum이 프로세스 종료시간보다 클 경우, b: time quantum이 프로세스 종료시간보다 짧을 경우(프로세스 종료 전에 문맥교환이 일어나는 경우)

- 프로세스는 자신의 time quantum을 다 사용하기 전에 I/O등을 요구하면 비효율적이다. 그래서 자신의 time quantum을 다 소비하기 전까지는 Ready Queue에 들어가지 않고 Auxiliary Queue에 들어간다. 이후 time quantum을 다 소비한다면 Ready Queue에 들어간다. (우선순위: Ready Queue < Auxiliary Queue) 이를 Virtual Round-Robin방식이라 한다.

 

Virtual Round-Robin

Priority Scheduling

프로세스마다 우선순위를 가진다. 우선순위가 클수록 숫자가 높고, 낮을수록 숫자가 작다.

이때 동일한 우선순위를 가지는 프로세스는 Round-robin방식을 사용하고, 동일한 우선순위의 프로세스를 다 수행하면 다음 우선순위의 프로세스를 수행한다.

Multilevel Feedback Queue (Multi Queue)

• 우선순위가 CPU-bound process < I/O-bound process이도록 하는 스케줄링 방법이다.
• RQ(Ready Queue)0은 우선순위가 가장 높고 RQn은 우선순위가 가장 낮다.
• RQ0에서 프로세스를 하나씩 가져와 처리하는데, 만약 CPU-bound process이면 다음 우선순위 큐로 넣는다.
• RQ0을 다 쓰면 RQ1에서 동작하는데, 이때도 CPU-bound이면 다음우선순위 큐로간다
• 이 과정을 거치면 CPU-bound process는 가장 낮은 우선순위의 Ready Queue로 가게되고 이를 우선순위가 낮아진다고 표현한다.

Feedback Scheduling

Shrot Process Next

예상 실행시간이 가장 짧은 프로세스를 먼저 실행하는 스케줄링 방법이다.

실행시간이 짧은 프로세스는 실행시간이 더 긴 프로세스를 뛰어넘어 먼저 실행한다.

예상 실행시간은 오른쪽의 식과같이 구하고, 이는 과거에 실행했던 실행시간의 평균을 보고 계산하는 방법이다. 식은 마지막 실행시간(Tn)과 그 전의 실행시간의 합(Sn)과 가중치(a)를 곱하는데, 이는 특정 작업이 평균시간보다 더 많이 걸리게 되면 평균이 높아질 수 있지만 식과 같이 계산하면서 변화되는 패턴에 빠르게 대응할 수 있다.

Exponetial Smoothing Coefficients

Guaranteed Scheduling

프로세스마다 CPU시간을 1/n씩 할당하여 실행하도록 보장해주는 스케줄링 방법이다. 이는 리눅스의 Fair Share Scheduling(다다음)에서 쓰인다.

Lottery Scheduling

n값이 랜덤일 때 각 프로세스마다 n%의 실행시간을 가지도록 하는 스케줄링 방법이다. 이때 시행비율을 임의로 조절 가능하다.

Fair-share Scheduling

프로세스마다 "공평한 몫"의 시간을 사용하도록 하는 스케줄링 방법이다.

CPU(i)값과 G(Group)CPU(i)값은 프로세스마다 1/2씩 decay된다.

P(i)값이 가장 작은 프로세스부터 실행되며 GCPU(i)값은 4*Wk(그룹마다 주는 가중치)로 나누어 더한다. 이는 한 프로그램이 프로세스를 여러개(n개)를 사용하면 CPU사용시간이 n배가 되므로 공평하지 않기 때문이다.

Fair-share Scheduling의 예시

1. 프로세스가 실행되면 프로세스의 CPU count가 증가한다.
2. 한 period가 지나면, 각 CPU count에 1/2를 곱한다.
3. 이때 decay로 1/2씩 곱한다.
4. 이후 값이 가장 작은 프로세스를 실행하고, 1번 과정부터 4번과정까지 반복된다.
5. 실행을 안하고 기다리게되면 decay로 우선순위가 다시 높아지게된다. 이는 계속 우선순위가 밀려 실행되지 않는 경우를 방지하고,  aging기능이라 할 수 있다.

Scheduling Mechanism vs Policy

• scheduling mechanism과 scheduling policy를 구분해야한다.
• 커널은 스케줄링 메커니즘을 가지고 있어야한다.
• 커널 알고리즘 또는 유저 프로세스는 scheduling policy를 결정해야한다. (FIFO, RealTime등의 메커니즘을 갖고있다가 지정하면 policy를 집행할 수 있어야 한다.)

Thread Scheduling

a: user-level threads를 스케줄링하는 방법. 커널은 프로세스 2개가 있다고 생각하며 A, B만 번갈아가며 실행하고 있다고 생각한다. 프로세스마다 미니 커널이 있어서 이 미니커널이 알아서 쓰레드를 조작한다.

b: kerner-level threads를 스케줄링하는 방법. 커널이 처음부터 쓰레드를 조작한다.

- 현재는 a의 유저레벨 쓰레드는 생각할 필요가 없다.

Traditional Unix Scheduling

각 priority queue들을 갖고있는 Round-robin방식을 이용해 Multilevel feedback을 사용한다.

한번 동작하면 우선순위가 낮아지고, 실행을 안하고 기다리고 있으면 우선순위가 다시 올라가는 방식이다.

매번 우선순위를 다시 계산하여 Pj(i)값이 작을수록 우선순위가 높다.

 

- 프로세스의 우선순위를 낮추는 경우는 다음과 같다.

• Swapper
• Block I/O device control
• File manipulation
• Character I/O device control
• User processes

- Unix Scheduling은 프로세스별로 특정 밴드(Bands)에 소속되어서 실행하도록 한다. 만약 입출력이 끝나면(깨어나면) 우선순위가 높은 밴드로 가게하여 빨리 처리하도록 한다!

Traditional Unix Scheduling 예시

BSD and SVR3 scheduling

- 프로세스가 실행되는 동안 p_cpu의 값은 증가하게된다.(clock tick increments)

- 매 초마다 모든 프로세스의 우선순위는 재계산된다.

• SVR3: 프로세스가 많아질수록 1/2 decay는 과하게 되어서 결국 대부분의 프로세스가 0이 되어서 구별할 수 없게된다.
• BSD: decay = (2*load_avg) / (2*load_avg + 1)의 식으로 동작하여 실행중인 프로세스의 개수에 따라 값이 정해지도록 한다.

Scheduling Examples

• Linux Scheduling
• Unix Scheduling
• Windows Scheduling

Linux Scheduling

O(1): Linux SCHED_OTHER Scheduling

• I/O-bound process에게 높은 우선순위를 주는 정책이다.
• 태스크(task, 리눅스에서 thread를 부르는 용어)의 실행시간 대비 휴먼시간 비율(sleep_avg)을 유지한다.
• 우선순위와 타임슬라이스 계산식
  effective prio = 인터액티브 정도 + 정적 우선순위
  새로운 타임슬라이스 = effective prio에 비례함
• 인터액티브 태스크는 expired Q가 아닌 active Q에 넣어 또 실행할 수 있도록 한다.
  (원래 태스크의 time slice를 다 소비하면 expired Q에 넣는다)

문제점

• Nice값이 timeslice의 절대값을 결정한다.
• Nice값의 차이가 timeslice 차이에 비례하지 않는다.
• Timeslice와  timertick의 granularity(정밀도)문제가 있다.
• Interactive task의 우선 문제가 있다.
  - sleep에서 깨어나면 무조건 active Q로 들어온다.

CFS 스케줄러

앞선 O(1)의 문제점을 보완하고 개선한 RSDL을 개발하였다.

• I/O-bound와 CPU-bound process의 구분을 없애고 CPU할당시간을 공평하게 분배하였다.
• Run Q를 없애고 RB-tree를 사용하였다.
• Jiffies와 HZ상수를 이용하지 않고 나노초단위로 동작하게(정확히 집행하도록) 하였다.
• 통계적 기법이나 휴리스틱을 이용하지 않았다.

Virtual Runtime

: Time slice와 timertick의 granularity문제를 해결한다.

-> 문맥교환(time slice) 주기가 20ms. 두 태스크가 45ms, 15ms비율로 수행해야하면 실제로는 40ms, 20ms씩 수행한다.

이 수행시간 40ms, 20ms에 scale factor(1:3)을 곱하여 virtual runtime을 구하는데, 40ms, 60ms로 같지 않다면 뒤쳐진 태스크(40ms)를 수행하여(-> 20ms더 수행하면 60ms, 60ms) 시간을 보상한다.

따라서 CFS의 목표는 모든 Virtual Runtime을 균등하도록 하는 것이다!

 

Unix SVR4 Scheduling

- 160개의 우선순위를 가진 스케줄링 Queue를 가진다. 

- Preemption point를 넣어 작동하도록 한다. 

Preemption point: 만약 시스템 호출하여 데이터를 리턴하기 전에 스케줄링한다면 시스템호출+스케줄링의 시간이 많이 길어질 수 있다.

이를 방지하기위해 커널에 preemption point, 즉 스케줄이 되는 지점을 몇개 넣어서 시스템 호출이 되더라도 이 point에 도달하면 급하게 작업할 프로세스(RealTime 등)가 있다면 바로 스케줄하여 작업을 실행하도록 한다.

Windows Scheduling

• 우선순위는 두가지의 band 혹은 class로 나뉜다. - Real time 또는 Variable(Non-Real time)
• 우선순위기반 preemptive scheduler을 사용한다.

Real-time: 31~16, Variable(일반 프로그램): 15~0값과 각각의 Queue를 가진다.

15~0의 일반 프로그램은 한번 동작하면 우선순위가 낮아지고, 실행을 안하고 기다리고 있으면 우선순위가 다시 올라가는 방식을 사용하여 동적으로 할당된다.

Dining Philosophers Problem

식사하는 철학자 문제. 데드락의 동기화 문제를 설명한다.

철학자가 식사하려면 양쪽의 모든 포크를 집어야하고, 어떤 경우는 철학자 모두 식사를 못하고 계속 굶어 죽을 수 있다.