CPU 스케줄링 알고리즘 (CPU Scheduling Algorithms)

운영체제는 CPU 스케줄링을 통해 Ready Queue에 있는 어떤 프로세스에 CPU를 할당할 것인지를 결정한다.

이때 운영체제는 여러 가지 다른 CPU 스케줄링 알고리즘들이 있다. 

 

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

• CPU를 먼저 요청하는 프로세스가 CPU를 먼저 할당받는다. 
• 선입선출(FIFO) Queue로 쉽게 관리할 수 있다.

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

• 일단 CPU가 한 프로세스에 할당되면, 그 프로세스가 종료 또는 I/O 처리를 위해 CPU를 방출할 때까지 CPU를 점유한다. 

(2) 호위 효과(convoy effect)

• 다른 프로세스들이 하나의 긴 프로세스가 CPU를 놓기를 기다리는 것
• 선입 선처리 스케줄링에서는 호위 효과가 발생한다.
• 결론적으로 낮은 CPU와 장치 사용률을 보이게 된다. 

(3) 문제(Problem)

• 한 프로세스가 지나치게 오랫동안 CPU를 점유하는 것을 허용되기 때문에 큰 손해가 발생한다.

 

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

• 각 프로세스의 next CPU burst 길이를 고려한 알고리즘이다.
• CPU가 이용 가능해지면, 가장 작은 next CPU burst를 가진 프로세스에 CPU를 할당한다.
• 두 프로세스가 동일한 길이의 next CPU burst를 가지면, 선입 선처리 스케줄링을 적용한다. 

(1) 최적의 알고리즘

• SJF 스케줄링 알고리즘은 주어진 프로세스 집합에 대해 최소의 평균 대기 시간을 가진다.

(2) 문제(Problem)

• 실행하기 전 next CPU burst의 길이를 완벽하게 예측하기 어렵다.

(3) Next CPU Burst 예측

• 한계를 극복하고자 next CPU burst를 예측한다.
• next CPU burst 길이의 근삿값을 계산한다.
• 지수 평균한 것으로 근삿값을 계산한다.

(4) 최소 잔여 시간 우선 (shortest remaining time first : STCF)

• 선점형 SJF(Preemptive version of SJF)
• 만약 새로운 프로세스가 현재 실행되고 있는 프로세스의 남은 시간보다도 더 짧은 CPU burst를 가지고 있다면 Context Switching 발생한다.

 

3. 라운드 로빈 스케줄링 (Round Robin Scheduling RR)

• 시간 할당량(time quantum), 또는 타임슬라이스(time slice)라고 하는 작은 단위의 시간을 정의한다.
• CPU 스케줄러는 준비 큐를 돌면서 한 프로세스에 한 번의 시간 할당량 동안 CPU를 할당한다.

(1) 실행 두 가지 경우

• 첫 번째, 프로세스의 CPU 버스트가 한 번의 시간 할당량보다 작은 경우
  • 프로세스 자신이 CPU를 자발적으로 방출할 것이다. 스케줄러는 그 후 준비 큐에 있는 다음 프로세스를 진행
• 두 번째, 현재 실행 중인 프로세스의 CPU 버스트가 한 번의 시간 할당량보다 긴 경우
  
  • 시간 할당량 이후에 interrupt 발생, Context Switching이 일어나고 실행하던 프로세스는 다시 준비 큐에 넣어진다. 그 후 스케줄러는 준비 큐의 다음 프로세스를 선택한다.

(2) 선점형

• CPU 버스트가 한 번의 시간 할당량을 초과하면, 프로세스는 선점되고 준비 큐로 되돌아간다. 그러므로 선점형이다.

(3) RR 알고리즘의 성능

• 시간 할당량(time quantum)의 크기에 매우 많은 영향을 받는다.
• 시간 할당량이 매우 크면, RR 알고리즘의 경우 선입 선처리 정책(FCFS)과 비슷해진다.
  • 한 프로세스가 지나치게 오랫동안 CPU를 점유하게 된다.
• 시간 할당량이 매우 적다면, RR 알고리즘은 매우 많은 Context Switching을 야기한다.

(4) 시간 할당량(Time Quantum)과 문맥 교환 시간(Context Switch Time)

• 시간 할당량은 Context Switch time보다 커야 한다.
  • 그렇지 않으면 문맥 교환 오버헤드로 인해 성능이 크게 저하된다.
• 만약 Context Switch time이 시간 할당량의 10%라면, CPU 시간의 약 10%가 Context Switch에 소비되는 것이다.
• 현대 운영체제의 시간 할당량은 10-100 ms, Context-Switch 시간은 10 ms

(5) 총 처리 시간(turnaround time)

• 총 처리 시간 또한 시간 할당량의 크기에 좌우된다.
• 한 프로세스 집합의 평균 총 처리 시간은 시간 할당량의 크기가 증가하더라도 반드시 개선되지는 않는다.

 

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

• CPU는 가장 높은 우선순위를 가진 프로세스에 할당된다.
• 우선순위가 같은 프로세스들은 선입 선처리(FCFS) 순서로 스케줄 된다.
• SJF(최단 작업 우선 스케줄링)은 일반적인 우선순위 스케줄링 알고리즘의 특별한 경우이다. 짧은 실행시간을 우선순위로 가진 경우

(1) 선점형과 비선점형

• 선점형은 새로 도착한 프로세스의 우선순위가 현재 실행되는 프로세스의 우선순위보다 높다면 Context Switching 발생한다.
• 비선점형은 준비 완료 Queue에 새로운 프로세스를 넣는다.

(2) 문제(Problem)

• 기아 상태(Starvation) 또는 무한 봉쇄(indefinite blocking)
  • 우선순위 스케줄링 알고리즘을 사용할 경우 낮은 우선순위 프로세스들이 CPU를 무한히 대기하는 경우가 발생한다.

(3) 해결(Solution)

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

(4) 우선순위 + 라운드 로빈 알고리즘 (Priority with RR Scheduling)

• 우선순위가 가장 높은 프로세스를 실행하고 우선순위가 같은 프로세스들은 라운드 로빈 스케줄링을 사용하여 스케줄 하는 방식이다.

 

5. 다단계 큐 스케줄링 (Multilevel Queue Scheduling)

• 우선순위마다 별도의 Queue를 가진다.
• 우선순위가 가장 높은 큐에서 프로세스를 스케줄 한다.
• 다단계 큐 스케줄링 알고리즘은 프로세스들이 시스템 진입 시에 영구적으로 하나의 큐에 할당된다.
  • 이 때문에 기아(starvation)상태가 발생할 수 있다.
• 준비 큐를 foreground와 background 큐로 나눌 수 있다
  • foreground(interactive)
  • background(batch)
  • Ex) 백그라운드 큐는 FCFS 알고리즘에 의해 스케줄 되는 반면, 포그라운드 큐는 RR 알고리즘에 의해 스케줄 될 수 있다. 

* Example

• 4개의 큐를 가진 다단계 큐 스케줄링 알고리즘의 예
• 각 큐는 낮은 우선순위의 큐보다 절대적인 우선순위를 가진다.
  • 예를 들어, 배치 프로세스가 실행되고 있는데, 대화형 프로세스가 준비 큐에 들어가면 배치 프로세스는 선점될 것이다.

• Foreground, Background 큐는 CPU 시간의 일정량을 받아서 자기 큐에 있는 다양한 프로세스들을 스케줄 한다.
  • 예를 들어, 포그라운드 큐는 RR 스케줄링을 위해 CPU 시간의 80%가 주어지고, 백그라운드 큐는 CPU 시간의 20%를 받아 사용한다.

 

6. 다단계 피드백 큐 스케줄링 (Multilevel Feedback Queue Scheduling)

• 다단계 피드백 큐 스케줄링 알고리즘에서는 프로세스가 큐들 사이를 이동하는 것을 허용한다.

(1) 다단계 피드백 큐 스케줄링의 동작

• 새로운 프로세스는 모두 첫 번째 큐에 들어간다. 그리고 라운드 로빈(RR) 알고리즘으로 동작
• 시간 할당량(time quantum) 안에 끝내지 못하면 낮은 우선순위 큐로 넘어간다.
• 낮은 우선순위의 큐는 FCFS 알고리즘으로 동작하게 되는데 이때 너무 오래 대기하는 프로세스는 높은 우선순위 큐로 이동할 수 있다.
  • 노화(Aging)를 이용해서 기아(starvation) 상태를 예방한다.

(2) 매개변수

• 큐의 개수
• 각 큐를 위한 스케줄링 알고리즘
• 한 프로세스를 높은 우선순위 큐로 올려주는 시기를 결정하는 방법
• 한 프로세스를 낮은 우선순위 큐로 강등시키는 시기를 결정하는 방법
• 프로세스가 서비스를 필요로 할 때 프로세스가 들어갈 큐를 결정하는 방법