At this point, you should be able to defend the need for process synchronization using a variety of practical examples. You should be able to describe the practical examples using formalisms that abstract from the specific details but preserve the essential requirement for synchronization.
You should be able to define precise requirements on process synchronization related to both correctness and liveness.
You should be able to demonstrate how process synchronization can be achieved using a variety of practical tools, including disabling interrupts, atomic reading and atomic writing of shared memory, atomic test and set over shared memory, atomic compare and swap over shared memory, message passing.
You should understand how process synchronization interacts with process scheduling. You should be able to explain how process synchronization can lead to scheduling anomalies.
You should demonstrate familiarity with both implementation and application of common synchronization primitives including barriers, signals, locks, semaphores, condition variables, monitors. You should be able to select and apply proper synchronization primitives to common synchronization problems.
Questions.
Explain what is a race condition.
Explain what is a critical section.
Explain the conditions under which a simple
I++
code fragment on an integer variable can lead to a race condition when executed by multiple threads.
Explain the conditions under which omitting the
volatile
declaration on an integer variable can lead to a race condition when the variable is accessed by multiple threads.
Describe the Mutual Exclusion synchronization task. Draw a Petri net illustrating the synchronization task and present an example of the task in a parallel application.
Describe the Rendez Vous synchronization task. Draw a Petri net illustrating the synchronization task and present an example of the task in a parallel application.
Describe the Producer And Consumer synchronization task. Draw a Petri net illustrating the synchronization task and present an example of the task in a parallel application.
Describe the Readers And Writers synchronization task. Draw a Petri net illustrating the synchronization task and present an example of the task in a parallel application.
Describe the Dining Philosophers synchronization task. Draw a Petri net illustrating the synchronization task and present an example of the task in a parallel application.
Explain how a deadlock can occur in the Dining Philosophers synchronization task. Propose a modification of the synchronization task that will remove the possibility of the deadlock.
Explain the difference between active and passive waiting. Describe when active waiting and when passive waiting is more suitable.
Present a trivial solution to the mutual exclusion problem without considering liveness and fairness. Use active waiting over a shared variable. Explain the requirements that your solution has on the operations that access the shared variable.
Present a solution to the mutual exclusion problem of two processes including liveness and fairness. Use active waiting over a shared variable. Explain the requirements that your solution has on the operations that access the shared variable.
Describe the priority inversion problem.
Explain how priority inheritance can solve the priority inversion problem for simple synchronization primitives.
Present a formal definition of a deadlock.
Present a formal definition of starvation.
Present a formal definition of a wait free algorithm.
Describe the interface of a lock and the sematics of its methods.
Describe the interface of a read-write lock and the sematics of its methods.
Explain when a lock is a spin lock.
Explain when a lock is a recursive lock.
Explain why Windows offer Mutex and
CriticalSection as two implementations of a
lock.
Implement a solution for the mutual exclusion synchronization problem using locks.
Describe the interface of a semaphore and the sematics of its methods.
Implement a solution for the producer and consumer synchronization problem over a cyclic buffer using semaphores.
Describe the interface of a condition variable and the sematics of its methods.
Explain what is a monitor as a synchronization tool and what methods it provides.
Exercises.
Implement a spin lock and then a recursive lock using the spin lock
and the Sleep and Wake functions, as
well as suitable functions of your choice for managing lists and other details,
all without any guarantees as to parallelism. Explain how this implementation
works on a multiprocessor hardware.