Scheduling User-Level Threads and Comparing Them With Kernel-level Threads

code.zip

Home >Computer Science homework help >Scheduling User-Level Threads and Comparing Them With Kernel-level Threads

Kernel_Level_Thread/functions.c

#include "functions.h" void *counter(void *arr) { long tid; pid_t id; int temp; id = syscall(SYS_gettid); int *ar = arr; struct timespec begin; struct timespec current; clock_gettime(CLOCK_MONOTONIC, &begin); long long int rf = 0; while (1) { rf++; clock_gettime(CLOCK_MONOTONIC, &current); if (((long long)current.tv_sec - (long long)begin.tv_sec) >= 10.0) { break; } } temp = (int)id%100; printf("temp = %d\n", temp); ar[temp] = rf; pthread_exit(NULL); } void *sleeping(void *arr) { long tid; pid_t id; id = syscall(SYS_gettid); int *ar = arr; int temp; struct timespec begin; struct timespec current; clock_gettime(CLOCK_MONOTONIC, &begin); long long int rf = 0; while (1) { rf++; clock_gettime(CLOCK_MONOTONIC, &current); if (id%2 == 0) { if(((long long)current.tv_sec - (long long)begin.tv_sec) == 5.0) sleep(3); } if (((long long)current.tv_sec - (long long)begin.tv_sec) >= 10.0) { break; } } temp = id%100; ar[temp] = rf; pthread_exit(NULL); }

Kernel_Level_Thread/functions.h

#define _GNU_SOURCE #include <pthread.h> #include <stdio.h> #include <stdlib.h> #include <unistd.h> #include <sys/types.h> #include <sys/syscall.h> #include <sys/resource.h> #include <time.h> void *counter (); void *sleeping();

Kernel_Level_Thread/kt_test.c

#include "functions.h" #include <string.h> #define NUM_THREADS 85 int main(int argc, char const *argv[]) { pthread_t threads[NUM_THREADS]; int rc; long t; int *arr; void *tab[] = {counter,sleeping}; int flag = -1; arr = (int *)malloc(100 * sizeof(int)); long long int sum = 0; for(int i=0 ; i<100 ; i++) arr[i] = 0; if(argc<2) { printf("Argument missing !!\n"); return -1; } flag = !(strcmp(argv[1],"counter"))? 0 : 1; printf("Code under execution .. \n"); for(t=0;t<NUM_THREADS;t++){ rc = pthread_create(&threads[t], NULL, tab[flag], (void *)arr); if (rc){ printf("ERROR; return code from pthread_create() is %d\n", rc); exit(-1); } } for (t=0 ; t<NUM_THREADS ; t++) pthread_join(threads[t],NULL); for(int i=0 ; i<100 ; i++) { printf("arr[i] = %d \n", arr[i]); sum += arr[i]; } printf("Counter = %lld\n",sum); pthread_exit(NULL); return 0; }

Kernel_Level_Thread/Makefile

# HEADERS = program.h headers.h default: kt_test # program.o: program.c $(HEADERS) # gcc -c program.c -o program.o functions.o: functions.c gcc -c -std=gnu99 -pthread functions.c -o functions.o -lrt kt_test: kt_test.c functions.o gcc -g -std=gnu99 -pthread kt_test.c functions.o -o kt_test -lrt clean: -rm -f kt_test functions.o

Kernel_Level_Thread/threads.c

//User level threads library // INCLUDES #include <stdio.h> #include <stdlib.h> #include <signal.h> #include <string.h> #include <unistd.h> #include <time.h> #include <sys/time.h> #include "threads.h" // DEFINES #define SECOND 1000000 #define MAX_NO_OF_THREADS 100 /* in any state */ #define STACK_SIZE 10000 //4096 #define TIME_QUANTUM 1 // Black box code //////////////////////////////////////////////////////////////////////// #ifdef __x86_64__ // code for 64 bit Intel arch //typedef unsigned long address_t; #define JB_SP 6 #define JB_PC 7 //A translation required when using an address of a variable //Use this as a black box in your code. address_t translate_address(address_t addr) { address_t ret; asm volatile("xor %%fs:0x30,%0\n" "rol $0x11,%0\n" : "=g" (ret) : "0" (addr)); return ret; } #else // code for 32 bit Intel arch //typedef unsigned int address_t; #define JB_SP 4 #define JB_PC 5 //A translation required when using an address of a variable //Use this as a black box in your code. address_t translate_address(address_t addr) { address_t ret; asm volatile("xor %%gs:0x18,%0\n" "rol $0x9,%0\n" : "=g" (ret) : "0" (addr)); return ret; } #endif //////////////////////////////////////////////////////////////////////// // Global variables thread_queue_t *thread_list; /* the list of all threads */ thread_queue_t *ready_list; /* the list of all ready threads */ thread_t *current; /* the current running thread */ int next_thread = 0; /* Used for assigning IDs */ int scheduling_type; /* Scheduling type 0 = RR, 1 = LOT */ int clean = 0; /* if in cleanup, exit out of dispatch */ unsigned start_time = 0; /* Time a thread is started */ extern void thread_enqueue(thread_t*, thread_queue_t*); // enqueue t to back of queue // dequeue from front of queue extern thread_t* scheduler(); //implementation of thread scheduler, RR and LOT int CreateThread(void (*f) (void), int priority) { // Return -1 if fail if (thread_list->size + 1 > MAX_NO_OF_THREADS) { printf("Too many threads\n"); return -1; } thread_t *thread = malloc(sizeof(thread_t)); thread->status = malloc(sizeof(status_t)); thread->stack = malloc(STACK_SIZE); thread->status->id = next_thread; thread->priority = priority; next_thread++; thread->status->state = READY; thread->sp = (address_t)thread->stack + STACK_SIZE - sizeof(address_t); thread->pc = (address_t)f; sigsetjmp(thread->jbuf, 1); (thread->jbuf->__jmpbuf)[JB_SP] = translate_address(thread->sp); (thread->jbuf->__jmpbuf)[JB_PC] = translate_address(thread->pc); sigemptyset(&thread->jbuf->__saved_mask); thread_enqueue(thread, ready_list); thread_enqueue(thread, thread_list); return thread->status->id; } void InsertWrapper(thread_t *t, thread_queue_t *q) { if (scheduling_type == 0) { thread_enqueue(t, q); } else { //InsertAtHead(t, q); return; } } // Signal handler void Dispatch(int sig) { if (clean == 1) { return; } unsigned time_delta = GetCurrentTime() - start_time; status_t *s = current->status; s->total_exec_time += time_delta; // Save state of current thread int ret = sigsetjmp(current->jbuf, 1); if (ret == 1) { return; } // Itterate through all threads list and deal with them. thread_node_t *node = thread_list->head; while(node != NULL) { switch(node->thread->status->state) { // Do nothing case READY: break; case RUNNING: break; case SUSPENDED: break; case SLEEPING: if (GetCurrentTime() >= node->thread->status->wake_time) { printf("wake time\n"); thread_enqueue(node->thread, ready_list); node->thread->status->state = READY; } break; case FINISHED: RemoveFromList(node->thread->status->id, ready_list); break; } node = node->next; } // Iterate through ready_queue to update wait times thread_node_t *ready = ready_list->head; while(ready != NULL) { ready->thread->status->total_wait_time += time_delta; ready = ready->next; } // Schedule new thread if (current->status->state == RUNNING) { InsertWrapper(current, ready_list); current->status->state = READY; } thread_t *next = GetNextThread(); current = next; status_t *stat = next->status; stat->state = RUNNING; stat->no_of_bursts++; stat->avg_exec_time = (stat->total_exec_time / stat->no_of_bursts); stat->avg_wait_time = (stat->total_wait_time / (stat->no_of_bursts + 1)); // + 1 b/c num_wait = num_run + 1 start_time = GetCurrentTime(); start_timer(); siglongjmp(next->jbuf, 1); } void Go() { thread_t *t = GetNextThread(); current = t; t->status->state = RUNNING; start_timer(); start_time = GetCurrentTime(); siglongjmp(t->jbuf, 1); while(1); } int GetMyId() { return current->status->id; } thread_t *GetThread(int thread_id) { if (thread_list->head == NULL) { return NULL; } thread_node_t *node = thread_list->head; while(node != NULL && node->thread->status->id != thread_id) { node = node->next; } if (node == NULL) { return NULL; } return node->thread; } int DeleteThread(int thread_id) { int currentId = GetMyId(); thread_t *t = GetThread(thread_id); if (t == NULL) { return -1; } t->status->state = FINISHED; if (thread_id == currentId) { YieldCPU(); } return 0; } int RemoveFromList(int thread_id, thread_queue_t *q) { thread_node_t *node = q->head; thread_node_t *prev_node = NULL; // Find node with corresponding thread_id if (!node){ return -1; } while(node->next != NULL && node->thread->status->id != thread_id) { prev_node = node; node = node->next; } // If it is not found return -1 if(node->thread->status->id != thread_id) { return -1; } // Head if (node == q->head) { // If the head is to be deleted. q->head = node->next; } // Tail else if (node->next == NULL) { prev_node->next = NULL; q->tail = prev_node; } // Otherwise in middle / end of list else { prev_node->next = node->next; } free(node); (q->size) --; return 0; } void YieldCPU() { raise(SIGVTALRM); } int GetStatus(int thread_id, status_t *status) { thread_t *t = GetThread(thread_id); if (t == NULL) return -1; status->id = t->status->id; status->state = t->status->state; status->no_of_bursts = t->status->no_of_bursts; status->total_exec_time = t->status->total_exec_time; status->total_sleep_time = t->status->total_sleep_time; status->total_wait_time = t->status->total_wait_time; status->avg_exec_time = t->status->avg_exec_time; status->avg_wait_time = t->status->avg_wait_time; return t->status->id; } int SuspendThread(int thread_id) { thread_t *t = GetThread(thread_id); if (t == NULL) return -1; t->status->state = SUSPENDED; RemoveFromList(thread_id, ready_list); if (current->status->id == thread_id) YieldCPU(); return thread_id; } int ResumeThread(int thread_id) { thread_t *t = GetThread(thread_id); if (t == NULL) return -1; if (t->status->state != SUSPENDED) return thread_id; thread_enqueue(t, ready_list); t->status->state = READY; return thread_id; } unsigned GetCurrentTime() { clock_t time = clock(); unsigned millis = ((double)(time) / CLOCKS_PER_SEC) * 1000; return millis; } void SleepThread(int sec) { current->status->state = SLEEPING; current->status->wake_time = (GetCurrentTime() + (sec * 1000)); current->status->total_sleep_time += (sec * 1000); RemoveFromList(current->status->id, ready_list); YieldCPU(); } void setup(int schedule) { srand(time(NULL)); scheduling_type = schedule; //RR=0, LOT == 1, FCFS == 2 ready_list = malloc(sizeof(thread_queue_t)); ready_list->head = ready_list->tail = NULL; ready_list->size = 0; thread_list = malloc(sizeof(thread_queue_t)); thread_list->head = ready_list->tail = NULL; thread_list->size = 0; current = NULL; signal(SIGVTALRM, Dispatch); } void start_timer() { struct itimerval tv; tv.it_value.tv_sec = TIME_QUANTUM; //time of first timer tv.it_value.tv_usec = 0; //time of first timer tv.it_interval.tv_sec = 0; //time of all timers but the first one tv.it_interval.tv_usec = 0; //time of all timers but the first one setitimer(ITIMER_VIRTUAL, &tv, NULL); } //Get the head of thread queue thread_t *GetNextThread() { return scheduler(); } /*Print the status of all threads and kill all threads. In other words, capture the last status of all threads.*/ void CleanUp() { clean = 1; // Print contents of status struct thread_node_t *node = thread_list->head; while(NULL != node) { thread_t *t = node->thread; status_t *s = t->status; printf("thread %d info:\n", s->id); switch(s->state) { case(RUNNING): printf("thread state = RUNNING\n"); break; case(READY): printf("thread state = READY\n"); break; case(SLEEPING): printf("thread state = SLEEPING\n"); break; case(SUSPENDED): printf("thread state = SUSPENDED\n"); break; case(FINISHED): printf("thread state = FINISHED\n"); break; } printf("num_runs = %d\ntotal_exec_time = %d\n" "total_sleep_time = %d\ntotal_wait_time = %d\navg_exec_time = %d\navg_wait_time = %d\n", s->no_of_bursts, s->total_exec_time, s->total_sleep_time, s->total_wait_time, s->avg_exec_time, s->avg_wait_time); node = node->next; } // delete all threads // free up readyQ node = ready_list->head; thread_node_t *next; while(NULL != node) { next = node->next; RemoveFromList(node->thread->status->id, ready_list); node = next; } free(ready_list); //free up threads node = thread_list->head; while(NULL != node) { next = node->next; thread_t *t = node->thread; RemoveFromList(node->thread->status->id, thread_list); free(t->stack); free(t->status); free(t); node = next; } free(thread_list); // exit exit(0); }

PA2.pdf

PA2: Scheduling User-Level Threads and Comparing Them With Kernel-level Threads

CMPSC 473, FALL 2017 Released on Sept. 17, 2017, due on October 5, 2017, 11:59:59pm

Ata Fatahi Baarzi, Aman Jain, Diman Tootaghaj, and Bhuvan Urgaonkar

1 Goals

This programming assignment (PA2) has three main goals. First, you will use the source code offered by us to understand how one may implement user-level threads. Second, you will implement the following CPU scheduling algorithms for these user-level threads: (i) Round Robin (RR) and (ii) Lottery (LOT). You will validate the correctness of your implementation using some test cases that we will provide. Finally, you will design sim- ple experiments to measure and compare the efficacy of user-level threads as a ”vehicle of concurrency” vs. kernel-level threads along the following axes: (i) context switching overheads, (ii) handling of blocking IO, and (iii) using multi-processors.

2 Understanding the Provided Code-Base

After accepting the invitational link to PA2 (please use the account for one of the members of your team and be sure to indiate the names of both members in all your files), you will be given to access to your own private repository. Clone the repository for PA2 to obtain a collection of files containing our code and test cases. If needed, read the Git manual in files section on canvas as well as in the repository, to clone the repository. You will find the following files:

• The user-level threads implementation: thread.c, thread.h, my scheduler.c available in the User Level Thread directory.

• Four parallel programs (”test cases”) based on user-level threads (each contained within a separate file with a name such as TestFile*.c) for you to test your scheduler implementation. These files have definitions for functions that you will pass to the CreateThread() function of the user-level threads implementation. Each of these files has a main() function which calls the CreateThread() func- tion multiple times to create a certain number of threads, and then call the Go() function to start scheduling and executing them. You can find these files also in the User Level Thread directory. Section 2 offers details on CreateThread(), Go(), and other associated functions.

• Two functions that threads comprising your parallel programs will run called (i) counter() and sleeping(). You will find the prototypes and definitions of these functions in functions.h and functions.c, respectively which you can find them in the Kernel Level Thread directory. Both of these functions increment a counter variable for 10 seconds of real time. Whereas the counter function incre- ments the counter continuously, the sleeping() function sleeps for a short period of time (less than 10 seconds) before resuming counting. To use these functions, we have provided a program called kt test.c which you can find it in the same di- rectory. This file uses kernel threads (created using the pthreads library) that run these functions. By running the program, you can tell each thread to run either the counter function or the sleeping function by passing an argument to the pro- gram. All of these are source codes, which can be compiled using the makefile included in the Kernel Level Thread directory.

User-level threads implementation: You must develop a clear understanding of how the provided user-level threads implementation works. Towards this, you will go over the code and combine this with material covered in class on context switching and user-level threads (Lectures 4-8). Among other things, you will use this to augment our discussion in class (Lectures 7-8) on how user-level threads differ from kernel-level threads. The main functions comprising our user-level threads implementation are:

• int CreateThread(void (*f) (void), int cpuweight): this function cre- ates a new thread with f() 1 being its entry point. The function returns the created thread id (≥ 0) or -1 to indicate failure. It is assumed that f() never returns. A thread can create other threads. The created thread is appended to the end of the ready list (state = READY). Thread ids are consecutive and unique, starting with 0. The second argument (cpuweight) specifies the weight for a thread when creating it. For FCFS and RR schedulers this argument is meaningless. For LOT, it represents the CPU weight of the thread as employed by this scheduling algorithm.

• void Go(): This function is called by your process to start the scheduling of threads. It is assumed that at least one thread is created before Go() is called. This function is called exactly once and it never returns.

• int GetMyId(): This function is called within a running thread. The function returns the thread id of the calling thread.

• int DeleteThread(int thread id): Deletes a thread. The function returns 0 if successful and -1 otherwise. A thread can delete itself, in which case the function does not return.

• void Dispatch(int sig): The signal handler for alarm signals. The CPU sched- uler will be invoked by this function. In our code, the scheduling algorithm is FCFS. It is assumed that at least one thread exists at all times - therefore there is a stack at any time. It is not assumed that the thread is in ready state.

1Use this opportunity to learn about function pointers if you are not already familiar with them.

• void YieldCPU(): This function is called by the running thread. The function transfers control to the next thread (in the scheduling order). The next thread will have a complete time quantum to run.

• int SuspendThread(int thread id): This function suspends a thread until the thread is resumed. The calling thread can suspend itself, in which case the thread will YieldCPU as well. The function returns id on success and -1 other- wise. Suspending a suspended thread has no effect and is not considered an error. Suspend time is not considered waiting time.

• int ResumeThread(int thread id): Resumes a suspended thread. The thread is resumed by appending it to the end of the ready list. Returns thread id on success and -1 on failure. Resuming a ready thread has no effect and is not considered an error.

• int GetStatus(int thread id, status *stat): This call fills the status struc- ture with thread data. Returns thread id on success and -1 on failure.

• void SleepThread(int sec): The calling thread will sleep until current time plus sec). The sleeping time is not considered wait time.

• void CleanUp(): Shuts down scheduling, prints relevant statistics, deletes all threads and exits the program.

Make sure you understand how these functions are implemented. Make sure you un- derstand the data structures used by this code (e.g., what are status t and thread t and how they relate to the data structures we discussed as part of context switching and CPU scheduling?) - these are contained in the file threads.h. Make sure you under- stand the role of various macros that the code defines (e.g., what is x86 64?) Many macros are important constants:

• MAX NO OF THREADS 100 /* in any state */

• STACK SIZE 4096

• SECOND 1000000

• TIME QUANTUM 1*SECOND

Our code in the User Level Thread folder implements FCFS scheduling. You will be implementing RR and LOT as described below.

3 Description of Tasks

3.1 Task 1: implement and test schedulers

3.1.1 Implement RR and LOT

You are now ready to implement the RR and LOT algorithms (both covered in class in Lecture 9). Your scheduler should implement the following interface:

• thread t *scheduler(): Returns the thread (from the ready queue) which should run next.

• void thread enqueue(thread t *t, thread queue t *q): Adds a thread t to the queue q.

• void InsertWrapper(thread t *t, thread queue t *q): When a thread’s state changes from SLEEPING to READY or from RUNNING to READY, you have to add it to the appropriate queue accordingly.

Again, your code will be written in the file my scheduler.c. By now, it should be clear to you that the (already implemented) FCFS scheduler always returns the thread at the head of the ready list. Your code for RR or LOT will choose a thread from the ready list differently based on how these scheduling algorithms work. Note that you may implement other functions based on your needs as well.

3.1.2 Test the correctness of your RR and LOT implementations

The makefile in User Level Thread directory creates a static library named libutl.a which contains threads.c, threads.h and my scheduler.c. You must link your Testfile1.c,Testfile2.c,Testfile3.c, and Testfile4.c against this library to compile and create the project2 object file. An example of how to do this is already included in the makefile. After writing the code for LOT and RR scheduler you should be able to run all 4 test cases for LOT and RR ( $./project2 LOT, $ ./project2 RR). These test cases are given just for illustrative purposes to test your code. As you will see, each test case consists of creating one or more threads which run specified functions. When LOT is to be used, certain weights are supplied. For example, CreateThread (clean up thread, 1) creates a thread which runs the clean up thread function and has a CPU weight of 1. This function prints the thread id within a loop and when the condition j=10 occurs, it shuts down scheduling, deletes all the threads and exits. The following statistics are printed for each thread after clean up:

• num runs: shows the number of runs for each thread for all calls of Dispatch(.),

• total exec time: shows the total execution time for the thread,

• total sleep time: shows the total sleeping time,

• total wait time: shows the total waiting time,

• avg exec time: shows the average execution time,

• avg wait time: shows the average execution time.

NOTE: You are NOT supposed to modify any of the test cases. You should consider creating more extensive test cases for further testing. The TAs will test your code with other test cases during grading and your code should still work correctly.

3.1.3 Understand given parallel programs and re-implement them using user-level threads

As mentioned earlier, you have been given two functions, counter() and sleeping(), implemented using pthreads. Go over these functions, and make your own improvised counter() and sleeping() functions for use with user-level threads.

3.2 Task 2: evaluate pros and cons of user-level threads

You will conduct the following experiments to compare parallel programs implemented using kernel-level threads provided by us vs. the same programs implemented using user-level threads with the RR scheduler.

3.2.1 Context switch time

Use the lmbench benchmark to measure the context switching time for kernel threads on the lab machine you have chosen to work on. (Among the various measurements listed under context switching, you should report the time mentioned under the heading 2p/0K. Make sure you understand what this heading means and what the other values are for.) Use this link to download the latest version of lmbench: http://www.bitmover. com/lmbench/lmbench3.tar.gz. Make sure you take several measurements for statistical significance and report the empirical average and variance across these. (Take the time to read up on these basic statistical concepts if you have forgotten them).

First, you will implement functionality to measure the context switching time within the user-level threads code. Hint: you could introduce calls to a C library function like clock gettime() (that has a microsecond or nanosecond resolution) within threads.c for this.

Launch 2 threads each running this improvised counter() function for 10 seconds and measure:

1. Total number of context switches.

2. Time taken for each context switch in microseconds. Report the empirical average and variance across all context switches during your experiment.

3.2.2 Effect of a blocking call

As described earlier, the sleeping() function sleeps for a short period of time (less than 10 seconds) before resuming counting. Execute the sleeping() function using kt test.c and compare the work done with the improvised sleeping() function to be used with User Level Threads. Report your observation with a brief description. You can use any plotting tool of your choice. To use the plotting script provided in the repository, type, $ python plot script.py <path to file> Your file should have exactly 6 entries to be compatible with this plotting script.

http://www.bitmover.com/lmbench/lmbench3.tar.gz

3.2.3 Using multiple processors

Vary the number of parallel threads within a program where each thread runs the counter() function. The number of threads should vary as {1,2,4,8,16,32}. Call the summation of the counter values reported by all threads the work done by the program. Plot how the work done by a program varies with the number of threads when the program is based on kernel-level threads vs. user-level threads. Relate observed behavior to the number of processors on the machine on which you perform this experiment.

4 Submission and Grading

PA2 will be done in groups of 2. A group may choose either member’s repository as their workplace. Do remember to list both members’ names in all files you submit (including your report). Just like in PA1, you will submit all your source files, Makefiles, READMEs (to convey something non-trivial we may need to know to use your code), and a report containing the results as described earlier. Check out the updated Git Manual, included in your repository, especially Section 4.

PA2 is worth 10 points (amounting to 10% of your overall grade). The TAs will evalu- ate your submission based on (i) the quality and correctness of your report and code and (ii) running your code on some test cases different from the ones you are being given. The distribution of points will be as follows:

• RR implementation and testing: 2

• LOT implementation and testing): 3

• Context switch time for kernel-level threads using lmbench: 1

• Context switch time for user-level threads: 2

• Effect of I/O blocking: 1

• Multiple processors: 1

Appendix

We offer miscellaneous tips here.

• While using ssh to log into a department Linux machine, please use the port for- warding option by passing the -X option like so:

$ ssh <username>@cse-p204instxx -X where xx is some machine number.

Goals
Understanding the Provided Code-Base
Description of Tasks

Task 1: implement and test schedulers

Implement RR and LOT
Test the correctness of your RR and LOT implementations
Understand given parallel programs and re-implement them using user-level threads

Task 2: evaluate pros and cons of user-level threads

Context switch time
Effect of a blocking call
Using multiple processors

Submission and Grading

Plotting_Script/plot_script.py

import sys import matplotlib.pyplot as plt # rootdir = sys.argv[1] path = sys.argv[1] rootdir = sys.argv[1] + '/../' f1 = open(path,'r') lines = f1.readlines() y1 = [] for line in lines: y1.append(line) # y2.append(string[1]) # print string[0],' ',string[1] x = [] count = 1 x.append(1) x.append(2) x.append(4) x.append(8) x.append(16) x.append(32) # for items in y1: # x.append(count) # count += 1 # line 1 points # plotting the line 1 points line1, = plt.plot(x, y1, label = "Counter Value") # line 2 points # plotting the line 2 points # plt.plot(x, y2, label = "Line 2") # naming the x axis plt.xlabel('x-axis -> Number of Threads') # naming the y axis plt.ylabel('y - axis -> Value of Counter') # giving a title to my graph plt.title('Performance vs. # Threads') # show a legend on the plot # line2, = plt.plot([3,2,1], label="Memory Consumption in KB", linewidth=1) plt.legend() # function to show the plot # plt.show() plt.savefig('Performance.png') plt.show()

User_Level_Thread/makefile

# Makefile for library t=1 all: my_scheduler.o threads.o libult.a libs project2 my_scheduler.o: threads.h my_scheduler.c gcc -c -std=gnu99 -Wall -Wextra -Wno-unused-parameter threads.h my_scheduler.c -lrt threads.o: threads.c threads.h my_scheduler.c gcc -c -std=gnu99 -Wall -Wextra -Wno-unused-parameter threads.c threads.h my_scheduler.c -lrt libult.a: threads.o my_scheduler.o ar rcs libult.a threads.o my_scheduler.o libs: libult.a project2: libult.a TestFile3.c gcc -g -std=gnu99 -o project2 TestFile$(t).c -L . -lult -lrt clean: rm -rf *.o libult libult.a project2 *.gch

User_Level_Thread/my_scheduler.c

#include "threads.h" extern int scheduling_type; extern thread_queue_t *ready_list; void InsertAtHead(thread_t *t, thread_queue_t *q) { thread_node_t *node = malloc(sizeof(thread_node_t)); node->thread = t; node->next = q->head; q->head = node; if(q->tail == NULL) q->tail = node; q->size++; } void thread_enqueue(thread_t *t, thread_queue_t *q){ thread_node_t *node = malloc(sizeof(thread_node_t)); node->thread = t; node->next = NULL; if (q->tail != NULL) q->tail->next = node; else q->head = node; q->tail = node; q->size++; } thread_t* scheduler() { int number, priority = 0; thread_node_t *node; if(ready_list->size == 0) return NULL; switch(scheduling_type) { case 0: // Round Robin //Put your code here case 1: // Lottery //Put your code here case 2: //First come first serve return ready_list->head->thread; default: return NULL; } }

User_Level_Thread/TestFile1.c

// Project 2: User level thread library // Test file #include "threads.h" void simple_thread() { int i = 0; int j = 0; while(1) { if (i % 100000000 == 0) { int id = GetMyId(); printf("simple_thread tid: %d j = %d\n", id, j); j++; } if (j == 10) { printf("DELETING MYSELF tid: %d\n", GetMyId()); DeleteThread(GetMyId()); } i++; } } void clean_up_thread() { int i = 0; int j = 0; while(1) { if (i % 100000000 == 0) { int id = GetMyId(); printf("simple_thread tid: %d j = %d\n", id, j); j++; } if (j == 10) { printf("CLEANUP()\n"); CleanUp(); } i++; } } void sleep_test() { int i = 0; int j = 0; int sleep = 0; while(1) { if (sleep == 1) { printf("WAKING UP\n"); sleep = 0; } if (i % 100000000 == 0) { int id = GetMyId(); printf("sleep_thread tid: %d j = %d\n", id, j); j++; } if (j == 5) { j++; printf("SLEEP FOR 20 SECONDS (tid: %d)\n", GetMyId()); sleep = 1; SleepThread(20); } i++; } } void suspend_test() { int i = 0; int j = 0; while(1) { if (i % 100000000 == 0) { int id = GetMyId(); printf("suspend_test tid: %d j = %d\n", id, j); j++; } if (j == 10) { j++; printf("SUSPEND THREAD 0\n"); SuspendThread(0); } if (j == 20) { j++; printf("RESUME THREAD 0\n"); ResumeThread(0); } i++; } } void yield_test() { int i = 0; int j = 0; while(1) { if (i % 100000000 == 0) { int id = GetMyId(); printf("yield_test tid: %d j = %d\n", id, j); j++; } if (j % 5 == 0) { j++; printf("YIELDING CPU tid: %d\n", GetMyId()); YieldCPU(); } i++; } } void delete_test() { int i = 0; int j = 0; while(1) { if (i % 100000000 == 0) { int id = GetMyId(); printf("delete_test tid: %d j = %d\n", id, j); j++; } if (j % 25 == 0) { j++; printf("DELETING MYSELF tid: %d\n", GetMyId()); DeleteThread(GetMyId()); } i++; } } void delete_other_test() { int i = 0; int j = 0; while(1) { if (i % 100000000 == 0) { int id = GetMyId(); printf("delete_other_test tid: %d j = %d\n", id, j); j++; } if (j == 20) { j++; printf("DELETING THREAD 1\n"); DeleteThread(1); } i++; } } void create_test() { int i = 0; int j = 0; while(1) { if (i % 100000000 == 0) { int id = GetMyId(); printf("create_test tid: %d j = %d\n", id, j); j++; } if (j == 30) { j++; printf("CREATING A NEW THREAD\n"); CreateThread(simple_thread, 1); } i++; } } int main(int argc, char *argv[]) { if (argc != 2) { printf("Usage: %s [RR] | [LOT] | [FCFS] \n", argv[0]); return 1; } else if (strcmp(argv[1], "RR") == 0) { setup(0); // RR } else if (strcmp(argv[1], "LOT") == 0) { setup(1); // LOT } else if (strcmp(argv[1], "FCFS") == 0) { setup(2); // FCFS } else { return 1; } CreateThread(simple_thread, 1); // 0 CreateThread(simple_thread, 1); // 1 CreateThread(clean_up_thread, 1); // 2 Go(); return 0; }

User_Level_Thread/TestFile2.c

// Project 2: User level thread library // Test file #include "threads.h" void simple_thread() { int i = 0; int j = 0; while(1) { if (i % 100000000 == 0) { int id = GetMyId(); printf("simple_thread tid: %d j = %d\n", id, j); j++; } if (j == 10) { printf("DELETING MYSELF tid: %d\n", GetMyId()); DeleteThread(GetMyId()); } i++; } } void clean_up_thread() { int i = 0; int j = 0; while(1) { if (i % 100000000 == 0) { int id = GetMyId(); printf("simple_thread tid: %d j = %d\n", id, j); j++; } if (j == 20) { printf("CLEANUP()\n"); CleanUp(); } i++; } } void sleep_test() { int i = 0; int j = 0; int sleep = 0; while(1) { if (sleep == 1) { printf("WAKING UP\n"); sleep = 0; } if (i % 100000000 == 0) { int id = GetMyId(); printf("sleep_thread tid: %d j = %d\n", id, j); j++; } if (j == 5) { j++; printf("SLEEP FOR 20 SECONDS (tid: %d)\n", GetMyId()); sleep = 1; SleepThread(20); } i++; } } void suspend_test() { int i = 0; int j = 0; while(1) { if (i % 100000000 == 0) { int id = GetMyId(); printf("suspend_test tid: %d j = %d\n", id, j); j++; } if (j == 10) { j++; printf("SUSPEND THREAD 0\n"); SuspendThread(0); } if (j == 20) { j++; printf("RESUME THREAD 0\n"); ResumeThread(0); } i++; } } void yield_test() { int i = 0; int j = 0; while(1) { if (i % 100000000 == 0) { int id = GetMyId(); printf("yield_test tid: %d j = %d\n", id, j); j++; } if (j % 5 == 0) { j++; printf("YIELDING CPU tid: %d\n", GetMyId()); YieldCPU(); } i++; } } void delete_test() { int i = 0; int j = 0; while(1) { if (i % 100000000 == 0) { int id = GetMyId(); printf("delete_test tid: %d j = %d\n", id, j); j++; } if (j % 25 == 0) { j++; printf("DELETING MYSELF tid: %d\n", GetMyId()); DeleteThread(GetMyId()); } i++; } } void delete_other_test() { int i = 0; int j = 0; while(1) { if (i % 100000000 == 0) { int id = GetMyId(); printf("delete_other_test tid: %d j = %d\n", id, j); j++; } if (j == 20) { j++; printf("DELETING THREAD 1\n"); DeleteThread(1); } i++; } } void create_test() { int i = 0; int j = 0; while(1) { if (i % 100000000 == 0) { int id = GetMyId(); printf("create_test tid: %d j = %d\n", id, j); j++; } if (j == 30) { j++; printf("CREATING A NEW THREAD\n"); CreateThread(simple_thread, 1); } i++; } } int main(int argc, char *argv[]) { if (argc != 2) { printf("Usage: %s [RR] | [LOT] | [FCFS] \n", argv[0]); return 1; } else if (strcmp(argv[1], "RR") == 0) { setup(0); // RR } else if (strcmp(argv[1], "LOT") == 0) { setup(1); // LOT } else if (strcmp(argv[1], "FCFS") == 0) { setup(2); // FCFS } else { return 1; } CreateThread(clean_up_thread, 10); // 0 CreateThread(clean_up_thread, 5); // 1 CreateThread(clean_up_thread, 5); // 2 CreateThread(clean_up_thread, 10); // 3 Go(); return 0; }

User_Level_Thread/TestFile3.c

// Project 2: User level thread library // Test file #include "threads.h" void simple_thread() { int i = 0; int j = 0; while(1) { if (i % 100000000 == 0) { int id = GetMyId(); printf("simple_thread tid: %d j = %d\n", id, j); j++; } if (j == 50) { printf("DELETING MYSELF tid: %d\n", GetMyId()); DeleteThread(GetMyId()); } i++; } } void clean_up_thread() { int i = 0; int j = 0; while(1) { if (i % 100000000 == 0) { int id = GetMyId(); printf("simple_thread tid: %d j = %d\n", id, j); j++; } if (j == 50) { printf("CLEANUP()\n"); CleanUp(); } i++; } } void sleep_test() { int i = 0; int j = 0; int sleep = 0; while(1) { if (sleep == 1) { printf("WAKING UP\n"); sleep = 0; } if (i % 100000000 == 0) { int id = GetMyId(); printf("sleep_thread tid: %d j = %d\n", id, j); j++; } if (j == 5) { j++; printf("SLEEP FOR 20 SECONDS (tid: %d)\n", GetMyId()); sleep = 1; SleepThread(20); } i++; } } void suspend_test() { int i = 0; int j = 0; while(1) { if (i % 100000000 == 0) { int id = GetMyId(); printf("suspend_test tid: %d j = %d\n", id, j); j++; } if (j == 10) { j++; printf("SUSPEND THREAD 0\n"); SuspendThread(0); } if (j == 20) { j++; printf("RESUME THREAD 0\n"); ResumeThread(0); } i++; } } void yield_test() { int i = 0; int j = 0; while(1) { if (i % 100000000 == 0) { int id = GetMyId(); printf("yield_test tid: %d j = %d\n", id, j); j++; } if (j % 5 == 0) { j++; printf("YIELDING CPU tid: %d\n", GetMyId()); YieldCPU(); } i++; } } void delete_test() { int i = 0; int j = 0; while(1) { if (i % 100000000 == 0) { int id = GetMyId(); printf("delete_test tid: %d j = %d\n", id, j); j++; } if (j % 25 == 0) { j++; printf("DELETING MYSELF tid: %d\n", GetMyId()); DeleteThread(GetMyId()); } i++; } } void delete_other_test() { int i = 0; int j = 0; while(1) { if (i % 100000000 == 0) { int id = GetMyId(); printf("delete_other_test tid: %d j = %d\n", id, j); j++; } if (j == 20) { j++; printf("DELETING THREAD 1\n"); DeleteThread(1); } i++; } } void create_test() { int i = 0; int j = 0; while(1) { if (i % 100000000 == 0) { int id = GetMyId(); printf("create_test tid: %d j = %d\n", id, j); j++; } if (j == 30) { j++; printf("CREATING A NEW THREAD\n"); CreateThread(simple_thread, 1); } i++; } } int main(int argc, char *argv[]) { if (argc != 2) { printf("Usage: %s [RR] | [LOT] | [FCFS] \n", argv[0]); return 1; } else if (strcmp(argv[1], "RR") == 0) { setup(0); // RR } else if (strcmp(argv[1], "LOT") == 0) { setup(1); // LOT } else if (strcmp(argv[1], "FCFS") == 0) { setup(2); // FCFS } else { return 1; } CreateThread(clean_up_thread, 10); // 0 CreateThread(clean_up_thread, 1); // 1 CreateThread(suspend_test, 20); // 2 CreateThread(clean_up_thread, 5); // 3 CreateThread(clean_up_thread, 10); // 4 Go(); return 0; }

User_Level_Thread/TestFile4.c

// Project 2: User level thread library // Test file #include "threads.h" void simple_thread() { int i = 0; int j = 0; while(1) { if (i % 100000000 == 0) { int id = GetMyId(); printf("simple_thread tid: %d j = %d\n", id, j); j++; } if (j == 50) { printf("DELETING MYSELF tid: %d\n", GetMyId()); DeleteThread(GetMyId()); } i++; } } void clean_up_thread() { int i = 0; int j = 0; while(1) { if (i % 100000000 == 0) { int id = GetMyId(); printf("simple_thread tid: %d j = %d\n", id, j); j++; } if (j == 50) { printf("CLEANUP()\n"); CleanUp(); } i++; } } void sleep_test() { int i = 0; int j = 0; int sleep = 0; while(1) { if (sleep == 1) { printf("WAKING UP\n"); sleep = 0; } if (i % 100000000 == 0) { int id = GetMyId(); printf("sleep_thread tid: %d j = %d\n", id, j); j++; } if (j == 5) { j++; printf("SLEEP FOR 5 SECONDS (tid: %d)\n", GetMyId()); sleep = 1; SleepThread(5); } i++; } } void suspend_test() { int i = 0; int j = 0; while(1) { if (i % 100000000 == 0) { int id = GetMyId(); printf("suspend_test tid: %d j = %d\n", id, j); j++; } if (j == 10) { j++; printf("SUSPEND THREAD 0\n"); SuspendThread(0); } if (j == 20) { j++; printf("RESUME THREAD 0\n"); ResumeThread(0); } i++; } } void yield_test() { int i = 0; int j = 0; while(1) { if (i % 100000000 == 0) { int id = GetMyId(); printf("yield_test tid: %d j = %d\n", id, j); j++; } if (j % 5 == 0) { j++; printf("YIELDING CPU tid: %d\n", GetMyId()); YieldCPU(); } i++; } } void delete_test() { int i = 0; int j = 0; while(1) { if (i % 100000000 == 0) { int id = GetMyId(); printf("delete_test tid: %d j = %d\n", id, j); j++; } if (j % 25 == 0) { j++; printf("DELETING MYSELF tid: %d\n", GetMyId()); DeleteThread(GetMyId()); } i++; } } void delete_other_test() { int i = 0; int j = 0; while(1) { if (i % 100000000 == 0) { int id = GetMyId(); printf("delete_other_test tid: %d j = %d\n", id, j); j++; } if (j == 20) { j++; printf("DELETING THREAD 1\n"); DeleteThread(1); } i++; } } void create_test() { int i = 0; int j = 0; while(1) { if (i % 100000000 == 0) { int id = GetMyId(); printf("create_test tid: %d j = %d\n", id, j); j++; } if (j == 30) { j++; printf("CREATING A NEW THREAD\n"); CreateThread(simple_thread, 1); } i++; } } int main(int argc, char *argv[]) { if (argc != 2) { printf("Usage: %s [RR] | [LOT] | [FCFS] \n", argv[0]); return 1; } else if (strcmp(argv[1], "RR") == 0) { setup(0); // RR } else if (strcmp(argv[1], "LOT") == 0) { setup(1); // LOT } else if (strcmp(argv[1], "FCFS") == 0) { setup(2); // FCFS } else { return 1; } CreateThread(sleep_test, 10); // 2 CreateThread(clean_up_thread, 10); // 0 CreateThread(clean_up_thread, 1); // 1 CreateThread(clean_up_thread, 5); // 3 Go(); return 0; }

User_Level_Thread/threads.c

//User level threads library // INCLUDES #include <stdio.h> #include <stdlib.h> #include <signal.h> #include <string.h> #include <unistd.h> #include <time.h> #include <sys/time.h> #include "threads.h" // DEFINES #define SECOND 1000000 #define MAX_NO_OF_THREADS 100 /* in any state */ #define STACK_SIZE 10000 //4096 #define TIME_QUANTUM 1 // Black box code //////////////////////////////////////////////////////////////////////// #ifdef __x86_64__ // code for 64 bit Intel arch //typedef unsigned long address_t; #define JB_SP 6 #define JB_PC 7 //A translation required when using an address of a variable //Use this as a black box in your code. address_t translate_address(address_t addr) { address_t ret; asm volatile("xor %%fs:0x30,%0\n" "rol $0x11,%0\n" : "=g" (ret) : "0" (addr)); return ret; } #else // code for 32 bit Intel arch //typedef unsigned int address_t; #define JB_SP 4 #define JB_PC 5 //A translation required when using an address of a variable //Use this as a black box in your code. address_t translate_address(address_t addr) { address_t ret; asm volatile("xor %%gs:0x18,%0\n" "rol $0x9,%0\n" : "=g" (ret) : "0" (addr)); return ret; } #endif //////////////////////////////////////////////////////////////////////// // Global variables thread_queue_t *thread_list; /* the list of all threads */ thread_queue_t *ready_list; /* the list of all ready threads */ thread_t *current; /* the current running thread */ int next_thread = 0; /* Used for assigning IDs */ int scheduling_type; /* Scheduling type 0 = RR, 1 = LOT */ int clean = 0; /* if in cleanup, exit out of dispatch */ unsigned start_time = 0; /* Time a thread is started */ extern void thread_enqueue(thread_t*, thread_queue_t*); // enqueue t to back of queue extern thread_t* scheduler(); //implementation of thread scheduler, RR and LOT int CreateThread(void (*f) (void), int priority) { // Return -1 if fail if (thread_list->size + 1 > MAX_NO_OF_THREADS) { printf("Too many threads\n"); return -1; } thread_t *thread = malloc(sizeof(thread_t)); thread->status = malloc(sizeof(status_t)); thread->stack = malloc(STACK_SIZE); thread->status->id = next_thread; thread->priority = priority; next_thread++; thread->status->state = READY; thread->sp = (address_t)thread->stack + STACK_SIZE - sizeof(address_t); thread->pc = (address_t)f; sigsetjmp(thread->jbuf, 1); (thread->jbuf->__jmpbuf)[JB_SP] = translate_address(thread->sp); (thread->jbuf->__jmpbuf)[JB_PC] = translate_address(thread->pc); sigemptyset(&thread->jbuf->__saved_mask); thread_enqueue(thread, ready_list); thread_enqueue(thread, thread_list); return thread->status->id; } void InsertWrapper(thread_t *t, thread_queue_t *q) { if (scheduling_type == 0) { thread_enqueue(t, q); } else { //InsertAtHead(t, q); return; } } // Signal handler void Dispatch(int sig) { if (clean == 1) { return; } unsigned time_delta = GetCurrentTime() - start_time; status_t *s = current->status; s->total_exec_time += time_delta; // Save state of current thread int ret = sigsetjmp(current->jbuf, 1); if (ret == 1) { return; } // Itterate through all threads list and deal with them. thread_node_t *node = thread_list->head; while(node != NULL) { switch(node->thread->status->state) { // Do nothing case READY: break; case RUNNING: break; case SUSPENDED: break; case SLEEPING: if (GetCurrentTime() >= node->thread->status->wake_time) { printf("wake time\n"); thread_enqueue(node->thread, ready_list); node->thread->status->state = READY; } break; case FINISHED: RemoveFromList(node->thread->status->id, ready_list); break; } node = node->next; } // Iterate through ready_queue to update wait times thread_node_t *ready = ready_list->head; while(ready != NULL) { ready->thread->status->total_wait_time += time_delta; ready = ready->next; } // Schedule new thread if (current->status->state == RUNNING) { InsertWrapper(current, ready_list); current->status->state = READY; } thread_t *next = GetNextThread(); current = next; status_t *stat = next->status; stat->state = RUNNING; stat->no_of_bursts++; stat->avg_exec_time = (stat->total_exec_time / stat->no_of_bursts); stat->avg_wait_time = (stat->total_wait_time / (stat->no_of_bursts + 1)); // + 1 b/c num_wait = num_run + 1 start_time = GetCurrentTime(); start_timer(); siglongjmp(next->jbuf, 1); } void Go() { thread_t *t = GetNextThread(); current = t; t->status->state = RUNNING; start_timer(); start_time = GetCurrentTime(); siglongjmp(t->jbuf, 1); while(1); } int GetMyId() { return current->status->id; } thread_t *GetThread(int thread_id) { if (thread_list->head == NULL) { return NULL; } thread_node_t *node = thread_list->head; while(node != NULL && node->thread->status->id != thread_id) { node = node->next; } if (node == NULL) { return NULL; } return node->thread; } int DeleteThread(int thread_id) { int currentId = GetMyId(); thread_t *t = GetThread(thread_id); if (t == NULL) { return -1; } t->status->state = FINISHED; if (thread_id == currentId) { YieldCPU(); } return 0; } int RemoveFromList(int thread_id, thread_queue_t *q) { thread_node_t *node = q->head; thread_node_t *prev_node = NULL; // Find node with corresponding thread_id if (!node){ return -1; } while(node->next != NULL && node->thread->status->id != thread_id) { prev_node = node; node = node->next; } // If it is not found return -1 if(node->thread->status->id != thread_id) { return -1; } // Head if (node == q->head) { // If the head is to be deleted. q->head = node->next; } // Tail else if (node->next == NULL) { prev_node->next = NULL; q->tail = prev_node; } // Otherwise in middle / end of list else { prev_node->next = node->next; } free(node); (q->size) --; return 0; } void YieldCPU() { raise(SIGVTALRM); } int GetStatus(int thread_id, status_t *status) { thread_t *t = GetThread(thread_id); if (t == NULL) return -1; status->id = t->status->id; status->state = t->status->state; status->no_of_bursts = t->status->no_of_bursts; status->total_exec_time = t->status->total_exec_time; status->total_sleep_time = t->status->total_sleep_time; status->total_wait_time = t->status->total_wait_time; status->avg_exec_time = t->status->avg_exec_time; status->avg_wait_time = t->status->avg_wait_time; return t->status->id; } int SuspendThread(int thread_id) { thread_t *t = GetThread(thread_id); if (t == NULL) return -1; t->status->state = SUSPENDED; RemoveFromList(thread_id, ready_list); if (current->status->id == thread_id) YieldCPU(); return thread_id; } int ResumeThread(int thread_id) { thread_t *t = GetThread(thread_id); if (t == NULL) return -1; if (t->status->state != SUSPENDED) return thread_id; thread_enqueue(t, ready_list); t->status->state = READY; return thread_id; } unsigned GetCurrentTime() { clock_t time = clock(); unsigned millis = ((double)(time) / CLOCKS_PER_SEC) * 1000; return millis; } void SleepThread(int sec) { current->status->state = SLEEPING; current->status->wake_time = (GetCurrentTime() + (sec * 1000)); current->status->total_sleep_time += (sec * 1000); RemoveFromList(current->status->id, ready_list); YieldCPU(); } void setup(int schedule) { srand(time(NULL)); scheduling_type = schedule; //RR=0, LOT == 1, FCFS == 2 ready_list = malloc(sizeof(thread_queue_t)); ready_list->head = ready_list->tail = NULL; ready_list->size = 0; thread_list = malloc(sizeof(thread_queue_t)); thread_list->head = ready_list->tail = NULL; thread_list->size = 0; current = NULL; signal(SIGVTALRM, Dispatch); } void start_timer() { struct itimerval tv; tv.it_value.tv_sec = TIME_QUANTUM; //time of first timer tv.it_value.tv_usec = 0; //time of first timer tv.it_interval.tv_sec = 0; //time of all timers but the first one tv.it_interval.tv_usec = 0; //time of all timers but the first one setitimer(ITIMER_VIRTUAL, &tv, NULL); } //Get the head of thread queue thread_t *GetNextThread() { return scheduler(); } /*Print the status of all threads and kill all threads. In other words, capture the last status of all threads.*/ void CleanUp() { clean = 1; // Print contents of status struct thread_node_t *node = thread_list->head; while(NULL != node) { thread_t *t = node->thread; status_t *s = t->status; printf("thread %d info:\n", s->id); switch(s->state) { case(RUNNING): printf("thread state = RUNNING\n"); break; case(READY): printf("thread state = READY\n"); break; case(SLEEPING): printf("thread state = SLEEPING\n"); break; case(SUSPENDED): printf("thread state = SUSPENDED\n"); break; case(FINISHED): printf("thread state = FINISHED\n"); break; } printf("num_runs = %d\ntotal_exec_time = %d\n" "total_sleep_time = %d\ntotal_wait_time = %d\navg_exec_time = %d\navg_wait_time = %d\n", s->no_of_bursts, s->total_exec_time, s->total_sleep_time, s->total_wait_time, s->avg_exec_time, s->avg_wait_time); node = node->next; } // delete all threads // free up readyQ node = ready_list->head; thread_node_t *next; while(NULL != node) { next = node->next; RemoveFromList(node->thread->status->id, ready_list); node = next; } free(ready_list); //free up threads node = thread_list->head; while(NULL != node) { next = node->next; thread_t *t = node->thread; RemoveFromList(node->thread->status->id, thread_list); free(t->stack); free(t->status); free(t); node = next; } free(thread_list); // exit exit(0); }

User_Level_Thread/threads.h

// Includes: #include <stdio.h> #include <stdlib.h> #include <signal.h> #include <string.h> #include <unistd.h> #include <time.h> #include <sys/time.h> #include <setjmp.h> #ifdef __x86_64__ typedef unsigned long address_t; #else typedef unsigned int address_t; #endif // Thread Status structure typedef struct status_t { int id; enum {RUNNING, READY, SLEEPING, SUSPENDED, FINISHED} state; unsigned no_of_bursts; unsigned total_exec_time; unsigned total_sleep_time; unsigned total_wait_time; unsigned avg_exec_time; unsigned avg_wait_time; unsigned wake_time; } status_t; // Thread Structure typedef struct thread_t { char *stack; status_t *status; int priority; sigjmp_buf jbuf; address_t pc; address_t sp; } thread_t; // Thread node typedef struct thread_node_t { thread_t *thread; struct thread_node_t *next; } thread_node_t; // Queue of threads typedef struct thread_queue_t { thread_node_t *head; thread_node_t *tail; int size; } thread_queue_t; address_t translate_address(address_t addr); thread_t *GetNextThread(); void thread_enqueue(thread_t *t, thread_queue_t *q); void setup(); void print_list(thread_queue_t *q); void YieldCPU(); void Dispatch(int sig); void Go(); void CleanUp(); void start_timer(); void SleepThread(int sec); int CreateThread(void (*f) (void), int priority); int RemoveFromList(int thread_id, thread_queue_t *q); int GetMyId(); int DeleteThread(int thread_id); int SuspendThread(int thread_id); int ResumeThread(int thread_id); int GetStatus(int thread_id, status_t *status); thread_t *GetThread(int thread_id); unsigned GetCurrentTime();