CIS506 Advanced Operation Systems

<< back to courseware demo page - This online lecture is for demonstration purposes

This lecture will cover an introduction to distributed systems. The menu to the right provides links to the major topics of the lecture. You may also scroll down to begin reading the lecture material.

Lecture Menu

Learning objectives

Preliminaries

What is a distributed system?

Advantages and disadvantages of distributed systems

Summary and Sample Test

 
 

After completing this lecture you should:

• understand the basic ideas of distributed systems
• know the difference between multiprocessors and multicomputers
• be able to distinguish between network operating systems and distributed operating systems

Two developments make computer systems of a large number of CPUs feasible:

• powerful microprocessors
• high speed computer networks
• local area networks (LANs)
• wide area networks (WANs)

• in contrast with centralized (single processor) systems.

Distributed systems offer the promise of increased computational power, but:

• there is not much software for distributed systems.

No completely satisfactory definition has been given for a distributed system, but the following can be used as a loose guide:

• A distributed system is a collection of independent computers that appears to the users of the system as a single computer. 

• A bank with many branch offices, each branch having a local computer which can connect to all the other branch computers and a central computer.
• If transactions can be carried out without regard to account location, this counts as a distributed system.

Advantages of distributed systems over centralized systems

• Distributed systems offer a better price/performance ratio than centralized computers.
• A distributed system may have more computing power than a centralized mainframe or supercomputer.
• Some applications are naturally distributed
• like the branch banking example above.
• Potential increased reliability:
• one machine crashing may still allow the system as a whole to continue functioning.
• Computing power may be added a little at a time:
• one or several new machines added may give sufficient improvement.

Advantages of distributed systems over independent PCs

• Users can have shared access to a database.
• Users can share printers, scanners and other peripherals.
• Communication, e.g. email, is facilitated.
• The workload may be spread over many machines.

• Software shortage
• Network problems, e.g. saturation
• Security
• Ease of data sharing makes protection harder

Flynn (1972) proposed a simple classification for (possibly) multiple CPU computers.  It has become widely known.
 

Flynn's taxonomy 

• SISD: single instruction stream; single data stream
• includes all traditional uniprocessors, PCs to mainframes
• SIMD: single instruction stream; multiple data stream
• array processors that execute one instruction on many data in parallel
• MISD: multiple instruction stream; single data stream 
• no known examples
• MIMD: multiple instruction stream; multiple data stream 
• includes all distributed systems

MIMD machines can be further classified into multiprocessors and multicomputers.

• multiprocessors have a
• shared global memory
• are tightly coupled (message passing at near CPU speed)
• multicomputers have
• no shared memory
• are loosely coupled (message passing at low speed compared to CPU)

Multiprocessors and multicomputers may use either bus based or switched interconnection networks.
 
 

Bus based multiprocessors have:

• independent CPUs connected by a high speed system bus with a global memory.
• Each CPU usually has a cache to improve performance.
• There is a limit of about 64 CPUs because of bus saturation.

Switched multiprocessors 

• Large switching networks to support many CPUs are expensive and may be slow.
• NUMA (non uniform memory access) systems reduce the cost:
• there is a small local memory for each CPU
• accessing another CPU's memory is allowed but is slower than accessing local memory.
• complex algorithms are needed for good software placement.

Generally a tightly coupled shared memory multiprocessor with a large number of CPUs is expensive and difficult to build.
 

Bus based multicomputers:

• are easy to build,
• consist of independent computers with local memory connected by a LAN or other bus topology network,
• have no global memory.

Switched multicomputers 

• Grid 
• rectangular array of CPUs with connections only to neighbors
• messages from one corner to the opposite corner in an n by n grid require (n-1)+(n-1) hops
• Hypercube
• an n-dimensional cube with CPUs at the vertices
• there are 2ⁿ CPUs
• messages from one CPU to a CPU most distant from it require n hops (= log2(number of CPUs))

Software for distributed and parallel systems

Network operating systems

• loosely coupled software on loosely coupled hardware
• usually workstations and file servers on a LAN
• each machine autonomous

True distributed systems 

• tightly coupled software on loosely coupled hardware
• appear to users to be a single computer
• single-system image
• virtual uniprocessor
• same kernel runs on each machine

Multiprocessor timesharing systems 

• tightly coupled software on tightly coupled hardware
• single run queue in shared memory
• traditional file system

SUMMARY: 

Distributed systems are:

• a collection of CPUs that cooperate to make the system resemble a single computer

Hardware for multiple CPU systems:

• multiprocessors
• shared memory
• bus-based or switched
• multicomputers
• no shared memory
• bus-based or switched

• Network operating systems
• independent workstations with shared file system
• Distributed operating systems
• single-system image
• Shared memory multiprocessor systems
• not true distributed systems

9. 14

10. 6