cron はどのようにジョブを内部的にスケジュールしますか?

この質問でいくつかのコオロギが聞こえました。いくつかの離散イベントシミュレーションの論文とウィキペディアを含む RTFC の良さ:

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

<ブロック引用>

この cron で使用されるアルゴリズムは次のとおりです:

<オール>

起動時に、すべてのアカウント所有者のホームディレクトリで .crontab という名前のファイルを探します。

見つかった crontab ファイルごとに、次回に各コマンドを実行する時間を決定します。

これらのコマンドを、対応する時間と「5 フィールド」時間指定子とともに Franta-Maly イベントリストに配置します。

メインループに入ります:<オール>

キューの先頭にあるタスクエントリを調べて、どれくらい先まで実行されるかを計算します。

その時間だけ眠る

目覚めて正しい時刻を確認した後、タスクを作成したユーザーの権限で、キューの先頭で (バックグラウンドで) タスクを実行します。

次回このコマンドを実行する時間を決定し、その時点でイベントリストに戻します

それを説明するブログ記事を書きました。
そこからの関連テキストの引用:

PriorityBlockingQueue からタスクをピックアップしてすべてのタスクを実行する、有限のスレッドプールを持つことができます。 (スレッドセーフなヒープ) job.nextExecutionTime() を優先 .
つまり、このヒープの一番上の要素が常に最も早く起動するということです。
標準のスレッドプールプロデューサー/コンシューマーパターンに従います。
無限ループで実行され、新しいジョブをキューから消費した後にスレッドプールに送信するスレッドが 1 つあります。これを 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 ファイルを監視し、それらをキューにプッシュするもう 1 つのスレッドがあります。
QueueProducerThread としましょう :

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

しかし、これには問題があります:
- スレッド 1 がスリープ状態で、1 時間後に起動するとします。
- その間、毎分実行されるはずの新しいタスクが到着します。
- この新しいタスクは、1 時間後まで実行を開始できません。
この問題を解決するために、新しいタスクがキュー内の先頭のタスクよりも早く実行される必要があるときはいつでも、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 が内部で実装されている方法ではない可能性があることに注意してください。ただし、これは私が考えることができる最も最適なソリューションです。ポーリングは必要なく、すべてのスレッドは作業が必要になるまでスリープします。