Dynamic condition
Race condition
Essential condition
Critical condition
Mutual exclusion
Critical exclusion
Synchronous exclusion
Asynchronous exclusion
스레드(thread)
파이프(pipe)
세마포어(semaphore)
소켓(socket)
뮤텍스(mutex)
이진 세마포어(binary semaphore)
뮤텍스와 이진 세마포어
위에 언급된 모두 해당 안됨
Priority removal
Priority inversion
Priority exchange
Priority modification
하드웨어 레벨
소프트웨어 레벨
하드웨어 레벨과 소프트웨어 레벨 모두
수신 측의 프로세스 구현을 모르는 채 통신
수신 측의 프로세스 구현에 의존적인 통신
다른 프로세스에 데이터를 직접 공유
메시지의 발신자와 수신자의 이름을 기록
write message와 delete message
delete message와 receive message
send message와 delete message
receive message와 send message
하나의 통신 링크(communication link)가 N 개의 프로세스와 연결될 수 있다.
하나의 통신 링크는 정확히 두 프로세스와만 연결된다.
N 개의 프로세스가 있을 때 정확히 N/2 개의 통신 링크가 존재한다.
연결된 두 프로세스의 쌍(pair)마다 정확히 두 개의 통신 링크를 가진다.
프로세스 P와 Q 사이에서 메시지를 받아 전달해주는 프로세스 R이 존재한다.
두 프로세스 간의 통신을 돕기위한 별도 머신이 존재한다.
두 프로세스 간의 통신을 돕기위한 메일박스(mailbox)가 존재한다.
직접 통신(direct communication)보다 느리다.
메시지가 수신될 때까지 계속하여 메시지를 보낸다
메시지를 받을 때까지 계속하여 메지를 보낸다
메시지를 보내고 메시지를 받을 때까지 대기한다
메시지를 보내고 작업을 재개한다
Queue가 적어도 하나의 메시지를 저장할 수 있다.
송신자는 수신자가 메시지를 받아갈 때까지 블록된다.
송신자는 계속해서 메시지를 보낼 수 있지만 메시지가 큐에 머무르지 않는다.
송신자는 상황에 따라 블록될 수도 안될 수도 있다.
무버퍼링 메시지 시스템(no-buffering message system)
버퍼링 메세지 시스템(buffering message system)
유한 메시지 시스템(bounded message system)
무한 메시지 시스템(unbounded message system)
프로그램되어진 버퍼링
자동 버퍼링
사용자 정의 버퍼링
무버퍼링(no buffering)
wait-free 알고리즘 하에서는 기아 상태(starvation)가 없다.
lock-free 알고리즘은 lock이 없어 공유 자원을 위한 경쟁이 필요없다.
모든 wait-free 알고리즘은 lock-free이다.
wait-free 알고리즘이 lock-free보다 구현이 어렵다.
모든 wait-free 알고리즘은 obstruction-free이다.
모든 lock-free 알고리즘은 obstruction-free이다.
모든 obstruction-free 알고리즘은 lock-free이다.
obstruction-free 알고리즘이 가장 약한 수준의 자유도를 보장한다.
Data consistency
Data inconsistency
Data insecurity
Data breach
Secure section
Critical section
Non-critical section
Synchronized section
상호 배제(mutual exclusion)
진행 조건(progress)
한계 대기(bounded waiting)
위에 언급된 모두 해당
다른 프로세스들은 임계 구역을 실행하고 있으면 안된다
다른 프로세스들도 임계 구역을 실행하고 있어야 한다
수행이 끝날 때까지 모든 시스템 자원은 블록되어야 한다
임계 구역을 수행 중이던 프로세스의 종료 후
임계 구역 요청 진입 후
한 번 임계 구역 수행을 마친 후 다시
1
2
3
4
각 프로세스를 큐에 삽입한 후 순서대로 자원을 할당한다
각 프로세스에 중복될 수도 있는 번호를 주고 제일 작은 번호를 가진 프로세스부터 자원을 할당한다
각 프로세스에 고유 번호를 주고 제일 높은 번호를 가진 프로세스부터 자원을 할당한다
각 프로세스에 고유 번호를 주고 제일 작은 번호를 가진 프로세스부터 자원을 할당한다
Single
Static
Atomic
Solid
특정 프로세스의 실행 후에
주기적으로
원자성을 가지고
비동기적으로
하드웨어
소프트웨어
변수
임계 구역(critical section) 진입이 불가할때 CPU를 낭비한다.
문맥 교환(context switch) 시간을 절약하기 위해 사용된다.
싱글 프로세서보다 멀티 프로세서에서 효율적이다.
동시성이 떨어질 수 있다.
문맥 교환(context switch)이 느리다.
신뢰성이 떨어진다.
구현이 복잡하다.
stop
block
hold
wait
비정상적인 경우이다
Signal operation이 있을 때까지 임계 구역(critical section)을 실행 중인 프로세스 외에는 다른 작업을 할 수 없는 상태이다
임계 구역에 진입하기 위해 대기 중인 프로세스가 있는 상태이다
Blocked였던 프로세스가 ready queue로 옮겨지는 상황이다
상호배제(mutual exclusion)
점유대기(hold and wait)
선점(preemption)
순환대기(circular wait)
© Seunggon Kim