Transcript Introduction - Wichita State University

Introduction
Chapter 1
Definition of a Distributed System (1)
A distributed system is:
A collection of independent
computers that appears to its
users as a single coherent
system.
Definition of a Distributed System (2)
1.1
A distributed system organized as middleware.
Note that the middleware layer extends over multiple machines.
Goals of a Distributed System
• Accessibility: A distributed system should easily
connect users to resources.
– Groupware is software for collaborative editing,
teleconferencing, and so on.
• Transparency: It should hide the fact that
resources are distributed across a network.
• Openness: It should be open.
– An open distributed system is a system that offers
services according to standard rules that describe the
syntax and semantics of those services.
• Scalability: It should be scalable.
Transparency in a Distributed System
Transparency
Description
Access
Hide differences in data representation and how a
resource is 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 to another
location while in use
Replication
Hide that a resource may be shared by several
competitive users
Concurrency
Hide that a resource may be shared by several
competitive users
Failure
Hide the failure and recovery of a resource
Persistence
Hide whether a (software) resource is in memory or
on disk
Different forms of transparency in a distributed system.
Openness Problems
• In distributed systems, services are generally specified
through interfaces, which are described in an Interface
Definition Language (IDL).
• Interoperability characterizes the extent by which two
implementations of systems or components from different
manufactures can co-exist and work together by merely
relying on each other’s services as specified by a common
standard.
– Example: Mobile phones
• Portability characterizes to what extent an application
developed for a distributed system A can be executed, without
modification, on a different system B that implements the
same interface as A.
– Example: Java
• Flexibility means that it should be easy to configure the
system out of different components possibly from different
developers.
Scalability Problems
• Scalability of a system can be measured in
three dimensions:
– Size
– Geographically scalable
– Administratively scalable
Scalability Problems
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
Examples of scalability limitations.
Scalability Problems
• Decentralized algorithms have the following
characteristics:
– No machine has complete information about the system
state.
– Machines make decisions based only on local
information.
– Failure of one machine does not ruin the algorithm.
– There is no implicit assumption that a global clock exists.
• There are basically three techniques for scaling:
hiding communication latencies, distribution, and
replication.
Scaling Techniques (1)
1.4
The difference between letting (reduce the server workload):
a)
a server or
b) a client check forms as they are being filled
•
Example: Java applets
Scaling Techniques (2)
1.5
An example of dividing the DNS name space into zones.
Hardware Concepts
• Computers that have shared memory are called
multiprocessors.
• Computers that do not have shared memory are called
multicomputers.
• Two types of interconnection network are used: bus and
switched.
• In multicomputers, a further distinction can be made between
homogeneous and heterogeneous systems.
• Examples of switched homogenous multicomputers:
– Massively Parallel Processors (MPPs) are huge, multimillion dollar
supercomputers consisting of thousands of CPUs.
– Clusters of Workstations (COWs) are basically a collection of
standard PCs connected through off-the-shelf communication
components such as Myrinet boards.
• Heterogenous multicomputers need distributed system as a
software layer.
Hardware Concepts
1.6
Different basic organizations and memories in distributed
computer systems: multiprocessors vs. multicomputers
Multiprocessors (bus-based)
1.7
A bus-based multiprocessor.
• The problem: More CPUs will overload the bus.
• The solution is to add a high-speed cache.
– It causes the incoherent memory.
• Limited scalability.
Multiprocessors (Switch-based)
1.8
a) A crossbar switch
b) An omega switching network
Homogeneous Multicomputer Systems
1-9
a) Grid
b) Hypercube
Software Concepts
• Operating systems for distributed systems:
– Act as resource managers.
– Hide the intricacies and heterogeneous nature of the
underlying hardware.
• Operating systems for distributed computers can be
divided into two categories:
– In tightly-coupled systems, the operating system tries to
maintain a single, global view of the resources (e.g.
Distributed Operating System - DOS).
– Loosely-coupled systems can be thought of as a collection
of computers to make their own services and resources
available to the others (e.g. Network Operating System NOS).
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
An overview between
• DOS (Distributed Operating Systems)
• NOS (Network Operating Systems)
• Middleware
Uniprocessor Operating Systems
• The operating system is a virtual machine offering
multitasking facilities to applications.
– Applications are protected from each other.
• Two modes of operation
– In kernel mode, all instructions are permitted to be executed, and the
whole memory and all registers are accessible.
– In user mode, memory and register access is restricted.
• Having all operating system code to be executed in kernel
mode results in a monolithic operating system that is not a
good idea from the perspective of openness, software
engineering, reliability, or maintainability.
• A flexible approach is to have a module for managing
devices executed in user mode and a microkernel containing
the code for hardware access.
– Advantages: flexibility
– Disadvantages: different from the current operating system and extra
communication.
Uniprocessor Operating Systems
1.11
Separating applications from operating system code
through a microkernel.
Multiprocessor Operating Systems
• Multiprocessor Operating Systems aim to support high
performance through multiple CPUs.
• Protection against simultaneous data access is done through
synchronization primitives: semaphores and monitors.
• A semaphore can be thought of as an integer with two
operations, down (wait) and up (signal).
down (S):
while S 0 do no-op;
S--;
up (S):
S++;
• Semaphore operations need to be atomic (once it starts, no
other process can access it.)
Multiprocessor Operating Systems
• The use of semaphores can easily lead to
unstructed code.
• A monitor is a programming-language
construct.
– A monitor is an object that allows only a single
process at a time to execute a procedure.
– A monitor can block a process based on condition
variables.
– Condition variables are special variables with two
operations wait and signal.
Multiprocessor Operating Systems (1)
monitor Counter {
private:
int count = 0;
public:
int value() { return count;}
void incr () { count = count + 1;}
void decr() { count = count – 1;}
}
A monitor to protect an integer against concurrent access.
Multiprocessor Operating Systems (2)
monitor Counter {
private:
int count = 0;
void decr() {
if (count ==0) {
int blocked_procs = 0;
blocked_procs = blocked_procs + 1;
condition unblocked;
wait (unblocked);
public:
blocked_procs = blocked_procs – 1;
int value () { return count;}
}
void incr () {
else
if (blocked_procs == 0)
count = count + 1;
else
count = count – 1;
}
}
signal (unblocked);
}
A monitor to protect an integer against concurrent access, but
blocking a process.
Multicomputer Operating Systems
• Communication for multicomputer operating
systems is through message passing.
• Each node has its own kernel containing
separate modules for managing local
resources and interprocessor communication.
Multicomputer Operating Systems (1)
1.14
General structure of a multicomputer operating system
Multicomputer Operating Systems (2)
1.15
Alternatives for blocking and buffering in message passing.
Multicomputer Operating Systems (3)
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
Relation between blocking, buffering, and reliable communications.
Distributed Shared Memory Systems
• The goal is to provide a virtual shared memory
machine, running on a multicomputer, for which
applications can be written using the shared memory
model even though this is not present.
• A pagebased distributed shared memory (DSM) is to
use the virtual memory capabilities of each
individual node to support a large virtual address
space.
• Having data belonging to two independent processes
in the same page is called false sharing.
– If a page contains data of two independent processes on
different processors, the operating system may need to
repeatedly transfer the page between those two
processors.
Distributed Shared Memory Systems (1)
a)
b)
c)
Pages of address
space distributed
among four
machines
Situation after
CPU 1 references
page 10
Situation if page
10 is read only
and replication is
used
Distributed Shared Memory Systems (2)
1.18
False sharing of a page between two independent processes.
Network Operating System
• In network operating system, the machines and their
operating systems may be different, but they are all
connected to each other in a computer network.
• Services available in NOS are:
– Remote login: rlogin
– Remote copy: rcp machine1:file1 machine2:file2
• File servers are used to provide a shared, global file
system.
• Different clients can have different a view of the file
system based on different file mounting.
Network Operating System (1)
1-19
General structure of a network operating system.
Network Operating System (2)
1-20
Two clients and a server in a network operating system.
Network Operating System (3)
1.21
Different clients may mount the servers in different places.
Middleware
• Middleware is an additional layer of software that is
used in network operating systems to more or less
hide the heterogeneity of the collection of
underlying platforms but also to improve
distribution transparency.
• Middleware models:
– File: Everything is treated as a file.
– Distributed file systems: Only traditional files are
concerned.
– Remote Procedure Calls (RPCs): A process can call a
procedure located on a remote machine like a local call.
– Distributed objects: Objects are invoked through the
interface.
– Distributed documents: Information is orgainzed into
documents (WWW).
Positioning Middleware
1-22
General structure of a distributed system as middleware.
Middleware
• Middleware services:
–
–
–
–
–
Communication facilities
Naming
Persistence storage
Distributed transactions
Security
• Middleware interoperability can be only
achieved by the same protocols and
interfaces.
Middleware and Openness
1.23
In an open middleware-based distributed system, the protocols
used by each middleware layer should be the same, as well as
the interfaces they offer to applications.
Comparison between Systems
Item
Distributed OS
Network
OS
Middlewarebased OS
Multiproc.
Multicomp.
Very High
High
Low
High
Yes
Yes
No
No
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
Degree of transparency
Same OS on all nodes
Number of copies of OS
A comparison between multiprocessor operating systems,
multicomputer operating systems, network operating
systems, and middleware based distributed systems.
The Client-Server Model
• In the basic client-server model, processes are
divided into two groups:
– A server is a process implementing a specific service.
– A client is a process that requests a service from a server.
• The client-server interaction is known as requestreply behavior.
• Communication between a client and a server can be
implemented by means of a simple connectionless
protocol based on the hypothesis that the underlying
network is reliable.
• Many client-server systems use a reliable
connection-oriented protocol.
Clients and Servers
1.25
General interaction between a client and a server.
An Example Client and Server (1)
The header.h file used by the client and server.
An Example Client and Server (2)
A sample server.
An Example Client and Server (3)
1-27 b
A client using the server to copy a file.
Layering Client-Server Model
• Client-server applications can be made distinct
among the following three levels:
– The user-interface level: the programs that allow end
users to interact with applications.
– The processing level: the core functions of applications.
– The data level: the programs that maintain the actual data.
Processing Level
1-28
The general organization of an Internet search engine into
three different layers
Client-Server Architectures
• Multitiered Architecture is to distribute the programs
in the application layers across different machines.
– Two-tieried architecture distribute programs to two kinds
of machines: clients and servers.
– Three-tired architecture divides applications into a userinterface, process components, and a data level.
– This type of distribution is referred as vertical
distribution.
Multitiered Architectures (1)
1-29
Alternative client-server organizations (a) – (e).
Multitiered Architectures (2)
1-30
An example of a server acting as a client.
Client-Server Architectures
• In horizontal distribution, multiple clients or servers,
each of which has its own data set, work together to
share the load.
– Example: Multiple Web servers
• For simple collaborative applications, there could be
no server but only peer-to-peer distribution.
Modern Architectures
1-31
An example of horizontal distribution of a Web service.