A garbage collector that knows that all values are immutable will be rather interesting, I think. Typically, a garbage collector will stop the world (i.e. halt execution) to do heap defragmentation of the old generation. When all values are immutable, though, you can defragment the heap by copying a value to another fragment and just swap the internal pointer to the value. This might actually have significant perform…
An immutable operating system
51–60 of 153 posts
Re: An immutable operating system
#52Awesome! You should have a look at Urbit: http://www.urbit.org/
Re: An immutable operating system
#53I gave an un-conference talk at Clojure days Amsterdam called "Purely Functional OS" on this exact topic and we had an incredibly interesting discussion about the topic. The conclusion we kept coming back to is that it's technically not all that difficult to implement, but that to make it usable in the real world would mean that computers would have to get a lot more cautious about source vs. derived data. The main t…
in the current state of technology it's impossible to determine what is derived data that can be easily recomputed and what is essential data without which the current state could not be recomputable. Can you elaborate more on that statement? I see it as an expensive problem, but not impossible. If you have a completely deterministic VM/instruction set, you can recompute any function output from any set of inputs. If…
At the process level there are already plenty of programs that work this way and it's exactly the kind of thing the Clojure ecosystem is geared towards.
That's why the Purely Functional OS is essentially a thought experiment in what it would take to extend this to the entire operating system.
When I said "impossible given the current state of technology" I meant exactly what you said in your last paragraph though: impossible without designing an OS that isolates derived data.
I believe such a system will come in the form of persistent data structures coupled with reactive programming but, while I believe it's inevitable in the long run, extending that concept all the way to the OS will be quite the challenge.
Re: An immutable operating system
#54I wrote an operating system in a purely functional dialect of Lisp; http://losak.sf.net
There are a few things I learned in the process that I think are relevant here:
1. Forget garbage collection in the sense of any variant of mark-and-sweep. For an operating system latency is more important than through put, so you really want real time memory management. If you use reference counting, then there is a lazy variant that gives you just that; no pauses due to reclaiming free memory. The downside with reference counting is that it doesn't work with cycles in heap-allocated memory, but if your data is all immutable then you can prevent cycles from being created in the first place.
2. Treat mutable memory as a form of I/O. Even if you just want to use memory mapped I/O, you will need some way to read and write to (some portion of) memory. Set aside a fixed block of memory (say, for instance, the first 10 MB), and only allow that memory to be read and written in an imperative fashion. Keep the managed heap completely separate from that mutable block, and don't allow any direct access to the managed memory.
3. You can actually perform preemptive multitasking entirely at compile time (or at program load time for apps not included when you build a binary for your OS). I've done this for both my OS and for Scheme (https://github.com/ojarjur/multischeme). It works extremely well and winds up being much faster than using the native primitives usually used for building multitasking support. For more details on exactly how to do it see the link to my Scheme implementation.
4. The biggest difficulty the author will hit, and the most likely cause for performance issues, will be in code generation. Since the proposal is for a new bytecode, the author will have to implement their own interpreter and/or JIT compiler for it, and writing an efficient one is an extremely large chunk of work. I've built an operating system and a programming language, and the language is by far the harder project. This is why I went from working on a new OS written in a new language to re-implementing my compile-time multitasking technique for Scheme; it allows me to take advantage of all of the hard work people have done to make compilers for that language which produce fast code.
Re: An immutable operating system
#55Why make the system language a Lisp instead of a language that is by default immutable? I'd think Haskell is a shoe in for something like this and you'd have a head start with House:
http://en.wikipedia.org/wiki/House_(operating_system)
Re: An immutable operating system
#56Is there a list of research / alternative operating systems anywhere?
I don't know how an OS would qualify to get on the list other than not DOS, Windows, OSX (or any of the Apple OSs), Linux (especially not 'ubuntu with a different DE'), or the BSDs (i guess there are exceptions if they're on a toaster).
Re: An immutable operating system
#57I wrote an operating system in a purely functional dialect of Lisp; http://losak.sf.net There are a few things I learned in the process that I think are relevant here: 1. Forget garbage collection in the sense of any variant of mark-and-sweep. For an operating system latency is more important than through put, so you really want real time memory management. If you use reference counting, then there is a lazy variant…
Author here. The language is the part I also dread the most, and is also the part that will be the least unique and the least interesting to "re-invent".. I'll look into finding an existing language that runs on bare metal and that has (or supports) immutable values.
Re: An immutable operating system
#58I don't really know how feasible this is without pretty significant performance impact (esp. memory usage), but as a research project, it sounds fascinating. Go for it.
My recommendation would be to modify an existing OS, like MINIX, to have two types of processes: mutable and immutable.
That way some (not all) of the potential advantages can be tested without having to start from scratch.
Re: An immutable operating system
#59I wrote an operating system in a purely functional dialect of Lisp; http://losak.sf.net There are a few things I learned in the process that I think are relevant here: 1. Forget garbage collection in the sense of any variant of mark-and-sweep. For an operating system latency is more important than through put, so you really want real time memory management. If you use reference counting, then there is a lazy variant…
> For an operating system latency is more important than through put
One interesting exception to this rule is operating systems for network packet routers. These need to be optimized for throughput over latency. I mean, the difference between 10 and 20 million packets per second is important, but the difference between 10 and 20 microseconds of processing delay is not.
This is a fun area to be in at the moment because simple academic-looking code can actually compete with highly optimized kernels like Linux because those have been optimized for something else.
Re: An immutable operating system
#60Why make the system language a Lisp instead of a language that is by default immutable? I'd think Haskell is a shoe in for something like this and you'd have a head start with House: http://en.wikipedia.org/wiki/House_(operating_system)
Personally I'm more of a fan of immutability than purity, which is why I haven't considered haskell. As mentioned in the post, though, I'm not sure if the language should be static or dynamic or something else.. And I don't really want to invent my own language either. Food for thought :)