Slashdot Mirror
Multics Scheduler
davecb wrote to us with a short description of three of the
Multics schedulers. The piece has some background information and history as well, which adds another element to the reading.
← Back to Stories (view on slashdot.org)
Multics (MULTiplexed Interactive Computer System) was a Bell Labs project that managed to acquire the unwelcome retrofitted acronym "Many Unnecessarily Large Tables In Core Simultaneously". UNICS (UNiplexed Interactive Computer System) was allegedly a "castrated MULTICS", and, as one of those odd quirks of history, the laboratory nickname stuck. Subsequently, they changed the spelling and capitalization and were then able to tell people that "Unix" was not an acronym. ;)
Geeky modern art T-shirts
It should be obvious that one of the primary reasons that Linux is as successful as it is is because when it appeared there were hundreds of thousands of coders and millions of lines of code all immediately available.
Infrastructure, infrastructure, infrastructure. You can't just tear it all down and make it perfect. You've got to work with the existing structure and move in little steps, so people aren't left holding the bag with nothing to show. Nobody wants to start from scratch. And really, nobody should have to start from scratch.
If you were to attempt to build up an OS to the level of Linux, from scratch, it would likely take you a decade. For what purpose? To end up with something that is a moderate improvement? Why not just improve what we've got?
Anyway, I am constantly amazed at the way people get all hyped out about a particular language or a particular OS. If you are a good coder, you can write good code in any language and on any OS. These are tools, people, and arguing about them is like two construction workers having a heated discussion over which hammer is better. Silly. Just pick the best tool available to you and go with it. If you don't like any of the tools, build your own. But don't whine because everyone else is too stupid to agree with you on what tool is the ultimate hammer. When I hear crap like that, I recall the old saying "it is a poor workman who blames his tools".
Yes, modern Unices are all "hacked together". But then, so is Windows. You see, there are two types of OS, those that people spend a lot of time hacking on, and those that no one uses. The latter have the sort of purity of an unlived in house. Everything is perfect, as the designer intended. But you have to realize that this would not last long were someone to move in.
The cake is a pie
What we need are some schedulers for the new century.
eBay: The Scheduler process posts information about available slots and processes bid for the time. After the auction period expires the slot is allocated to the winning process (once the 'cheque' has cleared). The duraction of an auction would be short. Reserve prices might be set but this could lead to idle cycles.
MiddleManagment: The Scheduler makes provisional assignments based upon its favourite strategy, but all of these have to be run past an administrative Daemon which has to authorise all slot allocations. The criteria would be very complex but factors include how sexy the process was and when the admin daemon last ran a golf game.
Such daemons only operate during core working hours and are easily distracted so the scheduler can sneak important but boring work through.
The government uses a variant of this called the RedTape scheme.
Boeing: The Scheduler runs a standard strategy but every so often it accidently allocates all the slots to the local refuse tip where processes dig through the mounds of trash looking for them.
OpenSource: The Scheduler insists on receiving a copy of the source code of any binary that applies for slots. It then allocates based upon the the degree of innovation (determined by metrics). Library calls or other attempts to restrict access to parts of the program reduce the priority.
SlashDot: The scheduler sets up pools of resource and processes submit requests for slots into this. Other processes enter their own bids or attach sub requests to other processes requests. Processes not engaged in bidding for resources on that pool rate the requests rewarding particularly appropriate requests and penalising irrelevant requests.
Particularly successful processes receive a bonus to future requests.
Gamma Testing - Where testing is extended to the full user community (AKA Shipping the Program)
... was that Multics was the only system whose directory separator makes sense. Forget "/" and "\" -- Multics used ">". When I switched to Unix, I found the arbitrariness of "/" to be annoying, the way people switching from Unix to Windows find the choice of backslash to be almost deliberately irritating.
If you read the article, you get a good idea of what Multics was like. It had tons of weird and wonderful features, like mapping memory to the file system. I think it was pretty successful in meeting most of its design goals, but was so large and idiosyncratic it could probably could never be ported to hardware not specifically designed to run it. Scalability runs two ways: Unix cherry picked the successful ideas from Multics, leaving a small but sophisticated OS that could run on low end hardware. The rest is history.
I think its kind of interesting to compare this to the Win2K/Linux situation, in that you have a large and complex system stuffed full of all the features anyone could dream up, stacked up against a small system implementing proven algorithms and techniques. Having been around a long time, this brief episode of indordinate Microsoft market power doesn't scare me: I know where I want to put my chips, at least in the server market.
Post may contain irony: discontinue use if experiencing mood swings, nausea or elevated blood pressure.
The rings of protection concept really did work. But it takes hardware support, which the PDP-11 didn't have, so UNIX, and its successors, don't work that way. They should. It would be easy to have ring hardware today; in fact, Pentium Pro/II/III machines have some of it, unused.
As for scheduling, Multics had Corbato's algorithm from the beginning, while UNIX had a truly awful scheduler for decades.
I think there's a fair amount of legitimacy to that argument. But, having come from an environment (Pr1me) that is to Multics sorta like Linux is to Unix, I'd like to make some observations.
First, surely some of Multics' complexity was overblown, perhaps because of attempts to have it do more than strictly necessary. I.e. it wasn't sufficiently simplified. We're committing the same "sins" throughout the GNU/Linux universe ourselves, e.g. piling feature after feature onto what should be simple, robust components (such as GCC) rather than providing separate tools. (Compare qmail's design to sendmail's, and then try and figure out why, after tons of discussion on the GCC mailing list last year, there's still no high-quality Open Source way to find pointer-alias bugs in C code.)
Second, much of what we take for granted in Unices of today was inspired, and to some extent proven in the field, by Multics and its descendants, like PRIMOS. Though not an expert on Linux-style dynamic linking, I've found it, and other things like signaling/exceptions, to be, in at least some crucial ways, poor second cousins compared to the technologies (in which I had substantial expertise) available in PRIMOS -- essentially a cheap sorta-clone of Multics -- back around 1984.
Third, hardware and networking improvements have probably significantly changed the "balance" of factors affecting design decisions that went into Multics. Back in those days, processors weren't cheap, therefore processes weren't cheap, nor were the process-creation and process-exchange activities we take for granted today. (Compare how many processes get exchanged and/or created just to handle an email or, heck, even a mouse click on a typical modern Unix system to contemporary equivalent activities back in the early 1970s, for example.)
Yet it seems today's "cutting-edge" Unix applications are designed with a similarly limited mind-set. Applications that truly and (IMO) properly take advantage of the "balance" of a modern Unix system, such as qmail, are few and far between. How many of today's new applications have what amounts to a scheduler inside of a single process, rather than relying on the Unix kernel (Linux, *BSD, whatever), for example? How many could change from using asynch or non-blocking I/O to the more easily understandable, maintainable, and verifiable (security-wise) traditional blocking I/O by breaking out the various functions into distinct processes/executables?
The "Keep It Simple, Stupid" (KISS) principle indeed may have been violated by the early Multics design sufficiently to doom it in the long run vs. Unix, but that doesn't mean we've entirely honored it in Unix-land either. Especially now that we've "won", in the sense that we're competing primarily against an OS that makes Multics look comparatively simple and straightforward (Windows 2000), it's tempting to just "pile on the code" without further regard to KISS, thinking the goal is to further the position of (some variant of) Unix, rather than the widespread deployment of KISS-based software.
Let's strive to avoid that temptation, assuming it's not already too late.
Practice random senselessness and act kind of beautiful.