We shall now see how an operating system supports wakeup and preemption events.
Like some other OS features we have seen earler,
these events require hardware support in the form of a real-time clock.
We shall study first this hardware and then other features required to
support time management.
Real-Time Clock
A real-time clock is a hardware device that pulses regularly an integral number of times each second, and interrupts the CPU each time a pulse occurs. It is important to distinguish this device from the time-of-day clock that keeps the current time. A time-of-day clock also emits pulses at regular intervals. However, unlike the real time clock, it does not interrupt the CPU after each pulse. Instead, it increments a counter, which the CPU may read to determine the current time. A real-time clock is also different from the CPU clock, which is not visible to an operating system.
The number of times a clock pulses in a second is called clock rate. Typical clock rates are 10Hz, 60Hz, 100Hz, and 1000Hz. In Xinu, the clock rate of the real-time clock is 60Hz.
It is important that clock interrupts be serviced promptly to ensure that they are not lost. The hardware helps by giving a clock the highest priority among the various devices that can interrupt. (In x86 architectures, power outage and interprocessor interrupts are given higher priority than clock, but these are not really devices.) Interrupts are serviced in the order of their priority, and a higher level interrupt can preempt a lower-level one. The software helps by keeping making clock interrupt processing efficient by reducing the number of procedure calls made.
Even if clock interrupt processing can keep up with the clock rate, it is important that the processor not spend all its time processing clock interrupts. This may happen with slow CPUs such as the LSI-11. Therefore it is necessary to adjust the clock rate to match the system.
Ideally, the hardware clock should be slowed down, but this is inconvenient or impossible. Instead, a slower clock can be simulated by the interrupt dispatcher. The dispatcher can divide the clock rate by ignoring a certain number of interrupts before it processes one. For instance, the clock dispatcher in Xinu ignores five pulses before it processes one. Thus the clock rate of 60 Hz is divided by 6 to 10 Hz. This slower simulated rate is called the tick rate, and determines the smallest size of the granularity of preemption and timed delays. (Is this small size a problem?)
Not all computers are connected to a real-time clock.
Systems like Xinu that are designed to run on such systems need to check through
software if a clock exists.
In Xinu the routine _setclkr performs this checking task.
It executes a loop 30,000 times, and if the clock interrupts during this time,
it sets a global flag clkruns to true.
Delta List Processing
We now look at a data structure required to maintain wake-up events. The system keeps a queue of sleeping processes ordered by the time at which they are to be woken up. An element of the queue needs to keep some information about the time at which it is to be woken up. This information is kept in the `key' field of a process table entry. The field could contain:
absolute time of the wake-up event,
time relative to the current time,
the delta (difference) between the times of its wake-up event and the wake-up event of the process in front of it in the queue.
(All times are in units of clock ticks).
Thus if there are four processes with wake-up events scheduled at times 1017, 1027, 1028, 1032, then at time 1000 the keys could contain one of the following three possibilities:
1017 1027 1028 1032--absolute 17 27 28 32--relative 17 10 1 4--delta
A disadvantage of keeping absolute times is that the key fields and the counter that keeps the current time might overflow. A disadvantage of keeping relative times is that every key element needs to be updated on each clock tick. Therefore deltas are kept, and the queue is called the delta list.
The delta list is associated with the procedure insertd (pid, head, key), which, given the relative time of the wake-up event of process pid in key, inserts the process in the appropriate place in the delta list "head" with the appropriate delta stored in the key field. To find the place of the process, the procedure keeps subtracting from key the delta of the processes it visits, till it comes across a process q whose delta is greater than key. It inserts p in front of q with its key equal to the current value of the parameter key. It also subtracts key from q's delta. Thus if at time 1000, a wake-up event for time 1030 was to be inserted, then the following are the values of key as various elements in the list are visited:
initial: 30 visits 1st process: 30 > 17 so key = 30 - 17 = 13 visits 2nd process: 13 > 10 so key = 13 - 10 = 3 visits 3rd process: 3 > 1 so key = 3 -1 = 2 visits 4th process: 2 < 4, so insert process with delta 2, and modify next delta to 4 - 2 = 2.
Sleep10
Given the delta list and procedure insertd, the implementation of sleep10 (n) is easy. It needs to block the process by changing its state and putting it in the delta list. To do so, it:
calls insertd(currpid, clockq, n), where clockq is a global variable.
changes state of process to SLEEP and calls resched
It also takes the following steps for efficiency reasons, which are crucial to make clock interrupt processing fast:
It indicates in global variable slnempty that the delta list is non-empty (the clock dispatcher uses this variable for efficient processing)
It stores address of the key of the process at the head of the queue in variable
sltop (to save the dispatcher from doing this job at clock interrupt time)
Sleep
The routine sleep(n) calls sleep10(10*1000) n div 1000 times and then once
sleep10(10* (n mod 1000)).
Thus the argument of each of these sleep10 is less than 32767 and
together all calls delay 10*n tenths of seconds.