Как cron внутренне планирует задания?

Несколько сверчков услышали в этом вопросе. Старый добрый RTFC с некоторыми документами по моделированию дискретных событий и Википедией:

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

Алгоритм, используемый этой cron, выглядит следующим образом:

1. При запуске найдите файл с именем .crontab в домашних каталогах всех владельцев учетных записей.
2. Для каждого найденного файла crontab определите, когда в следующий раз будет выполняться каждая команда.
3. Поместите эти команды в список событий Франта-Малы, указав соответствующее время и указав их "пять полей" спецификатора времени.
4. Enter main loop:
   1. Examine the task entry at the head of the queue, compute how far in the future it is to be run.
   2. Спите в течение этого времени.
   3. После пробуждения и проверки правильного времени выполните задачу в начале очереди (в фоновом режиме) с привилегиями пользователя, который ее создал.
   4. Определите следующий раз в будущем, чтобы запустить эту команду, и поместите ее обратно в список событий в это время.

Я написал сообщение в блоге с описанием этого. < br /> Цитата оттуда:

• У нас может быть конечный пул потоков, который будет выполнять все задачи, забирая их из PriorityBlockingQueue (потокобезопасной кучи) с приоритетом job.nextExecutionTime().
• Это означает, что верхний элемент этой кучи всегда будет тем, который сработает быстрее всего.
• Мы будем следовать стандартному шаблону производитель-потребитель пула потоков.
• У нас будет один поток, который будет работать в бесконечном цикле и отправлять новые задания в пул потоков после их использования из очереди. Назовем его 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)
        }
    }
}

• Будет еще один поток, который будет отслеживать файл crontab на предмет любых новых добавлений заданий и помещать их в очередь.
• Назовем его QueueProducerThread:

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

• However, there is a problem with this:
  • Imagine that Thread1 is sleeping and will wake up after an hour.
  • Тем временем появляется новая задача, которая должна выполняться каждую минуту.
  • Эта новая задача сможет начать выполнение только через час.
• Чтобы решить эту проблему, мы можем заставить ProducerThread пробудить ConsumerThread из спящего режима принудительно, когда новая задача должна выполняться раньше, чем передняя задача в очереди:

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

Обратите внимание, что это может быть не так, как внутренняя реализация cron. Однако это самое оптимальное решение, которое я могу придумать. Это не требует опроса, и все потоки спят, пока им не понадобится выполнять какую-либо работу.