Using the Operating System - Revision history

Rhooper: /* Term Paper */

2007-09-18T02:24:01Z

Term Paper

← Older revision		Revision as of 02:24, 18 September 2007
Line 76:		Line 76:
	For the Term Paper... You don't have to do a pure literature review. You could		For the Term Paper... You don't have to do a pure literature review. You could
	do an original operating system extension. There's one caveat: You've got		do an original operating system extension. There's one caveat: You've got
	to get what you're going to do with ~~the professor first~~. You have to ~~tell~~		to get what you're going to do with Professor Somayaji. You have to get permission
	~~him~~ a week before the outline is due Oct ~~22nd~~.		a week before the outline is due (The paper outline is due Oct 29).

	What types of things is he thinking of: Say you wanted to implement a new		What types of things is he thinking of: Say you wanted to implement a new

Rhooper at 01:21, 18 September 2007

2007-09-18T01:21:46Z

← Older revision		Revision as of 01:21, 18 September 2007
Line 1:		Line 1:
	These notes ~~are~~ have not yet been reviewed for correctness.		These notes have not yet been reviewed for correctness.

	== Lecture 3: Using the Operating System ==		== Lecture 3: Using the Operating System ==

Rhooper: /* Lab 1 */

2007-09-18T01:02:48Z

Lab 1

← Older revision		Revision as of 01:02, 18 September 2007
Line 30:		Line 30:
	All functioning lab machines are running Debian Linux 4.0 (etch).		All functioning lab machines are running Debian Linux 4.0 (etch).
	They should be connected to the internet. They should have a browser on them		They should be connected to the internet. They should have a browser on them
	called [~~IceWeasel~~ http://en.wikipedia.org/wiki/Naming_conflict_between_Debian_and_Mozilla].		called [http://en.wikipedia.org/wiki/Naming_conflict_between_Debian_and_Mozilla IceWeasel].
	Its really Mozilla Firefox. Because Mozilla has trademarked the name Firefox,		Its really Mozilla Firefox. Because Mozilla has trademarked the name Firefox,
	in order to use their name, you have to use exactly their binary distribution. Debian could		in order to use their name, you have to use exactly their binary distribution. Debian could

Rhooper: /* Processes and Threads */

2007-09-18T00:59:45Z

Processes and Threads

← Older revision		Revision as of 00:59, 18 September 2007
Line 184:		Line 184:
	somehow it doesn't seem to happen.		somehow it doesn't seem to happen.

	===== Processes and Threads =====		==== Processes and Threads ====

	There's lots of other devices, but from an OS level, there are two other big ones:		There's lots of other devices, but from an OS level, there are two other big ones:

Rhooper: /* Files */

2007-09-18T00:59:18Z

Files

← Older revision		Revision as of 00:59, 18 September 2007
Line 174:		Line 174:
	An even more minimal abstraction would be		An even more minimal abstraction would be
	to just treat storage devices as a bunch of fixed size blocks. However, that's getting too low level,		to just treat storage devices as a bunch of fixed size blocks. However, that's getting too low level,
	because now all programs have to worry about where they put files.		because now all programs have to worry about where they put files.

	Because the files abstract model is reasonably good, its stuck around for decades.		Because the files abstract model is reasonably good, its stuck around for decades.
Line 361:		Line 361:
	with this - which happens to be most applications. You'll learn this because		with this - which happens to be most applications. You'll learn this because
	the OS guys did this first.		the OS guys did this first.


	==== Graphics ====		==== Graphics ====

Rhooper at 00:45, 18 September 2007

2007-09-18T00:45:39Z

← Older revision		Revision as of 00:45, 18 September 2007
Line 1:		Line 1:
	These notes are ~~still in the process of being posted~~.		These notes are have not yet been reviewed for correctness.

	== Lecture 3: Using the Operating System ==		== Lecture 3: Using the Operating System ==

Rhooper at 00:42, 18 September 2007

2007-09-18T00:42:27Z

← Older revision		Revision as of 00:42, 18 September 2007
Line 255:		Line 255:
	starts running, then it creates a copy of itself with fork, then another, etc.		starts running, then it creates a copy of itself with fork, then another, etc.

	~~TODO~~: ~~diagram~~		[[Image:Comp3000-process-tree.png]]

	In this diagram, What is the value of ''x?'' on the bottom-left-most branch?		In this diagram, What is the value of ''x?'' on the bottom-left-most branch?

Rhooper at 00:16, 18 September 2007

2007-09-18T00:16:53Z

New page

These notes are still in the process of being posted.

== Lecture 3: Using the Operating System ==

=== Administrative ===

==== Course Notes ====
The course webpage has been changed to point to this wiki. Notes for lectures will continue to be posted here.

We still need volunteers to take notes and put them up. Don't forget the up to 3% bonus for doing so.

==== Lab 1 ====

Lab 1 will be up soon. Starting tomorrow, there are labs. Please show up.

If you're clever, you can probably find most of the answers online. Avoid looking up the answers
though, because you'll learn much more than the just answers if you explore
while using the computer.

You'll do better on the tests if you do the labs.

The point of this course is to build up a conceptual model of
how computers work. This conceptual model is not made up of answers, its made up
of connections. You'll start to make these connections by doing the labs.

The Lab will posted as a PDF. You can print it out to bring with it with you.
When you go to hand in the lab, print off your answers on a separate piece of paper.
Answers will be due in two weeks.

All functioning lab machines are running Debian Linux 4.0 (etch).
They should be connected to the internet. They should have a browser on them
called [IceWeasel http://en.wikipedia.org/wiki/Naming_conflict_between_Debian_and_Mozilla].
Its really Mozilla Firefox. Because Mozilla has trademarked the name Firefox,
in order to use their name, you have to use exactly their binary distribution. Debian could
have had a waiver, but because Debian is about freedom, Debian didn't want
the users of Debian to be bound by the terms of the Firefox agreement.

One thing you'll notice while studying operating systems is that there's a lot
of culture. This is because users get used to a particular way of doing things.
For example, lots of us are probably used to Windows and how it works. If
you changed the fundamentals of how Windows worked, many of us would be unhappy.

Some of the things we'll be studying are based on decisions made long ago, often
arbitrarily of for a technical reason was true at the time.
Even if it was wrong the, or is now wrong, we're often stuck with it.

We're going to look at some of the baggage in the operating systems as we progress in this course.

For the lab, we'll be given a set of questions in 2 parts.

Part A we should be able to finish during the hour, give or take a few minutes.
If it takes you 3-4 hours, you're probably doing something wrong.

Part B will take longer. Will need more research, and a bit more reading. You
should be working together. If you have trouble finding a buddy, talk to Dr.
S. Talk to each other to learn. The purpose isn't just about the right
answers, but more so about the operating systems.

We're going to look at:

- Processes, and how Unix deals with them.
- How are the parts of the system divided up.
- Dynamic libraries, where they are, where they fit in memory.
- What are the dependencies.
- How does the graphical subsystem fit in there. X-Windows, the classical
Unix graphical environment.
- Practice on the command line. (If you're wondering where these fit in
in modern graphical environments, read Neal Stephenson's essay)

Try to finish part A in the lab.
Answers due in class 2 weeks from today.

==== Term Paper ====

For the Term Paper... You don't have to do a pure literature review. You could
do an original operating system extension. There's one caveat: You've got
to get what you're going to do with the professor first. You have to tell
him a week before the outline is due Oct 22nd.

What types of things is he thinking of: Say you wanted to implement a new
file-system? This is inherently more work, because you still have to give a
nice write-up. The report should still cite other work.

All of us should have started the process by next week, even if its just
googling for 15 minutes. Just google and see what results come up. IF you
start now, you'll have time to pick a topic that you like, instead of the
first thing that comes along. Its better to work on something you like,
instead of stuck reading papers you're not interested in.

If you want to find good OS papers:
* USENIX association has a number of systems oriented conferences.
** OSDI
** USENIX Annual Technical Conference
** LISA

=== Using the Operating System ===

Chapter 2 looks at the programming model of an operating system.
The operating system provides certain abstractions to help programmers work with it.

What are some examples of abstractions?

==== Files ====

A file is a metaphor. What was the original metaphor? The manilla
coloured folder that we put paper in. Its interesting to note that a file is used
to hold many pages or documents, but that a computer file is a single document. Instead, a directory
holds many files, which are each generally one document.
The metaphor hasn't made much sense for a long time, but it is still in use.

What is a file?

A file is a bytestream you can read and write from.

We also have an abstraction called a byte, 256 possible values, 0-255.
We as computer scientists think we can represent just about anything
with these.

; file : named bytestream(s).

In modern operating systems there are potentially more than
one bytestream in a file. When there is more than one bytestream, we
call this a forked file.

An early operating system that used forked files was OS 9.
On a traditional system, you get a sequence of bytes
when you open a file. In a forked file, when you read it, you get some data,
but there is also other data hanging around. We'll talk about that later.

The standard API calls for a file are:

* open
* read
* write
* close
* seek

As well as a other operations that one might need to perform on files, such as:
* truncate
* append - (seek to end of file and write)
* execute

Why open and close? Why can't we just operate on a filename?
Because it (usually) takes a long time to go through the filesystem to find the files.
Open and close are optimizations -- the abstraction is a stateful interface.
You start by using open to obtain some sort of "handle" representing the file,
and pass this "handle" value to read and write. When you're done, closing the
file frees the resources allocated when opening the file. On most systems
you can only have a specific number of files open at any given time.

There are some filesystems where open and close don't do much of anything,
such as some networked filesystems.

File represent storage, on disks... They're random access. If they're random access
like RAM, why don't we access disks like we access RAM?
Why couldn't we just allocate objects as we need them? We could indeed do this, but
it turns out that there's a reason that we don't generally do this.

The file interface is a procedural interface.

One nice things about files is they're a minimal functionality interface. The concept of
minimal functionality is a recurring theme you'll find when we discuss filesystems.

The abstraction used to interface the filesystem
shouldn't prohibit you from creating particular forms of applications. If we chose
to use an object model, we'd be implying you don't want to give arbitrary access to the
data on disk, as objects tend to encapsulate their data.

The abstraction listed above is the minimal abstraction for efficiently
managing persistent storage (disks).

This doesn't necessarily mean this is the most absolutely minimal abstraction.
An even more minimal abstraction would be
to just treat storage devices as a bunch of fixed size blocks. However, that's getting too low level,
because now all programs have to worry about where they put files.

Because the files abstract model is reasonably good, its stuck around for decades.

Fundamentally, though, its a legacy. Some models of filesystems try to get
away from it. Look at the PalmOS - it resisted having files for a long time, but eventually
gave in to support removable media, but the primary OS and API still don't support files.
Microsoft's been wanting to get away from the legacy files abstraction too, but
somehow it doesn't seem to happen.

===== Processes and Threads =====

There's lots of other devices, but from an OS level, there are two other big ones:
CPU and RAM. These two are generally abstracted with processes.
The process is the basic abstraction in operating systems for these two,
but is not the only abstraction. There are also threads.

CPU + RAM are abstracted as:
* processes
* threads

A process may have multiple threads. A thread shares memory with its processes.

* A process is an exclusive allocation of CPU and RAM.
* A thread is a non-exclusive allocation of RAM within a process,
but is an exclusive allocation of CPU.
* One or more threads constitute a process.

Another way to talk about processes is in terms of address spaces and
execution context:
* An address space is just a virtual version of RAM. It may
be instantiated in physical memory, it may not be. Its a set of addresses you
can call your own.
* Execution context is CPU state (Registers, processor status
words, etc.). There's lots of state surrounding the processor when its running
a program. This state can be saved, and then restored later to resume execution
at a later time.

* A thread is one execution context matched with an address space.
* A process is one or more execution contexts plus an address space.
* A single-threaded process has one execution context, and one address space.
* A multithreaded process has multiple execution contexts, and one address space.

The concept of multiple address spaces is somewhat new in modern computing.
However, if you go back to the old days of MS-DOS, there was only one address space, the
physical address space. We used to have things like TSRs, a 640kb limit,
etc. There was no virtualization of memory. In order to run at the same
time, they had to co-exist in the physical memory address space.

If you don't have multiple address spaces, you don't have processes and threads.
At best, you have threads, sharing the one address space you have.

Historically, threads were abstracted differently than now: These are
capitalized here to differentiate them from the newer terms: FORK, JOIN, QUIT.

Why FORK? Think of a fork in the road. You're going along, then things split.
A FORK is supposed to represent that split.

By FORKing, the main thing to note is that you're creating two execution
contexts, that may be sharing memory. The execution may start at the same
place, but may be diverging. How do you stop creating more and more and more
of these, to bring them back under control or stop them? That's the JOIN
operation. Each thread tracks how many threads are running, if you JOIN and
you're not the last one running, you just go away, otherwise you need to
synchronize back into the main thread.

What's QUIT? QUIT stops the the whole program -- all execution. It will cut
all threads off, even if the thread is one of the branches and not the main
thread.

This was one of the earliest ways to abstract multiple execution context.

What if, when you did the fork, you made a copy of the entire process? There
are now two separate instances of the program, with the same state? The
difference here, is if you quit one, the other will stay around -- but the
difference is more profound: they're not sharing the same address space (nor
execution context). This is the Unix model of processes.

In the Unix process model the system starts with only one process: init. It
starts running, then it creates a copy of itself with fork, then another, etc.

TODO: diagram

In this diagram, What is the value of ''x?'' on the bottom-left-most branch?
''x'' is 5 in the Unix process model. However, if this was multithreaded,
''x'' could be 7 or 5, depending on how fast the threads are running. It might
be 5 if the thread asking for the value of ''x'' runs before the thread setting ''x''
to 7. This is known as a race condition,
because we don't know which thread will run or finish first.

In Unix, they decided to make it easy and have different processes. These
processes can't change the state of their parents or children.
To share a value, you have to set the value before forking. (Or through other means)

There's a small glitch with what we've said so far about Unix processes: That
they have exactly the same state when you fork. If this was true, they'd
always do the same thing. How do they know that they're different?

Turns out that Unix fork is very simple, yet it helps with this.
The idiom you'll usually see is:

pid = fork();

fork takes no arguments.

When you fork, the result of fork is the pid (process ID) of the new process,
or 0 if you're the child.

The tree of processes effectively becomes a family tree. (However, with some
bizarre genealogy that we'll see later)

What you usually do is check the value of pid, and if its 0, do one thing,
otherwise do something else. If pid is nonzero, it is the pid of the child
process we just created by forking. You usually use this to track your child.
The classic use of fork is to create disposable children that do a specific
task for a short while, then go away.

The nice thing about this model is that it keeps things separate. You don't
need to worry about what the child is doing. If you want to communicate, you
have to explicitly set up to do this. There are some standard ways of doing
that communication. We'll look at these later too.

So now we know how to make new processes? How do we do something different? In
principle we don't need anything else. We could open a file, read new code,
then jump to the new code. However, we have the idea of exec().
Exec replaces the running program with the specified program, but preserves
the pid.

In Unix, to start a new program you usually fork() then you exec() the desired
program on the child. If you don't fork() first, then exec() will kill the
original process, replacing it with the program you called exec on.

Exec causes the kernel to throw away the old address space, and give a new
address space, with the new binary. The pid stays the same though.

The Windows equivalent is CreateProcess()

CreateProcess() takes lots of arguments about how to create the new
process (what to load, permissions, etc). Fork takes none. With fork(),
you can set things up yourself, and most of the settings will carry over to
the new program. (Including open files). Note how different these two are.

In Unix, you have the building blocks to do things, and you have to put them
together yourself. In Windows, you have the single API call to do them all at
once. Neither is strictly right or wrong.

On older systems, when a big process was forked, everything was copied. On
newer systems, fork doesn't necessarily copy everything. With virtual memory
you can share much of the memory between two processes.

In older APIs there was vfork() - suspend parent, fork, exec, then let the
parent and child both start to go again. This idea avoided the copying when
the first thing you were going to do was exec.

The basic idea to make this efficient is that the descriptions of the virtual
memory address spaces don't have to be mutually exclusive. You could have
10 programs sharing portions of their address space -- such as the read-only
portions like the program code, but not the read-write portions.

What if you didn't want to do an exec after forking? A classic one is a
daemon. One listening on the network for an incoming connection. When that
incoming request comes in, the main program can deal with the request, but it
would also have to keep checking for more requests at the same time. Instead,
in Unix the typically idiom is to fork off a child to process that connection,
and then go back and wait for more.

You can have shared memory. But the default model for processes is
that nothing is shared, but the threading model is everything is shared.
For threads you have to implement protections, but for processes, you have to
opt-in to share.

Processes win out on reliability: fewer chances for errors. You control
exactly what state is shared.

Another thing we'll talk about later regarding threads versus processes is
how does this play on multiple cores? This depends on the implementation,
and sometimes is a little tricky.

Chapter two is talking about the model presented to the programmer. An API
for your processes and threads to talk to the world.

This course is fundamentally about how these things are implemented. Its
useful to know about these tricks, so that you know how the computer is used.
It turns out the same tricks are useful in lots of other circumstances. Such
as concurrency - when you have to deal with an application that has to deal
with this - which happens to be most applications. You'll learn this because
the OS guys did this first.

==== Graphics ====

This part of the lecture should help you with the lab. Its about graphics.

We've talked about some standard abstractions so far: files, processes, threads.

However, the thing you really interact with is the keyboard, mouse, and
display. In the standard Unix model, these are not a part of the operating
system. They're implemented in an application.

The Unix philosophy is that if you don't have to put it in the kernel,
don't put it there, or if you do, make it interchangeable.

The standard way to do graphics in Unix is X-Windows, or X for short.
Before X there was the W system. There was a Y system at one point,
as well as Sun NeWs.

There was also a system called Display Postscript. Postscript is a
fully fledged programming language. Originally used for printers.
It was developed for laser printers, by a little company called Adobe.
When laser printers came out, they had really high resolutions. It was
hard to get the data necessary to print a page to the printer fast
enough... So postscript programs were sent to the printer. In the
early days of the MacIntosh, the processor in the printer was more powerful
than the processor in the computer. Postscript is a funny little language.
Its a post-fix operator language. Instead of saying things like "4+5" you
say "4 5 +" -- you push them onto the stack, then run an operator on them.
The same with function calls.

In the 80s, there were many competing technologies for how to do graphics
in the Unix world. X won. But Display Postscript also kind of won,
because Macs use Display PDF in a system called Quartz, which was
created as a successor to Display Postscript. Because Postscript was linear,
it was hard to parallelize. PDF is easier to parallelize.

NeXT was the one that used Display Postscript first... NeXT was founded by
Steve Jobs. OS X is Unix with Display PDF... And you can run X-Windows on top
of that.

X-Windows lets you open windows on remote computers. The way you create a
window on your local computer is the same way that you open a window on a
remote computer, 1000s of miles away. X is based on something called the X
Window Protocol. It just happens to work locally as well (with some
optimization like shared memory), but the messages were designed to work well
over ethernet.

This was created by folks that wanted to talk to hundreds of computers, such
as the supercomputer in another room... but they wanted to see the windows
on their own computer.

Consider what you have to do to see a remote window in Windows. You fire up
Remote Desktop Client, and you get the whole desktop remotely. If you want to
do 10 computers, you end up with 10 windows with 10 desktops and 10 start
buttons. This difference is a result of X-Windows being designed for networks
and Windows being designed for one computer.

The terminology for X-Windows is a bit backwards from what we're used to: The
server is what we mostly think of of as a client. The server is what controls
access to the display: it runs where your display is to control your display,
mouse, keyboard... And to display a window, remotely or locally, you run a
program known as a client in X-Windows which connects over the network to
display a window on your X-Windows server.

A funny thing about X is it took the abstraction to an extreme. The people who
created X-Windows didn't know anything about usability or graphics or art. The
original X-Windows tools were created by regular programmers. Technically
underneath its very nice.. But they knew they didn't know, so they made it so
the user could decide what it should look like themselves. So that you can
just switch out a few programs and things keep on working.

This means that when you do things like moving your mouse to a window -- what
happens? Do you take focus or not? This is something known as click to focus.
In older X Systems, you could just point your mouse there, and focus followed.
This is potentially very efficient, but also very confusing if you're not used
to it... Or how do you handle key sequences, or minimize? Who decides how to
do this all? They had the idea of something called a Window Manager. This goes
back to X Servers providing the technical minimums so that you're not limited
to one behaviour. The Window Manager is just another X client, with some
special privileges so it can run anywhere. It could run 1000s of miles away.

This is why on Linux there's Gnome, KDE, etc. There's Motif, GTK, QT, IceWM,
Aferstep, Blackbox, Sawfish, fvwm, twm. Etc. Other graphical toolkits too,
abstracted away. These choices are all available there because the X-Windows
people left it very open by not making the choice for us. This does make
things a little confusing at times, though, because each application could
have different assumptions.