CPU 스케줄링
- 운영체제가 프로세스들에게 공정하고 합리적으로 CPU 자원을 배분하는 것
- 입출력 작업이 많은 프로세스(=입출력 집중 프로세스)의 우선순위는 CPU 작업이 많은 프로세스(=CPU 집중 프로세스)의 우선순위보다 높다.
- 프로세스 우선순위가 PCB에 저장
스케줄링 큐
스케줄링 큐 - 스케줄링에서의 큐는 반드시 선입선출 방식일 필욘 없음
- 준비 큐
- 대기 큐
- 입출력장치를 이용하기 위해 기다리는 줄
- 같은 장치를 요구한 프로세스들은 같은 큐에서 대기
선점형 스케줄링 (preemptive scheduling)
- 현재 CPU를 사용 중인 프로세스로부터 CPU 자원을 빼앗아 다른 프로세스에 할당
- 어느 한 프로세스의 자원 독점을 막고, 프로세스들에 골고루 자원을 배분할 수 있음
- 문맥 교환 과정에서 오버헤드가 발생할 수 있음
비선점형 스케줄링
- 현재 CPU를 사용 중인 프로세스의 작업이 끝날 때까지 프로세스 기다리기
- 선점형 스케줄링에 비해 문맥 교환에서 발생하는 오버헤드가 적음
- 모든 프로세스가 골고루 자원을 이용하기 어려움
스케줄링 알고리즘
1. 선입 선처리 스케줄링
- FCFS (First Come First Served) 스케줄링
- 단순히 준비 큐에 삽입된 순서대로 처리하는 비선점 스케줄링
- 먼저 CPU를 요청한 프로세스부터 CPU 할당
- 프로세스들이 기다리는 시간이 매우 길어질 수 있다는 부작용 (=호위 효과)
2. 최단 작업 우선 스케줄링
- SJF (Shortest Job First) 스케줄링
- CPU 사용이 긴 프로세스는 나중에 실행, CPU 사용 시간이 짧은 프로세스는 먼저 실행 -> 호위 효과를 방지
3. 라운드 로빈 스케줄링
- RR (Round Robin) 스케줄링
- 선입 선처리 스케줄링 + 타임 슬라이스(time slice)
- 타임 슬라이스 : 각 프로세스가 CPU를 사용할 수 있는 정해진 시간 -> 타임 슬라이스 크기가 중요
- 정해진 타임 슬라이스만큼의 시간 동안 돌아가면서 CPU를 이용하는 선점형 스케줄링
4. 최소 잔여 시간 우선 스케줄링
- SRT (Shortest Remaining Time) 스케줄링
- 최단 작업 우선 스케줄링 + 라운드 로빈 스케줄링
- 최단 작업 우선 스케줄링 : 작업 시간이 짧은 프로세스부터 처리하는 스케줄링 알고리즘
- 라운드 로빈 스케줄링 : 정해진 타임 슬라이스만큼 돌아가며 사용하는 스케줄링 알고리즘
- 정해진 시간만큼 CPU를 이용하되, 다음으로 CPU를 사용할 프로세스로는 남은 작업 시간이 가장 적은 프로세스 선택
5. 우선순위 스케줄링
- 프로세스들에 우선순위를 부여하고, 우선순위 높은 프로세스부터 실행
- 우선순위가 같은 프로세스들은 선입 선처리로 스케줄링
- 최단 작업 우선 스케줄링, 최소 잔여 시간 스케줄링 < 우선 순위 스케줄링
- 기아(starvation) 현상
- 우선 순위 높은 프로세스만 주구장창 실행
- 우선 순위 낮은 프로세스는 (준비 큐에 먼저 삽입되었음에도 불구하고) 실행 연기
- 기아 현상을 방지하기 위한 기법 : 에이징(aging)
- 오랫동안 대기한 프로세스의 우선 순위를 점차 높이는 방식
- 대기 중인 프로세스의 우선 순위를 마치 나이 먹듯 점차 증가시키는 방법
- 우선 순위가 낮아도 언젠가는 우선 순위가 높아짐
6. 다단계 큐 스케줄링
- Multilevel queue 스케줄링 -> 우선 순위 스케줄링의 발전된 형태
- 우선 순위별 준비 큐를 여러 개 사용하는 스케줄링 방식
- 우선 순위가 가장 높은 큐에 있는 프로세스를 먼저 처리
- 우선 순위가 가장 높은 큐가 비어 있으면 그 다음 우선 순위 큐에 있는 프로세스 처리
- 큐 별로 라운드 로빈, 타임 슬라이스 등 다르게 스케줄링을 적용할 수도 있음
- 큐 간의 이동이 불가 -> 우선 순위 낮은 프로세스는 계속해서 실행 연기 우려, 기아 현상 발생 가능성
7. 다단계 피드백 큐 스케줄링
- Multilevel feedback queue 스케줄링
- 다단계 큐 스케줄링의 발전된 형태
- 큐 간의 이동이 가능한 다단계 큐 스케줄링
- 에이징 기법 적용
- CPU 집중 프로세스의 우선 순위는 상대적으로 낮아지고, 입출력 집중 프로세스의 우선 순위는 상대적으로 높아짐
- 즉, 어떤 프로세스의 CPU 시간이 길면 우선 순위가 낮아지고, 어떤 프로세스가 낮은 우선 순위 큐에서 너무 오래 기다리면 우선 순위를 높이는 방식
- CPU 스케줄링 방식으로 알려져 있음
