6.Process Synchronization & Mutual Exclusion

 

Process Synchronization

동기화가 무엇일까?

 

우리가 사용하는 다중 프로그래밍 시스템에서는 여러 프로세스들이 독립적으로 동시 동작한다.

따라서 공유자원을 동시에 원할 경우? 문제가 발생할 수 있다.

즉 프로세스 동기화는

공유되는 자원을 두고 프로세스들 사이에 서로 겹치지 않게 동작을 맞추는 것/서로 정보를 공유하는 행위를 동기화라 한다.

 

Asynchronous and Concurrent P’s

비동기적(Asynchronous)이라는 말은 프로세스들이 서로에 대해 모르는 것이다 

병행적이라는 말은 여러 개의 프로세스들이 동시에 시스템에 존재하는 것이다. 

 

문제는 병행수행 중인 비동기적 프로세스들이 공유자원에 동시에 접근 시 문제가 발생할 수 있다.

<용어 정리>

Shared data/Critical data(공유 데이터) > 여러 프로세스들이 공유하는 데이터

Critical Section(임계 영역) > 공유 데이터를 접근하는 코드 영역(Code Segment)

Mutual exclusion(상호 배제) > 둘 이상의 프로세스가 동시에  Critical sectio(임계 영역)에  진입하는 것을 막는 것

Mutual Exclusion Methods

Murual Exclusion의 기본 연산기(primitive)

> enterCS() primitive 

> exitCS() privimtive

 

enter CS()는 크리티컬 섹션을 진입하기 전에 다른 프로세스가 그 안에 있는지 검사하는 연산이다.

exit CS()는 크리티컬 섹션을 벗아날 때 후처리 하는 과정으로 CS를 벗어난다는 것을 시스템에게 알려주는 연산 이이다.

Requirements for ME primitives

ME기본 연산을 위해서는 아래 세 가지 요구사항들을 만족해야 한다.

1. Mutrual Exclution(상호 배제)

> 크리티컬 섹션에 프로세스가 있다면 다른 프로세스의 진입을 금지해야 함

2. Progress(진행)

> CS안에 있는 프로세스 외 다른 프로세스가 CS에 진입하는 것을 방해하면 안 됨 즉 비어있는 CS에 접근하려는 프로세스를 다른 프로세스가 개입하여 막으면 안 된다는 것이다. 

3. Bounded waiting(한정 대기)

> 프로세스의 CS진입은 유한한 시간 내에 허용되어야 한다.

 

ME기본 연산을 구현하는 데 있어 위 3가지 조건(ME, P, BW)을 만족하는지 확인한다.

 

Mutual Exclusion Solutions.

ME를 구현하는데 있어 솔루션은 아래의 방법들로 구현될 수 있다.

1. SW solutions

• Dekker’s algorithm (Peterson’s algorithm)

데커스 알고리즘은 프로세스가 두 개일 때 ME를 보장하는 최조의 알고리즘이다.

Dekker&amp;amp;amp;amp;rsquo;s algorithm&amp;amp;amp;amp;nbsp;

피터슨은 위 데커스 알고리즘을 보다 간단히 구현한 알고리즘이다.

 

Peterson&amp;amp;amp;amp;rsquo;s Algorithm

N개의 프로세스에 대한 ME는 다양한 분들이 풀었지만 다익스트라만 보기로 하자

• Dijkstra’s algorithm(다익스트라 알고리즘)

깃발을 세 단계로 나누어 프로세스가 CS영역에 진입을 시도하지 않는 단계 ,  프로세스가 CS 영영에 들어가고 싶다는 의사를 표현하는 단계, 프로세스가 CS에 진입 직전 단계

SW 솔루션의 문제점

1. 속도가 느리다

2. 구현이 복잡하다

3. ME 연산 실행 중  preemption 될 수 있다. OS가 도와줘서 공유 데이터 수정중 interrupt를 억제할 수 있으나 이는 overhead를 발생시킨다

 

4. Busy waiting (기다리면서 바쁜) 이 있어 비효율적이다.

 

2. HW solution 

• Synchronization Hardware

TestAndSet (TAS) instruction

> Test와 Set을 한 번에 수행하는 기계어로 Machine instruction 이기 때문에 실행 중 interrupt를 받지 않으며(preemption 되지 않음) Atomicity 하고 나누어지지 않는다.

타깃의 현재 값은 반환하며 타깃을 true로 만드는 과정을 한 번에 수행한다.

3개 이상의 프로세스의 경우 Bounded waiting 조건에 위배된다.

N 개의 프로세스에서&amp;amp;nbsp; ME with TAS

장점은 구현이 간단하다 단점은 계속 기다리면서 돌고 있어 여전히 busywaiting 이 있어 효율적이지 못하다. Busy waiting 문제를 해소한 상호 배제 기법이 Semaphore이고 대부분의 OS들이 사용한다.

3. OS supported SW solution

• Spinlock

스핀 락은 쉽게 말해 정수형 변수이다.

 S는 초기화 연산인 P() , V() 연산으로만 접근 가능한 변수이며

P() , V() 연산은 OS가 indivisible(or atomic)을 보장한다.

S를 물건 개수라 하면 P는 S를 가져가는 것 , V는 S를 돌려놓는 과정이라 보자.

active = Spin lock 변수

스핀 락은 멀티 프로세서 시스템에서만 사용이 가능하고 아직 Busy waiting 문제가 있다.

 

• Semaphore

1965년 다익스트라님이 제안했으며 Busy waiting 문제를 해결하였다.

세마포어는 스핀 락과 마찬가지로 정수형 변수인데 음이 아닌 정수형 변수(S>=0)이다

스핀 락과 비슷하게 초기화 연산 P 와 V로만 접근이 가능하다

P: Probern (검사)

V : Verhogen(증가)

세마포어&amp;amp;nbsp; P V

 

스핀락과 세마포어의 가장 큰 차이는 임의의 S변수 하나에 Ready queue(일종의 대기실) 하나가 할당된다는 것이다.

즉 No busy waiting이며 기다려야 하는 프로세는 (block/asleep) 상태가 된다.

 

Binary semaphore

S가 0/1 두 종류의 값만 가지는 경우로 상호 배제 또는 프로세스 동기화의 목적으로 사용된다.

Counting semaphore

S가 0 이상인 정수 값을 가질 수 있는 경우로  생산자 소비자 문제 등을 해결하기 위해 사용다.

 

OS가 indivisible 한 연산을 보장해주며 전제가 한 instructin cycle에서 수행된다.

 

 

<세마포어로 해결 가능한 동기화 문제들>

상호 배제 문제(ME)

프로세스 동기화 문제(Process Synchronization Problem)

생산자 소비자 문제(Producer-consumer problem)

Reader-Writer 문제

Dining philosopher 문제

기타

 

상호 배제 문제(ME)

 

프로세스 동기화 문제

프로세스들의 실행 순서 맞추기를 세마포어로 해결 가능하다

세마포어 변수 sync 초기 0 세팅 물건(sync)이 현재 없음 Pj가 가지고 있다고 가정.

물건이 없으니 Pi는 물건이 올 때까지 기다린다(P(sync))

Pj가 물건을 다 쓰고 반납(V(sync)하면 sync =1

물건이 생겼으므로 대기실에 있던 Pi가 물건을 대여 sync =0  

생산자 소비자 문제(Producer-consumer problem)

> 특징

생산자가 물건을 만들어 놓는 동안 소비자가 가져가면 안 되며 소비자가 물건을 꺼내 가능동 안 생산자는 물건을 놓을 수 었다. 또한 물건이 있는데 또 물건을 놓을 수없다.

consumed : 소비되었니?

produced : 생산되었니?

M을 생산해서 넣으려고 하니 비었는지 확인해야 한다. P(comsumed) 소비자가 소비했으면 버퍼가 비었다는 것

비었으면 buffer에 M 넣는다.

생산 완료했음을 알려준다(V(produced))

 

생산을 했으니 이를 소비하고자 하는 자가 있는지 확인(list  확인) 누군가 있다면 P(produced) 생산되었니? 물어본다

생산했으니 소비자는 물건을 소비 (m <-buffer) 소비했다고 알린다(V(consumed)

 

그렇다면 생산자와 소비자가 여러 명일 때는 어떻게 해주어야 할까?

P(mutextP) : 생산자가 여러 명일 경우 동시에 놓으면 안 되기 때문에  한 번에 한 명만 일하도록 해준다

p(nrempty) 지금 버퍼 비어있니? 없으면? 공간 생길 때까지 Q에서 대기 있으면 안으로 들어감(Buffer [in]) 넣어 주었으니 다른 버퍼로 위치 갱신해주고 V(nrfull) 방금 넣은 곳의 버퍼는 채웠다고 말함

V(mutexP)로 현재 생산자는 일을 다했다고 말함

 

소비자도 이런 식으로 해석

Reader-writer 문제

> 특징

Reader 데이터를 읽기 연산만 수행, Writer데이터에 대해 갱신 연산을 수행 

데이터의 무결성 보장을 위해 Reader들은 동시에 데이터 접근이 가능하나 Writer 또는 Writer와 reader가 동시에 데이터 접근 시 상호 배제(동기화)가 필요하다.

 

 

읽으러 들어가기 전 현재 몇 명이 읽고 있는지 수를 체크 만약 현재  읽고있는 리더가 없다면 Writer가 쓰고  아니라면 리더를 한 명 증가시킨다. 그 후 읽는다(Perform read operation)

리더가 읽고 나오다가 리더스가 0이 되면? writer가 쓸 수 있다. 

 

• Eventcount/sequencer 

특징 

> 비지 웨이팅이 없다

> 먼저 온 애가 먼저 스케쥴링받아서 Starvation이 없다
> 세마포어는 못한 순서를 컨트롤 했으므로 low-level-control 가능하다고 볼 수 있다.

이렇게 만능일 것 같은 세마포어 에도 문제가 있는데 그건 wake-up순서가 비 결경적이기 때문에 무한 대기하는 Starvation 문제가 발생할 수 있다 는 것이다. 이런 경우가 없도록 순서에 맞춰 깨우자 하여 나온 것이 Eventcout /Sequencer다

Sequencer는 정수형 변수로 생성 시 초기값은 0이 다. 사건 발생 시 증가만 하며 감소는 하지 않는다. 

그렇기 때문에 사전 발생한 순서를 유지 가능하다.

이 Sequencer는 ticket() 연산으로만 접근이 가능하다.

 

ticket(S)란 현재까지 연산이 호출된 횟수를 반환한다. 

 

쉽게 Sequencer는 번호표 기계 ticket()은 순번이 적힌 번호표 종이라고 보자.

 

Eventcount 또한 정수형 변수로 새 성시 0으로 초기화되어있고 감소하지 않는다.

특정 사건의 발생 횟수를 기록하며 read(E) , advance(E), await(E, v) 연산으로만 접근 가능하다.

read(E)는 현재 이벤트 카운트 값을 반환하는 연산자이고 advance(E)는 E를 1 증가시켜 E를 기다리고 있는 프로세스를 꺠운다.

await(E, v)에서 v는 정수형 변수이며 if(E <v)이면 E에 연결된 Q에 프로세스를 전달하고 CPU scheduler를 호출한다.

 

 

4. Language-Level solution

Language-Level solutioin 은 High-level mechanisms이며

Monitor, Path expressions, Serializers, critical region, conditional cricital region 등 이 있다 이중 Monitor에 대해서 내가 본 강의는 설명하고 있다.

• Monitor

프로그램 언어가 ME해결을 서포트하며 사용이 쉽다.

 

모니터란 Critical data와 Critical section의 집합으로 

한 번에 한 프로세스만 들어올 수 있다.

 

모니터의 구조.

> Entry queue(진입 큐)

모니터 내의 function 수만큼 존재한다.

> Condition queue(조건 큐)

모니터 내의 특정 이벤트를 기다리는 프로세스를 대기하는 대기실

> Signaler queue(신호 제공자 큐)

모니터에 항상 하나의 신호제공자 큐가 존재하여 signal() 명령을 실행할 프로세스가 잠시 대기하는 공간이라고 보면 된다.

모니터 구조

 

모니터의 특성

> Mutual exclution

모니터 내에는 항상 하나의 프로세스만 진입 가능하기에 ME 특징이 있다. 언어가 ME를 보장한다.

> Information hiding(정보 은폐)

공유 데이터는 모니터 내의 프로세스만 접근 가능하므로 정보 은폐성을 가진다.

 

모니터의 장점
> 사용이 쉽다 (언어가 지원하므로)

> Deadlock 등 error발생 가능성이 낮다.(사용이 쉬우므로)

 

모니터의 단점

> 지원하는 언어에서만 사용 가능하다

> 언어로 작성한 것을 시스템에 적합한 기계어로 번역하기 위해서는 컴파일러가 OS를 이해하고 있어야 한다.

 

Dining philosopher problem

생각하거나 스파게티를 먹는 일만 반복하는 철학자 5명이 한 식탁에 있다. 

철학자들은 스파게티를 먹기 위해서는 양손에 포크 2개를 모두 들어야 한다. 

그런데 식탁에 포크가 6개뿐이다. 누군가 생각할 때 누군가는 먹어야 한다.

포크는 공유 데이터 철학자는 프로세스로 보고 이 문제를 풀자.