5
$\begingroup$

A multi-user, multi-processing operating system cannot be implemented on hardware that does not support

  1. Address translation
  2. DMA for disk transfer
  3. At least two modes of CPU execution (privileged and non-privileged)
  4. Demand paging

My attempt:

Somewhere it explain as : Address translation is needed to provide memory protection so that a given process does not interfere with another.

We also need at least 2 modes of execution to ensure user processes share resources properly and OS maintains control. This is not required for a single user OS like early version of MS-DOS.

Demand paging and DMA enhances the performances- not a strict necessity.

Can you explain it in a formal way, please?

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ If you assume cooperating processes, why do you need any protections? $\endgroup$
    – adrianN
    Jun 21, 2016 at 11:45
  • 3
    $\begingroup$ @adrianN - exactly - the OP specified only "multi-user, multi-processing" - not that the processes (much less the users) were "protected" from each other (in the modern sense of the word). TSS-8 ran on the extremely limited PDP-8 hardware, and RSTS-11 on PDP-11s without memory management. Even when you add a requirement for protection between processes or protection between users OS/360 MVT TSO ran on IBM-360 hardware without paging or (I believe) address translation. $\endgroup$
    – davidbak
    Jun 21, 2016 at 17:00
  • 1
    $\begingroup$ Address translation is not needed - there are other solutions, e.g. "memory protect" bits on regions (typically, fixed size like pages) of memory, e.g., IBM-360 "storage protection". $\endgroup$
    – davidbak
    Jun 21, 2016 at 17:03
  • 1
    $\begingroup$ @davidbak (and the OP) - Another example of a multiuser, multiprocessing operating system that ran on minimal hardware was Microware's OS-9, which ran on the Motorola 6809 processors and was ported to the Tandy Color Computer 1. A 0.89MHz 8-bit CPU (with a few 16-bit extensions, but no privilege modes), 64K flat memory structure (so no paging or translation), and no disk DMA. If configured well, you'd have 40K remaining for programs. It was multiuser because I used to run programs both on the console and log into the system with my Tandy 200 laptop over RS232. $\endgroup$
    – zmerch
    Jun 22, 2016 at 20:51

4 Answers 4

Reset to default
21
$\begingroup$

None of the above.

As you noted, DMA and demand paging can be useful features but are not necessary to support multiple users and multiprocessing.

Address translation is not necessary even for memory protection. Memory protection can be separated from address translation via a protection lookaside buffer or memory protection unit.

Providing a distinct privileged operating mode in the processor is not necessary for a multiuser system. In theory, provable trust of software can provide protection against misuse by users. Another alternative is capability systems; one can use non-forgeable fat pointers to provide resource protection.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Indeed, none of the above. Plenty of programming languages don't even have pointers. The BASIC and FORTRAN provided in IBM's CALL/360 time-sharing service didn't, so no protection was needed. $\endgroup$
    – Martin Kochanski
    Jun 21, 2016 at 12:37
  • 6
    $\begingroup$ Microsoft Research's Singularity OS is a good example of a modern (albeit experimental) OS that used compile-time proofs of safety instead of hardware privilege levels. $\endgroup$
    – zwol
    Jun 21, 2016 at 16:48
  • $\begingroup$ @zwol: I wanted to mention that, too. It's a really cool system, built by a team that included a significant portion of language, tools, verification, static analysis, type systems, and compiler researchers, which has a significant impact on the design of the OS, although there's some parallels to e.g. IBM OS/400 and some Java OSs. $\endgroup$
    – Jörg W Mittag
    Jun 21, 2016 at 17:26
9
$\begingroup$

I remember a counter-example from the 1980s:

OS-9/68000 was quite popular then: a multi-user, multi-processing real-time operating system for the Motorola 68K processor family, loosely patterned after UNIX. It didn't require any of the features from your list.

The 68000 didn't have address translation. OS-9 compilers produced position-independent code that could run from any address, using only relative branches (N bytes forward or backward) instead of absolute jumps (to a given address X). Static memory was always addressed relative to the OS-provided data start address. Dynamically-allocated memory always comes at "random" addresses, so applications always address dynamically-allocated data relative to an OS-provided address.

DMA disk transfer was typically used in OS-9 device drivers, but that was not necessary for the multi-user feature, only to avoid the blocking time of programmed I/O that would otherwise negatively affect the real-time capabilities.

If I remember correctly (wrong! Thanks, @davidbak), the 68000 itself didn't have a privileged mode, so the protection against evil code was limited. There was an optional memory management unit chip available that OS-9 could use for protection purposes.

OS-9 typically ran without demand paging. When physical memory was exhausted, new memory allocation attempts simply failed (demand paging doesn't fit nicely to a real-time OS). I even know a few Windows servers today where the admins completely switched off the pagefile feature.

But don't misunderstand me: The features you listed perfectly make sense for multi-user, multi-processing operating systems, I just wanted to point out that none of them is strictly necessary.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ 68Ks did have memory protection - see here, for example for example - but simpler hardware boards didn't support it - since it needed to be respected by the (discrete) memory controller and all I/O devices (which were memory mapped). And of course the operating systems of the day were simpler too, and some didn't support it. $\endgroup$
    – davidbak
    Jun 21, 2016 at 16:47
  • 1
    $\begingroup$ Looking that far back, MP/M-80 [en.wikipedia.org/wiki/MP/M] ran on the Intel 8080, which had no advanced features at all. $\endgroup$
    – Martin Kochanski
    Jun 21, 2016 at 18:58
  • $\begingroup$ @MartinKochanski - good one! I had forgotten that MP/M was not just multi-tasking but also multi-user. $\endgroup$
    – davidbak
    Jun 21, 2016 at 19:39
3
$\begingroup$

You could change the question to "I would not want to implement a multi-user, multi-processing operating system on hardware that does not support ... " and my answer to all four points would be "Yes", except for point two (DMA for disk transfer). But the question was "cannot be implemented..." and the answer is clearly no to everything.

You would probably have the problem that there would be no separation whatsoever between processes, so this would be very unsafe, and one rogue application could easily take down any other application and/or the operating system itself.

From personal experience, I remember one place that had high end workstations (16 GB of RAM each, which was a lot at that time), and they turned off demand paging. That way the machines ran 5% faster, and they knew that for their use, if 16 GB was not enough, demand paging would totally kill performance, and the only reasonable solution was buying a machine with more RAM.

Improve this answer
$\endgroup$
0
-1
$\begingroup$

Cannot be implemented is not the same as it's very hard to implement.

If a hardware supports turing-complete programming, then anything can be implemented on it, given enough time and memory. This means you could theoretically implement a multi-user, multi-processing operating system on a Turing machine. Written in Brainfuck.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ How do you propose to implement interactive computation on a Turing machine? $\endgroup$
    – David Richerby
    Jun 22, 2016 at 7:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.