In this model, memory is accessible by multiple threads. It has several advantages over the message passing. Communication between processors is fast and It does not need data partitioning.
There is no share resource between processes, and concurrent process communicate by exchanging messages. This method is lockless and mutual exclusion is not required.
- Strict Consistency specifies that memory commands(specially write) are indivisible and effects of command immediately is available to the later read commands.
- Sequentially consistent specifies that memory commands(specially write) are indivisible and effects of command immediately is available to the later read commands. It also specifies that all program's command executed in order that programmer wrote
- Relaxed(Weak) consistent memory commands are not atomic in all cases. This model is used to perform optimizations in hardware and compiler designing.
S = 1/(1-p+(p/n))
Amdahl's Law shows that the amount of parallelism is important because the maximum amount of speedup is:
1/(1-p)
Then speedup declines as sequential proportion increases and for getting a better performance we should try to minimize the sequential part.
- Single Instruction, Single Data stream (SISD) provide no parallelism
- Single Instruction, Multiple Data streams (SIMD) is useful in multi media applications such as image processing. A SIMD CPU has a single control unit and multiple ALUs. Control unit broadcasts instructions to the ALUs.
- Multiple Instruction, Single Data stream (MISD) is not practical
- Multiple Instruction, Multiple Data streams (MIMD) that most of today's computers use this architecture. In this model, CPU consists of a collection of fully independent processing units or cores. Each core has its own control unit and its own ALU.
- Organized by task
- Organized by data
- Organized by data follow
- synchronization: Threads need to coordinate the order of thread execution. Synchronization is used to access critical section or to reach a specific condition.
- communication: It means data exchange between threads. Message passing is one of the common way of communication. MPI(message passing interface) is the most common interface to communicate.
- load balancing: It means try to divide same amount of work among threads.
- scalability: It helps us to use efficiently system resource when run in more core system.
- Machine level instruction that provides atomic test and set value.
- Semaphore acts as a counter that controllers the access of specific number of threads to critical section. Strong semaphore can guarantee the order of process based on FCFS (First Come First Service).
- Conditional variable: When a specific condition occur one or more of waiting threads wake up.
- Monitor: Higher level construct to hide implementation details from programmer.
- Timeouts
- Deadlock prevention
- Deadlock detection
- Consistency: All nodes have a same data at the same time. If one part of database modification fails, the entire modification fails and the database state is left unchanged. We can achieve it by using Transaction.
- Availability: If some nodes fail, substitute nodes cover their duties. It is achievable by using Replication.
- Partition tolerance: System continues to operate despite loss of connection between some nodes.
Eventual Consistency(or optimistic consistency) sacrifices consistency to achieve a high availability. In this model updates propagate eventually through the nodes and all the replicas will be consistent eventually. Most of the modern database(NoSQL) are fall in this category.
If we have following definitions:
- N = number of nodes to store replicas
- W = minimum number of replicas that is need to have a successful update (if system cannot write to W nodes because of failures, the write operation has to fail)
- R = minimum number of replicas that is needed for a successful read (if system cannot read an identical value from R nodes because of failures or inconsistency, the read operation has to fail)
We have a strong consistency if W+R > N .
For example if N=3, R=2, W=2 then we have a strong consistency.
In eventual consistency(Weak consistency) W+R <= N to provide a better latency.
Multi-Version Concurrency Control (MVCC) is used to manage concurrent access to a distributed database. In MVCC mechanisms, requests are run in parallel without using lock then write operations do not block reads. To change a value in DB, you create an new version of that value and save it over the old one. Since new request can append new version of data to the database without having to wait for acquiring lock. Conflict can occurs when you change the same data(with same version) in two different database simultaneously. Conflict is detected and resolved by merging the two versions and save the result as a new version.