Linux cron 如何在内部调度作业？

How does cron internally schedule jobs?

提问by Jé Queue

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

“现代”cron守护进程如何在内部安排他们的工作？有些人crond过去常常通过at. 因此，在写出 crontab 后，会执行以下操作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?

1. 解析所有未来事件的 crontab 和间隔的睡眠？
2. 每分钟轮询一个聚合的 crontab 数据库以确定当前时间是否与计划模式匹配？
3. 其他？

Thanks,

谢谢，

采纳答案by Jé Queue

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

在这个问题中听到了一些蟋蟀。Good 'ol RTFC 与一些离散事件模拟论文和维基百科：

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

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

这个cron使用的算法如下：

1. 启动时，在所有帐户持有者的主目录中查找名为 .crontab 的文件。
2. 对于找到的每个 crontab 文件，确定将来每个命令要运行的下一次。
3. 将这些命令与相应的时间和“五场”时间说明符放在 Franta-Maly 事件列表中。
4. 进入主循环：
   1. 检查队列头部的任务条目，计算它在未来运行多远。
   2. 睡那段时间。
   3. 在唤醒并验证正确时间后，使用创建它的用户的权限在队列的头部（在后台）执行任务。
   4. 确定以后下一次运行这个命令并将其放回当时的事件列表中

回答by Anmol Singh Jaggi

I wrote a blog postdescribing it.
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:

• 我们可以有一个有限的线程池，它将通过从PriorityBlockingQueue优先级为 的（线程安全堆）中提取它们来执行所有任务job.nextExecutionTime()。
• 这意味着该堆的顶部元素将始终是最快触发的元素。
• 我们将遵循标准的线程池生产者-消费者模式。
• 我们将有一个线程在无限循环中运行，并在从队列中使用新作业后将新作业提交到线程池。让我们称之为QueueConsumerThread：

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

void executeJob(job, jobQueue){
    threadpool.submit(job); // async call
    job = job.copy();
    job.setNextExecutionTime(getCurrentTime() + job.getExecutionInterval());
    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:

• 还有一个线程将监视 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.
  • 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:

• 但是，这有一个问题：
  • 想象一下，Thread1 正在睡觉，一个小时后会醒来。
  • 同时，一个新任务到达，它应该每分钟运行一次。
  • 这个新任务要到一个小时后才能开始执行。
• 为了解决这个问题，我们可以让 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.
            jobQueueConsumerThread.interrupt()
        }
    }
}