switching to the RTC

Still on a quest to minimize CPU energy wastage by halting the CPU and disabling the millisecond interrupts on IRQ0 when no processes were ready to be scheduled, but failing in my attempt to use the second and third timers on the Intel 8253 as sources of interrupts at lower frequencies, I continued to search for options.

Before proceeding, however, I experimented with changing the behavior of the clkint assembler routine in clkint.S to determine whether it was the interrupt itself that was causing the CPU usage, or the interrupt handler. I soon learned that my own concept of a basic interrupt handler was fatally flawed. Not understanding the handler code, I replaced it with the following version:

clkint:
pushal
cli
sti
popal
iret

Surprisingly, an interrupt handler this simple actually caused major problems. Apparently the PIC requires that you notify it of your reception of an interrupt, and the removed instructions

.set    EOI,0x20
pushal
cli
movb $EOI,%al
outb %al,$OCW1_2
sti
popal
iret

were necessary for doing exactly that. After reinserting these instructions, though of course system timekeeping and preemption no longer happened, the system continued to function. However, CPU usage did not decrease. Apparently, the simple act of waking up to receive an interrupt was requiring significant CPU time.

Obviously, any attempt to conserve energy and CPU cycles would need to come by selectively disabling IRQ0 altogether, while somehow maintaining proper system time and providing preemption and timed millisecond sleeps to processes that needed them.

Research unveiled a number of options. This set of slides on timing measurement in Linux was initially helpful. My options included the Advanced Programmable Interrupt Controller (APIC) timer, the Real Time Clock (RTC), the High Performance Event Timer (HPET), and the Time Stamp Counter (TSC).

According to the OSDev Wiki (a very useful source of information on many operating systems development issues), the APIC timer runs at the speed of the CPU clock, and therefore it is necessary to first discover your CPU clock speed and then adjust accordingly. The HPET is part of a newer specification designed to replace the PIT and the RTC, and therefore must be discovered and configured using the Advanced Configuration and Power Interface (ACPI).

In contrast to these more complicated solutions, I decided that using the RTC would be perfectly suited to my goals, as its own clock speed is an exact divisor of a second, allowing basic timekeeping without any arithmetic drift. I proposed to use the RTC to keep a twice-per-second tick (its slowest available interrupt frequency), while using the PIT only in cases where millisecond accuracy was needed.

The RTC initialization proved to be only slightly more involved than the PIT initialization, mainly because the RTC does not automatically send interrupts to IRQ8 even though IRQ8 is reserved for its use. Instead, it requires that you turn those interrupts on via configuration. While configuring the chip, it is also necessary to disable the chip from receiving Non-Maskable Interrupts (NMIs) in order not to leave the RTC chip in an undefined state by only halfway configuring it. The following code performed the necessary initialization:


#define RTC_CMD     0x70  /*** Control port for RTC */
#define RTC_CMOS    0x71  /*** mem I/O port for RTC */
#define RTC_REG_A   0x0A
#define RTC_REG_B   0x0B
#define RTC_REG_C   0x0C
#define RTC_NMI     0x80 

.....

{

   /*** write the desired rate into the bottom 4 bits of register A */

    outb(RTC_CMD, RTC_REG_A | RTC_NMI);

    outb(RTC_CMOS, (char)intv);

    /*** then, enable IRQ8 to start the clock */

    /*** by writing 0x40 to enable bit 6 of register B */

    outb(RTC_CMD, RTC_REG_B | RTC_NMI);

    char reg_B_val = inb(RTC_CMOS);

    outb(RTC_CMD, RTC_REG_B | RTC_NMI); 

    /*** this enables the firing of interrupts */

    outb(RTC_CMOS, reg_B_val | 0x40); 

    rtc_nmi_enable();

}

My initial attempts were failures because I did not re-disable the NMIs with every write to the RTC_CMD register, causing the RTC to end up in a failed state and occasionally causing Global Protection Faults. Eventually, however, I was able to verify that I was receiving IRQ8 interrupts twice per second, fulfilling the first half of my goal!

interrupt handling in Xinu

Further investigation revealed that a source of the CPU usage was likely the timed interrupt wakeups found in clkint.S. The code looked like this:

clkint:
pushal
cli
movb $EOI,%al
outb %al,$OCW1_2
incl ctr1000
subw $1,count1000
ja cl1
incl clktime
movw $1000,count1000
cl1:
cmpl $0,slnonempty
je clpreem
movl sltop,%eax
decl (%eax)
jg clpreem
call wakeup
clpreem: decl preempt
jg clret
call resched
clret:
sti
popal
iret

Apparently, this code was being called by an interrupt and was thereby providing the system with a sort of timer that it was using to do scheduling, or preemption, or both. However, despite the counting code being relatively easy to decipher, there was still quite a bit of mystery to me here.

Not knowing very much about interrupts and their methods of operation, I decided to do some research into interrupts before proceeding. I first discovered that Xinu has an interrupt table initialization routine in evec.c called initevec(), which is called inside sysinit() in initialize.c. This appears to set NULL interrupt handlers for all interrupts, then to initialize the Intel 8259 Programmable Interrupt Controller (PIC), and then to mask all maskable interrupts (IRQ0-IRQ15) using setirmask, which writes a bitwise interrupt mask to the PIC.

So with no interrupts being actively handled by the operating system after initialization, it was time to find out who was enabling the interrupt that was causing my increased CPU usage. I eventually traced the call to the function clkinit() in clkinit.c, called from the very end of the sysinit() function in initialize.c:

void clkinit(void)
{
uint16 intv;

/* Set interrupt vector for clock to invoke clkint */
set_evec(IRQBASE, (uint32)clkint);

intv = 1193; /* clock rate in KHz */

sleepq = newqueue();
preempt = QUANTUM;

slnonempty = FALSE;

clktime = 0;

/*  set to: timer 0, 16-bit counter, rate generator mode,
counter is binary */
outb(CLKCNTL, 0x34);

/* must write LSB first, then MSB */
outb(CLOCK0, (char) (0xff & intv) );
outb(CLOCK0, (char) (0xff & (intv>>8)));
return;
}

This code, it seemed, was responsible for activating an interrupt handler for and unmasking IRQ0, and then setting up some sort of periodic interrupt with an unknown timer found at the bus address stored in CLKCNTL. Though this part of the source code gave no clues as to what type of device this was, I soon discovered that the Intel 8253 is a Programmable Interval Timer (PIT) that appears in all x86 systems.

My first attempt at tinkering with the PIT was to simply change the frequency, but my initial experiments were confusing. It seemed that lowering the value of intv (apparently the timer rate) caused my timer to speed up, while increasing it caused the timer to slow down. I therefore tracked down the Intel manual for the 8254-2, the specific superset more commonly in use today, and discovered that the rate is actually a divisor instead of a frequency. The internal counting element is set to the number provided, and then, at a rate of ~1.193181.81 MHz, decrements the counter. Upon reaching, 0, the counter fires an interrupt and, if set as a rate-generating counter, resets itself to the original value and begins decrementing again. 

Further documentation revealed that the 8253 includes not one but three timers. After verifying that, by changing the divisor of Timer 0 (and thereby breaking the accuracy of the Xinu system clock), I could lower the CPU usage of the Xinu system to as low as 8%, I decided that the best thing to do would be to somehow use the second and third timers in the 8253 to provide different interrupt rates under different system loads, while preserving the system's ability to keep accurate time.

Unfortunately, after writing the necessary code to set up and activate the timer interrupts from Timer 1 and Timer 2, I was disappointed to find that no interrupts were arriving from those timers. A long investigation culminated in the discovery that those timers are often not hooked to anything in modern architectures, and that Timer 0 is definitely the only timer hooked up to IRQ0. Thus, in order to preserve the core system functionality of millisecond sleeps (found in sleep.c) alongside accurate system timekeeping, it would be necessary to find another source of periodic interrupts.

process idling in Xinu

While experimenting with Xinu inside a virtual machine, I soon found that my laptop was getting quite warm, and the fan was running constantly. Examining my Mac's Activity Monitor, I saw that one of my CPUs was being used at 100% any time the Xinu VM was running. I decided to investigate the cause of the high CPU utilization.

The culprit wasn't hard to find. In initialize.c, after creating and "resuming" a shell process, the nulluser function goes on to enter a while (1) idle loop. The code comment at the top of the function indicated that this process remained in existence in order to provide the scheduler with a lowest-priority item suitable for scheduling on the CPU when no other process was "ready" to execute.  Extended Internet research discovered that many modern OSes provide a low priority process that is always 'ready' to execute in order to simplify the code for the scheduler, avoiding the necessity of a special case for when no processes are ready to execute. However, of course, most OSes do not actually consume the full time and power of the CPU during these busy-waiting loops.

I began to wonder if it would be possible to make the necessary changes to Xinu to provide a low-power/efficient busy-wait loop for when no processes were scheduled. Especially for an OS that is otherwise well suited for applications with low resource (memory, CPU, etc.) availability, it would seem to make sense to provide the benefit of low power consumption when no processes are ready to execute.

According to Wikipedia, modern architectures use the HLT (halt) instruction to allow an interrupt-driven CPU to enter a low power state while waiting for a timer or I/O-based interrupt to reactivate another process. Examining the code in intr.S, I found an existing assembler function "pause" that first enables interrupts with the sti instruction, and then issues the hlt instruction. By doing so, pause ensures first of all that any incoming interrupts will be able to wake the processor for handling, and then puts the processor into the low-power idle state to wait for such interrupts.

I initially attempted to have the while(1) loop in the nulluser() method in initialize.c simply execute a hlt instruction, since the nulluser() method had already enabled interrupts, but I found that I was causing boot hangups on occasion. By calling the pause() routine, I immediately realized a 85% reduction in CPU usage, without impacting any OS functionality. But I found myself wondering if there was anything to be done about the remaining 15% CPU usage, which was apparently happening even when no processes other than the shell were running on the Xinu system.

process creation in Xinu

The first order of business, upon resigning myself to an OS with no persistent storage, was to experiment with the interface presented by the shell. It was apparent that the shell had a very low number of built-in functions (the full list: argecho, cat, clear, devdump, echo, exit, help, kill, memdump, memstat, ps, ?), and none of these performed any long-running computation suitable for analyzing process scheduling.

Therefore, I began to investigate the feasibility of creating my own processes, and launching them from the shell. Initial investigation revealed that the Xinu shell itself is in fact run like any other system process, as it is created by a program called "main", which is itself created by a function called nulluser, found in initialize.c. According to shell.c, the shell then takes input and attempts to match it to one of a strictly bounded array of valid commands. Some of these are listed as being "builtins", and some are not - the builtins are called directly from within the shell's frame, while the non-builtins are created as new processes.

Further inspection of the code revealed that processes are create()d in a state of suspension, and must be resume()d to put marked as ready for execution. When the process is created, the operating system selects an available entry in the process table and fills in certain details, including a return location to which the code will progress when the process exits. This is set as a call to kill() with the process's pid, which builds in the capability that keeps the process table devoid of zombie processes.

starting out with Xinu on VirtualBox

Having examined the options for probing the workings of an operating system, I decided that Xinu would be the best for tying together the general concepts of an operating system with their most basic implementation.

Going down this path proved far from easy. The first challenge was getting a working version of Xinu.

According to the VirtualBox configuration document found here, the setup process should be fairly simple. However, the document fails to specify that it is the xinu-appliance.tar.gz file in the Xinu VM downloads directory that must be downloaded to start the setup process, instead of xinu-vm.tar.gz.

Having followed the document's instructions in configuring the virtual machines and then building Xinu on the development system, I found that I was not receiving any response from the Xinu backend system. As it turned out, I had improperly configured the backend VM to create the serial port COM1 - only the development system should create the port. Having corrected this, I soon found myself attached to a running Xinu machine via the minicom terminal emulator.

Almost as a reflex, the first command I typed upon reaching the Xinu shell was "ls". Sadly, this received only the message "command ls not found." Of course, I quickly discovered that Xinu does not implement a file system at all. In fact, in the VirtualBox setup, the GRUB bootloader loads the entire Xinu OS into memory via TFTP, and no form of persistent storage is made available by the operating system at all.

I spent some time scouring the Internet for versions of Xinu that had built-in filesystems, figuring that such a version would make for easier experimentation with other OS functionality, but though I stumbled across a couple of different implementations, I was unable to get any of them to compile on the developer box, and I realized that it would be wiser to spend my time investigating the way that Xinu is built.