[LOT-2] Analyze the xv6 scheduler

[hatfield-c]

We need to examine the xv6 scheduler, and determine the best way to replace it with our lottery scheduler.

xv6 currently utilizes a Round Robin scheduler, and due to the modular nature of the operating system we should be able to identify the few specific lines of code we need to swap out in order to utilize our own custom lottery scheduler.

[hatfield-c]

The professors gave us some helpful hints on where to first examine the scheduling functionality of xv6, and after looking it over, the functionality is primarily localized to two file locations:

• kernel/proc.h
• kernel/proc.c

Inside of kernel/proc.c, there is a function titled "scheduler(void)", and this is where the main functionality of the round robin scheduler is located. While it would be more in line with best practices to abstract the code within the function further, thus preserving the round robin methodology for comparison testing between our new solution, for the scope of this assignment we will just replace the code inside the function outright.

[hatfield-c]

Before we can implement our scheduler, we need to develop the infrastructure that it will be relying on. Thus, issues for the following features must be created:

• Identify a data structure within the existing code to hold the number of tickets a process has. From initial examination, the proc structure inside of kernel/proc.h looks to be a valid candidate. Each process receives its own virtualized cpu when it is created, so logically each process should receive its own cpu data structure.
• Develop the system call to set the number of tickets the calling process has. This system call will need to have some way to access the data in the selected structure, but theoretically when this system call is instantiated it should already be in the same context as the process which called it. More research needs to be done on the mechanics of this.
• Develop a psuedo-random number generator. The professor gave permission to utilize popular methods already discovered by previous developers, so research will begin on their methodology of doing so. The functionality for the number generator will be abstracted into a private function within kernel/proc.h, so as to cut down on code bloat within the scheduler function.

[hatfield-c]

The proc data structure does appear to be a suitable candidate - after running some tests, the proc structure can persistently hold the data assigned to it, and due to the preexisting locks used by the OS race conditions can be minimized. Moving forward with defining an issue.

[hatfield-c]

In addition to the pseudo-random number generator, we will need to develop and refine an architecture for how our new scheduler operates.

The logic for loading processes is fairly contained, and can be placed inside of whatever condition controls lottery success. Thus, the challenge for developing the system becomes keeping track of the number of tickets active at any given moment, and determining when the lottery "hits".

We can use a for loop to go through all the processes, determining if their tickets match the winning number as we go along, so we only need to worry about a "maximum" number so that our generator doesn't spend most of its time throwing numbers without associated processes.

[hatfield-c]

The easiest way to determine the max number of tickets per lottery, would be to loop over the process table during each lottery to determine the number of "active tickets" at any given time. After that, the number generator can do its thing with its new max value, and then the lottery can loop through the processes again to determine a winner.

It would be more efficient to have the max number of tickets modified whenever a new process is created or destroyed, but there is too much volatility in that approach as we don't always know exactly when a process terminates (such as error).

[hatfield-c]

The necessary issues have been created and completed - this analysis is now complete, and will be closed.