[ ] Higher-level software tools to solve the CSP:
- Mutex Locks: the simplest tools for synchronization. (1개의 instance)
- Semaphore: more robust, convenient, and effective tool. (n개의 instance)
- Monitor: overcomes the demerits of mutex and semaphore.
- Liveness: ensures for processes to make progress.
[★] Mutex Lock
- mutex: mutual exclusion.
- to protect critical section and prevent race condition.
- a process must acquire the lock before entering a critical section. (열쇠를 사용해서 접근하고 반납한다)
- releases the lock when it exits the critical section.
발생하는 문제
- Busy waiting:
Any other process trying to enter its critical section must loop continuously in the call to acquire().
Busy waiting is clearly a problem in a real multiprogramming system,
+ where a single CPU core is shared among many processes.
+ wastes CPU cycles for some other processes to use productively.
열쇠를 받을 때 까지 무한으로 대기하게 됨. 괜히 무한 loop를 돌기위해 CPU를 사용하게 됨.
- Spinlock: ( busy waiting과 같은 말이다. busy waiting이 발생하더라도 그 상황이 반드시 worst는 아니다. )
the type of mutex lock using the method of busy waiting.
the process spins while waiting for the lock to become available.
However, spinlocks do have an advantage, in that no context switch is required waiting on a lock. a context switch may take considerable time.
In certain circumstances on multicore systems, spinlocks,
+ are the preferable choice for locking.
+ one thread can spin on one processing core while another thread performs its critical section on another core
어차피 놀고 있는 Core가 여러 개가 있다면 busy waiting이 발생하더라도, 바로 진입할 수 있으니 반드시 이 상태가 나쁜 것은 아니다. Context switch가 발생하지 않으므로 오히려 효율적으로 CPU를 사용할 수 있다.
[★] Semaphore (신호장치, 신호기)
- A semaphore S is an integer variable that, apart from initialization, is accessed only through two standard atomic operations: wait() and signal(), or sometimes P() and V().
- Using the counting semaphore:
Initialize a semaphore to the number of resources available.
When a process uses a resource
+ wait() on the semaphore: decrements the count.
When a process release a resource
+ signal() on the semaphore: increment the count.
When the count goes to 0, all resources are being used.
+ Then, processes that wish to use a resource will block
+ until the count becomes greater than 0.
Definition of wait() and signal()
- All modifications to the integer value of the semaphore in the wait() and signal() operations must be executed atomically.
S의 수만큼 열쇠를 주는 것처럼 이해하면 좋다. 즉 n을 1로 두면 mutex lock과 매우 유사하다. (차이점은 Atomic variable을 counting 한다는 점- 내 생각)
- Using the semaphore to solve synchronization problem:
Consider two processes P1 and P2 running concurrently.
+ P1 with a statement S1, and P2 with a statement S2.
Suppose that S2 should be executed only after S1 has completed.
+ Let P1 and P2 share a semaphore synch, initialized to 0.
- Semaphores also suffer from the problem of busy waiting.
이를 해결하기 위해서 wait() 할 때, scheduling를 이용하여 waiting queue와 ready queue를 사용한다.
무한 Loop로 사용되는 CPU 점유만을 죽이는 목적을 명시한채 코드를 확인하면 쉽게 이해 가능하다.
공유 메모리에 한 개의 변수만이 있고, semaphores 가 5개가 있다면 이는 Mutual exclusion이 성립되지 않는다.
- The difficulty of using semaphores:
The semaphore is convenient and effective for synchronization.
However, timing errors can happen
+ if particular execution sequences take place.
+ these sequences do not always occur, and it is hard to detect.
[ ] Monitor
기본적인 개념은 semaphore을 사용함에 있어서 사람의 실수(Code에서 쉽게 발생할 수 있는 실수)를 줄이기 위한 목적으로 나온 상위 도구이다. = one fundamental high-level synchronization construct.
- A monitor type is an ADT that includes a set of programmer-defined operations that are provided with mutual exclusion within the monitor. (하나의 클래스)
- declares the variables
+ whose values define the state of an instance of that type.
+ along with the bodies of function that operate on those variables.
- 모니터가 자체적으로 Synchronization mechanisms 을 가질 수 있도록 Condition variable을 추가하여 사용한다.
모니터 안에서 x, y를 개별적으로 모니터링한다.
[ ] Liveness
Monitor는 Method 전체를 동기화 시켜주는 것, 그러나 mutex만 보장한다. 오히려 dead lock 문제를 더 일으킨다.
- Two criteria for the CSP: the progress and bounded-waiting.
Semaphores and monitors cannot solve these requirements.
- Liveness refers to > 아직 남은 과제(dead lock, starvation) 을 해결하기 위해 나온 개념.
a set of properties that a system must satisfy
to ensure that processes make progress during their execution cycle.
- Two situations that can lead to liveness failures.
deadlock and priority inversion.
[★] Deadlock
- a situation where two or more processes are waiting indefinitely for an event that can be caused only by one of the waiting process.
'Computing > Operating System' 카테고리의 다른 글
| 12 > 동기화(4) (0) | 2021.11.15 |
|---|---|
| 11 > 동기화(3) (0) | 2021.11.15 |
| 09 > 동기화(1) (0) | 2021.11.15 |
| 08 > CPU scheduling (0) | 2021.11.15 |
| 06 - 07 > Thread [쓰레드, 멀티 쓰레딩] (0) | 2021.11.07 |