Multiprocessor Scheduling

멀티프로세서는 한 시스템 내에 여러 개의 프로세서가 있는 것을 말한다.

멀티코어는 하나의 칩 안에 여러 개의 코어가 있어 동시에 작업을 처리할 수 있다.

우리가 흔히 사용하는 컴퓨터는 멀티코어를 사용하고 있다.

멀티프로세서를 사용하지 않는 이유는 멀티코어가 공간, 전력 효율성 측면에서 좋기 때문이다.

멀티프로세서를 사용하게 되면 CPU 간 메모리 공유와 통신 비용이 증가한다.

 

그냥 멀티코어를 사용하면 되는 거 아닌가?? 멀티프로세서는 언제 사용하면 좋을까?

하나의 칩 안에 넣을 수 있는 core의 개수가 물리적으로 제한되어 있기 때문에 이를 극복하기 위해서는

여러 개의 CPU가 필요한 것이다. 슈퍼컴퓨터나 대형 데이터센터처럼 수만 개의 작업을 병렬 처리해야 할 때는 어쩔 수 없이 멀티프로세서를 사용해야 만한다. 즉 더 많은 병렬처리를 하기 위해 멀티프로세서를 사용한다.

 

그러면 멀티코어를 사용한 멀티프로세서는 언제 사용될까?

슈퍼컴퓨터나, 고성능 서버를 만들 때 사용된다고 한다.

 

순차적인 코드는 CPU를 여러 개 사용하기에 적합하지 않다.

만약 코드가

#include <iostream>

using namespace std;

int main(void)
{
	cout << "나는";
	cout << "금오공대";
	cout << "김건오";
	cout << "이다";
	return 0;
}

이런 식으로 되어있으면 하나의 CPU(하나의 코어)에서만 진행되어야 한다.

 

멀티 코어와 멀티 프로세서는 병렬 프로그래밍과 멀티스레딩을 하기 위해 사용된다.

 

여러 개의 CPU를 사용하면 캐싱 문제와 동기화 문제, 작업 분배 문제가 발생할 수 있다. 이러한 문제점을 해결하기 위해서는 스케줄링을 변경해야 한다. 어떤 작업이 어떤 CPU에서 실행될지도 확인을 해야 하기 때문.

한 CPU에서 실행되던 작업이 다른 CPU로 옮겨질 수도 있음.(캐시 메모리 초기화와 같은 추가 비용이 발생)

위 그림은 싱글 CPU의 캐시 구조이다. 캐시 메모리와 메인 메모리가 있다.

캐시는 작고 빠른 메모리로 자주 사용하는 데이터를 저장한다.(메인 메모리보다 접근 속도가 빠르다.)

 

CPU0에서 D의 데이터를 수정하고 난 후 CPU1이 메모리에서 D의 데이터에 접근하면??(아직 수정된 데이터가 저장되어 있지 않다.) 멀티 코어에서도 이러한 문제가 발생할 수 있음(멀티 코어도 독립적인 캐시를 사용).

MESI 프로토콜 기법을 사용해서 데이터의 일관성을 유지해야 한다.

 

캐시의 일관성을 유지하기 위해서는 각 캐시는 버스를 감시해야 한다. 자신의 데이터가 최신인지 확인한다.

 

멀티프로세서나 멀티코어는 동기화 문제가 발생할 수 있다.

캐시의 친화성을 위해 이전에 수행했던 CPU를 선택하는 것이 유리함.(아니면 여기저기 캐시에 데이터가 저장됨.)

 

여러 CPU가 하나의 큐를 공유하면 어떤 CPU에 어떤 작업이 실행될지 미지수. 캐시 친화성이 없다.

 

이렇게 CPU마다 큐를 가지고 있다면 각각의 CPU에서 실행되는 작업을 정해져 있기 때문에 캐시 친화성이 생긴다.

이렇게 하게 되면 빠른 작업을 수행하는 CPU는 빠르게 일이 끝나서 노는 문제가 발생한다.

 

부하의 불균등 문제를 해결하기 위해 이주와 작업 가로채기 방식을 이용할 수 있다.

*이주*는 작업을 옮기는 것을 의미한다.

1.Sender-initiation은 CPU가 너무 바쁘고 일이 너무 많이 밀려 있으면 상대적으로 조금 여유로운 다른 CPU한테 일을 주는 것을 의미한다.

2.Receiver-initation은 CPU가 할 일이 없고 여유로우면 상대적으로 바쁜 CPU의 일을 요청한 후 가져와서 도와주는 것을 의미한다.

 

*작업 가로채기*는 CPU가 자신의 큐가 너무 여유로우면 작업이 많은 다른 CPU의 작업을 그냥 가져온다.(스스로 작업을 찾아 나선다.)

 

위 그림은 Linux 운영체제의 스케줄링에 대한 설명이다.

멀티 레벨 피드백 큐를 기반으로 하고 있다.

 

real-time(0~99)의 우선순위가 Time-sharing보다 높다.

real-time의 우선순위가 높은 이유는 시스템의 정확성과 신뢰성을 보장하기 위해서이다.

예) 오디오(재생하는데 지연이 발생하면 문제가 발생할 수 있음.), 센서 데이터(센서를 통해 들어오는 데이터는 시간 내에 처리해야 함.) 반면 웹 브라우저의 페이지 로딩은 조금 늦어져도 상관없음.

기아 상태를 방지하기 위해 시간이 지나면 우선순위를 높여줌.

높은 우선순위 작업이 더 긴 타임 슬라이스를 부여받는다.

 

CPU는 자신만의 Run큐를 관리한다.(캐시 친화성, 스케줄링 과정 오버헤드 감소)

Load Balancing 문제가 발생할 수 있는데 이주와 부하 균형 메커니즘을 사용해서 해결한다.

 

active priority array는 현재 실행 가능한 작업을 모아놓은 배열이고

expried priority array는 타임 슬라이스를 소모하게 된 작업들이 모이는 배열이다.

 

active priority array배열이 비게 되면 expried priority array과 active priority array 배열의 역할이 교체된다.