Extending the Reason Scheduler: Removing a Job
In this article we will extend Reason Scheduler to support a remove functionality
First, the Scheduler.remove method must take an argument that uniquely identifies the job which is to be removed. A possible solution is to add an id field of type int to the job record:
However, doing this would require users of the Scheduler API to deal with assigning a unique id to a job before adding it; notice the signature of Scheduler.add:
So instead, create a record called internalJobRep and keep it private by not adding its signature to Scheduler.rei, it should be identical to the original job record with the addition of anid field. internalJobRep will replace the use of job everywhere in the internals of the Scheduler. job will only be used as an argument to Scheduler.add.
To generate a unique id for each job, add a field called id_counter of type ref(int) to the scheduler record. Don’t forget to initialize the counter in Scheduler.create:
Notice how queue changed from type Heap.t(long, job) to Heap.t(long, internalJobRep).
Here is an updated Scheduler.add reflecting all previous changes:
The updateTimer method is a refactor of the code previously within the block statement following if(has_higher_priority(next_invocation, key)). Scheduler.add returns the id of the job we just added, so that the returned id can later be used as an argument to Scheduler.remove.
Since the Heap module is a generic heap with no knowledge of the values it stores, match_job_id is a predicate function passed to Heap.remove to identify the element we want to remove. Heap.remove throws the exception RemoveElementNotFound if no such job is found.
The block statement within the switch statement at the end of Scheduler.remove handles two cases: the case in which the removed job was the last job in the heap, and the case in which the removed job was at the head of heap.
That’s all for Scheduler.remove, now for Heap.remove:
The search methods returns the index in heap.queue of the heap element which is to be removed. If the index is None(meaning no job with the specified id exists), the RemoveElementNotFound exception is raised, otherwise, the heap element at that index is swapped with the heap element at the tail of heap.queue. The heapify method is then called with the aforementioned index to enforce the max heap property in case it got violated.
Below is the implementation for the search helper method. It recursively iterates through heap.queue looking for the heap element satisfying the criteria provided in the match argument:
And that brings us to the end of the implementation of the remove functionality.
As a reminder, the full code base for the scheduler, including the the remove functionality along with the related test cases is available in the solutions branch.
Attribution
I would like to thank Ali for reviewing this article and carbon.now.sh for generating the pretty code snippets.
