2020/2/7 online

[kyeongmincho]

세션

• 갱스쿤의 회사 아는 척 썰
• 직스쿤의 NP(Namchang's Problem h) 문제 해결기
• 홍의 쿠베 코어 발표 티저
• 남창 정렬된 딕셔너리 갈굼기
• 직스쿤의 Treiber Stack(+ Elimination Backoff) / Linearizability

액션 아이템

• 직: 연구 열심히....
• 갱
  • 로그 시스템 (수집부터 보여주는 것까지)
  • C# memory model
• 홍:
  • 쿠버네티스
  • 이스티오
• 창:

[kyeongmincho]

직스쿤의 NP(Namchang's Problem h) 문제 해결기

코드 참고

직스쿤의 Treiber Stack(+ Elimination Backoff) / Linearizability

• Treiber Stack
  • push, pop 할 때 CAS
  • contention이 있을 때 느림
  • 코드
• Elimination Backoff Stack
  • Treiber Stack 접근하기 전에 Elimination Backoff Array에 push, pop
  • 랜덤하게 인덱스 할당받고 거기서 기다림
  • 매칭되면 함수 리턴 / 매칭 안 되면 기존 트라이버 스택 알고리즘대로
• Linearizability(선형화 가능성): Concurrent Data Structure의 correctness 검증 기준
  • 스레드별 함수 호출-리턴 타임라인을 그리고
  • 각각에 적합한 순서대로 linearization point를 적당히 잡고
  • 정사영 뜬 뒤 그러한 호출 순서가 싱글스레드 자료구조에서 일어날 수 있는 일인지에 대한 가능성
  • From wikipedia:

This definition of linearizability is equivalent to the following:

• All function calls have a linearization point at some instant between their invocation and their response.
• All functions appear to occur instantly at their linearization point, behaving as specified by the sequential definition.