The purpose of Phase 0 of the OS 502 project is to get you (the student) working on the project as early in the semester as possible with some data structure implementation required for Phase 1 and Phase 2.
In this phase you will write a simple C module to create and manipulate priority queues of processes. You will also write a unit test driver to demonstrate the abilities of your queue module.
You are strongly encouraged to follow the guidelines for Implementing Modules in C for this assignment. Your process queue abstract data type should be one module and your test driver should be a separate module. Your program structure and comment style should also meet the expectations set forth in the Program Grading Guide. Note that this assignment is independent of the code base used in phases 1 and 2. However, the module written for this assignment will be integrated with the rest of the code for the later phases, so be careful how you structure things.
For this assignment, you will need the following type definition:
/* process table entry type */
typedef struct
proc_t {/* plus other entries to be added by you later */
} proc_t;
Note that proc_t and state_t are global type definitions (or will be by the time you implement the full operating system) and are not specific to the process queue module. Accordingly, they should be in a separate global type header file.
This module creates the abstraction of queues of processes. We suggest the following implementation. The elements in each of the process queues come from the array procTable[MAXPROC] of type proc_t (shown above). The unused elements of this array (i.e. the elements currently not in any process queue) are kept on a NULL-terminated simple linked list headed by the variable procFree_h. We will refer to this list as the procFree list. The variables procTable and procFree_h are local to the process queue module (i.e. declared as HIDDEN).
The module should have the following externally visible functions. You may add additional public or private functions as you see fit.
void
Initialize the procFree list to contain all the elements of the array procTable. Will be called only once during data structure initialization.
proc_t *
allocProc()
Return NULL if the procFree list is empty. Otherwise, remove an element from the procFree list and return a pointer to it.
void
Return the element pointed to by p into the procFree list.
void
Append the element pointed to by p into the process queue where qp is a pointer to the pointer to the head (first element). Note the double indirection through qp and how we use this variable as a handle to refer to a queue. The element is added to the end of the queue. Update the queue handle if necessary.
proc_t *
dequeueProc(proc_t ** qp)
Remove the first element from the process queue whose head-pointer (not head) is pointed to by qp. Return NULL if the queue was initially empty, otherwise return the pointer to the removed element. Update the pointer to the head of the queue if necessary.
void
Insert the element pointed to by p into the process queue following element pos, where qp is a pointer to the pointer to the head (first element). Update the queue handle if necessary.
proc_t *
removeProc(proc_t ** qp, proc_t * p)
Remove the process table entry pointed to by p from the process queue whose head-pointer is pointed to by qp. Update the pointer to the head of the queue if necessary. If the desired entry is not in the defined queue (an error condition), return NULL. Otherwise, return p. Note that p can point to any element of the queue (not necessarily the head element).
typedef
void (* procFnPtr) (proc_t *);void
Apply the specified function fn to all elements of the process queue whose head-pointer is pointed to by qp. The function should be applied to all elements in queue order (from head to tail).
You are responsible for designing and building a test suite to unit test your process queue module. You must demonstrate the correctness and functionality of all of the specified interfaces.
Build a separate module that drives the process queue ADT. The driver should perform appropriate initialization and create multiple process queues and then allocate, add and remove processes and print the results.
Be sure and test boundary conditions, such as operations on empty queues as well as invalid parameters at the interface.
You will want to write a function that pretty prints the field values of an individual process data structure (proc_t) and you can use applyProc to get output of an entire queue. You also should write functions to print the process free area.
You should hand in both the driver and the process queue modules, as well as the output from the test run(s). Annotate/highlight the test output so the purpose of each test is clear.
You will be graded on: