DISTRIBUTED COMPUTING

MODULE 4
Resource & Process Management
University of Mumbai | BE Computer Engineering | Semester 8
Comprehensive Exam Notes with Diagrams

Topics Covered in This Module

4.1 Desirable Features of Global Scheduling Algorithm

4.1 Task Assignment Approach (with solved numerical)
4.1 Load Balancing Approach — All 6 Design Policies
4.1 Load Sharing Approach
4.2 Process Migration (Preemptive vs Non-Preemptive, Address Space Transfer)
4.2 Code Migration (Mobility Models, Bindings, Paradigms — Cake Analogy)
4.2 Threads in Distributed Systems
4.3 Deadlock Detection: Cycles, Knots, AND & OR Models
4.3 Chandy-Misra-Haas (CMH) Algorithm with Full Solved Example
CHAPTER 4.1 — RESOURCE MANAGEMENT

Overview: What is Resource Management?

Resource management is the efficient and effective deployment of an organization's resources when they are
needed. A resource manager schedules the processes in a distributed system to optimize resource usage,
response time, and network congestion. Every distributed system contains a set of resources (logical: shared
files, databases; physical: CPU, memory, I/O devices) interconnected by a network.

Three Scheduling Techniques at a Glance

Technique Core Goal When to Use

Task Assignment Assign each task of a process to Task characteristics and inter-task
the optimal node based on IPC costs are known in advance
cost + execution cost
Load Balancing Equalize workload across ALL Uniform distribution required;
nodes — transfer processes from dynamic state info available
heavy to light nodes
Load Sharing Just ensure NO node is idle while Simpler systems; preventing
others are busy — NOT full idleness is sufficient
equalization

Desirable Features of a Global Scheduling Algorithm

📌 EXAM TIP
10-mark standard question. Write all 8 features with clear sub-headings. Aim for 2–3 lines per feature.

I. No A Priori Knowledge About Processes

Prior knowledge of process characteristics (CPU need, memory, execution time) is rarely available. A good
algorithm must work WITHOUT any prior knowledge — it should accept processes and schedule them
dynamically as they arrive. The algorithm must be able to determine process requirements from observed
behavior, not pre-stated characteristics.

II. Dynamic in Nature

The load assigned to any node changes dynamically at runtime. Scheduling decisions must be based on the
CURRENT (changing) load of nodes, not on a fixed static policy. The algorithm should continuously monitor and
adapt to fluctuating workloads.

III. Quick Decision-Making Capability

The system situation changes rapidly — processes arrive and depart constantly. The algorithm must make FAST
decisions about task assignment. Slow decision-making means the situation has already changed by the time a
decision is reached, making it suboptimal.

IV. Balanced Performance vs Scheduling Overhead

More global state info → more intelligent decisions, BUT → higher communication overhead. The algorithm
must BALANCE accuracy vs cost. Key tradeoff: Accuracy of decisions ↔ Cost of collecting information. The goal
is near-optimal performance with minimal overhead.

V. Stability (Avoid Thrashing)

An unstable algorithm causes PROCESSOR THRASHING — processes migrate continuously without doing useful
work. This happens when nodes oscillate between lightly-loaded and heavily-loaded states repeatedly. Double-
threshold policies create a "normal" buffer zone to prevent instability.

VI. Scalability
The algorithm must handle both small networks (few nodes) and large networks (thousands of nodes) without
degradation. Algorithms relying on broadcasting state info to ALL nodes are NOT scalable. Design must degrade
gracefully with increasing network size.

VII. Fault Tolerance

Individual nodes can crash at any time in a distributed system. When a node crashes, it must NOT affect the
overall scheduling performance. Single-point-of-failure designs (e.g., centralized coordinators) are poor in fault
tolerance. The algorithm must continue functioning after partial failures.

VIII. Fairness of Service

Multiple users may initiate equivalent processes simultaneously. All equivalent users and processes must receive
the SAME quality of service — no starvation allowed. The algorithm ensures equitable assignment so no process
waits indefinitely.

Task Assignment Approach

Each user process is viewed as a collection of related tasks. These tasks are scheduled to suitable nodes to
improve performance. The approach considers both the execution cost at each node and the inter-task
communication (IPC) cost between tasks.

Main Assumptions
● Processes have already been split into tasks before scheduling.
● Computation requirement of tasks and speed of processors are KNOWN IN ADVANCE.
● Cost of processing tasks on nodes is known (derived from processor speed × computation required).
● IPC cost between every pair of tasks is known: if tasks communicate n times with average time t, then
IPC cost = n × t.
● Resource requirements and available resources on each node are known.
 ● REASSIGNMENT of tasks is NOT possible once assigned.

Goals of Task Assignment (with Conflicts)

Goal Description Conflicts With

1. Minimize IPC Costs Place communicating tasks on the Goal 4: If all tasks on one node, no
SAME node to avoid network parallelism.
overhead.
2. Quick Turnaround Complete all tasks in shortest total Goal 3: Parallelism may require
time. splitting tasks.
3. High Parallelism Spread tasks across MULTIPLE Goal 1: Parallel execution
nodes for simultaneous execution. increases IPC cost.
4. Efficient Resource Use Use all nodes' resources — don't Goal 1: Concentrating tasks
leave nodes idle. wastes other nodes.

📌 KEY CONFLICT
Goal 1 (minimize IPC) says put all tasks on ONE node. Goal 3 (parallelism) and Goal 4 (resource use) say
spread across ALL nodes. The optimal assignment BALANCES both — this is why it is NP-hard.

Why Task Assignment is NOT Widely Used

● Requires ALL process characteristics to be known in advance (impractical in real systems).
● Cannot adapt to dynamically changing system states.
● The optimization problem (finding the minimum-cost assignment) is NP-hard for n > 2 nodes.

SOLVED EXAMPLE — Task Assignment Cost Calculation

📌 EXAM NOTE
This type of numerical is frequently asked. Learn to compute: (1) Execution Cost for each assignment.
(2) IPC Cost = only costs for tasks on DIFFERENT nodes. (3) Total Cost = Execution Cost + IPC Cost.

Given: 6 tasks (t1–t6) and 2 nodes (n1, n2)

Execution Cost Table

Task Node n1 Node n2 Constraint

t1 5 10 Can run on either

t2 2 ∞ (impossible) MUST run on n1 only
t3 4 4 Same cost on either
node
t4 6 3 Cheaper on n2
t5 5 2 Cheaper on n2
 Task Node n1 Node n2 Constraint

t6 ∞ (impossible) 4 MUST run on n2 only

IPC Cost Matrix (cost ONLY when tasks on DIFFERENT nodes)

t1 t2 t3 t4 t5 t6

t1 0 6 4 0 0 12
t2 6 0 8 12 3 0
t3 4 8 0 0 11 0
t4 0 12 0 0 5 0
t5 0 3 11 5 0 0
t6 12 0 0 0 0 0

📌 IMPORTANT
IPC cost is incurred ONLY when two communicating tasks are on DIFFERENT nodes. If on the same node
→ IPC cost = 0 (communication is local, no network involved).

Case 1 — Serial Assignment (All tasks on n1 except t6 which MUST be on n2):

Task Node Execution Cost

t1 n1 5
t2 n1 (forced) 2
t3 n1 4
t4 n1 6
t5 n1 5
t6 n2 (forced) 4

Execution Cost: 5+2+4+6+5 (on n1) + 4 (on n2) = 22 + 4 = 26

IPC Cost: Only t1↔t6 are on different nodes → 12
Total Serial Cost = 26 + 12 = 38

Case 2 — Optimal Assignment:

Task Node Reason

t1 n1 t1↔t6 IPC=12; t1 on n1 keeps t1

with t2 (IPC=6) to avoid cross-
node t1–t6 IPC
t2 n1 FORCED (n2=∞)
t3 n1 Same cost; keep with t2 to avoid
t2↔t3 IPC of 8
 Task Node Reason

t4 n2 Cheaper execution (3 vs 6); put

with t6
t5 n2 Cheaper execution (2 vs 5); keep
with t4 to save t4↔t5 IPC=5
t6 n2 FORCED (n1=∞)

Execution Cost: (t1+t2+t3 on n1) = 5+2+4 = 11. (t4+t5+t6 on n2) = 3+2+4 = 9. Total Exec = 20
IPC (cross-node pairs): t1↔t6=12, t2↔t4=12, t2↔t5=3, t3↔t5=11. Total IPC = 38
Total Optimal Cost = 20 + 38 = 58

📌 CUTSET CONCEPT
A "cutset" is the set of edges in the task communication graph between the n1-group and n2-group. IPC
cost = sum of communication costs along cutset edges. Optimal assignment minimizes: Total Execution
Cost + Sum of Cutset Edge Costs.
 Load Balancing Approach
Load balancing tries to EQUALIZE the workload across ALL nodes by transparently transferring processes from
heavily loaded nodes to lightly loaded ones. Goals: (1) Optimize resource use, (2) Maximize throughput, (3)
Minimize response time, (4) Avoid overload of any single resource.

Taxonomy of Load Balancing Algorithms

[ DIAGRAM: Load Balancing Algorithm Taxonomy Tree: Root: Load Balancing Algorithms ├── STATIC
(ignores current state) │ ├── Deterministic │ └── Probabilistic └── DYNAMIC (uses current state) ├──
Centralized └── Distributed ├── Cooperative └── Non-Cooperative ]
✏️ Draw this diagram in your exam answer

Type Sub-Type Description Fault Tolerance

STATIC Deterministic Uses known properties Poor (no adaptation)

of nodes (CPU speed,
memory) and processes
(execution time,
demands). Accurate but
inflexible.
STATIC Probabilistic Uses static system Poor (no adaptation)
attributes (node count,
topology). Simple rules
like Round-Robin. Easy
to implement.
DYNAMIC Centralized State info collected at Very poor (single point
ONE coordinator node. of failure)
All scheduling decisions
made by coordinator.
DYNAMIC Distributed – Multiple nodes Good (no single point of
Cooperative cooperate to make failure)
scheduling decisions.
More complex, higher
overhead but BETTER
stability.
DYNAMIC Distributed – Non- Each node acts Good
Cooperative autonomously. Simple
but less stable.

Six Design Policies for Load Balancing Algorithms

📌 EXAM TIP
These 6 policies are a very common 10-mark question. Cover all 6 with diagrams/examples.
Policy 1: Load Estimation Policy
Determines HOW to measure the workload of a node. Options:
● Total number of processes on the node (most common).
● Resource demands of running processes (CPU %, memory usage).
● Instruction mixes — types of instructions being executed.
● Architecture and speed of the node's processor.
● CPU Utilization: Set a timer to periodically check if CPU is idle or busy. Utilization = CPU cycles executed /
total real time.

Method Description When to Use

Memoryless Method All processes assumed to have the When no history is available
same expected remaining service
time, regardless of time used so
far.
Past Repeats Method Remaining service time = time When patterns repeat (batch jobs)
already used (assumes behavior
repeats).
Distribution Method If service time distribution is When distribution is known a
known, uses expected remaining priori
time conditioned on time used.

Policy 2: Process Transfer Policy

Determines WHEN to transfer a process. Uses THRESHOLD values to classify nodes as overloaded or
underloaded.

Threshold Type Description Drawback

Static Threshold Each node has a PREDEFINED fixed Cannot adapt to changing
threshold based on processing conditions.
capability.
Dynamic Threshold Threshold = Average workload of Higher overhead to compute.
all nodes × a predefined constant
(relative to node capability).

[ DIAGRAM: Single Threshold vs Double Threshold (High-Low Policy) Single Threshold: OVERLOADED
──────────── ← Threshold UNDERLOADED Problem: Node can rapidly flip between states →
THRASHING Double Threshold (High-Low): OVERLOADED → Send out local processes, reject incoming
remote processes ────────────── ← HIGH MARK NORMAL → Local processes run locally, reject
remote processes ────────────── ← LOW MARK UNDERLOADED → Local processes run locally,
ACCEPT remote processes Benefit: "Normal" buffer zone prevents instability ]
✏️ Draw this diagram in your exam answer

📌 KEY RULE
 Single threshold → unstable (thrashing). Double threshold → stable (hysteresis buffer zone called
"Normal" region prevents rapid state flipping).

Policy 3: Location Policy

Determines WHICH node to transfer a process to when a transfer decision has been made.

Method Description Advantage Disadvantage

Threshold (Random Select a random node. If Simple to implement. May need many probes;
Probe) it can accept, transfer. If probe limit may be
rejected, try another. reached without finding
Continue until probe suitable node.
limit.
Shortest Method Choose m distinct Better accuracy than Higher overhead (m polls
random nodes, poll each random. needed).
for its load, send to the
one with MINIMUM
load. Stop early if a zero-
load node is found.
Bidding Method Nodes act as MANAGERS Full autonomy; best offer High communication
(senders) and selected. overhead; pricing policy
CONTRACTORS hard to define.
(receivers). Manager
broadcasts bid request;
contractors respond with
bids; manager picks best
offer.
Pairing Each node randomly Simple; reduces load Only pairwise balancing,
picks another to pair variance between pairs. not global.
with. Two nodes with
very different loads swap
processes. Pair breaks
when done.

Policy 4: State Information Exchange Policy

Determines HOW OFTEN and WHEN nodes share their load state information. Key tradeoff: More messages →
better decisions but higher overhead.

Policy Description Problem

Periodic Broadcast Each node broadcasts state info Heavy traffic; many messages are
after every T time units (fixed fruitless (state may not have
interval). changed).
Broadcast When State Changes Broadcast only when a process Better; still generates traffic if
ARRIVES or DEPARTS. Improved: processes arrive/depart
broadcast only when state crosses frequently.
a threshold boundary.
 Policy Description Problem

On-Demand Exchange Node broadcasts a State- More targeted; fewer messages.

Information-Request ONLY when
its state changes to
UNDERLOADED or OVERLOADED.
Other nodes reply with their state.
Exchange by Polling Poll nodes ONE BY ONE until a Poor scalability if many nodes
suitable partner is found or poll must be polled.
limit is reached. Better for large
networks than broadcast.

Policy 5: Priority Assignment Policy

Determines the priority order of LOCAL vs REMOTE processes at a node.

Policy Priority Order Response Time Performance

Selfish Local processes > Remote WORST — remote processes may

processes starve.
Altruistic Remote processes > Local BEST — remote processes served
processes first; local may suffer.
Intermediate If #local ≥ #remote → local first; MIDDLE — balances both.
else → remote first

Policy 6: Migration Limiting Policy

Determines HOW MANY TIMES a process can migrate from node to node.

Policy Description Risk / Benefit

Uncontrolled Policy Remote process arriving at a node Risk: Process thrashing — keeps
is treated exactly like a local migrating endlessly.
process. Can migrate unlimited
times.
Controlled Policy Migration count parameter limits Avoids instability. Short processes:
migration frequency. • Irrevocable k=1. Long processes: k>1.
Migration: count = 1 (migrate only
once). • For long-execution: count
= k (some limit k > 1).

Load Sharing Approach

In a distributed system, it is NOT required to perfectly balance the load on all nodes. It is sufficient to prevent
nodes from being idle while some other nodes have more than two processes running. This is called Load
Sharing (also: Dynamic Load Sharing).

📌 KEY DIFFERENCE
 Load Balancing = Equalize workload on ALL nodes (complex, high overhead, impractical to perfect). Load
Sharing = Just ensure NO node is idle when others are busy (simpler, low overhead, achievable).

Design Policies for Load Sharing

I. Load Estimation Policy:
● Only needs to know: Is the node BUSY or IDLE?
● Simplest method: Count total number of processes on node.
● In modern systems (daemons always running): Use CPU utilization instead.

II. Process Transfer Policy:

● All-or-Nothing Strategy: Threshold value = 1 for all nodes.
● Receiver Node: Node with 0 processes — wants to receive work.
● Sender Node: Node with >1 process — can give work away.
● Double threshold used when CPU utilization is metric (avoids treating background-daemon nodes as
idle).

III. Location Policy:

Policy Who Initiates? Best Performance Special Requirements

Sender-Initiated OVERLOADED node Light to moderate None.

searches for a lightly system loads.
loaded node to receive
its processes.
Receiver-Initiated UNDERLOADED (idle) High system loads. Requires PREEMPTIVE
node searches for a process migration.
heavily loaded node to
take processes from.

IV. State Information Exchange Policy:

● Broadcast-when-state-changes: Sender-initiated → broadcast when OVERLOADED. Receiver-initiated →
broadcast when IDLE ("broadcast-when-idle").
● Poll-when-state-changes: In large networks, use polling instead of broadcast. Called "poll-when-idle" for
receiver-initiated with threshold=1.

Comparison: Task Assignment vs Load Balancing vs Load Sharing

Parameter Task Assignment Load Balancing Load Sharing

Goal Optimal task-to-node Equalize workload on Prevent any node from

assignment ALL nodes being idle
Knowledge Required Full advance knowledge Current state info of all Only busy/idle status
of task characteristics nodes needed
Complexity Highest (NP-hard) Medium (complex Lowest (simple
policies) threshold)
Parameter Task Assignment Load Balancing Load Sharing

Overhead Very high High (state info Low

gathering)
Adaptability None (static) High (dynamic) Medium
Concept Type Static Dynamic Dynamic (simpler)
CHAPTER 4.2 — PROCESS MANAGEMENT & CODE MIGRATION

Process Migration
Process migration is the relocation of a process from its source node to another destination node. The most
common application is in computer clusters where processes are moved from machine to machine for load
balancing or fault tolerance.

[ DIAGRAM: Process Migration Flow: Source Node Destination Node

────────────────── ────────────────── [Process P1 in execution] │ ▼ [Execution
Suspended] │ ├── Freezing Time ──────────────── Transfer of control ──► │
│ │ ▼ │ [Execution Resumed at Destination] │
[Process P1 in execution at Dest] ▼ (Source: done with P1) ]
✏️ Draw this diagram in your exam answer

Why Process Migration is Needed

● Move processes from one computing environment to another (load balancing, fault tolerance).
● Improve load distribution across nodes in a cluster.
● Exploit parallelism — run tasks closer to available resources.
● Improve resource utilization — avoid idle nodes.
● Move processes away from failing nodes for fault tolerance.

Types of Process Migration

Type When? Cost What Moves?

Non-Preemptive (Eager) BEFORE execution starts LOW — no execution Only process code and
at source node. state to transfer. initial data.
Preemptive DURING execution HIGH — entire process Code + Data + Stack +
(process is running and environment must Execution State + Open
gets moved). transfer. Files + Register values.

📌 EXAM NOTE
Preemptive migration is MORE COSTLY because the process state (memory, stack, open file handles,
register state) becomes much more complex after execution begins. The full "process environment"
must accompany the process to the new node.
Steps in Process Migration
Step Responsibility Description

Step 1: Select process for Migration Policy Identify which process should be
migration migrated (based on load, type,
priority).
Step 2: Select destination node Migration Policy Find the best target node — least
loaded, sufficient resources.
Step 3: Transfer the process Migration Mechanism Actually move — freeze, transfer
address space, restart at
destination.

Address Space Transfer Mechanisms

Mechanism Description Process Downtime Total Transfer Time

Total Freezing Freeze process HIGH (entire transfer Normal

completely. Transfer time)
ENTIRE address space.
Restart only after full
transfer.
Pre-Transferring Transfer pages in LOW (only dirty pages at Higher (some pages
advance WHILE process end) transferred multiple
still runs. Then freeze times if modified)
and transfer only
recently modified (dirty)
pages.
Transfer on Reference Transfer only the VERY LOW (start Distributed over
(Demand Paging) minimal initial state. immediately) execution time (on-
Start execution demand fetching)
immediately at
destination. Fetch
remaining pages on
demand (page fault)
from source.

Message Forwarding During Migration

Message Type When Does It Arrive? At Which Node?

Type 1 After execution stopped at source, Arrives at SOURCE node.

but BEFORE execution started at
destination.
Type 2 After execution has already Arrives at SOURCE node (must be
started at destination. forwarded).
Type 3 Messages sent directly to migrant Arrives at DESTINATION node.
process AFTER it started at
destination.
Four Message Forwarding Mechanisms
● Mechanism of Resending: Source resends the message to destination whenever a misrouted message
arrives.
● Origin Site Mechanism: Source maintains a forwarding table; all future messages routed via source.
● Link Traversal: Message follows a chain of forwarding pointers from old to new location.
● Link Update: When process migrates, notify all known communicating processes of new location
directly.

Features of Good Process Migration

Feature Description

Transparency Migration is invisible to users and communicating

processes. The migrant appears to be at its original
location.
Minimal Interference Migration should not significantly disrupt: (a) the
migrating process, (b) other processes at source, (c)
other processes at destination.
Efficiency Migration overhead (freeze time, transfer time,
forwarding overhead) should be minimized.
Robustness System recovers gracefully if migration fails midway.
Process continues at source or restarts at
destination.

Code Migration
Code migration refers to the transfer of program code (not necessarily an entire running process) from one node
to another, with the intention to have that code executed at the target node.

Why Code Migration?

● Reduce Network Bandwidth: Instead of sending large data across the network, send a small program to
the data's location. Process data there, return only the result.
● Load Distribution: Spread computation across lightly loaded nodes.
● Reduce Latency: Move computation closer to where resources are located.
● Flexibility: Execute code where specific resources (devices, databases) are available.
● Client Software Updates: Server provides client implementation when client binds to it. Client does not
need to install all software.

Three Segments of a Process (Code Migration Framework)

Segment Contents Example

Code Segment The actual set of instructions Python script, compiled Java
being executed — the program bytecode, binary executable.
code itself.
Resource Segment References to external resources Reference to TCP port 8080;
 Segment Contents Example

needed by the process: files, reference to /data/[Link].

printers, devices, network ports,
databases, communication
endpoints.
Execution Segment Current execution state: private Variable x=42 currently on stack;
data (variables), stack contents, function call frames on execution
instruction pointer (program stack.
counter), register values.

Two Mobility Models: Weak vs Strong

Parameter Weak Mobility (Code Migration) Strong Mobility (Process
Migration)

What transfers? Code segment + initialized data Code + Execution segment (data,
only. stack, PC, registers).
Execution starts from? ALWAYS from beginning (fresh Exactly where it LEFT OFF at
start). source.
Execution state preserved? No. Yes.
Cost Low. High.
Example Java Applets (downloaded, run Process migration in HPC/cluster
fresh in browser). computing.
Heterogeneous system support Easy — just recompile code. Hard — must also migrate
execution stack.

Sender-Initiated vs Receiver-Initiated Migration

Type Who Initiates? Examples Applies To

Sender-Initiated Machine WHERE code Uploading a search Both strong and weak
currently resides initiates program to a DB server; mobility.
the transfer. uploading to a compute
server.
Receiver-Initiated TARGET machine takes Java applets downloaded Both strong and weak
the initiative to fetch the by web browser; mobility.
code. JavaScript fetched from
server.

Mobile Code Paradigms (The Cake Analogy)

📌 CAKE ANALOGY
Executing a task = Baking a cake. Code (Know-How) = Recipe. Movable Resources (RC) = Ingredients.
Non-movable Resources = Oven. Computational Component (CC) = Person to bake. All elements must
be co-located at the SAME site to bake the cake (execute the service).
 [ DIAGRAM: Mobile Code Paradigms — What Moves?
┌─────────────────┬───────────────────────────────────────────────────┐ │ Client-Server │
NOTHING moves. ││ CS │ A: request ──────────────────────────────► B
││ │ A: result ◄────────────────────────────── B │
├─────────────────┼───────────────────────────────────────────────────┤ │ Remote Eval REV
│ CODE moves A → B. Server executes at B. ││ │ A: Code
──────────────────────────────────► B │ │ │ A: result
◄────────────────────────────── B │
├─────────────────┼───────────────────────────────────────────────────┤ │Code on Demand
│ CODE moves B → A. Client executes at A. ││ CoD │ A: request
──────────────────────────────► B │ │ │ A: code
◄───────────────────────────────── B │
├─────────────────┼───────────────────────────────────────────────────┤ │ Mobile Agent │
ENTIRE agent moves A → B → C. ││ MA │ [Code+Data+State] ─────────────────► B
────► C │ └─────────────────┴───────────────────────────────────────────────────┘ ]
✏️ Draw this diagram in your exam answer

Paradigm What Moves? Direction Example

Client-Server (CS) NOTHING moves. Client Request A→B, Result Traditional HTTP web
sends request, server B→A request/response.
executes, returns result.
Remote Evaluation (REV) Code (Recipe) moves Code A→B, executed at Client sends query
FROM client TO server. B program to DB server to
Server executes with its run there.
own resources.
Code on Demand (CoD) Code (Recipe) moves Code B→A, executed at Java Applets, JavaScript.
FROM server TO client. A
Client executes locally.
Mobile Agent (MA) ENTIRE agent (Code + Agent moves A→B→C Autonomous web
Data + Execution State) crawlers; search agents
moves from site to site that travel to data
autonomously. sources.

Migration and Local Resources — Process-to-Resource Bindings

📌 KEY CHALLENGE
When code migrates, its resource segment contains references to external resources. These references
may no longer be valid at the new location. How to handle them depends on the TYPE of binding (by
identifier, by value, or by type).

Process-to-Resource Bindings (Fuggetta et al., 1998)

Binding Type What Does the Process Need? Example

Binding by Identifier The EXACT SPECIFIC resource Specific URL

identified by its unique ID. ([Link]
Nothing else will substitute. specific TCP port (IP:port); unique
 Binding Type What Does the Process Need? Example

file inode.
Binding by Value Only the CONTENT/VALUE Standard libraries (math, datetime
matters. Any resource providing in Python) — content matters, not
the same value works; location the exact file path.
can differ.
Binding by Type Only needs a resource of a References to local devices: needs
SPECIFIC TYPE — any instance of "a printer" (not a specific one);
that type at destination will do. needs "a display screen".

Resource-to-Machine Bindings (Types of Resources)

Resource Type Description Can It Move? Example

Unattached NOT tightly coupled to a YES — easy. Data files, temporary

machine. Can be moved files, user documents.
easily.
Fastened Tied to a machine but YES — but costly. Large database,
CAN be moved at high application data
cost (data volume, repository.
reconfiguration).
Fixed Permanently tied to a NO — cannot move. Local hardware: monitor,
specific physical printer, webcam,
machine. CANNOT be sensors.
moved.

Actions When Migrating — Combined Binding Matrix

Unattached Resource Fastened Resource Fixed Resource

By Identifier MV (move) or GR (global GR or MV (if feasible) GR (resource stays; give

reference) it a global name)
By Value CP (copy) or MV or GR GR or CP GR
By Type RB (rebind to local RB or GR or CP RB or GR
resource of same type)
or GR or CP

Legend: GR = Global Reference | MV = Move resource | CP = Copy resource | RB = Rebind to local resource

📌 EXAMPLE 1 — Binding by Value

Migrating a Python script that uses the math module from Server A to Server B: You do NOT need to
migrate /usr/lib/python3.9/[Link] from A. Server B already has its own math module (possibly at a
different path). Since binding is BY VALUE, the script works fine at Server B. Action: GR or locally
available standard library.

📌 EXAMPLE 2 — Binding by Identifier

 A process holds TCP port 8080 on Machine A. When migrated, port 8080 may already be in use on
Machine B. The process needs that SPECIFIC port (binding by identifier). Solution: Give up old port,
request a new TCP port at B, and establish a GR (global reference with new IP:port).

Migration in Heterogeneous Systems

System Type Description Translation Needed?

Homogeneous Source and destination use SAME NO — direct migration possible.

CPU architecture and OS. Data
interpretation is consistent.
Heterogeneous Source and destination have YES — must translate data from
DIFFERENT CPU architectures or source CPU format to destination
OS. Data formats may differ. CPU format.

For n CPU types: Need n×(n−1) pieces of translation software to handle all source-destination pairs → O(n²)
complexity.
Solution — External Data Representation (XDR/ASN.1): Use a standard intermediate representation. Each node
converts TO and FROM the standard form. Reduces complexity from O(n²) to O(n) — only 2 conversion
programs per CPU type.

[ DIAGRAM: Translation without External Representation (n=4 CPU types): CPU1 ──► 3 conversions to
──► CPU2, CPU3, CPU4 CPU2 ──► 3 conversions to ──► CPU1, CPU3, CPU4 CPU3, CPU4 similarly Total
= 4×3 = 12 conversion programs Translation WITH External Representation (XDR): CPU1 ──► XDR format
──► CPU2, CPU3, CPU4 Each CPU needs only 2 programs: (to XDR) and (from XDR) Total = 4×2 = 8
programs (much less for large n) ]
✏️ Draw this diagram in your exam answer

Threads in Distributed Systems

A thread is a lightweight process — a flow of control through an address space. Each address space can have
MULTIPLE concurrent control flows (threads), and each thread has access to the ENTIRE address space.

Thread Models

[ DIAGRAM: Thread Models — Server Architecture Dispatcher-Workers Model: Team Model:

Pipeline Model: ┌─────────────────────────┐ ┌─────────────────────┐
┌─────────────────────┐ │ Server Process │ │ Server Process │ │ Server Process │ │
┌──────────────────┐ │ │ ┌───┐ ┌───┐ ┌───┐ │ │ [T1]→[T2]→[T3] │ │ │ Dispatcher Thread│ │ │
│T1 │ │T2 │ │T3 │ │ │ Input→Step1→Step2 │ │ └────────┬─────────┘ │ │ └───┘ └───┘ └───┘ │ │
→Step3→Output │ │ ┌──┐ ┌──┐ ┌──┐ │ │ All equal-rank │ └─────────────────────┘ │ │W1│
│W2│ │W3│ │ │ threads │ │ └──┘ └──┘ └──┘ │ └─────────────────────┘
└─────────────────────────┘ ]
✏️ Draw this diagram in your exam answer
 Model Description Use Case

Dispatcher-Workers ONE dispatcher thread + multiple General-purpose servers handling

worker threads. Dispatcher multiple concurrent client
accepts requests, dispatches to a requests.
free worker. Each worker handles
one request in parallel.
Team Model ALL threads are equal — no Servers where different request
dispatcher-worker hierarchy. Each types need different specialized
thread independently gets and handling.
processes client requests. Each
thread specialized for a specific
request type.
Pipeline Model Threads organized in a pipeline Applications with sequential
(producer-consumer chain). processing stages (data processing
Output of Thread 1 → input of pipelines, streaming).
Thread 2 → etc. Final thread
produces final output.

Process vs Thread: Comparison

Parameter Process Thread

Definition Basic unit of CPU utilization in Basic unit of CPU utilization in

traditional OS. threaded OS (lightweight process).
Parameters Owned Own program counter, registers, Own PC, registers, stack. SHARES
stack, and address space. address space with other threads.
Protection Needs protection (separate No protection needed (shared
address spaces). address space — implicit trust
between threads).
Weight Heavyweight. Lightweight.
Resource Sharing Less efficient (separate memory More efficient (shared memory —
spaces). no copying required).
Switching Cost Expensive (address space switch, Cheap (just register and stack
TLB flush). switch within same address
space).
Creation Overhead High (allocate new address space, Low (no new address space
copy OS resources). needed).
CHAPTER 4.3 — DEADLOCK DETECTION IN DISTRIBUTED SYSTEMS

Introduction to Deadlocks
A deadlock occurs when a set of processes are permanently blocked, each waiting for resources held by others,
and none can make progress.

Coffman's Four Necessary Conditions for Deadlock

📌 EXAM TIP
Deadlock occurs IF AND ONLY IF ALL FOUR conditions hold simultaneously. Breaking even ONE
condition prevents deadlock.

Condition Description How to Break It

1. Mutual Exclusion Only ONE process can use a Allow resource sharing where
resource at a time. Resources possible.
cannot be shared concurrently.
2. Hold and Wait A process HOLDING resources is Require processes to request ALL
WAITING for additional resources resources at once before starting
currently held by others. (Collective Request).
3. No Preemption A resource can ONLY be released Allow preemption — forcibly take
VOLUNTARILY by the holding resources from blocked processes.
process after task completion.
4. Circular Wait A circular chain: P0 waits for P1, Impose total ordering —
P1 waits for P2, ..., Pn waits for P0. processes must request resources
in increasing order (Ordered
Request).

Resource Allocation Graph (RAG)

A bipartite directed graph with two types of nodes: Process nodes (circles) and Resource nodes (rectangles).
Instances shown as dots inside rectangles.

[ DIAGRAM: Resource Allocation Graph (RAG) Notation REQUEST EDGE: Pi

──────────────────────────────► Rj (Process Pi is WAITING for resource Rj)
ASSIGNMENT EDGE: Rj ──────────────────────────────► Pi (Instance of Rj is HELD BY
process Pi) [Resource Rj] = rectangle with dots (instances) [Process Pi] = circle RAG WITH
DEADLOCK: RAG WITH CYCLE, NO DEADLOCK: R1 ────► P1 ───► R2 ────► P2 R1 has 2
instances ▲ │ P1 holds one instance └──────────────────────────┘ P3 holds
another instance (Cycle = Deadlock if 1 instance) P2 waiting → can get from P3
(Multiple instances → no deadlock) ]
✏️ Draw this diagram in your exam answer
Graph State Deadlock?

No cycle in RAG NO deadlock is possible.

Cycle exists AND each resource type has ONLY ONE DEADLOCK is certain.
INSTANCE
Cycle exists AND some resource types have POSSIBILITY of deadlock — not certain. Need further
MULTIPLE INSTANCES analysis.

Types of Distributed Deadlocks

Type Description Example Model Used

Resource Deadlock Two or more processes P1 holds R1, waits for R2. AND Model
wait PERMANENTLY for P2 holds R2, waits for R1.
resources held by each Both wait forever.
other. Each holds some
resources while waiting
for more.
Communication Processes wait for P1 waits for message OR Model
Deadlock messages from each from P2. P2 waits from
other but none can send P3. P3 waits from P1. All
because all are waiting. idle forever.
No messages are in
transit.

[ DIAGRAM: Resource Deadlock (AND Model): Resource1 ◄── Assigned ── Process1 │ │

Waiting Waiting ▼ ▼ Process2 ──── Assigned ──► Resource2 (Circular: P1
holds R1 waits R2; P2 holds R2 waits R1) Communication Deadlock (OR Model): P1 ─── waiting for msg
from ───► P2 ▲ │ │ waiting for msg from │ ▼
└───── waiting for msg from ─── P3 (All 3 waiting; no one sending any message) ]
✏️ Draw this diagram in your exam answer

Deadlock Models: AND Model and OR Model

AND Model

📌 AND Condition
A process can proceed ONLY when it has acquired ALL of its requested resources simultaneously. All
requests must be satisfied before the process can continue.

● Models: Resource Deadlock.

● Out-degree in WFG: Can be > 1 (process waits for multiple resources simultaneously — ALL must be
granted).
● Deadlock Condition: Existence of a CYCLE in the Wait-For Graph (WFG).
 ● Important: A process NOT in any cycle can STILL be deadlocked if it is dependent on a deadlocked
process.

OR Model

📌 OR Condition
A process can proceed when it has acquired AT LEAST ONE of its requested resources. Any single
request being satisfied is enough for the process to continue.

● Models: Communication Deadlock.

● Deadlock Condition: Existence of a KNOT in the Wait-For Graph (WFG). A cycle alone is NOT sufficient.
● Why cycle alone isn't enough? Even if a cycle exists, a process can break out if ANY external (non-cycle)
process sends it a message. The cycle only becomes a deadlock if there is NO way out.

Cycle vs Knot — THE KEY CONCEPT

📌 KNOT DEFINITION
A knot K is a set of nodes in the WFG such that: for EVERY node "a" in K, ALL nodes reachable from "a"
are EXACTLY the nodes in K and ONLY those nodes. Once inside a knot, you can NEVER ESCAPE — all
paths lead back into K with no exit to external nodes.

Criterion AND Model OR Model

Deadlock Condition CYCLE in WFG KNOT in WFG

Cycle present → Deadlock? YES — Cycle is both necessary NO — Cycle is necessary but NOT
AND sufficient sufficient (need knot)
Knot present → Deadlock? YES (knot implies cycle) YES — Knot is sufficient for
deadlock
Type of deadlock Resource Deadlock Communication Deadlock
Process condition Needs ALL resources (all WFG Needs ANY ONE resource (any
edges must resolve) single edge resolving is enough)

[ DIAGRAM: AND Model vs OR Model — Same WFG, Different Outcomes WFG: P11 ─► P21 ─► P24 ─►
P54 ▲ │ └──────────────────────┘ (cycle) P44 ─► P24 (depends on cycle member)
P33 ─► P32 (external to cycle) P32 ─► P11 (connects to cycle) AND Model Analysis: Cycle:
P11→P21→P24→P54→P11 → DEADLOCK (AND) P44 depends on P24 (deadlocked) → P44 is ALSO
deadlocked Even though P44 is not in the cycle! OR Model Analysis: Same cycle exists, but: P33 is NOT
in the cycle. When P33 finishes: → P32 gets unblocked (only ONE of its OR requests needs to be satisfied)
→ After P32 finishes, P11 can proceed (one request satisfied) → Cycle exists but NO DEADLOCK (escape
path through P33 exists) Therefore: cycle ≠ deadlock in OR model ]
✏️ Draw this diagram in your exam answer
 Deadlock Handling Strategies
Strategy Core Idea Techniques

Deadlock Prevention Eliminate ONE of Coffman's 4 (1) Ordered Request: Resources

conditions to make deadlock ordered globally; request in
structurally impossible. INCREASING order → no circular
wait. (2) Collective Request:
Request ALL resources before
execution; none allocated if any
unavailable → prevents Hold &
Wait. (3) Timestamp-based:
Process waits only if it has a
SMALLER (older) timestamp than
holder → no cycles.
Deadlock Avoidance Allow requests but only grant Banker's Algorithm: Track
them if system remains in a "safe allocation, maximum need,
state" (deadlock-free). available resources. Grant request
only if safe sequence exists. Use
"claim edges" in RAG for future
requests.
Deadlock Detection & Recovery Allow deadlocks to occur. Detect cycles/knots in WFG. Kill
Periodically detect them. Then one process to break deadlock.
break the deadlock. Roll back transactions.
Approaches: Centralized,
Hierarchical, Distributed (CMH
Algorithm).

Control Organization for Deadlock Detection

Approach Description Advantages Disadvantages

Centralized ONE coordinator Simple; coordinator has Single point of failure;

maintains the GLOBAL complete global view. bottleneck in large
WFG. Each machine systems; Phantom
sends local graph deadlocks possible.
updates to coordinator.
Coordinator detects
cycles and kills a process.
Hierarchical Nodes organized in a No single point of failure; More complex;
TREE. Each parent better scalability. hierarchical coordination
handles detection for its overhead.
cluster. Deadlocks
spanning clusters
escalate up the
hierarchy.
Distributed ALL nodes participate No single point of failure; More complex
equally. No single fast detection; highly algorithms; coordination
coordinator. Uses scalable. overhead.
algorithms like CMH.
📌 PHANTOM (FALSE) DEADLOCKS
In centralized detection: the coordinator may detect a "deadlock" that doesn't actually exist. Messages
travel with delays, so the coordinator may receive out-of-order/stale info creating an apparent cycle
that no longer exists. Solution: Use Lamport's Algorithm. When coordinator suspects deadlock at
timestamp T, it queries all nodes: "Any pending message with timestamp < T?" Only after ALL nodes
confirm NO earlier pending messages does it declare an actual deadlock.
 Chandy-Misra-Haas (CMH) Algorithm
📌 TYPE
Distributed deadlock detection algorithm using EDGE CHASING technique. A special message called a
PROBE is circulated through WFG edges to detect cycles/knots. No global graph construction is needed.

Key Terminologies
Term Definition

Probe (i, j, k) A 3-integer triplet message meaning: Process Pi

INITIATED the detection. Message sent BY home site
of Pj TO home site of Pk. Travels along outgoing WFG
edges.
Dependent Process Pi is dependent on Pj if there exists a sequence Pi,
Pi1, Pi2, ..., Pj where each process (except Pj) is
BLOCKED and each holds a resource that the
previous process is waiting for.
Locally Dependent Pi is locally dependent on Pj if Pi is dependent on Pj
AND both Pi and Pj are at the SAME SITE (same
machine).
Edge Chasing The probe message "chases" along the edges of the
WFG. When a blocked process receives a probe, it
forwards it along its outgoing WFG edges.

Data Structure
● Boolean array dependent_i[0..n-1] maintained by EACH SITE.
● Initially: dependent_i[j] = FALSE for all i and j.
● Meaning: dependent_i[j] = TRUE means process Pj is dependent on process Pi (according to information
available at Pi's home site).

Algorithm Steps

[ DIAGRAM: CMH Algorithm — Flowchart Step 1: INITIATION Blocked process Pi wants to check for
deadlock: FOR EACH process Pj that Pi is waiting for: SEND probe(i, i, j) to home site of Pj Step 2:
RECEIVING probe(i, j, k) at site of Pk IF (Pk is BLOCKED) AND (dependent_k[j] == FALSE): SET
dependent_k[j] = TRUE IF (k == i): ← PROBE RETURNED TO INITIATOR! → DEADLOCK
DETECTED! Pi declares itself deadlocked. ELSE: FOR EACH process Pm that Pk is waiting for:
SEND probe(i, k, m) to home site of Pm (If Pk is NOT blocked OR dependent_k[j] already TRUE: DISCARD
probe) ]
✏️ Draw this diagram in your exam answer
SOLVED EXAMPLE — CMH Algorithm (From Professor's Slides)

📌 SETUP
3 machines, 9 processes. Machine 0: P0, P4, P6. Machine 1: P1, P2, P3, P8. Machine 2: P5, P7. Wait
relationships: P0 waits for P4 AND P2 | P2 waits for P3 | P4 waits for P6 | P6 waits for P8 (cross-site) |
P8 waits for P0 (forms cycle back to initiator).

[ DIAGRAM: CMH Example — Wait-For Graph (WFG) Machine 0 Machine 1 Machine 2

[P0, P4, P6] [P1, P2, P3, P8] [P5, P7] │ │ P0 ──────────────────► P2 ──► P3
P0 ──────────────► P4 P4 ──────────────────► P6 P6 ──────────────────────────► P8 (cross-
site: M0→M1) P8 ──────────────────────────────────────────────► P0 (Forms cycle:
P0→P4→P6→P8→P0) ]
✏️ Draw this diagram in your exam answer

Step Action Probe Sent Description

1 P0 initiates deadlock probe(0,0,4) to Machine P0 is blocked waiting for

detection (P0 is blocked) 0; probe(0,0,2) to P4 and P2. Sends probes
Machine 1 to both.
2 Machine 0 receives probe(0,4,6) to Machine P4 is blocked waiting for
probe(0,0,4). Pk=P4, P4 0 P6. Set
is blocked. dependent_4[0]=TRUE.
Forward to P6.
3 Machine 1 receives probe(0,2,3) to Machine P2 is blocked waiting for
probe(0,0,2). Pk=P2, P2 1 P3. Set
is blocked. dependent_2[0]=TRUE.
Forward to P3.
4 Machine 0 receives probe(0,6,8) to Machine P6 is blocked waiting for
probe(0,4,6). Pk=P6, P6 1 P8 (on Machine 1). Set
is blocked. dependent_6[4]=TRUE.
Forward.
5 Machine 1 receives (P3 not blocked; probe P3 is NOT blocked (or no
probe(0,2,3). Pk=P3. discarded) outgoing edges). Probe
terminates here.
6 Machine 1 receives probe(0,8,0) to Machine P8 is blocked waiting for
probe(0,6,8). Pk=P8, P8 0 P0. Set
is blocked. dependent_8[6]=TRUE.
Sends probe to P0.
7 Machine 0 receives ⚠ DEADLOCK P0 receives its OWN
probe(0,8,0). Pk=P0, k==i DETECTED! probe back! k==i means
(k=0=i=0) cycle is complete. P0
declares DEADLOCK.

📌 DEADLOCK RESOLUTION
Strategy 1 (Naive): Initiating process (P0) commits suicide. Problem: Multiple processes might
simultaneously initiate probes → all commit suicide ("overkilling"). Strategy 2 (Better): Each process
 APPENDS ITS OWN ID to the probe as it travels. When probe returns to initiator, it has IDs of ALL
processes in the cycle. Kill the process with the HIGHEST process ID. All concurrent probes will agree on
the SAME victim, so only ONE process is killed.

Performance of CMH Algorithm

Metric Formula / Value Note

Maximum messages exchanged m(n−1)/2 m = number of processes, n =

number of sites.
Delay in detecting deadlock O(n) n = number of sites — detection
delay grows linearly.

Advantages vs Disadvantages of CMH Algorithm

Advantages Disadvantages

Simple probe message (just 3 integers) + small All sites may not be fully aware of which processes
boolean array. are involved.
Very little computation required at each site. Resolving the deadlock can be difficult (choosing
which process to kill).
Low communication overhead — only edge chasing. Correctness proof is mathematically complex.
No need to construct a global WFG.
Does NOT report phantom/false deadlocks (unlike
centralized).
No single point of failure — fully distributed.
Fast detection — O(n) delay.
QUICK REVISION TABLES

1. Load Balancing vs Load Sharing

Parameter Load Balancing Load Sharing

Goal Equalize workload on ALL nodes Prevent any node from being idle
Complexity High Low
Overhead High (extensive state info) Low (only busy/idle status)
Threshold High-Low double threshold Single threshold = 1 (all-or-
nothing)
Is perfect balance achievable? Theoretically yes, practically no No — just prevents idleness
Concept Type Dynamic Simpler dynamic

2. AND Model vs OR Model

Parameter AND Model OR Model

Condition to Unblock Needs ALL requested resources Needs ANY ONE requested
resource
Deadlock Condition CYCLE in WFG KNOT in WFG
Cycle → Deadlock? YES (necessary & sufficient) NO (necessary but not sufficient)
Knot → Deadlock? YES (knot implies cycle) YES (sufficient)
Type of Deadlock Resource Deadlock Communication Deadlock

3. Weak vs Strong Mobility

Parameter Weak Mobility Strong Mobility

What transfers? Code + initialized data only Code + Execution state (data,
stack, PC, registers)
Starts from? BEGINNING (fresh start) Exactly where it left off
Execution state? Not preserved Preserved
Cost Low High
Example Java Applets, JavaScript Process migration in clusters
 4. Mobile Code Paradigms
Paradigm What Moves Direction Example

Client-Server (CS) Nothing Request A→B, Result HTTP web request

B→A
Remote Evaluation (REV) Code (recipe) Code A→B, executed at Send DB query to DB
B server
Code on Demand (CoD) Code (recipe) Code B→A, executed at Java Applets, JavaScript
A
Mobile Agent (MA) Entire agent Agent moves A→B→C Autonomous web
(code+data+state) crawlers

5. Process-to-Resource Binding Actions

Unattached Resource Fastened Resource Fixed Resource

By Identifier MV or GR GR or MV GR
By Value CP or MV or GR GR or CP GR
By Type RB or GR or CP RB or GR or CP RB or GR

Legend: GR=Global Reference | MV=Move resource | CP=Copy resource | RB=Rebind to local resource

6. Deadlock Detection Approaches

Parameter Centralized Hierarchical Distributed (CMH)

Single point of failure? YES Partial NO

Phantom deadlocks? Possible (need Lamport Possible NO
fix)
Global graph needed? Yes Partial No (probe chasing)
Scalability Poor Medium Good
Algorithm Coordinator Cluster-based hierarchy Probe-based edge
polls/receives chasing (CMH)

7. CMH Algorithm Summary

Aspect Detail

Type Distributed edge-chasing deadlock detection.

Special message Probe (i, j, k): i=initiator, j=sender site, k=receiver
site.
Data structure Boolean 2D array dependent_i[j] per site.
Aspect Detail

When initiated? When blocked process Pi wants to check for

deadlock.
How detected? Probe returns to initiator (k == i in received probe).
Maximum messages m(n−1)/2 where m=processes, n=sites.
Detection delay O(n) where n=number of sites.
Phantom deadlocks? NO.
Deadlock resolution Kill process with highest ID (agreed by all concurrent
probes).

END OF MODULE 4 NOTES

Distributed Computing | University of Mumbai | BE Computer Engineering Semester 8