CS
CPU 스케줄링
YunH2
2023. 8. 28. 23:26
CPU 스케줄링 알고리즘?
cpu가 하나의 프로세스 작업이 끝나면 다음프로세스 작업을 수행해야 하는데,
이때 어떤 프로세스를 다음에 처리할 지 선택하는 알고리즘
- Preemptive(선점)
- 프로세스가 CPU를 점유하고 있는 동안 I/O인터럽트가 발생하지 않았음에도 다른 프로세스가 해당 CPU를 강제로 점유할 수 있다
- Non-Preemptive(비선점)
- 한 프로세스가 CPU를 점유했다면 I/O나 인터럽트 발생 또는 프로세스가 종료될 때까지 다른 프로세스가 CPU를 점유하지 못한다
선점형 스케줄링
- SRT (Shortest Remaining Time) 스케줄링
- 짧은 시간 순서대로 프로세스를 수행
- 현재 CPU에서 실행 중인 프로세스의 남은 CPU 버스트 시간보다 더 짧은 CPU 버스트 시간을 가지는 프로세스가 도착하면 CPU가 선점된다.
- Round Robin 스케줄링
- 시분할 시스템의 성질을 활용한 방법
- 일정 시간( Time Quantum(Time Slice) )을 정하여 하나의 프로세스가 이 시간동안 수행하고 다시 대기 상태로 돌아간다
- Multi-level Queue 스케줄링
- 프로세스를 그룹으로 나누어, 각 그룹에 따라 Ready Queue(준비 큐)를 여러 개 두며, 각 큐마다 다른 규칙을 지정할 수도 있다
(ex. 우선순위, CPU 시간 등) - 큐와 큐 사이에도 우선순위를 부여
- 프로세스를 그룹으로 나누어, 각 그룹에 따라 Ready Queue(준비 큐)를 여러 개 두며, 각 큐마다 다른 규칙을 지정할 수도 있다
4. Multi-level feedback Queue 스케줄링
- 기본 개념은 Multi-level Queue와 동일하나, 프로세스가 하나의 큐에서 다른 큐로 이동 가능하다는 점이 다르다
- 위 그림에서 모든 프로세스는 가장 위의 큐에서 CPU의 점유를 대기한다. 이 상태로 진행하다가 이 큐에서 기다리는 시간이 너무 오래 걸린다면 아래의 큐로 프로세스를 옮긴다
비선점형 스케줄링
1. FCFS (First Come First Server)
- 준비 큐에 먼저 도착한 프로세스가 먼저 CPU를 점유하는 방식
- CPU를 할당받으면 CPU 버스트가 완료될 때까지 CPU를 반환하지 않으며, 할당되었던 CPU가 반환될 때만 스케줄링이 이루어진다
- 단점
Convoy Effect 발생
- 소요 시간이 긴 프로세스가 짧은 프로세스보다 먼저 도착해서 뒤에 프로세스들이 오래 기다려야 하는 현상
2. SJF (Shortest Job First)
- 다른 프로세스가 먼저 도착했더라도 CPU 버스트가 짧은 프로세스에게 CPU를 먼저 할당하는 방식
- 선점, 비선점 모두 가능하다
SJF가 가장 효율적인 CPU 스케줄링 방법 같지만, 매우 비현실적이다.
컴퓨터 환경에서는 프로세스의 CPU 점유 시간(Burst time)을 알 수 없다.
3. Priority
- 우선순위가 높은 프로세스가 먼저 선택되는 스케줄링 알고리즘
- 우선순위는 정수값으로 나타내며, 작은 값이 우선순위가 높다
- 선점, 비선점 모두 가능하다
단점
Starvation(기아) 현상
- CPU의 점유를 오랜 시간 동안 하지 못하는 현상
Priority 스케줄링 방식에서 우선순위가 매우 낮은 프로세스가 ready queue에서 대기하고 있다고 가정
이 프로세스는 아무리 오래 기다려도 CPU를 점유하지 못할 가능성이 매우 크다.
해결 방법
aging
- ready queue에서 기다리는 동안 일정 시간이 지나면 우선 순위를 일정량 높여주는 것
참고