[OS] CPU 스케줄링 알고리즘

CPU 스케줄링 알고리즘

1. 선입 선처리 스케줄링
2. 최단 작업 우선 스케줄링
3. 라운드 로빈 스케줄링
4. 최소 잔여 시간 우선 스케줄링
5. 우선순위 스케줄링
6. 다단계 큐 스케줄링
7. 다단계 피드백 큐 스케줄링

---

선입 선처리 스케줄링(FIFO)

• CPU를 먼저 요청한 프로세스부터 CPU 할당
• 준비큐에 삽입된 순서되로 처리되는 비선점형 스케줄링이다.
• 부작용으로 호위효과가 있다.
  • 호위효과 : 다른 프로세스들이 하나의 긴 프로세스가 CPU를 양도하기를 기다리는 것

 

최단 작업 우선 스케줄링(SJF 스케줄링)

• 준비 큐 프로세스 중 CPU 이용시간이 짧은 프로세스부터 실행
• 호위효과를 방지할 수 있다.

 

라운드 로빈 스케줄링

• 선입 선처리 스케줄링에 타임 슬라이스가 지정되어있는 방식이다.
• 레디 큐에 삽입된 순서로 실행하되 타임 슬라이스만큼 실행되며 타임 슬라이스보다 긴 프로세스는 타임아웃으로 다시 준비상태가 된다.
• 선점형 스케줄링 방식이다.

 

최소 잔여 시간 우선 스케줄링(SRT 스케줄링)

• 최단 작업 우선 스케줄링 + 라운드 로빈 스케줄링
• 작업 시간 짧은 프로세스부터 처리하되 타임슬라이스만큼 실행된다.

 

우선순위 스케줄링

• 프로세스마다 우선순위를 부여하며 우선순위가 높은순으로 실행되는 방식
• 최단 작업 우선 스케줄링는 작업 시간 짧은순으로 우선순위 부여한다고 볼 수 있고 최소 잔여 시간 스케줄링은 남은 시간 짧은 순으로 우선순위가 부여된다고 볼 수 있기 때문에 우선순위 스케줄링은 범용적이라고 볼 수 있다.
• 아사현상을 야기할 수 있다.
  • 아사현상 : 우선순위가 높은 프로세스를  실행하느라 우선순위가 낮은 프로세스의 실행이 계속 연기되는 현상
  • 예를들어  각 우선순위가 1 2 5 7 8 인 프로세스가 준비상태에 있을 때 갑자기 우선순위가 높은 프로세스가 준비큐에 들어온다면 뒤에있는 우선순위가 낮은 프로세스가 계속 연기된다.
  • 아사현상을 해결하는 방법은 에이징 기법이다.
  • 에이징 기법 : 대기시간이 점차 길어지면 우선순위를 높히는 방식

 

다단계 큐 스케줄링

• 우선순위별 준비 큐를 여러개 사용하는 방식
• 프로세스 유형별로 큐 구분 가능(CPU 바운드, I/O 바운드, 실시간 프로세스 등)
• 큐 별 다른 스케줄링 알고리즘 적용 가능
• 큐 별 다른 타임슬라이스 적용 가능
• 다단계 큐 스케줄링 방식은 프로세스가 큐 간의 이동이 불가능하기 때문에 아사현상을 야기할 수 있다. 이것을 방지하기 위해 다단계 피드백 큐 스케줄링 방식이 있다.

 

다단계 피드백 큐 스케줄링

• 프로세스가 큐 간의 이동 가능 및 에이징 기법 적용
• 정해진 타임슬라이스동안 실행이 끝나지 않으면 낮은 우선순위 큐로 이동한다. 이후 에이징 기법을 통해 우선순위가 높아지는 식으로 작동한다.
• CPU 바운드 프로세스는 CPU를 점유하는 시간이 길기 때문에 자연스럽게 우선순위가 내려간다. 반대로 I/O 바운드 프로세스는 높은 우선순위에서 끝난다. 그렇기 때문에 CPU 바운드, I/O 바운드 프로세스를 구분할 수 있다.