Bounded Scheduling of Process Networks
Abstract
We present a scheduling policy for complete, bounded execution of Kahn process network programs. A program is a set of processes that communicate through a network of first-in first-out queues. In a complete execution the program terminates if and only if all processes block attempting to consume data from empty communication channels. We are primarily interested in programs that operate on infinite streams of data and never terminate. In a bounded execution, the number of data elements buffered in each of the communication channels remains bounded. The Kahn process network model of computation is powerful enough that the questions of termination and bounded buffering are undecidable. No finite-time algorithm can decide these questions for all Kahn process network programs. Fortunately, because we are interested in programs that never terminate our scheduler has infinite time and can guarantee that programs execute forever with bounded buffering whenever possible. Our scheduling policy has been implemented using Ptolemy, an object-oriented simulation and prototyping environment.
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 01, 1995
- Accession Number
- ADA637171
Entities
People
- Thomas M. Parks
Organizations
- University of California, Berkeley