Session 35: Overview
OS principles
layering
binding time
indirection
orthogonality
caching
OS frontiers
OS principles
Throughout this class, we've seen several applications of some
particular principles that apply throughout systems design. We haven't
talked about the explicitly, but they've been there nonetheless. I want
to take a moment to actually address these issues as they've arisen in
this class, coupled with specific examples.
Layering
Large systems become complex. Remember that operating systems can be
millions of lines or even tens of millions of lines long.
They become impossible to conceive of in whole.
For the developers get a handle on the overall system, it must be
structured somehow. One of the most useful structures for large
operating systems is the concept of layering, since
its job is to abstract the raw system from the overall system.
Layers also enable pieces to be more interchangeable, because the
dependencies between modules becomes lessened. You know, looking at a
particular module, that a module that's three layers away has almost
nothing to do with it.
Examples:
- network stack: We saw that TCP/IP itself (a
small fraction of the entire operating system, though nonetheless
large) is structured into layers, each having its own independent
protocol definition:
the physical layer (frequently
Ethernet), the internetwork layer (IP), the transport layer (TCP), and
the applicaton layer (HTTP, for example). Each layer adds some new
capability to the one below it.
- Minix architecture: Minix is structured into
layers: The process manager, the device drivers, the server processes,
and the user processes. There's a clearly defined hierarchy.
A microkernel architecture enforces some layers, but layers aren't
exclusive to microkernel architectures. Even monolithic kernels use
layering, just to make sense of the system. By convention, one layer
should only call functions in adjacent layers.
Binding time
This is an issue of when you make a decision: Do you commit early on,
probably gaining something in terms of both complexity and efficiency,
or do you delay the decision until the last moment,
gaining in flexibility?
Examples:
- loading programs to memory:
We saw binding time most explicitly when we talked about loading
programs into memory.
- We can commit to the memory addresses when we
compile the program. Though this simplifies the loading process quite a
bit, it means that the program can only be run
when the committed memory address range is available.
- We can commit to
the memory addresses as we load the program into memory. We lose in
efficiency, but the program can be placed anywhere the memory is
available.
- Or we can commit to the memory addresses as the execution
continues, using the concept of a segment registers. This requires some
added complexity in the processor, but it's actually more efficient than
committing at load-time, and it provides the ability to move a program
while it is loaded in memory.
- device drivers:
Minix adopts the simplest of solutions, where device drivers are
compiled into the system. If you have a new sort of device, then you
must recompile the entire kernel, install the new version, and reboot
the system. Other systems defer the binding of device drivers to boot
time (which allows you to avoid recompiling the kernel - which takes
quite a while, and which is anyway impossible on OSes where
the source code is not distributed, like Windows). Or, if they're really
fancy, they allow you to load new device drivers while the OS is
running, saving you from having to reboot the system. (The pain of
rebooting may not sound like much, unless you're running a server
serving lots of people, and 5 minutes of downtime means thousands of
dollars of lost business.)
- putting pixels on the screen:
Primitive graphics programs would commit to pixel locations at compile
time: The program would say to draw a line from at (3,3) to (20,20), and
that was done relative to the screen's top left corner.
Windowing systems give you more flexibility, by delaying the commitment
to be relative to the top left corner of a window. The window can be
moved, and the line moves with it. This provides more power, as well as
reduced conflicts between different processes.
Indirection
This we've seen in a number of contexts. It's been said that there's
no problem in computer systems that can't be solved by adding a new
layer of indirection. Of course, each layer of indirection involves a
loss in efficiency, since it means you have to look into a data
structure to get the real value. But the added flexibility is often
worth it.
Examples:
- virtual page table: The page table gives a layer of
indirection between memory references and their actual memory location.
With each memory reference, we have to look into the table to find out
where it actually is. By doing this, we can provide the illusion of
there being more memory than there actually is.
- interrupt numbers: When you initiate a software
interrupt, you indicate a number. This is used as an index into a table
of addresses, specifying where the interrupt handler is. Having a table
(instead of sending indicating the address directly when you initiate
the interrupt) allows the interrupt handler to be moved around by the
operating system. It also provides additional security protection, since
otherwise a system would be able to jump into any memory address with
unrestricted access.
- TCP port numbers: The TCP designers might have
decided that, whenever you send a message using TCP, you have to
indicate the process ID that should receive the message. However, this
would turn out to be impractical, since if I'm trying to access an HTTP
server at some new location, there's no way I can easily find what its
process ID on that computer is. Instead, they decided to use a port
number, which is basically an index into a table of process IDs that
have each port reserved. When a TCP module receives a segment, it uses
the port number to look into the table to see which process should
actually receive the message.
Orthogonality
Orthogonality is more of a interface design issue than an
enhancement issue. It refers to the fact that, generally, you should try
to separate out issues that really aren't related. By doing so, you
simplify the system while at the same time gaining flexibility.
It's a difficult concept to explain, except by way of example.
Here are a few.
- composite types in languages:
(This is a programming languages example, but it gives you some idea of
what I'm talking about.)
In C++, you can have an array of any type. It's not that they
distinguish an array of integers, from an vector of doubles, from a
string of characters. Indeed, you can even have an array of arrays -
they don't make two-dimensional arrays a separate language issue.
The C++ designers identified ``arrayness'' as a separate concept,
which can be applied to any other type. We would call it
orthogonal - you can imagine types on one axis of a
table, and having arrayness or not as being on another axis.
- threads versus processes:
Threads arise by identifying that processes actually involve two
completely separate concepts: execution sequences and resource
allocation. There's really no reason to understand these as separate,
and so threads come about as a way of talking about an execution
sequence independent of resource allocation. In this way of thinking,
processes become simply sets of resources, and a thread is just another
resource that can be allocated into a process.
- process initiation versus loading programs:
Unix identifies orthogonality between initiating a new process
(with fork()) and loading a program (with execve()).
This isn't an obvious orthogonality - it would make sense to combine the
two. But combining the two concepts would make things more complicated,
as now you'd have to provide for many more contigencies. In Unix, you
can alter things about the process before you load the new program.
Caching
Caching is something you do only for performance
enhancement, but it's such a useful concept that it deserves special
recognition here.
We've really only seen caching in three places during this course.
- virtual memory:
You cache the virtual memory, stored on disk, in memory.
- table lookaside buffer (TLB):
You cache virtual page entries on the CPU, to save on the expense of the
extra indirection layer.
- disk cache:
You cache disk contents in memory, so you don't have to load the same
file from the disk again if it's been accessed quite recently.
OS frontiers
- ``infinite'' address space: As 64-bit processors
come into the world, we get 64 bits of address space, which is,
practically speaking, infinite. This brings up two issues. The first,
simpler, issue is how we can adapt virtual memory to handle 64 bits, as
a page table for a full 64-bit space becomes no longer practical. We've
seen a solution, in the form of a hash table known as a inverse page
table.
The harder question is how to take advantage of it. For example, an
OS might decide to place the entire file system into the 64-bit address
space, so that reading from a file is just as easy as reading from
memory. No longer would you have to use all those painful system calls
to read in information.
- networked systems:
They've been around for a while, but whether we're taking full advantage
of it is still an issue. A truly distributed operating system would
perhaps be installed once but work on many computers, and it would take
advantage of all computers' ability to their maximum. We don't have
something like that yet.
- parallel systems:
Again, they've been around, but you can hope for something better than
what we have, which is really relatively painful to use.
- multimedia:
Delivering multimedia files (especially video) raises issues with
guaranteed delivery rates. With regular OSes, if there's a delay with
the disk, it just means we get the data a little more slowly. But with
multimedia, you need the file to come as a constant stream, and any
delay means reduced effectiveness. This becomes an issue especially for
multiuser systems (like a Web server, perhaps) delivering multimedia
content.
- battery-powered computers:
Mobile computers raise issues in terms of low-demand OSes a bit, but
that's probably just a matter of time. The bigger issue is that their
behavior is more unpredictable: Their battery might go out, or their
connection to the network might go off unexpectedly. Additionally,
wirelesss network communication comes at a higher premium (and at
reduced security, going over the airwaves).
- embedded systems:
This refers to the computer running as a small portion of a larger
device, like a toaster or a car or a railroad switch. This computer
needs an OS, but the requirements are different: Hardware comes at a
premium, since they compete on price more, so the available resources
are reduced. (It's my understanding that many such devices run some
version of Linux, which would make sense since it's freely available
for you to modify as you will.)
These are the issues that seem to be on the near horizon in OS
research. Of course, we can't look more than a few years ahead, and even
then we can't predict the innovations very precisely. But OS is still a
live area, and it's bound to be live as long as computers continue
breaking new ground.