[Python-de] cron-Ersatz

"Martin v. Löwis" martin at v.loewis.de
Die Aug 9 00:32:11 CEST 2005


Henning.Ramm at mediapro-gmbh.de wrote:
> Weil es wild in der Gegend herumrechnet und iteriert. ;-) Algorithmen
> sind leider nicht meine Stärke, und C verstehe ich auch nicht, so
> dass mir die Source von cron wohl auch nicht weiterhelfen würde. 
> Kennt jemand eine Beschreibung des cron-Algorithmus'? (Eine
> Diplomarbeit oder so?)

Das hilft, glaube ich, nicht viel. Ich würde in den Algorithmus
an allerlei Stellen Zähler einbauen, und schaun, wie die sich so
entwickeln. Wenn irgend etwas 1000 mal ausgeführt wird, ist da
ein Fehler.

Pro cron-Zeile würde ich 5 Vergleiche erwarten (wenn man
(mon,day,wday,hour,min)-Tupel betrachtet):

1. Finde pro Element den nächst-größeren Wert. Das ist
   linear in Abhängigkeit von der Länge der Wert-Spezifikation
   möglich, also 1,2,3-10,20-30 braucht 5 Schritte, jeder mit
   bis zu zwei Vergleichen. Laufzeiteffizienter sind indizierte
   Zugriffe:
   next[0]=1, next[1]=2, next[2]=3, next[3]=10, ... next[9]=10
   next[10]=11 usw. next[59]=1
   Muss man einmal beim Einlesen aufbauen, danach findet man
   den nächsten Wert in konstanter Zeit.
   nmon=mon
   nday=day
   nhour=hour
   nmin=next_min[min]

2. Test, ob nmin > min. Falls ja, ist das der nächste
   Ereigniszeitpunkt.

3. Falls nicht, ist min übergelaufen: nhour=next[nhour]
   Falls das auch überläuft, weiter mit wday.

wday bedarf vermutlich einer Sonderbehandlung: der nächste
Tag ist der, bei dem *entweder* day oder wday matcht.
Also muss nextday(day) vermutlich sowohl den nächsten
Tag als auch den nächsten Wochentag ausprobieren, und
schaun, welcher davon früher ist.

Bei mehreren cron-Zeilen: jeweils pro Zeile den nächsten
Ereigniszeitpunkt bestimmen, dann alle Zeilen aufsteigend
sortieren. Wenn das nächste Ereignis eingetroffen ist,
übernächsten Zeitpunkt für diese crontab-Zeile bestimmen,
array der nächsten Zeitpunkte aktualisieren, Feld neu
sortieren.

Ciao,
Martin