[운영체제] Ch6(1) Race condition & CS Problem & Peterson's Solution
Race Condition: 같은 프로그램을 수행하는데 결과가 상대적인 속도에 따라 다르게 나오는 것.
예시: Producer-Consumer problem
[설명]
counter++가 모두 수행 된 후 counter--가 수행되어야지(혹은 반대) counter값이 둘 다 똑같이 5가 된다. (기대한 결과)
하지만 예제처럼 동시에 수행하면서 실행이 뒤섞인다면 counter는 각각 6과 4과 되면서 동기화가 되지 않는다.
The Critical-Section Problem
race condition을 방지하기 위해 CS를 잘 보호해야 한다.
CS: 민감한 정보에 두개 이상의 프로세스가 접근해서 동시에 정보를 변경하면 문제가 생기는 부분.
[해결 방법의 조건]
1. Mutual Exclusion(상호배제): CS에 대한 독점권을 부여한다.
2. Progress: CS에 들어갈 때 이미 누가 CS에 있다면 CS에 들어갈 수 없다. CS에 아무도 있다면 들어가 수 있다.
3. Bounded Waiting: CS에 들어갈 때 이미 누가 CS에 있다면 기다려야 한다.(무한정 기다리는 거는 안됨)
- preemptive: 우선순위 높은 것이 언제든지 CPU를 뺏을 수 있다.
- nonpreemptive: 한번 CPU를 잡으면 끝까지 CPU를 쓴다. 따라서 CS problem(race condition)으로부터 자유롭다.
Peterson's Solution(SW적인 solution)
- int turn: 누구의 차례인지 저장
- boolean flag[2]: CS에 들어갈 의지가 있는지 저장
[Pi와 Pj가 있ㅇ르 때 Pi의 코드]
***turn을 상대방으로 하는 이유
[turn을 자기 자신으로 한다면?]
1. Pi가 첫번째로 들어와 turn=i로 설정한다.
2. Pi가 두번째로 들어오 turn=j로 설정한다.
--> 마지막으로 들어온 사람이 turn에 저장되는 불상사..!
[turn을 상대방으로 한다면?]
1. Pi가 첫번째로 들어와 turn=j로 설정한다.
2. Pi가 두번째로 들어오 turn=i로 설정한다.
--> turn=i가 되어서 먼저 들어온 Pi가 차례가 된다.
Pi가 CS에 들어갈려면
flag[j]==false거나, turn==i일 때.=(j가 CS에 들어가고 싶지 않거나, j보다 자신이 먼저 왔을 때)
Peterson's solution의 문제점
cpu나 compiler가 순서를 바꿀 수 있다.
[기대한 결과]
1. Thread2에서 x=100를 한 후, flag=true을 설정한다.
2. Thread1에서 flag 값에 의해 while문을 돌다가 빠져나와서 x=100을 출력한다.
[실제 가능한 결과]
1. Thread2이 flag=true를 먼저 설정한다.
2. Thread1이 실행되어 x를 읽어서 x=0을 출력한다.
3. Thread2이 x=100이 설정된다.
(Thread2가 모두 실행된 후 Thread1이 실행된다면 문제가 없다. 하지만 Thread1과 Thread2의 속도에 따라 결과가 다르게 나올 수 있다.-race condition)
--> 이와 같이 Peterson's Solution도 하드웨어적 문제로 인해 기대하던 결과가 나오지 않을 수도 있다.
HW적인 Solution
1. disable interrupt: 독점권 행사(CS사용 시 interrupt를 허용하지 않음)
2. Memory barriers
3. Hardware Instructions
4. Atomic variables
1. disable interrupt
독점권 행사(CS사용 시 interrupt를 허용하지 않음)
CS를 다쓰고 나갈때는 다시 interrupt를 허용해야 한다.
2. Memory barriers
한 쪽에서 메모리에 write를 하면?
Strongly ordered: 다른 메모리들 모두 read해야 한다. -->성능에 악영향
Weakly ordered: 즉시 read하진 않고 문제가 없을 때까지만 read하면 된다.
Weakly ordered를 할 때 문제가 없을 때까지의 그 지점을 정하는 것.
barrier 명령문: 전 후의 메모리 연산을 순서에 맞게 실행하도록 강제하는 기능이다. 즉 barrier 이전에 나온 연산들이 barrier 이후에 나온 연산보다 먼저 실행이 되는게 보장되어야 하는 것이다.
Thread2가 실행되어 x=100을 설정하고 memory_barrier()를 선언하는 순간 x=100을 모든 메모리에 전파한다.
3. Hardware Instructions
어떤 특별한 hardware Instruction은 중간에 intrrupt를 받지 않는다.
그 instruction을 Atomic instruction이라고 한다.
(insturction함수가 존재한다는 것이 아니라, 아래 함수처럼 HW가 동작한다는 것!!)
- Test-and-Set instruction
- Compare-and Swap insturtion
4. Atomic Variables
어떠한 값에 대해서 변화를 시키는 것이 Atomic하게 이루어 진다.
increment( )는 안에 매개변수를 Atomic variable(atomin_int*)로 선언해 놓아서, 중간에 다른 접근으로 값이 다르게 바뀌는 일이 없게 한다.
