CPU 스케줄링

프로세서 스케줄링 기법

크게 선점 방식과 비선점 방식으로 나눠 볼 수 있다.

 

비선점

이미 할당된 CPU를 다른 프로세스가 강제로 빼앗아 사용할 수 없는 스케줄링 기법이다.

 

프로세스가 CPU를 할당 받으면 해당 프로세스가 완료될 때까지 CPU를 사용하지 않는다.

매우 공정한 방법이지만 우선순위가 높은 프로세스에 대응하기에는 비효율적인 방법이다. 

 

비선점 스케줄링 기법의 종류는 아래와 같다. ⬇️

 

⚪️ FCFS (First Come First Serve / FIFO)

CPU를 먼저 요청한 프로세스가 먼저 CPU를 배정 받는 스케줄링 방법

 

예를 들어서 P1(24ms), P2(3ms), P3(3ms) 프로세스가 있다 가정하면, CPU 스케줄링의 결과는 다음과 같이 표현된다.

 

가장 간단한 방법이지만 평균 대기 시간을 계산하면, (p1(0) + p2(24) + p3(27)) / 3 = 17ms가 된다.

만약, P3가 우선순위가 가장 높은 프로세스였다면 대기 시간이 너무 길기 때문에 효율적이지 못하다.

 

이런식으로 다른 모든 프로세스들이 각 프로세스가 끝날 때까지 기다리는 현상은 convey effect라고 한다.

convey effect는 CPU와 장치들을 비효율적으로 사용하여 사용률을 낮추기 때문에 권장하지 않는 방식이다.

 

 

⚪️ SPN (Shortest Process Next / SJF, Shortest Job First)

준비 큐에서 기다리고 있는 프로세스 중에서 가장 CPU 요구량이 적은 것을 먼저 실행하는 방법

 

평균 응답 시간을 최소화할 수 있지만 실행 시간이 긴 프로세스(= 우선순위가 낮은)가 CPU를 할당받지 못하고 계속해서 대기하는 무한 대기 현상이 발생할 수 있다. 

 

 

⚪️ HRRN (Highest Response Ratio Next)

준비 큐에 있는 프로세스들 중에서 응답률이 가장 높은 프로세스에게 높은 우선순위를 주는 방식

 

응답률 = 대기시간 + CPU 요구량 / CPU 요구량 

*CPU 요구량은 프로세스의 크기라고 봐도 된다.

 

응답률에서 대기시간을 고려하게 되고 이는 무한 대기 현상을 방지하기 위한 장치이다.

 

선점

CPU 사용권을 선점할 수 있는 방식이다.

 

특정 요건에 따라 각 프로세스의 요청이 있을 때 프로세스에게 분배하는 방식으로 가장 자원을 필요로 하는 프로세스에게 CPU를 분배하며 상황에 따라 강제로 회수할 수 있다.

따라서 빠른 응답을 요구하는 대화식 시분할 시스템에 적합하며 긴급한 프로세스를 제어할 수 있다.

 

⚫️ RR (Round-Robin)

FCFS 스케줄링을 기반으로 하여 CPU를 할당하되, 시간 할당량이 존재한다.

 

각 프로세스는 한번에 쓸 수 있는 CPU 시간이 지나면 시간 종료 인터럽트에 의해 CPU를 뺏기게 된다. 

주로 우선순위 스케줄링과 결합해서 프로세스 시간할당량을 조절한다.

(시간 할당량이 너무 많으면 FCFS 방식과 차이가 없고 너무 적으면 문맥 교환의 오버헤드가 발생할 수 있다.)

 

*위의 FCFS 방식에서 프로세스 하나가 CPU를 독점하는 방식을 보완하지만 Context Switch의 오버 헤드가 있다.

 

 

 

⚫️ SRT (Shortest Remaining Time) 

준비 큐에서 완료까지 남은 CPU 요구량이 가장 짧은 것을 먼저 실행하는 방식 

 

실행 도중 남은 실행 시간이 더 적은 프로세스가 준비 큐에 들어오게 되면 현재 실행 중인 것을 중단하고 새로운 프로세스에게 CPU를 할당한다.

 

 

⚫️ 다단계 큐(Multi-level Queue)

프로세스들의 우선순위 개수만큼의 큐가 필요하다. 프로세스들은 자신의 우선순위 값에 해당하는 큐에 들어가게 되며, 우선순위가 낮은 하위 단계 큐의 작업은 실행 중이더라도 상위 단계 큐에 프로세스가 도착하면 CPU를 뺏긴다.

 

정리하자면 .. (Thx to 짱서현, a.k.a 소시서현)

✅ 스케줄링은 크게 비선점, 선점 방식이 있다.
- 비선점: 줬다 뺐지 않음
- 선점: 줬다 뺏음

✅ 스케줄러의 프로세서 101
FCFS: 응 ~ 무조건 먼저 온 프로세스부터 줄거야 ~ 줬다 뺏지 않을게 ~
SPN: 응 ~ 무조건 짧은 프로세스가 먼저야 ~ 줬다 뺏지 않을게 ~
SRT: 응 ~ 무조건 짧은 프로세스가 먼저야 ~ 줬다 뺏을거야 ~
HRRN: 프로세스 긴게 죄는 아니잖아 .. 대기시간 반영한 응답률으로 진행시켜 ~ 줬다 뺏지 않을게 ~
Round-Robin: 먼저 온 프로세스부터 줄게 .. 대신 정해진 시간 안에 못 끝내면 뺏을게 ~ 다른 애들도 기다리니까 다시 줄 서 ~