CSE 330 Project #1 Solution

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.

Data Structures:

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. 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 you implement 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 to by head.
4. item = DelQueue(&head) // deletes an item from head and returns a pointer to the deleted item
5. RotateQ(&head) // Moves the header pointer to the next element in the queue. This is equivalent to AddQ(&head, DeleteQ(&head)), but is simpler to use and more efficient to implement.


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



Part 2: (This part of the project is graded.)


Overview :
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. Note that TCB_t has previous and next pointers along with an ucontext_t field to store a thread context.

There is a routine in the tcb.h file called init_TCB, which is used to initialize a TCB for a new thread. The arguments to init_TCB are:

1. pointer to the function, to be executed
2. pointer to the thread stack
3. size of the stack

Step 1 consists of understanding tcb.h and changing the q-element type in your q.h file to TCB_t


Step 2:
Write a routine called start_thread and put it in a file called “threads.h”. Also routines defined in Step 3 will go into this file. You will need to include q.h into threads.h. The code for start_thread looks like:

void start_thread(void (*function)(void))
{ // begin pseudo code
allocate a stack (via malloc) of a certain size (choose 8192) allocate a TCB (via malloc)
call init_TCB with appropriate arguments call addQ to add this TCB into the “RunQ” which is a global
header pointer //end pseudo code
}

Step 3:
Write the routines called “yield” and “run” which cranks up the works (and put them in threads.h). These routines are defined as:

void run()
{ // real code ucontext_t parent; // get a place to store the main context, for
faking getcontext(&parent); // magic sauce
swapcontext(&parent, &(RunQ->conext)); // start the first thread
}

void yield() // similar to run
{ rotate the run Q;
swap the context, from previous thread to the thread pointed to by RunQ }

Step 4:
Write a driver program in a file called thread_test.c. Into thread_test.c.c include threads.h which includes q.h, which includes TCB.h, which includes ucontext.h.

Declare a global RunQ.

Write N functions with while loops (put a yield in each loop) counting the number of times each function is executed. There should be one global variable. Each function will have a local variable. Each function should increment the local variable by 1 and the global variable by the thread ID. If there were three functions in three threads (one in each thread), the first function will increment the global variable by 1 and the local variable by 1, the second function should increment the global variable by 2 and local variable by 1, the third function will increment the global variable by 3 and the local variable by 1. Each function should print the following before yielding

printf("This is %d th execution of thread X with global var value % d", local variable, global variable)

Where X can be 1 2 and 3 depending on the thread ID

Test cases

Each test case will have two numbers of the form
A,B

Here A is the total number of threads and B is the number of times each thread should be executed.

For example if a test case input is

2,3

You should output the following


This is 1 th execution of thread 1 with global var value 1

This is 1 th execution of thread 2 with global var value 3

This is 2 th execution of thread 1 with global var value 4

This is 2 th execution of thread 2 with global var value 6

This is 3 th execution of thread 1 with global var value 7

This is 3 th execution of thread 2 with global var value 9


To get the output simply use the following code in command line

gcc thread_test.c -o a.out
./a.out < test_case_file.txt > output_file.txt

If A = 0 then output No Threads
__________________________________

tcb.h

#include <ucontext.h>

typedef struct TCB_t { struct TCB_t *next; struct TCB_t *prev;
ucontext_t context;
} TCB_t;


void init_TCB (TCB_t *tcb, void *function, void *stackP, int stack _size) { memset(tcb, '', sizeof(TCB_t)); // wash, r inse
getcontext(&tcb->context); // have to get parent context, else snow forms on hell tcb-
>context.uc_stack.ss_sp = stackP; tcb->context.uc_stack.ss_size = (size_t) stack_size;
makecontext(&tcb->context, function, 0);// context is now cooked
}
SUBMIT:
Your project must consist of 4 files
1. TCB.h (uses ucontext.h) // this can be a copy of the file provided
2. q.h (includes TCB.h)
3. threads.h (includes q.h)
4. thread_test.c (includes threads.h) – must contain your name(s) in comments @ beginning
(make sure the compile command, “gcc thread_test.c” does the correct compilation).
All 4 files are to be ZIPPED into one zip or gzip file. The name of this file should reflect the name of the student (abbreviated, do not make it too long).

Submit in Canvas.

Note: Grading is on Ubuntu. It is in your interest to make sure the program compiles and runs in the target test platform.

Testing your code on grading test cases
Grading test cases are different from the test cases provided.
To test your code against grading testcases follow these steps:

Put the four files q.h tcb.h threads.h and thread_test.c in one zip folder with name YOUR LAST NAMEProject2.zip

For example BanerjeeProject2.zip. Do not put the files in a folder and zip. Gradescope expects that after uncompressing it only sees the files and not a folder inside.

Upload in gradescope.