The goal of the project was to further explore a concept covered in Software Systems. Since this was a collaborative project Brendan Doms and I discussed several possibilities and then settled on task switching. We chose this topic as it provided a sufficient level of challenge and it would allow us to explore the pratical aspects of the theory.
To simulate the difficulties orginial system programmers faced when implementing task switiching, we decided to implement our project in an embedded environment. We settled on the PIC 18F series as Brendan and I both had experience with PIC microcontrollers and the 18F series had all the necessary features to implement a process scheduler.
Methods
We used the MPLAB IDE to develop our implementation and the MPLAB assembler to produce the compiled binary. We ran our finished code in the MPLAB SIM simulator.
In order to accomplish our desired design, we utilized several hardware features. The first, and arguably the most critical, was the modifiable system stack. When a PIC microcontroller receives an interrupt it pushes the value of the program counter onto the stack and then jumps to the interrupt vector. In order to write a task switching operating system it was necessary to redirect the thread of execution to return to a different location than from where the PIC was interrupted. Utilizing the special stack modification instructions, we were able to load in an arbitrary program address and have the PIC return to it.
The second most important hardware feature that we utilized in our implementation was banked memory, which is memory that is divided into banks as opposed to a single continuous chunk. In order to access each different bank, it is necessary to modify a special register on the microprocessor. All memory addresses are then calculated relative to that bank. Banked memory is a fairly common feature, as it helps alleviate the problem of limited address space. In the context of task switching, a bank can be thought of as a process’s address space. Therefore, when switching between tasks, it is only necessary to change which bank is selected and the process’s state is restored, dramatically simplifying the state restoration/saving problem.
The tasks we created performed only simple instructions, as running complicated programs was unnecessary for the purposes of our experiment and would have added substantial development time. After the implementation was complete, we generated a stack trace from MPLAB SIM. The stack trace was then processed by a custom Python script in order to calculate the percentage of execution time each task received. This metric was then used as the basis for our results.
Results
The MPLAB SIM ran and returned a stack trace of 215 instructions. A tally counting the number of instructions in a specific task was then tabulated for each task. Each tally was then divided by the total number of instructions executed, yielding the percentages found below. Of the three tasks that we ran, tasks 1 and 2 used 31.9% of the executed instructions, while task 3 used only 31.5%. The scheduler itself used 4.7% of the executed instructions.
Conclusions
An ideal round-robin scheduler would run each task for an equal amount of time. Our results show that our scheduler was very close to being such an ideal round-robin implementation. The small discrepancy between the first two tasks and the third results from a limitation in our measurement methodology. Since the simulator can only return 215 instructions, execution will be arbitrarily halted once the simulator reaches its internal limit. In this case the third task was running when the simulator reached its limit and therefore did not complete its allocated quantum, skewing the data.
Therefore, by the definition of an ideal round-robin scheduler and the above results, the model we implemented was correct, fair, and efficient.
Related Work
This is not the first operating system feature to be implemented on a PIC microcontroller. The FreeRTOS is the biggest free implementation of an operating system for microcontrollers.
Much of the value of this project has been in creating a structure to support the basic operating system elements for a microcontroller: it helped us have a greater understanding of the underlying architecture and relationship to the hardware for all operating systems.
Future Work
The scheduler implementation we used in this project was simple and did not use any of the more advanced operating system features, such as virtual address spaces, device abstraction, or resource sharing. Some of these limitations drastically reduced the possible modes of operation of the processor. For example, much of the scheduler related research which occurs today revolves around the difference between computing bound processes and I/O bound processes. We could not compare this research to our own because our operating system does not allow for resource sharing or user interfacing, so none of the processes are I/O bound. In the future, these micro-programs could be used over USB, adding the possibility of user interaction. Moreover, new versions of the operating system could implement the ability to switch between more than three processes.
Acknowledgements
We would like to thank Professors Brad Minch and Allen Downey for their support and guidance. The Microchip website and documentation also proved to be very valuable resources.