Transcript distributed systems

Introduction
Chapter 1
Chapter 1  Introduction
1
Examples of Distributed Systems

DNS

WWW

Cray T3E

Condor/RES
o Hierarchical distributed database
o Origin servers and web caches
o Distributed database
o 2048 tightly coupled homogeneous processors
o Distributed/parallel computing
o Loosely coupled heterogeneous workstations
o Parallel/distributed computing
Chapter 1  Introduction
2
Other Distributed Systems
 Email
 Electronic
banking
 Airline reservation system
 Peer-to-peer networks
 Etc., etc., etc.
Chapter 1  Introduction
3
Computer Revolution

Processing power
o 50 years ago, $100M for 1 instr/sec
o Today, $1K for 107 instructions/sec

Price/perform. improvement of 1012
o If cars had followed same path as computers…
o “…a Rolls Royce would now cost 1 dollar and get
a billion miles per gallon”
o And it would “explode once a year, killing
everyone inside”
Chapter 1  Introduction
4
Computer Revolution
 High
speed networks
o 30 years ago, networks were unknown
o Today, Gigabit networks and the
Internet
 Before
networks, centralized systems
 Today, distributed systems
o Computers in many locations work as one
Chapter 1  Introduction
5
What is a Distributed System?

According to your textbook
o “A collection of independent computers that
appears to its users as a single coherent
system”

Two parts to definition
o Hardware  machines are autonomous
o Software  machines appear as one system
• Implies that communication hidden from user
• Implies that organization hidden from user
Chapter 1  Introduction
6
What is a Distributed System?

According to dict.die.net
o A collection of (probably heterogeneous)
automata whose distribution is transparent to
the user so that the system appears as one
local machine
o This is in contrast to a network, where the
user is aware that there are several machines,
and their location, storage replication, load
balancing and functionality is not transparent

Crucial point is transparency
Chapter 1  Introduction
7
How to Implement a Dist. System?
A
distributed system is a collection
of independent computers…
 …that acts like a single system
 How to accomplish this?
 Middleware
o Make distributed system as transparent
as possible
Chapter 1  Introduction
8
Role of Middleware
Distributed system as middleware
 Middleware extends over multiple machines

Chapter 1  Introduction
9
Goals
 For
a distributed system to be
worthwhile authors believe it should
o
o
o
o
Easily connect users to resources
Hide fact that resources are distributed
Be open
Be scalable
 First
2 of these about transparency
 Transparent, open, scalable
Chapter 1  Introduction
10
Transparency
Transparency
Description
Access
Hide different data representations, how resources accessed
Location
Hide where a resource is located
Migration
Hide that a resource may move to another location
Relocation
Hide that a resource may be moved while in use
Replication
Hide that a resource is replicated
Concurrency
Hide that a resource may be shared by several users
Failure
Hide failure and recovery of a resource
Persistence
Hide whether a (software) resource is in memory or on disk
Transparent system “acts” like one computer
 Various aspects of transparency listed above

Chapter 1  Introduction
11
Degree of Transparency
 Cannot
hide physical limitations
o Time it takes to send packet
 May
be a tradeoff between
transparency and performance
o What to do if Web request times out?
o Keeping replicated data current
Chapter 1  Introduction
12
Openness
 Open
== standards-based
 Provides
o Interoperability
o Portability
 Ideally,
flexible, i.e., extensible
 But many useful systems follow the
“American standard”
o Do whatever you want
Chapter 1  Introduction
13
Scalability

Concept
Example
Centralized services
A single server for all users
Centralized data
A single on-line telephone book
Centralized algorithms
Doing routing based on complete information
Scalability issues/limitations
Chapter 1  Introduction
14
Scalability
 Authors
believe centralized is bad
o Centralized server is source of
congestion, single point of failure
o Centralized data leads to congestion,
lots of traffic
o Centralized algorithm must collect all
info and process it (e.g., routing algs)
 Google?
Napster?
Chapter 1  Introduction
15
Scalability
 Decentralized
algorithms
o No machine has complete system state
o Decisions based on local info
o Failure of one machine does not kill
entire algorithm
o No assumption of global clock
 Examples?
Chapter 1  Introduction
16
Geographic Scalability
 Big
difference between LAN and WAN
 LANs have synchronous communication
o Client can “block” until server responds
 On
LAN, global time may be possible
(to within a few milliseconds)
 WAN unreliable, point-to-point
 WAN has different admin domains
o A security nightmare
Chapter 1  Introduction
17
Scaling Techniques
 Scaling
problems due to limited
capacity of networks and servers
 Three possible solutions
o Hide latencies  do something useful
while waiting (asynchronous comm.)
o Distribution  DNS, for example
o Replication  allows for load balancing
 Replication
Chapter 1  Introduction
creates consistency issues
18
Scaling Techniques
Server or client check form as it’s filled out?
 Having client do more, as in (b), may reduce
latency (but may cause security problems)

Chapter 1  Introduction
19
Scaling Techniques
DNS name space divided into zones
 Goto server in Z1 to find server Z2 and so on
 Like a binary search for correct server

Chapter 1  Introduction
20
Hardware Issues
 For
our purposes, 2 kinds of machines
 Multiprocessor
o Different processors share same memory
 Multicomputer
o Each processor has it’s own memory
 Each
of these could use either bus or
switched architecture
Chapter 1  Introduction
21
Hardware Issues
multiprocessor
Chapter 1  Introduction
multicomputer
22
Multiprocessors
A bus-based multiprocessor
 Cache coherence is an issue

Chapter 1  Introduction
23
Multiprocessors
a)
b)
A crossbar switch
Omega switching network
Chapter 1  Introduction
24
Homogeneous Multicomputer
Grid
Chapter 1  Introduction
Hypercube
25
Software Concepts
System
Description
Main Goal
DOS
Tightly-coupled operating system for multiprocessors and homogeneous
multicomputers
Hide and manage
hardware
resources
NOS
Loosely-coupled operating system for
heterogeneous multicomputers (LAN and
WAN)
Offer local
services to remote
clients
Middleware
Additional layer atop of NOS implementing
general-purpose services
Provide
distribution
transparency



DOS  Distributed Operating Systems
NOS  Network Operating Systems
Middleware  self-explanatory
Chapter 1  Introduction
26
Uniprocessor OSs

Separate apps from OS code via microkernel
Chapter 1  Introduction
27
Multiprocessor OSs
monitor Counter {
private:
int count = 0;
public:
int value() { return count;}
void incr () { count = count + 1;}
void decr() { count = count – 1;}
}

Hoe to protect count from concurrent access?
Chapter 1  Introduction
28
Multiprocessor OSs
monitor Counter {
void decr() {
private:
if (count ==0) {
int count = 0;
blocked_procs = blocked_procs + 1;
int blocked_procs = 0;
wait (unblocked);
condition unblocked;
blocked_procs = blocked_procs – 1;
public:
}
int value () { return count;}
else
void incr () {
count = count – 1;
if (blocked_procs == 0)
}
count = count + 1;
else
signal (unblocked);
}
}

Protect count from
concurrent access
o Using blocking
Chapter 1  Introduction
29
Multicomputer OSs

Multicomputer OS
Chapter 1  Introduction
30
Multicomputer OSs

???
Chapter 1  Introduction
31
Multicomputer OSs
Synchronization point
Send buffer
Reliable comm.
guaranteed?
Block sender until buffer not full
Yes
Not necessary
Block sender until message sent
No
Not necessary
Block sender until message received
No
Necessary
Block sender until message delivered
No
Necessary

Huh?
Chapter 1  Introduction
32
Programming Issues
 Programming
multicomputers much
harder than multiprocessors
 Why?
o Message passing
o Buffering, blocking, reliable comm., etc.
 One
option is to emulate shared
memory on multicomputer
o Large “virtual” address space
Chapter 1  Introduction
33
Distributed Shared Memory
a)
b)
c)
Pages of address
space distributed
among 4 machines
After CPU 1
references pg 10
If page 10 read
only and
replication used
Chapter 1  Introduction
34
Distributed Shared Memory

False sharing of page between two processes
o Two independent processors share same page
Chapter 1  Introduction
35
Network OS

Network OS
o Each processor has its own OS
Chapter 1  Introduction
36
Network OS
Clients and server in a network OS
 Global shared file system

Chapter 1  Introduction
37
Distributed System
 Distributed
OS not a distributed
system by our definition
 Network OS not a distributed system
by our definition
 What we need is middleware…
Chapter 1  Introduction
38
Positioning Middleware

A distributed system as middleware
o Individual node managed by local OS
o Middleware hides heterogeneity of underlying systems
Chapter 1  Introduction
39
Middleware and Openness


Open middleware-based system
Middleware layer should
o Use the same protocols
o Provide same interfaces to apps
Chapter 1  Introduction
40
Comparison of Systems
Item
Distributed OS
Network OS
Middlewarebased OS
Multiproc.
Multicomp.
Degree of transparency
Very High
High
Low
High
Same OS on all nodes
Yes
Yes
No
No
Number of copies of OS
1
N
N
N
Basis for communication
Shared
memory
Messages
Files
Model specific
Resource management
Global,
central
Global,
distributed
Per node
Per node
Scalability
No
Moderately
Yes
Varies
Openness
Closed
Closed
Open
Open

Middleware rocks!
Chapter 1  Introduction
41
Middleware Services

Main goal is access transparency
o Hides low level message passing

Naming
o Like yellow pages or URL

Persistence
o For example, a distributed file system

Distributed transactions
o Read and writes are atomic

Security
Chapter 1  Introduction
42
Client Server Model
 Read
this section
Chapter 1  Introduction
43
Clients and Servers
 Interaction
Chapter 1  Introduction
between client and server
44
Example Client and Server

header.h
o Used by client
o And by server
Chapter 1  Introduction
45
Example Client and Server

A sample server
Chapter 1  Introduction
46
Example Client and Server
 Client
using server to copy a file
Chapter 1  Introduction
47
Processing Level
 Internet
search engine as 3 layers
Chapter 1  Introduction
48
Multitiered Architectures
 Alternative
client-server organizations
Chapter 1  Introduction
49
Multitiered Architectures
A
server acting as client
Chapter 1  Introduction
50
Modern Architectures
 Horizontal
distribution of Web service
Chapter 1  Introduction
51
Summary

Distributed system
o Autonomous computers that operate together
as a single coherent system

Potential advantages
o Can integrate homogeneous systems
o Scales well, if properly designed

Potential disadvantages
o Complexity
o Degraded performance
o Poorer security
Chapter 1  Introduction
52
Summary
 Different
types of dist systems
 Distributed OS
o For tightly coupled system
o Can’t integrate different systems
 Network
OS
o For heterogeneous system
o No single system view
Chapter 1  Introduction
53
Summary
 Middleware
systems based on
o Remote procedure calls
o Distributed objects, files, documents
o Vertical organization
o Horizontal organization
Chapter 1  Introduction
54