Programming Project #2

CMPS 111, Spring 2006

Assigned: April 24th
Due: Thursday, May 11th at 11:59 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 dual queue 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.

One goal of best-effort scheduling is to give I/O-bound processes both faster service and a larger percentage of the CPU when they are ready to run. Both of these things lead to better responsiveness, which is one subjective measure of computer performance for interactive applications. CPU-bound processes, on the other hand, can get by with slower service and a relatively lower percentage of the CPU when there are I/O-bound processes that want to run. Of course, CPU-bound processes need lots of CPU, but they can get most of it when there are no ready I/O-bound processes. One fairly easy way to accomplish this in a lottery scheduler is to give I/O-bound processes more tickets – when they are ready they will get service relatively fast, and they will get relatively more CPU than other CPU-bound processes.

The key question is how to determine which processes are I/O-bound and which are CPU-bound. One way to do this is to look at whether or not processes block before using up their time quantum. Processes that block before using up their time quantum are doing I/O and are therefore more I/O-bound than those that do not. On the other hand, processes that do not block before using up a time quantum are more CPU-bound than those that do. So, one way to do this is to start with every process with some specified number of tickets. If a process blocks before using up its time quantum, give it another ticket (up to some set maximum, say 10). If it does not block before using up its time quantum, take a ticket away (down to some set minimum, say 1). In this way, processes that tend to do relatively little processing after each I/O completes will have relatively high numbers of tickets and processes that tend to run for a long time will have relatively low numbers of tickets. Those that are in the middle will have medium numbers of tickets.

This system has several important parameters: time quantum, minimum and maximum numbers of tickets, and the speed at which tickets are given and taken away.

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.

Lottery Scheduling

The first approach to scheduling is to use lottery scheduling, as described in class. System processes (queues 0–15) are run using their original algorithm, and queue 20 now contains the idle process. However, queue 16 contains all of the 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). 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 outstanding tickets. 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.

For dynamic priority assignment, you should modify lottery scheduling to decrease the number of tickets a process has by 1 each time it receives a full quantum, and increase its number of tickets by 1 each time it blocks without exhausting its quantum. A process should never have fewer than 1 ticket, and should never exceed its original (desired) number of tickets.

You must implement lottery scheduling as follows:

  1. Basic lottery scheduling. Start by implementing a lottery scheduler where every process starts with 5 tickets and the number of tickets each process has does not change.
  2. Lottery scheduling with dynamic priorities. Modify your scheduler to have dynamic priorities, as discussed above.

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

Dual Round-Robin Queues

The second algorithm you need to implement uses two 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). The scheduler runs all of the processes in the first queue once and then runs a single process from the second queue. 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.

Assume the following processes are in the two queues:

The scheduler would run processes in this order:
P1 , P2 , P3 , P4 , P1 , P2 , P3 , P5 , P1 , P2 , P3 , P6 ...
This allows long-running processes to make (slow) progress, but gives high priority to short-running processes.

To do this, you should add two additional queues to kernel/proc.c (perhaps using queues 17 and 18). 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. 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 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 200 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 14 May 2006 by Ethan L. Miller