1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
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
|