13장 병렬 프로그래밍과 병렬 처리
13.1 병렬 처리 소개
병렬 처리 (Parallel Processing)
- 다수의 프로세서들이 여러 프로그램들 또는 한 프로그램의 분할된 부분들을 동시에 처리하는 기술
병렬 프로그래밍에 대한 연구
1. 병렬 프로그래밍 언어에 대한 연구 (Ada, Occam, Concurrent Pascal)
2. 병렬 컴파일러에 관한 연구
Flynn 분류 (컴퓨터 시스템의 분류)
1. SISD (Single-Instruction Single Data)
2. SIMD (Single-Instruction Multiple Data) ; 병렬 처리 컴퓨터
3. MISD (Multiple-Instruction Single Data)
4. MIMD (Multiple-Instruction Multiple Data) ; 병렬 처리 컴퓨터 (가장 일반적)
* Stream: 하나의 프로세서에 의해 순서대로 처리되는 일련의 명령어들과 데이터들의 흐름
SIMD vs MIMD
MIMD 형태의 병렬 처리 컴퓨터는 프로세서들이 메모리를 사용하는 방식임
- 공유 메모리 구조 (Shared Memory Architecture)
- 분산 메모리 구조 (Distributed Memory Architecture)
공유 메모리 구조 (Shared Memory Architecture)
- 공유 메모리 구조에서 일반적으로 사용되는 상호 연결망
1. 버스 (Bus)
2. 크로스바 스위치 (Crossbar Switch)
3. 다단계 상호 연결망 (Multistage Interconnection Network; MIN)
- 여러 프로세서에서 같은 공유 메모리(Critical Section)를 읽거나 쓸 때 문제가 발생할 수 있음
분산 메모리 구조 (Distributed Memory Architecture)
- 프로세서마다 메모리를 할당하고 상호 연결시킨 구조
13.2 병렬 처리와 프로그래밍 언어
병렬 처리를 위한 세 가지 선택 방법
- 입상(Granularity)크기에 따른 분류
1. 명령어 수준의 병렬성 - Fine Grain
2. 프로시저 수준의 병렬성 - Medium Grain
3. 프로그램 수준의 병렬성 - Coarse Grain
* Fine Grain (작은 덩어리): 입상 프로세스 생성 유지 오버헤드
* Coarse Grain (큰 덩어리): 너무 큰 나머지 병렬성 부여 기회 소멸
13.3 세마포어 (Semaphor)
Process
- Terminate (정해진 시간 안에 임계구역 실행을 끝냄)
- Fair Scheduling (한정된 시간 안에 임계구역에 들어감, 모든 프로세스가 동일한 시간을 배정받는 것이 아님)
Critical Region (임계 구역) = Critical Section
- 여러 프로세스에서 공유하고 있는 메모리 위치
- Mutual Exclusion을 요구함 (한 프로세스가 접근 중일 때, 다른 프로세스의 접근을 제한하는 것)
Semaphor (세마포어)
- 다익스트라가 개발하여, Algol 68에서 선보인 개념
- 프로세스가 호출 가능한 기본 함수(Primitives)임
- Critical Region에 대해 Mutual Exclusion를 보호해줌
- Binary Value Semaphor는 0/1의 값을 가지며, 1은 해당 자원이 사용 가능함을, 0은 해당 자원이 사용 불가함을 알림
- Binary Semaphor = 0이면, 해당 프로세스는 대기큐에 저장되어 대기하게 됨
- signal()은 프로세스가 작업을 마친 후의 실행 방향을 결정함
ex) Mutual Exclusion Using a Binary Semaphore
- DB에 데이터를 동시에 읽거나 쓰면 문제가 발생하므로, 세마 포어 개념을 이용함
ex) 세마포어를 이용한 생산자-소비자 문제
- 특정 Buffer에 Producer가 데이터를 Produce하고, Consumer가 데이터를 Consume하는 구조라 가정
- Consumer는 Producer가 데이터를 Write할 때 까지 대기해야 함
- Producer는 Consumer가 데이터 Consume을 완료하기 전까지, Produce를 멈춰야 함
- 즉, Producer와 Consumer간의 Synchronization(동기화)에 세마포어 개념을 이용함
※ 두 개의 세마포어를 이용하여 하나의 Buffer에 대한 동기화 문제를 해결할 수 있음
Counting Semaphore (Algol 68)
- 다수의 같은 종류 자원이 존재할 때, 그 자원이 어떤 순간에 사용할 수 있는 자원의 개수를 대표하게 됨
- 즉, integer형 변수에 현재 사용 가능한 자원의 개수를 저장함
ex) 50개의 버퍼에 대한 세마포어 적용 예시
- par 부분부터, 병렬처리가 시작됨
- 첫 번째 do-od 파트가 Produce 파트, 두 번째 do-od 파트가 Consume 파트임
