33. 자동 파티 매칭의 정원 초과 (동시 배치 경합)

난이도 하

내 리뷰 · C#

내 리뷰 · C++

해설 · C#

해설 — 자동 파티 매칭의 정원 초과 (동시 배치 경합)

난이도: 하

요약

TryAdd는 "정원 확인 → (잠깐의 처리) → 추가"를 하나의 원자 단위로 묶지 않는다. 여러 워커가 동시에 같은 파티에 들어오면 모두 (A)에서 "자리 있음"을 통과한 뒤 (B)에서 추가하여 정원을 넘긴다. 게다가 List<int>는 스레드 안전하지 않아 동시 Add가 내부 배열을 깨뜨릴 수 있다.

문제점

[경쟁 조건 / check-then-act(TOCTOU)]
- 증상: 4인 파티에 5명 이상이 들어가거나, List 동시 수정으로 IndexOutOfRangeException·원소 유실·중복이 발생.
- 재현 조건: 현재 인원이 3일 때 워커 2개가 거의 동시에 진입 → 둘 다 (A)에서 3 < 4 통과 → AssignSlot 처리 동안 서로의 추가를 보지 못함 → 둘 다 (B) 실행 → 인원 5.
- 근본 원인: 검사 시점의 값(Count)과 행동 시점(Add) 사이에 다른 스레드가 끼어들 수 있다. 검사와 갱신이 원자적이지 않다. AssignSlot의 처리 시간이 창(window)을 넓혀 충돌 확률을 높인다.
[비스레드세이프 컬렉션]
- List<T>는 동시 쓰기에 안전하지 않다. 정원 문제와 별개로 Add가 재할당/이동 중일 때 다른 스레드가 끼어들면 상태가 깨진다.

수정안

검사와 추가를 같은 임계 구역에 넣는다. 비용이 큰 AssignSlot은 자리를 "예약"한 뒤 락 밖에서 처리한다.

public sealed class Party
{
    public const int MaxMembers = 4;
    public int PartyId { get; }
    private readonly List<int> _members = new();
    private readonly object _gate = new();

    public Party(int id) => PartyId = id;

    public int Count { get { lock (_gate) return _members.Count; } }

    public bool TryAdd(int playerId)
    {
        lock (_gate)
        {
            if (_members.Count >= MaxMembers) return false;
            if (_members.Contains(playerId)) return false; // 중복 배치 방지(멱등)
            _members.Add(playerId);                        // 검사+추가가 원자적
        }
        // 무거운 처리(슬롯 인덱스 계산, 입장 패킷)는 자리 확보 후 락 밖에서.
        AssignSlot(playerId);
        return true;
    }

    private void AssignSlot(int playerId) { /* ... */ }
}

AssignSlot이 실패할 수 있다면 실패 시 추가를 되돌려야(remove) 한다.

더 나은 설계

원자적 카운터로 자리 예약: 인원을 int로 두고 Interlocked.Increment 후 한도 초과면 Interlocked.Decrement로 롤백하는 "예약 후 확정" 패턴은 락 없이 정원을 지킬 수 있다. 다만 멤버 목록 자체의 일관성은 여전히 동기화가 필요하므로, 보통은 짧은 lock이 가장 단순하고 정확하다.
단일 소유 스레드(액터): 파티 변경을 한 스레드(또는 파티별 직렬 큐)로 일원화하면 락 없이도 경합이 사라진다. MMORPG에서 "파티/방은 한 스레드가 소유" 모델이 흔하다. 트레이드오프: 그 스레드가 병목이 될 수 있고, 교차-파티 작업(이전 등)은 메시지로 조율해야 한다.
트레이드오프: 락은 단순·정확하지만 경합이 심하면 직렬화 비용. 액터 모델은 경합을 제거하지만 설계 복잡도와 지연이 늘 수 있다.

면접 포인트

"검사하고 나서 행동하기(check-then-act)"는 검사와 행동이 한 임계 구역 안에 있어야 의미가 있다 — 정원·재고·중복 가입의 단골 버그.
무거운 작업을 락 안에서 하면 임계 구역이 길어진다. "자리 예약은 짧은 락, 실제 처리는 락 밖"으로 분리하는 패턴을 설명할 수 있는가.
List<T>/Dictionary<T>는 동시 쓰기에 안전하지 않다는 점, 그리고 멱등성(같은 플레이어 중복 배치 방지)을 함께 챙겨야 함을 짚는다.

해설 · C++

해설 — 자동 파티 매칭의 정원 초과 (동시 배치 경합)

난이도: 하

요약

try_add는 "정원 확인 (A) → 처리 → 추가 (B)"를 하나의 원자 단위로 묶지 않는다. 여러 스레드가 같은 파티에 동시에 들어오면 모두 (A)를 통과한 뒤 (B)에서 추가하여 정원을 넘긴다. 또한 std::vector에 대한 동시 push_back은 정의되지 않은 동작(자료 경쟁)이다.

문제점

[경쟁 조건 / check-then-act(TOCTOU)]
- 증상: 4인 파티에 5명 이상이 들어간다.
- 재현 조건: 인원이 3일 때 두 스레드가 거의 동시에 (A)를 평가하면 둘 다 3 < 4로 통과 → assign_slot 처리 동안 서로의 추가를 보지 못함 → 둘 다 (B) 실행.
- 근본 원인: 검사(size())와 행동(push_back) 사이가 보호되지 않아 다른 스레드가 끼어든다.
[자료 경쟁 / 미정의 동작]
- 여러 스레드가 동기화 없이 같은 std::vector를 push_back하면 재할당·크기 갱신이 겹쳐 UB다(원소 유실, 힙 손상, 크래시). 정원 문제와 별개로 그 자체로 잘못이다.

수정안

검사와 추가를 같은 뮤텍스로 보호한다. 무거운 assign_slot은 자리를 확보한 뒤 락 밖에서 처리한다.

#include <mutex>
#include <vector>
#include <algorithm>

class Party {
public:
    static constexpr int kMaxMembers = 4;
    explicit Party(int id) : party_id_(id) {}

    int count() const {
        std::lock_guard<std::mutex> lk(mu_);
        return static_cast<int>(members_.size());
    }

    bool try_add(int player_id) {
        {
            std::lock_guard<std::mutex> lk(mu_);
            if (static_cast<int>(members_.size()) >= kMaxMembers) return false;
            if (std::find(members_.begin(), members_.end(), player_id) != members_.end())
                return false;                       // 중복 배치 방지
            members_.push_back(player_id);          // 검사+추가가 원자적
        }
        assign_slot(player_id);                     // 무거운 처리는 락 밖
        return true;
    }

private:
    void assign_slot(int /*player_id*/) {}
    int party_id_;
    mutable std::mutex mu_;
    std::vector<int> members_;
};

mutex는 복사 불가이므로 Party도 복사 불가가 된다(파티는 보통 식별자로 다루므로 문제없다).

더 나은 설계

원자적 카운터로 예약: std::atomic<int> size_를 두고 fetch_add 후 한도 초과면 fetch_sub로 롤백("예약 후 확정"). 락 없이 정원을 지킬 수 있으나, members_ 벡터 자체의 일관성은 여전히 보호가 필요하다. 그래서 보통은 짧은 뮤텍스가 가장 단순하고 정확하다.
단일 소유 스레드 모델: 파티 변경을 파티별 한 스레드(또는 직렬 작업 큐)가 전담하면 경합 자체가 사라진다. MMORPG의 "방/존은 한 스레드 소유" 패턴. 트레이드오프: 소유 스레드 병목, 교차-파티 작업은 메시지로 조율.

면접 포인트

check-then-act 버그: 검사와 갱신이 한 임계 구역 안에 있어야 한다. assign_slot처럼 시간이 드는 처리가 창을 넓혀 경합을 키운다.
std::vector 동시 쓰기는 그 자체로 UB. 정원 로직이 맞아도 자료 경쟁은 별도 결함이다.
임계 구역 최소화: "자리 예약은 짧은 락, 실제 입장 처리는 락 밖"으로 분리하는 패턴을 설명할 수 있는가.

← 문제로 돌아가기