Lab: Scheduling

In this lab you will implement a priority scheduler for xv6.

$ grep "struct proc" *.h
defs.h:struct proc;
defs.h:pagetable_t     proc_pagetable(struct proc *);
defs.h:int             killed(struct proc*);
defs.h:void            setkilled(struct proc*);
defs.h:struct proc*    myproc();
proc.h:  struct proc *proc;          // The process running on this cpu, or null.
proc.h:struct proc {
proc.h:  struct proc *parent;         // Parent process
proc.h:struct prochist {
% grep "struct proc" *.c
exec.c:  struct proc *p = myproc();
file.c:  struct proc *p = myproc();
pipe.c:  struct proc *pr = myproc();
... lots of matches
sysproc.c:  struct proc* p = myproc();
trap.c:  struct proc *p = myproc();
trap.c:  struct proc *p = myproc();

$ echo > answers-scheduling.txt
$ echo 10 > time.txt

Fetch the xv6 source for the lab and check out the scheduling branch:

  $ git fetch
  $ git checkout scheduling
  $ make clean

Background

Xv6's proc.h and proc.c

The files proc.h and proc.c contain the data structures and algorithms used to implement Xv6's process model. The data structure struct proc defines process information that Xv6 uses. When performing Lab syscall, you added members to struct proc. For Lab Scheduling, I have added members to struct proc and code to proc.c.

• struct proc has a member int priority that you will use.
• proc.h has a struct prochist for maintaining a cirucular buffer of procs that are scheduled.
• proc.c has a function proc_hist() that when called adds information to the prochist[] circular buffer.
• param.h has two macros used for selecting a scheduling policy.

  #define SCHED_RR      0  // Round-Robin Scheduler
  #define SCHED_PRIOR   1  // Priority-Based Scheduler
  

• proc.c has a static variable int schedular_policy that can be set to either SCHED_RR for a round-robin scheduler or SCHED_PRIOR for a priority scheduler.
• proc.c has an updated scheduler() function that includes a conditional statement to select a scheduling policy based on the value of the variable schedular_policy. As provided the conditional executes the original Xv6 round-robin scheduler for both conditions. You will update the SCHED_PRIOR condition to be a priority scheduler.
• The updated scheduler() in proc.c calls proc_hist() to add information to prochist[].

Xv6 Process States

The file proc.h defines the enumerated type procstate as follows.

enum procstate { UNUSED, USED, SLEEPING, RUNNABLE, RUNNING, ZOMBIE };

Processes have a state diagram that is summarized as follows.

The scheduling algorithm searches a list of Runnable processes, selects the next process to run, and runs it. Running a process involves a context switch, which is described in the next section. The scheduling algorithm performs both the Scheduled arrow and the Descheduled arrows. The arrow labeled Scheduled moves a process from Runnable to Running, while at the same time the arrow labeled Descheduled moves the Running process back to the list of Runnable processes.

You will notice that procstate defines three additional states UNUSED, USED, and ZOMBIE. An UNUSED proc is available to be allocated. A proc is temporarily in the USED state until it is finally aloocated when it becomes RUNNABLE.

Another terminology for process states is Running, Ready, and Blocked. OS Three Easy Pieces uses this terminology. The following is a process state transition diagram using these terms.

Xv6 Scheduler

Xv6 supports a maximum 64 concurrent processes, and they are defined in the array struct proc proc[NPROC]; where param.h contains #define NPROC 64, and proc.h contains the definition of a struct proc. struc proc has many members, one of which is enum procstate state;. The function procinit() in proc.c initializes all of the struct proc elements in the array proc[] to UNUSED. An allocated process (allocproc() is briefly in the USED state until it is made RUNNABLE.

The Xv6 scheduler() iterates through the struct proc proc[] array searching for a RUNNABLE process. Once the scheduling algorithm selects a RUNNABLE process, Xv6 performs a context switch from the scheduler to the selected process. Context switches are a key component in operating systems. A timer interrupt causes the scheduling algorithm to run. Consider that the OS is currenting executing process Coletta when a timer interrupt occurs. First a context switch from Coletta to the scheduler must occur. Then, after the scheduler has selected Opal to run, a context switch from the scheduler to Opal must occur. Once Xv6 has booted, the scheduler enters an endless loop searching for RUNNABLE processes and performing context switches to them. The scheduler runs in kernel mode. Xv6 creates the initproc, and the scheduler runs it (i.e., performs a context switch). The initproc creates the sh (shell) process, and the scheduler runs it.

Xv6 Shell and User Programs

• ls.c creates ls.o
• ulib.c creates ulib.o
• usys.pl creates usys.S creates usys.o
• ls.o, ulib.o, usys.o are linked together into the ls program.

• Call fork() to create a duplicate shell process.
• Call exec() to replace the duplicate shell with the command's program. The call to exec() is performed in the child's portion of the fork's if statement. The parent calls wait() in its portion of the fork's if statement.

Xv6 Context Switches

The following diagrams displays a context switch from a process Coletta to a process Opal.

There is a lot to digest in the above simple-looking context switch diagram. The process Coletta is running in user mode, when a timer interrupt occurs, which is the OS interrupt used for a context switch. On the RISCV architecture, the timer interrupt is immediately processed in machine mode by timervec() (in kernelvec.S), which issues a software interrupt that is processed by uservec() (in trampoline.S). The RISCV CPU is now in supervisor mode, but the CPU is still using the page table of Coletta - not the OS page table. The code for uservec() is on the trampoline page, the virtual address of which is mapped in each user proc's page table. Coletta's trampoline page is marked to allow execution in supervisor mode. To refresh your memory on memory layout, you can examine memlayout.h and Figure 3.3 of our xv6 text book, which was part of our page table studies. Having the trampoline page mapped to Coletta's page table allows uservec() to begin executing in supervisor mode prior to changin to the OS page table, which also maps the virtual address trampoline page to the same address. Thus uservec() can switch to the OS page table and continue executing the trampoline code. Before switching to the OS page table, uservec saves all registers in Coletta's TRAPFRAME. Each process has a unique physical page allocated as its TRAPFRAME. Each process's TRAPFRAME is mapped to the same virtual address, which allows uservec() to save the registers. The process's struc proc member p->trapframe points to the trapframe with its physical address, which allows the kernel to access the process's TRAPFRAME using the kernel page table because the kernel's page table maps a virtual address to its corresponding physical address. For example, the kernel's page table maps the virtual page number 0x80000 to the physical page number 0x80000.

Xv6's Round Robin Scheduler

The Xv6 function scheduler() in the file proc.c implements a round robin scheduler.

Xv6's Priority Scheduler

You will implement a priority scheduler.

Scheduler Tester - testschd.c

• Coletta - 50
• Opal - 51
• Florence - 52

 $ testschd 20 3 31

The testschd.c program calls the system call function spoon(), which is exactly like fork(), but spoon() allows you to name the function. The function name is copied into the struct proc member name. Without spoon() all of the processes of testsched would have the name of their parent - e.g., they would be named testschd.

You must implement spoon() before testschd.c will run. Or you can change the calls to spoon to be calls to fork to temporarily run the program, but you must implement spoon() before completing the lab.

Scheduler Tester - ctrl-p

proc_id priority state name

$ testschd
ctrl-p
1 0 sleep  init
2 0 sleep  sh
3 100 sleep  testschd
4 50 runble Coletta
5 51 run    Opal
6 52 runble Florence
ctrl-p
1 0 sleep  init
2 0 sleep  sh
3 100 sleep  testschd
4 50 run    Coletta
5 51 runble Opal
6 52 runble Florence

Tmr Rupts: 250, Sch Loops: 212295, Swtch Run: 210, Swtch New: 13, Switch Old: 182, Swtch sh: 15

index: cpu proc_id priority name priority

$ testschd
Parent Sleeping - let children get priorities set.
Child Coletta:4, priority 0!
Child Coletta:4, priority 50!
Child Opal:5, priority 0!
Child Opal:5, priority 51!
Child Florence:6, priority 0!
Child Florence:6, priority 52!
Starting child Coletta:4
Starting child Opal:5
Starting child Florence:6
Child Coletta:4 with priority 50 has finished!
Child Opal:5 with priority 51 has finished!
Child Florence:6 with priority 52 has finished!
All children have finished!
Tmr Rupts: 206, Sch Loops: 108822, Swtch Run: 235, Swtch New: 167, Switch Old: 54, Swtch sh: 14
0: 0 4 Coletta 50
1: 0 5 Opal 51
2: 0 6 Florence 52
3: 0 4 Coletta 50
4: 0 5 Opal 51
5: 0 6 Florence 52
6: 0 4 Coletta 50
7: 0 5 Opal 51
8: 0 6 Florence 52
... 51 entries of Coletta, Opal, Florence ...
60: 0 4 Coletta 50
61: 0 5 Opal 51
62: 0 6 Florence 52
63: 0 3 testschd 100

Sample testschd.c Output for Priority Scheduler

$ testschd
Parent Sleeping - let children get priorities set.
Child Coletta:4, priority 0!
Child Coletta:4, priority 50!
Child Opal:5, priority 0!
Child Opal:5, priority 51!
Child Florence:6, priority 0!
Child Florence:6, priority 52!
Starting child Coletta:4
Starting child Opal:5
Starting child Florence:6
Child Florence:6 with priority 52 has finished!
Child Opal:5 with priority 51 has finished!
Child Coletta:4 with priority 50 has finished!
All children have finished!
Tmr Rupts: 224, Sch Loops: 121268, Swtch Run: 238, Swtch New: 15, Switch Old: 209, Swtch sh: 14
0: 0 1 initcode 0
1: 0 2 init 0
2: 0 3 testschd 0
3: 0 4 Coletta 0
4: 0 5 Opal 0
5: 0 6 Florence 0
6: 0 3 testschd 100
7: 0 6 Florence 52
8: 0 3 testschd 100
9: 0 6 Florence 52
10: 0 3 testschd 100
11: 0 5 Opal 51
12: 0 3 testschd 100
13: 0 4 Coletta 50
14: 0 3 testschd 100

$ make CPUS=1 qemu

$ make qemu

int setpriority(int);
int getpriority(void);

• Since setpriority and getpriority are system calls, you can review the steps for adding system calls at Reference: Xv6 System Calls.
• Add setpriority and getpriority to sysproc.c.
• You can examine testschd.c for sample calls to setpriority and getpriority.
• Create test code to ensure your setpriority and getpriority work.

Implement the spoon() System Call

Some Hints

• Since spoon() is a system call, you can review the steps for adding system calls at Reference: Xv6 System Calls.
• Add spoon() to proc.c.
• spoon() will be just like fork() except it will have a char* argument that is copied to the name member of its struct proc for the allocated process.
• Create test code to ensure your spoon() works.

Implement a Priority Scheduler

Some Hints

• Use your design created in your notebook for Question Q9. Do not attempt to implement your priority scheduler until you have completed a design and discussed it with me.
• A good design makes writing the code much easier.
• There is a requirement for performing round robin scheduling when procs have equal priority. I found it easier to first implemented my priority scheduler without this implementation. This meant that one of the equal priority procs would run to completion before the next.

$ testschd

Diagrams of Various Schedulers

The following diagram shows various scheduling algorithms. You will select a Timeline in your answers to questions below.

Submit the lab

This completes the lab. Read Lab Submissions for instructions on how to submit your lab; however, you do not copy/paste the output of make grade into your lab-scheduling-handin.txt file because Lab Scheduling does not have the make grade tests because the output of testsched varies slightly.