CPU 스케줄러

스케줄링 알고리즘 종류

1. 선점 스케줄링 : CPU를 할당받아 실행중인 프로세스로부터 CPU를 선점하여 다른 프로세스에 할당할 수 있는 방식이다. 프로세스 하나가 장시간 동안 프로세서를 독점하는 것을 방지하기 위한 것이다.

• 단순 반복 작업에 유리하며 일괄처리 방식에 적합하다.
• 장점: 우선순위가 높은 프로세스를 빠르게 처리할 수 있으며 비선점 스케줄링에 비해 대기 시간이 짧다. CPU 사용률을 극대화할 수 있으며 적절한 알고리즘을 사용할 경우, 공정성을 높일 수 있다.
• 단점: 복잡한 알고리즘을 필요로해 구조 설계가 어렵다. 스케줄링 동작에 의해 기본적으로 오버헤드가 있으며 문맥교환이 자주 발생해 응답 시간이 오래 걸려 성능에 영향을 미치게 된다.

2. 비선점 스케줄링 : 한 프로세스가 CPU를 할당 받았을 때 CPU스스로 반납할 때까지 계속 사용하도록 허용하는 방법이다.

• 멀티 프로그래밍 환경, 여러 개의 프로그램이 실시간으로 동작하는 환경에서 사용된다.
• 장점: 문맥 교환 발생이 적어 응답시간이 짧다.
• 단점: 공정성이 낮으며 대기시간이 길다. 우선순위에 의해 무한정 대기가 발생할 수 있다. 인터럽트가 발생하여도 CPU를 반환하지 않는 경우가 있어 사용 효율이 줄어든다.

 

2.1 FCFS (First Come First Service) - 비선점 방식

준비 큐에 먼저 도착한 프로세스에게 먼저 CPU를 할당해 준다. CPU를 할당받은 프로세스가 스스로 CPU를 반납할 때까지 CPU를 독점하여 사용하는 비선점 방식이다.

• 장점
  1. 준비 상태 프로세스들의 개수와 크기를 짐작할 수 있다면 각각의 프로세스들이 언제쯤 실행될 수 있을지 예측할 수 있다.
  2. 도착 순서만이 실행순서를 결정짓는 다는 관점에서 공평하다.
• 단점
  1. 평균 응답시간이 길어 대화식 시스템에 적합하지 않다.
  2. 소요시간이 긴 프로세스가 먼저 도착할 경우 효율성이 떨어진다.
• 우선 순위가 동일할 경우의 차선책으로 활용이 가능하다.

 

2.2 SPN (Shortest Process Next) / SJF - 비선점 방식

준비큐에서 기다리고 있는 프로세스 중에서 가장 짧은 (CPU 요구량이 가장 적은) 것을 먼저 실행시켜주는 비선점 방식의 스케줄링이다.

• 장점
  1. 평균 응답시간을 최소화 할 수 있다. 실행해 주어야 할 프로세스 수가 충분할 경우, 처리량에 훌룡한 성능을 보인다.
• 단점
  1. 실행 시간이 긴 프로세스가 CPU를 할당받지 못하고 계속해서 대기하는 무한 대기 현상이 발생할 수 있다. (기아 starvation 상태)
  2. 긴 프로세스일 수록 응답시간의 편차가 커져 예측 가능성이 떨어진다.
• 단점을 해결하기 위해 기다린 시간만큼 우선순위를 높여 실행 가능성을 높여주는 에이징 방법이 있다.
• HRRN 기법이 에이징 방법을 사용하는데 HRRN 기법은 CPU 요구량에 대한 대기 시간의 비율로 계산하여 스케줄링한다.

 

2.3 SRTF (Shortest Remaining Time First) - 선점 방식

SPN을 선점 방식으로 운영하는 스케줄링으로 준비 큐에서 완료까지 남은 CPU 요구량이 가장 짧은 것을 먼저 실행시켜 주는 방식이다. 실행 도중 남은 실행 시간이 더 적은 프로세스가 준비 큐에 들어올 경우 현재 실행 중인 것을 중단하고 새 프로세스에 CPU를 할당하는 선점 방식으로 진행된다.

• 장점
  1. 평균 대기 시간이 최소화된다.
• 단점
  1. 기아 상태의 프로세스가 발생할 수 있다.
  2. 새로운 프로세스가 도달할 때마다 스케줄링을 다시하기 때문에 CPU 사용 시간을 측정할 수 없다.
  3. 오버해드가 증가한다.

 

2.4 Priority Scheduling - 선점 방식

우선순위가 가장 높은 프로세스에게 CPU를 할당하는 선점형 스케줄링이다. 우선 순위는 정수로 표현하며 숫자가 작을수록 우선순위가 높다. 선점형 스케줄링 방식에서는 더 높은 우선순위의 프로세스가 도착하면 실행중인 프로세스를 멈추고 CPU를 선점한다. 비선점형 스케줄링 방식에서는 더 높은 우선순위의 프로세스가 도착한 경우, Ready Queue의 Head에 넣는다.

• 장점
  1. 각 프로세스의 중요성을 정확히 정의할 수 있다.
• 단점
  1. 기아 상태의 프로세스가 발생할 수 있다.
  2. 실행 준비가 되어 있어도 CPU를 사용하지 못하는 무기한 대기가 발생할 수 있다.
• 기다린 시간만큼 우선순위를 높여 실행 가능성을 높여주는 에이징 방법으로 문제를 해결할 수 있다.

 

2.5 Round Robin Scheduling

FCFS 스케줄링 방식을 기반으로 CPU가 할당하되, 각 프로세스는 한 번에 사용할 수 있는 CPU의 시간 크기인 시간 할당량을 사용하고 나면 시간 종료 인터럽트에 의해 CPU를 빼앗기게 되는 선점 방식의 스케줄링이다.

• 장점
  1. 한 프로세스가 CPU를 독점하는 상황을 방지하고 프로세스가 기다리는 시간치 CPU를 사용한 만큼 증가해 공정한 스케줄링이라고 할 수 있다.
  2. 응답시간이 빨라진다.
• 단점
  1. 시간 할당량이 클 경우 FCFS 스케줄링 방식과 같아지게 된다.
  2. 시간 할당량이 작을 경우 문맥 교환이 자주 발생해 문맥교환의 오버헤드가 커진다.
• 일반적으로 시간 할당량의 크기는 10에서 100밀리 초가 적당하다.

 

📚 참고 자료 📚

• OS? Oh Yes!
• 운영체제 내부구조 및 설계원리
• https://github.com/JaeYeopHan/Interview_Question_for_Beginner