ganesh@utah-cs.UUCP (03/08/87)
------------------------------------------------------------
When this newsgroup was formed, Dr. Tanenbaum listed
one of its purposes as "reporting class-room experiences".
I first heard about Minix in November, and contacted
Andy Tanenbaum for a "pre-release" copy of Minix. I was
fortunate that Dr. Tanenbaum had the time to send it to
me! (Thanks.) I used Minix in a graduate level course
(mostly taken by undergraduates) from January to March.
Here are the projects that the students and I did :
1 : Familiarization with System Calls
2 : Modification of the scheduler, and tracing the activities
of the Process-management layer.
3 : Writing a musical bell driver and the study of the printer driver
4 :(a) Implementation of three new system calls;
(b) Implementation of the "worst-fit" algorithm;
(c) Generation of a readable core dump;
(d) Memory compaction upon failure of "fork"
Most of the programming assignments were 2 weeks long.
They covered one chapter of the book each.
------------------------------------------------------------------
* Programming Assignment - 1 : Familiarization with System Calls *
------------------------------------------------------------------
The project consisted of developing a routine involving
fork, exec, pipe, alarm, sleep, etc. It went alright except
for an unexpected bug: if a child issues a "sleep" system
call and the parent issues an "alarm" system call, the
parent's alarm prematurely rings regardless of the
"sleep" and "alarm" arguments. I'll post the exact code
that caused the problem, soon.
---------------------------------------------------------------
* Programming Assignment - 2 : Modification of the scheduler, *
* and tracing the Process-management layer *
---------------------------------------------------------------
Part (a):
---------
Modifying the scheduler of Minix so that when the
F5 key is hit once, it would cause the scheduler to
assume a CPU bound job preferring mode. When F5 is
hit again, it would prefer I/O bound jobs.
Changes to Minix were made in two places:
(i) the TTY driver to keep a F5flag that was
toggled by the F5 key;
(ii) the "pick_proc" routine.
The project was succesfully completed by many. The
only real problem was the time-delay in rebuilding
the system, and the difficulty in debugging the
scheduler; if the scheduler was buggy (or unfair),
the system would simply hang.
Part (b):
---------
Install F3flag and F4flag in the TTY driver so that:
if F3 and !F4, the "interrupt" routine would
be made verbose; one can "watch" hardware
interrupts this way.
if !F3 and F4, the "sys_call" would be made verbose
thus reporting all "trap" activities.
if F3 and F4, "mini_send" and "mini_receive" would be
made verbose thus allowing all messages to be
traced.
if !F3 and !F4, silence.
--------------------------------------------------------------
* Programming Assignment - 3 : Writing a musical bell driver *
* and the study of the printer driver *
--------------------------------------------------------------
This short one-week programming assignment required the students
to write a modified TTY driver that recognized "ESC 7 n2 n1" and rang
the "bell" of the TTY for duration n2 with frequency n1. The programming
part was optional due to the shortage of time, but was completed
by a few.
---------------------------------------------------
* Programming Assignment - 4 : *
* (a) Implementation of three new system calls; *
* (b) Implementation of the "worst-fit" algorithm;*
* (c) Memory compaction upon failure of "fork" *
---------------------------------------------------
Part (a) implemented three new system calls:
--------------------------------------------
(i) nfork :
-----------
A variant of "fork" in which the parent gets
( child_pid << 5 | child_slot_number )
and the child gets
( parent_pid << 5 | parent_slot_number ).
The parent does a "getpid" before calling "nfork" so
that it knows who it is, and can tell whether it
is in the child or in the parent.
What we are really returning is a pair < pid , slot > ,
encoded in the above way.
The slot number also was returned for use with
nsend and nreceive (see below).
"nfork" was implemented by adding a new system call
with number 38; effectively, slot 38 of "table.c"
taken by "do_nfork" which we derived from "do_fork".
Only two changes were made in deriving "do_nfork" from
"do_fork" :
line 5759 :
change "reply(child_nr, 0, 0, NIL_PTR)"
to "reply(child_nr, ( ((mp->mp_pid)<<5 | who) , 0, NIL_PTR)"
/* value of nfork sent to child */
line 5760 :
change "return(next_pid)"
to "return(next_pid<<5 | child_nr)" /* value sent to parent */
We also need "nfork.s" when compiling C programs using
nfork. This is obtained from "fork.c" as follows:
Copy fork.c to nfork.c
Change "FORK" (system call number) to
"38" (or pick any other empty
slot in the dispatch table
in "table.c")
Compile "nfork.c" to get "nfork.s"
Also recompile "table.c" with entry 38
being "do_nfork".
(ii) nsend :
------------
Exactly like the "send" in the process management
layer, EXCEPT THAT we allowed users to use "nsend"
in their code.
This gives users a new IPC mechanism; effectively a
language like CSP !!
nsend ( process_slot_number, &message ) would send the
message to the process whose slot number was in the
first argument.
(iii) nreceive :
--------------
Similar to "nsend".
Changes made to Minix to implement "nsend" and "nreceive":
(1) Create "nsendrec.s" by copying "sendrec.s"
and just editing "_send" and "_receive" to
"_nsend" and "_nreceive". (If you want to use
the names "send" and "receive" at the user level,
you don't have to do this.)
Link "nsendrec.s" with those C programs using
nsend and nreceive.
(2) In "mini_send" (proc.c of kernel), change line 1951:
Originally, user processes were allowed to make system calls
only via the "sendrec" call that sets BOTH to true;
We bypass this restriction!
The code must read:
if (function != BOTH && caller >= LOW_USER) {
if (function == SEND) {
n = nmini_send(caller, src_dest, m_ptr);
rp->p_reg[RET_REG] = n;
return;
}
else {/* function == RECEIVE */
n = mini_rec(caller, src_dest, m_ptr);
rp->p_reg[RET_REG] = n;
return;
}
}
where nmini_send differs from mini_send in that it
lacks lines 1986, 1987 and 1988 !!
This also bypasses a restriction in Minix that
user processes can only call MM and FS. We want
user processes to be able to call OTHER user
processes.
An example program using these new system calls
is given below. Note: This program is to be
compiled with "nfork.s" and "nsendrec.s".
/* ==================== Two dining philosophers ========== */
/* ========== Written using nfork, nsend and nreceive ==== */
>
> #define TRUE 1
> #define PID_OF(x) ( (x >> 5) )
> #define SLT_OF(x) ( (x & 0x1F) )
>
> #include "../h/const.h" /* take from the /include */
> #include "../h/type.h" /* diskette of Minix */
> #include "../h/com.h"
>
> static message msg; /* will treat it as type 1 message */
> unsigned short Parpid, Parslot;
> unsigned int nfval;
> unsigned short P1slot, P2slot;
>
> /* The main program "parent" creates two philosophers, and
> * two forks, and then arbitrates fork acquisition requests.
> * Essentially, all the philosophers "nsend" to "main";
> * however, the "nreceive" of main matches only with
> * one of the two "nsends" (nondeterministically).
> */
> main ()
> {
> Parpid = getpid(); /* Who am I ? */
> nfval = nfork();
> if ( PID_OF(nfval) == Parpid)
> { /*------------------------ Philosopher 1 ----------------*/
> Parslot = SLT_OF(nfval); /* Parent's slot number */
> while (TRUE) {
> msg.m1_i1 = 1; /* Convey own identity to parent */
> nsend(Parslot, &msg); /* pick up forks 1 and 2 */
> printf("\n P1 is eating \n");
> nsend(Parslot, &msg); /* put down forks 1 and 2 */
> printf("\n P1 is thinking \n");
> }
> }
> P1slot = SLT_OF(nfval); /* Parent finds out where Philosopher 1 is */
>
> nfval = nfork(); /* and then creates the second philosopher */
> if ( PID_OF(nfval) == Parpid)
> { /*------------------------ Philosopher 2 ----------------*/
> Parslot = SLT_OF(nfval); /* Parent's slot number */
> while (TRUE) {
> msg.m1_i1 = 2; /* Convey own identity to parent */
> nsend(Parslot, &msg); /* pick up forks 1 and 2 */
> printf("\n P2 is eating \n");
> nsend(Parslot, &msg); /* put down forks 1 and 2 */
> printf("\n P2 is thinking \n");
> }
> }
> P2slot = SLT_OF(nfval);
> /* Now the parent (arbiter) does the following forever */
> while(TRUE) {
> nreceive(ANY, &msg);
> if (msg.m1_i1 == 1) nreceive(P1slot, &msg);
> if (msg.m1_i1 == 2) nreceive(P2slot, &msg);
> }
> } /* main */
>
> /* If Phil1 and Phil2 have to talk to each other, the
> main program has to tell them both (via messages) where
> their partners are.
> */
>
Part (b)
--------
In Part (b), we changed
"alloc.c" so that instead of following first-fit in allocating
memory (as presently), worst-fit was followed. (Note that
first-fit is better; we did worst-fit just for experience.)
-----------------------------
Part (c) : Memory Compaction:
-----------------------------
Sometimes, the Minix memory can get fragmented. A fork
can fail on line 5711 of "forkexit.c" because of the
lack of a sufficiently big hole. Similarly, exec also
can fail.
The project was to "compact" memory by moving ALL ACTIVE
PROCESSES to the lowest possible memory, thus leaving
one big hole at the top. Thereafter, the "fork" call was
to be re-attempted, hoping that the single big hole would
be big enough to fit the process to be forked or exec'ed.
The project involved changes in "alloc.c" followed by
a "sys_newmap" call for each process that was moved in
the process of compacting.
> Author: Eric Ivancich, Univ. of Utah, Salt Lake City, UT 84112
>
> Author's note: All of the work is done in compact_mem and move_mem. I have
> added an extra level of indirection to alloc_mem in order to test if the
> initial attempt failed.
>
> ADD THE FOLLOWING CODE TO mm/alloc.c TO GET THE EFFECT
> OF COMPACTION:
> #include "mproc.h" /* ADD THIS AFTER THE EXISTING includes */
>
/* THIS IS A NEW ROUTINE */
> /*========================================================================*
> * do_alloc_mem *
> *========================================================================*/
Here, stick in the code of the CURRENT alloc_mem routine.
/* THIS IS A MODIFIED ROUTINE */
> /*========================================================================*
> * alloc_mem *
> *========================================================================*/
> /* This is a new alloc_mem routine tries to allocate memory using
> * do_alloc_mem.
> * If enough memory can't be allocated, it compacts memory and calls
> * do_alloc_mem
> * again!
> */
> PUBLIC phys_clicks alloc_mem(clicks)
> phys_clicks clicks; /* amount of memory requested */
> {
> phys_clicks i;
>
> i = do_alloc_mem (clicks);
> if (i == NO_MEM) { /* Major addition */
> printf ("Compacting Memory\n"); /* debug */
> compact_mem ();
> return (do_alloc_mem (clicks));
> } else
> return (i);
> }
/* THIS IS A NEW ROUTINE */
> /*========================================================================*
> * move_mem *
> *========================================================================*/
> PUBLIC phys_clicks move_mem (mp, click_dist, slot_nr)
> struct mproc *mp;
> phys_clicks click_dist;
> int slot_nr;
> {
> phys_clicks prog_clicks;
> long prog_bytes, old_abs, new_abs;
> int i;
>
> prog_clicks = (phys_clicks) mp->mp_seg[T].mem_len +
> mp->mp_seg[D].mem_len + mp->mp_seg[S].mem_len;
> #ifdef i8088
> prog_clicks += mp->mp_seg[S].mem_vir - mp->mp_seg[D].mem_len;
> /* gap too */
> #endif
>
> prog_bytes = (long) prog_clicks << CLICK_SHIFT;
> old_abs = (long) mp->mp_seg[T].mem_phys << CLICK_SHIFT;
> new_abs = (long) old_abs - (click_dist << CLICK_SHIFT);
>
> i = mem_copy(ABS, 0, old_abs, ABS, 0, new_abs, prog_bytes);
> if (i < 0)
> panic("move_down can't copy", i);
>
> mp->mp_seg[T].mem_phys -= click_dist; /* tell proc it's moved */
> mp->mp_seg[D].mem_phys -= click_dist;
> mp->mp_seg[S].mem_phys -= click_dist;
>
> sys_newmap (slot_nr, mp->mp_seg); /* tell sys it's moved */
> return (prog_clicks);
> }
>
/* THIS IS A NEW ROUTINE */
> /*========================================================================*
> * compact_mem *
> *========================================================================*/
> PUBLIC compact_mem ()
> {
> register struct hole *hp;
> register struct mproc *mp;
> int i, found;
> phys_clicks base_clicks, up_clicks;
>
> hp = hole_head;
> while (hp->h_next != NIL_HOLE) {
> base_clicks = hp->h_base + hp->h_len; /* figure out base */
> for (i = 0; i < NR_PROCS; i++) { /* search for proc */
> found = 0;
> mp = &mproc [i];
> if (!(mp->mp_flags & IN_USE)) /* not in use, skip */
> continue;
> if (mp->mp_seg [T].mem_phys == base_clicks) { /* match? */
> found = 1;
> /* debug/help */ printf ("Moving PTE %d down %d clicks.\n",
> i, hp->h_len); /* print message */
> /* move proc down */
> up_clicks = move_mem (mp, hp->h_len, i);
> /* mod. hole table */
> hp->h_base += up_clicks; /* move hole up */
> merge (hp); /* maybe merge */
>
> break;
> }
> }
> if (!found) /* missing memory! -- stop */
> break;
>
> /* hp = hp->h_next; this shouldn't be needed */
> }
> }
------------------------------------------------------------------------------
Need more info ? e-mail to "ganesh@cs.utah.edu" or
write to: Dept. of Computer Science,
Univ. of Utah, Salt Lake City, UT 84112.
or call : (801) 581-3568
------------------------------------------------------------------------------