Coscheduling
Encyclopedia
Coscheduling is a mechanism proposed for concurrent systems that schedules related process
es to run on different processors at the same time. 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 only at the rate of one interprocess interaction per time slice.
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.
implicit or dynamic coscheduling.
Explicit coscheduling requires all processing to actually take place at the same time. This is also 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.
Process (computing)
In computing, a process is an instance of a computer program that is being executed. It contains the program code and its current activity. Depending on the operating system , a process may be made up of multiple threads of execution that execute instructions concurrently.A computer program is a...
es to run on different processors at the same time. 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 only at the rate of one interprocess interaction per time slice.
Coscheduling consists of two ideas:
- When scheduling any of the processes in the related group, schedule all of them for execution so that they can communicate efficiently.
- When a process in the group blocks while communicating with another process in the group, don't remove it from its processor. Instead, leave its state loaded on its processor for a short time, under the assumption that it will receive a response shortly. If this time elapses and the process still hasn't become runnable, then assume it will sleep for a long time and reschedule the processor.
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
Gang scheduling
In Computer science, Gang scheduling is a scheduling algorithm for parallel systems that schedules related threads or processes to run simultaneously on different processors...
is a stricter variant of Coscheduling that disallows fragments completely.
Types of Coscheduling
Researchers have classified three types of coscheduling: explicit coscheduling, local scheduling andimplicit or dynamic coscheduling.
Explicit coscheduling requires all processing to actually take place at the same time. This is also known as Gang scheduling
Gang scheduling
In Computer science, Gang scheduling is a scheduling algorithm for parallel systems that schedules related threads or processes to run simultaneously on different processors...
.
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 1982 in the paper by J. K. Ousterhout 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
- J. K. OusterhoutJohn OusterhoutJohn Kenneth Ousterhout is the chairman of Electric Cloud, Inc. and a professor of computer science at Stanford University. He founded Electric Cloud with John Graham-Cumming. Ousterhout previously was a professor of computer science at University of California, Berkeley where he created the Tcl...
. Scheduling Techniques for Concurrent Systems Proceedings of Third International Conference on Distributed Computing SystemsInternational Conference on Distributed Computing SystemsThe International Conference on Distributed Computing Systems is the oldest conference in the field of distributed computing systems in the world. It was launched by the IEEE Computer Society Technical Committee on Distributed Processing in October 1979, and is sponsored by such committee...
, 1982, 22—30. - Gang schedulingGang schedulingIn Computer science, Gang scheduling is a scheduling algorithm for parallel systems that schedules related threads or processes to run simultaneously on different processors...