Last update: @1/7/2023
•
CPU 스케줄링 알고리즘의 종류는 매우 다양하고 운영체제 저마다 서로 다른 스케줄링 알고리즘을 사용하고 있음
◦
선입 선처리 스케줄링(FCFS; First Come First Served Scheduling)
: 단순히 준비 큐에 삽입된 순서대로 프로세스들을 처리하는 비선점형 스케줄링 방식. 즉, 선입 선처리 스
케줄링은 CPU를 먼저 요청한 프로세스부터 CPU를 할당하는 스케줄링 방식
▪
선입 선처리 스케줄링은 언뜻 보기에는 가장 공정해 보이지만, 때때로 프로세스들이 기다리는 시간이 매우 길어질 수 있다는 점에서 부작용이 있는 방식임
•
이런 현상을 호위 효과(convoy effect)라고 함
◦
최단 작업 우선 스케줄링(SJF; Shortest Job First Scheduling)
: 준비 큐에 삽입된 프로세스들 중 CPU 이용 시간의 길이가 가장 짧은 프로세스부터 실행하는 스케줄링 방식
▪
기본적으로 비선점형 스케줄링 알고리즘으로 분류되지만, 선점형으로 구현될 수도 있음
◦
라운드 로빈 스케줄링(round robin scheduling)
: 선입 선처리 스케줄링에 타임 슬라이스라는 개념이 더해진 스케줄링 방식
▪
타임 슬라이스란 각 프로세스가 CPU를 사용할 수 있는 정해진 시간을 의미함. 즉, 한 번 CPU를 이용할 때 최대 사용 가능시간을 정해둔 방식
▪
타임 슬라이스가 지나치게 크면 사실상 선입 선처리 스케줄링과 다를 바 없어 호위 효과가 생길 여지가 있음
▪
타임 슬라이스가 지나치게 작으면 문맥 교환에 발생하는 비용이 커 CPU는 프로세스를 처리하는 일보다 프로세스를 전환하는 데에 온 힘을 다 쓸 여지가 있음
◦
최소 잔여 시간 우선 스케줄링(SRT; Shortest Remaining Time)
: 스케줄링은 최단 작업 우선 스케줄링 알고리즘과 라운드 로빈 알고리즘을 합친 스케줄링 방식
▪
최소 잔여 시간 우선 스케줄링 하에서 프로세스들은 정해진 타임 슬라이스만큼 CPU를 사용하되, CPU를 사용할 다음 프로세스로는 남아있는 작업 시간이 가장 적은 프로세스가 선택됨
◦
우선순위 스케줄링(priority scheduling)
: 프로세스들에 우선순위를 부여하고, 가장 높은 우선순위를 가진 프로세스부터 실행하는 스케줄링 알고리즘
▪
우선순위가 같은 프로세스들은 선입 선처리로 스케줄링 됨
▪
앞서 설명한 최단 작업 우선 스케줄링, 최소 잔여 시간 우선 스케줄링 알고리즘은 넓은 의미에서 우
선순위 스케줄링의 일종으로 볼 수 있음
▪
우선순위가 낮은 프로세스는 준비 큐에 먼저 삽입되었음에도 불구하고 우선순위가 높은 프로세스들에 의해 실행이 계속해서 연기될 수 있는데, 이를 기아(starvation) 현상이라고 함
•
이를 방지하기 위한 대표적인 기법이 에이징(aging)임. 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식
◦
다단계 큐 스케줄링(multilevel queue scheduling)
: 우선순위별로 준비 큐를 여러 개 사용하는 스케줄링 방식. 우선순위가 가장 높은 큐에 있는 프로세스들을 먼저 처리하고, 우선순위가 가장높은 큐가 비어 있으면 그다음 우선순위 큐에 있는 프로세스들을 처리함
▪
이렇게 큐를 여러 개 두면 프로세스 유형별로 우선순위를 구분하여 실행하는 것이 편리해짐
▪
가령 어떤 큐에는 우선순위가 비교적 높아야 하는 CPU 집중 프로세스가 삽입될 수 있고, 어떤 큐에
는 우선순위가 비교적 낮아도 상관없는 입출력 집중 프로세스가 삽입될 수 있음
▪
또 어떤 큐에는(우선순위가 비교적 높아야 하는) 백그라운드 프로세스들을 삽입할 수 있고, 어떤 큐에는 (우선순위가 비교적 낮아도 무방한) 사용자와의 상호작용이 잦은 프로세스들을 삽입할 수 있음
▪
또한 큐별로 타임 슬라이스를 여러 개 지정할 수도 있고, 큐마다 다른 스케줄링 알고리즘을 사용할
수도 있음. 예를 들어 어떤 큐에서의 타임 슬라이스는 크게, 어떤 큐에서의 타임 슬라이스는 작
게 사용하고, 어떤 큐에서는 선입 선처리 스케줄링을 사용하고, 어떤 큐에서는 라운드 로빈 스케줄링
을 사용할 수 있음
▪
다만 기아 현상이 발생할 수 있는 여지가 있음
◦
다단계 피드백 큐 스케줄링(multilevel feedback queue scheduling)
: 다단계 큐 스케줄링과 비슷하게 작동하지만, 프로세스들이 큐 사이를 이동할 수 있다는 차이점이 있음
▪
다단계 피드백 큐 스케줄링에서 새로 준비 상태가 된 프로세스가 있다면 우선 우선순위가 가장 높은 우선순위 큐에 삽입되고 일정 시간(타임 슬라이스) 동안 실행됨
▪
그리고 만약 프로세스가 해당 큐에서 실행이 끝나지 않는다면 다음 우선순위 큐에 삽입되어 실행되고, 또 해당 큐에서 실행이 끝나지 않는다면 프로세스는 또 다음 우선순위 큐에 삽입됨
▪
결국 CPU를 오래 사용해야 하는 프로세스는 점차 우선순위가 낮아짐
▪
CPU를 비교적 오래 사용해야 하는 CPU 집중 프로세스들은 자연스레 우선순위가 낮아지고, CPU를 비교적 적게 사용하는 입출력 집중 프로세스들은 자연스레 우선순위가 높은 큐에서 실행이 끝남
▪
프로세스들이 큐 사이를 이동할 수 있는 방식이기 때문에 낮은 우선순위 큐에서 너무 오래 기다리고 있는 프로세스가 있다면 점차 우선순위가 높은 큐로 이동시키는 에이징 기법을 적용하여 기아 현상을 예방할 수 있음
▪
어떤 프로세스의 CPU 이용 시간이 길면 낮은 우선순위큐로 이동시키고, 어떤 프로세스가 낮은 우선순위 큐에서 너무 오래 기다린다면 높은 우선순위 큐로 이동시킬 수 있는 알고리즘
▪
구현이 복잡하지만 가장 일반적인 CPU 스케줄링 알고리즘임