Possible Infinte Loop in Wait-free Bounded Queue

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

LIS 알고리즘 - 최장 증가 부분 수열 찾기

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

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

  • DP O(n2)
  • Binary Search O(nlogn)
  • Segment Tree O(nlogn)

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

Open Bw-Tree Performance Test

Test Case 생성기

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

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

키 값은 랜덤으로 생성.

Sublime Text 세팅하기

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

Mac 클린 설치 이후 개발 환경 구축/세팅 하기

Mac osX은 매년 메이저 업데이트가 진행되며 올해에도 9월 25일에 High Sierra 에서 Mojave로 새로운 버전이 출시되었습니다. 기존의 OS에서 포멧 후 클린 설치를 하지 않는 업그레이드 기능을 지원하며 해당 기능을 통해 업데이트를 진행하는 것이 매우 간단하지만 그럼에도 불구하고 메이저 업데이트는 메이저 업데이트인지라 종종 예상치 못한 곳에서 해결하기 쉽지 않은 오류들을 생성해 내곤 합니다.

그렇기에 이러한 문제를 미연에 방지하고자 많은 맥 사용자들이 메이저 업데이트가 배포될 때마다 포멧후 클린 설치를 진행하곤 합니다. 저 또한 이러한 부류에 속하는 편인데 올해에는 귀찮음을 견디지 못하고 약 한달간 업데이트 상태에서 지속적으로 사용해 오다가 오늘 큰 마음을 먹고 포멧 후 재설치를 진행하였습니다.

앞으로도 매년 이러한 현상은 반복될 것이기에 무엇보다 미래의 귀찮음과 반복작업을 줄이기 위하여 이번 포스트를 마련해 보았습니다. 포멧 후 완벽하게 깨끗한 상태에서부터 어떠한 과정을 통해 다시 개발환경을 세팅할 것인지, 미래의 나를 위한 가이드라인입니다.

하지만 그 가이드라인이 사용된 적은 없었다고 합니다.

Pagination


© 2020. All rights reserved.