CSE 330 - Operating Systems
Fall 2018
Project #1
Due Date: Feb 20, 2018

Groups: Groups of 2 are mandatory, and there will be a penalty of 40% for not having a group. Only 1 submission per group, i.e. there will be two names on each submission. 

It is essential that the project code works perfectly -- for the next projects to work. Hence the proper implementation is mandatory. Bugs in the Q routines have been the #1 cause for strange errors in the project, always. Careful that you get it right, else things will go bump later.

Overview:

For this project you are to write routines that perform standard queuing functions. The functions work on multiple queues, and structure each queue as a doubly linked, circular list (with a header/dummy element).

Data Structures:

The queue must be a circular doubly linked consisting of q-elements. The first q-element in the queue is a header, and this is a dummy element. The head pointer points to the dummy element. See the figure for a better explanation.

A queue consists of a head-pointer and a set of q-elements. A q-element is a structure, consisting of a prev and next pointer, and a payload consisting of 1 integer.

Functions:

The functions that you implement are:

1.     item = NewItem(); // returns a pointer to a new q-element, uses memory allocation

2.     head = newQueue() // creates a empty queue, consisting of one dummy element, returns the head pointer.

3.     AddQueue(head, item) // adds a queue item, pointed to by “item”, to the queue pointed to by head.

4.     item = DelQueue(head) // deletes an item from head and returns a pointer to the deleted item. If the queue is already empty, flag error.

5.     RotateQ(head); // rotates the q – the head element becomes the tail element and the element after the head becomes the head. Used for round robin scheduling.

Note: All the routines work on pointers. They do not copy q-elements. Also they do not allocate/deallocate space (except NewItem()). You may choose to implement a FreeItem(item) function – optional.

Implementation The routines should be implemented in C under the Linux operating system. If you are not familiar with Linux and/or do not have it installed. Please use an Ubuntu Virtual Machine. For more details/questions post requests on the discussion board.

All the above routines and data structures are to be placed in 1 file, called “q.h”. Do not include other files into this file. The test routines can be in “proj-1.c” and this will include q.h and other standard header files.

Testing

Write test routines that thoroughly test the queue implementation. Write a print routine that takes a head pointer and prints all the values of the payload field of the queue.

Use multiple queues. Pay special attention to deleting the last element of a q. One suggested test case: Add three elements to queue Q1, and then add 3 more to queue Q2. Delete elements from each q, one by one and print values till the queues are empty. Also, print the contents of the queues at each step. Make sure the Qs are empty. Repeat the above test again.

Further warning: Bugs in the Q routines have been the #1 cause for strange errors in the project, always.

Submission and Grading:

SUBMIT

Your project must consist of 2 files. (Usage of C is encouraged but if you use C++ the instructions would be similar)

1.       q.h   -- the functions defined above should be here, both definitions and body of the functions.

2.      proj_1.c (to test q.h)

 (make sure the compile command, “gcc proj_1.c” does the correct compilation).

The two files are to be ZIPPED into one zip or gzip file. The name of this file should reflect the name(s) of the people submitting (abbreviated, do not make it too long).

 Email the zip file to 430<dot>proj at gmail.

 Note: Grading will be done on Ubuntu. The entire project has already been tested for compatibility on Redhat (general), Ubuntu 11 and Ubuntu 12, and the same code works.