CPU Clocks and Clock Interrupts, and Their Effects on Schedulers (2015)

The rising and falling edges overshoot their levels, then dampen out toward the nominal voltage level.I’m going to use the idealized clock drawing in Figure 1a for the remainder of this discussion.A CPU interrupt is a signal that causes some out-of-band processing to occur. Mostly, the scheduler runs when an interrupt fires, but it may run at other times, too.An operating system typically will have some sort of clock interrupt, which causes code to execute that takes care of tasks that need to be processed periodically. At that time the scheduler will look at its list of processes, figure out which one should be executing, and (possibly) execute a context switch to that process.Clock interrupts fire at a rate much slower than the underlying speed of the CPU. The rate at which the clock executes is a balancing act: the more often a scheduler runs, the easier it is to balance the load between processes (in a time-sharing scheduler), or the faster a higher priority process will actually execute when it is ready (in a real-time scheduler). If your CPU’s clock is running at 6 553 600 Hz (slow by today’s standards), you get a clock interrupt 100 times a second, which was a fairly common frequency for a scheduler (modern x86 architecture clock interrupts execute at a faster rate).4 [Linux2] (I am going to assume a 100 Hz clock interrupt for the remainder of this discussion. “It’s just a matter of putting them all together to get the answer to your question.”When you call sleep(), its operating system-dependent implementation most likely calls an operating system function that suspends the process and causes a context switch – independent of the clock interrupt. (A 1000 millisecond sleep is equal to 100 clock interrupts.) It is easy for the scheduler to decrement a count every time it is executed as the result of the interrupt firing, and change the state of the process to ready-to-execute when the value reaches zero.You should be starting to see that the accuracy of the sleep() call is only as good as the underlying clock interrupt frequency. If the scheduler only runs every 10 milliseconds, you cannot get sub-10 millisecond accuracy from your call to sleep().Let us consider a system where the clock interrupt fires at our assumed rate – 100 times a second, for a period of 10 milliseconds. If your process is such that it is possible to call sleep() at any time between clock interrupts, a 10 millisecond sleep() call will, on average, cause your process to sleep for 5 milliseconds (in the absence of any other process activity). Even if your process is the highest priority process, and should be expected to be scheduled on the next clock interrupt, another interrupt higher in priority than the scheduler's may occur, delaying the execution of the scheduler and by extension further delaying your process. Your process remains ready-to-execute, so that it can be executed on the next context switch, assuming no other higher priority process also is ready-to-execute.There is a common pattern in process control software, represented by the following code fragment:The first pass through this loop can occur at any time relative to the clock interrupt; however, the second and subsequent passes through the loop are somewhat synched to the clock interrupt. The grey boxes represent one possible example of the areas in which the rising or falling edges might actually occur.In general, for a real-time scheduler the lower the priority of the process the higher the jitter is likely to be.7 In a round-robin scheduler jitter is the norm rather than the exception.