Operating System
[Operating System] CPU 스케줄링 : 알고리즘
WebDevLee
2024. 5. 19. 20:55
다양한 CPU 스케줄링 알고리즘에 대해 정리하였습니다.
참조 : 인프런 '개발자를 위한 컴퓨터공학 1: 혼자 공부하는 컴퓨터구조 + 운영체제'
< 선입 선처리 스케줄링 >
FCFS (First Come First Served) 스케줄링
- 준비 큐에 삽입된 순서대로 처리하는 비선점형 스케줄링 방식
- 먼저 CPU를 요청한 프로세스부터 CPU 할당
[ 단점 ] : 프로세스들이 기다리는 시간이 매우 길어질 수 있다( = 호위 효과)는 부작용이 있습니다.
< 최단 작업 우선 스케줄링 >
SJF (Shortest Job First) 스케줄링
- 선입 선처리 스케줄링의 호위 효과를 방지하기 위한 스케줄링
- CPU 사용이 긴 프로세스는 나중에 실행, CPU 사용 시간이 짧은 프로세스는 먼저 실행
- 기본적으로 비선점형 스케줄링이지만, 선점형 스케줄링 방식으로도 구현할 수 있습니다.
[ 장점 ] : 호위 효과를 방지할 수 있습니다.
< 라운드 로빈 스케줄링 >
RR (Round Robin) 스케줄링
- 선입 선처리 + 타임 슬라이스 (time slie) 방식의 선점형 스케줄링
(타임 슬라이스 : 각 프로세스가 cpu를 사용할 수 있는 정해신 시간) - 정해진 타임 슬라이스만큼의 시간 동안 돌아가며 CPU를 이용하는 방식
- 정해진 시간동안에 완료되지 않았다면 다시 큐의 맨 뒤에 삽입(문맥교환)
: 라운드 로빈 스케줄링에서는 타임 슬라이스의 크기가 중요합니다.
< 최소 잔여 시간 우선 스케줄링 >
SRT (Shortest Remaining Time) 스케줄링
- 최단 작업 우선 + 라운드 로빈 방식의 선점형 스케줄링
- 정해진 시간만큼 CPU를 이용하되, 다음으로 CPU를 사용할 프로세스로는 남은 작업 시간이 가장 적은 프로세스 선택
< 우선순위 스케줄링 >
PS ( Priority Scheduling ) 스케줄링
- 프로세스들에 우선순위를 부여하고, 우선순위 높은 프로세스부터 실행
(우선순위가 같은 프로세스들은 선입 선처리로 스케줄링) - 최단작업 우선 스케줄링과 최소잔여 시간 스케줄링 방식은 모두 우선순위 스케줄링 방식에 포함됩니다.
- 선점형 스케줄링과 비선점형 스케줄링 방식 모두 구현이 가능합니다.
[ 단점 ] : 우선순위 높은 프로세스 먼저 실행하기 때문에, 우선순위가 낮은 프로세스는 계속해서 실행이 연기되는 기아(starvation) 현상이 발생할 수 있습니다. 이를 방지하기 위해 에이징(Aging) 기법을 도입할 수 있습니다.
[ 에이징(Aging) 기법 ]
: 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식
< 다단계 큐 스케줄링 >
MQS ( Multilevel Queue Scheduling ) 스케줄링
- 우선순위별로 준비 큐를 여러 개 사용하는 우선순위 스케줄링의 발전된 형태
- 우선순위가 가장 높은 큐에 있는 프로세스를 먼저 처리, 우선순위가 가장 높은 큐가 비어 있으면 그 다음 우선순위 큐에 있는 프로세스 처리
- 보통 비선점형 스케줄링으로 구현되지만, 큐 간 우선순위에 따라 선점형 스케줄링으로도 구현될 수 있습니다.
[ 장점 ] : 프로세스를 유형별로 처리하기 쉬워집니다.
[ 단점 ] : 이 또한 우선순위가 낮은 프로세스는 계속해서 실행이 연기되는 기아(starvation) 현상이 발생할 수 있습니다.
< 다단계 피드백 큐 스케줄링 >
MFQS ( Multilevel Feedback Queue Scheduling ) 스케줄링
- 큐 간의 이동이 가능한 다단계 큐 스케줄링입니다.
- 어떤 프로세스의 CPU 시간이 길면 우선순위가 낮아지고, 어떤 프로세스가 낮은 우선순위 큐에서 너무 오래 기다리면 우선순위를 높이는( = 에이징) 방식입니다.
- 선점형 스케줄링입니다.
- CPU 스케줄링 방식의 가장 일반적인 형태입니다.
012
: 자연스럽게 CPU 집중 프로세스의 우선순위는 상대적으로 낮아지고 입출력 집중 프로세스의 우선순위는 상대적으로 높아집니다.
