This is short(?) summary of the textbook “Art of Multiprocessor Programming” by Maurice Herlihy & Nir Shavit.
A complete set of lecture slides & sample code is available at the textbook’s companion page
This work is licensed under a Attribution-ShareAlike 3.0.

Wait-free Bounded Queue는 atomic fetch_add() 함수를 사용하여 bounded된(사이즈가 정해진) 배열 내에서 값을 enqueue, dequeue 함으로서 작동하는 자료 구조입니다.
여러 enqueue/dequeue 요청이 병렬적으로 들어왔을 때에도 순차적인 처리를 위하여 배열 내부의 원소는 flag를 두고 있으며 해당 flag를 사용하여 enqueue/dequeue 요청을 순차적으로 처리할 수 있기 때문에 wait-free의 성질을 가지고 있습니다.

문제보기

• LIS (Longest Increasing Subsequence) : 최장 증가 부분수열
  LIS란 임의의 수열이 주어졌을 때, 해당 수열에서 몇 개의 수들을 뽑아 만든 부분수열 중 오름차순으로 정렬된(strictly increasing) 가장 긴 수열을 뜻합니다.

이 때 LIS의 길이를 구하는 방법은 크게 세가지가 있습니다.

• DP O(n²)
• Binary Search O(nlogn)
• Segment Tree O(nlogn)

오늘은 이 중 Binary Search, 즉 이분 탐색을 이용해 LIS의 길이와 수열을 찾는 방법을 알아보겠습니다.

현재 OpenBwTree에는 Update가 구현되어 있지 않습니다.
그렇기에 테스트 케이스 생성에 앞서 BwTree를 위한 Update를 제작해야 했습니다.

Test Case 생성기

instruction, thread 갯수와 insert ratio를 받아서 테스트 케이스가 적혀있는 tmp[num].txt 생성 (tmp1.txt, tmp2.txt …)

각 텍스트 파일에는 매 행마다 i num 혹은 d num 으로 입력, 삭제 할 키 값이 들어있음.

키 값은 랜덤으로 생성.

Open Bw Treed Benchmark 코드 흐름 따라가면서 파악하기.

서브라임 텍스트는 맥을 사며 코딩을 시작한 이후부터, 가장 오랫동안 가장 많이 사용해온 텍스트 에디터이다.
기본 기능은 거의 없다시피 하지만 패키지 컨트롤과 약간의 설정을 더해주면 IDE 못지 않은 편의성을 제공해주기 때문에 매우 편리하다.