ERTOS Summer Projects 12/2008 – 2/2009
These project are available to holders of the UNSW/NICTA Summer Research Scholarships. We may also provide some additional scholarships for good students with the a strong OS background who miss out in the official process. Talk to us if you are interested.
Contents
- Linux/Gelato Projects
- Real-Time Systems Projects
- Componentisation Projects
- L4 and Embedded Systems Projects
- Static Analysis and Verification Projects
- Other Projects
Projects marked 
are not on the official list but are available nevertheless.
Linux/Gelato Projects
These projects involve work on the (Itanium) Linux kernel or userspace in the context of Gelato. They will be supervised by Peter Chubb.
- Gel9: Merge Microstate Accouning with Taskstats
Microstate Accounting has been available for Linux from our website for a couple of years now. Last year, the taskstats infrastructure was merged into mainline. As two packages that do sort-of the same thing, it'd make it easier to merge our microstate accounting packages if the two used the same (or very similar) interfaces.
This project is to take the microstate accounting work and adapt it to report via the taskstats infrastructure.
It is likely that the result will be able to be pushed upstream into Linus's kernel. - Gel8: IA64 Live CD
Knoppix, UbuntuLive, PuppyLinux, ... there are many live CDs for x86 platforms. This project is to develop one for IA64, possibly based on Debian.
Challenges include working out how to build an EFI bootable CD, and creating an easy-to-use method of creating an image with selected contents. - Gel7: Extending the Open Source SKI Simulator
The Ski simulator is an instruction-level open-source simulator for Itanium machines. It was the first target for Linux on Itanium, and is still useful in exploring what the machine is doing for operating systems development.
This project, funded by HP, is to extend the Ski simulator to provice multicore and SMT support, and also to simulate later-generation processors. - Gel3: User-mode file systems
Any code in the kernel of an operating system is critical to the stability and security of the system. Hence, security and stability can be potentially improved my taking services out of the kernel. One service that does not need to be inside the kernel is the file system, provided that performance does not suffer unduly from running it at user level.
Using the libext2 library, a user-mode IDE device driver, and the user-mode NFS server, create a completely user-space NFS server. Benchmark it with various components in/out of the kernel.
more info - Gel0: Microstate accounting
The standard Linux tool for measuring how long a process spends running is getrusage(), which reports a statistical summary of time spent on the processor in the kernel and in user space, and a few other parameters to do with paging, resident set size, etc. Because it is a statistical summary, the times reported tend to overrepresent system time (because system time includes time spent in interrupt handlers) and underrepresent user time (the sleep/wakeup cycles of the measured process, if regular, tend to become synchronised with the sampling clock, and so even though the process wakes up and is on the queue at sample, time, it isn't actually on the processor).
We have instrumented the kernel to provide cycle-accurate measurement of the time spent running on the processor (in system calls, and when running user code), time on various queues, and time spent in interrupt handlers.
Subprojects:- Thread time tool
Brief: To design and implement a tool that collects microstate data from all threads in a process (either one started by the tool, or specified by PID on the command line) and displays the various times numerically, similar to the `top' program. - Visualisation tool
Brief: To design and implement a tool that collects microstate data about a process, and displays it graphicly as it evolves over time.
Subproject 1 and 2 could be based on a common library for obtaining the data from the kernel. - Improving getrusage()
Brief: To add code to the Linux kernel that implements some of the missing fields in the struct rusage, particularly the RSS and context switch counting; and also fixes the page fault accounting problem (at present, `major' faults include pages that can be obtained from the page cache without I/O) - Explore interactivity problems
Brief: Using the results of subprojects 1, 2 & 3, explore the behaviour of Linux under various workloads, particularly wrt solving `xmms skipping under load' type problems.
- Thread time tool
- Gel11: User-level drivers for user-mode Linux.
ERTOS has developed a framework for running device drivers in user-space on Linux, i.e. outside of the kernel. We have adapted our own virtualisation environment, LinuxOnLinux, to use it so that in the guest operating system, normal non-paravirtualised in-kernel drivers can pass through to selected devices.
This topic is to do the same for user-mode Linux, and to compare performance between the various possible solutions.
more info
Real-Time Systems Projects
Real-Time systems make up an increasing share of our day-to-day lives. Be it a mobile phone which needs to react to changes in the radio reception in a timely manner, an airbag in a car which has to be triggered within several microseconds of a crash, or a fly-by-wire system which needs to ensure synchronous behaviour of all actuators. The projects below work towards ensuring that such time-sensitive systems can be run reliably without violating any timing requirements. The projects will be supervised by Stefan Petters.
- SMP06: A constant bandwidth server for L4
Many systems incorporate several real-time applications which need to be isolated in the temporal sense. One way of achieving this is to set and monitor deadlines, which ensure that one application is not using more than its share. However, this restricts applications much more than necessary to be able to make any guarantees. A way around this is a constant bandwidth server, which ensures that a thread gets a certain fraction of CPU in any given window of time. To achieve this an accounting mechanism is required which tracks how much time an application has already consumed in this window. Again performance impact of the accounting mechanism is crucial.
more info
The following projects are in the area of worst-case execution time (WCET) analysis of real-time systems. As systems, and therefore their analysis, get more and more complex, the analysis problem is approached in a probabilistic way. Small units of the programs are profiled and combined probabilistically to represent a bound on the distribution of execution times of the worst case path of the program. Within the projects we are looking at the probability density function of individual small units. The projects will be supervised by Stefan Petters.
- SMP03: A Real-Time Programmers Guide Dog towards Better Predictable
Software
Another aspect of the estimation of the longest execution time of real-time software is the influence of the implementation of a given algorithm. Often small changes in the implementation can result in major changes in the overestimation. This project is focussed on identifying possible sources of overestimation and inform the user, where in his code, hand optimisation looks most promising. Typical examples are code, which is only executed in the first iteration of a loop and thus lead to severe overestimations, or small if-then-else constructs, which may be recoded to allow for larger units to be analysed.
The structural information and corresponding execution times are provided by an already existing tool chain. The project has a strong experimental character, which relies on many hands-on tests to be carried out. Within the project the student should look at many case studies and identify program constructs based on a control flow graph and execution trace, which may be automatically detected. In an evaluation step, the number of false positive and true negative detection should be compared with true positive detections. Additionally the gain in predictability of a set of detected cases should be reviewed.
The very limited implementation aspects of this projects may be implemented using C++, Java or C.
References (background information):- G. Bernat, A. Colin, and S. M. Petters
- WCET analysis of probabilistic hard real-time systems. In Proceedings of the 23rd Real-Time Systems Symposium RTSS 2002, pages 279-288, Austin, Texas, USA, December 2002.
- P. Puschner: Algorithms for dependable hard real-time systems. In Proceedings of the 8th IEEE International Workshop on Object Oriented Real-Time Dependable Systems , Mexico, January 2003.
- SMP10: Translation of X86 assembly language into pure lambda calculus for use in analysis of real-time program behaviour
Analysis of the real-time aspects of programs behaviour such as worst-case execution time is a new and active area of research. As part of NICTAs Potoroo project, we are attempting to automatically derive a worst-case execution profile for operating system kernels using a combination of statistical and analytic methods. At the core of our approach is a translation of the program being analysed into a purely-functional language resembling Haskell, and have completed the translation for the simple case of ARM assembly language. This project is intended to perform a similar translation for the much-more complex case of Intel Pentium/X86 architecture. The resulting translation defines precisely all aspects of the architecture including caches, branch prediction as well as the actual instruction execution in a mathematically-precise language of lambda calculus.
more info - SMP11: Coordination Instance for a Closer Look of WCET Analysis
A closer inspection and analysis of the dependencies of the execution time of small units of a program (blocks) is computationally expensive but may be rewarding in terms of reducing the overestimation.
This project aims to select promising candidates for the analysis. This selection is based on the impact of the individual blocks due to loops, their individual contribution to the overall execution time and variability of their execution time. As thresholds for the selection will be target and application dependent, the design should contain an adaptive strategy for these decisions.
more info - SMP12: Probabilistic combination of Execution Time Profiles
Recent work in worst-case execution-time analysis identifies dependencies between measured execution-time profiles. Combining profiles (covering conservatively any possible dependency) has a known, but pessimistic solution. Currently there is no solution to do this combination on partially known dependencies and subsequently reducing the overestimation produced by the worst-case execution time analysis.
more info - SMP13: GUI Implementation for an Analysis Tool
The worst-case execution-time analysis of code is performed by many different steps. Furthermore there are a number of different views the person analysing a piece of code may have. This GUI would need to coordinate the analysis steps of our tool-set and provide a suita ble extensible user interface to access all available informationen in an efficient way and allow the user to interact with the analysis. The project is aimed to work with graph visualisation software and a portable GUI library like QT and enable communication between the custom made GUI and the graph visualisation software
more info
Componentisation Projects
These projects deal with the building of componentised operating systems on top of L4, and CAmkES the component architecture that supports this. They are supervised by Ihor Kuz.
- IK38: Audio Framework for Embedded OS
Multimedia and audio devices are a popular class of embedded systems. As part of our research into modularised, microkernel-based operating systems for embedded devices, we wish to look at the design and implementation of an audio framework. This involves designing and developing a reusable software framework for audio applications and devices. The framework must be built using the component architecture we have developed for microkernel-based operating systems. Building a demonstrator showing the framework in use will also be part of the work.
more info - IK39: Embedded File System
One of the key services that an OS provides is a file system. We are in the midst of designing and building a modular (L4) microkernel-based operating system for embedded devices. While there are many file-systems available, we do not yet have a suitable file system service for our OS. Furthermore, not much work has been done on the design of a file system service in a componentised environment. This project involves designing and implementing an existing file system to work in a componentised operating system. Besides providing a functioning and reusable system component, it is necessary that the resulting file system also exhibits good performance.
more info - IK40: Linux as a Component
The ERTOS group has done (and commercialised) much work in virtualising Linux to run on the L4 microkernel. We have also done work developing a componentised microkernel-based OS. However the two essentially live in separate worlds. The goal of this project is to integrate virtualised Linux (and its applications) into the componentised OS. One way to do this is to treat Linux as a large component and develop appropriate interfaces and an appropriate framework for this. The project will investigate the best way to do this and implement a prototype system.
L4 and Embedded Systems Projects
These projects cover a wide range of operating systems and embedded systems research, mostly dealing with L4. They are supervised by Kevin Elphinstone, Gernot Heiser, and various PhD students and research engineers.
- KE2: Haskell on L4/Iguana
One approach to developing more reliable systems is to use a type-safe programmi ng language. Another approach is to formally model and verify the correctness of a system. Haskell is a type-safe functional programming language whose semantic s are close to those used for formal model and verification. Having the ability to use Haskell as a prototyping (and even the eventual implementation) language would open up the opportunity to explore the combination of these two approaches to building reliable systems.
more info - KE20: Bare Metal Haskell
Modern functional languages, such as Haskell, are becoming increasingly popular in application domains that require rapid development coupled with high safety and security demands. One particularly interesting such application domain is systems software for embedded systems, such as mobile phones. In this context, we have developed an executable specification of the seL4 microkernel, which improves existing second generation microkernels. In conjunction with an instruction level simulator, the executable kernel specification is a functional, if inefficient, implementation of the new microkernel.
We are working on a verified implementation of the specification in a low-level language for production use. However, this is a very resource-intensive endeavour. Hence, we are investigating an alternative implementation strategy where we run the Haskell code "on bare metal" - i.e., the Haskell implementation of the microkernel boots on standard hardware without any other operating system in between. This is a challenging project as it requires the adaptation of the Haskell runtime system to run without operating system support. Such a bare metal Haskell implementation would also be useful for other projects, such as trusted web service in high confidentiality environments and is the focus of this summer project.
more info - GHs82: VT-x support for OKL4
OKL4 uses para-virtualization to run Linux, even on x86, where pure virtualization is enabled by the VT-x extensions. This makes sense on performance-sensitive mobile devices, as para-virtualization has performance advantages over pure virtualization (see Adams and Agesen, ASPLOS'06). However, there are uses where the convenience of running an unmodified OS binary outweighs the performance penalty.
This project is to evaluate this tradeoff for the OKL4 platform. It will enable the execution of an unmodified Linux binary on the OKL4 hypervisor, and compare the performance with OK Linux (using lmbench and other benchmarks as appropriate).
This topic can easily scale into an honours thesis topic, with in-depth performance analysis and performance tuning, particularly when making use of more recent VT-x features, such as two-level virtual-address translation. - GHs81: SMT kernel locking trade-offs
Multi-threaded (SMT) processors are characterised by shared caches and very low (single-cycle) communication latencies between execution contexts. Consequently, treads on such a system are scheduled from a single scheduling queue, and other kernel data structures are also shared. This makes fine-grained locking hard and potentially expensive. For a kernel where average latencies of kernel operations are very short, a global kernel lock (i.e., single-threaded kernel) could be an appropriate approach.
This project is to investigate global vs fine-grained kernel locking on the OKL4 microkernel running on a highly (>4) multi-threaded processor core. This is likely to lead to publishable results. - GHs80: Performance comparison of Singularity and OKL4
Singularity (using language-based protection) and OKL4/seL4 (using hardware-based protection) are the leading examples of two alternative approaches to OS kernels for high security. This project is to do a quantitative comparison of the two approaches, focussing on the size of the trusted computing base and the performance of systems buillt on top (starting with assessing the basic communication performance).
more information - GHs81: NoTA prototype on OKL4
The Network on Terminal Architecture (NoTA) is an emerging approach for structuring software on a mobile phone handset, turning it logically into a distributed system. OKL4 should be the ideal platform for supporting NoTA with low overhead. This project is to demonstrate this by building a prototype NoTA-based system, and evaluate its performance. - GHs72: OKL4 on OLPC XO-1
Port OKL4 and OK Linux to the one-laptop-per-child laptop. - IK41: Web Server for L4-based Devices
Any computer system worth its salt must be able to run a web server these days. At ERTOS we are building a research OS based on a component architecture and a microkernel. We already have a (simple) network stack, but we still don't have a web-server! What this project will accomplish is to design and build a componentised web server and OS. But, it doesn't end there. The system must be fast. Therefore a significant amount of effort will also be spent analysing and optimising the resulting system.
- GHs27: Client-server vs. migrating threads
Perform a thorough qualitative and quantitative comparison of the client-server (or active-objects) and migrating-threads models of computation, in the context of an L4-based implementation. Examine and compare the performance and resource usage of both approaches. Examples of both approaches are available in the form of the Mungi and Iguana systems, which share many commonalities (including a large fraction of their source code). This should help a fair comparison.
more info - GHs70: BLUEsat OS
Design and implement an operating system for the BLUEsat student satellite project. The operating system will require a high degree of fault tolerance, including resilience against memory errors, and a very high degree of robustness.
more info - DS10: Validation of performance counter based frequency scaling schemes
Reducing the power and energy requirements of embedded systems is partly the responsibility of an operating system. Some new techniques for frequency scaling have been developed by NICTA, but it is not yet known whether they are generally applicable. The project will involve working closely with PhD and academic staff to implement and measure the performance of these new techniques on a number of embedded systems platforms, and the energy savings available.
more info
Static Analysis and Verification Projects
The following summer projects are strongly related to the Goanna project on static analysis of C/C++ source codes. Goanna is a collaborative project between ERTOS and the Formal Methods research program. The summer projects are joint supervised by researchers and engineers of the two programs. Details can be found on the Goanna summer projects page, or from the links below.
- Automatic Report Generation for Static Program Analyser
The goal of the Goanna project is to improve the quality of system software by automatically detecting software defects (bugs). Our prototype tool analyses C/C++ source code and prints warnings much like compilers do.
The goal of this summer project is to improve the tool so that it generates more sophisticated error reports in an easy to inspect format. It would be nice if programmers could browse source codes and the corresponding error messages with a web browser, easily linking similar or related bugs, ticking off false error reports and marking fixed problems.
more info - IDE for Static Program Analysis
The goal of the Goanna project is to improve the quality of system software by automatically detecting software defects (bugs). Our prototype tool analyses C/C++ source code, as well as embedded ARM assembly. Currently, it is a standalone command-line tool, which is explicitly started by the programmer or manually integrated into the development environment.
The goal of this summer project is to integrate the Goanna tool into a real integrated development environment (IDE) like Eclipse or Microsoft Visual Studio. The IDE should support to individually select the properties that Goanna should check and to display valuable feedback on the location of found program defects.
more info - Static Analysis of ARM Assembler Code
The goal of the Goanna project is to improve the quality of system software by automatically detecting software defects (bugs). System software (like kernel code) often contains embedded assembler parts. An existing module analyses embedded ARM assembler code, but it does not yet check for a wide range of properties.
The goal of this summer project is to extend the existing assembler analysis module by checking for many more interesting properties in embedded ARM assembler code, enabling the analysis of real operating system code.
more info - Error Trace Generator for Static Program Analyser
The goal of the Goanna project is to improve the quality of system software by automatically detecting software defects (bugs). Our prototype tool analyses C/C++ source code and prints warnings much like compilers do, i.e. it tells to programmer that a certain property is violated in a specific line of the source code.
The goal of this summer project is to improve the tool so that it gives better understandable traces of how the suspicious line would be reached in the program (without actually having to execute it). Such a trace is of great value to the programmer, as it tells what is happening before the suspicious code.
more info - Warning Suppression for Static Program Analyser
The goal of the Goanna project is to improve the quality of system software by automatically detecting software defects (bugs). Our prototype tool analyses C/C++ source code and prints warnings much like compilers do. Some of these warnings are annoying to programmers, because the warnings are false positives or indicate problems that the programmers are well aware of.
The goal of this summer project is to improve the tool so that it can suppress certain warnings or types of warnings. The tool should suppress the warnings even if the line numbers change, and show the warnings again if the affected code changes significantly.
more info