[Ykernel-misc] Some belated info

[michael scott johnson]

        All right -- I'm finally getting around to writing a little bit
about my experience with writing a simple kernel during winter
quarter, as requested.  As I
said, this was done on relatively simple, emulated hardware, so I don't know
much about low-level particulars of the x86 architecture.  But I'll try to 
cover here some paradigms that I found helpful for thinking about kernels
and their organization.

        I am very sorry for the long delay.  I'm finally done with classes,
so I have relatively little to do for the next three months and should now
be able to devote a significant portion of my time to this project.

        I think the best way to think of a kernel is as a resource management
system.  Every program that is run needs resources -- CPU time, memory, and
access to hardware being the most obvious.  The kernel's job is to allocate
resources for each of the various processes running on the machine.  To
facilitate this, the kernel uses a data structure known as a Process Control
Block, or PCB.  Each process running on the computer has a PCB associated with 
it.
Different kernels can store different kinds and amounts of information in the
PCB, but most of the time the PCB will at least include some sort of process 
id, memory management information, and information about the CPU state 
for the process.

        To a large extent, the kernel's job of allocating resources is 
handled by manipulating queues of PCBs.  For instant, there is usually a 
queue of processes which are waiting for CPU time, referred to as the "Ready
Queue".  There's also usually a queue associated with each hardware device.  
Let's suppose we have a situation where Process W is currently running on the
CPU, and Process X, Y, and Z trying to use hardrive C.  The kernel will issue
a command to C on X's behalf and place Y and Z on the queue associated with C.
Once X's command has executed, X will be taken off the hard drive queue and
placed on the Ready Queue, and the kernel will now issue a command to the 
hard-drive on Y's behalf.  Meanwhile, once the kernel has determined that W
has ran long enough, the kernel will place W at the end of the Ready Queue and
let X run for a certain amount of time.  
 
        Before going into the specifics of managing certain resources, I think
a quick word about how user processes communicate with the kernel is
appropriate.  Most modern CPUs have at least two modes, which I'm going to
refer to user mode and kernel mode.  While running in kernel mode, the CPU can
access all of the memory, hardware, etc. on the machine.  While running in CPU
mode, restrictions are enforced -- some memory is not visible, the code is
often NOT allowed to access hardware directory, etc.  This is basically to
help the OS developers enforce a certain level of protection -- obviously 
we don't want to give any old user program the ability to overwrite OS code in
memory, erase crucial files on disk, etc.  When the machine first boots, it
will be running in kernel mode.  The kernel will be booted and go through some
initilization steps, then usually start a process -- under Unix this process is
init.  Once the code for this process is running, user mode is entered.

        The obvious question is -- how does kernel code get executed once the
CPU has started executing user code?  The answer is TRAPS, also known as 
INTERRUPTS. Essentially, a kernel is an event-driven piece of software.  When
the system first boots, it runs through some initialization steps and starts
a user process, and from then on the only time the kernel code executes is when
something important happens.  A trap is simply the kernel-level version of an 
event.  When the kernel first boots, it sets up a table in memory
consisting of pointers to different kernel routines.  When a trap occurs, the
CPU will stop whatever it's doing, save it's state, and look in this table
to handle whatever event has just happened.  It will then go execute the
kernel code indicated in the table.  Traps are used for all sorts of things.
Hardware will usually send a certain trap number to the CPU in order to signal
completion of a given operation. The CPU will issue a trap when certain
kinds of errors occur -- a bad operand for instance.  And user code issues
a trap in order to request services of the kernel -- accessing a hardware
device, for instance.  Traps are also issued by the system clock, so that
the kernel can periodically switch which task is running on the CPU.

        To summarize: a kernel is an event-driven piece of software responsible
for allocating resources to user programs.  When an event (aka a trap) occurs, 
the CPU saves its state, enters kernel mode, and begins executing a function
which was previously designated to handle that event.  The kernel then gives
control back to a user process.

        Now that I've given an overview of the kernel's operation, I think it
might be go into a little more detail regarding some specific subsystems.



MEMORY
__________
        Obviously, each process running on the computer requires memory.
Once upon a time, there really wasn't anything difficult about memory 
management.
Programmers knew exactly what the machine they were writing programs for looked 
like internally.  The location of data and code was hardcoded into the program.
Code was loaded into the same memory location each time.
        Eventually things got complicated, however.  Once you have more than one
process running on a system, you can no longer simply store the physical address
of each piece of data or code in the system's memory.  A piece of software might
be loaded into different physical locations at different times, depending on
what other programs are running on the computer at the time.
        A very popular solution to this problem is known as "virtual memory".
Essentially, the OS tricks each user process into thinking it is running in 
nice, neat,
uniform memory each time.  The user process accesses memory in what is known as
a "virtual address space".  This address space is generally very large, on the 
order of
many gigabytes.  But this virtual address space is completely separate from the 
actual,
physical location of memory.  Internally, the physical memory is divided up 
into a 
number of pages, usually 4k or 8k in size.  Then, each virtual page is mapped 
onto
an actual, physical page of memory by the kernel.  This mapping is essentially 
just 
stored as a big table in memory. A special piece of hardware, the Memory 
Management
Unit (MMU), is responsible for translating addresses in the virtual address 
space to
addresses in the physical address space using this table.
        This scheme gives us the best of both worlds.  User processes can use 
simple
addressing schemes that remain uniform each time they are run.  Each user 
process
"thinks" that it is living in a big, standard address space which it has all to 
itself.
And the kernel is free to physically put each program wherever it can find the 
space.
        The x86 architecture also uses something called "segmentation".  This 
adds
another level of translation to the scheme.  I'm not very familiar with this 
scheme, so
I won't discuss it here.  Information on it is given in the x86 system 
programming
manuals.  Any information from anyone who has a good understanding of 
segmentation
would be appreciated.

CPU TIME
__________
        In principle, managing CPU time is pretty simple -- at least for single
processor systems.  CPU time is divided up into time slices.  Periodically a 
trap
is issued by the system clock signalling the end of a time slice.  The kernel 
then
saves the state of the process running right now and puts it on the end 
of the ready queue.  It then pops a process of the front of the ready queue and 
starts
running it.
        Of course, question of what exactly counts as a process' "state" might 
be
complicated.  On the simplified system I worked with "context switching" 
(switching
from one process to another) wasn't very difficult, but that doesn't mean it'll 
be
easy on the x86.  Intel's provisions for multitasking are covered in the 
systems 
programming manuals.  Also, a kernel can gain a lot of performance by 
implementing
more sophisticated scheduling algorithms in order to decide who gets CPU time.


HARDWARE DEVICES
-----------------
        Obviously this is a pretty big category.  As I said, user processes 
generally aren't given direct access to hardware.  Rather, the user process
requests services from the kernel, which in turn talks to the hardware on 
behalf of
the user process.  Not only does this make the user's life easier, it also 
protects
the system somewhat from buggy or malicious code.  Unfortunately, there are as 
many
different ways of talking to hardware as there are hardware devices.  Some 
hardware
devices need to "polled" -- they need to be read occasionally to determine their
status and get any useful information from them.  For instance, if a disk drive 
had
to be polled the kernel would give it a command and then check periodically to 
see
if it had completed the command yet.  In general, though, polling wastes CPU 
time, so
more often trap-driven access is used.  The kernel issues a command to a device,
and when the device finishes it issues a trap to let the kernel know that it has
finished.  Its then up to the kernel to give the appropriate information to
the requesting user process and issue another command to the hardware device.
        Personally, I think this will be one of the hardest things we will have 
to deal
with.  The specifics of the x86 architecture are complicated, but at least 
they're 
pretty well documented in publicly available Intel docs.  Information on how to 
talk
directly to the various available hard drive devices might be harder to find, 
since
it is generally only of interest to OS programmers.




I think that's about all I have to say for now.  I hope it was at least a little
helpful.  I realize that a lot of this is probably old hat, and the rest of it 
is
probably too obtusely written.  I'm realizing that I've never really had to 
write
about technical ideas before, and it's pretty damn difficult.  But hopefully 
this
will at least inspire a little dialog.  If anybody has any questions, feel free
to email the list with them.  I'll try to respond quickly.  I don't know a lot 
beyond
the basics, but hopefully we can help each other find the relevant information.

By the way, the Intel Architecture Software Developers Manual is available 
through
the following link:

http://www.intel.com/design/pentiumiii/manuals/

I expect we'll be using it a lot.  Especially volume III, which covers a lot
of the low level aspects of the architeture such as memory management schemes, 
etc.

--M.J.