[Chapter 5. CPU 스케줄링] 다중 처리기 스케줄링

* 본 글은 '운영체제(Operating System: Concepts) 9th edition'의 내용과 2021학년도 1학기에 수강한 '운영체제' 과목 강의 내용을 함께 정리하여 작성하였습니다.

 

 

지금까지는 단일 처리기 시스템(처리기(CPU)가 하나 있는 시스템)에서의 CPU 스케줄링에 대하여 알아보았다.

 

한 시스템 내에서 여러 개의 CPU가 사용 가능하다면 어떤 것들이 변화되며, 어떤 문제들이 추가적으로 발생할까?

 

다중 처리기 스케줄링 (Multiple-Processor Scheduling)

---

다중 처리기에서는 부하 공유(load sharing)가 가능해진다.

* 부하 공유 : 쉬고 있는 처리기에 할 일을 부여하는 것. 한 처리기는 계속 일하고 나머지는 놀고 있는 상태가 되어서는 안 된다.

 

하지만 이에 따라 스케줄링은 더 복잡해진다.

동일한 다중 처리기일지라도 때로는 스케줄링에 어떠한 제한 사항이 걸려있을 수 있기 때문이다.

 

예를 들어, 한 처리기의 사유(private) 버스에 부착된 입출력 장치를 가진 시스템이 존재할 경우

이 장치를 사용하고자 하는 프로세스는 반드시 그 처리기에서 수행되도록 스케줄 되어야 한다는 것이다.

 

 

다중 처리기 스케줄링에 대한 접근 방법에는 두 가지(비대칭 다중 처리와 대칭 다중 처리)가 존재한다.

1. 비대칭 다중처리 (Asymmetric Multiprocessing)

주 처리기(master server)가 모든 스케줄링 결정과 입출력 처리를 하며, 다른 시스템의 활동을 취급한다.

다른 처리기들은 사용자 코드만을 수행한다.

 

 

한 처리기만 시스템 자료구조를 접근하기 때문에 처리기 간에 커널 내 자료를 공유할 필요가 없다. (자료 공유의 필요성을 배제)

따라서 상호 배제 문제에서는 자유로우며 전반적으로 단순하다.

* 상호 배제 문제 : 서로 다른 프로세스가 공유 불가능한 자원을 동시에 사용하는 것에 대한 문제

 

하지만 처리기 간에 부하가 불균등해지고, (주 처리기의 부하 多)

주 처리기에 문제가 생기면 시스템 전체로 문제가 확산된다는 문제점이 존재한다.

 

2. 대칭 다중 처리 (Symmetric Multiprocessing, SMP)

각 처리기가 독자적으로 스케줄링을 수행한다.

모든 프로세스는 공동의 준비 큐에 있거나, 각 처리기마다 가지고 있는 사유의 준비 큐에 존재하게 된다.

 

 

각 처리기의 스케줄러가 준비 큐를 검사하여 자신이 실행할 프로세스를 선정하여 수행시킨다.

 

따라서 각각의 스케줄러가 공동의 자료에 접근하거나 갱신을 하게 되기 때문에 신중한 스케줄링이 필요하다.

즉, 서로 다른 처리기가 같은 프로세스를 선택하지 않아야 하며, 프로세스들이 큐에서 사라지지 않는다는 것을 보장해야 한다.

 

거의 모든 현대 운영체제들은 이 SMP를 지원한다.

 

 

 

SMP 시스템에 대한 이슈들에는 처리기 친화성, 부하 균등화 그리고 다중 코어 프로세서가 있다.

하나씩 알아보도록 하자!

 

처리기 친화성 (Processor Affinity)

프로세스의 다른 처리기로의 이주(migration)를 피하고, 같은 처리기에서 계속 실행시키려고 하는 성질을 말한다.

(프로세스가 현재 실행 중인 처리기에 친화성을 가진다)

 

 

프로세스가 특정 처리기에서 실행 중일 때 캐시 메모리에서는 어떤 일이 일어날까?

 

처리기에 의해 가장 최근에 접근된 데이터가 그 처리기의 캐시를 채우게 되어 프로세스의 잇따른 메모리 접근은 캐시 메모리에서 만족될 수 있다.

 

하지만 그 프로세스가 다른 처리기로 이주하게 된다면

첫 번째 처리기의 캐시 메모리 내용은 무효화되고, 두 번째 처리기의 캐시 메모리 내용이 다시 채워져야 한다.

 

이 비용은 상당히 많이 들기 때문에 프로세스를 계속 같은 처리기에서 실행시키려고 하는 성질이 발생한 것이다.

 

 

 

1. 연성 친화성 (Soft Affinity)

운영체제가 동일한 처리기에서 프로세스를 실행시키기 위한 정책을 가지고 있지만 이를 보장하지는 않으며,

프로세스가 처리기 사이에서 이주를 하는 것이 가능하다.

 

2. 강성 친화성 (Hard Affinity)

프로세스는 시스템 콜을 통해서 자신이 실행될 특정 처리기 또는 처리기 집합을 명시할 수 있다.

ex. Linux의 sched_setaffinity()

 

---

시스템의 메인 메모리 구조가 처리기 친화성에 영향을 줄 수 있다.

 

비균등 메모리 접근(Non-Uniform Memory Access, NUMA) 구조의 경우를 보자.

 

NUMA에서는 보드들이 병렬로 장착되는데,

CPU와 메모리가 같은 보드에 존재한다면 다른 보드의 메모리보다 빠르게 접근할 수 있다.

 

 

따라서 특정 CPU에 친화성을 갖는 프로세스를 해당 CPU와 같은 보드의 메모리에 배치하는 것을 통해 성능을 향상할 수 있다.

 

부하 균등화 (Load Balancing)

모든 처리기 사이에 부하가 고르게 분배되도록 하는 것이다.

이것은 SMP 시스템에서 처리기가 하나 이상이라는 것을 최대한 활용하기 위함이다.

 

SMP 시스템 중 각 처리기가 자기 자신만의 큐를 가지고 있는 시스템에서만 필요한 기능이다.

(하지만 대부분의 현대 운영체제들은 이러한 형태로 구현되어 있다.)

 

균등화 방안에는 두 가지가 존재한다. (Push 이주, Pull 이주)

이들은 Linux 스케줄러나 FreeBSD의 ULE 스케줄러에서처럼 병렬적으로 구현이 가능하다.

 

1. Push 이주(migration)

특정 태스크가 주기적으로 각 처리기의 부하를 검사한다.

만약 불균형 상태일 경우 과부하인 처리기에서의 프로세스를 다른 처리기로 이주시키는 것으로 부하를 분배한다.

 

 

2. Pull 이주(migration)

쉬고 있는 처리기가 부하가 높은 처리기를 기다리고 있는 프로세스를 pull 하여 이주시킨다.

 

 

---

부하 균등화는 처리기 친화성의 이익에 상충한다.

 

프로세스를 같은 처리기에서 계속 실행시키는 것의 이점은 프로세스가 그 처리기의 캐시 메모리에 존재하는 데이터를 활용하는 것에 있다.

하지만 프로세스를 한 처리기에서 다른 처리기로 pulling / pushing 하는 것은 이 이점을 없애는 것이다.

 

어떤 정책이 최선이냐는 것에 대한 절대적인 규칙은 없다.

 

어떤 시스템에서는 과부하인 처리기가 존재한다면 언제나 프로세스를 pull 이주시키는 정책을 가지며,

다른 시스템에서는 불균형 상태가 일정 문턱 값(threshold)을 넘었을 때에만 프로세스를 이주시킨다.

 

다중코어 프로세서 (Multicore Processors)

다중 코어는 하나의 물리적인 칩 안에 여러 개의 처리기 코어를 장착한 것이다.

이는 SMP보다 속도도 빠르고, 전력 소모도 적다.

 

운영체제 입장에서 각 코어는 별개의 물리 처리기처럼 보인다. (SMP 시스템과 동일)

하지만 스케줄링에서 다음과 같은 문제가 발생한다.

 

프로세서가 메모리를 접근할 때 데이터가 가용해지기를 기다리면서 많은 시간을 허비하게 되는데,

이를 메모리 멈춤(Memory Stall) 현상이라고 부르며

Cache miss(캐시 메모리에 접근하려는 데이터가 없음) 등의 여러 원인에 의해 발생하는 것이다.

 

 

메모리 멈춤 현상은 다중스레드 프로세서 코어를 통해서 해결할 수 있다.

 

둘 또는 그 이상의 하드웨어 스레드를 각 코어에 할당하여,

한 스레드가 메모리를 기다리면서 멈추게 된다면 코어는 다른 스레드로 전환하여 작업을 계속 수행할 수 있도록 한다.

 

아래 그림은 작업을 번갈아가면서 수행하고 있는 이중 스레드 프로세서 코어를 나타낸 것이다.

 

interleaving

 

운영체제 관점에서 각 하드웨어 스레드는 소프트웨어 스레드를 실행할 수 있는 논리 프로세서들로 보인다.

 

따라서 이중스레드, 이중코어 시스템에서는 4개의 논리 프로세서가 운영체제에게 제공되는 것이고

UltraSPARTC T3 CPU의 경우 칩당 16개의 코어가 존재하며, 코어당 8개의 하드웨어 스레드가 존재하기 때문에 총 128개의 논리 프로세서가 제공되는 것과 같다.

 

---

처리기를 다중 스레드화하는 방법에는 1. 거친 다중 스레딩과 2. 세밀한 다중 스레딩이 존재한다.

 

1. 거친(coarse-grained) 다중 스레딩

스레드가 메모리 멈춤과 같은 긴 지연시간을 가진 사건이 발생할 때까지 한 처리기에서 작업을 계속 수행한다.

긴 지연시간이 발생하면 처리기는 다른 스레드로 전환하게 된다.

 

하지만 다른 스레드가 수행되기 전에 명령어 파이프라인이 완전히 정리되어야 하기 때문에

스레드간 교환 비용이 많이 든다는 단점이 존재한다.

 

2. 세밀한(fine-grained) 다중 스레딩

명령어 사이클 경계(명령어 주기의 종료 시점)에서 스레드 교환이 일어난다.

 

이 시스템의 구조적 설계에는 스레드 교환을 위한 회로를 필요로 하며,

이 회로를 통해 스레드간의 교환 비용이 감소한다.

 

2 레벨 스케줄링

다중스레드-다중코어 프로세서는 기본적으로 두 단계의 스케줄링이 필요하다.

 

[ 레벨 1 ]

어느 소프트웨어 스레드가 각 하드웨어 스레드(논리 프로세스)에서 실행되어야 하는지를 결정한다.

운영체제가 관여하며, 다양한 스케줄링 알고리즘들(FCFS, SJF, 우선순위, RR, 다단계 큐, 다단계 피드백 큐 등)을 사용할 수 있다.

 

[ 레벨 2 ]

각 코어가 어느 하드웨어 스레드를 실행시킬지를 결정한다.