Project Goal Set VI - Preemptive Multitasking and System Calls
Our systems aren't enough like UNIX yet. Let's fix that!
In this project part, you will finish up the implementation of a large set of system calls and you will implement multitasking and scheduling. So here we go!
The first step is to introduce locking into your system. We have gone over how this works in XV6, and you should be able to adapt a lot of code from there to make this work. Go back through your system and identify things that need to be locked, and get that going.
Establishing Process Storage
Study xv6's process table. You will be doing something similar, though some of your process table will be offloaded to the scheduler. In particular, the scheduler daemon will be responsible for managing the state of the processes. The other portions will be maintained in the kernel. Give some thought to how you will do this, and take care that you do not make any hasty and lamentable choices.
Kernel System Calls
The system calls that will be handled by the kernel are:
- read(fd, buf, n)
- write(fd, buf, n)
Let's go ahead and implement those now. The easiest are pipe, dup, read, write. (You should already have read and write). Remember that basically what you are doing is tying your buffers to your processes. You'll need to have some of allocation table to handle this. Perhaps it will be similar to the other allocators we have studied?
After you have this all in place, try your hand at implementing getpid() as it is trivial. Fork will require a bit more work, but it can basically be taken from xv6 with some level of adaptation. I suggest using the lazy page allocation technique that xv6 uses, and therefore will refer you to the excellent chapter about this. It's not that hard to set up, especially given that you can copy and paste the vast majority of it.
kill will just force a process to invoke exit.
sbrk will be trivial, so let's do that last so as to gain a false sense of security before we try to implement the scheduler daemon!
Testing Kernel Calls
At this point you should be able to write some init code that does the following:
- forks several children
- establishes pipelines
- read/writes from pipes and stdin and stdout
Write something to test this to give it a whirl.
Ok, something went awry! What was it? There is nothing to schedule anything! Let's fix that.
User Space Design
"The time has come", the walrus said, "to speak of many sorts! Of userspace - and schedulers - of daemons and ports!" (My apologies to Lewis Carroll.)
So now, here is where go micro. We are going to offload the following system calls to user space daemons:
- Anything pertaining to the disk file system. (That's the next project part.)
The way I did this was via means of ports. You may choose to explore a different design, and I encourage it, but I will say that this is likely the easiest way to go about doing this.
So what is a port? It's just our buffers! That's all!
I created the following ports:
- SCHEDULER_NOTIFY - The kernel writes notifications about processes here.
- SCHEDULER_COMMAND - The scheduler writes commands here.
- DISK_WRITE - Write to the disk.
- DISK_READ - Read from the disk.
These basically just correspond to stdin and stdout except they are magical! I put these at the beginning of my buffer space. So basically I have the following defined constants:
#define TTY_IN 0 #define TTY_OUT 1 #define SCHEDULER_NOTIFY 2 #define SCHEDULER_COMMAND 3 #define DISK_WRITE 4 #define DISK_READ 5
Care must be taken in your buffer allocations to never allocate these to anything but what they are intended. Of course, TTY_IN and TTY_OUT will be mapped to processes somehow, but the others won't necessarily do that.
In order for a user daemon to do its job, it must claim a port of some kind. To this end, I added the following system call:
Where port is one of the following constants:
#define SCHED_PORT 1 #define DISK_PORT 2
By my design, a process may only claim one port because what happens is the standard input of the process gets mapped to the side the kernel will write to (SCHEDULER_NOTIFY or DISK_READ) and the standard output gets mapped to the side the kernel will read from (SCHEDULER_COMMAND, DISK_WRITE). Note that these user daemons should retail STDERR, so they can write error messages to the console as they may need to.
Another possibility exists in that you could say the first process to start will be the scheduler and the next will be the disk driver. I don't like that because it force th user space to behave in a certain way. Of course, my little scheme is very trusting and may even lead to collisions in that any process can claim a port. We could fix that, but it probably isn't worth it since our little system is meant to be an educational toy rather than a full usable system!
The Scheduler Daemon
Ok, now the gloves come off. It's time to write a scheduler demon!
The first thing to do is to establish some sort of protocol. My protocol, and therefore likely yours to, works as follows. When the kernel creates a new process, it writes the message:
to the SCHEDULER_NOTIFY buffer. Of course, here PID and PARENT will be replaced with the PID and PARENT PID of the process. For instance, when init gets spawned the message will be something along the lines of:
Then when init forks:
The other messages that the kernel will send are:
WAIT:PID SLEEP:PID:SECONDS EXIT:PID
You get the idea! (I hope...)
So then the scheduler does the following. When it wakes up, it does some interior magic and then writes a RUN:PID to the SCHEDULER_COMMAND port. So for instance, when init is to be run, the scheduler writes:
Note that the scheduler will have to schedule itself from time to time! (more on this later).
Claiming the Scheduler Port
When the scheduler daemon claims the scheduler port, the kernel will respond by adding the scheduler's special buffers to the open files. What I did with mine was close and dupe my stdin and stdout, that way I just interact with standard I/O.
Scheduling User Space
The scheduler should maintain an array of running PIDs as well as the status and parent of each. An array of structs will do nicely. Next, you should have some sort of scheduling scheme. I like to just simply use round robin. Every time the scheduler wakes up, I do the following:
- Read my SCHEDULER_NOTIFY buffer until it is empty, processing each command.
- Update any processes which have become runnable/gone to sleep.
- Write run commands for all runnable pids, separated by newlines. Do that every time so you don't have to worry about doing something crazy (like forgetting the schedule yourself)
Scheduling from the Kernel Side
The kernel's side of this relationship works as follows:
- On every fork (including init), write the "NEW" message to the SCHEDULER_NOTIFY
- On every wait and sleep, write an appropriate message to SCHEDULER_NOTIFY
- At the end of every trap, read a line from SCHEDULER_COMMAND. If there is a RUN command, switch contexts (and proc) to the matching PID.
Note that if there is no run command, the kernel simply goes back to running the process that called it.
Putting it all together
Here are the final steps of this project part:
- Set up the programmable timer to give you regular interrupts (see XV6 on how to do this)
- Make your init process fork and run your scheduler in its child.
- Make several more forks in init. Use these to test your pipes and other system calls. Upon successful completion, you should see scheduling and IPC. (And stars, soooo many stars... but that's just from the stress.)