[OS] 운영체제 프로세스 동기화 & 상호배제

다중프로그래밍 시스템은 프로세스가 여러개 존재하며, 프로세스들이 서로 독립적으로 동작한다. 그렇기에 공유 자원이나 데이터가 있을 경우 여러 프로세스가 접근하여 수행하면 예상치 못하는 문제가 발생할수 있다. 그렇기에 다중 프로그래밍 시스템 내에서 프로세스들 끼리 서로 동작을 맞추거나 대화를 하는 동기화과정이 필요하다.
이번에는 프로세스들간 동기화가 어떻게 이루어지는지, 그 과정에서 프로세스들간 상호배제가 어떻게 이루어지기에 공유 자원에 대해 자원을 할당받아 작업을 수행하는지 알아보자

동기화(Process Synchronization)

프로세스들이 서로 대화를 하며 동작을 맞추는 것을 의미한다. 서로간의 정보를 공유하는 것을 의미한다. 물론 다중 프로그래밍 시스템에서 프로세스들이 여러개 존재할 경우 필요한 것이다.

다중 프로그래밍 시스템에서의 프로세스 특징 두가지

1. 비동기적(Asynchronous)
   프로세스들이 서로에 대해서 모른다.
2. 병행적(Concurrent)
   여러개의 프로세스들이 동시에 시스템에 존재한다.

이런 특징을 가지고 있기에 병행적으로 존재하는 프로세스들은 공유 자원에 동시 접근할 때 문제가 발생할수 있다. - 상호배제로 공유자원에 대한 접근을 관리햐아함!

프로세스의 동기화 관련 용어

• Shared data(공유 데이터)
  여러 프로세스들이 공유하는 데이터이다.
• Critical section(임계 영역)
  공유데이터를 접근하는 코드 영역이다.
• Mutual exclusion(상호배제)
  둘이상의 프로세스가 임계영역에 진입하는것을 막는 것이다.(다중 프로그래밍 시스템에서 공유자원에 대해 접근하는 프로세스들을 관리하기 위해서..)

하나의 기계어 명령(machine instruction)은 원자성, 분리불가능의 특징을 가지고있다. 예를들면 cpu가 연산을 하기위해 레지스터로 메모리의 데이터를 옮기는 하나의 기계어 명령을 분리할수 없다.

상호배제가 필요한 경우

하나의 공유데이터 sdata에 접근하는 두 임계영역(1, 2, 3), (A, B, C)가 존재한다. 두 프로세스는 두 임계영역에서 공유 데이터에 대해 접근할수 있다. 그런데 프로세스는 항상 일정한 패턴으로 작업을 수행하는게 아니라, 갑자기 선점당해서 running 상태의 프로세스가 ready상태로 갈수도있고, blocked상태로 변할수도있다.(외부 자원에대한 요청으로 인해) 이렇게 프로세스가 작업을 수행하는데 있어서 작업이 수행되는 순서에 따라 공유데이터가 달라질수 있다. 이를 Race condition이라 한다.

이렇게 프로세스가 수행할때 명령이 수행되는 순서에 따라서 공유데이터가 달라질수 있다. 이렇기에 상호배제, 즉 공유데이터에 접근하는 코드인 임계영역에 둘 이상의 프로세스가 들어가는 것을 막는 것이 필요하다.

우리가 원하는 결과를 보장하려면 둘이상의 프로세스가 임계영역에 들어가는 것을 막고, 임계영역에 하나의 프로세스만 진입하도록 해야한다.!! - 상호배제가 필요하다.

상호배제(Mutual Exclusion)

위 그럼처럼 공유데이터가 있는 공유 메모리 자원에 접근하기 위한 임계영역에 둘이상의 프로세스가 접근하는 것을 막는 것이 상호배제이다. 프로세스1이 임계영역에 진입했으므로 프로세스2의 임계영역 접근은 막는 상황이다.

상호배제 기본연산 두가지(Mutual exclusion primitives)

primitive 는 컴퓨터 공학에서 기본연산을 의미한다.

• enterCS()primitive
  임계영역에 들어가기 전에 검사(다른프로세스가 임계영역에 있는지 검사)
• exitCS() primitive
  임계영역을 벗어날때의 후처리과정의 연산이다. 임계영역을 벗어났다고 시스템에 알려야 다른 프로세스가 임계영역에 진입할수있다.

상호배제의 필요조건 세가지

1. Mutual exclusion(상호배제)
   임계영역에 프로세스가 있으면 다른 프로세스는 임계영역에 진입 못함
2. Progress(진행)
   임계영역의 프로세스 외에 다른 프로세스는 어떠한 프로세스가 임계영역에 진입하는것을 방해하면 안된다. 즉, 임계영역의 프로세스만 임계영역에 진입하려는 프로세스를 방해할수 있다.
3. Bounded waiting(한정 대기)
   프로세스의 임계영역진입은 유한시간 내에 허용되야함.(=기아현상 일어나면 안된다.)

이 세가지 상호배제 조건에 맞는 기법을 이용해서 임계영역에 프로세스가 접근하는 것을 막아야한다.

상호배제 해결책

SW Solutions

Dekker's 알고리즘

두 프로세스의 상호배제를 보장하는 최초의 알고리즘

Peterson's 알고리즘

데커 알고리즘 보다 간단한 두 프로세스의 상호배제 보장하는 알고리즘

Dijkstra's 알고리즘

N개의 프로세스의 상호배제를 보장하는 알고리즘

위 상호배제 알고리즘들은 단점이 존재한다.

• 속도가 느림(while문으로 빙빙 돈다.)
• 구현이 복잡하다.
• 상호배제 도중 preemption이 될수 있다.
• Busy waiting(바쁘게 기다린다는 것을 의미하는 용어이다. 비효율적임을 나타낸다.)

HW Solutions

이번엔 하드웨어가 상호배제를 하는 방법을 알아보자.
하드웨어는 TestAndSet(TAS) instruction을 통해서 실행중 preemption을 받지 않는 장점이 있다.
야기서 TAS란 Test와 Set을 한번에 수행하는 기계어이고, Machine instruction으로 원자적인 특징이 있다.
그러나 SW Solution처럼 Busy waiting은 해결하지 못하기에 비효율적이다.

즉, TAS로 구현도 단순하고, 선점도 되지않으므로 간단하지만 SW 솔류션들과 같이 Busy waiting은 존재한다.

TAS instruction으로 간단하게 상호배제를 하는 모습이다. 그러나 Busy waiting은 존재한다. 그리고 상호배제의 조건중 3번인 bounded waiting도 지키지 못한다. 프로세스가 임계영역에 들어가려고 온 순서에 상관없이 우연하게 while문이 끝나는 프로세스가 임계영역에 접근가능하므로 운이 없는 프로세스는 계속해서 busy waiting만 하고 있을 수 있다.

데커, 피터슨, 다익스트라 알고리즘과같은 상호배제를 위한 소프트웨어 솔류션도, TAS instruction을 사용하는 하드웨어 솔류션도 모두 Busy waiting을 해결하지 못해서 비효율적으로 상호배제를 하는 모습을 볼수 있다. 이를 해결하기 위해 OS가 개입하게되었다!!!

OS supported SW solution

Busy waiting 문제를 해결하고자 OS가 support하는 솔루션이 등장했다.

Spinlock

정수변수를 의미한다.
즉, Spinlock은 정수변수와, 이 변수에대한 세 연산 초기화, P, V로 상호배제를 하는 솔루션이다.
여기서 OS가 support하는 부분은 P연산, V연산, 초기화연산을 atomic한 연산으로 가능하게 해준다. 즉, 이 연산들이 진행될때 preemption되어 프로세스가 중단될 일이 없도록 하겠다는 것이다.

P연산은 정수변수의 값을 1 빼는 연산 즉, 문을 잠그는 역할을 하는 연산이고
V연산은 정수변수의 값을 1 더하는 연산 즉, 문을 여는 역할을 하는 연산이다.

Spinlock을 통한 상호배제 과정이다. OS의 support로 p, v연산중 선점되지않으니 임계영역에 두개이상의 프로세스가 들어갈 일은 없다.

그러나 Spinlock의 단점이 존재하는데 바로, 여전히 Busy waiting을 한다는것이다. P연산으로 어떤 프로세스가 임계영역에 들어가있으면 다른 프로세스는 while문내에서 바쁘게 기다리고있다.
그리고 멀티프로세서 시스템내에서만 적용이 가능하다. spinLock은 os가 p(s)연산을 atomic하게 보장하는데 이는 프로세서를 할당해서 보장하는 것이다(프로세서를 할당받아서 연산을 하는 것이므로). 만약, 프로세서(cpu)가 하나라면 a 프로세스가 p연산내의 while문을 계속돌며 프로세서를 할당받고 OS는 해당 연산을 atomic하게 지원하기에 계속 돌게된다.(다른 프로세스가 프로세서를 할당받지못하게된다.) 그렇게되면 a 프로세스는 계속 while문을 돌며 자원을 할당받지 못하여 작업을 수행하지 못하고, 다른 프로세스들(b, c, d ...)도 a프로세스가 프로세서를 반납하지 않으므로 작업을 수행하지 못하게된다. 즉, spinLock은 멀티 프로세서 시스템에서만 가능하다는 단점이있다.

Semaphore

OS가 support하는 솔루션인 spinlock은 busy wating이라는 단점이 있다. 불필요하게 cpu를 사용하며 연산을 하는것이 비효율적이다. 그래서 등장한 다른 os support솔루션인 semaphore가 등장했다. Dijkstra가 제안했고 Busy waiting 문제를 해결했다!! 이제 어떻게 해결했는지 spinlock과 뭐가 다른지를 알아보자

Semaphore 연산

spinlock과 같이 초기화연산 P연산 V연산이 존재한다.(P연산은 감소, V연산은 증가)
역시 os가 support하기 때문에 위 연산들은 indivisible즉, atomic하다. (연산 도중 선점되지 않는다.)

spinlock과 다른점은 연산에 필요한 변수가 음이아닌 정수형 변수(>= 0)라는 것이다.
그리고 더 중요한건 임의의 S변수 하나에 ready queue 하나가 할당된다는 것이다. (정수변수 마다 queue를 가지고있다.)
이 ready queue에서 프로세스가 대기하고있어, busy watiting을 피할수 있다.(spinlock은 프로세서 할당받아서 while문 내에서 빙빙 돌면서 대기하는 busy waiting이 존재했다.)

대신 세마포어는 ready queue를 이용하지만 V연산시 큐에 block상태인 프로세스를 깨울 때는 one of them, 큐에 대기중인 프로세스중 어느 하나를 무작위로깨운다. 즉, 운이없으면 계속해서 자원을 할당받을수 없는 프로세스가 생긴다.(starvation 문제 존재)

Semaphore 종류

1. Binary semaphore
   변수가 이진으로 0, 1두 종류의 값만 갖는 경우이다.
   상호배제나 프로세스 동기화의 목적으로 사용된다.
2. Counting semaphore
   S가 0이상의 정수값을 가질수 있는 경우이다.
   생산자-소비자 문제를 해결하기 위해 사용된다.

세마포어 종류는 연산에 사용되는 변수의 종류로 구분한다.

semaphore의 P연산과 V연산

P연산을 보면 변수 S가 0보다 크면 1 감소시키고, 그렇지 않으면 ready queue에서 대기하는 것을 알수있다.(이 부분이 spinlock과 달라 busy waiting을 해결한다.)
V연산은 대기큐에 프로세스가 존재하면 깨우고 그렇지 않으면 변수를 증가시킨다.
즉, P연산의 결과로 ready queue에 대기중인 프로세스가 있으면! V연산시 큐에 대기중인 프로세스(block, asleep상태임)를 깨운다.(one of them)

Semaphore로 해결가능한 동기화 문제들

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

즉, 세마포어로 되게 많은 동기화 문제를 해결할수 있다. 이제 하나씩 보면서 어떻게 세마포어로 동기화 문제를 해결하는지 알아보자.

Semaphore로 해결하는 상호배제 문제(Mutual exclusion)

active라는 정수형 변수가 연산에 사용되며, active가 1이면 임계 지역에 실행중인 프로세스가 없으므로 p연산시 active를 감소시키고 임계영역에 프로세스가 진입힌다. 그렇지않고 active가 0이면 임계영역에서 실행중인 프로세스가 존재하므로 P연산시 ready queue에 프로세스가 대기하고 임계영역 작업 수행이 끝난 프로세스는 V연산을 실행하여 대기 큐에 기다리던 프로세스를 깨운다. 그러면 깨어난 프로세스는 임계영역에 들어가 작업을 한다.

spinlock과 다르게 busy waiting하며 불필요하게 cpu할당받아 연산을 할필요가 없기 때문에 더 효율적이다. 실제로도 세마포어로 동기화 문제를 해결한다.

Semaphore로 해결하는 프로세스 동기화 문제(process synchronization)

프로세스들간의 실행 순서를 맞춰야 할 경우 세마포어를 이용하여 쉽게 동기화 할수 있다.
pj프로세스가 먼저 Lj에 접근하고 그다음 pi가 li에 접근해야하는 경우
만약 pj가 먼저 lj에 접근한다면 정수변수의 값을 줄여주고 그다음 pi가 li에 접근하면 된다.(정수 변수가 감소된걸 보고 pi가 실행해도된다는걸 깨닫고 li에 접근함)
반대로 pi가 먼저 li에 접근했다면 정수형 변수가 감소되지 않은걸 보고 ready queue에 대기하고, pj가 lj에 접근하고 작업 수행이 끝나면 ready queue의 pi를 깨워서 pi가 li에 접근가능하도록한다.

세마포어로 busy waiting 문제를 해결하면서 상호배제 상호배제 문제를 해결하는 것을 계속해서 볼수있다.

Semaphore로 해결하는 생산자 소비자 문제(Producer-Consumer problem)

생산자 소비자 문제란 생산자는 생산을 하고 소비자는 소비를 하는데 생산자가 이미 존재하는데 생산하는 문제와, 소비자가 생산한게 없는데 소비하려는 문제를 의미한다. 예시로, 하나의 버퍼에 문자를 생성해야 소비자가 문자를 소비하는데, 버퍼에 아무 문자도 없는데 소비자가 버퍼에서 소비하려할때, 문제가 발생할 것이고 생산자가 소비자가 소비하는 와중에 버퍼에 생산하려하면 문제가 발생할 것이다.
이 생산자 소비자 문제 역시 세마포어를 통해 해결할수 있다.

생산자와 소비자가 생산하고 소비하는 공간인 버퍼가 하나일경우와 N개일 경우 나누어서 어떻게 세마포어로 해결하는 지 알아보자.

1. 버퍼가 1개일 경우 생산자 소비자 문제 세마포어로 해결
   

   

   
   소비했는지 즉, 비어있는지를 물어보는 consumed변수와, 생산했는지 즉, 채워져 있는지를 물어보는 produced변수가 존재 하고 버퍼는 하나이다.
   produced, consumed 변수를 통해서 문제를 해결할수 있다.

먼저 생산자가
P(consumed)를 통해서 소비했는지, 즉 비어있는지를 확인한뒤 비어있으면 P연산으로 1을 빼고, 버퍼에서 생산을 한뒤 V(produced)를 통해서 produced 변수를 V연산으로 1을 증가시킨다.(생산 했다는 flag이다.)
그 다음 소비자가
P(produced)를 통해서 생산했는지 확인한뒤 생산했으면 produced를 1 빼고 소비하고 다시 consumed를 1증가한다.(P연산과 V연산)
만약 생산되어 있지 않은데 소비자가 소비하려할 경우
P(produced)에서 produced가 0으로 생산되어 있지 않으면 ready queue에서 대기하고 생산자가 V(produced)로 1 증가시키고 ready queue에서 대기중이선 소비자를 깨우면 그때서야 소비자는 P(produced)로 produced를 1 빼고 소비하고 consumed를 1 더한다.

2. 버퍼가 N개일 경우 생산자 소비자 문제 세마포어로 해결

버퍼가 N개인 경우는 위 그림과같이 circular queue를 이용한다.

버퍼도 N개이고 생산자, 소비자도 여러개이다.

세마포어로 생산자 소비자 문제를 해결하는 방법이 딱히 버퍼가 한개인 경우와 다르지 않다.
일단 생산자와 소비자가 여러개 이므로 생산, 소비하는 작업 수행에 대하여 상호배제를 해주는 p(muteXP)와 V(muteXP) (생산자일경우만 적음)가 존재한다. 즉, 위 두 코드 사이의 부분을 critical section과 같이 생각하면 된다. 이제 내부동작을 알아보면 nrfull은 차 있니 에대한 변수이고 nrempty는 비어있니 에대한 변수이다. 생산자 하나에 대해서(상호배제 함) P(nrempty)에서 비어있으면 즉, nrempty 가 0 보다 크다면 P연산으로 1 줄이고 생산하고 비어있는 버퍼에 생산을 한다. 그리고 끝나면 V(rfull)로 1을 더하여 하나가 찼다는 걸 알려준다. 이 경우도 nrempty가 0이라면 대기 큐에서 대기하고 소비자가 nrempty를 하나 증가하면 그때서야 대기큐에서 깨어나서 P(nrempty)연산이 수행되고 생산한다.

Semaphore로 해결하는 reader-writer problem

생산자-소비자 문제와 다르게 reader-writer는 어떠한 자원에 대해서 동시에 읽을순 있지만 동시에 쓸순 없고, 읽고 있을 때 쓸수도, 쓰고 있을 때 읽을수도 없다. 이러한 문제에 대해서 세마포어로 해결하는 방법이 존재한다.

즉 reader는 동시에 자원에대해 접근이 가능하지만 writer, writer-reader는 동시에 자원에대해서 접근하지 못하는 문제를 말한다.

1. reader preference solution
   reader에 우선권을 주는 솔루션이다.(세마포어를 이용한)
   reader 가 자원에대해서 읽고있는중 writer가 들어온 상황에 대해서 또 다른 reder가 들어오면 첫번째 reader가 자원에 대해서 작업수행이 끝나도 writer가 아닌 두번째 reader가 읽기가 끝나지 않았으면 writer는 작업에 대해서 쓰는 작업수행이 밀리게 되는 문제에 대한 솔루션이다. 즉 writer는 starvation문제가 있을 수 있다.

간단하게 글로 적으면
writer는 동시에 하나만 접근할수 있으므로 상호배제로 P(mutexW)로 정수형 변수가 1이면 읽기를 하고 아니면 대기를 한다.
reader는 동시에 여러개 접근할수 있으므로 reader에 대해서는 nreaders(읽는 프로세스의 수)가 0이면 p(mutexW)로 writer가 접근하지 못하도록 막고 nreaders의 수를 1 증가하고 읽기가 끝나면 nreaders의 수를 1빼고 만약 nreaders가 0 이라면 v(mutexW)로 writer가 접근할수 있도록 한다. 즉 reader가 계속해서 들어오면 writer는 계속 자원에대해서 할당받지 못하는 기아현상이 일어날수 있는 솔루션이다.

2. writer preference solution
   writer에 우선권을 주는 솔루션이다.

이것도 간단하게 글로 적으면
reader preference solution과 같이 writer는 동시에 하나만 접근할수있지만 writer가 쓰는 중 reader가 읽기를 대기하는 상황에서 다른 writer가 대기하면 첫번째 writer가 수행이 끝나도 reader가 할당받는게 아닌 두번째로 와서 대기중인 writer가 자원을 할당받는 솔루션이다.

EventCount/Sequencer

os supported 솔루션인 세마포어를 통해 ready queue로 busy waiting문제를 해결하는것을 확인했다. 그러나 큐에 대기중인 프로세스중 무작위로 하나를 깨우기 때문에 starvation문제가 존재한다. 이 문제는 EventCount/Sequencer 솔루션을 통해서 해결할수 있다.

은행에서 업무를 보고싶으면 일단 번호표를 뽑아야한다. 그래서 내 번호표에 적힌 차례가 오면 그때서야 업무를 볼수 있다. 이 은행에서의 번호표 시스템과 EventCount/Sequencer는 아애 같은 매커니즘으로 동작한다.

Sequencer: 번호표의 번호이다. 정수형 변수로써 0으로 초기화되고 번호표답게 1씩 증가한다. Sequencer 정수형 변수는 ticket()연산을 통해서만 접근할수있다.
ticket(S): 현재까지 호출된 ticket연산의 회수를 반환한다.
EventCount: 업무 창구에서 호출하는 고객의 번호표이다. Sequencer와 같이 정수형변수로 1씩 증가한다.
read(E): 현재 EventCount를 반환한다.
advance(E): 업무가 끝나고 창구에서 다음 번호표의 고객호출을 위해 1을 증가하는 연산이다. 즉 E를 1증가하고, E를 기다리는 프로세스를 깨운다.
await(E, V): E는 EventCount, V는 정수형 변수로 프로세스가 받은 대기표 번호이다. if(E < V)이면 queue에서 프로세스를 대기시킨다. 그리고 if(E == V)이면 대기중이는 해당 프로세스를 깨운다.

EventCount/Sequencer로 해결하는 상호배제 문제

처음 E와 V는 0이고 처음에 프로세스가 오면 자신의 대기표인 0을 받고 Sequencer변수를 1증가한다. 그리고 await(E, V)에서 E == V (0 = 0)이므로 바로 작업을 수행하고 advance(E)로 EventCount를 1증가시킨다.
만약 프로세스 p2, p3, p4가 순서대로 온다면 p2, p3, p4는 각 대기표를 받고 p2는 await연산에서 E와 자신이 받은 대기표 V가 같으므로 작업을 수행하고 queue에는 p3, p4가 대기중이다. p2가 작업 수행이 끝나서 advance(E)연산으로 E를 1증가시키면 대기중이던 V가 3인 p3를 깨우고 await연산에서 같으므로 작업을 수행한다.

즉, 큐에 대기중이는 프로세스는 starvation문제가 발생할 걱정이 이젠없다.

EventCount/Sequencer로 해결하는 생산자-소비자 문제

생산자 소비자 문제도 EventCount/Sequencer를 통해서 Starvation걱정없이 해결할수 있다.

EventCount/Sequencer 정리

• busy waiting no! (ready queue를 이용하므로 바쁜 기다림은 이젠 없다.)
• starvation no! (깨울 프로세스가 정해져있어서 기아현상은 걱정없다!)
• semaphore보다 더 다양한 기능! (대기큐에 block된 프로세스를 깨우는 순서를 다양하게 커스텀할수 있다)

Language-level solution

• semaphore, eventcount/sequencer같은 솔루션들도 좋다. 유연하다. 그렇지만 복잡하다는 단점이있다. 즉, 에러가 생기기 쉽다.

그래서 언어에서 제공하는 솔루션이 존재한다. 이는 언어에서 제공되므로 사용이 쉽다.

Monitor

Language-level solution중 하나이다.
모니터는 공유데이터와 임계영역(critical section)의 집합을 의미한다
모니터에는 최대 한개의 프로세스만 접근가능하다.

Monitor 구조

java에서도 Monitor라는 클래스로 제공된다.

이 Language level solution을 이용하면 생산자 소비자문제, reader-writer, Dining philosopher문제를 해결할수 있다.

Monitor 장단점

• 장점 : 사용하기 쉽다. 언어자체에서 제공하니 에러도 적다.
• 단점 : 지원하는 언어에서만 사용이 가능한 제약이 있고, 컴파일러가 OS를 이해해야한다는 단점이있다.

https://www.youtube.com/watch?v=AnYN-kbCbRI&list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN&index=18