2nd USENIX Windows NT Symposium
   
[Technical Program]
Page 171 of the Proceedings | |
Distributed
Preemptive Scheduling on Windows NT
Donald McLaughlin
and Partha Dasgupta
Arizona State University
partha@asu.edu
This research is partially
supported by grants from DARPA/Rome Labs, Intel
Corporation and NSF.
|
Introduction |
All multitasking operating systems use preemptive
scheduling. Many multiprocessor systems also employ
preemptive inter-task scheduling when they run parallel
computations. However, preemptive scheduling in
distributed systems is rare, if not non-existent.Consider a cluster of workstations, running a parallel
application. The application divides itself into a set of
tasks. The scheduler assigns these tasks to a set of
workstations. Often the tasks are not of equal length,
the machines are not of equal speeds and tasks can create
further subtasks. These situations lead to non-optimal
matches of workers to tasks causing executions that do
not complete as quickly as it would be possible in a
better matched case. Also, the granularities of the tasks
may be small, leading to high overhead.
|
Distributed
Scheduling |
All multitasking operating systems use
preemptive scheduling. Many multiprocessor systems also
employ preemptive inter-task scheduling when they run
parallel computations. However, preemptive scheduling in
distributed systems is rare, if not non-existent.Consider a cluster of workstations, running a parallel
application. The application divides itself into a set of
tasks. The scheduler assigns these tasks to a set of
workstations. Often the tasks are not of equal length,
the machines are not of equal speeds and tasks can create
further subtasks. These situations lead to non-optimal
matches of workers to tasks causing executions that do
not complete as quickly as it would be possible in a
better matched case. Also, the granularities of the tasks
may be small, leading to high overhead.
|
Preemptive
Scheduling |
All multitasking operating systems use preemptive
scheduling. Many multiprocessor systems also employ
preemptive inter-task scheduling when they run parallel
computations. However, preemptive scheduling in
distributed systems is rare, if not non-existent.Consider a cluster of workstations, running a parallel
application. The application divides itself into a set of
tasks. The scheduler assigns these tasks to a set of
workstations. Often the tasks are not of equal length,
the machines are not of equal speeds and tasks can create
further subtasks. These situations lead to non-optimal
matches of workers to tasks causing executions that do
not complete as quickly as it would be possible in a
better matched case. Also, the granularities of the tasks
may be small, leading to high overhead.
|
Implementation and
Performance |
We have implemented the algorithms on the Chime parallel
processing system running on Windows NT. The major
roadblock turned out to be process migration under NT.
The lack of signals posed the greatest problem as a
thread can only be interrupted by another thread that
suspends it. Care has to be taken to ensure that the
thread to be migrated is not suspended waiting for a
runtime event. Race conditions and starvation conditions
have been encountered. The final
system runs well, and performance results are very
encouraging. We found that the round-robin scheduler
provided acceptable performance on large grained
programs, but was hampered by the migration overhead. The
task bunching scheduler performed really well in a wide
variety of situations. More information and papers can be
found at https://milan.eas.asu.edu.
|
|