Minix3 Scheduler

有关minix3的调度，相关的理论在  Operating Systems - Design and Implementation, 3rd Edition 中的  Scheduling in Interactive Systems   里介绍，

• Round-Robin Scheduling
  
• Priority Scheduling
  
• Multiple Queues
  
• Shortest Process Next
• Guaranteed Scheduling
  
• Lottery Scheduling

    之类的算法 。这个和批处理系统的job调度不同，所以不可能实现First-Come First-Served,Shortest Job First ,Shortest Reming Time Next之类的调度算法，下面找了一个国外UCSB大学的操作系统课程的相关Minix操作系统的调度算法，有点意思。

Adding a Lottery Scheduler to Minix

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 inkernel/proc.c , specifically thesched() and pick_proc() functions (and perhaps enqueue() and dequeue() ). You may also need to modifykernel/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 thesrandom() 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. 

实现方案：

http://code.google.com/p/minixlottery/

reference:

http://www.cs.ucsb.edu/~ravenben/classes/170/html/hw1.html