인프런 공룡책 정리 - Section 06 | CS Study

hoya·2022년 3월 9일
0

CS Study

목록 보기
7/13
post-thumbnail

⚠️ 해당 포스팅은 인프런 공룡책 강의를 듣고 개인적으로 정리하는 글입니다. 정확하지 않은 정보가 있을 수 있으니 주의를 요합니다.

Section 06

Chapter 6 CPU Synchronization Tools


Background

협력 프로세스(Cooperating Process)

  • 서로에게 영향을 주거나, 받을 수 있다.
  • 논리적 주소 공간을 공유하거나, 데이터를 서로에게 공유할 수 있다.
  • 하지만, 공유 데이터에 동시 접근하는 것은 데이터 불일치라는 결과를 야기할 수 있다.
  • 그런 이유로, 협력 프로세스에서는 순서대로 실행할 수 있게끔 설정하는 것이 중요하다.
  • 순서대로 실행한다면, 논리적 주소 공간에서의 데이터 일관성을 유지할 수 있다.

이런 일이 생긴다면 어떨까?

  • 다시 생산자-소비자 문제로 돌아가보면, 두 개의 프로세스가 데이터를 공유하며 이는 비동기적으로 작동된다.
  • 하나의 예를 들어 이해해보자.
  • 우선 버퍼에서 아이템의 수를 측정할 카운트 변수를 지정한다.
  • 새 아이템을 버퍼에 추가하면 카운트의 수가 증가하고, 버퍼에서 삭제되면 카운트의 수가 감소될 것이다.

int count = 5;

while(true) {
	while(count == BUFFER_SIZE)
    	; /* do nothing */
    
    buffer[in] = next_produced;
    in = (in + 1) % BUFFER_SIZE;
    count++;
}

while(ture) {
	while (count == 0)
 	;	/* do nothing */
        
    next_consumed = buffer[out];
    out = (out + 1) % BUFFER_SIZE;
    count --;
    
    /* consume the item in next_consumed */
}

/* 결과가 6이 나오는 것이 아니라, 4,5도 함께 나오며 제대로된 결과가 출력되지 않음 */
  • 데이터 일관성(Data inconsistency)
    • 두 프로세스는 개별적으로 보았을 때는 정확하지만, 동시에 실행할 경우 올바르게 작동하지 않을 수 있다.
    • count의 값이 5라고 지정하고 생산자와 소비자가 각각 카운트를 증가시키고 감소시키는 작업을 동시에 수행했을 때 결과가 4나 5, 혹은 6이 나오며 우리가 기대한 결과를 받지 못하게 된다.
  • 왜 이런일이 벌어지는 걸까?
  • 우리가 명령했던 카운트 증가와 감소, 즉 count++count-- 는 우리가 작성한 코드에서 보았을 때는 한 줄의 간단한 코드이다.
  • 그러나, 기계어 수준으로 들어가면 단순히 한 줄로 구성되지 않는다.
	/* count ++ */
    register1 = count
    register1 = register1 + 1
    count = register1
    
    /* count -- */
    register2 = count
    register2 = register2 - 1
    count = register2
  • 로우 레벨 단계에서는 단순히 한 줄이 아니라 세 줄로 구성되어 있는 것을 확인할 수 있다.
  • 레지스터1과 레지스터2는 물리적으로 동일한 레지스터를 공유하는 것이 맞지만, 레지스터의 내용을 저장하고 복원하는 것은 인터럽트 핸들러가 결정한다.
  • 즉, count++count-- 명령은 로우 레벨 단계에서 임의의 순서로 끼어지게 되며, 순차 실행과 동일한 결과를 낳게 된다.


Race Condition(경쟁 상황)

  • 여러 프로세스 혹은 스레드가 공유 데이터에 접근하거나 조작할 때를 일컫는 현상이다.
  • 실행의 결과는 어떤 순서에 따라 접근되는지에 따라 결정된다.
  • 경쟁 상황을 해결하기 위해서는, 오로지 하나의 포르세스가 특정 시간에 공유 데이터를 다룰 수 있게끔 설정해야 한다.
  • 이를 보장하기 위해 프로세스가 어떤 식으로든 동기화되어 있어야 하며, 이를 프로세스 혹은 스레드 동기화라고 한다.

public class RaceCondition2 {

    public static void main(String[] args) throws InterruptedException {
        RunnableTwo run1 = new RunnableTwo();
        RunnableTwo run2 = new RunnableTwo();

        Thread t1 = new Thread(run1);
        Thread t2 = new Thread(run2);

        t1.start();t2.start();
        t1.join(); t2.join();

        System.out.println("Result : " + RunnableTwo.count);
    }
}

public class RunnableTwo implements Runnable{

    static int count = 0; // 공유 데이터
    // 동시에 접근하며 경쟁 상황(Race condition) 발생

    @Override
    public void run() {
        for (int i = 0; i < 10000; i++) {
            count++;
        }
    }
}

/* 결과가 20000이 아니라, 무작위로 나옴. */

The Critical Section Problem

  • 시스템에 n개의 프로세스가 구성되어 있다고 가정했을 때 각각 프로세스의 코드 영역을 크리티컬 섹션이라고 칭한다.
  • 프로세스가 하나 이상의 다른 프로세스와 공유되는 데이터에 액세스하고 업데이트 할 수 있다.
  • 하나의 프로세스가 크리티컬 섹션을 실행중일 때 다른 프로세스는 크리티컬 섹션에 진입할 수 없게 설정하는 것이 시스템의 중요한 특징 중 하나이다.
  • 프로세스가 작업을 동기화하는데 사용할 수 있는 프로토콜을 설계하여 데이터를 올바르게 공유할 수 있게 설정해야 한다.

Sections of codes

  • Entry section : 크리티컬 섹션 진입의 허가를 요청한다.
  • Critical section : 크리티컬 섹션을 실행한다.
  • Exit section : 크리티컬 섹션 진입의 허가를 반납한다.
  • Remainder section : 남은 코드를 실행한다.

Three requirements for the solution

  • 크리티컬 섹션을 해결하는데 세 가지 요구사항이 존재한다.
  • Mutual Exclusion (상호 배제)
    • 한 프로세스가 크리티컬 섹션에 돌입하면 다른 프로세스는 크리티컬 섹션에 진입하지 못하게 해야 한다.
  • Progress (진전)
    • 데드락을 방지하기 위한 요구사항으로, 어떤 프로세스도 크리티컬 섹션을 실행하지 않는 상황에서, 한 프로세스가 크리티컬 섹션에 진입하길 원하면 곧바로 돌입할 수 있게 해주어야 한다.
    • 즉, 아무도 크리티컬 섹션에 진입하지 못하는 상황은 없어야 한다.
  • Bounded Waiting (한정 대기)
    • 기아(starvation) 상황을 방지하기 위한 요구사항으로, 프로세스가 크리티컬 섹션에 진입하고자 요청을 한 후부터 해당 요청 허용까지 다른 프로세스가 크리티컬 섹션에 진입할 수 있는 횟수를 제한해야 한다.
    • 쉽게 이야기하면 프로레스당 크리티컬 섹션 진입 횟수에 한계를 두어 동일 프로세스가 독점할 수 없게끔 한다는 이야기이다.
  • 가장 쉽게 크리티컬 섹션 문제를 해결하는 방법은 싱글 코어 환경을 이용하는 것이다.
    • 공유 변수를 수정하는 동안 인터럽트 발생을 억제한다.
    • 명령 리스트가 선점되는 현상 없이 순서대로 실행될 것이라는 확신을 얻을 수 있다.
    • 다른 명령이 지시되지 않음으로서 공유 데이터를 예기치 않게 수정하는 것을 방지할 수 있다.
    • 그러나, 멀티 프로세서 환경에서는 실행할 수 없는 방법이다.

Peterson's Solution

  • 크리티컬 섹션 문제를 해결하기 위해 여러가지 방법이 존재한다.
    데커의 알고리즘 : 두 프로세스 간 문제를 해결하는 방법
  • 피터슨 알고리즘은 크리티컬 섹션 문제를 해결하는데 이상적인 알고리즘이다.
  • 상호 배제, 진전, 한정 대기, 세 가지 요구 사항을 모두 충족하는 알고리즘이다.
  • turnflag 변수로 크리티컬 섹션에 진입할 프로세스 혹은 스레드를 결정한다.
public class PetersonTest {

    static int count = 0; // 공유 자원
    static int turn = 0; // 다음 차례 지정
    static boolean[] flag = new boolean[2]; // 실행 스레드 지정

    public static void main(String[] args) {
        Thread pThread = new Thread(new Producer());
        Thread cThread = new Thread(new Consumer());

        pThread.start();
        cThread.start();

        try {
            pThread.join();
            cThread.join();

        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        System.out.println("남은 갯수 : " + count); // 공공재 총량 출력
    }

    static class Producer implements Runnable {
    
        @Override
        public void run() {
            for (int i = 0; i < 10000; i++) {
                flag[0] = true; // 나 이제 실행할 준비가 됐어.
                turn = 1; // 내가 실행하면, 다음 차례는 너야

                while (flag[1] && turn == 1) ; // Busy Waiting
                // 너가 이미 실행을 하고 있으면 난 기다릴게

                // 실행을 다 마쳤으니 이제 내 차례고, 난 이제 크리티컬 섹션에 진입할거야.
                count++; // 크리티컬 섹션 조작

                flag[0] = false; // 내 실행을 모두 마쳤어.
            }
        }
    }

    static class Consumer implements Runnable {

        @Override
        public void run() {

            for (int i = 0; i < 10000; i++) {
                flag[1] = true; // 나 이제 실행할 준비가 됐어.
                turn = 0; // 내가 실행하면, 다음 차례는 너야.

                while (flag[0] && turn == 0) ; // Busy Waiting
                // 너가 실행중이면, 난 기다릴게.

                // 실행을 다 마쳤으니 이제 내 차례고, 난 이제 크리티컬 섹션에 진입할거야.
                count--; // 크리티컬 섹션 조작


                flag[1] = false; // 내 실행을 모두 마쳤어.
            }
        }
    }
}
  • 크리티컬 섹션 진입 전 기다리는 과정에서 무한 루프(busy waiting)를 돌게 되는데, 무한 루프에도 CPU 자원을 사용하기 때문에 CPU를 효율적으로 사용하지 못하는 문제가 있다.

  • 현대 컴퓨터가 load-store 같은 기계어를 수행하는 방식을 사용함으로 인해 올바른 실행을 매번 보장하지는 않는다.

Hardware Support for Synchronization

  • 크리티컬 섹션 문제를 풀기 위해 지원을 제공하는 하드웨어 명령을 제시하며 세 가지 옵션이 존재한다.

Memory barriers or fences

  • 메모리 장벽은 매우 낮은 수준의 연산으로 일반적으로 Mutual Exclusion 을 보장하는 특수 코드를 작성할 때 커널 개발자만 사용한다.

Hardware instructions

  • 특별한 하드웨어 명령으로 원자성을 가진 명령을 추가하는 방법이다.
  • 한 워드의 내용을 검사하고 변경하거나 두 워드의 내용을 원자적으로 교환할 수 있게 한다.
  • 즉, 인터럽트 할 수 없는 하나의 단위로 간단하게 크리티컬 섹션을 해결할 수 있다.
    이게 무슨소리야? -> a++ 은 아까 보았듯이 기계어 세 줄로 이루어져 있는데, 이를 기계어 한 줄로 줄여 중간에 인터럽트 되는 상황을 막겠다는 이야기이다.
  • test_and_set() 명령어와 compare_and_swap() 명령어로 예를 들어 설명해본다.
	boolean test_and_set(boolean *target) {
    	boolean rv = *target;
        *target = true;
        
        return tv;
    }
    
    do {
    	while (test_and_set(&lock)); /* do nothing, context switching X */
		// 본인의 lock 을 true 로 만들고 진입한다.
        
		/* critical section */
        
        lock = false; // 크리티컬 섹션을 빠져나온 후 false로 만들어 다른 프로세스 진입을 허용
        
        /* remainer section */
    	
    } while (true);
	int compare_and_swap(int *value, int expected, int new_value) {
    	int temp = *value;
        
        if (*value == expected)
        	*value = new_value;
          
        return tmp;
    }
    
    while (true) {
    	while (compare_and_swap(&lock, 0, 1) != 0);
        /* do nothing */
        
        /* critical section */
        
        lock = 0;
        
        /* remainer section */
    }

Atomic Variables

  • 원자적 변수는 정수 및 부울과 같은 기본 데이터 유형에 대해 원자적 연산을 제공한다.
  • 원자적 변수는 경쟁 상황이 일어나는 단일 변수에 대해 상호배제를 보장해준다.
  • 원자적 변수를 지원하는 시스템은 원자적 변수에 접근하고 조작하기 위한 기능 뿐 아니라 특별한 원자적 데이터 유형을 제공한다.
  • 오류가 났던 피터슨 알고리즘에 원자적 변수를 도입하면 정상적인 결과가 출력된다.
import java.util.concurrent.atomic.AtomicBoolean;

public class PetersonTest2 {

    static int count = 0;
    static int turn = 0;
    static AtomicBoolean[] flag; // 원자 변수

    static {
        flag = new AtomicBoolean[2];
        for (int i = 0; i < flag.length; i++)
            flag[i] = new AtomicBoolean();
    }

    public static void main(String[] args) {
        Thread pThread = new Thread(new PetersonTest2.Producer());
        Thread cThread = new Thread(new PetersonTest2.Consumer());

        pThread.start();
        cThread.start();

        try {
            pThread.join();
            cThread.join();

        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        System.out.println("남은 갯수 : " + count); // 공공재 총량 출력
    }

    static class Producer implements Runnable {
        @Override
        public void run() {
            for (int k = 0; k < 100000; k++) {
                
                /* entry section */
                flag[0].set(true);
                turn = 1;
                while (flag[1].get() && turn == 1); // 원자 변수 특정 명령어 
                
                /* critical section */
                count++;
                
                /* exit section */
                flag[0].set(false);
                
                /* remainder section */
            }
        }
    }

    static class Consumer implements Runnable {
        @Override
        public void run() {
            for (int k = 0; k < 100000; k++) {
                
                /* entry section */
                flag[1].set(true);
                turn = 0;
                while (flag[0].get() && turn == 0)
                    ;
                
                /* critical section */
                count--;
                
                /* exit section */
                flag[1].set(false);
                
                /* remainder section */
            }
        }
    }
}
profile
즐겁게 하자 🤭

0개의 댓글