개발 일기

컴퓨터 관련 분야에서 가장 중요한 것은 영어다.

격언 : 컴퓨터를 잘하는 사람에게 영어를 가르치는 것보다 영어를 잘하는 사람한테 컴퓨터를 가르치는 것이 더 낫다.

자신의 의견을 어필하기 위한 수단이 영어다.

영어 공부 열씨미 하즈아아

각설하고, Synchronization에 대해서 오늘은 공부하였다.

동기화 문제가 발생하는 이유는 바로 일관성(consistency)가 깨지기 때문이다. 만약 하나의 코어에서 하나의 process만 동작한다면 동기화가 필요 없겠지만, 다양한 process가 다양한 코어에서 사용되다 보니 일관성이 깨져 동기화 문제가 발생하게 되는 것...

이러한 문제를 해결하기 위한 방법으로 소프트웨어적인 방법과 하드웨어적인 방법 크게 두 가지가 존재한다.

아, 문제 해결 방법을 정리하기 전에 동기화 문제에 대해서 예시를 한 번 들어보자.

자, 예전에 공부했던 Producer-Consumer Problem에서 우리는 circular queue를 구현하여, 버퍼를 만들어 사용하였다. 이 때 empty와 full을 구분하기 위해 귀중한 buffer 하나를 사용하지 않으면서 말이다.

그런데 한가지 궁금증이 생긴다. 그냥 counter라는 공유 변수를 놓고 버퍼가 차면 하나 증가시키고, 버퍼가 빠지면 하나 감소시키면서 관리하면 되지 않는가?

여기서, 동기화 문제가 발생한다. HLL(=High Level Language)에서 한 줄은 실제 여러줄로 동작될 수 있다.

예를 들어, counter++ 이라는 명령어를 실제로 instruction set 단계로 내려가면

register1 = counter (LOAD)

register1 = register1 + 1 (ALU)

counter = register1 (STORE)

3가지 단계를 거치게 된다.

그런데 이 때 Race Condition이라는 문제가 발생하게 된다.

Race Condition이란?

한국 말로 "경쟁 상태"로서 둘 이상의 입력 또는 조작의 타이밍이나 순서 등이 결과값에 영향을 줄 수 있는 상태를 말한다.

- 위키

즉, 실행 순서에 따라서 결과가 다르게 나올 수 있다는 것이다. 말이 되는가? counter++을 했는데 결과가 2개 이상이 나올 수 있는 경우가 있다는 것이?????!!!!!!

결론은 가능하다!

자 예를 한 번 들어보자.

2개의 Process가 존재하고, 각 Process에서 counter++, counter--를 수행해보자.

각 명령은 3개의 instruction set으로 존재하고, 하나의 instruction이 atomic한 경우를 만족한다고 가정하면, context-switching은 instruction과 instruction 사이에서 발생할 수 있을 것이다.

만약 counter++, counter--를 수행하게 되면 초기값이 5였을 때 최종 결과는 항상 5가 되어야 하는데...

register1 = counter

register1 = register+1

------------------------------> context-switching 발생

register2 = counter

register2 = register -1

------------------------------> context-switching 발생

counter = register1

------------------------------> context-switching 발생

counter = register2

위의 과정을 거치면 counter 값은 4가 된다.

위와 같은 경우로 인해 우리는 circular queue에 두 개의 variable을 두고 Producer와 Consumer가 건드릴 수 있는 variable을 각각 설정한 것이다.(이는 공유 자원이 아니다!)

어떠한 이유로 동기화 문제가 발생하는 것을 알았으니, 어떻게 하면 이러한 문제가 발생하지 않을까?

"하나의 Process가 공유 자원을 사용하면 다른 Process는 공유 자원에 접근할 수 없다"

로 해결할 수 있을 것 같다.

좀 더 자세하게 들어가보자.

운영체제에서는 Cirtical Section Problem이라는 것이 있다.

Critical Section(<->remainder section)이란 상호 베타적인 접근을 보장해주는 영역으로서 각 Process마다 Critical Section을 가지고 있고, 어떠한 Process가 Critical Section에서 작업하고 있다면 다른 Process는 Critical Section에서 작업을 할 수 없는 것이다.

Problem은 어떻게 상호 베타적인 접근을 보장해주냐는 것을 의미하고 말이다.

이러한 Critical Section에 들어가기 위한 entry Section 나가기 위한 exit Section이 추가적으로 있고, 이를 그림으로

이와 같이 볼 수 있다.

자 이제 해결해야 할 문제는 어떻게 critical Section의 상호베타적 접근을 보장해주기 위한 해결책을 해.............보기 전에

Critical Section Problem에 대한 기준 3가지를 한 번 언급해보려 한다.

1. Mutual Exclusion

-> "상호 배제". 즉, 베타적인 접근을 보장해야 한다는 기준이다. critical section을 사용하는 가장 근본적인 이유라고 하겠다.

2. Progress

->"진행". Critical Section이 무기한 연기될 수 없다. 하나의 Critical Section이 다른 Critical Section에 의해 무기한 연기될 수 없다는 기준이다.

3. Bounded Waiting

-> "한계가 있는 기다림". 어떻게 보면 2와 동일한 말이다. 무기한 연기될 수 없으니깐 기다림에 있어서 제한을 둬야 한다는 기준이다.

이 3가지 기준을 모두 만족해야만 Critical Section Problem을 해결했다고 볼 수 있는 것이다.

그렇다면 구체적으로 들어가서 보자!

먼저 SW Solution을 분석해보자.

Peterson's Solution

위의 솔루션은 제한 조건이 있다.

1. 두 개의 Process에 대한 Solution

2. load, store instruction이 atomic하다. -> 요즘 시스템에는 맞지 않는 말이다.

그리고 2개의 variable을 사용한다.

1. int turn -> Critical Seciton에 누가 들어갈 것인지를 알려주는 변수

2. Boolean flag[2] -> Critical Section에 들어갈 것이라는 의사표시를 하는 변수

프로세스가 2개(Pi, Pj / i = 0, j = 1)가 있다고 했을 때 Peterson's Solution의 알고리즘은 아래와 같다.

entry_section에서 본인의 flag를 true로 바꾸고 turn값을 다른 process로 명명한다.

그리고 while문을 돌며 다른 process의 flag가 true이고, turn == 1일 경우 자신은 대기한다.

여기서 특이한 점은 P0에서 turn = 1을 수행하는 것인데.... 이는 turn에 대한 Consistency가 깨져도 Race Condition이 발생하지 않게 하기 위함이다.

해당 알고리즘은 두 개의 Process가 Critical Section에 접근하지 않으면 되는 것이다.

그렇다면 어떠한 경우에 while문을 빠져 나올 수 있는지를 확인해보자.

P0의 경우

flag[1]==false or turn == 0인 경우이고,

P1의 경우

flag[0] == faluse or turn == 1인 경우이다.