[OS] H/W support for Synchronization

Hα ყҽσɳɠ·2020년 5월 5일

Operating system

목록 보기

9/10

✅ Memory Model

메모리 모델은 컴퓨터 아키텍처가 응용 프로그램에 제공 할 메모리를 결정하는 방법이다.

Strongly ordered

a memory modification on one processor is immediately visible to all other processors.
퍼포먼스 측면에서 손해가 있을 수 있다.

Weakly ordered

modifications to memory on one processor may not be immediately visible to other processors
cache가 다시 write-back될 때 반영되는 것처럼 즉각 반영되지 않는다.
퍼포먼스를 위해 이것을 사용한다.

✅ Memory Barriers (== memory fences)

memory barriers는 cpu나 컴파일러에게 특정 연산의 순서를 강제하도록 하는 기능이다.
(All loads and stores are completed before any subsequent load or store operations are performed)

Example

지난 포스팅에서 피터슨 알고리즘의 문제점과 마찬가지로 Thread2에서 x = 100과 flag = true의 실행 순서가 바뀔 수 있다. 두 개의 코드 사이에 memory barrier()를 집어넣는다. memory barrier는 barrier 앞에 존재하는 메모리 읽기/쓰기 연산들이 실제 메모리에 커밋되는 것을 보장한다. 위의 예제에서 Thread1의 while(!flag) 조건이 깨지는 순간에는 x에 100이 들어가 있어, print x를 실행하였을 때, 100이라는 수를 출력하게 된다.

✅ Hardware Instructions

H/W support makes it easier and improve efficiency.

✔️ Mutual Exclusion by Lock variable

A shared variable lock

bollean lock = 0;

초기값이 0이면, 아무도 안 들어간 것이다. 임계영역에 들어간 다음 lock을 true로 만든다. (== 잠근다.)
다른 프로세스들은 entry section에서 기다려야 한다. 임계영역에 들어갔던 프로세스가 나올 때는 lock을 false로 만들어 lock을 풀고 다른 프로세스가 임계영역에 접근 할 수 있도록 한다.)

critical section에 들어가면 true(1), 들어가지 않으면 false(0)

만약 위의 P0, P1 2개의 프로세스가 동시에 실행 될 경우, 둘 다 critical section에 들어가게 된다. 따라서, mutual exclusion을 보장할 수 못한다.
❓왜 이런 일이 발생하는가? while(lock);과 lock = true;가 한덩어리로 실행된다는 것을 보장할 수 없기 때문이다. P0에서 while이 실행된 후, lock = true;가 실행 되기 전에 P1에서 while(lock);, lock = true;을 실행하여 critical section에 들어가버리면 결국 2개의 프로세스 모두 critical section에 들어가는 것을 막을 수 없다.
💡solved key idea: 두 코드를 한 번에 실행시켜야 한다.
❗️이 경우, 위의 사진에 표시한 것과 마찬가지로 while(lock);, lock = true; 대신 while(TestAndSet(&lock));를 쓰면 된다. 자세한 내용은 뒤에서 알아보겠다.

✅ Interrupt Disable

Interrupt Disable는 하드웨어에 의한 mutual esclusion을 보장하는 방법이다.
이 방법은 interrupt를 disabling 하는 것이다. 인터럽트를 disable하면, context switching이 발생하지 않아 race condition이 생기지 않는다.
하지만 멀티프로세서 프로그램과 잘맞지 않고, 비효율적이라 잘 사용하지 않는다.

✅ Hardware instructions

하드웨어에서 다음과 같은 atomic instructions을 제공하면, locking을 쉽게 처리할 수 있다.

TestAndSet

파라미터로 전달된 target은 true값을 갖게 되고, return 값은 target이 갖고 있던 값이 된다.

Swap

두 개의 파라미터 값을 exchange한다.

compare_and_swap

val와 expected 값이 같을 경우, new_val의 값을 val에 넣고 val의 초기값을 리턴한다.
만약, val와 expected 값이 같지 않을 경우, 기존 val의 값을 유지한 채 val 값을 리턴한다.

✅ Mutual Exclusion using TestAndSet

공유변수는 lock이며 초기값은 false(== 0)이다.
앞에서 설명한것과 같이 TestAndSet에 초기값 0을 가지고 있는 lock을 파라미터로 전달하면 0을 return한다.
따라서 while문의 조건이 fail되므로 기다리지 않고 critical section으로 들어간다. 이 순간 TestAndSet의 정의에 의해 lock variable은 true값을 가지게 된다. (리턴 값은 0, lock은 1)
두번째 프로세스가 들어오면 lock은 true이므로, while문 조건에 걸려 기다려야 한다.
첫번째 프로세스가 exit section에서 lock = false;를 실행시키면, while문에서 TestAndSet의 return value가 false가 되어, 두번째 프로세스가 critical section에 들어갈 수 있다.

✅ Mutual Exclusion using Swap

공유변수는 lock이며 초기값은 false이다. key라는 local variable에 true를 assign한다.
초기에는 Key에 true를 넣었기 때문에 while문이 true가 되고, swap을 실행시킨다.
key값은 true였으므로 lock에는 true가 들어가고, key에는 원래 lock에 있던 값인 false가 들어가게 된다. 다시 while loop 조건에서 key는 false이기 때문에, 조건이 fail되면서, 첫번째 프로세스는 critical section으로 들어갈 수 있게 된다.
두번째 프로세스가 entry section에 진입했을 때 lock에 true가 있는 상태에서, swap을 실행하면 여전히 key값이 true이므로, while-swap을 계속 실행하면서 첫번째 프로세스가 exit section에서 lock을 false로 만들기를 기다리게 된다.

✅ Mutual Exclusion using CAS

lock은 false로 초기화되어 있다. compare_and_swap의 정의에 따라 리턴값은 lock에 있는 초기값인 false이므로 while문의 조건이 깨지게 되고 첫번째 프로세스는 critical section에 들어가게 된다. 그 순간 lock 변수는lock = lock == false ? 0 : 1 조건에 의해 1의 값을 가지게 된다.
두번째 프로세스가 entry section에 들어왔을 때에는 lock 변수가 1의 값을 가지고 있기 때문에 1을 리턴해주면서 while문에서 기다리게 된다. 첫번째 프로세스가 임계영역 코드 실행을 마치고 exit section에 가서 lock을 0으로 바꿔주면, 두번째 프로세스가 조건을 탈출하여 critical section에 들어올 수 있게 된다.

✔️ Bounded Waiting Mutual Exclusion

shared resource에 접근할 수 있는 기회를 랜덤하게 주는 것이 아니라 오른쪽에 있는 프로세스에게 다음 들어갈 기회를 준다. 위의 그림과 같은 경우, 공유자원을 스고 싶어하는 프로세스는 P0, P1, P3, P5이다. 현재 P1이 공유 자원을 사용하고 있고, 그 다음에는 P3이 들어갈 수 있도록 하는 것을 의미한다.

구현한 알고리즘을 살펴보자...

shared variables

mutual exclusion을 위한 lock과 프로세스가 critical section에 들어가고 싶은지를 나타내는 waiting[n] 변수가 필요하다. (n은 프로세스의 갯수를 나타낸다.)
i번째 waiting이 true라는 것은, Pi가 critical section에 들어가길 원하지만 아직 들어가지 않았다는 것을 의미한다. 실제로 들어가 있는 프로세스와 들어갈 마음이 없는 프로세스의 waiting 변수는 false값을 가진다.

Algorithm using TestAndSet

TestAndSet을 이용한 알고리즘은 다음과 같다.
주석처리한 부분을 잘 읽어보면 이해가 될 것이다!

while(true){
/* entry section */
// critical section에 들어가고 싶지만, 
// 아직 못들어간 상태이므로 waiting을 true로 셋업
waiting[i] = true;

// key: lock의 값을 다루기 위해 선언한 변수
key = true;

// critical section에 들어가기 전 조건 체크
while(waiting[i] && key)
	// lock의 초기값이 false이므로 
	// key는 false, lock의 값은 true
	key = TestAndSet(&lock);
// while문이 깨지면 critical section에 진입 가능

// 더 이상 기다리는 상황이 아니게 되므로 waiting을
// false로 바꿔준다.
	waiting[i] = false;

/* critical section */

/* exit section */
// 현재 프로세스 index는 i, 기회를 줄 다음 프로세스는 j
// circular한 구조이기 때문에 % n
j = (i+1) % n;

// j == i일 경우 중지
// waiting[j]가 true인 것을 만나면 중지
while (j!=i && !waiting[j])
	j = (j+1) % n;

if(j == i){ //기다리는 프로세스가 없다는 뜻
	//아무나 들어가도 된다
	lock = false;
}
else{ 
	// 다음 들어가고자 하는 프로세스에게만 열어줘야 한다
	// 특정한 프로세스의 waiting value만 false로
	waiting[j] = false;
}
/* remainder section */
}