1. 스케줄링의 단계
- 스케줄링 : 여러 프로세스들이 번갈아 사용해야 하는 자원이 있을 경우, 주어진 시점에서 어떤 프로세스가 이 자원을 사용할 수 있도록 해줄 것인가를 결정하는 것
- 스케줄링이 요구되는 시점을 기준으로 장기, 중기, 단기 스케줄링 세 가지로 나뉜다.
- 장기 스케줄링(작업 스케줄링) : 어느 작업을 커널에 등록시켜 프로세스를 만들어 줄 것인가를 결정하는 것. 요청된 일을 프로세스로 만들어 시스템에 알려진 일거리로 추가하느냐를 결정하는 것으로 다중 프로그래밍의 정도를 조절하는 역할, 대부분 FIFO방식
- 중기 스케줄링 : 보류 상태의 프로세스들 중에서 어느 프로세스에게 메모리를 할당해 줄 것인가를 결정
- 단기 스케줄링 : 준비 상태에 있는 프로세스들 중에서 어드 프로세스에게 CPU를 할당할지를 결정하는 것
2. 스케줄링의 목적과 기준
- 스케줄링의 목적 : CPU를 할당받을 프로세스를 잘 골라 실행시켜줌으로써 전체적으로 시스템의 성능을 높이자는 것
- 어떤 것들이 성능을 평가하는 기준인가에 따라
- 사용자의 관점
- 응답 시간 : 대화형 시스템에서 프로세스의 요청에 대해 시스템이 최초로 출력을 내주기 시작할 때까지 걸린 시간, 직접적으로 시스템의 성능을 느낄 수 있는 지표
- 반환 시간 : 일괄 처리의 경우 요청으로부터 결과를 돌려받는 데까지 걸린 시간
- 예측가능성 : 요청한 일이 얼마 후 쯤에는 완료할 수 있을 것이라는 예측
- 시스템의 관점
- 처리량 : 단위 시간에 완료되어진 프로세스의 개수
- 활용도 : 주어진 시간동안 특정 자원이 실제로 가동된 시간의 비율로 계산한 지표
- 기타사항
- 공평성 : CPU사용 시간을 공평하게 나누어 주었는지 여부
- 특정 프로세스가 장시간 CPU를 받지 못하는 경우는 최대한 피하도록 한다.
- 시스템에 있는 여러 자원들을 가급적 균형있게 사용하도록 한다.
- 스케줄링 정책을 만들 때 고려해야 할 기준들
- 연산 위주(CPU-bound) 프로세스와 입출력 위주(I/O-bound) 프로세스 중, 어떤 종류의 프로세스를 더 우대할 지를 고려
- 시스템이 사용될 환경에 따라 응답 시간을 우선으로 할 지, 처리량을 우선할지 고려
- 특정 프로세스에게 우선적으로 빠른 응답시간을 보장해야 하는 경우가 있다면 이를 가능케 하는 기능 제공
- 프로세스의 크고 작음에 따라 어떤 것을 우선적으로 처리할 지의 기준을 가지고 있어야 한다.
3. 스케줄링 기법들
- 스케줄링이 가동되어야 할 시점들
- 프로세스가 실행상태에서 대기 상태로 전환될 때. 대표적인 예가 입출력 요청 시 - 비선점
- 프로세스가 실행 상태에서 준비 상태로 전환될 때. 시간 종료와 같은 인터럽트 발생 시 - 선점
- 프로세스가 대기 상태에서 준비 상태로 전환될 때. 예를 들어, 입출력의 종료 시 - 선점
- 프로세스가 수행을 마치고 종료될 때 - 비선점
- 스케줄링 기법 분류
- 비선점 스케줄링 : 한 프로세스가 CPU를 할당 받았을 때 CPU를 스스로 반납할 때까지 계속 사용하도록 허용하는 방법
- 선점 스케줄링 : CPU를 할당 받아 실행 중인 프로세스로부터 CPU를 선점하여(빼앗아) 다른 프로세스에게 할당할 수 있는 방식
- FCFS(First Come Fisrt Service) 스케줄링
- 준비 큐에 먼저 도착한 프로세스에게 먼저 CPU를 할당해주며, CPU를 할당받은 프로세스는 스스로 CPU를 반납할 때까지 CPU를 독점하여 사용하는 비선점 방식
- 프로세스가 CPU를 독점하여 사용하기 때문에 아주 긴 프로세스가 실행될 경우 뒤에 있는 프로세스들은 오래 기다려야 하므로 대화식 시스템에 적합하지 않으며, 평균 응답 시간이 길어지는 단점이 있다.
- 반면에 준비 상태 프로세스들의 개수와 크기를 짐작할 수 있다면 각각의 프로세스들이 언제쯤이면 실행될 수 있을지를 예측할 수 있고, 도착 순서만이 실행 순서를 결정짓는다는 관점에서 공평하다고 할 수 있다.
- 평균 응답 시간이 짧다고 모든 프로세스의 응답 시간이 짧아진다는 것은 아니지만 보편적으로 그럴 확률을 높일 수 있다
- SPN(Shortest Process Next) 스케줄링
- 준비 큐에서 기다리고 있는 프로세스 중에서 가장 짧은 것을 먼저 실행시켜 주는 비선점 방식
- 평균 응답 시간을 최소화할 수있지만 실행 시간이 긴 프로세스가 CPU를 할당 받지 못하고 계속해서 대기하는 무한 대기 현상이 발생할 수 있다.
- FCFS와 비교했을 때 전체적으로 빠른 응답시간을 기대할 수 있으나, 긴 프로세스일수록 그 편차가 커져 예측가능성은 오히려 떨어질 것이다.
- 에이징 : 무한대기 가능성을 낮추는 방법, 기다린 시간만큼 우선순위를 높이는 것
- 각 프로세스들의 크기를 실행 전에는 정확히 알 수 없음에도 그 크기를 가지고 스케줄링 해야한다.
- 지수 평균 : 프로세스의 크기를 실행 전에 추정해보는 방법
- SRT(Shortest Remaining Time) 스케줄링
- SPN을 선점 방식으로 운영하는 것
- 새로 도착하는 프로세스의 실행 시간 크기는 완료까지 남은 시간과 같으며, CPU를 할당받아 실행된 양만큼 완료까지 남은 시간은 줄어들게 될 것이다.
- 준비큐에서 완료까지 남은 CPU요구량이 가장 짧은 것을 먼저 실행시켜주는 방식이며, 실행 도중 남은 실행 시간이 더 적은 프로세스가 준비 큐에 들어올 경우 현재 실행중인 것을 중단하고 새 프로세스에게 CPU를 할당하는 선점 방식이다.
- 잦은 선점으로 인한 문맥교환의 부담이 있다.
- 반환 시간을 놓고 따져보면 SRT가 SPN보다 우수함
- Future-knowlege 스케줄링 : 처음 1초동안 CPU를 쉬게 하여 처음 1초 동안 미래를 알 수 있다면
- HRRN(Highest Response Ratio Next) 스케줄링
- SPN과 SRT방식의 약점인 수행 시간이 긴 프로세스의 무한 대기 현상을 방지하기 위한 기법.
- 준비 큐에 있는 프로세스들 중에서 응답률이 가장 높은 프로세스에게 높은 우선순위를 주며, 비선점식 방식이다.
- 응답률이란 프로세스의 크기 즉, CPU요구량에 대한 대기 시간의 비율로 다음과 같이 계산된다.
- 이 기법을 사용하면 프로세스가 기다리는 시간이 길어질수록 우선순위가 높아지므로 수행 시간이 긴 프로세스도 머지않아 CPU를 할당받을 수 있게된다.
- CPU 요구량이 분모에 있어큰 프로세스일수록 우선순위가 낮으므로 평균 응답 시간을 단축할 수 있다.
- 실행되지 못하고 기다리는 동안 대기 시간은 계속 증가할 것이므로 스케줄링을 할 때마다 준비 큐의 모든 프로세스들에 대해 응답률을 계산하여 CPU를 줄 프로세스를 선정하고, 선택된 프로세스는 자발적으로 CPU를 내놓지 않는 한 실행을 계속할 수 있다.
- 라운드 로빈(Round-Robin) 스케줄링
- FCFS 스케줄링을 기반으로 하여 CPU를 할당하되 각 프로세스는 한 번에 쓸 수 있는 CPU 시간 크기 즉, 시간 할당량이 지나면 시간 종료 인터럽트에 의해 CXU를 뺏기게 되는 선점 방식이다.
- CPU를 반환한 프로세스는 다시 준비 큐의 끝에 들어가게 되고, 준비 큐의 맨 앞에 있는 프로세스가 CPU를 할당받게 된다.
- 이 기법은 FCFS 기법에서처럼 한 프로세스가 CPU를 독점하는 단점을 방지할 수 있다.
- CPU의 선점에 따른 문맥교환의 오버헤드를 감수해야 한다.
- 대화식 시스템, 시분할 시스템에 적합한 방식
- 시간 할당량이 매우 크면 FCFS스케줄링 방식과 시스템이 성능이 같고 작을수록 문맥교환이 자주 발생해 문맥교환의 오버헤드가 커진다.
<가상 라운드 로빈>
- 연산 위주의 프로세스가 입출력 위주의 프로세스보다 CPU사용에 있어 우대받게 되기 때문에 이를 보완하기 위해 입출력을 마친 프로세스가 들어가는 준비 큐를 따로 하나 두고 우선순위는 더 높게 하되, 이 큐에서 CPU를 받을 때는 이전 입출력이 발생했을 때 쓰지 못하고 남긴 시간 할당량만큼만 준다.
- 물론 시간 할당량을 다 사용한 프로세스는 시간 종료 인터럽트와 함께 원래의 즌비 큐로 들어가도록 하므로 우선순위가 다른 준비 큐가 두 개 있는 경우이다.
- 다단계 큐(Multi-leve Queue) 스케줄링
- 정적 우선순위를 사용하는 스케줄링을 구현
- 같은 우선순위 값을 가지는 프로세스들을 위해 큐가 필요함과 동시에 서로 다른 우선순위의 프로세스들을 구별하고 관리하기 위해 우선순위의 개수만큼 큐가 필요하다.
- 프로세스들은 자신의 우선순위 값에 해당하는 큐에 들어가게 되며, 우선순위가 낮은 하위 단계 큐의 작업은 실행 중이더라도 상위 단계 큐에 프로세스가 도착하면 CPU를 뺏기는 선점 방식이다.
- 정적 우선순위이므로 큐들 간에 프로세스의 이동이 불가능함은 당연하다.
- 다단계 피드백 큐(Multi-level Feedback Queue, MFQ) 스케줄링
- 짧은 프로세스들에게 유리하면서 입출력 프로세스를 우대할 수 있는 스케줄링 기법
- 입출력 프로세스를 우대함으로써 CPU를 포함한 전체 자원들의 활용도를 높여 시스템의 성능을 높일 수 있다.
- 동적 우선순위 기반의 선점 방식
- 여러 단계의 큐가 있으며 각 단계마다 서로 다른 CPU 시간 할당량을 가지도록 하는데, 우선순위가 높은 단계의 큐일수록 시간 할당량은 작도록 한다.
- 새로운 프로세스는 최상위 단계의 준비 큐에 들어간 후 FCFS의 순서로 CPU를 할당받아 실행되다가 그 큐의 시간 할당량이 끝나면 한 단계 아래의 준비 큐에 들어감으로써 결과적으로 우선순위가 한 단계 낮아지게 된다.
- 각 단계에서도 그 단계 큐의 시간 할당량을 다 사용할 때까지 계속 실행된다면 다음 단계의 큐로 들어가게 되며, 마지막 단계에서는 더 내려갈 단계가 없으므로 라운드 로빈 방식으로 실행될 것이다.
- 어느 단계든 시간 할당량이 끝나기 전에 입출력응로 CPU를 내놓게 되면 다시 준비 상태가 되었을 때 한 단계 위의 큐에 들어가도록 함으로써 우선순위를 높여준다.
- 중간 단계의 맨 앞에 있는 프로세스는 상위 단계의 큐들이 비어있는 경우에만 CPU를 받을 수 있고, 할당된 CPU는 시간 종료 인터럽트에 의해 선점되나 입출력이 발생하지 않는 한 그 큐의 시간 할당량까지 쓸 수 있다.
- 다단계 큐와 차이점 : 중간 단계의 큐에서 일단 CPU를 받은 프로세스는 실행 중 상위 단계의 프로세스에 의해 선점되지 않고 부여받은 시간 할당량까지는 보장된다.
- 상대적으로 짧은 프로세스들이 하위 큐까지 내려가지 않도록 함으로써 비교적 높은 우선순위를 유지할 수 있도록 해주며, 입출력은 우선 순위의 상향조정으로 이어져 입출력 위주 프로세스들이 선호됨을 알 수 있다.
- 프로세스의 성격에 맞도록 우선순위를 조정해 줌으로써 적응성이 있는 스케줄링이 가능
- Fair-share 스케줄링
- 지금까지 본 기법들은 스케줄링의 대상이 되는 모든 프로세스들을 하나의 그룹으로 취급했다.
- 그룹별로 일정량의 CPU시간을 할애했을 때, 특정 그룹에 속한 프로세스의 과도한 CPU사용은 그 그룹 내의 다른 프로세스들에게만 불이익을 줄 뿐, 다른 그룹으로까지 파급되지 않도록 하겠다는 것
4. 실시간 스케줄링
- 경성 실시간 시스템 : 작업이 마감시한 내에 완료되지 않으면 시스템이 중지되는 치명적인 결과 초래(일반적인 실시간이라는 의미)
- 연성 실시간 시스템 : 작업이 마감시한 내에 종료되지 않으면 데이터의 손실 등 피해가 발생하지만 시스템은 계속해서 운영 가능한 시스템
<실시간 시스템에서 마감시한 내에 모든 프로세스들이 완료되도록 하는 방법>
- 정적인 방법 : 프로세스들의 특징과 개수를 알 수 있는 경우에 유용
- 동적인 방법 : 프로세스의 생성 시간이나 특성을 알 수 없는 경우에 사용된다.
- RM
- 정적 스케줄링 방식으로 크기와 개수가 알려진 프로세스들이 각자 주기적으로 발생되는 환경에서 사용된다.
- 프로세스들은 서로 독립적이고 주기적으로 수행되는 환경에서 각 프로세스의 마감시한으 각자의 주기와 같다고 가정하고 주기가 짧을수록 높은 우선순위를 받게 된다.
- 낮은 우선순위의 프로세스가 더 높은 우선순위의 프로세스가 도착할 경우 CPU를 빽시게 되는 선점 방식이며, 정적 환경에서 최적의 기법으로 알려져 있다.
- 스케줄링 비용이 적게 드는 대신, 새로운 프로세스가 추가되는 환경에 바로 적응하지 못하고 이 프로세스를 추가하여 전체 스케줄링을 다시 해야 하는 단점이 있다.
- EDF
- 프로세스의 마감시한이 가까울수록 우선순위를 높게 부여하는 선점 방식의 동적 스케줄링
- 우선순위에 의해 실행 중 CPU를 뺏길 수 있으며, 한 프로세스의 실행이 완료될 경우에는 마감 시한이 가장 가까운 것을 찾아 스케줄한다.
- 모든 프로세스가 주기적일 필요는 없으며 주기가 있을 경우에는 마감시한을 주기로, 그렇지 않을 경우는 마감시한이 알려져야 한다.
- 새로운 프로세스의 동적인 수용이 허용되나, 그럴 때마다 가능한 스케줄을 찾기 위한 계산을 해야 하는 부담이 있다.
- RM과 EDF모두 프로세스들이 상호 독립적이라는 가정을 하고 있기 때문에 공유 데이터를 통한 프로세스 간의 통신이 있는 경우에는 적용할 수 없다.
5. 윈도에서의 스케줄링
- 윈도는 스레드 단위로 CPU를 할당하는 우선순위에 의한 선점 스케줄링 방식이다.
- 두 개의 클래스로 구분하여 우선순위 16부터 31은 실시간 클래스를 위해, 0부터 15는 일반 클래스를 위해 배정한다.
- 실시간 클래스에 속하는 16개의 큐는 정적 우선순위로 운영되므로 다단계 큐로, 일반 클래스의 16개 큐는 동적 우선순위를 위해 위에서 배운 MFQ로 구현된다.
- 실시간 클래스의 다단계 큐 각각은 라운드 로빈 방식으로 스케줄링 되고 현재 실행 중인 스레드 보다 우선순위가 높은 스레드가 준비 상태가 되면 CPU가 선점된다.
