Sequential Consistency

Sequential Consistency:

1. All replicas execute operations in some total order
2. That total order preserves the process ordering between operations
   — If process P issues operation A before operation B, then A is ordered before B by the process order (i.e., preserves local ordering)
   — If different processes do operations A and B, then there is no process order between them. But there must be some total order.

Thus, The writes have to be synchronous, i.e. we cannot allow concurrent writes.

Implementation

1. Primary Server:

• Designate a primary machine. Every machine sends the read and write operations to the primary.
• The order in which the primary executes the writes determines the total order of the operations.
• The operations are slow. Every operation goes over the network
• The primary server is the bottleneck.

2. Partition Memory:

• Divides the memory into partitions.
• Each machine is assigned as the primary for different partitions.
• This spreads the storage loads across machines. Good performance is achieved if the machines operate mostly on the local partitions.

3. Global Locks:

• This implementation of SC uses one global lock for all addresses in memory.
• To access memory, the machine must first acquire the lock, operate on locked memory, and release the lock.
• This implementation attains SC; the locks' movement determines the total order.

IVY — Case Study

IVY — Integrated Shared Virtual Memory at Yale was one of the first designs for a DSM (Distributed shared Memory) runtime system.

Consistency Model:

IVY aims to provide sequential consistency

• Always read a fresh copy of the data
  — Must invalidate all cached pages before writing a page.
  — This simulates the FIFO queue for a page because once a page is written, all future reads must see the latest value
• Only one processor (owner) can write a page at a times

Shared Virtual Memory:

A shared virtual memory is a single address space shared by a number of processors.

The memory mapping manager views its local memory as a large cache of the shared virtual memory address space for its associated processor.

Memory mapping managers are responsible for the following:

1. implementing the mapping from the local memory to the shared virtual memory,
2. keeping the address space coherent, i.e. the value returned by a read operation is always the same as the value written by the most recent write operation to the same address.

A memory reference will cause a page fault when the page containing the memory location is not in a processor’s current physical memory. When this happens, the memory mapping manager retrieves the page from either the disk or the memory of another processor.

The performance of parallel programs on a shared virtual memory system depends mainly on the number of parallel processes and the degree of data sharing (i.e., contention). Theoretically, performance improves as the number of parallel processes increases, and contention decreases. The contention is less if a program exhibits a locality of references.