임계영역 해결 조건이 무엇인가요??
상호 배제가 보존되어야 합니다. 동시에 접근하지 않으려면 서로 배타적이어야 하기 때문입니다.
진행입니다. 임계영역에 어떤 프로세스의 접근이 없을 때 항상 접근이 가능해야 합니다.
무한정 대기가 없어야 합니다. 무한정 대기로 인해 기아현상이 발생할 수 있기 때문에 모든 프로세스가 임계 구역에 들어갈수 있도록 하기 위함입니다.
임계영역의 소프트웨어 해결책이 무엇이 있나요??
Dekker's 알고리즘이 있습니다.
Eisenberg and McGuire's 알고리즘 있습니다.
Bakery 알고리즘이 있습니다.
Peterson's 알고리즘이 있습니다.
피터슨 알고리즘이 무엇인가요??
임계 영역 문제를 해결한 소프트웨어 해결책입니다.
발표 당시에는 2개의 프로세스에 대해서만 적용이 가능했지만, 현재는 일반화되어 2개 이상의 프로세스에서 가능합니다.
피턴슨 알고리즘은 flag와 turn 변수를 이용합니다. flag는 신호를 나타내며, 내가 이 공유 자원을 쓰고 싶다는 뜻입니다.
turn은 누구 차례인지 명시해주는 변수입니다.
while(ture) {
flag[i] = ture;
true = j;
while(flag[j] && turn = j);
/* critical section */
flag[i] = false;
/* remainder section */
}2개의 프로세스가 동시에 임계영역에 들어가고 싶다고 가정해보면, 거의 비슷하게 turn변수가 i, j가 설정되는데, Pi가 빨랐으면 turn은 j로 Pj가 빨랐으면 turn은 i로 바꿔서 덮어버리게됩니다. 즉, 동시에 실행되도 덮어쓰여지는 현상 때문에 문제가 발생하지 않습니다.
피터슨 알고리즘은 결국 마지막에 결정된 turn의 값이 2개의 프로세스 중에 어떤게 공유된 자원을 먼저 사용할지 결정시키는 알고리즘입니다.
하지만 실제로 실행해보면 실패하는 경우가 존재합니다. entry section부분에서 컨텍스트 스위칭이 일어나면 실패하게 됩니다. (load & store)기계어 레벨로 생각하지 않으면 이해할수 가 없습니다.
하지만, 상호배제, 진행, 무한정 대기도 안하면서 이론적으로 완벽합니다.
임계영역의 하드웨어 해결책은 무엇이 있나요??
하드웨어로 임계영역을 지원해서 해결할 수 있으면 사용할 수 있습니다.
memory barriers or fences, hardware instructions, atomic variables을 이용할 수 있습니다.
Atomicity가 뭔가요??
원자성이라는 의미로, 더 이상 쪼갤 수 없는 단위입니다.
원자성은 컨텍스트 스위칭도 클락 단위로 실행이 되기 때문에 절대로 인터럽트가 걸릴 수 없습니다.
그래서 speical hardware instructions을 이용해서 atomic instructions을 만드는 것입니다.
예를 들어 count++을 3개로 쪼개지말고 instructions을 원 클락으로 끝내는 하드웨어 인스트럭션을 만들자는 것입니다.
atomic instructions에는 test_and_set()과 compare_and_swap()이 있습니다.
Atomic Variable이 뭔가요??
compare_and_swap이라는 instruction이 atomic variable 만드는 도구로 이용할 수 있습니다.
atomoic variable은 race conditiond이 있는 단일 변수가 있는 경우 상호 배제를 보장하는데 사용할 수 있습니다.