This page is dedicated to describing my work for the OS Bakeoff, which was the finale to a semester long advanced operating systems class. Students started by building their own shell, and later added support for booting the OS (on X86 hardware), paging (protected memory management), multiple program environments, scheduling, and preemptive multitasking to name a few.

VGA Mode 13h Graphics

With the goal to have an OS splash screen, I started to add code to initialization code (init.c). Looking at the console functions, I guessed the video buffer was at KERNBASE+A000. Modifying this address area had no effect on the monitor's graphics. I determined I needed to enter VGA mode 13 by calling the BIOS with an interrupt (int) 10h. This could only be done in real mode, and so I made a small modification to the bootstrapper assembly (Boot.S) to set this up. I hoped this setup in real mode would initialize the video memory address space (A000) and persist even as the kernel transitioned into 32bit protected mode. However, even with these modifications, I couldn't get anything to render on screen in the kernel. To ensure my setup code worked and that VGA graphics were even possible, I started to make video memory writes in Boot.S, which, after some tinkering, yielded working pixel drawing. With several hours already elapsed and several other ideas I wanted to pursue, I decided to abandon protected mode drawing functionality. Instead, I coded a simple proof-of-concept drawing demo in the bootloader, which draws 6 diagonal lines of various colors. With the ability to draw pixels (into essentially a 320x240 matrix), adding functions to draw rectangles, line segments, and even circles would be easy.

Colored Console Text

Having already hunted around the console drawing code for VGA graphics mode, I decided to hack in colored text support (backgrounds are just as easy, but I limited the scope for simplicity). I provide a kernel level function to set the current text color, which could be easily wrapped in a system call. Although the standard color output remains white, I color kernel error messages in red or pink (panics, trap frames, etc.) and console input in green. Determined to get a holiday-themed splash screen working, I got some nice ASCII art, which I painstakingly edited so it would fit on the console, and added some additional text, including a stylized ChriOS. The coloring is not done inline via some printf parsing mechanism. Instead, I had to decompose the ASCII art into its various color sequences, change the console to the desired color, and write text to the screen. Although time consuming, I’m very pleased with the final result.

Quasi–Lottery Based Scheduler

The current round robin scheduler does not draw a distinction between processes that yield the CPU voluntarily and ones that are preempted. I wanted to code a scheduler that favored friendly processes that yielded the CPU. First, I modified the kernel function sched_yield() so it took an argument noting whether the related process’ time quantum was complete or not (this distinction comes from whether sched_yield() was being called by a system call or from trap handling code). To favor processes that were friendly, I decided to use a quasi-lottery based scheduling system. This required the env structure to have an additional tickets field, which contains the number of tickets the process has been awarded. All processes start with 5 tickets. Every time a process is scheduled to run, a ticket is taken. Processes can have no less than 3 tickets. Processes that yield the CPU via a system call are awarded one ticket, but can have no more than 10. With this ticket system in place, a facility to randomly select the winning process was needed, and so I found code for a random number generator online (code is credited appropriately in sched.c). In short, the random number is used to select a ticket from the ticket pool. The ticket that is selected has the index in the envs array of the process that won the lottery.

int winner = genrand_int32()%totalTickets;

It would be very easy to add an interface to let users change the per-process ticket allotment, which would in effect provide scheduling priorities. All the functionality is there and the system calls would only need to be a few lines of code.

This sub-project was for fun. In it’s current form, it’s rather lousy, and processes can certainly take advantage of the scheduler by yielding (perhaps at the very end of it’s allotted quantum) in order to horde tickets and be unfairly favored. Ultimately, it provides a platform on which to make a smarter scheduler.

© Chris Harrison