Jak cron interně plánuje úlohy?

V této otázce bylo slyšet několik cvrčků. Dobrý 'ol RTFC s některými dokumenty o simulaci diskrétních událostí a Wikipedií:

http://cs.wikipedia.org/wiki/Cron#Multi-user_capability

Algoritmus používaný tímto cronem je následující:

1. Při spuštění vyhledejte soubor s názvem .crontab v domovských adresářích všech držitelů účtů.
2. U každého nalezeného souboru crontab určete, kdy příště v budoucnu bude každý příkaz spuštěn.
3. Umístěte tyto příkazy do seznamu událostí Franta-Maly s jejich odpovídajícím časem a jejich "pětipoleovým" specifikátorem času.
4. Vstoupit do hlavní smyčky:
   1. Prozkoumejte záznam úlohy na začátku fronty a vypočítejte, jak daleko v budoucnu má být spuštěna.
   2. Po tu dobu spěte.
   3. Při probuzení a po ověření správného času spusťte úlohu v čele fronty (na pozadí) s oprávněními uživatele, který ji vytvořil.
   4. Určete, kdy příště v budoucnu spustit tento příkaz, a v tu dobu jej umístěte zpět do seznamu událostí

Napsal jsem článek na blog, který to popisuje.
Cituji příslušný text odtud:

• Můžeme mít konečný fond vláken, který bude provádět všechny úkoly tím, že je vybere z PriorityBlockingQueue (thread-safe heap) s prioritou na job.nextExecutionTime() .
• To znamená, že nejvyšší prvek této hromady bude vždy ten, který vystřelí nejdříve.
• Budeme se řídit standardním vzorem sdružených výrobců a spotřebitelů.
• Budeme mít jedno vlákno, které bude běžet v nekonečné smyčce a bude odesílat nové úlohy do fondu vláken poté, co je spotřebuje z fronty. Nazvěme to QueueConsumerThread :

void goToSleep(job, jobQueue){
    jobQueue.push(job);
    sleep(job.nextExecutionTime() - getCurrentTime());
}

void executeJob(job, jobQueue){
    threadpool.submit(job); // async call
    if (job.isRecurring()) {
        job = job.copy().setNextExecutionTime(getCurrentTime() + job.getRecurringInterval());
        jobQueue.add(job);
    }
}

@Override
void run(){
    while(true)
    {
        job = jobQueue.pop()
        if(job.nextExecutionTime() > getCurrentTime()){
            // Nothing to do
            goToSleep(job, jobQueue)
        }
        else{
            executeJob(job, jobQueue)
        }
    }
}

• Bude zde ještě jedno vlákno, které bude v souboru crontab monitorovat jakékoli nové přidané úlohy a zařadí je do fronty.
• Řekněme tomu QueueProducerThread :

@Override
void run()
{
    while(true)
    {
        newJob = getNewJobFromCrontabFile() // blocking call
        jobQueue.push(newJob)
    }
}

• S tím je však problém:
  • Představte si, že Thread1 spí a po hodině se probudí.
  • Mezitím přijde nová úloha, která se má spouštět každou minutu.
  • Tento nový úkol se bude moci spustit až o hodinu později.
• Abychom tento problém vyřešili, můžeme nechat ProducerThread násilně probudit ConsumerThread z režimu spánku, kdykoli se nová úloha musí spustit dříve než přední úloha ve frontě:

@Override
void run()
{
    while(true)
    {
        newJob = getNewJobFromCrontabFile() // blocking call
        jobQueue.push(newJob)
        if(newJob == jobQueue.peek())
        {
            // The new job is the one that will be scheduled next.
            // So wakeup consumer thread so that it does not oversleep.
            consumerThread.interrupt()
        }
    }
}

Všimněte si, že toto nemusí být způsob, jakým je cron implementován interně. Toto je však nejoptimálnější řešení, které si dokážu představit. Nevyžaduje žádné dotazování a všechna vlákna spí, dokud nepotřebují provést nějakou práci.