Unit -3
Clock Synchronization:
Clock Synchronization is a mechanism to synchronize the time of all the systems connected in DS.
Clock Synchronization is a mechanism to synchronize the time of the computer in DS.
Clock Synchronization classification:
Physical Logical Mutual Exclusion
Physical:
1. All Computer have their own clock
2. Electronic Device
3. Time difference between 2 computers is known as drift.
4. Clock drift over the time is known as skew.
5. Synchronization is necessary
Logical:
1. They concentrate only on order of event rather than time at which that occur.
2. Logical clock can only advance forward not in reverse.
3. Lamport’s Algorithm for Synchronization.
Key Idea:
1. Process exchange messages
2. Message must be sent before receiving.
3. Send/Receive used to order event.
a1 → b2 {a happened before b}
before→ after
Clock (a) < clock (b)
Each message carries timestamp of sender’s clock
If receiver clock < message time stamp
Set system clock (message timestamp + 1)
Else
Do nothing
Algorithm for sender:
Time= time + 1
Timestamp = time
Send (message, timestamp)
Algorithm for Receiver:
(message timestamp) = receive()
Time = max (timestamp, time) +1
Clock Synchronization achieved by 2 ways:
1. External Clock synchronization: It is the one in which an external reference clock is present. It
is used as a reference and the nodes in the system can set and adjust their time accordingly.
2. Internal Clock Synchronization: It is the one in which each node shares its time with other
nodes and all the nodes set and adjust their times accordingly.
Clock Synchronization Algorithms:
1. Cristion’s Algorithm:
Distributed System Algorithms
Distributed systems are the backbone of modern computing, but what keeps them
running smoothly? It’s all about the algorithms. These algorithms are like the secret
sauce, making sure everything works together seamlessly. In this article, we’ll break
down distributed system algorithms in simple language.
Distributed System Algorithms
• Communication Algorithms
• Synchronization Algorithms
• Consensus Algorithms
• Replication Algorithms
• Distributed Query Processing Algorithms
• Load Balancing Algorithms
• Distributed Data Structures and Algorithms
• Failure Detection and Failure Recovery Algorithms
• Security Algorithms for a Distributed Environment
Event Ordering:
Happened -before Relation: it only partial ordering of the events in DS.
Event ordering is sometimes very difficult in DS as due to no common memory and
no common clock.
Happened -before Relation (→)
1. If A was executed before B, then A→B
2. If A is sending a message to B then A→B
3. If A→B and B→C then A→C
Implementation:
1. If A→B timestamp of A is less then time stamp of B.
2. Logical Clock L(i) is associated within each process P1
3. Process advances its logical clock when it receives msg whose timestamp is
greater than current values of logical clock
4. Ts(A) = Ts(B), it means the events are concurrent.
Mutual Exclusion:
It makes sure that processes access shared resources or data in serialized way.
Critical Region:
➔ Shared resources which is accessible only to one at a time.
➔ It is a section which is accessible only to one process at a time.
➔ When a process is accessing a shared variable, the process is said to be
in critical section.
➔ No two process can be in the same Critical Region at the same time.
➔ Mutual exclusion means Critical Region is available to one precess at a
time.
Properties or requirements of Mutual Exclusion:
1. Safety Property: At most one process may in the Critical section at a time.
2. Liveness Property: A process requesting entry to the critical section is
eventually granted it. Liveness simplifies freedom of deadlock and starvation.
3. Fairness: Each process should get fair chance to execute the critical section.
Performance Metrices:
1. Synchronization Delay: Time interval between critical section exit and new
entry by any process.
2. Message complexity: Number of Messages that are required critical section
by a process.
3. System throughput: Rate at which system execute request for the critical
region or rate at which request for critical section et executed.
S=1/SD + E
SD= Synchronization delay
E= Average Execution time.
Deadlock:
Deadlock is a situation where a set of processes are blocked because each process
is holding a resource and waiting for another resource acquired by some other
process. In a deadlock process never finish executing and system resources are
tied up, preventing other job from starting.
Necessary Condition for deadlock:
A deadlock situation can arise if the following 4 conditions hold simultaneously in a
system.
1. Mutual Exclusion: At least one resource must be held in a non-sharable
mode means only one process at a time can use the resource.
2. Hold and wait: There must exist a process that is holding at least one
resource and is waiting to acquire additional resources that are currently
being held by the other process.
3. No preemption: Resources can not be preempted a resource can be released
by the process after completion of task.
4. Circular wait: There must exist a set (P1, P2,….. Pn) of waiting processes sch
that P0 is waiting for resource that is held b P1, P1 is waiting for resource
that is held by P2 and so on.
Deadlock and its prevention Techniques:
Election Algorithm:
Resource Management:
The functionality of DOS is to assign process to the node that are nothing but resource of DS.
Resource usage
Response time optimal performance
Network Congestion
1. Task Assignment Approach:
Each process submitted by the user for processing is viewed as a collection of related tasks.
This task is scheduled to suitable resource in order to improve the performance.
• Execution time of task
• Amount if computation required by each task.
• Speed of CPU.
• Cost of processing each task on every node.
• The time of communication between one task of another task.
• How many tasks we have?
2. Load Balancing Approach:
All processes submitted by the user are distributed among the resources of the system.
It is done to equalize the workload among the resources and remove unbalanced load on the resources.
• Load balancing is an art or way of distributed load units (jobs or tasks) across a set of processor that
are connected to a network and may be distributed across the globe.
• In every system there is always a possibility that sone nodes are heavily loaded while some are
having fewer loads.
• In such case processor in a system can be identified according to their present load.
• Based on this they are termed as
➔ Heavily loaded – enough job are waiting for execution.
➔ Lightly loaded - Where less jobs are waiting
➔ Idle Processes – Have no jobs for execution
The basic aim is making every process equally busy and to finish the task approximately at the same time.
This can be achieved by load balancing concept.
Load balancing aims to:
1. Optimize resource use
2. Maximize throughput
3. Minimize Response time
4. Avoid overload of any single resource.
Detail explanation:
1. Load estimation policy:
Determine how to estimate the workload of a node.
The first issue in a load balancing algorithm is to decide which method to use to estimate the
workload of a particular node.
Estimation of the workload of a particular node is a difficult problem for which no completely
satisfaction solution exists.
A node workload can be estimated based on some measurable parameter below:
➔ Total number of processes on the node
➔ Resource demand of these process
➔ Instruction mixes of these process
➔ Architecture and speed of the node’s processor
2. Process Transfer policy:
➢ Determine whether to execute a process locally or remotely
➢ It is used to transfer processes from heavily loaded nodes to lightly loaded nodes.
➢ Most of the algorithm uses threshold policy to decide whether the node is heavily
loaded or lightly loaded.
➢ The threshold value is limiting work load of node which can be determined by:
Threshold
Static Dynamic
➔ Below threshold node accept the process to execute
➔ Above threshold value node transfer the process to lightly loaded node.
3. Location Policy:
Determines to which node the transferable process should be sent.
It determines the node where the process to be executed.
For this there are different method shown below
➔ Threshold Method: select random node, check node is able to receive process, YES then
transfer No, then repeat till problem limit.
➔ Shortest Method: Select 1 nodes at random
Poll them to find load
Transfer process to node with lowest node
Discontinue when node with 0 load encountered.
➔ Binding Method: In this node’s contains manager (to send process) and contractor (to
receive process).
Manager broadcast request for bid, contractor respond manager select best bid.
➔ Pairing:
Reduces variance of load only between pairs each node asks some randomly chosen node
to form a pair with it. If it receives a rejection, it random select another node and tries to
pair again two nodes that differ greatly in load are temporarily paired with each other and
migration start.
4. State information exchange policy:
Determines how to exchange load information among nodes.
It includes:
➔ Periodic broadcast: All nodes broadcast static information after every T units of time.
Cause heavy traffic poor scalability.
➔ Broadcast when state changes: Broadcast when process to a node arrives and departs.
➔ On demand exchange: Broadcast when node shift from either overload or unload.
➔ Exchange by policy: Partner node is search by polling other node by one until poll limit
reached.
5. Priority Assignment Policy:
It determines which node to execute first local or remote.
➔ Selfish: local process has more priority.
➔ Altruistic: Remote process has more priority.
➔ Intermediate: Process with max count has more priority.
6. Migration Policy:
Determines the total number of times a process can migrate.
➔ Uncontrolled: Process can be migrated n number of times
➔ Controlled: Number of time process to be migrated is determined by predefined factor.
3. Load sharing Approach:
➢ The attempt here is to conserve the ability of the system to perform the work.
➢ This is achieved by assuring that none of the node are idle and none of the process are
queued.
➢ Simply attempts to avoid idle nodes while processes wait for being processed.
Global Scheduling
Flexible: The algorithms should be flexible enough to migrate the process multiple times in case
there in a change in the system load.