Published 2020. 5. 18. 21:05

14. Synchronization (1)

Quiz

When threads can concurrently access and change shared variables, we say that part of code is a ( ) and it may lead to a ( ).

To make the program run correctly, we need a mechanism to ( ) threads.

A ( ) is one of such mechanisms. A correct implementation should provide ( ), ( ), and ( ) properties.

Answer

critical section , race condition

synchronized

Lock, mutual exclusive, progressive,bounded waiting

Synchronization (동기화)
1. 논리주소 공간을 공유하는 협렵적 프로세스의 질서 있는 실행(orderly excution)을 보장하며, 데이터의 일관성(consistency)을 유지할 수 있으며, 이를 Synchronization 이라고 한다.
2. 여러 프로세스가 동시에 실행되게 되면, 여러 프로세스가 공유하는 데이터의 무결성에 문제를 일으킬 수 있다.
3. concurrency 때문에 프로그램의 행동이 non-deterministic하게 바뀔 수 있다.
4. 프로세스 또는 쓰레드들이 shared memory에 접근할 때, 그들의 순서를 조절해 주는 것 = Synchronization
5. Synchronization 하기위해 처리해주는 장치 = Lock
  1. aquire() : 화장실 문 열기
  2. release() : 안에 있는 사람 나오기
Race condition : 2개 이상의 concurrency한 쓰레드들이 공유된 자원에 접근할 때 Synchronization 메커니즘 없이 접근하려는 상황
Critical section
1. 여러 프로세스들이 공유하는 데이터에 접근하는 코드 영역
2. Critical section 에서 Race condition 이 발생한다.
3. 한번에 오직 하나의 프로세스만이 Critical section에 접근해야 한다.
4. Race condirion 의 해결 조건
  1. Mutual Exclusion
    1. 만약 프로세스 A가 Critical section에 진입해 있다면, 다른 모든 프로세스는 진입할 수 없어야 한다.
    2. 아무 프로세스도 Critical section에 못 들어가도 Mutual Exclusion은 만족한다. 그럼 어떻게? -> Progress
  2. Progress
    1. 만약 어떤 프로세스도 Critical section 내에 있지 않고, Critical section에 집입하려는 프로세스가 존재한다면
      실행 중이 아닌 프로세스들중 누가 진입할 지 결정할 수 있어야 한다.
    2. 결정은 무한히 연기될 수 없다.
  3. Bounded Waiting
    1. 프로세스가 Critical section에 진입할 때까지 걸리는 시간에 limit가 존재하여야 한다. 안그러면 Starvation 발생
      1. 프로세스의 개수 = n
      2. time quantum = q
      3. limit = (n-1) x q
5. Race condition 해결 방법
  1. Spinlock
    1. 문이 잠겼는지 안 잠겼는지 계속 확인하는 것
    2. while문을 돌면서 lock이 1이면 계속 기다리고 lock이 0이면 들어갈 수 있다.
    3. 단점 : 0번이 끝나고 1,2번이 Mutual Exclusive 할 수 있다 >> 문고리 동시에 잡아버린다.
  2. Software-only Alogorithm
    1. 상대방 = other, 나 = my_id. 를 통해 상태를 알린다.
    2. 단점 : 서로 기다리는 상황이 발생할 수 있다 >> Progress 가 제공이 안될 수 있다.
  3. Peterson’s Algorithm
    1. turn = other를 통해 먼저 양보하는 방법
    2. 단점 : atomic 하지 않은 곳에 쓸 수 없다.
  4. Synchronization Hardware
    1. Disabling Interrupt
      1. 인터럽트를 끄는 것.
      2. scheduler가 관여하지 못한다.
      3. 단점 : 안정성을 해친다, 보안이 약하다.
    2. Test-And-Set(변수의 위치, 새로 바뀔 값)
      1. 쪼개지 않고 한번에 수행하는 방법.
      2. 문고리를 잡고, 문을 잠그는 것을 쪼개지 않고 동시에 한다.
      3. 테스트해서 원하는 값이면 새로운 값으로 바꾸겠다.
    3. Compare-And-Swap
      1. 세개의 변수를 이용해서 처리한다.

쓰레드가 같은 데이터에 접근할 때 어떻게 될것인가?

우리가 돈 인출을 동시에 두군데서 한다면?

팔달관에서 돈을 빼가고 있는데 갑자기

팔달관에서 20만-5만 = balance 15만원으로 저장했는데

신학생회관에서 5만원을 빼가려고 한다.

아직 팔달관에서 set_balance하지 않았으므로 현재 팔달관 balance는 15만원이고, 신학생회관 balance는 20만원이고,

신학생회관에서 set_balance 해서 15만원되고, 팔달관에서도 그 후에 set_balance해서 15만원이 됐다.

이렇게 교묘하게 꼬여버리면 비정상적으로 돌게 된다.

이런 순서로 context switching이 되면서 수행되면 문제가 발생한다.

공유된 데이터를 동시에 업데이트를 하면 이 비슷한 경우는 항상 생기게 된다.

만약 쓰레드 두개가 동시에 inc()를 부르면

둘다 + 를 했지만 하나만 + 하게 된 꼴이 된다.

movl 0x100, %eax // 읽어오고
addl %1, %eax // 업데이트하고
movl %eax, 0x1000 //써라

Race Condition & Synchronization

여러 개의 인스턴스들이 shared resource에 대해서 값을 바꿀려고 한다.

그러면 concurrency 때문에 프로그램의 행동이 non deterministic 하게 바뀔 수 있다.

이것이 synchronization problem 이다.

두 개 이상의 concurrency한 쓰레드들이 공유된 자원에 접근하려고 할 때,

Synchronization 메커니즘 없이 접근하려는 상황을 race condition 이라고 한다.

race condition 때문에 이러한 문제가 발생했다.

이런 문제는 debug 하기가 굉장히 어렵다. >> Heisenbugs

요약 :

두개 이상의 쓰레드가 하나의 shared resource에 동시에 accessing하고 manipulting 하려다 보니까

프로그램이 non-deterministic한 결과를 내는데 이것을 race condition이 발생했다고 한다.

이런 경우가 발생 했을 때 발생하지 않도록 프로세스들이 shared resource에 접근하는 것을 잘 처리해 줘야 하는데,

그것을 우리가 synchronization이라고 얘기한다.

즉, 프로세스 또는 쓰레드들이 shared memory에 접근할 때, 그들의 순서를 조절하는 것을 Synchronization 이라고 한다.

Critical Section

첫번째로 어디서 race condition이 생기는지를 알아야 한다.

두개 이상의 쓰레드나 프로세스를 동시에 access 하거나 manipulation 할 때 생기므로

코드에서 여러개의 쓰레드나 프로세스가 동시에 건드리는 코드 부분이 있을 것이다.

그러한 부분을 critical section 이라고 한다.

다시 말하면 공유된 자원, 즉 동시 접근하려고 하는 그 포커싱된 자원! 에서 문제가 발생하지 않게 독점을 보장해줘야 하는 영역을

critical section 이라고 한다.

쓰레드 T1과 T2가 0x1000 이라는 주소에 있는 것을 처리하는 부분이다.

이 부분을 두개가 동시에 읽고 업데이트 하는 구조이다.

이런 부분이 critical section이다.

여러개의 쓰레드들이 이부분에 동시에 들어가는 것을 막아줘야 한다.

Lock

데이터 영역을 접근하는 것을 막는 것을 Lock 이라고 한다.

Lock 의미 그대로 걸어잠구는 행위를 의미한다.

내가 자원을 사용하고 있는 동안에는 문을 걸어 잠궈서 나 말고는 아무도 못 들어오게 하는 방식이다.

내가 쓰고 있으니 너는 기달려~ 이게 lock이다.

이러면 동시 접근 문제가 발생하지 않는다.

aquire() : Lock 에서 누가 해당하는 부분을 잡으려고 할 때 이 함수를 쓴다.

누군가 잡고 있다면 기다려야 한다. 누가 놓고 나가면 들어간다.

release() : 누군가 놓고 나가

ex)

화장실 => critical section

두명 다 들어가려고 한다 => race condition

한명만 들어갈 수 있게 하자 => mutual exclusive 하게 접근하자

화장실 문 => lock

화장실 문 열기 => aquire()

안에 있는 사람이 나오기 => release()

critical section에 위와 같은 코드로 처리해주면 된다.

Critical Section의 해결 조건

어떻게 하면 lock을 잘 설정할까?

Mutual exclusion : 하나의 쓰레드가 critical section에 한번씩 접근할 수 있다.

Progress : 누군가 lock을 잡고 놓았을 때 다른 쓰레드가 aquire해서 critical section에 잘 들어갈 수 있는가.

당연한거 같지만 잘못 짜면 여러개의 쓰레드가 lock을 하지만 아무도 aquire할 수 없는 상황이 발생한다.

Bounded waiting : 다른 애들이 계속 잡아가서 내가 원하는 애가 Starvation이 발생하여 진행이 안되는 상황

동시에 shared resource 접근 = Race Condition

Race Condition을 잘 막아주는 Synchroniztion

Synchronization하기 위해 처리해주는 장치 = Lock

Lock은 Correctness, Fairness, Performance 를 잘 고려해서 만들어줘야 한다.

Correct하려면 Mutual exclusive, Progressive property, Bounded wait property를 다 만족해야 한다.

Spinlock

held 가 0이면 아무도 없는 것

held 가 1이면 누군가 있는 것

while(I->held); 에서 held가 1이면 무한루프를 돌게 된다. 즉 여기서 Lock이 풀릴때까지 계속 도는 것이다.

그래서 우리는 이런 것을 빙글빙글 돌고 있다고 해서 spinlock 이라고 한다.

while문에서 도대체 이 무한루프를 어떻게 빠져나오나 의문이 들 수 있다.

그런데 지금은 스레드가 두개가 있다.

unlock이라고 하는 function을 다른 쓰레드가 호출해주면 held의 값이 0으로 바껴서

그 spinlock에 있던 쓰레드가 다른 쓰레드에 의해서 빠져나오게 되고 held를 1로 만드는 것이다.

I->held = 1; // 누군가 나올때 lock을 1로 만든다.

I->held = 0; // 누군가 나올때 lock을 0으로 만든다.

while (1->held); 누군가 있다면 계속 기다린다.(계속 돌고)

문이 잠겼는지 안잠겼는지 계속 확인하는 것 = spinlock

이게 잘 될까?

만약 0번 쓰레드가 lock이 끝나고 기다리고 있던 1번, 2번 쓰레드가 parrellel 하게 lock을 잡는다면?

이것도 제대로 된 구현이 아니다. Mutual Exclusive 하지 않기 때문이다. 화장실을 둘 다 쓸라고 문고리 잡아버림

소프트웨어 만으로 lock을 구현할 수 있고

하드웨어의 도움을 받아서 lock을 구현할 수 있다.

소프트웨어 적으로 Lock을 하는 법

화장실에 들어오려는 사람 두명! = 2개의 쓰레드

내가 화장실을 쓰고 싶어. 근데 너도 쓰고싶냐?

내 아이디를 0이라 하면 상대방은 1이 되고 내 아이디가 1이 되면 상대방은 0이 된다.

상대방을 other라고 한다.

상대방이 누군지 알게 되고

interested에서 내가 화장실 가겠소 하고 셋팅을 해놓고

while (interested[other]); // 만약 상대방이 화장실을 쓰고 있으면 기다린다.

interested[my_id] = FALSE; // 나는 화장실 다 썼소 하고 clear하고 나온다.

그럼 이건 잘 돌까? : 아니다.

interested[my_id] = TRUE; 에서 서로 1로 셋팅되면

while (intrerested[other]); 에서 서로 기다리고 있다.

실질적으로 lock이 aquire 안되고 있다.

Progressive property가 제공이 안되고 있는 것이다.

딱 한줄만 다르다.

서로 들어와서 나 관심 있소. 하면서 자기가 셋팅을 한다.

그런데 상대방에게 먼저 양보를 한다.

turn = other; 로 상대방의 값을 turn으로 저장한다.

while (interested[other] && turn == other); 을 통해서

상대방이 관심이 있으면 기다리고 && 상대방이 쓰려고 하는 턴이면 기다리고

상대방이 관심이 없고 && turn이 상대방 턴이 아니면 내가 쓴다.

interested[my_id] = TRUE; // 나 화장실 가고싶소

turn = other // 근데 너가 관심있으면 너가 먼저가

while (interested[other] && turn = other); // 너가 관심이 없던지 다 썼어? 그러면 내가 쓸게

1:1 >> Mutual exclusion is preserved : 상호 배제가 보존 되어야 한다. 동시에 접근하지 않으려면 서로 배타적이어야 한다.

0 >> Progress requirement is satisfied : critical section에 어떤 쓰레드의 접근도 없을 때 항상 접근이 가능해야 한다는 것이다.

1~ >> Bounded waiting requirement is met : 무한정 대기가 없어야 한다. 한 프로세스만 cs에서 돌면 다른 프로세스는 starvation 겪는다.

P0프로세스와 P1프로세스가 있지만 좀 더 일반화를 위해서 Pi와 Pj 프로세스로 표시해보자.

이 알고리즘의 특징은 flag 와 turn 이라고 하는 두 개의 변수를 사용한다.

flag 는 말 그대로 깃발, 즉 신호를 나타낸다. 내가 이 공유자원을 쓰고 싶어! 라고 표현하기 위한 변수이다.

turn 도 마찬가지로 차례를 의미하므로 누구 차례인지 명시해주는 변수라고 이해하면 된다.

// n개의 프로세스가 있을 때, i 번째 프로세스의 피터슨 알고리즘 구조도

do {
    flag[i] = true;
// 자 내가 먼저 critical section에 들어가고 싶으니까 내가 쓰고 싶다고 신호를 알려야 겠지?
// i 프로세스가 지금 사용하고 싶어! 라는 의미를 전달하기 위해 flag를 true로 바꿔준다.
    
    turn = j;
// 내가 들어가고 싶다고 선언해주고 j차례로 돌려줆으로써,
// 혹시 쓰고 싶은 다른 프로세스가 있나 확인한다.
// 만약 다른 프로레스 (j)가 이 공유 자원을 쓰고 싶어서
// 7번까지 실행한 상태(j입장에서는 flag[j] = true; turn = i; 까지 실행한 상태) 라면
// i 프로세스가 j 프로세스로 차례로 넘겨주자마자 while() 을 수행하고 critical section에 들어간다!
// 즉 내가 쓰기 전에 먼저 쓰고 싶어했던 애가 있는지 확인하고 수행시켜주는 코드가 7번 라인이다.
    
    while (flag[j] && turn == j);
// critical section에 들어가기 위해서는 당연히 내 차례여야 한다.
// 즉 turn == j일 경우 내 차례가 아닌데 j가 자원까지 쓰고 싶어 한다면
// 나는 spinlock에서 머물러야 한다.
// 반면에 내 차례거나 j가 자원을 쓰고싶지 않은 경우 (flag[j] == false)
// 이제 spinlock을 빠져나와 진입할 수 있다.
// 이렇게 turn과 flag 변수를 이용해서 동시 접근을 막는 것이다.

    flag[i] = false;
    
} while (true);

하드웨어 적으로 Lock을 하는 법

피터슨 알고리즘은 제약이 있다.

load and store 읽는 것과 쓰는 것이 다 일어나던지 다 일어나지 않던지 라는 가정을 하고 쓰는 것이다.

atomic 하다 = 다 쓰여지던지 다 쓰여지지 않던지

atomic 하지 않으면 i = 99가 넣어질 수도 있다.

atomic 하지 않은 곳에서는 피터슨 알고리즘을 쓸 수 없다.

그래서 100% 소프트웨어 만으로 구연하진 않고 하드웨어가 atomicity 한 기능을 제공해주고 나머지를 소프트웨어가 지원해준다.

(1) Disabling Interrupt

첫번째 방법은 interrupt를 끄는 것이다. 아예 읽고 업데이트 하고 하는 것을 하나로 하는 것

다른 애가 못 끼어들게 하는 것이다.

read, compute, update 의 과정을 하나로 하고, atomic하게 하고, 이 과정이 일어나는 동안 interrupt를 끄는 방법이다.

interrupt가 꺼져있는 동안에는 scheduler가 관여를 하지 못한다.

문제는 더 이상 interrupt라는 알람시계가 울지 않음으로 컴퓨터를 독차지하므로 보안 문제라던지 안좋은 문제가 생긴다.

시스템의 안정성을 해치는 것이다.

또한 다른 코어의 interrupt를 꺼버리는 문제도 생긴다.

(2) Test-And-Set

두번째 방법은

Atomic instruction : 어떤 instruction이 있는데 이 instruction은 다 수행이 되던지 아예 수행이 안되던지

Test-And-Set : 테스트해서 원하는 값이면 새로운 값으로 바꾸겠다.

xchg가 TestAndSet instruction 중 하나이다.

TestAndSet(변수의 위치, 새로 바뀔 값)을 받는다.

쪼개지지 않고 무조건 한번에 한다.

원래 값을 old에 빼주고 새로운 값을 변수의 위치에 넣어준다.

lock을 제일 처음 구현했을 때를 생각해보자.

lock의 위치를 넣어주고 lock이 held가 되어있는 동안 돌다가 만약에 안되면 내가 값을 셋팅을 하고 나가고.

이 예제의 문제는 mutual exclusion이 안되는 것이었다.

언제? 만약 T0, T1, T2라는 쓰레드가 들어와서 이 lock을 aquire 하고 있는데

held값을 T0가 가져가서 T1과 T2는 held값이 1이니까 계속 보고있는 상황에서

T0가 release해서 held 값을 0으로 바꿔버리는 순간, T1, T2 두개가 동시에 진입해서 held값이 둘다 1이 되어서

mutual exclusive property가 제공이 안되는 것이었다.

이것을 오른쪽과 같이 수정하면 정상적으로 돈다.

만약 T1이 TestAndSet(변수의 위치, 새로 바뀔 값)을 받으면 1이 되면

T2는 TestAndSet(변수의 위치, 새로 바뀔 값)을 받으면 1로 받아서 계속 spinlock을 돈다.

코드를 한 줄로 짰기 때문에 끼어들 곳이 없어서 인터럽트가 발생해서 꼬일 일이 없다.

atomic 하기 때문에 끼어들 수가 없다.

(3) Compare-And-Swap

expected 값과 원래의 v값이 같다면 원래 v값 리턴해준다.

compare_and_swap은 세개의 매개변수를 필요로 한다.

lock이 첫번째 매개변수와 두번째 매개변수가 같을 때만(lock이 0일 때만) Lock을 1로 설정한다.

하지만 return값은 두번째 세번째 매개변수와 상관 없이 항상 Lock의 상태를 반환해준다.

즉 lock이 아무것도 안 걸려있으면 0을 반환하고 lock을 1로 바꿔주고

lock이 걸려 있으면 1을 반환하고 lock은 그대로 1로 내버려둔다.

즉 lock이 1이면 계속 wile문에서 빠져나오지 못하고 기다리고 있는 것이다.

'🚦 Server > Operating System' 카테고리의 다른 글

16. Synchronization (3) (0)	2020.05.26
15. Synchronization (2) (0)	2020.05.26
Process VS Processor (0)	2020.05.17
13. Process Scheduling (4) (0)	2020.05.12
12. Process Scheduling (3) (0)	2020.05.07