11-02) CPU 스케줄링 알고리즘

운영체제마다 서로 다른 스케줄링 알고리즘을 가지고 있으며 매우 다양하다. 당연하게도 각 스케줄링 마다 장, 단점을 가지고 있음!
작동 방식에 대해서 다양한 알고리즘 아이디어가 있음!

스케줄링 알고리즘의 종류

• 선입 선처리 스케줄링
• 최단 작업 우선 스케줄링
• 라운드 로빈 스케줄링
• 최소 잔여 시간 우선 스케줄링
• 우선순위 스케줄링
• 다단계 큐 스케줄링
• 다단계 피드백 큐 스케줄링

.... 이외에도 여러가지 스케줄링에 대한 아이디어들이 있음.

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

First Come First Served

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

위 그림예시에서 앞선 프로세스의 실행시간 만큼 대기시간을 가지게 된다. 그래서 예로들어 맨 처음 대기큐로 들어온 프로세스가 실행시간이 긴 경우 뒤 프로세스는 그만큼 긴 대기시간을 가지게 된다. 이러한 호위효과를 방지하려는 방식이 다음 방식이다!

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

Shortest Job First

• CPU 사용시간이 짧은 프로세스 먼저 실행, 긴 프로세스는 나중에 실행
• 위 비교하면 평균 대기시간이 줄어든 것을 볼 수 잇따! ( 13ms -> 3ms)
• 비선점형 스케줄링 알고리즘으로 분류됨.

3. 라운드 로빈 스케줄링(RR)

round robin scheduling

• 선입 선처리 스케줄링 + 타임 슬라이스(time slice)
• 타임 슬라이스 : 각 프로세스가 cpu를 사용할 수 있는 정해진 기간.
• 정해진 타임 슬라이스만큼의 시간을 돌아가며 cpu를 이용하는 선점형 스케줄링, 만약 정해진 시간만큼 프로세스가 완료가 되지 않았다면 다시 큐의 맨 뒤로 삽입(문맥 교환)

타임 슬라이스의 크기가 중요하다 !
타임 슬라이스가 지나치게 크다면, 결국엔 선입선출처럼 호위효과가 생길 수 가 있고, 또한 너무 작다면 문맥교환이 자주 일어나기 때문에 CPU가 전환하는 비용이 더 커진다.

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

Shortest Remaining Time

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

5. 우선 순위 스케줄링

• 프로세스들에게 우선순위를 부여하고, 우선순위 높은 프로세스부터 실행
• 우선순위가 같다면, 선입 선처리로 스케줄링
• 최단 작업 우선 스케줄링, 최소 잔여 시간 스케줄링 역시 우선순위이다
  즉, 최단작업은 작업시간이 짧은 프로세스에 높은 우선순위를 주는 것처럼..

근원적인 부작용을 가지고 있음.

• 우선순위 스케줄링의 근본적인 문제점 : 💀기아 현상!(starvation)
• 우선순위 높은 프로세스만 주구장창실행되고 우선순위가 낮은 프로세스는 (준비 큐에 먼저 삽입되었음에도 불구하고) 실행이 연기 ....

그렇다면 기아현상을 해결 할 수 있는 방법이 있는 기법도 있음.
에이징(aging) : 오랫동한 대기한 프로세스의 우선순위를 점차 높여가는 방식, 마치 나이를 먹는것처럼 ( 우선순위가 낮아도 실행되지 않는다면 점차 우선순위가 높아진다)

6. 다단계 큐 스케줄링

Multilevel queue 스케줄링

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

큐가 여러개 있다면, 유형별로 구분해서 수행할 수 있다.(입출력집중프로세스, CPU집중프로세스..) 또한 큐별로 다른 스케줄링 알고리즘, 타임슬라이스를 여러개 지정 등을 할 수 있따.

하지만 큐 간의 이동이 불가능하기때문에 기아 현상이 발생할 수 있다.

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

Multilevel feedback queue

• 다단계 큐 스케줄링의 발전된 형
• 큐 간의 이동이 가능한 다단계 큐 스케줄링
• 다단계 큐 스케줄링에선 기본적으로 큐간의 이동이 불가능
  - 우선순위 가 낮은 프로세스는 계속해서 실행연기 우려! (기아현상)

1. 준비된 프로세스가 있다면 우선 가장 높은 우선순위 큐에 삽입되고 일정시간(타임슬라이스 ) 동안 실행된다.
   
2. 실행이 끝나지 않았다면 우선순위가 다음 우선순위 큐에 삽입되어 실행된다. 즉 CPU를 오래 사용해야 되는 프로세스는 점차 우선순위가 낮아진다.
   

자연스럽게 CPU 집중 프로세스의 우선순위는 상대적으로 낮아지고
입출력 집중 프로세스는 우선순위는 상대적으로 높아짐..

다단계 스케줄링 큐의 에이징

• 낮은 우선순위 큐에서 너무 오래 기다리고 있는 프로세스가 있다면 점차 우선순위가 높은 큐로 이동시키는 에이징기법을 사용.
  

---

즉! CPU 시간이 오래걸리면 우선순위는 낮아지고, 어떠한 프로세스가 낮은 우선순위 큐에 오래 기다린다면 우선순위를 높인다.

다단계 피드백 큐 스케줄링은 구현이 복잡하나, 가장 일반적인 CPU 스케줄링 알고리즘으로 알려짐.