CPU 스케줄링

CPU 스케줄링 정의

스케줄링은 컴퓨터의 자원(Resource)을 효율적으로 사용하기 위한 정책을 계획하는 것이다. 특정 자원을 요청하고 있는 프로세스들을 대상으로 CPU 자원을 할당해주는 순서를 정하는 일이다. 프로세스가 생성되어 실행될 때 필요한 시스템의 여러 자원을 해당 프로세스에게 할당하는 작업을 의미하며, 이를 수행하는 것을 스케줄러라고 한다. 프로세스가 생성되어 완료될 때까지 프로세스는 여러 종류의 스케줄링 과정을 거치게 된다. 프로세스 스케줄링 기법에는 비선점(Non-Preemptive) 스케줄링과 선점(Preemptive) 스케줄링이 있다.

 

스케줄링

프로세스 스케줄링 목적

CPU 활용을 극대화해 CPU의 유휴 시간을 최소화 시킨다. 응답시간을 단축해 프로세스 평균 응답 시간 단축시키고, 공평한 자원을 활용해 주어진 기간 동안특정 자원을 효율적으로 사용할 수 있게 한다. 또한 Multi-Tasking 효율적으로 해 다중 프로세스를 공평하게 처이할 수 있도록 한다.

 

---

비선점(Non-Preemptive) 스케줄링

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

[장점] 응답 시간 예상 용이, Batach Process 적합, 프로세스에 대한 요구를 공정하게 처리

[단점] 짧은 작업에도 장기간 대기하는 경우가 발생

 

(1) FCFS(First Come First Service) = FIFO(First In First Out)

대기 큐에 도착한 순서에 따라 CPU를 할당한다. 일단 프로세스가 CPU를 차지하면 완료될 때까지 수행한다. 긴 작업이 짧은 작업을 오랫동안 기다리게 할 수 있으며, 중요하지 않은 작업이 중요한 작업을 기다리게 할 가능성이 존재한다. (대화식 Real Time 시스템에는 부족하다.)

 

(2) SJF(Shortest Job First)

대기 큐에서 기다리고 있는 프로세스들 중에서 실행 시간이 가장 짧은 프로세스에게 먼저 CPU를 할당하는 기법이다. FCFS보다 평균 대기시간을 감소시키는 반면, 큰 작업에 대해서는 FCFS에 비해 대기시간 예측이 어렵다. 비선점형 스케줄링 기법이다.

 

(3) HRN

실행 시간이 긴 프로세스에 불리한 SJF 기법을 보완하기 위한 것으로, 대기 시간과 서비스(실행) 시간을 이용하는 기법이다.

 

(4) 우선 순위

대기 큐에서 기다리는 각 프로세스마다 우선 순위를 부여하여 그 중 가장 높은 프로세스에게 먼저 CPU를 할당하는 기법이다.

 

선점(Preemptive) 스케줄링

[개념] 하나의 프로세스가 CPU를 할당받아 실행하고 있을 때 우선순위가 높은 다른 프로세스가 CPU를 강제로 빼앗아 사용할 수 있는 스케줄링 기법

[장점] 빠른 응답으로 모바일, RTOS에 사용한다. 대화식 시분할 적합.

[단점] Overhead 발생

 

(1) 라운드 로빈(Round-Robin)

FCFS에 의해서 프로세스들이 내보내지며 각 프로세스는 같은 크기의 CPU 시간을 할당한다. CPU 시간이 만료될 때까지 처리를 완료하지 못하면 CPU는 대기중인 다음 프로세스로 넘어가며(Preemptive), 실행 중이던 프로세스는 준비 완료 리스트의 가장 뒤로 보내진다. 즉, 선점형 스케줄링 기법이다.

 

(2) SRT(Shortest Remaining Time)

SJF와 마찬가지로 새로 도착한 프로세스를 포함하여 처리가 완료되는 데까지 가장 짧은 시간이 소요된다고 판단되는 프로세스를 먼저 수행한다. 실행 중인 프로세스라도 남은 처리 시간이 더 짧다고 판단되는 프로세스가 생기면 언제라도 실행중인 프로세스가 선점된다. SJF 방식에 선점 방식을 도입하였으며 실시간 시스템에 유리하다.

 

(3) 다단계 큐(Multi Level Queue)

여러 종류의 그룹으로 나뉘어 여러 개의 큐를 이용하는 스케줄링 기법이다. 그룹화된 작업들은 각각의 준비 큐에 넣어두고 각 큐의 독자적인 스케줄링 알고리즘에 따라서 CPU를 할당받는 방법이다.

 

(4) 다단계 피드백 큐(Multi Level Feedback Queue)

입출력 위주와 CPU 위주인 프로세스의 특성에 따라 서로 다른 타임 슬라이스를 부여한다. 새로운 프로그램이 들어오면 높은 우선순위를 할당해줘 단계 1에서 즉시 수행하고, 점차 낮은 우선순위를 부여하며 단계가 n쯤 되는 나중에는 그 작업이 완료될 때까지 라운드로빈으로 순환한다. Multi Level Feedback Queue는 비선점 기법인 우선순위 Queue와 라운드 로빈을 모두 사용하므로 하이브리드 스케줄링 기법이다.