Introduction to Scheduling and Load Balancing
Introduction
One of the biggest issues in parallel and distributed operating environments is the
development of effective techniques for the distribution of the processes of a parallel program
on multiple processors. The problem is to schedule the processes among processing elements
to achieve some performance goal(s), such as minimizing communication delays
and execution time and/or maximizing resource utilization.
Local scheduling performed by the OS of a processor consists of the assignment of the
processes to the time-slices of the processor. Global scheduling is the process of
deciding where to execute a process in a multiprocessor system. It may be
carried out by a single authority or it may be distreibuted among processing
elements.
Static Scheduling
In static scheduling, the assignment of the proceesors is done before the program execution
begins. Info regarding the task execution times and resources are assumed to be known at compile time itself.
These methods are processor nonpreemptive. The approach here is
to minimize the execution time of the concurrent program while minimizing the
communication delay. Thus methods aim at
- Predict the program exec. behaviour at compile time
- Perform a partitioning of smaller tasks into coarser grain processes to reduce communication
delays.
- Allocate processes to processors.
Perhaps one of the most critical drawbacks of this approach, is that generating optimal schedules is an
NP-complete problem, hence only restricted solutions can be given.
Heuristic methods rely on the rules of the thumb to guide the scheduling
processes in the proper track for a near optimal solution. For example, the
length of the critical path for a task is the length of one of the several longest possible paths from the
task, till the end of the program. Thus using this heuristic method, we give priority
to the process with the longer critical path, allowing us to schedule other
paths of less length around them.
Dynamic Scheduling
This method is based on redistribution of processes at execution time. This is achieved by
transferring the tasks from heavily loaded processors to the lightly loaded ones
called Load Balancing . The definition of a typical algorithm
for load balancing has the three inherent policies:
- Information policy : Specifies the amount of load information made available
to the placement decision makers.
- Transfer policy : Specifies the conditionsunder which a job is transferred,
i.e. the current load of the host and size of the job. In addition, task migration
may also be considered where relevant.
- Placement policy : Involves allocation of processes to the different
processing elements.
The load balancing operations may be centralized in a single processor or distributed
among all processing elements. Combined policies where information policy is centralized
but the transfer and placement policies may be redistributed. In a distributed
environment, each processing element has its own image of the system load. We
can have a cooperative scheduling arrangement, where gradient distribution of the
load is performed, or in a nocooperative setup, we use random scheduling which
is especially useful, when the load for all the processing elements is high.
The main advanteage of the dynamic approach over the static approach is
the inherent flexibility allowing for adaptation to the unforeseen application
requirements at run-time, though at the cost of communication overheads. The
disadvantages are mainly due to communication delays, load information transfer
and decision making overheads.
Future research areas could encompass new concepts for
- Hybrid dynamic/static scheduling
- Effective load index measures
- Hierarchical system organizations with local load information distribution
and local load balancing policies
- Incorporation of a set of primitive tools at the distributed OS level
Next
Index(TOC)