자물쇠가없는 진보 보장을 충족하는 쓰기 알고리즘 또는 데이터 구조의 어려움 중 하나는 동적 메모리 할당입니다. malloc 또는 new과 같은 호출은 휴대용 방식으로 잠금이 해제되지 않을 수 있습니다 . 그러나 많은 잠금이 필요없는 구현 인 malloc 또는 new이 있으며 잠금없는 알고리즘/데이터 구조를 구현하는 데 사용할 수있는 다양한 잠금없는 메모리 할당자가 있습니다.동적 잠금없는 메모리 할당 자
그러나 데이터 구조 나 알고리즘을 미리 할당 된 정적 메모리 풀로 특별히 제한하지 않는 한 실제로 이것이 잠금없는 진행 보장을 어떻게 완전히 만족시킬 수 있는지는 여전히 이해할 수 없습니다. 하지만 동적 인 메모리 할당이 필요하다면, 장기간에 걸쳐 lock-free 메모리 할당자가 맹목적으로 잠금을 해제 할 수있는 방법을 이해하지 못합니다. 문제는 잠금 장치가없는 malloc 또는 new이 얼마나 놀랍지 만 궁극적으로 메모리가 부족하여 운영 체제에 더 많은 메모리를 요청해야 할 때가 있습니다. 즉 궁극적으로 더 많은 메모리에 실제로 액세스하려면 brk() 또는 mmap() 또는 이와 같은 하위 수준 코드를 호출해야합니다. 그리고 이러한 낮은 수준의 호출이 잠금없는 방식으로 구현된다는 보장은 없습니다.
메모리 보호를 제공하지 않는 MS-DOS와 같은 고대 OS를 사용하거나 완전히 자물쇠가없는 운영 체제를 작성하지 않는 한이 방법을 사용하면 안됩니다. 실용적이지 않은 두 가지 시나리오 그렇다면 어떻게 동적 메모리 할당자가 정말로 lock-free가 될 수 있습니까?
맞아요 ...하지만 할당 자만 OS에서 큰 블록 만 요청하기 때문에 'sbrk()'에 대한 총 호출 횟수 또는 문제가되지 않는 지점까지 엄격하게 제한 할 수있는 모든 항목을 적시에 릴리스 할 필요는 없습니다. 물론 이것은 까다로운 실시간 요구 사항을 만족 시키지는 못하지만 동적 할당이 완전히 자물쇠가 없더라도 그러한 요구 사항을 만족시킬 것이라고는 생각하지 않습니다. –
지연에 대해 걱정 하시거나 https://en.wikipedia.org/wiki/Nonblocking_algorithm을 사용 하시겠습니까? 후자의 경우, 가장 좋은 OS는 다른 스레드가 mmap을 사용하지 못하도록 잠금을 유지하면서 스레드가 커널 내부에서 잠자기하는 것이 불가능하다고 생각합니다. 그래서 nonblocking 알고리즘을 작성하는 한, 스레드를 잠자 게하는 것이 가능하다면 잠금은 문제가되기 때문에 기술적으로는'mmap'을 사용하는 것이 문제가 아니라고 생각합니다. 크리티컬 섹션 내부의 몇 가지 CPU 캐시 미스는 아마도 당신이 얻는 최악의 경우 일 것이다. –
실제 시스템에서 실행되는 모든 할당자는 어느 시점에서 메모리를 모두 사용해야합니다. 고정 풀이 할당 될 때 잠금 해제 할당 자 (lock-free allocator)가 부족하다는 것은 운영체제가 충분하다고 판단 할 때 정상적인 할당 자와 질적으로 다른 점이다. –