맨위로가기

라이브니스

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

라이브니스는 멀티프로세스 시스템에서 프로세스가 임계 영역에 접근하고 실행을 완료하는 것을 보장하는 속성이다. 라이브니스는 교착 상태로부터의 자유, 기아 상태로부터의 자유, 경계 있는 바이패스 등 여러 형태로 정의될 수 있으며, 기아 상태로부터의 자유는 교착 상태로부터의 자유보다 강력한 보장이다. 경계 있는 바이패스는 프로세스가 임계 영역에 접근하려는 시도에 대해 다른 프로세스에 의해 추월당하는 횟수를 제한하여 라이브니스를 보장하는 가장 강력한 방법이다. 라이브니스는 안전성과 구분되며, 경계 있는 추월은 라이브니스 속성으로 단정할 수 없다.

광고

더 읽어볼만한 페이지

  • 병행 컴퓨팅 - 슈퍼컴퓨터
    슈퍼컴퓨터는 일반 컴퓨터보다 훨씬 높은 성능을 가진 컴퓨터로, 복잡한 계산과 시뮬레이션을 수행하며, 프로세서, 메모리, 스토리지, 네트워크 등으로 구성되어 병렬 처리를 통해 높은 성능을 구현하고, 군사, 기상 예측, 과학 기술 분야, 인공지능 등 다양한 분야에서 활용되고 있다.
  • 병행 컴퓨팅 - 프로세스
    프로세스는 컴퓨터에서 실행되는 프로그램의 인스턴스로, 운영 체제가 시스템 자원을 효율적으로 관리하며 멀티태스킹 환경에서 독립적인 실행 흐름을 유지한다.

2. 라이브니스의 형태

라이브니스는 시스템의 특성에 따라 여러 형태로 정의된다. 주로 상호 배제(mutex) 장치로 보호되는 임계 영역이 있는 멀티프로세스 시스템에서 논의된다. 이때 모든 프로세스는 상호 배제 규칙을 올바르게 따르며, 임계 영역 실행을 성공적으로 마치는 것을 '진행'이라고 정의한다.

주요 라이브니스 형태는 다음과 같으며, 뒤로 갈수록 더 강력한 보장 수준을 의미한다.


  • 교착 상태로부터의 자유 (Deadlock Freedom): 가장 기본적인 라이브니스 보장 형태로, 임계 영역 접근을 위해 경쟁하는 프로세스 그룹이 있을 때, 이후 어떤 프로세스든 결국 임계 영역에 진입하여 진행할 수 있음을 의미한다. 시스템 전체가 멈추는 교착 상태가 발생하지 않음을 보장한다.[8]
  • 기아 상태로부터의 자유 (Starvation Freedom): 교착 상태로부터의 자유보다 더 강력한 보장이다. 임계 영역 접근을 원하는 모든 프로세스가 언젠가는 반드시 해당 영역에 진입하여 실행될 수 있음을 보장한다. 특정 프로세스가 무한정 기다리게 되는 기아 상태가 발생하지 않는다.[8]
  • 경계 있는 바이패스 (Bounded Bypass): 가장 강력한 라이브니스 보장 형태이다. 기아 상태로부터의 자유를 보장할 뿐만 아니라, 특정 프로세스가 임계 영역에 진입하기 위해 다른 프로세스에게 순서를 양보하는 횟수에 상한선이 있음을 보장한다. 즉, 각 프로세스는 정해진 횟수 이상으로 추월당하지 않고 임계 영역에 진입할 수 있다.[8]

2. 1. 교착 상태로부터의 자유 (Deadlock Freedom)

교착 상태로부터 자유로운 것은 라이브니스의 한 형태이며, 상대적으로 약한 수준의 보장이다. 여러 프로세스가 상호 배제 장치로 보호되는 하나의 임계 영역을 사용하는 시스템을 가정해 보자. 어떤 시점에 여러 프로세스가 임계 영역 진입을 위해 경쟁하고 있을 때, 이후 시점에 어떤 프로세스든 결국 임계 영역에 진입하여 작업을 진행할 수 있다면 이 시스템은 교착 상태로부터 자유롭다고 할 수 있다. 이때 임계 영역에 진입하는 프로세스는 반드시 처음에 경쟁하던 그룹에 속한 프로세스일 필요는 없으며, 경쟁 시작 전이나 후에 접근 권한을 얻은 다른 프로세스일 수도 있다.[8]

2. 2. 기아 상태로부터의 자유 (Starvation Freedom)

기아 상태(또는 "유한 바이패스")로부터 자유로운 것은 교착 상태로부터의 자유보다 더 강력한 라이브니스 보장이다.[8] 이는 임계 영역에 대한 접근을 위해 경쟁하는 모든 프로세스가 결국에는 해당 영역에 진입하여 실행될 수 있음을 보장한다. 따라서 기아 상태로부터 자유로운 시스템은 교착 상태로부터도 자유롭다.

2. 3. 경계 있는 바이패스 (Bounded Bypass)

경계 있는 바이패스(Bounded Bypass)는 라이브니스 보장 중 가장 강력한 수준으로, 기아 상태로부터의 자유보다 더 엄격한 조건을 요구한다.

시스템 내에 n개의 프로세스가 임계 영역에 접근하기 위해 경쟁한다고 가정할 때, 경계 있는 바이패스는 특정 프로세스가 임계 영역 접근을 요청한 후 다른 프로세스에 의해 추월당하는 횟수에 상한선이 있음을 보장한다. 즉, 어떤 함수 f(n)이 존재하여, 각 프로세스는 최대 f(n)번만 다른 프로세스에게 순서를 양보한 뒤에는 반드시 임계 영역에 진입할 수 있게 된다. 이는 특정 프로세스가 무한정 기다리게 되는 기아 상태를 방지할 뿐만 아니라, 대기 시간에 대한 예측 가능성을 높여준다.

3. 라이브니스와 안전성

B. 알펀(B. Alpern)은 교착 상태(deadlock) 발생 여부를 예시로 들어 안전성과 라이브니스를 구분한다. 안전성은 시스템이 교착 상태와 같은 특정 '나쁜' 상태에 절대로 도달하지 않아야 한다는 속성으로, 시스템이 항상 '안전한' 상태를 유지해야 함을 의미한다.

반면, 라이브니스는 시스템 내의 어떤 프로세스가 결국에는 작업을 수행하거나 상태가 변경될 것이라는 속성이다. 예를 들어, 특정 프로세스가 영원히 멈춰있지 않고 언젠가는 반드시 진행될 것이라는 보장이 라이브니스에 해당하며, 이는 시스템이 '살아있음'을 나타낸다.

이 두 속성에 대한 더 자세한 형식적 정의와 구체적인 예시는 하위 섹션에서 다룬다.

3. 1. 형식적 구별

안전성과 라이브니스는 시스템의 중요한 속성으로, 특정 조건을 나타내는 술어 P(t)(t는 시간)를 사용하여 형식적으로 구별할 수 있다. 안전성은 일반적으로 시스템이 원치 않는 상태에 도달하지 않음을 보장하고, 라이브니스는 시스템이 결국 원하는 상태에 도달함을 보장하는 속성을 의미한다.

각 속성에 대한 구체적인 형식적 정의와 예시는 하위 '안전성' 및 '라이브니스' 섹션에서 자세히 설명한다.

3. 1. 1. 안전성

B. 알펀에 따르면, 데드락 프리(deadlock-free, 교착 상태 없음)는 안전성 속성이다. 그는 시스템의 상태가 데드락이 있는 상태(빨간색 상태)와 데드락이 없는 상태(녹색 상태)로 나뉜다고 가정한다. 이때 시스템이 영원히 녹색 상태에 머무르는 것, 즉 빨간색 상태가 되지 않는 속성이 바로 안전성 속성이다.

안전성과 유효성(라이브니스)의 구분은 술어 P(t)를 통해 형식적으로 확립할 수 있다. 여기서 t는 시간을 의미하며, t_0는 라이브니스와 안전성 특성을 평가하기 시작하는 시점이다. 예를 들어, x를 데드락 프리임을 보장하고 싶은 프로세스(또는 스레드)라고 가정해보자.

안전성은 다음과 같은 형식으로 정의된다:

\forall t \ge t_0: P(t) = \textrm{False}.

이는 특정 '나쁜' 상태를 나타내는 P(t)가 시간 t_0 이후의 모든 시간 t에 대해 결코 참(True)이 되어서는 안 된다는 의미이다. 예를 들어, P(t)가 "x가 시간 t에 교착 상태에 있다"는 것을 의미한다면, 안전성은 프로세스 x가 절대로 데드락 상태에 빠지지 않아야 함을 나타내는 속성이 된다.

3. 1. 2. 라이브니스

B. 알펀에 따르면, 교착 상태(데드락)가 없는 상태(deadlock-free)는 안전성 속성이다. 시스템 상태를 교착 상태가 있는 상태(빨간색 상태)와 없는 상태(녹색 상태)로 나눌 수 있다고 가정할 때, 시스템이 영원히 녹색 상태에 머무르는 것(즉, 빨간색 상태가 되지 않는 것)이 안전성 속성이다. 하지만 상태 구분이 명확하지 않은 경우, 시스템 내의 어떤 프로세스가 결국에는 진행될 것이라는 속성을 라이브니스 속성이라고 한다.

안전성과 라이브니스의 구분은 특정 조건 P(t)를 통해 형식적으로 정의할 수 있다. 여기서 t는 시간을 의미하며, t_0는 속성을 평가하기 시작하는 시점이다. 예를 들어, 교착 상태가 없음을 보장하고 싶은 프로세스(또는 스레드) x가 있다고 가정해 보자.

  • 안전성: 모든 시간 t \ge t_0에 대해 P(t)는 항상 거짓이다.

\forall t \ge t_0: P(t) = \textrm{False}.

  • 예시: P(t)가 "x가 시간 t에 교착 상태에 있다"는 것을 의미한다면, 안전성은 x가 절대로 교착 상태에 빠지지 않음을 보장한다.

  • 라이브니스: 임의의 시간 t_1 \ge t_0에 대해, 그 이후 언젠가(t \ge t_1이고 유한한 시간 t < \infty) P(t)가 참이 되는 순간이 반드시 존재한다.

\forall t_1 \ge t_0, \exists t \ge t_1, t < \infty: P(t) = \textrm{True}.

  • 예시: P(t)가 "x가 시간 t에 대기 상태를 벗어나거나 멈춤 상태에서 벗어나 진행한다"는 것을 의미한다면, 라이브니스는 x가 결국에는 작업을 수행하거나 상태가 변경될 것임을 보장한다. 즉, 영원히 대기하거나 멈춰 있지 않는다.

4. 경계 있는 추월 (Bounded Overtaking) vs. 경계 있는 바이패스 (Bounded Bypass)

경계 있는 추월(Bounded Overtakingeng)은 어떤 프로세스가 임계 구역 진입을 선언한 후, 해당 프로세스가 실제로 진입하기 전까지 다른 프로세스들이 그 프로세스를 추월하는 횟수가 제한되는 것을 의미한다. 하지만 추월 횟수가 제한되더라도 해당 프로세스가 임계 구역에 반드시 들어갈 수 있다는 보장은 없다. 예를 들어, 교착 상태에 빠진 시스템에서는 어떤 프로세스도 다른 프로세스를 추월하지 않으므로 '경계 있는 추월'은 자명하게 성립하지만, 임계 구역 진입은 불가능할 수 있다. 따라서 '경계 있는 추월' 자체만으로는 라이브니스 속성이라고 보기 어렵다. 프로세스 P1이 임계 구역 진입을 시도할 때마다, 다른 프로세스 P2는 P1이 진입을 시도하기 전에 최대 한 번만 임계 구역에 진입할 수 있도록 제한하는 경우가 '경계 있는 추월'의 한 예시이다.

반면, 경계 있는 바이패스(Bounded Bypasseng) 또는 경계 있는 대기(Bounded Waitingeng)는 어떤 프로세스가 임계 구역 진입 의사를 밝힌 후, 다른 프로세스들에 의해 추월(바이패스)되는 횟수가 시스템 내 프로세스 수에 기반한 함수에 의해 제한되는 것을 의미한다. 중요한 점은 '경계 있는 바이패스'가 해당 프로세스가 반드시 임계 구역에 진입할 수 있음을 보장한다는 것이다.

'경계 있는 추월'과 '경계 있는 바이패스'의 구분은 미묘할 수 있다. 기아 방지(starvation freedom) 속성과 '경계 있는 추월' 속성이 함께 만족될 때, 이는 '경계 있는 바이패스'를 의미하게 된다. 즉, '경계 있는 바이패스'는 라이브니스 속성과 안전성 속성이 결합된 특성으로 볼 수 있다.[3]

5. 관련 사항


  • 넌블로킹 알고리즘

참조

[1] 논문 Proving the Correctness of Multiprocess Programs
[2] 서적 Introduction to reliable and secure distributed programming Springer Berlin
[3] 서적 Liveness by invisible invariants
[4] 논문 Proving the Correctness of Multiprocess Programs
[5] 서적 Introduction to reliable and secure distributed programming
[6] 논문 Eventual Consistency Today: Limitations, Extensions, and Beyond
[7] 논문 Recognizing safety and liveness
[8] 서적 Concurrent Programming: Algorithms, Principles, and Foundations


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com