[ OS 기초 ] 06. 프로세스 동기화, 상호배제 (2) - 상호배제 기법

1. SW solutions - 데커, 피터슨, 다익스트라 알고리즘
2. HW solutions - TAS Instruction
3. OS supported SW solutions - Spinlock, Semaphore, Eventcount & Sequencer
4. Language Level Solution - Monitor

 

00 도입

여러 프로세스가 동시에 같은 자원을 필요로 하는 상황에서 발생할 수 있는 문제를 해결하기 위해 상호 배제, 즉 임계 공간(critical section)에는 한 번에 하나의 프로세스만 들어갈 수 있도록 구현해야 함을 알 수 있었다. 이러한 상호 배제 기법에는 소프트웨어를 통한 구현, 하드웨어를 통한 구현, 운영체제의 지원을 기반으로 구현하거나 프로그래밍 언어를 통한 구현의 방법이 있다. 구체적으로 각 방식에는 어떤 기법들이 있는지 알아보았는데, 이해가 완벽히 되지 않는 부분들도 있어서 일단 핵심 위주로 정리해보았다.

 

01 SW solutions

소프트웨어를 통한 상호배제 구현 방법에는 대표적으로 데커 알고리즘, 피터슨 알고리즘, 다익스트라 알고리즘이 있다.

01-1 데커 알고리즘
- 두 개의 프로세스 간 상호 배제를 보장하는 최초의 알고리즘
- Flag, Turn 활용 : Flag의 t/f 여부에 따라 while문 진입을 결정, while문 내부에서 turn에 따라 flag를 바꾸거나 cs 진입
- Flag : CS에 진입할 때 / CS에서 나올 때
- Turn : 자신의 차례일 때 / 자신의 차례가 아닐 때(or 끝났을 때)
생각해보기 : 만약 각 단계에서 preemption이 발생했다면 어떻게 될까?

01-2 피터슨 알고리즘
- 데커 알고리즘보다 간단하게 구현할 수 있는 알고리즘
- while문의 밖에서 flag,turn을 확인하고, 상대에게 차례를 양보함 (=늦게 양보한 애가 나중에 들어감)
생각해보기 : 만약 두 개의 프로세스가 아니라 N개의 프로세스가 있다면?

01-2 다익스트라 알고리즘
- flag의 상태를 3가지로 정의함 : idle, want-in, in-CS

• idle : 진입 시도를 하지 않을 때 있을 곳 / 진입이 끝났을 때 도달하는 곳
• want-in : 진입하기위한 첫 번째 단계 - 들어갈 의사를 밝히는 곳
• in-CS : 진입하기위한 두 번째 단계 - 진입 직전에 머무르는 곳

이 진행 과정을 단계별로 간단히 살펴보면

1. flag[ 프로세스 i ] 상태를 want-in으로
2. turn을 확인 : 만약 i의 turn이 아니면, 현재 turn인 프로세스가 idle 상태가 될 때까지 돌기(while문)
3. i의 차례가 되면 flag[ 프로세스 i ] 상태를 want-in에서 in-CS로 변경
4. flag를 돌면서 만약 in-CS 상태인 프로세스가 없다면 while문을 빠져나와 i 가 CS로 들어가고, 만약 in-CS 상태인 프로세스가 존재한다면 또 계속 돌이(while문)

흐름을 잘 살펴보면, while 문에서 빠져나오는 순서는 따로 정해져 있는 게 아니다. 따라서 대기 중인 상태에서 계속 while문을 돌아야 하는 Busy waiting 문제가 발생하거나, preemption 문제도 생길 수 있음을 알 수 있다.

 

이러한 소프트웨어 기반 알고리즘의 경우 속도가 느리고 구현이 복잡하다는 단점이 있다. 또 수행 도중 preemption이 발생할 수도 있으며 운영체제가 이런 인터럽트를 막아준다고 하더라도 이로인한 오버헤드가 발생한다. 이에 더해 Busy waiting, 즉 프로세스가 cs로 진입할 수 있는 차례가 되기까지 계속해서 대기하며 돌아야 하는 문제도 있다. 

반면, 다음에 살펴 볼 하드웨어 솔루션의 경우 하드웨어가 직접 preemption을 방지하여 한 번에 알고리즘이 수행될 수 있도록(기계어 기반) 상황을 보장해줌으로써 소프트웨어 솔루션의 일부 문제를 해결할 수 있다.

 

02 HW solutions

하드웨어 솔루션은 간단히 말해 하드웨어가 직접 나서서 이 문제를 해결해준다는 것이다. 구체적으로는 하드웨어가 기계어인 TAS(Test And Set Instruction)을 만들어줘서 실행 중 방해를 받지 않도록 보장해준다.

02-1 TAS Instruction
- 핵심 : 한 번에 수행된다 (how? TAS라는 한 번에 수행되는 기계어를 만들어줘서)
- 원리 : 타겟에 들어갈 값을 인자로 받는다 => 원래 타겟의 값을 temp에 넣어준다 => 인자로 받은 값을 타겟에 넣는다 => temp의 값을 리턴한다
- 원리대로라면 두 프로세스의 상호배제를 보장할 수 있지만 만약 프로세스가 3개 이상일 때는 Bounded Waiting 조건을 위배할 수도 있다.

ex ) 프로세스1 이 실행 중이고 프로세스 2, 프로세스 3이 대기 중이라고 가정하면, 프로세스 1 이 cs를 나가면서 상태를 변경해준 뒤 다음 순서로 프로세스 2가 들어갈지, 프로세스 3이 들어갈지는 정해져 있지 않다. 결국 누가 while문에서 먼저 빠져나오는지에 따라 최악의 경우 한 프로세스가 오랫동안 들어가지 못할 수도 있다. 
=> 이런 상황에서는 waiting, key, lock을 활용해 대기중인 프로세스들 중 실행 중인 프로세스와 가장 가까운 하나를 진입시켜서 순서대로 프로세스를 수행시키는 방법이 있다.

 

하드웨어 솔루션은 구현이 비교적 간단하고, 기계어를 통해 preemption으로 인한 인터럽트 문제는 해결했지만 이 또한 busy waiting 문제가 있다. 이를 해결하기 위해서 OS가 개입한 Semaphore 기법을 사용할 수 있다.

 

03 OS supported SW solutions

03-1 Spinlock
- 정수형 변수 S, 그리고 이 S에 유일하게 접근할 수 있는 P() 연산과 V() 연산을 활용해 상호 배제를 구현하는 방법
(이때 P,V연산은 모두 atomic 한 연산으로 도중에 preemption이 발생하지 않는다)
- 쉽게 비유적으로 표현하자면 S는 물건의 개수, P는 물건을 꺼내가는 상황, V는 물건을 집어넣는 상황
- 또 다른 비유로는 CS는 화장실, S는 화장실의 키, P는 키를 꺼내와 화장실에 들어가는 상황, V는 화장실에서 나와 키를 제자리에 넣어두는 상황

• P연산 관점 - 꺼내갈 물건이 없다면? : 생길 때까지 꺼내갈 수 없음
• P연산 관점 - 꺼내갈 물건이 있다면? : 물건을 가져감 = S의 개수 -1
• V연산 관점 - 물건을 하나 집어넣을 수 있음 = S의 개수 +1

spinlock은 os가 P,V연산이 방해 없이 한 번에 수행될 수 있게끔 보장해주지만 프로세서가 하나인 경우에는 사용할 수 없어 멀티 프로세서 시스템에서만 사용할 수 있으며, busy waiting 문제를 단점으로 갖는다.

 

03-2 Semaphore
- 다익스트라가 제안한 또 다른 기법으로 busy waiting 문제를 해결한 상호 배제 기법이다
- 세마포어는 의미대로 '차단기'의 역할을 하는 변수를 활용하는 방법
- 마찬가지로 정수형 변수 S(단, S >=0), 두 개의 초기화 연산 P(), V() 
- spinlock 과의 차이점 : 임의의 변수 S 하나에 ready queue(대기실) 하나가 할당됨★★★ 

semaphore의 진행 과정을 간단히 살펴보면 다음과 같다.

• 가져가려고 하는 물건(S)이 있는가?
• 있으면 꺼내서 안으로 들어가고(S <- S-1)
• 없으면 S에 할당된 레디큐에서 기다리겠다(S를 가져가기 위한 대기실)
  참고 ) Spinlock이라면 S가 없을 때 spin 하면서 lock 상태가 될 때까지 돌면서 기다림
• S를 다 쓰고 난 다른 프로세스가 V연산을 수행
• V연산이 수행되면서 S에 할당된 레디큐에서 대기하고있는 프로세스가 있는지 확인
  있으면? wake up 해서 그 프로세스에게 차례가 되었음을 알림
  없으면? S에 다시 물건을 넣어놓기 (S <- S+1)

여기서 핵심은 계속 lock 상태를 기다리며 while문을 돌아야 하는 spinlock과는 달리 semaphore는 대기실에서 편하게 대기한 뒤 다른 프로세스가 깨워주기를 기다리기만 하면 된다는 점. 세마포어는 다음과 같은 상황에서 활용될 수 있다.

• Binary semaphore : 0,1 <= 상호 배제에 활용
• counting semaphore : 0 이상 <= 생산자 소비자 문제 해결에 주로 사용

 

특히 Semaphore를 통해서 다음과 같은 다양한 동기화 문제를 해결할 수 있다.

• 상호 배제 문제
• 프로세스 동기화 문제
• 생산자-소비자 문제
• Reader-Writer 문제
• Dining philosopher 문제
• 기타

 

03-3 Eventcount / Sequencer
- 이벤트 카운트 및 시퀀서의 핵심은 순서에 맞춰서 프로세스를 깨워준다는 것으로 은행의 번호표에 비유할 수 있다.
- Sequencer : 정수형 변수로 은행의 번호 뽑는 기계에 비유할 수 있다. 0으로 초기화되어 있고 숫자가 오르면서 순서를 만들어낸다. 이때 숫자는 올라가기만 해서 사건의 순서를 유지할 수 있다. Sequencer의 값은 ticket() 연산으로 접근할 수 있다.
- Ticket : Sequencer 값을 바꿔주는 연산으로 Ticket 연산이 수행되면 현재의 sequencer 번호가 반환되고 이후 sequencer에 +1 연산을 수행한다.
- Eventcount : 정수형 변수로 Sequencer처럼 줄어들지 않으며 은행원이 부르는 번호에 비유할 수 있다. 즉, 지금까지 처리한 업무의 수를 의미하는 변수이며 read(), advance, await 세 연산자로만 접근할 수 있다.

• read(E) : 현재 번호를 읽는 것
• advance(E) : 다음 차례 호출. 번호가 1 증가하는 연산. 이때 특정 프로세스의 번호가 울리면 wake up 됨
• await(E, v) : v는 정수형 변수. E는 내 차례 v는 현재 차례. 내 번호가 더 크다면 더 기다려야 함

이벤트 카운트를 활용하면 순서를 부여할 수 있어 세마포어의 무한 대기 문제, starvation을 해결할 수 있다.

 

이처럼 운영체제가 개입하는 상호 배제 기법들은 유연(flexible)하지만 동시에 복잡하기도 하다. 따라서 활용하기 어렵고 에러가 발생할 가능성도 높다. 이러한 기법들을 low-level 메커니즘이라 부른다면, 프로그래밍 언어 차원에서 지원하는 상호배제 기법들은 high-level 메커니즘으로 이를 활용하면 좀 더 쉽게 상호 배제를 구현할 수 있다.

 

04 Language level solution

04-1 Monitor
- 쉽게 표현하자면 critical data, critical section을 한 공간에 모아놓고 하나의 프로세스만 공간을 이용할 수 있게끔 구현해 놓은 공간이라고 볼 수 있음
- 특별한 변수와 wait(), signal(), operations() 연산을 통해 구현
- 모니터의 구조

• 엔트리큐 : function 마다 한 개씩 존재
• 특징 : 상호 배제, 정보 은폐성
• 컨디션 큐(조건 큐) : 특정 조건을 기다리는 대기실
• 시그널러 큐(신호 제공자 큐) : 전화부스처럼 다른 프로세스에 시그널을 보내는 공간. 모니터에는 항상 하나의 신호제공자 큐가 존재하고, 여기서 컨디션 큐로 시그널 명령을 보냄

모니터를 통해 자원 할당 문제, 사이즈가 n인 원형 큐의 생산자-소비자 문제, Dining Philosopher 문제 등을 해결할 수 있다.

모니터 방식은 앞서 살펴본 다른 상호 배제 기법 대비 쉽고 에러 발생 가능성이 낮다는 장점을 갖고 있다. 다만 상호 배제를 지원하는 언어가 제한적이며, 이를 사용하기 위해서는 컴파일러가 OS를 이해하고 있어야 한다(=> 코드를 기계어로 바꾸어주는 건 컴파일러가 하는 작업이기 때문)는 단점 또한 갖고 있다.

 

**  KOREATECH 무료 OS강의(클릭) 학습 후 나름대로 이해한 뒤 정리한 내용입니다. **

[Course] Operating System (CPA310) - 운영체제 강의