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)
To me, it seems the only right way to go from Unix. Because Unix won't be the ideal system forever. What do you think, is EROS too complex to survive?
NOSPAM@REMOVETHIS.NO.SPAM - you'll find the real address somewhere
Mark Miller (who has a really cool web page on advanced OS stuff) used to have a page on Hydra; seems to be gone now, unfortunately.
Hydra was a capability-based system, and is likely moreso a parent of EROS than it is a child of Multics...
If you're not part of the solution, you're part of the precipitate.
If you pull the CPU out of your PCI bus system while it's running, it is Rather Likely that you'll do severe damage to the hardware.
The more we see things like USB, I2O, and serial IDE, where there are I/O controllers independent of the CPU, the more there will be an ability to attach/detach peripherals while the system is running. And if there was a motherboard that provided a "protocol" to allow connecting/disconnecting CPUs and memory online, that would be a further extension of this.
Mind you, the cost of allowing such a "protocol" would likely substantially increase the cost of the motherboard, and people are generally price sensitive particularly to things that they rarely fiddle with, which discourages adding this feature to any computer systems that any of us can afford to buy...
If you're not part of the solution, you're part of the precipitate.
More correctly, some PDP-11's with MMUs had three protection levels (Kernel, Supervisor, and User), but most operating systems, including but not limited to UNIX, used only two of them. (I think some Digital OSes, e.g. RSX-11M Plus?, may have eventually used Supervisor mode, on machines that had it, to provide an additional address space; I don't know whether they actually used it to provide finer-grained protection levels, however. Bell Labs's MERT used supervisor mode - it ran a low-level kernel in kernel mode, and ran a UNIX kernel-level environment atop it in supervisor mode, with that environment running user-mode code in user mode - i.e., it did use it to provide finer-grained protection levels. There may have been other OSes that did so as well - KSOS?)
VAXes had four levels, and VMS, as far as I know, used all of them (kernel code in kernel mode, RMS in executive mode(?), command interpreter in supervisor mode, and userland code in user mode); UNIX, however, used only kernel and user.
Memory-mapped files are now present in most if not all all modern UNIX-compatible OSes, as well as Windows 9x and Windows NT/2000 - but
The ring stuff, if that's what you're referring to, is, as far as I know, in all members of the IA-32 series, unless you count embedded versions that lack a full-blown IA-32 MMU, as those might not have it.
It may not be in all members of the IA-16 series (8086/8088, 80186/80188, 80286), but that's another matter.
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
Um, how does one go about contacting an AC?
Seriously, though, I think it would be very interesting to see about a free Multics clone for PC hardware. But do you honestly think that Linus knew what he was starting when he began coding the Linux kernel? Even if you don't like Unix in general, the value of his kernel, showing up at that point in time, is inestimable. He doesn't deserve a punch in the face. Do you think the guy who's maintaining FreeDOS should be punched? What if it becomes popular? Sheesh.
(see subject line)
Chris Wareham
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.
ThadThad
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)
But it sure looks like UNIX has its multiuserness at a reasonably deep level. Can you elaborate on the lack of UNIX multiuserness, perchance?
If you're not part of the solution, you're part of the precipitate.
I read somewhere that Multics machines feature hot-swappable everything. Peripherals, cards, drives, even CPU's.
That's why I want a Multics box. Imagine the looks on the faces of your friends as you say, "Check this out!" and immediately yank a CPU out of your machine without the computer skipping a beat. MWHAAHAHAHAHAHAHAHAHAHAHAHAHAHAH
oh, I thought you had to have been castrated to operate one. Whew.
try { do() || do_not(); } catch (JediException err) { yoda(err); }
To what is he referring when he says "mapping memory to files", and how is this different from "mapping files to memory" (except in the order of the two words relative to "mapping" and "to")? (Or did he just decide to use the words in the reverse order in which they tend to be used when talking about mmap(), in which case we're both talking about the same thing....)
In Multics, you initiated a segment, which caused a file to appear in your address space; this is, to some extent, similar to opening a file and mmap()ing it, or doing the appropriate Win32 voodoo dance to get something to hand to MapViewOfFile() and then doing so.
(See the definition of "initiate":
in the "i" section of the Glossary on the Multicians.org site.)
I.e., they both involve taking a file name (pathname in UNIX or Win32; pathname, or segment name to be searched for in a path, in Multics) and, after making various calls to low-layer OS code, eventually getting a pointer that can be dereferenced, causing page faults that are satisfied by fetching data from the file, and possibly allowing stores through that pointer, with dirty pages pushed back to the file.
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
Which is the system full of all the features anyone could dream up and which is the small system?
Windows 2000 actually has some pretty nice features. If the user interface were replaced with something sane (by which I mean, doesn't assume I'm an idiot and do something other than what I say), it could be a decent system. I think it's sort of wishful thinking to call Linux small. Sure, the kernel may be only 50 megs of source, but the system as a whole (take any disto you want) is far too big to be understood by anyone but an expert with time to burn. Not that Win2k is better, but it isn't clearly inferior to Linux in this particular case.
Does Multics live on, conceptually, in the AS/400? I heard that it uses segments, and a "memory is disk is memory" permanent storage scheme ala multics. Does anyone know more aobut how OS/400 works?
...
Amusingly, AskJeeves returned "Dementia -neurological diseases and disorders - more resources" when I asked, "how is os/400 related to multics"
Napster-to-go says "Fill and refill your compatible MP3 player", which is a lie. It's not MP3. It's WMA with DRM.
... 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.
Sorry. I have asked the ISP for temporary relief from its bandwidth limitation policy. They "strive to read all email within 24 hours." -- tom
Two things.. First of all, there is no way to find all aliasing bugs in a program unless we solve the halting problem. (which is unsolveable).
But regardless of that, code which has pointer aliasing bugs is not standards conformant. The compiler is completely within the spec if it miscompiles this code, or if it prints out 'You are an idiot' one million times.
You can try to write code in the compiler to detect these bugs. It can't be completely accurate, the question is can we make it useful. If it catches every bug, but also flags a lot of standards-conformant code as bad, that's can be more useless than missing instances of this bug.
Besides which, aliasing issues exist because compilers are using the many registers that a modern RISC CPU's has, and they don't want to be forced to reload potentially dirty data on every memory-write. Choose another language then. C/C++ wasn't, isn't, and can't be fully optimized on this type of modern CPU. Even with aliasing analysis, there are still avoidable ineffeciencies.
Windows 2000 actually has some pretty nice features.
I don't doubt it for a moment. The MS people are not stupid or insane; they're playing the hand they were dealt. Multics had a lot of really cool stuff, just way more than was necessary.
Sure, the kernel may be only 50 megs of source, but the system as a whole (take any disto you want) is far too big to be understood by anyone but an expert with time to burn.
Well, using my Catholic school education and borrowing an idea from Aquinas, there's essential complexity and accidental complexity. Call it architectural vs. implementation if you will. Essentially, Unix is very easy to administer, but it has lots of accidental complexities. The way to deal with it is to RTFM and use the source. The old joke was that the Unix manual was written for a Unix guru with a faulty memory. There's more than a little truth in this, in that you can be a Unix guru without having to remember everything.
by which I mean, doesn't assume I'm an idiot and do something other than what I say
I think this is sometimes symptomatic of complex behavior with a simplistic facade thrown over it.
Post may contain irony: discontinue use if experiencing mood swings, nausea or elevated blood pressure.
The "percentage" feature was required by university customers who funded their multi-million dollar machines by combining funds from multiple departments. The departments wanted to be sure they got what they paid for: "darn CS students are using more than their share of the machine."
The realtime scheduler was invented to win benchmarks, and it did. A relatively underpowered CPU was able to run specified workloads more efficiently that its competition, because of the tuning control available.
Both of these problems have gone away, now that each of us has more power on our desktops than the multi-million-dollar machines that a whole university used to have to share.
I am a fan of Unix and Mach. They solve different problems than the one Multics was solving, and do so in a different economic and technical world.
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.
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?
If you're not part of the solution, you're part of the precipitate.
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.