상호배제와 동기화 - 경쟁 상태 예방의 필요성

진행 - p1에 들어갔다가 다시 p1에 들어가려 하면 lock=2라 안되기 때문에 진행이 만족하지 못한다.

 

한정대기 -  p1에 들어갔다가 다시 p1에 들어가려 하면  lock=2라 안되기 때문에 계속 기다리게 됩니다.

 

상호배제는 왜될까요? lock이 고정이 되면 상대편에 들어가서 바꾸기 전까지는 바뀌지 않습니다.

 

진행과 한정대기가 겹친다.

 

 

 

 

 

 

 

 

상호배제와 동기화 - 경쟁 상태 예방의 필요성

상호배제가 왜 필요한가를 설명입니다.

 

경젱상태란?

 

여러 쓰레드들이 경쟁적으로 공유자원에 접근하려 합니다.

 

 

경쟁 상태의 예 - 생산자,소비자 문제

컴파일러가 생산하면 어셈블러가 소비해야 합니다.

 

생산과 소비는 박자를 맞추지 못합니다.

 

버퍼를 이용해서 문제를 해결하려 했습니다.

 

버퍼에 임시저장했다가 필요하면 출력 프로세서가 가져가서 출력장치가 꺼내 씁니다.

 

비동기성 - 생산도 각자 하고싶을 때 소비도 각자 하고 싶은 것

이러한 문제를 해결 했습니다.

생산자는

버퍼가 가득 차면 생산을 중지합니다.

아니면 버퍼에 데이터를 저장하고

다음번에 잘 저장하기 위해서 저장할 위치에 포인터를 이동해 놓습니다.

 

소비자는

처리란 프린트 하는 것 입니다.

버퍼 에서 데이터를 받아서 처리합니다.

 

버퍼로 동기화 한 것입니다.

 

 

 

버퍼는 원형 큐로 만듭니다.

그래야 효율적입니다.

 

집어넣을 때마다 in 포인터를 1식 증가시키고

out할 때마다도 포인터를 1씩 증가시킵니다.

 

 

버퍼를 코드화한 것입니다.

버퍼에 들어갈 아이템 하나하나를 구조체로 선언했습니다.

 

이렇게 버퍼를 가지고 동기화하는 것이 잘 될까?

비동기화를 해결할 수 있을까?

 

여기에 경쟁 상태가 있나요?

(버퍼와 카운터)도 공유 자원 입니다.

 

생산자 프로세스, 소비자 프로세스 동시에 접근할 때 문제가 됩니다.

증가, 감소 연산을 동시에 수행할 때 문제가 됩니다.

 

메모리에 있는 count값을 cpu로 가져와서 1증가시킨다음

다시 메모리에 저장시킵니다.

 

하지만 동시에 수행되면 기계어 레벨에서 오버랩 되서 이상한 결과가 나옵니다.

 

 

 

경쟁 상태의 예 - 커널 변수 next_available_pid 문제

fork가 일어날 때마다 next_available_pid가 증가됩니다.

 

프로세스 2개가 동시에 fork 하면 자식 프로세스 번호가 같아집니다.

 

이는 심각한 문제가 됩니다.

 

임계영역에 대한 해결책이 

counter같은 공유 변수를 임계영역으로 설정하는 것

 

더 나아가서 병행 프로세스 동기화를 위해 

busy waiting과 deadlock을 해결해야 합니다.

 

 

2번 입니다.

 

진행을 못하는 것은 아닙니다.

진행을 해서 망한 결과를 내놓는 것입니다.

 

이건 deadlock에 대한 설명입니다.

 

1번 같습니다.

 

 

상호배제 방법들 

 

testandset명령어는 하드웨어 명령어 입니다.

 

세마포, 모니터 - 운영체제의 지원이 있어야 합니다.

 

알고리즘 만으로 하니깐 더 느릴 것입니다.

하나의 하드웨어 명령어로 동작해서 중간에 인터럽트가 걸리지 않습니다.

 

 

상호배제 알고리즘 - Dekker's algorithm

두 프로세스가 서로 들어가려하면 turn을 잡는 프로세스만 진입합니다.

 

 

flag변수와 turn 변수를 사용합니다.

 

공유 메모리가 사실 flag 입니다.

turn은 순서를 잡는 것입니다.

 

flag는 깃발을 올리는것 = 나 들어가고 싶어요!

 

프로세스 P0와 P1의 코드 입니다.

 

들어가기 전에 flag[0] = true;로 나 들어가고 싶어요 합니다.

 

나갈 때는 flag를 false로 만들고 turn을 상대편에 넘겨줄 수 있습니다.

(한 차례만 지나면 진입할 수 있습니다.)

 

 

2번 while문 자체가 상대편이 들어가려는 의지가 있다면 if문으로 계속 채크합니다.

 

만약 동시에 들어가고 자 하고 turn이 0이면 어떻게 될까요?

프로세스 P0에서 

2번 문장에서 상대편이 들어가고자 하는 의지가 있으니 기다려 줍니다.

만약  turn이 상대편이면 깃발을 내립니다.

 

그동안 프로세스P1은 while문을 계속 돌고 있고 그 다음 flag[1]을 true로 만듭니다.

 

 

 

turn으로 상호배제중 '진행'을 체크 합니다.

잘 들어가는지 체크해봅시다.

 

(진행 만족하는지)

turn이 0일 때 프로세스 P1이 임계영역을 수행할 수 있을까요?

들어갈 수 있습니다!

왜냐하면 flag[0]이 false이니 while문에 들어가지 않습니다.

그러니 '진행'을 만족합니다.

다른 프로세스가 들어가지 않는다면 들어갈 수 있습니다.

 

turn이 0이더라도 들어갈 수 있습니다.

 

 

 

(한정대기 만족하는지)

'한정대기'도 만족하나요?

상대방이 실행하고 있다면 임계영역이 끝나면

turn도 상대에게 주고 flag도 내리기 때문에 

계속 가지고 있을 일은 없습니다.

 

 

 

만약 다른 프로세스가 임계영역 안에 들어있다면 다른 프로세스는 어디서 기다릴까요?

while( turn == 1)에서 기다릴 것입니다.

상대방이 돌고 있으니 깃발은 true일 것입니다.

내 깃발은 내려놓고 while문이 끝나면 다시 깃발을 올립니다.

 

 

 

만약 다른 프로세스가 임계영역 안에 들어가 있는 상태에서 turn이 0입니다. 근데 프로세스P0가 임계영역에 들어가려 합니다. 이 때 어디 라인에서 기다릴까요?

while( flag[1] == true) 입니다.

 

 

3번

'한정대기'는 flag로 해결 가능합니다.

 

4번은 임계영역에 대한 상호배재를 말합니다.

 

상호배제 알고리즘 - Perterson's algorithm

단점이 있습니다.

바쁜 대기 - while문을 계속 돕니다.

그리고 2 프로세스 에 대한 것만 적용됩니다.

 

critical section = 임계영역

 

flag 변경부분 = 탈출 부분 입니다.

 

동시에 들어가고자 하면 어떤일이 벌어질까요?

동시에 시작하면 turn이 0과 1중에 하나로 결정됩니다.

 

하나로 판가름이 나면 그쪽이 진입하고 나머지는 busy waiting(while문에서 기다리는 것) 하다가 

다른 프로세스가 끝나면 임계영역에 들어갈 수 있습니다.

 

하나가 임계영역에 들어간 상태로 다른 프로세스가 들어가면 어떻게 되는가?

 

하나가 계속 반복하려면 잘 되는가?