6. CPU 스케줄링 알고리즘

🖥️ CPU 스케줄링 알고리즘 🖥️ 

1. 선입 선처리 스케줄링

FCFS(First Come First Served) 스케줄링

- 준비 큐에 삽입된 순서대로 처리하는 비선점 스케줄링

- 먼저 CPU를 요청한 프로세스부터 CPU 할당

호위 효과(convoy effect)를 방지하려면 어떻게 할 수 있을까?

 

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

SJF(Shortest Job First) 스케줄링 (기본적으로는 비선점, 선점형이 될 수도 있음)

CPU 사용 시간이 짧은 프로세스는 먼저 실행, CPU 사용 시간이 긴 프로세스는 나중에 실행하기 (평균 대기 시간 단축)

 

3. 라운드 로빈 스케줄링

RR(Round Robin) 스케줄링 (돌아가며)

- 선입 선처리 스케줄링 + '타임 슬라이스'

* 타임슬라이스: 각 프로세스가 CPU를 사용할 수 있는 정해진 시간.

- 정해진 타임 슬라이스만큼의 시간 동안 돌아가며 CPU를 이용하는 선점형 스케줄링

- 큐에 삽입된 프로세스들은 순서대로 CPU를 이용하지만, 정해진 시간 만큼만 이용

- 정해진 시간을 모두 사용했음에도 프로세스가 완료되지 않았다면 다시 큐의 맨 뒤에 삽입(문맥 교환)

너무 크면 비효율적(선입 선처리 스케줄링과 거의 유사해져버림)

타임슬라이스가 너무 크면 호위효과 발생 가능, 타임슬라이스가 너무 작으면 문맥교환으로 인한 오버헤드 발생 가능

 

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

SRT(Shortest Remaining Time) 스케줄링

- 최단 작업 우선 스케줄링 + 라운드 로빈 스케줄링

- 정해진 시간 만큼 CPU를 이용하되(타임 슬라이스), 다음으로 CPU를 사용할 프로세스는 남은 작업 시간이 가장 적은 프로세스 선택

 

5. 우선순위 스케줄링

- 프로세서들에 우선순위를 부여하고, 우선순위가 높은 프로세스부터 실행

- 우선순위가 같은 프로세스들은 선입 선처리로 스케줄링

우선순위 스케줄링 안에(넓은 범위) 최단 작업 우선 스케줄링, 최소 잔여 시간 스케줄링이 포함되는 형태 

매직패스의 서러움..

- 기아 현상을 방지하기 위한 기법 '에이징(aging)'

오래 대기한 프로세스들의 우선순위를 점차 높이는 방식.

우선순위가 낮은 프로세스가 계속 낮은 우선순위인 것이 아니라, 시간이 지나며 점차 우선순위가 높아짐.

 

 

6. 다단계 큐 스케줄링

Multilevel queue 스케줄링

- 우선순위 스케줄링의 발전된 형태

- 우선순위별로 준비 큐를 여러 개 사용하는 스케줄링 방식

큐별로 스케줄링을 다르게 할 수 있다는 장점이 있다.

but 프로세스가 큐 간 이동이 불가능함. 우선순위가 낮은 프로세스는 계속 우선순위가 낮은 큐에 있어서 기아현상이 발생할 수 있음.

 

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

Multilevel feedback queue 스케줄링

- 다단계 큐 스케줄링의 발전된 형태

- '큐 간 이동이 가능한' 다단계 큐 스케줄링

 

준비 상태가 된 프로세스가 있으면, 우선순위0 큐에 삽입을 함

타임 슬라이스 만큼 CPU를 사용하게 하고, 실행이 끝나지 않았다면 우선순위가 다음으로 높은 큐에 삽입(우선순위 1 큐)

여전히 실행이 끝나지 않았다면, 우선순위 2 큐에 삽입.

즉 CPU 사용량이 많은 프로세스의 우선순위가 점차 낮아지게 됨.

다단계 피드백 큐에서도 에이징 기법 적용 가능함.

오랜 시간 낮은 우선순위 큐에 삽입된 경우 우선순위 높이기(기아 현상 방지)

 

학습 출처: https://www.youtube.com/watch?v=bls_GjX-4U8&list=PLVsNizTWUw7FCS83JhC1vflK8OcLRG0Hl