[운영체제] 비선점 스케줄링과 선점 스케줄링

비선점 vs 선점 스케줄링

• 비선점 스케줄링 : 프로세스가 입출력 요구 등으로 CPU를 자진 반납할 때까지 CPU에 의한 실행을 보장해주는 스케줄링이다. 작업 실행 시간 전체 또는 한번의 CPU 배당에 적용된다.
• FCFS(First-Come-Fist-Served) / 최단 작업 우선(SJF, Shortest Job First) / 우선순위 스케줄링 (Priority Scheduling)이 이러한 비선점 스케줄링의 알고리즘이다.
• 선점 스케줄링 : 시분할 시스템에서 타임슬라이스가 소진되었거나 인터럽트 혹은 시스템 호출 종료로 인한 여파로 현 프로세스보다 높은 우선순위의 프로세스가 나타나는 스케줄링이다. 현 프로세스로부터 강제로 CPU를 회수한다.
• 라운드 로빈 스케줄링 / 다단계 큐 스케줄링 / 다단계 피드백 큐 스케줄링이 이러한 선점 스케줄링의 알고리즘이다.

비선점 알고리즘 1. FCFS(First-Come-Fist-Served)

• 프로세스 도착순으로 CPU를 배정한다. 즉, 준비 큐에 도착한 순서대로 CPU를 배정한다. (실행 중 입출력을 요구하면 다시 다음 준비 상태에서 FCFS를 적용한다.)
• 시분할 시스템에서는 백 그라운드 또는 실시간 프로세스 등의 타임 슬라이스를 적용하지 않는 프로세스에 대해서도 사용할 수 있다.
• 호위 효과(Convoy Effect) 문제가 있다. 즉, 수행 중인 긴 작업을 여러 개의 짧은 작업이 기다릴 수 있다. 이는 짧은 작업의 반환시간과 대기시간을 늘려 평균반환시간과 평균대기시간을 늘린다.
• 따라서 도착 순서 이외에 특별한 추가 정보를 얻을 수 없는 경우(배치 작업 등의 장기 스케줄러)에 주로 활용한다.

비선점 알고리즘 2. 최단 작업우선(SJF, Shortest Job First)

• 대기하는 작업 중 CPU Burst Time이 가장 작은 작업에 CPU를 할당하는 기법
• 평균 대기 시간에 있어서는 최적의 알고리즘 (두번째 수행되는 작업이 가장 짧은 시간을 대기하려면 첫번째 작업이 전체 중 가장 짧은 작업이어야 한다. 이는 세번째, 네번째도 마찬가지이다. 결국엔 SJF와 동일하다.)
• 다만 도착시점(arrival time)을 고려하면 아직 도착하지 않은 프로세스는 스케줄링의 대상이 되지 않기 때문에 더 긴 프로세스가 먼저 할당될 수 있다.
• Burst Time이 동일할 경우 FCFS로 도착순으로 처리한다.
• 문제점 : 사실상 CPU의 Burst Time은 미리 알기 어렵다. 장기 스케줄링에서는 작업시간 예측치를 함께 제출할 수 있다. 하지만 단기 스케줄링에서는 다음 CPU Burst Time을 미리 알 수 없어 사용하기 어렵다.
• 해결방안 : 이전 Burst Time을 분석해 다음 Burst Time을 예측한다. 다음 Burst Time을 이전 Burst Time들의 지수적 평균으로 간주하는 방법이 주로 쓰인다.
• cf. 실행한 시간을 바형태의 표로 그린 것은 간트차트(Gannt Chart)라고 한다.

최단 작업우선 예시

• 도착시간이 0,2,4,5이고 Burst Time이 7,4,1,4인 프로세스 1,2,3,4가 있다고 하자.
• 이 때는 프로세스1이 Burst Time과 상관없이 가장 먼저 처리되고, 프로세스3, 프로세스2, 프로세스4 순서대로 처리될 것이다.
• 평균 대기시간은 (0 + 6 + 3 + 7) / 4 = 4 가 된다.
• 반환시간은 (7 + 10 +4 + 11) / 4 = 8 인데, 이는 평균대기시간 4에서 평균 Burst Time값 4를 더한 값과 같다.
• 이러한 SJF는 선점 스케줄링에도 적용할 수 있다. 앞선 예시와 같은 상황에서 타임슬라이스가 더해졌다고 생각하면 된다. 타임슬라이스가 2마다 적용된다고 하자. 그러면 프로세스2가 도착하면서 CPU에는 프로세스2가 할당된다. 도착한 순간의 프로세스1의 남은 Burst Time은 5로 프로세스2의 Burst Time보다 길기 때문이다. 나머지도 마찬가지로 남은 Burst Time의 기준으로 작동된다. 그결과 프로세스1은 조금 뒤에 처리되지만 결국 평균 대기시간은 (9 + 1 + 0 + 2) / 4 = 3으로 더 짧아진다.

비선점 알고리즘 3. 우선 순위 스케줄링(Priority Scheduling)

• 프로세스 자체적으로 우선순위를 정해두고, 우선순위 값이 제일 큰 프로세스에게 CPU를 할당한다. 순위가 같을 경우 FCFS를 적용한다.
• SJF도 결국엔 우선 순위 스케줄링에 포함된다고도 할 수 있다. (우선순위가 CPU Burst Time의 역수)
• 내부적 우선순위 고려 : 제한시간, 메모리 요구량, 사용하는 파일 수, 평균 CPU Burst에 대한 평균 I/O Burst 비율
• 외부적 우선순위 고려 : 사용료, 정책적 변수
• 일반적으로 연산 위주(CPU-Bound) 프로세스보다 입출력 위주(I/O-Bound) 프로세스에게 높은 우선순위를 부여하여 대화성을 증진시킨다.
• 기아 상태(Starvation)가 유발될 수 있다. 우선순위가 높은 작업이 계속적으로 들어올 경우 우선순위가 낮은 작업이 준비 상태에서 보장없이 머물 수 있다.
• 이러한 기아 상태는 에이징(Aging)으로 해결할 수 있다. 시스템에 머무는 시간이 증가하면 우선순위를 높여주는 것이다. 아무리 우선순위가 낮았던 프로세스라도 시간이 지나면서 우선순위가 높아져 결국은 CPU를 할당받을 수 있게 된다.

선점과 동적 우선순위

• 선점(Preemption) : 현 프로세스로부터 CPU를 회수하여 다른 프로세스에게 할당하는 행위
• 동적 우선순위 : 프로세스 실행 중 시스템의 성능, 프로세스의 특성을 고려해 우선순위를 재조정할 수 있다. 결과적으로 스케줄링에 의해 선점이 발생할 수 있다.
• 동적 우선순위 스케줄링은 dynamic priority scheduling이라 하고 고정 우선순위 스케줄링은 fixed priority scheduling이라 한다.
• 전체적인 시스템 성능의 향상 및 프로세스 속성을 고려하여 커널의 여러 곳에서 우선 순위를 조정하는 원칙과 기법이 필요하다. (커널 개발자가 담당해야 하는 부분이다.)
• 시분할 시스템마다 타임슬라이스의 양(길이)는 다르다. 이 역시 동적으로 변할 수 있다. 우선순위의 동적 변화에 따라 타임슬라이스의 양이 변하는 것이다. 즉, 타임슬라이스는 가변성을 가지고 있다.
• 가변적인 타임슬라이스는 일률적인 Clock Interrupt Interval로 구성된다. 이는 타임슬라이스보다 미세하게 구성되어 있다.
• 타임슬라이스의 소진 여부는 이러한 Clock Interrupt Interval을 기준으로 계산된다.
• Clock Interrupt Interval은 보통 10ms, 타임 슬라이스는 10~200ms이다. Clock Interrupt Interval을 10ms보다 작게할 경우 오버헤드가 과다 발생할 위험이 있다.
• 리눅스 2.4v을 예로 생각해보면 인터랙티브(대화성) 정도가 높을 수록 우선순위가 높아지고 타임 슬라이스가 높아진다. (참고: 우선순위는 -20~19까지 40단계로 표현하며 수가 작을수록 우선순위가 높다.) 대화성이 높은 프로세스(I/O Bound)라면 CPU를 할당해주어도 입출력이 일어나면서 CPU를 자진반납할 수 있다. 따라서 그냥 타임 슬라이스를 충분히 주는 것이다. CPU Bound 프로세스는 그 반대이다.

선점 알고리즘 1. 라운드 로빈(Round Robin) 스케줄링

• 준비 큐를 원형 큐로 간주하고 순환식으로 각 프로세스에게 작은 단위의 시간량(타임퀀텀)만큼씩 CPU를 할당한다.
• 실행상태의 프로세스는 타임퀀텀이 지나면 선점된다. (타임퀀텀은 타임슬라이스와 마찬가지의 개념이다.)
• 새로운 프로세스가 부가될 때는 큐의 맨 뒤에 덧붙여 진다.
• 물론 입출력이 발생하면 CPU를 자진반납한다.
• 이론상 N개의 프로세스가 1/N 속도로 동시에 실행되는 셈이다. 준비 큐에 N개의 프로세스가 있고, 타임슬라이스가 Q이면 각 프로세스는 (N-1)* Q 시간 이내에 다음 슬라이스를 받게된다. (문맥교환 시간은 고려하지 않았다.)
• 아무리 짧은 작업이라도 앞선 다른 작업이 큐 앞에 있다면 한 번이라도 각각의 타임퀀텀을 거쳐야하기 때문에 일반적으로 평균반환시간이 SJF보단 크다. 하지만 모든 프로세스가 공정하게 기회를 얻게되어 기아상태가 발생하지 않는다는 장점이 있다.
• 타임퀀텀의 크기에 따라 성능이 큰 영향을 받는다. 타임퀀텀이 매우 커지면 FCFS와 유사해진다. 매우 작아지면 잦은 문맥교환에 따라 오버헤드가 커져 처리율이 감소한다.
• 일반적으로 타임퀀텀이 커지면 평균 반환시간이 개선될 수 있다. 많은 작업이 한번에 처리될 확률이 증가되기 때문이다. 다만 많은 짧은 작업이 긴 작업들보다 순서상 늦게 처리되는 경우가 발생할 수 있어 무조건 그런 것은 아니다. 만약 대부분의 프로세스가 타임퀀텀내에 하나의 CPU Burst를 처리한다면 평균반환시간이 개선될 것이다. 따라서 80% 정도의 CPU Burst Time은 타임퀀텀보다 짧도록 조정하는 것이 가장 적절하다.

선점 알고리즘 2. 다단계 큐 스케줄링

• 목적에 맞도록 우선순위들을 정하고, 그 우선순위마다 준비 큐를 따로 설정하는 것이다.
• 가장 높은 우선 순위 큐의 프로세스에 CPU를 할당한다.
• 각 큐는 독자적으로 라운드로빈이나 FCFS같은 알고리즘을 사용할 수 있다.
• 대화형, 배치 등 프로세스의 성격에 따라 우선 순위를 부여한다. (예 : 시스템작업 / 대화형 작업 / 대화형 편집 / 일괄 처리 / 학생 작업)

선점 알고리즘 3. 다단계 피드백 큐 스케줄링

• 다단계 큐에 동적인 프로세스 우선 순위 변화를 적용한다.
• 즉, 단계별 큐를 이동할 수 있도록 한 것이다.
• 타임 슬라이스를 계속 모두 소진하는 경우 하위 큐의 뒤로 삽입한다. (하위 큐일수록 CPU-bound 프로세스가 된다.)
• 가장 하위 큐는 FCFS로 스케줄링한다.
• 맨 아래 큐에서 너무 오래 대기 시 에이징 기법을 사용하여 상위로 이동시킨다.
• 가장 일반적인 방법이지만, 적용하기엔 매우 복잡하다. (큐의 수, 각 큐에 대한 스케줄링 알고리즘, 순위를 변경하는 시기 결정법, 프로세스들이 어느 큐에 들어갈지 결정하는 방법 등을 모두 결정해야 한다.)