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

[1two13]

• CPU 스케줄링 알고리즘은 매우 다양하고 운영체제마다 다르기 떄문에 암기하기 보다는 작동 방식과 장단점을 이해하기!

스케줄링 알고리즘 종류

1. 선입 선처리 스케줄링(FCFS 스케줄링)

• First Come First Served Scheduling
• 준비 큐에 삽입된 순서대로 프로세스를 처리하는 비선점형 스케줄링 방식이다.
• 호휘 효과가 발생한다. 호위 효과는 CPU를 오래 사용하는 프로세스가 먼저 도착하면 다른 프로세스는 그 프로세스가 CPU를 사용하는 동안 무작정 기다리는 현상이다.

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

• Shortest Job First Scheduling
• 호위 효과를 방지하기 위해 탄생한 스케줄링이다.
• 즉, CPU 이용 시간의 길이가 가장 짧은 프로세스부터 실행하는 스케줄링 방식이다.
• 기본적으로 비선점형 스케줄링 알고리즘으로 분류되지만, 선점형으로 구현될 수도 있다.

3. 라운드 로빈 스케줄링

• 선입 선처리 스케줄링 + 타임 슬라이스 개념이 더해진 스케줄링 방식이다.
• 타임 슬라이스: 각 프로세스가 CPU를 사용할 수 있는 정해진 시간
• 즉, 정해진 타임 슬라이스만큼의 시간 동안 돌아가며 CPU를 이용하는 선점형 스케줄링이다.
• 타임 슬라이스 크기가 매우 중요하다. 타임 슬라이스가 지나치게 크면 선입 선처리 스케줄링과 다를 바 없어 호위 효과가 생길 여지가 있고, 지나치게 작으면 문맥 교환에 발생하는 비용이 크기 때문이다.

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

• Shortest Remaining Time
• 2번과 3번을 합친 스케줄링 방식이다. (최단 작업 우선 스케줄링 + 라운드 로빈 스케줄링)
• 최소 잔여 시간 우선 스케줄링 하에서 프로세스들을 정해진 타임 슬라이스만큼 CPU를 사용하되, CPU를 사용할 다음 프로세스로는 남아있는 작업 시간이 가장 적은 프로세스가 선택된다.

[1two13]

5. 우선순위 스케줄링

• 프로세스들에 우선순위를 부여하고, 가장 높은 우선순위를 가진 프로세스부터 실행하는 스케줄링 알고리즘이다. 만약 우선순위가 같을 경우 선입 선처리로 스케줄링된다.
• 기아 현상이 발생한다는 문제점이 있다. 기아 현상은 우선 순위가 높은 프로세스만 계속 먼저 실행되다 보니깐 우선 순위가 낮은 프로세스의 실행은 계속 뒤로 밀리는 현상이다.
• 이를 방지하기 위한 대표적인 기법으로 에이징이 있다. 에이징은 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식이다.

6. 다단계 큐 스케줄링

• 우선순위 스케줄링의 발전된 형태로, 우선순위별로 준비 큐를 여러 개 사용하는 스케줄링 방식이다.
• 큐별로 타임 슬라이스를 여러 개 지정할 수도 있고, 큐마다 다른 스케줄링 알고리즘을 사용할 수도 있다.

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

• 다단계 큐 스케줄링에서 프로세스들이 큐 사이를 이동할 수 없는 문제점, 즉 우선 순위가 낮은 프로세스는 계속 연기되어 기아 현상이 발생하는 문제점을 보완한 스케줄링 방식이다.
• 어떤 프로세스의 CPU 이용 시간이 길면 낮은 우선순위 큐로 이동시키고, 어떤 프로세스가 낮은 우선 순위 큐에서 너무 오래 기다린다면 높은 우선 순위 큐로 이동시킬 수 있는 알고리즘이다.
• 가장 일반적인 CPU 알고리즘이다.