Synchronization

Background

• Concurrent access to shared data may result in data inconsistency.
• Maintaining data consistency requires a mechanism to ensure the orderly execution of the cooperating process.

Race condition

• Race condition: the situation where several processes access and manipulate shared data concurrently. The final value of the shared data depends upon which process finishes the list.
• To prevent a race condition, concurrent processes must be synchronized.
• On a single-processor machine, we could disable interrupt or use non-preemptive CPU scheduling.
• Commonly described as a critical section problem

Critical Section Requirements

• Mutual Exclusion: if process P is executing in its CS, no other processes can be executing in its CS.
• Process: if no process is executing in its CS and there exist some processes that wish to enter their CS, these processes cannot be postponed indefinitely.
• Bounded waiting: a bound must exist on the number of times that other processes are allowed to enter their CS after a process has made a request to enter its CS.

Critical Section Solutions & Synchronization Tools

• Software Solution.
• Peterson's Solution.
• Bakery algorithm(n process).
• Condition Variable(CV).
• wait() --- Block until another thread call signal() or broadcast() on the CV
• signal() --- Wake up one thread waiting on the CV
• broadcast() --- Wake up all threads waiting on the CV
• Synchronization Hardware.
• Atomic instructions(as one uninterruptible unit).
• Examples: TestAndSet(var), Swap(s,b) .
• Semaphore.
• A tool to generalize the synchronization problem(easier to solve, but no guarantee for correctness).
• A record of how many units of a particular resource is available
• If # record = 1 -> binary semaphore, mutex lock.
• If # record > 1 -> counting semaphore.
• Monitor.
• High-level synchronization construct that allows the safe sharing of an abstract data type among concurrent processes.
• The presentation of the monitor type consists of:
• Declarations of variables whose values define the state of an instance of the type.
• Procedure/functions that implement operations on the type.
• The monitor type is similar to a class in the O.O. language.
• A procedure with a monitor can access only local variables and formal parameters.
• The local variables of a monitor can be used only by the local procedures.
• But, the monitor ensures that only one process at a time can be active within the monitor.
• A similar idea is incorporated into many progs. language: 
• Concurrent Pascal, C#, and Java

Monitor condition variables

• To allow a process to wait within the monitor, a condition variable must be declared, as condition x,y.
• The condition variable can only be used with the operations wait() and signal().
• x.wait()
• This means that process invokes this operation until another process invokes it.
• x.signal()
• Resume exactly on the suspended process. If no process is suspended, then the signal operation has no effect(in contrast, the signal always changes the state of a semaphore).

reference:

https://www.amazon.com/-/zh_TW/Operating-System-Concepts-Abraham-Silberschatz/dp/1119800366/ref=sr_1_1?keywords=Operating-System-Concepts&qid=1669538704&s=books&sr=1-1