11-02) CPU 스케줄링 알고리즘
![](https://velog.velcdn.com/images/jobmania/post/26012a93-57e3-419b-bc7a-efa1b57eaea5/image.png)
운영체제마다 서로 다른 스케줄링 알고리즘을 가지고 있으며 매우 다양하다. 당연하게도 각 스케줄링 마다 장, 단점을 가지고 있음!
작동 방식에 대해서 다양한 알고리즘 아이디어가 있음!
스케줄링 알고리즘의 종류
- 선입 선처리 스케줄링
- 최단 작업 우선 스케줄링
- 라운드 로빈 스케줄링
- 최소 잔여 시간 우선 스케줄링
- 우선순위 스케줄링
- 다단계 큐 스케줄링
- 다단계 피드백 큐 스케줄링
.... 이외에도 여러가지 스케줄링에 대한 아이디어들이 있음.
1. 선입 선처리 스케줄링(FCFS)
First Come First Served
![](https://velog.velcdn.com/images/jobmania/post/83f80a05-1d97-40c7-98e2-c586f261d678/image.png)
- 단순히 준비 큐에 삽입된 순서대로 처리하는 비선점 스케줄링
- 먼저 CPU를 요청한 프로세스부터 CPU 할당.
- 당연하게 단점은 프로세스들이 기다리는시간이 매우 길어질 수 있다. (=호위 효과)
위 그림예시에서 앞선 프로세스의 실행시간 만큼 대기시간을 가지게 된다. 그래서 예로들어 맨 처음 대기큐로 들어온 프로세스가 실행시간이 긴 경우 뒤 프로세스는 그만큼 긴 대기시간을 가지게 된다. 이러한 호위효과를 방지하려는 방식이 다음 방식이다!
2. 최단 작업 우선 스케줄링(SJF)
Shortest Job First
![](https://velog.velcdn.com/images/jobmania/post/95c78eac-28e6-48b3-8121-8b3f15e0d387/image.png)
- CPU 사용시간이 짧은 프로세스 먼저 실행, 긴 프로세스는 나중에 실행
- 위 비교하면 평균 대기시간이 줄어든 것을 볼 수 잇따! ( 13ms -> 3ms)
- 비선점형 스케줄링 알고리즘으로 분류됨.
3. 라운드 로빈 스케줄링(RR)
round robin scheduling
![](https://velog.velcdn.com/images/jobmania/post/65021d29-91fe-4cf4-9455-1ba5c1e3a116/image.png)
- 선입 선처리 스케줄링 + 타임 슬라이스(time slice)
- 타임 슬라이스 : 각 프로세스가 cpu를 사용할 수 있는 정해진 기간.
- 정해진 타임 슬라이스만큼의 시간을 돌아가며 cpu를 이용하는 선점형 스케줄링, 만약 정해진 시간만큼 프로세스가 완료가 되지 않았다면 다시 큐의 맨 뒤로 삽입(문맥 교환)
타임 슬라이스의 크기가 중요하다 !
타임 슬라이스가 지나치게 크다면, 결국엔 선입선출처럼 호위효과가 생길 수 가 있고, 또한 너무 작다면 문맥교환이 자주 일어나기 때문에 CPU가 전환하는 비용이 더 커진다.
4. 최소 잔여 시간 우선 스케줄링(SRT)
Shortest Remaining Time
- 최단 작업 우선 스케줄링 + 라운드 로빈 스케줄링
- 최단 작업 우선 스케줄링 : 작업 시간이 짧은 프로세스부터 처리하는 스케줄링 알고리즘
- 라운드 로빈 스케줄링 : 정해진 타임 슬라이스만큼 돌아가며 사용하는 스케줄링 알고리즘
- 즉, 정해진 시간만큼 CPU를 이용하되, 다음으로 CPU를 사용할 프로세스로 남은 작업 시간이 가장 적은 프로세스 선택.
5. 우선 순위 스케줄링
- 프로세스들에게 우선순위를 부여하고, 우선순위 높은 프로세스부터 실행
- 우선순위가 같다면, 선입 선처리로 스케줄링
- 최단 작업 우선 스케줄링, 최소 잔여 시간 스케줄링 역시 우선순위이다
즉, 최단작업은 작업시간이 짧은 프로세스에 높은 우선순위를 주는 것처럼..
근원적인 부작용을 가지고 있음.
![](https://velog.velcdn.com/images/jobmania/post/a3694687-241f-41cf-a57e-da81ad068387/image.png)
- 우선순위 스케줄링의 근본적인 문제점 : 💀기아 현상!(starvation)
- 우선순위 높은 프로세스만 주구장창실행되고 우선순위가 낮은 프로세스는 (준비 큐에 먼저 삽입되었음에도 불구하고) 실행이 연기 ....
그렇다면 기아현상을 해결 할 수 있는 방법이 있는 기법도 있음.
에이징(aging) : 오랫동한 대기한 프로세스의 우선순위를 점차 높여가는 방식, 마치 나이를 먹는것처럼 ( 우선순위가 낮아도 실행되지 않는다면 점차 우선순위가 높아진다)
![](https://velog.velcdn.com/images/jobmania/post/a3e2bb88-3aaf-4a64-86d2-5f6a6d86d72c/image.png)
6. 다단계 큐 스케줄링
Multilevel queue 스케줄링
- 우선 순위 스케줄링의 발전된 행태
- 우선순위별로 준비 큐를 여러개 사용하는 스케줄링 방식
- 우선순위가 가장 높은 큐에 있는 프로세스먼저 처리
- 우선순위가 가장 높은 큐가 비어있으면 다음 우선순위 큐에 있는 프로세스 처리 .
큐가 여러개 있다면, 유형별로 구분해서 수행할 수 있다.(입출력집중프로세스, CPU집중프로세스..) 또한 큐별로 다른 스케줄링 알고리즘, 타임슬라이스를 여러개 지정 등을 할 수 있따.
하지만 큐 간의 이동이 불가능하기때문에 기아 현상이 발생할 수 있다.
7. 다단계 피드백 큐 스케줄링
Multilevel feedback queue
- 다단계 큐 스케줄링의 발전된 형
- 큐 간의 이동이 가능한 다단계 큐 스케줄링
- 다단계 큐 스케줄링에선 기본적으로 큐간의 이동이 불가능
- 우선순위 가 낮은 프로세스는 계속해서 실행연기 우려! (기아현상)
- 준비된 프로세스가 있다면 우선 가장 높은 우선순위 큐에 삽입되고 일정시간(타임슬라이스 ) 동안 실행된다.
![](https://velog.velcdn.com/images/jobmania/post/9c2a0470-716a-4a79-a434-04d19a3544a1/image.png)
- 실행이 끝나지 않았다면 우선순위가 다음 우선순위 큐에 삽입되어 실행된다. 즉 CPU를 오래 사용해야 되는 프로세스는 점차 우선순위가 낮아진다.
![](https://velog.velcdn.com/images/jobmania/post/8f0c0ee7-5f73-450d-8333-a3fe62732eb3/image.png)
자연스럽게 CPU 집중 프로세스의 우선순위는 상대적으로 낮아지고
입출력 집중 프로세스는 우선순위는 상대적으로 높아짐..
다단계 스케줄링 큐의 에이징
- 낮은 우선순위 큐에서 너무 오래 기다리고 있는 프로세스가 있다면 점차 우선순위가 높은 큐로 이동시키는 에이징기법을 사용.
![](https://velog.velcdn.com/images/jobmania/post/18376c11-0707-4f5a-8c4d-f3ce01144444/image.png)
![](https://velog.velcdn.com/images/jobmania/post/c5b34877-2865-4346-8267-7db8d08f4845/image.png)
즉! CPU 시간이 오래걸리면 우선순위는 낮아지고, 어떠한 프로세스가 낮은 우선순위 큐에 오래 기다린다면 우선순위를 높인다.
다단계 피드백 큐 스케줄링은 구현이 복잡하나, 가장 일반적인 CPU 스케줄링 알고리즘으로 알려짐.
소중한 정보 감사드립니다!