CPU 스케줄링의 종류

CPU 스케줄링의 종류

Context Switching을 할 때 우선순위가 가장 높은 프로세스에게 CPU 자원을 할당해주는 것인데, 이 우선순위를 결정하는 방법은 크게 두가지로 비선점 스케줄링과 선점 스케줄링이다.

 

비선점 스케줄링

• FCFS (First Come First Served)
  • 프로세스가 Ready Queue에 도착한 순서대로 CPU 할당
  • 장점 : 작업 완료 시간으 예측하기 용이하다.
  • 문제점 : CPU처리 시간이 길지만 덜 중요한 작업이, CPU 처리 시간이 짧고 더 중요한 작업을 기다리게 할 수 있다. 이 상태를 호위 상태(Convoy Effect)라고 한다.
• SJF (Shortest Job First)
  • 프로세스의 CPU 처리 시간이 짧은 순서대로 CPU에 할당하는 방식이다.
  • 장점: 모든 방식을 통틀어 평균 대기 시간을 가장 짧게 만드는 방식
  • 문제점: CPU 처리 시간이 긴 프로세스가 계속해서 뒤로 밀려나 영원히 CPU할당을 받지 못하는 기아 상태(Starvation)가 발생한다.
• HRN (Highest Response Ratio Next)
  • SJF 스케줄링 방식에서 발생할 수 있는 기아 상태를 해결하기 위한 방식이다.
  • 우선순위를 단순히 CPU 처리 시간으로 결정하지 않고, Ready Queue에 대기한 시간까지 고려하여 결정한다.
  • 대부분 우선순위를  ( 대기시간 + CPU 처리시간 ) / CPU 처리시간 으로 결정한다.
  • 이처럼 기다린 시간에 비례하여 우선순위를 높이는 방식을 에이징(Aging)기법이라고 한다.
  • 문제점 : HRN 방식은 여러모로 효율적으로 보이지만 프로세스마다 CPU 처리시간을 예측하는 것이 힘들어 사용하기 어렵다.
• 우선순위 (Priority)
  • 대기중인 프로세스들에게 우선순위를 부여하여 높은 순서대로 처리
  • 여기서도 기아상태가 발생할 수 있으므로 에이징 기법 사용
  • 우선순위는 동적 혹은 정적으로 부여할 수 있다.
  • 동적 : 구현이 복잡하고 오버헤드가 많다. 하지만, 시스템의 응답속도를 증가시킨다.
  • 정적 : 동적의 반대

 

 

선점 스케줄링

프로세스가 Running 상태에서 Ready 상태로, 할당받은 CPU 시간을 다 사용하지 않았는데 스케줄러에 의해 강제로 이동될 수 있는 것을 선점 스케줄링이라고 한다.

시분할 시스템에서 사용하는 스케줄링

프로세스의 I/O 요청, I/O 응답, Interrupt 발생, 작업 완료 등의 특별한 상황에서 발생

장점 : 긴급히 처리되어야 할 프로세스를 처리할 수 있다.

문제점 : 비선점 스케줄링 방식에 비해 Context Switching이 자주 발생할 수 있다.

 

• SRT (Shortest Remaining Time)
  • SJF 스케줄링 방식을 선점 스케줄링 방식으로 변경한 기법 
  • 현재 점유중인 프로세스의 남은 시간과 Ready Queue의 실행시간이 가장 짧은 프로세스에게 CPU를 할당하는 기법
• 라운드 로빈 (Round-Robin)
  • FCFS 스케줄링 방식에 선점 스케줄링 방식과 Time Quantum 개념을 추가한 방식
  • 각 프로세스마다 CPU를 연속적으로 사용할 수 있는 시간에 제한을 둔다.
  • Time Quantum을 크게 둘 경우 FCFS와 같이 작동하기 때문에 호위 상태가 발생할 수 있는 문제점이 있다.
  • 작게 둔다면 Context Switching 많이 발생해서 오버헤드가 커지는 문제점이 있다.
• 다단계 큐 (Multi-Level Queue)
  • 프로세스를 특정 그룹으로 분류하고 그룹에 따라 각기 다른 준비상태 큐를 사용한다.
  • 따라서 각 큐마다 다른 스케줄링 방식을 적용할 수도 있다.
  • 사용자와 직접 상호작용하는 Foreground Queue에는 응답 시간을 줄이기 위해 라운르 로빈 스케줄링 방식을 적용하고
  • 백그라운드에서 돌아가는 프로세스들의 집합인 Background Queue에는 응답 시간이 중요하지 않기때문에 FCFS 스케줄링 방식으로 적용하는 등, 각 Queue마다 운영체제가 가장 적절하다고 판단하는 방식을 사용한다.
  • 다단계 큐는 여러개의 Queue를 사용하기 때문에 Queue에 CPU를 얼마나 오래 할당할지 결정하는 스케줄링이 필요하다. 크게 두 가지가 있다.

고정 우선순위 (Fixed Priority)

- Queue마다 우선순위를 두는 방식

- 우선순위가 높은 Queue에 처리해야 할 프로세스가 남아 있다면, 그것을 처리해야만 다음 우선순위의 Queue를 처리한다.

- 문제점 : 우선순위가 낮은 Queue에 있는 프로세스가 무한정 기다려야 하는 상황이 발생할 수 있다.

 

타임 슬라이스 (Time Slice)

- 고정 우선순위 스케줄링 방식에서 기아 상태를 해결하고자 생기 스케줄링 방식

- 운영체제가 Time Slice를 두고, 이 시간 비율에 따라서 각각의 Queue를 서비스하게 된다.

- 예를 들면 CPU 자원의 75%는 Foreground Queue, 25%는 Background Queue를 서비스하는데 할당할 수 있다. 

 

 

• 다단계 피드백 큐 (Multi-Level Feedback Queue)
  • 다단계 큐 스케줄링 방식에 에이징 기법을 적용한 방식이다.
  • 우선순위가 낮은 큐에서 너무 오래 기다린 프로세스의 우선순위를 높은 큐로 옮겨주는 방식
  • 기아상태를 어느정도 해결 할 수 있다.

결론

우리는 컴퓨터를 사용할 때 많은 프로세스들을 동시에 실행한다. 하지만 CPU는 한 번에 한 가지 작업만 처리하기에, 이 프로세스들을 동시에 처리하는 것처럼 보이기 위해 CPU는 어떤 프로세스에게 얼마나 많은 자원, 시간 할당을 해야할 지 결정해야 한다. 이를 결정하는 CPU 스케줄링 방식에 비선점, 선점 방식으로 분류하고 수많은 방식이 존재한다.

멀티스레드의 스케줄링은 운영체제가 처리하지 않기 때문에 프로그래머가 직접 동기화 문제에 대응해야한다.

그러나 CPU 스케줄링은 멀티스레드와는 다르게 운영체제가 사용자도 모르는 사이 자동으로 진행하는 작업이다.

 

 

 

 

출처

• https://velog.io/@raejoonee/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C%EC%9D%98-CPU-%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81
• https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/OS#cpu-%EC%8A%A4%EC%BC%80%EC%A4%84%EB%9F%AC
• https://operatingsystems.tistory.com/entry/OS-Preemption-and-NonPreemption?category=495588