Multiple Processor Systems
Chapter 8
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Multiple Processor Systems
Figure 8-1. (a) A shared-memory multiprocessor. (b) A message-
passing multicomputer. (c) A wide area distributed system
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Multiprocessor Hardware
Figure 8-2. Three bus-based multiprocessors. (a) Without caching.
(b) With caching. (c) With caching and private memories.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
UMA Multiprocessors Using
Crossbar Switches
Figure 8-3. (a) An 8 × 8 crossbar switch. (b) An open
crosspoint. (c) A closed crosspoint.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
UMA Multiprocessors Using
Multistage Switching Networks (1)
Figure 8-4. (a) A 2 × 2 switch with two input lines, A and B,
and two output lines, X and Y. (b) A message format.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
UMA Multiprocessors Using
Multistage Switching Networks (2)
Figure 8-5. An omega switching network.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
NUMA Multiprocessors (1)
Characteristics of NUMA machines which
distinguish them from other multiprocessors:
[Link] is a single address space visible to all
CPUs.
[Link] to remote memory is via LOAD and
STORE instructions.
[Link] to remote memory is slower than
access to local memory.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
NUMA Multiprocessors (2)
Figure 8-6. (a) A 256-node directory-based multiprocessor
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
NUMA Multiprocessors (3)
Figure 8-6. (b) Division of a 32-bit memory address into
fields. (c) The directory at node 36.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Multiprocessor Operating System Types
Each CPU Has Its Own Operating System
Figure 8-7. Partitioning multiprocessor memory among four CPUs,
but sharing a single copy of the operating system code. The boxes
marked Data are the operating system’s private data for each CPU.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Master-Slave Multiprocessors
Figure 8-8. A master-slave multiprocessor model.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Symmetric Multiprocessors
Figure 8-9. The SMP multiprocessor model.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Multiprocessor Synchronization (1)
Figure 8-10. The TSL instruction can fail if the bus cannot be locked.
These four steps show a sequence of events where the failure is
demonstrated.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Multiprocessor Synchronization (2)
Figure 8-11. Use of multiple locks to avoid cache thrashing.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Time Sharing
Figure 8-12. Using a single data structure for scheduling a
multiprocessor.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Space Sharing
Figure 8-13. A set of 32 CPUs split into four partitions,
with two CPUs available.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Gang Scheduling (1)
Figure 8-14. Communication between two threads belonging
to thread A that are running out of phase.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Gang Scheduling (2)
Gang scheduling has three parts:
[Link] of related threads are scheduled as a
unit, a gang.
[Link] members of a gang run at once on different
timeshared CPUs.
[Link] gang members start and end their time
slices together.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Gang Scheduling (3)
Figure 8-15. Gang scheduling.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Interconnection Technology (1)
Figure 8-16. Various interconnect topologies. (a) A single switch. (b)
A ring. (c) A grid. (d) A double torus. (e) A cube. (f) A 4D hypercube.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Interconnection Technology (2)
Figure 8-17. Store-and-forward packet switching.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Network Interfaces
Figure 8-18. Position of the network interface boards
in a multicomputer.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Blocking versus Nonblocking Calls (1)
Figure 8-19. (a) A blocking send call.
(b) A nonblocking send call.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Blocking versus Nonblocking Calls (2)
Choices on the sending side:
[Link] send (CPU idle during transmission).
[Link] send with copy (CPU time wasted
for the extra copy).
[Link] send with interrupt (makes
programming difficult).
[Link] on write (extra copy probably needed
eventually).
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Remote Procedure Call
Figure 8-20. Steps in making a remote procedure call.
The stubs are shaded gray.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Distributed Shared Memory (1)
Figure 8-21. Various layers where shared memory can be implemented. (a)
The hardware. (b) The operating system. (c) User-level software.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Distributed Shared Memory (2)
Figure 8-22. (a) Pages of the address space distributed
among four machines.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Distributed Shared Memory (3)
Figure 8-22. (b) Situation after CPU 1 references page 10 and
the page is moved there.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Distributed Shared Memory (4)
Figure 8-22. (c) Situation if page 10 is read only and
replication is used.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
False Sharing
Figure 8-23. False sharing of a page containing
two unrelated variables.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Graph-Theoretic Deterministic
Algorithm
Figure 8-24. Two ways of allocating nine
processes to three nodes.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Sender-Initiated Distributed
Heuristic Algorithm
Figure 8-25. (a) An overloaded node looking for a lightly loaded node
to hand off processes to. (b) An empty node looking for work to do.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Distributed Systems (1)
Figure 8-26. Comparison of three kinds of multiple CPU systems.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Distributed Systems (2)
Figure 8-27. Positioning of middleware in a distributed system.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Network Hardware
Ethernet
Figure 8-28. (a) Classic Ethernet. (b) Switched Ethernet.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
The Internet
Figure 8-29. A portion of the Internet.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Network Services
Figure 8-30. Six different types of network service.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Network Protocols
Figure 8-31. Accumulation of packet headers.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Document-Based Middleware (1)
Figure 8-32. The Web is a big directed graph of documents.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Document-Based Middleware (2)
For the browser to get the page
[Link]
[Link] asks DNS for IP address of [Link]
[Link] replies with [Link]
[Link] makes a TCP connection to port 80 on
[Link]
[Link] sends a request asking for the file
getting-started/[Link]
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Document-Based Middleware (3)
5. The [Link] server sends the file
getting-started/[Link]
6. Browser displays all the text in
getting-started/[Link].
7. Browser also fetches and displays all images on the
page
8. The TCP connection is released
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
File-System-Based Middleware
Transfer Model
Figure 8-33. (a) The upload/download model.
(b) The remote access model.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
The Directory Hierarchy
Figure 8-34. (a) Two file servers. The squares are directories
and the circles are files. (b) A system in which all clients have
the same view of the file system. (c) A system in which
different clients may have different views of the file system.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Naming Transparency
Common approaches to file and directory
naming in a distributed system:
[Link] + path naming, such as /machine/path
or machine:path.
[Link] remote file systems onto the local
file hierarchy.
3.A single name space that looks the same on all
machines.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Semantics of
File Sharing
Figure 8-35. (a) Sequential
consistency. (b) In a distributed
system with caching, reading a file
may return an obsolete value.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Object-Based Middleware
Figure 8-36. The main elements of a distributed system
based on CORBA. The CORBA parts are shown in gray.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Coordination-Based Middleware (1)
Figure 8-37. Three Linda tuples
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Coordination-Based Middleware (2)
A match occurs if the following three conditions
are all met:
[Link] and tuple have the same number of
fields.
[Link] of corresponding fields are equal.
[Link] constant or variable in the template
matches its tuple field.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
Publish/Subscribe
Figure 8-38. The publish/subscribe architecture.
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.
End
Chapter 8
Tanenbaum & Bos, Modern Operating Systems: 4th ed., Global Edition (c) 2015 Pearson Education Limited. All rights reserved.