Process Synchronization (Concurrency Control)

뚝딱이·2023년 10월 30일

목록 보기

9/15

컴퓨터 시스템안에서 데이터가 접근되는 패턴에 대해 알아보자. 컴퓨터 시스템안에 어떤 위치에 있던간에 데이터를 접근하는 것은 아래와 같은 경로를 통한다.

저장되어 있는 data 를 가져와 연산하고 원래 있던 자리에 저장

data가 저장되어 있는 위치를 추상적으로 Storage - Box, 연산을 수행하는 위치를 Execution - Box라 하자.

이러한 방식에서는 누가 먼저 읽어갔느냐에 따라 결과 값이 달라질 수 있다. 따라서 이를 해결할 수 있는 방법에 대해 소개한다.

위와 같이 Storage - Box(Memory address space)를 왼쪽의 box(CPU Process)만 가지고 있는다면 아무런 문제가 없다. 하지만 오른쪽의 Box와 Storage-Box를 공유하기 때문에 문제가 생긴다.

왼쪽 박스가 Storage에 있는 data를 가져가 연산하는 동안 오른쪽 박스가 Storage에 있는 해당 data를 가져가 연산한다면 최종적으로 저장되는 것은 count--를 한 결과일 것이다. 따라서 여러 주체가 하나의 데이터를 동시에 접속하려고 할 때를 Race Condition이라고 한다.

이런 문제가 과연 컴퓨터 시스템에서 많이 생기는가 ?
여러군데에서 발생할 수 있다. 연산 주체를 CPU라고 하고 저장되어있는 곳을 Memory라 할 수 있다. 연산 주체를 컴퓨터 내부라 가정하면 저장되는 곳은 I/O 장치, 즉 하드 디스크라고 할 수 있다. 연산 주체를 프로세스라 가정하면 저장되는 곳을 해당 프로세스의 주소 공간이라고 할 수 있다.

CPU가 하나밖에 없는 시스템에서는 이러한 문제가 발생하지 않을 것 같음
프로세스가 여럿이서 각자의 주소 공간만 접근 -> 문제 발생 없을 것 같음

CPU 여러개 -> 메모리 공유 -> 문제가 생길 수 있음

또 프로세스는 자기자신만의 주소공간을 접근할 수 있지만, 공유 메모리를 사용할 수도 있다. 따라서 이러한 상황에서 문제가 생길 수 있는 것이다. 더 중요한 문제는 커널과 관련된 문제들이다.
프로세스는 일반적인 경우라면 자기 주소공간만 접근하기 때문에 이러한 문제가 발생할 일이 없다. 프로세스들이 본인이 직접실행할 수 없는 부분, 운영체제가 대신해줘야 하는 부분은 운영체제에게 부탁을 한다. 따라서 시스템콜을 하므로 커널의 코드가 그 프로세스를 대신해서 실행이 된다. 커널의 코드가 실행된다는 것은 커널의 data가 변경된다는 것이다. 그래서 커널의 코드가 실행되고 있을 때 다른 프로세스가 운영체제를 호출하면 커널의 변경전 data를 건드릴 수 있는 것이다.

예) 커널모드 수행 중 인터럽트로 커널모드 다른 루틴 수행시

OS 에서 race condition은 언제 발생하는가?

kernel 수행 중 인터럽트 발생시

커널이 CPU에서 실행중 -> Count++ (고급언어로 된 문장은 CPU내에서 여러개의 instruction을 통해 행해짐 -> data를 load -> 연산 -> data store) -> Count++ 중에 interrupt -> Count++ 멈춤 -> interrupt 처리 루틴 실행 -> interrupt handler(커널에 있는 코드) 실행 -> Count--(커널에 있는 코드) -> interrupt 처리 끝 -> Count++로 돌아옴 -> 원래 값하고 같아야 하는데 기존에 있던 커널이 load후에 멈추고 interrupt 처리 후에 연산을 진행했기 때문에 Count--는 무시됨

커널모드 running중 interrupt가 발생해 인터럽트 처리 루틴이 수행 -> 양쪽 다 커널 코드이므로 kernel address space 공유

어떻게 해결하느냐 ? 커널 수행중이라면 interrupt가 걸려도 interrupt 처리 루틴으로 바로 넘기는게 아니라 본래 하던 작업을 다하고 (interrupt를 disable) interrupt 처리

결국엔 순서를 정해주면 되는 것이다. 누군가 어떤일을 수행할 때 다른 사람이 수행하지 않고 기다릴 수 있도록 하면되는 것. 하지만 순서를 잘못정하면 오래기다려야 할수도 있고 이는 곧 성능에 영향을 끼치기 때문에 이를 잘 정해야한다.

Process가 system call을 해 kernel mode로 수행중인데 context switch가 일어나는 경우

어떤 프로세스가 실행 -> 본인의 코드만 실행 and 운영체제에게 부탁
프로세스에겐 할당 시간이 있고 할당시간을 넘길 경우 CPU는 다른 프로세스에게 넘어간다. 따라서 아래와 같이 PA가 사용하다가 PB가 CPU를 받아 실행할 때 PA 와 같은 data를 건드린다면 문제가 생기는 것이다.

해결책 : 커널 모드에서 수행중일 때는 CPU를 preempt하지 않음, 커널 모드에서 사용자 모드로 돌아갈 때 preempt => 즉 작업이 완료 될 때 까지 CPU를 뺏지 않으면 된다. 할당시간이 끝나도 CPU를 뺏기지 않도록 !
그렇다면 할당시간이 늘어날 순 있다. 하지만 이는 real time 시스템이 아니기 때문에 이러한 것을 통해 복잡한 문제를 쉽게 해결할 수 있다.

Multiprocessor에서 shared memory내의 kernel data

자주 등장하는 경우는 아니다.
앞에서의 해결책들로는 해결이 안된다.

작업 진행 중 interrupt disable -> 다른 CPU에는 상관없기 때문에 해결 못한다.

데이터를 접근할 때 lock을 걸어야한다. 오른쪽 CPU가 data를 들고가 수정할 때 해당 data에 lock을 걸어 다른 사람들이 접근하지 못하도록 한다. 연산이 끝난 후 lock을 풀어 다른 CPU가 접근할 수 있도록 한다.

이러한 개별 변수에 대해 lock을 걸었다 풀 수 있고 좀 더 쉬운 방법은, 이러한 문제가 생기는 것은 사용자 프로그램이 아닌 커널을 통한 실행 때문이므로 한번에 하나의 CPU만이 커널에 들어갈 수 있게 하는 것이다.

커널 전체를 하나의 lock으로 막고 커널을 나올 때 lock을 풀어주는 방법이다. 이 방법을 쓰면 CPU가 여럿있더라도 커널에 접근하는 것은 CPU 하나이다. 하지만 굉장히 비효율적이므로 해당 데이터만 lock을 거는 것이 좋다.
그래서 lock이 걸린 data가 아니라면 접근할 수 있도록 한다.

Process Synchronization 문제

공유 데이터의 동시 접근은 데이터의 불일치 문제를 발생시킬 수 있다.
일관성 유지를 위해서는 협력 프로세스간의 실행 순서를 정해주는 메커니즘이 필요하다.

Race condition

여러 프로세스들이 동시에 공유데이터를 접근하는 상황
데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 달라짐

race condition을 막기 위해서는 concurrent process는 동기화 돼야한다.

사용자 프로세스 P1 수행 중 timer interrupt가 발생해 context switch가 일어나 P2가 CPU를 잡으면?
보통 공유데이터를 사용하지 않으면 문제가 생기지 않는다. 하지만 커널의 데이터를 건드리거나 공유 데이터를 사용하는 도중 CPU를 뺏긴다면 원하는 결과가 나오지 않고 일관성이 깨진 불일치 문제가 생길 수 있다는 것이다.
단순히 CPU를 뺏긴다고 문제가 생기는 것은 아니다.

The Critical-Section Problem

Critical-Section : 공유 데이터를 접근하는 부분

critical section의 코드를 수행할 때 다른 모든 프로세스는 critical section에 접근하지 못해야한다. 그리고 critical section의 코드 수행이 끝나면 다른 프로세스들이 접근할 수 있도록 해야한다.

문제를 해결해보자 !

공유 데이터를 그냥 접근하게 허용한다면, 동시접근을 통해 문제가 생길 수 있다. 따라서 공유 데이터의 코드 이전에 entry section을 통해 lock을 건다.

그래서 동시에 critical section으로 접근하는 것을 막고 critical section이 끝난다면 exit section을 통해 lock을 해제해 접근을 허용한다.

해결법의 충족 조건

그렇다면 문제를 해결하는 충족 조건은 무엇이 있을까?

Mutual Exclusion (상호 배제)

프로세스 Pi가 critical section 부분을 수행 중이면 다른 모든 프로세스들은 그들의 critical section에 들어가면 안된다.

Progress

아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있으면 critical section에 들어가게 해줘야 한다.
굉장히 당연한 이야기일지도 모르나 이 조건이 만족되지 않을 수 있다. 둘이 동시에 들어가는 것을 막고자 하다보니, 아무도 없는데 둘이 동시에 들어가려고 해 막힌다면 이 조건을 충족하지 못하는 것이 된다.

Bounded Waiting (유한 대기)

프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야한다.
기다리는 시간이 유한해야 한다. 두 번째 조건과는 약간 다르다. 특정 프로세스 입장에서 critical section에 들어가지 못하고 지나치게 오래 기다리는 starvation이 생기지 않아야 된다는 것이다.

어떨 때 발생할까?

critical section에 들어가고자 하는 프로세스가 3개가 있을 때 앞의 두개만 서로 번갈아가면서 계속 사용할 때 3번째 프로세스가 starvation이 생길 수 있다.

int turn을 사용해 해결 시도

프로세스 P0, P1이 있다고 가정하자.

동기화 변수

int turn;
initially turn = 0;

Pi는 turn == i 일 때 critical section에 들어갈 수 있다. 따라서 P0, P1 각각을 위한 코드는 아래와 같다. turn은 누구의 차례인가를 나타내는 변수이다.

아래는 P0를 위한 코드다.

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

반대로 P1을 위한 코드는 아래와 같다.

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

그래서 처음에는 turn을 프로세스 0번 차례로 만들고 시작한다. 0번 프로세스가 시작되어 turn이 0이 아닌 동안엔 while문을 계속 돌면서 기다린다. 만약 turn이 0이 되면 critical section으로 들어가게 되는 것이다. critical section에서 나오고 나서 turn = 1을 통해 차례를 1번 프로세스로 바꿔주는 것이다.

따라서 본인의 차례가 아닌 경우 while문에서 기다리고, turn의 변경과 동시에 자신의 차례가 된다면 critical section에 들어간다. 후에 critical section에서 나온 뒤 다른 프로세스에게 차례를 넘겨준다.

turn을 통해서 차례가 온 프로세스만 접근하기 때문에 다른 프로세스가 동시에 접근할 수 없다. 따라서 위의 알고리즘은 Mutual Exclusion을 만족한다.

문제점

하지만 progress 를 만족하지 못한다. 코드를 보면 프로세스는 반드시 교대로 들어가도록 설계가 되어 있다. 따라서 P0이 critical section에 들어갔다가 나와야지만, 상대 차례가 된다. 또한 상대가 critical section에 들어갔다가 나와야만 P0이 들어갈 수 있다. 아무런 문제가 없어보이지만 critical section에 접근하는 빈도수의 차이가 있을 때 문제가 생긴다. P0는 critical section에 자주 접근하지만 P1은 접근 하는 빈도가 굉장히 적다면, P0은 상대적으로 많은 시간을 P1을 기다리는 데에 써야할 것이다. 왜냐하면 P0이 critical section에 들어갔다가 다시 들어가고 싶다면 P1이 들어가기를 기다려야 하기 때문이다. 최악의 경우 P0는 상대방이 turn을 바꿔주지 않아 영원히 들어가지 못할 수도 있는 것이다.

boolean flag를 사용해서 해결 시도

turn만 바꿔주는 것으로는 한계가 있음을 깨닫고 이를 개선한 알고리즘

동기화 변수

boolean flag[2];
initially flag[모두] = false; /* no one is in CS */

처음에는 critical section에 들어가고 싶은 상태가 아니므로 모두 false로 초기화
만약 flag[i] == true라면 Pi는 critical section에 들어갈 준비가 된 것이다.

Pi를 위한 코드는 아래와 같다.

do {
    flag[i] = true;   /* Pretend I am in */
    while(flag[j]);   /* Is he also in? then wait */
    critical section
    flag[i] = false;  /* I am out now */
    remainder section
} while (1);

본인이 critical section에 들어가고 싶다면 본인의 flag를 true로 변경한다.
그리고 critical section에 들어가고 싶은 상대방이 있는지 상대방의 flag를 확인한다. 만약 flag[j]가 true라면 들어가고 싶어하는 사람이 있는 것이므로 while문을 돌면서 대기한다. 만약 상대방이 flag를 세팅하지 않았다면 critical section에 들어가고 나올 때 본인의 flag를 false로 바꿔 만약 기다리고 있는 상대방이 있다면 접근을 허용해준다.

문제점

일단 Pi가 본인의 flag, 즉 flag[i]를 true로 설정한 다음 CPU를 뺏겨 Pj에게 CPU가 갔다고 가정해보자. 이때 Pj도 critical section에 들어가고 싶어서 flag[j]를 true로 설정한다. 그리고 상대방의 flag를 확인해야 하므로 while문을 살펴보는데 flag[i]가 true이다. 따라서 Pj는 계속 while문에서 대기해야하고 Pj의 flag 또한 true이므로 CPU가 Pi로 다시 넘어간다고 하더라도 Pi또한 while문을 넘지 못하고 계속 대기해야하는 상황이 생긴다. 따라서 Mutual exclusion은 만족하지만 아무도 들어가지 못하는 상황이 생겨 progress는 만족하지 못한다.

Petersons's Algorithm

순서를 변경해주는 turn과 critical section에 들어가고 싶은 의사표현을 나타내는 flag를 모두 사용한다.

do {
    flag[i] = true;                 /* My intention is to enter ...*/
    turn = j;                       /* Set to his turn */
    while (flag[j] && turn == j);   /* wait only if .. */
    critical section
    flag[i] = false;
    remainder section
} while(1);

따라서 critical section에 들어가고 싶다면 flag를 true로 바꿔 들어가고 싶다는 의사표현을 하고 turn을 상대방으로 바꿔 놓는다. 즉, Pi가 지금 critical section으로 들어가고 싶다면 flag[i] = true로 의사표현을 하고 turn = j를 통해 차례를 바꾼다는 것이다. 그리고 critical section으로 들어가기 전에 체크한다. 상대방이 들어가고 싶고, 상대방의 차례인지 확인하는 것이다. 둘 모두를 만족하면 프로세스는 대기한다.

그래서 이 방법은 모든 경우의 수를 다 따져 중간 어디에서 CPU를 뺏긴다고 하더라도 조건을 모두 충족한다.

둘 다 critical section에 들어가고 싶은 경우에만 turn을 통해 차례를 보고 결정하고 그렇지 않다면 turn에 관계 없이 들어갈 수 있는 것이다.

하지만 이 코드도 Busy waiting이라는 문제점이 있다. Busy waiting을 다른 말로는 spin lock이라는 표현도 사용한다. 만약에 P0이 critical section에 들어가 있는 상태에서 CPU를 뺐겨 P1이 CPU를 받고 critical section에 들어가려 한다면, while문을 계속 돌아야 할 것이다. 하지만 이 while문은 CPU의 할당시간이 끝나기 전까지 바뀔리가 없다. 즉, 변할 일이 없음이 자명한데도 계속 CPU와 memory를 사용하면서 이를 체크하는 것이다. 이를 Busy waiting이라고 하며 비효율적인 방법이라 할 수 있다.

그냥 Lock을 걸고 나올 때 풀면 되는건데, 코드가 복잡하고 길어진 이유는 고급언어의 문장 하나가 여러 instruction으로 구성되고 문장 하나하나가 실행되는 도중 CPU가 뺏길 수 있기 때문이다.

Synchronization Hardware

사실은 하드웨어적으로 하나의 instruction만 주어지면 이를 해결할 수 있다.
이 instruction이 Test_and_set이다. 문제가 생겼던 이유는 어떤 데이터를 읽는 것과 쓰는 것을 하나의 instruction으로 처리할 수 없기 때문이다. 따라서 데이터를 읽고 쓰는 것이 하나의 instruction이 실행될 때 동시에 이루어진다면 CPU가 뺏긴다고 해서 문제가 생기지 않는다. 왜냐하면 CPU는 하나의 instruction이 끝나고 나서 interrupt를 확인하기 때문이다.

따라서 하드웨어적인 지원이 가능해진다면 간단하게 lock을 거는 문제를 해결할 수 있다.

만약 a라는 데이터가 0이었다면 1에서 0이 읽히고 a의 값이 1로 바뀌게 되는 것이다. 반대로 a이 값이 1이었다면 읽었을 때 1이 읽히고 이를 1로 다시 세팅하는 것이다.

Test & Set의 코드를 살펴보면 다음과 같다.

boolean test and set(boolean *target) { 
    boolean rv = *target;
    *target = true;
    
    return rv;
}

target을 lock이라고 생각해보자. 만약 내가 critical section에 들어가기 위해 lock에 true를 넣으면 내가 lock을 걸기전의 lock이 반환되는 것을 볼 수 있다. 따라서 반환되는 값(이전의 lock)에 따라 대기 여부를 결정할 수 있다.

따라서 이게 지원된다면 소프트웨적으로 코드를 복잡하게 짤 필요없이 아래와 같이 간단하게 코드를 작성할 수 있다.

do {
    while (test and set(&lock)); /* do nothing */
    critical section
    lock = false;
    remainder section
} while (true);

위의 코드를 보면 단순하게 test and set을 통해서 lock을 걸고 이전에 lock이 걸려있지 않았다면 critical section을 거친다음 lock을 해제하고 lock이 걸려있었다면 대기하는 것을 확인할 수 있다.

만약 lock이 0이었다면 lock이 걸려있지 않은 것이다 -> 내가 lock을 걸고 들어가면 됨
만약 lock이 1이었다면 읽히는 값이 1이므로 lock이 걸려있던 것이다. -> 대기 -> 누군가가 critical section을 지나 lock을 0으로 바꿔줌 -> 대기 하던 프로세스가 들어갈 수 있다.

하드웨어적으로 값을 읽는 것과 쓰는 것을 atomic하게 수행할 수 있다면 lock을 걸고 푸는걸 간단하게 해결할 수 있다는 것이다.

Semaphores

추상 자료형 : object와 operation으로 구성되는 것이다. 정수 추상 자료형이라고 하면, 정수 숫자들이 있고 그 숫자에 대해 곱셈, 뺄셈 등의 연산이 정의된다. 이처럼 추상자료형은 논리적으로 정의를 하는 것이지 실제로 컴퓨터에서 자료형이 어떻게 구현되는 것과는 별개이다.

Semaphore도 추상 자료형의 일종이다.

Semaphore s가 있으면 정수값(자원의 개수)을 가질 수 있고, 변수에 대해 정의되는 operation이 필요하다.

왜 사용하는가 ?
lock을 걸고 풀고를 간단하게 프로그래머에게 제공할 수 있다. 공유자원을 획득하고 반납하는 것을 세마포어가 처리해주는 것이다.

Semaphore의 operation

정수값인 s는 자원의 개수를 나타낸다. 따라서 s가 5라면 다섯개의 프로세스가 자원을 할당받아 가져갈 수 있다. 그래서 s가 5일 때 wait가 한번 호출되면 프로세스가 공유 데이터를 하나 획득해 자원이 4개 남는 것이다.
따라서 wait 연산을 총 5번 실행할 수 있다.

wait(S)

공유 데이터를 획득하는 과정 => lock을 거는 과정

wait(S) {
    while (S <= 0); // busy wait
    S--;
}

S값이 양수가 되면 자원을 획득할 수 있다. 즉, 누군가가 자원을 반납해서 자원이 남아있는 경우 획득 가능하다.
하지만 계속 대기를 해야하는 상황이 생기므로 이 역시 Busy waiting이다.

signal(S)

공유 데이터를 반납하는 과정 => lock을 푸는 과정

signal(S) { 
    S++;
}

자원의 개수가 4개인 상태에서 signal을 수행하면 5개로 늘어난다.

P0이 statement S0을 실행, P1이 statement S1을 실행한다면 아래와 같은 흐름일 것이다.

S1; 
signal(synch);
wait(synch); 
S2;

동기화 변수
semaphore mutex;

Pi에 대해 아래와 같이 프로그래밍 할 수 있다.

do {
    wait(mutex);  /* 양수라면 공유 데이터를 획득 밑 -- 연산, 음수일 경우 대기 */
    critical section
    signal(mutex); /* ++연산 */
    remainder section
} while (1);

문제는 Busy waiting이다. 그래서 우리는 block&wakeup 방식으로 구현할 수 있으며 이는 sleep lock이라고 부를 수 있다.

Block & Wakeup Implementation

우리는 프로세스가 CPU를 획득하고 뺏는 과정에 대해서 앞에서 공부했다. 특정 프로세스가 CPU를 점유해 일을 하다가 오래걸리는 I/O 작업이 들어올 경우 CPU를 내려놓고 잠깐 blocked 상태가 되어 CPU를 얻을 수 있는 권한 자체가 없어진다. 그리고 I/O 작업이 끝나면 Ready로 돌아올 수 있는 것이다.

마찬가지로 특정 프로세스가 공유 데이터를 쓰고 있으면 해당 데이터를 다 사용할 때 까지 다른 프로세스들은 접근하지 못한다. 따라서 while문을 통해 기다리고 있는 것이 아니라 프로세스 자체를 blocked 시켜 CPU를 반납시키고 잠들어 있다가 공유 데이터에 접근할 수 있게 될 때 blocked에서 깨어나 CPU를 받아 공유데이터에 접근하는 것이다.

세마포어를 다음과 같이 정의하자

typedef struct
{ 
    int value;
    struct process *list; 
} semaphore;

여기서 value는 semaphore를 나타내고 list는 프로세스가 대기하는 queue이다.

그래서 만약 지금 데이터를 획득할 수 없다면 block 시키고, 획득하게 되면 block된 프로세스를 깨워 ready queue로 옮기는 것이다.

block
- 커널은 block을 호출한 프로세스를 suspend 시킨다.
- 이 프로세스의 PCB를 semaphore에 대한 wait queue에 넣는다.
wakeup(P)
- block된 프로세스 P를 wakeup 시킨다.
- 이 프로세스의 PCB를 ready queue로 옮긴다.

wait()

s--를 했을 때 음수라면 => 자원이 없다면 => 프로세스를 S.list에 프로세스를 연결시켜 blocked 시키는 것이다.
여기서 주의할 점은 자원이 있든 없든 일단 S.value--를 하는 것이다. 따라서 value가 0미만이라면 지금 blocked되어 있는 프로세스가 존재함을 의미한다. 따라서 위에서 S가 자원의 개수를 의미해 연산을 하던 것과는 의미가 다르다.

wait(semaphore *S) { 
    S->value--;
        if (S->value < 0) {
            add this process to S->list;
            sleep(); /* block */
        }
}

signal()

자원을 반납하고 끝나는게 아닌 자원을 기다리고 있는 프로세스가 있다면 깨워주고 끝난다.
자원을 반납했는데(value++)도 0 이하라면 대기하고 있는 프로세스가 있다는 것을 의미한다.


signal(semaphore *S) { 
    S->value++;
        if (S->value <= 0) {
            remove a process P from S->list; 
            wakeup(P);
        }
}

Busy-wait vs Block&WakeUp

보통은 Block&WakeUp을 쓰는게 더 효율적이다. 의미있게 CPU를 이용하는 비율이 높아지기 때문이다. 하지만 Block&WakeUp도 ready queue로 왔다갔다 하는 등의 오버헤드가 있다.

critical section의 길이가 긴 경우 => Block&Wakeup
critical section의 길이가 매우 짧은 경우 => Block&WakeUp의 오버헤드가 Busy-wait 오버헤드보다 더 커질 수 있다.

Two Types of Semaphores

Counting semaphore

도메인이 0이상인 임의의 정수값이다.
주로 resource counting에 사용된다.
자원의 개수가 여러개 있어서 여분이 있으면 가져다 쓸 수 있는 경우이다.

Binary semaphore (=mutex)

자원이 하나인 경우 => 0 또는 1 값만 가질 수 있다.
주로 mutual exclusion (lock/unlock)에 사용된다.

주의점

Deadlock

We say that a set of processes is in a deadlocked state when every process in the set is waiting for an event that can be caused only by another process in the set.

내가 어떤일을 하기 위해 S와 Q를 둘 다 획득해야하는 경우이다. 예를 들어 하드디스크 A에 있는 것을 하드디스크 B로 복사하고 싶을 땐 A와 B에 있는 것을 획득하고 나서 A에서 읽고 B에 쓰는 경우가 있다. 그래서 이러한 작업을 P0,P1이 실행하고 S와 Q가 1로 초기화된 semaphore라고 가정해보자. 즉, 1로 초기화된 semaphore이므로 한번에 한 process만 작업 할 수 있다.

P0가 CPU를 먼저 얻어서 S라는 semaphore를 먼저 획득하고 P1에게 CPU에게 뺏겼다. 이때 P1이 Q라는 semaphore를 획득했다. 그리고 나서 S를 획득하려고 했더니 이미 P0가 획득했기 때문에 P1은 기다려야 한다. 이때, 언제까지 기다려야 하는가 ? 영원히 기다려야 한다. 왜냐하면 P0가 S를 놓아줄 때 까지 기다려야 하는데 P0이 S를 놓아주려면 Q를 획득해야하기 때문이다.

따라서 두 프로세스가 자원을 하나씩 가지고 서로 원하는 것을 쥐고 주지 않아 영원히 기다려야 하는 이러한 상황을 데드락이라고 한다.

이는 자원을 얻는 순서를 바꾼다면 해결될 수 있는 문제이다. P1이 P0처럼 S다음 Q를 획득하면 된다.

Starvation

특정 프로세스가 영원히 자원을 얻지 못하고 무한히 기다려야 하는 상황을 starvation이라고 한다. 위의 dead lock 또한 starvation이라고 할 수도 있다.

여기서 이야기 하는 starvation은 특정 프로세스끼리 자원을 공유하면서 다른 프로세스는 영원히 자신의 차례가 오지 못하도록 하는 것을 말한다.

젓가락이 하나씩만 놓여 양쪽에 있는 젓가락을 모두 획득해야만 식사를 할 수 있는 식탁이 있다고 가정하자. 이때 양쪽에 있는 사람이 번갈아 가면서 자신의 양쪽 젓가락을 이용해 식사를 한다면 중간에 있는 사람은 밥을 영원히 먹지 못한다.

여기선 dead lock도 생길 수 있다. 모든 사람이 왼쪽 젓가락을 잡는다고 생각해보자. 그럼 모든 사람이 오른쪽 젓가락을 잡을 때 잡지 못해 영원히 식사하지 못한다.

Classical Problems of Synchronization

Bounded-Buffer Problem

Producer-Consumer Problem이라고도 한다.
임시로 데이터를 저장하는 공간 -> buffer

circular buffer로 유한한 버퍼 환경이 있다고 가정해보자.
프로세스가 두가지 종류가 있다. Producer와 Consumer이다. Producer와 Consumer 각각은 하나씩 있는 것이 아닌 여러개가 있다. Producer는 공유 버퍼에 데이터를 하나 만들어서 집어넣는 역할을한다. 주황색 버퍼 => 데이터가 들어있는 버퍼 / 회색 버퍼 => 비어있는 버퍼

따라서 주황색 버퍼는 producer가 데이터를 넣어놓은 버퍼이다. 회색 버퍼는 데이터는 넣지 않았거나 consumer가 꺼내간 버퍼이다. 여기서 동기화와 관련된 문제는 어떤게 있을까?

한가지 문제는 공유 버퍼이므로 생산자가 둘이 동시에 도착해서 비어있는 한 버퍼에 동시에 데이터를 넣으려고 할 때이다. 그래서 생산자가 비어있는 버퍼를 확인하고 집어넣는 작업을 그냥 하는게 아닌 공유 데이터에 lock을 걸어 다른 프로세스의 접근을 막고 난뒤에 데이터를 넣고 lock을 풀어 다른 프로세스들이 접근할 수 있도록 해야한다. 소비자도 마찬가지이다. 소비자 둘도 동시에 꺼내려고 하면 문제가 생기므로 lock을 통해 해결해야한다.

또다른 문제는 버퍼가 유한하기 때문에 생기는 문제다.
만약에 생산자들이 한꺼번에 도착해서 공유 버퍼를 가득채운 상황에서 소비자가 와서 데이터를 꺼내가면 좋은데, 이게 아니라 생산자가 또 도착해서 데이터를 집어넣어야 하는 상황에선 어떻게 해야할까?
생산자 입장에서는 사용할 수 있는 자원이 없는 상태로 볼 수 있다. 세마포어가 자원의 개수를 카운트하는데에도 사용될 수 있다고 공부했다. 그래서 생산자 입장에서 비어있는 버퍼를 자원으로써 카운트해 관리하면 된다. 비어있는 버퍼가 없으면 소비자가 데이터를 꺼내가 비어있는 버퍼가 생길 때 까지 대기한다.

반면에 소비자 입장에서는 모든 버퍼가 비어있을 때 문제가 된다. 데이터를 꺼내가야 하는데 꺼내갈 데이터가 없기 때문이다. 따라서 소비자 입장에서의 자원은 채워져 있는 버퍼이다. 채워져있는 버퍼가 없으면 대기해야한다.

해야할 일

semaphore

둘이 동시에 공유 버퍼에 접근하는 것을 막기 위해 공유 버퍼 전체에 lock을 걸어 혼자 공유 버퍼에 접근한 뒤 lock을 푸는 것

버퍼가 가득 차거나 비었을 때, 가용자원의 개수를 세는 역할

producer

빈 버퍼가 있는지 확인 -> 없으면 기다린다.
공유 데이터에 lock을 건다 -> 다른 프로세스의 접근을 막음
빈 버퍼에 데이터를 입력 및 조작(비어있는 버퍼의 위치 포인터를 하나 증가시킴)
lock을 풀어 다른 프로세스의 접근을 허가
full buffer(생산자의 자원) 하나 증가

consumer

차 있는 버퍼가 있는지 확인 -> 없으면 대기
공유 데이터에 lock을 건다 -> 다른 프로세스의 접근을 막음
차 있는 버퍼에서 데이터를 꺼내고 버퍼 조작
lock을 풀어 다른 프로세스의 접근을 허가
empty buffer(소비자의 자원) 하나 증가

공유 데이터

buffer 자체
buffer 조작 변수(empty/full buffer의 시작 위치)

동기화 변수들

mutual exclusion -> binary semaphore 필요
- lock을 걸고 풀기 위해
- 공유 데이터의 mutual exclusion을 위해
resource count -> integer semaphore 필요
- 남은 empty/full buffer의 수 표시
- 생산자 입장(비어있는 버퍼의 개수), 소비자 입장(내용이 들어있는 버퍼)

sudo code

semaphore 변수를 세개로 두고 있는 걸 볼 수 있다.

mutext : lock을 걸기 위함
- lock을 걸어 하나의 프로세스만 접근하게 하기 위해 1로 초기화
full : 내용이 들어있는 버퍼의 개수를 세기 위함
empty : 내용이 비어있는 버퍼의 개수를 세기 위함

producer

빈버퍼 있는지 확인
빈버퍼 획득

없으면 대기

lock을 검
버퍼에 데이터를 집어 넣음
버퍼 조작 끝
lock 품
내용이 들어있는 버퍼를 1증가

소비자 입장에서는 반대로 하면된다.

Readers-Writers Problem

프로세스의 종류로는 reader,writer가 있고 각각 여러개 있을 수 있다. 공유 데이터는 DB이다.
프로세스는 DB에서 뭔가를 읽거나, 쓰는 역할을 한다. 공유 데이터인 DB를 여러 프로세스가 접근하면 안되므로 lock을 걸어줘야한다.

writer는 동시에 작업하면 안되지만 reader는 동시에 작업해도 동기화 측면에서 아무런 문제가 없다는 것이 차이점이다. 쉽게 구현하기 위해선 reader, writer 둘 다 lock을 걸면 된다. 하지만 reader는 동기화 문제가 없기 때문에 lock을 걸면 비효율 적이다. 따라서 reader는 누군가 쓰고 있으면 접근하지 못하지만 누군가 읽기만 하고 있는 것은 접근 할 수 있다는 것이다.

이 문제를 어떻게 풀어야 하는가?

sudo code

P(db)를 통해 lock을 걸고 있다.

Reader

writer와 같이 구현해도 문제 해결은 되나 비효율적이다.
어쨌든 lock은 걸어야 하는 상황이다. writer가 읽는 도중 접근하면 안되기 때문이다. 하지만 reader는 접근이 가능해야한다.

그래서 현재 읽고 있는 reader수를 세는 readCount둬 이를 해결한다. 내가 최초의 reader라면 (아무도 읽고 있지 않은 상태라면) db에 lock을 건다. 누군가가 이미 읽고 있다면 lock을 걸 필요가 없다. 최초의 reader가 이미 lock을 걸었을 것이기 때문이다. 하지만 readCount 또한 공유 변수이기 때문에 동시에 접근하면 문제가 생긴다. 따라서 이를 바꾸기 위해 lock을 거는 것이 필요하고 P(mutex)로 이를 해결한다.

그래서 db를 읽는 작업이 끝났다면 빠져나가면 되는데, 내가 마지막 reader(마지막으로 읽고 나가는)라면 (if (readcount==0)) db에 대한 lock을 풀어 writer의 접근을 허가한다.

공유 데이터

DB 자체
readcount: 현재 DB에 접근 중인 reader 수

동기화 변수

mutext : 공유 변수 readcount를 접근하는 코드의 mutual exclusion 보장을 위해 사용
db : reader와 writer가 공유 DB 자체를 올바르게 접근하게 하는 역할

writer는 모든 reader가 나갈 때 까지 기다려야한다. 하지만 reader는 reader끼리 lock을 걸지 않으므로 꾸준히 계속 들어올 수 있다. 따라서 writer는 계속 기다려야해 starvation 문제를 야기한다.

어떻게 해결할까?

reader와 writer 순서대로 진행한다.
- 비효율성이 존재할 수 있다.
어느정도의 reader가 지나갔으면 더이상의 reader 진입을 막고 마지막 reader가 나간다면 writer에게 주는 해결법

우리 일상생활에서 신호등을 생각해보면된다. 신호등이 없다고 가정할 때 차가 끊임없이 온다면 나는 영원히 건널 수 없게 된다. 신호등이 있다면 언젠가 건널 수 있다.

Dining-Philosophers Problem

철학자 5명이 있다. 생각하는 시간이 있고, 배가 고파 식사를 하는 시간이 있다. 배가 고파 식사를 하면 생각을 멈추고, 배가 불러 식사를 멈추면 생각을 한다. 이런 것을 무한 반복하는 것이다.
하지만 밥을 먹으려면 젓가락을 두개 다 잡아야한다.

sudo code

do {
    P(chopstick[i]);
    P(chopstick[(i+1)%5]);
    ...
    eat();
    ...
    V(chopstick[i]);
    V(chopstick[(i+1)%5]);
    ...
    think();
    ...
} while (1);

chopstick[i] : 왼쪽 젓가락, chopstick[(i+1)%5] : 오른쪽 젓가락
왼쪽 젓가락을 잡고 싶은데 이미 왼쪽 사람이 해당 젓가락을 잡아 식사하고 있다면 잡지 못한다. 또한 젓가락은 한번에 한명만 접근해야하므로 다른 사람이 쓰고 있으면 기다려야하는 것이다.

이 코드는 굉장히 위험한 문제가 있다.

dead lock

모든 5명의 철학자가 동시에 배가 고파져 왼쪽에 있는 젓가락을 가져간 뒤 배가 부를 때 까지 놓지 않는다면, 오른쪽 젓가락은 아무도 잡을 수 없는 상황이 된다.

해결법

4명의 철학자만이 테이블에 동시에 앉을 수 있도록한다.
젓가락을 두 개 모두 잡을 수 있을 때에만 젓가락을 잡을 수 있게 한다.
- 두개 모두 잡을 수 없다면 젓가락을 잡을 수 있는 권한을 주지 않는 것
비대칭
- 짝수(홀수) 철학자는 왼쪽(오른쪽) 젓가락 부터 집도록한다.

semaphore DiningPhilosophers
{
    enum {THINKING, HUNGRY, EATING} state[5]; 
    semaphore self[5];
    semaphore mutex = 1;
    
    do {
        pickup(i);
        eat();
        putdown(i);
        think();
    } while(1);
    
    void pickup(int i) { 
        P(mutex);
        state[i] = HUNGRY; 
        test(i);
        V(mutex);
        P(self[i]);
    }   
    
    void putdown(int i) { 
        P(mutex);
        state[i] = THINKING; 
        test((i + 4) % 5); 
        test((i + 1) % 5);
        V(mutex);
    }
    
    void test(int i) {
        if ((state[(i + 4) % 5] != EATING) && (state[i] == HUNGRY) && (state[(i + 1) % 5] != EATING)) {
            state[i] = EATING;
            V(self[i]);
        } 
    }
}

semaphore의 원리에 잘 맞게 짜여진 코드는 아니다.

state[5] : 상태를 나타내는 공유 변수
- thinking, hungry, eating
- hungry는 코딩을 돕기 위해 추가
self[5] -> 5명의 철학자에게 젓가락 잡는 권한을 줄것인가에 대한 변수
- self[1] = 0 : 1번 철학자는 젓가락 두개를 다 잡을 권한이 없다.
- self[3] = 1 : 3번 철학자는 젓가락 두개를 다 잡을 권한이 있다.
mutex
- 철학자의 상태를 바꾸는 것은 본인만 바꿀 수 있는 것이 아니라 옆에 사람도 바꿀 수 있다.
- 따라서 철학자가 동시에 상태를 바꾸는 것을 막기 위함이다.

함수별로 살펴보자

    void pickup(int i) { 
        P(mutex);
        state[i] = HUNGRY; 
        test(i);
        V(mutex);
        P(self[i]);
    }

철학자i는 상태를 건드리므로 lock을 건다. 자신의 상태를 hungry로 변경 (젓가락을 잡을 것이기 때문에)
그 후 젓가락을 잡을 수 있는 상태인지 test해본다. 권한을 얻었다면 P(self[i]);를 통해 권한을 업그레이드 한다. 만약 test 연산에서 권한을 획득하지 못했다면 P 연산을 하더라도 계속 self연산이 1이 돼도록 기다려야 한다. 이건 그럼 누가 바꿔주느냐? 인접한 철학자가 밥을 다 먹고 조건이 충족되면 된다 !

    void test(int i) {
        if ((state[(i + 4) % 5] != EATING) && (state[i] == HUNGRY) && (state[(i + 1) % 5] != EATING)) {
            state[i] = EATING;
            V(self[i]);
        } 
    }

젓가락 두개를 다 잡을 수 있는 권한 -> 왼쪽 철학자, 오른쪽 철학자가 밥먹고 있지 않고 내가 지금 배고픈 상태일 때
보통 semaphore하면 자원의 개수를 초기값으로 한다. 즉, self[5]=1로 하는데 여기선 0으로 둔다.
따라서 권한이 있다면 권한 변수를 수정한다.

    void putdown(int i) { 
        P(mutex);
        state[i] = THINKING; 
        test((i + 4) % 5); 
        test((i + 1) % 5);
        V(mutex);
    }

밥을 다 먹고 내려놓을 땐 인접 철학자를 챙기는 것이다. 인접 철학자가 자신 때문에 기다리고 있진 않은지 확인해 self를 업데이트 해준다. -> 대기하던 철학자들이 밥을 먹을 수 있게 된다.

Monitor

Semaphore의 문제점

프로그래머에게 wait(), signal()등의 연산을 제공해 코딩을 비교적 쉽게 하도록 해주었으나, 문제가 생겼을 때 버그를 잡기가 어렵다.
정확성의 입증이 어렵다.
자발적 협력이 필요하다.
따라서 한번의 실수가 모든 시스템에 치명적인 영향을 끼친다.

위의 상황에서 wait() 다음 signal()이 와야하는데, 프로그래머의 실수로 signal() 다음에 wait()가 왔다. 이런 경우 mutual exclusion이 깨진다.

위의 경우는 wait() 다음 signal()이 와야하는데, wait()가 다시 왔다. 그래서 어느 누구도 critical section에 들어가지 못하는 상황이 된다.

monitor는 특별히 프로그래밍 언어 차원에서 synchronization 문제 해결을 위한 high-level synchronization construct이다. 객체지향 프로그래밍 언어를 보면 객체를 중심으로 operation이 정의 되는 것을 볼 수 있는데 monitor도 이에 기반해서 공유 데이터에 접근하기 위해서는 monitor라고 정의된 내부의 프로시저를 통해서만 접근할 수 있게 만드는 것이다.

위와 같이 내부에 공유 데이터를 선언하고 프로시저를 함수형태로 정의해놓는다.

그래서 예를 들어 공유 데이터가 있으면 밖에서 아무나 접근할 수 있는 것이 아니라 monitor안에 공유 데이터와 공유데이터를 접근하는 프로시저를 정의 해놓고 공유데이터에 접근한다면, 프로시저를 통해서 접그근할 수 있게 하는 것이다. 그리고 monitor가 원천적으로 monitor 내부에 있는 프로시저는 동시에 여러개가 실행되지 않도록 통제하는 권한을 주는 것이다. (monitor내에서는 한번에 하나의 프로세스만이 활동 가능) 이렇게 하면 프로그래머는 lock을 걸 필요가 없어진다. semaphore는 동시접근을 위해 항상 wait()연산을 통해 lock을 걸어주고 풀어주는 것을 프로그래머가 해줬어야 했다. 하지만 monitor는 동시접근 자체를 알아서 막아준다.

예를 들어 어떤 프로세스가 monitor에 와서 공유 데이터를 접근하는 코드를 실행하고 있다가 CPU를 빼았겨 다른 프로세스가 monitor로 접근하려한다면 ? 코드를 실행하던 도중에 CPU를 빼앗겼기 때문에 그 코드는 여전히 active한 상태로 남아있는 것이다. 그래서 다른 프로세스가 monitor안에 있는 코드를 실행하지 못하고 monitor 밖의 queue에서 대기한다.
그렇다면 언제 들어올 수 있나?
안에 active한 프로세스가 0이 될 때 => 지금 monitor를 쓰고 있던 프로세스가 다 쓰고 나가던지, 이 프로세스가 monitor 내부에서 무언가 충족되지 않아 잠들던지(active하지 않은 상태가 되는 것)
=> 아 이제 active한 프로세스가 없구나 하고 들어온다.

프로그래머 입장에서 lock에 관해 신경을 안써도 되니 훨씬 수월하다.

따라서 semaphore와의 차이점은 lock을 걸 필요가 없다는 것

monitor 안에서 어떤 코드를 실행하다가 무언가 충족되지 않아 오래걸려야함 -> 잠들게 해야한다 -> 어떤 조건에 따라 잠들게 되었는지에 따라 이것을 변수로 둘 수 있다. 이러한 변수를 condition variable이라한다. 이는 값을 가지는 변수가 아니라, 어떤 프로세스를 잠들게 하고 줄 세우기 위한 변수이다. 값을 카운드 XX

하지만 monitor에도 자원의 개수를 세는 것(자원이 없으면 대기, 자원이 있으면 획득 등)은 필요한데, 그걸 위해 세마포어 변수처럼 비슷한 역할을 하는 condition variable이라는 것이 있다. (프로세스가 monitor안에서 기다릴 수 있도록 하기 위해 condition variable 사용)
condition variable은 wait와 signal 연산에 의해서만 접근 가능하다.

x.wait();
- x.wait();을 invoke한 프로세스는 다른 프로세스가 x.signal();을 invoke하기 전까지 suspend된다.
- 잠들게 하겠다 -> x라는 조건을 만족하지 못해 잠드는 거임 -> x.wait() -> x 뒤에 가서 줄섬
x.signal();
- x.signal();은 정확하게 하나의 suspend된 프로세스를 resume한다.
- suspend된 프로세스가 없으면 아무 일도 일어나지 않는다.
- x를 다 쓰고 나갔는데 x를 위해 기다리고 있는 프로세스를 깨워주는 것

bounded-buffer problem (semaphore)

bounded-buffer problem (monitor)

공유 버퍼가 monitor안에 정의된 것을 볼 수 있다. 공유 버퍼에 데이터를 집어넣거나 빼는거 앞뒤에 lock을 거는 것이 없다. 비어있는 버퍼가 없다면 비어있는 버퍼를 기다리는 줄에 기다리게 보내는 것이다. 비어있는 버퍼가 있다면 집어넣으면 된다.

잠들어 있는 프로세스가 있다면 깨워주는 코드가 들어있다.

consumer는 이의 반대이다.

monitor의 변수는 줄에 있는 걸 깨워주기 위함

monitor DiningPhilosophers
{
    enum {THINKING, HUNGRY, EATING} state[5]; 
    condition self[5];
    
    void pickup(int i) { 
        state[i] = HUNGRY; 
        test(i);
            if (state[i] != EATING)
                self[i].wait();
    }   
    
    void putdown(int i) { 
        state[i] = THINKING; 
        test((i + 4) % 5); 
        test((i + 1) % 5);
    }
    
    void test(int i) {
        if ((state[(i + 4) % 5] != EATING) && (state[i] == HUNGRY) && (state[(i + 1) % 5] != EATING)) {
            state[i] = EATING;
            self[i].signal();
        } 
    }
    
    initialization code() {
        for (int i = 0; i < 5; i++)
            state[i] = THINKING;
    } 
}

출처

Operating System Concepts 10th
KOCW 강의 - [운영체제] 이화여자대학교 반효경 교수

뚝딱이

백엔드 개발자 지망생

이전 포스트

CPU Scheduling

다음 포스트

Process Synchronization (Concurrency Control)

운영체제

OS 에서 race condition은 언제 발생하는가?

kernel 수행 중 인터럽트 발생시

Process가 system call을 해 kernel mode로 수행중인데 context switch가 일어나는 경우

Multiprocessor에서 shared memory내의 kernel data

Process Synchronization 문제

Race condition

The Critical-Section Problem

문제를 해결해보자 !

해결법의 충족 조건

Mutual Exclusion (상호 배제)

Progress

Bounded Waiting (유한 대기)

어떨 때 발생할까?

int turn을 사용해 해결 시도

문제점

boolean flag를 사용해서 해결 시도

문제점

Petersons's Algorithm

Synchronization Hardware

Semaphores

Semaphore의 operation

wait(S)

signal(S)

Block & Wakeup Implementation

wait()

signal()

Busy-wait vs Block&WakeUp

Two Types of Semaphores

Counting semaphore

Binary semaphore (=mutex)

주의점

Deadlock

Starvation

Classical Problems of Synchronization

Bounded-Buffer Problem

해야할 일

semaphore

producer

consumer

sudo code

producer

Readers-Writers Problem

sudo code

Reader

공유 데이터

동기화 변수

Dining-Philosophers Problem

sudo code

dead lock

해결법

Monitor

Semaphore의 문제점

출처

CPU Scheduling

Deadlocks

0개의 댓글