Theory
each jobs ge some tickets that represent its share ofo CPU time.
Assuming
A holds tickets 0 through 74
B 75 through 99
the winning ticket simply determines whether A or B runs.
ticket currency, ticket transfere, ticket inflation
Implementation example
1. good random number generator to pick the winning ticket
2. data structure to track the processes of the system (e.g., a list)
3. total number of tickets
winning ticket: 300
counter: 0 -> 100 -> 150 -> 400
counter 400 job win.
1 // counter: used to track if we’ve found the winner yet
2 int counter = 0;
3
4 // winner: call some random number generator to
5 // get a value >= 0 and <= (totaltickets - 1)
6 int winner = getrandom(0, totaltickets);
7
8 // current: use this to walk through the list of jobs
9 node_t *current = head;
10 while (current) {
11 counter = counter + current->tickets;
12 if (counter > winner)
13 break; // found the winner
14 current = current->next;
15 }
16 // ’current’ is the winner: schedule it...Actual implementation
Requirements:
The first is int settickets(int number), which sets the number of tickets of the calling process.
The second is int getpinfo(struct pstat *). This routine returns some information about all running processes, including how many times each has been chosen to run and the process ID of each.
You'll need to make sure a child process inherits the same number of tickets as its parents.
TODO: 1. randn generator 2. set tickets 3. getpinfo 4. scheduler modification
random number generator:
ulib.c
user.h
settickets:
sysproc.c
getpinfo:
ptable: Fixed-size array of all processes
– Real kernels have dynamic-sized data structures
CPU scheduler in the OS loops over all runnable processes, picks one, and sets it running on the CPU.
Thus, we have to use that ptable to properly set pstat structure.
proc.c
defs.h
sysproc.c(system call)
This process of code is possible because that user program are not linked with proc.c. The function getpinfo() in user program is eventually considered as system call. (uprogs are linked only with ulib.o usys.o...)
scheduler:
proc.c
When it is time for a process to give up the CPU(yield() routine in trap() routine), the process’s kernel thread calls swtch to save its own context and return to the scheduler context.
trap.c
sched(), which calls swtch to save the current context in p->context and switch to the scheduler context previously saved in cpu->scheduler.
In our example, sched called swtch to switch to cpu->scheduler, the per-CPU scheduler context. That context had been saved by scheduler’s call to swtch. When the swtch we have been tracing returns, it returns not to sched but to scheduler, and its stack pointer points at the current CPU’s scheduler stack.
swtch saves the ra register, which holds the return address from which swtch was called(in scheduler()). When swtch returns, it returns to the instructions pointed to by the restored ra register, that is, the instruction from which the new thread previously called swtch. In addition, it returns on the new thread’s stack.
The scheduler loops over the process table looking for a runnable process, one that has p->state == RUNNABLE. Once it finds a process, it sets the per-CPU current process variable c->proc, marks the process as RUNNING, and then calls swtch to start running it.
proc.c
