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.
- On IA32, uses same mechanism as for hardware interrupts:
- Modern CPUs have different protection levels or rings (4 on Intel CPUs, but nobody uses anything but ring 0 and ring 3).
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 1010 clock cycles for the user to click the mouse, why not let somebody else use the CPU?
Same thing for 108-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
- We'll take small fast memory and a big slow disk and combine them to get big fast virtual memory.
- Process abstraction
- 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.
- Present big-bag-of-bits as structured collection of files.
- 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.
- This makes kernel programming harder.
- You are also running on the bare hardware.
- Mistakes are harshly punished.
- OS development happens without all the nice tools an OS gives you.
- 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?
- Build up from core abstractions adding new functionality at each layer
- 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 1010 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.
- Why separate address spaces/file permissions/etc.?
- Performance
- Famous old SGI story
Suppose we install a kernel on 108 machines.
- Every day each machine wastes 1 second of a user's life.
108 machines times 103 days = 1011 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?
- Famous old SGI story
- Consistency
- Backwards-compatibility is a huge issue, especially for commercial OSs.
- 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.