Due date: 3/3

Outline of the project objectives

Submitting and grading

Details about the assignment

1. As an opening exercise, you should copy and paste the following code, which maintains a priority queue. Inspect the details of this. Run a few experiments to get a feel for it. You can do this either in Minix or in Linux. For the test code that appears in main below, 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 heap code that follows is also available in a text file     here.
   
   

                /*
                  This 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 afecting 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 the main() function, which is just test code, be included? */
   
            #define INCLUDE_HEAP_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_HEAP_IN_MINIX_KERNEL
       */
   
                /* If so, should node identifiers really be pointers to proc structures? */
       /*
            #define PTR_TO_PROC_TABLE_MODE
       */
   
                /*
                  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
       */
   
                /* Are we dubugging in a stand alone environment? */
       /*
            #define DEBUG_OUTSIDE_OF_MINIX
       */
   
                /* Are we debugging as part of the Minix kernel? */
       /*
            #define DEBUG_HEAP_IN_MINIX
       */
   
   
            #ifdef INCLUDE_HEAP_TEST_CODE
               #include < stdio.h >
            #endif
   
            #define MAX_NODES 100
   
            #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_TABLE_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_HEAP_IN_MINIX_KERNEL
                 /*
                   This next function is not part of the heap stuff really, and is
                   mainly here to test my theory about p_nr in the proc table in Minix.
                 */
                   int proc_pid(p)
                   struct proc *p;
                   {
                     int i;
                     if (p == NIL_PROC)
                     {
            #ifdef DEBUG_HEAP_IN_MINIX
                       putk('!');
            #endif
                       return -1;
                     }
                     for (i = 0; i < NR_PROCS; i++)
                       if (p == pproc_addr[NR_TASKS+i])
                       {
            #ifdef DEBUG_HEAP_IN_MINIX
                         if (i != p->p_nr) putk('@');
                         if (proc_addr(i) != p) putk('&');
            #endif
                         return i;
                       }
            #ifdef DEBUG_HEAP_IN_MINIX
                     putk('?');
            #endif
                     return -1;
                   }
            #endif
   
   
            #ifndef PTR_TO_PROC_TABLE_MODE
                /* Display heap */
                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
   
                /* Switch two nodes in the heap */
                void swapInHeap(i, j)
                int i;
                int j;
                {
            #ifdef PTR_TO_PROC_TABLE_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_OF_MINIX
                      showHeap('.');
            #endif
                      }
                }
   
   
                /* Add a node to the heap */
                void insertIntoHeap(id, priority)
            #ifdef PTR_TO_PROC_TABLE_MODE
                struct proc *id;
            #else
                int id;
            #endif
                int priority;
                {
                  id_array[heapsize] = id;
                  priority_array[heapsize] = priority;
                  wait_counter_array[heapsize++] = 0;
                  heapifyUp();
            #ifdef DEBUG_HEAP_IN_MINIX
                  putk('(');
                  putk('+');
                  putk('0'+heapsize);
                  putk('0'+proc_pid(id));
                  putk(')');
            #endif
            #ifdef DEBUG_OUTSIDE_OF_MINIX
                      showHeap('^');
            #endif
                }
   
   
                /* 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_OF_MINIX
                  showHeap('.');
            #endif
                  heapifyDown(bigger);
                  }
            #ifdef DEBUG_OUTSIDE_OF_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_TABLE_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_TABLE_MODE
                struct proc *extractFromTopOfHeap()
            #else
                int extractFromTopOfHeap()
            #endif
                {
                  int i;
            #ifdef PTR_TO_PROC_TABLE_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_HEAP_IN_MINIX
                  putk('(');
                  putk('^');
                  putk('0'+heapsize);
                  putk('0'+proc_pid(id_array[heapsize]));
                  putk(')');
            #endif
                  return id_array[heapsize];
                }
   
   
                /* Delete specified node and reheapify. Return -1 if not found. */
                int deleteFromHeap(id)
            #ifdef PTR_TO_PROC_TABLE_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_HEAP_IN_MINIX
                  putk('(');
                  putk('-');
                  putk('0'+heapsize);
                  putk('0'+proc_pid(id));
                  putk(')');
            #endif
                  return 0;
                }
   
                /* Return size of heap */
                int getHeapsize()
                {
                  return heapsize;
                }
   
   
                /* Find wait count for node with given id. Return -1 if not found. */
                int getWaitCount(id)
            #ifdef PTR_TO_PROC_TABLE_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_TABLE_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_TABLE_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;
                      hold_heapsize = heapsize;
                      for (heapsize = 2; heapsize <= hold_heapsize; heapsize++) {
                        heapifyUp();
            #ifdef DEBUG_OUTSIDE_OF_MINIX
                        showHeap('^');
            #endif
                      }
                      heapsize = hold_heapsize;
                      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;
            }
   
   
            #ifdef INCLUDE_HEAP_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);
            #ifdef DEBUG_OUTSIDE_OF_MINIX
                  showHeap('*');
            #endif
                  setPriority(4,13);
                  setPriority(10,10);
            #ifdef DEBUG_OUTSIDE_OF_MINIX
                  showHeap('*');
            #endif
                  printf("%d\n", extractFromTopOfHeap());
                  printf("%d\n", extractFromTopOfHeap());
                  printf("%d\n", extractFromTopOfHeap());
                  printf("%d\n", extractFromTopOfHeap());
            #ifdef DEBUG_OUTSIDE_OF_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
   

   
   Be sure to make backup copies of all Minix files that you will alter, before you alter them.
   Be sure to restore these system files to their original versions before you quit using Minix.
   
   
2. The objective now is to get ready to incorporate the above priority queue into Minix, and to use it in place of the FIFO queue for user processes. This replacement will actually be done in Section 4. Start by altering the the code in /usr/src/kernel/proc.h to give each process a new integer value, init_priority (which will be set at the time the process is created). Next look at the code for do_fork() in /usr/src/kernel/system.c, on page 729 of the textbook. This is part of where processes get created. We need to change things here a bit. If you have been using the mined text editor, then unfortunately this file is too big for it (but other files mentioned below are not too big). We only need to make small changes to system.c, so a minimal acquaintence with the vi editor will actually suffice. Look at the man page for vi if you need to. Now, you need to put an include directive at the top of system.c to include stdlib.h. Then add

   rpc->init_priority = rand() % 1000;

   to the bottom of do_fork(). Any time a child process gets created, it will thus be given a random initial priority (so we can experiment with lots of processes with different priorities). Next add

   EXTERN int heapsize; 

   to the top of the file glo.h, so that heapsize will become a global variable in Minix. It needs to be initialized to zero though inside the file main.c. Do this right after the variable declarations in the main() function. Next, you need to get the above heap code (I will assume that you put this in a file heap.c) copied into the file proc.c. If you use cp to copy proc.c to proc.c.old, then you can use the command

   cat heap.c proc.c.old > proc.c

   to accomplish this objective. This will put the heap code at the top of the file proc.c. You will need to move the heap code to the position just above the interrupt() function in proc.c. If necessary, check the man page for the editor you are using, to find out how to move a block of text. After you make all these changes, rebuild the Minix kernel, and then reboot Minix to make sure that nothing that you did had any noticable impact on Minix.
   
   
3. 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 moments that are appropriate when we later actually let the heap take the place of the FIFO queue. First go inside proc.c and change the heap code by commenting out or un-commenting out constants definitions, in order to make
   
   USING_HEAP_IN_MINIX_KERNEL, PTR_TO_PROC_TABLE_MODE and DEBUG_HEAP_IN_MINIX defined, but
   
   INCLUDE_HEAP_TEST_CODE, HEAPSIZE_DEFINED_LOCALLY, TRY_TO_BE_FAIR_WHEN_EQUAL_PRIORITIES (actually, this one doesn't matter) and DEBUG_OUTSIDE_MINIX undefined.
   
       Notice how the debugging 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 (+,^,-), the next character should be a digit indicating the heapsize after the operation (assuming heapsize is between zero and nine), and the next character should be an integer identifier for the process being added to or removed from the heap. Inspect the code to see where these diagnostic messages occur, and so too see what each of the three symbols +,^,- signifies in the diagnostic messages. (I needed to use putk because printf is too high level and will hang the system.)
   
       You will now need to add code to the functions pick_proc(), ready() and unready() functions. 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 the USER_Q ready queue, and not in any way affect the other queues at any time during this project. This requires an understanding of the existing code. Actually, at this stage, any code you add should be carefully designed so as not to impact the working behavior of Minix. Later you will disable the USER_Q queue, but for now you must not impact the functionality of any of the queues. Use insertIntoHeap() inside ready(). Use deleteFromHeap() inside unready(). Use whoIsOnTopOfHeap() inside pick_proc(), because the Minix way of doing things leaves the process that it selects for execution in the ready queue. (Alternatively, you could extract and then reinsert, but this is wasteful.) Again, you should understand the existing code, and more or less let the usage of the USER_Q queue 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 removing it.
   • In ready(), just insert rp into the heap, using the appropriate initial priority.
   • In unready(), delete rp from the heap (don't worry that it might not be there), and if rp "is" the current process (i.e. points to the table for the current process), then reschedule using pick_proc().
   
       Once you've done all this, you should 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, boot hd1, fix the kernel that you just changed, halt again, and return to the partition you were working in.
   
   
4. Now for the touchiest part. The time has come to disable the user process FIFO queue and replace it with the heap. The first detail is to go into the file clock.c and change the function clock_handler(). Comment out a bit and add a bit to make it look like this towards the bottom:

    /* #if (SHADOWING == 0)
         rdy_head[USER_Q] != NIL_PROC) {
   #else
         (rdy_head[USER_Q] != NIL_PROC || rdy_head[SHADOW_Q] != NIL_PROC)) {
   #endif
   */
        heapsize > 0 ) {
   

   
   Then get back into proc.c. Change the body of the function sched() to look like this:

     if (getHeapsize() == 0) return;
     pick_proc();
   
   /*
     if (rdy_head[USER_Q] == NIL_PROC) return;
   */
     /* One or more user processes queued. */
   /*
     rdy_tail[USER_Q]->p_nextready = rdy_head[USER_Q];
     rdy_tail[USER_Q] = rdy_head[USER_Q];
     rdy_head[USER_Q] = rdy_head[USER_Q]->p_nextready;
     rdy_tail[USER_Q]->p_nextready = NIL_PROC;
     pick_proc();
   */
   

   Then go back to the functions pick_proc(), ready() and unready() and very carefully comment out the functionality of the USER_Q FIFO queue. Now, rebuild the kernel again, cross your fingers and reboot Minix. If all goes well, you've done the hard work, so congradulations. Now halt, boot hd1, log in, use fix_kernel to undo the changes you made to the kernel, halt, boot the Minix you changed, log in, go back to /usr/src/kernel, and proceed as follows. Comment out the definition of DEBUG_HEAP_IN_MINIX, rebuild the kernel, and reboot. Minix should appear to be working as normal, but of course it is now using the heap.
   
   
5. Now a bonus problem (1 point): Copy the following C program and get it running. It will make a lot of processes, and have them stay busy and periodically print messages. Get this running. Remember that all these processes have different (random) priorities. You should therefore see the process with the highest priority starving out all the other processes. It isn't until this one finishes that the next highest priority process gets a chance to really do anything. And so forth. You're final mission is to alter the code in proc.c again so that, after rebuilding and rebooting, when you run the following C program, it starts off exhibiting the starvation behavior, but over time it assists starved processes so that towards the end, the processes are sharing the CPU more or less evenly. Here is the C program:

       /*
         Create lots of child processes, keep them busy, and have them
         report periodically.
       */
   
       #include 
   
       #define NUM_CHILDREN 50
       #define NUM_PRINTS 20
       #define NUM_DELAY_LOOPS 3000000
   
       void main()
       {
          int i, j, pid, status;
          for(i=0; i < NUM_CHILDREN; i++)
            if ((pid = fork()) == 0) break;
          if (pid != 0)
            for(i=0; i < NUM_CHILDREN; i++)
              waitpid(-1, & status, 0);
          else {
            pid = getpid();
            for (i=0; i < NUM_PRINTS; i++)
            {
              for (j=0; j < NUM_DELAY_LOOPS; j++) /* do nothing */ ;
              printf("Hello there from process %d.\n", pid);
            }
          }
          printf("Good-bye from process %d.\n", getpid());
       }
   

   The above program is also available in a text file     here.
   
       Once you have this working, or whatever portion of the programming part of this project you were able to complete, you should submit enough to show me what you did. If you sucessfully rebuilt the kernel and can execute the above program, then capture its output in a file (using redirection ">"), and print this file. In any case, print your altered proc.c, or at least enough of it so that I can see the changes you made to the functions pick_proc(), ready() and unready().