take a non thread-safe version of a hash table and modify it so that it correctly supports running with multiple threads. Thank you

Start by downloading parallel_hashtable.c and compile it with:

$ gcc -pthread parallel_hashtable.c -o parallel_hashtable

Now run it with one thread:

$ ./parallel_hashtable 1 [main] Inserted 100000 keys in 0.006545 seconds [thread 0] 0 keys lost! [main] Retrieved 100000/100000 keys in 4.028568 seconds

So with one thread the program is correct. But now try it with more than one thread:

$ ./parallel_hashtable 8 [main] Inserted 100000 keys in 0.002476 seconds [thread 7] 4304 keys lost! [thread 6] 4464 keys lost! [thread 2] 4273 keys lost! [thread 1] 3864 keys lost! [thread 4] 4085 keys lost! [thread 5] 4391 keys lost! [thread 3] 4554 keys lost! [thread 0] 4431 keys lost! [main] Retrieved 65634/100000 keys in 0.792488 seconds

Play around with the number of threads. You should see that, in general, the program gets faster as you add more threads up until a certain point. However, sometimes items that get added to the hash table get lost.

Part 1

Find out under what circumstances entries can get lost. Update parallel_hashtable.c so that insert and retrieve do not lose items when run from multiple threads. Verify that you can now run multiple threads without losing any keys. Compare the speedup of multiple threads to the version that uses no mutex -- you should see that there is some overhead to adding a mutex.

You will probably need:

pthread_mutex_t lock; // declare a lock pthread_mutex_init(&lock, NULL); // initialize the lock pthread_mutex_lock(&lock); // acquire lock pthread_mutex_unlock(&lock); // release lock

You can use man to get more documentation on any of these.

Part 2

Does retrieving an item from the hash table require a lock? Update the code so that multiple retrieve operations can run in parallel.

Part 3

Update the code so that some insert operations can run in parallel. Hint: if two inserts are being done on different buckets in parallel, is a lock needed? What are the shared resources that need to be protected by mutexes?

Please show the modified parallel_hashtable.c and your partner.txt?

------------------------------------------------------------------------------------------------------------------

Please copy the parallel_hashtable.c below:

#include #include #include #include #include #include

#define NUM_BUCKETS 5 // Buckets in hash table #define NUM_KEYS 100000 // Number of keys inserted per thread int num_threads = 1; // Number of threads (configurable) int keys[NUM_KEYS];

typedef struct _bucket_entry { int key; int val; struct _bucket_entry *next; } bucket_entry;

bucket_entry *table[NUM_BUCKETS];

void panic(char *msg) { printf("%s ", msg); exit(1); }

double now() { struct timeval tv; gettimeofday(&tv, 0); return tv.tv_sec + tv.tv_usec / 1000000.0; }

// Inserts a key-value pair into the table void insert(int key, int val) { int i = key % NUM_BUCKETS; bucket_entry *e = (bucket_entry *) malloc(sizeof(bucket_entry)); if (!e) panic("No memory to allocate bucket!"); e->next = table[i]; e->key = key; e->val = val; table[i] = e; }

// Retrieves an entry from the hash table by key // Returns NULL if the key isn't found in the table bucket_entry * retrieve(int key) { bucket_entry *b; for (b = table[key % NUM_BUCKETS]; b != NULL; b = b->next) { if (b->key == key) return b; } return NULL; }

void * put_phase(void *arg) { long tid = (long) arg; int key = 0;

// If there are k threads, thread i inserts // (i, i), (i+k, i), (i+k*2) for (key = tid ; key < NUM_KEYS; key += num_threads) { insert(keys[key], tid); }

pthread_exit(NULL); }

void * get_phase(void *arg) { long tid = (long) arg; int key = 0; long lost = 0;

for (key = tid ; key < NUM_KEYS; key += num_threads) { if (retrieve(keys[key]) == NULL) lost++; } printf("[thread %ld] %ld keys lost! ", tid, lost);

pthread_exit((void *)lost); }

int main(int argc, char **argv) { long i; pthread_t *threads; double start, end;

if (argc != 2) { panic("usage: ./parallel_hashtable "); } if ((num_threads = atoi(argv[1])) <= 0) { panic("must enter a valid number of threads to run"); }

srandom(time(NULL)); for (i = 0; i < NUM_KEYS; i++) keys[i] = random();

threads = (pthread_t *) malloc(sizeof(pthread_t)*num_threads); if (!threads) { panic("out of memory allocating thread handles"); }

// Insert keys in parallel start = now(); for (i = 0; i < num_threads; i++) { pthread_create(&threads[i], NULL, put_phase, (void *)i); } // Barrier for (i = 0; i < num_threads; i++) { pthread_join(threads[i], NULL); } end = now(); printf("[main] Inserted %d keys in %f seconds ", NUM_KEYS, end - start); // Reset the thread array memset(threads, 0, sizeof(pthread_t)*num_threads);

// Retrieve keys in parallel start = now(); for (i = 0; i < num_threads; i++) { pthread_create(&threads[i], NULL, get_phase, (void *)i); }

// Collect count of lost keys long total_lost = 0; long *lost_keys = (long *) malloc(sizeof(long) * num_threads); for (i = 0; i < num_threads; i++) { pthread_join(threads[i], (void **)&lost_keys[i]); total_lost += lost_keys[i]; } end = now();

printf("[main] Retrieved %ld/%d keys in %f seconds ", NUM_KEYS - total_lost, NUM_KEYS, end - start);

return 0; }