CPU 스케줄링 알고리즘
- 선입 선처리 스케줄링 : FCFS (First Come Fisrt Served)
- 최단 작업 우선 스케줄링 : SJF (Shortest Job First)
- 라운드 로빈 스케줄링 : RR (Round Robin)
- 최소 잔여 시간 우선 스케줄링 : SRT (Shortest Remaining Time)
- 우선순위 스케줄링 : Priority
- 다단계 큐 스케줄링 : MQ (Multilevel Queue)
- 다단계 피드백 큐 스케줄링 : MFQ (Multilevel feedback queue)
1. FCFS (First Come First Served)
선입 선처리 스케줄링 (비선점)
- 단순히 준비 큐에 삽입된 순서대로 처리하는 비선점(Non-preemptive Scheduling) 스케줄링
- 먼저 CPU를 요청한 프로세스부터 CPU 할당
- 단점 : 프로세스들이 기다리는 시간이 매우 길어질 수 있다는 부작용 (=호위효과 , convoy effect)
2. SJF (Shortest Job First)
최단 작업 우선 스케줄링 (비선점형)
- CPU 사용이 긴 프로세스는 나중에 실행, CPU 사용 시간이 짧은 프로세스는 먼저 실행
- CPU 사용시간이 가장 짧은 프로세스부터 처리하는 스케줄링 방식
- 호위효과를 방지할 수 있음
3. RR (Round Robin)
라운드 로빈 스케줄링 (선점형)
- 선입 선처리 스케줄링 + 타임 슬라이스 (time slice)
- Time slice : 각 프로세스가 CPU를 사용할 수 있는 정해진 시간
- 정해진 time slice 만큼의 시간 동안 돌아가며 CPU를 이용하는 선점형 스케줄링
- 큐에 삽인된 프로세스들은 순서대로 CPU를 이용하되 정해진 시간만큼만 이용
- 정해진 시간을 모두 사용하였음에도 아직 프로세스가 완료되지 않았다면 다시 큐의 맨 뒤에 삽입 (Context switching)
time slice 의 크기가 중요
- time slice 가 너무 크면 FCFS 스케줄링의 단점처럼 호위 효과를 야기할 수 있음
= time slice 가 너무 작으면 context switching 때문에 발생하는 오버헤드 때문에 CPU 의 부담이 커짐
4. SRT (Shortest Remaining Time)
최소 잔여 시간 우선 스케줄링 (선점형)
- 최단 작업 우선 스케줄링 + 라운드 로빈 스케줄링
- 최단 작업 우선 스케줄링 : 작업 시간이 짧은 프로세스부터 처리하는 스케줄링 알고리즘
- 라운드 로빈 스케줄링 : 정해진 타임 슬라이스만큼 돌아가며 사용하는 스케줄링 알고리즘
- 정해진 시간만큼 CPU를 이용하되, 다음으로 CPU를 사용할 프로세스로는 남은 작업 시간이 가장 적은 프로세스 선택
5. Priority
우선 순위 스케줄링
- 프로세스들에 우선순위를 부여하고, 우선순위 높은 프로세스부터 실행
- 우선순위가 같은 프로세스들은 선입 선처리로 스케줄링
- SJF (Shortest Job First), SRT (Shortest Remaining Time) ⊂ 우선 순위 스케줄링
- SJF 는 작업 시간이 짧은 프로세스에 우선순위를 높게 부여하는 방식
- SRT 는 남아 있는 시간이 짧은 프로세스에 우선 순위를 높게 부여하는 방식
문제점
- 우선순위(Priority) 스케줄링의 근본적인 문제점, 기아(starvation) 현상
- 우선순위 높은 프로세스만 주구장창 실행
- 우선순위 낮은 프로세스는 (준비 큐에 먼저 삽입되었음에도 불구하고) 실행 연기
- 우선순위가 낮은 프로세스는 한도 끝도 없이 연기될 수 도 있다. 즉 실행이 안될 수도 있다. = 기아(starvation) 현상
해결법
- 이를 방지하기 위한 기법 : aging
- 오랫동안 대기한 프로세스의 우선순위(Priority)를 점차 높이는 방식
- 대기 중인 프로세스으 우선순위를 마치 나이 먹듯 점차 증가시키는 방법
6. MQ (Multilevel queue)
다단계 큐 스케줄링 (혼합 , 선점형 비선점형)
- 우선순위(Priority scheduling)의 발전된 형태
- 우선순위별로 준비 큐(Ready queue)를 여러개 사용하는 스케줄링 방식
- 우선순위가 가장 높은 큐에 있는 프로세스를 먼저 처리
- 우선순위가 가장 높은 큐가 비어 있으면 그 다음 우선순위 큐에 있는 프로세스 처리
정리
- Ready queue를 특성 별로 여러 개 갖는다.
- Ready queue에 우선순위가 있다.
- Ready queue마다 독립적인 스케줄링을 갖는다.
- Ready queue 간에 프로세스 이동이 안 된다.
- 우선순위가 가장 높은 큐(Queue)에서는 비선점으로 사용된다.
장점
- 프로세스 유형별로 우선순위를 구분하는 것이 쉬워진다
- 어떤 큐에는 입출력 집중 프로세스(IO Bound) 삽입될 수 있고 , 어떤 큐에는 우선순위가 비교적 낮아도 상관없는 CPU Bound process 가 삽입 될 수 있다.
- 또 어떤 큐에는 time slice 를 적게 지정할 수도 있고 크게 지정할 수도 있다
- 또 어떤 큐에는 FCFS 스케줄링을 사용할 수도 있고, 어떤 큐에는 Round Robin 스케줄리을 사용할 수도 있다
- 즉 그룹화를 하여 CPU bound와 I/O bound가 섞여서 효율이 안 좋은 것을 막을 수 있다.
문제점
- Queue 간의 이동이 불가능
- 즉 우선순위가 낮은 프로세스는 계속 우선순위가 낮은 프로세스에 머무를 수 밖에 없다 (= starvation)
7. MFQ (Multilevel feedback queue)
다단계 피드백 큐 스케줄링 (선점형)
- Multilevel queue 스케줄에 문제점(starvation)을 해결한 발전된 형태
- Queue 간의 이동이 가능한 Multilevel queue 스케줄링
- Multilevel queue 스케줄링에서는 기본적으로 Queue 간의 이동이 불가능
- 우선순위 낮은 프로세스는 계속해서 샐행 연기 우려
- 기아 현상 발생 가능
- CPU bound 프로세스 일 수록 Priority 가 자연스럽게 낮아진다
- IO Bound 프로세스 일 수록 Priority 가 높아진다
주요 특징
- 여러 대기열: 여러 개의 대기열이 존재하며, 각각 다른 우선순위를 가집니다. 보통 가장 높은 우선순위의 큐가 CPU에 더 빨리 접근할 수 있습니다.
- 피드백에 의한 동적 조정: 프로세스는 시간이 지남에 따라 다른 큐로 이동할 수 있습니다. 이는 프로세스의 행동과 요구에 따라 동적으로 조정됩니다.
- 시간 할당량(타임 퀀텀): 각 큐는 고유한 시간 할당량(또는 타임 퀀텀)을 가집니다. 일반적으로 우선순위가 높은 큐의 타임 퀀텀은 짧고, 우선순위가 낮은 큐의 타임 퀀텀은 길게 설정됩니다.
- 성능 최적화: 이 알고리즘은 시스템의 성능을 최적화하기 위해 CPU 버스트 시간이 짧은 작업과 긴 작업을 효과적으로 구분합니다.
작동 방식 예시 1
- 우선순위에 따른 실행: 프로세스는 우선순위에 따라 해당하는 큐에서 실행됩니다. 우선순위가 높은 큐의 프로세스가 먼저 CPU를 할당받습니다.
- 타임 퀀텀 초과: 프로세스가 할당된 시간 내에 작업을 완료하지 못하면, 다음 우선순위가 낮은 큐로 이동합니다.
- 타임 퀀텀 내 완료: 프로세스가 할당된 시간 내에 작업을 완료하면, Ready queue 로 프로세스를 이동
- 기아 현상 방지: 오랫동안 CPU를 할당받지 못하는 프로세스의 우선순위를 점진적으로 높여서 기아 현상을 방지합니다.
작동 방식 예시 2
(참고 : https://jaegukim.github.io/posts/multilevel-feedback-queue-schedulingmlfq/)
1. 처음 들어오는 프로세스들은 queue1으로 들어갑니다.
2. queue1에서 프로세스들이 4unit (4unit=time slice=time quantum)내에 실행이 완료된다면, 이 프로세스의 우선순위는 바뀌지 않고, 다음에 ready queue에 프로세스가 들어오면 다시 queue1에서 실행을 시작합니다.
3. queue1에있는 프로세스가 4unit내에 실행되지 않으면, 우선순위가 감소하게 되고 queue2로 이동하게 됩니다.
4. queue2에서도 위의 2,3단계를 똑같이 반복하지만 이번에는 time quantum이 8입니다. 이번에는 8unit만에 실행이 되지 않으면 더 낮은 우선순위 큐로 이동합니다.
5. 마지막 큐에서, 프로세스들은 FCFS 방식으로 스케줄링됩니다.
6. 낮은 우선순위 큐에있는 프로세스는 더 높은 우선순위의 큐들이 비어있어야 실행됩니다.
7. 낮은 우선순위 큐에있는 프로세스는 더 높은 우선순위의 큐들로 할당된 프로세스에 의해서 인터럽트 됩니다.
- 위의 구현의 문제점 - 낮은 우선순위큐에있는 프로세스는 CPU time이 짧은 프로세스들때문에 Starvation에 빠질수있습니다.
- 해결책 - 일정 시간후에 프로세스들의 우선순위를 최우선으로 높여줍니다.
.