Coscheduling

Coscheduling is the principle for concurrent systems of scheduling related processes to run on different processors at the same time (in parallel). There are various specific implementations to realize this.

If an application consists of a collection of processes working closely together, and if some but not all of the processes are scheduled for execution, the executing processes may attempt to communicate with those that are not executing, which will cause them to block. Eventually the other processes will be scheduled for execution, but by this time the situation may be reversed so that these processes also block waiting for interactions with others. As a result, the application makes progress at the rate of at most one interprocess interaction per time slice, and will have low throughput and high latency.

Implementation

Coscheduling consists of two ideas:

Some coscheduling techniques exhibit fragments of processes that do not run concurrently with the rest of the coscheduled set. The occurrence of these fragments is usually minimized by these algorithms. Gang scheduling is a stricter variant of coscheduling that disallows fragments completely.

Types of coscheduling

Researchers have classified three types of coscheduling: explicit coscheduling, local scheduling and implicit or dynamic coscheduling.[1]

Explicit coscheduling requires all processing to actually take place at the same time, and is typically implemented by global scheduling across all processors. A specific algorithm is known as gang scheduling.

Local coscheduling allows individual processors to schedule the processing independently.

Dynamic (or implicit) coscheduling is a form of coscheduling where individual processors can still schedule processing independently, but they make scheduling decisions in cooperation with other processors.

History

The term "coscheduling" was introduced in Ousterhout (1982). The original definition is that the process working set must be coscheduled (scheduled for execution simultaneously) for the parallel program to make progress.

See also

Notes

  1. Fabrizio Petrini, Wu-chun Feng. Improved Resource Utilization with Buffered Coscheduling, Journal of Parallel Algorithms and Applications, 2000
This article is issued from Wikipedia - version of the Friday, February 26, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.