상호배제 알고리즘 - Lamport 알고리즘 알아보기

프로세스가 여러개 인 것에 대해서도 알아봐봅시다.

 

하드웨어 명령어인 TestAndSet 명령어를 봐봅시다.

아토믹 연산 - 중간에 인터럽트 걸리지 않고 한번에 실행되는 것

 

데커, 피터스 알고리즘은 두 프로세스의 임계영역 해결책 입니다.

 

 

상호배제 알고리즘 – Lamport's bakery algorithm

순서대로 기다리니깐 n개의 프로세스가 달려들어도 n번만 기다리면 나의 순서가 들어옵니다.

즉, O(n)의 시간이 걸립니다.

 

코드로 봐봇디ㅏ.

0~n-1까지가 프로세스 입니다.

 

임계영역에서 나오면 번호표를 반납합니다.

(number[i] = 0 ) 부분에서 번호표를 반납한다고 합니다.

 

number가 0이라면 번호표를 가지지 않은 상태입니다.

그러면 새로운 프로세스는 몇 번부터 몇번 까지 번호를 받을 수 있을까요? 1~n까지 범위내에서 받을 수 있습니다.

번호는 1부터 받습니다.

번호표를 계속 가지고 있으면 n보다 큰것을 발생시킬 수 있습니다.

 

max(number[0~n-1]) +1 은 무엇일까요?

가장 큰 번호표로 배정합니다.

모두 0이면 다음 번에 들어온 것은 1번 입니다. 다음은 2번 이겠지요

n을 받았따면 다음에 들어올 것이 n+1을 받을 것입니다.

 

내가 번호표를 받는 중이라는 것은 isReady[i]로 표시합니다.

 

번호표를 비교하고 있습니다.

i프로세스 번호표랑 j프로세스 번호표

 

먼저number[]를 비교하고 같더라도 뒤에 것(i,j)을 다시 봅니다.

 

왜 번호표가 같은 경우도 고려해야 할까요? 기존에 있던 번호표를 주는것입니다. 상호배제가 생길 수 도 있습니다.

동시에 같은 번호표를 받을 수 있습니다.

 

그러면 큰 프로세스 번호로 결정을 합니다.

 

나보다 번호표가 작거나 같더라도 프로세스 번호가 작으면 기다립니다.

나보다 작은애들이 다하면 내 차례는 돌아옵니다.

 

 

만약 번호표를 받는 중이면 받게 합니다.

 

while( number[j] && (number[j],j) < (number[i],i));

은 왼쪽이 true여야지 임계영역에 들어갈 수 있습니다. while문에 걸려서는 안되겠지요

 

만약 0~9번 프로세스가 있다고 합시다.

3번 프로세스가 혼자 임계영역에 들어가고 싶다는 시나리오를 코드와 함께 설명해봅시다.

 

나머지 들은 번호표를 안받은 상태이니깐 나머지 프로세스들은 number가 0일 것입니다.

isReady를 false로 만들고

0번 프로세스 부터 9번 프로세스 까지 비교를 합니다.

 

만약 나머지 프로세스가 true라면 while문에 막히지만 다 false입니다.

 

number[j]는 다른 프로세스 번호표 입니다.

다른 프로세스는 들어갈 생각도 없을 것이니 false가 나서 && 연산은 무조건 0이 나옵니다.

만약 j=3이라면 true가 됩니다.

number[j]는 1이고 number[i]도 1입니다. 같아서 false로 while문을 빠져나갑니다. 

다른 프로세스도 똑같이 수행됩니다.

 

만약 프로세스 3이 다시 들어가려하면?

문제 없이 들어갈 수 있습니다.

들어갈 때 마다 받는 번호표는 1일 것입니다.

 

 

만약 3번 프로세스가 임계영역에 들어가있고 5번 프로세스가 들어가려 하면 어떤일이 벌어질까요?

2번 번호표를 받습니다.

 

프로세스 3번에서 while문이 걸리게 됩니다.

j=3일 때 

number[3] == 1이고 && number[3] == 1이고

number[5] == 2입니다.

 

그리고 

P3이 임계영역에서 나오면 number[3]이 0으로 바뀌니 while문이 false로 바뀝니다.

 

 

만약 P5가 임계영역에 들어가고 

 

P7번이 들어가고 자 하면 번호표는 무엇을 받을까요?

3번을 받을 것입니다. number[7] == 3입니다.

현제 존재하는 번호표에서 가장 큰수 +1 입니다.

 

 

j가 5일때는 2번째 while문에서 기다릴 것입니다.

while(2 && 2 < 3) 으로 while문에 걸립니다.

 

임계영역 해결책으로 상호배제가 만족 되는가?

번호표로 임계영역에 들어갈 순서를 배정받아서 됩니다.

 

임계영역 해결책으로 진행이 만족 되는가? 비어있다면 누군가는 들어갑니다.

 

임계영역 해결책으로 한정대기가 만족 되는가?

번호표가 나보다 작은 프로세스만 기다리면 되기 때문에 한정대기가 만족합니다.

 

 

 

 

이러한 알고리즘은 소프트웨어적으로 하기 때문에 느리고 

cpu를 계속 사용하기 때문에 자원을 많이 사용합니다.

 

 

타임아웃 - 인터럽트 

cpu가 "너 시간다 됐으니 나가" 하는 것입니다.

 

1번입니다.

아토믹적 연산이라 인터럽트가 걸리지 않습니다.

 

TestAndSetTAS(테스) 명령어

초기값(lock)은 false로 두고

 

TestAndSet하면 false를 리턴하면서 true로 바꿔놓는것

 

그런대 이미 true인 상태에서 TestAndSet하면 계속 true를 반환합니다.

 

 

 

코드로 봐봅시다

return 할 값을 저장하고 그 값을 true로 바꿔놓는 것입니다.

 

 

이걸 어떻게 임계영역에 대한 해결책으로 활용할까요?

Testandset하고 보면 true로 리턴받으면 다른 프로세스가 들어가 있다는 뜻입니다.

 

P1이 다 끝나면 lock을 false로 바꿔뒵니다.

 

다른 누군가 득달같이 달려들면 한 프로세스는 임계영역(false)를 가지게 됩니다.

 

그러면 그 프로세스가 임계영역을 차지합니다. (다른 프로세스는 true를 계속 받습니다.)

오직 P2만 false로 바꿀 수 있습니다.

 

 

이것이 상호배제를 만족할까요?

상호배제: y

lock으로 다른 프로세스들은 false가 될 때까지 임계영역에 들어가지 못합니다.

 

진행: y

동시에 여러개 들어간다고 치면 비어있는대 들어가고자 하는 놈이 있다면 들어갈 수 있습니다.

 

한정대기: n

내 순서가 들어가는 보장이 안됩니디.

 

TestAndSet 명령어로써 임계 영역 구현 시 장점과 단점

제일 큰 장점

단순하고 쉽게 구현합니다.

프로세스 수에 관계없습니다.

임계영역이 많아도 가능합니다.

 

단점

while문에서 계속 돌아야 한다 => 바쁜 대기

 

기아 상태 => 한정대기가 없어서 임계영역에 계속 못들어가 는 프로세스가 발생할 수 있습니다.

 

 

1번 입니다.

아니였습니다.

 

3번 입니다.

교착 상태란 아무것도 못하고 꽉 막혀있는 상태입니다.

이건 들어가거나 못들어가거나 입니다.

 

기아 문제를 해결할 수 있습니다!

그림에서 네모칸에 해당하는 변수는 코드에서 무엇일까요? 

TestAndSet하는 대상 변수 입니다.

누가 임계영역에 들어가 있다면 True이고 아니면 False입니다.

 

답은 lock 입니다.

 

들어가는 화살표 True는 TestAndSet의 반환값입니다.

나가는 화살표는 key값에 저장됩니다.

 

waiting 배열은 내가 기다리고 있다는 뜻입니다.

 

내가 waiting을 끝내면 임계영역에 들어가게 됩니다.

 

 

ex)프로세스가 10개 있다고 칩시다.

P0~P9까지 있다고 칩시다.

 

P5만 들어가고 싶고 나머지들은 아무 관심이 없다면 어떤일이 벌어질 까요?

lock변수가 false로 되어있으니깐

while문에 key가 5로 바뀌어서 false로 되고 탈출하게 됩니다.

 

그리고 waiting[5]는 false로 되서 임계영역으로 들어갑니다.

 

j=6으로 하고 

(j != i) => 같은 프로세스 돌아보지 않고

!waiting[j] => 다른 프로세스가 false인지

 

j가 5이면 while문을 나옵니다.

 

한바뀌 완전히 돌아서 없다는게 확인된다면 lock을 false로 바꾸고 나옵니다.

아니면 다른애한테 기회를 줍니다.(=false로 바꿉니다.)

 

P7만 들어가고 싶고 나머지들은 아무 관심이 없다면 어떤일이 벌어질 까요?

lock변수가 false로 되어있으니깐

while문에 key가 7로 바뀌어서 false로 되고 탈출하게 됩니다.

 

그리고 waiting[7]는 false로 되서 임계영역으로 들어갑니다.

 

j=8으로 하고 

(j != i) => 같은 프로세스 돌아보지 않고

!waiting[j] => 다른 프로세스가 false인지

 

j가 8이면 while문을 나옵니다.

j를 9로 만들고 기다리는지(=waiting가 true인지)를 채크합니다.

9까지 찾습니다.

그리고 0,1,2,3,4,6까지 다시 가고 

j=7이 왔을 때 while문이 종료됩니다.

 

한바뀌 완전히 돌아서 없다는게 확인된다면 lock을 false로 바꾸고 나옵니다.

아니면 다른애한테 기회를 줍니다.(=false로 바꿉니다.)

 

이 예제가 

상호배제,

진행

한정대기를 만족하는지 공부해옵시다.

 

상호배제 - lock변수가  false가 아니라면 임계영역에 누군가 들어가 있다는 뜻이니 다른 변수가 들어가지 못하게 됩니다. 그래서 상호배제를 만족합니다.

진행 - waiting이 다른 프로세스 모두 다 false라면 lock을 false로 해놔서 다른 프로세스의 임계영역 진입을 허용합니다.

한정대기 - lock이 false로 바뀌었어도 TestAndSet을 수행값을 받지 못하면 계속 대기하게 됩니다.