CPU 스케쥴링

CPU 스케쥴링?

작업을 처리하기 위해서 프로세스들에게 CPU를 할당하기 위한 정책을 계획하는 것

 

 

 

cpu 스케줄링 알고리즘

 

비선점형 방식

A프로세스가 CPU를 사용하고 있을 때 우선순위가 더 높은 B프로세스가 들어온다고 하더라도 A프로세스의 CPU를 빼앗지 않고 명령이 끝날 때까지 기다렸다 할당받는 방식

- 문맥 교환의 오버헤드가 적다 

- 모든 프로세스가 골고루 자원을 이용하기 어렵다

 

 

👉 FCFS (First Come First Served) - 준비 큐에 삽입된 순서대로 처리 

단점 : 호위 효과 convoy effect - 실행시간이 긴 프로세스가 앞순서에 오고 뒷순서에 실행시간이 짧은 프로세스가 오게 되면 전체 프로세스들의 평균 대기시간이 늘어나는 현상

 

A의 대기 시간 0 / B의 대기 시간 20  / C의 대기 시간 23

평균 대기 시간 : (0+20+23) / 3 = 14.3

 

 

👉 SJF(Shortest Job First) - 실행시간이 짧은 프로세스의 우선순위를 높여 먼저 처리

- 대기 시간을 최소화 하는데 최적이다.

단점 : 기아 현상 Starvation - 긴 실행 시간을 가진 프로세스가 실행되지 않는 현상

 

A의 대기 시간 4 / B의 대기 시간 1  / C의 대기 시간 0

평균 대기 시간 : (4+1+0) / 3 = 1.6 

 

 

👉 우선순위 - 가장 높은 우선순위를 가진 프로세스를 먼저 처리 

- 오랫동안 대기하는 프로세스들의 우선순위를 점진적으로 증가시키는 aging방식 사용한다.

(aging은 기아 상태를 방지하기 위해 프로세스의 대기 시간을 측정하고, 대기 시간이 긴 프로세스의 우선순위를 높이는 방식)

- 우선순위가 같은 프로세스들은 선입 선처리로 스케줄링이다.

 

 

계산 방법 : 우선순위 = (대기시간 + 실행시간) / 실행시간

 

위 그림에서 우선순위를 계산해 보면,

A = (15 + 5) / 5 = 4

B = (20 + 20) / 20 = 2

C = (5 + 10) / 10 = 1.5

 

큰 값대로 우선순위를 부여하여 A - B - C 순으로 스케줄링된다. 

 

선점형 방식

A프로세스가 실행되고 있는데 특정한 기준에 의해 우선순위가 더 높은 B프로세스가 CPU를 요청하게 되면 A프로세스는 그 즉시 CPU를 사용하지 못하고 뺏기게 되는 방식

- 문맥 교환의 오버헤드가 발생할 수 있다

- 모든 프로세스가 골고루 자원을 이용할 수 있다

 

 

👉 라운드 로빈 - 각 프로세스마다 동일한 할당 시간 부여, 끝나지 않으면 다시 준비 큐에 들어가 처리

- 모든 프로세스가 같은 우선순위를 가진고, 타임 슬라이스를 기반으로 스케줄링한다. (타임 슬라이스 : 각 프로레스가 CPU를 사용할 수 있는 정해진 시간)

- 타임 슬라이스가 너무 크면 FCFS가 되고 너무 작으면 컨텍스트 스위칭이 잦아져 오버헤드 발생한다.

 

 

👉 SRF(Shortest Remaining Time First)  - 처리 중 더 짧은 작업이 들어오면 프로세스 중지 후 짧은 작업 먼저  처리

 

SJF와 차이점? 

SJF는 중간에 시간이 더 짧은 작업이 들어와도 기존의 작업을 모두 수행하지만,

SRF는 중간에 짧은 작업이 들어오면 수행하던 프로세스를 중지하고 들어온 작업을 수행한다.

 

 

👉 다단계 큐 - 우선순위에 따른 준비 큐를 여러 개 사용, 큐마다 다른 스케줄링 적용

- 가장 높은 우선순위 큐가 완료되어야만 그다음 순위의 큐로 넘어갈 수 있다.

- 낮은 우선순위 큐에서 작업 실행 중이더라도 상위 단계의 큐에 프로세스가 도착하면 CPU를 빼앗는다.

- 큐들 간의 프로세스 이동이 불가하기 때문에 스케줄링 부담이 적지만 유연성이 떨어진다.

단점 : 낮은 우선순위의 프로세스는 기아가 발생할 수 있다. 

 

 

👉 다단계 피드백 큐 - 큐 간의 이동이 가능한 다단계 큐 스케줄링 / 다단계 큐 스케줄링의 발전된 형태

- 해당 큐의 시간 할당량(Time Quantum)이 끝나면 한 단계 아래의 준비 큐에 들어간다.

- 결국 자연스럽게 프로세스의 CPU 시간이 길면 우선순위가 낮아지게 된다. 

- 낮은 우선순위 큐에서 너무 오래 기다리면 우선순위를 높인다. (에이징 기법을 통한 기아상태 예방)