Least Laxity Verfahren?

[Basti (Gast)]

Hallo zusammen!

Ich habe ein Verständnisproblem in Sachen Prozessabarbeitung. Ich habe 
versucht im INternet was zum Least Laxity Verfahren zu finden aber 
leider verstehe ich nicht wie das ganze funktioniert. Vielleciht kann 
sich jmd der Aufgabe annehmen die ich hier stelle.

Im Anhang ist ein Bild zu sehen welches Prozesse beschreibt mit ihren 
Ausführungszeiten Deadlines etc. könnte jmd ein Prozessablaufdiagramm 
erstellen und mir erklären wie er darauf gekommen ist?

Dabei geht es lediglich um das Least Laxity Verfahren. EDF und Fixed 
Priority sind mir klar.

Hab schon gefunden dass man die Laxity berechnen muss und dafür die 
Ausführungszeit und die Deadline benötigt. danach ist mir klar mit 
welchen Prozess ich beginne jedoch nicht wie es dann weiter geht und wie 
die Prozesse unterbrochen werden.

Ich verzweifel gleich-.-


Danke!

[Uwe .. (uwegw)]

Nach jedem Zeitintervall wird die Laxity für alle Prozesse neu 
berechnet, und dann werden die beiden Prozesse mit der geringsten Laxity 
ausgeführt, wozu ggf. andere Prozesse unterbrochen werden können.

[Basti (Gast)]

ändert sich auch die Deadline der prozesse oder bleibt die gleich und 
die ausführungszeit wird um 1 verringert?

[Uwe .. (uwegw)]

Die Deadline bleibt per Definition immer gleich.

Nach jedem Arbeitschritt prüft man für jeden Task, wie lange er noch bis 
zur Deadline hat. Daraus erfolgt dann die Entscheidung. Alles andere ist 
erst mal unerheblich (außer wenn ein Task fertig ist, dann muss er 
natürlich nicht noch mal ausgewählt werden).

(im Vergleich zu den anderen Verfahren ist LL von Hand ziemlich 
aufwendig zu machen. Daher kam es bei mir im Studium auch nie in 
Klausuraufgaben dran, weil es einfach zu viel Zeit braucht. Ich meine, 
wir hätten nicht mal ne Übungsuafgabe dazu gemacht...)

[Basti (Gast)]

LL: T0=(P1,P2), T1=(P1,P3), T2=(P1,P4)

das steht in der lösung als ansatz aber da komm ich einfach nicht drauf 
könntest du mir die schritte bis 2T bzw 3T mal vormachen :(

Danke!

[Uwe .. (uwegw)]

So, hier meine Lösung.
Manchmal trat die Situation auf, dass zwei Prozesse den selben Spielraum
haben. Dann habe ich den mit der kleineren Nummer gewählt, und die
anderen rot markiert.

In den Zellen ist immer der Spielraum zum jeweiligen Zeitpunkt
eingetragen. Man erkennt, dass bei den gerade nicht aktiven Tasks der
Spielraum stets abnimmt, während er bei den aktiven Tasks konstant
bleibt.

Bei P3 wird dann am Ende die Deadline überschritten.

PS: deine Lösung kann nicht korrekt sein, da P1 erst ab T2 rechenbereit
ist.

PPS: natürlich muss man nur bis T3 rechnen, um die Frage beantworten zu 
können!

[tud (Gast)]

Weiteres Beispiel: 
http://www.et.tu-dresden.de/ifa/uploads/media/PLT2_002-Echtzeitprogrammierung_Rev01_01.pdf
(ab Folie 38)