CAS lock-free
12231 단어 Lock
http://en.wikipedia.org/wiki/Compare-and-swap
In computer science , compare-and-swap (CAS) is an atomic instruction used in multithreading to achieve synchronization . It compares the contents of a memory location to a given value and, only if they are the same, modifies the contents of that memory location to a given new value. This is done as a single atomic operation. The atomicity guarantees that the new value is calculated based on up-to-date information; if the value had been updated by another thread in the meantime, the write would fail. The result of the operation must indicate whether it performed the substitution; this can be done either with a simple Boolean response (this variant is often called compare-and-set), or by returning the value read from the memory location (not the value written to it).
The following C function shows the basic behavior of a compare-and-swap variant that returns the old value of the specified memory location; however, this version does not provide the crucial guarantees of atomicity that a real compare-and-swap operation would:
int compare_and_swap (int* reg, int oldval, int newval)
{
int old_reg_val = *reg;
if (old_reg_val == oldval)
*reg = newval;
return old_reg_val;
}
lock-free 프로 그래 밍 은 정말 사람 을 사랑 하고 미워 하 게 한다.블 로 거들 은 이전에 lock-free 프로 그래 밍 에 관 한 글 을 몇 편 쓴 적 이 있다.예 를 들 어잠 금 없 는 프로 그래 밍 에 대하 여,병발 데이터 구조:매혹 적 인 원자.lock-free 프로 그래 밍 을 더욱 깊이 이해 하고 실천 하려 면CLR 2.0 Memory Model,병렬 데이터 구조:Stack를 참고 하 십시오.이 글 은 lock-free 기술 을 어떻게 사용 하 는 지 계속 논술 하지 않 고 부정적인 영향 에 대해 이야기 할 계획 이다.lock-free 에 대한 전면적 인 인식 을 갖 게 합 니 다.
lock-free 프로 그래 밍 하면 현실 적 으로 CAS 원 어 를 자주 사용 합 니 다.CAS 는 영어 Compare and Swap 의 약자 입 니 다.Windows 와.NET 플랫폼 에 서 는 역사적 인 이유 로 Interlocked API 로 쓰 여 있 습 니 다.원자 조작 이 x86 구조 CPU 에 대응 하 는 어 셈 블 리 명령 은 XCHG,CMPXHG,INC 등 이 있 습 니 다.물론 LOCK 를 접두사 로 추가 해 야 합 니 다. 병발 데이터 구조:매혹 적 인 원자 )。
CAS 원 어 는 경도 와 중도 경쟁 에서 프로그램 성능 을 크게 향상 시 킬 수 있 는 것 은 사실이다.그러나 모든 일 에 유리 하면 반드시 폐단 이 있다.CAS 원 어 는 프로그램의 신축성 을 극도로 말살 했다(기타 단점 은잠 금 없 는 프로 그래 밍 에 대하 여를 보십시오).관리 들 은 이런 관점 이 좀 과격 하 다 고 생각 할 지 모 르 지만 사실은 그렇다.블 로 거들 이 자세히 말 하도록 허락 해 주 십시오.
대부분의 CAS 작업 은 잠 금 이 들 어 오고 종료 할 때 발생 합 니 다.잠 금 은 단일 CAS 작업 으로 구 축 될 수 있 지만.NET CLR Monitor 류 는 두 개(하 나 는 Enter 방법,다른 하 나 는 Exit 방법)를 사용 했다.lock-free 알고리즘 도 잠 금 메커니즘 대신 CAS 원 어 를 자주 사용한다.그러나 메모리 재 구성 으로 인해 이러한 알고리즘 은 CAS 명령 을 사용 하 더 라 도 명시 적 인 울타리 가 필요 하 다.자물쇠 메커니즘 은 매우 사악 하지만,대부분의 합격 한 개발 자 들 은 자 물 쇠 를 최대한 적 게 가지 도록 하 는 것 을 안다.따라서 잠 금 메커니즘 이 얄 밉 고 성능 에 도 영향 을 미친다.그러나 대량의 빈번 한 CAS 조작 에 비해 프로그램의 신축성 에 영향 을 주지 않 는 다.
간단 한 예 를 들 어 100,000,000 회 를 늘 렸 다.이렇게 하려 면 몇 가지 방법 이 있다.단일 핵 단일 프로세서 에서 만 실행 된다 면 일반적인 메모리 작업 을 사용 할 수 있 습 니 다.
static volatile int counter = 0;
static void BaselineCounter()
{
for (int i = 0; i < Count; i++)
{
counter++;
}
}상기 코드 예제 가 스 레 드 가 안전 한 것 은 아니 지만 카운터 에 좋 은 시간 기준 을 제공 한 것 은 분명 하 다.다음은 스 레 드 안전 의 첫 번 째 방법 으로 LOCK INC 를 사용 합 니 다.
static volatile int counter = 0;
static void LockIncCounter()
{
for (int i = 0; i < Count; i++)
{
Interlocked.Increment(ref counter);
}
}현재 코드 예제 스 레 드 가 안전 합 니 다.우 리 는 또 다른 방식 을 채택 하여 노선 의 안전 을 보장 할 수 있다.만약 검증(예 를 들 어 메모리 넘 침 보호)을 실행 해 야 한다 면,우 리 는 보통 이런 방식 을 사용 할 것 이다.CMPXCHG(즉 CAS)를 사용 하 는 것 입 니 다.
static volatile int counter = 0;
static void CASCounter()
{
for (int i = 0; i < Count; i++)
{
int oldValue;
do
{
oldValue = counter;
}
while (Interlocked.CompareExchange(ref counter, oldValue + 1, oldValue) != oldValue);
}
}지금 재 미 있 는 질문 을 하 겠 습 니 다.캐 시 경쟁 을 할 때 어떤 방법 이 더 느 립 니까?깜짝 놀 랄 수도 있어.
Intel 4 핵 프로세서 에서 테스트 결 과 는 다음 과 같 습 니 다.
그림 에서 CPU 가 2 개의 핵 을 사용 할 때 BaselineCounter 방법 은 단일 핵 단일 상황 의 2.11 배 이다.다른 상황 은 유사 하 다.결과 비 교 를 통 해 우 리 는 더 많은 병발 성 이 결 과 를 더욱 어 묵 으로 만 들 었 다 는 것 을 알 수 있다.이것 은 대부분의 원인 이 메모리 경쟁 으로 인 한 것 이다.
CAS 작업 이 실 패 했 을 때 회전 대기 로 CASCounter 방법의 다 중 핵 처리 장치 에서 의 성능 을 개선 할 수 있 습 니 다(구체 적 인 기 교 는 여름 이 좋 은 계절 형의스스로 경량급 의 신 호 량 을 실현 하 다(1)|(2)).이 는 자물쇠 와 관련 된 내 연 이 자 물 쇠 를 방해 하 는 데 걸 리 는 시간 을 크게 줄 일 수 있다.
물론 이 예 는 극단 적 이다.그것 은 같은 메모리 주 소 를 자주 반복 해서 수정한다.기간 동안 특정한 함수 호출 을 삽입 하면 공유 메모리 에 접근 을 지연 시 키 면 스트레스 를 크게 완화 할 수 있 습 니 다.
예 를 들 어 두 개의 함수 호출 을 삽입 하면 우 리 는 다음 과 같은 데 이 터 를 얻 을 수 있 습 니 다.
64 개의 함수 호출 을 삽입 한 후 데 이 터 는 다음 과 같 습 니 다.
이때 우 리 는 다 핵 이 단 핵 보다 적은 시간 을 보 았 다.이것 이 바로 우리 가 병행 을 사용 하 는 데 가 져 온 가속 이다.여기 서 우 리 는 2 개 에서 64 개 함수 호출 로 결과 가 점점 좋아 졌 으 니 64 개 함수 호출 이 더 좋아 지지 않 을 까 생각 할 수 있 습 니 다.실제로 128 개의 함수 호출 을 삽입 한 후 가속 이 한계 에 이 르 렀 다.결 과 는 다음 과 같다.
가속 비 를 어떻게 계산 하 는 지 참고병행 사고[II].세상 에 공 짜 는 없다.CAS 도 예 외 는 아니다.우 리 는 lock-free CAS 코드 를 코드 에 신중하게 넣 어야 하 며,스 레 드 가 자주 실행 되 는 지 알 아야 합 니 다.우 리 는 공유 가 악마 라 는 것 을 다음 과 같은 말로 요약 할 수 있다.그것 은 근본적으로 응용 프로그램의 신축성 을 제한 하 므 로 가능 한 한 피 하 는 것 이 가장 좋다.공유 메모 리 는 병행 제어 가 필요 하고,병행 제 어 는 CAS 가 필요 하 다.CAS 는 또 매우 비 싸 공유 메모리 도 매우 비싸다.많은 사람들 이 lock-free 기술,사무 메모리,읽 기와 쓰기 자물쇠 등 프로그램 신축성 을 개선 할 수 있다 고 주장 한다.안 타 깝 게 도 이런 경 우 는 드물다.CAS 는 종종 잠 금 메커니즘 을 정확하게 실현 하 는 해결 방안 보다 더 나쁘다.공유 메모리,낙관적 실패 시도,캐 시 실효 등 이 큰 원인 이다.
Update 는 2009 년 4 월 8 일 21:10
overred 형 은 review 라 는 글 에서 좋 은 질문 을 했 습 니 다.Interlocked API 를 사용 할 때 공유 변 수 는 volatile 로 수식 하지 않 습 니 다.
이 문 제 를 더욱 편리 하 게 설명 하기 위해 서 나 는 간단 한 코드 예 시 를 써 서 다음 과 같다.
using System;
namespace Lucifer.CSharp.Sample
{
class Program
{
static volatile int x;
static void Main(string[] args)
{
Foo(ref x);
}
static void Foo(ref int y)
{
while (y == 0) ;
}
}
}우리 가 Visual Studio 에서 이 코드 를 컴 파일 할 때 IDE 는 컴 파일 경 고 를 보 냅 니 다.다음 과 같 습 니 다.
일반적으로 우 리 는 이러한 컴 파일 경고 에 대해 충분히 중시 해 야 한다.예 를 들 어 위의 예 에서 JIT 컴 파일 러 는 Y 가 변 하지 않 았 다 고 생각 하여 순환 을 일으킨다.IA 64 플랫폼 에서 이 는 특수 한 load-acquire 접근 대신 일반 메모리 접근 으로 여 겨 져 CPU 명령 재 구성 방면 의 bug 를 초래 할 수 있 습 니 다.그러나 한 가지 예 외 는 Interlocked API 와 Thread.VolatileXXX 방법 과 자 물 쇠 를 사용 하 는 것 이다.이 API 내부 에 서 는 메모리 울타리 와 하드웨어 원자 명령 을 명시 적 으로 요구 하기 때문에 외부 공유 변수 가 volatile 수식 을 사용 하 든 말 든 상관 하지 않 습 니 다.따라서 글 에서 사용 하 는 테스트 방법 은 안전 하 다.이 컴 파일 경고 가 귀 찮 으 면\#pragma 명령 을 사용 하여 이러한 경 고 를 금지 할 수 있 습 니 다.다음 과 같 습 니 다.
static volatile int x;
static void Foo()
{
#pragma warning disable 0420
Interlocked.Exchange(ref x, 1);
#pragma warning restore 0420
}물론 volatile 수식 자 를 전혀 사용 하지 않 아 도 된다.CLR 메모리 모델 은 이 점 을 보증 했다.
volatile 을 어떻게 정확하게 사용 합 니까? ，병렬 데이터 구조:volatile 변 수 를 이야기 합 니 다.를 참고 하 세 요.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
java Lock 인터페이스 상세 및 실례 코드java Lock 커넥터 java.util.concurrent.locks 인터페이스 잠금 public interface Loce Loce는 synchronized 방법과 문장을 사용하는 것보다 더 광범위한 잠금 조작...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
