Distributed Multimedia Systems

Objectives

To understand the motivation for preferring the shared memory programming model to message passing, but at the same time to appreciate its limitations. To understand the
concept of distributed shared memory, and in particular the page-based and higher-level middleware-based approaches to it. To appreciate the design and implementation issues associated with DSM. To be familiar with write-update and write-invalidation protocols. To understand Ivy’s use of write-invalidation to achieve sequential consistency. To appreciate the costs involved in implementing sequential consistency, and therefore the motivation for release consistency and other weaker forms.

Points to emphasize

The goal of porting programs written for shared memory multiprocessors to clusters of workstations or distributed memory multiprocessors, using the DSM abstraction, is not straightforward. The programmer needs to understand the operation of DSM, and may need to annotate or alter her program (for example, she may have to change the layout of data items).

The consistency model is a quite different concept to the programmer’s synchronization model; but the two are related in release consistency (and other hybrid forms of consistency).

Use of write-update vs. write-invalidate depends upon the sharing pattern between readers and writers. Apart from the protocol and the consistency semantics, avoidance of thrashing, choice of granularity and avoidance of false sharing are strong determinants of the efficiency of a DSM implementation.

Sequential consistency is expensive to implement. Weaker forms of consistency, which depend upon programmers’ use of synchronization objects, can be more efficiently implemented. But the correctness of the resultant executions is not to be taken for granted: it may depend on certain properties of the programs.

Possible difficulties

The distinction between synchronization model and consistency model takes some getting used to.

Students are liable to find difficult the notions of linearizability, sequential consistency and weaker forms of consistency.

The discussion of memory accesses that may or may not have `performed’ will seem obscure if it is not related to how protocols operate.

Teaching hints

Review the topic of mutual exclusion, as taught on undergraduate OS courses.

To implement (mutable) DSM is to replicate data with appropriate consistency semantics, and this is a problem that the students also meet in Chapter 14. Also Chapter 11’s study of multicast semantics should throw light on ways to implement the different consistency models.

If the students are familiar with mapped files, then appeal to shared mapped files is likely to make the problems concrete for them.

Encourage the students to find examples of executions on sequentially inconsistent and consistent memories. Use the R(x)a, W(y)b notation. Do the same for the other consistency models.