RE: [Ykernel-misc] Some belated info

[Ishwar Joshi]

thanks for the info mj! i think this is great.

on other front: i tried to mess with the bochs and redhat image etc.
however the whole thing is *too* slow becoz it emulates a pc on my
laptop.

so i guess i am back to hacking on my desktop. am aiming to now put a
latest redhat linux install on my desktop and then compile the linux
0.0.1 source we found earlier.

anybody else had any luck with anything at all?

-----Original Message-----
From: address@hidden
[mailto:address@hidden On Behalf Of
michael scott johnson
Sent: Thursday, June 20, 2002 10:28 PM
To: Misc
Subject: [Ykernel-misc] Some belated info


        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.



_______________________________________________
Ykernel-misc mailing list address@hidden
http://mail.freesoftware.fsf.org/mailman/listinfo/ykernel-misc