⚠️ 해당 포스팅은 인프런 공룡책 강의를 듣고 개인적으로 정리하는 글입니다. 정확하지 않은 정보가 있을 수 있으니 주의를 요합니다.
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
- 크리티컬 섹션 문제를 해결하기 위해 여러가지 방법이 존재한다.
데커의 알고리즘 : 두 프로세스 간 문제를 해결하는 방법 - 피터슨 알고리즘은 크리티컬 섹션 문제를 해결하는데 이상적인 알고리즘이다.
- 상호 배제, 진전, 한정 대기, 세 가지 요구 사항을 모두 충족하는 알고리즘이다.
turn과flag변수로 크리티컬 섹션에 진입할 프로세스 혹은 스레드를 결정한다.
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 */
}
}
}
}
즐겁게 하자 🤭