hallo zusammen,

auf der folie 15 (kapitel 3, rtos-schedule, annotiert) steht, dass ein zwei-prozessor schedule für tasks mit gleicher arrival-time und gleicher deadline NP-vollständig ist.
kann mir vielleich jemand ein kleines bsp nennen, wo der folgende algorithmus nicht auf anhieb eine lösung geben würde?

algorithmus:
- sortiere taskmenge absteigend nach ausführungszeit
- nehme ersten (längsten) raus und ordne einem der prozessoren zu, dessen summe der ausführungszeiten, der bisher zugeteilten tasks kleiner ist. wenn die summe gleich ist (z.b. am anfang sind beide 0) dann beliebigen prozessor aussuchen



1 mal bearbeitet. Zuletzt am 14.09.2008 21:52 von drdreii.

Versuch es mal mit fünf Tasks bei denen
* zwei Tasks 3 Zeiteinheiten und
* drei Tasks 2 Zeiteinheiten
benötigen.

Die Deadline ist bei 6.