Slashdot Log In
Multics Scheduler
Posted by
Hemos
on Tue Mar 07, 2000 10:19 AM
from the looking-at-new-timing dept.
from the looking-at-new-timing dept.
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.
This discussion has been archived.
No new comments can be posted.
Multics Scheduler
|
Log In/Create an Account
| Top
| 71 comments
(Spill at 50!) | Index Only
| Search Discussion
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
On the origins of "Unix"... MULTICS and UNICS (Score:4)
Re:As a hard-core Multics user (Score:5)
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.
small point (Score:3)
Zurk wrote:
This is a dangerouse attitude, because not only does it assume that what is good for you is good for sombody else (theory of absolute truth), it assumes that what is good now cannot be bettered.
Unix *is* good, for you, for me, for many people, but no nesseserly good for everyone. No only that, but this assumption that *nix is *right* implies that everything else is *wrong*. Not only everything that has been, but everything that is to come. The simple truth is that at some point in the future, you, I, Linus, IBM, Apple, or, god forbid, Microsoft, might create something better, and we have to be able to accept that, and go with it, or hold back the state of the art, because of bigotry.
ThadNew Scheduler Strategies (Score:5)
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.
The best thing about Multics... (Score:4)
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.
The importance of Multics (Score:4)
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.
The Unattainable Holy Grail... (Score:3)
It runs up against several problems:
- According to Multicians, an important aspect to Multics was the use of PL/I as the programming language.
- Another crucial aspect was the hardware support for memory management and rings.
- One alternative is to create a hardware emulator that emulates the Honeywell hardware. That would allow using existing Multics software, rather than merely involving creating analagous software.
- Another option would be to create a "Multics shell" to parallel Ksh, Zsh,
... and create a vaguely Multics-like environment atop Linux. - I've had Organick's book on Multics on order from Spamazon for a couple years, and have heard nothing. Some documentation may be hard to come by.
In effect, the problem with creating a Multics clone is twofold:There's not a "free" PL/I compiler.
Probably the nearest alternative would be to implement using the nearest thing to MacLisp, namely Common Lisp. But down that road lies the rather different path of creating a Lisp OS. [hex.net]
Apparently Intel designed some Multics-like capabilities into some (not all!) members of the IA-32 series.
Unfortunately, that means having to get access to the Multics software base, which is not likely terribly available these days.
The only system known to still be in production use is at DND: Maritime Command in Halifax, Nova Scotia, and its decommissioning is planned this year. Remember, military system. They're not likely to be willing to give out copies, independent of any rights Honeywell, Bull, and others may have...
Of course, that doesn't get you segment/ring control, which hurts the emulation.
Does it have to run the same software? Does it have to use PL/I? Can it be upgraded with other modern notions?
Multics -> Unix: KISS Victory? (Score:4)
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.