다빈치 SW 공모전

'언택트 시대에 유용한 앱 혹은 서비스를 주제로한 SW 공모전으로
2020-2학기 비공학 전공 재학생 2인 이상이면 참가 가능합니다.

자세히 알아보기

캡스톤 디자인 경진대회

캡스톤 디자인 교과목 수행 결과물 또는 졸업 작품 심사
2019년 2학기, 2020년 1학기 중 한 학기 이상 캡스톤 디자인 교과목을
수강한 학생만 참가 가능합니다.

자세히 알아보기

PE연구활동 발표대회

PE연구/개발 활동을 수행하면서 얻어진 다양한 형태의 결과물
(논문형태의 결과보고서, 논문, 발명품, 작품, 콘텐츠 등)을 심사

자세히 알아보기

SW·AI 창업아이디어경진대회

SW 관련 전공 학부생 여러분!
반짝이는 SW창업 아이디어로 여러분의 미래를 바꾸십시오!

자세히 알아보기

SW·AI융합우수성과 발표회

SW융합전공 / 복수 전공 학생 여러분!
SW융합전공 / 복수전공을 이수하는 과정에서 얻어진 성과를 뽐내 주세요.

자세히 알아보기

다빈치 주니어 SW 작품대회

창의적인 아이디어와 소프트웨어를 활용한
멋진 SW 작품을 만들어 보세요!

자세히 알아보기

다빈치오픈소스 SW·AI 딥러닝 해커톤

4차 산업혁명을 견인하는 심층학습을 주제로한 SW·AI 딥러닝 해커톤으로
소프트웨어대학 재학생으로 구성된 2인 이하 팀으로 참가 가능합니다.

자세히 알아보기

코딩경진대회

소프트웨어 중심 대학으로서 중앙대학교의 소프트웨어 관련
교육 프로그램 성과를 공유합니다.

자세히 알아보기

PE연구활동 발표대회

  • 이상묵

    등록자
    이상묵 (소프트웨어학부 | 3학년)
좋아요 81

작품영상

  • 참여 목적 및 참여 당시 활동 목표
  • 참여 목적
    리눅스 커널에 대한 공부를 해보던 중에 리눅스에 여러 종류의 Lock을 확인하고 이러한 Lock을 제거한 Lock Free를 구현해내면 더 높은 성능을 구현해 낼 수 있을 것이라고 생각하게 되어 이번 PE 프로그램에 참여하여 직접적으로 linux kernel을 다루는 syslab에 지원하게 되었다.



    활동 목표
    - 리눅스에서 가장 많이 사용하고 있는 자료구조 중 하나인 Tree의 lock을 풀면 여러 군데에 적용이 가능해 성능이 좋아질 거란 생각에 BST(Binary Search Tree)에 관해 집중적으로 조사를 해보았다.
    - 현재 리눅스 내부의 BST의 경우 여러 thread가 접근할 수 있는 multi-threading 환경에서의 consistency를 보장하기 위해서 lock을 사용하고 있다.
    - 이러한 BST의 lock을 제거한 Lock Free BST를 구현하여 BST의 최적의 성능을 내보도록 하는 것이 이번 PE 활동 목표이다.
  • 연구 및 학습활동 결과
  • 연구 배경 및 목적
    - Multi-threading 환경에서의 가장 기본적인 BST와 이를 순차적으로 계선한 2가지의 다른 Lock을 사용하는 BST를 구현하고 최종적으로 Lock Free BST를 구현하여 성능의 차이를 측정한다.
    - 자료조사를 통해 미완성의 Lock Free 자료를 참고 할 수 있었다. 이를 완성하고 성능 보완을 통해 최적의 Lock Free BST를 완성하는 것이 목적이다.
    - Binary Search Tree의 주요 기능인 insert, search, delete  3가지 함수의 성능을 측정하는 것을 기본으로 한다.

    연구 절차
    - 가장 기본 BST인 Lock BST의 경우 3가지 주요 기능을 하는 동안 tree 전체의 lock을 잡아 다른 thread는 자신의 작업을 수행하지 못하고 기다리고 있다. 이러한 Lock BST를 구현하여 내용은 아래의 그림과 같다.

    Lock1.png
    thread 5가 사용중일 때 thread 6,7,8은 Lock 으로 인해 기다리는 시간이 발생한다.
    - 이러한 waste를 개선한 것이 Fine Grained BST이다. Fine Grained BST는 락을 함수 전체를 잡는 것이 아닌 접근하는 노드 자체의 락을 사용하기 한다. 이때 사용하는 락의 2가지 종류 mutex와 spin lock을 사용하여 BST의 코드 구현을 진행하였다. 원리는 아래의 그림으로 쉽게 설명이 가능하다.


    Lock2.png


    - thread 5,7의 경우 작업을 수행하지만 thread 5가 searching 하는 동안 노드5에 Lock이 걸려있으므로 thread 6이 searching을 하는데 다음노드로 진행하지 못하고 waiting 을 하게 된다.
    - 이경우 Lock BST보단 적은 waste 가 발생하지만 아직도 상당한 waste가 발생한다.
    - 이러한 waste를 해결하기 위해 현존하는 Lock Free의 자료를 참고한 BST는 다음의 구조를 가진다.Lock3.png

    - 위의 그림을 보면 tree 자체에 lock 이 존재하지 않음을 확인할 수 있다. 위의 경우 각 thread가 waiting을 하지 않고 작업중인 노드를 global한 array에 넣어둔다.
    - 이 global한 array는 특정노드를 physically free해주는 과정에서 scan을 하기 위해 필요한데 이 array에 새로운 노드를 넣을 때마다 array 존재하는 Lock에 의해 waste가 발생한다.
    - 이러한 Lock Free BST를 더 수정하여 완전한 Lock Free를 구현하여 보았다.
    - Lock Free BST(Proposed)의 경우 아래의 그림과 같은 내용으로 구현되었다.


    Lock4.png
    - 기존의 Lock Free BST 의 경우 Global한 array에서 Lock 이 존재한다. 이 Global한 array를 각 쓰레드가 본인의 array가 존재하도록 split하였다. 이 경우 Lock 이 필요하지 않기 때문에 Lock을 제거하여 Lock Free를 이루었다.
    - 위의 경우 Lock 을 없애면 consistency 보장에 대한 이슈가 발생했었다. 하지만 logically delete된 노드의 경우 각 thread의 array에서 더 이상 접근할 일이 없어 lock이 필요하지 않고 physically delete하는 경우에도 각 thread의 array를 스캔하는 과정에서도 사용중인 node가 존재하면 physically free해주지 않고 남겨두므로 문제가 발생하지 않는다.

    연구 결과

    - random 하게 100,000개의 노드를 insert, search한 것의  performance를 측정한 결과이다.
    - 측정 환경은 Intel Xeon CPU E7 2.40Hz (18.core*4), 62thread 로 측정을 진행하였다.

    Pic1.png

    - 위쪽 그림 : 왼쪽 부터 Lock BST, Fine Grained BST(mutex), Fine Grained BST(spin), Lock Free 의 순으로 성능이 잘 나오는 것을 확인 할 수 있다.
    - Lock search의 경우 semaphore read lock을 사용하여 read 하는 경우에는 lock을 거의 안 잡으므로 성능이 좋게 나왔다.
    - Lock BST < FG(m) < FG(s) < Lock Free 의 순으로 성능이 잘 나온 것을 확인 할 수 있었다.

    Pic2.png
    - 위의 그림은  자료를 참고하여 LF를 구현하여 측정한 LF와 이를 더 보완하여 최적의 성능을 보인 LF(p)의 insert, search, delete이다.
    - delete의 경우 lock free 에서 threshold 이하 갯수의 node의 경우 physically free하는 코드 진행을 하지 않아 run time이 더 적게 측정되었다.
    - 확연하게 LF(p)가 성능이 7~9배 정도 좋아진 것을 확인할 수 있었다.
  • 참여 소감 및 향후 계획
  • 참여 소감
    내가 직접 linux에 존재하는  lock을 지워보려고 시도했다는 것 자체가 처음이라 신선하고 재미있는 과정이었다. 연구를 진행하면서 여러가지 난황에 부딪히고 막히면서 묵묵히 진행하는 과정에서 많을 것을 배웠고 앞으로도 도움이 될 것 같았다. 특히 muti-threading의 환경에서의 오류를 발견하고 찾아내는 과정과 lock free의 이해를 통한 코드 수정의 과정에서 수 없는 벽에 막힌것 같았었다. 이러한 경험을 토대로 앞으로의 연구 방향성도 잡히고 순항으로 나아가고 있는 것 같아서 뜻 깊은 시간이었다고 생각한다.

    향후 계획
    - 해당 BST의 경우 OS의 여러 부분에 사용되고 있어서 여러 부분에 직접 대입하여 더 좋은 성능을 측정해볼 예정이다.
    - pagecache의 bottleneck이 측정되어 우선적으로 살펴볼 예정이고 이외에도 ext4 의 extent status tree등 여러 tree를 순차적으로 살펴보고 적용 가능한 부분이 있으면 적용을 하여 performance 측정을 해볼 계획이 다음으로 잡혀있다.


     
  • 증빙자료
  • - 더 자세한 사항의 경우는 PE 연구활동 보고서에서 확인해 볼 수 있다.

좋아요 참여 81

  • 학년 별

  • 학과 별

중앙대학교 다빈치 sw tech fair 참가신청 닫기