Outline Announcement Distributed file systems continued Distributed shared memory Announcement Programming project 1 demonstration You can come on April 1 or April 3 from 9 30 11 00 in my office to do the demonstration Or you can set up an appointment with me You need to have the demonstration before April 17 What you need to prepare I may ask you some questions based on your report and your implementation I will ask you to demonstrate at least one configuration with and without mutual exclusion January 15 2019 COP 5611 Operating Systems 2 Distributed Shared Memory Distributed computing is mainly based on the message passing model Client server model Remote procedure calls Distributed shared memory is a resource management component that implements the shared memory model in distributed systems where there is no physically shared memory January 15 2019 COP 5611 Operating Systems 3 Memory Hierarchies January 15 2019 COP 5611 Operating Systems 4 Virtual memory January 15 2019 COP 5611 Operating Systems 5 Page Table Mapping January 15 2019 COP 5611 Operating Systems 6 Distributed Shared Memory cont This is a further extension of the virtual memory management on a single computer When a process accesses data in the shared address space a mapping manager maps the shared memory address to the physical memory which can be local or remote January 15 2019 COP 5611 Operating Systems 7 Distributed Shared Memory cont January 15 2019 COP 5611 Operating Systems 8 Distributed Shared Memory cont A mapping manager is a layer of software to map addresses in user space into the physical memory addresses January 15 2019 COP 5611 Operating Systems 9 Distributed Shared Memory cont With DSM application programs can access data in the shared space as they access data in traditional virtual memory Mapping manager can move data among the local main memory local disk and another nodes January 15 2019 COP 5611 Operating Systems 10 Distributed Shared Memory cont Advantages of DSM It is easier to design and develop algorithms with DSM than message passing models DSM allows complex structures to be passed by reference simplifying the distributed application development DSM can cut down the overhead of communication by exploiting locality in programs DSM can overcome some the architectural limitations of shared memory machines January 15 2019 COP 5611 Operating Systems 11 Distributed Shared Memory cont Central implementation issues in DSM How to keep track of the location of remote data How to overcome the communication delays and high overhead associated with communication protocols How to improve the system performance January 15 2019 COP 5611 Operating Systems 12 The Central Server Algorithm A central server maintains all the shared data It serves the read requests from other nodes or clients by returning the data items to them It updates the data on write requests by clients January 15 2019 COP 5611 Operating Systems 13 The Central Server Algorithm cont January 15 2019 COP 5611 Operating Systems 14 The Migration Algorithm In contrast to the central server algorithm data in the migration algorithm is shipped to the location of data access request Subsequent accesses can then be performed locally Thrashing can be a problem January 15 2019 COP 5611 Operating Systems 15 The Migration Algorithm cont January 15 2019 COP 5611 Operating Systems 16 The Migration Algorithm cont January 15 2019 COP 5611 Operating Systems 17 The Read Replication Algorithm The read replication algorithm allows multiple node to have read access or one node to have read write access January 15 2019 COP 5611 Operating Systems 18 The Read Replication Algorithm January 15 2019 COP 5611 Operating Systems cont 19 The Read Replication Algorithm January 15 2019 COP 5611 Operating Systems cont 20 The Full Replication Algorithm This is a further extension of the readreplication algorithm It allows multiple nodes to have both read and write access to shared data blocks Data consistency issue January 15 2019 COP 5611 Operating Systems 21 The Full Replication Algorithm January 15 2019 COP 5611 Operating Systems cont 22 Memory Coherence Memory consistency models Many consistency models have been proposed These models differ in Restrictiveness Implementation complexity Ease of programming Performance January 15 2019 COP 5611 Operating Systems 23 Memory Coherence cont Strict consistency Any read on a data item x returns a value corresponding to the result of the most recent write on x Sequential consistency The result of any execution is the same as if the operations by all processes on the data store were executed in some sequential order and the operations of each individual process appear in this sequence in the order specified by its program January 15 2019 COP 5611 Operating Systems 24 Memory Coherence cont January 15 2019 COP 5611 Operating Systems 25 Memory Coherence cont Process P1 Process P2 Process P3 x 1 print y z y 1 print x z z 1 print x y January 15 2019 COP 5611 Operating Systems 26 Memory Coherence cont x 1 print y z y 1 print x z z 1 print x y x 1 y 1 print x z print y z z 1 print x y y 1 z 1 print x y print x z x 1 print y z y 1 x 1 z 1 print x z print y z print x y Prints 001011 Prints 101011 Prints 010111 Prints 111111 a January 15 2019 b c COP 5611 Operating Systems d 27 Memory Coherence cont General consistency All the copies of a memory location eventually contain the same data when all the writes issued by every process have completed Causal consistency Writes that are causally related must be seen by all the processes in the same order concurrent writes may be seen in a different order on different machines Processor consistency is related to causal consistency but with one more relaxation January 15 2019 COP 5611 Operating Systems 28 Memory Coherence cont Weak consistency Accesses to synchronization variables are sequentially consistent Before a synchronization access all previous regular data accesses must be completed Before a regular data access all previous synchronization accesses must be completed January 15 2019 COP 5611 Operating Systems 29 Memory Coherence cont January 15 2019 COP 5611 Operating Systems 30 Memory Coherence cont Release consistency Synchronization operations are broken down into acquire and release operations Before a read or write operation on shared data is performed all previous acquires done by the process must have completed successfully Before a release is allowed all previous reads and write
View Full Document
Unlocking...