[운영체제] Synchronization tools

Race condition

• 공유 데이터에 대한 엑세스가 제어되지 않았을 때 경쟁 상태(race condition)가 존재하며, 데이터 값이 손상될 수 있다.
• 실행결과는 엑세스가 수행되는 순서에 따라 달라진다.

 

 

 

Critical section

• 각 프로세스는 critical section이라는 코드의 한 부분을 가지고 있다.
• 한 프로세스가 critical section에 접근했으면 다른 프로세스는 기다려야 한다.
• entry section: entry section에서 critical section에 접근하겠다고 요청, 허가되면 들어가고 아니면 entry section에서 기다려야함
• exit section: 프로세스가 exit section으로 나오며 critical section을 빠져나왔다고 알리면 다른 프로세스가 critical section으로 접근 가능

 

 

Critical section problem

Critical section problem을 해결하기 위해서는 다음의 세가지가 조건이 필요하다:

1. Mutual exclusion: 한 프로세스가 critical section을 실행하고 있으면 다른 프로세스는 그곳에 접근할 수 없도록 해야한다.
2. Progress: 어떤 프로세스도 critical section을 실행하고 있지 않고 어떤 프로세스가 critical section을 실행하기를 원하면 실행될 수 있도록 해야함
3. Bounded waiting: 무한정 기다려서는 안 되고 기다림이 끝난다는 보장이 있어야한다. 또한 프로세스의 속도는 알 수 없지만 어찌되었건 진행은 되고 있어야 한다.

 

 

 

Interrupt base solution

• Entry section에서 interrupt를 disable해서 critical section에서 preemtion이 안되도록 함
• Exit section에서는 interrupt를 enable해서 다른 프로세스가 critical section을 실행할 수 있게 함
• But 한 프로세스가 계속 critical section을 점유해서 starving이 발생할 수 있고, CPU가 여러 개일 때 복잡해짐

 

One software solution

• 자신의 turn에만 critical section을 실행 가능

• 두 프로세스가 따로 실행되기 때문에 Mutual exclution은 만족
• 한 프로세스가 remainder section에서 지연되면 다른 프로세스도 critical section에 들어갈 수 없으므로 progress는 성립 안됨

 

 

 

Peterson’s solution

• Turn 외에도 프로세스가 critical section에 들어갈 준비가 되었는지 나타내는 flag가 존재

• Mutual exclusion, progress, bounded waiting 모두 만족
• But 현대 컴퓨터에서 잘 동작할 거라는 보장이 없음(프로세서나 컴파일러가 operation의 순서를 바꿀 수 있으므로)

 

 

 

Hardware support for synchronization

1.  Memory barriers

Memory barrier는 cpu나 컴파일러에게 barrier 명령문 전 후 메모리 연산을 순서에 맞게 강제하는 기능이다. 즉 메모리 베리어 후 명령은 메모리 베리어 전 명령이 끝난 뒤 실행되어야 한다.

 

2.  Atomic instructions

한 덩어리씩 끝나게 하는 명령어

• Test and set instruction

 

Lock이 걸려있으면 계속 while문, Lock이 풀려있으면 critical section 들어가면서 lock을 걸어줌

 

 

• Compare and swap instruction

Lock이 0이면 lock이 1이 되고 critical section으로 들어감, lock이 1이면 lock은 그대로 1이고 while문 실행

 

 

3.  Atomic variable

Variable을 업데이트할 때는 항상 atomic하게 업데이트 하는 것(업데이트 하는 중에 끊기지 않아야함)

업데이트 시 compare_and_swap 등을 써서 업데이트

 

 

 

Mutex Lock

• Atomic instruction은 하드웨어 적인 영역이라 프로그래머가 다룰 수 없음
• Mutex lock은 OS레벨에서 lock을 사용할 수 있게 API를 제공한 것
• acquire lock – lock을 얻으면 critical section에 접근할 수 있음
• release lock – critical section에서 나오면 lock을 풀어줌
• acquire() 과 release()는 atomic 해야함

• while 문으로 busy waiting 함

 

 

 

Semaphore

• semaphore 값 S는 허용될 수 있는 프로세스 개수
• wait()는 S값이 0이하이면 기다리고 아니면 S를 하나 줄이고 critical section 실행
• signal()은 S를 하나 늘려줌

1. counting semaphore: 사용가능한 리소스의 개수만큼 semaphore이 있음
2. Binary semaphore: semaphore이 0과 1만 갖음(mutex lock과 동일)

 

 

 

Semaphore w/o busy waiting

• Semaphore이 value(프로세스 개수)와 list(프로세스들이 담겨있음)를 가진다.
• Block: 작업을 호출하는 프로세스를 적절한 waiting queue에 배치해 놓는다.
• Wake up: waiting queue에서 프로세스 하나를 제거하고 ready queue에 배치한다.

• Wait()에서 S가 0이하(전체 리소스의 수보다 작업을 호출하는 프로세스의 수가 더 많으면)이면 프로세스 하나를 waiting queue에 넣어 놓는다.
• Signal()에서는 S가 0이하이면 프로세스 하나를 waiting queue에서 꺼내서 ready queue에 넣는다.

 

 

 

Semaphore problem

Semaphore은 사용자가 임의로 signal()과 wait()를 지정할 수 있기 때문에 오류가 발생할 수 있음

 

 

 

Monitor

• High level로 synchronize 하기 위해 사용
• Monitor 안에다 공유 데이터와 공유 데이터에 접근하기 위한 procedure을 정의해 놓고 공유 데이터에 접근하기 위해서는 monitor 내부의 procedure을 통해서만 접근할 수 있도록 만들어 둔 것
• 모니터 내부의 procedure는 동시에 여러 개 실행되지 못함 -> lock을 걸 필요가 없이 모니터가 알아서 해줌

         

 

Condition variable

모니터 안에서 코드를 실행하다가 충족되지 않은 부분 때문에 오래 걸리는 경우 해당 프로세스를 잠들게 한다. 어떤 조건이 충족되지 않아서 잠들게 했는지에 따라 조건에 해당하는 것을 condition variable이라는 변수로 둘 수 있다.

Wait() – 어떤 프로세스를 잠들게 하기 위한 연산

Signal() – 누군가 x라는 condition variable을 다 쓰고 빠져나가면 x라는 조건 때문에 잠들어 있던 프로세스가 있는 경우 그 프로세스 중 하나를 깨워주는 연산

 

-        Monitor을 구현하기 위해 semaphore을 사용함

 

Semaphore mutex: mutual exclusion을 지키기 위해 사용하는 variable

Semaphore next: 다른 프로세스들에게 자신이 끝났음을 알려주기 위해 사용하는 variable

 

 

https://cs-ssupport.tistory.com/m/428

[OS] 5-2. Mutex Lock & Semaphore & Monitor