Unit II DISTRIBUTED OPERATING SYSTEMS

Distributed Operating Systems: Issues – Communication Primitives – Lampert’s Logical Clocks – Deadlock
handling strategies – Issues in deadlock detection and resolution-distributed file systems –design issues
– Case studies – The Sun Network File System-Coda.

A distributed operating system (DOS) is an essential type of operating system. Distributed systems use
many central processors to serve multiple real-time applications and users. As a result, data processing
jobs are distributed between the processors.
It connects multiple computers via a single communication channel. Furthermore, each of these systems
has its own processor and memory. Additionally, these CPUs communicate via high-speed buses or
telephone lines. Individual systems that communicate via a single channel are regarded as a single
entity. They're also known as loosely coupled systems.
This operating system consists of numerous computers, nodes, and sites joined together via LAN/WAN
lines. It enables the distribution of full systems on a couple of center processors, and it supports many
real-time products and different users. Distributed operating systems can share their computing
resources and I/O files while providing users with virtual machine abstraction.

Types of Distributed Operating System

There are various types of Distributed Operating systems. Some of them are as follows:
 Client-Server Systems
 Peer-to-Peer Systems
 Middleware
 Three-tier
 N-tier
Client-Server System
This type of system requires the client to request a resource, after which the server gives the requested
resource. When a client connects to a server, the server may serve multiple clients at the same time.
Client-Server Systems are also referred to as "Tightly Coupled Operating Systems". This system is
primarily intended for multiprocessors and homogenous multicomputer. Client-Server Systems function
as a centralized server since they approve all requests issued by client systems.
Server systems can be divided into two parts:
1. Computer Server System
This system allows the interface, and the client then sends its own requests to be executed as an action.
After completing the activity, it sends a back response and transfers the result to the client.
2. File Server System
It provides a file system interface for clients, allowing them to execute actions like file creation,
updating, deletion, and more.
Peer-to-Peer System
The nodes play an important role in this system. The task is evenly distributed among the nodes.
Additionally, these nodes can share data and resources as needed. Once again, they require a network
to connect. The Peer-to-Peer System is known as a "Loosely Couple System". This concept is used in
computer network applications since they contain a large number of processors that do not share
memory or clocks. Each processor has its own local memory, and they interact with one another via a
variety of communication methods like telephone lines or high-speed buses.
Middleware
Middleware enables the interoperability of all applications running on different operating systems.
Those programs are capable of transferring all data to one other by using these services.
Three-tier
The information about the client is saved in the intermediate tier rather than in the client, which
simplifies development. This type of architecture is most commonly used in online applications.
N-tier
When a server or application has to transmit requests to other enterprise services on the network, n-tier
systems are used.
Features of Distributed Operating System
There are various features of the distributed operating system. Some of them are as follows:
 Openness : It means that the system's services are freely displayed through interfaces.
Furthermore, these interfaces only give the service syntax. For example, the type of function, its
return type, parameters, and so on. Interface Definition Languages are used to create these
interfaces (IDL).
 Scalability : It refers to the fact that the system's efficiency should not vary as new nodes are
added to the system. Furthermore, the performance of a system with 100 nodes should be the
same as that of a system with 1000 nodes.
 Resource Sharing : Its most essential feature is that it allows users to share resources. They can
also share resources in a secure and controlled manner. Printers, files, data, storage, web pages,
etc., are examples of shared resources.
 Flexibility : A DOS's flexibility is enhanced by modular qualities and delivers a more advanced
range of high-level services. The kernel/ microkernel's quality and completeness simplify the
implementation of such services.
 Transparency : It is the most important feature of the distributed operating system. The primary
purpose of a distributed operating system is to hide the fact that resources are shared.
Transparency also implies that the user should be unaware that the resources he is accessing
are shared. Furthermore, the system should be a separate independent unit for the user.
 Heterogeneity : The components of distributed systems may differ and vary in operating
systems, networks, programming languages, computer hardware, and implementations by
different developers.
 Fault Tolerance: Fault tolerance is that process in which user may continue their work if the
software or hardware fails.
Examples of Distributed Operating System
There are various examples of the distributed operating system. Some of them are as follows:
 Solaris : It is designed for the SUN multiprocessor workstations
 OSF/1 : It's compatible with Unix and was designed by the Open Foundation Software
Company.
 Micros : The MICROS operating system ensures a balanced data load while allocating jobs to all
nodes in the system.
 DYNIX : It is developed for the Symmetry multiprocessor computers.
 Locus : It may be accessed local and remote files at the same time without any location
hindrance.
 Mach : It allows the multithreading and multitasking features.
Applications of Distributed Operating System
There are various applications of the distributed operating system. Some of them are as follows:
 Network Applications : DOS is used by many network applications, including the Web, peer-to-
peer networks, multiplayer web-based games, and virtual communities.
 Telecommunication Networks: DOS is useful in phones and cellular networks. A DOS can be
found in networks like the Internet, wireless sensor networks, and routing algorithms.
 Parallel Computation : DOS is the basis of systematic computing, which includes cluster
computing and grid computing, and a variety of volunteer computing projects.
 Real-Time Process Control :The real-time process control system operates with a deadline, and
such examples include aircraft control systems.
Advantages and Disadvantages of Distributed Operating System
There are various advantages and disadvantages of the distributed operating system. Some of them are
as follows:
Advantages
 There are various advantages of the distributed operating system. Some of them are as follow:
 It may share all resources (CPU, disk, network interface, nodes, computers, and so on) from one
site to another, increasing data availability across the entire system.
 It reduces the probability of data corruption because all data is replicated across all sites; if one
site fails, the user can access data from another operational site.
 The entire system operates independently of one another, and as a result, if one site crashes,
the entire system does not halt.
 It increases the speed of data exchange from one site to another site.
 It is an open system since it may be accessed from both local and remote locations.
 It helps in the reduction of data processing time.
 Most distributed systems are made up of several nodes that interact to make them fault-
tolerant. If a single machine fails, the system remains operational.
Disadvantages
 There are various disadvantages of the distributed operating system. Some of them are as
follows:
 The system must decide which jobs must be executed when they must be executed, and where
they must be executed. A scheduler has limitations, which can lead to underutilized hardware
and unpredictable runtimes.
 It is hard to implement adequate security in DOS since the nodes and connections must be
secured.
 The database connected to a DOS is relatively complicated and hard to manage in contrast to a
single-user system.
  The underlying software is extremely complex and is not understood very well compared to
other systems.
 The more widely distributed a system is, the more communication latency can be expected. As a
result, teams and developers must choose between availability, consistency, and latency.
 These systems aren't widely available because they're thought to be too expensive.
 Gathering, processing, presenting, and monitoring hardware use metrics for big clusters can be
a real issue.
What is a communication primitive in distributed operating system?
Communication primitives are the high level construct with which programs use the underlying
communication network. They play a significant role in the effective usage of distributed systems. The
communication primitives influence a programmers choice of algorithms. Distributed primitives are the
essential building blocks that help nodes in a network coordinate and interact in distributed systems.
Message forwarding, locking, leader election, atomic transactions, consensus, and replication are typical
examples of distributed primitives.
Common Problems in Distributed Systems and their Solutions
 Unreliable Network: When a system is divided into two separate parts, communication between
parts can sometimes become unreliable or unavailable.
 Inconsistent Data: In a distributed system there can be inconsistencies when nodes have
different versions of the same data. Maintaining consistent data across multiple nodes in a
distributed system is critical in most cases.
 Node Failures: Nodes can fail. Detecting and recovering it should not be complex and time-
consuming.
 Bad resource utilisation and uneven load: Distributing workload fairly across nodes in a system is
challenging, especially when nodes have different processing capabilities or network speeds.
 Security risks: Ensuring secure communication and protecting sensitive data in a distributed
system is critical for some use cases.
 High Latency: Network latency can slow down a distributed system, and the overall system
throughput can be limited by the slowest node.
What type of communication is used in distributed operating systems?
Broadcast Communication: When the host process tries to communicate with every process in a
distributed system at same time. Broadcast communication comes in handy when a common stream of
information is to be delivered to each and every process in most efficient manner possible.
What are the three major modes of communication in distributed systems?
We then look at three widely-used models for communication: Remote Procedure Call (RPC), Message-
Oriented Middleware (MOM), and data streaming. We also discuss the general problem of sending data
to multiple receivers, called multicasting.

Lampert’s Logical Clocks

Lamport’s Logical Clock was created by Leslie Lamport. It is a procedure to determine the order of
events occurring. It provides a basis for the more advanced Vector Clock Algorithm. Due to the absence
of a Global Clock in a Distributed Operating System Lamport Logical Clock is needed.
A Lamport logical clock is a numerical software counter value maintained in each process. Conceptually,
this logical clock can be thought of as a clock that only has meaning in relation to messages moving
between processes. When a process receives a message, it re-synchronizes its logical clock with that
sender.
Algorithm:
 Happened before relation (->): a -> b, means ‘a’ happened before ‘b’.
 Logical Clock: The criteria for the logical clocks are:
 [C1]: Ci (a) < Ci(b), [ Ci -> Logical Clock, If ‘a’ happened before ‘b’, then time of ‘a’ will be
less than ‘b’ in a particular process. +
 [C2]: Ci(a) < Cj(b), [ Clock value of Ci(a) is less than Cj(b) ]
Reference:
 Process: Pi
 Event: Eij, where i is the process in number and j: jth event in the ith process.
 tm: vector time span for message m.
 Ci vector clock associated with process Pi, the jth element is Ci[j] and contains Pi‘s latest value for
the current time in process Pj.
 d: drift time, generally d is 1.
Implementation Rules[IR]:
 [IR1]: If a -> b *‘a’ happened before ‘b’ within the same process+ then, Ci(b) =Ci(a) + d
 [IR2]: Cj = max(Cj, tm + d) *If there’s more number of processes, then tm = value of Ci(a), Cj = max
value between Cj and tm + d]
For Example:

 Take the starting value as 1, since it is the 1st event and there is no incoming value at the starting
point:
 e11 = 1
 e21 = 1
 The value of the next point will go on increasing by d (d = 1), if there is no incoming value i.e., to
follow [IR1].
 e12 = e11 + d = 1 + 1 = 2
 e13 = e12 + d = 2 + 1 = 3
 e14 = e13 + d = 3 + 1 = 4
 e15 = e14 + d = 4 + 1 = 5
 e16 = e15 + d = 5 + 1 = 6
 e22 = e21 + d = 1 + 1 = 2
 e24 = e23 + d = 3 + 1 = 4
 e26 = e25 + d = 6 + 1 = 7
 When there will be incoming value, then follow [IR2] i.e., take the maximum value
between Cj and Tm + d.
1. e17 = max(7, 5) = 7, [e16 + d = 6 + 1 = 7, e24 + d = 4 + 1 = 5, maximum among 7 and 5 is 7]
2. e23 = max(3, 3) = 3, [e22 + d = 2 + 1 = 3, e12 + d = 2 + 1 = 3, maximum among 3 and 3 is 3]
3. e25 = max(5, 6) = 6, [e24 + 1 = 4 + 1 = 5, e15 + d = 5 + 1 = 6, maximum among 5 and 6 is 6]
Limitation:
 In case of [IR1], if a -> b, then C(a) < C(b) -> true.
 In case of [IR2], if a -> b, then C(a) < C(b) -> May be true or may not be true.

Deadlock handling strategies

The following are the strategies used for Deadlock Handling in Distributed System:
 Deadlock Prevention
 Deadlock Avoidance
 Deadlock Detection and Recovery
1. Deadlock Prevention: As the name implies, this strategy ensures that deadlock can never happen
because system designing is carried out in such a way. If any one of the deadlock-causing conditions is
not met then deadlock can be prevented. Following are the three methods used for preventing
deadlocks by making one of the deadlock conditions to be unsatisfied:
Collective Requests: In this strategy, all the processes will declare the required resources for their
execution beforehand and will be allowed to execute only if there is the availability of all the required
resources. When the process ends up with processing then only resources will be released. Hence, the
hold and wait condition of deadlock will be prevented.
But the issue is initial resource requirements of a process before it starts are based on an assumption
and not because they will be required. So, resources will be unnecessarily occupied by a process and
prior allocation of resources also affects potential concurrency.
Ordered Requests: In this strategy, ordering is imposed on the resources and thus, process requests for
resources in increasing order. Hence, the circular wait condition of deadlock can be prevented.
 An ordering strictly indicates that a process never asks for a low resource while holding a high
one.
 There are two more ways of dealing with global timing and transactions in distributed systems,
both of which are based on the principle of assigning a global timestamp to each transaction as
soon as it begins.
 During the execution of a process, if a process seems to be blocked because of the resource
acquired by another process then the timestamp of the processes must be checked to identify
the larger timestamp process. In this way, cycle waiting can be prevented.
 It is better to give priority to the old processes because of their long existence and might be
holding more resources.
 It also eliminates starvation issues as the younger transaction will eventually be out of the
system.
Preemption: Resource allocation strategies that reject no-preemption conditions can be used to avoid
deadlocks.
Wait-die: If an older process requires a resource held by a younger process, the latter will have to wait.
A young process will be destroyed if it requests a resource controlled by an older process.
Wound-wait: If an old process seeks a resource held by a young process, the young process will be
preempted, wounded, and killed, and the old process will resume and wait. If a young process needs a
resource held by an older process, it will have to wait.

2. Deadlock Avoidance: In this strategy, deadlock can be avoided by examining the state of the system
at every step. The distributed system reviews the allocation of resources and wherever it finds an unsafe
state, the system backtracks one step and again comes to the safe state. For this, resource allocation
takes time whenever requested by a process. Firstly, the system analysis occurs whether the granting of
resources will make the system in a safe state or unsafe state then only allocation will be made.
A safe state refers to the state when the system is not in deadlocked state and order is there for the
process regarding the granting of requests.
An unsafe state refers to the state when no safe sequence exists for the system. Safe sequence implies
the ordering of a process in such a way that all the processes run to completion in a safe state.
3. Deadlock Detection and Recovery: In this strategy, deadlock is detected and an attempt is made to
resolve the deadlock state of the system. These approaches rely on a Wait-For-Graph (WFG), which is
generated and evaluated for cycles in some methods. The following two requirements must be met by a
deadlock detection algorithm:
Progress: In a given period, the algorithm must find all existing deadlocks. There should be no deadlock
existing in the system which is undetected under this condition. To put it another way, after all, wait-for
dependencies for a deadlock have arisen, the algorithm should not wait for any additional events to
detect the deadlock.
No False Deadlocks: Deadlocks that do not exist should not be reported by the algorithm which is called
phantom or false deadlocks.

There are different types of deadlock detection techniques:

Centralized Deadlock Detector: The resource graph for the entire system is managed by a central
coordinator. When the coordinator detects a cycle, it terminates one of the processes involved in the
cycle to break the deadlock. Messages must be passed when updating the coordinator’s graph.
Following are the methods:
A message must be provided to the coordinator whenever an arc is created or removed from the
resource graph.
Every process can transmit a list of arcs that have been added or removed since the last update
periodically.
When information is needed, the coordinator asks for it.
Hierarchical Deadlock Detector: In this approach, deadlock detectors are arranged in a hierarchy. Here,
only those deadlocks can be detected that fall within their range.
Distributed Deadlock Detector: In this approach, detectors are distributed so that all the sites can fully
participate to resolve the deadlock state. In one of the following below four classes for the Distributed
Detection Algorithm- The probe-based scheme can be used for this purpose. It follows local WFGs to
detect local deadlocks and probe messages to detect global deadlocks.
There are four classes for the Distributed Detection Algorithm:
Path-pushing: In path-pushing algorithms, the detection of distributed deadlocks is carried out by
maintaining an explicit global WFG.
Edge-chasing: In an edge-chasing algorithm, probe messages are used to detect the presence of a cycle
in a distributed graph structure along the edges of the graph.
Diffusion computation: Here, the computation for deadlock detection is dispersed throughout the
system’s WFG.
Global state detection: The detection of Distributed deadlocks can be made by taking a snapshot of the
system and then inspecting it for signs of a deadlock.
To recover from a deadlock, one of the methods can be followed:
 Termination of one or more processes that created the unsafe state.
 Using checkpoints for the periodic checking of the processes so that whenever required, rollback
of processes that makes the system unsafe can be carried out and hence, maintained a safe
state of the system.
 Breaking of existing wait-for relationships between the processes.
 Rollback of one or more blocked processes and allocating their resources to stopped processes,
allowing them to restart operation.
Issues of Deadlock Detection
Various issues of deadlock detection in the distributed system are as follows:
 Deadlock detection-based deadlock handling requires addressing two fundamental issues: first,
detecting existing deadlocks, and second, resolving detected deadlocks.
 Detecting deadlocks entails tackling two issues: WFG maintenance and searching the WFG for
the presence of cycles.
 In a distributed system, a cycle may include multiple sites. The search for cycles is highly
dependent on the system's WFG as represented across the system.
Resolution of Deadlock Detection
Various resolutions of deadlock detection in the distributed system are as follows:
 Deadlock resolution includes the braking existing wait-for dependencies in the system WFG.
 It includes rolling multiple deadlocked processes and giving their resources to the blocked
processes in the deadlock so that they may resume execution.
Distributed File System
A Distributed File System (DFS) as the name suggests, is a file system that is distributed on multiple
file servers or multiple locations. It allows programs to access or store isolated files as they do with
the local ones, allowing programmers to access files from any network or computer.
The main purpose of the Distributed File System (DFS) is to allows users of physically distributed
systems to share their data and resources by using a Common File System. A collection of
workstations and mainframes connected by a Local Area Network (LAN) is a configuration on
Distributed File System. A DFS is executed as a part of the operating system. In DFS, a namespace is
created and this process is transparent for the clients.
DFS has two components:
Location Transparency – Location Transparency achieves through the namespace component.
Redundancy – Redundancy is done through a file replication component.
In the case of failure and heavy load, these components together improve data availability by
allowing the sharing of data in different locations to be logically grouped under one folder, which is
known as the “DFS root”.
It is not necessary to use both the two components of DFS together, it is possible to use the
namespace component without using the file replication component and it is perfectly possible to
use the file replication component without using the namespace component between servers.
File system replication:
Early iterations of DFS made use of Microsoft’s File Replication Service (FRS), which allowed for
straightforward file replication between servers. The most recent iterations of the whole file are
distributed to all servers by FRS, which recognises new or updated files.
“DFS Replication” was developed by Windows Server 2003 R2 (DFSR). By only copying the portions
of files that have changed and minimising network traffic with data compression, it helps to improve
FRS. Additionally, it provides users with flexible configuration options to manage network traffic on
a configurable schedule.
Features of DFS :
Transparency :
Structure transparency – There is no need for the client to know about the number or locations of
file servers and the storage devices. Multiple file servers should be provided for performance,
adaptability, and dependability.
Access transparency – Both local and remote files should be accessible in the same manner. The file
system should be automatically located on the accessed file and send it to the client’s side.
Naming transparency – There should not be any hint in the name of the file to the location of the
file. Once a name is given to the file, it should not be changed during transferring from one node to
another.
Replication transparency – If a file is copied on multiple nodes, both the copies of the file and their
locations should be hidden from one node to another.
User mobility : It will automatically bring the user’s home directory to the node where the user logs in.
Performance : Performance is based on the average amount of time needed to convince the client
requests. This time covers the CPU time + time taken to access secondary storage + network access
time. It is advisable that the performance of the Distributed File System be similar to that of a
centralized file system.
Simplicity and ease of use : The user interface of a file system should be simple and the number of
commands in the file should be small.
High availability : A Distributed File System should be able to continue in case of any partial
failures like a link failure, a node failure, or a storage drive crash.
A high authentic and adaptable distributed file system should have different and independent file
servers for controlling different and independent storage devices.
Scalability : Since growing the network by adding new machines or joining two networks together
is routine, the distributed system will inevitably grow over time. As a result, a good distributed file
system should be built to scale quickly as the number of nodes and users in the system grows.
Service should not be substantially disrupted as the number of nodes and users grows.
High reliability : The likelihood of data loss should be minimized as much as feasible in a suitable
distributed file system. That is, because of the system’s unreliability, users should not feel forced to
make backup copies of their files. Rather, a file system should create backup copies of key files that
can be used if the originals are lost. Many file systems employ stable storage as a high-reliability
strategy.
Data integrity : Multiple users frequently share a file system. The integrity of data saved in a shared
file must be guaranteed by the file system. That is, concurrent access requests from many users who
are competing for access to the same file must be correctly synchronized using a concurrency
control method. Atomic transactions are a high-level concurrency management mechanism for data
integrity that is frequently offered to users by a file system.
Security : A distributed file system should be secure so that its users may trust that their data will
be kept private. To safeguard the information contained in the file system from unwanted &
unauthorized access, security mechanisms must be implemented.
Heterogeneity : Heterogeneity in distributed systems is unavoidable as a result of huge scale. Users
of heterogeneous distributed systems have the option of using multiple computer platforms for
different purposes
Design Issues of Distributed System
Distributed System is a collection of autonomous computer systems that are physically separated
but are connected by a centralized computer network that is equipped with distributed system
software. These are used in numerous applications, such as online gaming, web applications, and
cloud computing. However, creating a distributed system is not simple, and there are a number of
design considerations to take into account. The following are some of the major design issues of
distributed systems:
Design issues of the distributed system –
Heterogeneity: Heterogeneity is applied to the network, computer hardware, operating system, and
implementation of different developers. A key component of the heterogeneous distributed system
client-server environment is middleware. Middleware is a set of services that enables applications
and end-user to interact with each other across a heterogeneous distributed system.
Openness: The openness of the distributed system is determined primarily by the degree to which
new resource-sharing services can be made available to the users. Open systems are characterized
by the fact that their key interfaces are published. It is based on a uniform communication
mechanism and published interface for access to shared resources. It can be constructed from
heterogeneous hardware and software.
Scalability: The scalability of the system should remain efficient even with a significant increase in
the number of users and resources connected. It shouldn’t matter if a program has 10 or 100 nodes;
performance shouldn’t vary. A distributed system’s scaling requires consideration of a number of
elements, including size, geography, and management.
Security: The security of an information system has three components Confidentially, integrity, and
availability. Encryption protects shared resources and keeps sensitive information secrets when
transmitted.
Failure Handling: When some faults occur in hardware and the software program, it may produce
incorrect results or they may stop before they have completed the intended computation so
corrective measures should to implemented to handle this case. Failure handling is difficult in
distributed systems because the failure is partial i, e, some components fail while others continue to
function.
Concurrency: There is a possibility that several clients will attempt to access a shared resource at
the same time. Multiple users make requests on the same resources, i.e. read, write, and update.
Each resource must be safe in a concurrent environment. Any object that represents a shared
resource in a distributed system must ensure that it operates correctly in a concurrent environment.
Transparency: Transparency ensures that the distributed system should be perceived as a single
entity by the users or the application programmers rather than a collection of autonomous systems,
which is cooperating. The user should be unaware of where the services are located and the transfer
from a local machine to a remote one should be transparent.
Sun’s Network File System (NFS)
One of the first uses of distributed client/server computing was in the realm of distributed file
systems. In such an environment, there are a number of client machines and one server (or a few);
the server stores the data on its disks, and clients request data through well-formed protocol
messages. Following figure depicts the basic setup. As you can see from the picture, the server has
the disks, and clients send messages across a network to access their directories and files on those
disks. Why do we bother with this arrangement? (i.e., why don’t we just let clients use their local
disks?) Well, primarily this setup allows for easy sharing of data across clients. Thus, if you access a
file on one machine (Client 0) and then later use another (Client 2), you will have the same view of
the file system. Your data is naturally shared across these different machines. A secondary benefit is
centralized administration; for example, backing up files can be done from the few server machines
instead of from the multitude of clients. Another advantage could be security; having all servers in a
locked machine room prevents certain types of problems from arising