spinlock(busy waiting)은 충분치 않다.
- 다른 것들에 의해 lock이 잡혀있을 경우
- cs안에서 조건이 맞지 않을 경우
**많은 CPU를 소모한다는 단점이 있다.**- spinlock과 disabling interrupts(끼어들기를 못하게 하는 것)는 매우 짧고 간단한 cs에 유용하다.
- 따라서 wasteful하고 primitive로써 활용되며 상호 배제 외에는 cpu사용량을 줄이거나 사용이 편하다 등 장점이 없다.
고수준 동기화
- block waiters : while문을 돌며 CPU소모를 하지 않고 block 상태로 대기한다.
- Leave interrupts enabled within cs : cs안에서 인터럽트를 disable하는 것은 매우 치명적인 약점이다.
- semaphore : binary(mutex) and counting
- monitors : mutexes and condition variables
- 따라서 세마포어와 모니터를 개발하여 primitive로써 atomic locks를 사용한다.
Semaphore #1
- lock보다 고수준 동기화 primitive
- busy waiting을 요구하지 않는다.
- wait, signal로 atomically 조작이 가능하다.
wait(s) : p(), decrement(감소), 세마포어가 오픈될 때까지 block한다. down()이라고도 함.(값을 내린다.)
signal(s) ; v(), increment(증가), 다른 것이 들어올 수 있도록 허락해준다. up()이라고도 함.(깂을 올린다.)- while로 cpu를 소모하지 않고 멈춰 있는 상태로 만들어 줄 수 있다.
- 각 세마포어는 프로세스와 스레드의 큐와 연관되어 있다.
만약 wait()이 스레드에 의해 호출되면 open일 때 스레드를 진행하고 closed일 때, 스레드를 block하고 큐에서 기다린다.
signal()이 세마포어를 열고 한 스레드를 unblock해주며 다른 스레드가 들어갈 수 있도록 해준다. 즉, 스레드가 큐에서 기다리고 있으면 한 스레드는 unblock된다.
큐에 스레드가 없으면 signal은 나중에 기억되고 wait이 호출된다.(open상태도 두는데 큐에서 기다리도록 한다.)
세마포어는 counter라 부르는 history를 갖는다. counter가 0 아래로 떨어지면 세마포어가 닫히며 wait()는 counter를 감소시키고 signal은 counter를 증가시킨다.
Semaphore #2
wait, signal 모두 cs에 있어도 문제가 없어야 하며 atomic operation이어야 문제 없이 동작한다.
system call과 interrupt disable/enable, H/W instruction을 통해 cs에도 문제가 없도록 지원하며 단, CPU 소모를 하지 않는 방향으로 해야 한다.
Binary semaphore(mutex)
cs에 상호적 배제를 보장한다.
그러나 한 번에 하나의 스레드/프로세스를 들어가도록 한다.
counter는 1로 초기화된다.
Counting Semaphore
여러 개의 유닛(프로세스, 스레드)이 cs에 접근 허용
counter는 N(유닛의 개수)으로 초기화
Deadlock
서로 다른 리소스를 잡고 있어 아무도 들어가지 못하는 상태이다.
즉, lock/semaphore 2개를 이용하여 사용할 때 문제가 생기며 두 개가 atomic해야 해결할 수 있다. 서로 S, Q를 기다리고 있다. 두 세마포어가 1로 초기화.
starvation
무한대 blocking
프로세스/스레드가 언젠가는 큐에서 빠져나와서 cs로 들어갈 수 있어야 하는데 그렇지 못하고 영원히 큐에서 기다리고 있는 상태이다.
priority inversion
높은 우선순위의 프로세스가 필요한 락을 낮은 우선순위의 프로세스가 잡고 있어서 스케쥴링 문제가 생긴다.
우선순위 상속 프로토콜(priority inheritance protocol)을 통해 해결
동기화 문제
Bounded buffer problem
Producer/consumer problem
리소스 버퍼는 프로듀서/컨슈머에 의해 공유된다.
프로듀서는 버퍼에 리소스(output, disk block, memory page)를 넣고 컨슈머는 버퍼로부터 리소스를 꺼낸다.
프로듀서와 컨슈머는 다른 rate(주기)로 동작한다. 서로 독립적이다.
count++, count--는 실제로 어셈블러 레벨로 바뀌면 3줄이 된다. 따라서 cs가 얼마든지 일어날 수 있다. 따라서 문제가 생긴다.
Dining Philosopher
철학자의 삶처럼 프로세스가 동작
생각하고, 배고프고, 젓가락 2개를 들고, 먹는다.
자신의 오른쪽에 젓가락 하나씩 있어서 2개를 집으면 누군가는 먹지 못한다.
->deadlock을 야기할 수 있다. ex) 모두가 배고파서 자신의 오른쪽 젓가락 하나씩 집었을 때, 아무도 먹지 못하는 상태가 된다.
세마포어의 문제점
- 공유되는 전역 변수를 필수적으로 갖는다. 이것은 소프트웨어공학 관점에서 매우 좋지 않으며 어디에서나 접근이 될 수 있다. 따라서 세마포어 메커니즘이 깨지는 문제가 발생할 수 있다.
- cs를 지키기 위한 mutual exclusion과 coordination(스케쥴링)이 한꺼번에 일어나고 있다. 이들의 사용에 제약이 없고 프로그래머가 잘 사용할 것이라고 믿는다. 즉, 적절한 사용의 보장이 없다.
- 프로그래머가 wait, signal을 적절히 사용해야 한다. wait -> cs -> signal
- Deadlock, starvation이 있다.
-> 따라서 사용하기 어렵고 버그를 양산하기 쉽다.
-> 또다른 접근법으로 프로그래밍 언어 지원을 사용한다.
세마포어의 문제점 해결(모니터)
지금까지 lock, semaphore는 개발자가 코딩해야 해서 실수를 만든다.
하지만 이를 막기 위해 컴파일러가 컴파일할 때 자동으로 동기화하는 코드를 삽입하고 프로그램 실행 시 이를 강제화한다.
동시 발생하는 프로세스들 간에 추상적인 데이터 타입의 안전한 공유를 허락한다.
모니터는 컴파일러에 의해 자동으로 삽입되는 소프트웨어 모듈이다.
공유된 데이터 구조를 포함한다.
공유된 데이터에서 작동하는 프로시저와 같은 개념으로 쓰인다.
이 프로시저들을 부르는 동시발생의 프로세스들 사이에서 동기화를 자동으로 제공한다.
구조화되지 않은 접근으로부터 데이터를 보호한다.
컴파일러에 의해 자동으로 기계적으로 삽입되기 때문에 오직 프로시저를 통해 데이터를 접근한다. ex) Java synchronized keyword
