25. CPU 스케줄링 알고리즘

 

출처 : https://www.guru99.com/cpu-scheduling-algorithms.html

1. 선입 선처리 스케줄링

FCFS_first come first served 스케줄링

• 준비 큐에 삽입된 순서대로 처리하는 비선점 스케줄링
• 먼저 CPU에 요청한 프로세스부터 CPU 할당
• 프로세스들이 기다리는 시간이 매우 길어질 수 있다는 부작용= 호위효과

2. 최단 작업 우선 스케줄링

SFF_shortest job First 스케줄링

• 호위효과를 방지하기 위한 방법
• CPU 사용이 긴 프로세스는 나중에 실행, CPU 사용 시간이 짧은 프로세스는 먼저 실행
• CPU 사용 시간이 가장 짧은 프로세스부터 처리하는 스케줄링 방식
• 선점형 비선점형 모두 적용 가능하지만 기본적으로 비선점형 스케줄링에 해당한다.

3. 라운드 로빈 스케줄링

RR_round robin 스케줄링

• 선입선처리 스케줄링 + 타임 슬라이스
• 타임 슬라이스 : 각 프로세스가 CPU를 사용할 수 있는 정해진 시간
• 정해진 타임 슬라이스만큼의 시간 동안 돌아가며 CPU를 이용하는 선점형 스케줄링
  - 큐에 삽입된 프로세스들은 순서대로 CPU를 이용하되 정해진 시간만큼만 이용
  - 정해진 시간을 모두 사용하였음에도 아직 프로세스가 완료되지 않았다면 다시 큐의 맨 뒤에 삽입

4. 최소 잔여 시간 우선 스케줄링

SRT_shortest remaining time 스케줄링

• 최단 작업 우선 스케줄링 + 라운드 로빈 스케줄링
• 최단 작업 우선 스케줄링 : 작업 시간이 짧은 프로세스부터 처리하는 스케줄링 알고리즘
• 라운드 로빈 스케줄링 : 정해진 타임 슬라이스만큼 돌아가며 사용하는 스케줄링 알고리즘
• 정해진 시간만큼 CPU를 이용하되, 다음으로 CPU를 사용할 프로세스로는 남은 작업 시간이 가장 적은 프로세스 선택

5. 우선순위 스케줄링

• 프로세스들에 우선순위를 부여하고, 우선순위 높은 프로세스부터 실행
• 우선순위가 같은 프로세스들은 선입 선처리로 스케줄링
• 최단 작업이 우선 스케줄링, 최소 잔여 시간 스케줄링 < 우선순위 스케줄링
• 우선순위가 높은 프로세스만 계속 실행되고 우선순위가 낮은 프로세스는 계속 실행 연기되는 문제점 발생
• 이를 방지하기 위해 에이징 aging 기법
  - 오랫동안 대시한 프로세스의 우선순위를 점차 높이는 방식으로 대기 중인 프로세스의 우선순위를 점차 증가시키는 방법

6. 다단계 큐 스케줄링

Multilevel queue 스케줄링

• 우선순위 스케줄링의 발전된 형태
• 우선순위별로 준비 큐를 여러 개 사용하는 스케줄링 방식
  - 우선순위가 가장 높은 큐에 있는 프로세스를 먼저 처리하고 그다음 우선순위 큐에 있는 프로세스 처리

7. 다단계 피드백 큐 스케줄링

Multilevel feedback queue 스케줄링

• 다단계 큐 스케줄링의 발전된 형태
• 큐 간의 이동이 가능한 다단계 큐 스케줄링
• 다단계 큐 스케줄링에서는 기본적으로 큐 간의 이동 불가
  - 우선순위 낮은 프로세스는 계속해서 실행이 연기되는 기아 현생 발생
• 어떤 프로세스의 CPU 시간이 길면 우선순위가 낮아지고 낮은 우선순위 큐에 너무 오래 대기하면 우선순위를 높이는 방식
• 구현은 어렵지만 가장 일반적인 CPU 스케줄링 알고리즘으로 사용한다.