*scratch*

vijay's weblog

Job scheduler

This post describes a simple job scheduler. Each job description consists of a procedure and some ticks into the future. The scheduler will pick up the job after the given ticks (seconds) and run the procedure. A job description is represented using the following structure. (All code in Spark-Scheme.):

(define-struct job (run-at proc))

There is a fixed size vector that is used to store the jobs.

(define max-jobs 10)
(define jobs (make-vector max-jobs ()))

The index on which a job get stored is calculated as:

(remainder (+ (current-seconds) ticks) max-jobs)

The job is added to a list at the resulting index. The following procedure contain the complete logic for scheduling a job:

(define (schedule-job ticks job-proc)
  (let* ((run-at (+ (current-seconds) ticks))
         (job (make-job run-at job-proc))
         (index (remainder run-at max-jobs))
         (q (vector-ref jobs index)))
       (vector-set! jobs index (cons job q))))

The scheduler wakes up for each second and run all the jobs scheduled for that second. If the current list has jobs that are scheduled to run in the future, they are left back to be executed later:

(define (scheduler)
  (sleep 1)
  (run-jobs (current-seconds))
  (scheduler))

(define (run-jobs now)
  (let* ((index (remainder now max-jobs))
         (q (vector-ref jobs index)))
    (let loop ((old-q q) (new-q ()))
      (if (not (null? old-q))
          (let ((job (car old-q)))
            (if (run-job job now)
                (loop (cdr old-q) new-q)
                (loop (cdr old-q) (cons job new-q))))
          (vector-set! jobs index new-q)))))

 (define (run-job job now)
   (if (<= (job-run-at job) now)
       (begin
         (thread (job-proc job))
         #t)
       #f))

The scheduler runs in its own thread:

(define (run-scheduler)
  (thread scheduler))

A test run of the scheduler:

> (run-scheduler)
> (schedule-job 5 (lambda () (printf "group1 job1~n") (flush-output)))
> (schedule-job 5 (lambda () (printf "group1 job2~n") (flush-output)))
> (schedule-job 15 (lambda () (printf "group3 job1~n") (flush-output)))
> (schedule-job 10 (lambda () (printf "group2 job1~n") (flush-output)))
;; after 5 seconds:
group1 job1
group1 job2
;; after 10 seconds:
group2 job1
;; after 15 seconds:
group3 job1

Reference: The Design and Implementation of the FreeBSD Operating System.