Minix Scheduler Programming Project

Due: 7/10/2013

Purpose

The main goal for this project is to modify the MINIX 3 scheduler to be a lottery scheduler.

Basics

The goal of this assignment is to gain some familiarity with scheduling in an operating system. In this assignment you are to implement a lottery scheduler in the Minix operating system. A lottery scheduler assigns each process a number of tickets, then randomly draws a ticket among those which are 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 and the sheduling 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 approach this is to start with every process having 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. The Minix scheduler is split between kernel space and user space. The kernel space scheduler is a basic, default scheduler. The user space scheduler is intended for any user defined scheduling algorithms.

The Minix Wiki has an extensive discussion on user space scheduling. In particular is a report by Bjorn Smith.

Lottery Scheduling

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 may be the place to initialize any data structures.

Deliverables

You must hand in a compressed tar file of your project directory, including your design document and your test program. Talk to your instructor if you don't know how to use the programs tar and gzip for this assignment. 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 grader. Your code and other associated files must be in a single directory; the grader will copy them to his/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.

Hints

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 should do your design first, before writing your code. 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 with a project partner of your choice. If you choose to work with a partner (encouraged), you both receive the same grade for the project. Please make sure that both partners' names and accounts appear on all project files.

Submitting Your Work

All of your source files MUST be in plain text format. You will lose points if you try to do your own thing... Place all of your files (including a readme.txt and the test program) in a directory called project3 in your account. If you are working with a partner, only ONE of the partners should submit the project. However, both partners should KNOW that it was or was not submitted. Submit this directory electronically, from a CS Linux workstation, using the following command:

submit -v rwd-grd 440-project-3 project3

------------------------------------------------------------------------

This assignment adapted from UC Santa Cruz, Computer Science Department, Ethan Miller.