Resource Management

Resource Management Distributed Operating Systems

Types of scheduling algorithm • Task Assignment approach • Process viewed as collection of related tasks • Tasks assigned to different nodes for optimization

• Load Balancing approach • Processes are distributed to equalize workload

• Load Sharing approach • No node is idle while processes are waiting

Features of good global Scheduling algorithm • • • • • • • •

No prior knowledge about the processes Dynamic in nature Quick decision making capability Balanced system performance and scheduling overhead Stability (No processor trashing) Scalability (Handle small and large networks) Fault tolerance Fairness service

Task assignment approach Assumptions • Process split into tasks • Computation and speed each processor is known • Cost of processing each task in each node is known • IPC cost between every pair of tasks is known • Resource requirements for each task is known • Reassignment is not possible

Goals… • Minimize IPC costs • Quick turnaround time for the complete process • High degree of parallelism • Efficient usage of system resources

Finding optimal assignment • Use assignment graph • Find cutset • Find minimum weight cutset

Load balancing Algorithms Static

Deterministic Probabilistic

Dynamic Centralized Cooperative

Distributed Noncooperative

Static Vs Dynamic • Static algorithms use only average information about the system

• Dynamic algorithms use current state of the system

Deterministic Vs Probabilistic • Deterministic algorithms use info about the properties of nodes and characteristics of the processes • Probabilistic algorithms use info regarding static attributes of the system(like number of nodes, processing capabilities of the nodes etc)

Centralized • Scheduling done on a centralize server node • Replication necessary • Alternative method of reinstantiation to improve the reliability with cost of delay of several seconds • Single server with k entities monitoring it • When fault is detected new instance of server is started and reconstructs its state info

Distributed Algorithms • Non Cooperative : individual entities make decisions independently

Issues in load balancing algo • • • • • •

Load estimation policies Process transfer policies Location policies State information policies Priority assignment policies Migration limiting policies

Load Estimation policies • Balance workload on all the nodes • Parameters – Total number of processes on the node at the time of load estimation – Resource demand of these process – Architecture and speed of the node’s processor

• Better parameter : Sum of remaining service times of all process on that node • Method to calculate the remaining service time – Memoryless method : Same expected remaining time for all the processes – Pastrepeats : Remaining time is equal to the time used so far – Distribution method : If service time is known, remaining time is calculated.

Process Transfer policies • Concept of threshold policy • Threshold : limiting value of the node’s workload • Methods to determine the threshold value – Static policy • Predefined threshold value • Value does not vary • No exchange of information between the nodes

– Dynamic policy • Calculated as product of average workload of the nodes by a constant figure ci • Ci depends on the processing capability of the node relative to other nodes • Exchange of state information between nodes

Process Transfer policies ctd. Types of threshold Single threshold Double threshold

High Mark Threshold Low Mark

Process Transfer Policies ctd. • Most load balancing algorithm use single threshold policy • In single threshold policy – A node accepts a new process if its load is below threshold value and attempts to transfer local processes and rejects remote process requests if load above threshold value – A node should transfer , if the transfer improves performance of its local processes – A node should accept remote processes if its load is such that added workload does not significantly affect service to the local processes

Double threshold • When the load of the node is in the overloaded region new local processes are sent to be run remotely and remote requests are rejected • In normal : new local processes run locally and requests to run remote processes are rejected • In underload : new local processes run locally and requests to run remote processes are accepted

Location policy • Selection of destination node for process’s execution • Main location policies : – Threshold • Random selection and checking is done

– Shortest • Distinct nodes are selected at random and polled to determine the load. • Process transferred to node with min load • If none available , process executed at originating node

– Pairing • Two nodes that differ greatly in loads pair with each other sharing job • Migration done by comparing time for completion on both the nodes

– Bidding • Manager • Contractor

Bidding ctd. • Manager – Node having a process in need of a location to execute

• Contractor – Node that is able to accept remote process

• Manager broadcasts request for bids • Contractors replies with bids • Manager selects bid that is – Cheapest – Fastest – Best price-performance

State information exchange policy • • • •

Periodic broadcasts Broadcast when state changes On demand exchange Exchange by polling

Priority assignment policies • Rule for scheduling local and remote processes – Selfish • Local processes are given higher priority than remote processes

– Altruistic • Remote processes are given higher priority than local processes

– Intermediate • Depends of the number of local and remote processes, whichever greater in number is given higher preference

Priority assignment policies ctd. • Selfish priority gives worst response time for remote processes – Better for processes arriving at lightly loaded node and bad for busy nodes

• Altruistic priority best response time • In intermediate priority response time is near to altruistic priority

Migration Limiting policy • Decision on the number of times a process should be allowed to migrate • Uncontrolled – Process can migrate any number of times – May cause instability

• Controlled – Migration count parameter is maintained – Value can be generated statically or dynamically – Value may also depend on the characteristics of the processes ex. Long process are allowed to migrate more times than short process

Load sharing approach • No node is idle when processes are waiting to be executed • Issues – Load estimation policies – Process transfer policies – Location policies – State info exchange policies

Issues • Load estimation Policies • Determine node is idle or not by counting the number of processes • CPU utilization better option

• Process Transfer Policies • All-or-nothing strategy with single threshold(=1)

• Location Policies – Sender-initiated policy(sender decides where to send) • Broadcasts or probes when overloaded

– Receiver-initiated policy(receiver decides from where to get the process • Broadcasts or randomly probes when free • Preemptive process migration

Issues ctd… – Sender initiated policy better in light or moderate system loads – Receiver initiated policy better in high system loads

• State Information exchange policy – Broadcast when state changes • In Sender initiated - when overloaded • In Receiver initiated - when underloaded – Broadcast-when-idle

– Poll when state changes • Random subset of network • Better for large networks • Poll-when-idle for receiver initiated policy where threshold=1