Source code and usage instructions

I have posted my source code online at http://petergaultney.com/school/CS594_OS/low_power_xinu.tar.gz. My changes to the source code can be found mostly in clkinit.c, clkint.S, initialize.c, xsh_msleep.c, xsh_spawn_decprio.c, xsh_spawn_incprio.c, evec.c, and wakeup.c. Naturally, not all of the code in those files is mine, but the differences between those files and those available at the Xinu website should make my contributions clear. Also, a grep -RF "/***" * will reveal the locations of most of my source code comments, either made to describe my own code, or made in the course of inspecting the Xinu source as I began to understand it.

To test or use the software, the easiest method would be to run it in a virtual machine, as I did. The instructions for setting up your environment can be found, just as they were linked in my first post, here. Then, create a share on your develop-end machine by adding something like the following to /etc/fstab and creating the directory "share" inside the xinu home directory:

xinu_share    /home/xinu/share     vboxsf   gid=1000,uid=1000   0    0

and configure your VirtualBox VM shares as demonstrated in this screenshot:

and untar/gzip the source into a directory inside the directory you chose to share to the guest OS as xinu_share. From that point on, you'll be able to edit files on your host operating system, and just use the guest develop-end OS for compilation and the minicom modem viewer.

System verification and final thoughts

In order to verify that my low-power modifications had not fundamentally altered or even minorly regressed the behavior of the Xinu OS, I designed two simple tests: a scheduling test and a millisecond sleep test. These tests are written as two programs launchable from the shell. The first is a basic millisecond sleep interface, which allows the shell user to perform sleeps with millisecond accuracy. The second is a pair of commands called spawn_incprio and spawn_decprio that spawn 5 processes of increasing priority and decreasing priority, respectively. These processes will complete in order of highest priority to lowest priority, regardless of which command is given.

All three commands were tested on a stock Xinu image as well as my custom low power image, and were verified to work in exactly the same way on both. Their source is provided along with the rest of the Xinu source code that I used to create my low power consumption Xinu OS.

FINAL THOUGHTS

In the course of the development of this low power variant of Xinu, I read and analyzed about 60% of the source code of the OS itself (found in the system and include directories), and about 50% of the shell process code as well. I did not spend any time looking at the device/tty code, though I imagine it would be interesting, and perhaps the source of some strange printf buffering issues I observed while playing with the stock Xinu image. The scheduling subsystem, and in particular the ctxsw assembler routine (which sets up the stack and registers to look as though they are in a function that was called by the new process, and then "returns" from that function), were very interesting because of the way that they seamlessly transfer control from one process to another without . But, to me, the most interesting of all was definitely the interrupt subsystem. The x86 architecture is interrupt-driven, and it seems that a large part of the functionality of an x86 OS depends on its ability to properly manage and handle interrupts, both as external sources of I/O and as an internal process management tool. It would be very interesting to investigate a multicore OS such as Linux to see how it manages handling IRQs on multiple cores without losing parallelism. Further, it would be interesting to attempt to change Xinu into an operating system that operates in protected mode instead of real mode, by converting the various system calls into functions that perform a software interrupt, and then providing software interrupt handlers that transfer control to the actual system calls themselves and eventually return control to the processes via normal scheduling algorithms.

I learned even more than I imagined I would, and I highly recommend Xinu as a study tool for others trying to understanding how an operating system actually does what it does. While Xinu is certainly much simpler than most OSes in use today, the foundational concepts that it requires you to truly understand in order to tinker with it allow the user to begin to actually grasp the more complex realities that face a modern OS.

sleep timers and process scheduling in Xinu

Having successfully switched my main system clock to a handler hooked to the RTC via IRQ8, I was able to provide basic system timing functionality at only 8% CPU usage by the virtual machine in which I was running Xinu. Having reduced this CPU wastage from 100% to 15%, and now again to 8%, I felt quite satisfied. As far as I can tell, there are no other regular interrupts being handled by Xinu, and I suspect that the remaining 8% CPU usage is actually the work performed by the virtual machine to emulate the PIT, RTC, and other hardware timers and resources.
However, my work was not yet quite complete. Without an interrupt-based millisecond timer, my modified version of Xinu would be unable to properly service the millisecond sleep()s offered by the sleepms() API provided in sleep.c.

Studying the process creation, scheduling, preemption, wakeup, and context-switching design of Xinu, I found that Xinu's current scheduling system is basically an absolute-priority system with only no situations under which a process may ordinarily make way for another, lower-priority process. For a process to be chosen to run, it must be at the front of the ready list. The readylist is ordered strictly by process priority, and that order is defined during process insertion. When processes are resume()d, the new process is inserted by ready() into the ready list according to its priority, as previously defined by either create() or chprio(). During a resched(), the previously running process is reinserted into the ready list according to its priority, and the first process in the readylist is removed and given the CPU. Surprisingly, even the chprio() method does not remove and re-insert the process into the ready list, meaning that the process' priority will only functionally change once it has had the opportunity to become the highest priority (i.e. ended up at the front of the readylist) process available to run and then been reinserted into the ready list.

Semaphores and signals (using send()), along with resume() and unsleep() are all methods of causing a resched() and possibly a context switch. However, since all of these can only happen by the will of a an already running process, since no process with a lower priority than the currently running process would ever be chosen by the scheduler, and since no higher priority process can be added to the readylist without one of those four functions being called by the currently running process, there is no need to run a periodic preemption timer, as the currently-running process is always the highest priority process that is available to run anyway.

This means that there in the current Xinu architecture, all that would be needed to complete my low-power Xinu build is a millisecond timer that is active while there are sleeping processes, and deactivated as soon as the sleeping queue is empty again. This was easily accomplished by embedding a call in sleep() to a function that unmasks IRQ0, and embedding a call in wakeup() that masks IRQ0 interrupts if there are no processes in the sleeping queue. Thus, as soon as a process requests to sleep, the timer is activated and regular wakeups commence.

The resulting code in clkinit.c and clkint.S is basically as follows:


void clkinit(void) {
    set_evec(IRQBASE + 8, (uint32)rtcint); /*** set handler for IRQ8 (RTC) */

    sleepq = newqueue();    /* allocate a queue to hold the delta   */
    preempt = QUANTUM;      /* initial time quantum         */
    slnonempty = FALSE;
    clktime = 0;            /* start counting seconds       */

    intv = 15; /*** this should give us a clock rate of 2 Hz */

    /*** first, 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); /*** set the register index to 'B' */
    char reg_B_val = inb(RTC_CMOS);
    outb(RTC_CMD, RTC_REG_B | RTC_NMI); /*** CMOS reads reset the register index to 'D' */
                              /*** so we need to reset it to 'B' */
    outb(RTC_CMOS, reg_B_val | 0x40); /*** this enables the firing of interrupts */

    rtc_nmi_enable(); /*** not sure this is necessary, but may as well */

    /*** now set up Intel 8254-2 (PIT) */
    /*  set to: timer 0, 16-bit counter, rate generator mode,
        counter is binary */

    outb(CLKCNTL, SET_CLOCK0_AS_BINARY_TIMER);

    intv = 1193182/CLKTICKS_PER_SEC;

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

clkint:

    pushal

    cli

    movb    $EOI,%al

    outb    %al,$OCW1_2 

    cmpl    $0,slnonempty   # if no sleeping processes,

    je      clpreem     #   skip to preemption check

    movl    sltop,%eax  # decrement key of first

    decl    (%eax)      #   sleeping process

    jg      clpreem     # must use jg for signed int

    call    wakeup      # if zero, call wakeup

clpreem:

    decl    preempt     # decrement preemption counter

    jg      clret       # must use jg for signed int

    call    resched     # if preemption, call resched

clret:                  # return from interrupt

    sti

    popal

    iret

rtcint: /*** this clock interrupt happens @ 2Hz */

    pushal

    cli

    mov     $EOI,%al

    outb    %al,$OCW1_2

    mov     $EOI,%al

    outb    %al,$OCW2_2 /*** must restore both PICs since this is a second-PIC interrupt */

    /*** to keep the interrupts enabled, we must read RTC register C */

    movb    $RTC_REG_C,%al

    outb    %al,$RTC_CMD

    inb     $RTC_CMOS   /*** currently, we're uninterested in the actual value */

    subw    $1,count2

    ja      cl1     /*** if we're in between half-second ticks, just return */

    incl    clktime

    movw    $2,count2   /*** reset down-counter */

rtcret:

    sti

    popal

    iret

Even better, this low-power system is adaptable to preemptive schedulers with some basic added logic that would intercept all calls to chprio() and the other routines that might possibly affect which process should be currently chosen to run, and temporarily enabling the periodic millisecond wakeups in order to service these situations where preemption is desirable. Best of all, the system would still be able to return to its low-power configuration any time all processes were in a waiting queue for interrupt-signaled I/O, for semaphores, or other inter-process signalling.

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.