The second phase of your operating system project introduces basic (non-preemptive) process control and a system call interface. Your system will create several processes and oversee their execution. Each process will have its own TSS to facilitate transfer of control between processes. This phase also introduces the code needed to implement system calls; that is, procedure calls from user programs to the operating system. This will be done by using a kernel task (operating as a coroutine) which receives and processes system call requests from users. Each system call triggers a task switch to the kernel task for processing.

System call interface

To create the mechanism by which the kernel task can be called on by user processes, we need to do the following:

1. Kernel task. This is in fact an extension of your main program. A TSS for the kernel has already been set up by the startup code (in boot16.c). After creating the first user process and yielding control to it, the kernel task enters a loop in which it accepts and processes system calls. It will get control by means of a task gate whenever a user makes a system call. After processing the call, the kernel performs the "iretd" instruction (return from interrupt) to return control to the calling user task. The basic logic of this loop is as follows:

while (1){
    Locate the calling task's TSS;
    Get the function number and arguments from the calling task's TSS; (The
        function number will be in the EAX register. Arguments (1 word each) will
        be in [EBP+8], [EBP+12], [EBP+16], etc...)
    Call the worker routine corresponding to the requested function; (Use a
        switch statement to divide control.)
    Put the return code in the calling task's TSS; Put the TSS selector of
        the task to return to in the BackLink field of the kernel's TSS. (This
        allows the kernel to return control to a task different than the one which
        called it.)
    Perform the iretd instruction;
    } 

Note: It is the kernel task's responsibility to verify that incoming parameters are valid.

2. All of our system calls will use INT 49. In order to cause the INT 49 instruction to cause a task switch to the kernel task, your system initialization (your main function) must create a task gate which references the kernel task, and insert it in the interrupt descriptor table (slot 49; that is, IDT[49]). The gate should contain:

a. Its selector field is the selector of the kernel TSS (SelKernel).
b. Its type is "32-bit task gate".
c. Its DPL is user level (i.e., ring 3). This allows it to be called by a user program.
d. It is "present" and a "system" descriptor.

Implementing Process Control

In this phase we are implementing basic system calls for process control, using the UNIX model. These are the fork, wait, and exit routines.

Data Structures:

Ready queue. The Ready queue is a queue of processes which are awaiting execution on the CPU. It can be implemented as a singly-linked list of the PCBs of the ready processes.

PCB. Add a "next" field as the first entry in the PCB, so that PCB's may be linked together. Add four additional data fields to each PCB: this process's exit code, the number of children of this process, the pid of this process's parent, and a queue of terminated children ("zombies"). Allow for two new process states: 2 = waiting for a child to terminate, 3 = terminated.

Code:

Modifications to the initialization routine (main program):

1. Initialize the ready queue.
2. Create the kernel task (described below).

Modifications to ProcessCreate:

Assign values to the new PCB fields described above. When the PCB has been initialized, insert it in the ready queue.

Queue ADT

Implement a Queue as a singly-linked list of nodes. Include basic access routines such as QInit, QEmpty, QLength, QInsert, and QDelete. Put the (application-independent) code for the queue ADT in separate files called queue.h and queue.c. Make the "next" field in a queue node the first field in the node. This will make it possible to use the queue routines for a variety of block types, including PCBs.

dispatch()

Dispatch is responsible for choosing the process to run and then transferring control to that process. with a yield_ operation. Processes will be dispatched in FIFO order. Dispatch performs the following steps:

1. Attach the running PCB to the rear of the ready queue. (Do this only if the state of the running process is ready.)
2. Dequeue a PCB from the ready queue. This becomes the running process.
3. Yield control to the running process. This is done by setting the BackLink field in the kernel TSS to equal the tss selector of the running process, then performing an iretd instruction.

getpid and getppid

These are two simple system calls which simply get the pid and ppid fields from the running PCB and pass them back to the caller.

fork -- create a child process

The fork function is called by a process (the "parent") to create a new process (the "child") which is a logical copy of itself. All processes in the system, except for the first one, are created by fork. To create the child process, fork allocates and initializes a new PCB, TSS, and LDT for the child. The value returned to the parent is the PIN of the child; the child receives a return code of 0. The action of fork is similar to that of the ProcessCreate function from the previous assignment, except that most of the contents of the PCB is copied from the parent process. In more detail, fork should do the following:

1. Locate an unused PCB in the process table and mark it as "ready".
2. Assign a PIN to the child process.
3. Allocate a block of memory space to use as the child's code/data/stack segment. The size of the segment will be exactly the same as the parent's.
4. Copy the contents of the parent's memory segment to the child's.
5. Save the base address and length of the segment in the child's PCB.
6. Allocate space for a kernel stack for the child.
7. Fill in the LDT for the child as you did in ProcessCreate.
8. Allocate space for a TSS for the child. Initialize it by copying the contents of the parent's TSS. The LDT and ESP0 fields must be modified to refer to the LDT and kernel stack of the child rather than the parent. Also, store 0 in the EAX field of the child's TSS (Why?).
9. Create global descriptors for the child's LDT and TSS.
10. Insert the child PCB in the ready queue.
11. Return the pin of the child to the parent.

yield -- yield control of the cpu to another process

A process can call yield in order to voluntarily give up the CPU; that is, cause a task switch to a different process. The kernel task accomplishes this by calling the dispatcher.

exit_(int exitcode) -- exit from a process.

The exit_() routine marks a process for removal from the system. It also must perform some interactions with its parent and child processes.

1. Set the "process state" flag in the running PCB to "terminated" and print a message containing the PIN of the process and its return code.
2. Locate the caller's parent, using the caller's ppid. (If ppid=0, go on to step 3.) If the parent is waiting on a child, copy the caller's PIN and exit code to the parent, wake up the parent, and set the caller's ppid=0. If the parent is neither terminated nor waiting, save the exit code in the caller's PCB and attach the PCB to the parent's zombie list (to prepare for a wait call by the parent).
3. If the caller has any zombie children, they should be deleted from the process table by calling cleanup. Set ppid=0 in any active children.
4. Transfer control to another process by calling dispatch.

int wait_(int*status) -- wait for termination of a child process

Wait allows a parent process to wait for termination of one of its children. There are three cases:

1. If the caller has no children (dead or alive), this is an error and wait returns -1.
2. If the caller has children, but none are terminated, the caller must wait. Set its state to waiting and call dispatch.
3. If the caller has at least one terminated child, delete one from the caller's zombie list. Obtain the zombie's pid and exit code to pass back to the caller. Call cleanup for the terminated child.

cleanup -- clean up after a terminated process

Cleanup may be called by either exit or wait to remove the resources from a terminated process. Cleanup should:

1. Free the memory space used by the kernel stack and tss of the process.
2. Release the two gdt entries used by the process.
3. Mark the process's PCB as unused.

Notes:

1. All pointers passed from a process to the kernel are relative to the process's base address. For the kernel to use or dereference these pointers, it must convert them to linear addresses by adding the process's base address.
2. The new code to implement processes should be in files process.h and process.c. The code to implement the kernel task belongs in kernel.c.