In che modo cron pianifica internamente i lavori?

Alcuni grilli sentiti in questa domanda. Buon vecchio RTFC con alcuni documenti di simulazione di eventi discreti e Wikipedia:

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

L'algoritmo utilizzato da questo cron è il seguente:

1. All'avvio, cerca un file denominato .crontab nelle home directory di tutti i titolari di account.
2. Per ogni file crontab trovato, determina la prossima volta che ogni comando deve essere eseguito.
3. Inserisci questi comandi nell'elenco degli eventi Franta-Maly con l'ora corrispondente e l'identificatore di tempo "cinque campi".
4. Inserisci ciclo principale:
   1. Esamina la voce dell'attività in testa alla coda, calcola fino a che punto deve essere eseguita nel futuro.
   2. Dormi per quel periodo di tempo.
   3. Al risveglio e dopo aver verificato l'ora corretta, eseguire l'attività in testa alla coda (in background) con i privilegi dell'utente che l'ha creata.
   4. Determinare la prossima volta in futuro per eseguire questo comando e riposizionarlo nell'elenco degli eventi in quel momento

Ho scritto un post sul blog descrivendolo.
Citando il testo pertinente da lì:

• Possiamo avere un pool di thread finito che eseguirà tutte le attività prelevandole da un PriorityBlockingQueue (heap thread-safe) con priorità job.nextExecutionTime() .
• Ciò significa che l'elemento superiore di questo heap sarà sempre quello che si attiverà prima.
• Seguiremo il modello produttore-consumatore standard del threadpool.
• Avremo un thread che verrà eseguito in un ciclo infinito e invierà nuovi lavori al pool di thread dopo averli consumati dalla coda. Chiamiamolo 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)
        }
    }
}

• Ci sarà un altro thread che monitorerà il file crontab per eventuali nuove aggiunte di lavoro e li metterà in coda.
• Chiamiamolo QueueProducerThread :

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

• Tuttavia, c'è un problema con questo:
  • Immagina che Thread1 stia dormendo e si sveglierà dopo un'ora.
  • Nel frattempo arriva una nuova attività che dovrebbe essere eseguita ogni minuto.
  • Questa nuova attività non sarà in grado di iniziare l'esecuzione fino a un'ora dopo.
• Per risolvere questo problema, possiamo fare in modo che ProducerThread risvegli forzatamente ConsumerThread dalla sua sospensione ogni volta che la nuova attività deve essere eseguita prima dell'attività principale in coda:

@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()
        }
    }
}

Tieni presente che questo potrebbe non essere il modo in cui cron viene implementato internamente. Tuttavia, questa è la soluzione ottimale a cui riesco a pensare. Non richiede polling e tutti i thread restano inattivi fino a quando non devono eseguire alcuna operazione.