Bagaimana cron menjadwalkan pekerjaan secara internal?

Beberapa jangkrik terdengar dalam pertanyaan ini. Good 'ol RTFC dengan beberapa makalah simulasi kejadian diskrit dan Wikipedia:

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

Algoritme yang digunakan oleh cron ini adalah sebagai berikut:

1. Saat start-up, cari file bernama .crontab di direktori home dari semua pemegang akun.
2. Untuk setiap file crontab yang ditemukan, tentukan waktu berikutnya di masa depan untuk menjalankan setiap perintah.
3. Tempatkan perintah tersebut di daftar acara Franta-Maly dengan waktu yang sesuai dan penentu waktu "lima medan".
4. Masuk loop utama:
   1. Periksa entri tugas di bagian atas antrean, hitung seberapa jauh tugas itu akan dijalankan di masa mendatang.
   2. Tidur selama jangka waktu tersebut.
   3. Saat bangun dan setelah memverifikasi waktu yang tepat, jalankan tugas di bagian atas antrean (di latar belakang) dengan hak istimewa pengguna yang membuatnya.
   4. Tentukan waktu berikutnya di masa mendatang untuk menjalankan perintah ini dan tempatkan kembali pada daftar acara pada waktu itu

Saya menulis posting blog yang menjelaskannya.
Mengutip teks yang relevan dari sana:

• Kita dapat memiliki kumpulan utas terbatas yang akan menjalankan semua tugas dengan mengambilnya dari PriorityBlockingQueue (thread-safe heap) diprioritaskan pada job.nextExecutionTime() .
• Artinya, elemen teratas tumpukan ini akan selalu menjadi elemen yang akan diaktifkan paling cepat.
• Kami akan mengikuti pola produsen-konsumen threadpool standar.
• Kita akan memiliki satu utas yang akan berjalan dalam loop tak terbatas dan mengirimkan tugas baru ke kumpulan utas setelah menggunakannya dari antrean. Sebut saja 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)
        }
    }
}

• Akan ada satu utas lagi yang akan memantau file crontab untuk penambahan pekerjaan baru dan akan mendorongnya ke antrean.
• Sebut saja QueueProducerThread :

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

• Namun, ada masalah dengan ini:
  • Bayangkan Thread1 sedang tidur dan akan bangun setelah satu jam.
  • Sementara itu, tugas baru tiba yang seharusnya dijalankan setiap menit.
  • Tugas baru ini tidak akan dapat dijalankan hingga satu jam kemudian.
• Untuk mengatasi masalah ini, kita dapat meminta ProducerThread membangunkan ConsumerThread dari tidurnya secara paksa setiap kali tugas baru harus berjalan lebih cepat daripada tugas depan dalam antrean:

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

Perhatikan bahwa ini mungkin bukan bagaimana cron diimplementasikan secara internal. Namun, ini adalah solusi paling optimal yang dapat saya pikirkan. Ini tidak memerlukan polling dan semua utas tidur sampai mereka perlu melakukan pekerjaan apa pun.