동시 데이터 구조

Concurrent data structure

컴퓨터 과학에서 동시 데이터 구조는 컴퓨터에 여러 개의 컴퓨팅 스레드(또는 프로세스)에 의해 접근을 위한 데이터를 저장하고 조직하는 특별한 방법이다.

역사적으로, 그러한 데이터 구조는 다중 컴퓨팅 스레드(또는 프로세스)를 지원하는 운영 체제를 갖춘 단일 프로세서 기계에 사용되었다.동시성이라는 용어는 프로세서가 데이터에 동시에 액세스하는 두 개의 작업을 실행하지 않았음에도 불구하고 운영체제에 의해 데이터에 대한 스레드 작업의 멀티플렉싱/인터리빙을 포착했다.

오늘날, 병렬 처리를 제공하는 멀티프로세서 컴퓨터 아키텍처가 지배적인 컴퓨팅 플랫폼이 되면서(멀티코어 프로세서의 확산을 통해), 이 용어는 여러 스레드에 의해 실제로 데이터에 동시에 액세스할 수 있는 데이터 구조를 주로 의미하게 되었다. 이는 서로 다른 프로세서에서 실행되기 때문이다.서로 의사소통하는 s.동시 데이터 구조(공유 데이터 구조라고도 함)는 일반적으로 공유 메모리라고 하는 추상적인 스토리지 환경에 상주하는 것으로 간주되지만, 이 메모리는 물리적으로 "긴밀하게 결합"되거나 스토리지 모듈의 분산 모음으로 구현될 수 있다.

기본 원리

병렬 또는 분산 컴퓨팅 환경에서 사용할 동시 데이터 구조는 여러 가지 면에서 단일 프로세서 기계에서 사용할 "순차적" 데이터 구조와 다르다.[1]가장 주목할 만한 것은 순차적 환경에서는 데이터 구조물의 속성을 명시하고 안전 특성을 제공하여 데이터 구조가 올바르게 구현되었는지 점검한다.동시 환경에서 규격은 구현이 제공해야 하는 활성 속성을 설명해야 한다.안전 속성은 보통 나쁜 일은 일어나지 않는다고 말하는 반면, 사랑 속성은 좋은 일이 계속 일어난다고 말한다.예를 들어, 이러한 속성은 선형 시간 논리를 사용하여 표현할 수 있다.

livity 요구사항의 유형은 데이터 구조를 정의하는 경향이 있다.메서드 호출은 차단 또는 비차단일 수 있다.데이터 구조는 한 종류로 제한되지 않으며, 일부 메서드 호출이 차단되고 다른 것들은 차단되지 않는 경우 결합을 허용할 수 있다(예: Java 동시성 소프트웨어 라이브러리에서 찾을 수 있다).

동시 데이터 구조의 안전 속성은 서로 다른 스레드에 의해 호출되는 방법의 상호연결이 많은 경우 이들의 행동을 포착해야 한다.인터리빙이 없는 순차적 설정에서 추상적인 데이터 구조가 어떻게 동작하는지를 지정하는 것은 상당히 직관적이다.따라서 동시 데이터 구조의 안전 속성(예: 연속성, 선형성, 순차 일관성 및 대기 정합성[1])을 주장하기 위한 많은 주요 접근방식은 순차적으로 구조 속성을 명시하고, 동시 실행을 순차적 데이터 집합에 매핑한다.

안전성과 탄력성을 보장하기 위해, 동시 데이터 구조는 일반적으로 스레드가 동시 데이터 액세스 및 수정 요청의 결과에 대해 합의에 도달할 수 있도록 허용해야 한다(항상 그렇지는 않지만).이러한 합의를 지원하기 위해, 복수의 스레드가 합의에 도달할 수 있도록 하는 현대의 멀티프로세서 기계에서 이용할 수 있는 특별한 원시 동기화 연산(동기화 원시 요소 참조)을 사용하여 동시 데이터 구조를 구현한다.이러한 컨센서스는 잠금장치를 사용하거나 잠금장치를 사용하지 않는 방식으로 차단할 수 있으며, 이 경우 비차단이 된다.동시 데이터 구조 설계에 대한 이론의 폭이 넓다(서적 참조 참조 참조).

설계 및 구현

동시 데이터 구조는 순차적 구조보다 설계와 검증이 훨씬 더 어렵다.

이러한 추가적인 난관의 주요 원인은 동시성인데, 이는 스레드가 완전히 비동기적이라고 생각되어야 한다는 사실에 의해 악화된다. 스레드는 운영 체제 선점, 페이지 결함, 인터럽트 등의 영향을 받는다.

오늘날의 기계에서는 프로세서와 메모리의 레이아웃, 메모리의 데이터 레이아웃, 멀티프로세서 아키텍처의 다양한 요소에 대한 통신 부하가 모두 성능에 영향을 미친다.더욱이, 정확성과 성능 사이에는 긴장이 있다: 성능 향상을 추구하는 알고리즘적 향상으로 인해 정확한 데이터 구조 구현을 설계하고 검증하는 것이 종종 더 어려워진다.[2]

성능의 핵심 척도는 구현 속도 향상에 의해 포착된 확장성이다.Speedup은 애플리케이션이 실행 중인 기계를 얼마나 효과적으로 사용하고 있는지를 나타내는 척도다.P 프로세서가 장착된 기계에서 속도 상승은 단일 프로세서의 구조 실행 시간과 P 프로세서의 실행 시간의 비율이다.이상적으로, 우리는 선형 속도 향상을 원한다: 우리는 P 프로세서를 사용할 때 P의 속도 증가를 달성하고 싶다.P와 함께 속도가 증가하는 데이터 구조를 확장 가능한 구조라고 한다.동시 데이터 구조의 성능을 어느 정도까지 확장할 수 있는가는 암달의 법칙으로 알려진 공식과 구스타프손의 법칙과 같은 좀 더 정제된 버전에 의해 포착된다.

동시 데이터 구조 성능의 주요 문제는 메모리 경합 수준이다. 즉, 여러 스레드가 동시에 메모리의 동일한 위치에 액세스하려고 시도함에 따른 메모리의 트래픽과 메모리의 트래픽 오버헤드.이 문제는 메모리에 대한 접근을 잠그는 차단 구현에서 가장 심각하다.잠금을 획득하기 위해서는 나사산이 반복적으로 그 위치를 수정하려고 시도해야 한다.캐시 일관성 있는 멀티프로세서(프로세서가 저장된 최신 값과 일관성을 유지하기 위해 하드웨어에 의해 업데이트되는 로컬 캐시를 갖는 프로세서)에서 이는 위치 수정을 시도할 때마다 대기 시간이 길어지며, 잠금 획득 시도에 실패한 추가 메모리 트래픽으로 인해 악화된다.

참고 항목

참조

  1. ^ a b Mark Moir and Nir Shavit (2007). "Concurrent Data Structures". In Dinesh Metha and Sartaj Sahni (ed.). 'Handbook of Data Structures and Applications' (1st ed.). Chapman and Hall/CRC Press. pp. 47–14–47–30. {{cite book}}:외부 링크 위치 chapter=(도움말)
  2. ^ Gramoli, V. (2015). More than you ever wanted to know about synchronization: Synchrobench, measuring the impact of the synchronization on concurrent algorithms (PDF). Proceedings of the 20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. ACM. pp. 1–10. Archived from the original (PDF) on 10 April 2015.

추가 읽기

  • 낸시 린치 "분산 컴퓨팅"
  • 하짓 아티야와 제니퍼 웰치 "분산 컴퓨팅:기초, 시뮬레이션 및 고급 주제, 2차 개정"
  • 더그 리아, "자바에서의 전류 프로그래밍: 설계 원리 및 패턴"
  • Maurice Herlihy와 Nir Shavit, "다중 프로세서 프로그래밍의 기술"
  • 매트슨, 샌더스, 매싱일 "병렬 프로그래밍을 위한 패턴"

외부 링크