Distributed Shared

Memory
Distributed Operating
Systems
Distributed Shared Memory
( DSM )

1
Distributed shared memory

 DSM paradigm provides process with shared address

space.
 Primitives for shared memory:
1. Read(address)
2. Write(address, data)
 Shared memory paradigm gives the system a illusion of
physically shared memory.
 DSM refers to shared memory paradigm applied to
loosely coupled distributed memory systems.

2
Cont….
 Shared memory exists only virtually.
 Similar concept to virtual memory.
 DSM also known as DSVM.
 DSM provides a virtual address space shared among
processes on loosely coupled processors.
 DSM is basically an abstraction that integrates the local
memory of different machine into a single logical entity
shared by cooperating processes.

3
Distributed shared memory

4
DSM Architecture
 Each node of the system consist of one or more CPUs
and memory unit.
 Nodes are connected by high speed communication
network.
 Simple message passing system for nodes to exchange
information.
 Main memory of individual nodes is used to cache pieces
of shared memory space.
 Reduces network latency

5
Cont….
 Memory mapping manager routine maps local memory
to shared virtual memory.
 Shared memory space is partitioned into blocks.
 Data caching is used in DSM system to reduce network
latency.
 The basic unit of caching is a memory block.

6
Cont….
 If data is not available in local memory network block
fault is generated.

 On Network block fault:

 The missing block is migrated from the remote node to the
client process’s node and OS maps it into the application’s
address space.
 Data blocks keep migrating from one node to another on
demand but no communication is visible to the user processes.

7
Design and implementation issues
1. Granularity
2. Structure of Shared memory
3. Memory coherence and access synchronization
4. Data location and access
5. Replacement strategy
6. Thrashing
7. Heterogeneity

8
Granularity

 Refers to the block size of DSM.

 The unit of sharing & the unit of data transfer across the
network when a network block fault occurs.

 Possible unit are a few word, a page or few pages.

9
Structure of Shared memory

 Structure refers to the layout of the shared data in

memory.

 Dependent on the type of applications that the DSM

system is intended to support.

10
Memory Coherence & Access Synchronization
 Replicated and shared data items may
simultaneously be available in the main memories of
a number of nodes.

 Memory coherence problem

 Deals with the consistency of a piece of shared data lying
in the main memories of two or more nodes.

11
Data location and access

 To share data in a DSM, it should be possible to locate

and retrieve the data accessed by a user process.

12
Replacement strategy
 Ifthe local memory of a node is full, a cache miss at that
node implies not only a fetch of accessed data block from
a remote node but also a replacement.

 Data block must be replaced by the new data block.

13
Thrashing

 Data block migrate between nodes on demand.

 Therefore if two nodes compete for write access to a

single data item, the corresponding data block may be
transferred back.

14
Heterogeneity

 The DSM system built for homogeneous system need not

address the heterogeneity issue.

 However, if the underlying system environment is

heterogeneous, the DSM system must be designed to take
care of heterogeneity so that it functions properly with
machines having different architectures.

15
Granularity

 Most visible parameter in the design of DSM system is

block size.

 Sending small packet of data is more expensive than

sending large packet.

16
Cont…
 Factors influencing block size selection:
1. Paging overhead
2. Directory size
3. Thrashing
4. False sharing

17
Paging overhead

 A process is likely to access a large region of its

shared address space in a small amount of time.

 The paging overhead is less for large block size as

compared to the paging overhead for small block size.

18
Directory size

 The larger the block size, the smaller the

directory.

 Result: reduced directory management overhead

for larger block size.

19
Thrashing

 The problem of thrashing may occur:

 when data item in the same data block are being

updated by multiple nodes at the same time.

 with any block size, more likely with larger block

size.

20
False sharing

 Occurs when two different processes access

two unrelated variable that reside in the
same data block.

21
Cont…

 The larger is the block size, higher is the probability of

false sharing.

 False sharing of a block may lead to a thrashing problem.

22
Cont…
Using page size as block size

 Relative advantage and disadvantages of small

and large block size makes it difficult for DSM
designer to decide on a proper block size.

 On Intel Core2 Duo 64-bit system, the page size

is 4kB, which is normal for almost every desktop
PC architectures.

 Linux kernel 2.6.x versions support large pages

(4MB).
23
Advantages of using page size as
block size

 Use of existing page fault schemes to trigger a DSM page

fault.
 Allows the access right control.
 Page size do not impose undue communication overhead
at the time of network page fault.
 Page size is a suitable data entity unit with respect to
memory contention.

24
 Structure of Shared-Memory Space

 Structure defines the abstract view of the shared

memory space for application programmers.

 The structure and granularity of a DSM system are

closely related.

25
Cont…
Three approaches:
1. No structuring
2. Structuring by data type
3. Structuring as a database

26
No structuring

 The shared memory space is simply a linear

array of words.

 Advantages:
 Convenient to choose any suitable page size as the
unit of sharing.
 A fixed grain size may be used for all application.
 Simple and easy to design such a DSM system.

27
Structuring by data type
 The shared memory space is structured as a collection of
objects in the source language.

 The granularity in such DSM system is an object.

 DSM system uses variable grain size to match the size of

the object/variable being accessed by the application.
 Complicates the design and implementation.

28
Structuring as a database
 Structures the shared memory like a database.

 Shared memory space is ordered as an associative memory

called tuple space.

 To perform update, old data item in the DSM are replaced by

new data item.

 Processes select tuples by specifying the number of their

fields and their values or type.

 Access to shared data is non-transparent.

29
Consistency Models
 Consistency requirement vary from application to
application.

 Refers to the degree of consistency that has to be

maintained for the shared memory data.

 If a system supports a stronger consistency model,

weaker consistency model is automatically supported
but the converse is not true.

30
Types of Consistency Models
1. Strict Consistency model
2. Sequential Consistency model
3. Casual consistency model
4. Pipelined Random Access Memory consistency
model (PRAM)
5. Processor Consistency model
6. Weak consistency model
7. Release consistency model

31
Strict Consistency Model
 The strongest form with most stringent consistency
requirement.

 Value returned by a read operation on a memory

address is always the same as the value written by
the most recent write operation to that address.

 All writes instantaneously become visible to all

processes.

 Implementation requires the existence of an absolute

global time to synchronize clocks of all nodes.
 Practically impossible.

32
Sequential Consistency Model
 Proposed by Lamport in 1979.

 All processes see the same order of all memory access

operations on the shared memory.

 Exact order of access operations are interleaved & does

not matter.

33
Cont…
Example :
 Operations performed in order
1. Read(r1)
2. write(w1)
3. Read(r2)

34
Cont…

 Only acceptable ordering

 for a strictly consistency memory
(r1, w1, r2)

 For sequential consistency model

Any of the orderings (r1,w1,r2), (r1,r2,w1), (w1,r1,r2),
(w1,r2,r1), (r2,r1,w1), (r2,w1,r1), is correct

if all processes see the same ordering.

35
Cont…
 The consistency requirement of the sequential
consistency model is weaker than that of the strict
consistency model.

 A sequentially consistent memory provide one-copy

/single-copy semantics.

 Acceptable by most applications.

36
Casual Consistency Model (PCR)
 Proposed by hutto and ahemad in 1990.

 All processes see only those memory reference

operations in the correct order that are potentially
casually related (PCR).
 Otherwise seen by different processes in different order.

 Required to construct and maintain dependency graphs

for memory access operations.

37
Pipelined Random Access Memory
(PRAM) Consistency model
 Proposed by Lipton and Sandberg in 1988.
 A weaker consistency semantics.
 Ensures that all write operations performed by a single
process are seen by all other processes in the order in
which they were performed as if all write operations
performed by a single process are in a pipeline.

38
PRAM
 P1 – W11 & W12
 P2 – W21 & W22
 P3 can see these as ((W11,W12), (W21,W22))
 P4 can see these as ((W21,W22), (W11,W12))

39
Cont…

 Advantages:
 Simple and easy to implement.
 Good performance

 Limitation:
 All processes may not agree on the same order of memory
reference operations.

40
Processor Consistency model
 Proposed by Goodman in 1989.

 Very similar to PRAM model with additional restriction of

memory coherence.

 Memory coherence:
 For any memory location, all processes agree on the same order
of all write operation to that location.

 Processor consistency ensures that all write operations

performed on the same location are seen by all
processes in the same order.
41
Weak consistency model
 Proposed by Dubois in 1988.

 Many applications may demand that:

 It is not necessary to show the change in memory
done by every write operation to other processes.

 Isolated accesses to shared variable are rare.

42
Cont…
 Idea of weak consistency:
 Better performance can be achieved if consistency
is enforced on a group of memory reference
operations rather than on individual memory
reference operations.

 Uses a special variable called a

synchronization variable to synchronize
memory.

43
Cont…
Requirements:
1. All accesses to synchronization variables must obey
sequential consistency semantics.
2. All previous write operations must be completed
everywhere before an access to a synchronization
variable is allowed.
3. All previous accesses to synchronization variables must
be completed before access to a non-synchronization
variable is allowed.
4. Better performance at the cost of putting extra burden on the
programmers.
44
Release consistency model

 Enhancement of weak consistency model.

 Use of two synchronization variables:

 Acquire
 Release

45
Cont…

 Acquire
 Used to tell the system that a process is
entering Critical section.

 Results in propagating changes made by other

nodes to process's node.

46
Cont…

 Release
 Used to tell the system that a process has just
exited critical section.

 Results in propagating changes made by the

process to other nodes.

47
Cont…
 A variation of release consistency is lazy
release consistency proposed by Keleher in
1992.

 Modifications are not sent to other nodes at the

time of release but only on demand.

 Better performance.

48
Implementing sequential consistency
model
 Protocol for implementing depends on
whether the DSM system allows:
 replication & / or
 Migration
Of shared memory data blocks.

49
Cont…
Strategies:
1. Nonreplicated, Nonmigrating blocks (NRNMB)
2. Nonreplicated, Migrating blocks (NRMB)
3. Replicated, migrating blocks (RMB)
4. Replicated, Nonmigrating blocks (RNMB)

50
NRNMBS
 Simplest strategy.

 Each block of the shared memory has a single

copy whose location is always fixed.

51
Cont…

52
Cont…
 Enforcing sequential consistency is trivial.

 Method is simple and easy to implement.

 Drawbacks:
 Serializing data access creates a bottleneck.

 Parallelism is not possible.

53
Cont…
Data locating in the NRNMB strategy:
 There is a single copy of each block in the entire
system.

 The location of a block never changes.

 Requires a simple mapping function to map a block

of a node.

54
NRMBS
 Each block of the shared memory has a single
copy in the entire system.

 Migration is allowed.
 Owner node of a block changes as soon as the
block is migrating to a new node.

 Only the processes executing on one node

can read or write a given data item at any
time.
55
Cont…

56
Cont…
 Advantage :
 No communications cost are incurred when a
process accesses data currently held locally.
 Advantage of data access locality.

 Drawbacks:
 Prone to thrashing problem.
 No parallelism.

57
Data locating in the NRMB strategy

 There is a single copy of each block, the location

of a block keeps changing dynamically.

58
Cont…
Following method used:
1. Broadcasting
2. Centralized server algorithm
3. Fixed distributed server algorithm
4. Dynamic distributed server algorithm

59
Broadcasting

 Each node maintains an owned block table

that contains an entry for each block for
which the node is the current owner.

60
Cont…

61
Cont….

 On a fault,
 Fault handler of the faulting node broadcasts a
read/write request on the network.

Disadvantage:
 Not scalable.

62
Centralized server algorithm

63
Cont…
 A centralized server maintains a block table
that contains the location information for all
block in the shared memory space.

Drawbacks:
 A centralized server serializes location
queries, reducing parallelism.

 The failure of the centralized server will cause

the DSM system to stop functioning.
64
Fixed distributed server algorithm

65
Cont..
 A direct extension of the centralized server
scheme.

 There is a block manager on several nodes.

 Each block manager is given a predetermined

subset of data blocks to manage.

 On fault, the mapping functions is used by

the currently accessed block.
66
Dynamic distributed server algorithm

67
Cont…
 Does not use any block manager and
attempts to keep track of the ownership
information of all block in each node.

 Each node has a block table.

 Contains the ownership information for all blocks.

 Use of probable owner.

 When fault occurs, the faulting node extracts 68

from its block table the node information.
RMB - Replicated, migrating blocks
 Used to increase parallelism.

 Read operations are carried out in parallel at multiple

nodes by accessing the local copy of the data.

69
Cont…
 Replication tends to increase the cost of write
operation.
 Problem to maintain consistency.

 Extra expense if the read/write ratio is large.

70
Cont…
 Protocols to ensure sequential consistency:
1. Write-invalidate
2. Write-update

71
Write-invalidate
 All copies of a piece of data except one are invalidated
before a write can be performed on it.

 After invalidation of a block, only the node that performs

the write operation on the block holds the modified
version of the block.

72
Cont…

73
Write-update
 A write operation is carried out by updating all copies of
the data on which the write is performed.

 On write fault, the fault handler copies the accessed

block from one of the block’s current node to its own
node.

 The write operation completes only after all the copies of

the block have been successfully updated.

74
Cont…

75
Cont…

 Assign sequence number to the modification and

multicasts that to all the nodes where a replica of the
data block to be modified is located.

 The write operations are processed at each node in

sequence number order.

 If the verification fails, node request the sequencer

for a retransmission of the missing modification.

76
Cont…

77
Cont…
 Write-update approach is very expensive.

 Inthe write-invalidate approach, updates are only

propagated when data is read and several updates
can take place before communication is necessary.
 Use of status tag associated with each block.
 Indicates the block is valid/shared/ read-only / writable.

78
Cont…

Read request:
 If there is a local block containing the data and if it
is valid, the request is satisfied by accessing the
local copy of data.

 Otherwise, the fault handler of the requesting node

generates a read fault.

79
Cont…

Write request:
 If there is a local block containing the data and if it
is valid and writable, the request is immediately
satisfied by accessing the local copy of the data.

 Otherwise, the fault handler of the requesting node

generates a write fault and obtain a valid copy of
the block and changes its status to writable.

80
Data Locating in the RMB strategy

Write-invalidate protocol

1. Locating the owner of a block.

2. Keeping track of the node that currently has a
valid copy of the block.

81
Cont…
Following algorithms may be used:
1. Broadcasting
2. Centralized-server algorithm
3. Fixed distributed-server algorithm
4. Dynamic distributed-server algorithm

82
Cont… : Broadcasting

83
Cont…
 Each node has an owned block table.
 Contains an entry for each block for which the node is the
owner.

 A copy-set field in each entry

 Contains a list of nodes that currently have a valid copy of the
corresponding block.

 When the read fault occurs, the faulting node sends a

broadcast read request on the network.

 When a write fault occurs, the node sends a broadcast

write request on the network. 84
Centralized-server algorithm

85
Cont…
 Similar to the centralized-server algorithm of the NRMB
strategy.
 Each entry of the block table, managed by the
centralized server, has:
 an owner-node field.
 Indicates the current owner node of the block.
 a copy-set field
 Contains a list of nodes having a valid copy of the block.

86
Cont…

 When read/write fault occurs, the node send a

read/write fault request for the accessed block to the
centralized server.

87
Fixed distributed-server algorithm

88
Cont…
 Role of the centralized server is distributed to several
distributed servers.
 There is a block manager on several node.
 When fault occurs, the mapping function is used to find
the location of the block manager.

89
Dynamic distributed-server algorithm

90
Cont…
 Each node has a block table that contains an entry for all
block in the shared memory space.

 When a fault occurs, the fault handler of the faulting

node extracts the probable owner node information,
send a request for the block to that node.

 On receiving the block and copy set information, node

sends an in validation request to all nodes in the copy-
set.
91
Cont…
 To reduce the length of the chain of node to be
traversed to reach the true owner of a block, the
probable owner field of a block in a node is updated:
1. Whenever the node receives an invalidation request.
2. Whenever the node relinquishes ownership, that is on a
write fault.
3. Whenever the node forwards a fault request.

92
Cont…

 First two cases the probable owner field is changed to

the new owner of the block.

 Third case the probable owner field is changed to the

original faulting node.

93
Replicated, Non-migrating Block
 A shared memory block may be replicated at multiple
node of the system but the location of each replica is
fixed.
 All replicas of a block are kept consistent by updating
them all in case of a write access.
 Sequential consistency is ensured by using a global
sequencer to sequence the write operation of all nodes.

94
Data locating in the RNMB strategy
Following characteristics:
1. The replica location of a block never change.
2. All replicas of a data block are kept consistent.
3. Only a read request can be directly sent to one of the
node having a replica and all write requests have to
be sent to the sequencer.

95
96
Cont….
 The sequencer assign the next sequence number to
the requested modification.

 It multicasts the modification with this sequence

number to all the nodes listed in the replica set field.

97
Munin : A Release Consistent DSM
System
 Pg 259 – Pg 262

98
Replacement strategy
 DSM system allows shared memory block to
be dynamically migrated/replicated.

 Issues:
 Which block should be replaced to make space for
a newly required block?

 Where should the replaced block be placed?

99
Which block to replace?

 Classification of replacement algorithms:

1. Usage based verses non-usage based

2. Fixed space verses variable space

100
Cont…
Usage based algorithms
 Keep track of the history of usage of a cache line and use
this information to make replacement decisions.

 Example : Least recently used.

 Suitable for DSM

 Due to data access locality feature.

101
Cont…
Non-usage based algorithms
 Do
not take the record of use of cache lines into account
when doing replacement.

 Example:First in first out and Rand (random or

pseudorandom).

102
Cont…
Fixed space algorithms
 Assumes that the cache size is fixed.

Variable space algorithms

 Assumes that the cache size can be changed dynamically
depending on the need.
 A fetch does not imply a replacement, and a swap-out
can take place without a corresponding fetch.
 Not suitable for a DSM system.

103
Cont…
 Classification of each memory block of a
node:
 Unused
 a free memory block that is not currently being
used.

 Nil
 a block that has been invalidated.

104
Cont…

 Read-only
 a block for which the node has only read access
right.

 Read-owned
 a block for which the node has only read access
right but it also owner of the block.

 Writable
 a block for which the node has write access
permission.

105
Cont…
 Replacement priorities
1. Both unused and nil block have the highest
replacement priority.
2. The read-only block have the next replacement
priority.
3. Read-owned and writable block for which
replica(s) exist on some other node (s) have the
next replacement priority.
4. Read-owned and writable block for which only this
node has a copy have the lowest replacement
priority.
106
Where to place a replaced block
 Approaches for storing a useful block:
1. Using secondary store.
1. The block is simply transferred on to a local disk.
2. It does not waste any memory space.

2. Using the memory space of other nodes.

 Methods require each node to maintain a table of
free memory space in all other nodes.

107
Thrashing
 Occurs when the system spends a large amount of time
transferring shared data blocks from one node to
another.

 Degrades system performance considerably.

108
Cont…
 Situations for thrashing:
1. When interleaved data accesses is made by
processes on two or more node.

2. When blocks with read only permission are

repeatedly invalidated soon after they are
replicated.

109
Cont…

Methods for solving Thrashing problems:

1. Providing application controlled locks.

 Locking data to prevent other node from

accessing that data for a short period of time can
reduce Thrashing.

110
Cont…

2. Nailing a block to a node for a minimum

amount of time

1. Disallows a block to a be taken away from a node

until a minimum amount of time t elapses after its
allocation to that node.

2. Drawback: Difficult to choose the appropriate

value for the time t.

111
Cont…

3. Tailoring the coherence algorithm to the shared-

data usage patterns.

Thrashing can also be minimized by using different

coherence protocols for shared data having
different characteristics. For example, the
coherence protocol used in Munin for write shared
variables avoids the false sharing problem, which
ultimately results in the avoidance of thrashing.

112
Reading
 Pg 266 – Pg 270

113
Advantage of DSM
1. Simpler Abstraction
1. The shared memory programming paradigm shields
the application programmers from many such low
level concern.

2. Advantage:
1. Simpler abstraction to the application programmers of
loosely coupled distributed memory machine.

114
Advantage of DSM
2. Better portability of distributed application programs
 The access protocol is consistent with the way
sequential application access data.

 More natural transition from sequential to distributed

application.

 Worse performance of application if they use

message passing directly.

115
Cont…
3. Better performance of some application
 Some application using DSM can outperform their
message passing counterparts due to:

 Locality of data

 On-demand data movement

 Larger memory space

116
Cont…

 Locality of data
 The computation model of DSM is to make the data
more accessible by moving it around.

 Results in reduced overall communication cost for

such application.

117
Cont…
 On demand data moment
 The computation data modeled of DSM also
facilitates on demand moment of data as they are
being accessed.

 Time needed for the data exchange phase is often

dictated by the throughput of existing
communication bottlenecks.

 On demand data movements facility provided by

DSM eliminates the data exchange phase.

118
Cont…
4. Flexible communication environment
 The message passing paradigm requires recipients
identification and coexistence of the sender and
receiver processes.

 Here, the sender process need not specify the

identity of the receiver processes of data.

119
Cont…

5. Ease of process migration

 Migration of a process is tedious and time
consuming.

 The computation model of DSM provides the facility

of on demand migration of data between
processors.

120