ECE344 Operating Systems: Assignment 1

ECE344 - Operating Systems

Assignment 1: Linked Lists

Due Date: Sunday, January 21, 2001, 11:59:59pm.

Objectives

In this assignment, you will need to write C code that creates and manages linked lists. (You will be able to make very good use of this code later in the assignments that will follow.) You will have to write code that tests the linked lists for correctness. Moreover, you should learn to manage the source code with make and learn how to control and examine the program and its data structures with gdb.

The purpose of this assignment is three-fold:

to write relatively simple C code (just to get back in the groove);
to learn how to use the gdb source-level debugger; and,
to learn how to use make to manage multiple source files.

Specification

Here, we specify the required functionality of the C program that you will be writing. In this specification, wherever we give detailed instructions you must follow them closely, but in places where the specification is vague you are free to use your own creativity to fill in details.

Consider the following data structure:

    typedef int ProcessId ;
    struct PD
      {
         struct PD * link ;
         ProcessId   pid ;
         int         priority ;
         int         waittime ;
         struct LL * inlist ;
      } ;

You don't really need to understand the purpose of this structure just yet but, briefly, each process that exists is represented in the kernel by a process descriptor (PD). This structure will later be expanded to be such a process descriptor. Much of the OS kernel operation simply involves moving PD's from one list to another, hence this assignment. What is important, however, is that a PD is in at most one such list at a time. The link field in the PD is used to link up the PD to the next one in the list.

You will need to create a function that can allocate a new process descriptor, as well as a function that deallocates one:

struct PD *allocPD() ;
int deallocPD( struct PD * ) ;

Since you do not know how many PD's will have to be allocated -- there could be many -- you must use dynamic memory allocation (malloc()) for this.

It is then useful to define a few functions that give access to some of the elements of a PD without having to know about the exact internal structure:

    ProcessId getPid( struct PD * ) ;
    int setPid( struct PD *, ProcessId ) ;
    int getPriority( struct PD * ) ;
    int setPriority( struct PD *, int ) ;
    int getWaittime( struct PD * ) ;
    int setWaittime( struct PD *, int ) ;

The set functions should return -1 (negative one) as an error code if the arguments are invalid. For now, ProcessId should be in the range [0..512], and Priority in the range [0..128].

Finally, you will need to define a structure to contain the head of a linked list. This structure must identify what type of list it is:

    typedef enum { UNDEF, L_PRIORITY, L_LIFO, L_WAITING }  ListType ;
    struct LL
      {
         ???? ????
         ListType  type ;
      }

For now, three types of lists containing PD structures must be supported:

Priority Lists: the PD's in the list are kept in priority order; the lower the value of priority, the closer to the head of the list.
LIFO Lists: for Last In First Out operation.
Waiting List: the total waiting time for a PD in the list is equal to the value of its own waittime plus the sum of the waittime's of all elements ahead of it in the list. For example if the elements have waiting times of 3, 3, 2, 5, and 27 respectively, then they are sorted as they are entered into the list in ascending order by the wait time (2,3,3,5, and 27) and stored in the list with the waittime entries being 2, 1, 0, 2, and 22, respectively.

Specifically, you will need to implement the following routines:

struct LL * CreateList( ListType type ): : allocates and properly initializes a list structure (using malloc()) and returns a pointer to it or NULL.
int DestroyList( struct LL *list ): : destroys list, whose pointer is passed in as an argument. Returns -1 if list is not empty, and 0 otherwise.
struct PD * DequeueHead( struct LL *list ): : dequeues the PD at the head of list and returns a pointer to it, or else NULL.
int PriorityEnqueue( struct PD *pd, struct LL *list ): : if list is a priority list, then enqueues *pd in its proper location. Returns -1 if list is not a priority list and 0 otherwise.
int HeadEnqueue( struct PD *pd, struct LL *list ): : enqueues *pd at the head of list. Returns -1 if list is not a LIFO list and 0 otherwise.
int WaitlistEnqueue( struct PD *pd, int waittime, struct LL *list): : if list is a waiting list, then inserts pd in its correct position assuming it should wait for waittime. The waittime values of the other elements in the list should be properly adjusted. Return -1 if list is not a waiting list and 0 otherwise.
struct PD * FindPD( ProcessId pid, struct LL *list): : searches list for a PD with a process id pid, and returns a pointer to it. If the element cannot be found, return NULL.
void DequeuePD( struct PD *pd ): : dequeues *pd from whatever list it might be in, if it is in one. Element inlist of the PD should be used to help efficiently identify which list a PD is in.

If a routine is to return an error code (e.g., -1) then it should ensure that none of the data structures are changed.

Finally, write code that tests each type of list and each of these routines. Make sure you've tested each aspect. Throughout, program defensively: assume others will write code that call your functions . . . and it's always safest to assume that other programmers are somewhat incompetent. ;)

Submission

In your home directory, create a directory called ece344; create a subdirectory called as1 and then in that directory create files with your code as follows:

main.c: should contain only the main function and nothing else at this time.
list.c: should contain the list functions.
test.c: should contain your testing code
defs.h: should contain definitions of structures, typedefs, and any defines you might use.

You should only submit source files. To submit the assignment you should use the submission procedure described in the policies section.