Assignment/Kern 1 (Procs)

From WoxWiki

This is the first of two parts of the first CS169-only project in this course. CS167 students should be working on UThreads instead. There is another page with an overview of the full kernel project. The second part to this project deals with device drivers.

Please remember to read the course Programming Guide for good style guidelines.

Introduction

If you are reading this we assume you have already read the general kernel page and the Weenix/Guide/Hackers Guide section on processes and threads.

Note that you must complete the two parts of kernel in the order they are being given to you. Device I/O (necessary for drivers) depends upon then Xen bus thread. Which (as the name suggests) requires threading support in order to work.

For this first assignment you will be adding the following features to Weenix:

• Threads and processes (one thread per process)
• Scheduling and context switching
• Exiting
• Synchronization primitives

Each of the functions you need to implement will be marked with the NOT_YET_IMPLEMENTED macro.

For this project your work should be concentrated in the kernel/ sub-directory (that is where all the files you need to edit are). You might also want to take a look at the memcore/, it contains some of the core memory management functions of Weenix which you will be using throughout the semester. This directory does not belong to any particular project (although you will need to add some code to it when you get to VM).

Booting

Most of the boot process is handled for you by Xen and the TA code. Xen gives us an initial machine context and calls the start_kernel function, which initializes the TA provided support systems, and calls your bootstrap function in main.c.

At this point we are still in the boot process, which means that we don't have a context in which to properly execute. We cannot block, and we cannot execute user code. The goal of the bootstrap function is to ultimately set up the first kernel thread and process which should start executing the idleproc function. This should be a piece of cake once you've developed and implemented the functionality for threads and the scheduler.

Inside of idleproc is where all of your test code will be placed. When your operating system is nearly complete, this will execute a binary program in user mode, but for now be content to put together your own testing system for threads and processes.

Functions you will need to write in kernel/main.c:

    void bootstrap (void);
    void idleproc  (long arg1, void *arg2);

Processes

Functions you will need to write in kernel/proc.c:

    void proc_init       (int i);
    int  proc_kern_alloc (int pid);
    int  proc_alloc      (void);

Threads

There are a few important restrictions on our threading model which makes it much easier to write this kernel:

• Each process only had one thread associated with it.
• There is no preemption in Weenix (all threads run until they explicitly yield control of the processor).
• Weenix is only running on one processor.

There are some hacks regarding context creation when writing kthread_init. See the comments for the functions as well as the Hacker's Guide for details. These most likely will not come up until VM. Don't worry about them now.

Note that you may need to implement the scheduler in order to understand and write some of these functions.

Functions you will need to write in kernel/kthread.c:

    int        kthread_init         (proc_t* proc, kthread_func_t func, long arg1, void *arg2, int kernel);
    void       do_thr_cancel        (kthread_t *kthr, int status);
    void       do_thr_exit          (int status);
    int        kthread_copy         (proc_t *old_proc, proc_t *new_proc);
    void       sleep_on             (ktqueue_t *q);
    int        cancellable_sleep_on (ktqueue_t *q);
    kthread_t *wakeup_on            (ktqueue_t *q);

Scheduler

Once you have created processes and threads, you will need a way to run these threads and switch between them. If you choose to write a yield function it is advisable to name it sched_yld() or something similar, as the name sched_yield() is taken by a Linux system call.

Functions you will need to write in kernel/sched.c:

    void sched_switch        (void);
    void sched_make_runnable (kthread_t *thr);

Exiting

After finishing this section you should make sure that you can have multiple processes with multiple threads running, and that exiting threads and processes works correctly.

Functions you will need to write in kernel/exit.c:

    void  proc_exit (proc_t *proc, int status);
    pid_t do_wait   (int *status);
    void  do_exit   (pid_t pid, int status);

Synchronization Primitives

Since the kernel is multi-threaded, we need some way to ensure that certain critical paths are not executed simultaneously by multiple threads. Once mechanism you will need is the mutex. Feel free to implement semaphores (or condition variables) as well if you so desire, though they are in no way necessary to have a functioning kernel.

Functions you will need to write in kernel/kmutex.c:

    void kmutex_init             (kmutex_t *mtx);
    void kmutex_lock             (kmutex_t *mtx);
    void kmutex_lock_cancellable (kmutex_t *mtx);
    void kmutex_unlock           (kmutex_t *mtx);

Xen Bus Daemon

We mentioned in the introduction the reason you must complete this part of your kernel before writing device drivers is that there is a kernel thread called xenbusd which must be running in order for device I/O to work. You might be asking yourself, "How am I going to get debug output about my threads into a terminal without a terminal driver or even device I/O?". The answer is that we are cheating at first. Xen provides a special debug console which is what you will be using to see your debug output. Your debug messages will be passed directly to the Xen hypervisor via a call intended for debugging and then printed to your terminal. Therefore an important part of making sure your processes and threads are working is making sure that xenbusd is working properly.

To turn off our use of Xen's debug statements take a look in your Makefile.defines file. You should see a few lines that look like this:

    USE_CONSOLE_IO = 1
               VFS = 0
              S5FS = 0
                VM = 0 # Enable this first
                FI = 0 # Enable this second

You want to change the first line such that it reads:

    USE_CONSOLE_IO = 0

Note that the rest of the lines we listed are the lines you will need to change as you progress through the semester and wish to compile more components of Weenix (as you can see they are named after their respective project names).

Once you make this change you will need to run:

    $ make clean

to make sure you clean up any binaries created using the old flags. When you run your Weenix again you should get 4 terminals. 3 are intended to correspond to tty devices for which you are about to write drivers, the last is the debug console where your debug output is printed. Since you have drivers yet you will be unable to test writing to the consoles, but assuming you have done thorough testing you are probably in good shape. Note that xenbusd is rather complicated and would be a very bad test case for your threading code, you should not make this change until you are confident your code is well tested.

Closing Remarks

We know that this assignment can seem overwhelming. It is also possible that this is your first exposure to a large code base. You should definitely spend some time poring over the existing code, thinking about what it is that we are asking you to implement. For a richer understanding, it will helpful understand where your code fits into the existing support code.

Don't forget to hand in once you finish.

Finally, be sure to ask questions. Your mentor TAs worked through this last year and over the summer. If you are not sure how something works or why, ask! Constant communication is the key for this project.

Good Luck!