잠금 장치 무료 할당 장치 구현 - 올바른지?

간단한 포인터 증가 할당 자 (그들은 공식적인 이름이 있습니까?) 나는 lock-free 알고리즘을 찾고 있습니다. 그것은 사소한 것처럼 보이지만 내 구현이 올바른지에 대한 피드백을 받고 싶습니다.잠금 장치 무료 할당 장치 구현 - 올바른지?

하지 스레드 구현 :

byte * head; // current head of remaining buffer 
byte * end; // end of remaining buffer 

void * Alloc(size_t size) 
{ 
    if (end-head < size) 
    return 0; // allocation failure 

    void * result = head; 
    head += size; 
    return head; 
}

스레드 안전 구현을 내 시도 : CMPXCHG이 (destination, exchangeValue, comparand) 인수과 비교 연동 교환이 원래의 값을

외모를 반환한다

void * Alloc(size_t size) 
{ 
    byte * current; 
    do 
    { 
    current = head; 
    if (end - current < size) 
     return 0; // allocation failure 
    } while (CMPXCHG(&head, current+size, current) != current)); 
    return current; 
}

나에게 잘해 - 다른 스레드가 get-current와 cmpxchg 사이에 할당하면 루프가 다시 시도합니다. 다른하실 말씀 있나요?

출처

2009-08-28 peterchen

어떻게 할당을 해제합니까? –

@Neil - 전에 이런 패턴을 보았습니다. 작업의 다른 부분에 대해 이런 식으로 경기장에서 신속하게 메모리를 할당하고 완료되면 전체 일을 무료로하십시오. – Michael

마이클이 말했듯이 - 당신은 청크 (머리) 전체를 단지 할당 해제합니다. 크고 불변의/자라는 유일한 데이터 구조를 구축하는 데 적합합니다. – peterchen

현재 코드가 작동하는 것 같습니다. 귀하의 코드는

do 
{ 
    original = *data; // Capture. 

    result = DoOperation(original); // Attempt operation 
} while (CMPXCHG(data, result, original) != original);

편집 부작용없이 데이터의 단일 단어를 운영하고있는 잠금이없는 알고리즘을 구현하는 데 사용할 수있는 간단한 패턴 아래의 코드와 동일하게 동작 : 내 원래의 제안을 interlocked add는 공간이 충분하지 않을 경우 할당 및 실패를 지원하기 때문에 여기서 제대로 작동하지 않습니다. InterlockedAdd를 사용하면 이미 포인터를 수정하고 후속 allocs가 실패하게됩니다.

출처

2009-08-28 21:01:25 Michael

잠금 장치 무료 할당 장치 구현 - 올바른지?

답변

관련 문제