상호배제 해결방법, 프로세스 동기화

• 상호배제 해결방법

-임계영역 해결방법(=상호배제 알고리즘)

상호배제는 임계 영역에 막 들어가는 것을 막는다. 남이 못들어오게하는 entry section이 필요하다. 그리고 exit section이 필요하다. 임계 영역과 상관 없는 것은 잔류 연역에 있다.
임계 영역은 변수 공유하는 문제 때문에 발생한다.

 

-알고리즘1

p1 1~12, p2 13~22, main으로 구분했다.

p1과 p2가 병행 프로세스다. 
빨간색이 임계영역
어떻게 1개만 임계 영역에 들어가게 하느냐가 포인트

 

main
processnumber을 1로 세팅하고 p1, p2를 동시 수행하게함, 

p1
7번: 무한루프 processnumber가 2인 것은 거짓이 된다. 그래서 8번째 줄 실행 => 일단 p1이 임계 영역에 진입

p2
17번: 무한루프 processnumber 1이라 참이 된다. 조건문이 참인동안 반복해라
; 는 널 스테이트먼트->컨트롤을 저기에 묶고 다음으로 진행하지 말라는 의미

p1이 있으니 임계 영역에 가지 말아라
그러면 조건문만 계속 체크하다가 거짓이되는 순간 진행

p1
9번째줄로 넘어가면 processnumber에 2을 넣는다. 그러면 p2의 17번째 줄에서 갑자기 2로 바꾸면 while 문이 거짓이되고 18번째 줄로 넘어간다. p1은 임계 영역을 나오고 p2는 임계 영역으로 들어간다. p1은 10번째 줄의 잔류 연역으로 가고 다시 올라가서 반복 실행 그러다가 다시 7번째 줄가면 프로세스 넘버가 2이다. 그래서 거짓이 될때까지 진행하지 않고 while 문만 실행

p2

프로세스 넘버를 1로 세팅을하고 다시 p1에서 8번 줄로 가서 실행한다.

 

-Lockstep Synchronization Problem

p1 p2가 시간의 흐름에 따라 병행 실행을하면 교차적으로 임계 영역에 들어간다. 그러면 상호배제를 할 수 있다.

하지만 문제가 있다.
ex) p1이 임계 영역에 먼저 들어가 있으면 8번줄 실행하다가 9번 가야하는데 p1이 못풀리고 죽으면 p2 입장에서는 계속 기다린다.

 

-알고리즘2

p1inside, p2inside 2개의 변수 사용
p1, p2, main으로 구성
p1inside, p2inside 변수 초기값 false로 하고 p1 p2 병행실행

p1
7번: 실행하고 p2inside는 false로 반복문에서 빠져나온다.

8번: p1inside를 true로 바꾼다 => 알고리즘 1의 문제 해결을 위해 들어가자마자 상대편을 임계 영역에 못들어오게 막아줬다. 누가 됐든 먼저 들어간 프로세스가 상대를 못들어 오게 막음

9번: 임계 영역에 들어간다.

10번: 프로세스가 끝나면 다른 프로세스가 들어올 수 있게끔 풀어준다.

p2
18번: p1이 먼저 실행되서 while문에 걸려있게된다.

19번: p1 10번에서 false되면 무한 루프를 벗어나 19번 줄이 실행된다.

20번: 상대가 못들어오게 막아줍니다.

21번: 임계 영역에 들어간다.

22번: 프로세스가 끝나면 다른 프로세스가 들어올 수 있게끔 풀어준다.

 

하지만 이것도 문제가 있다.
p1inseide, p2inside 둘 다 false로 세팅하고 둘다 동시에 들어갈 수도 있다. 

=> 동시에 임계 영역 들어가면 상호배제가 보장되지 않음

 

-알고리즘3

p1enter p2enter 사용 초기값 false 세팅

p1부터 보면 쭉 실행되다가 

7번: p1enter을 true로 바꾼다 

8번: p2enter가 거짓이라 통과

9번: p1이 먼저 임계 영역에 들어가게 된다.

p2에선 

18번: p2enter을 true로 세팅

19번: p1 7번에서 참이라서 while이 계속 반복

=> 일단 다른 프로세스가 못들어오게 먼저 막고보자

p1 

일단 막고 10번에서 풀어주면 p2는 19번 줄에서 풀리고 임계 영역에 들어간다.

 

이거도 문제가 있다.
7번 에서도 막고 18번 에서도 막고 진입하면 둘 다 막힐 수 있다.

 

동시에 세팅하면 둘 다 막아버리게된다 => Deadlock이 걸렷다.
Deadlock는 자원을 서로 쓸려보니 어떤 프로세스도 이용하지 못하는 현상
동시라는 것 때문에 Deadlock이 생겼다.

 

-알고리즘4

원리는 같다. 시간차를 만들려보니 11 27번 줄에 일부러 시간 딜레이를 줬다. 랜덤하게 시간차를 만든다. 
함수는 sw->cpu,하드웨어가 실행시킨다. 어쩔땐 맞을수도 틀릴수도있다.
시간차가 만들어진다고 보장을 할 수가 없다. 경우에 따라 랜덤값이 같을 수도 있다.
하드웨어적으로 시간차를 만드는 방법을 제안, delay 부분을 하드웨어로 구현하면 확실하게 시간차를 줄 수 있다. 소프트웨어 보단 하드웨어 랜덤이 같을 확률이 훨씬 줄어든다. 하드웨어로 구성하면 하드웨어 구현비용이 들어간다.

=>임계 영역에서 프로세스가 죽으면 알고리즘 1 2는 문제가 발생
알고리즘 3 4는 중간에 죽어도 상관없다.

 

 

-Dekker 알고리즘

p1 p2 main 3가지 구성

=>순서대로하되 자기 순서가 아니면 양보해준다.

main 
p1enter, p2enter, fporcess 3가지 변수를 사용한다.
fporcess는 누구 순서인지를 정해준다.

p1 p2
동시에 돌린다. 그러면 병행성을 가지고 돌아간다

p1
p1enter 변수에 true로 세팅, 내가 먼저 임계영역 들어간다는 의미
while에서 p2enter문 테스트, 참이면 무한반복, 먼저들어가 놓고 일단 기다린다, 즉 상대방이 먼저 진입했다면 기다린다. 이러면 p2가 먼저 실행될 수도 있음

 

p1이 먼저 실행되는 경우

if문에서 fprocess가 second인지 다시 한번 확인, 초기값은 first가 입력되어 있어서 수행하지 않는다.
만약 p2가 먼저 실행되면 fprocess가 second가 되서 밑에 부분 수행하고 위에 p1enter을 취소하는 의미로 false로 바꾼다. 그리고 내 차례가 될 때 까지 while문에서 대기한다.
p2가 풀어지면 다시 자기 차례라고 p1enter을 true로 선언하고 임계 영역에 들어간다.
임계영역이 끝나면
fporcess를 2로 바꿔 2번째 프로세서 순서 차례라 하고 자신은 수행이 끝났단 의미로 p1enter을 false로 바꾸고 해제한다.

그 다음 p2에선
p2enter을 true로 바꿔 자기가 들어왔다고 선언
while문에서 체크해서 p1enter가 들어있으면 대기
그 후에는 변수만 다를뿐 p1과 과정은 같다

 

pertson's Algorithm도 있다.(중요, 찾아서 공부해보기)

지금까지 본 알고리즘들은 상호배제를 해결하기 위한 알고리즘이다.

 

• 프로세스 동기화

-Semaphore, S

1. 2개 이상의 프로세스가 병행성을 가질 수 있다. 공유자원을 사용하는데 있어서 프로세스가 2개 동시에 못들어가도록 해야한다 => 상호배제
2. 1, 2, 3 프로세스가 있을 때, 1결과를 가지고 2를 실행, 2가 만든 결과로 3을 실행하는 순서의 구조가 있는 경우라면 순서를 맞춰줘야한다. 이것을 동기화라고 부른다. 동기화의 방법으로써 Semaphore가 제시되었다

 

S-> 세마포어 변수라고 부른다.
신호등 예시를 많이 든다, 다익스트라가 제시

제공하는 기능
1. 상호배제
2. 동기화

a와 b가 구해져야 k를 구할 수 있다. 만약 그전에 계산하면 결과가 달라진다. 그래서 순서가 중요하다. 

 

p1 p2가 종료되어야 p3가 실행될 수 있다. 3개의 프로세스가 병행이라 각자 돌고있다.

P, V를 가지고 통제가능
알고리즘으로 해결이 가능하지만 기존 상호배제로는 일반화시키기 어렵다

P 오퍼레이션, wait operation
세마포어 변수를 파라미터로 사용하고
S<=0인 경우
no-op, 노오퍼레이션으로 반복수행, 즉 여기서 대기한다, 다음으로 컨트롤을 이동시키지 않음
루프를 벗어나면 S값 감소

V 오퍼레이션, siganl operation

S값을 증가 시킨다 -> wait를 풀어준다라는 의미

P와 V를 코드에 적용하면? 

P1, P2가 끝날때까지 p3는 대기해야한다.
따라서 p3에 기다리는 연산이 들어가야한다.
p1 p2는 풀어줘야해서 끝났다는 사실을 알려주는 V가 필요
=> 이렇게하면 동기화가 된다.

원리를 가지고 S = -1이라하면
처음에 p3에서는 P 오퍼레이션 부터 먼저 실행
S가 -1이라서 조건식은 참이된다. 따라서 대기를 한다.

여기서 P1은 계산하고 V 오퍼레이션한다.
그러면 S는 -1에서 0이 된다.
0으로 바뀐 상황에서 P를 실행 왜냐면 p3 입장에선 계속 테스팅을 한다. 참이된다. 그래서 여전히 대기한다.

p2에서는 계산하고 V 오퍼레이션 실행하고 S 값은 0에서 1로 바뀐다. 그러면 p3 입장에선 S가 1로 넘어와서 조건식이 거짓이되고 다음으로 컨트롤이 진행되어서 S값을 1 감소하고 계산을 실행한다.
=> 동기화 시켜줄 수 있다. 세마포어 방식 

조금 문제되는 것은 P오퍼레이션을 할때 cpu가 계속 검사를 해야한다 -> busy waiting 성능에 문제가 생길 수 있어서 나쁘다
cpu는 코드 실행이 본업이다. 하지만 본업은 뒷전에 두고 P 조건 테스팅만 계속하면 조건 검사에 시간을 많이 들여서 궁극적으로 성능이 저하된다.

 

1개 자원: binary semaphore라 부르고
n개 자원: counting semaphore라고 부른다. 

p1 p2가 각각의 자원들을 다 풀어주고 확보해야 p3가 가능하다

 

-세마포어의 특성

세마포어가 제기능을 하기위해서 2가지 조건이 붙는다.

1. 세마포어 연산자는 반드시 원자적(atomic)이여야한다.
세마포어 변수 S를 사용한다. 이것도 병행 프로세스를 하는데 이것도 공유자원이다. 이거 조차 상호배제, 동기화를 해줘야한다는 문제가 있을 수 있다.
그래서 조건을 붙인다. P, V 오퍼레이션에서 사용할 때, 세마포어를 사용할 때는 인터럽트, 이벤트에 의해 중단되지 않아야한다. 다른 것들은 접근불가하게 만들어서 공유 자원에 영향을 주지 않아야한다.
세마포어가 구현될 때 저 조건이 만족해서 구현되고 있다.

2. busy wating을 금지 시키고 대신에 sleep & siganl 방식으로 구현, busy waiting이 문제였다. 성능 안정화 시키고 할 수 있는 방법 

sleep은 재우는거다. 대기상태, 프로세스를 1초 재우는거다. 1초 뒤에 조건을 체크하는 거다. 계속 체크할 필요없이 타이머 세팅하고 자다가 일어나서 체크하는 방식이다. 
이렇게 운영하면 busy waiting을 안해도된다.

=> 이 2가지를 이용해야 성능저하 없이 이용할 수 있다.

 

세마포어 변수 s를 선언
그 값을 초기화 값으로 1로 세팅

s.wait(): wait 대기
(critical section): 임계영역이 있을때
s.signal(): siganl 풀어준다

 

-Dining Philosophers Problem

프로세스 동기화에 있어서 인용되는 프로세스
프로세스의 동기화 문제를 이해하는데 사용되는 예시

철학자가 있다. 철학자는 사고, 식사 2가지만 한다.
먹을 땐 생각하지 않는다. 사고할 땐 먹지 않는다. 라는 조건이 있다.
원탁에 스파게티가 있다. 먹을 땐 같이 먹어야하고 스파게티를 먹을 땐 반드시 포크 2개를 잡고 먹어야한다.
5명중에 동시에 포크를 잡는다하면 몇사람이 먹을 수 있는가?

=> 2명

이문제를 컴퓨터에 대입 철학자는 cpu, 포크는 공유 자원이다.
그러면 2개의 프로세스만 병행성을 갖는다. 

만약 5명 모두가 왼쪽 포크를 집어들면? 아무도 못먹는다.
다른 사람이 포크를 놓을 때 까지 기다려야한다. 계속 기다린다 -> 이런 상태를 deadlock이라고한다. 
다른 포크를 잡으려고 끊임 없이 기다린다 -> 결국 굶어죽음
이런상태를 starvation 기아상태라고 부른다.

=>이 예시로 동기화, 데드락, starvation 설명이 가능하다

코드 설명?

동기화 문제는 병행 프로세스에서 항상 나올 수 있는 문제이다.

 

-모니터(Monitor), 프로세스의 동기화 기법

자원이 여러개 있다. 프로그램에서 성능을 극대화 시키려고 병행성을 갖도록 프로그램을 짜고 싶은데 자원 공유를 한다. 그래서 P, V 오퍼레이션을 프로그램 전체에 널려있다. 나중에 이 양이 많아 흩어지면 헷갈린다. 유지, 보수, 개발하는데 어려워질 수 있다. 왜냐면 자원, 세마포어의 영향 범위를 알아야 하기 때문이다.
만약 프로그램을 짜고 퇴사하면 후임은 이것을 알기 어렵다.

그래서 나온게 모니터이다.
오른쪽이 모니터 그림 구조이라 한다. 공유자원을 한 곳에 몰아 넣는다. 공유 자원을 헨들링하는 부분이 밑에 부분에 들어있다. 자바로 프로그램을 짜면 클래스 정의를 한다. 클래스 인스턴스 만들면 객체가 생기고 객체를 헨들링해서 프로그램 만든다.

모니터의 모습
객체 안에는 멤버 변수, 멤버함수=메소드가 있다. 공유자원은 멤버면수

모니터를 구현한게 자바에선 클래스이다.
공유자원을 사용하려면 메소드를 통해서 간접적으로 접근하게 함으로써 임계영역, 프로세스 동기화 문제가 해결된다.

 

위에가 자원, 변수 밑이 메소드
진입 큐를 만들고 밑의 연산 쪽에서 자원에 접근

 

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

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