General Information

You can find the original homework document here (or here). This homework assignment is 14% of your final grade. The deadline has been extended to 11:59pm, Saturday November 22nd.

Grading Information

To receive full credit, you must complete everything listed in the homework document. Here is a summary:

1. Include Makefile & Readme
2. Have well commented code
3. Implement setLotteryTickets as defined in the homework document
4. Modify process creation/deletion to update total amount of tickets assigned
5. Modify fork to fail when no more tickets remain in system
6. Implement lottery scheduling

New: The actual distribution of percentage points will be as follows:

• 2% Documentation (1,2)
• 8% Allocation of tickets (3,4,5)
• 4% Lottery scheduling (6)

The numbers in parentheses indicate which item(s) from the summary list fall under that category. For example, items 1 and 2 from the above summary are included in the 'Documentation' section.

Interactive Grading

We will be doing interactive grading for this homework assignment. Interactive grading will take place in the Kemper Hall TA Room (same location for the TA office hours). There are several things you can do to make sure this process goes smoothly:

• Name your user-level library function setLotteryTickets
• Have systest.c and stattest.c already in your Minix system
• Modify systest.c and stattest.c to use your libary file
• Have your kernel modifications already compiled and working

You may bring your laptop for interactive grading. Otherwise, you must have your modifications working on your CS account. Sign-up sheets will be located outside the TA room in Kemper Hall.

NEW: Interactive grading signup sheets will be posted Wednesday (11/19) evening. Eric will be holding interactive grading sessions from 8:00am - 12:00pm on the following days:

• Tuesday, November 25th
• Monday, December 1st
• Tuesday, December 2nd
• Wednesday, December 3rd

Sophie will be holding interactive grading sessions from 1:30pm - 5:30pm on the following days:

• Sunday, November 23rd
• Wednesday, November 26th
• Wednesday, December 3rd
• Friday, December 5th

Handin Information

In addition to interactive grading, you are required to submit some files using handin. We may be using Moss to detect cheating.

There are three things total that you must submit using handin. The files are:

• /usr/src/kernel/system.c
• /usr/src/kernel/proc.c
• readme.txt

The readme should contain the following information:

• Basic information, such as your name, student id, and the date.
• One or two paragraphs on how you implemented setLotteryTickets and lottery scheduling.
• List of what modifications you made to system.c and proc.c, so that we can easily find your code.

From your CS account, execute the following command to submit your files:

Note: You must submit the actual files, NOT floppy.img. Details on how to get the files off of Minix are below:

If you do not have a floppy disk or are unable to complete this process, please contact one of the TAs for help.

Test Programs

We will use several programs to test your implementation. Below are some sample test programs we may use:

• systest.c (updated 14 november 2003)
  • Tests setLotteryTickets(...)
  • Tests to make sure fork() fails when the maximum number of tickets have been allocated
  • Tests to make sure that tickets are reclaimed by the system when a process dies
• systest2.c (updated 14 november 2003)
  • Similar to systest.c
  • Requires a system call getTotalTickets to get the total number of tickets currently assigned
  • Carefully tests how the number of tickets assigned gets updated when processes are created and destroyed
  • This version will not be used to grade your homework, since it requires getTotalTickets to be implemented (which is not a requirement of homework 2)
• stattest.c (updated 18 november 2003)
  • Tests lottery ticket scheduling
  • Read comments for usage information

You can download a floppy image with the test programs already on it here. You should try running these programs to test your implementation of setLotteryTickets() and lottery ticket scheduling.

Homework Clarification

Regarding setLotteryTickets( PID, tickets )

The system call setLotteryTickets( PID, tickets ) should assign a total of tickets to the process, not add the amount of tickets to the number of tickets already assigned to the process. For example, if process pid 4 has 20 tickets currently, and the call setLotteryTickets( 4, 10 ) is made, process 4 should end up having 10 tickets.

Also, setLotteryTickets( PID, tickets ) should return the number of tickets assigned to the process, even if it is less than tickets. The value of -1 should be returned only if setLotteryTickets(...) failed due to an error. Read the homework document for more information.

Suppose process 4 has 10 tickets, and that the maximum number of tickets have already been assigned. Then setLotteryTickets( 4, 20 ) should return 10 because 10 tickets can be assigned to process 4 (since 4 already has 10 tickets allocated to it). However, fork() should return -1 at this point since there are no more additional tickets left in the system for a new process.

Regarding ticket assignment

When deciding if more tickets may be assigned, you must compare num_assigned to MAX_TICKETS. The maximum number of tickets (MAX_TICKETS) is defined as 256 in the homework document. The value of num_assigned should include the number of tickets for all user processes (whether the process is in a ready or wait state). See Hints & Tips for more information.

Regarding lottery scheduling

You should only attempt to schedule user process that are in the ready state.

When choosing a random number, you should choose a number in the range of 1 to max where max is the total number of tickets assigned to ready processes. You should not include the number of tickets from processes that are in a wait or non-ready state in the calculation of max.

Homework Hints & Tips

Various guides and slides have been created to help with homework 2. You can find these here:

• Adding System Calls in Minix (guide for creating a simple system call in Minix)
• Eric's Discussion Section Slides (slides detailing how to create setLotteryTickets)
• Sophie's Discussion Section Slides (slides giving various hints and tips, many of which are listed below)

Tracking Total Assigned Tickets

You will have to track how many tickets have been assigned for various parts of this homework assignment. It may be helpful to create a system call (in the same manner as you will create setLotteryTickets) that returns the total number of tickets assigned in the system. However, you must be careful what processes you include. When determining if fork() should fail, you should count the number of tickets for all user processes (even those that are not in a ready state). When you are doing lottery scheduling, you should count the number of tickets for ready processes only.

Looping Through Processes

When searching for a process pid, counting tickets, etc., you will need to loop through processes. There are a couple of ways to do this, depending on what processes you want to loop through.

Using Pointers: To loop through ready processes only, you can make use of rdy_head[USER_Q] and the attribute p_nextready. You might also want to make use of NIL_PROC. Look at page 117 of your book, and in proc.h for more information.

Using the Process Table: To loop through the entire process table, you can simply iterate through proc[]. However, you have to figure out where to start the iteration and where to end the iteration. Where to end is easy - as we know the size of proc[] is NR_TASKS + NR_PROCS. Where to start iteration is a little more tricky. We do not want to loop through tasks, and want to start our loop at the first user process. Here are a few hints: What is the first user process? What is happening on line 06817 in your book's source code (page 603)?

When looping through proc[], we also have to be wary of empty slots. Not every slot has valid process information. If the slot is not being used, we do not want to include that slot. Therefore we will also have to test for this. Look at /usr/src/kernel/proc.h and examine the attributes p_flags and p_priority. Also look at the macros contained in proc.h. Some of this stuff is omitted from the source code in your book, so be sure to look at the actual files on your Minix system.

Writing the System Call

You should write the system call setLotteryTickets(...) in an iterative manner. First get a simple system call which resides in MM working. Then add a system call that makes a task call to the kernel. Lastly, add the actual functionality that the system call must accomplish. Here are a few hints that may help you along the way:

• Be careful of how you name your parameters. For example, pid is defined in /usr/src/mm/param.h and PID is defined in /usr/minix/com.h.
• You must pass parameters using messages for this system call. The message m1 should satisfy your needs. Read more in your book (pages 109-110) or examine /usr/include/minix/types.h.
• You can call _taskcall(...) straight from MM without having to add another library function. Just be sure to include minix/com.h.
• Define a constant MAX_TICKETS as the maximum number of tickets the system can support. You should place this such that both kernel and the servers (MM, FS) can access the constant. Hint: You may want to look at where the constant NR_PROCS is used and where it is defined.

Tickets and Process Creation, Deletion

You have to modify process creation (fork) and deletion (kill, exit) to take in account the number of tickets assigned in the system. If you constantly calculate the number of tickets assigned versus keeping a global variable, you will not have to worry about process deletion. Otherwise, when a process dies it must subtract its tickets from the number of tickets assigned.

There are two things you must worry about when it comes to process creation. First you must decide if fork() should fail based on how many tickets are already assigned in the system. If there are no more tickets left, fork() should return -1. You want to make this check before memory is allocated for the new process. Refer to the lecture 2 slides for more information on fork().

Second, you must initialize the number of tickets for a new process to 1. You may want to do this in the same place that fork() initializes the child pid.

One last thing... you may have to worry about initializing the number of tickets for init. Remember, init is not a result of a fork() since it is the first/initial user process. Hint: Look at /usr/src/kernel/main.c.

Lottery Scheduling

The first thing you should do is read the section "Scheduling in MINIX" on page 140 of your book and get familiar with proc.c, and understand lottery scheduling in general.

Suppose we have the following ready queue of user processes, where the bold number on top is the pid and the blue number on bottom is the number of tickets that process has:

To schedule the next process using lottery scheduling, we would first choose a random number. In this example, the total number of tickets assigned to a ready process is 36. Therefore we choose a random number between 1 and 36. Starting at the beginning of the queue, we count up the number of tickets assigned to each process until the count is greater than or equal to our random number.

Suppose our random number is 14. We count the tickets of processes 1, 4, 7, and 12 such that our count becomes 1 + 1 + 10 + 4 = 16 >= 14. Since our count became greater than or equal to our random number when we reached process 12, we let process 12 run next.

Now suppose we have to make a new scheduling decision, and our random number is 4. Using the implementation described above, process 7 would be scheduled to run next. The following picture provides the range of numbers that allow a particular process to run:

For example, process 12 will run whenever our random number is between 13 and 16. Process 4 will run only when the random number is equal to 2.

NEW: If you get a divide by zero error after implementing lottery scheduling - you are most likely trying to mod something by zero. Depending on your implementation, lottery scheduling may be called before there are ANY tickets assigned in the system (thus the total number of tickets will be zero). You may have to add code to lottery scheduling to handle this!

NEW: If you are modifying the ready queue of processes, you will have to update the p_nextready links in the queue. There are three different cases that you have to check for. They are:

• Process is rdy_head[USER_Q]
• Process is rdy_tail[USER_Q]
• Process is located somewhere in the middle of the queue

Random Tips

After adding an attribute to struc proc, running ps to display running processes may return junk to the screen. There are two ways to get around this:

• You can always press F1 for a screen-dump of the running processes.
• You can recompile/reinstall ps. This process does not take very long. Just type make ps and make install while in /usr/src/tools.

NEW: Sometimes the kernel is not updated after you run make hdboot. (You may see a message similar to: 2.0.3r7 is up to date.) To remedy this situation you can try a few different things:

• Delete the file /minix/2.0.3r#, where # is the latest revision number.
• Delete the file /usr/src/tools/image.
• Use a fresh installation of Minix.

After trying one of the above items, you should be able to type make hdboot to actually recompile/install the new kernel.