병행 프로그래밍의 개념
- 병행 프로그래밍이란?
병행 프로세스로 프로그램을 작성하는 것을 의미한다.
- 병행 프로세스란?
병행 프로세스(Concurrent Process)는 두 개 이상의 프로세스들이 동시에 존재하여 실행 상태에 있는 것을 의미한다.
여러 프로세스들이 독립적으로 실행되는 것을 독립적 병행 프로세스, 서로 협업하며 동시에 실행되는 것을 협동적 병행 프로세스라고 한다.
병행 프로세스는 다중 처리 시스템이나 분산 처리 시스템에서 중요한 개념으로 사용된다.
문제점
동시에 두 개 이상의 프로세스를 병행 처리하면 한정된 자원(CPU, Memory, Disk, I/O 장치 등)에 대한 사용 순서 등 여러 가지 문제가 발생한다.
해결책
- Critical Section (임계구역)
- Mutual Exclusion (상호 배제)
- 동기화 기법
-Semaphore (세마포어)
-Monitor (모니터)
병행 프로그래밍 기법의 종류
임계 구역
임계 구역(Critical Section)은 다중 프로그래밍 운영체제에서 여러 개의 프로세스가 공유하는 데이터 및 자원에 대하여 어느 한 시점에서는 하나의 프로세스만 자원 또는 데이터를 사용하도록 지정된 공유 자원(영역)을 의미한다.
임계 구역에는 하나의 프로세스만 접근할 수 있으며, 해당 프로세스가 자원을 반납한 후에만 다른 프로세스가 자원이나 데이터를 사용할 수 있다.
임계 구역은 특정 프로세스가 독점할 수 없으며, 임계 영역에서 수행 중인 프로세스는 인터럽트가 불가능하다.
임계 구역의 자원이나 데이터는 여러 프로세스가 사용해야 하므로 임계 구역 내에서의 작업은 신속하게 이루어져야 한다.
프로세스가 임계 구역에 대한 진입을 요청하면 일정 시간 내에 진입을 허락해야 한다.
현재 임계 구역에서 실행되는 프로세스가 없다면 임계 구역 사용을 기다리고 있는 잔류 영역에 있는 프로세스의 사용을 허락해야 하며, 그 이외에 있는 프로세스는 임계 구역에 진입할 수 없다.
- 임계 구역 원칙
상호 배제 기법
상호 배제(Mutual Exclusion)는 특정 프로세스가 공유 자원을 사용하고 있을 경우 다른 프로세스가 해당 공유 자원을 사용하지 못하게 제어하는 기법을 의미한다.
여러 프로세스가 동시에 공유 자원을 사용할 때 각 프로세스가 번갈아가며 공유 자원을 사용하도록 하는 것으로, 임계 구역을 유지하는 기법이다.
상호 배제 기법을 구현하기 위한 방법에는 소프트웨어적 구현과 하드웨어적 구현이 있다.
1) 소프트웨어적 구현 방법
-
두 개의 프로세스 기준 : 데커(Dekker) 알고리즘, 피터슨(Peterson) 알고리즘
-
여러 개의 프로세스 기준 : Lamport의 빵집 알고리즘
2) 하드웨어적 구현 방법
- Test & Set 기법과 Swap 명령어 기법이 있다.
동기화 기법
동기화 기법(Synchronization)은 두 개 이상의 프로세스를 한 시점에서는 동시에 처리할 수 없으므로 각 프로세스에 대한 처리 순서를 결정하는 것으로 상호 배제의 한 형태이다.
동기화를 구현할 수 있는 방법에는 세마포어와 모니터가 있다.
1) 세마포어(Semaphore)
세마포어는 '신호기', '깃발'을 뜻하며, 각 프로세스에 제어 신호를 전달하여 순서대로 작업을 수행하도록 하는 기법이다.
세마포어는 다익스트라(E. J. Dijkstra)가 제안하였으며, P와 V라는 두 개의 연산에 의해서 동기화를 유지시키고 상호 배제의 원리를 보장한다.
S는 P와 V 연산으로만 접근 가능한 세마포어 변수로, 공유 자언의 개수를 나타내며 0과 1 혹은 0과 양의 값을 가질 수 있다.
2) 모니터(Monitor)
모니터는 동기화를 구현하기 위한 특수 프로그램 기법으로 특정 공유 자원을 프로세스에게 할당하는 데 필요한 데이터와 이 데이터를 처리하는 프로시저로 구성된다.
자료 추상화와 정보 은폐 개념을 기초로 하며 공유 자원을 할당하기 위한 병행성 구조로 이루어져 있다.
모니터 내의 공유 자원을 사용하려면 프로세스는 반드시 모니터의 진입부를 호출해야 한다.
외부의 프로시저는 직접 액세스할 수 없다.
모니터의 경계에서 상호 배제가 시행된다.
모니터에는 한 순간에 하나의 프로세스만 진입하여 자원을 사용할 수 있다.
모니터에서는 Wait과 Signal 연산이 사용된다.
병행 프로그밍 기법 종류별 작동 메커니즘, 코드 사례
상호 배제 기법
1) 소프트웨어적 구현 방법
- 두 개의 프로세스 기준
1. 데커(Dekker) 알고리즘
//A 프로세스의 구조
while(1){
flag[A] = true;
while(flag[B]){
if(turn == B){
flag[A] = false;
while(turn == B);
flag[A] = true;
}
}
V++; //critical section
flag[A] = false;
turn = B;
}데커의 알고리즘은 2개의 프로세스를 위한 최초의 정확한 상호 배제 해결법으로 알려져 있다.
구성요소는 다음과 같다.
-
flag : 초기값은 flag [0] = flag [1] = false이고 임계 영역에 들어가겠다는 표시는 true로 한다.
-
turn : 0 또는 1의 값을 갖는다. 0인 경우엔 A의 순서, 1인 경우엔 B의 순서이나 위 코드에는 이해를 위해 A, B로 표시한다.
두 프로세스는 동시에 진행하면서 자신의 flag 를 true로 하고
상대방 flag 를 검사한 다음 turn 값에 따라서 if 이하 절을 수행하거나 수행하지 않을 수 있고,
결국 turn 값이 A 이면 A 프로세스가 진입하고 turn값이 B 이면 B 프로세스가 진입하게 된다.
따라서 한 프로세스는 두 번 연속해서 임계 영역에 진입할 수 있다.
2. 피터슨(Peterson) 알고리즘
//A 프로세스의 구조
while(1){
flag[A] = true;
turn = B;
while(flag[B] && turn == B);
V++; //critical section
flag[i] = false;
}피터슨의 알고리즘은 모든 상호 배제를 위한 추가 조건을 만족하고 데커의 알고리즘보다 단순하다.
구성요소는 데커의 알고리즘과 같다.
동작을 살펴보자.
A 프로세스를 동작시키고 싶다면 임계 영역에 들어가고 싶다는 표시로 flag [A]를 true로 만든다.
turn 변수를 B로 설정하고 내부 while문을 수행한다.
이때 B 프로세스가 들어갈 의사표시를 하지 않았다면, 즉 flag [B]가 false라면 A 프로세스는 임계 영역에 바로 들어갈 수 있다.
그러나 만약 두 프로세스가 동시에 동작하려고 하면 turn 변수가 늦게 수행된 프로세스가 내부 while문에서 기다리며 순서를 양보한다.
먼저 임계 영역에 들어갔던 프로세스는 나오면서 자신의 flag를 false로 만들고 다른 프로세스가 임계 영역에 들어가는 것을 허용한다.
따라서 두 프로세스가 동시에 수행될 때 내부 while문의 turn값에 따라서 어떤 프로세스가 임계 영역에 들어갈지가 결정된다. turn이 A이면 B 프로세스가 수행되고 turn이 B이면 A 프로세스가 먼저 수행된다.
- 여러 개의 프로세스 기준
1. Lamport의 빵집 알고리즘
빵집에서 번호표를 뽑고, 순서대로 1명씩 점원에게 가는 것과 유사하다고 하여 베이커리 알고리즘이다. 3개 이상의 프로세스에 대해서도 요청한 순서대로 처리가 가능하다.
각 손님을 쓰레드라고 가정하고, 각 손님은 번호표를 가지고 있다고 하자.
그리고 점원은 손님을 다 처리하면 다음 처리할 번호를 부른다고 하자.
이 알고리즘은 데커/피터슨의 단점을 해결한 방법이다.
여러 프로세스가 동시에 접근하려고 하더라도, 순차적인 접근을 보장해주기 때문이다.
또한 기아현상도 없다.
linux kernel 에선 ticket spinlock 이라는 이름으로 구현되어 있으며, 2.6.25 커널 이후에 적용되어 있다.
ticket spinlock 의 개발자는 이 알고리즘을 구현한 건 아니라고 하지만 실제로 핵심 방식은 동일하다.
2) 하드웨어적 구현 방법
- Test & Set 기법
데커/피터슨, 램포트 베이커리 알고리즘이 SW 적인 상호배제 방법이었다면, test and set 은 하드웨어적인 방법이다.
-
test and set(a,b) == b 값을 a로 복사하고, true 를 리턴함. (1 을 리턴)
이 명령어는 lock 이 잡혀있는지 보고, 안잡혀있으면 lock 을 잡는 것과 같은 의미로 볼 수 있다. -
이 명령어가 상호배제에서 사용되는 예제를 슈도코드로 작성해보면 다음과 같다.
region:
test_and_set(a, shared);
if a == 0; ==> 자원 접근 가능. shared == 1 로 변경하여 lock 잡은 것을 표시.
Access resoucre;
else ==> lock 이미 잡혀있음. 자원 접근 불가.
goto region;- Swap 명령어 기법 (Compare-And-Swap)
멀티 쓰레드 환경, 멀티 코어 환경에서 각 CPU는 메인 메모리에서 변수값을 참조하는 것이 아닌, 각 CPU에서 캐시 영역에서 메모리를 값을 참조하게 된다.
이때, 메인 메모리에 저장된 값과 CPU 캐시에 저장된 값이 다른 경우가 있다.
이를 가시성 문제라고 한다.
이때 사용되는 것이 CAS 알고리즘, 현재 쓰레드에 저장된 값과 메인 메모리에 저장된 값을 비교하여 일치하는 경우 새로운 값으로 교체하고 일치하지 않는다면 실패하고 재시도를 한다.
이렇게 하면 CPU캐시에서 잘못된 값을 참조하는 가시성 문제가 해결된다.
연산의 결과는 쓰기가 제대로 이루어졌는지 나타낸다.
이 연산은 atomic하기 때문에 새로운 값이 최신의 정보임을 보장한다.
구현은 다음과 같다.
int compare_and_swap(int* reg, int oldval, int newval)
{
int old_reg_val = *reg;
if (old_reg_val == oldval)
*reg = newval;
return old_reg_val;
}CAS란 특정 메모리 위치의 값이 주어진 값을 비교하여 같으면 새로운 값으로 대체된다.
동기화 기법
1) 세마포어(Semaphore)
운영 체계 또는 프로그램 작성 내에서 공유 자원에 대한 접속을 제어하기 위해 사용되는 신호.
병행 내지 병렬로 동작되는 둘 이상의 프로세서 사이에서 마이크로프로세서 시간이나 입출력 접속구와 같은 공유 자원을 동시에 사용할 수 없기 때문에 한 프로세서가 사용하고 있는 동안에 세마포어를 세워서 다른 프로세서를 대기시키고 사용이 끝나면 해제시키는 방법으로 사용한다.
세마포어 처리과정
세마포어의 계수가 0보다 큰경우 Thread가 데이터에 접근이 가능하고, 0인 경우는 접근을 차단한다.
Thread는 세마포어에 접근할때(acquire()) 세마포어 계수(permits)를 하나 감소시키고, 작업이 종료되고 나올때 (release()) 세무포어 계수를 다시 1증가 시키게 된다.
위와 같이 간단한 메커니즘으로 Semaphore를 통한 Thread 동시접근을 제어한다.
예제 코드
import java.util.concurrent.Semaphore;
public class SemaphoreTest {
public static void main(String[] args) {
final SomeResource resource = new SomeResource(3);
for (int i = 1; i <= 10; i++) {
Thread t = new Thread(new Runnable() {
public void run() {
resource.use();
}
});
t.start();
}
}
}
class SomeResource {
private final Semaphore semaphore;
private final int maxThread;
public SomeResource(int maxThread) {
this.maxThread = maxThread;
this.semaphore = new Semaphore(maxThread);
}
public void use() {
try {
semaphore.acquire(); // Thread 가 semaphore에게 시작을 알림
System.out.println("[" + Thread.currentThread().getName() + "]" + (maxThread - semaphore.availablePermits()) + "쓰레드가 점유중");
// semaphore.availablePermits() 사용가능한 Thread의 숫자
Thread.sleep((long) (Math.random() * 10000));
semaphore.release(); // Thread 가 semaphore에게 종료를 알림
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}2) 모니터(Monitor)
세마포어는 실제로 매우 오래된 동기화 도구이다.
현재에는 모니터(monitor)라는 동기화 도구를 주로 사용하며, 이는 좀 더 고수준의 동기화 기능을 제공한다.
모니터 구조
위는 모니터의 구조를 간단히 나타낸 그림이다.
모니터는 공유 자원 + 공유 자원 접근함수로 이루어져 있고, 2개의 큐를 가지고 있다.
각각 mutual exclusion(상호배타) queue, conditional synchronization(조건동기) queue이다.
상호배타 큐는 말그대로 공유 자원에 하나의 프로세스만 진입하도록 하기 위한 큐이다.
조건동기 큐는 이미 공유자원을 사용하고 있는 프로세스가 특정한 호출 wait()을 통해 조건동기 큐로 들어갈 수 있다.
조건동기 큐에 들어가 있는 프로세스는 공유자원을 사용하고 있는 다른 프로세스에 의해 깨워줄 수 있다. 이 역시 깨워주는 프로세스에서 특정한 호출 notify()을 해주며, 깨워주더라도 이미 공유자원을 사용하고 있는 프로세스가 해당 구역을 나가야 비로소 큐에 있던 프로세스가 실행된다.
기본 형식
if (monitor.enterIf(guard)) {
try {
do_something();
} finally {
monitor.leave();
}
} else {
do_anotherthing_without_monitor();
}예제 코드
import java.util.List;
import java.util.concurrent.TimeUnit;
import org.junit.Test;
import com.google.common.collect.Lists;
import com.google.common.util.concurrent.Monitor;
public class GuavaTest {
List list = Lists.newArrayList();
Monitor monitor = new Monitor();
Monitor.Guard capacityGuard = new Monitor.Guard(monitor) {
@Override
public boolean isSatisfied() {
return (list.size() < 1);
}
};
@Test
public void monitorTest() throws InterruptedException {
monitor.enterWhen(capacityGuard);
try {
list.add("Samuel");
System.out.println("Samuel");
} finally {
monitor.leave();
}
if (monitor.enterWhen(capacityGuard, 100, TimeUnit.MILLISECONDS)) {
try {
list.add("Jason");
System.out.println("Jason");
} finally {
monitor.leave();
}
}
}
}
