diff options
author | Jack Sangdahl <[email protected]> | 2024-04-02 23:09:10 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-04-02 23:09:10 -0600 |
commit | 6312e34a350ede7a73906792a8ff5d5efcf2f534 (patch) | |
tree | 205ecc2cd419deb394ebd5698720a4b840905810 | |
parent | 8dbe92136c33a2254b617e6d5273d5499de5ad90 (diff) | |
download | csci3753-6312e34a350ede7a73906792a8ff5d5efcf2f534.tar.gz csci3753-6312e34a350ede7a73906792a8ff5d5efcf2f534.zip |
pa4
-rw-r--r-- | pa4_shared_array/Makefile | 11 | ||||
-rw-r--r-- | pa4_shared_array/array.c | 55 | ||||
-rw-r--r-- | pa4_shared_array/array.h | 48 | ||||
-rw-r--r-- | pa4_shared_array/readme.md | 129 | ||||
-rw-r--r-- | pa4_shared_array/test.c | 77 |
5 files changed, 320 insertions, 0 deletions
diff --git a/pa4_shared_array/Makefile b/pa4_shared_array/Makefile new file mode 100644 index 0000000..02f4e1f --- /dev/null +++ b/pa4_shared_array/Makefile @@ -0,0 +1,11 @@ +OBJS = array.o test.o +CFLAGS = -Wall + +all: $(OBJS) + cc $(CFLAGS) -o shared_array $(OBJS) + +clean: + rm *.o shared_array + +array.o: array.h +test.o: array.h diff --git a/pa4_shared_array/array.c b/pa4_shared_array/array.c new file mode 100644 index 0000000..3a44566 --- /dev/null +++ b/pa4_shared_array/array.c @@ -0,0 +1,55 @@ +// Jack Sangdahl +// CSCI3753 SP24 +// PA4 Shared Array +#include "array.h" + +int array_init(array *s) { + s->top = 0; + s->array = (char **)malloc(ARRAY_SIZE * sizeof(char *)); + for (int i = 0; i < ARRAY_SIZE; i++) + s->array[i] = (char *)malloc(MAX_NAME_LENGTH * sizeof(char)); + sem_init(&s->mutex, 0, 1); + sem_init(&s->space, 0, ARRAY_SIZE); + sem_init(&s->items, 0, 0); + return 0; +} + +int array_put(array *s, char *hostname) { + if (s->top == ARRAY_SIZE - 1) { + printf("ERROR: stack full\n"); + return -1; + } + if (strlen(hostname) > MAX_NAME_LENGTH) { + printf("ERROR: %s size > %d\n", hostname, MAX_NAME_LENGTH); + return -1; + } + sem_wait(&s->space); + sem_wait(&s->mutex); + strcpy(s->array[s->top++], hostname); + sem_post(&s->mutex); + sem_post(&s->items); + return 0; +} + +int array_get(array *s, char **hostname) { + if (!s->top) { + printf("ERROR: stack empty\n"); + return -1; + } + sem_wait(&s->items); + sem_wait(&s->mutex); + *hostname = (char *)malloc(MAX_NAME_LENGTH * sizeof(char)); + strcpy(*hostname, s->array[--s->top]); + sem_post(&s->mutex); + sem_post(&s->space); + return 0; +} + +void array_free(array *s) { + for (int i = 0; i < ARRAY_SIZE; i++) + free(s->array[i]); + free(s->array); + sem_destroy(&s->mutex); + sem_destroy(&s->space); + sem_destroy(&s->items); +} diff --git a/pa4_shared_array/array.h b/pa4_shared_array/array.h new file mode 100644 index 0000000..9d67e1e --- /dev/null +++ b/pa4_shared_array/array.h @@ -0,0 +1,48 @@ +// Jack Sangdahl +// CSCI3753 SP24 +// PA4 Shared Array +#include <semaphore.h> +#include <stdint.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#define ARRAY_SIZE 8 // number of hostnames in data/ is 618 +#define MAX_NAME_LENGTH 16 // longest string length in data/ + +typedef struct { + char **array; + uint8_t top; + sem_t mutex; + sem_t space; + sem_t items; +} array; + +/** + * @brief initialise the array + * @param s + * @return int + */ +int array_init(array *s); + +/** + * @brief place element into array. block when full + * @param s + * @param hostname + * @return int + */ +int array_put(array *s, char *hostname); + +/** + * @brief remove element from the array. block when empty + * @param s + * @param hostname + * @return int + */ +int array_get(array *s, char **hostname); + +/** + * @brief free array's resources + * @param s + */ +void array_free(array *s); diff --git a/pa4_shared_array/readme.md b/pa4_shared_array/readme.md new file mode 100644 index 0000000..6ed3735 --- /dev/null +++ b/pa4_shared_array/readme.md @@ -0,0 +1,129 @@ +## PA4 - Shared Array +### introduction +you will build a thread-safe shared array that will then be used in pa6 to create a multi-threaded +dns resolver program. to help organise your code, it is required that a separate module be created +to solely deal with the shared array. the modularisation will allow you to build and test a shared +array abstraction without having to worry about details of pa6 solution. this approach is an +application of principal of separation of concerns. in order to illustrate how to build a program +as separate modules, we'll need to review the relationship between an interface and implementation + +### interface & implementation +when developing an abstraction, we usually start with the proposed interface. an interface is +similar to a contract, in this case between the users of an abstraction and the developer of the +code that implements that abstraction. as an example, consider the following method prototypes +that comprise the interface for a stack that stores integers +```c +int stack_init(stack *s); // initialize the stack +int stack_push(stack *s, int element); // place element on the top of the stack +int stack_pop (stack *s, int *element); // remove element from the top of the stack +void stack_free(stack *s); // free the stack's resources +``` + +in c, interfaces are defined in a standalone header file, so here's a more complete version of +`stack.h`, including the definition of a struct to hold our data: +```c +#ifndef STACK_H +#define STACK_H + +#define STACK_SIZE 10 // max elements in stack + +typedef struct { + int array[STACK_SIZE]; // storage array for integers + int top; // array index indicating where the top is +} stack; + +int stack_init(stack *s); // init the stack +int stack_push(stack *s, int element); // place element on the top of the stack +int stack_pop (stack *s, int *element); // remove element from the top of the stack +void stack_free(stack *s); // free the stack's resources + +#endif +``` + +notice that each method of our interface, other than `stack_free()` returns an integer to indicate +the status of the operation. generally, a zero return value means success, and anything else means +a failure. also note that `stack_pop()` passes the popped value back to the caller via a reference +the implementation (executable code) is contained in a c source file of the same name, `stack.c` +```c +#include "stack.h" + +int stack_init(stack *s) { // init the stack + s->top = 0; + return 0; +} + +int stack_push(stack *s, int element) { // place element on the top of the stack + if (s->top >= STACK_SIZE) return -1; // return failed if the stack is full + s->array[s->top++] = element; + return 0; +} + +int stack_pop(stack *s, int *element) { // remove element from the top of the stack + if (s->top < 1) return -1; // return failed if the stack is empty + *element = s->array[--s->top]; + return 0; +} + +void stack_free(stack *s) { // free the stack's resources +} +``` + +we can then test our code by writing a small program, `test.c`, that calls each of the methods of +our stack implementation: +```c +#include "stack.h" +#include <stdlib.h> +#include <stdio.h> + +int main() { + stack my_stack; + int i; + + if (stack_init(&my_stack) < 0) exit(-1); // init stack, exit if failed + while (stack_push(&my_stack, rand() % 10) == 0); // push random numbers until full + while (stack_pop(&my_stack, &i) == 0) printf("%d ", i); // pop and print until empty + stack_free(&my_stack); // destroy stack + exit(0); +} +``` + +compile and test: +```shell +$ cc test.c stack.c +./a.out +1 9 2 6 5 3 5 7 6 3 +``` + +### shared array +your thread-safe shared array will require you to implement a solution to the bounded buffer +problem as discussed in lecture and textbook. the shared array must be built on top of one or +more contiguous linear arrays of memory. you can organise this array as fifo, circular queue, +or lifo. we will not accept solutions that rely on linked lists, trees, dictionaries, etc. your +array should implement at minimum, the following interface +```c +int array_init(array *s); // initialize the array +int array_put (array *s, char *hostname); // place element into the array, block when full +int array_get (array *s, char **hostname); // remove element from the array, block when empty +void array_free(array *s); // free the array's resources +``` +this interface defines a shared array that stores hostnames as c strings. the size of your array +and the maximum size string that your array can handle should be defined by a macro in `array.h`: +```c +#define ARRAY_SIZE 8 +#define MAX_NAME_LENGTH xxx +``` +you'll need to determine an appropriate maximum hostname length based on the input data provided +in [pa4.zip](pa4.zip) and how you decide to implement the shared buffer. unlike above example, your shared +array must **incorporate some sort synchronisation and/or signaling mechanisms** (mutexes, semaphores, +condition variables, etc.) to ensure there are no race conditions or busy waiting. while c does +not implement them directly, you can consider designing something that works like a monitor. you +can use the same concepts used for monitors to ensure that race conditions don't creep into your +solution. you should also consider writing some unit tests that verify the functionality of your +array. your tests will need to exercise the array in such a way that you're ensuring thread safety. +generally, the way to do this is use `pthread_create()` to start a number of simultaneous threads, +each of which either put or get data to your shared array, multiple times. + +### submission +due date: **03.03.2024 23:59** +* `array.h` header containing prototypes for your shared array interface definition +* `array.c` source containing the implementation of your shared array diff --git a/pa4_shared_array/test.c b/pa4_shared_array/test.c new file mode 100644 index 0000000..7333a16 --- /dev/null +++ b/pa4_shared_array/test.c @@ -0,0 +1,77 @@ +// Jack Sangdahl +// CSCI3753 SP24 +// PA4 Shared Array +#include "array.h" +#include <dirent.h> +#include <pthread.h> +#include <stdio.h> +#define MAX_FILE_SIZE 255 +#define MAX_FILE_COUNT 30 +#define NUM_THREADS 10 + +array stack; +char *data, **hostnames; + +void gen_hostnames(char **hostnames) { + DIR *dptr = opendir("data"); + struct dirent *entry; + char filenames[MAX_FILE_COUNT][MAX_FILE_SIZE]; + uint8_t file_count = 0; + while ((entry = readdir(dptr))) + if (strstr(entry->d_name, ".txt")) { + strncpy(filenames[file_count], entry->d_name, MAX_FILE_SIZE); + file_count++; + if (file_count >= MAX_FILE_COUNT) + break; + } + closedir(dptr); + for (uint8_t i = 0; i < MAX_FILE_COUNT; i++) { + char *curr_file = (char *)malloc(strlen(filenames[i] + 6)); + strcpy(curr_file, "data/"); + strcat(curr_file, filenames[i]); + FILE *fptr = fopen(curr_file, "r"); + char *buffer = (char *)malloc(sizeof(char) * MAX_NAME_LENGTH); + uint8_t hostname_count = 0; + while (fgets(buffer, sizeof(buffer), fptr)) { + hostnames[hostname_count] = + (char *)malloc((strlen(buffer)) * sizeof(char)); + strcpy(hostnames[hostname_count], buffer); + hostname_count++; + } + free(buffer), free(curr_file); + fclose(fptr); + } +} + +void *thread_produce(void *a) { + for (uint8_t i = 0; i < ARRAY_SIZE; i++) + array_put(&stack, hostnames[i]); + return NULL; +} + +void *thread_consume(void *a) { + for (uint8_t i = 0; i < ARRAY_SIZE; i++) + array_get(&stack, &data); + return NULL; +} + +int main(int argc, char **argv) { + pthread_t *produce = malloc(NUM_THREADS * sizeof(pthread_t)); + pthread_t *consume = malloc(NUM_THREADS * sizeof(pthread_t)); + hostnames = (char **)malloc(sizeof(char *) * MAX_FILE_SIZE); + gen_hostnames(hostnames); + for (int i = 0; i < ARRAY_SIZE; i++) + printf("%s\n", hostnames[i]); + array_init(&stack); + for (uint8_t i = 0; i < NUM_THREADS; i++) { + pthread_create(&produce[i], NULL, thread_produce, &stack); + pthread_create(&consume[i], NULL, thread_consume, &stack); + } + for (uint8_t i = 0; i < NUM_THREADS; i++) { + pthread_join(produce[i], NULL); + pthread_join(consume[i], NULL); + } + free(produce), free(consume), free(hostnames); + array_free(&stack); + return 0; +} |