| Introduction to Minix |
click here |
Due: 1/25 |
| Chapter One |
Chapter One exercises 1, 2, 3, 5, 7, 8,
13, 14, 17, 21, 25, and the following exercise:
What happens when the code
for (i=0; i<3; i++) fork(); is execute?
How many processes will be created? |
Due: 1/30 |
| Minix Part of Chapter Two
|
Ch. 2: 34, 35, 36, 37, 38,
44 (last one involves changing Minix, and I'm altering it a bit - see
message below) |
Due: 2/8 |
| Early Part of Chapter Two
|
Ch. 2: 10, 13, 14, 15, 16,
plus...
- Figure out how to make the following solutions work for three
processes instead of two processes:
- Peterson's solution
- Semaphore solution (I added this!)
- What big advantage do the sleep-and-wakeup and the semaphore
solutions have over the prior "solutions?"
|
Due: 3/6
|
| Middle Part of Chapter Two
|
Ch. 2: 21, 22, 27, 28, 30
|
Due: 3/13
|
- The first two HW assignment have been posted.
- If you opt to install Minix at home and want to do your HW #1 and
maybe future projects there, then a couple issues arise, for which I
offer suggestions below:
- If you are unable to regularly use the Minix Computer in the Sheppard Lab (Howard Hall computer lab)
and also unable (or unwilling) to install Minix 3 on your computer, then I have another solution.
You can download and install the "Bochs simulator" and get Minix 2 running on that.
No need to repartition your disk, nor do anything dangerous. Simply go to
this site to learn how to download and install
Bochs and Minix. Then click on the minix.brxc
inside the C:\Program Files\Bochs 2.1.1\minix204 folder, in order to launch Minix.
Unfortunately, you will only be able to use Minix 2, not Minix 3.
The good news is that the code is not very different, and I will let you work on
either a Minix 2 or a Minix 3 version of the programming projects (and HW #1).
I will supply further details on using this simulator approach soon. For now,
just get started.
- Here is something else I just learned, and which will make it possible for you to work with a
single Minix partition on your hard-drive (or virtual hard-drive if you are using the Bochs simulator).
After logging into Minix 3, do the following:
cd /boot
mkdir safe
cp image/* safe
halt
After halting Minix 3, you are back at the boot monitor. Give the
command
image=/boot/safe
Then give the command
set
which will show you the values of certain parameters that the boot monitor uses. You should
here see image=/boot/safe . Now give the command
boot
to reboot Minix 3. But it is now booting the kernel stored in
/boot/safe.
We will never change this kernel and should always be able to boot it .
Now halt again, and do the following in the boot monitor:
image=/boot/image
set
boot
Now we're booting the original kernel, the one stored in /boot/image .
This is the one you will rebuild and likely corrupt from time to time. Anytime
you cannot boot it, just boot the "safe" one instead.
Actually, I just realized that if you're using Minix 2 instead of Minix 3 (probably
because you're using the Bochs simulator), then you need to do things a bit differently.
When you are logged into Minix, give the commands
cd /
mkdir safe
cp minix/* safe
halt
Then at the boot monitor, you should either use
image=/minix
or
image=/safe
depending on whether you want to boot the usual kernel (the one you will
alter and probably corrupt) or the safe kernel (the one that should never change).
Here is another thing, if you are working with Minix 2 instead of Minix 3. You'll need
my rebuild script. Download it (see above posting) and then put it on an
MS-DOS formatted disk. If you are using the Bochs simulator, alter the minix.bxrc
file to make the real (not virtual) floppy work. I'll hand out how it should look in
class. Put the floppy in the drive BEFORE starting the simulator. After logging into Minix,
give the command
dosdir /dev/fd0
which should show you the contents of the floppy, including
REBUILD
Now give the following commands in Minix:
cd /usr/bin
dosread -a /dev/fd0 REBUILD > rebuild
chmod 744 rebuild
This should cause rebuild to be copied into /usr/bin and be
nearly ready for usage. You need to edit the file a bit though. Using the editor
you like (elle, elvis or mined), change rebuild by replacing the line
rm /boot/image/*
with the line
rm /minix/*
Also, delete the line
make clean
Also, replace the line
mv /boot/image/* /boot/image/3.1.0
with the line
mv /minix/* /minix/2.0.4
Now you can cd /usr/src/kernel and work on Part 6
of HW #1. However, you must make a change to proc.c that is different than
the change described in the original assignment, because that was written for Minix 3 and
you are using Minix 2. You should instead alter proc.c by adding something
near the top of the definition code for the function interrupt. Just after the
statement
register struct proc *rp;
insert the statement
putk('.');
Note that when you use rebuild in Part 6 of HW #1, this might take a while due to the
simulator. .
- Another thought. After changing proc.c in HW #1 (and
similarly in future projects), but before doing rebuild, it is
a good idea to quickly test what you've done by giving the command
cc -c proc.c -o proc.o
to make sure that proc.c will still compile. Ignore warning
message though.
- On the last Monday of each month, I will not begin my office hours
until 4:30, due to a department meeting.
- The command grep is particularly useful for trying to
explore the Minix source code to find where things are defined and used.
For example, if you go into /usr/src/kernel and give the
command
grep 'struct proc' *.h | more
this will show you every place in a header file (in
/usr/src/kernel)
that struct proc occurs. Likewise
grep 'enqueue(' *.c | more
will show you every place in a .c file (in
/usr/src/kernel)
that enqueue( occurs.
- After looking over the Chapter One HW again, it all looks
reasonable to me. So please take a stab at all the problems.
Well, actually, skip Problem 25. By the way, remember from CS 130 that a
CPU can either run in a protected mode or unprotected mode. Protected
mode is often called "user mode," while unprotected mode is ofter called
"kernel mode," because an operating system kernel needs this power.
- Ignore the following message until we fine
tune the procedure.....
If you are using Bochs, then we can probably help you get Minix 3
running in it, although some computers seem to have trouble with the
following procedure (due to Michael). Proceed as follows:
- Execute bximage.exe in the Bochs folder. Use it to
create a 500 MB harddrive disk image. Name it minix3.img.
- Download the minix3.bxrc (see above link) file and put
it in the Bochs directory.
- Put your Minix 3 CD in the CD drive.
- Double click on the minix3.bxrc icon. This should
cause the simulator to boot Minix from the CD.
- Once it does, log in and give the command setup.
When prompted to type "yes", do so, and otherwise, hit return
for defaults. Before long, you should be installing Minix 3
from your CD into your virtual harddrive (minix3.img).
(It will take a while.)
- Afterwards, terminate execution of the Bochs simulator.
- Then change minix3.bxrc so that it causes
it to boot from the harddrive ("disk") rather than the CD.
- Double click on it to start up Bochs with Minix 3.
- OK. Those who have opted to use VMWare instead of Bochs seem happy.
Here are easy directions for using Minix3 in this simulator. (Thanks
Alan.)
- Go to this site
- Follow link to VMWare site. Download and install VMWare.
- Go back and grab the Minix 3 image file at the original site,
and install it.
- Copy the four files from this zipped file to the same folder
holding the VMWare stuff (probably C:\Program Files\VMWare\VMWare
Player).
- Edit the dos.vms file in order to set
floppy0.present = "TRUE" (instead of "FALSE").
- Launch VMWare by double clicking on the vmplayer.exe
icon.
- When prompted for configuration file, select dos.vms.
- Select "create" and click "OK."
- You should be able to take it from here. If not, let me know.
Now that I see how simple this is, I will plan on writing the two
Minix projects for Minix 3 only (not Minix 2). That should be easier
on all of us. Before Project One, get comfortable in the Minix 3
environment, either in a simulator or not. Understand what you did in HW
#1 so as to avoid relatively "small issues" later. Just play around
until you are comfortable.
No Silver Bullet. After playing more with VMWare, I see that it too has
issues. But there are workarounds. Here goes:
- It is fairly easy to cream this system. Therefore,
keep a backup folder of all the VMWare and Minix stuff. Copy and
paste all of it later if you blow things up.
- After halting Minix, you sometimes cannot use the boot monitor
and also
lose control of the mouse. At this point you have no recourse
except CTRL-ALT-DEL to use the Task Manager to clobber the VMWare
simulator. I think we'll be able to find a way to prevent this
from happening. Stay tuned.
- However, while starting up VMWare, you can press down on the
escape key to get to the boot monitor, and you will be able to
use it. So try "set" and "image = /boot/safe" and "image = /boot/image"
as discussed in an earlier message (after copying the contents of
/boot/image to /boot/safe). This way, if you build a bad kernel in
/boot/image, you'll still be able to use the good one in
/boot/safe.
I recant the first bullet to a large extent.
Maybe VMWare is a silver bullet. If you are careful, you won't blow it
up. Also it is much faster than Bochs, I think. To avoid trouble, when
you are finished using Minix in VMWare, use the command "halt" to get to
the boot monitor. Here give the command "off" to cleanly "power down"
the virtual machine.
- I altered rebuild a bit (posted). Remember that you should
use this file to rebuild the kernel, unless you prefer to give the
commands individually. It is posted (above) and there are directions
(above) as to how to set it up. You no longer need fix_other as
is clear from an earlier message (above).
- I've decided to hand out my handwritten lecture notes as we go
along. I'll hand out the first batch tonight.
- Cancel Chapter Two exercise 50 (page 220), unless you really
want to do it. Concerning Chapter Two exercise 44 (page 219), you can
either do the problem as originally stated, or do something easier (I
feel), namely, instead of implementing the F4 key behavior, just
do the following. Each time a message as passed between processes,
increment the counter (as already indicated), but then check to see it
the counter is now divisible by 10000. If so then use kprintf
(works like printf but avoids involvement with file system, so
kernel can use it even before file system is set up) in order to display
a triple of numbers: the ("nr") number of the source of the message, the
number of the destination, and the value of the counter. Here are some
hints and suggestions based on my experience implementing this:
- Inside proc.h :
- Using the arrays proc and pproc_addr as
models (sort of), include a big enough two-dimentional array of integers
to serve as the message counters.
- Using the preprocessor definition for proc_addr
(and similar definitions), write a preprocessor definition for
get_message_count(m,n) that treats m and n as offset indices
into your array (offset by NR_TASKS). I urge you to remember
the equivalence of the two lines of code on page 164, and to use
something analogous to the second approach.
- Similarly make a preprocessor definition for
inc_message_count(m,n) that would be used to increment one of
the counters.
- Inside main.c, initialize your array of counters so
that it is filled with zeros.
- Inside proc.c, notice that the mini_send
function is used to send messages between processes. Notice also that
the first parameter is a pointer to the process table entry of the
processes that is sending the message (message source). You can obtain
the number of this process via caller_ptr->p_nr and store this
in a local variable, say src. Notice too that the second
parameter dst is just the number of the intended destination.
Thus inc_message_count(src,dst) would increment the correct
counter. The use get_message_count(src,dst) to get the value of
the counter. Remember that you should only print this value (along with
the values of src and dst) only when the value
of the counter is a multiple of 10000. Otherwise, you'll end up
displaying way too many times. When you have it working notice that
there are a lot of messages sent during system initialization and during
halting.
Important: Whenever working on a Minix assignment that changes
the kernel, don't try to do too much too fast. Make small changes and
the rebuild the kernel. Also, I remind you that if you make a change to
say main.c, you might want to make sure there are no syntax
errors introduced before rebuilding the whole kernel. All you need to do
is
cc -c main.c -o main.o
to discover whether or not main.c compiles. If so, then you
can go on to use rebuild.
- Project One will soon be handed out. It presumes a familiarity with
Minix 3, at least in so far as the topics in HW #1 are concerned. You
should be certain that you are able to tranfer files via diskettes
(floppies), DOS-formatted or Minix-formatted.
- Project One is posted, although it might undergo a little tweaking before I pass it out
officially on Wednesday.
- Update on Ch. 2 homework assignment:
- 34 - several issues may occur to you, but focus especially on
interrupts
- 35 - skip this!
- 36 - consider the ready queue structure. For now you don't need
to know about its detail, but realize that it is comprised of several
FIFO queues, each of which is a linked list. Details on this next time.
- 37 - skip this! You won't understand until next time.
- 38 - could be an issue, except that tasks and servers were
designs to keep starvation of other processes from happening. Hint: see
last paragraph on page 166.
- 44 - I simplified. See earlier message.
- 50 - skip this!
- Minor fixes have been made to the project document (like fixing
"mimick" - ouch!). Also, if you don't have a partner for the projects
and would like one, please let me know before class tomorrow.
- The posted old exams (from 2002 and 2004) might be of help to you.
- Here is the solution to my "fork exercise": After the first
iteration of the loop, there was one call to fork, resulting in one
child process for a total of two processes. The "parent-child tree" for
this
situation would look like so:
O
|
|
O
where each node (circle) represents a processes and a child process is
placed below its parent process. Then BOTH of these processes will go
through the loop two more times. The next time through the loop, each
will have (another) child process. The picture would then be:
O
|\
| \
O O
|
|
O
Finally, all four of these processes execute (on their own!) one final
iteration of the loop. Each will create a child process. The picture
then becomes:
O
/|\
/ | \
O O O
/| |
/ | |
O O O
|
|
O
There are thus eight processes in all. Note: There is no significance to
the way child processes are ordered in my pictures. I just drew them the
way I wanted to.
It is reasonable to expect something similar on the test.
Here are some mathematical observations that you may SAFELY
IGNORE. Suppose the loop continued for an arbitrary number of
iterations. After n iterations the number of processes at level k (i.e.
k steps away from the original process in the tree) would be "n choose
k." Also, the number of processes with exactly m child processes would
be 2 raised to the n-m-1 as long as n > m, but would equal one when n =
m. Question: How many processes would be at level k and have exactly m
child processes? The above tree shows that when n=3, k=2 and m=0, the
answer is 2. OK. I just figured out the answer, but have not proved it.
Here is the answer, based on the evidence: "n-m-1 choose k-1" provided
that k is at least one and that m+k does not exceed n. When k = 0 and m
= n, the answer is one. In all other cases, the answer is zero. This
claim can be proven by induction (I'm confident), but may admit to a
more "obvious" explanation. In any case, CS 160 students need not worry
about any of this.
- Josh Goldberg has been exploring "mtools," a system implemented in
Minix 3 for handling MS-DOS file systems. I had only a little awareness
of the existence of this before the course started. Wish I had found it
earlier, because it is nicer that just using dosdir, dosread,
doswrite. If you get frustrated at the limitations of these three
commands, then check out the posted link (above) that Josh found.
- I have also set a link to the website for the course from two years
ago. Remember that we were using Minix 2 at that time, and are now using
Minix 3, so some things will be different there.
- I will try to remember to announce this in class. Please remind me.
There will be an interesting mathematics talk concerning "capillary surfaces" on Wednesday. Here are the details:
Title: Capillary surfaces and their behaviors in cylinders
Speaker: Dr. Kirk Lancaster, Professor of Mathematics, Wichita State University
Date and time: Wednesday, February 22, 3:30 pm Location: Howard Hall 308
Following the talk, Prof. Lancaster will be available to talk with students who are thinking about graduate school.
Abstract: Capillary surfaces are ubiquitous: a drop on your windshield, the sap in a tree, the fuel in a spaceship, fluid in a cylinder, etc.
Capillary phenomena occur as the result of an interaction of surface tension, exterior force fields (e.g. gravity) and the attraction of fluids
to surfaces (i.e. "wetting energies"). In a microgravity environment such as in free fall or at very small scales such as occurs in nanoscale
fabrication, the influence of gravity becomes largely insignificant and the interaction of surface tension and surface chemistry becomes
dominant in determining the shapes of stationary liquids.
Special types of capillary surfaces can be of great interest; some examples are hanging drops ("pendant drops"), drops on a surface ("sessile
drops"), liquid bridges, fluids in a vertical cylinder and fluids in a container. When the container is not smooth (e.g. has edges or
corners), determining the behavior or shape of a capillary surface in the container can be problematic. I will consider capillary surfaces in
a vertical cylinder whose cross-section has a corner P. In this case, the capillary surface will be a graph z=f(x,y) over the cross-section and
the function f may be discontinuous at P; this problem has been investigated by a variety of researchers. When the cross-section has a convex
(or protruding) corner at P, Paul Concus and Robert Finn made a conjecture approximately 14 years ago that under certain conditions, f must be
discontinuous at P. I will describe the behavior of capillary surfaces z=f(x,y) near P when f is discontinuous at P and give a very brief
outline of my recent proof of the Concus-Finn Conjecture. I will also discuss examples.
- New rule: You must have a DIFFERENT partner (if any) for each project.
- An error in the notes I handed out: On page 39, at the bottom. I
screwed up the last step of "heapify down." I was suppose to use the
priority numbers to decide, but used the IDs instead. So the node (5,29)
should be where I put the node (15,4).
- A couple points that arose while helping a team with the project:
- The IDLE process sits alone (always!) in the linked list with
the lowest priority, i.e. highest index.
- Notice the code in dequeue that conditionally calls pick_proc.
When you remove from the heap instead of the linked list, you need to do
the same thing, i.e. conditionally call pick_proc.
- On Project One, the very last part concerning altering the way the
heap scheduling works in order to avoid starvation IS NOT NECESSARY to
get full credit for the project. I will let you do it for a 5 percent
bonus though, if you wish.
- I just posted the early Chapter Two homework we discussed. I also
pushed back the due date. However, I added to one of the problems.
- If you are using one of the simulators, then you should probably
remove the line "make clean" from /usr/bin/rebuild to
substantially speed things up. However, very rarely, this may cause
trouble. It did 2 years ago, but not this year. May not even be an issue
for Minix 3. So just go ahead and remove "make clean".
- Project Two is now posted.
- Game plan:
- Tues., Mar. 7: last chance to submit "early part of Ch. 2" HW.
- Wed., Mar. 8:
- Sleeping Barber Problem (quick)
- More on process scheduling
- Return HW and discuss some of it
- Mon., Mar. 13: Collect last batch of Ch. 2 HW and discuss it.
- Wed., Mar. 15: You know what.
- Here is part of Prof.
Solomon's Lecture Notes very nice lecture notes on Operating
Systems. If you go to this page, and search for the word "serious" you
will encounter the following sentences: "A more serious problem is that
Peterson's solution only works for two processes. Next, we present three
solutions that work for arbitrary numbers of processes." This is
followed by algorithms, one of which is the ``bakery algorithm'' of
Leslie Lamport. You aren't responsible for this code, but you might wish
to take a look.
- I posted the second exam from two years ago in the solutions
section (above), but only part of it is relevant to you right now.