[08] 운영체제 - 충돌-2

안녕하세요. 오늘은 저번 시간에 이어서 충돌의 해결방안 중 하나인

Semaphore에 관해 포스팅을 해보도록 하겠습니다.

그럼 바로 시작하도록 하겠습니다.

Semaphore

Semaphore란 앞서 다뤘던 key를 얻고 반납하는 과정이 비슷한데요.

여기서는 정수형 변수 s와 중요한 두 함수인 wait(s) 와 signal(s)가 존재합니다.

그럼 두 함수의 코드를 살펴보도록 하겠습니다.

wait(s){ while s <= 0; s--;}signal(s){ s++;}

이전의 포스팅의 나온 코드들을 보신 분들이라면 조금은 감이 오실 것 같으신데요.

여기서는 s가 key의 역할을 하게 됩니다. 그리고 차이점은 s의 초깃값에 따라서 여러 프로세스가 동시에 접근이 

가능할 것이라는 것도 예측이 가능하실 것입니다. 여기서 wait(s)의 while에 의해 대기하게 되고

signal(s)의 s++을 통해 waits(s)의 while 문을 빠져나가는 것을 아실 수 있으실 겁니다.

위에서 언급하였듯이 Semaphore의 s 값에 따라 하나의 프로세스만 진입하게 하거나 다수의 프로세스가 진입하게 해줄 수 있습니다.

이러한 s의 값에 따라

- Binary Semaphore (0.. 1)

- Counting Semaphore(0.. N)

으로 나눌 수 있습니다. 이렇게 정해지는 값을 mutex라고 합니다. 그러면 실제 어떻게 적용이 되는지 살펴보도록 하겠습니다.

위와 같은 코드에 두 개의 프로세스가 동시에 접근하고 mutex가 1로 정해졌다면 상황은 다음과 같다.

P2가 먼저 진입하게 되면 wait(mutex)에 의해 mutex는 0이 되고 Critical Section이 진행되면서

Context Switching이 일어나도 mutex 가 0이기 때문에 P1 은 wait(mutex)에서 대기하게 됩니다.

P1으론 다시 Context Switching이 일어나서 Critical Section을 마저 실행하고 Signal(mutex)를

통과하면서 mutex가 다시 1이 되고 이때 비로 소야 P1이 wait(mutex)를 빠져나와 나머지 코드를 실행하게 됩니다.

그리고 Semaphore의 mutex 값을 잘 조정해주고 wait(mutex)와 signal(s)의 순서를 잘 조정해준다면

프로세스의 작업 순서를 정해줄 수 있게 됩니다.

위의 예시에서 mutex는 0으로 초기화된다면 P2는 P1의 S1 작업 이후 signal(mutex)에 의해 값이 증가되어야만

S 2로 진입할 수 있게 됩니다. 이렇게 함으로써 프로세스들의 작업 순서를 정해줄 수도 있게 됩니다.

하지만 여기서도 약간의 문제가 발생하는데요 wait(mutex)를 통해 기다리는 동안 지속해서 while 문을 통해

mutex 값을 확인하는 것 역시 CPU 자원의 낭비라고 할 수 있는데요.

이러한 현상을 Busy Waiting이라고 합니다.

Busy Waiting 현상을 보완하기 위해 나온 방법이 Blocking & Wake-Up 방식입니다.

이 방식은 여러 프로세스가 동시에 접근하고 하나의 프로세스만이 Critical Section에 진입하게 되면

나머지는 wait(mutex)에서 무한 Loop를 돌면서 대기하는 것이 아니라 Wait Queue에 들어가 대기하게 됩니다.

그리고 Ready Queue로 넘어가 Critical Section이 끝난 프로세스가 Signal(mutex)를 통해

mutex의 값을 증가시키면 Ready Queue에서 스케줄링 알고리즘에 따라 하나가 선택되어 Critical Section에 진입하여

작업을 수행하게 됩니다. 이러한 Blocking & Wake-Up 방식 또한 완벽한 것은 아닌데요.

바로 빈번한 Context Switching이 일어난다는 것입니다.  두 방식은 각각 Critical Section의 길이에 따라 선택되는데요

Critical Section이 짧으면 wait(mutex)에서 기다리는 것이 덜 부담스러운 Busy Waiting,

반대로 Critical Section이 길면 Blocking & Wake-Up 방식을 사용합니다.

Semaphore도 역시 몇 가지 문제점이 있는데요. 그 문제점은 다음과 같습니다.

1. Deadlock & Starvation

2. Priority Inversion

1. Deadlock & Starvation

-Deadlock  

Deadlock 이란 프로세스가 서로의 Signal을 기다리게 되면서 모두 무한정 대기하게 되는 현상을 말합니다. 

다음의 사진을 보시면 더욱 이해가 잘 되실 것입니다.

만약 S와 Q가 모두 1이라면 어느 프로세스가 먼저 들어오게 되더라도 wait(S)나 wait(Q)가 수행되는데 이때 S나 Q는 0이 됩니다.

그리고 그다음의 코드에서 다시 각각 wait(S)나 wait(Q)가 실행되는데 이렇게 되면 S와 Q 둘 다 0이 돼버리기 때문에 두 프로세스

모두 Critical Section에 들어가지 못하고 모두 signal을 기다리지만 이 signal은 Critical Section 뒤에 있기 때문에 무한정 대기를 합니다.

다음의 그림을 보시면 더욱 이해가 잘 되실 것입니다.

-Starvation 

Starvation은 앞에서 언급했던 Blocking & Wake-Up 방식에서 Ready Queue에 대기하고 있는 

프로세스 중 하나를 선택하는 스케줄링 과정에서 여러 이유 중 하나로 선택되지 못하여 실행되지 못하는 프로세스가 생기는 현상입니다.

2. Priority Inversion (우선순위 역전)

우선순위 역전 현상이란 간단히 말하자면 우선순위가 낮은 프로세스 때문에 우선순위가 높은 프로세스가 실행되지 않는 현상을 말합니다.

다음의 그림을 보며 이야기해보도록 하겠습니다.

숫자가 작을수록 우선순위가 높음

먼저 Sema-A는 1로 초기화되어 있고 우선순위가 5인 Process C가 실행되면서 wait에 의해 Sema-A가 0이 되고,

우선순위가 3으로 더 높은 Process B가 들어오게 되면 Process B가 실행이 되게 됩니다.

그러다가 그보다 높은 우선순위가 1인 Process A가 들어오게 되며 뉴 Process A가 실행되는데 이때 Process A가

Sema-A를 요청을 하지만 (wait을 통해) 이미 Process C에 의해 Sema-A는 0이 된 상태이므로 계속해서 대기하게 됩니다.

그리고 Context Switching(Time Quantum 등의 이유로)이 일어나 Process C보다 우선순위가 높은 프로세스가

실행된다면 (여기선 Process B) Process C는 우선순위에 밀려 계속 실행되지 않고 이로 인해 signal이 되지 않아 Process A가

실행되지 않게 됩니다. 이러한 현상을 Priority Inversion, 우선순위 역전 현상이라고 합니다.

이러한 우선순위 역전 현상을 해결하기 위한 방안도 역시 존재하는데요.

특정 프로세스가 우선순위가 높은 프로세스에서 요구하는 자원을 가지고 있을 때 그 특정 프로세스의 우선순위를 

자원을 요구하는 프로세스의 우선순위로 높여주는 방법입니다.

이러한 방법을 Priority Inheritance Protocol (우선순위 계승)이라고 합니다.

Priority Inheritance Protocol

Semaphore Classical Problems

1. Bounded-Buffer Problem

상호작용하는 두 프로세스는 buffer를 통한 데이터 주고받는데, Producer 프로세스는 데이터를 하나 만들면

buffer에 추가하고 Consumer 프로세스는 buffer에 데이터가 있으면 하나씩 가져와 처리를 합니다.

이때 buffer 안의 데이터 개수의 동기화 문제가 발생할 수 있는데 이때 Semaphore을 사용하여 해결할 수 있습니다.

세 개의 Semaphore가 존재해야 합니다.

1. Mutex : buffer의 접근을 관리하는 것으로 1로 초기화. 

2. Full : buffer의 들어가 있는 데이터의 수를 관리하는 것으로 0으로 초기화.

3. Empty : buffer의 빈 공간의 개수를 의미하는 것으로 buffer 전체 크기인 N으로 초기화.

Producer는 buffer에 빈 공간이 있는지 확인 후 buffer의 접근을 시도하고

Consumer는 buffer에 가져올 데이터가 있는지 확인 후 buffer의 접근을 시도합니다.

이때 wait(mutex)를 통해 하나의 프로세스만 buffer에 접근을 할 수 있게 되고

데이터를 집어넣거나 가져온 후에는 그에 맞는 signal을 해준 후 signal(mutex)를 통해 buffer 접근 권한을 내려놓습니다.

여기서 헷갈리지 말아야 할 것은 Context Switching은 언제 일어날지 모른다는 것이며 이 말은 한 번 데이터를 넣고

한번 가져오는 것이 아니라 여러 번 넣고 여러 번 가져올 수 있다는 뜻입니다.

2. Readers-Writers Problem

공유 데이터 공간에 대해 데이터를 입력하는 것은 하나의 Writer 프로세스만이 접근이 가능하고

데이터를 읽을 때는 여러 개의 Readers 프로세스가 접근이 가능할 때 데이터를 저장하고 읽어올 때 충돌로 인한

데이터의 불일치를 방지할 때 역시 Semaphore를 이용하여 문제를 해결할 수 있습니다.

여기서 사용되는 Semaphore 역시 세 가지가 필요합니다.

1. readcount : 현재 몇 개의 Reader 프로세스가 데이터 읽기를 시도하는지를 관리.

2. mutex : readcount의 값을 변경할 때 값의 일치성을 관리.

3. wrt :  데이터 접근에 대해 Reader와 Writer를 동시에 접근할 수 없게 관리. 

먼저 Writer는 wait(wrt)를 통해 데이터에 쓰기를 수행하기 위해서는 Reader가 현재 읽기를 수행하고 있는지 확인을 해야 하고

그렇지 않다면 데이터 쓰기를 수행합니다. 그리고 Reader가 데이터 읽기를 하기 위해서는 먼저 읽기를 하려는 Reader의 readcount를 증가시켜야 하는데 이때 readcount의 불일치를 방지하기 위해 wait(mutex)와 signal(mutex)를 위아래에 작성해줍니다.

그리고 하나의 Reader라도 읽기를 수행하고 있다면 wait(wrt)을 통해 Writer 프로세스의 접근을 막습니다.

역시 읽기 수행이 끝나고 readcount를 감소시킬 때도 wait(mutex)와 signal(mute)를 통해 데이터의 일치성을 보장해주고

더 이상 데이터 읽기를 수행하는 Reader 프로세스가 존재하지 않는다면 signal(wrt)를 통해 Writer 프로세스의 데이터 접근을 허용합니다.

Monitor

우리는 지금까지 Semaphore에 대해 알아보았는데요. 이러한 Semaphore는 충돌이나 동기화의 문제들을 해결해주지만

직접 프로그래머가 작성해주어야 하고 이로 인해 사소한 실수에도 심각한 문제를 일으킬 수 있게 됩니다. (Deadlock, Starvation, Priority Inversion 등등) 그래서 프로그래밍 언어의 설계 단계에서부터 이러한 것들을 언어 자체가 해결할 수 있게 해주는 기능이 Monitor입니다. Monitor는 동시 접근에 대한 문제는 해결해주지만 동기화에 대한 문제를 완전히 해결하지는 못하는데 

이를 해결하기 위해 도입한 것이 Condition 변수입니다. Condition 변수를 통해 프로세스들은 순서를 보장받게 됩니다.

Monitor와 Semaphore의 가장 뚜렷한 차이점은 직접 작성하냐 기능을 제공받느냐, 값에 따라 여러 프로세스가 접근할 수 있는지 아니면 오로지 하나의 프로세스만이 접근할 수 있는지 등이 있습니다.

둘의 비교는

http://stackoverflow.com/questions/7335950/semaphore-vs-monitors-whats-the-difference 

이 글을 참고하시면 도움이 되실 것입니다.

Semaphore vs. Monitors - what's the difference?

What are the major differences between a Monitor and a Semaphore?

stackoverflow.com

지금까지 충돌에 대한 해결방안들을 살펴보았는데요.

사실 작성하면서도 부족한 부분이 있는 것이 느껴졌기에 더욱 많이 공부해야 한다는 것을 깨달았습니다.

그리고 여기까지가 1차 중간고사 범위였는데요.

사실 이미 시험을 본 시점이고 상당히 시험을 못 친 것 같지만 그래도 이렇게 포스팅을 하는 것이

공부하는데 상당한 도움을 주었던 것 같습니다.

앞으로 2차 중간고사, 기말고사까지 열심히 포스팅해보도록 하겠습니다.

감사합니다.