스케줄링의 목적
스케줄링의 주된 목적은 멀티 프로세스 환경에서 모든 프로세스를 공평하게 실행하는 것이다.
•
공평성
모든 프로세스가 공평하게 실행되어야 한다.
특정 프로세스가 실행되지 않는 경우가 없도록 스케줄링해야 한다.
•
효율성
자원을 효율적으로 사용해 자원이 사용되지 않는 시간이 없도록 스케줄링해야 한다.
•
안정성
우선순위를 고려해 높은 우선순위의 프로세스를 먼저 처리하도록 스케줄링해야 한다.
•
반응 시간 보장
프로세스가 오랜 시간 응답이 없으면 사용자는 시스템이 멈춘 것으로 보기 때문에 일정 시간 내에 응답할 수 있도록 스케줄링해야 한다.
•
무한 연기 방지
특정 프로세스에 대한 처리가 무한히 연기되지 않도록 스케줄링해야 한다.
스케줄링의 단계
스케줄링은 장기 스케줄링, 중기 스케줄링, 단기 스케줄링으로 나뉜다.
•
장기 스케줄링(long-term scheduling)
준비 큐에 어떤 프로세스를 넣을지 결정해 메모리에 올라가는 프로세스 수를 조절한다.
잡 스케줄링(job scheduling) 또는 승인 스케줄링(admission scheduling)이라고도 한다.
주로 배치 처리 시스템에서 많이 사용되었으며 현대 운영체제에서는 시분할 시스템을 사용하기 때문에 대부분 사용하지 않는다.
•
중기 스케줄링(mid-term scheduling)
메모리에 로드된 프로세스 수를 동적으로 조절한다.
메모리에 프로세스가 많이 로드되면 스왑 아웃(swap out)해서 일부 프로세스를 통째로 저장한다.
스왑 아웃된 프로세스는 중단 상태(suspended)가 된다.
중단 상태는 준비 상태에서 스왑 아웃된 ‘중단된 준비 상태’와 대기 상태에서 스왑 아웃된 ‘중단된 대기 상태’로 구분된다.
•
단기 스케줄링(short-term scheduling)
준비 큐에 있는 대기 상태 프로세스 중 어떤 프로세스를 다음으로 실행할지 스케줄링 알고리즘으로 결정한다.
즉, 어떤 프로세스를 디스패치할지 결정하는데 이를 CPU 스케줄링이라고도 한다.
스와핑 용어 정리
•
스와핑(swapping)
스왑 아웃과 스왑 인처럼 프로세스를 통째로 메모리 영역과 저장 공간으로 옮기는 것을 스와핑이라고 한다.
스와핑하면 메모리 공간보다 많은 프로세스를 실행할 수 있다는 장점이 있다.
•
스왑 아웃(swap out)
프로세스가 실행되려면 메모리에 로드되어야 한다.
그런데 메모리 공간보다 많은 프로세스가 로드되는 경우가 있을 수 있다.
이럴 때 중기 스케줄러가 이벤트 발생을 기다리고 있는 프로세스를 통째로 저장 공간(SSD 등)으로 옮겨 저장하는 것을 스왑 아웃이라고 한다.
•
스왑 인(swap in)
스왑 아웃한 프로세스에서 이벤트 요청이 오면 해당 프로세스를 통째로 다시 메모리에 로드하는 것을 스왑 인이라고 한다.
스케줄러 관점에서 프로세스 스케줄링을 표현하면 다음과 같다.
1.
스케줄러가 준비 큐에 있는 프로세스 중 하나를 선택해 CPU에 디스패치 한다.
이때 스케줄링 알고리즘을 이용한다.
2.
CPU에서 프로세스를 실행한다 이때 프로세스는 실행 상태다.
•
프로세스 수행이 완료되면 프로세스를 종료한다.
•
일정 시간을 초과하면 인터럽트가 발생해 프로세스가 준비 큐로 들어가고 준비 상태가 된다.
•
입출력 요청이 들어오면 인터럽트가 발생한다. 이때 프로세스는 대기 큐로 들어가서 대기 상태가된다. 입출력이 완료되면 프로세스는 준비 큐로 들어간다.
3.
fork()가 호출되면 자식 프로세스가 생성되고 자식 프로세스는 준비 큐로 들어간다.
스케줄링 알고리즘
스케줄링 알고리즘은 CPU 스케줄러(단기 스케줄러)가 준비 큐에 있는 프로세스 중 어떤 프로세스를 실행시킬지 결정하는데 사용한다.
스케줄링 알고리즘은 스케줄링의 목적을 달성하기 위해 다음과 같은 기준으로 평가한다.
•
CPU 사용률
CPU를 놀리지 않고 사용하는지 판단
•
처리량
단위 시간(time unit)당 실행한 프로세스 수
•
응답 시간
프로세스에 요청이 발생했을 때 응답까지 걸리는 시간
•
반환 시간
프로세스가 로드된 이후부터 종료될 때까지 걸리는 시간
•
대기 시간
프로세스가 대기 큐에서 대기하는 시간의 총합
스케줄링 알고리즘은 비선점형과 선점형으로 나뉜다.
비선점형 스케줄링
비선점형 스케줄링(non-preemptive scheduling)은 실행 중인 프로세스가 종료될 때까지 다른 프로세스를 실행할 수 없음을 의미한다.
•
FCFS(First Come First Served) 스케줄링
준비 큐에 먼저 들어온 프로세스가 우선순위를 갖는 알고리즘이다.
준비 큐에 먼저 들어온 프로세스를 먼저 실행한다.
•
SJF(Shortest Job First) 스케줄링
실행 시간이 짧은 프로세스가 우선순위를 갖는 알고리즘으로 SJN(Shortest Job Next) 스케줄링이라고도 한다.
준비 큐에 있는 프로세스 중 CPU를 점유하는 실행 시간이 가장 짧은 프로세스부터 실행한다.
평균 대기 시간이 가장 짧지만 실행 시간이 긴 프로세스는 실행 시간이 짧은 프로세스에 밀려 기아 상태가 될 수 있다.
•
HRRN(Highest Response Ratio Next) 스케줄링
각 프로세스의 응답 비율을 계산하여 가장 높은 응답 비율을 가진 프로세스를 우선적으로 실행한다.
주로 대기 시간과 서비스 시간(즉, CPU 사용 시간)을 모두 고려하여 프로세스의 우선순위를 정하고 처리하여 기아 현상을 방지하는데 중점을 둔다.
선점형 스케줄링
선점형 스케줄링(preemptive scheduling)은 스케줄러가 실행 중인 프로세스를 중단시키고 다른 프로세스를 실행할 수 있음을 의미한다.
•
RR(Round Robin) 스케줄링
비선점형 스케줄링과 달리 프로세스 간 우선순위가 없다.
모든 프로세스를 순서대로 일정 시간 동안 실행하며 일정 시간을 초과하면 다른 프로세스를 실행한다.
여기서 일정 시간은 ‘시간 단위’를 의미하며 타임 퀀텀 또는 타임 슬라이스라고도 한다.
일반적으로 시간 단위는 10~100밀리초다.
컨텍스트 스위칭이 빈번하게 일어나서 오버헤드가 크다는 단점이 있지만 모든 프로세스가 반복 수행되어 응답 속도가 빠르다는 장점도 있다.
•
SRTF(Shortest Remaining Time First) 스케줄링
준비 큐에서 대기 시간이 가장 짧게 남은 프로세스를 우선 수행하는 알고리즘이다.
한 프로세스가 실행 중일 때 실행 시간이 더 짧은 프로세스가 준비 큐에 들어오면 실행 시간이 더 짧은 프로세스가 CPU를 차지하게 된다.
평균 대기 시간이 짧다는 장점이 있지만 수행 시간이 긴 프로세스는 기아 상태가 되기 쉽다.
•
멀티 레벨(multi level) 스케줄링
준비 큐를 목적에 따라 여러 개로 분리해 사용하는 알고리즘이다.
분리한 큐는 각각 우선순위가 있고 각자 다른 스케줄링 알고리즘을 적용할 수 있다.
여러 개의 큐는 foreground 큐와 background 큐로 나뉜다.
foreground 큐에는 응답 속도가 중요한 프로세스가 들어가고, background 큐에는 응답 속도보다 성능을 중요시하는 프로세스가 들어간다.