Scout paths are passive entities. In a sense, they provide lanes within a modular system through which data flows. The entities that move the data through these lanes are threads. Threads are orthogonal to paths, meaning that at any time there may be zero, one, or several threads executing in a path. Each thread is scheduled independently, though threads normally inherit scheduling parameters from the path that they are currently executing in.
An alternative to independent threads would be to constrain each thread to a particular path. Such threads could be viewed as server threads that are responsible for moving (processing) the data enqueued at the path's input queues. However, such an approach would force a context switch every time a message needs to be moved from one path to another. With independent threads, such context switches can be typically avoided. Moreover, when a thread moves from one path to another, it is also often possible to bypass the output and input queues of the paths involved. This makes moving from one path to another highly efficient---the only overhead is due to the dynamic routing decision that the module at the end of the path needs to make to find the next path on which to continue, and possibly an adjustment of scheduling priority when the thread enters the new path. Note that the dynamic routing decision is necessary in a purely modular system as well, so, strictly speaking, it would be more appropriate to consider it a part of the data processing cost, rather than a part of the overhead. Owing to the efficiency with which threads can typically move from one path on to another, even a system with many short paths is likely to perform comparably to or better than traditional systems that avoid per-layer context switching, such as the x-kernel or UNIX [49, 89].
Furthermore, an approach using independent threads does not prevent building a system in which threads have path affinity. Whether a thread enqueues a message when reaching the end of a path or whether it continues processing the message by moving on to the next path is under control of code provided by the module at the end of the path, so ultimately, it is up to the modules to implement one or the other policy. Path affinity might, for example, make sense in an environment where the cost of bringing a path's code into the caches is high relative to the cost of bringing the data into the caches [10]. If the costs are reversed, then letting a thread move a message as far as possible is likely to result in better performance [16]. Rather than based on cache costs, the decision of whether a thread should continue executing in the old path or should move on to the next path may depend on path priority. It seems advisable that a new path is entered only if it has a priority that is at least as high as the priority of the current path. The issue becomes quite interesting when there are sequences of three or more paths. In that case, two high-priority paths may be connected by a low-priority path. This might require a form of priority inheritance to ensure correct scheduling decisions. In any case, the point is that, depending on circumstances, one or another policy may be more appropriate for a given path. With independent threads, this policy choice is left to the individual modules in a path. If necessary, these modules can coordinate their efforts by establishing well-known path attributes, such as the execution priority, but Scout does not dictate a particular choice.
In Scout, threads are scheduled non-preemptively according to a
scheduling policy and priority. Two scheduling policies are supported
and a higher-level round-robin scheduler allocates percentages of CPU
time to each.
The choice of a non-preemptive scheduler may seem unusual. However, for information appliances there is likely to be little reason to introduce the complexity of preemptive scheduling. In contrast to general purpose machines, where preemption has to be dealt with anyway due to the true concurrency present in shared-memory multi-processors, many appliances are expected to be uniprocessors (at least for the near- to medium-range future). Not having to worry about pre-emption has the advantage of greatly reducing and often eliminating locking overhead, providing a simpler programming model, and allowing for more efficient context switching. For example, on the Alpha architecture, only nine integer registers need to be saved and restored in a synchronous context switch. In contrast, an asynchronous switch requires preserving all 31 integer registers. On the other hand, a non-preemptive scheduler does require a certain amount of cooperation among different tasks. For example, in Scout it is expected that no thread executes longer than one time-slice without giving the scheduler the opportunity to reschedule the CPU. Thus, long-running processing loops have to explicitly call a thread yield primitive at least once per time-slice. While this partly offsets the performance advantage of the synchronous context switching, the yield primitive can be implemented as a single memory read access and a conditional branch for the common case where the CPU does not have to be yielded. The bigger disadvantage of explicit yielding may be that it complicates the programming model somewhat. This can be avoided by moving the responsibility of placing yield calls to the compiler. While this would essentially guarantee correct use of the yield primitive, it is likely that a compiler would place such calls conservatively, causing more overhead than strictly necessary. Thus, there is a choice between a safe solution (using compiler placed yields) and a solution that, at least theoretically, provides the most efficient solution (manually placed yield calls). Scout currently employs the latter approach.
As mentioned in the introduction to this section, threads inherit the scheduling parameters (policy and priority) from the path they are executing in. Once a thread is executing inside a path, it can adjust its own scheduling parameters by calling the appropriate thread primitive. But the scheduling parameters also need to be set when waking up a thread to execute on behalf of a path. For this purpose, the path object provides the realtime and prio members (see Section 3.3.3). If realtime evaluates to true, then a thread entering the path should be scheduled as a realtime task with the deadline set to the value given by prio. This value is interpreted as a deadline in micro-seconds. With a thirty-two bit integer, this accommodates task execution times of up to slightly more than thirty minutes. If realtime is false, then the thread should be scheduled using the round-robin scheduler and using prio as its fixed priority.
Code inside a path can and may modify these two scheduling parameters at any time. The only restriction is that a non-realtime constraint set may not replace a realtime deadline unless that deadline has already expired. Similarly, a path's realtime deadline may be replaced only with an earlier deadline unless the existing deadline has been met or has already expired. These rules ensure that threads in a path are scheduled according to the most stringent constraints that exist inside the path. Note that this inheritance scheme does not permit differentiation between multiple threads that may be entering a path. However, once inside a path, a thread is able to adjust its own priority as necessary.
A final question related to the execution model is when threads are created and destroyed. Since they are first-class objects, threads can be created by any existing thread as necessary and a thread can terminate itself whenever its task is complete. In addition to this, device drivers create and schedule new threads as messages arrive at the input queues of paths. Logically, Scout implements a thread-per-message model, i.e., every message has its own thread, called a shepherd, that takes care of moving it through the path.
The thread-per-message model is a convenient abstraction, but when a system operates under overload conditions, the input queues can quickly build up and as a result the number of threads may become so large that they overwhelm the system. To ameliorate this problem, Scout keeps the number of shepherds executing in a path as small as possible. This optimization is based on the observation that a path can notice a violation of the thread-per-message model only if it were to deadlock due to an insufficient number of threads. Thus, Scout strives to maintain the invariant that there is exactly one runnable shepherd per path whenever one of the path's input queues is non-empty. This is realized as follows: when a message is enqueued on a path with formerly empty input queues, Scout assigns a new shepherd to the path. As long as that shepherd continues to execute inside the path, there is no danger of deadlock and hence Scout does not assign any additional shepherds, even if the input queues continue to grow. However, should the shepherd block while inside the path, there is a danger of deadlock. In this case, Scout assigns a new shepherd to the path as soon as its input queues grow non-empty. Note that this simple scheme does not guarantee exactly one runnable shepherd per path since, eventually, the blocked shepherd will resume execution and, at that point, two or more shepherds may be runnable inside the path. But having multiple threads execute in the same path is consistent with the thread-per-message model, so this is not a problem.
The real issue is that while this scheme minimizes the number of threads in the system to the degree possible, it does not bound it. This is because each time a shepherd blocks, a new message may arrive and thus a new shepherd may get assigned which may then block as well. Since this process can repeat itself indefinitely, an unbounded number of shepherds may accumulate inside a path. Unfortunately, putting an arbitrary limit on the number of shepherds per path introduces the risk of deadlock. It is easy to determine the number of points inside a path that may block, but determining the maximum number of times shepherds may block at those points is undecidable, in general. For this reason, the Scout infrastructure does not prevent paths from indefinitely accumulating shepherds (and therefore from unbounded resource consumption). Instead, it leaves it up to higher-level mechanisms to ensure that the overall system does not suffer from such problems. In essence, each module individually or in combination with others must take the necessary precautions to avoid creating situations where shepherds may accumulate without bound. This is typically achieved either through a feedback mechanism (such as TCP flow-control) or a load shedding mechanism (such as dropping messages).