Previous: InstrTable Up: A Bestiary of Kiwi Objects Next: Collector
The Kiwi Scheduler is very simple compared to the multi-level feedback queues of a UNIX scheduler. Since Kiwi is a non-real time system, maximizing processor utilization minimizes total running time. Hence, the Kiwi Scheduler need not consider process priorities, CPU versus I/O boundedness, or throughput. The only concern is keeping all the processors busy doing useful work.
Rahn[10] summarizes the scheduling algorithms of two software synthesizers -- MUSIC 4BF[7] and CMIX[6]. The CMIX system constructs a disk file for the entire piece and initializes it with zeroes. As the samples for each Note are calculated, their values are added to the disk file, replacing the zeroes. If more than one note contributes to a given time interval, the samples are summed. Thus, the CMIX disk file acts as a running total of contributions from each note. This means that notes can be computed in any order. The speed of this process is limited by the size of its ``running total'' buffer. Such a buffer is too large to fit in physical memory, and disk accesses become a major bottleneck.
The MUSIC 4BF approach divides the score into segments during which there are a constant number of instruments playing (i. e., the segments are defined by the beginnings and ends of notes). All the samples for a given segment are computed before moving on to the next segment. The potential parallelism in MUSIC 4BF is limited by the number of simultaneous notes. For example, a monophonic score would induce a series of segments containing exactly one note, and only one processor would compute samples.
The Kiwi scheduler is a hybrid of these two approaches. It includes a Collector, which emulates CMIX's buffer. Following the model of MUSIC 4BF, Kiwi divides the piece into segments (referred to here as grains) as in MUSIC 4BF, but unlike MUSIC 4BF Kiwi employs segments of fixed duration that do not depend on the score. Each grain is entirely synthesized before the next begins.
Figure 2.6. Scheduling example
The Scheduler maintains an internal clock, myclock, and a pair of pointers begin_chord and end_chord. These pointers define a sublist of the score list (referred to below as the ``current chord'') that is sounding at time myclock. Even though the Notes are sorted in order of starting time, the set of Notes sounding at a given time need not form a contiguous portion of the score list. Thus, the list defined by begin_chord and end_chord may contain some notes that do not sound at time myclock. For example (see Figure 2.6), a note lasting five seconds may begin at time 1, followed by a note lasting half a second starting at time 2 and a note lasting six seconds starting at time 3. At time 4 there are only two notes sounding (the first and the third), but there is no way to include them in a list without excluding the middle note.
When a Processor calls Scheduler::get_task, the Scheduler does one of two things. If there is a note in the current chord that has not been scheduled, the Scheduler constructs a new Task representing the portion of the note in the current grain. Thus, a note spanning several grains will require several Tasks. If all of the Notes in the current chord have been scheduled, then the Scheduler waits for the Collector to signal and moves myclock ahead to the next grain. Then, the and end_chord pointers are updated to reflect the new clock. Then, the Scheduler creates a Task for the first note in the new chord.
Kiwi uses semaphores for synchronization and mutual exclusion. It is safest to assume that multiple tasks waiting on a semaphore will be accepted in random order. For this and other reasons it is possible that a Processor could be indefinitely delayed while contending for the Collector or while computing samples. If the other processors proceeded with computation, the Collector would be unable to guarantee that a grain was finished before starting the next. To prevent this, the Scheduler and Collector are synchronized. After scheduling all the Tasks for a particular grain, the Scheduler waits for the Collector to receive all the samples for that grain before continuing. Suppose Processor is one of several contending for the Collector; eventually the Scheduler will schedule all the Tasks for its current grain and their samples will be computed and reported. Processor would be the last and only Processor waiting for the Collector as the other Processors contend for the Scheduler. The Scheduler will not proceed to the next grain until is successful. Unfortunately, this Scheduler/Collector synchronization can result in wasted processor time. This waste is minimized by making the grain size as large as possible (about 400,000 samples).