Interruptions, time management and scheduling
- to make you handle the interruptions,
- to make you understand time management in a kernel,
- and show you how a scheduler works .
Implementation of a test program (∼ 45mn)
Start by getting the code from xv6:
- git clone https://gitlab.inf.telecom-sudparis.eu/csc4508/xv6-riscv.git -b scheduler-lab
- or git checkout scheduler-lab if you already have a local copy of the repository
You are now in the scheduler-lab branch which contains the source file user/stest.c. This file contains #pragma (i.e. directives for the compiler) to avoid that gcc performs optimizations (this is equivalent to using the -O0 option of gcc). These optimizations should be avoided because the code we are going to run in stest is so simple that gcc happens to entirely eliminate it if optimization are enabled.
Modify stest.c so that it creates 3 child processes with fork(). Each child should display PID starts then PID ends, where PID is the process PID, before exiting. Check that your program behaves correctly. If you see that xv6 starts mentionning zombies, don't worry: we will get rid of these evil zombies in the next question.
If you are curious, do not hesitate to read the code of fork() in proc.c. This code is informative and shows how we can duplicate a process, that is, at high level, copy its memory and structure proc. Don't hesitate to ask your teachers if you want have more details on this code that we will not study more in this module.
In general, a user rarely sees zombies because:
- a shell destroys its zombie children on its own,
- when a zombie's parent dies, the zombie, like any other process, is adopted by an adopting process (process 1, a process named systemd or sometimes a process with another name specialized in this role). When adopting a zombie, the adopting process destroys it.
In xv6, the init process is the adopting process and it displays a message when it sees a zombie. Using the code from init.c as inspiration, make sure that stest destroys its zombie children.
- init creates file descriptors 0, 1, and 2, and associates them with the console. These are the input, output, and error streams of init. These open files being inherited during a fork (see the code of fork() in proc.c), you should understand how a parent and child share their input, error or output streams.
- init then creates a shell, this is the one with which you can interact with xv6.
Interruptions (∼ 30mn)
Let's start by reactivating the clock interrupts. xv6 does not use an absolute external source of time. It only keeps ticks, that are incremented exclusively by the CPU 0 when a timer interrupt is triggered on this CPU core. In addition, those ticks are used as jiffies, i.e., are global to the kernel (whereas ticks are usually local to each core).
In the timerinit() function of start.c (executed only by the CPU 0), add the code to configure the CLINT timer. To do this, copy the following code at the end of the function:
- the first line sets the time when the CLINT must trigger a timer interruption, this time is defined as a delay (interval) after the current time (CLINT_MTIME);
- the last line enables machine-mode timer interrupts, i.e., the RISC-V platform will make the local CPU jump to the interrupt vector defined in mtvec (close to the end of timerinit()) when a timer interrupt is triggered by the local CLINT.
Run xv6. If your code is correct you should regularly see a message telling you that xv6 is alive.
- only core 0 manages jiffies (the function clockintr is only called when the timer interrupt is served by CPU 0), and this variable is called tick in xv6 (the use of the name tick here is not ideal: usually this variable is called jiffies and the tick is local to a core);
- you can also notice the call to wakeup() which wakes up the processes which wait on the variable jiffies. It is with this synchronization mechanism that xv6 implements the sleep() system call (see the code for sys_sleep in sysproc.c).
Scheduling (∼ 1h15)
Modify the code of usertrap() and kerneltrap() so that the current process releases the processor each time the kernel receives a tick, using yield().
To do this, add the following code to usertrap (before the call to usertrapret):
The RUNNABLE state means that the process is ready to run but that he is not elected. The RUNNING state means that the process runs on a core.
The inconsistency could come from the fact that a process is elected on two cores simultaneously.
The yield() function begins by acquiring the ptable.lock lock and setting the process state to RUNNABLE since the latter is no longer elected. Then yield() calls sched().
The sched() function starts by checking that the state of the kernel is consistent before calling the swtch() function. This magic function in assembler allows you to switch from the current context to a new context, i.e., from the kernel context running the scheduler to the elected process and vice-versa. In detail, the swtch() function saves the processor registers and restore those of the kernel context running the scheduler. In particular, it restores the stack pointer of the context. The program counter and the page table of the process are restored by the normal mechanism of the functions usertrap() and kerneltrap() that handled the interruption that ultimately led to the call to swtch().
You can see the kernel context running the scheduler function as the scheduler process (although it does not appear in the list of processes). This special process runs an infinite loop in the kernel which takes care of finding a process to elect (with elect()) and switches to this process using the swtch() function.
Technically, scheduler is the last function called in mpmain, which is called by main. This main function is the entry point into the kernel on startup (see previous lab). We can therefore conclude that the scheduler() is simply the initial startup process.
The elect() function chooses the first ready process of the array proc, which ultimately amounts to systematically electing the same process.
Modify the elect() function to avoid the famine problem that you observe (in other words to ensure that all processes are elected regularly). This question is long and should keep you occupied until the end of the lab. You have several solutions. For the most talented students, we advise to choose the variable priority policy and for other students, FIFO policy. For the super-human students, they can directly get into the PetitLinux policy:
- [FIFO]: you can use the old parameter which indicates what was the last process elected, and move to the next one in the table. In Linux, this policy is called SCHED_RR (round-robin).
- [Fixed priority]: you can add a static priority prio to a process (in the proc structure) that you will set manually (for example with prio = pid / 2); then apply a FIFO algorithm on the highest priority processes (solution starting to get closer to what we do in real time);
- [LRU]: you can add a timestamp to the proc structure indicating which process was least recently elected. For that, you just have to understand what the tick variable is (this is a relatively realistic implementation);
- [Variable priority]: you can add a prio variable to the proc structure. Then, make this variable increase with each tick for unelected processes and decreases sharply with each tick for the elected process indicated by the old variable. Linux's SCHED_OTHER policy is somehow similar to this solution but is fairer;
- [PetitLinux]: you can add process type and apply the following policy:
- If old has the type FIFO, you keep it elected. With this policy, as soon as a process is elected, it has the guarantee to remain elected, unless it falls asleep. This is the policy you had at the beginning of this lab;
- Otherwise, if there is a process with the SCHED_FIFO attribute, you elect him;
- Otherwise, if the old process has the type SCHED_RR, you elect the SCHED_RR process by applying a FIFO policy;
- Otherwise, if there is a process of type SCHED_RR, you elect it;
- Otherwise, you apply a variable priority algorithm or LRU.
