kgc2007 세션 정리 기타

양일간 들었던 세션중에 가장 괜찮았다고 생각하는 두가지 세션을 정리했습니다. 모두 ETRI 연구원 분들이 발표하신 세션이었습니다.

온라인 게임 네트워크 부하테스트 환경
  • 네트워크 부하 테스트 툴

    • 패킷 캡쳐를 통해 얻은 데이터로 대량의 네트워크 부하를 발생시킴.
    • 다양한 네트워크 상황 재현 : 패킷 지연, 손실
    • 분석기능 및 스크립팅 기능.
  • 네트워크 부하 테스트툴 소개

  • VENUS Blue

    • ETRI에서 개발한 온라인게임 서버 및 네트워크 부하 테스트 솔루션.
    • 한 PC당 1000개 이상의 가상 사용자 생성.
    • PC별 각각의 네트워크 환경제공(56KBps, 100MBps)
  • VENUS NAT

    • NAT 환경 시뮬레이션 기술로서 각 NAT 타입별 소프트웨어 기반 시뮬레이션
    • 4종의 NAT type 지원 : Symmetric / Port Restricted / Restricted / Full Cone
    • 네트워크 에뮬레이션 : 패킷 지연, 손실

Lock-Free 알고리즘
  • Compiler reorder

    • 성능의 향상을 위해 Compiler가 코딩된 프로그램의 순서를 로직이 유지되는 한도 내에서 바꾼다.
    • while loop의 종료 조건을 가진 bool 변수의 값이 변경되어도 다시 읽어오지 않는 현상 등.
    • _ReadBarrier, _WriteBarrier, _ReadWriteBarrier, volatile 로 막을 수 있다.
    • _ReadBarrier

      • _ReadBarrier전에 읽은 값을 확실히 다시 읽음.
      • 이미 읽어온 값이 있어도 다시 읽는다.
    • _WriteBarrier

      • WriteBarrier 전에 쓴값은 확실히 씀.
      • 필요없는 write라도 완료함.
  • CPU reorder

    • CPU 내에 있는 out of order execution 기능으로 인하여 명령의 실행 순서가 바뀜.
    • Cache 및 write-back,queue 등으로 인하여 read 되는 순서와 write 값의 순서가 바뀐다.
    • X86 은 write 를 reorder를 하지 않으나 read reorder는 함.
    • InterlockedXXX 계열의 함수로 막을 수 있다.
  • CAS(Compare and Swap)

    • Atomic operation
    • 주어진 메모리의 값을 읽어서 comparand와 비교하여 같은 경우 메모리에 newvalue를 저장하고 비교의 결과를 return 한다.
    • Lock Free 알고리즘을 구현하기 위해 꼭 필요한 기능.
    • windows에는 InterlockedCompareExchange가 있음.
  • SC(Store-Conditional)
  • LL(register, memory)

    • Memory위치에서 값을 읽어옴.
  • Lock-Free 알고리즘

    • 정의 : 언제 연산이 종료되는지 미리 알 수 없지만, 연산이 종료되는 방향으로 계속 진행되는 알고리즘(물론 Lock 없이)
    • 일반적으로 CAS나 LL/SC등으로 구현됨.
    • 일반적 구조 : read - modify - write

    int * p = memory_loc;
    int x, new_x;
    do
    {
        x = * p; // read
        new_x = calculate_newvalue(x); // modify
    } while ( ! CAS(p, x, new_x) ); // write(p값이 x값과 같으면 new_x로 변경.아니면 한번더 뺑뺑이)

     

    • Atomic Addition

    int AtomicAdd(int * p, int addnd)

    {
        int x;
        do {
            x = *p;
        } while ( ! CAS(p, x, x + addnd));
        return x;
    }

     

    • Lock-Free Stack


    • Lock-Free Queue

    Data definitions:
    node = {data val; node* next};
    node* Head, Tail;

    Initialisation:
    Head = Tail = new(node);
    Head->next = null;


    enqueue(value: data)
      node = new_node();
      node->value = value; node->next = NULL;
      loop
        tail = Tail; next = tail->next;
        if tail == Tail
          if next == NULL
            if CAS(&tail->next, next, node)
              CAS(Tail, tail, node);
              return;
            endif
          else
            CAS(Tail, tail, next);
          endif
        endif
      endloop


    dequeue(pvalue: pointer to data): boolean
      loop
        head = Head; tail = Tail;
        next = head->next;
        if head == Head
          if head == tail
            if (next == NULL) return FALSE; endif
            CAS(Tail, tail, next);
          else
            *pvalue = next->value;
            if CAS(Head, head, next)
              free(head);
              return TRUE;
            endif
          endif
        endif
      endloop

     

    • ABA문제 : 1번 스레드에서 A값을 읽어서 연산중에 2번 스레드에서 해당 메모리를 B값으로 변경한후 또 다른 스레드에서A값으로 재변경하면 1번 스레드에서는 CAS 과정에서 해당 메모리 값이 A이니 그 값을 변경하고 루프를 마치는 현상.

덧글

댓글 입력 영역