So I have started learning internals of Operating System through OSTEP, and the plan is going to be implement each section from OSTEP into xv6 kernel.
What is xv6
xv6 is an educational open source operating system developed by MIT for teaching concepts of operating system.
Find more here: https://pdos.csail.mit.edu/6.828/2012/xv6.html
Github: https://github.com/mit-pdos/xv6-public
My implementation: https://github.com/lightsigma96/xv6-riscv
xv6 is minimal but contains all the important components needed to create an Operating System.
Understanding xv6 and QEMU
QEMU is a hypervisor and machine emulator which lets you have virtual hardware emulation required by the os.
As implementation of xv6 that I am using supports RISC-V assembly instructions and my CPU is x86_64, direct execution of instructions is not possible.
This is where QEMU steps in, it emulates the disk, RAM, CPU, etc and runs xv6, making xv6 think that it is actually executing RISC-V instructions on RISC-V hardware whereas in reality it is actually being executed on x86_64 system.
While modifying xv6 we can think that we are on actual RISC-V hardware and do not need to worry about translation.
Setting Up xv6
Setting up xv6 is straightforward, just have to use make with correct target to compile xv6 and connect via gdb to default port given.
Multi-Level Feedback Queue (MLFQ)
Now that xv6 is set up, what is MLFQ?
MLFQ is a scheduler policy which determine which process to schedule for CPU to execute depending on various factors.
Turnaround time:
This is the time which specifies the time difference between the time process arrived and the time when it completed executing.
So lets say three process A,B,C arrived where time take by A > B > C, in order to maximize this factor we can schedule C first as it takes least time and A at the last as it takes the most time.
Now the problem here is that unless C, B finish A can't do anything so this approach increases response time.
If the user is waiting for A's response of any kind they would have to wait for C, B to finish.
Response Time:
In order to make system more interactive, we can process all process partially so that user can at least see that the process is running and is responding.
We can have a time slice which is a interval after which we switch process and execute the next one.
So if A takes 10s, B takes 6s, C takes 2s, and our time slice/allocated time is 1s, then we will run all 3 processes in 3s which will make user feel that all process are interactive.
But one caveat over here is, if you look at time taken by each process, then C takes 2s while A takes 10s, with our time slice it would actually take 6s to finish process C whereas running it directly would have just taken 2s.
This is the trade off of optimizing for response time, we lose turnaround time.
SJF (Shortest Job First) optimizes for turnaround time while Round Robin uses allotment time and optimizes for response time.
MLFQ comes into picture
So how can we optimize for both turnaround time and response time? MLFQ can help us with it.
A MLFQ consists of multiple queues which are given different priorities as seen in the figure below.
The idea is that all jobs will be scheduled on the top most queue, and then will gradually be demoted to lower priority if they don't finish within the given time (aka allotment time).
This idea optimizes both allotment time and turnaround time, as jobs which are longer will be demoted down to lower queue so they don't block shorter jobs optimizing for turnaround time. We also give longer process some time (allotment time) which also optimizes for response time.
There is a catch, jobs which issues I/O basically are considered to be done within allotment time, but this causes problem as some bad program can issue I/O frequently causing it to stay on the same priority.
My experience while implementing MLFQ in xv6
When first writing code for xv6 you realize that you are modifying the kernel itself, which means there is no standard library, which means you don't have functions like malloc(), printf(), and most of the functions you use while writing user programs.
xv6 already provides implementation for malloc() as kalloc(), free() as kfree(), etc.
There is also this weird workflow that I had to get my head around, which was that I had to assume some of the events are automatically called and are not in my control like hardware traps (which entirely depends on implementation of risc-v cpu), also I studied how context switch actually happens and how data is copied into cpu registers and into memory.
There is also one thing not mentioned above, which is that, periodically all jobs are boosted to top queue, this is done to avoid starvation where if there are a lot of short jobs, longer jobs wouldn't get CPU at all.
I did this promoting by calculating the difference between CPU ticks when the jobs were last promoted to top priority queue.
Conclusion
This was a good lower level dive, almost at the lowest level I guess we can get just with software.
This was my attempt to implement a section of OSTEP (Operating System in Three Easy Pieces) which was cpu virtualization, up next is memory virtualization.
Will try to implement such more concept from OSTEP in this project.
Top comments (0)