Competitive analysis of static-priority partitioned scheduling on uniform multiprocessors
Consider the problem of scheduling a set of sporadically arriving tasks on a uniform multiprocessor with the goal of meeting deadlines. A processor p has the speed Sp. Tasks can be preempted but they cannot migrate between processors. On each processor, tasks are scheduled according to rate-monotoni...
| Autor principal: | |
|---|---|
| Outros Autores: | |
| Formato: | conferenceObject |
| Idioma: | eng |
| Publicado em: |
2014
|
| Texto completo: | http://hdl.handle.net/10400.22/3950 |
| País: | Portugal |
| Oai: | oai:recipp.ipp.pt:10400.22/3950 |
| Resumo: | Consider the problem of scheduling a set of sporadically arriving tasks on a uniform multiprocessor with the goal of meeting deadlines. A processor p has the speed Sp. Tasks can be preempted but they cannot migrate between processors. On each processor, tasks are scheduled according to rate-monotonic. We propose an algorithm that can schedule all task sets that any other possible algorithm can schedule assuming that our algorithm is given processors that are √2 / √2−1 ≈ 3.41 times faster. No such guarantees are previously known for partitioned static-priority scheduling on uniform multiprocessors. |
|---|