Department of Computer Science, UMass Amherst Andrew H. Fagg

Announcements/Reminders

_ Exams are available upon request

_ Lab 3 proposal comments are back (look in~/lab3/GRADE.txt _le)

_ Lab 2 due tonight

_ HW 3 due Friday

_ Wednesday is the last day to drop (Check your EdLab email for possible

recommendations in this regard)

CMPSCI 377: Operating Systems Lecture 11, Page 1

Department of Computer Science, UMass Amherst Andrew H. Fagg

0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

0

0.5

1

1.5

2

2.5

3

3.5

4

4.5

5

Exam1

count

median = 0.72

mean = 0.70448

Standard deviation = 0.155

CMPSCI 377: Operating Systems Lecture 11, Page 2

Department of Computer Science, UMass Amherst Andrew H. Fagg

0.9 0.92 0.94 0.96 0.98 1

0

10

20

30

40

50

60

70

80

90

100

Lab 0

count median = 1

mean = 0.99873

CMPSCI 377: Operating Systems Lecture 11, Page 3

Department of Computer Science, UMass Amherst Andrew H. Fagg

0 0.2 0.4 0.6 0.8 1

0

5

10

15

20

25

30

35

40

Lab 1

count

median = 0.96

mean = 0.79105

CMPSCI 377: Operating Systems Lecture 11, Page 4

Department of Computer Science, UMass Amherst Andrew H. Fagg

0 0.5 1 1.5 2

0

5

10

15

HW 1+2

count

median = 1.6111

mean = 1.507

CMPSCI 377: Operating Systems Lecture 11, Page 5

Department of Computer Science, UMass Amherst Andrew H. Fagg

0 0.5 1 1.5 2

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

HW 1+2

EXAM

CORR = 0.48559

CMPSCI 377: Operating Systems Lecture 11, Page 6

Department of Computer Science, UMass Amherst Andrew H. Fagg

Distributed Programming with Events: The Poker Example

waiting

for

players

waiting

to

start

betting payout

player

1

player

2

player

N

player

player

dealing

request

start

player dropped

player dropped

done done

bet/fold/quit

bet/fold/quit

bet/fold/quit

CMPSCI 377: Operating Systems Lecture 11, Page 7

Department of Computer Science, UMass Amherst Andrew H. Fagg

Lab 3 Hints

_ RMI calls can return arbitrary objects (just as any method call can).

However, if the object is not of a primitive class, the class must

implement the 'Serializable' interface (just declare this in the class

de_nition and you are all set).

_ In many cases, your server will have to communicate information back to

the clients. There are at least two ways to do this:

{ Have the clients check continuously for new messages (see the

ReturnMessage example that we give for our poker player).

{ Make the main client object also extend the UnicastRemoteObject (but

you should not have to bind the client object to an RMI server).

_ Reminder: all work must be your own (the only exception is the example

code that we provide in the class).

CMPSCI 377: Operating Systems Lecture 11, Page 8

Department of Computer Science, UMass Amherst Andrew H. Fagg

Distributed Systems

_ Distributed system: a set of physically separate processors connected by

one or more communication links

Network

P3

P5

P4

P1 P2

_ Nearly all systems today are distributed in some way.

{ Email, _le servers, network printers, remote backup, world wide web

CMPSCI 377: Operating Systems Lecture 11, Page 9

Department of Computer Science, UMass Amherst Andrew H. Fagg

Parallel versus Distributed Systems

_ Tightly-coupled systems: \parallel processing"

{ Processors share clock, memory, and run one OS

{ Frequent communication

_ Loosely-coupled systems: \distributed computing"

{ Each processor has its own memory

{ Each processor runs an independent OS

{ Communication should be less frequent

CMPSCI 377: Operating Systems Lecture 11, Page 10

Department of Computer Science, UMass Amherst Andrew H. Fagg

Advantages of Distributed Systems

_ Resource sharing:

{ Resources need not be replicated at each processor (for example,

shared _les)

{ Expensive (scarce) resources can be shared (for example, printers)

{ Each processor can present the same environment to the user (for

example, by keeping _les on a _le server)

_ Computational speedup:

{ n processors potentially gives you n times the computational power

{ Problems must be decomposable into subproblems

{ Coordination and communication between cooperating processes

(synchronization, exchange of results) is needed.

CMPSCI 377: Operating Systems Lecture 11, Page 11

Department of Computer Science, UMass Amherst Andrew H. Fagg

Advantages of Distributed Systems

_ Reliability:

{ Replication of resources yields fault tolerance.

{ For example, if one node crashes, the user can work on another.

{ Performance will degrade, but system remains operational.

{ However, if some component of the system is centralized, a single

point of failure may result

{ Example: If an Edlab workstation crashes, you can use another

workstation. If the _le server crashes, none of the workstations are

useful.

_ Communication:

{ Users/processes on di_erent systems can communicate.

{ For example, mail, transaction processing systems like airlines, and

banks, WWW.

CMPSCI 377: Operating Systems Lecture 11, Page 12

Department of Computer Science, UMass Amherst Andrew H. Fagg

Distributed Operating Systems

_ Manages distributed resources

_ Looks to users like a centralized OS

{ Access remote resources as they do local ones

{ But, operate on multiple, independent processors

_ Provides transparency

{ Location

{ Data/process migration

{ Concurrency control

{ Replication

{ Parallelism

CMPSCI 377: Operating Systems Lecture 11, Page 13

Department of Computer Science, UMass Amherst Andrew H. Fagg

Distributed Systems

_ What do we need to consider when building these systems?

{ Communication and networks

{ Security

{ Reliability

{ Performance and scalability

{ Programming models

CMPSCI 377: Operating Systems Lecture 11, Page 14

Department of Computer Science, UMass Amherst Andrew H. Fagg

Networks

_ Networks are usually concerned with providing e_cient, correct, and

robust message passing between two separate nodes.

_ Local Area Network (LAN) usually connects nodes in a single building

and needs to be fast and reliable (for example, Ethernet).

{ Media: twisted-pair, coaxial cable, Cat5, _ber optics

{ Typical bandwidth: 10-100 Mb/s

_ Wide Area Network (WAN) connects nodes across the state, country,

or planet.

{ WANs are typically slower and less reliable than LAN (for example,

Internet).

{ Media: telephone lines (T1 service), microwave links, satellite channels

{ Typical bandwidth: 1.544 Mb/s (T1), 45 Mb/s (T3), 1Gb

(Internet-2)

CMPSCI 377: Operating Systems Lecture 11, Page 15

Department of Computer Science, UMass Amherst Andrew H. Fagg

Point-to-Point Network Topologies

Fully Connected

_ Fully connected: all nodes connected to all other nodes

{ Each message takes only a single \hop", i.e., goes directly to the

destination without going through any other node

{ Failure of any one node does not a_ect communication between other

nodes

{ Expensive, especially with lots of nodes, not practical for WANs

CMPSCI 377: Operating Systems Lecture 11, Page 16

Department of Computer Science, UMass Amherst Andrew H. Fagg

Point-to-Point Network Topologies

Partially Connected

_ Partially connected: links between some, but not all nodes

{ Less expensive, but less tolerant to failures. A single failure can

partition the network.

{ Sending a message to a node may have to go through several other

nodes )need routing algorithms.

{ WANs typically use this structure.

CMPSCI 377: Operating Systems Lecture 11, Page 17

Department of Computer Science, UMass Amherst Andrew H. Fagg

Point-to-Point Networks Topologies

Tree Structured

_ Tree structure: network hierarchy

{ All messages between direct descendants are fast, but messages

between \cousins" must go up to a common ancestor and then back

down.

{ Some corporate networks use this topology, since it matches a

hierarchical world view...

{ Not tolerant of failures. If any interior node fails, the network is

partitioned.

CMPSCI 377: Operating Systems Lecture 11, Page 18

Department of Computer Science, UMass Amherst Andrew H. Fagg

Point-to-Point Networks Topologies

Star

_ Star: - all nodes connect to a single centralized node

{ The central site is generally dedicated to network tra_c.

{ Each message takes only two hops.

{ If one piece of hardware fails, it can disconnect the entire network.

{ Inexpensive, and sometimes used for LANs

CMPSCI 377: Operating Systems Lecture 11, Page 19

Department of Computer Science, UMass Amherst Andrew H. Fagg

Ring Networks Topologies

Ring

_ One directional ring - nodes can only send in one direction.

{ Given n nodes, message may need to go n _ 1 hops.

{ Inexpensive, but one failure partitions the network.

_ Bi-directional ring - nodes can send in either direction.

{ With n nodes, a message needs to go at at most n=2 hops.

{ Inexpensive, tolerates a single failure by increasing message hops. Two

failures partition the network.

CMPSCI 377: Operating Systems Lecture 11, Page 20

Department of Computer Science, UMass Amherst Andrew H. Fagg

Ring Networks Topologies

_ Doubly connected ring nodes connected to neighbors and one away

neighbors

{ A message takes at most n=4 hops.

{ More expensive, but more tolerant of failures.

CMPSCI 377: Operating Systems Lecture 11, Page 21

Department of Computer Science, UMass Amherst Andrew H. Fagg

Bus Network Topologies

Linear Bus

Ring Bus

_ Bus - nodes connect to a common network

_ Linear bus - single shared link

{ Nodes connect directly to each other using multiaccess bus technology.

{ Inexpensive (linear in the number of nodes) and tolerant of node

failures.

{ Ethernet LAN use this structure.

_ Ring bus - single shared circular link

{ Same technology and trade-o_s as a linear bus.

CMPSCI 377: Operating Systems Lecture 11, Page 22

Department of Computer Science, UMass Amherst Andrew H. Fagg

Communication in Distributed Systems

_ Must be ultimately be able to address a machine and a process

{ Typically locate an address through a Domain Name Server (DNS)

_ Servers are distributed and hierarchical

_ A local server cache is used to speed the lookup process

_ Secondary, back-up servers are used in case of a crash

{ Locate a local address through a broadcast request

CMPSCI 377: Operating Systems Lecture 11, Page 23

Department of Computer Science, UMass Amherst Andrew H. Fagg

Routing Strategies

Sending Messages Through the Network

_ Routers: entity in the network responsible for moving messages between

physical connections

_ Routing table: representation of how a packet destined for a speci_c IP

address should be routed

{ Often static

{ ... But can be dynamic (especially in mobile networks)

_ Routing protocol: mechanism by which routing tables may be

automatically updated as the network topology changes

CMPSCI 377: Operating Systems Lecture 11, Page 24

Department of Computer Science, UMass Amherst Andrew H. Fagg

Connection Strategies

How are network resources recruited during a dialog between two

remotely-located processes?

_ Circuit switching

{ Telephone networks

{ Resources required along the entire path (bu_ers and bandwidth) are

reserved for the entire duration of the session

{ Guarantee transmission rate, but a potential waste of resources

CMPSCI 377: Operating Systems Lecture 11, Page 25

Department of Computer Science, UMass Amherst Andrew H. Fagg

Connection Strategies (cont)

_ Packet switching

{ Internet

{ Resources are not reserved, but instead are used on demand

{ Di_erent packets of the same session may take di_erent paths through

the network

{ Congestion control, but no guarantees of transmission rate

_ Message switching

{ ATM networks

{ An entire message is kept as a single packetized unit

CMPSCI 377: Operating Systems Lecture 11, Page 26

Department of Computer Science, UMass Amherst Andrew H. Fagg

Principles of Packet-Switched Network Communication

_ Data sent into the network is chopped into \packets", the network's basic

transmission unit.

_ Packets are sent through the network.

_ Computers at the switching points control the packet ow.

_ Analogy: cars/road/police - packets/network/computer

_ Shared resources can lead to contention (tra_c jams).

_ Analogy:

{ Shared node - Mullins Center

{ Shared link - bridge

CMPSCI 377: Operating Systems Lecture 11, Page 27

Department of Computer Science, UMass Amherst Andrew H. Fagg

Communication Protocols

_ Protocol: a set of rules for communication that are agreed to by all parties

_ Protocol stack : networking software is structured into layers

{ Each layer N, provides a service to layer N+1, by using its own layer N

procedures and the interface to the N-1 layer.

{ Example: International Standards Organization/ Open Systems

Interconnect (ISO/OSI)

Application

Presentation

Session

Transport

Network

Physical Physical

Application

Presentation

Session

Transport

Network

Physical

Network

connection

Virtual peer-to-peer

A B C

CMPSCI 377: Operating Systems Lecture 11, Page 28

Department of Computer Science, UMass Amherst Andrew H. Fagg

ISO Network Protocol Stack

_ Application layer: applications that use the net, e.g., mail, netscape,

X-services, ftp, telnet, provide a UI

_ Presentation layer: data format conversion, e.g., big/little endian

integer format)

_ Session layer: implements the communication strategy, such as RPC.

Provided by libraries.

CMPSCI 377: Operating Systems Lecture 11, Page 29

Department of Computer Science, UMass Amherst Andrew H. Fagg

ISO Network Protocol Stack (cont)

_ Transport layer: reliable end-to-end communication between any set of

nodes. Provided by OS.

_ Network layer: routing and congestion control. Usually implemented in

OS.

_ Data Link Control layer: reliable point-to-point communication of

packets over an unreliable channel. Sometimes implemented in hardware,

sometimes in software (PPP).

_ Physical layer: electrical/optical signaling across a \wire". Deals with

timing issues. Implemented in hardware.

CMPSCI 377: Operating Systems Lecture 11, Page 30

Department of Computer Science, UMass Amherst Andrew H. Fagg

TCP/IP Protocol Stack

remote terminal protocol, telnet

mail transfer protocol, SMTP

name server protocol, NSP

network management protocol, SNMP

WWW, http

file transfer protocol, FTP

layer 1-3

UDP TCP

User Application Process

IP

IEEE802.X/X.25

LAN/WAN

layers 5-7

layer 4

CMPSCI 377: Operating Systems Lecture 11, Page 31

Department of Computer Science, UMass Amherst Andrew H. Fagg

TCP/IP Protocol Stack (cont)

_ Most Internet sites use TCP/IP - Transmission Control Protocol/Internet

Protocol.

{ Has fewer layers than ISO to increase e_ciency.

{ Consists of a suite of protocols: UDP, TCP, IP...

{ TCP is a reliable protocol { packets are received in the order they are

sent

{ UDP (user datagram protocol) an unreliable protocol (no guarantee of

delivery).

CMPSCI 377: Operating Systems Lecture 11, Page 32

Department of Computer Science, UMass Amherst Andrew H. Fagg

Packet

_ Each message is chopped into packets.

{ Each packet contains all the information needed to recreate the original

message.

{ For example, packets may arrive out of order and the destination node

must be able to put them back into order.

{ Ethernet Packet Contents

data

preamble - start of packet

length of data section

frame checksum

start of frame delimiter

bytes

7

1

6

2

0-1500

4

0-46

fixed pattern so packet start is

recognizable

packet must be > 63 bytes long

{ The data segment of the packet contains headers for higher protocol

layers and actual application data

CMPSCI 377: Operating Systems Lecture 11, Page 33

Department of Computer Science, UMass Amherst Andrew H. Fagg

Summary

_ Virtually all computer systems contain distributed components

_ Networks hook them together

_ Networks make trade-o_s between speed, reliability, and expense

CMPSCI 377: Operating Systems Lecture 11, Page 34

Department of Computer Science, UMass Amherst Andrew H. Fagg

Next Time

_ Sockets and Remote Procedure Calls: Chapter 15

CMPSCI 377: Operating Systems Lecture 11, Page 35