본문 바로가기

Computer Science 254

Deadlock Deadlock concurrent하게 실행되는 프로세스가 있을 때, 그 프로세스들이 progress를 만들지 못하고 영원히 정지되는 현상을 말한다. 다음과 같은 상황은 deadlock에 빠질 수 있다. Deadlock의 조건 Deadlock이 발생하기 위해서는 아래 4가지 조건이 충족되어야 한다. 역은 성립하지 않는다. 즉, 아래 4가지 조건이 충족되어도 무조건 deadlock은 아니다. mutual exclusion critical section에 오직 하나의 프로세스만 들어갈 수 있다. hold and wait 어떤 프로세스가 이미 critical section에 들어가있고, 다른 critical section에도 들어가기 위해서 기다린다. 다른 프로세스에서 이미 들어가있는 critical sect.. 2021. 6. 20.
Synchronization Problems Classical Synchronization Problems 여러 전통적인 synchronization 문제가 있다. Semaphore와 mutex는 단지 primitive로, 실제 프로그래밍을 할 때 발생하는 문제에 대해서는 단순히 이용해서는 안되고 응용해야 한다. readers and writers problem dining-philosopher problem Readers and Writers Problem Critical section에 접근하는 프로세스가 2종류인 상황을 의미한다. reader : critical section에 읽기만 가능하다. writer : critical section에 쓰기만 가능하다. Race condition은 여러 프로세스가 동시에 한 shared resource.. 2021. 6. 20.
Synchronization with OS Support : Mutex Mutex 운영체제가 동기화를 위해 제공하는 primitive 이다. POSIX APIs Mutex를 위해 다음과 같은 POSIX API가 제공된다. int pthread_mutex_init(pthread_mutex_t *mutex, const pthread_mutexattr_t *mutex_attr) int pthread_mutex_destory(pthread_mutex_t *mutex) int pthread_mutex_lock(pthread_mutex_t *mutex) semaphore의 wait과 유사 lock을 잡지 못하면 block 된다. int pthread_mutex_unlock(pthread_mutex_t *mutex) semaphore의 signal과 유사 int pthread_mutex.. 2021. 6. 20.
Synchronization with OS Support : Semaphore Semaphore Semaphore는 synchronization primitive이다. 일반적인 동기화 문제를 해결하는데 primitive 한 수단이다. Bakery 알고리즘이나 peterson의 알고리즘은 synchronization 문제를 해결할 수는 있으나 알고리즘이 복잡하기 때문에 흔히 사용되지는 않는다. 일반적인 synchronization 문제의 경우 semaphore을 이용해서 해결한다. APIs Semaphore는 정수형 변수로, 운영체제가 특별하게 보호하는 변수이다. 때문에 임의로 접근하지 못하고 운영체제가 제공하는 api를 이용해서 접근해야 한다. 이런 api는 atomic하게 동작하며, 작동 중에는 다른 함수가 개입하지 못한다. wait(S) semaphore가 양수이면 1 감소한다.. 2021. 6. 20.
Synchronization with Hardware Support Synchronization with Hardware Support 다음과 같은 방법이 있다. interrupt disabling : disable/enable INT test-and-set : Intel에서 제공 swap : ARM에서 제공 Interrupt Disabling Critical section에서 disable INT (interrupt)를 해서 race condition이 일어나지 않게 한다. CPU가 1개라면 race condition은 스케줄링에 의해 발생한다. Critical section의 값이 바뀌기 전에 스케줄링이 일어나서 발생하는 것이다. 그리고 스케줄링은 대부분 timmer interrupt에 의해 발생한다. 따라서 critical section에서 disable INT (.. 2021. 6. 19.

티스토리툴바