Ch 04. CPU 스케줄링

스케줄링(Scheduling) : 기다리고 있는 여러 프로세스 중에 누구를 선택해야 할 지에 대한 방식과 기준

 

4.1 스케줄링의 단계

스케줄링이 요구되는 시점에 따라 장기, 중기, 단기로 구분됨

 

1) 장기 스케줄링 ( = 작업 스케줄링)

어느 작업을 커널에 등록시켜 프로세스로 만들어 줄 것인가를 결정하는 것.

요청된 일을 프로세스로 만들어 시스템에 알려진 일거리로 추가하느냐를 결정하는 것. (다중 프로그래밍의 정도를 조절하는 역할)

수행 횟수가 적으며, 대부분 FIFO 방식.

 

일괄처리 시스템) 새로 작업이 들어오면 디스크에 놓아둔 채 일괄처리 큐에서 대기하도록 한 후 장기 스케줄러를 거쳐 프로세스가 되도록 함

시분할) 사용자의 접속 시도를 허용할지 말지를 결정하는 단계

 

2) 중기 스케줄링

보류 상태의 프로세스들 중에서 어느 프로세스에게 메모리를 할당해줄 것인가를 결정.

스왑아웃된 프로세스 중 어떤 프로세스를 다시 스왑인 할 것인가를 결정. (단기와 장기의 중간 단계)

 

3) 단기 스케줄링

준비 상태에 있는 프로세스들 중에서 어느 프로세스에게 CPU를 할당할 지를 결정하는 것. 프로세스 스케줄러 or 디스패처에 의해 수행된다.

 

4.2 스케줄링의 목적과 기준

CPU를 할당받을 프로세스를 잘 골라 실행시켜줌으로써 전체적으로 시스템의 성능을 높이자는 것이 스케줄링의 목적.

 

시스템 성능 평가 지표 

1) 사용자의 관점 : 응답 시간

-> 프로세스의 요청에 대해 시스템이 최초로 출력을 내주기 시작할 때까지 걸린 시간.

일괄 처리의 경우 반환 시간이 중요 지표가 될 것이며, 예측 가능성 (요청한 일이 얼마 후 쯤에는 완료될 수 있을 것) 등도 지표로 활용할 수 있다.

 

2) 시스템의 관점 : 

처리량 : 단위 시간에 완료되어진 프로세스의 개수. 스케줄링을 통해 CPU가 얼마나 잘 활용되었는가.

활용도 : 주어진 시간 동안 특정 자원이 실제로 가동된 시간의 비율로 계산한 지표

 

3) 그 외

공평성 : 가능한 CPU 사용 시간을 공평하게 나누어 주어야 한다는 것. 특정 프로세스가 장기간 CPU를 받지 못하게 되는 경우는 최대한 피하고, 여러 자원들을 가급적 균형 있게 사용되도록 해야 한다는 것

 

대화형 시스템 : 응답 시간

일괄처리 시스템 : 처리량

 

스케줄링 정책을 만들 때 고려해야 할 기준

1) 프로세스의 성격

연산 위주 프로세스 : CPU를 사용하는 연산 > 입출력

입출력 위주 프로세스 : CPU를 사용하는 연산 < 입출력

 

4.3 스케줄링 기법들

1. 프로세스가 실행 -> 대기로 전환될 때 입출력 요청

2. 프로세스가 실행 -> 준비로 전환될 때 시간 종료와 같은 인터럽트가 발생할 때

3. 프로세스가 대기 -> 준비로 전환될 때 입출력의 종료

4. 프로세스가 수행을 마치고 종료될 때

 

스케줄링 기법 

1) 비선점 스케줄링 (1,4)

: 한 프로세스가 CPU 할당 받았을 때 스스로 반납할 때까지 계속 사용하도록 허용

 

2) 선점 스케줄링 (2,3)

: CPU를 할당받아 실행 중인 프로세스로부터 CPU를 선점(빼앗아)하여 다른 프로세스에 할당할 수 있는 방식

 

 

- FCFS (First Come First Service) 스케줄링 (=FIFO)

준비 큐에 먼저 도착한 프로세스에게 먼저 CPU를 할당해주는 비선점 방식

대화식 시스템에 적합하지 않으며, 평균 응답 시간이 길어진다.

준비 상태 프로세스들의 개수와 크기를 짐작할 수 있다면 각각의 프로세스들의 실행 시간을 예측할 수 있고, 도착 순서만이 실행 순서를 결정짓는다는 점에서 공평하다고 할 수 있다.

 

- SPN (Shortest Process Next) 스케줄링 (=SJF (Shortest Job First) 스케줄링)

준비 큐에서 기다리고 있는 프로세스 중에서 가장 짧은 (=CPU 요구량이 가장 적은) 것을 먼저 실행하는 비선점 방식

처리량에 관해서 매우 훌륭한 성능, FCFS에 비해 전체적으로 빠른 응답 시간. 그러나 긴 프로세스일 수록 편차가 커져 예측가능성은 떨어질 것임.

각 프로세스의 크기를 실행 전에는 정확히 알 수 없음에도 그 크기를 가지고 스케줄을 해야 함 -> 해결책 : 지수 평균 방법

 

에이징 : 기다린 시간만큼 우선순위를 높여 실행 가능성을 높여주는 것

 

- SRT(Shortest Remaining Time) 스케줄링

SPN을 선점 방식으로 운영하는 것.

새로 도착하는 프로세스의 실행 시간 크기 = 완료까지 남은 시간

CPU를 할당받아 실행된 양만큼 완료까지 남은 시간은 줄어들게 될 것

 

준비 큐에서 완료까지 남은 CPU 요구량이 가장 짧은 것을 먼저 실행하는 방식. 

실행 도중 남은 실행 시간이 더 적은 프로세스가 준비 큐에 들어올 경우 현재 실행 중인 것을 중단하고 새 프로세스에게 CPU를 할당하는 선점 방식. -> 많은 문맥 교환이 요구됨.

 

- Future-knowledge 스케줄링

가까운 미래에 도착하게 될 프로세스의 정보를 알 수 있다면 기다렸다가 SPN을 적용하여 CPU를 쉬게 하는 것이 더 우수한 결과를 가질 수도 있음

 

- HRRN(Highest Response Ratio Next) 스케줄링

SPN과 SRT의 무한 대기 현상을 방지하기 위한 기법.

준비 큐에 있는 프로세스들 중에서 응답률이 가장 높은 프로세스에게 높은 우선순위를 주는 비선점 방식.

 

응답률 =  (대기시간 + CPU 요구량) / CPU 요구량

 

분모를 보면 큰 프로세스일 수록 우선순위가 낮으므로 응답 시간의 단축도 꾀하고 있음

 

- 라운드 로빈 스케줄링

FCFS 스케줄링을 기반으로 CPU를 할당하되, 각 프로세스는 한 번에 쓸 수 있는 CPU의 시간 크기, 시간 할당량이 지나면 시간 종료 인터럽트에 의해 CPU를 뺏기게 되는 선점 방식.

 

CPU를 반환한 프로세스는 다시 준비 큐의 끝에 들어가게 됨.

한 프로세스가 CPU를 독점하는 단점을 방지할 수 있으나 CPU 선점에 따른 문맥교환의 오버헤드를 감수해야 한다.

 

- 가상 라운드 로빈 스케줄링

시간 할당량 부분을 보상받지 못한 채 큐의 맨 뒤로 들어가는 문제 발생

-> 입출력을 마친 프로세스가 들어가는 준비 큐를 따로 하나 두고 우선순위는 더 높게 하되, 이 큐에서 CPU를 받을 때는 이전 입출력을 발생했을 때 쓰지 못하고 남긴 시간 할당량만큼만 주도록 함.

 

+) 우선순위

여러 가지를 고려하여 계산된 값을 프로세스가 생성될 때 부여하고, 이 값을 기준으로 스케줄링 하는 방식을 모두 우선순위 스케줄링이라 부르고, 속성상 선점 방식을 취하게 됨.

정적 : 프로세스가 생성될 때 부여된 우선순위가 완료 때까지 변하지 않는 값

동적 : 시스템에 있는 동안 조정되도록 하는 것

구매 우선순위 : 실행을 빨리할 목적으로 비용을 지불하고 우선순위를 높이도록 하는 것

 

- 다단계 큐 (Multi-level Queue) 스케줄링

정적 우선순위를 사용하는 스케줄링을 구현하기에 적합한 자료구조

같은 우선순위 값을 가지는 프로세스들을 위해 + 서로 다른 우선순위의 프로세스들을 구별하고 관리하기 위해 우선순위의 개수만큼 큐가 필요하게 된다.

 

- 다단계 피드백 큐 (MFQ) 스케줄링

프로세스들의 CPU 요구량을 몰라도 짧은 프로세스들에게 유리하면서 입출력 프로세스를 우대할 수 있는 스케줄링 기법

동적 우선순위를 기반으로 하는 선점 방식으로 운영됨.

여러 단계(우선순위 개수만큼)의 큐가 있으며, 각 단계마다 서로 다른 CPU 시간 할당량을 가지게 함.

우선순위 높은 큐일수록 시간 할당량은 작도록 한다.

새로운 프로세스는 최상위 단계의 준비 큐에 들어간 후 FCFS의 순서로 COU를 할당받아 실행되다가 시간 할당량이 끝나면 한 단계 아래 준비 큐에 들어감 (=우선순위가 한 단계 낮아지게 됨)

 

짧은 프로세스들이 하위 큐까지 내려가지 않도록 함으로써 비교적 높은 우선순위를 유지할 수 있도록 해줌.

프로세스의 성격에 맞도록 우선순위를 조정해줌으로써 adaptive한 스케줄링 가능

 

- Fair-share 스케줄링

프로세스들의 특성이나 중요도에 따라 그룹으로 나누고, 각각의 그룹에 서로 다르게 CPU 시간을 할당하는 기법

 

4.4 실시간 (Realtime) 스케줄링

실행될 모든 프로세스들이 정해진 시간 내에 완료되어야 하는 시스템

 

1) 경성 실시간 시스템 (Hard Realtime)

작업이 마감시한 내에 완료되지 않으면 시스템이 중지되는 등의 치명적인 결과를 초래하는 시스템

마감시한을 넘긴 후 완료되는 일은 아무 가치가 없다.

 

2) 연성 실시간 시스템 (Soft Realtime)

작업이 마감시한 내에 종료되지 않으면 데이터의 손실 등 피해가 발생하지만 시스템은 계속해서 운영 가능한 시스템

마감시한을 넘긴 후부터는 완료의 가치가 점점 떨어지게 된다.

 

정적 : 프로세스들의 특징과 개수를 알 수 있는 경우에 유용

동적 : 프로세스의 생성 시간이나 특성을 알 수 없는 경우에 사용

 

 

- RM (Rate Monotonic) 알고리즘

정적 스케줄링 방식. 

프로세스들은 서로 독립적이고, 주기적으로 수행되는 환경에서 각 프로세스의 마감시한은 각자의 주기와 같다고 가정하고, 주기가 짧을수록 높은 우선순위를 받게 된다.

더 높은 우선순위의 프로세스가 도착할 경우 CPU를 뺏기게 되는 선점 방식.

 

스케줄링 비용이 적게 드는 대신, 새로운 프로세스가 추가되는 환경에 바로 적응하지 못하고 이 프로세스를 추가하여 전체 스케줄링을 다시 해야 하는 단점이 있다.

 

- EDF (Earlist Deadline First) 알고리즘

프로세스의 마감시한이 가까울수록 우선순위를 높게 부여하는 선점 방식의 동적 스케줄링

(동적 : 새로운 프로세스가 도착할 때 바로 대응할 수 있다는 것)

우선순위에 의해 실행 중 CPU를 뺏길 수 있으며, 한 프로세스의 실행이 완료될 경우에는 마감 시한이 가장 임박한 것을 찾아 스케줄한다.

주기가 있을 경우에는 마감시한을 주기로, 그렇지 않을 경우에는 마감시한이 알려져야 한다.

 

4.5 윈도에서의 스케줄링

윈도 : 스레드 단위로 CPU를 할당하는 우선순위에 의한 선점 스케줄링 방식

두 개의 클래스로 구분. 우선순위 16~31 : 실시간 클래스 / 0~15 : 일반 클래스

실시간 클래스에 속하는 16개의 큐

: 정적 우선순위로 운영되므로 다단계 큐. 각각은 라운드 로빈 방식으로 스케줄링 됨

일반 클래스에 속하는 16개의 큐 : 동적 우선순위를 위해 MFQ로 구현됨