3 Different Threads are created and are all constantly competing for CPU resources to add up various sums.
#include#include #include #include #include #include /*global variables*/ int N = 10000; //1000 Variables int seq = 0; int k = 100; int m = 200; //memory cells /*structs*/ typedef struct { int memLookTable[200]; int physicalTable[200]; int metaTable[200]; } memoryStruct; /*global variables part II */ int disk[10000]; memoryStruct memory; pthread_mutex_t memLock; FILE *output; /*method declarations*/ void initMemory(); int fetch(int i); void pageInLeast(int i); void pageInMost(int i); void pageInRandom(int i); void* tOne(void *arg); void* tTwo(void *arg); void* tThree(void *arg); void printThread(); int main() { initMemory(); output = fopen("output.txt" , "w"); pthread_mutex_init(&memLock, NULL); //initializing the lock for memory int iret1, iret2, iret3; pthread_t thread1, thread2, thread3; pthread_create(&thread1, NULL, tOne, (void *) 10); pthread_create(&thread2, NULL, tTwo, (void *) 10); pthread_create(&thread3, NULL, tThree, (void *) 10); pthread_join(thread1, NULL); pthread_join(thread2, NULL); pthread_join(thread3, NULL); printf("Done!\n"); fclose(output); } //Complete Random Order void* tThree(void *arg) { int task = 0; int done = 0; int i = 0; int adder; int hasLock = 0; int r; //random while(done == 0) //while the entire thread is not done { int sum = 0; while(i <= k) //compute the sum of X_r2 to X_(rk) where r is a random number { r = rand() % N; if(hasLock == 0) //if thread doesn't have lock (had to page previous iteration) { pthread_mutex_lock(&memLock); seq++; hasLock = 1; } adder = fetch(r); if (adder != -1) //variable is in memory { sum = sum + adder; i++; } else //variable needs to be paged { pageInRandom(r); adder = fetch(r); pthread_mutex_unlock(&memLock); hasLock = 0; if (adder != -1) { sum = sum + adder; i++; } else printf("ERROR in thread 3! r=%i\n", r); } } //task is done if(hasLock == 1) //if it still has the lock { pthread_mutex_unlock(&memLock); hasLock = 0; } printThread(3, task); task++; if(task > 2000) done = 1; } } //Sequential Order void* tTwo(void *arg) { int task = 0; int done = 0; int i = 0; int adder; int hasLock = 0; int a = 0; //what to add to k while(done == 0) //while the entire thread is not done { int sum = 0; while(i <= (k+a)) //compute the sum of X_1 to X_(k+a) { if(hasLock == 0) //if thread doesn't have lock (had to page previous iteration) { pthread_mutex_lock(&memLock); seq++; hasLock = 1; } adder = fetch(i); if (adder != -1) //variable is in memory { sum = sum + adder; i++; } else //variable needs to be paged { pageInRandom(i); adder = fetch(i); pthread_mutex_unlock(&memLock); hasLock = 0; if (adder != -1) { sum = sum + adder; i++; } else printf("ERROR in thread 2!\n"); } } //task is done if(hasLock == 1) //if it still has the lock { pthread_mutex_unlock(&memLock); hasLock = 0; } printThread(2, task); task ++; a++; if(task > 2000) done = 1; } } //Common Hot Set void* tOne(void *arg) { int task = 0; int done = 0; int i = 0; int adder; int hasLock = 0; while(done == 0) //while the entire thread is not done { int sum = 0; while(i < k) //compute the sum of 1 to k-1 variables { if(hasLock == 0) //if thread doesn't have lock (had to page previous iteration) { pthread_mutex_lock(&memLock); seq++; hasLock = 1; } adder = fetch(i); if (adder != -1) //variable is in memory { sum = sum + adder; i++; } else //variable needs to be paged { pageInRandom(i); adder = fetch(i); pthread_mutex_unlock(&memLock); hasLock = 0; if (adder != -1) { sum = sum + adder; i++; } else printf("ERROR in thread 1!\n"); } } int r = rand() % (N-k); if(hasLock == 0) //if thread doesn't have lock (had to page previous iteration) { pthread_mutex_lock(&memLock); seq++; hasLock = 1; } adder = fetch(r); if (adder != -1) //variable is in memory sum = sum + adder; else //variable needs to be paged { pageInRandom(r); adder = fetch(r); pthread_mutex_unlock(&memLock); hasLock = 0; if (adder != -1) { sum = sum + adder; } else printf("ERROR in Thread 1! r=%i\n", r); } //task is done printThread(1, task); task++; if(hasLock == 1) //if it still has the lock { pthread_mutex_unlock(&memLock); hasLock = 0; } //10 Tasks if(task > 2000) done = 1; } } void printThread(int thread, int task) { fprintf(output, "(%i), (%i), (%i)\n" , thread, task, seq); printf("(Thread: %i), (Task: %i), (Task Seq: %i)\n", thread, task, seq); } void initMemory() { int i; for(i=0; i < m; i++) { memory.memLookTable[i] = -1; memory.physicalTable[i] = -1; } } /* Check to see if X_i is in memory yes: return value no: return -1 */ int fetch(int i) { int b; for(b=0; b < m; b++) { if(memory.memLookTable[b] == i) //variable is not in memory return memory.physicalTable[b]; } return -1; //else //variable IS in memory //return memory.physicalTable[i]; } /* LEAST RECENTLY USED ALGORITHM puts value of X_i from disk to memory by ^ if a value in memory must be evicted, it must be written back to disk first */ void pageInLeast(int i) { int index = checkEmptyMemorySlot(); if(index != -1)//if nothing needs to be evicted { memory.memLookTable[index] = i; memory.physicalTable[index] = disk[i]; memory.metaTable[index] = seq; } else //evict something { //find smallest value in metaTable int q, small, smallIndex; for(q=0; q < m; q++) //after done, smallIndex is the smallest metaTable index { if(q==0) { small = memory.metaTable[0]; //initial value smallIndex = 0; } else if (small > memory.metaTable[q]) //if a smaller meta value is found { small = memory.metaTable[q]; smallIndex = q; } } //Place Evicted Value back in disk memory.metaTable[smallIndex] = seq; int temp = memory.memLookTable[smallIndex]; disk[temp] = memory.physicalTable[smallIndex]; //Pagining in new value memory.memLookTable[smallIndex] = i; memory.physicalTable[smallIndex] = disk[i]; } } //Returns -1 if memory is full, else returns the index of an open slot in memory int checkEmptyMemorySlot() { int i; for(i=0; i < m; i++) { if(memory.memLookTable[i] == -1) return i; } return -1; } /* Most RECENTLY USED ALGORITHM puts value of X_i from disk to memory by ^ if a value in memory must be evicted, it must be written back to disk first */ void pageInMost(int i) { int index = checkEmptyMemorySlot(); if(index != -1)//if nothing needs to be evicted { memory.memLookTable[index] = i; memory.physicalTable[index] = disk[i]; memory.metaTable[index] = seq; } else //evict something { //find biggest value in metaTable int q, big, bigIndex; for(q=0; q < m; q++) //after done, bigIndex is the biggest metaTable index { if(q==0) big = memory.metaTable[0]; //initial value else if (big < memory.metaTable[q]) //if a smaller meta value is found { big = memory.metaTable[q]; bigIndex = q; } } //Place Evicted Value back in disk memory.metaTable[bigIndex] = seq; int temp = memory.memLookTable[bigIndex]; disk[temp] = memory.physicalTable[bigIndex]; //Pagining in new value memory.memLookTable[bigIndex] = i; memory.physicalTable[bigIndex] = disk[i]; } } /* Random ALGORITHM puts value of X_i from disk to memory by ^ if a value in memory must be evicted, it must be written back to disk first */ void pageInRandom(int i) { int index = checkEmptyMemorySlot(); if(index != -1)//if nothing needs to be evicted { memory.memLookTable[index] = i; memory.physicalTable[index] = disk[i]; } else //evict something { //picking a random value to evict int r; r = rand() % m; //random number 0-999 //Place Evicted Value back in disk int temp = memory.memLookTable[r]; disk[temp] = memory.physicalTable[r]; //Pagining in new value memory.memLookTable[r] = i; memory.physicalTable[r] = disk[i]; } }
Posts
