CPU 스케줄링의 알고리즘 알아보기
대표 방식 7가지
1. 선입 선처리 스케줄링
2. 최단 작업 우선 스케줄링
3. 라운드 로빈 스케줄링
4. 최소 잔여 시간 우선 스케줄링
5. 우선순위 스케줄링
6. 다단계 큐 스케줄링
7. 다단계 피드백 큐 스케줄링
1. 선입 선처리 스케줄링
- First Come First Served
- 단순히 준비 큐에 삽입된 순서대로 처리하는 비선점 스케줄링.
- 단점: 프로세스들이 기다리는 시간이 매우 길어질 수 있다는 부작용이 있다. (먼저 들어간 프로세스의 실행시간이 길어질 경우)
2. 최단 작업 우선 스케줄링
- SJF(Shortest Job First) 스케줄링
- 호위 효과를 방지하기 위함
- CPU 사용이 긴 프로세스는 나중에 실행, CPU 사용 시간이 짧은 프로세스 먼저 실행
- CPU 사용 시간이 가장 짧은 프로세스부터 처리하는 스케줄링 방식
- 선점형, 비선점형 둘다 있지만 보통 비선점형으로 분류된다.
3. 라운드 로빈 스케줄링
- RR(Round Robin) : 돌아가면서 뭔가를 한다는 용어이다.
- 선입 선처리 스케줄링 + 타임 슬라이스(time slice)
- 타임 슬라이스 : 각 프로세스가 CPU를 사용할 수 있는 정해진 시간
- 정해진 타임 슬라이스만큼의 시간 동안 돌아가며 CPU를 이용하는 선점형 스케줄링
- 큐에 삽입된 프로세스들은 순서대로 CPU를 이용하되 정해진 시간 만큼만 이용
- 정해진 시간을 모두 사용하였음에도 아직 프로세스가 완료되지 않았다면 다시 큐의 맨 뒤에 삽입 (문맥 교환)
4. 최소 잔여 시간 우선 스케줄링
- SRT (Shortest Remaining Time) 스케줄링
- 최단 작업 우선 스케줄링 + 라운드 로빈 스케줄링
- 최단 작업 우선 스케줄링 : 작업시간이 짧은 프로세스부터 처리하는 스케줄링 알고리즘
- 라운드 로빈 스케줄링: 정해진 타임 슬라이스만큼 돌아가며 사용하는 스케줄링 알고리즘
- 즉, 정해진 시간만큼 CPU를 이용하되, 다음으로 CPU를 사용할 프로세스로는 남은 작업 시간이 가장 적은 프로세스 선택
5. 우선 순위 스케줄링
- 프로세스들에 우선순위를 부여하고, 우선순위가 높은 프로세스부터 실행
- 우선순위가 같은 프로세스들은 선입 선처리로 스케줄링
- 최단 작업 우선 스케줄링, 최소 잔여 시간 스케줄링 또한 우선순위 스케줄링 방식으로 볼 수있다.
- 근본적인 문제점: 기아(starvation 스타베이션) 현상
- 우선순위 높은 프로세스만 주구장창 실행 하게되면
- 우선순위 낮은 프로세스는 (준비 큐에 먼저 삽입되었음에도 불구하고) 한도끝도없이 실행이 연기된다.
- 해결책: 에이징(aging) 기법
- 나이를 먹게하는 효과 라고 이해하자
- 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식
- 대기중인 프로세스의 우선순위를 마치 나이 먹듯 점차 증가시키는 방법
- 우선순위가 낮아도 언젠가는 우선순위가 높아진다.
6. 다단계 큐 스케줄링
- Multilevel queue 스케줄링
- 우선순위 스케줄링의 발전된 형태
- 우선순위별로 준비 큐를 여러 개 사용하는 스케줄링 방식
- 우선순위가 가장 높은 큐에 있는 프로세스를 먼저 처리
- 우선순위가 가장 높은 큐가 비어 있으면 그 다음 우선순위 큐에 있는 프로세스 처리
- 장점: 프로세스 유형별로 우선순위를 구분하는것이 되게 쉬워진다. (큐별로 스케줄링을 달리적용해서 프로세스를 유형별로 처리하는것이 쉬워진다.)
- 단점: 기본적으로 프로세스가 큐간의 이동을 할 수밖에 없다. 우선순위 낮은녀석들이 계속해서 밀리는 현상이 발생할 수 있다. 즉, 기아현상이 발생할 수 있다.
7. 다단계 피드백 큐 스케줄링
- Multilevel feedback queue 스케줄링
- 다단계 큐 스케줄링의 단점을 해결한 형태
- 큐 간의 이동이 가능한 다단계 큐 스케줄링
- 새롭게 준비상태가 된 프로세스가 있으면 일단 가장 우선순위가 높은 큐에다가 삽입한다.
- 그런 뒤 일정시간(타임슬라이스)만큼 할당을 받아 CPU를 사용을 하게 한다.
- 이때 실행이 끝났다면 나이스, CPU가 안끝났다면 그 다음 우선순위 큐에 삽입을 해놓는다.
- 거기서 실행이 끝났다면 나이스, 여기서도 실행이 끝나지 않았다면 그 다음 우선순위 큐에 삽입을 한다.
즉, CPU 집중 프로세스의 우선순위는 상대적으로 낮아지고 입출력 집중 프로세스의 우선순위는 상대적으로 높아진다.
"너, 타임 슬라이스 동안 실행을 다 못 끝내겠으면 일단 낮은 우선순위로 이동해!"
- 다단계 피드백 큐에서도 에이징 기법 적용 할 수 있다.
- 어떤 프로세스가 낮은 우선순위 큐에서 너무 오래 기다리면 우선순위를 높여준다.
구현이 조금 복잡할 수는 있지만, CPU 스케줄링 방식의 가장 일반적인 형태로 알려져있다.