thread-worker.c

// File:	thread-worker.c

// List all group member's name:
// username of iLab:
// iLab Server:

#include "thread-worker.h"

//Global counter for total context switches and 
//average turn around and response time
long tot_cntx_switches=0;
double avg_turn_time=0;
double avg_resp_time=0;


// INITAILIZE ALL YOUR OTHER VARIABLES HERE
// YOUR CODE HERE
tcb* scheduleThread = NULL;
tcb* currentThread = NULL;
tcb* mainThread = NULL;
tcb* lastThread = NULL;
static void schedule();
static void sched_psjf();
static void sched_mlfq();
unsigned int nextThreadID = 0;
unsigned int nextMutexID = 0;
List* queueList = NULL;
List* waitList = NULL;
List* mutexList = NULL;
List* blockList = NULL;
List* finishedList = NULL;
struct itimerval timer;
int noInterrupt;
int handleTimerFailed;
unsigned int totalTimeElapsed = 0;
unsigned int numResponseTimes = 0;
unsigned int numFinishedThreads = 0;

void printQueue(List* list);
void printPriorityQueue(List* list);
void printMutexes(List* list);
void enqueue(void* obj, List* list);
void dequeue(List* list);
void enqueueAtEnd(tcb* obj, List* list);
void moveShortestJobToFront(List* list);
void movePriorityJobToFront(List* list);
void moveAllJobsToPriority(List* list);
int queueHasID(worker_t id, List* list);
void* dequeueByID(worker_t id, List* list);
void enqueueMutex(void* obj, List* list);
void* dequeueByMutex(worker_t id, List* list);
int mutexesHasID(worker_t id, List* list);
void dequeueEnqueueThreadByMutexID(worker_t id, List* list);
tcb* getThreadByID(worker_t id, List* list);
tcb* waitListHasElement(worker_t id);
void stopTimer();
void startTimer();
void handleTimer(int signum);
void keepContext();
void resumeNormalContext();
double getCurrentTime();
void initializeScheduler();

/* create a new thread */
int worker_create(worker_t * thread, pthread_attr_t * attr, 
                      void *(*function)(void*), void * arg) {
    // - create Thread Control Block (TCB)
    // - create and initialize the context of this worker thread
    // - allocate space of stack for this thread to run
    // after everything is set, push this thread into run queue and 
    // - make it ready for the execution.

    // YOUR CODE HERE
    if (scheduleThread == NULL) {
		initializeScheduler();
	}
    tcb* newTCB = NULL;
	void* newStack = NULL;
	newTCB = malloc(sizeof(tcb));
	newStack = malloc(STACK_SIZE);
	newTCB->elapsed = 1;
	newTCB->priority = HIGH_PRIO;
	newTCB->lastPriorityChange = 1;
	newTCB->startTime = getCurrentTime();
	*thread = nextThreadID++;
	newTCB->id = *thread;
	newTCB->threadFinished = 0;
	newTCB->mutexID = -6;
	getcontext(&newTCB->context);
	newTCB->context.uc_stack.ss_sp = newStack;
	newTCB->context.uc_stack.ss_size = STACK_SIZE;
	newTCB->context.uc_stack.ss_flags = 0;
	newTCB->context.uc_link = NULL;
	makecontext(&newTCB->context, (void (*)(void)) function, 1, arg);
	enqueue(newTCB, queueList);
		
	//fprintf(stderr, "Thread %d created. Ptr: %p. Sched ptr: %p.\n", newTCB->id, newTCB->context.uc_stack.ss_sp, scheduleThread->context.uc_stack.ss_sp);
	//setcontext(&scheduleThread->context);

    return 0;
};


#ifdef MLFQ
/* This function gets called only for MLFQ scheduling set the worker priority. */
int worker_setschedprio(worker_t thread, int prio) {
   	// Set the priority value to your thread's TCB
   	// YOUR CODE HERE
	keepContext();
	//fprintf(stderr, "Thread to sched prio: %d\n", thread);
	tcb* obj = getThreadByID(thread, queueList);
	if (obj == NULL) {
		obj = getThreadByID(thread, blockList);
		if (obj == NULL) {
			obj = getThreadByID(thread, waitList);
			resumeNormalContext();
			return 1;
		}
	}
	obj->priority = prio;
	obj->lastPriorityChange = obj->elapsed;
	resumeNormalContext();
	return 0;

}
#endif



/* give CPU possession to other user-level worker threads voluntarily */
int worker_yield() {
	
	// - change worker thread's state from Running to Ready
	// - save context of this thread to its thread control block
	// - switch from thread context to scheduler context

	// YOUR CODE HERE
    stopTimer();
	//fprintf(stderr, "Yield process started\n");
	if (currentThread->elapsed == currentThread->lastPriorityChange) {
		currentThread->priority = currentThread->priority + 1;
	}
	swapcontext(&currentThread->context, &scheduleThread->context);
	return 0;
};

/* terminate a thread */
void worker_exit(void *value_ptr) {
	// - de-allocate any dynamic memory created when starting this thread

	// YOUR CODE HERE
    stopTimer();
	//fprintf(stderr, "Thread %d exit process.\n", currentThread->id);
    dequeue(queueList);
	tcb* obj = waitListHasElement(currentThread->id);
	while (obj != NULL) {
		//fprintf(stderr, "loop thru for waitlist threads\n");
		if (value_ptr != NULL && obj->value_ptr_to_set != NULL) {
			*obj->value_ptr_to_set = value_ptr;
			obj->value_ptr_to_set = NULL;
		}
        enqueue(obj, queueList);
        obj = waitListHasElement(currentThread->id);
    }
	//fprintf(stderr, "current turnaround response time: %f. Current number of threads exited: %d. Thread start time: %ld. Current time: %ld.\n", avg_turn_time, numFinishedThreads, currentThread->startTime, getCurrentTime());
	avg_turn_time = (avg_turn_time * (numFinishedThreads) + (getCurrentTime() - currentThread->startTime)) / (numFinishedThreads + 1);
	numFinishedThreads++;
	//fprintf(stderr, "try free: %p\n", currentThread->context.uc_stack.ss_sp);
	free(currentThread->context.uc_stack.ss_sp);
	//fprintf(stderr, "free success\n");
	if (value_ptr != NULL) {
		currentThread->value_ptr = &value_ptr;
		enqueue(currentThread, finishedList);
	} else free(currentThread);
	currentThread = NULL;
	//fprintf(stderr, "Exit success.\n");
	setcontext(&scheduleThread->context);
};


/* Wait for thread termination */
int worker_join(worker_t thread, void **value_ptr) {
	
	// - wait for a specific thread to terminate
	// - de-allocate any dynamic memory created by the joining thread
  
	// YOUR CODE HERE
    keepContext();
    //fprintf(stderr, "Worker join function %d\n", thread);
	int isFinished = queueHasID(thread, finishedList);
	if (isFinished || (!queueHasID(thread, waitList) && !queueHasID(thread, queueList) && !queueHasID(thread, blockList))) {
		if (isFinished && value_ptr != NULL) {
			*value_ptr = *getThreadByID(thread, finishedList)->value_ptr;
		}
		//fprintf(stderr, "Thread %d already finished\n", thread);
		resumeNormalContext();
		return 0;
	}
	dequeueByID(currentThread->id, queueList);
	
	currentThread->waitID = thread;
	if (value_ptr != NULL) currentThread->value_ptr_to_set = value_ptr;
	enqueue(currentThread, waitList);
	handleTimerFailed = 0;
	noInterrupt = 0;
	swapcontext(&currentThread->context, &scheduleThread->context);
	return 0;
};

/* initialize the mutex lock */
int worker_mutex_init(worker_mutex_t *mutex, 
                          const pthread_mutexattr_t *mutexattr) {
	//- initialize data structures for this mutex

	// YOUR CODE HERE
    keepContext();
    if (scheduleThread == NULL) {
		initializeScheduler();
	}
	mutex->id = ++nextMutexID;
	mutex->assignedTCB = -1;

	enqueueMutex(mutex, mutexList);
    resumeNormalContext();
	return 0;
};

/* aquire the mutex lock */
int worker_mutex_lock(worker_mutex_t *mutex) {

    // - use the built-in test-and-set atomic function to test the mutex
    // - if the mutex is acquired successfully, enter the critical section
    // - if acquiring mutex fails, push current thread into block list and
    // context switch to the scheduler thread

    // YOUR CODE HERE
    keepContext();
	//fprintf(stderr, "Mutex ID: %d. Mutex owner: %d\n", mutex->id, mutex->assignedTCB);
    if (mutex == NULL || !mutexesHasID(mutex->id, mutexList) || mutex->assignedTCB == currentThread->id) {
		//fprintf(stderr, "mutex lock failed due to invalid mutex.\n");
		return 1;
	}
	//fprintf(stderr, "test1\n");
    while (mutex->assignedTCB != -1) {
        //fprintf(stderr, "mutex lock failed by thread %d due to mutex already in use by thread %d.\n", currentThread->id, mutex->assignedTCB);
        dequeue(queueList);
		currentThread->mutexID = mutex->id;
		enqueue(currentThread, blockList);
        swapcontext(&currentThread->context, &scheduleThread->context);
    }
    mutex->assignedTCB = currentThread->id;
	//fprintf(stderr, "Thread %d achieved mutex lock.\n", currentThread->id);
    resumeNormalContext();
    return 0;
};

/* release the mutex lock */
int worker_mutex_unlock(worker_mutex_t *mutex) {
	// - release mutex and make it available again. 
	// - put threads in block list to run queue 
	// so that they could compete for mutex later.

	// YOUR CODE HERE
    keepContext();
    //fprintf(stderr, "Thread %d attempting mutex unlock.\n", currentThread->id);
    if (mutex == NULL || !mutexesHasID(mutex->id, mutexList) || mutex->assignedTCB != currentThread->id) {
		//if (mutex->assignedTCB != currentThread->id) fprintf(stderr, "Mutex unlock failed by thread %d. Current mutex assigned to %d.\n", currentThread->id, mutex->assignedTCB);
		return 1;
	}
    mutex->assignedTCB = -1;
    dequeueEnqueueThreadByMutexID(mutex->id, blockList);
    //fprintf(stderr, "Thread %d achieved mutex unlock.\n", currentThread->id);
    resumeNormalContext();
	return 0;
};


/* destroy the mutex */
int worker_mutex_destroy(worker_mutex_t *mutex) {
	// - de-allocate dynamic memory created in worker_mutex_init
    keepContext();
    dequeueEnqueueThreadByMutexID(mutex->id, blockList);
	dequeueByMutex(mutex->id, mutexList);
    resumeNormalContext();
	return 0;
};

/* scheduler */
static void schedule() {
	// - every time a timer interrupt occurs, your worker thread library 
	// should be contexted switched from a thread context to this 
	// schedule() function

	// - invoke scheduling algorithms according to the policy (PSJF or MLFQ)

	// if (sched == PSJF)
	//		sched_psjf();
	// else if (sched == MLFQ)
	// 		sched_mlfq();

	// YOUR CODE HERE
//fprintf(stderr, "Schedule function called\n");
stopTimer();
// - schedule policy
    #ifndef MLFQ
    	// Choose PSJF
		sched_psjf();
    #else 
    	sched_mlfq();
    	// Choose MLFQ
    #endif

}

/* Pre-emptive Shortest Job First (POLICY_PSJF) scheduling algorithm */
static void sched_psjf() {
	// - your own implementation of PSJF
	// (feel free to modify arguments and return types)

	// YOUR CODE HERE
    //fprintf(stderr, "PSJF function called\n");
    while(1) {
		//fprintf(stderr, "Loop\n");
        handleTimerFailed = 0;
	    noInterrupt = 0;
        if (currentThread != queueList->tail->entry) {
			currentThread = NULL;
		}
        if (currentThread != NULL) {
			//fprintf(stderr, "current id: %d\n", currentThread->id);
			dequeue(queueList);
			currentThread->elapsed = currentThread->elapsed + 1;
			enqueue(currentThread, queueList);
			moveShortestJobToFront(queueList);
		}
        if (queueList->tail != NULL) {
			currentThread = queueList->tail->entry;
			//fprintf(stderr, "Thread %d has mutexID of %d.\n", queueList->tail->entry->id, queueList->tail->entry->mutexID);
			if (currentThread != lastThread) {
				tot_cntx_switches++;
			}
			lastThread = currentThread;
			if (currentThread->elapsed == 1 && currentThread->id > 0) {
				//fprintf(stderr, "current avg response time: %f. Current number of threads measured: %d. Thread start time: %ld. Current time: %ld.\n", avg_resp_time, numResponseTimes, currentThread->startTime, getCurrentTime());
				avg_resp_time = (avg_resp_time * (numResponseTimes) + (getCurrentTime() - currentThread->startTime)) / (numResponseTimes + 1);
				numResponseTimes++;
			}
			//printQueue(queueList);
			startTimer();
			swapcontext(&scheduleThread->context, &currentThread->context);
		} else {
			//fprintf(stderr, "breaking out of loop. End of all");
			break;
		}
    }
}


/* Preemptive MLFQ scheduling algorithm */
static void sched_mlfq() {
	// - your own implementation of MLFQ
	// (feel free to modify arguments and return types)

	// YOUR CODE HERE
	//fprintf(stderr, "MLFQ function called\n");
    while(1) {
        handleTimerFailed = 0;
	    noInterrupt = 0;
        if (currentThread != queueList->tail->entry) {
			currentThread = NULL;
		}
        if (currentThread != NULL) {
			dequeue(queueList);
			currentThread->elapsed = currentThread->elapsed + 1;
			enqueue(currentThread, queueList);
			//fprintf(stderr, "%d, %d\n", totalTimeElapsed, totalTimeElapsed % REFRESH_QUANTUM);
			if (totalTimeElapsed % REFRESH_QUANTUM == 0) {
				moveAllJobsToPriority(queueList);
			} else movePriorityJobToFront(queueList);
		}
        if (queueList->tail != NULL) {
			currentThread = queueList->tail->entry;
			//fprintf(stderr, "Thread %d has mutexID of %d.\n", queueList->tail->entry->id, queueList->tail->entry->mutexID);
			if (currentThread->priority > LOW_PRIO) {
				currentThread->priority = currentThread->priority - 1;
				currentThread->lastPriorityChange = currentThread->elapsed;
			}
			if (currentThread != lastThread) {
				tot_cntx_switches++;
			}
			lastThread = currentThread;
			if (currentThread->elapsed == 1 && currentThread->id > 0) {
				//fprintf(stderr, "current avg response time: %f. Current number of threads measured: %d. Thread start time: %ld. Current time: %ld.\n", avg_resp_time, numResponseTimes, currentThread->startTime, getCurrentTime());
				avg_resp_time = (avg_resp_time * (numResponseTimes) + (getCurrentTime() - currentThread->startTime)) / (numResponseTimes + 1);
				numResponseTimes++;
			}
			startTimer();
			swapcontext(&scheduleThread->context, &currentThread->context);
		} else {
			//fprintf(stderr, "breaking out of loop. End of all");
			break;
		}
    }
}

//DO NOT MODIFY THIS FUNCTION
/* Function to print global statistics. Do not modify this function.*/
void print_app_stats(void) {

       fprintf(stderr, "Total context switches %ld \n", tot_cntx_switches);
       fprintf(stderr, "Average turnaround time %lf \n", avg_turn_time);
       fprintf(stderr, "Average response time  %lf \n", avg_resp_time);
}


// Feel free to add any other functions you need

// YOUR CODE HERE

void printQueue(List* list) {
	Node* ptr = list->head;
	if (list->head == NULL || list->tail == NULL) {
		fprintf(stderr, "Queue: Empty\n");
		return;
	}
	//fprintf(stderr, "Head: %d, Tail: %d\n", list->head->entry->id, list->tail->entry->id);
	if (ptr->entry == NULL) {
		fprintf(stderr, "ptr->entry is null, ");
	} else fprintf(stderr, "idk, ");
	fprintf(stderr, "ptr->entry->id: %d\n", ptr->entry->id);
	fprintf(stderr, "Queue: ");
	int x = 1;
	
	while (ptr->next != NULL) {
		fprintf(stderr, "Thread: %d, Count(%d) -> ", ptr->entry->id, /*ptr->entry->elapsed*/x);
		ptr = ptr->next;
	}
	fprintf(stderr, "Thread: %d, Count(%d) -> NULL\n", ptr->entry->id, /*ptr->entry->elapsed*/x);
}
void printPriorityQueue(List* list) {
	Node* ptr = list->head;
	if (list->head == NULL || list->tail == NULL) {
		fprintf(stderr, "Queue: Empty\n");
		return;
	}
	//fprintf(stderr, "Head: %d, Tail: %d\n", list->head->entry->id, list->tail->entry->id);
	fprintf(stderr, "High Prio %d: ", HIGH_PRIO);
	while (ptr->next != NULL) {
		if (ptr->entry->priority == HIGH_PRIO) fprintf(stderr, "Thread: %d, Count(%d) -> ", ptr->entry->id, ptr->entry->elapsed);
		ptr = ptr->next;
	}
	if (ptr->entry->priority == HIGH_PRIO) fprintf(stderr, "Thread: %d, Count(%d) -> NULL", ptr->entry->id, ptr->entry->elapsed);
	fprintf(stderr, "\n");
	fprintf(stderr, "Medium Prio %d: ", MEDIUM_PRIO);
	ptr = list->head;
	while (ptr->next != NULL) {
		if (ptr->entry->priority == MEDIUM_PRIO) fprintf(stderr, "Thread: %d, Count(%d) -> ", ptr->entry->id, ptr->entry->elapsed);
		ptr = ptr->next;
	}
	if (ptr->entry->priority == MEDIUM_PRIO) fprintf(stderr, "Thread: %d, Count(%d) -> NULL", ptr->entry->id, ptr->entry->elapsed);
	fprintf(stderr, "\n");
	fprintf(stderr, "Default Prio %d: ", DEFAULT_PRIO);
	ptr = list->head;
	while (ptr->next != NULL) {
		if (ptr->entry->priority == DEFAULT_PRIO) fprintf(stderr, "Thread: %d, Count(%d) -> ", ptr->entry->id, ptr->entry->elapsed);
		ptr = ptr->next;
	}
	if (ptr->entry->priority == DEFAULT_PRIO) fprintf(stderr, "Thread: %d, Count(%d) -> NULL", ptr->entry->id, ptr->entry->elapsed);
	fprintf(stderr, "\n");
	fprintf(stderr, "Low Prio %d: ", LOW_PRIO);
	ptr = list->head;
	while (ptr->next != NULL) {
		if (ptr->entry->priority == LOW_PRIO) fprintf(stderr, "Thread: %d, Count(%d) -> ", ptr->entry->id, ptr->entry->elapsed);
		ptr = ptr->next;
	}
	if (ptr->entry->priority == LOW_PRIO) fprintf(stderr, "Thread: %d, Count(%d) -> NULL", ptr->entry->id, ptr->entry->elapsed);
	fprintf(stderr, "\n");
}
void printMutexes(List* list) {
	Node* ptr = list->head;
	if (list->head == NULL || list->tail == NULL) {
		fprintf(stderr, "Queue: Empty\n");
		return;
	}
	fprintf(stderr, "Head: %d, Tail: %d\n", list->head->mutex_entry->id, list->tail->mutex_entry->id);
	fprintf(stderr, "Mutex Queue: ");
	while (ptr->next != NULL) {
		fprintf(stderr, "%d -> ", ptr->mutex_entry->id);
		ptr = ptr->next;
	}
	fprintf(stderr, "%d -> NULL\n", ptr->mutex_entry->id);
}
void enqueue(void* obj, List* list) {
	if (list->head == NULL) {
		list->head = malloc(sizeof(Node));
		list->head->entry = obj;
		list->head->next = NULL;
		list->head->prev = NULL;
		list->tail = list->head;
		return;
	}
	Node* newHead = malloc(sizeof(Node));
	newHead->entry = obj;
	newHead->next = list->head;
	newHead->prev = NULL;
	list->head->prev = newHead;
	list->head = newHead;
}
void dequeue(List* list) {
	if (list->tail == NULL) return;
	Node* oldTail = list->tail;
	list->tail = list->tail->prev;
	if (list->tail == NULL) {
		list->head = NULL;
		free(oldTail);
		return;
	}
	list->tail->next = NULL;
	free(oldTail);
}
void enqueueAtEnd(tcb* obj, List* list) {
	if (list->head == NULL) {
		list->head = malloc(sizeof(Node));
		list->head->entry = obj;
		list->head->next = NULL;
		list->head->prev = NULL;
		list->tail = list->head;
		return;
	}
	Node* newTail = malloc(sizeof(Node));
	newTail->entry = obj;
	newTail->next = NULL;
	newTail->prev = list->tail;
	list->tail->next = newTail;
	list->tail = newTail;
}
void moveShortestJobToFront(List* list) {
	if (list->tail == NULL || list->head == list->tail) return;
	Node* ptr = list->head->next;
	tcb* currentShortestJob = list->head->entry;
	while (ptr != NULL) {
		if (currentShortestJob->elapsed >= ptr->entry->elapsed) {
			currentShortestJob = ptr->entry;
		}
		ptr = ptr->next;
	}
	dequeueByID(currentShortestJob->id, list);
	enqueueAtEnd(currentShortestJob, list);
}
void movePriorityJobToFront(List* list) {
	if (list->tail == NULL || list->head == list->tail) return;
	Node* ptr = list->head->next;
	tcb* currentPriorityJob = list->head->entry;
	while (ptr != NULL) {
		if (currentPriorityJob->priority <= ptr->entry->priority) {
			currentPriorityJob = ptr->entry;
		}
		ptr = ptr->next;
	}
	dequeueByID(currentPriorityJob->id, list);
	enqueueAtEnd(currentPriorityJob, list);
}
void moveAllJobsToPriority(List* list) {
	Node* ptr = list->head;
	while (ptr != NULL) {
		ptr->entry->priority = HIGH_PRIO;
		ptr->entry->lastPriorityChange = ptr->entry->elapsed;
		ptr = ptr->next;
	}
}
int queueHasID(worker_t id, List* list) {
	Node* ptr = list->head;
	while (ptr != NULL) {
		if (ptr->entry->id == id) return 1;
		ptr = ptr->next;
	}
	return 0;
}
void* dequeueByID(worker_t id, List* list) {
	if (list->tail == NULL) return NULL;
	Node* ptr = list->head;
	while (ptr != NULL) {
		if (ptr->entry->id == id) {
			void* res = ptr->entry;
			if (ptr == list->head) {
				if (ptr == list->tail) {
					list->head = NULL;
					list->tail = NULL;
				} else {
					list->head = list->head->next;
					list->head->prev = NULL;
				}
			} else if (ptr == list->tail) {
				list->tail = list->tail->prev;
				list->tail->next = NULL;
			} else {
				ptr->prev->next = ptr->next;
				ptr->next->prev = ptr->prev;
			}
			free(ptr);
			return res;
		}
		ptr = ptr->next;
	}
	return NULL;
}
void enqueueMutex(void* obj, List* list) {
	if (list->head == NULL) {
		list->head = malloc(sizeof(Node));
		list->head->mutex_entry = obj;
		list->head->next = NULL;
		list->head->prev = NULL;
		list->tail = list->head;
		return;
	}
	Node* newHead = malloc(sizeof(Node));
	newHead->mutex_entry = obj;
	newHead->next = list->head;
	newHead->prev = NULL;
	list->head->prev = newHead;
	list->head = newHead;
}
void* dequeueByMutex(worker_t id, List* list) {
	if (list->tail == NULL) return NULL;
	Node* ptr = list->head;
	while (ptr != NULL) {
		if (ptr->mutex_entry->id == id) {
			void* res = ptr->mutex_entry;
			if (ptr == list->head) {
				if (ptr == list->tail) {
					list->head = NULL;
					list->tail = NULL;
				} else {
					list->head = list->head->next;
					list->head->prev = NULL;
				}
			} else if (ptr == list->tail) {
				list->tail = list->tail->prev;
				list->tail->next = NULL;
			} else {
				ptr->prev->next = ptr->next;
				ptr->next->prev = ptr->prev;
			}
			free(ptr);
			return res;
		}
		ptr = ptr->next;
	}
	return NULL;
}
int mutexesHasID(worker_t id, List* list) {
	Node* ptr = list->head;
	while (ptr != NULL) {
		if (ptr->mutex_entry->id == id) return 1;
		ptr = ptr->next;
	}
	return 0;
}
void dequeueEnqueueThreadByMutexID(worker_t id, List* list) {
	if (list->tail == NULL) return;
	Node* ptr = list->head;
	while (ptr != NULL) {
		if (ptr->entry->mutexID == id) {
			tcb* res = ptr->entry;
			if (ptr == list->head) {
				if (ptr == list->tail) {
					list->head = NULL;
					list->tail = NULL;
				} else {
					list->head = list->head->next;
					list->head->prev = NULL;
				}
			} else if (ptr == list->tail) {
				list->tail = list->tail->prev;
				list->tail->next = NULL;
			} else {
				ptr->prev->next = ptr->next;
				ptr->next->prev = ptr->prev;
			}
			res->mutexID = -5;
			enqueue(res, queueList);
		}
		ptr = ptr->next;
	}
}
tcb* getThreadByID(worker_t id, List* list) {
	Node* ptr = list->head;
	while (ptr != NULL) {
		if (ptr->entry->id == id) {
			tcb* obj = ptr->entry;
			return obj;
		}
		ptr = ptr->next;
	}
	return NULL;
}
tcb* waitListHasElement(worker_t id) {
	Node* ptr = waitList->head;
	while (ptr != NULL) {
		if (ptr->entry->waitID == id) {
			tcb* obj = ptr->entry;
			obj->priority = 0;
			obj->lastPriorityChange = obj->elapsed;
			dequeueByID(ptr->entry->id, waitList);
			return obj;
		}
		ptr = ptr->next;
	}
	return NULL;
}
void stopTimer() {
	//fprintf(stderr, "End Timer\n");
	//printf()

	timer.it_interval.tv_usec = 0; 
	timer.it_interval.tv_sec = 0;

	timer.it_value.tv_usec = 0;
	timer.it_value.tv_sec = 0;

	setitimer(ITIMER_PROF, &timer, NULL);
}
void startTimer() {
	//fprintf(stderr, "Start Timer\n");

	timer.it_interval.tv_usec = 0; 
	timer.it_interval.tv_sec = 0;

	timer.it_value.tv_usec = TIME_QUANTUM;
	timer.it_value.tv_sec = 0;

	// Set the timer up (start the timer)
	setitimer(ITIMER_PROF, &timer, NULL);

	//while(1);
}
void handleTimer(int signum) {
	//fprintf(stderr, "Handle Timer, No Interrupt: %d\n", noInterrupt);
	totalTimeElapsed++;
	stopTimer();
	if (!noInterrupt) {
		//fprintf(stderr, "Handle Timer, Timer Success: %d\n", handleTimerFailed);
		swapcontext(&currentThread->context, &scheduleThread->context);
	} else {
		//fprintf(stderr, "Handle Timer, Timer Failed: %d\n", handleTimerFailed);
		handleTimerFailed = 1;
	}
}
void keepContext() {
    noInterrupt = 1;
}
void resumeNormalContext() {
	if (handleTimerFailed) {
		handleTimerFailed = 0;
		noInterrupt = 0;
		swapcontext(&currentThread->context, &scheduleThread->context);
	}
}
double getCurrentTime() {
	struct timespec currTime;
	clock_gettime(CLOCK_MONOTONIC, &currTime);
	return (double) (currTime.tv_nsec) / 1000000 + (currTime.tv_sec) * 1000;
}
void initializeScheduler() {
	//fprintf(stderr, "Main Thread creation process started\n");
	void* mainStack = NULL;
   	mainThread = malloc(sizeof(tcb));
	mainThread->id = nextThreadID++;
	mainThread->threadFinished = 0;
	mainThread->elapsed = 1;
	mainThread->priority = HIGH_PRIO;
	mainThread->lastPriorityChange = 1;
	getcontext(&mainThread->context);
	mainThread->context.uc_link = NULL;

	currentThread = mainThread;

	queueList = malloc(sizeof(List));
	queueList->head = NULL;
	queueList->tail = NULL;

	waitList = malloc(sizeof(List));
	waitList->head = NULL;
	waitList->tail = NULL;

	finishedList = malloc(sizeof(List));
	finishedList->head = NULL;
	finishedList->tail = NULL;

	if (mutexList == NULL) {
		mutexList = malloc(sizeof(List));
		mutexList->head = NULL;
		mutexList->tail = NULL;

		blockList = malloc(sizeof(List));
		blockList->head = NULL;
		blockList->tail = NULL;
	}
	enqueue(mainThread, queueList);
	//fprintf(stderr, "Schedule Thread creation process started\n");
			
	// TIMER
	struct sigaction sa;
	memset (&sa, 0, sizeof (sa));
	sa.sa_handler = &handleTimer;
	sigaction (SIGPROF, &sa, NULL);

	startTimer();
	////////////////////////////////////////

	scheduleThread = malloc(sizeof(tcb));
	void* scheduleStack = malloc(STACK_SIZE);
	getcontext(&scheduleThread->context);
	scheduleThread->context.uc_stack.ss_sp = scheduleStack;
	scheduleThread->context.uc_stack.ss_size = STACK_SIZE;
	scheduleThread->context.uc_stack.ss_flags = 0;
	scheduleThread->context.uc_link = NULL;
	makecontext(&scheduleThread->context, schedule, 0);
}