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.