[OS] Scheduling Techniques Depending on Environment

 

 

 

---

Scheduling Techniques

Multiple-Processor Scheduling

---

 

 

 

앞서서는 Scheduling 알고리즘 자체에 대해서 알아보았습니다.

근데 그 알고리즘들은 모두 single-processor라는 전제 하에 배웠는데, 오늘은 그 이외의 상황들에 있어서는 어떤 방식으로 스케줄링이 되어야 하는지에 대해서 알아보도록 하겠습니다.

 

 

1. Multiple-Processor Scheduling

 

우선 이 멀티프로세서 스케줄링의 경우에는 여러개의 비슷한(homogeneous) 프로세서들로 이루어져있습니다.

이러한 멀티프로세싱은 크게 두 가지로 나뉩니다.

 

- Asymmetric Multiprocessing

'비대칭'이라는 단어처럼 하나의 대장 프로세서가 있고, 그 친구가 스케줄링 및 자원분배를 담당합니다.

그리고 나머지 프로세서들은 대장 프로세서에게 종속된 상태로, 시키는 것만 하겠죠.

 

- Symmetric Multiprocessing

Symmetric Multiprocessing은 대장 프로세서 없이, 알아서 분배하여 각자 할 일을 진행합니다. (self-scheduling)

그러면 '어떻게 분배를 할 것인가'에 대해서 고민해봐야 할 것 같죠?

크게 common queue를 구비하여 공통적으로 해결하는 방법과, private queue를 마련하여 정리하는 방법이 있습니다.

 

 

두 방법의 차이점은 당연히 알고 있어야겠죠?

 

1. common queue

- race condition이 발생할 수 있음 (같은 시간에 request가 발생하였을 때 어떻게 처리 할 것인가?)

- 보통 race condition 방지를 위해 locking을 이용

 

 

2. private queue

- race condition의 문제는 전혀 없음.

- starvization현상이 발생할 수 있기 때문에 workload balancing이 필요함

 

 

- Memory Stall

결국 프로세서가 할당을 받아서 연산을 시작하기 위해서는 메모리를 할당 받아야 합니다. 그런 상황에서, 당연히 그 메모리에 대한 정보를 받는데 시간이 걸리겠죠?

이러한 과정이 반복된다면 효율적이지 못하다는 것이 이 개념의 핵심입니다.

(최악의 경우에는 전체 시간의 반을 기다리는데 소요해야함)

 

이런걸 해결하기 위해 Multithreading processing cores를 사용합니다.

위 그림처럼 다른 스레드의 computation이 진행되는 동안에 memory stall을 하게끔 설계하여 결론적으로 봤을 때는 계속해서 computing을 하도록 하는 방법입니다.

근데 이것도 이론상 이런 거지, 실생활로 적용시킨다면 이렇게 나눠서 할 수 있는 건 제한이 있다고 합니다. 

 

그리고 이런 multithreading processing core는 thread가 여러개 있는 것이 특징입니다. 여기서 thread들은 실제 물리적으로 나뉘어져 있는 건 아니지만, 나뉘어져있는 것 마냥 다른 일들을 수행합니다. 따라서 이런 hardware thread들은 논리적 코어 라고 불립니다. 코어인척하는 친구들이라는거죠.

그래서 OS의 입장에서는 비록 실제 프로세서가 4개의 코어밖에 가지고 있지 않아도, 각 코어가 2개의 쓰레드를 가지고 있기 때문에 OS는 그냥 CPU가 8개 있고만~하고 생각하는 것입니다.

 

 

그래서 실제로 프로그램을 구동시킬 때는 다음과 같이 진행됩니다.

 

 

우선 user영역의 software thread들이 scheduling을 통해 각 kernel 영역의 hardware thread에 연결이 됩니다. software thread가 많아도 상관없는 이유는 concurrency때문이겠죠?

 

 

+) Fine-grained and Coarse-grained multithreading

그냥 둘의 차이만 알면 될듯