Synchronization and Concurrency fundamentals

Notes

1. Alice & Bob examples and show why Synchronization is so easy for Humans and difficult for Computers
2. Take Alice & Bob examples “Art of Multiprocessor programming” & “Concurrent and Synchronization algorithms”
3. Develop this example thoroughly.
4. Take a little digression to Message Passing Systems and ponder over implementing the Alice and Bob problems using Message passing systems. In this case, it will turn out to be easier to do it via message passing
5. Take the problem of removing an element from Q1 and adding it to Q2. The condition is that for the rest of the world (other threads), the element must either be in Q1 or Q2, but not in both or nowhere. How to solve this using Message passing and Synchronization mechanisms?
6. Read Dijkstra’s original paper to find out if there are some logical deductions for needing monitors, semaphores and condition variables. What is the relation between them? How semaphores are monitors with condition variables. Are Condition variables and Monitors the fundamental concepts for synchronization?
7. What are locks and Mutexes? Explain that they are just synonyms of Blocking Semaphores a.k.a. Binary semaphores
8. Argue if all the synchronization issues can be dealt with theoretically using just Condition variables, Monitors, Semaphores and Mutexes? Obviously yes. But what is the cost incurred and why is that not preferred? Even if the synchronization are issues are fixed, what other problems is it not able to avoid? How atomicity, fault-tolerance and transaction related issues arise here. How will you guarantee atomicity of instructions. How much hardware support is needed? What problems are caused by Compiler driven reordering of instructions. What is the solution to these – Software Transaction Memory or Message Passing Systems?
9. A binary semaphore is logically just like a mutex.However, although it is not enforced, mutexes should be unlocked only by the thread holding the lock. There is no notion of “the thread holding the semaphore,” so any thread can perform a V (or sem_post(3RT)) operation.
10. Why do we need Synchronization primitives other than just atomic registers. State and prove the classic impossibility result in Computer Science:
    

    It is impossible to construct a wait-free implementation of any object with consensus number greater than 1 using atomic registers

11. Explain what Synchronization primitives are why Consensus is so important.
12. Explain if one would still need synchronization primitives in functional programming or are we better of with just STM in a language that allows mutable data structures. This will perhaps decide between Clojure and Scala camps.

Advertisement