CPU Scheduling - Scheduling Algorithm_6

Multiple -Processor Scheduling(이하 MPS), 다중 처리기 스케쥴링

이전까지 소개했던 알고리즘들은 Processor 즉, 처리기가 하나일때의 알고리즘들이다. 

그렇다면 만일 Processor가 여러개라면 어떻게 스케쥴링을 해야할까? 

Processor가 여러개라고 해도 Processor를 다루는 방식에도 차이가 있다. 예전 포스트에서도 소개 한적이 있는데 바로 그것이

Symmetric( or Homogeneous) Multi-Processing(이하 SMP)과 Asymmetric( or Heterogeneous) Multi-Processing(이하 AMP)이다.

여러개의 Processor가 있으면 Load Sharing(부하 분담, 많은 처리량을 분담해서 처리)이 가능해 지고

 

각 Processor별로 별도의 Queue를 설정 가능하게 된다. 하지만 이 경우 아무일도 하지 않는 Processor가 발생할 가능성이 있다.

 

하지만 별도의 Queue를 설정할 경우 아무 일도 하지 않는 Processor가 존재할 수 있다. 때문에 별도의 Queue가 아닌

 

 공동의 Common Ready Queue, 즉, 공동의 Queuefmf 사용하는 방법이 있다.

이때 두가지의 방식으로 나뉘는데 첫번째는 Process를 각각의 Processor들이 Scheduling하는 방식이 있는데 이 방식이 SMP방식이다.

하지만 이 경우 가장 큰 문제점이 Critical Section Problem이 발생 할 수 있다. 때문에 하나의 Processor가

 

Master가 되고 다른 Processor들이 Slave가 되어 Master Processor가 다른 Processor들을 Scheduling하는 방식이 있는데

 

이 방식이 AMP방식이다.

Real-Time Scheduling(이하 RTS), 실시간 스케쥴링

실시간 상황에서도, 아니 실시간 상황이기 때문에 더욱더 스케쥴링 필요하다. Real-Time에는 종류가 두 가지가 있는데 하나가

Hard-Real-Time과 Soft-Real-Time이다. Hard-Real-Time은 주어진 시간내에 Process의 수행이 완료되어야 하고

 

Soft-Real-Time의 경우는 중요한 Process가 다른 Process보다 높은 Priority를 유지시키는 방식이다.

 

우리가 사용하는 Windows가 이 Soft-Real-Time방식이다.

이러한 Soft-Real-Time방식을 구현하는데 주위 할 점이 몇가지 있다.

1. Priority Scheduling이 적용되어야 한다.

당연히 Priority를 가져야만 우선처리가 가능하기 때문이다. 하지만 중요한 Process의 Priority값이 하향 조정되면 Real-Time이 

안되기 때문에 Real-Time Process의 경우에는 하향 조정이 되면 안된다. 즉, Aging기법이 사용되지 않는다. 그러므로 구현이 간단하다.

2. Dispatch Latency가 최소화 되어야 한다.

System Call이나 I/O처리시에 Preemption이 일어나지 않기 때문에 Latency가 길어질 가능성이 존재한다.

 

 때문에 Preemption Point를 넣어 주거나 전면적인 Preemption일어나도록 설정해야한다.

 

만일 Preemption Point를 넣을 경우에는 Critical Section이 아닌 곳에서는 높은 Priority를 

가진 Process가 수행 요청을 한다면 이를 수행 할 수 있게 해준다. 전면적인 Preemption을 허용하는 경우에는

 

 Kenel에서도 Preemption이 일어나기 때문에 Kernel Data에 대한 동기화 문제를 고려해야 한다. Dispatch Latecy의 구성은 아래와 같다.

 

위의 그림중에서 Conflict에서 처리하는 작업은 아래와 같다. 

1. Kenel에서 수행중이 Process의  Preemption

2. 높은 Priority를 가진 Process가 필요로 하는 자원을 낮은 Priority를 가진 Process가 가지고있다면 해제

3. 수행중인 Process와 높은 Priority를 가진 Process의 Context Switching

3. Priority Inversion

높은 Priority값을 가지고 있는 Process가 수행을 요청할 경우 Preemtion이 일어나서 CPU의 제어권을 가지고 오는데

 

이때 낮은 Priority값을 가지고 있는 Process가 Critical Section에 대한 권한을 가지고 있으면

 

 높은 Priority값을 가진 Process는 CPU에 대한 제어권을 자기고 있어도 Data에 접근 할 수 없는 현상이 일어나는데

 

이를 Priority Inversion이라고 한다. 이를 해결하기 위해서

Priority Inheritance Protocol(이하 PIP)라는 방법이 사용된다. PIP란 Priority Inversion현상이 발생할 때 수행을 요청한 높은 Priority의

Process가 가지고 있는 해당 Priority값을 자기의 값으로 삼는다.(일시적으로 Priority 상향) 그리고 수행이 종료된 뒤에 다시 원래의

Priority값으로 돌아가게 된다. 이는 Real-Time System에서 동기화 문제를 해결하는 방법중에 하나이다.