The clock interrupt handler

The most important part of the clock driver is the clock interrupt handler. This is called every time there is a clock interrupt a.k.a clock-tick. All the basic timekeeping work is done here.

Everything done in the interrupt handler is a simple integer operation: arithmetic, comparison, logical AND/OR or assignment. There is no function call to complete the time-keeping work. So these operations are guaranteed to finish predictably and very fast.

One interesting point here is that since interrupts can be disabled by the system, clock-ticks can be lost. In some cases Minix can correct for this effect by maintaining lost clock-ticks in a global variable. Usually, when interrupts are disabled long enough that one or more clock-ticks may be lost the boot monitor is involved in the flow and it can keep track of time with the help of the BIOS. The boot monitor returns the number of ticks lost and this is used for the correction.

What does the clock driver do?

We talked about clock hardware in the last post. This post describes the different functions performed by the clock driver:

1. The first function is to maintain the time of the day. The logic is very simple - keep a count of the clock-ticks and compute the time of the day. Since a large number of clock-ticks arrive every second the design should take into account overflow possibilities. A 32-bit counter can overflow pretty quickly for even a modest clock-rate. Multiple techniques can be used to overcome this problem: a) Use larger counters (say 64 bit counters). b) Maintain time in seconds rather than ticks using a resettable subsidiary counter that counts ticks until a whole second has been accumulated. c) Count the clock-ticks but do it relative to the time the system was booted and then compute time of day by adding the boot time to the clock-tick counter.
2. The second function is to prevent processes from running too long. Whenever a process is started (or resumed), the scheduler initializes a counter with the value of that process' quantum in clock-ticks. At every clock-tick, the clock driver decrements this counter by 1 and when the counter reaches zero, the clock-driver calls the scheduler which switches out the currently running process and schedules another process.
3. The third function is to do CPU accounting. The idea is to keep track of CPU utilization by each process. Various techniques exist for this, one of them being to 'charge' each clock-tick to the currently running process. But the number of clock-ticks charged to a process does not always indicate a proportional utilization because the running process can be interrupted any number of times between clock-ticks. Accurate CPU accounting is very expensive and so it is rarely done. 
4. The fourth function is to be able to provide a timer functionality to running processes. Many times running processes may request the OS to give them a signal/warning/wake-up call after a specified time interval. This is accomplished by the clock driver by using multiple virtual clocks (since there is only one physical clock) which are basically counters in different data structures that are all updated each time the clock-driver runs. Based on which counter reaches zero, the clock driver causes a signal to be sent to the appropriate process. Parts of the OS also use timers to be called back at future times. These are called watch-dog timers and use the same mechanism.
5. Lastly the clock-driver can be used to do profiling. It can record the position of the program counter for any process that is being profiled and over the lifetime of the process a graph of where it is spending time can be created. 

The Clock Task in Minix

The clock task in Minix is driven by interrupts generated by the clock hardware. The clock task is special in that it executes in kernel space and has access to all kernel functions and data. User space processes can access the clock task only indirectly via the system task.

But first a little info on the clock hardware.

The principle of crystal oscillation is behind most computer clocks. A properly cut quartz crystal which is mounted under tension can be made to generate a periodic signal of very high accuracy. The frequency of the oscillation depends upon the type of crystal and the tension it is subjected to. This signal is used as the synchronizing signal to every circuit in the computer. Think of the clock as the conductor of an orchestra and the rest of the computer components as the musicians who play the symphony. Another way to look at the clock is as a traffic cop who controls the flow of traffic by periodically stopping some and letting others move.

The signal from the oscillator is fed into a counter to make it count down to zero. When the counter gets to zero, it causes a CPU interrupt, resets itself to its max value and the cycle continues. The max value is saved in a holding register from where it can be copied into the counter.

The periodic interrupts from the clock hardware are called clock-ticks. Modern computers have programmable clocks in which the interrupt frequency can be controlled by software.

The CPU can respond to the clock interrupt in a variety of ways, one of which is the initiation of a context switch.

One more thing. The clock task is designed in such a way that it is guaranteed to finish its work before the next clock tick arrives.

Will be back

I know I have been silent for more than a year now! Will be back with more in 2012.

kernel/proc.c - sys_call() internals

I gave some idea about sys_call() in the preceding diagrams. sys_call() does a number of checks before it allows a message or notification to be passed from one process to another. These are all part of the security mechanisms in the kernel that keep processes from doing things they are not allowed to do and from corrupting each other's memory maps. Assuming that a process has just made a system call, here is the list of checks that happen:

1. Does the process have the privileges to make this particular system call? (the priv structure for this process in the process table is looked up to determine this)
2. In the case of a 'send' or 'notify', is the destination a valid process? In the case of a 'receive' is the source a valid process? Note that a caller can specify 'ANY' as its source in which case it is looking for a message or notification from any process, so this check is unnecessary for that case. 'ECHO' is also a special case where this check doesn't make sense.
3. Does the message pointer point to a valid region in memory i.e. is it really within the memory map limits of the calling process? Again, the memory map limits are available in the memmap struct for this process in the process table.
4. If the request is to 'send' to some process, is the caller allowed to send to the destination process?
5. Is the destination process running?
6. Has system shutdown started?
   

If all the checks above have passed then call one of the following functions: mini_notify(), mini_receive() or mini_send() depending upon the nature of the request.

Refer to the 'Message Primitives and Process States' diagrams (preceding posts) for details on what happens within the above functions.

Comments welcome.

Message Primitives and Process States - Case 3

Message Primitives and Process States - Case 2