Chapter 4

Resource and Process Management

1
 Introduction
• Distributed systems contain a set of resources
interconnected by a network
• Processes are migrated to fulfill their resource
requirements
• Resource manager are to control the assignment of
resources to processes
• Resources can be logical (shared file) or physical
(CPU)
• We consider a resource to be a processor
2
System Calls for Process Management
 Process Management
• Process migration
– Freeze the process on the source node and restart it at the
destination node
– Transfer of the process address space
– Forwarding messages meant for the migrant process
– Handling communication between cooperating processes
separated as a result of migration
– Handling child processes

• Process migration in heterogeneous systems

 Process Migration
• Transfer of sufficient amount of the state
of a process from one computer to
another
• The process executes on the target
machine

5
 Motivation
• Load sharing
– Move processes from heavily loaded to
lightly load systems
• Communications performance
– Processes that interact intensively can be
moved to the same node to reduce
communications cost
– May be better to move process to where the
data reside when the data is large
6
 Motivation
• Availability
– Long-running process may need to move
because the machine it is running on will be
down
• Utilizing special capabilities
– Process can take advantage of unique
hardware or software capabilities

7
 Initiation of Migration
• Operating system
– When goal is load balancing
• Process
– When goal is to reach a particular resource

8
 What is Migrated?
• Must destroy the process on the source
system and create it on the target system
• Process image and process control block
and any links must be moved

9
Example of Process Migration

10
Example of Process Migration

11
 What is Migrated?
• Eager (all):Transfer entire address space
– No trace of process is left behind
– If address space is large and if the process
does not need most of it, then this approach
my be unnecessarily expensive

12
 What is Migrated?
• Precopy: Process continues to execute
on the source node while the address
space is copied
– Pages modified on the source during
precopy operation have to be copied a
second time
– Reduces the time that a process is frozen
and cannot execute during migration

13
 What is Migrated?
• Eager (dirty): Transfer only that portion
of the address space that is in main
memory and have been modified
– Any additional blocks of the virtual address
space are transferred on demand
– The source machine is involved throughout
the life of the process

14
 What is Migrated?
• Copy-on-reference: Pages are only
brought over when referenced
– Has lowest initial cost of process migration
• Flushing: Pages are cleared from main
memory by flushing dirty pages to disk
– Relieves the source of holding any pages of
the migrated process in main memory

15
 Negotiation of Migration
• Migration policy is responsibility of
Starter utility
• Starter utility is also responsible for
long-term scheduling and memory
allocation
• Decision to migrate must be reached
jointly by two Starter processes (one on
the source and one on the destination)

16
17
 Eviction
• Destination system may refuse to accept
the migration of a process to itself
• If a workstation is idle, process may
have been migrated to it
– Once the workstation is active, it may be
necessary to evict the migrated processes to
provide adequate response time

18
• Users not aware of multiplicity of machines
– Access to remote resources similar to access to local
resources
• Data Migration – transfer data by transferring entire
file, or transferring only those portions of the file
necessary for the immediate task
• Computation Migration – transfer the computation,
rather than the data, across the system
– Via remote procedure calls (RPCs)
– or via messaging system
 Resource Management
 A resource can be a logical, such as a shared file, or physical, such as a CPU (a
node of the distributed system).
 One of the functions of a distributed operating system is to assign processes to
the nodes (resources) of the distributed system such that the resource usage,
response time, network congestion, and scheduling overhead are optimized.
 There are three techniques for scheduling processes of a distributed
system:
1) Task Assignment Approach, in which each process submitted by a user for
processing is viewed as a collection of related tasks and these tasks are
scheduled to suitable nodes so as to improve performance.
2) Load-balancing approach, in which all the processes submitted by the
users are distributed among the nodes of the system so as to equalize the
workload among the nodes.
3) Load-sharing approach, which simply attempts to conserve the ability of
the system to perform work by assuring that no node is idle while processes
wait for being processed.
The task assignment approach has limited applicability to practical situations
because it works on the assumption that the characteristics (e.g. execution
time, IPC costs etc) of all the processes to be scheduled are known in advance.
 Definition
• Load balancing is the process of improving the
performance of a parallel and distributed system
through a redistribution of load among the
processors.
• Distributed Scheduling
– Resource management component of a system which
moves jobs around the processors to balance load and
maximize overall performance.
– Typically makes sense in LAN level distributed systems
due to latency concerns.
– Needed because of uneven distribution of tasks on
individual processors
• Can be due to several reasons.
• Can even make sense for homogeneous systems with (on
average) even loads.
• How does one characterize
– Performance : average response time
– Load:
• It has been shown that queue lengths for resources (e.g. CPUs)
can be a good indicator.
• How does one handle the delay of transfer when systems are
unevenly loaded and we seek to rectify that ?
– Timeouts, holddowns
• Queue length not very appropriate for (nor correlated with)
CPU utilization for some tasks (e.g. interactive).
 Types of Load Balancing Algorithms
(Draw diagrams from Textbook in Syllabus)
Who Initialized the load balancing algorithm ?
• Sender Initiated
– Initialized by the sender.
– Sender sends request messages till it finds a receiver
that can accept the load.

• Receiver Initiated
– Initiated by the receiver.
– Receiver sends request messages till it finds a sender
that can get the load.
• Load balancing approaches further classified as:
– Static: Decisions are “hard wired” a-priori into the
system based on designers understanding.
– Dynamic: Maintain state information for the
system and make decisions based on them. Better
than static, but have more overhead.
– Adaptive: A subtype of dynamic, they can change
the parameters they analyze based on system load.
 Static Load Balancing
• The performance of the processors is determined at
the beginning of execution.

• Master processor and slave processors.

• A task is always executed on the processor to

which it is assigned.
• Reduce the execution time, minimizing the
communication delays
 Static Algorithms
• Round Robin Algorithm
– Processor choosing is performed in series
and will be back to the first processor if the
last processor has been reached.

• Randomized Algorithm
– Uses random numbers to choose slave
processors based on statistics .
 Static Algorithms Cont…

• Central Manager Algorithm

– The central processor is able to gather all slave
processors load information
– The chosen slave processor is the processor
having the least load
• Threshold Algorithm
– The processes are assigned immediately upon
creation to hosts.
– Under loaded, medium and overloaded.
 Dynamic Load Balancing
• Dynamic algorithms allocate processes
dynamically when one of the processors
becomes under loaded.

• Buffered in the queue

• Allocated dynamically upon requests

from remote hosts
 Dynamic Load Balancing
• Dynamic algorithms allocate processes
dynamically when one of the processors
becomes under loaded.

• Buffered in the queue

• Allocated dynamically upon requests

from remote hosts
 Dynamic Load Balancing Algorithms
• Central Queue
– Stores new activities and unfulfilled requests as a cyclic
FIFO queue on the main host.

• Local Queue

• A parameter defines the minimal number of ready

processes the load manager attempts to provide on
each processor
 Performance Analysis of Load
Balancing Algorithms
• Adaptability
– Static No, Dynamic Yes
• Predictability
– Static Yes, Dynamic No
• Waiting Time (Queuing time )

• Execution System
 Types of Load Balancing
Algorithms
Who Initialized the load balancing algorithm ?
• Sender Initiated
– Initialized by the sender.
– Sender sends request messages till it finds a receiver
that can accept the load.

• Receiver Initiated
– Initiated by the receiver.
– Receiver sends request messages till it finds a sender
that can get the load.
• Transfers may be preemptive or non-preemptive
– Preemptive transfers involve transferring execution state
as well as the task. Non-preemptive transfers are
essentially “placements”
• Load Distribution System Components
– Transfer policy: Which node should send, who should
receive (threshold based approaches are common)
– Selection policy: Which task should be moved (new
tasks, location independent tasks, long running tasks …)
– Location Policy: Finding a receiver for a task. Typical
approaches are polling or broadcast.
– Information Policy
• Demand driven, Periodic, or State Change driven
• Stability in a load sharing system
– Queuing Theoretic: When total work arrival (tasks + load
sharing overhead) is greater than rate at which CPU can
work. Alternatively, look at the effectiveness of the
algorithm.
– Algorithmic : Does the algorithm lead to thrashing ?
 Sender Initiated LD Algorithms
• The overloaded node attempts to send tasks to
lightly loaded node
– Transfer Policy: If new Tasks takes you above threshold,
become sender. If receiving task will not lead to crossing
over threshold, then become receiver
– Selection Policy: Newly arrived tasks
– Location Policy
• Random – still better than no sharing. Constrain by limiting the
number of transfers
• Threshold – chose nodes randomly but poll them before
sending task. Limited no. of polls. If process fails execute
locally.
• Shortest – Poll all randomly selected nodes and transfer to least
loaded. Doesn’t improve much over threshold.
– Information Policy, Stability
 Receiver initiated
• Load sharing process initiated by a lightly
loaded node
– Transfer Policy: Threshold based.
– Selection Policy: Can be anything
– Location Policy: Receiver selects upto N nodes
and polls them, transferring task from the first
sender. If none are found, wait for a
predetermined time, check load and try again
– Information Policy
– Stability: At high loads, few polls needed since
senders easy to find. At low loads, more polls
but not a problem. However, transfers will tend
to be preemptive.
 Symmetric Algorithms
– Simple idea – combine the previous two. One works well
at high loads, the other at low loads.
– Above Average Algorithm: Keep load within a range
• Transfer Policy: maintain 2 thresholds equidistant from
average. Nodes with load > upper are senders, Nodes with load
< lower are receivers.
• Location Policy: Sender Initiated:
– Sender broadcasts “too high” message and sets up too high
alarm
– Receiver getting toohigh message replies with accept,
cancels its too low alarm, starts an awaiting task alarm, and
increments load value
– Sender which gets accept message will transfer task as
appropriate. If it gets too low message, it responds with a
too high to the sender.
– If no accept has been received within timeout, send out
• Location Policy: Receiver Initiated
–A receiver broadcasts a too low message
and sets too low alarm.
–Upon receiving too high message, do as in
sender initiated
–If too low alarm expires, send change
average message
• Selection Policy
• Information Policy is demand driven, and has
low overhead. Each node can change the range
individually.
 Adaptive Algorithms
• Stable Symmetric Algorithm.
– Use information gathered during polling to change behaviour. Start
by assuming that everyone is a receiver.
– Transfer Policy: Range based with Uppper and Lower Threshold
– Location Policy: Sender Initiated component polls node at head of
receiver list. Depending on answer, either a task is transferred or
node moved to OK or sender list. Same thing happens at the
receiving end. Receiver initiated component polls senders list in
order, OK list and receivers list in reverse order. Nodes are moved
in and out of lists at sender and receiver.
– Selection Policy – any, Information Policy – Demand driven
– At high loads, receiver lists get empty preventing future polling
and “deactivating” sender component. At low loads, receiver
initiated polling is deactivated, but not before updating receiver
lists.
 Requirements for load
distribution
• Scalability
• Location Transparency
• Determinism
• Preemption
• Heterogeniety
 Case Studies
• V System
– Measure system parameters and broadcast.
Each node caches “n best” nodes to migrate a
job to. When it gets a new job, checks if it is in
“ n best” else migrate to one of the others
• Sprite
– Receivers notify coordinator of status. Sender
selects jobs manually. Preemptive transfers to
provide “console user” with best service.
• Task Migration Issues
– Policy mechanism separation, state transfer and
restarts, location transparency, performance
 Code Migration

• Why Code Migration?

• Code Migration Models
• Migration and Handling Resources
• Heterogeneous Systems
• Migration Security
 Why Code Migration?
• Process Migration - definition
– Transfer an entire running process from one
machine to another
• Load distribution
• Measured by CPU queue length or utilization
• Good for computational systems
• Reduce Network Bandwidth
– Migrate part of client application to server
• Migrate part of client application to database server to
perform many database operations
• Send only result across network
 Why Code Migration?
• Reduce Network Bandwidth
– Migrate part of server application to client
• Migrate part of database server to client to process
forms on client side
• Reduces database operations over the network
• XSS - Javascript
• Parallelism
– Mobile Agent
• Dynamic Configuration of Distributed
Systems
– Download and Initialize Code
 Code Migration Models
⚫Code Migration Framework
− Code Segment
⚫Set of instructions being executed
− Resource Segment
⚫References to external resources
⚫Files, printers, devices, et cetera
− Execution Segment
⚫Process state
⚫Private data
⚫Stack
⚫Instruction pointer
 Code Migration Models

• Weak Mobility
– Transfer code segment and initialized data
– Portable code
– Predefined starting positions
• Java Applets
• Strong Mobility
– Transfer includes execution segment
– Process can be stopped, moved to another
machine, and resumed
 Code Migration Models

• Sender-initiated
– Code transfer is initiated by machine currently
executing the code
– Example
• Uploading programs to a computational server
• Receiver-initiated
– Transfer is initiated by machine that will execute
code
– Example
• Java applets
 Handling Resources

• Process-to-resource binding
– Binding by identifier (strong)
• Process refers to resources by their identifiers
• Example
– URL
– Binding by value (weaker)
• Process refers to another resource with the same value
– Binding by type (weakest)
• Process refers to local devices
 Handling Resources

• Resource-to-machine binding
– Unattached resources
• Can be moved easily
– Data Files
– Fastened resources
• Can be moved at high cost
– Database
– Fixed resources
• Cannot be moved
– Local devices
 Heterogeneous Systems

• Heterogeneous systems are platforms with

different operating systems and/or different
machine architectures
• Problems with heterogeneous systems is
similar to those of portability
• Solutions
– Highly portable languages
• Scripting languages, interpreted languages (Java)
– Migrating computing environments
– Migrating virtual machines
 Migration Security
• Protecting mobile agents
– need to protect sensitive data
• Three mechanisms for securing mobile
agents
– Read-only state
• Data items are signed by agent's owner
– Append-only state
• Data can only be appended to logs
– Selective reading
• Each data entry can only be updated by selected
servers
 Migration Security

• Protecting hosts against malicious mobile

code
– Sandbox
• Monitor specific instructions, registers, memory
regions
• Easier to do with interpreted languages
– Java sandbox
– Playground
• Separate machines exist to execute mobile code
– Code-signing
– Stack introspection