요약

프로세서가 여럿이면 “다음에 누구를 실행할까”에 “어느 프로세서에서”가 더해진다. 식당 주방장이 여럿일 때, 주문을 한 줄로 받아 손 빈 사람이 가져가게 할지, 같은 테이블 요리는 한꺼번에 여러 사람이 맡게 할지를 정하는 것과 같다. 스레드끼리 자주 주고받는 프로그램은 그 스레드들을 동시에 돌려야 빨라진다. 대신 프로세서를 놀리는 시간이 생기거나, 공용 대기열을 두고 다투는 부담이 생긴다.

예시로 보기

스레드 넷이 서로 결과를 주고받으며 계산하는 프로그램이 있다고 하자. 프로세서 넷 중 둘에서만 이 스레드들이 돌고 나머지 둘은 다른 프로그램을 돌린다면, 실행 중인 스레드가 아직 실행되지 않은 스레드의 결과를 기다리며 자주 멈춘다. 네 스레드를 네 프로세서에 동시에 올리면 서로 기다리는 시간이 줄어든다. 이것이 갱 스케줄링의 생각이다.

반대로 앱 하나는 스레드 넷, 다른 앱은 스레드 하나라고 하자. 두 앱에 시간을 똑같이 반씩 주면, 스레드 하나짜리 앱이 돌 때 프로세서 셋이 논다. 전체 시간의 절반 동안 넷 중 셋이 노니 \(\frac{1}{2} \times \frac{3}{4} = 37.5\%\)를 낭비한다. 스레드 수로 무게를 매겨 4/5와 1/5로 나누면 낭비가 15%로 준다.

정확히 말하면

다중 프로세서의 종류와 병렬성의 입도

다중 프로세서는 프로세서끼리 얼마나 단단히 묶여 있느냐로 세 종류다.

종류 내용
느슨하게 결합 프로세서마다 자기 메모리와 입출력 채널을 가진다(클러스터)
기능별 특화 입출력 프로세서처럼 특수 프로세서를 주 프로세서가 지휘한다
단단히 결합 프로세서들이 주기억장치를 함께 쓰고 하나의 운영체제가 지휘한다

병렬성은 프로세스끼리 얼마나 자주 동기화하는가(입도)로 다섯 단계로 나뉜다.

입도 동기화 예
독립 없음. 서로 다른 응용이나 작업 시분할 시스템
매우 굵음 / 굵음 아주 드묾 단일 프로세서에서 다중 프로그래밍으로 돌던 동시 프로세스. 다중 프로세서에서도 거의 바꾸지 않고 돈다
중간 한 응용의 스레드들이 자주 주고받음 스레드 사이 조율이 응용 전체 성능을 좌우한다
가늘음 매우 잦음 고도로 병렬화된 응용. 특수하고 쪼개진 분야

게임 회사 Valve는 하이브리드가 가장 낫다는 것을 알았다. 소리 섞기처럼 프로세서 하나에 맡기는 편이 나은 일도 있고, 장면 그리기처럼 스레드로 나눠 여러 프로세서에 펼치면 크게 빨라지는 일도 있다.

설계할 세 가지

다중 프로세서 스케줄링은 서로 얽힌 세 문제다. 프로세스를 어느 프로세서에 배정할지, 각 프로세서에서 다중 프로그래밍을 할지, 실제로 무엇을 디스패치할지다. 어떻게 정할지는 응용의 입도와 프로세서 수에 달렸다. 배정은 고정해 두는 정적 방식과 그때그때 옮기는 동적 방식이 있다.

배정 내용 장단점
정적 프로세스를 한 프로세서에 영구히 배정하고, 프로세서마다 단기 큐를 둔다 부담이 적고 갱 스케줄링을 쓸 수 있다. 한 프로세서는 놀고 다른 프로세서는 일이 밀릴 수 있다
동적 스레드를 한 프로세서의 큐에서 다른 프로세서의 큐로 옮긴다. 또는 공용 큐 하나에서 아무 프로세서나 가져간다 부하가 고르게 퍼진다

누가 배정하느냐로도 나뉜다.

구조 내용 문제
주종 (master/slave) 핵심 커널 기능은 늘 한 프로세서(주)에서 돈다. 주가 스케줄링하고, 나머지(종)는 주에게 서비스를 요청한다 주가 고장 나면 시스템 전체가 멈추고, 주가 성능 병목이 된다
대등 (peer) 커널이 어느 프로세서에서나 돈다. 각 프로세서가 스스로 스케줄링한다 운영체제가 복잡해진다. 두 프로세서가 같은 프로세스를 고르지 않게 해야 한다

스레드 스케줄링의 네 방법

스레드는 프로세스의 나머지와 따로 실행되므로, 다중 프로세서에서는 같은 프로세스의 스레드들이 동시에 실행되어 크게 빨라질 수 있다.

방법 내용 장단점
부하 공유 프로세스를 특정 프로세서에 배정하지 않는다. 공용 준비 큐 하나에서 놀고 있는 프로세서가 스레드를 가져간다. 큐는 단일 프로세서 스케줄링 방식 중 아무것으로나 관리한다 부하가 고르게 퍼지고 중앙 스케줄러가 필요 없다. 공용 큐에 상호 배제가 필요해 병목이 될 수 있다. 선점된 스레드가 같은 프로세서로 돌아가기 어려워 캐시 효율이 떨어진다. 한 프로그램의 스레드들이 동시에 프로세서를 얻기 어렵다
갱 스케줄링 관련된 스레드들을 프로세서들에 일대일로 동시에 올린다 동기화로 막히는 일과 프로세스 전환이 줄고, 한 번의 결정으로 여러 프로세서를 정해 부담이 준다
전용 프로세서 배정 프로그램이 실행되는 동안 스레드 수만큼 프로세서를 통째로 준다. 끝나면 반납한다 프로세서에서 다중 프로그래밍을 하지 않아 스레드가 막히면 그 프로세서가 논다. 하지만 프로세서가 수십~수백 개인 시스템에서는 프로세서 하나의 가치가 작고, 전환을 피하는 이득이 더 크다
동적 스케줄링 응용이 실행 중에 스레드 수를 바꾼다. 운영체제는 그에 맞춰 부하를 조절한다 이용률을 높인다

전용 배정 실험에서, 프로세서 16개 시스템에서 행렬 곱셈과 FFT 두 응용을 동시에 돌리며 스레드 수를 늘렸을 때, 응용마다 스레드가 8개를 넘어 전체 스레드 수가 프로세서 수를 넘자 성능이 크게 나빠졌다.

활용

  • 리눅스와 Windows는 부하 공유에 가까운 방식에, 스레드를 마지막에 돈 프로세서로 되돌려 보내는 친화성을 더한다 → 대칭형 다중 처리의 프로세서 친화성
  • 갱 스케줄링이 효과를 내려면 커널이 스레드를 알아야 한다 → 커널 수준 스레드

연결

확인 문제

C1 다음 상황에 부하 공유, 갱 스케줄링, 전용 프로세서 배정 중 무엇이 맞는가? ① 서로 관계없는 웹 요청 수천 개 ② 스레드 8개가 매 단계 서로 결과를 기다리는 과학 계산, 프로세서 64개

답: ① 부하 공유. 스레드끼리 동기화가 없으니 놀고 있는 프로세서가 아무 요청이나 가져가면 된다. ② 갱 스케줄링이나 전용 배정. 서로 기다리는 스레드들이 동시에 돌아야 막히지 않는다. 프로세서가 많으니 프로세서 8개를 통째로 줘도 손해가 작다.

C2 프로세서 4개에서 스레드 4개짜리 앱과 1개짜리 앱을 갱 스케줄링한다. 시간을 반반 나누면 낭비율은? 스레드 수로 무게를 매기면?

답: 반반: 1개짜리 앱이 도는 절반 동안 3/4이 논다. \(\frac{1}{2} \times \frac{3}{4} = 37.5\%\). 무게 4/5, 1/5: \(\frac{1}{5} \times \frac{3}{4} = 15\%\).

C3 주종 구조가 프로세서가 많아질수록 불리해지는 이유는?

답: 모든 스케줄링과 커널 서비스 요청이 주 프로세서 하나로 몰린다. 프로세서가 늘수록 요청이 늘어 주가 병목이 된다. 주가 고장 나면 전체가 멈춘다는 위험도 그대로다.