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)
I've been surprised for many years that more theft wasn't committed on some of the many excellent design ideas in Multics by the Linux community.
When you go to this site, remember Ashworth's Law: "there's usually something even more interesting, somewhere else on the site". My favorite is the list of still-running Multics implementations.
Even today, ten or more years after there was any hope of reasonable support, there are _still_ three sites using Multics in production.
As a cross-link, the Motorola HA Linux work ties right in here, conceptually: Multics was originally intended as a 'comuting utility', where any part could be swapped out at any time, including CPUs and memory.
Good show.
Cheers,
-- jra
-----
Actually, the PDP-11 did have 3 rings of protection. UNIX just didn't bother to use them.
forgot the link...
Userfriendly
I have been told by IBM colleagues that deep inside AIX, there's a virtual-memory file-mapping OS also derived from FS.
Does "Multics live on" here? No. The single-level store idea was used by several OS designs, and implemented in various ways. A better way to say it is that this feature "lives on."
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.
:-) = I am happy
:^) = I am happy with my big nose
C:\> = I am happy with my OS
Over half of the early Stratus SW engineers were from the seventies Multics group. The goal of Stratus was to develop a hardware fault- tolerant product to compete with Tandem. There were twenty other companies founded to do the same thing, and all but Stratus tried using a UNIX OS. The VOS operating system, done at Stratus from scratch by Multics veterans under commercial and start-up pressures, succeeded where 19 UNIX ports failed.
Eventually Stratus did a UNIX port as well. The day the UNIX port began, one engineer --- not a Multician --- noted: "VOS took everything from Multics that was easy, UNIX took everything that was wrong." This validates the KISS concept noted on another thread. VOS was 10x as reliable as UNIX for many years.
Now I'm writing this on a UNIX box. Worthy or not, UNIX is our most recognizable heir, it's "family". I'm equally tired of Multicians throwing it out of the house and those who believe UNIX came from the other, better, side of the tracks.
Although Multics is quite esoteric, it is not overly complicated. In fact, it can be well understood with the mastery of a few fundamental concepts. What killed Multics was the degree to which it fully utilzed the hardware capabilities of the machines it ran on and the competency of the companys that owned it. It was one of many industries that General Electric has abandoned in its lifetime, and Honeywell, who "adopted" it, never wanted to sell it. It was viewed as competition for its GCOS systems. It is amazing how many Multics systems were sold, since you had to beg the salesforce to sell you one.
Actually we used to update software asynchronously, too: when I worked in Mineapolis, a different database layout was being exposure-tested during several weekends. I couldn't even tell they were experimenting, much less that they were rolling forward and back with something so low-level. (I was a dumb user in those days, you understand).
A smarter colleague taught us the algorithm, but that's a rant for another day...
--davedavecb@spamcop.net
--
Brian Fundakowski Feldman
Actually it's more the opposite: they're relatively simple, and intended for a system whose main purpose in life was to provide good interactive performance. The multi-queues trick was a way to keep the cost of scanning the process queue down.
In modern systems, very large numbers of processes (or threads) can cause you to spend way too much time in the dispatcher: this was the subject of an IBM/Linux paper recently...
--davedavecb@spamcop.net
Dude?
Episode 1 will be out on video in a month or so. Hold yer horses.
Oh, and stop using copies of the Principia Discordia for rolling papers.
Posting as an AC to preserve my karma...
/Brian
You should add that the RedTape scheme never actually dispatches any useful work; only the internal administrative processes are ever eligible and they are not allowed to complete.
This post is the best idea I've seen in a long time. You see, if all the troll posts get put in _one_ comment, and that gets moderated down, all the people who like them can just read the one comment, and all the people who hate them don't need to.
On the other hand there are many good examples of programming in linux. What comes to mind for me is the 'mutt' email program -- you only need to dig into the configuration if you want to -- and of course vim, tcsh, pine, etc. You only have to learn a few simple commands to use them. Complexity is not 'forced' on you.
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.
I'd like to give a big punch in the face to Linus Torvalds. Personally.
Why did he decide to use the Unix design, which is neither modern nor usable? Multics offered superior performance and effiency, even on th e most modest hardware (and a JVM is on the way).
IMHO, Unix is both dead and smelly. The ancient syntax, obscure system calls, and horrible choice of systems programming language (C? I don't think I'd be jumping to conclusions if I said Ken was partaking of 60's culture, perhaps too much) leads up to one hulking monster, still haunting users today. Unix has gone through so many revisions that today you can see just how horribly hacked together it is.
And some people wonder why Linux has a hard time earning acceptence! If it had Linics, I think we would truly be entering a new era of computing. To this end, I am starting the WAM! project (WAM ain't Multics) to create a new Multics clone, for modern hardware, completely free. Right now, I've got a working PL/I compiler going on my pentium. If you'rew interested, drop me a line.
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
Thank goodness we don't see this kind of insane bloat in UNIX systems
Additional Names
Wow, those are a lot of complicated algorithms. They weren't kidding when they said that MULTICS was huge and overly complicated...
Some of these make more sense coming from a "batch-job scheduling" perspective. Of course, we still use credit-based scheduling algorithms today (because they rule!) and I can't picture using six queues(!).
Also, about the name: If MULTICS is an OS designed by a lot of people, then Unix would be an OS designed by one person...
---
pb Reply or e-mail; don't vaguely moderate.
pb Reply or e-mail; don't vaguely moderate.
The idea of having the 6 queues is a clever way to make minimize time wasted in context switches by giving long-running non-interactive processes large but less frequent time slices... Sounds cool to me...
---
Play Six Pack Man. I
(see subject line)
Chris Wareham
Do you think the guy who's maintaining FreeDOS should be punched?
No, him and Pat Viliani deserve a free lifetime supply of Dove(tm) bars.
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); }
He's talking about mapping memory to files, not files to memory.
Who said technical people have no artistic sensibilities? Who said there couldn't possibly be a poet on slashdot? God what a wonderful, superb troll! U R truelie the greatest!!!1! - Gratefully yours WDK
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.
VOS, an OS which runs on Stratus computers, uses ">" as its directory separator character.
Sweet jesus you're a long winded bastard! This thing goes on for like 5 pages or something! I will give you credit though for the one line:
"Cripes, I've been arrested for Statuetory rape"
after all that Natalie Portman turning into a statue fantasy stuff--probably best not to try and over-analyze that too long.
All in all about as interesting as this "Science" article about multics...
Shows you how badly something can be designed
when everyone wants to throw their two cents in.
Also when designed primarily by professors who
have no market constraints.
Software engineering fortunately learned a few
things since the 1970s.
UNIX took the philosophy of simplicity and elegance. Its most elegant version being CMU Mach
(in NeXT and Apple) and most widespread version in Linux.
(Victim of Multics at MIT in the 1970s.)
Unix does many things wrongly!
.oO0Oo.
A single user system with muli-user capabilities tacked on.
But it does things good enough for most people but blindly holding it up as the shining beacon of correctness is clearly pointless.
There are places where the networks are not touching,and there are places where they are-Boeing's Lori Gunter
... 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.
Unfortunately the referenced Multics link seems to be /.-ed. But it brings up a subject that's been on my mind lately; the Linux scheduling algorithm. Anyone have any links to a discussion of it? (Other than the code!) I've noticed, with RH 6.0 at least, that Linux seems a lot more "clunky" in its response when it gets a bit loaded. Much more so that Solaris or FreeBSD. But I've not looked at scheduling algorithms since reading The Design of the Unix Operating System by Maurice Bach very, very many years ago.
But ended up with a supercomputer instead...
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.
I'd have to agree that Linux isn't clearly superior, or even smaller. Code size figures for Windows include all sorts of things which aren't in the Linux kernel.
But I have to take issue with your comment about the Windows 2000 GUI. I agree it's still not brilliant, but it's noticeably nicer to use than 98. There's still a few silly little things I'm not quite comfortable with, but it's not all that bad a GUI. Really.
Greg, posting under IE5 as Netscape's playing up. Oh, it's nice to be reminded of just why I hate IE...
Greg
(Inside a nuclear plant)
Aaaarrrggh! Run! The canary has mutated!
Do not post links to Amazon, you may be violating a patent ;-)
Let's start coding an PC-MULTICS Operating System *g
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.