SOFT3410 Tutorial 5 Dynamic Memory and Threads
The goal of this lab is to act as an introduction to threads and encounter some parallel problems
Question 1: Malloc and Free
Unlike Java, C’s heap allocation is explicit and depends on standard library functions. The functions we will be using for heap allocation are malloc and free. Lets build a two-dimensional jagged array.
…
int** rows = ….
….
for(int i = 0; i < 4; i++) {
for(int j = 0; j < lens[i]; j++) { *((*(rows+i))+j) = j+1;
} }
for(int i = 0; i < 4; i++) {
for(int j = 0; j < lens[i]; j++) {
printf("%d ", rows[i][j]);
}
puts(""); }
...
Given this segment, how could we allocate memory for rows, how is the data accessed and do we need to allocate memory for for each individual row? Use this code segment and provide the correct allocation scheme.
What happens at the end of your program? Do we need to use free?
1
Question 2: Stack
Given the following struct definitions and function declaration, implement the logic for a linked stack.
struct stack_node {
void* val;
struct stack_node* next;
};
struct stack {
struct stack_node* top; size_t size;
};
void* stack_pop_object(struct stack* s);
void stack_push_copy(struct stack* s, void* data, size_t nbytes); void* stack_peek(struct stack* s);
Question 3: Linked List Map
Constructing basic data structures in C is a great way to get acquainted with memory ownership and reference semantics. For this task, you will need to create a variation of a linked list that will couple keys and values.
Your linked list map must not include duplicate keys and can support a variety of key and value types. Use the following declarations to construct your map.
struct linkedlist_map_entry; struct linkedlist_map;
struct linkedlist_map* linkedlist_map_new(int (*cmp)(void*, void*), void (*keydel)(void*), void(*valdel)(void*));
void linkedlist_map_put(struct linkedlist_map* map, void* key void* value); void* linkedlist_map_get(struct linkedlist_map* map, void* key);
void* linkedlist_map_remove(struct linkedlist_map* map, void* key);
size_t linkedlist_map_size(struct linkedlist_map* map);
void linkedlist_map_destroy(struct linkedlist_map* n); You can safely assume the following.
• keys and values given to the map via put will take ownership of the data
• When remove is called, value will be transferred to caller but key will be deallocated • When get is called, it will provide a reference but will not transfer ownership to caller • Any keys and values stored in the map must be deallocated when destroyed
SOFT3410 Dynamic Memory and Threads
Concurrency Page 2 of 5
Question 4: Welcome to threads
Up until now, most of your programs have involved only a single thread. Within this lab we will explore initialising threads and writing separate thread functions. Given the following segment, you should be able to observe the output from the program below.
Update the code to output thread id more than two times.
struct thread_data { int tid;
};
void* work1(void* arg) {
struct thread_data* data = (struct thread_data*) arg; printf("Hello from thread %d\n", data->tid);
return NULL;
}
int main() {
}
struct thread_data data = { { 1 }, { 2 } }; pthread_t threads[2];
pthread_create(threads, NULL, work1, &data); pthread_create(threads+1, NULL, work2, &data); printf(“main thread has created threads\n”);
pthread_join(threads[0], NULL);
pthread_join(threads[1], NULL);
printf(“program finished\n”); return 0;
Discuss with your class the following.
• How is data passed to the thread?
• How is the thread started
• How do we rejoin the thread with the main thread?
SOFT3410 Dynamic Memory and Threads
Concurrency
Page 3 of 5
Question 5: False Sharing
Given the following segment of code, examine the performance, do you notice any issues when we increase the number of threads. Does the increase of threads correspond with an increase of perfor- mance or not?
struct thread_data { int* result;
int result_index; int* numbers;
int numbers_len; };
void* worker(void* data) {
struct thread_data* d = (struct thread_data*) d;
for(int i = 0; i < d->numbers_len; i++) { d->result[d->result_index] += d->numbers[i];
}
return NULL;
}
Question 6: Addressing False Sharing with Padding
Given the information that a cache line is 64 bytes, how could we resolve the false sharing issue using padding? How could we transform the data?
Question 7: Ruining our linked list
Design a program that will share a linked list among multiple threads, where each thread will add elements to the linked list. Run the program and observe the results, if it happens to finished, your program should attempt to traverse the linked list and ensure that all elements were added.
• What did you observe with your program?
• If a problem is occuring, what could causing it?
• What issues can arise when you share data among threads?
• If you were use a global variable instead of separate thread data objects, what issues could arise?
• When data is shared between threads, do you notice a speed up with multiple threads?
SOFT3410 Dynamic Memory and Threads
Concurrency Page 4 of 5
Question 8: Hoarder and Maker
Unfortunately we can’t have multiple threads working on our linked list, however we can ensure that any data sent to our linked list is by one thread.
For this problem you are required to give roles to two threads.
• Thread 1 will be responsible for accepting storing data sent to it, it will use a linked list map to store the data
• Thread 2 will be responsible for sending data to Thread 1
As implied by the title of the question, one thread is a hoarder and the other is a maker. Use a pipe to satisfy this constraint.
SOFT3410 Dynamic Memory and Threads
Concurrency Page 5 of 5