Programming Project #2

CMPS 111, Fall 2007

Assigned: October 18th
Due: Thursday, November 1st at 10:00 PM

Remember: your project must be turned in online.

Purpose

The main goal for this project is to modify the MINIX 3 scheduler to be more flexible. You must implement:

This project will also teach you how to experiment with operating system kernels, and to do work in such a way that might crash a computer. You'll get experience with modifying a kernel, and may end up with an OS that doesn't work, so you'll learn how to manage multiple kernels, at least one of which works.

You should also read over the general project information page before you start this project. In them, you will find information about MINIX 3 as well as general guidelines and hints for projects in this class.

Basics

The goal of this assignment is to get everyone up to speed on modifying MINIX 3 and to gain some familiarity with scheduling. In this assignment you are to implement a multi-level feedback-based scheduler and a lottery scheduler. A lottery scheduler assigns each process some number of tickets, then randomly draws a ticket among those allocated to ready processes to decide which process to run. That process is allowed to run for a set time quantum, after which it is interrupted by a timer interrupt and the process is repeated. The number of tickets assigned to each process determines both the likelihood that it will run at each scheduling decision as well as the relative amount of time that it will get to execute. Processes that are more likely to get chosen each time will get chosen more often, and thus will get more CPU time. The feedback scheduler does a similar thing using multiple queues. To accomplish this goal, you'll need to add 16 more process queues to the MINIX operating system—your modifications should only apply to user processes, not to OS kernel processes.

Details

In this project, you will modify the scheduler for MINIX. This should mostly involve modifying code in kernel/proc.c (All of the source code, except where specified explicitly, is in /usr/src), specifically the sched() and pick_proc() functions (and perhaps enqueue() and dequeue() ). You may also need to modify kernel/proc.h to add elements to the proc structure and modify queue information (NR_SCHED_QUEUES, TASK_Q, IDLE_Q, etc.) and may need to modify PRIO_MIN and PRIO_MAX in /usr/include/sys/resource.h. Process priority is set in do_getsetpriority() in servers/pm/misc.c (don't worry—the code in here is very simple), which calls do_nice() in kernel/system.c. You might be better off just using the nice() system call , which calls do_nice() directly. You'll probably want to modify what do_nice() does—for lottery scheduling, nice() can be used to assign or take away tickets.

The current MINIX scheduler is relatively simple. It maintains 16 queues of "ready" processes, numbered 0–15. Queue 15 is the lowest priority (least likely to run), and contains only the IDLE task. Queue 0 is the highest priority, and contains several kernel tasks that never get a lower priority. Queues 1–14 contain all of the other processes. Processes have a maximum priority (remember, higher priorities are closer to 0), and should never be given a higher priority than their maximum priority. You're going to need to add 16 queues to the existing 16, for a total of 32 queues. The easiest solution is to use the top 16 queues for system processes using the existing code, and to use the bottom 16 queues for user processes. You can identify system processes by seeing if the SYS_PROC bit is set in a process's flag variable.

Lottery Scheduling

The first approach to scheduling is to use lottery scheduling, as described in class. System processes (queues 0–14) are run using their original algorithm, and queue 15 still contains the idle process. However, queue 16 contains all of the runnable user processes, each of which has some number of tickets. The default number of tickets for a new process is 5. However, processes can add or subtract tickets by calling setpriority(ntickets), which will increase the number of tickets by ntickets (note that a negative argument will take tickets away). A process cannot accumulate more than 100 tickets.

Each time the scheduler is called, it should randomly select a ticket (by number) and run the process holding that ticket. Clearly, the random number must be between 0 and nTickets-1, where nTickets is the sum of all the tickets belonging to processes in the ready queue (processes that are blocked are ineligible to run). You may use the random() call (you may need to use the random number code in /usr/src/lib/other/random.c) to generate random numbers and the srandom() call to initialize the random number generator. A good initialization function to use would be the current date and time.

New processes are created and initialized in kernel/system/do_fork.c. This is probably the best place to initialize any data structures.

Multiple Round-Robin Queues

The second algorithm you need to implement uses sixteen round robin queues, and are placed into one of the queues based on their calculated priority. The priority is calculated each time a process is placed into a ready queue (either by completing a quantum or by finishing an I/O) by calculating actpriority = min(estcpu/2 + nice, 15), where nice is the priority set by setpriority(). Calculating estcpu is a bit more involved. estcpu initialized at zero, and is incremented each time the process uses its entire quantum. Approximately every 2 seconds, estcpu for each process is decayed—reduced to 90% of its previous value. Note that this happens for all processes, not just those in a ready queue. The result is that processes that don't use lots of CPU get a lower value for actpriority, making them more likely to run. The value actpriority determines the queue into which a process is placed; a user process with actpriority=4 is placed into queue 20. Processes are added to the end of the appropriate queue. Each time it is called, the scheduler runs the process at the head of the highest priority user queue.

To implement this assignment, you should add sixteen additional queues to kernel/proc.c by setting NR_SCHED_QUEUES appropriately. System processes are scheduled by the same mechanism they use currently, but user processes are scheduled by evaluating the above equation. Keep in mind that estcpu is initialized to zero; you'll need to keep track of estcpu in the process data structure. You'll probably need to modify sched() and pick_proc() in kernel/proc.c. You might also need to modify enqueue() and dequeue(), and should feel free to modify any other files you like.

Deliverables

You must hand in a compressed tar file of your project directory, including your design document. You must do a "make clean" before creating the tar file. In addition, you should include a README file to explain anything unusual to the teaching assistant. Your code and other associated files must be in a single directory; the TA will copy them to his MINIX installation and compile and run them there.

Do not submit object files, assembler files, or executables. Every file in the tar file that could be generated automatically by the compiler or assembler will result in a 5 point deduction from your programming assignment grade.

Your design document should be called design.txt (if plain ASCII text, with a maximum line length of 75 characters) or design.pdf (if in Adobe PDF), and should reside in the project directory with the rest of your code. Formats other than plain text or PDF are not acceptable; please convert other formats (MS Word, LaTeX, HTML, etc.) to PDF. Your design document should describe the design of your assignment in enough detail that a knowledgeable programmer could duplicate your work. This includes descriptions of the data structures you use, all non-trivial algorithms and formulas, and a description of each function including its purpose, inputs, outputs, and assumptions it makes about the inputs or outputs. A sample design document is available on the course web page.

Hints

We assume that you are already familiar with makefiles and debugging techniques from earlier classes such as CMPS 101 or from the sections held the first week of class. If not, this will be a considerably more difficult project because you will have to learn to use these tools as well.

This project doesn't require a lot of coding (typically fewer than 250 lines of code), but does require that you understand how to use MINIX and how to use basic system calls. You're encouraged to go to the class discussion section or talk with the course staff during office hours to get help if you need it.

You should do your design first, before writing your code. To do this, experiment with the existing shell template (if you like), inserting debugging print statements if it'll help. It may be more fun to just start coding without a design, but it'll also result in spending more time than you need to on the project.

IMPORTANT: As with all of the projects this quarter, the key to success is starting early. You can always take a break if you finish early, but it's impossible to complete a 20 hour project in the remaining 12 hours before it's due....

Project groups

You may do this project, as well as the third and fourth projects with a project partner of your choice. However, you can't switch partners after this assignment, so please choose wisely. If you choose to work with a partner (and we encourage it), you both receive the same grade for the project. One of you should turn in a single file called partner.txt with the name and CATS account of your partner. The other partner should turn in files as above. Please make sure that both partners' names and accounts appear on all project files.

Last updated 18 Oct 2007 by Ethan L. Miller