CPU 스케줄링

프로세스는 프로세스 스케줄링을 통해 적절한 CPU에 배치된다고 하였다.

프로세스들은 프로세스 스케줄러에 의해 준비 완료 큐에 놓이게 되며 CPU의 할당을 기다리고 있는다. 이후 단기 스케줄러에 의해 프로세스에게 CPU가 할당되면서 준비 상태에서 실행 상태로 변경된다고 하였다.

​다중 프로그래밍의 목적은 프로세스의 CPU 이용을 최대화하여 사용되지 않는 CPU를 최소화하는 것이라고 하였다. CPU 스케줄링은 CPU 이용률을 최대화하기 위해 준비 완료 큐에 있는 프로세스에게 어떤 기준으로 CPU를 할당할 것인지를 결정하는 방법이다.

​

CPU 스케줄링은 다양한 알고리즘들이 존재한다. 이들의 성능을 비교하는 특성은 CPU 이용률(Utilization), 처리량(Throughput), 총처리 시간(Turnaround time), 대기 시간(Waiting time), 응답 시간(response time) 5가지가 있다.

​CPU 이용률과 처리량을 최대화하고 총처리 시간, 대기 시간, 응답 시간을 최소화하는 것이 바람직할 것이다. 따라서 우리는 상황에 맞게 적절한 CPU 스케줄링 알고리즘을 사용해야 할 것이다.

​그렇다면 어떠한 CPU 스케줄링 알고리즘이 있는지 하나씩 살펴보도록 하자.

​

1. 선입 선처리 스케줄링(First-Come, First-Serverd Scheduling, FCFS)

 

​ㅁ 특징

• CPU를 먼저 요청하는 프로세스가 CPU를 먼저 할당받는 방식
• 비선점형(Non-Preemptive) : CPU가 프로세스에게 할당되면 프로세스가 CPU를 방출할 때까지 CPU를 점유
• 선입선출(FIFO) 큐로 쉽게 구현 및 관리가 가능

 

ㅁ 문제점

• 호위 효과(Convoy Effect) : 비선점형이기 때문에 모든 다른 프로세스들이 하나의 긴 프로세스가 CPU를 양도하기를 기다려야 하는 문제가 발생

​

 

2. 최단 작업 우선 스케줄링(Shortest-Job-First Scheduling, SJF)

 

ㅁ 특징

• CPU가 이용이 가능해지면, 가장 작은 다음 CPU 버스트를 가진 프로세스에게 할당하는 방식
• 두 프로세스가 동일한 길이의 다음 CPU 버스트를 가진다면, 선입 선처리 스케줄링을 적용
• 비선점형(Non-Preemptive)
• 주어진 프로세스 집합에 대해 최소의 평균 대기 시간을 가진다는 점에서 최적
• 다음 CPU 버스트의 길이를 파악하기 힘들기 때문에 장기 스케줄링에서 자주 사용되지만, 단기 스케줄링에서는 힘듬 → 과거의 데이터를 통해 다음 CPU 버스트의 길이를 예측하는 방식을 사용

​

ㅁ 문제점

• 가장 효율적인 방법이지만 CPU 버스트가 긴 프로세스는 CPU를 할당받기가 굉장히 힘듬

​

 

3. 최소 잔여 시간 우선(Shortest Remaining Time First, SRT) - 선점형 SJF

​

ㅁ 특징

• 최단 작업 우선 스케줄링의 선점형 버전
• 현재 실행 중인 프로세스의 남은 시간보다 더 짧은 CPU 버스트를 가진 새로운 프로세스가 준비 완료 큐에 도착하게 되면 현재 실행하고 있는 프로세스의 CPU를 가로챔

​

ㅁ 문제점

• 기아 상태(Starvation) : 특정 프로세스의 우선순위가 낮아서 원하는 자원을 계속 할당받지 못하는 상태

 

 

4. 우선순위 스케줄링(Priority Scheduling)

​

ㅁ 특징

• 가장 높은 우선순위를 가진 프로세스에게 CPU를 할당하는 방식
• 우선순위가 같은 프로세스들은 선입 선처리 스케줄링을 적용
• 선점형(Preemptive) : 새로 도착한 프로세스의 우선순위가 현재 실행되고 있는 프로세스의 우선순위보다 높다면 CPU를 선점
• 비선점형(Non-Preemptive) : 더 높은 우선순위를 가진 프로세스를 준비 완료 큐의 머리 부분에 넣음

​

ㅁ 문제점

• - 기아 상태(Starvation)
• 무한 봉쇄(Indefinite Blocking) : 실행 준비는 되어있으나 CPU를 사용 못 하는 프로세스를 CPU가 무한히 대기하는 상태

​

ㅁ 해결책

• 노화(Aging) : 오랫동안 시스템에서 대기하는 프로세스들의 우선순위를 점진적으로 증가

​

 

5. 라운드 로빈 스케줄링(Round Robin)

​

ㅁ 특징

• 시분할 시스템을 위해 설계된 스케줄링 알고리즘
• 각 프로세스는 동일한 크기의 시간 할당량(Time Quantum) or 시간 조각(Time Slice)을 가짐
• 준비 완료 큐는 원형 큐(Circular Queue)로 동작
• 할당 시간이 지나면 프로세스는 선점당하고 준비 완료 큐의 꼬리에 추가
• 선점형(Preemptive)
• 오직 시간 할당량으로만 프로세스에게 CPU를 할당하기 때문에 모든 프로세스는 공정한 기회를 가짐

 

ㅁ 주의할 점

• 시간 할당량이 문맥 교환 시간에 비해 너무 커지게 되면 선입 선처리 방식과 같아진다. 반대로 너무 작아지면 잦은 문맥 교환으로 성능이 저하된다. 따라서 적당한 시간 할당량을 설정하는 것이 중요하다.