동시성과 상호배제

병행성(동시성)과 상호배제

 

상호배제 

 병행 프로세스의 공유 자원 동시 접근 금지 -> 공유자원은 한순간에 한 프로세스만 접근

 이때 두 프로세스가 동시에 사용할 수 없는 프로그램 코드 영역을 임계 영역이라고 한다. 

 

 이러한 임계영역에 대한 해결책의 조건

  - 상호배제

  한 순간에는 한 프로세스만이 임계영역안으로 들어갈 수 있다.

  - 진행

  임계 영역 안에 프로세스가 없다면 임계 영역에 들어갈려는 프로세스들이 존재해야 한다.

  - 한정대기 

  다른 프로세스가 임계 영역에 들어갈려면 영원히 기다리면 안됨 

 

프로세스 동기화

 협력하는 프로세스들 사이에 실행 순서를 보장

 공유 데이터를 사용하는 프로세스를 조정하여 공유자원의 일관성을 보장

 -> 상호배제는 보장하지만 교착상태나 기아상태가 발생할 수 있따. 

 

경쟁상태

 상호배제와 동기화가 잘이루어지지 않을시 일어날 수 있다.

 여러 프로세스들이 동시에 공유 자원에 접근하여 데이터의 일관성을 해질 수 있다.

 

 예)

 생산자 소비자 문제

 -생산자가 생성한 데이터를 소비자가 소비하는데 생기는 동기화문제 -> 비동기적 생산과 소비 

 -생산자가 데이터를 생성하여 버퍼에 저장하고, 소비자가 버퍼에서 데이터를 가져와 소비하는 과정에서 발생할 수 있      는 문제를 뜻한다. 초기에는 선형버퍼(queue)로 문제를 해결 -> 공간 낭비가 생김 -> 원형버퍼를 사용

 

https://m.blog.naver.com/hirit808/221785171412

  이러한 경쟁상태를 해결하기위해 상호배제를 사용한다. -> 이러한 것만 사용한다면 Busy waiting 과 DeadLock     

  이 생길 수 있음 

 

  

 

상호배제 방법

 알고리즘 : 데커(Busy waiting), 피터슨(Busy waiting), 다익스트라(기아상태)

 운영체제: 세마포, 모니터

 하드웨어 수준: TestAndSet

 

TestAndSet

 검사와 수정을 원자적으로 하는 하드웨어 명령어

https://aerocode.net/116

  1. bool flag는 lock이 false임을 나타내준다. 

  2. False 를 Test했을 경우 return false이며 Set을 했음으로 True를 리턴하게 된다. 

  3. 이때 Set한 결과를 강제로 false로 변경하면 flag가 false로 돌아감 

 

간단한예제) https://stackoverflow.com/questions/1152246/mutual-exclusion-using-testandset-instruction

프로세스 1이 Set를해 Lock을 true로 만들고 점유하고 있다.  다른 프로세스를 보면 계속 true를 반환 위의 return true의 모습이다.

점유한 프로세스를 반납 프로세스2에 False로 변경해주면서 프로세스2가 접근하기 시작한다

   이러한 과정이 반복되면서 프로세스마다 공유자원을 사용할 수 있다. -> 한 프로세스가 점유하는 동안

   다른 프로세스는 기다리고 있음으로 Busy Waiting와 대기자가 2개 이상인 경우에는 한정대기를 만족하

   지 못할 수 있다. -> 기아상태 발생 -> waiting을 만들어 lock을 풀지않고 안에서 넘겨줌

 

 

세마포(semaphore)

 P와V라는 표준 단위 연산에 의해서만 접근되는 정수형 변수

 TestAndSet의 단점 해결 -> 바쁜대기

 

 세마포의 용도

 - 상호배제

 - 여러 개의 공유 자원 관리

 - 프로세스들 간의 동기화 -> 연산의 순서 제어

 

 세마포의 구성

 세마포 S 

 - 정수 변수

 - 사용 가능한 자원의 개수 표시

 - 표준 단위 연산 P와 V로만 접근

 

 연산 P

 - 임계 영역에 진입하는 연산

 - 프로세스가 대기하는 wait동작

 

 연산 V

 - 임계 영역에서 나오는 연산

 - 대기 중인 다른 프로세스를 깨우는 signal 동작

 

 

https://luv-n-interest.tistory.com/461

 여기서 s는 사용가능한 자원이라고 생각하면된다.

 wait() P 연산임으로 임계영역에 들어가는 연산이다. 그럼으로 S  ==  value라고 생각하면 된다.

 그래서 자원의 수를 감소시킨다. < 0 인 이유는 사용가능한 자원이 없다면 해당 작업을 리스트에 대기시켜야 하기 때   문

 

 signal v 연산은 임계영역에 나오는 연산임으로 자원값을 증가시켜준다. <=0 이면 기다리고 있는 작업이 한개 이상이라

 는 뜻임으로 대기상태 였던 작업을 준비상태로 변경

   

 

 단일 프로세서

  wait와 signal 연산 수행 중 인터럽트 금지를 하게 만들어사 사용 두개의 함수 자체가 임계영역이됨 -> 인터럽트 레지    스터 사용

 

 다중 프로세서

  단일 프로세서와 같이 인터럽트를 금지할 수 없음 -> 성능저하

  세마포 + TestAndSet을 사용해서 상호배제를 해결 -> 즉 완전히 문제점을 극복하지 못함(busy waiting) but  세마포

  연산의 시간이 짧음으로 수용가능하다. 

 

 문제점

  wait()를 두번할 경우 -> 무한대기

  wait와 signal 연산이 바뀐경우 -> dead lock

  한 번의 실수가 모든 시스템에 치명적이다.