Credits:4

Notes by Pritee Parwekar,ANITS 27-Nov-16 1

 Understand the Distributed Systems and the
challenges involved in Design of the Distributed
Systems.
 Understand how communication is created and
synchronized in Distributed systems
 Design and Implement Distributed applications
using Technologies like RPC, threads.
 Learn how to store data in Distributed File
System.
 Understand How Distributed Shared Memory is
managed.

Notes by Pritee Parwekar,ANITS 27-Nov-16 2

 Introduction to Distributed Systems, What is a Distributed System?, Hard ware
concepts, Software concepts, Design issues.

 Communication in Distributed Systems, Lay red Protocols, ATM networks, The

Client – sever model, Remote Procedure call, Group communication.

 Synchronization in Distributed System, Clock Synchronization, Mutual Exclusion,

Election algorithms, Atomic transactions, Deadlocks in Distributed Systems.

 Process and processors in Distributed System threads, System Models, Processors

allocation, Scheduling in Distributed System, Fault tolerance, Real time Distributed
System.

 Distributed File Systems, Distributed File System Design, Distributed File System
implementation, Trends in Distributed File System.

 Distributed Shared Memory, Introduction, What is Shared memory?, Consistency

models, Page based Distributed Shared memory, Shared – variable Distributed
Shared memory, Object based Distributed Shared Memory.

Notes by Pritee Parwekar,ANITS 27-Nov-16 3

TEXT BOOK:
 Distributed Operating Systems, Andrew S.
Tanenbanm

REFERENCE BOOK:
 Advanced Concepts in Operating Systems,
Makes Singhal and Niranjan G.Shivaratna.

Notes by Pritee Parwekar,ANITS 27-Nov-16 4

 To understand the function of Operating
Systems (OS) and what are the types of
operating systems.

 To make the students learn about the

concept of Distributed Operating Systems
(DOS).

Notes by Pritee Parwekar,ANITS 27-Nov-16 5

By end of this lecture, the students would know the following:-

 What are operating systems?

 What are the functions of operating systems?

 Types and operating systems

 Functions of operating systems

 Introduction to distributed operating systems

 Difference between distributed and network operating systems

 Examples of operating systems

Notes by Pritee Parwekar,ANITS 27-Nov-16 6

Notes by Pritee Parwekar,ANITS 27-Nov-16 7
Notes by Pritee Parwekar,ANITS 27-Nov-16 8
 Batch Operating Systems

 Timesharing Operating Systems

 Real Time Systems

 Network Operating Systems (NOS)

 Distributed Operating Systems (DOS)

Notes by Pritee Parwekar,ANITS 27-Nov-16 9

Notes by Pritee Parwekar,ANITS 27-Nov-16 10
 The users of a batch operating system do not
interact with the computer directly.
 Each user prepares his job on an off-line device
like punch cards and submits it to the computer
operator.
 To speed up processing, jobs with similar needs
are batched together and run as a group.
 The programmers leave their programs with the
operator and the operator then sorts the
programs with similar requirements into batches.

Notes by Pritee Parwekar,ANITS 27-Nov-16 11

Notes by Pritee Parwekar,ANITS 27-Nov-16 12
 Time-sharing is a technique which enables
many people, located at various terminals, to
use a particular computer system at the same
time.
 Time-sharing or multitasking is a logical
extension of multiprogramming.
 Processor's time which is shared among
multiple users simultaneously is termed as
time-sharing.

Notes by Pritee Parwekar,ANITS 27-Nov-16 13

 A real-time system is defined as a data
processing system in which the time interval
required to process and respond to inputs is
so small that it controls the environment.

 The time taken by the system to respond to

an input and display of required updated
information is termed as the response time.
So in this method, the response time is very
less

Notes by Pritee Parwekar,ANITS 27-Nov-16 14

 Hard real-time systems guarantee that critical
tasks complete on time.

 In hard real-time systems, secondary storage

is limited or missing and the data is stored in
ROM. In these systems, virtual memory is
almost never found.

Notes by Pritee Parwekar,ANITS 27-Nov-16 15

Extremely Fast
Reaction Time

Notes by Pritee Parwekar,ANITS 27-Nov-16 16

 Soft real-time systems are less restrictive. A
critical real-time task gets priority over other
tasks and retains the priority until it
completes.
 Soft real-time systems have limited utility
than hard real-time systems.
 For example, multimedia, virtual reality,
Advanced Scientific Projects like undersea
exploration and planetary rovers, etc.

Notes by Pritee Parwekar,ANITS 27-Nov-16 17

Multimedia / Sending &
Receiving Packets

Notes by Pritee Parwekar,ANITS 27-Nov-16 18

 A Network Operating System runs on a server
and provides the server the capability to
manage data, users, groups, security,
applications, and other networking functions.

 The primary purpose of the network

operating system is to allow shared file and
printer access among multiple computers in a
network, typically a local area network (LAN),
a private network or to other networks.

Notes by Pritee Parwekar,ANITS 27-Nov-16 19

Notes by Pritee Parwekar,ANITS 27-Nov-16 20
 Centralized servers are highly stable.

 Security is server managed.

 Upgrades to new technologies and hardware

can be easily integrated into the system.

 Remote access to servers is possible from

different locations and types of systems.

Notes by Pritee Parwekar,ANITS 27-Nov-16 21

 High cost of buying and running a server.

 Dependency on a central location for most

operations.

 Regular maintenance and updates are

required.

Notes by Pritee Parwekar,ANITS 27-Nov-16 22

 Distributed Operating System is a model where
distributed applications are running on multiple
computers linked by communications.

 Distributed system is a collection of independent

computers that appear to the user of the system
as a single computer.

 A distributed operating system is an extension of

the network operating system that supports
higher levels of communication and integration
of the machines on the network.

Notes by Pritee Parwekar,ANITS 27-Nov-16 23

Notes by Pritee Parwekar,ANITS 27-Nov-16 24
 Network Operating Systems :- Contains N copies of
Operating Systems, communication between
machines is via shared files.

 Distributed OS : - Contains N copies of Operating

systems, communication between nodes is via
messages over a network. These messages pass
the necessary parameters for the task and on
completion messages return the results. Its as if
computers sends emails to other computers with
request and answer.

Notes by Pritee Parwekar,ANITS 27-Nov-16 25

Notes by Pritee Parwekar,ANITS 27-Nov-16 26
 Give more performance than single system

 If one pc in distributed system malfunction or

corrupts then other node or pc will take care
of More resources can be added easily.

 Resources like printers can be shared on

multiple pc’s

Notes by Pritee Parwekar,ANITS 27-Nov-16 27

Item Description
Economics Microprocessors offer a better
price/performance than
mainframes
Speed A distributed system may have
more total computing power than
a mainframe
Inherent Distribution Some applications involve spatially
separated machines
Reliability If one machine crashes, the system
as a whole can still survive
Incrementatl Growth Computing power can be added in
small increment

Notes by Pritee Parwekar,ANITS 27-Nov-16 28

Item Description
Data Sharing Allow many users access to a
common data base
Device Sharing Allow many users to share
expensive peripherals like color
printers
Communication Make human-to-human
communication easier, for
example, by electronic mail
Flexibility Spread the workload over the
available machines in the most
effective way

Notes by Pritee Parwekar,ANITS 27-Nov-16 29

 Security problem due to sharing, easy access also
applies to secret data

 Some messages can be lost in the network system.

 Bandwidth is another problem if there is large data

then all network wires to be replaced which tends to
become expensive

 Software : Little software exists at present for

distributed systems

 Networking : Network can saturate or cause other

problems

Notes by Pritee Parwekar,ANITS 27-Nov-16 30

In this lecture we have learnt

 What are operating systems?

 What are the functions of operating systems?

 Types and operating systems

 Functions of operating systems

 Introduction to distributed operating systems

 Difference between distributed and network operating systems

 Examples of operating systems

Notes by Pritee Parwekar,ANITS 27-Nov-16 31

Notes by Pritee Parwekar,ANITS 27-Nov-16 32
 To understand the hardware and software
concepts of distributed operating concepts

 To understand the design issues comes with

hardware and software concepts

Notes by Pritee Parwekar,ANITS 27-Nov-16 33

By end of this lecture, the students would know the following:-

 What is the term multiprocessor?

 What is the term multicomputer?

 Flynn’s Classification

 How multiple processors are connected ?

 How multiple processors communicate ?

 What are the hardware and software concepts ?

 Design issues involved

Notes by Pritee Parwekar,ANITS 27-Nov-16 34

 .
 All Distributed Systems consist of multiple
CPUs and there are different ways of
interconnecting them and how they
communicate

Notes by Pritee Parwekar,ANITS 27-Nov-16 35

 SISD
 MISD
 MISD
 MIMD

Notes by Pritee Parwekar,ANITS 27-Nov-16 36

 MIMD (Multiple-Instruction Multiple-Data)

 MIMD can be split into two classifications

 Multiprocessors - CPUs share a common
memory
 Multicomputers - CPUs have separate
memories

Notes by Pritee Parwekar,ANITS 27-Nov-16 37

 Tightly-coupled - short delay in
communication between computers, high
data rate (e.g., Parallel computers working on
related computations)

 Loosely-coupled - Large delay in

communications, Low data rate (Distributed
Systems working on unrelated computations)

Notes by Pritee Parwekar,ANITS 27-Nov-16 38

 Bus - All machines connected by single
medium (e.g., LAN, bus, backplane, cable)

 Switched - Single wire from machine to

machine, with possibly different wiring
patterns (e.g, Internet)

Notes by Pritee Parwekar,ANITS 27-Nov-16 39

Notes by Pritee Parwekar,ANITS 27-Nov-16 40
 Up to 64 Tightly-coupled CPUs on a bus,
backplane or motherboard with a shared
memory module
 Plus point is - coherent
 Disadvantage is Bus traffic
 So add high speed memory cache to each
CPU
 Snoopy cache

Notes by Pritee Parwekar,ANITS 27-Nov-16 41

Notes by Pritee Parwekar,ANITS 27-Nov-16 42
Notes by Pritee Parwekar,ANITS 27-Nov-16 43
 To build a multiprocessor with more than 64
processors, a different method is needed to
connect the CPUs with the memory.
 Two switching techniques are employed for
it.

a. Crossbar Switch

b. Omega Switch

Notes by Pritee Parwekar,ANITS 27-Nov-16 44

Notes by Pritee Parwekar,ANITS 27-Nov-16 45
 Memory is divided into the modules and are
connected to the CPUs with the crossbar switch.
 At every intersection is a tiny electronic crosspoint
switch that can be opened and closed in hardware.
 When a CPU wants to access a particular memory, the
crosspoint switch connecting them is closed, to allow
the access to take place.
 If two CPUs try to access the same memory
simultaneously, one of them will have to wait.
 The downside of the crossbar switch is that with n
CPUs and n memories, n2 crosspoint switches are
needed. For large n this number can be prohibitive.

Notes by Pritee Parwekar,ANITS 27-Nov-16 46

Notes by Pritee Parwekar,ANITS 27-Nov-16 47
 It contains 2x2 switches, each having two
inputs and two outputs.
 Each switch can route either input to either
output. A careful look at the figure will show
that with proper setting of the switches, every
CPU can access every memory.
 In general case, with n CPUs and n memories,
the omega network requires log2n switching
stages, each containing n/2 switches, for a
total of (nlog2n)/2 switches.

Notes by Pritee Parwekar,ANITS 27-Nov-16 48

Bus-Based Multicomputers
 easy to build

 communication volume much smaller

 relatively slow speed LAN (10-100 MIPS,

compared to 300 MIPS and up for a
backplane bus)
 Switched Multicomputers

 interconnection networks: E.g., grid,

Hypercube
 Hypercube: n-dimensional cube bus)

Notes by Pritee Parwekar,ANITS 27-Nov-16 49

Notes by Pritee Parwekar,ANITS 27-Nov-16 50
 Software more important for users

Three types:

 1. Network Operating Systems

 2. (True) Distributed Systems

 3. Multiprocessor Time Sharing

Notes by Pritee Parwekar,ANITS 27-Nov-16 51

 loosely-coupled software on loosely-coupled
hardware
 A network of workstations connected by LAN
 each machine has a high degree of autonomy
rlogin machine
rcp machine1:file1 machine2:file2

 Files servers: client and server model

 Clients mount directories on file servers
 Best known network OS:
 Sun’s NFS (network file servers) for shared file
systems
 a few system-wide requirements: format and
 meaning of all the messages exchanged

Notes by Pritee Parwekar,ANITS 27-Nov-16 52

Notes by Pritee Parwekar,ANITS 27-Nov-16 53
 NFS Architecture
– Server exports directories
– Clients mount exported directories


NSF Protocols
– For handling mounting
– For read/write: no open/close, stateless

Notes by Pritee Parwekar,ANITS 27-Nov-16 54

 tightly-coupled software on loosely-coupled
hardware

provide a single-system image or a virtual

uniprocessor
a single, global interprocess communication
mechanism, process management, file system; the
same system call interface everywhere

Ideal definition:

“ A distributed system runs on a collection of computers

that do not have shared memory, yet looks like a single
computer to its users.”

Notes by Pritee Parwekar,ANITS 27-Nov-16 55

 Tightly-coupled software on tightly-coupled
hardware

Examples: high-performance servers
shared memory

single run queue

traditional file system as on a single-processor
system: central block cache

Notes by Pritee Parwekar,ANITS 27-Nov-16 56

Notes by Pritee Parwekar,ANITS 27-Nov-16 57
Notes by Pritee Parwekar,ANITS 27-Nov-16 58
 Transparency

 Flexibility

 Reliability

 Performance

 Scalability

Notes by Pritee Parwekar,ANITS 27-Nov-16 59

 How to achieve the single-system image, i.e.,
how to make a collection of computers appear
as a single computer.

• Hiding all the distribution from the users as

well as the application programs can be
achieved at two levels:

1) hide the distribution from users

2) at a lower level, make the system look transparent
to programs.
1) and 2) requires uniform interfaces such as access
to files, communication.

Notes by Pritee Parwekar,ANITS 27-Nov-16 60

Notes by Pritee Parwekar,ANITS 27-Nov-16 61
In flexibility there are two schools of thoughts
 One school maintains that each machine
should run a traditional kernel that provides
most services itself.
 The other maintains that the kernel should
provide as little as possible with the bulk of
the operating system services available from
user level servers.
 This two models known as the monolithic
kernel and microkernel respectively.

Notes by Pritee Parwekar,ANITS 27-Nov-16 62

 Make it easier to change

• Monolithic Kernel: systems calls are trapped and

executed by the kernel. All system calls are served by
the kernel, e.g., UNIX.

• Microkernel: provides minimal services.

1) IPC
2) some memory management
3) some low-level process management and scheduling
4) low-level i/o

E.g., Mach can support multiple file systems, multiple

system interfaces.

Notes by Pritee Parwekar,ANITS 27-Nov-16 63

Notes by Pritee Parwekar,ANITS 27-Nov-16 64
 Distributed system should be more reliable
than single system.
Example: 3 machines with 0.95 probability of
being up. The probability of all being down will be
0.05 3
– Availability: fraction of time the system is usable.
Redundancy improves it.
– Need to maintain consistency
– Need to be secure
– Fault tolerance: need to mask failures, recover
from errors.

Notes by Pritee Parwekar,ANITS 27-Nov-16 65

 Without gain on this, why bother with
distributed systems.

• Performance loss due to communication

delays:

– fine-grained parallelism: high degree of interaction

– coarse-grained parallelism: data is communicated

infrequently, after larger amounts of computation.

• Fault Tolerance also exacts its price.

Notes by Pritee Parwekar,ANITS 27-Nov-16 66

 Systems grow with time or become obsolete.
Techniques that require resources linearly in terms of
the size of the system are not scalable.

 e.g., broadcast based query won't work for

large distributed systems.

• Examples of bottlenecks
Centralized components: a single mail server
Centralized tables: a single URL address book
Centralized algorithms: routing based on complete
information

Notes by Pritee Parwekar,ANITS 27-Nov-16 67

Notes by Pritee Parwekar,ANITS 27-Nov-16 68
Notes by Pritee Parwekar,ANITS 27-Nov-16 69
 Omega network: 2x2 switches for n CPUs and
n memories,
log2 n switching stages, each with n/2
switches, total (n log2 n)/2 switches

Notes by Pritee Parwekar,ANITS 27-Nov-16 70

Notes by Pritee Parwekar,ANITS 27-Nov-16 71
 If n=1024,
 How many switched stages will be there ?
 How many will be the total switches stages
(CPU to Memory & Memory –CPU) ?
 If a processor takes 10 nsec instruction
execution time then now many a RISC
processor executes instructions in MIPS ?
 What would be the switching time for one
instructions ?

Notes by Pritee Parwekar,ANITS 27-Nov-16 72

 NUMA (Non-Uniform Memory Access):
placement of program and data
building a large, tightly-coupled, shared
memory multiprocessor is possible, but is
difficult and expensive

Notes by Pritee Parwekar,ANITS 27-Nov-16 73

 A multi-computer with 256-CPUs is
organized as a 16X16 grid. What is the
worst-case delay (in hops) that a message
might have to take?

Notes by Pritee Parwekar,ANITS 27-Nov-16 74

 Consider a 256 CPU-hypercube what is the
worst case delay here again in hops?

Notes by Pritee Parwekar,ANITS 27-Nov-16 75

 A multiprocessor has 4096 CPUs connected
to memory by an omega network.
 Find out how many switches stages required ?
 How many total switches stages required ?
 How many total switches required ?

Notes by Pritee Parwekar,ANITS 27-Nov-16 76

 A multiprocessor has 4096 50MIPS CPUs
connected to memory by an omega network.
How fast do the switches have to be to allow
a request to go to memory and back in one
instruction time ?

Notes by Pritee Parwekar,ANITS 27-Nov-16 77

1.Explain the following in brief :
a) Scalability can be achieved by applying
different techniques. What are these
techniques? -2M
b) Advantages of distributed systems over
independent PCs -2M
2.Discuss software concepts of distributed
system. -6M
3.Explain design issues of distributed systems
-6M
(CO-1)

Notes by Pritee Parwekar,ANITS 27-Nov-16 78