Fred's Home Page

This page provides a pool of ideas for various potential projects, targeted largely at 3rd and 4th year undergraduate students. The projects are mainly KRoC/occam related. This page is more or less a merge of an existing project page with RMoX based projects. These are not set in concrete by any means, just a pool of ideas.. :-)

Don't forget, of course, to check the real 3rd year project suggestions pages for CO600 projects and CO620 projects ;-). The ideas and such on this page are largely derived from the work of the concurrency research group and others. Main acknowledgements to: Peter Welch, David Wood and Brian Vinter.

KRoC/Linux for Windows

The latest versions of KRoC/Linux now build on Windows, using cygwin. This largely utilises the UNIX/POSIX environment provided by cygwin, along with posix threads to handle external blocking calls (e.g. socket I/O, etc.).

This project would investigate adding a specific `winlib' to KRoC, giving occam programs access to parts of the Win32 API. For example, enabling an occam program to exchange messages with other Windows applications, or put an icon in the ``system-tray''. Cygwin provides the necessary glue to get at the Win32 API from its own environment. More generally, graphics would be nice -- popping up message boxes isn't particularly difficult (it's an API call), but fully functional windows/forms/etc. would be. The interface exposed to occam should ideally be fairly generic, allowing for alternate graphics back-ends in the future (e.g. X11 and MacOS X -- when we get around to it).

Scope and difficulty: CO620, challenging.

KRoC/Linux for MIPS

The current KRoC/Linux release is targetted primarily at the i386 platform. The dependencies mainly lie in the native code-generation phase of translation and in certain parts of the run-time kernel (primarily for providing the occam interface). Recent developments to Linux/MIPS provide a platform comparable in functionality to Linux on the i386. As such, porting KRoC/Linux from i386 to MIPS should be feasible. The bulk of this work will be in modifying the code generator (tranx86) to generate MIPS code, instead of i386 code. Changes to the run-time kernel (ccsp) will also need to be made, to provide a suitable entry/exit interface for occam.

There is already a native-code kernel for KRoC/MIPS, written in assembler, designed for use with IRIX. However, this system has not been worked on for a while, but should provide a good starting point and existing background work for KRoC/Linux/MIPS. Access to Linux/MIPS systems is available.

While we're at it, it might be nice to produce a new KRoC/IRIX too. GCC and friends are available in the IRIX distribution (and on their freeware website).

Update (April 2004): This is now well underway, being developed by Christian Jacobsen and myself. The port more or less works now, so there isn't much scope for a KRoC/Linux/MIPS project directly. Porting to IRIX would be a possible project.

Scope and difficulty: CO620, challenging.

Occam Graphics

The past two years have seen, primarily, two GUI libraries for occam. The first, by Paul White, was built on GTK (the Gimp Toolkit), and was a summer internship project. Although this worked, more or less, significant problems exist with occam and GTK. Suffice to say, the problem is the combination of blocking system-calls (required to interact with an X server over a socket), and the pthreads library (POSIX threads), as used by GTK (and also directly by Xlib if desired). There is at present no working solution to this -- although there was one possible way out, but probably requiring the recompilation of libpthreads. The end (and broken) result was random segfaulting (usually after a few minutes of successful execution).

Last year (2002-2003), Jonathan Stott built (as a 3rd year project) bindings between occam and WG (Window Gadgets). This was more successful in the sense that it worked without crashing (functional demonstrators were produced), but requires more work to bring it into a state suitable for deployment.

Projects that build on this are welcomed.. Much of the current problems with WG-occam (wgocc) are minor. The most obvious is a lack of gadgets. Less obvious are problems with gadget refreshes and screen updates. Screenshots and code of what currently exists can be found on the WG-occam page.

I can think of three ways forward at this point:

Continue developing WG-occam as it stands. This means providing support for more of WG's gadgets, and fixing any existing problems (maybe an over-haul of the occam interfacing code). WG is written in C++, so at least some knowledge of C/C++ would be useful. Java isn't all that different (syntactically), so as long as you can/do understand `pointers' and `aliasing', the C++ shouldn't be a problem. Much of the interface code can probably be generated automatically (from suitable input templates) -- implementing this would be a good idea, as writing the code by hand is a real exercise in the search/replace capabilities of your editor (I use vim, so no great problem there, but it was boring..).
Avoid the problems of interfacing WG (C++) and occam completely by separating those components out. In a nutshell, write some WG/C++ that provides the interface, then talk to it remotely (via a socket) from occam (well, a graphics library that would need to be developed). I already had ideas along this line before, since it avoids a great many problems. See the RAPP (Remote APPlications) page, although no substantial code has come forth (yet), it's been thought about a lot.
Do something completely different. Some interesting graphics oddities can be found on my occam page. (`xraster', and more recently, `dxraster'). I've also got the X11 protocol reference manual available for loan, if someone fancies writing Xlib in occam directly. That would take a lot of time, however, but would provide a better platform for building gadget/widget libraries. Or starting at a slightly higher level, an interface to Xlib (with a same/similar interface to the native X-protocol-over-socket version). And some gadgets to go on top. :-).

Scope and difficulty: CO620, challenging.

Nested Mobiles for occam

The current occam system provides support for MOBILE types. These are like ordinary types, except that communication and assignment have movement semantics (as opposed to copying semantics). The implementation is efficient, communicating pointers to data only. The implementation of statically-sized mobiles means that there are unit-time costs for allocation, deallocation and movement. Dynamic mobiles are limited to run-time sized arrays and mobile channel-types, and have slightly higher (but still unit-time) costs for the same.

These mobiles, both dynamic and static, are limited to single-level (outermost) cases. You cannot, currently, define a mobile data-type which has mobile sub-types. In our usage of mobile types, the need for nested mobiles has not been obvious, but there have been cases where it would be useful (rather than necessary). The ability to have dynamically-sized mobile arrays within mobile record structures would be helpful. Multi-dimensional dynamic mobile arrays have been implemented and may serve as a good reference point.

The implementation of nested mobiles has been worked out in part already, especially as to how it should fit in with the existing allocation scheme. One restriction that we intend to impose is ensuring that any type-tree containing a mobile type is wholly mobile. This is a technical restriction only -- it makes things much simpler!

The work to be done will be almost exclusively in C (hacking of the occam compiler), with a collection of example occam programs to test the correctness of the implementation. The occam compiler is not simple, comprising of some 120,000 lines of code. This work would ideally suit someone who has a good background in C programming already, and who is not afraid of getting their hands dirty in the compiler. Technical support on various aspects of the compiler will be available. Being familiar with stack-machines would also be an advantage, since the compiler generates extended transputer byte-code.

Scope and difficulty: CO620, challenging.

An occam IRC Server

This project would involve implementing an IRC server in occam. The new occam now supports all the features desirable for this kind of application: socket-handling, dynamic process creation, and dynamic network re-configuration.

The envisaged approach would be to have `channels' existing as processes. Client connections would be handled by separate (parallel) processes, dynamically connected to the `channel'-processes in use by that client. Additionally, some additional management process would be required, to handle incoming connections, client and channel discovery, and (potentially) server-to-server communication.

An RFC (1459) describes the IRC protocol in detail. Real-world servers use some extensions to this, that are generally minor, but should probably be supported.

Scope and difficulty: CO600, 3-4 students, flexible.

An occam Mail Server

This project would involve implementing an RFC 822/821 compliant mail-server in occam. The new occam now supports all the features desirable for this kind of application: socket-handling, dynamic process creation, and mobile communication.

One possible implementation of this would be to encompass an `email' in a (mobile) record-type, or have it handled by a separate (parallel) processes -- created dynamically as required. The main part of the network would consist of `mail-routing' and `mail-delivery' components. Mail routing would essentially be mail-packet switching based on some condition (target address, for example). The system must also be able to handle rejection sensibly -- i.e. possibly reject a mail before the remote MTA sends the message body. In light of this, having `connection-handling' processes seems like a good idea. Mail delivery would typically be: remote SMTP (RFC 822); or local maildrop.

It would be nice if the system could support interaction with external mail filters too. Spam and virus checking, for example. One of the primary aims here is to create a mail server that is free from potential buffer-overflow exploits (occam checks array access at run-time, and there are no pointer types).

Scope and difficulty: CO600, 3-5 students, flexible.

User-mode RMoX

We want to run the main kernel bits in the standard Linux environment -- like user-mode-linux (sort of). The primary reasons for doing this are to enable a faster development cycle and to better facilitate debugging. The work involved for this would be replacing various device-drivers with functionally similar drivers that interface with the KRoC/Linux environment, rather than the raw hardware.

A nice way of handing the keyboard and VGA drivers would be to have an X11 app providing input and output. The advantage of using the X Window System as opposed to a simple TTY is that we get `real keypresses', as opposed to characters. Additionally, handling GUI interfaces under X11 is nice and simple -- the same cannot really be said for SVGAlib, etc.

Updated: August 2003. Christian Jacobsen has done much work on this, and as a result, we have a working user-mode RMoX. The current system uses a X interface called `xtextwindow'. This is fast, but is a bit incomplete (many keys are not handled, for example). An alternative interface, using dxraster is also available. Whilst this is a much more complete interface, it is orders of magnitude slower than `xtextwindow' (dxraster draws text itself, xtextwindow uses X11 fonts..).

Scope and difficulty: CO620, challenging.

Device drivers for RMoX

There is a lot of hardware available these days, especially for PC based computers. There are even more device drivers, for all versions and flavours of operating system. The currently implemented device drivers in RMoX have been done using direct hardware access, which is relatively simple in occam (once the memory or IO regions have been reserved by the OSKit -- largely for its own management of such). Hardware interrupts are currently handled by calling an external PROC which suspends the process until the requested interrupt occurs.

One useful addition to RMoX would be a mechanism for `wrapping-up' (glue-code) the device-drivers provided by the OSKit. Some of the OSKit drivers are native, others are existing Linux/BSD drivers wrapped up to present an OSKit compatible interface. RMoX device drivers are currently classified as input (keyboard, serial), output (vga, serial) or block (floppy, ramdisk). A device driver may support any number and type of these interfaces.

On the other side, writing device drivers in occam is fun, and there may be places where parallelism can be usefully exploited.

Scope and difficulty: CO620, challenging.

GUIs for RMoX

Most operating systems have a GUI interface. The majority of uses tend to work well with these. Code has existed for an X11 server, written in occam, but which was targetted at real transputer hardware (using the transputer compiler toolkit). Assuming that access to the VGA framebuffer is pretty easy -- which it is -- porting the X11 server should not be impossible. It will certainly be challenging however.

There are a lot of open ends in any such project; handling accelereted (GL, etc.) interfaces, client connections (channel and/or TCP), stock X11 protocol extensions (shape, XKB, etc.). Interacting with the keyboard and mouse is also an issue, but less technical than handling X itself.

Scope and difficulty: CO600, 3-5 students, challenging.

Low-level memory handling for RMoX

The current state of RMoX ({\it Raw Metal occam}), a.k.a. `the occam operating-system', is that all occam processes run within the same memory space. Currently a fairly flat model provided by the Flux OSKit, on which the occam processes and run-time kernel sit. As it stands, this is fine, since the run-time checking traps potentially fatal errors. Direct access to memory and IO is available, but it has to be trusted. This impacts the flexibility user-code can have -- we don't want user processes trampling on other processes memory space. For the most part, we would have to ban things like inline transputer ASM, restricting the user-stuff to just pure occam. Obviously, this is not a desirable situation.

There are essentially two sub-projects here, the second dependent on the first.

The first thing here would be to provide an occam OS kernel mechanism for handling memory protection using the standard i386 protection mechanisms. This could either be done by using what the OSKit provides with suitable glue to let occam get at it, or by implementing it in a direct-to-hardware fashion. The balance between C and occam here is pretty flexible, but more occam would be preferred.
After implementing a suitable protection mechanism, placing occam processes inside it and running them will be fairly trivial. Suitable mechanisms for handling errors, page-faults, etc. will need to be implemented, as well as the necessary reporting back to the process which started it. There are a number of issues here with regard to memory mapping and occam process scheduling.

Alternatively, we're happy to do away with the OSKit -- it is very broad considering our small requirement.

Scope and difficulty: CO620, challenging.

Low-level scheduling in RMoX

As mentioned, we're using the Flux OSKit to provide the boot mechanisms and other low-level stuff (memory protection fiddling, etc.). Not that RMoX needs much once booted, however.

It would be nice to be able to run arbitrary C programs on top of RMoX, with some suitable interfacing. However, C programs must be run in their own virtual machine, since no guarantee can be made about the integrity of such programs. RMoX, as viewed by the OSKit, is a single simple process. The scheduling of occam processes is handled by RMoX, not the OSKit. The basic requirements are:

That RMoX retains complete control whilst it is running. I.e. it will not be pre-empted by anything, with the exception of interrupts, that it handles itself anyway.
When anything other than RMoX is running, RMoX is in a known state (suspended). Thus, if an interrupt is received whilst executing in another VM, RMoX can be immediately switched back in to handle the interrupt. This can be fast -- we know what state RMoX is in when the interrupt is received!
The underlying mechanisms for switching VMs will be controlled by RMoX, not visa-versa.

Last year, Ramsay Taylor developed a low-level infrastructure, to load and boot ELF files. This has not been incorporated into RMoX yet, it needs more work ideally. I've not looked at the code yet either, but it is believed to be largely functional and heading in the right direction. A project could, ideally, build on this (including integration with RMoX).

Anything in this area is likely to be related to low-level memory handling (in order to ``hide'' RMoX's memory from external processes).

Scope and difficulty: CO620, challenging.

Window Gadgets

Window Gadgets is a visual toolkit for building X11 applications in C++. More `end-user' (programmer) information can be found on the Window Gadgets page. WG provides a selection of C++ classes that implement various parts of the system. At the lowest (practical) level is the `XConnection' class. This is a central component that visual and non-visual gadgets `register' with.

Internally, XConnection uses other classes to provide specific functionality -- XDisplayServer, XFontServer, XPixmapServer and XColorServer. The XConnection class is designed to be able to register with itself, although I've not quite implemented all the needed bits yet. This allows one application to run on multiple X servers, that can be quite a useful feature.

Also on the WG page is WGBuilder. This was our (Dave Reeve, Steve Fagg, Paul Rogers, Karim Saykali and me) 3rd year project in 98/99. It works. :-). Essentially, whatever happens to WG must not break WGBuilder. If possible (time constraints), the `gadget database' in WGBuilder should reflect the current state of the gadgets in WG.

The implementation of WG, and any gadgets that run on top, is wholly event-driven. Once suitably initialised, an application calls `mainloop()' in the XConnection class. This, more or less, starts with a call to `select()', with the various file-descriptors on which events can happen. Generally, this will include the socket descriptor of the X-server connection. Once `select' returns, events are processed by calling methods in their associated objects (gadgets) -- `xc_mouse_down()' for example. Gadgets may then further call user-specified functions (the application callback).

The code that generates user-interfaces can either be programmed explicitly (boring), or through the use `buildinit' and .hpd (hierarchal program description) files. `buildinit' combines the interface description with `mapping' files that specify how various properties are set for particular gadgets, in addition to the available callbacks, and produces the code required to create (and destroy) the interface. See the examples on the WG page to get a clearer idea.

So, some project suggestions:

Application callbacks are currently done using function pointers. Whilst this works perfectly well, it doesn't quite fit into the whole OO/C++ style. A better way would be to use `callback classes'. My suggestion would be to allow such callback-classes to contain function-pointers, such that original compatibility can be retained -- simply `button->callback->on_click = my_button_click;' instead of `button->on_click = my_button_click;'. Actions in a gadget would change from being `if (on_click) { on_click (...); }' to `callbacks->cb_click(...)'. The callback class (default) implementation can then either call the user-specified function or do nothing. Also, an application can inherit from a callback class, overriding its methods with application-specific code -- the OO approach. This project would require a good knowledge of C and C++ programming.
The event-driven nature of WG leads to some subtle problems. In particular, the thread-of-control can get knotted through non-strict application programming. This problem is typical of many software systems and languages -- usually when OO is added to a typically imperative language. Concurrency is the solution, and CSP the right approach. This project would involve adding concurrency (and a lot of it) to WG. Ultimately, we would want each gadget and/or component to be its own thread of control, communicating and synchronising using occam-style channels. This could be engineered in a variety of ways: CCSP (a pure C user-level thread scheduler), CIF (a C interface for the KRoC/occam system), C++CSP (Neil Brown's C++ posix-based thread scheduler), libCSP (Richard Beton's C posix-based thread scheduler), the MESH scheduler, and there are probably others. The requirements are simple: processes and synchonising channel communication. The handling of asynchronous I/O is relatively simple for both posix-based thread schedulers and the CIF interface; less easy for CCSP and MESH.

Such changes could be performed in conjunction with the WG-occam binding, and ideally WGBuilder too. The current interface between occam and WG is slightly messy..

Scope and difficulty: CO620, flexible.

Inter-mixer effects for Soundtracker

Soundtracker is an open-source XM-style (e.g. fast-tracker) GTK based tracker, written mostly in C. Whilst it is, in general, a superb tracker (imo), it could be even better! The DOS-based Impulse-tracker supports various audio effects, beyond the standard MOD/S3M/XM effects, that affect on what/how-many channels the sound it output (before/inside mixing at a guess). What can be done with Impulse-tracker in this respect seems to be fairly limited, but the resulting audio output is significantly enhanced.

This project would involve adding support for an additional effects channel, to Sound-tracker and the XM file format (done in a backward-compatible way, so that non-soundtracker players don't break when loading the file -- the structure of module files should make this pretty trivial).

The effects (suggested list of some below) should provide a nice and simple way of changing the distribution of sound in output channels (generally stereo).

phase - stereo separation with delay
reverb - standard reverb effects (room,hall,etc.)
echo - standard echo effect (perhaps with stereo separation, pitch change, etc.)
and any others that might be interesting/useful/amusing

Conceptually, we might wish to create effect-processing such as:

example XM effect processing

The limiting factor will most likely be computation power in the mixer (playing is a real-time process). For modern processors (1+ GHz), this shouldn't be much of a problem -- and there's always .wav output, where the effect-processing speed is less relevant.

Technically, this project requires a good working knowledge of C programming. Some experience of i386 assembler would also be useful, for the purposes of optimisation. At the moment, I think a concurrent two-part implementation would be the best:

Addition of mixer effect processing, including representation of the mixer network and a processing implementation. The diagram shows things in a parallel-style, but the implementation will probably have to be serial (unless anyone wants to write an occam tracker ;-)). Some sort of XML definition might be appropriate for this, and maybe some tools to manipulate this in XM files -- as this bit it un-changing, soundtracker only really needs to read and use it, rather than be able to re-arrange these things at run-time.
Addition of the effect-control channel. This will require changes to the Soundtracker GUI, although that shouldn't be too massive a task. It'll also require changes to the internal representation of XM patterns (to include the effects channel), and appropriate handling for XM file load/save.

Directives in the effects-channel will control the processing of effects in the effect-network. This will require some way of identifying the different effect `processors', and signalling might include a general `beat', `on', `off', or more specific settings such as `level', `balance', `frequency', etc. An effects `matrix' might be more suitable for the GUI-part, rather than unit-size row-by-row control (an existing gripe about XM's is, with some effect combinations, that you can't apply two effects simultaneously -- not because the tracker is incapable, but because there is no `room' to encode it in the XM). This almost leads to another potential project: support for effect-only channels, that can apply effects to different channels.

Scope and difficulty: CO600, 3-5 students, challenging.

Networking for MOSS (1)

This project involves adding networking support to MOSS (Mini Operating-System Simulator). There are two ways to provide networking inside MOSS -- either use Java's own networking support, or do it the hard way. This project describes the former; the other way of providing networking is described below.

MOSS provides a POSIX-like interface to its user-processes, in the `MPosixIf' class. To provide networking support for user-processes, the following methods would need to be added: `socket()', `connect()', `bind()' and `shutdown()'. This is primarily for TCP/IP sockets; UDP/IP would require the addition of `sendto()' and `recvfrom()' methods. This is the POSIX view of sockets (more or less). What Java provides in the API for networking isn't quite like this. The underlying code in MOSS would need to handle this abstraction fairly carefully -- e.g. an actual Java socket need not be created until `bind()' or `connect()' is called. To support general I/O operations, some class implementing `MFileOps' would be required, perhaps on a per-socket basis.

In addition to the MOSS kernel support for networking, it would be good to provide some standard user-land utilities (as much as the underlying support allows), e.g. `nslookup' (UDP), `wget' (TCP). Dealing with ICMP would be hard, perhaps impossible.

Scope and difficulty: CO600, 2-3 students, flexible.

Networking for MOSS (2)

This project involves adding networking support to MOSS (Mini Operating-System Simulator). There are two ways to provide networking inside MOSS -- using Java's own networking support (described above), or using a low-level interface to real networking. Typically, this would involve speaking SLIP (Serial Line IP) to a local tty device (e.g. `/dev/ttyq0'), with the underlying OS connected to the pty-half providing the `outlet' (principally packet routing). This method has been used successfully with the user-mode version of RMoX (an occam operating-system), using Linux as the host operating-system.

The main part of this project is implementing a TCP/IP network stack in Java. Existing work could be drawn on to a greater or lesser extent. MOSS provides a POSIX-like interface to its user-processes, in the `MPosixIf' class. To provide networking support for user-processes, the POXIX networking-related `system-calls' would need to be added, e.g. `socket()', `bind()', `connect()', etc. These would connect into the `top' of the network stack. At the `bottom' of the stack would be the SLIP driver, relaying IP frames (packets, or parts of packets) between the `/dev/tty..' device and the MOSS network stack, with appropriate SLIP encapsulation.

Implementing networking using this technique would provide a complete network support for MOSS, including TCP (stream-based), UDP (message-based) and ICMP (control-based) -- some of these are related (e.g. `TCP connection refused' is indicated using ICMP). It is expected that such an implementation would support features such as multiple interfaces and packet routing (including `gateway' handling). Additional features might include support for some form of IP-filtering (like `iptables' in Linux).

A good demonstrator of this would be a simple `telnet' server, allowing a user to access MOSS remotely. MOSS currently has very little in the way of security (i.e. user login), but this won't be a problem.

Scope and difficulty: CO600, 3-5 students, challenging.

Virtual Memory-Management for MOSS

MOSS memory-management

MOSS currently has no real concept of memory management. From the view of the host operating-system, it is just another running JVM. Internal to the JVM, MOSS consists of various running Java `Thread's, static methods and static data -- in some ways, there is no memory to manage; the JVM handles this transparently. There is, however, good reason to simulate memory-management -- principally for educational purposes.

The envisaged implementation would be a simulation of a fairly standard paging mechanism, with controllable amounts of real-memory (page-frames) and a way of investigating different page-replacement strategies. Most importantly, there should be a way of visualising the paging activity -- e.g. a graphical display of page-frames and what processes they belong to. Clicking on a page could bring up information about a process's virtual memory, etc. The image on the right shows a basic idea of what I'm thinking of; `R' and `M' indicate that a page has been referenced or modified (and referenced). This is quite a basic display; it might be nice to show the various process's page-tables too, perhaps with links into the page frames when they are resident.

The actual implementation would most likely involve adding `page-tables' to processes (`MProcess'), combined with `memory-management' code (that simulates the various aspects of memory-management, including the page-frames), some suitable display mechanism, and the addition of `hooks' into other parts of the operating-system that signal `activity' to the memory-management sub-system. This latter part is required in order to mark pages as referenced and/or modified, that in turn causes simulated page-faults and the activation of a page-replacement strategy.

Scope and difficulty: CO600, 2-4 students, flexible.

Virtual Disk-Handling for MOSS

This project involves adding a `disk-simulator' to MOSS. Currently, there is no permanent storage within MOSS, although adding a block device-driver that reads/writes to an underlying file on the host file-system is not too hard (some students did this as part of the CO501 coursework). Rather than having a simple block-by-block mapping onto a file, a `virtual disk' would provide a track/sector/head layout, with a suitable mapping between logical and physical addressing, although the underlying file mapping would probably still be based on logical addressing (i.e. blocks 0 to `n-1').

This `virtual-disk' driver should provide a graphical display, showing the disk activity as it happens. In order to be interesting, there needs to be a mechanism for queuing I/O requests made by the system. The most effective way of generating disk I/O is with a file-system. MOSS currently has an `object file-system', that resides entirely in memory. This could be used as a starting-point for a disk-based file-system, using the virtual-disk.

The virtual-disk driver should take into account the properties of a real disk for the purposes of simulation -- e.g. the read/write heads cannot move instantaneously from one part of the disk to another, so there should be suitable delays (that could be generated by the animation itself). One of the more interesting parts of the project would be the provisision of different types of disk-scheduling algorithm (first-come first-served, circular-scan, etc.). Given suitable disk I/O, it should be possible to see the effects of different types of disk scheduling clearly.

Scope and difficulty: CO600, 2-4 students, flexible.

[ds] [plain]