정의
CPU 를 사용하려는 프로세스들 사이의 우선순위를 관리하는 작업으로, 어떤 프로세스에 작업을 얼마나 할당할 지를 결정한다.
- CPU 스케줄링은 I/O 같은 자원을 사용할 수 없어 프로세스가
waiting상태로 진입한 동안 다른 프로세스가 CPU 를 사용할 수 있도록 해준다. - CPU 스케줄링의 목표는 프로세스들에게 자원을 최대한 공평하게 배분해 처리율과 CPU 사용률을 증가시키고 오버헤드, 응답시간, 대기시간을 최소화하는 것이다.
CPU 스케줄링이 필요한 상황
CPU 스케줄링이 필요한 상황은 크게 4 가지가 있다.
프로세스의 상태
new : 프로세스 생성
ready : 프로세스가 자원을 사용하고 있지 않지만 언제든지 사용할 수 있는 상태로, CPU의 할당을 기다리는 상태
running : 프로세서를 차지해서 명령어들을 실행하고 있는 상태
waiting : 프로세스가 실행하다 CPU를 반납하고, 입출력이나 어떤 사건(event)이 완료되기를 기다리는 상태
termianted : 프로세스 종료
running상태에 있던 프로세스가 I/O 요청 등에 의해waiting상태가 되는 경우running상태에 있던 프로세스가 타이머 인터럽트에 의해서ready상태가 되는 경우waiting상태에 있던 프로세스의 I/O 작업이 완료되어 인터럽트가 발생하고, 그 결과 프로세스의 상태가ready상태가 되는 경우running상태에 있던 프로세스가 종료되어termianted되는 경우
참고 : ready vs waiting
ready 와 waiting 은 어떤 상태의 변화를 기다리는 것이지만, ready 는 다른 프로세스가 차지하고 있는 CPU 의 할당을 기다리고 있는 것이고, waiting 는 I/O 나 어떤 사건(event)를 기다리고 있는 것이다.
예를 들어, 로그인을 할 경우 ID/PW 을 받는 작업을 하는 동안 running 에서 waiting 상태가 되어서 데이터가 들어오기를 기다린다. 이 후, ID/PW 가 입력되면 waiting 에서 다시 running 가 된다.
로그인이 끝나면 인터럽트 신호를 보내고 running에서 ready상태가 된다. 즉, CPU 의 사용률을 높이기 위한 작업에 필요한 프로세스 상태라고 생각하면 된다.
스케줄링 분류
CPU 스케줄링은 크게 선점형 스케줄링과 비선점형 스케줄링 두 가지로 나뉜다.
선점형 스케줄링
프로세스가 CPU를 점유하고 있는 중 다른 프로세스에게 CPU 제어권을 빼앗긴다.
- 실시간 응답환경이나 Deadline 응답환경 등 우선순위가 높은 프로세스를 빠르게 처리해야 하는 경우에 유용하다.
Round Robin
- 똑같은 사용 시간을 정해서 그 시간 동안만 CPU를 할당하는 방식이다.
- 할당 시간이 만료되면 Ready Queue 에 삽입
- 할당 시간이 너무 크면 FCFS 와 동일하게 동작하고 너무 작으면 context switching 의 오버헤드가 발생한다.
다단계 큐(Multi-Level Queue)
- 프로세스들이 CPU 를 한 줄로 기다리는게 아니라 여러 줄로 기다리는 방식이다.
- 프로세스들을 종류별로 나뉜 큐에 넣는다.
- 각 큐는 독자적인 스케줄링을 가진다 (우선순위, CPU 시간 등등..)
다단계 피드백 큐(Multi-Level FeedBack Queue)
- 다단계 큐에 동적인 프로세스 우선순위 변화를 적용했다.
- 프로세스는 생성 시 가장 높은 우선순위 Ready Queue 에 삽입돼서 실행하다가 CPU 시간 할당량이 끝나면 한 단계 아래의 Ready Queue 에 들어간다.
- 가장 하위 Queue 는 FCFS 스케줄링 방식인데, 여기서 너무 오래 대기하면 다시 상위 큐로 이동한다. (에이징 기법을 통한 기아상태 예방)
비선점형 스케줄링
프로세스가 CPU를 점유하고 있는 중 다른 프로세스에게 CPU 제어권을 빼앗기지 않는다.
- 모든 프로세스에 대해서 공정하게 처리할 수 있지만 짧은 작업을 수행하는 프로세스가 긴 작업 시간의 프로세스가 끝나기를 대기하는 상황이 발생할 수 있다. (Convoy Effect)
FCFS
- 선입선출 방식의 스케줄링 방식
- 짧은 프로세스가 긴 프로세스를 기다리는 convoy effect 가 발생할 수 있다.
SJF (Shortest Job First)
- 프로세스 도착 순서와 관계없이 실행 시간(CPU Burst Time)이 가장 적은 프로세스에게 CPU 를 할당해주는 방식
- 평균 대기시간이 가장 짧은 최적의 스케줄링 방식이지만, 실행 시간이 긴 프로세스들이 영원히 할당을 받지 못하는 기아현상이 발생할 수 있다.
- 프로세스의 CPU 실행 시간을 얼마나 가지는지 미리 알 수 없기 때문에 실제로 적용하기 어렵다.
- 선점, 비선점 모두 적용이 가능하다.
Priority
- 우선순위가 높은 프로세스가 먼저 선택되는 스케줄링 방식
- 우선순위가 낮은 프로세스가 오랜 시간동안 CPU 를 할당받지 못하면 Aging 기법을 통해 우선순위를 높이는 방법을 사용한다.
