clockintr: add a priority queue
- Add cq_pend to struct clockintr_queue. cq_pend is the list of clock
interrupts pending to run, sorted in ascending order by cl_expiration
(earliest deadline first; EDF). If the cl_expiration of two
clockintrs is equal, the first clock interrupt scheduled has priority
(FIFO).
We may need to switch to an RB tree or a min-heap in the future.
For now, there are only three clock interrupts, so a linked list
is fine.
- Add cl_flags to struct clockintr. We have one flag, CLST_PENDING.
It indicates whether the given clockintr is enqueued on cq_pend.
- Rewrite clockintr_dispatch() to operate on cq_pend. Clock
interrupts are run in EDF order until the most imminent clockintr
expires in the future.
- Add code to clockintr_establish(), clockintr_advance() and
clockintr_schedule() to enqueue/dequeue the given clockintr
on cq_est and cq_pend as needed.
- Add cq_est to struct clockintr_queue. cq_est is the list of all
clockintrs established on a clockintr_queue.
- Add a new counter, cs_spurious, to clockintr_stat. A dispatch is
"spurious" if no clockintrs are on cq_pend when we call
clockintr_dispatch().
With input from aisha@. Heavily tested by mlarkin@. Shared with
hackers@.
ok aisha@ mlarkin@