Improving partitioned scheduling bounds
MetadataShow full item record
We consider multiprocessor scheduling of real-time systems of periodic or sporadic tasks. Prior to execution, tasks are partitioned onto the processors using the First-Fit Decreasing algorithm. We demonstrate methods of allocating tasks onto processors even without complete information about the task. We propose two new models to answer two general questions: 1. Given the description of a task set, how many processors should our system have to ensure that the actual task set can be partitioned onto the system? 2. Given the description of a task set and a specific number of processors, how large can our total utilization be? Answers to these are useful to system designers who make design decisions before fully developing tasks. A task set is characterized using maximum utilization, umax and utilization binder, in our first model and a cumulative utilization function Ucum(i) in our second model.