Process Synchronization(1)_운영체제(5)

Synchronization

• 여러 개의 process가 협력하는 상황에서 resource를 share하는 상황에서 발생
• share 중에 read가 아닌 write가 하나라도 있어야한다.
• 이러한 실행 흐름을 조정하는 것
• 임의의 속도(arbitrarily)라고 가정을 해야 한다.
• CPU scheduling에 application이 관여할 수 없다.

problem

• 공유하는 자원을 제어하지 않으면 문제가 발생한다.
• Race condition : 실행시킬 때마다 결과가 순서에 따라 달라지는 현상 : non-deterministic
  • 문제가 생겼을 때 bug 재현이 어려운 문제도 있다.
• shared data에 접근하는 것을 제어해야하고 방법이 필요하다.
• buffer, queue, variable..

Critical Sections

• program에서 공유되고 있는 memory, files, resources 등이 있는 부분
• 상호 배제(mutual exclusion)를 만족하면서 접근해야한다.
  • 한 번에 하나의 process만 critical section에 들어간다.
  • 다른 process가 있다면 entry에서 기다렸다가 그 process가 떠나면 접근해야한다.
• entry section / critical section / exit section 순서로 코드가 진행된다.
• race condition을 야기한다.

Solution

• Mutual exclusion
• Progress
  • ex) 짝수는 process A, 홀수는 process B
  • mutual exclusive하지만, process의 처리 시간에 따라 안좋아질 수 있다.
• Bounded waiting(no starvation)
  • 일정의 time이 지나면 critical section에 있는 process를 바꾸는 방식
• Performance
  • 수행 능력이 좋아야한다.

Critical section 만들 때 기법

• Lock(Hardware) / Mutex(OS)
• Semaphores(OS)
• Monitors
  • language(compiler)가 지원하는 방식
  • ex) Java “synchronized”
• Message
  • recvfrom(), sendto() 등을 활용하여 순서를 정한다.

Locks

• 메모리 내에 lock에 관한 상태 변수가 있고 이를 다루는 2가지 함수가 있다.
• 서로 다른 두 process가 공유하는 object에 대해 작동하는 것.
  • acquire() : lock을 획득한다. lock이 free면 used mark 후 획득, lock을 다른 process가 사용하고 있다면 free가 될 때까지 wait
  • release() : used로 되어있다면 free mark 후 lock을 반납한다.
• spin lock : lock의 상태를 계속 체크하는 형태 – lock을 polling하는 것
• mutex : block작업을 하는 것

Using lock – mutual exclusion

• critical section에 입장 전 acquire, 나올 때 release를 해야 한다.
• lock이 사용되고 있을 때 acquire를 호출하면 lock이 release할 때까지 wait한다.
• 오직 1개의 process만이 lock을 소유한다.

Busy Waiting

• 원하는 자원을 얻기 위해 기다리는 것이 아니라 권한을 얻을 때까지 확인하는 것
• 권한 획득을 위해 CPU를 낭비하는 단점이 있다.

Serialization (순서화)

• P의 transaction이 일어나고 다음 Q의 transaction이 차례로 일어나는 것.

Implementing Locks

• Mutual exclusion 안될 수 있다. → while이후 바꿀 때 timer(interrupt)가 온다면 문제가 생긴다.
• Atomic operation : 분리하는 것이 아닌 하나의 동작으로 처리해야한다. - acquire이 나눠지면 안된다.

Solution

• Software-only algorithms : software로만 처리한다. 하지만 제약사항이 너무 많다.
• Hardware atomic instructions
  • test-and-set, compare-and-swap : hardware에서 처리
• Disalbe/Enable interrupts
  • Interrupt를 끄고 context switches를 일어나지 않게 한다.

Software-only Algorithms

• simple version
• tie 상황이 생겨 process 2개가 다 못 들어가는 경우가 생겨버린다.

Peterson’s Algorithm

• turn 변수를 사용하여 설정 / while 조건문에서 turn 변수에는 먼저 온 process의 번호가 작성되어있다.
• other 변수에 다른 process의 번호가 저장되기 때문이다.
• 제한된 개수의 process에만 사용 가능(2개)

Bakery Algorithm

• Findmax()까지 acquire 코드
• 대기표를 뽑아 기다리는 형식

Atomic Hardware Instructions

• 특별한 instruction으로, memory에서 read-modify-write가 1개의 cycle로 작동하는 것.
• 1개의 cycle로 작동을 하다 보니 interrupt가 중간에 발생할 수 없다.

Test–and–Set semantic

• rv라는 변수에 v를 읽어내고, v에 새로운 값을 작성하고 old value인 rv를 return
• 변수에 메모리 주소가 주어지면 이 값을 리턴하고 값에는 1을 넣는다.
• 원래 있던 값을 read와 함께 1을 해당 변수에 작성을 한다.

• 0을 보는 순간 바로 바꾸기 때문에 겹칠 일이 없다.

• 1개의 single cycle로 이루어진다.

Spinlocks problems

• Spinlocks
  • 낭비가 너무 심하다.
  • critical section의 길이가 길수록 CPU 낭비도 심해진다.
• OS의 도움을 받아 blocking 기능을 지원(Mutex)을 받는다.

Disabling Interrupts

• Interrupt를 금지하는 방법
• Multi core에서는 작동을 하지 않는다.
• 병행성이 떨어지게 된다.