COS 318

COS 318 : Operating system
Fall 2003, Princeton University

Project 2: Non-Preemptive Scheduling

Important Dates:

Design review: 7 PM Monday, October 4, 2004
Due: 11:59 PM Monday, October 11, 2004

With the bootup mechanism built in the first project, we can start developing a operating system kernel. The goal of this project is to design and implement a simple multiprogramming kernel with a non-preemptive scheduler. Although the kernel will be very primitive, you will be dealing with several main mechanisms and apply techniques that are important for building multiprogrammed operating systems.

The kernel of this project and future projects supports both processes and threads. Note that the processes in this project are different from those in traditional operating systems (like Unix). Our processes have their own protection domains, but they share a flat address space. In the future, we will be providing processes with separate address spaces. Our threads are kernel level threads that always share the same address space with the kernel; they will never run in user mode. The kernel threads are linked together with the kernel, subsequently they can access kernel data and functions directly. On the other hand, processes use the single entry-point mechanism described in the lecture.

From now on, the kernel will use the protected mode of the x86 processors instead of the real mode. In this project, everything runs in kernel mode. You are required to do the following:

Initialize processes and threads including their stack and related kernel data structures.
Implement a simple, non-preemptive scheduler such that every time a thread calls yield() or exit(), the scheduler picks the next thread and schedules it. As discussed in the class, threads need to explicitly call yield() or exit(), in order to invoke the scheduler, otherwise a thread can run forever.
Implement a very simple system call mechanism. Since everything in this project runs in only the kernel mode, the system call mechanism can be a simple jump table. But the basic single-entry system call framework should be in place. You are required to implement two system calls: yield() and exit(). As previously mentioned, processes can make system calls, while threads can call scheduler functions directly.
Implement two synchronization primitives for mutual exclusion: lock_acquire() and lock_release(). Their semantics should be identical to that described in Birrell's paper. To implement lock_acquire() and lock_release(), the scheduler needs to support block() and unblock() for threads and processes. Blocking and unblocking is performed within the kernel - these are not system calls.
Measure the running time of a process/thread context switch.

You should use the code available in /u/cos318/2_pre/ as a starting point for your project. We provide you with 20 files. Don't be scared by so many files since you are already familiar with some of them; you will need to change only 6 of them (listed in bold face).

Makefile: A make file for you to compile with the right options.
bootblock.s: Code for the bootblock that handles arbitrary size image files, switches the machine into protected-mode, and creates a flat address space.
createimage.c: Your familiar Linux tool to create a bootable operating system image on a floppy diskette.
kernel.h: Interface for the kernel.
kernel.c: A template for you to write the implementation of the kernel.
common.h: Commonly used definitions.
lock.h: Interface for the synchronization primitives.
lock.c: Template for you to write the implementation of the synchronization primitives.
th.h: Declaration of threads in th1.c and th2.c.
th1.c: Code of the first kernel thread.
th2.c: Code of two kernel threads to test the synchronization primitives.
process1.c: A user process.
process2.c: Another user process.
scheduler.h: Interface of the scheduler, part of the kernel
scheduler.c: Template for you to write scheduler functions
entry.S: Template for assembly code that used by the kernel and scheduler
util.h: Declaration of useful routines like print_int() and get_timer().
util.c: Implementation of the functions declared in util.h.
syslib.h: Interface for the kernel functions available to processes.
syslib.c: Implementation of the functions declared in syslib.h.

Since our entire project will be using the USB flash disk, please do not read/modify the hard disk.

To signup for the design review, please use online signup form here.

Detailed Requirements and Hints

You need to understand the PCB (Process Control Block) and decide whether you would like to add additional items for your needs. The PCB provided has essential fields for a context switch. Since the processes and threads share the same address space in this project, the PCB can be very simple. Consider how data is saved during a context switch, and which stacks are used by threads and processes.

In the template file kernel.c, you need to implement _start() function to initialize the processes and threads you wish to run. For example, you need to know at which location in memory the code for the process or thread starts and where the stack for that process or thread is. Once the required information has been recorded in the appropriate data structures you will need to start the first process or thread. Note that each process is placed at a fixed location in memory. You can figure this out by looking at the Makefile.

Once a process is started it will run until it gives up execution by calling yield() or exit(). The scheduler than decides what process to run next. This process is executed as a return from its yield()call. Consider what should happen when a process exits or makes an invalid system call. You need to understand how a thread's state changes upon calling synchronization primitives.

The system call mechanism should be a single entry mechanism as discussed in the class. The main difference is that you are not making an entry by using the INT instruction to trap into the kernel; you will simply make a procedure call instead. This is because there is no user-mode processes in this project. In order to make this mechanism work, you need to understand the stack frame and the calling sequence.

The synchronization primitives lock_acquire() and lock_release() are for threads. They are not designed for processes to synchronize; processes cannot share data structures. On the other hand, they need to deal with the PCB data structures to block and unblock threads. An important step is to figure out how to queue blocked threads. Although it is nice to implement the synchronization primitives in the way that works with a preemptive scheduler, it is not required in this project.

Finally, once all this is up and running we would like you to measure the time taken for a context switch in your system. To do this you can use a provided function get_timer() to get the CPU clock ticks. This call contains basically an one-line assembly instruction that returns the number of clock cycles that have passed since the processor was booted. Note that the value returned is a 64-bit quantity (unsigned long long int). Also, notice that this function will only run on Pentium or newer processors.

Extra Credit

You can earn 1 extra point in this project.

To receive an extra credit, your implementation needs to keep track of the user and system time used by each process. When a process exits, this usage should be printed (much like 'time' on any UNIX system). You will be measuring the time in clock cycles using the get_timer() routine that you used to measure the time of a context switch. (1/2 point).

For the remaining 1/2 point extra credit, change the scheduler so that is tries allocating relatively even CPU time to each process or thread. The scheduler can implement a strategy trying to achieve fairness, subject to processes giving up control. (1/2 point)

Useful Resources

Object file format
- Executable and Linkable Format (ELF)

Assembly programming resources
- A Guide to Programming on Intel IA32 PC Architecture
- Using as, the GNU Assembler

Official Intel IA32 manuals

Reference books
- Protected Mode Software Architecture, by Tom Shanley, MindShare, Inc. 1996.
  This book rehashes several manuals by Intel if you are reading the Intel manuals above.
- Undocumented PC, 2nd Edition, by Frank Van Gilluwe, Addison-Wesley Developers Press, 1997. This book was written for hard-core PC software hackers. It has information about various Intel architectures (8086, 286, 386, 486, Pentium and Pentium Pro) and PC systems. No need to read this book to do the projects.
- C Programming: A Modern Approach, K. N. King, Norton & Co. 1996.
An Introduction to Programming with Threads, Andrew D. Birrell
M-x info under Emacs. Then : gcc -> C extensions -> Extended Asm

Design review

For the design review, you need to have figured out all the details including the PCB data structure, the call sequence executed during a context switch or system call, how process state is saved and restored, etc. In other words, you should understand the role of each function, being ready to implement it.

Before you come to meet the TA you should prepare for a brief 10 min presentation on a piece of paper. Only oral presentation is not acceptable.

Submitting Programming Assignments

Submit your final solution electronically using the following command:

/u/cos318/bin/318submit 2 README entry.S kernel.c kernel.h threads.c threads.h scheduler.c scheduler.h <other files>

The submit command copies your files to the directory /u/cos318/submit/UserLogin/number and lists all the files that you have submitted for assignment number. UserLogin is your user account name. If you execute submit after the project deadline, your files are placed in directory number_late. You can run submit more than once, and you can submit partial lists of files. Each group needs to submit only one copy. This means that only one of you needs to submit.

CS318 Staff