Sign up here
Design Review is graded as follows:
Data structures diagram
1 point. Draw the contents of the data structures for PCBs and locks.
Scheduling
1 point. Given that the threads below are listed in order, explain how the execution unfolds and why.
Kernel threads and scheduling design
1 point. Describe at a medium level how you will implement this part, with particular emphasis on how you are using your data structures.
Processes and system calls design
1 point. Similar to the above.
Mutual exclusion design
1 point. Similar to the above.
The threads:
lock_init(&lock); lock_acquire(&lock); do_yield(); lock_release(&lock); do_exit();
while(TRUE) {
do_yield();
}
do_yield(); lock_acquire(&lock); lock_release(&lock); do_exit();
lock_acquire(&lock); lock_release(&lock); do_exit();
You should start with the template code . Compiling this project is tricky, so we have provided you with a Makefile. If you type make, it will compile all sources and prepare an image floppy.img for use with bochs. We've also supplied a bochsrc that instructs bochs to use this image as a floppy. On the fishbowl machines, to load the image onto a USB stick, type make boot. On other machines, edit Makefile to use the appropriate device.
The kernel proper consists of a collection of kernel threads. These threads run in the most privileged protection ring, and their code is part of the kernel loaded by the boot block. Kernel threads share a flat address space, but they do not share register values or stacks.
After the boot block has loaded the kernel, it calls the function kernel.c:_start(). This function performs the setup necessary to run the tasks listed in tasks.c, including initializing process control blocks (PCBs) and allocating a kernel stack for each task. Since there is no fork() call, the number of tasks does not increase, and you are allowed and encouraged to allocate space for the PCBs statically, in the .data section. This is accomplished with the C declaration
pcb_t pcbs[NUM_TASKS]
Note that in this project, processes need twice as much context information as threads. It's OK to waste space on threads by letting the user context information go unused.
Stacks are STACK_SIZE bytes and are allocated contiguously at increasing addresses starting with STACK_MIN. Use the macro common.h:ASSERT() to enforce the invariant that all stacks lie in the interval STACK_MIN inclusive to STACK_MAX exclusive.
Since you are writing a non-preemptive scheduler, kernel threads run without interruption until they yield or exit by calling scheduler.c:do_yield() or scheduler.c:do_exit(). These functions in turn call entry.S:scheduler_entry(), which saves the contents of the general purpose and flags registers in the PCB of the task that was just running, calls scheduler.c:scheduler() to choose the next task, restores the next task's registers, and returns to it. (This may seem strange, but we'll devote part of the precepts to it.) scheduler.c:scheduler() chooses the next task to run in a strict round-robin fashion, and in the first round, the tasks are run in the order in which they are specified in tasks.c.
scheduler.c:scheduler() increments the global variable scheduler.c:scheduler_count every time it runs. Don't change this.
In future projects, processes will have their own protected address spaces and run in a less privileged protection ring than the kernel. For now, however, there are only slight differences between threads and processes. Unlike threads, processes are allocated two stacks: one user stack, for the process proper, and one kernel stack, for system calls made by the process. Moreover, process code is not linked with the kernel, although for this project it is part of the image loaded by the boot block.
There are two system calls: syslib.c:yield() and syslib.c:exit(). These correspond to scheduler.c:do_yield() and scheduler.c:do_exit() respectively. Processes cannot invoke the latter directly, since they don't know the address of these functions, and (in later projects), they don't have the requisite privileges to modify kernel data structures. This project uses a simple dispatch mechanism to overcome the former difficulty. kernel.h defines an address ENTRY_POINT, at which kernel.c:_start() writes the address of the function entry.S:kernel_entry(). To make a system call, syslib.c:SYSCALL calls the function at this address, passing the number of the desired call as an argument. entry.S:kernel_entry() saves the registers in a different part of the PCB than is used by entry.S:scheduler_entry(), restores the kernel stack and calls kernel.c:kernel_entry_helper(), which calls the appropriate function in scheduler.c. On return, entry.S:kernel_entry() restores the registers and returns to the user process. In later projects, this mechanism will become more complicated.
IMPORTANT: once you have transferred control to a process for the first time, the kernel MUST NOT write to its stack. It's OK for _start() to initialize the stack in some way.
lock.c contains three functions for use by kernel threads: lock_init(), lock_acquire(), and lock_release(). lock_init() initializes a lock structure; initially no thread holds the specified lock. In the event an uninitialized lock structure is passed to the other functions, the results are up to you. Your implementation must support multiple locks, and lock_acquire() must not block the thread when it is not necessary.
Threads call lock_acquire() to acquire a lock. If no thread currently holds the specified lock, it marks the lock as being held and returns. Otherwise it uses scheduler.c:block() to indicate to the scheduler that it is waiting for the lock and should not be run, and then it yields. When lock_release() is called by the thread holding the lock, it passes the lock to the process that has been waiting longest and unblocks it. If no processes are waiting, it marks the lock as being not held. When a thread is unblocked, all tasks that are currently neither blocked nor running should be scheduled first. The results of a thread attempting to acquire a lock it already holds or to release a lock it doesn't hold are up to you.
We have put a non-conforming implementation of mutual exclusion in lock.c so that you can write and test the kernel threads part in isolation. When you are ready to test your own implementation, change the constant lock.c:SPIN to FALSE.
Note: your lecture notes describe how to synchronize access to the fields associated with a lock. Since there is no preemption, if lock_acquire() and block() don't call do_yield() in the middle of manipulating data structures, you don't need to worry about race conditions as these functions do their job. In particular, it is not necessary to protect the scheduler data structures with a test-and-set lock.
The function util.c:get_timer() returns the number of instructions that have been executed since boot. Using util.c:print_int() and util.c:print_str(), use the first line of the display to show us the number of cycles required by a context switch between threads and between processes. We've left space in th3.c and process3.c for your code.
Please turn in your measurement code and have it run when I compile and boot your OS. We don't need or want you to state the results in the README.
For 1 point extra credit: using util.c:get_timer(), implement a scheduler that allocates CPU time fairly, together with some tests that prove to us that it's working. The grading criteria will be similar to that of the main assignment.
Processes --> Timing a process context switch
Kernel threads --> Mutual exclusion
Timing a thread context switch
Submit via Dropbox; please read the submission requirements in the official rubric; only one person per group should submit.