🗓️ CPU 스케줄링 알고리즘

CPU 스케줄러가 프로세스에서 해야 하는 일을 스레드 단위로 CPU에 할당할 때 CPU 스케줄링 알고리즘에 따름.

• CPU 스케줄링 알고리즘이 어떤 프로그램에게 CPU 소유권을 줄 것인지 결정.

CPU 스케줄링 알고리즘의 목표

1. CPU 이용률이 높도록
2. 주어진 시간에 많은 일을 하도록
3. 준비 큐(ready queue)에 있는 프로세스는 적도록
4. 응답 시간은 짧게 설정하도록

🦕 비선점형(Non-preemptive) 방식

프로세스가 스스로 CPU 소유권을 포기하는 방식

• 강제로 프로세스를 중지하지 않음.
• 컨텍스트 부하가 적음.

FCFS(Frist Come, First Served)

가장 먼저 온 것을 가장 먼저 처리하는 알고리즘

• 준비 큐에서 오래 기다리는 현상(Convoy Effect)이 발생함.
  • 먼저 온 프로세스가 수행 시간이 길 경우 발생.

SJF(Shortest Job First)

실행 시간이 가장 짧은 프로세스를 가장 먼저 실행하는 알고리즘

• 평균 대기 시간이 가장 짧음.
• 긴 시간을 가진 프로세스가 실행되지 않는 현상(Starvation)이 발생함.
• 실제로 실행 시간을 알 수 없기 때문에 과거의 실행했던 시간을 토대로 추측해서 사용.

우선순위

SJF의 Startvation 현상을 보완하기 위한 알고리즘.

• 오래된 작업일수록 우선순위를 높이는 방법(Aging)을 통해 보완.

🦖 선점형(Preemptive) 방식

지금 사용하고 있는 프로세스를 알고리즘에 의해 중단시켜 버리고 강제로 다른 프로세스에 CPU 소유권을 할당하는 방식

• 현대의 운영체제가 쓰는 방식.

라운드 로빈(RR, Round Robin)

각 프로세스에 동일한 할당 시간을 주고 그 시간 안에 끝나지 않으면 다시 준비 큐(Ready Queue)의 뒤로 가는 알고리즘

• 현대 컴퓨터가 쓰는 우선순위 스케줄링(Priority Scheduling) 방식의 일종.
• 로드밸런서에서 트래픽 분산 알고리즘으로도 쓰임.

• 일반적으로 전체 작업 시간은 길어지지만 평균 응답 시간은 짧아지는 특징을 가짐.

• 할당 시간이 너무 크면 FCFS가 됨.
• 할당 시간이 너무 짧으면 컨텍스트 스위칭이 잦아져 오버헤드(비용)이 커짐.

SRF(Shortest Remaining time First)

SJF 를 개선한 알고리즘.

• SJF에서 중간에 실행 시간이 더 짧은 작업이 들어와도 기존의 짧은 작업을 모두 수행하고 그 다음 중간에 들어온 해당 작업을 이어나감.
• SRF는 중간에 더 짧은 작업이 들어오면 수행하던 프로세스를 중지하고 해당 프로세스를 수행함.

다단계 큐

우선순위에 따른 준비 큐를 여러 개 사용하고, 큐마다 라운드 로빈이나 FCFS 등 다른 스케줄링 알고리즘을 적용한 방식.

• 우선순위가 낮은 큐에서 작업이 실행 중일 때 우선순위가 높은 큐에 프로세스가 도착하면 CPU를 빼앗는 방식.(선점형)
• 우선순위가 낮은 큐에 Starvation 현상이 발생할 수 있음.

• 큐 간의 프로세스 이동이 안되므로 스케줄링 부담이 적음.
• 유연성이 떨어짐.

참고

• https://cocoon1787.tistory.com/124