Project Three

CS 160 - Project One
Heap-based Priority Queue
for Minix Processes

Drake University
Spring, 2006

Due date: 2/22

Outline of the project objectives

The purpose of this project is to experiment with the Minix 3 "ready queue" for process scheduling, and (in part) to replace it with a different ready queue based on a different data structure. The ready queue as it exists in Minix 3 is in reality a sequence of FIFO queues that together implement a priority queue. We will be (partially) replacing this with a different priority queue, one based on a "heap." This is a data structure that you perhaps recall from CS 66, although I will reintroduce it in class. There is also a link at our website concerning heaps. You will also design, implement and test a dynamic priority scheme for this heap in order to avoid "starvation."

Submission, grading, caution, curtousy, etcetera

Submit a series of tree diagrams, representing heaps, for Part 1. Submit all course code changes you made for whatever portion of the programming part of this project you were able to complete.

On a ten point scale, Part 1 is worth 2 points, Parts 2-4 are worth 6 points, and part 5 is worth 2 points.

I will supply you with a DOS-formatted diskette containing the two C source code files needed for this project: heap.c and children.c. However, if you are working in Sheppard, you won't need this, since these files can be found in /usr/mqr. If you are working at home with a simulator (VMWare, Bochs, etcetera), then as a consequence of doing HW #1, you should already be in good shape using the physical floppy disk drive. However, I have sometimes experienced trouble getting these simulators to consistantly work with this. (For example, VMWare seems to sometimes like to reset the dos.vmx file back to its original state by setting floppy0.present="FALSE".) To transfer the files from the diskettes to your Minix 3 environment, use the following copmmands:

          dosdir 
          dosread -a /dev/fd0 HEAP.C > heap.c 
          dosread -a /dev/fd0 CHILDREN.C > children.c

Let's make certain you get the two source files into your Minix 3 environment as soon as you receive the diskette from me (almost). Also, keep your eyes on the posted messages in case I need to announce any further technical help.

Be sure to make backup copies of all Minix kernel source files that you will alter, before you alter them. Be sure to restore the system files to their original versions before you quit using Minix. If you are working in Sheppard, be sure to remove all evidence that you were there! That is, please don't leave your altered code there!

Details about the assignment

As an opening exercise, you should transfer this source code to your Minix 3 environment, unless you are working in Sheppard Lab, where you will already be able to find it as /usr/mqr/heap.c. Inspect the details of this code, which is listed in the appendix of this document. Compile it by means of the command
```
        cc heap.c -o heap
```
and execute it by means of
```
 
        ./heap 
```
Run a few experiments to get a feel for it. For the test code that appears in main(), show by means of tree diagrams how the heap grows, is transformed, and ultimately shrinks, during the execution of this program. Note that the data is actually held in arrays, but that conceptually, the heap is a tree. The number of nodes in the tree is heapsize at any given time. Only the data in the arrays from index 0 to heapsize - 1 is considered to be part of the heap at any given time. We will discuss all this in class.
The objective now is to get ready to incorporate the above priority queue into Minix, and to use it to partially replace the FIFO queues, at least for "true user processes." Basically, we will regard that rp points to a "true user processes" whenever istrueuserp(rp) is true (see below), although this is actually a little arbitrary, since all I know is that processes whose p_nr value is below 18 tend to be system processes, and those above tend to be honest user processes. The actual incorporation of the heap into the process selection strategy won't actually occur until Section 4. The next couple sections are preparation for that event.

Start by altering the the code in /usr/src/kernel/proc.h. All you need to do here is to make two preprocessor macro definitions, istrueuserp(p) and istrueusern(n), that simply mimic the existing preprocessor macro definitions, isuserp(p) and isusern(n), except that these should check to see if a process's number is at least 18, rather than at least 0. (Many system processes are actually "user processes" in the weak sense that their numbers are positive. We don't want to affect how these processes are queued up. We will let them and the system tasks, whose numbers are negative, continue to use the FIFO queues as usual. This is because we are afraid of them!! They are too crucial to the basic operation of Minix 3.)

Next, you need to get the above heap code (I will assume that you put this in a file heap.c) copied to the directory /usr/src/kernel. From this directory (go there) you need to get the heap code copied into the file proc.c. First use cp to copy proc.c to proc.c.old, so that we don't lose the original version. Then give the command
```
cat heap.c proc.c.old > proc.c
```
to accomplish the objective. This will put the heap code at the top of the file proc.c. You will need to move all of the heap code to the position just following the include statements that are part of the original proc.c. If necessary, remember that you can (and should!) check the man page for the editor you are using, to find out how to move a block of text and other useful things (like searching for strings and jumping to lines by means of line numbers). Remember that elle is similar to emacs, and here you would use control-6 to mark the start of a block of text, then move the cursor to the bottom of the block, then use control-k to cut and control-y to paste. Similarly elvis behaves pretty much like vi.

After moving the heap code in proc.c, change it slightly by commenting out or un-commenting out constants definitions, in order to make

USING_IN_MINIX_KERNEL, HEAPSIZE_DEFINED_LOCALLY, PTR_TO_PROC_MODE and DEBUG_INSIDE_MINIX defined,

but

INCLUDE_TEST_CODE, DEBUG_OUTSIDE_MINIX and TRY_TO_BE_FAIR_WHEN_EQUAL_PRIORITIES undefined.

PTR_TO_PROC_MODE requires an explanation. The heap code was originally intended to work with integer values for identifiers (IDs). However, the Minix FIFO queues hold pointers to processes instead. So I arranged for pointers to processes to serve as the "IDs" in the heap code. It is therefore confusing when you see id in the heap code, because it really means a pointer to a proc. So in that code, don't take id literally. From now on its a pointer to a proc structure.

Before integrating the heap code into the Minix 3 code, notice how the debugging inside Minix works here. It will print little packets of info when something is added to or removed from the heap. Inside parentheses, the first character indicates the particular heap operation being performed (+,^,-). This is followed by a pair of integers, namely the resulting heapsize and the number (p_nr) of the process being added to or removed from the heap. Inspect the code to see where these diagnostic messages occur, and see what each of the three symbols +,^,- signifies in the diagnostic messages.

After you make the changes, rebuild the Minix kernel, and let it reboot Minix to make sure that nothing that you did so far had any noticable impact on Minix. If you have trouble, go back to HW #1 and the posted messages. Learn to use the "safe" (unaltered) version of the kernel by telling the boot monitor image=/boot/safe followed by boot, as discussed carefully in my posted messages. Remember too that image=/boot/image will let you use the altered (rebuild) version of the kernel.
The next step is to try to get the heap working along side the regular Minix user process FIFO queue. At this stage, we won't actually change the way Minix operates, but will add and remove processes to and from the heap at the appropriate moments. This is in order to prepare for later when you will actually let the heap take the place of the FIFO queue. For now though, let processes continue to be added and deleted from the FIFO queues as usual. The heap will just mimic this behavior for now.

You will now need to add code to the functions enqueue, dequeue and pick_proc. Study these functions and understand each one in (nearly) complete detail, before altering them. Basically, insert rp (with the appropriate priority) into the heap at the same moment that it is added to the user's ready queue. It is important that you only get involved with "true user processes," as determined by the preprocessor macros you added to proc.h. Remember that we never want to alter the way in which Minix 3 handles the system processes. (Well, later, if you feel bold, you can play with those too.) Notice that at this stage, any code you add should be carefully designed so as not to impact the working behavior of Minix. Later you will stop putting "true user processes" into the FIFO queues, and instead will only put them into the heap. Here are some details concerning what needs to be done at the present stage.

Use insertIntoHeap() inside enqueue(). Use deleteFromHeap() inside dequeue(). Use whoIsOnTopOfHeap() inside pick_proc(), because the Minix way of doing things leaves the process that it selects for execution in the ready queue. Again, you should understand the existing code, and more or less let the usage of the FIFO queues guide what you do with the heap. You should implement the following:
- In pick_proc(), if the heap is nonempty, then determine which process is on the top of the heap, without actually doing anything with this information for now. Let pick_proc() continue to function as normal apart from this simple task involving the heap.
- In enqueue(), if rp points to a "true user process," then insert rp into the heap, using its priority. Study the code to figure out how to do this. Now, regardless of the nature of rp, continue to use the existing code to insert rp into a FIFO queue as usual.
- In dequeue(), if rp points to a "true user process," then delete rp from the heap (don't worry that it might not be there). You might want to do this in a loop in case rp was added multiple times to the heap, although I don't think this can happen. Now, continue to go on to delete rp from the FIFO queues as usual regardless of whether or not it is a "true user process," at least for the time being.
Once you've done all this, you should check that it compiles using
```
 
         cc -c proc.c -o proc.o 
```
and then again rebuild the kernel and reboot Minix. If all goes well, when Minix comes up, you'll see the diagnostic information concerning the heap being displayed all over the place, but you will still be able to log in. Inspect the diagnostic messages and figure them out (see above). Then halt and reboot using the safe (unaltered) kernel.
Now for the touchy part. The time has come to disable the usage of the FIFO queues for "true user processes" and let the heap take the place of these. You need to go back into proc.c and alter your changes as follows:
- In pick_proc(), arrange for the FIFO queues to be checked as usual to see if there is a ready process here. However, do not include IDLE in this check. Remember that IDLE is in its own FIFO queue, which is the one with the highest index in the array of FIFO queues, so don't check that FIFO queue at this point (tiny change to code here). If a process is found in this way, proceed as usual to select such a process.
  
  Otherwise, check the heap next. If it is nonempty, then select the process at the top of the heap, and mimic the original code for the FIFO lists. Don't remove anything from the heap at this point. Later on, you will. Now, if the heap is also empty, then the IDLE process is the only ready processes, so arrange for it to be used.
- In enqueue(), if rp points to a "true user process," then continue to insert rp into the heap, using its priority, but now don't put it also into a FIFO queue. When rp does not point to a "true user process," proceed as usual.
- In dequeue(), if rp points to a "true user process," then do not bother trying to delete it from the FIFO lists anymore, though you should of course still delete (all copies of) it from the heap.
Now, rebuild the kernel again, cross your fingers and reboot Minix using the altered kernel. If all goes well, you've finished the sensitive work, so congradulations. Using the unaltered (safe) kernel, you should now go back into proc.c and comment out the DEBUG_INSIDE_MINIX contant, and rebuild the kernel again and boot it. The diagnostic messages will have disappeared, though you will still be using the heap as part of the scheduling strategy.
Now we'll really put the heap to work and in the process (no pun ...) discover a weakness in our approach to scheduling. You will need THIS file, which is source code (listed below too) for a user program that will create lots of child processes, in fact too many for the original Minix 3 configuration. So one of your first duties here is to enlarge the Minix process table and related data structures. All you need to do is to go to /usr/src/include/minix and edit the file sys_config.h so that _NR_PROCS is defined to be (say) 256. That will be plenty big. Do a rebuild now, but just to be on the safe side (since Minix make facility is a little flakey), I recommend that while you are still inside .../minix that you give the command make clean followed by make all. If that goes well, then do a rebuild.

We will want child processes to be assigned random priorities when they are created. I will have you set their maximum priority equal to their priority. This is because, Minix 3 has a strategy for increasing process priorities to some maximum level, to prevent starvation. I want to disable this strategy. Here is what you need to do to implement the random assignments of priorities to child processes: Go to /usr/src/kernel/system. Then edit the file do_fork.c and at the bottom of the do_fork, function, just before the return, insert the following code:
```
          if (istrueuserp(rpc)) { 
              rpc -> p_max_priority = 1 + rand()%99;  /* between 1 and 99 */ 
              rpc -> p_priority = rpc -> p_max_priority; 
          } 
```
Once again, I recommend doing a make clean and a make all before doing a rebuild.

The last step in altering the Minix code to prepare for our experiment is to go back to the pick_proc function in proc.c and add the following to the code you wrote. Arrange that when and only when the heap is used to set rp (selected process), that the following executes as well:
```
 
          kprintf("(%d %d) ", rp->p_nr, rp->p_priority); 
          for (q=0; q<1000000; q++); 
```
This way, whenever the heap is used to select the next process to run, we'll see which process it is (its "nr" number, not its "pid"), and we'll also see its priority. The second line is here to slow things down a bit so that the information doesn't shoot past you too fast. Depending on your computer/simulator, you will probably need to adjust "1000000" to a number that gives comfortable results in your environment. Again, rebuild. This time you should see a stream of little ordered pairs, indicating processes and their priorities. Still, you should go ahead and log in as usual, although the login prompt will be followed by tons of these ordered pairs. Once you log in, go ahead and halt and set the boot monitor to boot the unaltered (safe) kernel, so you can get around without all those pairs getting in your way.

Now, compile the user program source code by means of the command
```
 
          cc children.c -o children
```
If you next try to run it using
```
 
          ./children 
```
you'll be told that there is not enough room in the process table. That's because you are using the original kernel. You need to halt again and boot up the altered kernel, the one with enough process table space and the one that displays all those ordered pairs. Try running children now. After a couple seconds of displaying pairs, there will be a pause (corresponding to the sleep(10); statement in children.c). After the delay, all of the child processes should have been created, and they will all want to execute their code (which is a useless for-loop). Watch as they vie for the system's attention! They get placed in the heap and eventually each process gets to execute to completion. Nevertheless, there is essentially starvation taking place here, because the processes with very low priorities must wait for the processes with higher priorities to finish (terminate) first before they are given an opportunity to execute. That's not fair!! Your job now is to go back and alter things so as to maintain a reasonable priority system, but to adjust it dynamically so as to avoid starvation. A rule here is that you must keep a process's maximum priority equal to its priority at all times. This will prevent existing Minix 3 code from automatically changing priorities. That's your job now!

Appendix - C Source Code

Here is the heap.c code:

 
       /*
           The following code implements a priority queue as a heap. 
           Each node of the heap has an identifier (id) as well as 
           a priority. insertIntoHeap() is used to add a node to 
           the heap. extractFromHeap() is used to extract the node 
           with the highest priority from the heap and return
           its identifier. whoIsOnTopOfHeap() simply returns the 
           identifier of this node, without affecting the heap. 
           deleteFromHeap() is used to remove an arbitrary node 
           from the heap. (See further comments for each individual 
           function.) The variable "heapsize" is the number 
           of nodes in the heap at any given moment. getPriority() 
           can be used to check the priority of a node, and
           setPriority() can be used to change the priority, 
           which will cause the heap to be reconfigured. Also, a 
           "wait counter" has been added to each node. This counts 
           the number of nodes that have been removed from the queue 
           since the given node was inserted. The function 
           getWaitCounter() can be used to obtain this value. The 
           function bumpAllPriorities() can be used to change all 
           priorities by a certain amount. These four utility functions
           (or a subset of them) can be used to implement a dynamic 
           priority policy to avoid starvation. 
       */


  /* Should below main() function (which is just test code) be included? */

             #define INCLUDE_TEST_CODE


  /* Should heapsize be defined here (or is it defined elsewhere)? */

             #define HEAPSIZE_DEFINED_LOCALLY


  /* Are we compiling as part of the Minix kernel? */
/*        
             #define USING_IN_MINIX
*/         
  /* If so, should node identifiers really be pointers to proc structures? */
  /* In this case, "id" is misleading since it suggests an integer */ 
/*        
             #define PTR_TO_PROC_MODE
*/          

   /* Are we debugging in a stand alone environment? */

             #define DEBUG_OUTSIDE_MINIX


   /* Are we debugging as part of the Minix kernel? */
/*
             #define DEBUG_INSIDE_MINIX
*/ 

  /* If more than one process has the highest priority and if the constant
     TRY_TO_BE_FAIR_WHEN_EQUAL_PRIORITIES is defined, then it will "try" 
     to extract the one added first to the heap. 
  */
/*
             #define TRY_TO_BE_FAIR_WHEN_EQUAL_PRIORITIES
*/

   /* How big can the heap get? */ 
             #define MAX_NODES 1000


   /* Now begin generating code for the heap. */ 


             #ifdef INCLUDE_TEST_CODE
                #include < stdio.h >
             #endif

             #ifdef HEAPSIZE_DEFINED_LOCALLY
                    int heapsize = 0;
             #endif

/* 
  Corresponding triples of entries from the following three arrays constitute 
  a single entry ("node") in a priority queue, implemented as a heap.
*/ 
             #ifdef PTR_TO_PROC_MODE
                 struct proc *id_array[MAX_NODES];
             #else
                 int id_array[MAX_NODES];
             #endif
                 int priority_array[MAX_NODES];
                 int wait_counter_array[MAX_NODES];

             #ifdef USING_IN_MINIX

  /* 
    Given pointer to proc structure, returns offset index to it in 
    the proc array. SHould be same as "nr" but I don't trust.  
  */      
             #ifdef PTR_TO_PROC_MODE 
                    int proc_index(p)
                    struct proc *p;
                    {
                      int i;
                      if (p == NIL_PROC) 
                      {
             #ifdef DEBUG_INSIDE_MINIX
                        kprintf("!");
             #endif
                        return -1;
                      }
                      for (i = 0; i < NR_PROCS; i++) 
                        if (p == pproc_addr[NR_TASKS+i]) 
                        {
             #ifdef DEBUG_INSIDE_MINIX
                          /* should never print these */ 
                          if (i != p->p_nr) kprintf("@");
                          if (proc_addr(i) != p) kprintf("&");
             #endif
                          return i;
                        }
             #ifdef DEBUG_INSIDE_MINIX
                      kprintf("?");
             #endif
                      return -1;
                    }    
             #endif  /* PTR_TO_PROC_MODE */ 
             #endif  /* USING_IN_MINIX */ 

             #ifndef USING_IN_MINIX 
             #ifdef  DEBUG_OUTSIDE_MINIX 
                 /* Display heap (for debugging outside Minix) */
                 void showHeap(char c)
                 {
                   int i;
                   printf("%c ",c);
                   for (i=0; i < heapsize; i++) printf("%d ", id_array[i]);
                   printf("\n ");
                   for (i=0; i < heapsize; i++) printf("%d ", priority_array[i]);
                   printf("\n");
                 }
             #endif 
             #endif 

                 /* Switch two nodes in the heap */
                 void swapInHeap(i, j)
                 int i;
                 int j;
                 {
             #ifdef PTR_TO_PROC_MODE
                   struct proc *temp1;
             #else 
                   int temp1;
             #endif
                   int temp2;
                   temp1 = id_array[i];
                   id_array[i] = id_array[j];
                   id_array[j] = temp1;
                   temp2 = priority_array[i];
                   priority_array[i] = priority_array[j];
                   priority_array[j] = temp2;
                   temp2 = wait_counter_array[i];
                   wait_counter_array[i] = wait_counter_array[j];
                   wait_counter_array[j] = temp2;
                 }

                 /* Heapify from the bottom up */
                 void heapifyUp()
                 {
                   int n, parent;
                   n = heapsize - 1;
                   while (n > 0) {
                     parent = (n-1)/2;
                     if (priority_array[parent] >= priority_array[n]) break;
             #ifdef TRY_TO_BE_FAIR_WHEN_EQUAL_PRIORITIES
                     if (parent % 2 == 1 &&
                      priority_array[parent] == priority_array[parent+1]) 
                       swapInHeap(parent,parent+1);
             #endif
                     swapInHeap(n,parent);
             #ifdef TRY_TO_BE_FAIR_WHEN_EQUAL_PRIORITIES
                     if (parent % 2 == 1 && 
                      priority_array[parent] == priority_array[parent+1])
                       swapInHeap(parent,parent+1);
             #endif
                     n = parent;
             #ifdef DEBUG_OUTSIDE_MINIX
                       showHeap('.');
             #endif
                       }
                 }

                 /* Add a node to the heap if room for it. */
                 /* Return -1 if not. */ 
                 int insertIntoHeap(id, priority)
             #ifdef PTR_TO_PROC_MODE
                 struct proc *id;
             #else
                 int id;
             #endif
                 int priority;
                 {
                   if (heapsize >= MAX_NODES) return -1; 
                   id_array[heapsize] = id;
                   priority_array[heapsize] = priority;
                   wait_counter_array[heapsize++] = 0;
                   heapifyUp();
             #ifdef DEBUG_INSIDE_MINIX
                   kprintf("(+ %d %d)", heapsize, proc_index(id)); 
             #endif
             #ifdef DEBUG_OUTSIDE_MINIX
                       showHeap('^');
             #endif
                   return 0; 
                 }

                 /* Recursively heapify downwards from index n */
                 void heapifyDown(n)
                 int n;
                 {
                   int left, right, bigger;
                   bigger = left = 2*n + 1;
                   right = 2*n + 2;
                   if (left >= heapsize) return;
                    else if (right < heapsize &&
                     priority_array[left] < priority_array[right])
                      bigger = right;
                   if (priority_array[n] < priority_array[bigger]) {
                     swapInHeap(n,bigger);
             #ifdef TRY_TO_BE_FAIR_WHEN_EQUAL_PRIORITIES
                     if (bigger == right &&
                      priority_array[left] == priority_array[right])
                       swapInHeap(left,right);
                     if (n % 2 == 1 && priority_array[n] == priority_array[n+1]) 
                       swapInHeap(n,n+1);
             #endif
             #ifdef DEBUG_OUTSIDE_MINIX
                   showHeap('.');
             #endif
                   heapifyDown(bigger);
                   }
             #ifdef DEBUG_OUTSIDE_MINIX
                   showHeap('V');
             #endif
                 }

                 /* 
                   Return id of node at top of heap (highest priority) 
                   or -1 or NIL_PROC if empty.
                 */
             #ifdef PTR_TO_PROC_MODE
                 struct proc *whoIsOnTopOfHeap()
                 {
                   if (heapsize > 0) return id_array[0]; else return NIL_PROC;
                 }
             #else 
                 int whoIsOnTopOfHeap()
                 {
                   if (heapsize > 0) return id_array[0]; else return -1;
                 }
             #endif

       /* 
          Extract the top node of the heap (highest priority) and return
          the id for this node. Also, increment all counters. If heap is
          empty, return -1 or NIL_PROC.
       */
             #ifdef PTR_TO_PROC_MODE
                 struct proc *extractFromTopOfHeap() 
             #else
                 int extractFromTopOfHeap() 
             #endif
                 {
                   int i;
             #ifdef PTR_TO_PROC_MODE
                   if (heapsize == 0) return NIL_PROC;
             #else
                   if (heapsize == 0) return -1;
             #endif
                   for (i=0; i < heapsize; i++) wait_counter_array[i]++;
                   swapInHeap(0,--heapsize);
                   heapifyDown(0);
             #ifdef DEBUG_INSIDE_MINIX
                   kprintf("(^ %d %d)", heapsize, proc_index([id_array[heapsize])); 
             #endif
                   return id_array[heapsize];
                 }

   /* Delete specified node and reheapify. Return -1 if not found. */
                 int deleteFromHeap(id)
             #ifdef PTR_TO_PROC_MODE
                 struct proc *id; 
             #else 
                 int id;
             #endif
                 {
                   int i, hold_heapsize;
                   for (i=0; i < heapsize; i++) 
                     if (id == id_array[i]) break;
                   if (i == heapsize) return -1;
                   if (i == 0) {
                     swapInHeap(0,--heapsize);
                     heapifyDown(0);
                   } else {
                     swapInHeap(i,--heapsize);
                     hold_heapsize = heapsize;
                     for (heapsize = 2; heapsize <= hold_heapsize; heapsize++)
                       heapifyUp();
                     heapsize = hold_heapsize;
                   }
             #ifdef DEBUG_INSIDE_MINIX
                   kprintf("(- %d %d)", heapsize, proc_index(id)); 
             #endif
                   return 0;
                 }

                 /* Return size of heap */
                 int getHeapsize()
                 {
                   return heapsize;
                 }

		/* rebuild whole heap from arrays */
                void rebuildHeap() 
                {
                   int hold_heapsize; 
                   hold_heapsize = heapsize;
                   for (heapsize = 2; heapsize <= hold_heapsize; heapsize++) 
                   {
                     heapifyUp();
             #ifdef DEBUG_OUTSIDE_MINIX
                     showHeap('^');
             #endif
                   }
                   heapsize = hold_heapsize;
                }

  /* Find wait count for node with given id. Return -1 if not found. */
                 int getWaitCount(id)
             #ifdef PTR_TO_PROC_MODE
                 struct proc *id;
             #else
                 int id;
             #endif
                 {
                   int i;
                   for (i=0; i < heapsize; i++) 
                     if (id == id_array[i]) return wait_counter_array[i];
                   return -1;
                 }

   /* Find priority of node with given id. Return -1 if not found. */
                 int getPriority(id)
             #ifdef PTR_TO_PROC_MODE
                 struct proc *id;
             #else
                 int id;
             #endif
                 {
                   int i;
                   for (i=0; i < heapsize; i++) 
                     if (id == id_array[i]) return priority_array[i];
                   return -1;
                 }

    /* Set the priority of a node. Return 0 if successful, else -1. */
                 int setPriority(id, priority)
             #ifdef PTR_TO_PROC_MODE
                 struct proc *id;
             #else 
                 int id;
             #endif
                 int priority;
                 {
                   int i, hold_heapsize;
                   i = 0;
                   while (i < heapsize)
                   {
                     if (id == id_array[i]) {
                       priority_array[i] = priority;
                       rebuildHeap(); 
                       return 0; 
                     }
                     i++;
                   }
                   return -1;
                 }

             /* Increase priorities of all nodes by some amount */
             void bumpAllPriorities(amount)
             int amount;
             {
               int i;
               for (i=0; i < heapsize; i++) priority_array[i] += amount;
             }

             void promoteIdleNodes(delay, amount)
             int delay, amount; 
             {
                int i; 
                for (i=0; i < heapsize; i++) 
                  if (wait_counter_array[i] >= delay) 
                  {
                     priority_array[i] += amount;                      
                  } else { 
                     wait_counter_array[i]++; 
                  }                     
             }

             #ifndef USING_IN_MINIX 
             #ifdef  INCLUDE_TEST_CODE
                 void main()
                 {

                   insertIntoHeap(1,13);
                   insertIntoHeap(2,22);
                   insertIntoHeap(3,45);
                   insertIntoHeap(4,81);
                   insertIntoHeap(5,13);
                   insertIntoHeap(6,22);
                   insertIntoHeap(7,13);
                   insertIntoHeap(8,45);
                   insertIntoHeap(9,81);
/*
                   insertIntoHeap(1,81);
                   insertIntoHeap(2,45);
                   insertIntoHeap(3,13);
                   insertIntoHeap(4,22);
                   insertIntoHeap(5,13);
                   insertIntoHeap(6,81);
                   insertIntoHeap(7,45);
                   insertIntoHeap(8,22);
                   insertIntoHeap(9,13);
*/
             #ifdef DEBUG_OUTSIDE_MINIX
                   showHeap('*');
             #endif
                   setPriority(4,13);
                   setPriority(10,10);
             #ifdef DEBUG_OUTSIDE_MINIX
                   showHeap('*');
             #endif
                   printf("%d\n", extractFromTopOfHeap());
                   printf("%d\n", extractFromTopOfHeap());
                   printf("%d\n", extractFromTopOfHeap());
                   printf("%d\n", extractFromTopOfHeap());
             #ifdef DEBUG_OUTSIDE_MINIX
                   printf("Wait count for %d is %d.\n", 7, getWaitCount(7));
                   printf("Wait count for %d is %d.\n", 10, getWaitCount(10));
             #endif
                   printf("%d\n", extractFromTopOfHeap());
                   printf("%d\n", extractFromTopOfHeap());
                   printf("%d\n", extractFromTopOfHeap());
                   printf("%d\n", extractFromTopOfHeap());
                   printf("%d\n", extractFromTopOfHeap());
                   printf("%d\n", extractFromTopOfHeap());
                   printf("\n");
                 }
             #endif   /* INCLUDE_TEST_CODE */ 
             #endif   /* USING_IN_MINIX */

Here is the children.c code:

 
    /* 
      Create lots of child processes and keep them busy.
    */

    #include 

    #define NUM_CHILDREN 50
    #define NUM_DELAY_LOOPS 50000000

    void main()
    {
       int i, j, pid, status;
       for(i=0; i < NUM_CHILDREN; i++)
         if ((pid = fork()) == 0) break;
       if (pid != 0) { 
         /* original process code */ 
         for(i=0; i < NUM_CHILDREN; i++)
           waitpid(-1, & status, 0);
         printf("Children are all done. Bye.\n"); 
       } else {
         /* child process code */ 
         /* wait for everyone to be born before fighting for CPU */ 
         sleep(10);
         /* now try to get CPU and waste clock cycles doing nothing! */ 
         for (i=0; i < NUM_DELAY_LOOPS; i++) ;
       }
    }

CS 160 - Project One Heap-based Priority Queue for Minix Processes