Programming Project #2

CMPS 111, Spring 2008

Assigned: April 15th @ 11:53pm
Due: May 1st @ 11:59pm

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 3 more process queues to the MINIX operating system—your modifications should only apply to user processes, not to OS kernel processes.

Details

Unless explicitly specified, all source code can be found in /usr/src/.

In this project, you will modify the scheduler for MINIX. This should mostly involve modifying code in kernel/proc.c 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 3 queues to the existing 16 for a total of 19 queues. The easiest solution is to use the top 16 queues for system processes using the existing code, and to use the bottom 3 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 three round robin queues. Processes are placed into the first queue when they are created, and move to the second queue after they have completed five quanta (that is, after they have been scheduled five times without waiting for I/O first), and to the third queue after they have completed ten quanta. The scheduler runs all of the processes in the first queue once and then runs a single process from the second queue. After all of the processes in the second queue have run, a process from the third queue is selected to run. This can be implemented in several ways; one possibility is to include a “pseudo-process” in the first queue that, when at the front of the queue, causes a process from the second queue to be run (also repeated in the second queue to run a process in the third queue).

Assume the following processes are in the three queues:

The scheduler would run processes in this order:
P1 , P2 , P3 , P4 , P1 , P2 , P3 , P5 , P6 , P1 , P2 , P3 , P4 ...

This allows long-running processes to make (slow) progress, but gives high priority to short-running processes.

To do this, you should add three additional queues to kernel/proc.c. System processes are scheduled by the same mechanism they use currently, but user processes are scheduled by being initially placed into queue 1, with a later move to queue 2 (or from queue 2 to queue 3). You can do this by modifying 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 her 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 15 Apr 2008 by Darrell Long or perhaps by Stephanie Jones