Concurrent B+Tree

>>181217
- read https://computing.llnl.gov/tutorials/pthreads/#Mutexes
- port b-tree code to pthreads
- use mutexes to protect data structures that can't withstand concurrent modification or read-during-modification

Granularity of mutexing should be proportional to how much the assignment is worth. If it's just "introduction to threads", global write lock should suffice.

>>181219
Thank you! I'll read that, but, if you go line 1416, 1430 and there is other, mutexing is already use....

>>181217
>https://github.com/uit-inf-2202-f16/assignment-1/blob/master/precode/bpt.c
Actually, he's already done "port b-tree code to pthreads" for you, so all you need to do is identify the structures that need protected, and mutex them.

>>181220
That's just boilerplate to create a barrier out of a mutex, which is later used by the test harness so the main thread of the harness can wait on all the worker threads finishing.

It's worth reading it to see how it's done, and see if there's anything in there you can reuse.

>>181221
So i have to modify the method "do_test" or directly insert/delete/update methods?

So if I got it, line : 1838

for (i = 0; i<num_thread; i++)
pthread_join (pid[i], NULL);

If I change that for :

for (i = 0; i<num_thread; i++){
pthread_mutex_lock (myMutex);
pthread_join (pid[i], NULL);
pthread_mutex_unlock (myMutex);
}

It will works?

Or, no, more at line 1800 when we call the "insert" function

>>181224
>So i have to modify the method "do_test" or directly insert/delete/update methods?
Don't modify do_test.

Modify the tree methods so that do_test passes.

What you need is a readers-writer lock, which appears simple, but is fundamental to OS programming; Ph.Ds have been written on readers-writer locking.

To read the structure, you need to get a read lock (which there can be many of); to modify the structure you need to get a write lock, which you can only get if no-one has a read lock. Writers can starve if the structure is being read all the time, so most implementations delay handing out more read locks if there's a writer waiting on a write lock.

Given that this seems to be an "intro-to-pthreads" course, I'm gonna guess you're allowed to use pthread_rwlock, which is documented quite well here: https://docs.oracle.com/cd/E19455-01/806-5257/6je9h032m/index.html .

If you were writing it yourself, you'd probably use something like a counting lock for the readers, and a two-stage lock for the writers, so a writer can take stage one of the write lock and this stops further readers from getting more read locks.

Ok, i'll try that!
>>181230

>>181226
You need to be using the same mutex for each lock, so make sure you've defined myMutex in the global scope, like in line 1494.

>>181232
Hum... do_test only call insert method, which call a finding method, so I only have to modify those with read lock !?

>>181287
If you've already acquired the write lock, you don't need the read lock.

You need to check for this, because when the write lock is held, you can't acquire read locks, so if you have the write lock and try to take a read lock, you'll never be given it, and your writer will wait forever.

Because it's doing this while holding the write lock, no-one can get a write lock or a read lock, and your entire datastructure ends up deadlocked.

>>181230
Can you explain my what is "counting lock" and "two-stage lock"

Can I use this example to my case ?

https://groups.google.com/forum/#!topic/comp.unix.programmer/4ZkoPLmZxGQ

>>181609
I use spin lock! But thank you for your advices