CMSC 412

Project 2: Multiprogramming, Part I

Multiprogramming is a technique in which the CPU switches between running multiple processes that are fully or partially in memory at the same time. In this project, you will implement a small, non-preemptive multiprogramming system for an IBM compatible PC. The kernel will support three system calls, as described below. You will demonstrate your implementation by running several concurrent processes.

These are suggested file names. Some of the files will be extended from the ones you wrote for project 1.

• cmsc412.c, cmsc412.h
  There has been a slight modification of Cprintf() . This function now calls Put_char() instead of putch() . This requires screen.h to be included since Put_char() is presumed to be defined in this file. You should get a new copy.
  Also, look at Mod_int and use that instead of asm CLI and asm STI.
• keyboard.c/keyboard.h The keyboard interrupt handler goes here.
• screen.c/screen.h The screen handler, Put_char(), etc.
• queue.c/queue.h Queue related functions.
• codes.h: Also, from project 1.
• makefile: Sample makefile.
• kernel.c / kernel.h System calls, and System_service
• main.c New version of main for this project.
• proc.c Sample proc.c used to test. You should write your own versions as well (for testing your code).

In this project, a process will execute the code of a C function. Sample process code can be found in proc.c. You will compile the kernel (in kernel.c) and user processes (in proc.c) separately, but link them together. This means that if you pass the name of the function (which is a function pointer), the kernel will know the address of this function. If the kernel and user process code had not been linked, then the kernel would not be able to resolve the addreses.

Each process will have useful information concerning the process kept in a PCB (process control block), which is a data structure. A PCB will be created during the initialization of a new process. You will need to determine what information the PCB structure should hold by reading this description carefully.

During its lifetime, a process can go through many states. For this project, a process is either running, or it ready to run. At most one process can be running at any given time. Normally, a process can also exist in other states (blocked, terminated, etc.), but you only have to concern yourself with the two states mentioned.

To indicate which state a process is in, you will place the PCB associated with a given process on a queue associated with the state of the process. For example, if a process is currently running, its PCB will be in the run queue. Since at most one process can be running at any given time, at most one PCB can be in the run queue. The run queue should be implemented as a pointer to a PCB. It should be noted that the run queue is not a true queue (i.e., there's no real enqueueing or dequeueing) despite its name.

If a process is not running, then it is ready to run. Processes that are ready to run have their PCBsa in the ready queue (which is a queue). When the running process yields, the PCB on the run queue will be removed and then enqueued onto the ready queue. A new PCB will then be dequeued from the ready queue and placed on the run queue, and that process will be activated. Selecting a new PCB from the ready queue and placing it on the run queue will be the responsibility of the function, Scheduler.

A system call is a request for an operating systems service. Each system call carries out some specific task. Your kernel will support three system calls:

Imagine you entered the following in your favorite shell. What would happen?

% a.out foo bar

   

The shell (whch is a user-level program) would parse this input. In particular, it would determine that there are three arguments. The shell would create an array of pointers to strings. In this case, the array would contain three pointers which would point to the strings: "a.out", "foo", and "bar". We will call this array the "argv" array because these are the arguments that can be accessed from the argv array in the main() function of a.out.

The shell would then make a system call requesting that the kernel create a process from the a.out executable. At the very least, the shell should pass the following arguments to the system call: the number of arguments, and the "argv" array. While you will not write a shell, you will write the system call. This system call will be called Proc_start. Because there is no shell to read and parse a command line, you will need to hardcode the "argv" array as shown in the sample proc.c.

Among the many tasks that the kernel performs when initializing a new process, it must create a new copy of the "argv" array. This includes the array itself as well as the strings that the array points to. It must also set up the stack for the child process so that the child process can access "argc", the argument count, and "argv". This is similar to what happens in programs that you write. You are allowed to access argc and argv from main().

Proc_start has three arguments. The first is the name of the function you wish the newly created process to run. Recall that in C, the name of a function is a pointer to that function's code. You will need to write the functions used as processes in proc.c (or use the ones provided). The second argument is the number of parameters in the argv array. This always has a value greater than or equal to 1, because the name of the command (e.g., a.out) is always the first argv parameter. In C, this parameter is commonly called "argc" for the argument count. The third argument is the argv array which was described earlier.

To illustrate, if you wanted to create a process that runs the function foo with arguments 23 and cat, you would create an array of three elements whose first element contains a pointer to the string ``foo'', whose second element is 23 converted to a string, and whose third element is the string, ``cat''. Use Safe_malloc() to allocate the space.

This array is then passed as the third argument to Proc_start(). Proc_start() will generate interrupt 0x62, which will invoke the kernel. Within the kernel, you will need to determine that Proc_start() was called, and then make a copy of the argv array for the new child process that is about to be created. There is a reason for making this copy.

In a protected environment, processes usually have distinct address spaces. In particular, a parent process can not access the addresses of a child process and vice versa (this is not true in DOS, because processes can access any address, there is no real mechanism to protect a range of memory addresses for a given process). The reason for doing so is to prevent processes from acting maliciously. One tenet of operating systems is that a process should not be able to (easily) interfere with another process, and writing into another process's address space constitutes interference.

Suppose the kernel did not copy the "argv" array, and the child process could somehow point to the parent's copy. If the parent process terminates, its copy of the array will be freed (processes that are terminated have its resources, including memory, freed). If the child process accessed this array, it could contain garbage. We assume that a child process is independent of the parent process, i.e., if a parent process terminates, the child continues to run.

Proc_start should return the process ID of the newly created child process.

Proc_term() terminates the current process. No arguments are passed. The kernel should free up memory used by the process (stack space, PCB, etc.) This is typically not called within the user program. See further on to see how Proc_term is actually used.

Yield() is called when the running process wants to temporarily give up use of the CPU. The kernel will move the PCB from the run queue to the ready queue, then select a new PCB from the ready queue, place it in the run queue, and activate the new process. Note that only the running process can call Yield(). For this project, a process voluntarily yields control of the CPU by calling Yield(), otherwise, it will run until completion when it is trivially pre-empted. The next project will allow the kernel to forcibly preempt a process, and switch to a new one.

The various system calls are "implemented" as functions. However, the functions are very simple. They basically generate an interrupt. Specifically, a number identifying the specific system call is placed the AX register. Then, a software interrupt is called (say, 0x62). That's usually the entire function (return values should be placed in AX). The kernel code (which is hooked at interrupt 0x62) does most of the work.

Normally, either the process making the system call or the kernel code must save the state of the user process prior to executing kernel code, then restore the state upon completion. However, if you write the kernel routines in C using a Borland ``interrupt'' function, the CPU environment will be preserved automatically by the compiler.

What happens to the invoking process depends on which system call was made. For Yield(), the current state is saved, the address of a Dispatch function is pushed on the stack, the stack pointer (ss:sp) is saved in the running process's PCB, the PCB is moved to the ready queue, and the scheduler is invoked to select a new process to run. To restore a yielded process, you need to restore the stack pointer (the one saved in the PCB), and call RETF, which will call the Dispatch function which restores the state of the process, and starts it running again.

For Proc_start(), a new PCB and stack are created using Safe_malloc, a new unique process ID is generated for this process, the PCB is added to the ready queue, and its process ID is returned to the calling process by altering the _AX value in the calling process's preserved CPU context. Accessing the SAX parameter from the interrupt handler's argument list (to be discussed momentarily) will do this. Note: Proc_start() only creates a new process (and PCB) and places the PCB in the ready queue. It does not run this newly created process! The scheduler eventually handles this.

If the requested system call is Proc_term(), then the process is deactivated by removing its PCB from the run queue, then returning first its stack space, then its PCB to the memory pool via Safe_free. The "argv" array must also be freed. The CPU scheduler is then invoked to select a process from the ready queue to run next.

The stack for a newly created process will appear as follows (note: SP value is for a stack of size 2K = 0x400):

Note: the stack looks as if Proc_term() called the new process; thus when the process finishes, it will automatically invoke Proc_term(). This is a rather interesting solution to the problem of ``How do you terminate a process that does not call Proc_term()?''. Set up the stack in such a way that it appears that Proc_term() called the function that is being passed to Proc_start(), and when that function complete, Proc_term() will execute. This will perform various cleanup duties needed to properly terminate a process.

Dispatch() is a function that uses the ``asm'' feature. Since every C function creates its own stack frame, you first have to destroy it by the following asm instructions:

Then pop off the registers (in the order shown above) and call the IRET instruction.

Note that the stack frame of any process on the ready queue will look similar to that shown above. In particular, the stack frame will contain the ``IP of dispatch()'' through ``flags'' fields.

The following code is an outline for the code that will be included in kernel.c. This file should include System_service plus all of the system calls avaiable to the user programs ( Proc_start, Proc_term, and Yield) as well as the Dispatch() function all).

For those of you who are interested, the difference between Borland 4.5 and earlier versions is that the register DS would be pushed after sflags. That is, after sflags, you would add sds2, then sbp2. However, it is assumed that you will use Borland 4.5 for this project.

It may seem odd that System_service(), which is basically an interrupt handler, has an argument list. After all, an interrupt is not called like a normal function with arguments passed. The above is really a trick. When Proc_start is called, and interrupt 0x62 generated, the stack will look exactly like the arguments being passed to System_service with sbp at the top of the stack, an argv at the bottom, and in the order listed as shown in the formal parameter list. This makes it easier to access arguments on the stack without having to calculate the locations of all the registers on the stack.

The following function is at vector 0x63:

This interrupt will handle the yielding of a process. It leaves the stack of the yielding process with the address of Dispatch() on top. The role of Dispatch() is to pop all the register off, and restore the state of the yielded process, when this process is scheduled to run.

Note that when the yielded process is scheduled to run, the stack pointer will be reset to the value saved in the PCB of this yielded process. By calling the RETF assembly instruction, the CS and IP pointer to by the stack pointer will be loaded as the new CS and IP, and this will be the address of Dispatch(), which pops the registers and does an IRET instruction. The process then continues executing in System_service(), right where it left off, when it was yielding. System_service() then pops the registers (again; this is done automatically if it is an ``interrupt'' function) and returns to the process.

Calling RETF will cause the hardware to pop 4 bytes off the stack. The first two bytes will be placed in IP, and the second in CS. RETF stands for "far return" and is basically how a function returns to the function that called it. However, this mechanism can also be thought of as jumping directly to the address on the stack. Note that RETF does not care if the values on the stack are legitimate addresses. It will take the 4 bytes off the stack, stuff it in CS and IP, which effectively jumps to that address. Either you or the compiler are responsible for making sure the address is correct.

IRET is typically called during a return from an interrupt. During an interrupt, the flags register, and the program counter (cs:ip) are pushed on the stack. IRET undoes this action by popping off 6 bytes. The first 4 bytes are still placed in CS and IP as before. The last 2 bytes are placed in the FLAGS register. This register records the interrupt status (enabled or disabled) as well as the status of the last instruction executed (typically, for use in branch instructions).

The scheduler will use FIFO scheduling to determine the next process to run. Once the process has been chosen, it is added to the run queue and dispatched by loading ss:sp from the PCB and doing a RETF instruction.

The first time the scheduler is run, it should push the BP onto the stack, then save the SS and SP into static variables. Later, when it finds that there are no more processes to run, it should restore SS and SP from those variables, pop BP, and return. At that point, execution will resume in main after the call to schedule. You will write a function called Scheduler() to handle this. Place this in kernel.c.

Since I/O operations are not implemented as system calls, no I/O-computation overlap will be achieved by this project. Nonetheless, you must use the keyboard and screen drivers from Project 1 to perform some I/O, or there would be no way to see your processes working. For Put_char(), the lack of an ``I/O wait'' state is of little consequence, since screen operations are memory-mapped. With Get_char(), however, the lack of the ``I/O wait'' state hurts performance. As in Project 1, Get_char() must not busy wait.

Without preemption, Get_char() and Put_char() can be used as desired without the need, for example, to exclude other processes when printing a line of characters. Likewise, a line of characters can be read in with confidence that they will be delivered to the same process.

The main() routine that you will write constitutes the kernel initialization code. A number of actions must be taken to set up the kernel. First, the interrupt vectors for the keyboard driver and kernel routines must be saved (i.e., the old DOS versions kept around), then re-vectored to the routines you have written. An initial process must be created, as described below. Finally, main() will invoke the scheduler.

The initial process, called Init(), is responsible for starting the other processes. Init() sets up the parameters for each process, invokes Proc_start() to start the other processes running, prints their process ID's with Cprintf() (which calls Put_char()), then terminates. Link with the file cmsc412.c in order to use a version of Cprintf() that calls your Put_char().

Recall that Proc_start() will only create a PCB and the stack for a new process. You will still need to call the scheduler to start up the Init() process. Init() should take argc and argv as arguments.

All user processes, including the Init() process, should be included in a separate module titled proc.c. You can test your kernel by running a small number of processes concurrently, each of which first prints its arguments, then loops a small number of times. Each loop should produce a line of output that identifies the process for each loop iteration, then invokes Yield() to allow the next process to run.

We will test your programs by running your test routines, then by running our own Init() and a number (< 10 concurrently) of other processes. Note that the names and parameters for the three system calls (Proc_start, etc.) must be designed as specified, or our test procedures will not run correctly.

Your diskette should have all files necessary for execution and compilation, and only these files, available on the root directory, including a makefile. The only specified file names for this project are makefile for the makefile and proc.c for your Init() and user processes.

Your file proc.c MUST be compiled separately and linked with the kernel. Including proc.c in your kernel code is not acceptable. Also, your OS must create Init() as the initial process (using Proc_start() ). No other name may be used.

Comments and indentation are important. Make your code readable! Include a README file that lists the various files used, and a brief description of each of the functions used in each of the files. Also, add any comments that you feel the TA needs to know, especially where you feel there might be confusion, or where you have chosen to implement some part of your code in a different manner from the one specified.