Comment cron planifie-t-il les tâches en interne ?

Quelques grillons entendus dans cette question. Bon 'ol RTFC avec quelques articles sur la simulation d'événements discrets et Wikipedia :

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

L'algorithme utilisé par ce cron est le suivant :

1. Au démarrage, recherchez un fichier nommé .crontab dans les répertoires d'accueil de tous les titulaires de compte.
2. Pour chaque fichier crontab trouvé, déterminez la prochaine fois dans le futur que chaque commande doit être exécutée.
3. Placez ces commandes sur la liste des événements Franta-Maly avec leur temps correspondant et leur spécificateur de temps "cinq champs".
4. Entrez dans la boucle principale :
   1. Examinez l'entrée de la tâche en tête de file d'attente, calculez jusqu'où elle doit être exécutée dans le futur.
   2. Dormir pendant cette période.
   3. Au réveil et après vérification de l'heure correcte, exécutez la tâche en tête de file d'attente (en arrière-plan) avec les privilèges de l'utilisateur qui l'a créée.
   4. Déterminez la prochaine fois dans le futur pour exécuter cette commande et replacez-la dans la liste des événements à ce moment-là

J'ai écrit un article de blog le décrivant.
Citant le texte pertinent à partir de là :

• Nous pouvons avoir un pool de threads fini qui exécutera toutes les tâches en les récupérant à partir d'un PriorityBlockingQueue (tas thread-safe) priorisé sur job.nextExecutionTime() .
• Cela signifie que l'élément supérieur de ce tas sera toujours celui qui se déclenchera le plus tôt.
• Nous suivrons le modèle standard producteur-consommateur de threadpool.
• Nous aurons un thread qui s'exécutera dans une boucle infinie et soumettra de nouveaux travaux au pool de threads après les avoir consommés à partir de la file d'attente. Appelons-le 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)
        }
    }
}

• Il y aura un autre thread qui surveillera le fichier crontab pour tout nouvel ajout de travail et les mettra dans la file d'attente.
• Appelons-le QueueProducerThread :

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

• Cependant, il y a un problème avec ceci :
  • Imaginez que Thread1 dort et se réveille au bout d'une heure.
  • Entre-temps, une nouvelle tâche arrive qui est censée s'exécuter toutes les minutes.
  • Cette nouvelle tâche ne pourra commencer à s'exécuter qu'une heure plus tard.
• Pour résoudre ce problème, nous pouvons demander à ProducerThread de réveiller ConsumerThread de force chaque fois que la nouvelle tâche doit s'exécuter plus tôt que la tâche principale dans la file d'attente :

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

Notez que ce n'est peut-être pas ainsi que cron est implémenté en interne.Cependant, c'est la solution la plus optimale à laquelle je puisse penser.Il ne nécessite aucune interrogation et tous les threads dorment jusqu'à ce qu'ils aient besoin de faire un travail.