Concurrent Binary Search Tree
Team
| leeshinyook | hs-krispy |
|---|---|
 |
 |
We are students of Dankook University's software department. We are working on a project for the Cpu
scheduling algorithm.
Pull requests are always welcome.
Code Structure
We did this project to measure the performance of both locking(fine-grained lock, coarse-grained lock) in BST.
insert,remove
Basic BST in single thread
insert_fg,remove_fg
Fine-grained lock in multi-threaded BST
insert_cg,remove_cg
Coarse-grained lock in multi-threaded BST
How to run
We have set up a makefile for convenient code execution.
Since it is a file written in c lang, so gcc installation is required!
Also, make installation is required, so please install it first.
1. Clone Project
$ git clone https://github.com/hs-krispy/Lab2_Sync.git
2. Make
$ make lab2_bst
The make command creates an executable file. An executable file should have been created in your current directory.
3. Run
$ ./lab2_bst -t 4 -c 1000000
If you want to delete the generated files, type make clean
Measure and Review
We visualized about 30 data per thread Using Python. First, using c file input and output, csv files were created. The set of data is in BST.csv.
Insert
That is, even though the number of threads increases, there is no part to be processed in parallel, and the above results can be confirmed due to the number of locks and unlocks and the cost issues associated with context switching.
Delete
The lock contention of threads occurs excessively and the execution time is slowed down due to the cost. As a result, it can be seen that in a multi-threaded environment, lock and unlock must be properly applied around the critical area to improve performance.