[운영체제 Step12] - 상호배제 솔루션(2)

지난 포스팅에선 SW 솔루션을 다루어봤고 SW쪽으로만 해결하려니 문제가 많아, 이를 하드웨어쪽에서 지원하기 시작합니다.

어떤 것이 있는지 한 번 살펴보겠습니다.

- TestAndSet (TAS) Instruction

-> Test와 Set을 한 번에 수행하는 기계어입니다.

실 행 중 방해를 전혀 받지 않기 때문에 선점(preemption) 이 이루어지지 않습니다.

TAS 명령어입니다.

중요한건 저 구문이 한 번만 수행이 된다는 사실입니다.

boolean 타입의 temp 는 target이라는 값을 가집니다.

그리고 이 target은 true로 만들고 temp를 return합니다.

이 동작이 한 번만 이루어 지고 있으며 현재 가진 target의 값을 반환하면서 값을 true로 바꾸는 원리입니다.

이게 한 번만 수행된다는 부분이 아주 중요합니다. 

어떻게 ME와 관련해서 연산이 되는지 알아보겠습니다.

그래서, TAS에 lock을 넣고 이 lock의 초기값은 false라고 하고 TAS에 적용되면서 true가 됩니다.

그럼 CS에 들어가게 되고 lock은 false가 되겠죠.

이후, 다른 프로세스인 Pj가 들어왔을 때 똑같이 TAS 명령어를 통해 true가 되고 CS에 들어갈 수 있습니다.

또한 한 프로젝트가 CS에 있을 때 다른 프로세스는 들어올 수 없기 때문에 ME문제가 간단히 해결되었죠?

SW 솔루션에서 복잡하게 해결했는데, HW 솔루션으로 정말 간단하게 해결할 수 있었씁니다.

그러나, 프로세스가 3개 이상이 될 경우 Bounded waiting 조건에 위배할 수 있다는 단점이 있었습니다.

예를 들어, 한 프로세스가 CS에 있고 2,3번 프로세스가 while문을 돌고 있다고 해봅시다.

그럼 여기서 1번이 나가고 2번이 먼저 들어간다고 할 경우, 4번 프로세스가 등장하여 while문에 3,4번이 같이 존재한다면 그 다음엔 누가 들어갈지 제대로 순서를 정할 수 없습니다.

이 때문에 만에 하나 3번 프로세스가 계속해서 대기해야 한다면 무한 대기 현상이 발생할 수 있어 이를 지양해야 겠습니다.

 

그러므로 이를 해결하기 위해 N개의 프로세스를 처리하는 ME와 TAS Instruction가 등장합니다.

2번의 waiting[i] = true는 본인이 기다려야 하는가?를 의미합니다.

만약 기다려야 한다면 key를 true로 저장하고 while문으로 들어갑니다.

이 때 대기 중인 프로세스를 찾습니다.

만약 프로세스가 대기중이지 않다면 프로세스의 진입을 허용하고 대기 중인 프로세스가 있다면 다음 순서로 CS에 들어갈 수 있게끔 해줍니다.

이처럼 여러개의 프로세스가 진입할 수 있게끔 TAS를 통해 지원할 수 있습니다.

 

따라서 보신 것처럼 SW에 비해 구현이 상당히 간단하다는 장점이 있습니다.

그러나 여전히 빙글 빙글 돌아야 한다는 Busy waiting라는 단점이 존재했으며 비효율적일 수 있습니다.

 

그래서 이를 해결하기 위해 OS에서도 이를 돕는 솔루션들이 등장하는데요.

제일 먼저 Spinlock입니다.

Spinlock

스핀락은 쉽게 말하면 정수형 변수입니다.

지금까지 했던 것처럼 s = s + 1;같은 연산을 하는 것이 아니라 초기화, P(), V() 연산으로만 접근 가능합니다.

이 P와 V연산은 Atomic(원자성) 연산입니다.

OS가 관리하는 이 연산들은 Preemption(선점) 되지 않도록 보장하기 때문에 한 번 실행되면 끝가지 실행되는 특징을 가지고 있습니다.

P는 물건을 꺼내가는 것, S는 물건의 개수, V는 물건을 집어 넣는 것 이렇게 이해하고 위의 그림을 살펴보겠습니다.

P를 먼저 살펴보자면, S가 0보다 적은 동안(물건이 없다면) 물건이 생기기를 기다릴 것입니다.

그러나 물건이 있다면, 이를 S - 1해주어 S를 0으로 만듭니다.

이를 한 번에 실행하도록 보장해주는 것. 이것을 P연산이라고 합니다.

V는 물건을 집어 넣는 것이기 때문에 S = S + 1;이라고 이해하시면 되겠습니다.

 

어떻게 쓰일 수 있는지 한 번 살펴보겠습니다.

만약 이해가 어렵다면 P는 문을 잠그는 것, V는 문을 여는 것으로 치환해서 이해해봅시다.

그럼 어떻게 동작되는지 한 번 봅시다.

처음에 active를 1로 설정했습니다.

그럼 물건이 있는 상태이므로 Pi에서 P가 active이므로 CS로 물건이 들어갑니다.

그리고 V가 실행되고 active는 0이 됩니다.

이후 Pj가 들어오고 P가 실행되어 다시 active가 1이되고 CS에 들어가서 일을 하게 됩니다.

말씀드린 것처럼 P연산은 Preemption이 보장되기 때문에 누구의 개입이나 선점 없이 쭉 이어가게 됩니다.

그러므로 ME의 문제(Mutual Exclusion)를 간단히 해결할 수 있겠습니다.

이처럼 Software에서 어렵게 접근을 해왔었는데 OS가 도와주니까 정말 간단히 해결이 되었습니다.

그렇다고 SW솔루션이 필요 없는 것은 아닙니다.

어쩌면 이런 과정이 있었기에 더더욱 운영체제가 Support하는 기능도 등장하고 운영체제도 발전해왔습니다.

 

그러나 스핀락은 CPU가 최소 2개 이상일 때 사용가능하다는 단점을 가지고 있습니다.

Pi와 pJ가 동시에 돈다고 가정을 해야만 위의 로직이 성립을 할 수 있기 때문입니다.

그리고 스핀락도 위에서 살펴보았듯이 여전히 Busy waiting이 존재하기 때문에 이를 해결할 또다시 새로운 솔루션인 Semaphore가 등장합니다.

 

자 요약하자면 위의 스핀락은 P,V를 OS가 보장해 줌으로써 ME를 해결해주었지만 여전히 Busy Witing이라는 현상이 잔재했습니다.

그래서 다익스트라가 제안한 Semaphore에 대해 알아보겠습니다.

이 솔루션은 Busy waiting을 해결하기 위해 만들어졌습니다.

무려 1965년에 말입니다.

 

앞에서 정수의 변수를 사용했다면 다익스트라는 S를 음이 아닌 정수형 변수로 보았습니다.

스핀락과 마찬가지로 초기화, P, V로만 연산가능하다는 비슷한 방식을 채택합니다.

다익스트라는 이 솔루션을 '차단기'라는 개념에 유사하게 해결했습니다. (실제로 세마포어 뜻이 차단기)

P는 검사, V는 증가의 개념으로서 사용을 했는데, 여기까지는 스핀락과 상당히 유사합니다.

하지만 결정적인 차이는 여기서 드러납니다.

-> 세마포어는 임의의 변수 S마다에 Ready Queue 하나를 할당 합니다. (중요)

이게 어떻게 Busy waiting을 해결하는지 한 번 알아보겠습니다.

세마포어는 두 가지로 구분해볼 수 있는데요.

하나는 0과 1의 종류만 가지는 세마포어를 Binary semaphore, 0이상의 정수만 다루는 것을 Counting semaphore라고 합니다.

바이너리 세마포어는 상호배제나 프로세스 동기화 문제들에 해결하는데 다루고 카운팅 세마포어는 생산자-소비자 문제 등에서 해결하기 위해 등장합니다. 나중에 자세하게 나올테니 일단 개념만 짚고 넘어가곘습니다.

그래서 세마포어를 접근하는 연산자를 먼저 자세히 알아보겠습니다.

초기화 연산은 스핀락과 똑같습니다.

중요한 것은 P, V입니다.

P연산은 만약 S가 0보다 크다면(물건이 있다면) S = S - 1;을 시행하고 아니라면 (물건이 없을 때) Queue에 대기시킵니다. 스핀락이었으면 이를 계속 뱅뱅 돌렸을텐데 세마포어는 그렇지 않고 대기실에 기다리고만 있게 합니다.

어쩌면 프로세스라 생각하면 Block된 상태라고 이해할 수 있겠습니다.

이제 V연산이 시행될건데, (E거꾸로 쓰면 어떤입니다) 어떤 프로세스가 큐에 있다면 그것 중 하나를 깨우고 아니라면, (아무도 없다면) S에 S+1을 해줍니다.

이것이 Semaphore의 기본 연산 방식이며 스핀락과 아주 큰 차이입니다.

마찬가지로 모두가 indivisible 연산이며 이것 역시 OS가 Support하며 (os가 보장) 전체가 한 cycle에 수행됩니다.

 

그럼 이것들을 이용해서 어떻게 문제를 해결할 수 있을까요?

실제 위의 windows사진을 보시면 Create뒤에 세마포어 붙어있는걸 보시면, 실제로 운영체제에 어떤 솔루션이 사용되고 있는지 알 수 있습니다.

알아두시면 많이 도움이 될 것입니다.

 

다음은 세마포어로 해결 가능한 문제들에 대해 구체적으로 알아보겠습니다.

 

 

 

제일 먼저 Mutual Exclusion (ME) 입니다.

만약 Pi가 Queue 상태에 들어가서 진입 대기중이라면, 프로세스가 종료된 Pj가 와서 Pi를 깨워주고 (wake up) Pi가 프로세스가 실행되게 했습니다.

아주 간단하지요? 넘어가겠습니다.

이른바 프로세스 동기화 문제는 어떻게 해결할 수 있을까요?

그림에서 나와있는 것처럼 Pi는 Pj가 Lj지점을 통과할 때 까지 Li지점에서 대기하도록 OS에서 지원합니다.

그래서 구현하고자 한다면 이렇게 그려집니다.

말씀드렸다시피 P는 검사이고 V는 반납이었습니다.

만약 sync에 0으로 setup했을 때, (물건이 없는 상태) 이 물건을 Pj가 들고있다고 해보겠습니다.

그럼 이 Pi는 P(sync)를 통해 물건이 반납된 후에 지나가야 합니다.

따라서 Pj는 V(sync)를 통해 물건을 반납함으로써 sync는 1이되고 그 때 되어서야 P연산이 실행되어 Pi가 실행됩니다.

 

다음 문제를 살펴보겠습니다.

굉장히 유명하고 또 재미있는 문제입니다.

 

생산자는 무언갈 생산하는 느낌으로 이해해봅시다.

그러므로 왼쪽의 라인 프린터 드라이버, 컴파일러, 어셈블러를 생산자 프로세스,

오른쪽의 라인 프린터, 어셈블러, 로더를 소비자 프로세스라고 해봅시다.

일단 single buffer에 대해 생각해보겠습니다.

싱글 버퍼이기 때문에 여러 명이 동시에 접근할 수 없고, 한 명이 한 번에 접근해야 합니다.

제일 위의 공유 변수에 consumed, produced, buffer를 선언했습니다.

consumed는 소비되었는지, produced는 생산되었는지를 확인하는 변수입니다.

밑의 Pi에서, 먼저 새로운 메세지를 생성해서 넣으려고 합니다.

그럼 제일 먼저 무엇을 확인할까요?

네, buffer가 비었는지(소비를 했는지)를 확인합니다.

consumed가 1이면, consumed를 0으로 바꾸고 buffer를 놓습니다.

그리고 produced를 1로 바꿉니다.(자기가 생산함)

이후 소비자 Pj로 들어갑니다.

제일 먼저 produced가 생산 되었는지 묻습니다.

만약 생산되었따면 buffer를 놓고 V를 사용하여  consumed를 1로 바꿉니다.

따라서 정리를 하자면 consumed는 1로 시작해서, 1 -> 0 -> 1 순서로 바뀌고

produced는 0으로 시작해서 0 -> 1 -> 0으로 끝나며 둘이 서로 대칭되는 관계를 보여줍니다.

 

그럼 이제 버퍼가 여러 개일 경우를 풀어보겠습니다.

수학으로 쉽게 생각하면 원순열에 가까운 모양새입니다.

저 원을 계속 뱅뱅 돌면서 in과 out에 물건을 놓고 뺍니다. (컨테이너 벨트와 비슷함)

이 문제일 경우는 생산자도 여러 명, 소비자도 여러 명입니다.

nutexP 와 mutexC는 상호배제의 생산자, 상호배제의 소비자를 의미합니다.

Pi는 여러 명일수 있으므로 한 번에 한 명만 일할 수 있습니다.

마찬가지로 소비자도 한 번에 한 명만 일할 수 있습니다.

일단 Pi가 들어왔다고 가정해보겠습니다.

그럼 Pi는 물을 것입니다. 공간 있어?? 라고 묻습니다. (nrempty)

공간이 없으면 공간이 생길 때까지 대기합니다.

그러므로 P(nrempty)가 0보다 크면 안으로 들어가게 되는데, 내가 놓을 buffer에 물건을 놓고 in의 물건을 (in+1)mod N으로 갱신합니다.

mod는 N을 나누고 뺀 나머지라고 생각하시면 되겠습니다.

그리고 nrfull을 V연산을 실행하여 +1 시켜줍니다. (스핀락의 V, P를 사용)

 

이제 소비자 입장에서 살펴보겠습니다.

제일 먼저 nrfull인지 (물건 있는지?)를 묻습니다.

만약 0보다 크다면 m에 들어가서 물건을 꺼내고 out +1modN으로 갱신하고, nrempty를 +1해줍니다.

 

정리하자면 생산자는 생산자 중 한 명만 일해야 하고 소비자도 소비자 중 한 명만 일해야 했습니다.

그래서 생산자는 들어갈 때 공간이 잇는지 확인하고 소비자는 물건이 있는지 확인을 합니다.

만약 물건이 없으면 대기실에 있을 것이고 열심히 생산한 다음에 V연산에서 물건이 생산됐으면 물건을 기다리고 있는지 볼테고 대기하는 사람이 있으면 Pj를 wake-up해주고 나올테고, 기다리는 사람이 없다면 nrfull에다가 +1을 해주고 다음에 물건을 가지러 온 애가 가지러 올 수있도록 만들어 줍니다.

 

이번에는 Reader - Writer problem에 대해 알아보겠습니다.

Reader 는 데이터를 읽기 연산만 수행하고, Writer는 데이터를 갱신하는 연산만 수행합니다.

Writer는 여러 명이 쓰면 난리가 나겠죠? 그래서 일반적으로 Writer는 한 명만 쓰는 것을 원칙으로 합니다.

또한 Reader들은 동시에 데이터에 접근할 수 있습니다. 그러나 Writer는 동시에 데이터 접근할 경우 상호배제가 꼭 필요하겠습니다.

그래서 Reader와 Writer에 대해 각각 우선권을 부여하면서, 이것들을 해결하는 방법에 대해 알아보겠습니다.

일단 Reader가 우선권을 가지는 상황에 대해 알아보겠습니다.

wmutex는 Writer + 상호배제 + x(동시에 들어가는거 x)이고 

rmutex는 Reader + 상호배제 + x(동시에 들어가는거 x)를 의미합니다.

nreaders는 Reader가 몇 명인지를 나타냅니다.

Writer를 먼저 보면, wmutex가 1일 때(아무도 안쓸 때) writer 연산을 수행하고, 0으로 만듭니다. 이후 V를 통해 다시 1로 만들고 종료됩니다.

 

Reader쪽을 살펴보면, 읽기 조금 어렵기 때문에 P와 V를 한 세트, 다음의 P와 V를 한 세트로 나누어서 살펴봅시다.

최초의 P와 V내에서, (1단계) 처음에 nreader를 체크합니다.

만약 0명이면 wmutex를 P로 실행합니다.(내가 읽을테니까 w는 쓰지마)

그리고 만약 nreaders > 0 이면 누군가 작업을 했다는 것이므로 P연산을 시행하지 않습니다.

그리고 nreader를 +1 시켜줍니다. 여기까지가 모두 CS에 들어갑니다.

이후 2단계로 진입을 합니다. 2단계는 사후 단계로서 연산을 수행하고 나갈 때 작업을 의미합니다.

따라서 nreader를 -1 해주고 만약 nreaders가 0이면 V(wmutex)를 실행하는데, wmutex를 0으로 만듭니다.

 

자 이 세마포어의 가장 큰 특징은 대기실이 있다는 것입니다.

즉, Busy waiting 문제가 해결되었습니다. 

하지만 남아있는 한 가지 문제점이 남아있습니다.

V연산을 할 때, 누군가 기다리고 있다면 wake-up해주는데, 위를 잘 보시면 wake up one of them. 즉, wake-up 순서가 비결정적이라는 문제가 있습니다. 

이로 인해 무한 대기 현상인 Starvation problem 현상도 일어날 수 있습니다.

그래서 다음 포스팅에선, 이를 해결할 새로운 솔루션을 소개해드리겠습니다.

감사합니다.