봉황대 in CS

버전 락, (대개) 낙관적 락(Optimistic Locking)이라고 부르는 locking 개념에 대해서 정리해보고자 한다.진행하고 있는 연구 구현에서 최근에 이 친구를 추가했다 ㅎ__ㅎ Main idea어떤 데이터에 대해서 reader가 writer 보다 훨씬 많은 상황을 생각해 보자.즉, 갱신이 자주 발생하지는 않으며, 읽기 연산은 많이 발생하는 데이터라는 것이다. 여기서 비관적 락(Pessimistic Lock)처럼, 연산을 진행하기 위해서는 무조건 lock을 잡아야 한다면 매우 큰 성능 저하가 발생할 수 있다. 읽기 연산은 여러 reader가 동시에 진행할 수 있는데, 그것을 아예 막아버렸기 때문이다.  따라서 버전 락(낙관적 락)은 '우선 그냥 읽어! → 읽는 동안 쓰기가 발생했다면, 다시 읽..

현재 진행하고 있는 연구는 특정 workload에서, thread의 개수가 증가하면 performance(이 연구에서는 throughput)도 같이 좋아지는 scalable 한, 그리고 lock-free로 동작하는 스토리지 시스템을 설계하는 것이다. 따라서 multi-threaded 환경에서 발생하는 concurrency issue들을 '매우 잘' 해결해야 한다. 이 '매우 잘'에는 수많은 내용이 함축되어 있는데.. n달 동안 내가 설계한 것을 구현하고, 디버깅하고, 디버깅 완료하면 또 다른 문제를 마주하고, 디자인 변경하고, 더 큰 문제를 마주해서 다시 이전 버전으로 되돌아가고, 다시 디버깅하고, ... 이러한 작업을 계속 진행하고 있다.  문제는, 어떠한 이슈를 마주하고 디버깅을 진행할 때마다 매번 ..

이번 학기에 '협동 분산 시스템' 과목을 수강하는데, 'Design Issues of Clients and Servers'라는 주제가 있었다.client와 server 각각 사용 편의성을 제공하기 위해서, 그리고 사용자에게 더욱 빠른 서비스를 제공해 주기 위해서는 어떤 이슈들이 존재하며 그들을 해결하기 위해서는 어떤 기법을 사용할 수 있는지를 다루었다. server 쪽에서는 multi-threading을 통해서 performance를 올리는 것을 중점적으로 다루었는데, 여기서 갑자기 single-threaded server이지만 parallelism을 제공하여 성능 향상을 줄 수 있는 방법은 asynchronous non-blocking system call을 사용하는 것이라고 하셔서 대혼동이 발생했다..

key들이 쭉 저장되어 있는 배열이 주어졌을 때,이 배열에 저장되어 있는 key들을 통해서 B+-Tree를 Bottom-Up 방식으로 생성하는 것은 어떻게 구현해야 할까? 현재 진행하고 있는 연구에서 이를 구현하기 위해 코드를 3번이나 갈아엎는 시행착오를 겪게 되었다.이 과정을 통해서 깨달았던 것들을 여기에 정리하고자 한다.  Build: Top-Down Approach보통 B+-Tree를 생성하고자 한다면 Top-down 방식을 생각할 것이다. Top-down 방식은 search → insert → split 단계로 진행된다. root에서부터 시작하여, 현재 tree에 넣고자 하는 key를 저장할 수 있는 leaf node를 찾는다.해당 leaf node에 key를 insert 한다.만약 leaf n..

* 본 글은 2023학년도 2학기에 수강한 '시스템 프로그래밍' 과목 강의 내용을 함께 정리하여 작성하였습니다. Zombie Processes Zombie process(좀비 프로세스)는 process가 할 일을 전부 마쳐서 종료되었음에도 불구하고, 자원들을 계속 소비하고 있는 process를 말한다. Reaping Process의 생성과 종료가 정상적으로 진행되는 상황을 보자. Parent process가 fork() system call을 호출하여 Child process가 생성된다. Child process가 자신의 할 일들을 모두 마치고 종료한다. → Parent process에게 SIGCHLD signal을 보내고, Kernel은 Child process의 자원들을 회수한다. → 이때 Chil..

* 본 글은 2023학년도 2학기에 수강한 '알고리즘' 과목 강의 내용을 함께 정리하여 작성하였습니다. Greedy Algorithms 답을 찾기 위해서 선택을 반복하는 알고리즘이다. 비교적 간단한 기준으로 답을 계속 골라 담고, 이를 바꾸지 않는다. Minimum Spanning Tree 모든 node를 포함하며, edge cost가 최소가 되는 connected acyclic graph 찾기! Given a Graph, find Subset of Edges so that a Connected Graph results with Minimum Sum of Edge Costs. - minimum : edge cost가 최소가 되는 - spanning : 전체를 덮는, 즉 모든 node를 포함하는 Input..

* 본 글은 2023학년도 2학기에 수강한 '알고리즘' 과목 강의 내용을 함께 정리하여 작성하였습니다. Proof of Correctness of Sorting 'Sorting이 되었다'라고 말할 수 있으려면 어떠한 조건들이 만족되어야 하는가? - 입력 값 : a[0], a[1], ... , a[n-1] - sorting이 끝난 후 배열에 저장된 값 : b[0], b[1], ... , b[n-1] 조건 1: 값이 없어지거나, 새로 생기면 안된다. (집합 조건) {a[0], a[1], ... , a[n-1]} = {b[0], b[1], ... , b[n-1]} 조건 2: 값 기준, 오름차순 정렬된 순서로 저장되어 있어야 한다. b[0] < b[1] < ... < b[n-1] Merge Sort Merge ..

* 본 글은 2023학년도 2학기에 수강한 '알고리즘' 과목 강의 내용을 함께 정리하여 작성하였습니다. Proof of Correctness of Sorting 'Sorting이 되었다'라고 말할 수 있으려면 어떠한 조건들이 만족되어야 하는가? - 입력 값 : a[0], a[1], ... , a[n-1] - sorting이 끝난 후 배열에 저장된 값 : b[0], b[1], ... , b[n-1] 조건 1: 값이 없어지거나, 새로 생기면 안된다. (집합 조건) {a[0], a[1], ... , a[n-1]} = {b[0], b[1], ... , b[n-1]} 조건 2: 값 기준, 오름차순 정렬된 순서로 저장되어 있어야 한다. b[0] < b[1] < ... < b[n-1] Selection Sort by..