This portion of Project 1 requires you to change the process scheduler functionality inside Minix. Obviously, you will need to modify Minix kernel code to make this happen. Specifically, you will be adding functionality to support Lottery Scheduling. Lottery scheduling is a flexible way to schedule CPU time by giving each process a number (n) of tickets. Each time the scheduler is called, it looks at the total number of tickets outstanding (i.e. held by all processes). It randomly chooses one of the outstanding tickets, and the process holding that ticket is the process that gets to run. The intuition is that processes can increase or decrease their share of the CPU by getting or giving away tickets.

Modifying the scheduler for Minix should mostly involve modifying code in kernel/proc.c , specifically thesched() 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() inservers/pm/misc.c (don't worry-the code in here is very simple), which calls do_nice() inkernel/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 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. 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 Tickets-1, where Tickets 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.