라이브니스

위키백과, 우리 모두의 백과사전.
둘러보기로 가기 검색하러 가기

동시성 컴퓨팅에서, 라이브니스란, 시스템에서 동시에 실행되는 구성 요소("프로세스")가 임계 영역(여러 프로세스에 의해 동시에 실행될 수 없는 프로그램의 일부분)으로 "교대로 전환"해야 한다는 사실에도 불구하고 시스템이 진행되도록 하는 동시성 시스템 속성의 한 집합을 나타낸다.[1] 라이브니스 보장은 운영 체제와 분산 시스템에 있어 중요한 속성이다. [2]

라이브니스 속성은 실행 종료 이후 어떤 시점에 "좋은" 이벤트가 이론 상 일어날 수 있기 때문에 분산 시스템의 유한 실행 내에서 위반될 수 없다. 결과의 무결성은 라이브니스 프로퍼티의 한 예이다.[3] 모든 속성들은 안전성과 라이브니스 속성의 교차점으로 표현될 수 있다.[4]

라이브니스의 형태[편집]

여러 형태의 라이브니스가 인정된다. 다음 내용들은 일부 상호 배제 (mutex) 장치에 의해 보호되는, 임계 영역을 갖는 멀티프로세스 시스템의 용어로 정의된다. 모든 프로세스는 mutex를 올바르게 사용할 것으로 가정된다(과정은 임계 영역 실행 종료로 정의된다).

  • 약하긴 하지만, 교착 상태로부터 자유로운 것이 라이브니스의 한 형태이다. 어떤 상호 배제 장치에 의해 보호되는, 멀티 프로세스와 단일 임계 영역이 존재하는 시스템을 가정해보라. 프로세스 그룹이 특정 시점에 임계 영역에 대한 액세스를 위해 경쟁할 때, 일부 프로세스가 결국 이후 시점에 때에 맞춰 진행한다면, 그러한 시스템은 교착 상태로부터 자유롭다고 말할 수 있다. 해당 프로세스는 앞서 언급한 그룹에 속할 필요는 없다(그 프로세스는 이전 시점이든 또는 이후 시점이든 액세스를 얻었을 수도 있다).[5]
  • 기아 상태 (또는"유한 바이패스")로부터 자유로운 것은 교착 상태보다 더 강력한 라이브니스 보장이다. 임계 영역에 대한 액세스에 대해 경쟁하는 모든 프로스세가 결국 진행될 것임을 확실히 한다. 기아 상태로부터 자유로운 모든 시스템은 교착 상태로부터도 자유롭다.[5]
  • 바운드 바이패스에 대한 요구 사항은 여전히 더 강력한다. 즉, n 개의 프로세스가 임계 영역에 대한 액세스를 위해 결정하고 있을 경우, 각각의 프로세스는 어떤 함수 f 에 대해 다른 프로세스에 비해 최대 f(n) 회까지 우회한 후 진행된다.[5]

관련 사항[편집]

  • 넌블로킹 알고리즘

참조 문헌[편집]

  1. Lamport, L. (1977). “Proving the Correctness of Multiprocess Programs”. 《IEEE Transactions on Software Engineering》 (2): 125–143. doi:10.1109/TSE.1977.229904. 
  2. Luís Rodrigues, Christian Cachin; Rachid Guerraoui (2010). 《Introduction to reliable and secure distributed programming》 2.판. Berlin: Springer Berlin. 22–24쪽. ISBN 978-3-642-15259-7. 
  3. Bailis, P.; Ghodsi, A. (2013). “Eventual Consistency Today: Limitations, Extensions, and Beyond”. 《Queue》 11 (3): 20. doi:10.1145/2460276.2462076. 
  4. Alpern, B.; Schneider, F. B. (1987). “Recognizing safety and liveness”. 《Distributed Computing》 2 (3): 117. doi:10.1007/BF01782772. 
  5. Raynal, Michel (2012). 《Concurrent Programming: Algorithms, Principles, and Foundations》. Springer Science & Business Media. 10–11쪽. ISBN 3642320279.