동기화와 세마포어

앞에서 알아본 상호배제 개념을 구현하는 알고리즘을 알아보자

 

Algorithm 1

메인 프로세스 -> processnumber = 1선언, 그후 프로세스 A, B동시 실행

Process A -> processnumber == 2일 때  ; 실행 -> 그 후 임계영역 진입

Process B -> processnumber == 1일 때 ; 실행 -> 그 후 임계 영역 진입

 

과정

Process A 먼저 실행 조건이 거짓 이므로 실행 후 임계영역 진입

그 후 processnumber = 1로 선언하여 빠져나오면서 B의 진입을 허가

B는 조건이 거짓이 되었으므로 While문에서 빠져나와 임계영역에 진입 

 

결론 

이 알고리즘은 공유자원인 processnumber을 이용해 임계영역에 진입하는 알고리즘이다.

그러나 문제점이 존재한다.

 

문제점

만약 A가 임계영역에 진입한 상황에서 비정상적으로 진입하게 되면 B는 계속해서 cpu를 사용하며

대기상태에 빠지게 된다,

또한 한 프로세스가 계속해서 임계영역을 점유하면, 다른 프로세스는 영원이 접근할 수없는 Starvation가 

발생할 수 있다.

 

---

Algorithm 2

Mainprocess -> lock1, lock2를 false로 설정, process A, B를 동시 실행

A -> while 문의 조건이 참이 아니므로 lock1을 true로 바꾸고 임계영역 진입,

B -> A가 lock1을 true로 바꾸었기 때문에 while문 조건이 참이므로 대기

A -> 임게영역에서 빠져나오고 lock1을 false로 바꾸고 잔류영역으로,

B- > A가 lock1을 false로 바꾸었기 때문에 lock2를 true로 바꾸고 임계영역 진입,

임계영역에서 빠져나온 후 lock2를 false로 바꾸고 잔류영역으로,

 

결론 : 공유자원 2개를 이용한 임계영역관리 알고리즘이다.

 

문제점 : 동시실행을 하므로 A, B 둘다 임계영역으로 들어갈 수 있다, 즉 상호배제가 안될 수 있다.

 

---

Algorithm 3

MainProcess -> lock1, lock2 = false, A, B 동시실행

A, B 각각 lock1, 2를 true로 바꾼다,(서로 못들어고게 하려는 의도)

A -> while 조건 참이 되므로 대기

B -> while 조건 참이 되므로 대기

결과 -> 둘다 못들어가고 무한대기에 빠진다.

 => 이런 상황을 Deadlock

---

Dekker's Algorithm

MainProcess -> turn 선언 후 B 대입, lock1, 2 false 선언, process A, B 동시실행

A, B -> 둘다 동시에 lock조건을 각각true로 설정한다.

그와 동시에 if문을 확인하여 turn조건을 확인한다.

만약 참이라면 상대가 임계영역에 진입하도록 lock조건을 변경한다,

이를 통해 한쪽이 임계영역에 접근하고 빠져나오면서 turn조건, lock조건을 변경한다,

남은 프로세스는 임계영역에 접근할 수 있게 된다.

 

결론 : 양쪽다 동시에 진입 시도 -> 조건을 통해 상대의 선진입을 확인하면 조건 변경 및 자신의 진입을 차단

-> 상대가 끝나면 진입

---

peterson's Algorithm

mainprocess -> lock1, 2 = false, turn = A로 세팅

A와 B가 둘다 lock1 = true, lock2 = true로 선언 후 진입시도

하지만 각각 turn을 B, A로 선언하며 양보한다

이로 인해 어느한쪽이 만약 먼저 진입하게 되면 다른쪽은 양보하게된다

 

---

하드웨어 기반 알고리즘

실행은 CPU가 하고, 실제 값은 메모리에 있는 것을 가져옴 -> 메모리와 cpu 간의 차이에 의한 문제가 발생한다.

이를 해결하기 위해 메모리 배리어가 등장하였다.

 

메모리 베리어 : 4개의 프로세스가 작동중일 때 다 실행이 완료되어야 다음 단계로 넘어갈 수 있도록 한다.

위에 나온 알고리즘에 대 한 문제들을 하드웨어적으로 구현하였다.

 

---

세마포어

 : 동시성 제어기법 중 하나로 공유자원에 대한 접근을 관리하기 위한 정수값을 사용한다. 경쟁상태를 

방지하기 위해 고안되었다.

 

기존의 상호배제 알고리즘의 임계영역문제를 일반화 하기 어렵다.

따라서 단순화, 일반화하기 위한 방법으로 세마포어가 등장하였다.

 

P : wait 연산 -> S가 0보다 작을 때 대기, 클 때 -> S를 감소시킨다

바쁜 대기 상태가 발생할 수 있다, 리소스를 점유하거나 잠금을 걸 때 사용한다.

V : S의 값을 증가 시킨다, 리소스를 해제하거나 잠금을 푸는것을 의미한다.

 

원자적 명령:  세마포어를 실행하는 동안에는 인터럽트나 이벤트에 의해 중단되지 않아야한다,

즉 점선을 기준으로 S--, S++이 동시 실행되어서는 안된다.

---

특성

spinLock문제 : 검사하는 과정에서 끊임없이 CPU를 사용하는 문제

예 : busy waiting

해결

: busy waiting 대신 sleep모드로 변경하여 CPU의 부담을 최소화한다,

---

특성

1. N개의 이ㅏㅁ꼐영역 문제를 해결할 수 있다.

2. N개 프로세스의 상호배제를 구현할 수 있음.

 

사례

문제 설명:

 

• 다섯 명의 철학자가 원형 테이블에 앉아 있으며, 각 철학자 앞에는 그들이 먹을 음식(스파게티)이 있습니다.

• 각 철학자는 생각하다가 배가 고프면 먹기로 전환합니다.

• 철학자는 먹기 위해 두 개의 **포크(젓가락)**를 필요로 합니다. 그러나 각 철학자 사이에는 포크가 하나씩만 있으며, 두 개의 포크를 동시에 집지 않으면 먹을 수 없습니다.

• 철학자들이 동시에 포크를 집으려 하면 교착 상태(deadlock)가 발생할 수 있습니다.

 

결론 : 세마포어를 사용해 각 포크의 사용을 제어하여 교착상태, 기아상태를 방지할 수 있다.

---

모니터 

:

동시성 제어를 위해 사용하는 고수준의 동기화 메커니즘으로, 프로세스나 스레드 간에 상호 배제를 보장하고 **임계 구역(Critical Section)**을 안전하게 보호하는 역할을 한다.

 

세마포어가 프로그램 전체에 널려 있을 경우 문제가 발생한다. -> 이해와 작성에 어려움을 발생시킴, 유지보수 까다로움

 

따라서 공유자원을 핸들링하는 코드 -> 임계영역, 공유자원 영역을 구분시킴

 

모니터 : 하나 이상의 프로시저와 초기화 코드, 공유 데이터로 구성된 소프트웨어 모듈 객체

기능 : 모니터 경계에서 한번에 한 프로세스만 진입하도록 제어 -> 상호배제 원칙을 지킴

---