Synchronization (computer science)

Concept in computer science, referring to processes, or data

In computer science, synchronization is the task of coordinating multiple of processes to join up or handshake at a certain point, in order to reach an agreement or commit to a certain sequence of action.

The need for synchronization does not arise merely in multi processor systems but for any kind of concurrent processes; even in single processor systems. Mentioned below are some of the main needs for synchronization:

Forks and Joins: When a job arrives at a fork point, it is split into N sub jobs which are then serviced by n tasks. After being serviced, each sub job waits until all other sub jobs are done processing. Then, they are joined again and leave the system. Thus, parallel programming requires synchronization as all the parallel processes wait for several other processes to occur. Producer Consumer: In a producer consumer relationship, the consumer process is dependent on the producer process until the necessary data has been produced. Exclusive use resources: When multiple processes are dependent on a resource and they need to access it at the same time, the operating system needs to ensure that only one processor accesses it at a given point in time. This reduces concurrency.

One of the challenges for exascale algorithm design is to minimize or reduce synchronization. Synchronization takes more time than computation, especially in distributed computing. Reducing synchronization drew attention from computer scientists for decades. Whereas it becomes an increasingly significant problem recently as the gap between the improvement of computing and latency increases. Experiments have shown that (global) communications due to synchronization on distributed computers takes a dominated share in a sparse iterative solver. This problem is receiving increasing attention after the emergence of a new benchmark metric, the High Performance Conjugate Gradient(HPCG), for ranking the top 500 supercomputers.

Many systems provide hardware support for critical section code. A single processor or uniprocessor system could disable interrupts by executing currently running code without preemption, which is very inefficient on multiprocessor systems. "The key ability we require to implement synchronization in a multiprocessor is a set of hardware primitives with the ability to atomically read and modify a memory location. Without such a capability, the cost of building basic synchronization primitives will be too high and will increase as the processor count increases. There are a number of alternative formulations of the basic hardware primitives, all of which provide the ability to atomically read and modify a location, together with some way to tell if the read and write were performed atomically. These hardware primitives are the basic building blocks that are used to build a wide variety of user level synchronization operations, including things such as locks and barriers. In general, architects do not expect users to employ the basic hardware primitives, but instead expect that the primitives will be used by system programmers to build a synchronization library, a process that is often complex and tricky." Many modern pieces of hardware provide such atomic instructions, two common examples being: test and set, which operates on a single memory word, and compare and swap, which swaps the contents of two memory words.

In Java, one way to prevent thread interference and memory consistency errors, is by prefixing a method signature with the synchronized keyword, in which case the lock of the declaring object is used to enforce synchronization. A second way is to wrap a block of code in a synchronized(someObject){ } section, which offers finer grain control. This forces any thread to acquire the lock of someObject before it can execute the contained block. The lock is automatically released when the thread which acquired the lock leaves this block or enters a waiting state within the block. Any variable updates made by a thread in a synchronized block become visible to other threads when they similarly acquire the lock and execute the block. For either implementation, any object may be used to provide a lock because all Java objects have an intrinsic lock or monitor lock associated with them when instantiated. Java synchronized blocks, in addition to enabling mutual exclusion and memory consistency, enable signaling—i. e. sending events from threads which have acquired the lock and are executing the code block to those which are waiting for the lock within the block. Java synchronized sections, therefore, combine the functionality of both mutexes and events to ensure synchronization. Such a construct is known as a synchronization monitor. The NET Framework also uses synchronization primitives. "Synchronization is designed to be cooperative, demanding that every thread follow the synchronization mechanism before accessing protected resources for consistent results. Locking, signaling, lightweight synchronization types, spinwait and interlocked operations are mechanisms related to synchronization in NET." Many programming languages support synchronization and entire specialized languages have been written for embedded application development where strictly deterministic synchronization is paramount.

Another effective way of implementing synchronization is by using spinlocks. Before accessing any shared resource or piece of code, every processor checks a flag. If the flag is reset, then the processor sets the flag and continues executing the thread. But, if the flag is set (locked), the threads would keep spinning in a loop and keep checking if the flag is set or not. But, spinlocks are effective only if the flag is reset for lower cycles otherwise it can lead to performance issues as it wastes many processor cycles waiting.

Synchronization was originally a process based concept whereby a lock could be obtained on an object. Its primary usage was in databases. There are two types of (file) lock; read only and read–write. Read only locks may be obtained by many processes or threads. Readers–writer locks are exclusive, as they may only be used by a single process/thread at a time. Although locks were derived for file databases, data is also shared in memory between processes and threads. Sometimes more than one object (or file) is locked at a time. If they are not locked simultaneously they can overlap, causing a deadlock exception. Java and Ada only have exclusive locks because they are thread based and rely on the compare and swap processor instruction. An abstract mathematical foundation for synchronization primitives is given by the history monoid. There are also many higher level theoretical devices, such as process calculi and Petri nets, which can be built on top of the history monoid.

Following are some synchronization examples with respect to different platforms.