[OS] 프로세스 스케줄링

CPU 스케줄링

요즘과 같은 다중프로그래밍 환경에서 가장 중요한 부분은 스케줄링이라고 할 수 있습니다.

- "응답시간과 처리량, 효율성을 증대시키기 위해 CPU가 다음에 실행할 프로세스를 선택하는 것"이라고 할 수 있습니다.

선점과 비선점

선택함수라고도 하는데 다음번 실행을 위해 준비 큐에서 대기중인 프로세스 하나를 고를 때 사용하는 알고리즘을 이야기합니다.

비선점 모드

- 프로세스가 일단 실행 상태에 진입하면 종료되거나 자발적으로 CPU를 놓을 때 까지는 CPU를 빼앗기지 않습니다.

- 자발적으로 CPU를 놓는다는 것은 프로세스가 종료되거나 입출력 요구 및 시스템 서비스 호출 등으로 인해 스스로 블록되는 현상을 말합니다.

- 모든 프로세스에게 공정하고 응답시간의 예측이 가능합니다.

- 짧은 프로세스가 작업시간이 긴 프로세스를 기다리는 경우도 생깁니다.

- FCFS, SPN, HRRN 이 해당됩니다.

선점 모드

- 현재 실행중인 프로세스라 할지라도 운영체제에 의해 인터럽트가 걸려 비자발적으로 준비 큐로 이동될 수 있습니다.

- 현재 실행중인 프로세스를 선점시킬 수 있는 시점

 + 새로운 프로세스가 진입하는 순간

 + 하드웨어로부터 인터럽트가 걸려 대기중이던 선점된 프로세스가 다시 준비 큐로 들어오는 순간

 + 클록 인터럽트에 의해 주기적으로 스케줄러가 호출되는 시점

- 빠른 응답시간을 요구하는 시분할 시스템에 유용합니다.

- 높은 우선순위의 프로세스들이 들어오게되면 오버헤드 현상이 일어날 수 있습니다.

- RR(라운드-로빈), SRT, 피드백 이 해당됩니다.

비선점 스케줄링 알고리즘

FCFS (First Come First Served)

가장 단순한 형태의 스케줄링 정책으로 FIFO(First In First Out)이라고도 합니다. 이는 큐잉 체계를 지키고 있다는 의미이기도 합니다.

- 비선점형

- 프로세스들은 대기 큐에 도착한 순서대로 CPU를 할당받습니다.

- 현재 실행 중인 프로세스가 실행을 종료하면 준비 큐에서 대기 중이던 프로세스 중 가장 오랫동안 기다렸던 프로세스가 다음 번 실행할 프로세스로 선정됩니다.

- 짧은 프로세스 보다는 긴 프로세스에 유리합니다.

- 단일 처리기 시스템에서 매력적이지 못한 스케줄러이긴 하지만 FCFS가 우선순위에 기반한 스케줄링 정책들과 어우러지면 효율적인 스케줄러가 되기도 합니다.

SPN(Shortest Process Next)

FCFS에서 긴 프로세스만 우대하는 편향성을 완화시키는 접근법으로 가장 짧은 프로세스를 먼저 실행시키는 정책입니다.

- 비선점형

- 종료시까지 남아있는 실행시간이 가장 짧은 프로세스를 다음 번 프로세스로 선택합니다. 실행시간이 짧은 프로세스가 늦게 도착하더라도 긴 프로세스들을 제치고 준비 큐의 앞으로 전진하게 됩니다.

- 긴 프로세스 보다는 짧은 프로세스에 유리합니다.

- FCFS보다 평균 대기 시간 감소효과가 있습니다.

HRRN(Highest Response Ratio Next)

현재 실행 중인 프로세스가 종료했거나 어떤 다른 이유로 실행이 선점되었을 때 스케줄러는 준비 큐에 있는 프로세스 중 R값이 가장 큰 프로세스를 다음 번 프로세스로 선택합니다.

R = w + s / s

R : 응답 비율, w : 처리기를 기다리며 대기한 시간, s : 예상되는 서비스 시간

- 비선점형

- w : 프로세스가 시스템 내에 머문 시간을 고려하고 있기 때문에 오래 기다린 프로세스를 먼저 실행하기도 하지만!

- s : 서비스 시간이 짧은 프로세스의 R 값이 상대적으로 크기 때문에 짧은 프로세스를 우대하기도 합니다. 그렇다고 긴 프로세스들은 위에서 말한대로 오래 기다렸기 때문에 R값이 증가하며 먼저 실행되는 경우도 있습니다.

- 긴 프로세스와 짧은 프로세스의 불평등을 보완한 기법입니다.

- 각 프로세스들의 서비스 시간이 얼마나 될지는 미리 알 수 없기 때문에 정확한 구현은 어렵지만 근사치를 구해 활용할 수 있습니다.

선점 스케줄링 알고리즘

RR(Round-Robin)

시간을 측정하고 있다가 어떤 긴 프로세스가 일정 시간 이상을 넘어가는 순간 실행을 강제로 선점시키는 것입니다. 프로세스 실행 시간을 재기 위해 필수적인 것이 클록 인터럽트인데, 클록 인터럽트는 주기적으로 발생합니다. 클록 인터럽트가 발생하면 클록 인터럽트 서비스 루틴이 실행되며 클록 인터럽트 서비스 루틴은 실행 중이던 프로세스는 준비 큐로 이동시키고 준비 큐에서 FCFS 방식으로 다음 프로세스를 골라 실행합니다.

- 선점형

- 각 프로세스는 같은 크기의 CPU 사용시간을 할당받습니다.

- 시분할 방식에 효과적이며 할당 시간의 크기가 중요합니다.

- 할당시간이 크면 FCFS와 같고 작으면 문맥교환이 자주 일어납니다.

- 장점 : 골고루 서비스 가능, 대화식 시스템에 적합

- 단점 : 할당 시간이 작으면 문맥교환이 자주 일어나 비효율

SRT(Shortest Remaining Time)

SPN의 선점 모드라고 볼 수 있습니다. SPN에서는 실행시간이 가장 짧은 프로세스가 다음 번 프로세스로 선택되었지만, SRT에서는 남아 있는 실행시간이 가장 짧은 프로세스가 다음 프로세스로 선택됩니다.

- 선점형

- 만약 새로 도착한 프로세스의 예상되는 남아있는 실행시간 (새로 도착했으므로 예상되는 전체 실행시간과 동일할 것)이 현재 실행중인 다른 모든 프로세스들보다 짧다면 제일 늦게 도착했더라도 바로 현재 실행 중인 프로세스를 선점하고 선택됩니다.

 + SPN : 준비 큐 대기, SRT : 바로 CPU 선점

- SRT는 SPN을 개선한 버전이라고 할 수 있지만 매 스케줄링 때마다 프로세스의 남아있는 시간을 평가해야하는 부담은 여전히 존재합니다.

- SPN과 마찬가지로 긴 프로세스가 기아상태에 빠질 가능성도 있습니다.

- FCFS에서 긴 프로세스를 편애하는 현상은 SRT에서는 발생하지 않습니다.

다단계 피드백

실행시간이 긴 프로세스는 단계적으로 불이익을 받는 형태입니다. 

지금까지의 스케줄링 방식들이 남아있는 시간, 프로세스의 실행 시간을 고려했다면 다단계 피드백은 우선 프로세스를 실행시키고 실행 시간이 오래되면 선점되는 방식입니다.

- 선점형

- 여러개의 큐를 두고 시간이 지나면 우선순위가 떨어지는 큐로 밀려납니다.

- 시간 할당량 배정 시마다 선점 모드로 수행되며 동시에 동적인 우선순위 정책을 병행하여 사용합니다.

- RQ0에서 실행되다가 선점(실행시간 소진, 인터럽트 등)되면 RQ0가 아닌 RQ1로 들어갑니다.

 + 우선순위가 낮은 큐로 진입

 + 프로세스의 서비스 시간이 짧다면 낮은 우선순위로 강등되지 않을 수도 있음

 + 긴 프로세스 일 수록 우선순위가 낮은 큐로 밀려남

- 가장 낮은 우선순위의 큐가 아니면 모두 FCFS 방식으로 다음번 프로세스를 선택합니다.

- 가장 낮은 우선순위의 큐는 RR방식으로 스케줄링됩니다.

스케줄링 알고리즘들의 특징

	FCFS	RR	SPN	SRT	HRRN	피드백
결정 모드	비선점	선점	비선점	선점	비선점	선점
처리량	강조 안됨	시간 할당량이 아주 작으면 처리량이 낮을 수 있음	높음	높음	높음	강조 안됨
응답시간	길어질 수 있음 특히, 각 프로세스의 총 실행시간 편차가 클 경우 응답시간이 안좋아질 수 있음	짧은 프로세스에 좋은 응답시간을 제공	짧은 프로세스에 좋은 응답시간 제공	좋은 응답시간 제공	좋은 응답시간 제공	강조 안됨
오버헤드	최소	최소	커질 수 있음	커질 수 있음	커질 수 있음	커질 수 있음
프로세스에 미치는 영향	짧은 프로세스에 불리함 입출력 중심 프로세스에 불리함	모든 프로세스에 공정함	긴 프로세스들에게 불리함	긴 프로세스들에게 불리함	공정성이 좋음	입출력 중심 프로세스를 우대하는 경향이 있음
기아상태	가능성 없음	가능성 없음	가능성 있음	가능성 있음	가능성 없음	가능성 있음

출처 : http://wonjayk.tistory.com/238