Operating System - Mutual Exclusion

안녕하세요 :)

운영체제를 주제로 한 다섯번째 포스팅은 Mutual Exclusion(상호배제) 에대하여 다루어 보겠습니다.

 

이번 포스팅에서는 공유 자원에서의 충돌을 방지 해주기 위한 상호 배제와 이에 관련한 내용에 대하여 다루어볼것입니다. 예제로 비교적 C언어 코드가 많이 사용될 예정입니다.

 

먼저 이번장을 들어가기전 꼭 알아두어야 할 용어들이 몇가지 있습니다. 그 용어들을 정리해보겠습니다.

-atomic operation, 아토믹 하면 원자의 이런뜻입니다. 쪼개지지가 않는 operation을 말합니다.

-critical section, 프로세스내의 코드 영역으로 공유자원(네트워크 프린터 같은)을 엑세스하는 부분을 말합니다.

-deadlook, 2개 이상의 프로세스가 전진하지 못하는 상황, 어영부영 기다리기만한다.

-livelook, 상태만 변화 시키며 프로세스의 전체적인 실행 사이클에서의 전진은 없는경우 (레디 러닝 왔다갔다)

-mutual exclusion, 크리티컬 섹션에 진입시 또다른 프로세스가 크리티컬 섹션에 들어가면 안된다. 라는 상호배제의 조건

-starvation, 굶어 죽은, runable 상태인데 우선순위가 낮아서 계속 무시되는 경우

-race condition, 공유변수가 여러 상황에 따라 달라지는것, 수행순서에 따라 결과가 달라짐

 

mutual exclusion)

상호 배제를 말한다. 어떠한 프로세스가 크리티컬섹션에 들어가있을경우 다른 프로세스의 접근을 차단함.

 

race condition)

먼저 공유되는 변수 a가 있다고 가정하겠습니다. 이 a는 프로세스 X ,프로세스 Y두개의 프로세스 사이에서 공유되고있습니다.

X라는 프로세스는 변수 a에 1을 더해서 출력하는 프로세스이고 프로세스 Y는 10을 더해서 출력하는 프로세스입니다.

X가 a변수에 1을 더해서 출력하려는순간 clock인터럽트가 발생해 Y에게 권한이 넘겨져 버렸습니다...

그럼 Y는 a변수에 10을더해서 출력하고 종료 되었고 다시 권한은 X에게 넘겨졌습니다. 그리고 X는 남은 작업인 출력을 해보니 원래 하여던 더하기 1이 아닌 더하기 11이 되어버렸습니다. 

 

이러한 충돌은 같은 글로벌 변수를 사용하고 같은 메모리를 공유하기때문에 발생한 문제입니다

충돌이 발생했을 경우 프로세스간에는 세가지의 경우로 문제를 해결하는데 그것은 다음과 같습니다.

 

1. 무조건적인 경쟁(processes unaware of each other) 리소스에대한 무조건적인 경쟁이 이루어짐

2. 공유는하지만 대상은 모름(processes indirectly aware) 간접적인 공유

3. 대상을 PID로 정확히 알고 공유(processes directly aware) 직접적인 커뮤니케이션

 

processes unaware of each other)

이러한 상태에서는 운영체제가 모두 알아서 해주고 리소스는 무조건적인 경쟁을 통해 해결된다.

이상태에서는 mutual exclusion을 운영체제가 해결해주기때문에 유저는 따로 신경쓸 부분이 없고 그과정에서 부수적으로 데드락과 스타베이션이 발생할수 있다.

예를들어 프린터의 사용은 운영체제가 하나의 프로세스만 사용할수있게 보장하기 떄문에 여러 프로그램에서 프린터로 작업을 걸었을때 문장이나 글자가 막 섞여서 안나오고 프로그램 하나하나씩 요청된 작업이 수행되는것을 확인할수 있다.

 

 

processes indirectly aware)

이상태에서 프로세스는 데이터를 공유하며 협력합니다. 하지만 정확히 어떤프로세스와 데이터를 공유하고 있는지는 모릅니다.

이런경우  mutual exclusion 을 운영체재가 해결해주지 않기 떄문에 크리티컬 섹션에 들어가기전후로 보장이 필요합니다.

 

 

processes directly aware)

이경우 상대방의 PID를 정확하게 알기 때문에 따로 mutual exclusion 문제가 발생하지 않습니다. 또, 프로세스간의 통신시 공유되는것이 없습니다.

 

 

mutual exclusion보장해야 하지만, 조건이 6가지 존재합니다 그 조건은 다음과 같습니다.

-오직 하나의 프로세스가 크리티컬섹션에 들어가야한다

-크리티컬 섹션에 있지 않은 프로세스는 다른 프로세스의 동작을 방해해서는 안된다.

-mutual exclusion을 보장한다고 데드락이나 스타베이션을 방치하면 안된다. 스타베이션의 경우 레디큐에서 오래 기다린다면 중요도를 올려주는 방법등

-크리티컬 섹션이 비어있다면, 크리티컬섹션에 들어가려는 프로세스를 막으면 안된다.

-프로세스 속도나 프로세스 개수와 관련된 다른 가정이 있어서는 안된다.

-크리티컬섹션에 들어가서 무한히 머무를수는 없다

 

그러면 이러한 상호배제를 수행하는 방법은 어떤것이 있을까요? 

1. 유저가 짠 프로그램을 이용한다 -> dekker's 알고리즘, 소프트웨어적인 해결(너무 복잡해서 사용x)

2. 하드웨어의 도움을 받는다

3. 운영체제 또는 프로그래밍 언어에 도움을 받는 매커니즘을 이용한다,

(이것이 앞어 이야기한 세가지방법semaphore,monitor,message passing)

 

하드웨어의 도움을 받는다 

-하드웨어의 도움을 받는 첫번째 방법은 인터럽트를 disable 시키는 것입니다 정말 간단하고 무식하지만 가능합니다.

  만약 인터럽트를 무시한다면 프로세스를 바꾸는 어떠한 인터럽트도 허용되지 않을것입니다. 대표적인 예로 클럭 인터    럽트도 말입니다. 그러면 하나의 프로세스가 CPU사용을 독점하기 때문에 크리티컬섹션또한 독점할수 있을것입니다.

  하지만 프로세서의 활용도가 낮아져 효율적이지 않고 멀티프로새서환경에서는 해결되는 방안이 아닙니다.

  코드는 다음과 같습니다.

 

ex) entercritical (a);

   do something for a

  exitcritical(a);

 

-두번째 방법은 특별한 하드웨어적 명령을 사용하는방법입니다(special machine instruction) 한싸이클의 명령을 사용할것인데 이 특별한 명령은 수행하는동안 인터럽트를 허용하지 않습니다. 그 방법으로는 compare&swap 과 exchange 가 있습니다

 

compare & swap code

함수의 인자로 int형 세가지를 받습니다. 간단한 비교연산인데 원리는 간단히 이렇습니다.

첫번째 인자와 두번째 인자를 비교후 같을시 세번째인자에 그 값을 저장한다.

 

구체적 코드는 아래와 같습니다.

 

bolt 라는 글로벌 변수를 선언하여 크리티컬섹션에 들어가면 값을 1로바꾸고 빠져나올땐 값을 0으로 돌려놓습니다. 그동안 그 섹션에 접근하려는 다른프로세스는 계속 조건비교연산을 하며 현재의 bolt값이 0이 되기를 기다리다가 이전 프로세스가 섹션을 빠져나와 값을 0으로 돌려놓으면 그때 진입후 값을 1로 바꿉니다.

 

장점 : compare & swap 을 사용하면 여러개의 크리티컬 섹션이 보장됩니다 (한섹션당 하나의 고유한 글로벌 변수를 선언, 만약 크리티컬 섹션이 3개라면 bolt와 같은 변수도 3가지), 그리고 멀티 프로세서 환경에서도 사용이 가능합니다. 글로벌 변수는 메모리의 영역에서 공유되는 것이기 때문에 프로페서는 혼동을 겪지 않습니다.

 

단점: BUSY-WAIT, 비교연산 조건문을 사용하는것이기 때문에 크리티컬섹션이 사용되고 있을시 다른 프로세스들은 계속 조건을 비교연산하고 있어야 하기 때문입니다.

 

 

운영체제 또는 프로그래밍 언어에 도움을 받는 매커니즘을 이용한다,

- semaphore, monitor, message passing

 

 

semaphore

아주 간단하게는 그냥 스페셜 변수 하나입니다.

 

프로세스들 사이의 시그널을 주고 받기 위한 용도이다.