User-Level Scheduling

Application level information is often useful for controlling scheduling to improve performance. For example, the A*-search is an algorithm to find the best answer in terms of some evaluation function. It uses the estimated value of the answer, which is computed from the intermediate status, as a scheduling priority of a thread. As the branch-and-bound algorithms do, it prunes--terminating subcomputations that have no possibility to reach the best answer--is effective for reducing the search space. Since such scheduling facilities are not provided in most language systems, programmers are forced to write a program that explicitly controls the order of execution. Usually, this is realized with an user-level scheduler object as a server embedded in the base-level application code, and searcher objects as clients, as is shown in Figure 7. (1) The scheduler activates a searcher object. (2) The object sends requests for object creation and activation, instead of creating its sub-objects, for the next search step. These requests are stored in the queue belonging to the scheduler object. (3) When the activated object finishes its execution, it yields its execution by sending a message to the scheduler. (4) The scheduler then selects a request having the highest priority from the queue, and creates and activates a search object that corresponds to the selected request. The queue of the scheduler is sorted by the priority value of each request, and the scheduler can prune requests from the queue.

  

Figure 7: Explicit user-level scheduling system

One of the problem of this programming style is that the control flow in the original algorithm, which is represented as dashed arrows in the figure, is replaced with more complicated communications, which is represented as solid arrows. As a result, the program becomes unclear and difficult to maintain. Our goal is to provide syntactic support which hides such explicit communications with the scheduler, allowing a programmer to write their search algorithms in a `natural' style in Figure 6.