79

How do "modern" cron daemons internally schedule their jobs? Some cronds used to schedule a run every so often via at. So after a crontab is written out, does crond:

  1. Parse the crontab for all future events and the sleep for the intervals?
  2. Poll an aggregated crontab database every minute to determine if the current time matches the schedule pattern?
  3. Other?

Thanks,

2 Answers 2

92

A few crickets heard in this question. Good 'ol RTFC with some discrete event simulation papers and Wikipedia:

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

The algorithm used by this cron is as follows:

  1. On start-up, look for a file named .crontab in the home directories of all account holders.
  2. For each crontab file found, determine the next time in the future that each command is to be run.
  3. Place those commands on the Franta-Maly event list with their corresponding time and their "five field" time specifier.
  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. Sleep for that period of time.
    3. On awakening and after verifying the correct time, execute the task at the head of the queue (in background) with the privileges of the user who created it.
    4. Determine the next time in the future to run this command and place it back on the event list at that time
9
  • 6
    Based on the man page for cron, it looks like it wakes up every minute to check if it should run a job: "cron then wakes up every minute, examining all stored crontabs, checking each command to see if it should be run in the current minute." This is from Vixie Cron which came installed on Debian (written by Paul Vixie). I think the algorithm you described was used when waking up every minute was too costly.
    – carleton
    Commented Sep 14, 2016 at 2:45
  • 2
    I wish I could find a description of a franta-maly event list somewhere online. Is this a common data structure? Commented Jan 28, 2018 at 20:14
  • 6
    @TylerBrock, I believe OP is referring to Franta, W. R., and Kurt Maly. An Efficient Data Structure for the Simulation Event Set. University of Minnesota, staff.ii.pw.edu.pl/~gjb/aal/index_lists.pdf. Commented Dec 18, 2018 at 13:48
  • Amazing, thank you @AaronBlenkush! Been trying to answer that question for a while now. Commented Jan 15, 2019 at 18:11
  • 1
    @ifly6 the short oversimplified answer is that a process can tell the kernel's process scheduler to wake it up after a certain amount of time. The process scheduler uses the CPU's hardware to keep track of time. There is of course way more to process scheduling than will fit in a comment.
    – Vinay Pai
    Commented Oct 16, 2019 at 18:08
15

I wrote a blog post describing it.
which contains my thoughts on how to implement task scheduling utilities like Cron or Quartz.

Quoting the relevant text from there:

  • We can have a finite thread-pool which will execute all the tasks by picking them up from a PriorityBlockingQueue (thread-safe heap) prioritized on job.nextExecutionTime().
  • Meaning that the top element of this heap will be always be the one that will fire the soonest.
  • We will be following the standard threadpool producer-consumer pattern.
  • We will have one thread which will be running in an infinite loop and submitting new jobs to the thread pool after consuming them from the queue. Lets call it 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)
        }
    }
}
  • There will be one more thread which will be monitoring the crontab file for any new job additions and will push them to the queue.
  • Lets call it 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.
    • Meanwhile a new task arrives which is supposed to run every minute.
    • This new task will not be able to start executing until an hour later.
  • To solve this problem, we can have ProducerThread wakeup ConsumerThread from its sleep forcefully whenever the new task has to run sooner than the front task in the queue:
@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()
        }
    }
}

Note that this might not be how cron is implemented internally. However, this is the most optimal solution that I can think of. It requires no polling and all threads sleep until they need to do any work.

2
  • Right, but how getNextExecutionTime works? I'm trying to figure out how does it merge all these schedules to get the next time and I cannot tell. Commented Aug 5, 2021 at 23:06
  • The intial value of nextExecutionTime will have to parsed from the cron string. For instance, if cron string says that the job should be executed every 10 minutes, then when we read this from the cron file, we will set the next execution time to currentTime + 10 minutes. Since its a recurring job, after the first run, a new job will be created with the next closest execution time: job = job.copy().setNextExecutionTime(getCurrentTime() + job.getRecurringInterval()); Commented Aug 6, 2021 at 13:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.