/*
Implement a program that satisfies the requirements below.
1. Reads from the console a number E of elements and a number W of
threads (we will call them workers). (1p) DONE
2. Generates a linked list using the structure below containing E
elements and populates the "value" fields with random numbers. (2p) DONE
3. Populates the "worker" fields with values between 0 and W-1, so that
the difference between the number of elements of each worker is at
most 1, basically trying to distribute the work evenly among
workers) (1p) DONE
4. Creates W worker threads, each given its creation order number. Each
worker will continuously parse the linked list and for the elements
belonging to it (match the worker's order number with the elem
"worker" field) will replace the value with its square root. (2p)
5. The main thread of the program will be signaled to wake up from
waiting whenever 5 elements or all the elements left in the list
(if less than 5) have their value less than 2. Upon waking up, the
main thread eliminates the elements with values less than 2. The
program stops when the list is empty. (2p)
6. No more than 3 workers can access the linked list at the same
time. (2p)
struct elem {
int value;
int worker;
struct elem* next;
};
*/
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <fcntl.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <string.h>
#include <semaphore.h>
#include <math.h>
struct elem {
int value;
int worker;
struct elem* next;
};
struct elem* root;
pthread_mutex_t flg_mtx;
pthread_mutex_t main_mtx;
pthread_cond_t cond;
pthread_rwlock_t rwl;
sem_t sem;
int fiveFlg;
int doneFlg;
void printList(struct elem* root) {
while(root != NULL) {
printf("W %d V %d --> ", root->worker, root->value);
root = root->next;
}
printf("\n");
}
struct elem* createList(int numE, int numW) {
int i;
struct elem* aux = NULL;
for(i = 0; i < numE; i++) {
struct elem* e = (struct elem*)malloc(sizeof(struct elem));
e->value = rand() % 200;
e->worker = i % numW;
e->next = aux;
aux = e;
}
return aux;
}
void deleteNodes() {
struct elem * e = NULL;
struct elem * ee = NULL;
struct elem * aux = NULL;
e = root;
while(e != NULL) {
if(e->value < 2) {
if(ee != NULL) {
ee->next = e->next;
aux = e;
e = e->next;
free(aux);
} else {
aux = e;
e = e->next;
root = root->next;
free(aux);
}
} else {
ee = e;
e = e->next;
}
}
}
void * worker(void * wNum) {
int self = *(int *)wNum;
struct elem* aux;
int ok = 1;
printf("!!!Started thread number: %d\n", self);
while(ok == 1) {
ok = 0;
aux = root;
sem_wait(&sem);
while(aux != NULL) {
if(aux->worker == self && aux->value >= 2) {
ok = 1;
aux->value = (int)sqrt(aux->value);
//printf("Worker number: %d changed node value to: %d\n", self, aux->value);
if(aux->value < 2) {
printf("!!!Trying to get mutex for worker %d...\n", self);
pthread_mutex_lock(&flg_mtx);
printf("Thread %d: changed value to: %d (incrementing flag...)\n", self, aux->value);
fiveFlg ++;
if(fiveFlg == 5) {
printf("!!!Signaled Main!!!\n");
pthread_mutex_unlock(&flg_mtx);
pthread_cond_signal(&cond);
break;
} else {
pthread_mutex_unlock(&flg_mtx);
}
}
}
aux = aux->next;
}
sem_post(&sem);
}
aux = root;
ok = 1;
if(aux != NULL){
while(aux != NULL) {
if(aux->value >= 2) {
ok = 0;
}
aux = aux->next;
}
if(ok == 1) {
printf("!!!Sent last signal to main\n");
fiveFlg = 5;
pthread_cond_signal(&cond);
}
}
return NULL;
}
void initialiseSync() {
if(0 > sem_init(&sem, 0, 3)) {
printf("Failed to create semaphre\n");
exit(1);
}
if(pthread_mutex_init(&flg_mtx, NULL) != 0) {
printf("Failed to initialise the flag mutex\n");
exit(1);
}
if(pthread_rwlock_init(&rwl, NULL) != 0) {
printf("Failed to initialise rwlock\n");
exit(1);
}
if(pthread_cond_init(&cond, NULL) != 0) {
printf("Failed to initialise conditional variable\n");
exit(1);
}
}
void destroySync() {
sem_destroy(&sem);
pthread_mutex_destroy(&flg_mtx);
pthread_cond_destroy(&cond);
}
int main(int argc, char * argv[]) {
if(argc != 3) {
printf("Two parameters must be supplied!\n");
exit(1);
}
int numE, numW;
int i;
numE = atoi(argv[1]);
numW = atoi(argv[2]);
int wrkNums[numW];
pthread_t threads[numW];
root = NULL;
fiveFlg = 0;
doneFlg = 0;
printf("!!!Number of elements: %d Number of threads: %d\n\n", numE, numW);
srand(time(NULL));
initialiseSync();
root = createList(numE, numW);
printList(root);
printf("!!!Creating threads...\n");
for(i = 0; i < numW && i < numE; i++) {
wrkNums[i] = i;
pthread_create(&threads[i], NULL, worker, &wrkNums[i]);
}
printf("!!!Threads created successfully\n");
printf("!!!Trying to get the mutex in MAIN...\n");
pthread_mutex_lock(&flg_mtx);
while(root != NULL) {
printf("!!!Main is waiting for flag\n");
pthread_cond_wait(&cond, &flg_mtx);
printf("!!!Main got flag. Deleting nodes...\n");
printList(root);
deleteNodes();
fiveFlg = 0;
pthread_mutex_unlock(&flg_mtx);
printf("!!!Done deleting nodes\n");
printList(root);
}
printf("!!!Waiting for threads...\n");
for(i = 0; i < numW && i < numE; i++) {
pthread_join(threads[i], NULL);
}
printf("!!!Done waiting. Terminating...\n");
printList(root);
destroySync();
return 0;
}
Comments