프로세스 동기화(2022.03.20 수정)

728x90

E-Box와 S-Box는 추상화된 박스라고 생각

E-Box	S-Box
CPU	Memory
컴퓨터 내부	디스크
프로세스	해당 프로세스의 주소 공간

동기화 이슈 원인

데이터를 읽기만 하면 문제가 생기지 않는다.
하지만 데이터를 읽어와서 수정하고 결과를 다시 저장하는 방식에서는
"누가 먼저 읽느냐"에 따라 결괏값이 달라질 수 있다

경쟁 상태(Race Condition)

"여러" 주최가 "하나"의 데이터를 동시 접근하려 할 때를 Race Condition(경쟁 상태)라고 한다.

ex)

E-Box 2개가 동시에 S-Box 하나에 접근하여 count를 읽게 된다면 원치 않는 값이 나올 수 있다.

이때 E-Box 2개는 서로 "경쟁 상태"에 있다고 한다.

경쟁 상태 가능성

Memory <-> CPU

멀티 프로세서 시스템에서 A CPU가 C 데이터를 읽어가는 동안에 B CPU가 C 데이터를 읽을 경우

process 주소 공간 <-> process

공유 메모리를 사용하는 프로세스들

프로세스는 일반적인 경우에 자기 자신의 고유한 주소 공간에 접근하기 때문에 경쟁 상태가 일어나지 않는다.
하지만 프로세스 자기 자신이 직접 실행할 수 없는 부분은 운영체제에게 대신 요청(시스템 콜) 한다.
이때, 커널의 코드가 그 프로세스를 대신해서 실행된다.
커널 코드가 실행된다는 건 커널 내의 데이터에 접근한다는 것이다.
만약 이때, CPU를 뺏겨 또 다른 프로세스가 시스템 콜을 해서 커널 코드를 실행한다면
"커널 데이터"에서 경쟁 상태가 발생할 수 있다.
또, 커널 코드 실행 중에 "인터럽트"가 들어올 수 있다. 인터럽트를 처리하는 코드 또한 커널의 코드이다.
즉, 커널의 data에 접근한다는 것이다.

이처럼 유저 레벨에선 별로 문제가 생기지 않지만 커널로 들어가면

운영체제 커널 안에 있는 데이터는 "공유 data"이기 때문에 문제가 발생한다.

OS에서 경쟁 상태는 언제 발생할까?

kernel 수행 중 인터럽트 발생 시

count를 증가시키기 위해서 CPU 내부에서는 여러 번의 명령을 수행하게 된다.

메모리에 있는 변수 값을 CPU 안에 있는 레지스터로 불러들인다
- 이때 인터럽트가 발생 -> 인터럽트 핸들러로 넘어간다.
- 인터럽트 핸들러도 커널에 있는 코드이다. 즉, 커널 data인 count에 접근하여 1 뺄 수 있다.
- 인터럽트 처리를 끝내고 원래 상태로 되돌아온다.
레지스터에 있는 count값을 1 증가시킨다
다시 메모리의 변수 위치에 가져다 놓는다.

원래 예상 count 값은 그대로 이어야 한다.

하지만 인터럽트 때 1 감소시킨 것은 반영되지 않는다.

왜?
인터럽트가 일어난 시기를 보면 count 값을 레지스터로 불러들일 때이다.
그때 count에 1이 저장돼있다고 생각해보자.
인터럽트가 처리되고 나서 원래 상태로 되돌아왔을 때, 레지스터에 있는 count의 값은 1이다.
따라서 인터럽트 때 1을 뺀 것은 반영되지 않고 count는 2가 된다.

근데 count가 어떻게 공유되는 것일까?

커널 모드에서 실행 중 인터럽트가 발생하여 인터럽트 처리 루틴이 실행된다.
즉, 양쪽 다 커널 코드이므로 kernel address space를 공유하여 count가 공유되는 것이다.

결론

커널의 코드가 수행 도중에 인터럽트가 발생하여 처리하게 되면 커널의 데이터를 양쪽에서 접근하게 된다.
즉, 수행 도중에 CPU를 얻어가서 처리했기 때문에 이런 문제가 생기게 된다.

해결 방법

count와 같은 변수 값을 건드는 동안에는 인터럽트가 들어와도 인터럽트 처리 루틴으로 넘기는 게 아니라 작업이 끝날 때까지 인터럽트 처리를 하지 않는다.
인터럽트를 disable 시키고, 작업이 끝난 뒤, enable 시킨다.

Process가 System call 하여 커널 모드로 수행 중인데, context switch가 일어나는 경우

이 상황은 P(A)가 System call을 하여 커널 코드에서 실행하면서 count 값을 1 증가시키는 도중에

P(A)의 할당 시간이 끝나서 CPU가 P(B)에게 넘어갔다.

P(B)도 System call을 하여 count 값을 1 증가시키고 할당 시간이 끝나서 다시 A에게 CPU가 넘어갔다.

A는 실행했던 것을 메모리에 올려, 이어서 count 값을 1 증가시키려고 한다.

그래서 count는 2가 증가해야 하지만, P(B)에서 증가된 것은 반영되지 않는다.

왜?
증가되기 이전의 count값을 읽었고, 그 시점에서 context를 저장했기 때문이다.
따라서 context를 다시 불러들일 때, count 값은 증가되기 이전의 값이었고
결국 1이 증가된다.

해결 방법

프로세스가 커널 모드에 있을 때는 할당 시간이 끝나도 CPU를 뺏기지 않도록 한다
타임 퀀텀이 끝났지만 커널 모드가 끝나고 유저 모드로 빠져나올 때 CPU를 빼앗는다.

Q.
그러면 한 프로세스가 할당 시간을 넘어서 사용하게 되는데, 이 부분은 문제가 없을까?
A.
time sharing은 real time 시스템과 다르게 조금 시간이 더 갔다고 해서 시스템에 문제가 생기지 않는다.

멀티 프로세서에서의 환경 ( CPU가 여러 개 있는 환경 )

이 문제는 앞에서 설명한 것들로 해결이 안 된다.

공유 데이터에 접근하는 작업이 진행되는 동안에 인터럽트를 disable 시키는 방법

이 방법이 통하지 않는 이유는 1번 CPU에서 인터럽트를 막는다고 2번 CPU가 접근하지 말라는 법은 없기 때문이다.
작업 주최가 "하나"가 아닌 "여러 개"여서 해결할 수 없다.

이러한 문제가 생기는 근본적인 이유

사용자 프로그램이 아닌 "운영체제 커널"에 여러 CPU가 동시에 접근하기 때문

그러면 어떻게 해결해야 할까?

두 가지 방법이 있다.

개별 변수(커널 내부에 있는 각 공유 데이터)에 접근할 때 lock을 걸어야 한다
- 데이터를 들고 가기 전에 lock을 걸어, 어느 누구도 이 데이터에 접근 못하게 한다.
- 데이터를 변경하고 저장이 끝났으면 lock을 풀어서 해당 데이터에 접근할 수 있게 한다.
커널에 접근하는 CPU를 매 순간 하나만 접근하게 한다. 즉, 커널 전체를 하나의 lock으로 막고 커널에서 빠져나올 때 lock을 푼다
- 해당 방법은 매우 비효율적이다. 그래서 개별 변수마다 lock을 거는 방법이 더 낫다.

정리

프로세스 동기화 문제

여러 주최가 동시에 공유 데이터에 접근하려 해서 데이터의 불일치가 발생
- 공유 데이터에 동시에 접근하려는 상황을 "Race Condition"이라 함
- "Race Condition"에 생기는 문제를 막기 위해 동시에 실행하는 프로세스 간에 동기화가 잘 돼야 한다.
이러한 데이터 일관성 유지를 위해 프로세스 간의 실행 순서를 정해주는 메커니즘 필요

경쟁 상태의 예

사용자 프로세스 P1 수행 중 timer interrupt가 발생해서 context switch가 일어나 P2가 CPU를 잡으면 어떻게 될까?
앞에서 말했다시피 일반적으로는 문제가 생기지 않는다.
왜?
프로세스는 각각 고유한 주소 공간에 접근하기 때문이다.

그러나 shared memory를 사용하거나 실행 중에 커널 코드를 건드리는 동안이면 생기는 문제이다.

Q.
이런 문제가 있다는 전제 하에 서로 다른 주최 2개가 공유 데이터를 접근한다면 문제를 어떻게 해결할까?

A.
프로세스가 "크리티컬 섹션"에 들어가 있으면 CPU를 뺏겨서 다른 프로세스가 CPU를 넘겨받아도
공유 데이터를 접근하는 크리티컬 섹션에 들어가지 못하게 한다.
P1이 크리티컬 섹션에서 빠져나갔을 때, P2는 공유 데이터를 접근할 수 있게 한다.

크리티컬 섹션

우리말로 임계 구역, 즉, 공유 데이터를 접근하는 "코드"를 말한다.
그림에서 크리티컬 섹션은 어디일까?
- 공유 데이터인 X에 접근하는 "X = X + 1, X = X - 1"이다.

Critical Section(임계 구역)

do{
    entry section
    critical section
    exit section
    remainder section        
} while(1)

어떤 프로세스든 간에 공유 데이터에 접근하거나(critical section)

그렇지 않거나(remainder section)가 반복되면서 구성된다.

만약 공유 데이터를 그냥 접근하면 동시 접근을 통해 문제가 발생할 수 있기 때문에

접근하기 이전에 entry section 부분에서 lock을 건다.

왜?
여러 프로세스가 크리티컬 섹션에 들어가는 것을 방지하기 위해

그러고 나서 exit section에 가면 lock을 풀어줘서 다른 프로세스가 임계 구역에 들어갈 수 있게 한다.

임계 구역 문제 해결

임계 구역 문제를 해결하기 위해서 3가지를 만족해야 한다.

Mutual Exclusion(상호 배제)
- 배타적으로 접근해야 한다. 어떤 프로세스가 임계 구역에 들어가 있으면 다른 모든 프로세스는 임계 구역에 들어가지 못하게 한다.
Progress(진행)
- 아무도 임계 구역에 있지 않은 상태에서 임계 구역에 들어가고자 하는 프로세스가 있으면 들어가게 해줘야 한다.
- 다만 이 조건은 충족하지 못할 경우도 있다.
  - 두 개의 프로세스가 동시에 들어가는 것을 막다 보니, 둘 다 안 들어가 있음에도 불구하고 코드를 잘못 짜면 아무도 못 들어가게 하는 그런 문제가 생길 수 있다.
Bounded Waiting(유한 대기)
- 특정 프로세스 입장에서 임계 구역에 들어가지 못하고 지나치게 오래 기다리는 "starvation"이 생기지 않아야 한다.
  - starvation
    - 임계 구역에 들어가고자 하는 프로세스가 3개 있는데, 2개만 서로 번갈아가며 임계 구역에 들어가면서 나머지 하나는 못 들어가고 마냥 기다리는 그런 상황을 말한다. 즉 유한 대기 조건을 만족하지 못하는 상황이 나올 수 있다.

Q.
그렇다면 이 임계 구역 문제는 도대체 왜 발생하는 걸까?

A.
만약에 CPU를 뺏기지 않고 do-while문을 한 번에 수행한다면 문제가 발생하지 않을 것이다.
단일 instruction이 끝나면 CPU를 빼앗기거나, 빼앗기지 않을 수 있다.
하지만 do-while문은 단일 instruction이 아니기 때문에,
이걸 수행하는 "도중에" CPU를 뺏길 수 있어 문제가 발생하는 것이다.

임계 구역 문제를 해결하기 위한 알고리즘

동기화 변수인 turn을 사용

int turn;
initially turn = 0;
do{
    while(turn != 0);
    critical section
    turn = 1;
    remainder section
} while(1)

turn의 값이 Pi 프로세스의 차례이다. 즉, P0이 임계 구역에 들어가기 위해서는 turn = 0을 만족해야 한다.

해당 방식의 문제점은 Progress 조건을 만족하지 못한다.

왜?
해당 코드는 임계 구역을 반드시 교대로 들어가게 설정됐다.
만약 각 프로세스들이 임계 구역에 들어가려는 빈도가 균일하지 않으면 어떻게 될까?
예를 들어 P0는 임계 구역을 1번만 들어가고 싶고, P1은 여러 번 들어가고 싶은 상황이다.
P0가 한 번 들어가서 turn을 1로 바꿔주고 P1이 임계 구역에 들어갔다 나오면서 turn을 0으로 바꿔준다.
그 이후에는 P0가 들어가지 않기 때문에 turn이 1로 바뀌지 않는다.

flag 사용

boolean flag[2];
flag[ALL] = false;
do{
    flag[i] = true;
    while(flag[j]);
    critical section
    flag[i] = false;
    remainder section
} while(1)

flag는 깃발이라는 의미로 해당 index의 프로세스가 임계 구역에 들어가고 싶은 의중을 나타난다.

초기값은 false로 두 프로세스가 임계 구역에 들어가고자 하는 상태가 아님을 나타낸다.

각 프로세스가 임계 구역에 들어가려면 본인 flag을 true로 만든다.

그리고 상대방 flag를 체크한다.

상대방의 flag가 true라면 상대방은 지금 임계 구역에 들어가겠다는 표시를 했고, 현재 임계 구역에 있겠구나 라는 생각으로 while문에서 계속 돈다.
만약 상대방의 flag가 false라면 임계 구역에 들어가고, 나오면서 본인 flag을 false로 한다.

해당 방식의 문제점은 Progress 조건을 만족하지 못한다.

왜?
Pi가 본인의 깃발을 들고(flag[i] = true) , 지금 CPU를 뺏긴다고 가정해보자.
CPU를 뺏기고 나서 해당 CPU는 Pj에게 넘어간다.
그리고 당연히 Pj는 자신의 깃발을 들고 임계 구역에 들어가려 한다.
하지만 깃발을 들고 Pi의 flag를 체크하는데 true가 되어있다. -> while문을 계속 돌게 된다.

즉, 지금 상황은 두 프로세스가 깃발을 든 상태이며 누구도 임계 구역에 들어가지 않은 상태이다.

피터슨 알고리즘

do{
    flag[i] = true;
    turn = j;
    while(flag[j] && turn == j);
    critical section
    flag[i] = false;
    remainder section
} while(1)

해당 방법은 1번의 turn과 2번의 flag를 모두 사용한다.

Pi가 임계 구역에 들어가고자 할 때

자신의 깃발을 든다(flag [i] = true) -> turn은 상대방으로 바꿔놓는다(turn = j)
상대방이 깃발을 들고 있고, 이번이 상대방의 turn이라면 기다린다.
상대방이 깃발을 들지 않았거나 "또는" 상대방의 턴이 아니라면 Pi가 임계 구역에 들어간다.

해당 방법은 "수행 중"에 CPU를 빼앗기더라도 앞의 3가지 조건을 모두 만족한다.

해당 방식의 문제점은 "Busy Waiting"이 존재한다. (spin lock)

Busy Waiting(Spin Lock)?

현재 P0가 임계 구역에 들어가 있는 상태에서 P1이 CPU를 잡게 된다면 P1은 계속 while문을 돈다.
왜?
임계 구역에 P0가 들어가 있고, 현재 CPU는 P1이 잡고 있기 때문에 계속 기다려도 P0가 CPU를 잡고 임계 구역에서 나오지 않는 이상 while문을 계속 돌게 된다.

즉, 임계 구역에 들어갈 수 없는 상황에서 자신의 CPU 할당 시간 동안 계속 while문을 돈다.

Q.
단순하게 생각해보면 임계 구역 문제를 해결하려면
임계 구역 들어가기 전에 락 걸고, 나올 때 락 풀면 되지 않나?
왜 turn, flag을 같이 쓰면서 이렇게 복잡하게 코드를 만들까?

A.
하나의 instruction이 끝나면 CPU를 빼앗길 수도, 빼앗기지 않을 수도 있다.
이러한 여러 개의 문장(여러 개의 instruction) 이 하나하나 실행되는 도중에 CPU를 빼앗길 수 있다는 가정 하에
코드를 작성하다 보니 소프트웨어적으로 복잡한 코드가 만들어진 것이다.

Synchronization Hardware

소프트웨어 기반 해결책은 최신 컴퓨터 아키텍처에서 작동하지 않을 수 있음

왜 이렇게 말하는 걸까?
앞서 피터슨 solution은 "현대 컴퓨터 구조"에서 load와 store 같은 수행방식에서는 올바르게 실행 보장 X
"현대 컴퓨터 구조"란 멀티 스레드 환경을 말함. 싱글 스레드에서는 "재정렬"이 되어도 최종 결과가 같음
- 종속성이 없는 읽기 및 쓰기 작업을 "재정렬"할 수 있음. 멀티 스레드 환경에서는 재정렬에 의해 값이 달라질 수 있음
예로 위의 피터슨 방법에서 while문 위쪽 코드의 순서를 바꾸게 되면 CS에 동시에 들어가는 경우 발생
- process0이 trun = 1로 변경
- process1이 turn = 0, flag[1] = true 로 변경한 후 cs에 접근
- process0이 flag[0] = true로 변경한 후 cs에 접근
  - turn == 1 이 false 이기 때문에 cs에 접근 가능, 즉, process0이 깃발을 들고 있고 자기 차례임

만약에 "하드웨어"적으로 읽기와 수정을 atomic 하게 수행할 수 있도록 지원할 경우
앞의 임계 구역 문제는 쉽게 해결할 수 있다.

우리가 어떤 데이터를 읽기, 수정하는 것을 하나의 instruction으로 처리할 수 없기 때문에 이런 일이 발생하는 것이다.
만약에 읽기, 수정을 하나의 instruction으로 즉, atomic 하게 연산할 수 있다면 도중에 CPU를 빼앗기지 않을 것이다.
즉, 하나의 instruction이 끝났을 때 인터럽트가 들어와서 CPU를 빼앗길 수 있다.
그래서 instruction 하나를 가지고 동시에 작업할 수 있다면, "하드웨어"적인 그런 것이 있다면 간단하게
락을 걸고 푸는 문제를 해결할 수 있다.

Memory Barriers

"프로그래머"가 모르게 cpu 내부에서 코드의 순서를 바꿔 최적화 하는 기능이 존재함
따라서 프로그래머가 "원하는 순서"와 실제 실행되는 순서가 달라짐
이를 위해 Memory Barrier 생김
Memory Barrier 기준으로 뒤에있는 코드가 앞에있는 코드보다 먼저 메모리에 반영될 수 없다
- 즉, 뒤에 있는 코드가 먼저 실행될 수는 있지만(CPU가 쉬는게 아님), 앞에 있는 코드가 실행될 때는 메모리에 반영되지 않는 상태의 데이터를 받음
강한 메모리 모델 : cpu 내부에 주어진 "코드 순서 그대로" 한다
약한 메모리 모델 : cpu 가 "프로그래머"가 "모르게" 최적화를 진행할 수 있음, 즉 순서가 달라질 수 있음

Test_and_Set

lock = false;
do{
    while(Test_and_Set(lock))
    critical section
    lock = false;
    remainder section
} while(1)

하드웨어적으로 "Test_and_Set"이라는 고유의 instruction이 있다.

매개변수의 값을 읽어내고 그 값을 1로 바꿔준다.

읽고 수정하는 것을 atomic 하게 실행한다.

Test_and_Set(a)
- a = 0
  - 0을 읽고 a의 값은 1로 바꾼다.
- a = 1
  - 1을 읽고 나서 다시 1로 세팅한다.

프로그래머가 매번 이러한 작업을 하는 게 대단히 불편함

그래서 보통은 프로그래머가 이런 작업을 하는 게 아니라 연산만을 통하여 락을 이용하기 위해

추상화 자료인 "세마포어"를 사용한다.

Semaphores

세마포어라는 변수를 사용하고, 그에 대한 연산이 있다. 연산은 두 가지가 있다.

그렇다면 우리는 왜 세마포어를 사용할까?

앞서 락을 걸고, 풀었던 작업을 세마포어를 이용해서 연산을 통해 프로그래머에게 간단하게 제공한다.
공유 자원에 대해 획득하고 반납하는 것을 세마포어가 처리해준다.
mutex보다 더 정교하게 동기화할 수 있음

연산 종류

S는 세마포어 변수이다.

P, V 연산은 "atomic" 하게 연산되는 것을 가정하고 있다.

P연산(wait)

세마포어 변수를 획득하는 과정, 즉, 공유 데이터를 획득하는 과정
자원이 있으면 하나를 가져가고, 없으면 while문을 돌면서 기다린다. 당연히 이 작업은 atomic 하게 이뤄져야 함

V연산(signal)

자원을 사용하고 나서 반납하는 과정

Counting 세마포어 & Binary 세마포어(=mutex)

Counting 세마포어
- 세마포어 변수인 S는 "정수 값"을 가질 수 있다 -> "자원의 개수"라고 생각
Binary 세마포어(mutual exclusion(lock/unlock)에 사용)
- 세마포어 변수가 0 또는 1 만을 가진다고 생각하면 된다.
- 즉, P는 락을 거는 연산, V는 락을 푸는 연산이다.

여기서도 busy-waiting이 발생하게 된다.

왜?
자원이 없을 때, P 연산을 하게 되면 while문을 계속 돌아봐도 자원이 없기 때문에
할당된 CPU 시간 동안에 while문을 계속 돌다가 시간을 다 쓰면 반납한다.

임계 구역 문제에서의 세마포어 적용

semaphore mutex = 1;
do{
    P(mutex);
    critical section
    V(mutex);
    remainder section
} while(1)

임계 구역에 들어갈 때 P연산을 하고, 나올 때 V연산을 하면

임계 구역 문제가 자연스럽게 해결된다.

프로그래머는 세마포어가 지원된다면 이처럼 P, V 연산만 해주면 된다.
P, V 연산이 어떻게 구현되어있는지는 구현한 시스템에서의 몫이다.
앞에서 Test_and_Set 이런 것처럼 코딩하는 것이 아닌,
"추상 자료형"을 제공받고, 프로그래머는 단지 세마포어만 사용하면 된다.

하지만 위에서 말했다시피, 해당 코드에서 spin lock이 발생한다.

spin lock이 발생하지 않기 위해 세마포어 구현 방식을 block & wakeup로 할 수 있다.
- 락을 얻지 못한 프로세스는 쓸데없이 CPU를 사용하지 못하게 block 상태로 만든다.

누군가가 공유 데이터를 쓰고 있다
데이터를 반납할 때까지 내 차례가 오질 않는다
쓸데없이 while문을 돌지 않고 block 시켜 CPU 반납 시킴
누군가가 데이터를 반납할 때 block 된 프로세스를 wake 함
wake 된 프로세스는 ready 큐에 들어가서 CPU 할당 받음

Block / Wakeup 방식

typedef struct{
    int value;
    struct process *L;
}
P(S)
        S.value--;
        if(S.value < 0) {
            add this process to S.L;
            block();
        }
        
V(S)
        S.value++;
        if(S.value <= 0){
            remove a process P from S.L;
            wakeup(P);
        }

value

세마포어 변수 값

세마포어 때문에 잠들어 있는 프로세스들을 연결하기 위한 큐(wait queue)

만약 지금 세마포어를 획득할 수 없다면 프로세스 block

누군가가 세마포어를 쓰고 반납하게 된다면 block 된 프로세스 중에 하나를 wakeup

세마포어를 얻지 못한 프로세스들은 L에 PCB를 줄줄이 연결시켜 놓는다.

P연산
- 자원을 획득하는 과정
- 자원의 여분이 있다면 획득, 없다면 block
- 자원의 값을 먼저 1 뺀다
- 세마포 값이 음수이면 이미 자원의 여분이 없는 상태 -> block
V연산
- 자원을 반납하는 과정
- 자원을 반납하고 끝내지 않고 해당 자원이 없어 잠들어있는 프로세스를 wakeup
- 여기서 왜 자원을 반납하고 나서 value <= 0 일 때 깨우는 것일까? 왜 value > 0일 때 깨우는 게 아닐까?
  - P연산을 보면 자원을 획득할 때 value의 값을 빼놓고 잠이 들었기 때문이다. 그래서 만약에 자원을 내놓았음에도 불구하고 그 값이 0 이하라는 말은 해당 자원을 기다리면서 block 된 프로세스가 있다는 뜻이다.
  - 만약 양수였다? 하면은 이미 P연산 때 빼고 자원을 할당받았을 것이다 -> block 된 프로세스가 없다.

busy-waiting과 block & wakeup 차이

busy-waiting
- value가 0이면 자원이 없는 것이고 1이면 자원이 한 개 남아있다는 뜻
block & wakeup
- s.value가 자원의 개수를 세는 그런 의미와 좀 다르다.
  - s가 음수면 자원을 기다리는 process가 존재하는 뜻
  - s가 양수 또는 0이면 자원의 여분이 있기 때문에 기다리는 process 존재하지 않는다는 뜻
- 즉, 깨워야 할 프로세스가 존재하는지 판단하는 "상황"을 나타내는 것이라고 생각!

둘 중 어느 것을 사용하는 것이 좋을까?(스핀락 or block & wake-up)

보통 block 방법을 사용하는 것이 효율적

물론 block 방법도 오버헤드가 존재

block 경우
- running -> waiting
wake-up 경우
- waiting -> ready
- ready상태로 바꿔주는 것이지 wake-up하는 스레드가 CPU를 반납해야하는 것이 아님

만약에 임계 구역의 길이가 짧다면 busy-waiting을 해도 심한 오버헤드 유발하지 않는다.

왜?
만약에 임계 구역의 길이가 길어진다면,
락이 풀어질 때까지 오랜 시간이 걸리기 때문에,
그 시간 동안 while문을 계속 돈다면 CPU를 매우 비효율적으로 사용하게 된다.

Q.
busy waiting가 더 효율적인 경우도 존재한다고 한다.
결국 block&wake-up 방식에서와 같이 컨텍스트 스위칭이 일어날텐데 왜 효율적이라고 할 수 있는 것일까?
무조건 block&wake-up 방법이 좋은거 아닐까?

A.
싱글코어에서의 block&wake-up은 CS에 접근하기 위해서는 컨텍스트 스위칭이 일어나야함.
그래서 스레드가 lock을 얻지 못한다면 계속 CPU를 쓰는 것보다 바로 block하여 CPU를 반납하는 것이 효율적!!
따라서 "싱글코어"에서는 block&wake-up방식이 효율적임!!

멀티코어에서는 각 코어에 스레드가 수행되는 것임
만약 block&wake-up이라면 곧 자기 차례가 올텐데, 그 순간을 견디지 못하고 컨텍스트 스위칭
컨텍스트 스위칭 시간과 자기 차례가 올때까지 기다려야하는 시간이 lock -> unlock 수행 시간보다 길면 당연히 busy waiting하는 것이 효율적이다.

결국 질문에 대한 답을 말하자면
멀티코어에서의 busy waiting 방식에서는 컨텍스트 스위칭이 일어나지 않는다! 그래서 무조건 block&wake-up 방법이 효율적인 것이 아니다

모니터

세마포어는 프로세스 동기화를 시행하지만,

"어떤 동기화할 수 있는 방법"을 프로그래머에게 알려주고, 프로그래머는 P, V 연산을 통해서 사용한다.

그래서 세마포어를 사용하다가 프로그래머가 실수하게 되면 동기화가 깨지게 되어 엄청난 치명적 영향을 줄 수 있다.

그래서 모니터라는 것이 등장했다.

모니터는 "프로그래밍 언어" 차원에서 동시 접근과 관련된 문제를 모니터가 자동으로 해결해줌으로써

프로그래머의 부담을 줄여준다.

모니터는 "프로그래밍 언어 차원"에서 동기화 문제를 해결한다.

공유 데이터에 접근하기 위해서는 모니터라고 정의된 내부의 procedure를 통해서만 공유 데이터에 접근할 수 있다.

그림에서 보시다시피 공유된 데이터는 바깥에서 접근할 수 없다.

모니터의 기능

접근하는 procedure를 정의하고, 공유 데이터를 접근하고 싶으면 정의된 procedure를 통해서만 접근할 수 있다.
모니터가 원천적으로 내부의 procedure가 동시에 실행을 할 수 없게 한다.
- 모니터 내에서는 한 번에 하나의 프로세스만이 활동 가능
- 프로그래머 입장에서 락을 걸 필요가 없다.
- 기본적으로 동시 접근을 허락하지 않기 때문이다.
프로세스가 모니터 안에서 기다릴 수 있도록 condition variable (x, y) 사용 -> wait, signal 연산에 대해서만 접근
condition 변수는 세마포어처럼 어떤 값을 가지는 "변수"가 아니라 어떤 프로세스를 잠들게 하고, 줄 세우기 위한 변수이다. 개수를 카운트하거나 값을 가지고 있지는 않다.
예를 들어, 모니터 안에서 어떤 코드가 실행하다가 조건을 충족하지 못해 block 시킨다. "어떤 조건"을 만족하지 못해서 잠들게 됐는지에 따라 그 조건에 해당하는 것을 변수로 두는 것이다.
- wait
  - x라는 자원 여분이 있으면 바로 접근할 수 있게 해 주고, 여분이 없어서 기다려야 함
  - 어떤 프로세스를 block 시킨다 할 때 x.wait를 호출하면 해당 프로세스는 x라는 컨디션 변수에 가서 줄 서있게 된다.
  - x라는 조건을 만족하지 못해서 잠들어있다는 뜻
- signal
  - 빠져나갈 때 호출
  - x.signal이라는 것은 누군가가 이제 x를 다 쓰고 빠져나가서 혹시 x가 없어서 잠들어있는 프로세스가 있다면 깨워주는 행동까지 수행

Bounded-Buffer Problem -> 모니터로 변화

보시다시피 모니터에서는 락을 걸 필요가 없다.

왜?
공유 버퍼가 "모니터 내부"에 정의되어 있음. 즉, 바깥에서 접근하지 못함
생산하거나 소비하는 작업을 하기 위해서는 모니터 내부 코드를 실행해야 하고,
생산자든 소비자든 하나의 프로세스만 활성화되기 때문에 락을 걸 필요가 없다. (모니터 내부에서 동시 실행을 제어)
즉, 공유 버퍼에다가 데이터를 집어넣거나 빼는데 락을 걸 필요가 없어진다.

full.signal()

데이터가 들어있는 버퍼가 없어서 잠들어있는 소비자가 있다면 깨워준다.

세마포어와 모니터 "목적에 따른 차이"

모니터
- 모니터 차원에서 아예 동시 접근을 막는다.
세마포어
- 자원을 획득하기 위해서 프로그래머가 알아서 P, V 연산을 해줘야 하는 것

Q.
프로세스 동기화, 병행 제어 둘이 같은 말일까?

A.
프로세스 동기화는 "프로세스가 동시에 무언가를 실행하면서 생기는 문제를 해결하는 것"이고,

병행 제어는 "동시 실행될 때 그것을 잘 컨트롤해서 문제가 생기지 않게 하는 것"이다.

Q.
여러 가지 프로세스 동기화와 관련된 문제들이 있는데 그걸 해결하는 방안으로 프로그래머 관점에서 어떻게 하면은 병행 제어를 잘할 수 있을까?

A.
그걸 제공하는 "수단"으로 세마포어가 있다.

모니터 정리

procedure와 공유 데이터를 모니터 안에 정의함으로써 "프로세스가 공유 데이터에 접근"하려면
모니터 안에 정의돼있는 procedure을 통해서만 공유 데이터에 접근할 수 있다.
또한, procedure를 동시에 실행시키지 못하게 모니터 자체가 모니터 안에서 "액티브한 프로세스"를
단 하나만 있게 제어한다.

Q.
어떻게 "액티브한 프로세스"를 단 하나만 있게 제어할까?

A.
한 프로세스가 procedure를 수행하다가 도중에 CPU를 뺏겨서 다른 프로세스가 모니터에 접근하려 할 때,
이미 CPU를 뺏긴 프로세스가 여전히 액티브한 상태로 모니터에 남아있다.
그래서 현재 CPU를 할당받은 프로세스가 모니터 안에 있는 코드를 실행하지 못하고,
모니터 밖에 있는 큐에 줄 서서 기다리게 된다.
줄 서 있는 프로세스는 모니터 내부의 액티브한 프로세스의 개수가 0이 될 때 들어올 수 있다.

액티브한 프로세스는 block 되거나 모니터에서 빠져나갈 때 개수가 0이 된다.

Q.
프로세스가 모니터 안에서 CPU를 빼앗길 때는 액티브한 상태이고, blcock 상태가 되면 액티브한 상태가 아닌 것인가?

A.

세마포어를 사용하면서 발생되는 Deadlock & Starvation

세마포어를 사용할 때 원치 않는 문제가 생길 수 있어서 사용할 때 주의점이 있다.

Deadlock

가정
- 현재 어떤 작업을 하기 위해서는 S, Q 세마포어를 모두 획득해야 한다.
- P0, P1 모두 그 작업을 하려고 자원을 얻는 중이다.
- S와 Q는 배타적으로 프로세스 하나만 사용할 수 있는 세마포어이다.
실행
- P0가 먼저 CPU를 얻어 S 세마포어를 얻은 다음에 CPU를 뺏김
- P1이 CPU를 얻어 Q 세마포어를 획득
- S를 획득하려고 했으나 P0가 가지고 있어서 현재 P2는 기다림
- 그러나 영원히 기다려야 함
  - S를 획득하기 위해서는 P0가 S를 반납해야 하지만 P0 또한 Q까지 획득한 다음에 작업을 완료하고 S를 반납함
- P0, P1이 자원 각각 하나씩 획득하면서 둘이 절대 자원을 반납하지 않으면서 상대방이 가진 것을 기다리는 상황
양쪽 다 영원히 조건을 충족하는 못하는 상황인 "Deadlock"
정리
- 상대방 것을 기다리면서 자기 것은 내놓지 않은 상황 -> 영원히 기다려야 함
- 해당 문제를 해결하기 위해서는 자원을 얻는 데에 우선순위를 둔다
- 즉 Q를 얻기 위해서는 무조건 S를 얻어야 한다.

Starvation

특정한 프로세스가 영원히 자원을 얻지 못하고 무한히 기다려야 하는 현상
Deadlcok도 starvation이라 할 수 있음
- 하지만 지금 말하는 starvation은 "특정 프로세스"들만 자원을 공유하면서 "다른 프로세스"는 영원히 자기 차례로 오지 못하는 현상
식사하는 철학자

Synchronization와 관련된 Classic 한 3가지 문제점

1. Bounded-Buffer Problem(Producer-Consumer Problem)

임시로 데이터를 저장하는 "버퍼"라는 공간이 유한적이다.

프로세스의 종류

Producer(생산자 프로세스)
- 공유 버퍼에 데이터를 하나 생산하여 집어넣는 프로세스
- 주황색으로 표시된 것들이 데이터가 들어있는 것
Consumer(소비자 프로세스)
- 색칠되어있지 않은 버퍼는 비어있는 버퍼를 의미
- 공유 버퍼에서 데이터를 하나 가져가는 프로세스

그렇다면 해당 문제는 동기화와 관련해서 어떤 문제가 발생할까?

공유 버퍼이기 때문에 생산자가 동시에 도착하여 한 곳의 비어있는 버퍼에 동시에 데이터를 만들어 저장
- 해결 방법 : 공유 버퍼에 락을 걸어서 다른 프로세스의 접근을 막고, 집어넣는 과정이 끝나면 락을 푼다
소비자도 마찬가지로 동시에 도착하여 한 곳의 버퍼에서 데이터를 꺼내갈 때
만약 생산자들이 한꺼번에 도착해서 공유 버퍼를 가득 채운 뒤, 또 생산자가 오면 어떡할까?
- 생산자 입장에서는 사용할 수 있는 자원이 없는 상태이다. 즉, 생산자 입장에서는 비어있는 버퍼가 자원이기 때문에 소비자가 와서 버퍼를 비워줄 때까지 기다려야 한다
만약 소비자들이 도착했는데 모든 버퍼가 비어있다면 어떡할까?
- 마찬가지로 소비자 입장에서도 사용할 수 있는 자원이 없는 상태이다. 즉, 소비자 입장에서는 데이터가 들어있는 버퍼가 자원이기 때문에 생산자가 버퍼를 채워줄 때까지 기다려야 한다

세마포어가 하는 일

둘이 동시에 공유 버퍼에 대한 접근을 막기 위해서 사용(락을 건다)
버퍼가 가득 차거나 비어있을 때, 생산자, 소비자 프로세스를 위한 자원을 카운팅 하는 세마포어가 필요
- Consumer 5번 과정이 끝나고 나면 혹시 생산자 프로세스가 버퍼를 채우기 위해 기다리고 있는지 확인하고 깨워주는 역할까지 한다.

생산자 입장

버퍼에 빈 곳이 있는지 확인
empty == 0 일 경우엔 빈 버퍼가 없는 뜻이므로 기다려야 함
버퍼가 비어있을 경우에 버퍼에 P 연산을 통해 락을 걸고 데이터를 집어넣고 V연산을 통해 락을 푼다
마지막으로 데이터가 들어있는 버퍼의 개수를 1 증가시키는 연산(V)을 함
- 이때, V(full)은 소비자 입장의 자원을 하나 증가시켜주는 의미로 소비자 프로세스 중에 혹시 채워진 버퍼가 없어서 기다리고 있다면 그 프로세스를 깨워주는 역할까지 하게 된다.

소비자 입장

P를 통해 버퍼에 데이터가 들어있는지 확인
버퍼가 있다면 버퍼 전체에 락을 걸고 데이터를 꺼낸 뒤에 락을 푼다
비어있는 버퍼의 개수를 1 증가시킨다.
- 이 때, V(empty)은 생산자 입장의 자원을 하나 증가시켜주는 것으로, 생산자 프로세스 중에 빈 버퍼가 없어 데이터를 넣지 못하는 프로세스를 깨워주는 작업 수행

2. Readers and Writers Problem

write는 동시에 여럿이 하면 안 되지만 read 하는 직업은 동시에 해도 아무런 문제가 생기지 않는다.
쉽게 구현을 하려면 reader, writer 구분 없이 공유 데이터에 접근하려 할 때, 무조건 락을 걸고 빠져나올 때 락을 풀면 된다.
read는 동시에 해도 되는데 굳이 락을 걸게 되면 비효율적

프로세스의 종류 및 공유 데이터

//공유 데이터
int readcount = 0;
DB

Synchronization variables
semaphore mutex = 1, db = 1;

Writer
        P(db);
        writing DB;
        V(db);

Reader
        P(mutex);
        readcount++;
        if(readcount == 1) P(db);
        V(mutex);

        reading DB;

        P(mutex);
        readcount--;
        if(readcount == 0) V(db);
        V(mutex);

읽는 프로세스
쓰는 프로세스
공유 데이터
- 공유 데이터 명을 DB라고 한다. 해당 문제는 DB에서 주로 발생하는 문제
- readcount라는 변수는 읽는 사람의 수를 의미
세마포어 변수
- DB에 접근하기 위한 세마포어 변수인 db
- readcount에 접근하기 위한 세마포어 변수인 mutex

과정

writer
- writer는 공유 데이터에 한 프로세스만 접근할 수 있기 때문에 DB에 접근할 때 락을 걸고 나올 때 락을 푼다.
reader
- writer와 다르게 코드가 복잡함 -> 여러 "읽는" 프로세스가 동시에 접근할 수 있기 때문에 락을 걸어버리면 다른 읽는 프로세스가 기다려야 하므로 매우 비효율적
- 최초 reader일 경우 readcount 1 증가시키고, db에 락을 건다
- 최초 reader가 아닐 경우 readcount 1 증가시켰을 때 db에 락을 걸 필요가 없어진다.
  - readcount를 1 증가시킬 때 또한 락을 걸어줘야 한다. 왜냐하면 readcount도 공유 변수이기 때문에 여러 reader가 동시에 와서 readcount를 증가시킬 수 있기 때문이다
  - mutex라는 세마포 변수를 사용하여 readcount에 접근하는 것을 제어한다.
- reader가 다 읽고 나면 다시 mutex를 이용하여 락을 걸고 readcount 1 감소시킨 뒤에 mutex 락을 푼다.
- 이때 마지막 reader라면 db에 건 락을 풀어줘야 한다.

문제점

해당 방법은 writer가 starvation 상태에 놓일 수 있게 된다.
- 예를 들어 reader가 끊임없이 계속 온다면 writer의 순서는 뒤로 밀리게 되고 모든 reader가 데이터에서 다 나올 때까지 기다려야 한다.
- 그렇다고 순차적으로 처리하면 매우 비효율적이다.
  - 동시에 읽을 수 있는 reader가 있음에도 불구하고 writer가 있어서 나중에 읽어야 하기 때문이다.

해결 방법

큐에 우선순위를 두어 writer에게 일정 우선순위를 주어 너무 기다리지 않게 한다.

3. Dining-Philosophers Problem(식사하는 철학자)

5명의 철학자가 하는 일은 두 가지가 있다.

"생각하는 일", "밥 먹는 일"

Synchronization variables
semaphore chopstick[5];

do{
    P(chopstick[i]);
    P(chopstick[(i+1)%5]);
    
    eat();

    V(chopstick[i]);
    V(chopstick[(i+1)%5]);
    
    think();
} while(1)

조건 및 과정

5명의 철학자는 각각 생각, 밥 먹는 일의 주기가 다르다.
생각하려면 젓가락을 모두 놓는다.
철학자가 밥을 먹기 위해서는 "양쪽의 젓가락을 모두 집어야 한다."
- i가 왼쪽 젓가락, i+1이 오른쪽 젓가락을 의미
- 옆에 있는 철학자가 이미 밥을 먹고 있다(젓가락을 들고 있다) 면 나는 밥을 먹지 못한다.
젓가락은 "공유 자원", 초기값은 1
- 이 의미는 동시에 둘이 잡을 수 없고, 혼자서만 집을 수 있다.

문제점

deadlock 가능성
- 모든 철학자가 동시에 배가 고파져 왼쪽 젓가락을 집어버린 경우
  - 코드를 보면 왼쪽 젓가락부터 드는 것을 알 수 있음
  - 철학자들은 밥을 먹을 수 있을 때까지 젓가락을 놓지 않는다
- 결국 모든 철학자들이 오른쪽 젓가락을 들 수 없어서 deadlock이 걸린다.
- 잘못된 코드임

해결 방안

젓가락을 두 개 모두 집을 수 있을 때에만 젓가락을 집을 수 있게 한다.

해당 코드는 세마포어의 원리에 맞게 잘 짜인 코드가 아니기 때문에 이해하기 어려울 수 있다.

동작원리만 잘 파악해보자!!

변수 설명

self
- 각각의 철학자가 양쪽 젓가락을 잡을 수 있어서 젓가락을 잡을 수 있는 "권한"을 결정하는 세마포어
- self[1] = 0 의미는 2번 철학자가 지금 젓가락 두 개를 들 수 있는 권한이 없다는 뜻
state
- 철학자의 상태를 나타내는 state
- 생각, 배고픔, 먹는 상태가 있다.
mutex
- state라는 변수는 내가 혼자만 바꿀 수 있는 것이 아니라 옆의 철학자가 젓가락을 내려놓음으로써 나의 "상태"를 "변화"시킬 수 있다.
- 여러 철학자가 동시에 state를 바꿀 수 있기 때문에 state 또한 공유 데이터
- 공유 데이터에 대한 "동시 접근"을 막기 위해 mutex를 사용한다

과정

pickup(젓가락을 잡는 함수)
- 철학자 i는 state에 접근하기 때문에 락을 건다. state를 hungry로 바꾼다.
- 철학자 i가 젓가락 두 개를 모두 잡을 수 있는 상태인지 test 한다
test(젓가락 두 개를 모두 잡을 수 있는지 체크)
- 양쪽 젓가락을 집을 수 있는 권한은 양쪽 철학자가 밥을 먹지 않고 있고 AND 배고픈 상태
- 만족한다면 상태를 먹는 것으로 바꾸고, 젓가락을 들 수 있는 권한을 준다
  - 헷갈리는 점
    - 세마포어는 원래 자원의 개수를 초기값으로 1 이상인 값을 주는데, 이번 세마포어 값은 처음부터 0을 놓고 시작한다.
    - 이 말은 test 하는 단계에서 V연산을 통해 0을 1로 바꾸는데, 이것이 즉, 젓가락을 두 개 집을 수 있는 "권한"을 주는 것이다.
- 권한을 얻지 못하면 test가 함수가 끝난다.
  - 이때 P연산을 하더라도 젓가락 집을 수 있는 권한이 없기 때문에 self [i] = 1이 될 때까지 기다린다.
  - self [i]는 인접한 철학자가 밥을 다 먹고 나서 젓가락을 내려놨을 때 바꿔줄 수 있다.
putdown(젓가락을 내려놓는 함수)
- 밥을 다 먹고 젓가락을 내려놓을 때, 생각하는 상태로 바뀌게 되고, 인접한 철학자를 test 해준다
  - 현재 밥을 다 먹은 철학자 때문에 젓가락을 들지 못한 철학자가 있을 수 있기 때문이다

Reference

출처 :
- ABRAHAM SILBERSCHATZ ET AL., OPERATING SYSTEM CONCEPTS, NINTH EDITION, WILEY, 2013
- 반효경, 운영체제와 정보기술의 원리, 이화여자대학교 출판부, 2008

프로세스 동기화

https://core.ewha.ac.kr/publicview/C0101020140401134252676046?vmode=f

https://core.ewha.ac.kr/publicview/C0101020140404144354492628?vmode=f

https://core.ewha.ac.kr/publicview/C0101020140404151340260748?vmode=f

https://core.ewha.ac.kr/publicview/C0101020140408134626290222?vmode=f

https://core.ewha.ac.kr/publicview/C0101020140411143154161543?vmode=f

728x90

저작자표시 비영리 변경금지

'Operating System' 카테고리의 다른 글

cpu, core, processor, multicore, multiprocessor (0)	2022.06.13
파일 시스템 (0)	2022.05.11
데드락(2022.04.03 수정) (0)	2022.03.27
메모리 관리(2022.04.09 수정) (0)	2022.01.23
CPU 스케줄링(2022.03.13 수정) (0)	2022.01.16

경쟁 상태(Race Condition)

경쟁 상태 가능성

OS에서 경쟁 상태는 언제 발생할까?

kernel 수행 중 인터럽트 발생 시

결론

해결 방법

Process가 System call 하여 커널 모드로 수행 중인데, context switch가 일어나는 경우

해결 방법

멀티 프로세서에서의 환경 ( CPU가 여러 개 있는 환경 )

공유 데이터에 접근하는 작업이 진행되는 동안에 인터럽트를 disable 시키는 방법

이러한 문제가 생기는 근본적인 이유

정리

경쟁 상태의 예

크리티컬 섹션

Critical Section(임계 구역)

임계 구역 문제 해결

임계 구역 문제를 해결하기 위한 알고리즘

동기화 변수인 turn을 사용

flag 사용

피터슨 알고리즘

Synchronization Hardware

Memory Barriers

Test_and_Set

Semaphores

연산 종류

P연산(wait)

V연산(signal)

Counting 세마포어 & Binary 세마포어(=mutex)

임계 구역 문제에서의 세마포어 적용

Block / Wakeup 방식

busy-waiting과 block & wakeup 차이

둘 중 어느 것을 사용하는 것이 좋을까?(스핀락 or block & wake-up)

모니터

세마포어와 모니터 "목적에 따른 차이"

모니터 정리

세마포어를 사용하면서 발생되는 Deadlock & Starvation

Synchronization와 관련된 Classic 한 3가지 문제점

Reference

'Operating System' 카테고리의 다른 글

검색 태그

티스토리툴바