• 카테고리

    질문 & 답변
  • 세부 분야

    게임 프로그래밍

  • 해결 여부

    미해결

Queue가 비어있을 때, TryPop 질문입니다.

24.05.15 05:00 작성 24.05.15 06:16 수정 조회수 94

0

	shared_ptr<T> TryPop()
	{
		// [data][data][ ]
		// [head][tail]

		CountedNodePtr oldHead = _head.load();

		while (true)
		{
			// 참조권 획득 (externalCount를 현시점 기준 +1 한 애가 이김)
			IncreaseExternalCount(_head, oldHead);

			Node* ptr = oldHead.ptr;
			if (ptr == _tail.load().ptr)
			{
				ptr->ReleaseRef();
				return shared_ptr<T>();
			}

			// 소유권 획득 (head = ptr->next)
			if (_head.compare_exchange_strong(oldHead, ptr->next))
			{
				T* res = ptr->data.load(); // exchange(nullptr); 로 하면 버그 있음!
				FreeExternalCount(oldHead);
				return shared_ptr<T>(res);
			}

			ptr->ReleaseRef();
		}
	}

static void IncreaseExternalCount(atomic<CountedNodePtr>& counter, CountedNodePtr& oldCounter)
{
    while (true)
    {
       CountedNodePtr newCounter = oldCounter;
       newCounter.externalCount++;

       if (counter.compare_exchange_strong(oldCounter, newCounter))
       {
          oldCounter.externalCount = newCounter.externalCount;
          break;
       }
    }
}
void ReleaseRef()
{
    NodeCounter oldCounter = count.load();

    while (true)
    {
       NodeCounter newCounter = oldCounter;
       newCounter.internalCount--;

       // 끼어들 수 있음
       if (count.compare_exchange_strong(oldCounter, newCounter))
       {
          if (newCounter.internalCount == 0 && newCounter.externalCountRemaining == 0)
             delete this;

          break;
       }
    }
}

TryPop을 할 때는 ExternalCount를 증가시키는데
head와 tail이 같을 경우에는 internal 카운트를 감소시키고 return 합니다.

만약 push가 없고 pop만 반복된다면,
ExternalCount는 계속 증가하고
internalCount는 계속 감소하는것같은데 맞나요?

 

externalCount 와 internalCount가 일정해야하는게 옳은 결과값 같아서 질문합니다.

답변 1

답변을 작성해보세요.

0

인프런 AI 인턴님의 프로필

인프런 AI 인턴

2024.05.17

안녕하세요, 인프런 AI 인턴입니다.

질문하신 내용을 기반으로 답변 드리겠습니다. shared_ptr<T> TryPop() 함수 내에서 Queueheadtail이 같다면, 즉 Queue가 비어있을 경우에는 NodeinternalCount를 감소시키고, 해당 Node에 더 이상 접근할 수 없음을 의미하는 shared_ptr<T>() 를 반환합니다. 여기서 질문하신 것처럼, push 작업이 없고 pop 작업만 반복될 경우, externalCountIncreaseExternalCount() 함수를 통해 각 pop 시도 때마다 증가하게 됩니다.

externalCountNode에 대한 외부에서의 참조 횟수를 의미하고, internalCountNode 내부적으로 관리되는 참조 횟수의 감소를 나타냅니다. 따라서, 반복적인 pop 연산에서 push가 일어나지 않는 경우, externalCount는 계속 증가하고 internalCount는 감소하는 것이 맞습니다.

그러나 이 작업의 근본적인 목적은 Queue의 다음 Node로의 안전한 이동과 소유권의 전환을 보장하는 것입니다. externalCountinternalCount의 균형이 깨지는 것 같지만, 실제로는 Queue의 안전한 동작을 위해 설계된 메커니즘의 일부입니다. externalCount는 해당 Node가 여전히 사용 중임을 나타내고, internalCount 감소는 해당 Node의 사용이 종료되었음을 의미합니다. externalCount가 증가하는 것은 해당 Node의 접근이 아직 안전함을, 즉 다른 스레드에서 해당 Node를 접근할 수 있다는 가능성을 염두에 두고 카운트를 증가시키는 것입니다.

이러한 설계는 멀티스레딩 환경에서 Queue의 안전한 사용을 보장하기 위한 것으로, 각 Node에 대한 참조가 안전하게 관리되도록 합니다. 따라서, externalCountinternalCount의 동작은 Queue의 올바른 동작을 위해 의도적으로 설계된 것입니다.