Section 1: Summary :

Section 1:

Summary:

This assignment will need routines written that perform standard queuing functions. The functions work on multiple queues, and structure each queue as a doubly linked, circular list.

Data Structure:

A queue consists of a head-pointer and a set of q-elements.

A q-element is a structure, consisting of a previous and next pointer, and a payload consisting of 1 integer. The header is a pointer to the first element of the queue. The head pointer is "null" if the q is empty.

Functions:

The functions that need implementing are:

1. item = NewItem(); // returns a pointer to a new q-element
2. InitQueue( &head) // creates a empty queue, pointed to by the variable head.
3. AddQueue(&head, item) // adds a queue item, pointed to by "item", to the queue pointed
4. to by head.
5. item = DelQueue(&head) // deletes an item from head and returns a pointer to the deleted
6. item
7. RotateQ(&head) // Moves the header pointer to the next element in the queue. This is
8. equivalent to AddQ(&head, DeleteQ(&head)), but is simpler to use and more efficient to implement.

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

a FreeItem(item) function.

Implementation and Testing

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 a 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.

Write test routines that thoroughly test the queue implementation. Use multiple queues. Pay special attention to deleting the last element of a q. Also make sure "RotateQ" is behaves properly (strange behavior of this routine means the insert/delete routines have bugs.)

Further warning: 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.

Section 2:

Summary:

Using the queuing routines (not all will be used) this project will implement the ability to run multiple functions as threads, using non-preemptive scheduling.

Step 1: TCB and context:

The queue items defined in your q.h file has to changed, to be of type TCB_t. The TCB_t and an initialization routine are provided in a header file tcb.h