|
Application Program Interface (API) for internet protocols
API is
a programming interface between application programs
and communication subsystems based on open network protocols.
The API lets any application program operating in its own MVS address space
to access and use communication services provided by an MVS subsystem that
implements this interface. TCP access, which provides communication services
using TCP/IP protocols, is an example of such a subsystem.
This programmer's reference describes an interface
to the transport layer of the Basic Reference Model
of Open Systems Interconnection (OSI). Although the
API is capable of interfacing to proprietary protocols, the Internet open
network protocols are the intended providers of the transport service. This
document uses the term "open" to emphasize that any system
conforming to one of these standards can communicate with any other system
conforming to the same standard, regardless of vendor. These protocols are
contrasted with proprietary protocols that generally support a closed
community of systems supplied by a single vendor External Data Representation
and Marshalling.
Data
Representation & Marshaling
The information stored in running programs is represented as data
structures – for example, by sets of interconnected objects – whereas the
information in messages consists of sequences of bytes. Irrespective of the
form of communication used, the data structures must be flattened (converted
to a sequence of bytes) before transmission and rebuilt on arrival.
The individual primitive data items transmitted in messages can be data
values of many different types, and not all computers store primitive values
such as integers in the same order. The representation of floating-point
numbers also differs between architectures. To support any data type that
can be passed as an argument or returned as a result must be able to be flattened and the individual
primitive data values represented in an agreed format.
External data representation– an
agreed standard for the representation of data structures and primitive
values
Marshalling– the
process of taking a collection of data items and assembling them into a form
suitable for transmission in a message
Unmarshalling– is
the process of disassembling them on arrival into an equivalent
representation at the destination The marshalling and unmarshalling are
intended to be carried out by the middleware layer. ……………Reference
{george-coulouris-distributed-systems-concepts-and-design}
Group
Communication
What is a group?
·
A number of processes which
cooperate to provide a service.
·
An abstract identity to name a
collection of processes.
Group
Communication: For
coordination among processes of a group.
Who Needs Group Communication?
·
Highly available servers
(client-server)
·
Database Replication
·
Multimedia Conferencing
·
Online Games
·
Cluster management
Client Server Communication
Client and
server communication take place when both are connected to each other via a
network. Client and the server are two individual computing systems having
their own operating system, applications and functions. When connected via a
network they are able to share their applications with each other.
It is not
necessary that client and server use a same platform as operating system,
many varied operating systems can be connected with each other for advanced
communication using communication protocol. The responsibility of
implementing the communication protocol lies with an application known as
communication software.
Using the
features of a communication software client and server can exchange files and
data for effective communication. The process of communication between client
and server can be explained as follows:
·
Data resides in the server.
·
Client system sends a query to the server
·
Server searches the data for the information to be exchanged
·
Server sends the requested data in the form of final result
Unit-03/Lecture-02
INTRODUCTION TO RPC ((Dec-2013)
- A
remote procedure call(RPC) is an inter – process communication
that allows a computer program to cause a procedure to execute in
another address space (commonly on another computer on a shared network)
without the programmer explicitly coding the details for this remote
interaction.
- It further aims at hiding most of the
intricacies of message passing and is idle for client-server
application.
- RPC allows programs to call
procedures located on other machines. But the procedures ‘send’ and
‘receive ’do not conceal the communication which leads to achieving
access transparence in distributed systems.
- Example: when process A calls a
procedure on B, the calling process on A is suspended and the execution
of the called procedure takes place. (PS: function, method, procedure
difference, stub, 5 state process model definition)
- Information can be transported in
the form of parameters and can come back in procedure result. No message
passing is visible to the programmer. As calling and called procedures
exist on different machines, they execute in different
address spaces, the parameters and result should be identical and if
machines crash during communication, it causes problems
IMPLEMENTING RPC MECHANISM
·
To achieve the goal of semantic transparency, the
implementation of an RPC mechanism is based on the concept of stubs, which
provide a perfectly normal (local) procedure call abstraction
by concealing from programs the interface to the underlying RPC system. We
saw that an RPC involves a client process and a server process.
·
Therefore, to conceal the interface of the
underlying RPC system from both the client and server processes, a separate
stub procedure is associated with each of the two processes. Moreover, to
hide the existence and functional details of the underlying network, an RPC
communication package (known as RPC Runtime) is used on both the client and
server sides. Thus, implementation of an RPC mechanism usually involves the
following five elements of program.
1.The client
2.The client stub
3.The RPC Runtime
4.The server stub
5.The server
·
The interaction between them is shown in Figure
4.2. The client, the client stub, and one instance of RPC Runtime execute on
the client machine, while the server, the server stub, and another instance
of RPC Runtime execute on the server machine. The job of each of these
elements is described below
Fig: Implementation of RPC mechanism
Client :
The
client is a user process that initiates a remote procedure call. To make a
remote procedure call, the client makes a perfectly normal local call that
invokes a correspond ding procedure in the client stub.
Client Stub :
The client stub is responsible for
carrying out the following two tasks :
·
On receipt of a call request from
the client, it packs a specification of the target procedure and the
arguments into a message and then asks the local RPC Runtime
to send it to the server stub.
·
On receipt of the result of
procedure execution, it unpacks the result and passes it to the client.
RPC Runtime :
·
The RPC Runtime handles transmission of messages
across the network between client and server machines. It is responsible for
retransmissions, acknowledgements, packet routing, and encryption.
The RPC
Runtime on the client machine receives the call request message from the
client stub and sends it to the server machine. It also receives the message
containing the result of procedure execution from the server machine and
passes it to the client stub.
·
On the other hand, the RPC Runtime on the server
machine receives the message containing the result of procedure execution
from the server stub and sends it to the client machine. It also receives the
call request message from the client machine and passes it to the server
stub.
Server Stub :
The job of the server stub is very
similar to that of the client stub. It performs the following two tasks :
· On
the receipt of the call request message from the local RPCRuntime, the server
stub
unpacks it and makes a perfectly normal call to invoke the appropriate
procedure
in the server.
·
On receipt of the result of procedure execution from the server, the server
stub packs
the result
into a message and then asks the local RPCRuntime to send it to the client
stub.
Server : On
receiving a call request from the server stub, the server executes the
appropriate procedure and returns the result of procedure execution to the
server stub.
……………Reference {P.K.Sinha,
DISTRIBUTED OPERATING SYSTEMS,171}
|
S.NO
|
RGPV QUESTIONS
|
Year
|
Marks
|
|
Q.1
|
What is API for
internet protocol?
|
Dec.2014
|
7
|
|
Q.2
|
Explain the various Remote Procedure Call
semantics?
|
Dec.2013
|
7
|
|
Q.3
|
Describe the various RPC protocol
supporting client-server communication?
|
Dec2013
|
7
|
|
Q.4
|
Explain why and how a
client is prevented from calling arbitrary code within a server under
lightweight RPC ?
|
Dec2014
|
7
|
|
Q.5
|
Compare and explain
times for Synchronous and
Asynchronous remote
procedure calls with
suitable diagrams
|
Dec2014
|
7
|
STUB
GENERATION
Stubs
can be generated in one of the following two ways :
1. Manually:
In this method, the RPC implementer provides a set of translation functions from which a user can construct
his or her own stubs. This method is simple to implement and can handle very
complex parameter types.
2. Automatically:
This is the more commonly used method for stub generation. It uses Interface
Definition Language (IDL) that is used to define the interface between a
client and a server.
·
An interface definition is mainly a list of
procedure names supported by the interface, together with the types of their
arguments and results. This is sufficient information for the client and
server to independently perform compile-time type checking and to generate
appropriate calling sequences.
·
However, an interface definition also contains
other information that helps RPC reduce data storage and the amount of data
transferred over the network. For example, an interface definition has
information to indicate whether each argument is input, output, or both –
only input arguments need be copied from client to server and only output
arguments need be copied from server to client.
·
Similarly, an interface definition also has information
about type definitions, enumerated types, and defined constants that each
side uses to manipulate data from RPC calls making it unnecessary for both
the client and the server to store this information separately
·
A server program that implements procedures in an
interface is said to export the interface and a client program that calls
procedures from an interface is said to import the interface. When writing a
distributed application, a programmer first writes an interface definition
using the IDL. He or she can then write the client program that imports the
interface and the server program that exports the interface.
·
The
interface definition is processed using an IDL computer to generate
components that can be combined with client and server programs, without
making any changes to the existing compliers. In particular, from an
interface definition, an IDL complier generate a client stub procedure and a
server such procedure for each procedure is the interface.
·
The header file is included in the
source files of both the client and server programs, the client stub
procedures are complied and linked with the client program, and the server
stub procedures are compiled and linked with the server program.
·
An IDL
compiler an be designed to process interface definitions for use with
different languages, enabling clients and servers written in different
languages, to communicate by using remote procedure calls.
RPC MESSAGES (Dec-2011)
·
Any remote procedure call involves a client
process and a server process that are possibly located on different
computers. The mode of interaction between the client and server is that the
client asks the server to execute a remote procedure and the server returns
the result of execution of the concerned procedure to the client. Based on
this mode of interaction, the two types of messages involved in the
implementation of an RPC system are as follows :
1. Call
messages that are sent by the client to the server for requesting
execution of a particular remote procedure.
2 .Reply
messages that are sent by the server to the client for returning the result
of remote procedure execution.
·
The protocol of the concerned RPC system defines
the format of these two types of message. Normally, an RPC protocol is
independent of transport protocols. That is, RPC does not care how a message
is passed from one process to another. Therefore an RPC protocol deals only
with the specification and interpretation of these two types of messages.
Call Messages : Since a
call message is used to request execution of a particular remote procedure
the two basic components necessary in a call message are as follows :
- The
identification information of the remote procedure to be executed.
- The
arguments necessary for the execution of the procedure.
In
addition to these two fields, a call
message normally has the following fields.
- A
message identification field that consists of a sequence number. This
field is useful of two ways–for identifying lost
messages and duplicate messages in case of system failures and for
properly matching reply messages to outstanding call messages,
especially in those cases when the replies of several outstanding call
messages arrive out of order.
- A
message type field that is used to distinguish call messages from reply
messages. For example, in an RPC system, this field may be set to 0 for
all call messages and set to 1 for all reply messages.
- A
client identification field that may be used for two purposes–to allow
the server of the RPC to identify the client to whom the reply message
has to be returned and to allow the server to check the authentication
of the client process for executing the concerned procedure.
Reply Messages :When the
server of an RPC receives a call message from a client, it could be faced
with one of the following conditions
Fig.A
typical RPC reply message format : (a) a successful reply message format;
(b) an unsuccessful
reply message format
……………Reference {P.K.Sinha, DISTRIBUTED OPERATING SYSTEMS,175}
Unit-03/Lecture-04
Synchronization (Dec-2013)
Synchronization
mechanisms that are suitable for distributed systems. In particular, the
following synchronization related issues are described :
(i)
Clock
synchronization
(ii)
Event ordering
(iii)
Mutual exclusion
(iv)
Deadlock
(v)
Election algorithm
CLOCK
SYNCHRONIZATION
·
Every computer needs a timer mechanism (called a computer clock) to
keep track of current time and also for various accounting purposes such as
calculating the time spent by a process in CPU utilization, disk I/O and so
on, so that the corresponding user can be charged properly.
·
In a distributed system, an application may have processes that
concurrently run on multiple nodes of the system. For correct results,
several such distributed applications require that the clocks of the nodes
are synchronised with each other. For example, for a distributed on line
reservation system to be fair, the only remaining seat booked almost
simultaneously from two different nodes should be offered to the client who
booked first, even if the time different between the two bookings is very
small.
·
It may not be possible to guarantee this if the clocks of the nodes of
the system are not synchronized. In a distributed system, synchronized clocks
also enable one to measure the duration of distributed activities that start
on one node and terminate on another node, for instance calculating the time
taken to transmit a message from one node to another at any arbitrary time.
It is difficult to get the correct result in the case if the clocks of the
sender and receiver nodes are not synchronized.
How computer
clocks are implemented :
·
A computer clock usually consists of three components – a quartz
crystal that oscillates at a well – defined frequency, a counter register,
and a holding register. The constant register is used to store a constant
value that is decided based on the frequency of oscillation of the quartz
crystal.
·
That is, the value in the counter register is decremented by 1 for each
oscillation of the quartz crystal. When the value of the counter register
becomes zero, an interrupt is generated and its value is reinitialized to the
value in the constant register. Each interrupt is called clock tick.
To
make the computer clock function as an ordinary clock following things are
done :
·
The value in the holding register is chosen 60 so that on 60 clock
ticks occur in a second.
·
The computer clock is
synchronized with real time .For this,two values are stored in system- a
fixed starting date and time ,and the number of ticks.
……………Reference {P.K.Sinha, DISTRIBUTED OPERATING SYSTEMS,283}
|
S.NO
|
RGPV QUESTIONS
|
Year
|
Marks
|
|
Q.1
|
What is significance of time in distributed
system? What are the ways for synchronizing clock? Give brief overview of
various techniques?
|
Dec.2013
|
7
|
Unit-03/Lecture-05
MUTUAL
EXCLUSION
·
There are several resources in a system that must
not be used simultaneously by multiple processes if program operation is to
be correct. For example, a file must not be simultaneously updated by
multiple processes.
·
Similarly, use of unit record peripherals such as
tape drives or printers must be restricted to a single process at a time.
Therefore, exclusive access to such a shared resource by a process must be
ensured. This exclusiveness of access is called mutual exclusion between
processes.
·
The sections of a program that need exclusive
access to shared resources are referred to as critical sections. For mutual
exclusion, means are introduced to prevent processes from executing
concurrently within their associated critical sections.
An
algorithm for implementing mutual exclusion must satisfy the following
requirements :
Issues in Recovery from Deadlock: Two important issues in the recovery action
are selection of victims and use of transaction mechanism. These are
described below.
Selection
of Victim(s): In any of the recovery approaches described above, deadlock is
broken by killing or rolling back one or more processes. These processes are
called victims. Notice that even in the operator intervention approach,
recovery involves killing one or more victims. Therefore, an important issue
in any recovery procedure is to select the victims. Selection of victim(s) is
normally based on two major factors:
1 Minimization of recovery
cost :
This factor suggests that those processes should be selected as victims whose
termination / rollback will incur the minimum recovery cost. Unfortunately,
it is not possible to have a universal cost function, and therefore, each
system should determine its own cost function to select victims. Some of the
factors that may be considered for this purpose are
(a) The
priority of the processes;
(b) The
nature of the processes, such as interactive or batch and possibility of
return with
no ill effects;
(c) The number and types of resources held
by the processes;
(d) The length
of serviceable ready received and the expected length of service further
needed by the processes; and
(e) The
total number of processes that will be affected.
2. Prevention of starvation: If a
system only aims at minimization of recovery cost, it may happen that the
same process (probably because its priority is very low) is repeatedly
selected as a victim and may never complete. This situation known as
starvation, must be somehow prevented in any practical system. One approach
to handle this problem is to raise the priority of the process every time it
is victimized. Another approach is to include the number of times a process
is victimized as a parameter in the cost function.
Use of
Transaction Mechanism: After a process is killed or rolled back for recovery
from deadlock, it has to be return. However, rerunning a process may not
always be safe, e specially when the operations already performed by the
process are non-idempotent. For example, if a process has updated the amount
of a bank account by adding a certain amount to it, re-execution of the
process will result in adding the same amount once again, leaving the balance
in the account in an incorrect state. Therefore, the use of transaction
mechanism (which ensures all or no effect) becomes almost inevitable for most
processes when the system chooses the method of detection and recovery for
handling deadlocks.
However,
notice that the transaction mechanism need not be used for those processes
that can be rerun with no ill effects. For example, rerun of a compilation
process has no ill effects because all it does is read a source file and produce an object
file
|
S.NO
|
RGPV QUESTIONS
|
Year
|
Marks
|
|
Q.1
|
What are the requirements for
distributed mutual exclusion algorithms?
|
Dec.2014
|
7
|
Unit-03/Lecture-06
ELECTION ALGORITHMS
·
Several distributed algorithms
require that there be a coordinator process in the entire system that
performs some type of coordination activity needed for the smooth running of
other processes in the system.
·
Two examples of such coordinator
processes encountered are the coordinator in the centralized algorithm for
mutual exclusion and the central coordinator in the centralized deadlock
detection algorithm.
·
Since all other processes in the
system have to interact with the coordinator, they all must unanimously agree
on who the coordinator is. Furthermore, if the coordinator process fails due
to the failure of the site on which it is located, a new coordinator process
must be elected to take up the of the failed coordinator.
Election algorithms are meant for
electing to take coordinator process from among the currently running
processes in such a manner that at any instance of time there is a single
coordinator for all processes in the system.
·
Election algorithm are based on the following
assumptions :
(1) Each process in the system
has a unique priority number.
(2) Whenever an election is
held, the process having the highest priority number
among the currently
active processes is elected as the coordinator.
(3)On recovery, a failed process
can take appropriate actions to rejoin the set of
active processes.
·
Therefore,
whenever initiated, an election algorithm basically finds out which of the currently active processes has
the highest priority number and then informs this to all other active
processes.
·
Different election algorithms differ in the way
they do this. Two such election algorithms are described below.
Bully Algorithm: (Dec-2012)
When any process notices
that the coordinator is no longer responding to the requests, it asks
for the election. Example: A process P holds an
election as follows:
1) P sends
an ELECTION message to all the processes with higher numbers.
2) If no
one responds, P wins the election and becomes the coordinator.
3) If one
higher process answers; it takes over the job and P’s job is done.
·
At any moment
an “election” message can arrive to process from one of its lowered numbered
colleague. The receiving process replies with an OK to say that it is alive
and can take over as a coordinator.
·
Now this receiver holds an election and in the end all the processes
give you except one and that one is the new coordinator.
The new coordinator announces its new post by sending all the processes a
message that it is starting immediately and is the new coordinator of the system. If the old
coordinator was down and if it gets up again; it holds for an election which works in the above mentioned fashion. The biggest
numbered process always wins and hence
the name “bully” is used for this algorithm.
Figure : The bully election algorithm
a) Process 4 holds an election.
b) Process 5 and 6 respond, telling
4 to stop.
c) Now 5 and 6 each hold an
election.
d) Process 6 tells 5 to stop.
e) Process 6 wins and tells
everyone.
Unit-03/Lecture-07
Ring Algorithm: (Dec-2012)
It is based on the use of a ring as
the name suggests. But this does not use a toke. Processes are physically
ordered in such a way that every process knows its successor.
2 When
any process notices that the coordinator is no longer functioning, it builds
up an ELECTION message containing its own number and passes it along the to
its successor. If the successor is down, then sender skips that member along
the ring to the next working process.
3
At each step, the sender adds its own process number to the list in the
message effectively making itself a candidate to be elected s the coordinator.
At the end, the message gets back to the process that started it.
4 That
process identifies this event when it receives an incoming message containing
its own process number. Then the same message is changed as coordinator and
is circulated once again.
5 Example:
two process, Number 2 and Number 5 discover together that the previous
coordinator; Number 7 has crashed. Number 2 and Number 5 will each build an
election message and start circulating it along the ring. Both the messages
in the end will go to Number 2 and Number 5 and they will convert the message
into the coordinator with exactly the same number of members and in the same
order. When both such messages have gone around the ring, they both will be
discarded and the process of election will re-start.
Figure: Election algorithm using Ring
|
S.NO
|
RGPV QUESTION
|
YEAR
|
MARKS
|
|
Q.1
|
Describe the
Ring election algorithm with example? Discuss the complexity of Bully and
Ring selection algorithm in terms of
message?.
|
Dec2012
|
10
|
|
References
|
|
S no.
|
BOOK
|
Author
|
Priority
|
|
1
|
Distributed Operating System Concept &
Design, PHI
|
P.K.Sinha
|
1
|
|
2
|
Distributed System Concepts and Design,
Pearson Pub
|
Coulouris & Dollimore
|
2
|
|