This question appears in Mumbai University > Parallel And Distributed System subject

Marks: 10 M

Year: Dec 2015

Job Scheduling:

Dividing which process should execute on which machine (processes) in a distributed environment is called job scheduling. It mainly deals with task assignment.

Load balancing:

The process of maintaining a balanced load on all the machine in a system. It mainly focuses on process utilization of CPU cycles (Process time).

The issues in load balancing algorithms:

1.Local estimation policy: The nodes work load can be estimated based on following parameter. - Total no. of processes on the node. - Resources needed by processes. - Instruction mixes of there processes. - Architecture and speed of node's processes.

The load estimation policies are completely application dependent.

2.Process transfer policy: While transferring the process from heavily loaded node to lightly loaded node, most of the algorithm uses threshold policy. The threshold value of a node may be determined by any of the following methods. - Static threshold policy: The threshold value does not vary at all. - Dynamic Policy: The threshold value may vary with the dynamic changes in the node. There can be a single threshold policy as double threshold policy.

3.Location policy: It is used for selecting the destination node to which the process is being transferred. The location can be chosen based on following- - Threshold: In this the random node which is under loaded is chosen for process migration. - Shortest: In this the node with minimum load is selected for process migration. - Biding: In this method nodes contain managers to send processes and contractors to receive processes. Managers broadcast a request for bid and contractors respond with bids where the manager selects the best offer. The winning contractor is notified and asked whether it accepts the process for execution or not. A contractor is never forced to accept remote process. - The pairing policy: Is used to reduce the variance of load only between nodes of the system. Each node asks some randomly chosen node to form a pair with it. If it receives a rejection it randomly selects another node and tries to pair again. Two nodes that differ greatly in load are temporarily paired with each other and migration starts. The pair is broken as soon as the migration is over. A node only tries to find a partner if it has at least two processes.

4.Priority assignment policy: This decides that which process should have highest priority.

• Selfish priority assignment rule: In this the local processes are given higher priority than remote processes.

This rule has the worst response time performance of the three policies due to poor performing processes.

Best response time performance is achieved for local processes.

• Altruistic priority assignment rule: Remote processes are given higher priority than local processes in this rule.

It has the best response time performance of the three policies.

Remote process incur lower delays than local processes as local processes are treated as principal while remote processes are secondary workload.

• Intermediate priority assignment rule: Priority in this rule is decided depending on number of local and remote processes on a node.

When the number of local processes is greater or equal to the number of remote processes than local processes are given higher priority or else remote processes are given higher priority than local processes.

Performance of this rule is between the two above policies. Overall response time performance is close to altruistic policy.

5.Static state information exchange policy: State information is exchanged during following situations-

• Periodically
• Broadcast when state changes
• On demand exchange
• Exchange on policy

6.Migration limiting policy for Load-balancing algorithms: This policy determines the total number of times a process can migrate. One of the following two policies may be used-

a.Uncontrolled: A remote process arriving at a node is treated just as a process originating at a node due to which a process may be migrated any number of times.

b.Controlled: This avoids the instability of the uncontrolled policy and uses a migration count parameter to fix a limit on the number of time a process that can migrate.