[OS] 4. Concurrency : Mutual Exlusion and Synchronization

본 게시글은 PC버전에 최적화 되어 있습니다.

 

Operating Systems, Internals and Design Principles (9th Ed.), William Stallings, Pearson, 2017

충남대학교 컴퓨터공학과 최훈 교수님의 '운영체제 및 실습'을 참고하였습니다.

1. Principles of Concurrency

컴퓨터 내부에서 다양한 프로세스 쓰레드가 실행되는데 한정된 자원을 갖고 동시다발적으로 작동하므로 충돌할 가능성이 있음.

1) 용어 정리

1. Race Condition : 경쟁 상태

두 개 이상의 프로세스 혹은 쓰레드가 공유된 자원을 읽고 쓰는 과정에서 어떤 결과가 나올지 모르는 상황

 

2. Mutual Exclusion : 상호 배제

하나의 프로세스가 공유된 자원에 접근하면 다른 프로세스는 접근하지 못하게 하는 것 -> Race Condition의 해결법

 

3. Critical Section : 임계 구역

Race Condition이 발생하는 부분으로 Mutually Exclusive 해야하는 부분, 공유된 자원이 존재하는 부분

 

-> Critical Section이 Mutually Exclusive 하지 않으면, Race Condition이 발생한다.

 

4. Starvation : 빈곤 상태

자원이 오랜시간 할당되지 않고 계속 기다리는 상황

 

5. DeadLock : 교착 상태

둘 이상의 프로세스가 다음 상태로 진행할 수 없는 상황 -> 모든 프로세스가 Starvation 상태

2) Multiprocessor의 Race Condition

 

하나의 자원에 접근하려고 할 때

두 개의 프로세스

위의 코드처럼 두 개의 프로세스가 getchar()를 통해 입력을 받고 이를 출력하려고 한다.

P1이 먼저 실행되어 입력을 받고 chout에 저장을 했는데 time slice가 끝나서

P2가 실행되고 입력을 진행하고 chout에 저장을 했는데 또 time slice가 끝나서 P1으로 다시 왔다.

이 경우에는 어떤 값이 출력될까?

 

이처럼 공유 자원에 동시에 접근하는 경우 Race Condition이 발생할 수 있다.

3) Producer / Consumer Problem

counter++와 counter--는 크리티컬하게 동작해야한다.

 

Shared Data

shared memory 영억에 공유 자원이 할당되었다고 가정하자.

Producer는 counter를 증가하는 쪽으로, Consumer는 counter를 감소하는 쪽으로 코드가 구현되었을 때

특정 동작을 진행하다가 time slice가 발생해 다른 프로세스로 넘어가게 되면

공유 자원에서 Race Condition이 발생할 수 있다.

 

Race Condition

4와 6중 어느값이 출력될지 모르게 된다. (Producer와 Consumer 중 먼저 실행되는 쪽)

 

이를 해결하기 위해서는 Critical Section, 즉 공유 자원이 존재하는 구역을 Atomic하게 실행할 필요가 있다.

여기서 말하는 Atomic이란, Interrupt(time slice)에 의해 프로세스가 전환되지 않도록 Interrupt를 비활성화 시키는 것이다.

좋은 방법처럼 보인다.

But, 특수한 상황을 고려해보자.

짧은 경우에는 상관이 없지만 Critical Section을 사용자가, 또는 해커가 엄청 길게 구현한 경우 계속적으로

Interrupt가 비활성화되어서 프로세스는 현재상태를 계속 반복하며 영영 다른 프로세스를 실행할 수 없을 수도 있다.

 

그래서 필요한 것이 담장, Fence이다.

Critical Section 주변에 담장을 쳐서 담장 안으로는 하나만 들어갈 수 있게 하자는 것이 두 번째 방법.

4) Critical Section 문제를 해결하기 위한 3가지 조건

1. Mutual Exclusion : 상호 배제

어느 순간에 Critical Section에는 하나의 프로세스만 들어가야 한다.

 

2. Progress : 진행

Critical Section에 아무도 없는 경우 들어갈 수 있어야 한다.

 

3. Bounded Waiting : 한정적인 기다림

다른 프로세스가 Critical Section에 들어가 있는 경우 이를 기다리되, 유한한 시간만큼 기다려야 한다. -> 무한정 기다리면 안됨.

2. Software Solution

 

Critical Section

Entry Section : Critical Section으로 들어가기 위한 조건

1) Turn 이용

 

1. Turn 변수 이용

Turn 변수를 선언하여 이를 통해 해결. Mutual Exclusion은 해결, 하지만 Progress는 만족하지 못한다.

예를 들어 turn의 초기상태가 0이라고 가정해보자.

프로세스 스케쥴링에 의해 P1이 실행된 경우 while문의 조건에 만족하면서 무한정 기다리는 Busy Waiting 상태가 되버린다. Critical Section에 다른 프로세스가 존재하지 않는데 들어갈 수 없으므로 Progress을 만족하지 못하는 것이다.

2) Peterson's 알고리즘

Turn 변수를 이용하면 Progress를 만족하지 못하여 Critical Section을 해결할 수 없다.

이를 해결하기 위해 등장한 알고리즘으로 두 개의 프로세스인 경우에만 해결 가능하다.

 

2. Peterson's 알고리즘

Turn 변수와 또 다른 변수 Flag를 선언하여 Critical Section 문제를 해결.

프로세스 스케쥴링에 의해 P0가 실행된 경우 flag[0] = true, turn = 1가 된다.

그러던 중 time slice에 의해 P1으로 전환된 경우 이 변수를 다시 설정함으로써

Entry Section을 지나치고 Critical Section으로 진행할 수 있게 된다.

어떤 프로세스가 먼저 실행되던 혹은 실행 도중  Context Switch에 의해 다른 프로세스로 전환이 되던

무조건적으로 Critical Section에 들어갈 수 있게 된다.

3) Bakery 알고리즘

Peterson's 알고리즘이 두 개의 프로세스일 경우에만 해결 가능해서 이를 확장한 버전.

3개 이상의 프로세스에도 적용이 가능하다.

 

3. Bakery 알고리즘

3. Hardware Solution

특수한 Atomic Instruction을 정의해서 사용.

1) Test And Set

 

Testset 함수

 

인자가 0인 경우 1로 바꿔주고 True를 리턴, 1인 경우 False를 리턴.

 

Code

 

bolt의 초기값은 0

예를 들어 프로세스 2번이 먼저 실행됐다고 가정하자.

Entry Section에서 testset(0)을 호출하여 bolt를 1로 바꿔주고 True를 리턴한다.

while문 조건에 해당하지 않으므로 Critical Section에 접근할 수 있게 된다.

이후 time slice에 의해 다른 프로세스로 전환되었다고 가정하자.

bolt는 현재 1이므로 testset(1)은 False를 리턴한다.

while문 조건에 해당하므로 while문을 계속 돌게 된다.

프로세스 스케쥴링에 의해 이전 프로세스는 Busy Waiting 상태가 되고 새로운 프로세스로 전환이 된다.

만약 프로세스 2번으로 다시 돌아오게 되면 Exit Section에서 bolt가 다시 0으로 바뀌게 된다.

이렇게 되면 다른 프로세스 역시 Critical Section에 접근할 수 있게 된다.

 

어느 프로세스가 처음 실행되든 모두 Critical Section에 접근할 수 있으므로 Progress를 만족한다.

Critical Seciton에는 하나의 프로세스만 접근 가능하므로 역시 Matual Exclusive를 만족한다.

하지만, Bounded Wait는 만족하지 못한다. 프로세스 스케쥴링에 의해 선택된 프로세스가 접근하게 되고

이미 접근한 프로세스가 언제 끝날지 모르므로 만족하지 못한다.

뿐만 아니라 Busy Waiting으로 인해 메모리 낭비가 심하다.

 

이를 해결하기 위해 등장한 것이 Semaphore

2) Semaphore

값을 감소시키는 semWait()과 값을 증가시키는 semSignal()을 활용.

Busy Waiting 대신 Sleep 상태, Block 상태로 만든다.

 

semWait와 semSignal

 

1. semWait

인자 값을 -1 해주고 이 값이 0보다 작은 경우, 즉 기존의 인자가 0 이상인 경우였으므로

누군가가 공유자원을 이미 이용 중이라는 것을 알 수 있다. 

해당 프로세스를 Block Queue에 넣어준다.

 

2. semSignal

인자 값을 +1 해주고 이 값이 0 이하인 경우, 즉 기존의 인자가 -1 이하인 경우였으므로

누군가가 Block Queue에 존재한다는 것을 알 수 있다.

맨 앞에 있는 프로세스를 Ready Queue에 넣어준다.

 

semaphore

공유 자원에 접근한 경우와 그렇지 않은 경우를 표현하기 위한 세마포어 변수 s를 1로 초기화해준다.

s가 1인 경우는 아직 어떠한 프로세스도 접근하지 않은 경우이므로 프로세스를 정상적으로 실행한다.

 

Three Processes

3개의 프로세스가 실행됐을 때 Block Queue와 세마포어 변수 s의 값을 보여준다.

3) Producer / Consumer Problem using Semaphores

세마포어를 활용하여 해결할 수 있다.

 

Producer Code

Consumer Code

 

empty는 Queue의 빈 공간의 개수라고 생각하면 된다.

Producer가 물건을 생산했으므로 empty의 공간을 -1을 해준다.

이후 Critical Section에 접근하기 위해 mut_ex를 -1을 해준다.

 

이 때 time slice가 발생해서 consumer로 넘어가게 되면

counter, 즉 생산된 물건은 0이므로 -1을 하게 되면 0보다 작아지게 된다.

따라서 이 프로세서를 Block Queue에 넣어주고, mut_ex 현재 값이 0이므로 -1을 하게 되면 0보다 작아지게 된다.

이 역시 Block Queue에 넣어준다. 따라서 Critical Section에 접근할 수 없게 된다.

 

다시 Producer로 넘어오면 append()를 실시하고

다른 프로세서가 Critical Section에 접근할 수 있게 mut_ex를 +1 해준다.

counter 역시 +1을 해줌으로써 다른 프로세스가 완벽하게 접근할 수 있게 해준다.

 

세마포어는 대칭성을 띄고 있는데 아래 그림과 같다.

 

Semaphore Set

꼭, 꼭 세트를 이뤄야한다.

4. Readers / Writers Problem

Critical Section Problem의 확장 버젼

Writers만 한 명이면 되는거 아니야? 라는 느낌

 

Writer

Writers의 코드는 세마포어 코드와 비슷하다는 것을 느낄 수 있다.

 

그럼 Readers는?

 

Reader

readcount가 1이면 읽고 있는 프로세스가 있다는 의미, 따라서 semWait(wsem)을 통해 쓰는 것을 Block.

Reader가 유리한 상황.

 

이 문제 역시 세마포어끼리 세트를 이뤄야한다.

5. Monitor

고수준의 동기화 방법

Monitor

Entrance : Entry Section과 같은 역할.

이전 프로세스가 진행 중에 Context Switch가 발생하면 왼쪽 영역의 Queue에 저장하고 다른 프로세스를 받는다.

 

스크롤이 상당하다...

개인적으로 가장 재미있는 부분이였다. 처음 강의 들었을 때는 이해가 1도 안됐는데 시험 공부하려고 복습하다보니 쏙쏙 들어온다.