Splay trees, compression, encryption, and embedding (by alaric)

There's a little-known data structure with some useful properties; the Splay tree.

It's quite a useful data structure in its own right, but it also has interesting applications in data compression, and cryptography...

Read more »

NEON (by alaric)

NEON is the user interface system for ARGON. I've not designed what the UI will "look like", since I think that would be a stupid thing to do - different people need different UIs, especially when they have differing hardware (think mobile devices, wearable computers, and interaction devices for the blind, in particular). But what I have been designing is the UI architecture, by which applications will expose their interface in such a way that different UIs can map them to their available hardware.

Anyway, I've had some pretty similar ideas to Tuomo Valkonen - who has an idea called VIS. So I finally dropped him an email detailling my thoughts, focussing on how they differ from VIS: Read more »

Hobby OS projects (by alaric)

There are a lot of hobby OS projects out there. The Wikipedia article barely scratches the surface; I've come across projects to build Lisp-based OSes, 32-bit multitasking extensions to DOS, you name it.

Lots of people decide they want to write an OS. They look at a world dominated by Windows, with open source UNIX clones and MacOS bringing up the rear, and think: "I can do better". And they usual don't get too far. Even if you do write a full operating system, able to utilise a wide range of hardware and with all the applications home and business users need, you'll still have a hard time getting people to use it - because it's unfamiliar.

I'm proud to say that I, too, am writing my own OS. Read more »

Generic indexed storage for TUNGSTEN (by alaric)

For TUNGSTEN, I plan to split the local storage manager into two layers; the physical manager and the logical managers. The physical manager takes a collection of block storage devices (such as hard disks), and a configuration giving advice on which disks to use for what, and provides an administrative interface for modifying said configuration and monitoring usage, and an interface to the logical managers. The latter interface provides access to a single unified associative data store; the local store is divided into regions for each volume mirrored on the local node (by a numeric volume ID), which are in turn divided into regions for each entity (by a numeric entity ID), which are in turn divided into regions for each object within the entity (by a numeric object ID), which may then be structured as the logical manager responsible for that object sees fit. The structure available to the logical manager within an object is a set of records, each with a key and a value. The physical manager provides the ability to create, abort, or commit transactions, and within a transaction, read, write, add, and remove records, including iterating through records by key range.

Read more »

Garbage collection (by alaric)

One of the interesting little problems in converting a CPU, some RAM, and a bunch of I/O devices into a useful system is memory management.

Your everyday PC with 512MB of RAM contains about 512 million little memory cells, each of which contains an eight-digit binary number. This is where all running applications, and all the information they are dealing with, must be stored; programs, text, images, and whatnot are all encoded as sequences of these eight-digit numbers (known as bytes) and stuffed into memory.

The problem is - where to put everything? After all, when you double click on a program, the computer looks at the size of the program on disk, and needs that many bytes of memory to load the program into. How does it know which bits are free and which are in use? Different computers have different amounts of memory, and may be running any combination of apps already, so there's no way to reserve a given bit of memory for a particular program; the system has to keep track of what's in use and what isn't in real time. And when you load your app, it will start asking for bits of memory to keep track of the windows it has open, to store your document in, and so on.

Now, the first problem to be solved is how to keep track of which bits of memory are in use and which aren't, in such a way that the computer can efficiently find a block of free memory of a specified size - that problem is harder than it may seem, especially when you consider that multiple threads of execution will be requesting memory at once. But that's not the problem I was pondering as I sat on the train today.

My problem is how to figure out when a block of memory isn't used any more, so that it can be handed back to the system that keeps track of free blocks and reused.