Operating System Lab 2

2019 Operating System Lab 2 LAB 2 SYNCHRONIZATION CHOI GUNHEE, CHOI JONG MOO

[ Lab 2 Synchronization ] 운영체제수업을통해 Race Condition 의위험성및 Synchronization 의필요성에대해숙지하였다. 이를바탕으로본과제에서는 pthread 기반 mutex 를활용해 Race Condition 상황을해결하고추가로간단한 assembly language 를통해 atomic 하게동작하도록 spinlock 을직접구현해본다. 아래실습과제위치와설명을적어두었다, 두번째실습관련직접수정및구현해야하는파일은아래빨간색으로표기하였으며, 보너스과제관련되어수정및구현해야하는파일은초록색으로표기하였다. 과제구성 Makefile - 실습자료들을컴파일하기위한파일 include/lab2_sync_types.h - 실습에사용할구조체및구현할함수에대한헤더파일. lab2_example.c - mutex 사용예시를보여주기위한파일. lab2_bst.c - 실습에서구현해야할, thread-safe BST 부분파일. lab2_bst_test.c - 구현한, thread-safe BST 의 test code lab2_bonus.c - 실습보너스과제를위해구현해야할, spin lock 부분파일. lab2_bonus_test.c - 구현한 spin lock 부분의 test code. 1

A. Race Condition 운영체제수업을통해 Race Condition, Critical Section 및이를막기위한다양한기법을숙지하였다. 본과제에서는그중하나인 mutex 를통해 Race Condition 상황을해결해본다. 따라서 Critical Section & Race Condition 에대한간단한개념을돌아보고 mutex 의실행예시를통해간단히사용방법을숙지한다. 1. Critical Section & Race Condition Race Condition 이란둘이상의입력또는조작이동시에이루어져, 프로그램의결과가입력, 조작의순서에의존하여동작하게되어버리는상황을의미하는것이며, 동시적조작에있어, 공유가되는부분을 Critical Section 이라고한다. Race condition 을고려해야하는상황으로 Multi-thread 가있다. Multi-thread application 은어떤형태로든 thread 간에정보를공유하는것이필요하다. Thread 간어느 thread 가작업을완료했고, 어느 thread 가아직진행중인지서로공유를할수도있으며, 여러 thread 가같은공통적인 data 에대해작업을수행할수있다. 대표적인예로모든 thread 가동시에 Database 에접근하여 data 추가, 삭제, 조작등의연산을수행할경우, 각작업의진척도를나타내는 counter 를서로공유해야하며, 각연산들이완전하게수행되도록보장할수있어야한다. 2. Synchronization Primitives Race Condition 을방지하기위해서는 Critical Section 에대해한번에하나의입력또는조작등의연산이수행되도록보장해주어야하며이를 Mutual Exclusion 기법이라고한다. 이러한기법에기본적으로 atomic operation spinlock, semaphore, mutex 등이있으며, 이를통해특정공유리소스에대한접근을한번에한 thread 로제한하거나, 해당리소스에관련된작업이완료되기전에다른작업이시작되지않게 Mutual Exclusion 을보장함으로써, Race Condition 을방지할수있다. 더나아가공유자원에대한 reader, writer 구조에서 writer 에대해서는 Mutual Exclusion 을보장하고 reader 에대해서 reader 끼리동시에접근이가능하되 writer 가존재한다면, Mutual Exclusion 으로동작하는 read/write spinlock,read/write semaphore 등이있으며, Multi-thread 등의환경에서특정실행순서를보장해주어야할때, condition variable, barrier 등이사용된다. i. Mutex lock Mutex lock 은한번에한 thread 만특정 code 영역에접근할수있도록하는 Mutual Exclusion 을통해 Synchronization 을제공하는기법이며, lock 을획득하지못한 thread 는 lock 을획득한 thread 가작업을끝내고, lock 을반환할때까지 2

대기하게된다. Mutex lock 을이용하기위해서는변수선언, 초기화, 적절한함수를사용하여야한다. 실습자료의아래와같은위치에 mutex 사용법의예시를포함하였다. mutex 예시파일. 위그림은 mutex 예시파일의위치를보여준다. lab2_example.c 소스파일 을통해 mutex 의사용예시를확인할수있다. 3

위그림은 lab2_example.c 파일의주요코드부분이며, 과제를구현하는데 있어참고자료로첨부하였다. 위코드는 num_threads 의수만큼 thread 를 생성하며, 각 thread 는 num_iteration 만큼반복하며 shared_variable 이라는 변수를증가시키는연산을수행하는코드이다. 초기화 위코드에서는 56 번째줄에서정적변수인 mutex 를정적인방법으로 초기화하였다. 초기화에는정적초기화와동적초기화가있다. 정적초 기화는 mutex 변수를위와같이 PTHREAD_MUTEX_INIT 을통해초기 화한다. 동적초기화는 list, tree 등과같이 heap 영역에동적으로생성되는 mutex 등을초기화할때사용하며아래와같은함수를사용하여초기화 한다. pthread_mutex_init(pthread_mutex_t *mutex, const pthread_mutexattr_t *attr) critical section 에대한 lock 잡기 위코드에서는 68 번줄에서 thread 가 critical section 인 shared_variable 을증가시키는부분에도입하기전 pthread_mutex_lock 함수를통해 lock 을잡도록하였다. pthread_mutex_lock 함수를통해이미다른 thread 가 critical section 에진입하여수행중일경우, 현재 thread 는 lock 을잡지 못하고대기하여야한다. critical section 에대한 lock 풀기 위코드에서는 73 번줄에서 critical section 을수행한 thread 가잡고있던 lock 을풀수있도록하였다. 이를통해 lock 을기다리고있던다른 thread 는 critical section 에진입할수있다. 4

mutex 예시파일컴파일 # make lab2_example 위그림과같이 make lab2_example 명령어를통해컴파일하면 lab2_example.c 의실행파일인 lab2_example 이생성된다. mutex 예시파일실행 #./lab2_example t 4 i 1000000 s o #./lab2_example t 4 i 1000000 s m 위와같은 lab2_example 실행파일에는 t, i, s 옵션을주어실행할수있으며각옵션의의미는아래와같다. 옵션을주지않고실행하게되거나올바르지않은옵션을주게되면위와같이사용법을출력한다. t (thread) : critical section 을동시에수행할 thread 의개수를설정한다. i (iteration) : critical section 에서 shared_variable 을증가시키는연산을반복수행할횟수를설정한다. s (sync mode) : critical section 을수행할방법을설정한다. o 로설정할경우, mutex 를사용하지않고 critical section 을수행하며, m 으로설정할경우 critical section의수행에 mutex를사용하여수행한다. 5

위그림은 critical section을 4개의 thread가동시에수행하며, critical section 에서 shared_variable에대해 1000 회증가연산을수행하며, mutex를사용하지않도록설정한수행결과이다. 4개의 thread가각각 shared_variable 증가연산을 1000 회수행한다면, 수행을결과는 4000이될것으로예상할수있으며, 그결과또한정상적으로출력이되어 race condition이발생하지않은것을확인할수있다. 여러번수행하여결과를확인해보면, race condition이발생하여결과가 4000 이아닌다르결과가출력되는것을확인할수있지만, 좀더확실히 race condition 을확인하기위해반복횟수를늘리게되면아래와같은실행결과를볼수있다. 위그림은 critical section을 4개의 thread가동시에수행하며, critical section 에서 shared_variable에대해 1000000 회증가연산을수행하며, mutex를사용하지않도록설정한수행결과이다. 예상한결과는 4000000 이지만, 실제 shared_variable 을출력한결과는 1518380 이나온것을확인할수있으며실행할때마다그결과가. 이를통해 lock을사용하지않을경우, critical section 에대해 race condition이발생하게되어실행시마다결과가달라지는것을확인할수있다. 6

B. BST with Coarse-grained Lock & Fine-grained lock Race Condition 으로부터보호하기위해서는 Critical Section 파악하고어느정도까지 Lock 을통해보호할것인지결정하는것이중요하며이에따라성능이크게달라질수있다. 본과제에서는 Race Condition 을해결하기위해 Tree 자료구조를사용한다. Tree 는 BST, Btree, B+tree, AVL tree, Red-Black tree 등다양한종류의알고리즘을사용하는 Tree 가있으며이중, 간단한알고리즘이며, 2 학년 2 학기자료구조수업시간에배운 BST 를활용해 Multithread 수행시발생할수있는 Race Condition 을 Coarse-grained locking, Fine-grained locking 라는두가지방식으로해결하며, 그성능을비교한다. 따라서과제수행전 BST, Coarse-grained Lock, Fine-grained Lock 의간단한개념및 Multi-thread 환경에서 thread-safe 한 BST 를구성하는방법에대해숙지한다. 1. Binary Search Tree BST(Binary Search Tree) 는위그림처럼 node 마다 key 값을가지며, left, right 두개의 child link 를가지는자료구조이다. 가장상위에있는 node 를 root node 라고하며가장하단에존재하는 node 를 leaf node 라고한다. 각 node 의 left child link 에는자신보다작은값을가지는 node 들이저장되며, right child link 에는자신보다큰값을가지는 node 들이저장된다. Tree 에는기본적으로 node 를 insert, remove, search, traversal 하는연산등이있다. i. node insert tree 에새로운 node 를추가하는연산으로 root node 부터, key 값을비교하여새로운 node 가저장될위치를찾아간다. 위그림과같은 tree 에 key 값이 25 인 node 를추가한다고하면아래그림과같이 root node 부터 leaf node 에도달하기까지각 node 와비교하며위치를찾아간다. 7

ii. node remove tree 에새로운 node 를삭제하는연산으로먼저삭제할 node 를찾은후, BST 의구조를유지하기위해삭제할 node 의위치의값을재설정한다. 삭제할 node 가자식을한개만가지거나, 자식 node 를가지지않을경우는아래왼쪽그림과같이수행한다. key 값이 30 인 node 를삭제한다고하면, 오른쪽그림처럼삭제후 node 값이재설정된다. 자식이두개인 node 를삭제할때는 BST 구조를유지하기위해삭제할 node 의왼쪽자식 sub tree 중가장큰값또는오른쪽자식 sub tree 중가장작은값을선택하여삭제할 node 의값을재설정한다. 아래그림을통해 key 값이 20 인 node 를삭제하려고할때의결과를볼수있다. 8

iii. node search tree 의 node 를찾는연산으로 insert 연산에서추가할위치를찾거나 remove 연산에서삭제할 node 를찾는것과같은방법으로 tree 에있는 node 를찾는다. iv. node traversal tree node 를순회하는연산이다. 순회에는순회순서에따라전위순회 (preorder), 중위순회 (inoder), 후위순회 (postorder) 가있으며각각아래와같이순회한다. 전위순회는아래그림과같은순서대로 node 를순회한다. 중위순회는아래그림과같은순서대로 node 를순회한다. 후위순회는아래그림과같은순서대로 node 를순회한다. 9

2. Coarse-grained Lock & Fine-grained Lock Multi-thread 등의 Critical Section 이존재하는환경에서 Race Condition 을방지하기위해 Lock 을사용할수있다. 하지만 Race Condition 이발생하지않더라도 Lock 을사용하는방식에따라그성능이크게좌우될수있다. Lock 을사용하는방식은 Critical Section 의선정범위에따라즉 Lock 을얼마나세분하게설정하느냐에따라 Coarse-grained Locking, Fine-grained Locking 의두가지방식으로사용될수있다. Coarse-grained Locking 방식은 Critical Section 의범위를크게잡아많은양의데이터를한번에보호하는방식이며, Fine-grained Lock 은 Critical Section 의범위를세분화하여각부분마다 Lock 을사용하는방식이다. 각각장단점이있으며본과제에서는실행시간확인및직접구현해봄으로써두가지방식을비교해본다. 3. BST with Coarse-grained Lock & Fine-grained Lock 여러 thread 가동시에 BST 에접근하여 insert, remove, search 등의연산을수행할때, Race Condition 이발생하여정상적으로동작을하지못하게된다. 다양한상황이있을수있지만예를들어 Producer & Consumer 구조를생각해볼수있다. Producer & Consumer 구조에서, 즉 BST 에새로운 node 를추가하는 producer thread 와기존의 node 를삭제하는 consumer thread 가있다고할때, 추가를하는도중, consumer thread 가경로의특정 node 를삭제해버리면문제가될수있다. 또한. 또는 BST 의특정 node data 를읽어들이는 Reader thread 와 BST 의특정 node 에 data 를수정하는 Writer thread 의 Reader & Writer 의경우특정 node 의 data 를읽어들이는동안에 Wrier 에의해값이바뀌어버리면문제가발생할수있다. Race Condition 을막기위해선 BST 의각연산이안전하게수행되는것이보장되어야하며이를위해 Coarse-grained Lock, Fine-grained Lock 방법을사용할수있다. i. BST with Coarse-grained Lock Race Condition 을막기위해 BST 에대한 insert, remove, search 등의연산수행시각연산이수행되는동안다른 thread 가 BST 에접근할수없도록, Tree 전체를 Critical Section 으로간주하여 Lock 을사용할수있다. 아래그림은이러한 Coarse-grained Lock 방식을사용한예시이다. 현재 insert 연산을수행하는 Thread 가 Tree 를사용중이므로다른 Thread 는 insert 연산이완료될때까지기다려야하는것을볼수있다. 10

ii. BST with Fine-grained Lock Race Condition 을막기위해 BST 에대한 insert, remove, search 등의연산수행시연산이수행되는동안접근하는 tree 의 node 에대해다른연산들이접근을못하도록 Critical Section 의범위를 Tree 전체가아닌, 각 node 별로설정하여 Lock 을사용할수있다. 아래그림은이러한 Fine-grained Locking 방법의예시이다. 11

C. Lab2 BST Synchronization 운영체제내에서는다양한자료구조들이사용되며이들자료구조들간의또는자료구조내부에서발생하는 Race Condition 을막기위해다양한기법들이사용된다. 본과제에서는운영체제의다양한부분에서사용되는 Tree 자료구조의간단한알고리즘중하나인 BST 를사용하여동기화기법을구현한다. 1. 기본과제구성 Lab2 BST Synchronization 은아래그림과같은위치에있으며 lab2_bst.c 라는파일의함수들을구현해야한다. 함수구현은소스파일내에정해진형식대로구현하지않아도되나정해진형식을변경하게되면 include/lab2_fs_types.h 의함수선언을변경해주어야한다. 구현해야하는소스파일을빨간색으로표시하였다. lab2_bst.c 파일의 TODO 로명시된함수를구현하여야한다. 2. 기본과제컴파일방법아래그림과같이 make lab2_bst 명령어를통해구현한 lab2_bst.c 소스파일을컴파일하면컴파일결과생성되는 lab2_bst 라는실행파일과, object 파일들을확인할수있다. # make lab2_bst 3. 기본과제테스트방법 lab2_bst.c 를구현한후 lab2_bst 를 test 하는시나리오는 fine-grained 와 coarsegrained 를비교하기위해 thread 의수, test 할 node 의수를입력받아, insert 연산과, remove 연산을 test 각각독립적으로수행되도록하여야한다. remove 연산의경우 random key 값 node 를입력받은 node 의수만큼생성하여 bst 에추가해놓고, 입력받은 thread 의수만큼 node 를분할하여 BST remove 연산을수행후결과를확인한다. insert 연산의경우 random key 값 node 를 12

입력받은 node 의수만큼생성하는연산을입력받은 thread 의수만큼 node 를 분할하여 BST insert 연산을수행후결과를확인한다. 테스트실행파일은아래와같은옵션을통해컴파일할수있다. - t : thread 의개수를의미한다. - c : test 에생성할 node 의개수를의미한다. 지정한수만큼난수의 key 값을 만들어 node 를생성하기때문에겹치는 key 값을가지는수가생길수있다. 13

lab2_bst.c 의함수들이제대로구현되지않는다면, bst 를 Multi thread 에서실행하는데있어오류가출력되며 lab2_bst test 파일이종료될것이다. 하지만, 정상적으로구현하였다면위와같은출력결과를확인할수있을것이다.( 수행결과출력되는 execution time 은레포트제출을위해결과값을가렸다. ) 수행결과출력되는수행시간을통해 single thread, multi-thread coarse grained, multi-thread fine grained 로수행하였을때의결과를비교할수있다. 4. 보너스과제구성기본과제에서 pthread mutex 를활용한 Synchronization 해결기법을구현하였다. 보너스과제에서는 Synchronization 에사용되는 spin lock 을직접구현해본다. s 구현해야하는소스파일을빨간색으로표시하였다. lab2_bonus.c 파일의 TODO 로명시된함수를구현하여야한다. 보너스과제에서는 spinlock 을 atomic 하게구현하기위해 C source code 내에서시스템프로그래밍수업에배운 assembly language 를사용하여야한다. 이를위해 lab2_bonus.c 에함수내부에서 assembly language 의사용예시로 atomic_add, atomic_sub, atomic_inc, atomic_dec 함수를첨부하였다. 보너스과제에서는이를참고하여 atomic 하게동작하는 spinlock 을구현하여야한다. spinlock 은수업시간에숙지한 test and set 연산또는 compare and swap 으로구현할수있다. 5. 보너스과제컴파일방법아래그림과같이 make lab2_bonux 명령어를통해구현한 lab2_bonus.c 소스파일을컴파일하면컴파일결과생성되는 lab2_bonus 라는실행파일과, object 파일들을확인할수있다. # make lab2_bonus 6. 보너스과제테스트방법 보너스과제실행파일에는아래와같은옵션을줄수있다. 14

-s o 옵션을통해 spin lock 을사용하지않은결과 Race Condition 이발생한것을 확인할수있다. #./lab2_bonus t 4 i 1000000 s o -s s 옵션을통해구현한 spin lock 버전으로확인한결과정상적으로구현이 되었다면 Race Condition 이발생하지않은것을확인할수있다. #./lab2_bonus t 4 i 1000000 s s 15

7. 과제제출 i. 제출사항. 구현한 lab2_sync 의압축파일. 구현한 lab2_sync/lab2_bst 의실행결과출력되는 single thread execution time, multi-thread coarse grained execution time, multi-thread fine grained execution time 에대한비교와그이유에대한레포트. ii. 제출방법. lab2_sync 구현제출 아래와같은 directory 에서 tar 명령을통해구현한 lab2_sync directory 에대해압축을수행한후압축결과생기는 lab2_sync_ 학번.tar 파일을 choi_gunhee@dankook.ac.kr 으로제출한다. # tar cvf lab2_sync_ 학번.tar lab2_sync 레포트제출 해당수업시간에교수님께제출. 16