[OS / 운영체제] Peterson's solution, Erroneus Algorithm, Peterson's Solution, Memory Barriers, Hardware Instructions, compare and swap, TestAndSet

Peterson's solution

프로세스가 2개 있다고 가정, 3개부터는 어떻게 하는가. Peterson의 solution으로는 안된다. Pi, Pj는 상대적인 이름이다. 나 자신이 P0라면 Pi가 P0가 된다. Pi는 나 자신을 일컫는 말이다. turn, 누가 들어갈 차례인지가 turn 변수에 해당한다. flag변수는 사이즈가 2인 배열이다. 프로세스가 2개 있다고 가정을 했기 때문. turn의 초깃값은 0 flag도 0으로 초기화 되어있다.

 

 

Erroneus Algorithm

do while 루프 안에서 critical section이 존재한다. entry section이 while 시작문이고 exit section은 아래 처럼 구현한다는 것이다. 내 차례가 아니면 기다리라는 반복문이 된다. turn이 i 인 경우 false가 되서 critical section에 들어갈 수 있다. 상대방에게 차례를 주면서 끝나게 된다.

 

 

Erroneus Algorithm

0으로 초기화 되어있을 때 시작은 P0부터 시작한다. condition이 true이면 while문을 계속 돌게 된다. Process2는 기다린다. Process1이 끝나면 turn 1이 되면 Process2가 들어갈 수 있게 된다. turn을 0으로 만들면서 나오면 다시 상대방이 들어갈 수 있게 된다. Mutual exclusion은 보장이된다. (초기화가 잘 되었다는 전제조건이다.) 동시에 들어오는 상황이어야 의미가 있다. 둘이 동시에 들어오고 turn의 값에 따라서 0이냐 1이냐에 따라서 한 가지만 실행할 수 있게 된다. Progress는 보장이 안된다. remainder section에서 상대방에게 신호를 주지 않는 경우에 Critical section에 있지도 않으면서 상대방이 critical section에 들어가는 것을 막고 있다.

 

 

Erroneus Algorithm2

flag[i] = true; 나는 critical section에 들어갈 거라고 선언을 하는 것이다. while(flag[j]);는 상대방이 들어가 있는지를 확인하는 것이다. 만약 상대방이 들어가 있지 않다면 내가 critical section에 들어갈 수 있다. critical section을 떠날 때 flag를 false로 하고 떠나게 된다. 

 

 

Erroneous Algorithm2

Mutual exclusion은 보장이 된다. Progress가 보장이 안된다. (CPU가 두 개인 경우 문제가 발생할 수 있다. ) flag[0] =0  flag[1] = 0 -> flag[0] =1 flag[1] = 1 되면 둘이 서로를 진입하지 못하게 하는 상황이 발생한다. while과 true 할당의 순서를 바꾸면?? mutual exclusion이 보장이 안된다. 

 

 

Peterson's Solution

turn 하고 flag를 둘 다 사용한다. 둘 중에 하나만 false이면 critical section으로 들어갈 수 있다.

처음은 P0가 실행된다 저 사진에서;..

둘이 동시에 들어올 때 발생하는 일인 mutual exclusion 상태를 살펴 보자. 동시에 들어온 경우 turn의 값은 0일 수도 1일 수도 있다. 뒤에 실행되는 것이 turn의 값이 된다. while loop가 둘 다 false될 가능성은 없다. 왜냐하면 turn이 0인 동시에 1이어야 하기 때문이다.--> Mutual Exclusion 만족

Progress는 어떻게 되는가? P0만 들어가는 경우 P0만 실행이 된다.

flag[1] = false; 가 Time quantum이 끝나지 않아서 remainder를 실행하고 다시 실행하게 하는 경우도 Progress가 보장된다. 

 

 

Peterson's Solution

Synchronization은 thread간에서도 이루어진다. 변수 flag 변수와 x 변수가 존재한다. x는 무조건 100일 때만 출력한다. x가 0일 때 실행할 수 없다. 컴파일러 입장에서 Thread2를 컴파일 할 때 thread 1을 신경쓰지 않는다. Thread2간의 statement 관계가 전혀 없다. 바꿔서 속도 계산이 있다고 해서 먼저 flag = true로 바꿀 가능성이 있다. 그럴 때는 x 가 0으로 출력될 가능성이 존재한다. 

 

 

Memory Model

CPU 하나가 변수를 바꿨다. 그 바꾸자마다 변화를 즉시 반영하는 경우 Strongly ordered memory라고 부른다. cache에 있는 값이 존재한다. 해당하는 변수가 cache에만 존재하고 memory에만 반영되는 delay가 있는 경우 우리가 생각하는 if 문이 다르게 돌아갈 수 있는 가능성이 있다. 

 

 

Memory Barriers

barrier이전에 있었던 모든 이슈들은 이후에 모두 반영이 되어야 한다는 것이다. 제한을 걸어놓는 것이다. 그렇다면 x 가 100이 된 이후에만 반영이 될 것이라는 것이 아까와 차이점이 된다. 

 

 

Hardware Instructions

entry section과 exit section이 존재한다는 것. lock 변수가 존재한다. lock 이 0이면 들어가도 되고 1이면 들어가면 안된다. lock은 당연히 shared variable이다. entry section에서 해야 하는 것. 들어간다고 표시하고 누가 잠그지 않았는지 확인한다. 나올 때는 문을 열어 놓고 나온다. 

 

 

Mutual Exclusion by Lock variable

while(lock) 잠겨있지 않으면 내가 들어간다는 것. lock = true는 문을 잠그는 것이 된다. 나올 때는 lock = false로 하고 나온다. 동시에 들어가면 mutual exclusion이 보장되지 않는다. knocking과 locking 사이에 gap 이 있기 때문이다. 이것이 동시에 이루어져야 하는데 따로 따로 이루어지는 중간 타임이 위기 상황이 된다. lock과 knock은 분리 될 수 없다는 조건이 들어오면 된다. 한 번에 실행한다는 것은 actomic이라고 부른다. 

 

 

Interrupt disable

Interrupt를 막으면 Context Switching이 발생하지 않는다. 중간에 멈추지 않고 가버린다는 것을 의미한다. 

 

 

Hardware Instruction

TestAndSet

machine instruction이다. (Function이 아님!!!!!!!!!) 중간 과정이 없고 한 번에 확 실행이 되어버린다. 변수의 원래 값을 local에 카피하고 무조건 true로 셋업한 후 원래값을 반환한다. 어떤 값을 리턴하면서 동시에 그 변수의 값을 1로 바꿔버리는 것이다. knocking은 값을 꺼내오는 것이다. 그리고 locking하는 것은 1을 넣는 것이다. 함수가 아니라 Machine Instruction이 이렇게 동작한다는 것의 수도 코드이다(*******************)

lock 변수 a , local 변수 b가 있다. 값을 꺼내는 동시에 1로 바꿔버리는 동시적인 효과를 줄 수 있다.

 

 

compare and swap

value에 lock 변수가 expected와 같으면 new_value를 value에 집어 넣으라는 것. value의 값을 일단 꺼내온다. 변수의 값이 0이면 1로 overwrite해야 한다. CAS라고 부른다. knocking과 locking을 하나로 묶게 되는 명령어가 된다.