Distributed Operating

System
Issues in distributed operating system – communication networks and
Primitives –lamport’s logical clocks – causal ordering of messages.
Distributed OS

 Extends the concept of resource management and user Interface to a distributed computing
system encompassing of several autonomous computers connected by a network

 To the users OS appears as a centralized operating system to a single machine.

 Identical copy of operating system may be running on every computer.

 The key feature is transparency(ie, access of multiple processors and remote data is invisible to
the user)
Issues in Distributed OS

Some of the important issues that arises during the design of distributed OS are:
1. Unavailability of up-to-date global knowledge
2. Naming
3. Scalability
4. Compatibility
5. Process synchronization
6. Resource management
7. Security
8. Structuring of Operating System
 Global Knowledge

 Up to date knowledge about the processes and resources(ie global state)

should be completely known.

 But in DOS due to the unavailability of a global memory and global clock
and delay in message passing , it is impossible to keep up-to date
information about global state.
 Global Knowledge

 Absence of knowledge about global state, arriving at consensus is a

significant challenge.

 Another important issue in the absence of global clock is regarding the

ordering of events that happen at different times in different systems
 Naming

 In computer systems names are used to name objects like printers, computers, services, files etc.

 Logical names are mapped to physical addresses and stored in table lookup for mapping

 In distributed systems, files(table lookup) are replicated to increase availability and overcome single
point of failure.

 The disadvantages of replication are:

 Requires more storage capacity
 Need to synchronize when directories are updated.
 Naming

 Instead of replicated directories, partitioned directories can be used to over come drawbacks.

 In partitioned systems, each machine holds only some subset of the total files. 

 Drawback: finding the partition containing a particular named object and its address is complicated.

 Another issue is naming is the method of naming the objects , such that an object can be identified
irrespective of its logical name
 Scalability

 The techniques used for designing a system shouldn’t result in the unavailability or degradation of
performance of the system, when the system grows with time.

 The requirement of scares resources like storage, manpower ,communication bandwidth etc, increases
with the no:of computers in the systems, and are thus costly to implement.

 For example consider Distributed system for File locating by broadcast of queries.

 Here with increase in no: of users , no: of file queries increases, the overhead will also grow large,
affecting the performance of each system.
 Compatibility

 Compatibility refers to the interoperability among resources in a system.

 There are 3 different levels of compatibility that exists in a Distributed system:

 Binary level
 Execution level
 Protocol level
 Compatibility

 In a system that is compatible at binary level, all processors execute the same binary instructions
irrespective of difference in performance and input output.

 The main advantage of binary level compatibility is easier system development.

 But distributed system rarely supports binary compatibility as they cannot include computers with
different architectures.

 Execution level compatibility is said to exist in a DS if same source code can be compiled and executed
properly on any computer in the system.
 Compatibility

 Protocol level compatibility is the least restrictive form of compatibility

 It achieves interoperability by requiring all system components to support a common set of protocols

 Significant advantage of protocol level is that individual computers can run different operating system
without sacrificing interoperability

 For example in a DS common protocols can be implemented for services like file access, naming etc.
 Process synchronization

 Process synchronization is difficult in DS due to the unavailability of shared memory.

 A DOS has to synchronize processes running at different computers when they concurrently access a
shared resource.

 This is called problem of mutual exclusion where a shared resource is accessed by a single processor
at a time.

 The concurrent access to the shared resources by several uncoordinated user request must be
serialized
 Process synchronization

 In DS Processes request resources and release resources in any order that may not be
known prior.

 If the sequence of allocation of resources is not controlled in such cases, dead lock may
occur.

 The dead locks should be detected and resolved immediately as it will degrade the
performance of the system.
 Resource Management

 In Distributed systems, both the local and remote resources should be available to user in an
effective manner

 The resources of a distributed system are made available to the user in the following ways:

 Data migration
 Computation migration
 Distributed sharing
 Resource Management

 Data Migration: In this approach data is transferred from its source to the location of computation.

 If the computation updates the data, it should be updated in the original location

 If the data accessed is a file then access request is managed by Distributed file system, which
implements a common file system for all computers is DS

 If the data accessed is in the physical memory of another system, it will be managed by Distributed
shared memory
 Resource Management

 Computation Migration: Here the computation migrates to location where required data is present

 For example: If one computer may require another computer’s status, it is efficient to find out this
information at the remote computer and send the required information back, rather than sending the
private data structure.

 Remote procedure call is widely used for computation migration

 Resource Management

 Distributed Scheduling: Processes are transferred from one computer to another by Distributed OS.

 It happens in situations when the system in which the process originated is overloaded and doesn’t
have necessary resources or it is overloaded.

 Distributed scheduling is responsible for distributing process among computers such that overall
performance is maximized.
 Security

 Security of a system is the responsibility of its operating system

 Two issues concerning the security of a system are:

 Authentication
 Authorization
 Authentication is the process of guaranteeing that an entity is what it claims to be
 Authorization is the process of deciding what privileges an entity has and making
only these privileges available
 Structuring

 The structure of an operating system defines how various parts of the operating system are
organized:

 MONOLITHIC KERNEL: The traditional method where operating system is constructed as one
big monolithic kernel, which provides all OS services.

 But in DS different computers are meant for different purposes and not every computer would use all
the OS services.

 So it is a waste for all computers to run huge monolithic operating systems

 Structuring

 THE COLLECTIVE KERNEL: Operating system services are implemented as a collection of

processes that are independent of each other.

 The microkernel manages the interaction between processes that provide system services.

 Microkernel provides services that are essential for a system in Distributed environment like
processor management, virtual memory management task management etc.

 Microkernels runs on all computers in DS while other processes runs on a computer based on need
and hardware available in computer
 Structuring

 Object Oriented Operating System: operating system services are implemented as a

collection of objects.

 Each object encapsulates a data structure and defines a set of operations on that data
structure

 By performing operations on objects the data encapsulated can be accessed and modified.
 Client Sever Computing Model

 In this model processes are categorized as Clients and servers.

 Processes that need service are referred to as clients and processes that provide service are
servers.

 Clients sends request to server, which performs the requested task and sends a reply to client

 In systems with multiple servers it is desirable that when providing services to clients, locations
and conversations among servers should be transparent to clients.

 Client server systems can easily adapt to collective kernel structuring technique.
 Communication Networks

 All computers in a distributed system are interconnected through a computer

communication network

 A computer can exchange messages with other computers and access data stored in other
computers through this network.

 Communication networks are broadly classified as:

 Local Area Network.

 Wide Area Network
 Wide Area Networks

 WAN’s are employed to interconnect various devices spread over a large geographical area
that cover diff states, cities or countries.

 Communication facility consists of switches connected through communication links.

 These links may be established through telephone lines, satellites or micro wave links.

 WAN employ point-to point or store and forward technique, where data is transferred
through a series of switches between computers
Wide Area Networks
 Wide Area Networks

 Switches are special devices that are responsible for routing data from one point to another
through an appropriate path avoiding data congestion

 Data congestion takes place either because of heavy data communication or limited
bandwidth.

 Communicate data can be lost due to switch crashes, communication link failure,
transmission error etc.
 Circuit Switching Vs Packet Switching

 Communication n/w can be utilized in one of the 2 modes namely circuit switching and
packet switching
 Circuit Switching :A dedicate path is established b/w the 2 devices that wishes to
communicate
 The path is broken when one side terminates the conversation.

 Packet switching: A path is established between source device and the nearest switch
 Data is broken down into small packets and the address of the destination is contained in
each packet
 Circuit Switching Vs Packet Switching

 Packets are send to the nearest switch by source device.

 The packets are routed from one switch to other switch until it reaches the switch
connected to destination device and packet is delivered to the device.

 There is no reserved path for the devices that communicate.

 It uses the approach of dynamic selection of path based on demand basis.

 Circuit Switching Vs Packet Switching

 The achievable utilization of communication network is high under packet switching.

 Data transmission time is less as packets belonging to a single message can be transmitted
parallel.
 ISO /OSI Reference Model

 ISO/OSI Reference model provides a framework for communication protocol in a

heterogeneous environment to communicate.

 It organizes the protocols as 7 layers and specifies the function of each layer
 ISO /OSI Reference Model

 Each layer is aware of the protocol and header formats of its counterpart and doesn’t
understand header or protocols used by other layers

 Each layer is independent and can change its protocol without affecting other layers

 The physical layer is responsible for the transmission of raw bit stream of data across the
communication network.

 This layer takes care of communication n/w implementation details like type of network,
mode of data transfer etc
 ISO /OSI Reference Model

 Data link layer is responsible for flow control and recovery of data from transmission
error.

 Flow control takes care of the speed with which the bits can be send and received.

 DL layer makes the communication facility provided by physical layer reliable

 ISO /OSI Reference Model

 Network Layer is responsible for routing and congestion control

 It breaks the msg into packets and decide which outgoing line will carry the packets
towards their destination

 The transport layer is responsible for hiding all the details of communication n/w from
the layers above.

 It provides n/w independent device to device communication

 ISO /OSI Reference Model

 Session layer is responsible for establishing and maintaining a connection between two
processes.

 Connection establishing involves authentication of communicating processes and selection

of right transport service.

 It keep tracks of outstanding requests and replies from processes.

 The presentation layer is the interface between user programmer and the network
 ISO /OSI Reference Model

 Takes care of data transformation utilities and difference in representing information at

source and destination

 Application layer’s function is to provide user processes with a facility to use ISO/OSI
protocol.

 Its content vary specific to the application

 Local Area Network

 A communication network that interconnects a variety of data communication devices in a

small geographical area.

 Some characteristics of LAN:

 High data transmission rate

 Confined to a small geographical area (single building or several buildings like a campus)

 Low transmission error rate

 Local Area Network

 Widely used network topologies for LAN are: Bus ,Ring and Tree
 Network Topology

 In bus topology communicating devices transmit data in the form of packets where each packet
contains the address of the destination and the message .

 Bus topology is a network setup where each computer and network device is connected to a single
cable or backbone.

 A tree topology LAN is obtained by interconnecting many bus topology LANS to a common bus.

 Bus topology Lan’s can be viewed as the branches of the tree.

 As the devices share a common bus for data communication, protocols are implemented to control the
access to the bus.
 Network Topology

 CSMA/CD (Carrier Sense Multiple Access with Collision Detection)is a protocol

commonly used with bus topology in LAN.

 In this protocol a device listens to the medium before transmission and transmits data only
if no other transmissions are in progress.

 In case of another transmission the device waits for a random amount of time and checks
again

 The main advantage of this protocol is its simplicity.

 Network Topology

 Another protocol used in bus/tree topology is token bus, where devices are organized to
from a logical ring.

 Each device knows the identity of its predecessor and successor

 Access to the bus is controlled by a token and the device with token is allowed to transmit
data and receive data from other devices.

 A device is allowed to keep token only for a fixed time interval and it should be transferred
to the device following it in the ring
 Network Topology-Ring

 In Ring topology the devices are connected together to form a physical ring.

 Data transmission is point-to-point

 At each point the packet address is checked to find out if packet belongs to the device at
that point

 If address matches, the packet is copied or else it is retransmitted to next device in the ring
 Network Topology

 Slotted ring is another protocol to control access to a ring network

 Here a no: of fixed length slots continuously circulate around the ring

 A device which wants to transmit data wait for an empty slot ,marks it full and insert the
destination address and data into the slot.

 The device can’t retransmit the data until this slot reaches the device which is then marked
empty.

 Few bits are reserved in each slot to transmit the result of transmission
 Communication Primitives

 Communication n/w provides a way for data transfer

 Communication primitives are high level constructs with which the program use
underlying communication network

 2 commonly used communication models that provide primitives are: Message passing
and Remote procedure call

 These 2 models are widely used for developing Distributed operating system and
applications for distributed systems
 Message Passing Model

 This model provides 2 basic communication primitives: SEND and RECEIVE

 SEND primitive has 2 parameters: message and its destination

 RECEIVE primitive also has 2 parameters: Source of the message and buffer for storing
the message.

 These primitives can be commonly seen in client server computation model.

 The client which requires a service sends a message to server and waits for reply
 Message Passing Model

 Depending upon the design of the communication model the semantics of SEND and
Receive Primitives may vary.

 2 Design issues that determine the semantics of 2 primitives are:

 Blocking vs Non blocking primitive

 Synchronous vs Asynchronous Primitive
 Blocking Vs Non Blocking

 Standard message passing model uses buffered option for transfer of messages.

 It uses both the user and kernel buffers of both sender and receiver

 The message is copied from user buffer to kernel buffer of sending computer and then to
kernel buffer of receiver and finally to user buffer of receiver.

 In non blocking primitive the SEND primitive returns the control to the user process as
soon as the message is copied fro user buffer to kernel buffer
 Blocking Vs Non Blocking

 The RECIEVE primitive allocates a buffer for receiving the message and periodically
checks the buffer.

 In blocking primitives SEND primitive doesn’t return control to the user process until
message is send or acknowledgement is received.

 Similarly a RECEIVE primitive doesn’t return control until the message is copied to the
user buffer.
 Synchronous vs Asynchronous

 In synchronous communication the SEND primitive is blocked until a corresponding

RECEIVE primitive is executed in the receiving computer.

 In asynchronous Communication, the messages are buffered.

 A SEND primitive is not blocked even if there is no corresponding execution of a

RECIEVE primitive.

 The use of buffers involves the additional tasks like creating, managing and destroying
buffers.
 Remote Procedure Call(RPC)

 Message passing Communication model is supposed to handle the following details:

 Paring the responses with request message

 Should know the address of the remote machine or server
 Should handle the communication failures

 Remote procedure call(RPC) was designed to overcome these difficulties

 RPC hides all the above details from user.
 Remote Procedure Call(RPC)

 RPC makes use of procedures to transfer data and control across a communication network

 RPC can be viewed as a client server interaction where a client needing a service invokes
a procedure at server.

 On invoking the remote procedure, the calling process is suspended and parameters if any
are passed to the remote machine where the procedure will execute.

 On completion of procedure execution the results are passed back from server to client
and client resumes execution
 Remote Procedure Call(RPC)

 RPC is based on the concept of stub procedures

 When the client makes a RPC a client stub procedure is invoked corresponding to the
procedure

 The stub procedure creates a message containing the identity of remote procedure and
parameters and sends msg to remote server machine

 The message is received by server stub procedure and makes a local call to the procedure
in msg and passes parameters if any.
 Remote Procedure Call(RPC)

 Once the remote procedure completes execution, control is transferred to server stub procedure

 It transfers the result back to client stub procedure at calling machine, which returns the result to user.
Design Issues in RPC

1.Binding
 RPC uses a process called binding to determine the remote procedure and the machine to execute it,
on a RP invocation

 Different binding approaches are available from which a suitable one has to be selected : one
approach is binding server
 Remote Procedure Call(RPC)

Design Issues in RPC

2. Parameter and Result passing:
 To pass parameters or results to RP they have to be presented in a format understood by
remote machine.

 A standard format can be used

 Also how to deal with passing parameters by value and reference.

 Passing parameters by value is comparatively simple, while pass by reference is complicated

Remote Procedure Call
 Remote Procedure Call(RPC)

Design Issues
3. Error Handling
 A remote procedure call can fail mainly due to 2 reasons: computer failures or
communication failures
 Handling failures in DS is difficult.
 Communication failures may cause repeated invocation and execution of the remote
procedure.
 Crashing of client computer immediately after invocation of RP may results in the vain
execution of RP.