Mumbai University > Information Technology > Sem 6 > Distributed System

Marks: 10Marks

Implementing Sequential Consistency Model:

Most commonly used consistency model in DSM.

Protocols depends on whether the DSM system allows replication/migration of shared –memory blocks.

Different Strategies are,

• Non-Replicated, Non-Migrating Blocks(NRNMBs)

• Non-Replicated ,Migrating blocks (NRMBs)

• Replicated, Migrating blocks(RMBs)

• Replicated ,Non-Migrating blocks(RNMBs)

Non-Replicated, Non-Migrating Blocks(NRNMBs)

• Simplest strategy.

• Each block of the shared memory has a single copy whose location is always fixed.

• All access request to a block from any node are sent to the owner node of the block, which has only copy of the block.

• On receiving, a request from a client node, the MMU and OS of the owner node return a responsed to the client.

• Serializing data access creates a bottleneck.

• Parallelism is not possible.

• There is single copy of each block in the system.

• The location of the block never changes.

Non Replicated, Migrating Blocks:

Each block of the shared memory has a single copy in the entire system however; each access to a block causes the block to migrate from its current node to the node from where it is accessed.

The owner node of a block changes as soon as the block is migrated to a new node.

High locality of reference.

It is prone to thrashing.

Parallelism is not possible.

Data Locating in NRMB Strategy

There is a single copy of each block and the location of a block changing dynamically.

Broadcasting: Each node maintains an owned blocks table that contains an entry for each block for which the node is the current owner.

Replicated Migrating Blocks:

To increase parallelism, all DSM systems replicated blocks.

With replicated blocks, read operations can be carried out in parallel with multiples nodes, the average cost of read operation is reduced.

However , replication tends to increase the cost of write operations because for a write to a block all its replicas must be invalidated or update to maintain consistency.

Replication complicates the memory coherence protocol. Basically there are two protocols for enhancing sequential consistency

Write Invalidate:

In this scheme, all copies of a piece of data except one are invalidated before write operation can be performed on it.

When a write faults occurs, its fault handler copies the accessed block from one of the block’s to its own node and invalidates all other copies by sending an invalidate message.

The write operation is performed on own node.

The own node holds the modified version of block and is replicated to other nodes.

Replicated Non-Migrating Blocks (RNB’s)

In this strategy, shared-memory blocks may be replicated at multiples node of the system.

The location of replica is fixed.

A read or write access to a memory address is carried out by sending the access request to one of the nodes having a replica of the block containing the memory address.

Write-update protocol is used.

Sequential consistency is ensured by using a global-sequencer.