Lesson 4c Flashcards
parallel systems
what is barrier sync?
threads will wait until all of them reach a defined point
What is a centralized barrier or counting barrier?
We set N to the number of threads. When each thread reaches the barrier the count is atomically decremented and the thread spins until reaching 0
What is a potential problem of the centralized barrier?
We don’t want to wake up waiting threads (leave the barrier) until count is reset to the number of threads. If we don’t then other barriers could be passed
what is the correct code for the barrier when N = 0?
if c = 0 c := N;//last processor to arrive else while(c > 0); while(c != n);//don't leave the barrier until N is reset
What problem is the sense reversing barrier solving for?
The two spin loops that the counting barrier has
What does the sense variable control?
It switches between true and false as borders are crossed. s=t | s=f | s=t | s=f in this case for barrier b1, b2, b3, b4
what do we spin on?
sense reversal
What is the problem with centralized barrier?
The counting variable causes a log of contention on the network
How do we avoid the centralized contention
divide and conquer “Tree Barrier”
What information is in the non-leaf nodes?
count and lock sense
what are in the leaf nodes
the processes
what do the leafs do when a barrier is reached?
they walk up the tree decrementing the count. If the count = 0 go to parent.
what happens when the root node reaches zero?
all processes are at the barrier. Set count to number braches, flip the lock sense and move down the tree. When the sense is flipped the processes will eventually wake up
What is the benefit of tree barrier?
Less contention since we have many variables
Is the locksense flag statically or dynamically determined
Dynamic. It is determined by the arrival of the process in the tree
