[OS] CPU 스케쥴링

CPU 스케쥴링

• CPU가 하나의 프로세스 작업이 끝나면 다음 프로세스 작업을 수행해야 한다.
• 이때 어떤 프로세스를 다음에 처리할 지 선택하는 알고리즘을 CPU 스케쥴링 알고리즘이라고 한다.
• 상황에 맞게 CPU를 어떤 프로세스에 배정하여 효율적으로 처리하는 가가 중요하다.

Preemptive vs Non-Preemptive

1. Preemptive(선점)

• 프로세스가 CPU를 점유하고 있는 동안 I/O나 인터럽트가 발생하지 않았음에도 다른 프로세스가 해당 CPU를 강제 점유할 수 있다.
• 즉, 프로세스가 정상적으로 수행중인 동안 다른 프로세스가 CPU를 강제로 점유하여 실행할 수 있다.

2. Non-Preemptive(비선점)

• 한 프로세스가 CPU를 점유했다면 I/O나 인터럽트 발생 또는 프로세스가 종료될 때까지 다른 프로세스가 CPU를 점유하지 못하는 것이다.

선점형 스케쥴링

1. SRT(Shortest Remaining Time) 스케쥴링

• 짧은 시간 순서대로 프로세스 수행
• 현재 CPU에서 실행 중인 프로세스의 남은 CPU 버스트 시간 보다 더 짧은 CPU 버스트 시간을 가지는 프로세스가 도착하면 CPU가 선점된다.

2. Round Robin 스케쥴링

• 시분할 시스템의 성질을 이용한 방법
• 일정 시간을 정하여 하나의 프로세스가 이 시간동안 수행하고 다시 대기 상태로 돌아간다.
• 그리고 다음 프로세스 역시 같은 시간 동안 수행한 후, 대기한다. 이러한 작업을 모든 프로세스가 돌아가면서 진행하며, 마지막 프로세스가 끝나면 다시 처음 프로세스로 돌아와서 작업을 반복한다.
• 일정 시간을 Time Quantum(Time Slice)라고 부른다. 일반적으로 10 ~ 100msec 사이의 범위를 갖는다.
• 한 프로세스가 종료되기 전에 time quantum이 끝나면 다른 프로세스에게 CPU를 넘겨주기에 선점형 스케쥴링이 대표적인 예시다.

3. Multi-level Queue 스케쥴링

• 프로세스를 그룹으로 나누어, 각 그룹에 따라 Ready Queue를 여러개 두며, 각 큐마다 다른 규칙을 지정할 수도 있다. (ex. 우선순위, CPU 시간 등)
• 즉, 준비 큐를 여러 개로 분할하여 관리하는 스케쥴리 기법이다.
• 프로세스들이 CPU를 기다리기 위해 한 줄로 서는 게 아니라 여러 줄로 선다.
  

4. Multi-level feedback Queue 스케쥴링

• 기본 개념은 Multi-level Queue와 동일하나, 프로세스가 하나의 큐에서 다른 큐로 이동 가능하다는 점이 다르다.
  

• 위 그림에서 모든 프로세스는 가장 위의 큐에서 CPU의 점유을 대기한다. 이 상태로 진행하다가 이 큐에서 기다리는 시간이 너무 오래 걸리면 아래의 큐로 프로세스를 옮긴다. 이와 같은 방식으로 대기 시간을 조정할 수 있다.

• 만약, 우선순위 순으로 큐를 사용하는 상황에서 우선순위가 낮은 아래의 큐에 있는 프로세스에서 starvation상태가 발생하면 이를 우선순위가 높은 위의 큐로 옮길 수 있다.

• 대부분 상용 운영체제는 여러 개의 큐를 사용하고 각 큐마다 다른 스케쥴링 방식을 사용한다. 프로세스의 성격에 맞는 스케쥴링 방식을 사용하여 최대한 효율을 높일 수 있는 방법을 선택한다.

---

비선점 스케쥴링

1. FCFS(First Come First Server)

• 준비 큐에 먼저 도착한 프로세스가 먼저 CPU를 점유하는 방식
• CPU를 할당 받으면 CPU 버스트가 완료될때까지 CPU를 반환하지 않으며, 할당되엇던 CPU가 반환될때만 스케쥴링이 이루어진다.
  
  
  표는 3개의 프로세스와 각 프로세스가 CPU를 사용하는 시간(Burst Time)을 나타낸다.
  이를 간트 차트로 표현하면 위와 같다. (도착 시간은 모두 0초라고 가정한다.)
  평균 대기 시간은
• Average Waiting Time = 0 + 24 + 27 / 3 = 17msec
  만약, 프로세스가 들어온 순서가 P3, P2, P1이라면 간트차트는 아래와 같이 바뀐다.
  
• Average Waiting Time = 3 + 6+ 0 / 3 = 3msec
  두 경우에서 모든 프로세스가 끝난 시간은 30msec로 같지만, 평균 대기 시간으로 봤을 때는 위의 예제는 17msec이고 아래는 3msec이다.

즉, 들어온 순서로 수행한다고 해서 반드시 효율적이진 않다.

위의 예제처럼 P1, P2, P3 순서로 들어온 경우를 Convey Effect라고 한다.

이는 CPU 시간을 오래 사용하는 프로세스가 먼저 수행되는 동안 나머지 프로세스들은 그만큼 오래 기다리는 것을 뜻한다. P1이 수행되는 동안 P2, P3는 오래 기다리게 된다.

단점

• Convey Effect 발생 : 소요 시간이 긴 프로세스가 짧은 프로세스보다 먼저 도착해서 뒤의 프로세스들이 오래 기다리는 현상.

2. SJF(Shortest-Job First)

• 다른 프로세스가 먼저 도착했더라도 CPU 버스트가 짧은 프로세스에게 CPU를 먼저 할당하는 방식.
• 선점, 비선점 모두 가능하다.
  
  
  위의 간트 차트는 SJF를 사용했다. 평균 대기 시간은 아래와 같다.
• Average Waiting Time = 3 + 9 + 16 + 0 / 4 = 7msec

이번에는 위의 표를 FCSF를 사용해 간트 차트로 나타내고 평균 대기 시간을 보자.

• Average Waiting Time = 0 + 6 + 14 + 21/4 = 10.25msec

SJF가 평균 대기 시간이 더 짧다. 수학적으로 증명되며, 어떠한 예제를 보더라도 SJF가 AWT이 더 짧다는 것을 알 수 있다.

SJF가 가장 효율적인 CPU 스케쥴링 방법 같지만, 매우 비현실적이다.
왜냐? 컴퓨터 환경에서는 프로세스의 CPU 점유 시간을 알 수 없다.
한 프로세스가 실행 중에는 많은 변수가 존재하기에 CPU 점유 시간을 알려면 실제로 수행하여 측정할 수 밖에 없다. 실제 측정한 시간으로 예측하여 SJF를 사용할 수도 있지만, 이는 오버헤드가 매우 큰 작업이다.

3. Priority

• 우선 순위가 높은 프로세스 먼저 선택되는 스케쥴링 알고리즘이다.
• 우선순위는 정수값을 나타내며, 작은 값이 우선 순위가 높다(Linux,Unix기준)
• 선점, 비선점 모두 가능하다.
  
  
  우선순위가 낮은 순서대로 수행한 모습을 간트 차트로 나타냈다.
• Average Waiting Time : 0 + 6 + 16 + 18 + 1 / 5 = 8.2msec

우선순위를 정하는 방법은 크게 내부적인 요소와 외부적인 요소로 나뉜다.

• Internal : time limit, memory requirement, I/O to CPU burst(I/O작업은 길고, CPU 작업은 짧은 프로세스 우선) 등
• External : amount of funds being paid, political factors 등
• 단점 : starvation 현상

CPU의 점유를 오랜 시간 동안 하지 못하는 Starvation현상. Priority 스케쥴링 방식에서 우선순위가 매우 낮은 프로세스가 ready queue에서 대기하고 있다고 가정해보자.

이 프로세스는 아무리 오래 기다려도 CPU를 점유하지 못할 가능성이 매우 크다.
실제 컴퓨터 환경에서는 새로운 프로세스가 자주 ready queue에 들어온다. 이러한 프로세스가 모두 우선순위가 높은 상태라면 이미 기다리고 있던 우선순위가 낮은 프로세스는 하염없이 기다리고만 있는 상태로 남아있을 수 있다.

이를 해결하는 방법 중 하나는 aging이 있다.
ready queue에서 기다리는 동안 일정 시간이 지나면 우선순위를 일정량 높여주는 것이다. 그러면 우선순위가 매우 낮은 프로세스라고 하더라도 기다리는 시간이 길어질수록 우선순위도 계속 높아지므로 수행될 가능성이 커진다.

Reference

• Ready-For-Tech-Interview