• OperatingSystemsOverview

1. What is an operating system?

• Difficult legal question in Europe and in Clinton-era US
• We can consider several definitions:

  User's view

  Software that came with my computer that I can't get rid of.

  Textbook view

  Software that hides details of the underlying hardware, mediates access to resources, and enforces security policies.

  System programmer's view

  Anything that runs in ring 0.

• We will mostly adopt the programmer's view.
• Essential idea is that OS provides an abstraction layer on top of the bare hardware.

  • Typical modern system: Hardware -> BIOS -> kernel -> libraries -> user programs.

  • Where to draw the boundary? E.g., do libraries fold into the OS?
  • Natural boundary is the system call.
    • Modern CPUs have different protection levels or rings (4 on Intel CPUs, but nobody uses anything but ring 0 and ring 3).
      • Kernel code (ring 0) has full access to hardware.

      • User code (ring > 0) doesn't.

    • If user code tries to execute a privileged instruction, it traps to kernel code.
      • On IA32, uses same mechanism as for hardware interrupts:
        • CPU switches to ring 0.
        • Various magic happens in the background (memory system switches context, interrupts may be disabled).
        • IP jumps to new location based on interrupt vector table in low memory.

          • => kernel is whatever the interrupt table sends you to?

      • Kernel can now decide what to do in response to the "illegal instruction"

        • Userspace process is doing something wrong => kill it!

        • Or maybe it just needs some help from the kernel => help it.

          • This is the system call case.

          • Eventually return using specialized opcode (iret on IA32)

          • int/iret acts like very expensive context-switching procedure call.

2. History

• In the beginning: no OS
  • Program raw hardware with a soldering iron (still used in 23rd century according to Star Trek!)
  • Eventually graduate to punch cards/paper tape/magnetic tape.
  • Model is that a batch-mode program gets complete control over the entire machine.
• IBM virtual machines
  • Build one machine that pretends to be many machines.
  • Each individual machine still acts exactly like the classic IBM 1401 (or whatever) that you programmed with punch cards.
    • Includes virtual punch card readers, magnetic tapes, etc. with bug-for-bug compatibility.
    • We actually haven't gotten very far from this.
  • Most programming is still done in batch mode.
• Timesharing
  • Build abstract processes that run on an idealized virtual machine.
  • Works nicely for interactive systems with many users.
  • Enabling economic change: cheap computers and expensive users.
    • Happened first in well-funded research laboratories e.g. Xerox PARC, Bell Labs, MIT AI Lab.
    • Now we all do it.
• Distributed systems
  • Get thousands or millions of machines to work together.
  • Enabling economic change: cheaper to buy many small computers than one big one; cheap networks.
  • Dates back to 1960's parallel machines like ILIAC, now shows up as peer-to-peer systems and server farms.
  • We mostly won't talk about these.

3. What abstractions does an OS provide?

• Hide ugly details of hardware interfaces.
  • Most hardware ships with software drivers.
  • This means hardware designers don't have to provide nice interfaces since driver can paper it over.
    • This is usually a good thing!
    • Software is easier to change than hardware
      • Can upgrade capabilities by upgrading drivers.
      • Can fix bugs without burning new ICs.
    • Software is cheaper than hardware: can exploit brainpower of the CPU

      • Example: WinModems

      • But sometimes we want the speedup we get from hardware (e.g. graphics cards)
  • OS goal: provide a standardized interface to device drivers.

    • New picture: hardware -> BIOS + device drives -> kernel -> libraries -> user programs.

  • Secondary goal: convince hardware designers to write drivers for your OS
    • Works best if you own a large chunk of the OS market.
    • Obstacle to new OS development: even experimental OS's have to pretend to be Windows or Linux to device drivers!
• Pretend we have more resources than we really have.
  • Process abstraction
    • Yes, you only bought 1 CPU (or 2, or next year 8), but we'll pretend you have infinitely many.

    • This works by time-sharing CPU(s) between processes.

      • Cooperative multitasking: polite processes execute yield system call, kernel switches to another process.

        • This lets a runaway process freeze your system!
        • But it's easy to implement.
        • Used in practice in pre-NT Windows, pre-OSX MacOS, even today in many embedded OSs (e.g. PalmOS).

      • Pre-emptive multitasking: kernel switches to another process whether you like it or not!

        • No runaway processes

        • But requires more work in kernel and in processes since they have to deal with concurrency issues.

    • Why this works: most programs have "bursty" demand on CPU.

      • If you are waiting 10¹⁰ clock cycles for the user to click the mouse, why not let somebody else use the CPU?

      • Same thing for 10⁸-cycle disk operations.

      • With good scheduling, nobody will notice we are doing this.
    • Further design decisions:
      • How to choose which processes to schedule? E.g. real-time, priorities, fair-share: many possible policies.
      • How much context to store for each process?
        • E.g. threads vs processes: does a process get its own address space in addition to its own virtual CPU?
        • Some historical oddities that persist for convenience like current working directories.
      • How to manage processes?
  • Virtual memory abstraction
    • We'll take small fast memory and a big slow disk and combine them to get big fast virtual memory.
      • Only works because most memory isn't used very often.
      • Usually requires hardware support (memory manager)
    • Bonus: each process gets its own address space
      • Security payoff: bad process can't scribble on good process
      • Compiler payoff: don't need to write position-independent code
• I/O abstractions
  • Next step up from hardware drivers: make all your devices look the same
  • Keyboards, printers, console display, the mouse, many USB devices: all streams of bytes.
  • Disks, flash drives, remote network storage: all blocks of bytes.
    • Old days: all stacks of 80-column EBCDIC punch cards
  • Goal is to simplify programmers' lives.
    • Why in kernel and not in libraries? Easier to change kernel for new hardware since we have to bring in device drivers anyway.
• Filesystem abstractions
  • Present big-bag-of-bits as structured collection of files.
    • File is typically a big-bag-of-bits.
    • But there is a tree structure organizer files into directories/folders.
    • Files may also have metadata.
      • What it is called.
      • Who has writes to the file.
      • When it was created.
      • What program to use to read it.
    • Goal is to provide enforced common language for application program developers.
    • Unix approach: represent things that aren't files in the filesystem anyway

      • E.g. /dev/tty, /proc/cpuinfo, /proc/self/cmdline.

      • Allows reuse of same interface everywhere.
    • Things to think about:
      • Why not do this at the library level?
      • Why a tree structure when databases dumped this design for tables?
        • Note that attempts to bring in tables (e.g. in Windows) have generally failed.
      • Why unstructured files?
        • Old days: all stacks of 80-column EBCDIC punch cards
        • Windows: text vs binary files
        • These seem to mostly be holdovers.
• Security
  • Any time we provide an abstraction, we can enforce limits on what you can do with it
  • Process limits
  • File permissions
  • I/O permissions
  • In some systems, very fine-grained control, SECRET/TOP SECRET enforcement, etc.
• Other things that get shoved into the kernel for performance.
  • E.g. window systems

4. Recurring themes

• Suffering
  • OS development happens without all the nice tools an OS gives you.
    • This makes kernel programming harder.
      • Have to use low-level languages and assembly.
      • Debugging tools are limited.
  • You are also running on the bare hardware.
    • Mistakes are harshly punished.
• Modularity

  • OS is a large software system like any other => we can't build it unless we can divide up the work

  • Layered approach
    • Build up from core abstractions adding new functionality at each layer

      • E.g.: BIOS -> device drivers -> memory management -> process management -> I/O management -> network abstractions -> filesystem

      • Getting the order of the layers right can be tricky: what if I want to swap VM out to files?
  • Microkernel approach
    • We like processes so much we'll push everything we can out into userspace.
    • Advantage: can restart your filesystem daemon without rebooting the whole machine.
    • Disadvantage: where are you loading your filesystem daemon from?
    • Very active area of research in 1980's and 1990's, but then most people gave up because of bad performance.
    • (But still used in some niches and performance has been getting better.)
  • Exokernel approach
    • Provide minimal partitioning of resources and then push everything into the libraries.
    • Generally not seen in the wild.
    • Main selling point: cool name.
  • Monolithic/modular kernel approach
    • Kernel is one giant program.
    • But use OO techniques to modularize it.
      • E.g. standard device driver interface with dynamic loading.
    • Advantage is that internal calls in the kernel are cheap procedure calls instead of expensive context switches.
    • Disadvantage is that one bad module can destroy your entire system.
  • Virtualization
    • Run an entire OS inside a process
    • Rationale: protects system against an OS you don't trust
    • Possible other rationale
      • Systems are now being built from multiple processes

      • => need a second level of process abstraction to encapsulate whole systems

      • E.g. virtual WWW servers.
      • Possibly a sign that process hierarchy is too flat: analogy to 1960's BASIC/FORTRAN subroutines that couldn't be recursive.
• Security
  • Why separate address spaces/file permissions/etc.?
    • Can't trust users, they make mistakes.

    • Can't trust programmers, they make mistakes that execute at 10¹⁰ instructions per second.

    • Can't trust poorly-socialized script kiddies, they don't share your agenda.
    • Good fences contain the damage (but note most OSs don't really try to protect against malicious users).
  • Why reboot?
    • Bugs produce errors that accumulate over time.
    • Restarting processes from scratch resets to a known state.
    • (Same reason humans aren't immortal: easier to manufacture new humans than repair the old ones.)
    • (Also same reason people throw away their virus-infested PCs rather than disinfect them.)
  • Trade-off: "A computer is only secure when it's unplugged."
    • Too much security makes users bypass it.
    • Too much security destroys your work.
• Performance
  • Famous old SGI story

    • Suppose we install a kernel on 10⁸ machines.

    • Every day each machine wastes 1 second of a user's life.

    • 10⁸ machines times 10³ days = 10¹¹ wasted seconds = 30 wasted lifetimes.

    • => bad coders are worse than serial killers.

  • Less of an issue over time as machines get faster
  • But defining constraint on early OS development (also why PC OS's recapitulated mainframe OS's 20-25 years later)
  • Question to ask: what features of my OS are solutions to performance issues that are no longer relevant?
• Consistency
  • Backwards-compatibility is a huge issue, especially for commercial OSs.
    • Free OS users tolerate disasters as part of the whole hair-shirt mentality :-]
    • Microsoft story

      • When SimCity broke because Windows closed the use-after-free loophole, users blamed Windows and not SimCity

      • So Windows now recognizes SimCity and runs a special compatibility version of malloc/free

  • If your API is too complicated or too restrictive, natural selection comes into play.
  • Sometimes crummy interfaces persist through lock-in or survival of the least inadequate.
    • E.g. NFS, X11, sockets, and other de facto sub-standards.

  • Hard to guess what users want => safe OS research makes existing interfaces 10% faster.

  • But you become famous for new approaches that catch on.
• Separation between policy and mechanism
  • We can't predict exactly what scheduling/security/etc. policies users will want.
  • So build the OS so we can change the policy later.
  • Modularity helps here just as in regular programming.