Message Mechanism And Process Scheduling

Outline of the project objectives

    The purpose of this project is to experiment with the Linux  "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 Linux  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 Linux 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 Linux 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 Linux 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 Linux. 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 Linux 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 Linux, 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 Linux 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_Linux_KERNEL, HEAPSIZE_DEFINED_LOCALLY, PTR_TO_PROC_MODE and DEBUG_INSIDE_Linux defined, 

but INCLUDE_TEST_CODE, DEBUG_OUTSIDE_Linux 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 Linux 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 Linux code, notice how the debugging inside Linux 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 Linux kernel, and let it reboot Linux to make sure that nothing that you did so far had any noticable impact on Linux. 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 Linux user process FIFO queue. At this stage, we won't actually change the way Linux 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 Linux 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 Linux. 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 Linux 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 Linux. If all goes well, when Linux 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 Linux 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_Linux 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 Linux configuration. So one of your first duties here is to enlarge the Linux process table and related data structures. All you need to do is to go to /usr/src/include/Linux 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 Linux make facility is a little flakey), I recommend that while you are still inside .../Linux 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, Linux 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: 

11.                  if (istrueuserp(rpc)) { 

12.                      rpc -> p_max_priority = 1 + rand()%99;  /* between 1 and 99 */ 

13.                      rpc -> p_priority = rpc -> p_max_priority; 

14.                  } 

Once again, I recommend doing a make clean and a make all before doing a rebuild. 

The last step in altering the Linux 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 Linux 3 code from automatically changing priorities. That's your job now!