Memory Management in Distributed Systems Group 4 Bandar Alturaif Praveen Gadikota Ashwin Avinash Jadhav Kalyan Chakravarthy Mantravadi Introduction For 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 2 INTRODUCTION 01 14 19 Distributed Memory Management 3 Introduction 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 4 Introduction 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 5 Introduction 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 6 WHY 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 calllike 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 7 DSM ARCHITECTURE 01 14 19 Distributed Memory Management 8 DISTRIBUTED 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 9 ALGORITHMS FOR IMPLEMENTING DSM 01 14 19 The Central Server Algorithm The Migration Algorithm The Read Replication Algorithm The Full Replication Algorithm Distributed Memory Management 10 The 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 11 The Central Server Algorithm 01 14 19 Distributed Memory Management 12 The 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 13 The Migration Algorithm 01 14 19 Distributed Memory Management 14 The 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 15 The Read Replication Algorithm X 01 14 19 Distributed Memory Management X 16 The 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 17 The Full Replication Algorithm 01 14 19 Distributed Memory Management 18 DSM DESIGN ISSUES 01 14 19 The shared virtual memory provides a virtual address space that is shared among all processors in loosely coupled distributed memory multiprocessor systems Application programs can use the shared virtual memory just as they would a traditional virtual memory except that processes can run on different processors in parallel Memory mapping managers implement the mapping between the local memories and the shared virtual memory address space The main difficulty in building shared virtual memory is solving the memory coherence problem Distributed Memory Management 19 VIRTUAL TO PHYSICAL ADDRESS TRANSLATION 01 14 19 Distributed Memory Management 20 Memory Coherence Problem A memory is coherent if the value returned by a read operation is always the last value written to the same address The design of shared virtual memory is greatly influenced by the strategies for maintaining coherence 01 14 19 Distributed Memory Management 21 Memory Coherence Strategies The techniques are classified by the way they deal with 1 Page Synchronization 2 Page Ownership 01 14 19 Distributed Memory Management 22 Page Synchronization There are two basic approaches 1 Invalidation 2 Write broadcast 01 14 19 Distributed Memory Management 23 1 Invalidation There is a single owner of each page and only the owner can read and write to it If a write fault to a page occurs all copies of the page are invalidated the access of the page is changed to write a copy of the page is moved to the requesting processor if it does not have one already This processor is now the owner of the page and can proceed in reading and writing return to the faulting instruction 01 14 19 Distributed Memory Management 24 1 Invalidation If a read fault to a page occurs
View Full Document
Unlocking...