Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Miscellaneous Problem with Periodic Tasks <s> Abstract A uniform multiprocessor machine is comprised of an integer number of processors. Each processor P is characterized by a computing capacity P . c with the interpretation that a job executing on processor P for t time units completes ( P . c × t ) units of execution. The scheduling of systems of periodic tasks on uniform multiprocessor systems is considered. <s> BIB001 </s> Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Miscellaneous Problem with Periodic Tasks <s> Each processor in a uniform multiprocessor machine is characterized by a speed or computing capacity, with the interpretation that a job executing on a processor with speed s for t time units completes (s /spl times/ t) units of execution. The scheduling of systems of periodic tasks on uniform multiprocessor platforms using the rate-monotonic scheduling algorithm is considered here. A simple, sufficient test is presented for determining whether a given periodic task system will be successfully scheduled by algorithm upon a particular uniform multiprocessor platform-this test generalizes earlier results concerning rate-monotonic scheduling upon identical multiprocessor platforms. <s> BIB002
Baruah BIB001 has considered scheduling systems of realtime tasks that are specified according to periodic model. In the periodic model of hard real-time tasks, a task T is characterized by two integer parameters -an execution requirement T.e and a period T.p with the interpretation that the task generates a job at each integer multiple of T.p and such job has an execution requirement of T.e execution units, which should be met by a deadline equal to the next integer multiple of T.p. A periodic task system consists of several such periodic tasks that are to execute on specified processor architecture. In this research, the job execution on a processor may be preempted. The author has designed an optimal algorithm for scheduling such periodic tasks on uniform parallel machines. Goossens and Baruah have considered the online scheduling of hard-real-time systems in which all jobs must be completed by specified deadlines on uniform multiprocessor machines. In this paper, they provided resource-augmentation techniques that permit on-line algorithms to perform better given the inherent limitations. Results derived here are applied to the scheduling of periodic task systems on uniform multiprocessor machines. Baruah and Goossens BIB002 considered the rate-monotonic scheduling on uniform multiprocessors. For systems comprised of periodic tasks that are to execute upon a single shared processor, a very popular static-priority run-time scheduling algorithm is the rate-monotonic scheduling algorithm (Algorithm RM). It assigns each task a priority inversely proportional to its period. The authors have obtained the first non-trivial feasibility test for a static-priority scheduling algorithm that adopts a global approach to task allocation on uniform multiprocessors. They have obtained simple sufficient conditions for determining whether any given periodic task system will be successfully scheduled by Algorithm RM upon a given uniform multiprocessor platform.