CH9-2 Uniprocessor Scheduling

Feedback

실행 시간이 긴 프로세스의 우선순위를 낮추는 방식

실행 시간을 예측하지 않고도 실행 시간이 짧은 프로세스한테 우선순위를 줄 수 있는 방식

starvation 발생 가능성이 있다

 

q = 2^i - i는 큐의 번호로, 0번 큐는 2^0: 1시간 실행  가능, 1번 큐는 2^1: 2시간 실행 가능,,, , n번 큐는 2^n: n시간 실행 가능

큐의 번호가 클수록 실행 가능한 시간이 길어져서 starvation 발생 가능성을 줄일 수 있다.

 

Multi-level Feedback Queue

- 여러 개의 피드백 큐를 사용한다.

0번 큐에 있는 프로세스: 아직 한 번도 실행하지 않음

1번 큐에 있는 프로세스: 1초 이상 실행함

2번 큐에 있는 프로세스: 2초 이상 실행함

...

n번 큐에 있는 프로세스: n초 이상 실행함

 

0번 큐에서 나와서 CPU를 차지하고 실행하다가 타임아웃이 되면 1번 큐로 들어간다.

1번 큐에서 나와서 CPU를 차지하고 실행하다가 타임아웃이 되면 2번 큐로 들어간다. (0번 큐가 비어 있는 경우)

...

n번 큐에서 나와서 CPU를 차지하고 실행하다가 타임아웃이 되면 n번 큐로 들어간다. (0번부터 n-1번까지의 큐가 모두 비어 있는 경우)

 

Fair-Share Scheduling

- 하나의 애플리케이션이 여러 프로세스의 묶음으로 동작하는 경우를 가정한다. 

- 개별 프로세스의 성능보다는 자신이 실행하는 애플리케이션 전체의 성능에 더 관심이 있다.

- 만약에 그룹 1에 10개의 프로세스를, 그룹 2에 1개의 프로세스를 실행 중일 때, 일반적인 스케줄링은 그룹 1에게 그룹 2보다 10배 많은 CPU 시간을 할당할 수 있다. 하지만 이 방식은 두 그룹에게 거의 동등한 CPU 시간을 할당하여 그룹 간의 공정성을 맞춘다.

 

그룹 1 애플리케이션: 프로세스 A

그룹 2 애플리케이션: 프로세스 B, 프로세스 C

 

프로세스 A를 실행한 후에 타임아웃이 되면 B, C 중 하나를 실행시킨다.

 

A → B or C → A → B or C ...

 

Traditional UNIX Scheduling (CPU가 1개인 시스템을 가정)

UNIX는 공정성을 가장 중요한 요소로 생각한다. 따라서 예측 가능성이 높고 starvation 발생 가능성이 없다.

 

- 다단계 피드백 큐 구조를 사용하고 같은 우선순위 큐 안에서는 라운드 로빈 방식으로 프로세스를 처리한다. 즉, 같은 레벨의 프로세스들은 공평하게 CPU 시간을 조금씩 나눠 쓴다.

- 큐 내에서 실행되는 방식이 라운드 로빈 방식이라 공정하고 예측 가능한 방식으로 프로세스가 스케줄링된다.

- 1초에 한 번씩 모든 프로세스의 우선순위를 다시 계산하기 때문에 계속 CPU를 많이 사용한 프로세스는 우선순위가 낮아진다.

 

- Base Priority: 프로세스를 고정된 우선순위 그룹으로 나누는 기준

 

swapper (우선순위가 가장 높다)

block I/O device control

character I/O device control

user processes (우선순위가 가장 낮다)

 

- nice: 프로세스의 우선순위를 동적으로 조정할 수 있는 값

- nice 값을 통해 프로세스가 우선순위 그룹 내에서 좀 더 높은 우선순위나 낮은 우선순위를 갖도록 할 수 있다.

 

CPUj(i) = Uj(i-1)/2+Uj(i-2)/4+Uj(i-3)/8+Uj(i-4)/16+ ……

바로 직전의 실제 CPU 사용량에는 가장 큰 가중치인 1/2를 부여한다. 

 

최근 CPU를 많이 쓴 프로세스의 우선순위를 낮추고 최근에 CPU를 많이 사용하지 못한 프로세스의 우선순위를 높여서 골고루 CPU를 사용할 수 있도록 하는 것이 핵심 목표이다.

 

Scheduling Formula

CPU를 많이 쓴 프로세스는 CPU 값이 높아져서 우선순위(P)값이 커지고 결과적으로 실제 우선순위는 낮아진다.