Memory Management in Distributed SystemsIntroductionINTRODUCTIONSlide 4Slide 5Slide 6WHY DISTRIBUTED SHARED MEMORY?DSM ARCHITECTUREDISTRIBUTED SHARED MEMORYALGORITHMS FOR IMPLEMENTING DSMThe Central-Server AlgorithmSlide 12The Migration AlgorithmSlide 14The Read-Replication AlgorithmSlide 16The Full-Replication AlgorithmSlide 18DSM DESIGN ISSUESVIRTUAL TO PHYSICAL ADDRESS TRANSLATIONMemory Coherence ProblemMemory Coherence StrategiesPage SynchronizationInvalidationSlide 25Write-broadcastPage OwnershipCoherency Classes and Memory ConsistencyMemory ConsistencySlide 30Memory Consistency ModelsStrong ConsistencySlide 33Sequential ConsistencySlide 35Causal ConsistencySlide 37Processor ConsistencySlide 39Weak ConsistencySlide 41Release ConsistencySlide 43Slide 44Slide 45Concurrent Writer ProtocolsMultiple Reader and Single Writer ProtocolSlide 48Multiple Reader and Multiple Writer ProtocolSlide 50Cache Coherence ProblemSlide 52Slide 53Snooping CacheSlide 55Directory BasedSlide 57Lock BasedManagement Of Distributed Shared MemorySlide 60Centralized management schemeSlide 62Distributed Management schemeFixed Distributed Management schemeDynamic Distributed Management schemeSlide 66Broadcasting Dynamic Distributed Management schemeHinting Dynamic Distributed Management schemeSlide 69Slide 70Distributed Management SchemesSlide 72Slide 73Slide 74IMPLEMENTATION ISSUESFault-HandlingSlide 77Page ReplacementSlide 79Page SizeSlide 81HARDWARE SUPPORT FOR DSMSlide 83Slide 84CASE STUDIESCloudsSlide 87IVYMEMNETSlide 90METHERMACHREFERENCESQUESTIONSMemory Management in Distributed SystemsGroup#4:•Bandar Alturaif•Praveen Gadikota •Ashwin Avinash Jadhav•Kalyan Chakravarthy Mantravadi01/14/19 Distributed Memory Management 2IntroductionFor using multiple CPUs:•Multiprocessors: contain physical shared memory; Processors in a multiprocessor can easily communicate by reading and writing words in this memory.•Multicomputers: do not contain physical shared memory; processors communicate by exchanging messages.01/14/19 Distributed Memory Management 3INTRODUCTION01/14/19 Distributed Memory Management 4Introduction•To combine the advantages of multiprocessors and multicomputers, simulate shared data on a multicomputer.•These mechanisms are implemented with message passing but they provide the illusion of shared data, namely processors in a multicomputer communicating through distributed shared memory.01/14/19 Distributed Memory Management 5Introduction•A Distributed Shared Memory (DSM) is a memory space that is logically shared by processes running on computers connected by a communication network.•Most existing distributed systems are structured as a number of processes with independent address spaces. These processes communicate via some form of Inter-Process Communication (IPC) system, typically message passing or remote procedure call.01/14/19 Distributed Memory Management 6Introduction•In a DSM system data sharing is supported directly: processes communicate with each other by reading and modifying shared directly-addressable data.•A DSM can be:flat and paged virtual address space.segmented single level store.physical address space.01/14/19 Distributed Memory Management 7WHY DISTRIBUTED SHARED MEMORY?•A distributed system can be viewed as group of computers cooperating with each other to achieve some goal.•Remote Procedure Calls (RPC), were introduced to provide a procedure-call-like interface. Because the "procedure call" is performed in a separate address space, it is difficult for the caller to pass context related data or complicated structures.01/14/19 Distributed Memory Management 8DSM ARCHITECTURE01/14/19 Distributed Memory Management 9DISTRIBUTED SHARED MEMORY•Shared virtual memory is a model of distributed shared memory.•It is a single address space shared by a number of processors.•Any processor can access any memory location in the address space directly.•This address space is divided into pages, which are distributed among the processes.•The system provides a coherent address space: a read operation always returns the value of most recent write to same address.•Mutual-exclusion synchronization can be implemented by locking pages.01/14/19 Distributed Memory Management 10ALGORITHMS FOR IMPLEMENTING DSM•The Central-Server Algorithm•The Migration Algorithm•The Read-Replication Algorithm•The Full-Replication Algorithm01/14/19 Distributed Memory Management 11The Central-Server Algorithm•A central-server maintains all the shared data. •It services the read requests from other clients by returning the data items to them.•It updates the data on write requests by clients and returns acknowledgement messages.•Simple to implement•It is a bottleneck, so shared data is distributed among several servers.01/14/19 Distributed Memory Management 12The Central-Server Algorithm01/14/19 Distributed Memory Management 13The Migration Algorithm•The whole page or block containing data is shipped to the location of the data access request (locality of reference).•It allows only one node to access the shared data at time.•Thrashing problem: pages frequently migrate between nodes while servicing only a few requests.•Use a tunable parameter to determine the duration for which a node can posses a shared data item.01/14/19 Distributed Memory Management 14The Migration Algorithm01/14/19 Distributed Memory Management 15The Read-Replication Algorithm•Extends the migration algorithm by replicating data blocks and allowing multiple nodes to have read access or one node to have read-write access.•The write operation is expensive as all copies of a shared block will have to be invalidated or updated.•It must keep track of location of all the copies.•Reduces average cost of read operations when ratio of reads is large.01/14/19 Distributed Memory Management 16The Read-Replication AlgorithmXX01/14/19 Distributed Memory Management 17The Full-Replication Algorithm•Extension of read-replication algorithm by allowing multiple nodes to have both read and write access to shared data blocks.•Gap-free sequencer: all nodes wishing to modify shared data will send modifications to a sequencer that assigns a sequence# and multicasts modification + sequence# to all nodes with a copy of shared data.01/14/19 Distributed Memory Management 18The Full-Replication Algorithm01/14/19 Distributed Memory Management 19DSM DESIGN ISSUES•The shared virtual memory provides a