aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-04-02 23:09:10 -0600
committerJack Sangdahl <[email protected]>2024-04-02 23:09:10 -0600
commit6312e34a350ede7a73906792a8ff5d5efcf2f534 (patch)
tree205ecc2cd419deb394ebd5698720a4b840905810
parent8dbe92136c33a2254b617e6d5273d5499de5ad90 (diff)
downloadcsci3753-6312e34a350ede7a73906792a8ff5d5efcf2f534.tar.gz
csci3753-6312e34a350ede7a73906792a8ff5d5efcf2f534.zip
pa4
-rw-r--r--pa4_shared_array/Makefile11
-rw-r--r--pa4_shared_array/array.c55
-rw-r--r--pa4_shared_array/array.h48
-rw-r--r--pa4_shared_array/readme.md129
-rw-r--r--pa4_shared_array/test.c77
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;
+}