동시성 문제[1] - 동시성 문제의 원인과 해결법

동시성 문제

동시(concurrent)에 공유 데이터에 access(접근)하여 데이터를 manipulate(조작)하는 과정에서 데이터의 일관성이 깨지는 문제

동시성 문제의 근본 원인

프로세스나 스레드는 instruction 실행 도중 intruppted(중단) 될 수 있고 CPU의 코어는 다른 프로세스나 스레드 작업을 할당 받을 수 있다. 즉, 두개 이상의 프로세스나 스레드를 동시에 수행할 때 CPU의 context-switching으로 인해 발생한다는 것이다. 아래 간단한 예제를 통해 동시성 문제의 한 예를 보자.

public class ConcurrencyProblem {

   public static int COUNT = 0;

   public static void main(String[] args) {
       Thread producerTh = new Thread(new Producer());
       Thread consumerTh = new Thread(new Consumer());
       producerTh.start();
       consumerTh.start();
       System.out.println(COUNT);
   }

   static class Producer implements Runnable {
       @Override
       public void run() {
           for (int i = 0; i < 1000000000; i++) {
               COUNT++;
           }
       }
   }

   static class Consumer implements Runnable {
       @Override
       public void run() {
           for (int i = 0; i < 1000000000; i++) {
               COUNT--;
           }
       }
   }
}

Producer 스레드는 공유 데이터인 COUNT 값을 1만큼 증가시키는 작업을 10억번 진행한다.

Consumer 스레드는 COUNT 값을 1만큼 감소시키는 작업을 10억번 진행한다.

출력 결과를 보면 0이 나와야할 것 같지만 실제 값은 1238, 2078, 2423, 0 등으로 0 이외의 값이 굉장히 자주 나타난다.

동시성 문제에 대해 어느정도 알고 있는 사람들은 값을 read하고 modify하는 시간 사이에 누군가 값을 바꾸면 기대한 값으로 값이 변경되지 않는 현상이 나타난다는 것을 잘 알 고 있다.

허나, 위의 명령어는 read하고 modify하는 연산 없이 count++; count–; 작업을 바로 수행한다.

우리는 동시성 문제에 대해 보다 깊이 있게 이해하기 위해서는 프로그래밍 수준이 아닌 os수준에서 이해할 수 있어야 한다.

count++ 명령어는 실제 CPU에 의해 아래와 같이 작업이 이루어진다.

cpu의 기억장치인 레지스터에서 count 값을 read하고 해당 값에 1을 더해주고, count 변수에 1을 더한 값을 할당한다.

count–; 작업도 마찬가지로 과정으로 작업이 이루어진다.

프로그래밍 수준에서는 Atomic한 함수였지만 기계어 수준에서는 3개의 instruction으로 이루어져있다.

여러개의 instruction이 수행되는 과정에서 스레드의 context switching이 일어나 count값이 변경되어 +1이나 -1을 하면

이전에 읽어들인 값과 달라지기에 기대한 결과가 나타나지 않는 것이다.

아래의 예시를 보자.

(T는 Task(작업)을 의미하며 0~5는 실행 순서를 의미한다.)

T0 : producer의 작업이 실행되고 이때 읽어들인 count 변수의 값 5를 CPU의 register1에 저장시킨다.

T1 : register1에 register1+1을 수행한 결과를 저장하기에 6을 저장시킨다.

T2 : 이때 context-switching이 일어나 consumer의 작업이 수행되는데 T1의 결과는 아직 count 변수에 저장된 것이 아니라
cpu의 register1에 저장된 값이므로 count 변수의 값은 5이다. 따라서 register2에는 5가 할당된다.

T3~T5 : 각각의 작업 수행

최종 결과는 4가 나왔다. 두 작업이 수행되기 전의 값이 5였고, 각각 한번씩 수행됬기에 기대결과는 5가 나와야하지만 하지만 결과가 다르다.

이러한 문제의 원인은 두 스레드가 공유 데이터에 동시에 access(접근)하고 manipulate(조작)하는 instruction을 수행하는 도중 context-switching이 일어나 기대결과가 나타나지 않은 것이다.

이와 같은 상황을 Race Condition(경쟁상황) 이라고 부른다.

Race Condition

여러개의 프로세스(스레드)가 실행되는 환경
공유 데이터에 동시에 access하고 manipulate함
실행결과는 어느 시점에 공유 데이터에 접근하는지에 따라 달라짐
(= context-switching이 어느시점에 이뤄지는에 따라 결과가 달라짐)

Race Condition이 발생하지 않기 위해서는 오직 하나의 프로세스만 동시에 공유 데이터를 조작 할 수 있어야한다.

그리고 이를 프로세스(or 스레드) 동기화라고 부른다.

동시성 문제의 종류

Producer-Consumer Problem -> 데이터 일관성 깨짐
Reader-Writer Problem -> 기아문제(Starvation)
Dining philosophers Problem -> 데드락(Deadlock)

Producer-Consumer Problem

read-modify하는 instruction 실행 도중 Producer와 Consumer간의 context-switching이 일어나 기대 결과가 달라지는 문제이다.

예를들어 버퍼라는 공간에 Producer는 데이터를 넣을수만 있고, Consumer는 데이터를 가져올수만 있다.

T0가 Producer가 버파가 한칸 비어있다는 것을 확인하고 데이터를 넣을려고할 때, Context-Switching이 일어나고, T1의 Producer가 버퍼가 한칸 비어있다는 것을 읽고 데이터를 넣은 후에 T0가 다시 실행되면 T0은 이전에 버퍼가 한칸 남아있다고 판단했으므로 데이터를 버퍼에 넣게 되면 T1에 의해 가득차있기에 데이터는 유실될 것이다.

Consumer의 경우에도 동일하게 이러한 상황을 겪게 된다.

이를 해결하기 위해서는 상호배제라는 조건이 필요하다 이는 둘 이상의 스레드가 동시에 공유자원을 사용하는 것을 방지하는 알고리즘이다.

Reader-Writer Problem

Reader는 데이터를 읽기만 하며 여러 Reader들이 공유 데이터에 동시에 접근할 수 있고, Writer는 데이터를 읽고 쓸수 있으며 Writer가 공유 데이터에 접근하면 다른 Reader나 Writer는 공유 데이터에 접근하지 못한다.

이로인해 Writer가 공유 데이터에 접근하면 다른 Reader나 Writer가 무한정 대기에 빠지는 현상이 나타날 수 있다.

이를 기아현상(Starvation Problem)이라고 한다.

Dining philosophers Problem(식사하는 철학자)

철학자들이 원탁에 앉아있고, 양옆에 포크가 하나씩 있다.
스파게티를 먹기 위해서는 양옆의 포크를 동시에 들어야한다.

이때 왼쪽 포크부터 들고, 오른쪽 포크를 나중에 들게 되면오른쪽의 포크를 오른쪽 철학자가 가져간 상태이기 때문에
아무도 스파게티를 먹지 못하고 무한정 서로가 포크를 내려놓기를 기다리는 상태에 빠지게 될 수 있다.

이러한 현상을 Dead Lock(교착상태)라고 하는데, 두 개 이상의 스레드가 서로의 작업이 끝나기만을 기다리고 있기에 아무 작업도 수행하지 못하는 상태를 말한다.

위 내용에 대해 간단히 정리하면,

Producer-Consumer는 동시성 문제의 근본 원인인 여러 스레드의 작업을 CPU가 동시에 수행하는 경우 context-switching으로 인한 데이터의 일관성이 깨지는 근본 원인에 대해 말하는 것이고,

기아문제나 데드락은 동시성 문제를 제대로 해결하지 못했을 때, 나오는 파생적인 문제이다.

앞으로 자세히 설명하겠지만, 기아문제나 데드락은 동시성 문제로 인한 데이터 일관성이 깨지는 문제를 해결하기 위한

상호배제를 적용하더라도 나타날 수 있는 현상이다.

동시성 문제는 완벽하게 해결 할수는 없다.

허나 상황에 따른 적절한 해결책들은 존재하고 그 예시들에 대해 알아보자.

Critical Section Problem

Critical Section Problem의 유래

동시성 문제가 발생하는 Race Condition 문제를 해결하기 위해 Critical Section Problem이라는 문제영역을 도출하고
이 문제를 해결한다면 동시성 문제를 해결할 수 있다는 이론적 정의이다.

Critical section이란

Critical Section(임계 영역)이란 공유 데이터가 존재하고 여러 프로세스에 의해 접근 가능하고 공유 데이터 수정이 가능한 코드가 존재하는 영역이다.

Critical Section(임계 영역) 에서는 하나의 프로세스만 실행 가능하고 이때, 다른 프로세스는 접근이 불가하다.

[코드 영역의 종류]

entry-section : 임계영역으로 접근 허가를 요청하는 코드 영역
critical-section : 공유 데이터가 존재하는 영역
exit-section : 임계 영역을 빠져나오는 코드 영역
remainder-section : 나머지 코드 영역

[Critical Section Problem의 해결 조건]

Mutual Exclusion : 임계영역에 하나의 프로세스가 접근하면 다른 프로세서는 접근 못함
Progress(avoid deadlock) : 어떤 프로세스가 임계영역에 진입하여 다른 프로세스가 무한대로 진입이 연기되는 상황을 피해야함
Bounded Waiting(avoid starvation) : 대기시간을 한계를 줘서 프로세스가 진입하지 못하는 상황을 피해야함

Peterson’s Solution

Critical Section Problem의 해결책

public class PetersonSolution {

static boolean[] flag = new boolean[2];

static int turn = 1;

static int sum = 0; // 공유 데이터

public static void main(String[] args) throws InterruptedException {

Thread th1 = new Thread(new Producer());

Thread th2 = new Thread(new Consumer());

th1.start();

th2.start();

th1.join();

th2.join();

System.out.println(sum);

}

static class Producer implements Runnable {

@Override

public void run() {

for (int i = 0; i < 10000; i++) {

/** entry section **/

flag[0] = true;

turn = 1;

while (flag[1] && turn == 1) ;

/** critical section **/

sum++;

/** exit section **/

flag[0] = false;

}

static class Consumer implements Runnable {

@Override

public void run() {

for (int i = 0; i < 10000; i++) {

/** entry section **/

flag[1] = true;

turn = 0;

while (flag[0] && turn == 0) ;

/** critical section **/

sum--;

/** exit section **/

flag[1] = false;

}

공유 데이터는 sum이며 flag와 turn은 critical section에 들어가기 위한 entry section에서 체크하는 값이다.

producer는 0번째 인덱스, consumer는 1번째 인덱스의 플래그(깃발)를 할당 받는다.

entry section에서 producer는 critical section에 들어가기 위해 자신의 깃발에 true를 선언하고 다음 차례 turn에 consumer의 인덱스인 1을 선언한다.

critical section에서는 공유 데이터를 조작한다.

exit section에서는 자신의 깃발에 false를 선언한다.

consumer는 같은 절차를 대칭적인 값으로 선언한다.

while문을 보면

producer는 consumer가 설정한 1번째 인덱스의 플래그 값과 자신이 설정한 turn의 값을 체크한다.

consumer가 깃발을 내렸는지 확인하고 자신이 critical section으로 들어갈 준비가 됬는지 확인하고

두 조건이 모두 맞으면 임계영역에 들어가는 것이다.

즉, 상대방 작업이 끝나고 내가 준비가 되면 들어가는 구조이다. 이는 이론적으로 완벽하다.

공유 영역에 동시에 들어가지 않으므로 상호배제를 이루었고,

한번씩 번갈아가며 동작하기에 교착상태에 빠지거나, 무한정 대기하는 기아문제가 발생하지 않는다.

(실제로 구동하면 1, 2와 같은 값들도 나오는데 이는 sum++, sum–가 원자함수가 아니기 때문이다.)

여기서 entry section에 들어가기 위한 아래 코드의 순서를 바꿔 보겠다.

flag[0] = true;

turn = 1;

아래와 같이 turn을 먼저 선언하고 flag를 나중에 선언하는 구조로 바꿔보자.

turn = 1;

flag[0] = true;

producer와 consumer를 모두 바꿔주고 실행을 하면

-17, -23 등 이번에는 동시성 문제가 더욱 빈번하게 발생된다.

flag[0] = true; 와 같은 함수는 원자함수가 아니다. flag[0] 값을 읽어 오고, 그 이후 true를 할당하는 명령어로 이루어져 있다.

만일 이 과정에서 context-switching이 일어나면 consumer가 flag[0]를 읽을 때 false이기에 임계영역에 진입하고,

다시 context-switching이 발생하여 producer가 while문 체크할 때 turn이 0으로 선언되어 임계영역에 진입하게 되어

둘다 임계영역에 진입하는 상호 배제에 실패하는 결과를 얻게 된다.

Peterson’s Solution은 이론적으로 완벽하지만 실제 컴퓨터 환경에서는 CPU의 context switching으로 인해
동기화 문제가 해결되지 않는다. 이를 위해서는 Hardware적인 지원이 필요하다.

Atomic variable or Atomic instruction

이론적으로 완벽한 Peterson’s Solution은 데이터를 읽고 쓰는 사이에 CPU의 context-switching 발생하여

실제 컴퓨터 환경에서 동시성 문제를 해결하지 못했다.

따라서, 읽고 쓰는 instruction을 하나로 만든다면 context-switching의 영향을 받지 않고 동시성 문제를 해결할 수 있다.

이러한 원자적 처리를 가능하게 하는 변수와 명령여를 Automic variable(원자적 변수)와 Atomic instruction(원자적 명령어)이라고 한다.

public class PetersonSolutionWithHardwareSupport {

static AtomicBoolean[] flag = new AtomicBoolean[2];

static int turn = 1;

static AtomicInteger sum = new AtomicInteger(0); // 공유 데이터

static {

flag[0] = new AtomicBoolean();

flag[1] = new AtomicBoolean();

}

public static void main(String[] args) throws InterruptedException {

Thread th1 = new Thread(new Producer());

Thread th2 = new Thread(new Consumer());

th1.start();

th2.start();

th1.join();

th2.join();

System.out.println(sum);

}

static class Producer implements Runnable {

@Override

public void run() {

for (int i = 0; i < 10000; i++) {

/** entry section **/

turn = 1;

flag[0].set(true);

while (flag[1].get() && turn == 1) ;

/** critical section **/

sum.incrementAndGet();

/** exit section **/

flag[0].set(false);

}

static class Consumer implements Runnable {

@Override

public void run() {

for (int i = 0; i < 10000; i++) {

/** entry section **/

turn = 0;

flag[1].set(true);

while (flag[0].get() && turn == 0) ;

/** critical section **/

sum.decrementAndGet();

/** exit section **/

flag[1].set(false);

}

코드에서 변경된 부분은 boolean 배열을 AtomicBoolean 배열로 변경하였고 공유 데이터 int타입의 sum을 AtomicInteger 타입으로 변경하였다.

이전에 flag[0] = true; 나 sum++; sum–;는 읽고 쓰는 instruction이 여러개로 이루어져있지만 위에서 사용하는 명령어는 instruction이 하나이기에 중간에 context-switching이 발생하여 동시성 문제가 발생하는 일이 생기지 않는다.

출력을 해보면 0으로 동기화 문제가 해결됨을 볼수 있을 것이다.

이렇게해서 동기화 문제의 원인과 해결책에 대해 알아보았다.

허나 실제로 동기화 문제를 해결하는 코드를 구현하는 것은 쉽지 않다.

Pererson’s Solution에서 보았듯이 이론적으로 완벽하더라도 entry section, critical section, exit section에서 사용하는 명령어가 Atomic 하지 않다면 원치 않는 결과가 나타날 수 있다.

동기화 문제를 직접 코드로 해결한다면 기계어 수준에서도 생각할 수 있어야한다.

또한 Atomic variable이나 Atomic instruction을 구성하는 것은 OS 개발자에게 요구되는 수준이며

응용 프로그램 개발자가 이를 직접 구현하기란 쉽지 않은 일이다.

따라서 다음 포스팅에서는 다양한 동기화 도구를 소개하며 고급 언어인 자바에서 동기화 처리를 하는 방식에서도 설명을 하겠다.

저작자표시

'OS & Hardware & Network > OS' 카테고리의 다른 글

동시성 문제[2] - Mutex, Semaphore, Monitor(동기화 도구) (0)	2024.07.28
프로세스[1] - 프로세스란, PCB와 Context Switch (0)	2024.07.25

코딩공장공장장

동시성 문제[1] - 동시성 문제의 원인과 해결법