Assignment 4 Solution

Task-1: Fix me! (20 Marks)




For this task, please refer to the code template and helper routines provided in part-1 folder and go through the README le carefully. In this task, a le is passed as input which is chucked into blocks of 64bytes and a hash is calculated for every block. An output array is used to store the calculated hash values of corresponding blocks. A serial implementation is provided in the provided code which does not work correctly when executed with more than one threads. Your task is to modify the hashit function in thread func.c to make it work correctly with more than one threads. Note that, the calculate and store hash function should be invoked without holding any locks. To test your program, you can use any existing le on your system. (see README)










Task-2: A miser’s read-write lock! (35 Marks)




A read-write lock allows multiple readers but one writer to enter the critical section. Refer to the slide#9 - #15 in https://www.cse.iitk.ac.in/users/deba/cs330/producer-consumer. pdf for details and an example implementation using semaphores. For this task, please refer to the code template and helper routines provided in part-2 folder and read the README le carefully.




The proposed RWLOCK uses a single 64-bit long integer. One of the ways to implement a read-write lock using a single variable is to use the single variable in an innovative manner as explained below.


































Value at the bit position 47 plays a crucial role in determining the state of the lock as explained below,




Value 0x1000000000000
--
unlocked
0x0000000000000
--
locked for writing
0xFFFFFFFFFFFF
--
one reader



1



0xFFFFFFFFFFFE -- two readers




.....




In the template code and helper les, you are provided with the implementation for atomic add (see common.h). The val argument can be negative. This function returns 0, 1 and -1 if the result of atomic add is zero, positive and negative, respectively. Implement the template functions in rwlock.c. A sample main program is also provided to test basic correctness (in main.c). However, you should use your own test programs to validate the lock implementation.










Task-3: Parallel hashing (45 marks)




For this task, please refer to the code template and helper routines provided in part-2 folder and read the README le carefully. Implement a parallel hash implementation (linear probing based). A serial implementation with the template and infrastructures are provided. Refer to the code and comments for details of the implementation. Note that, your implementation should not perform a global serialization of hash operation and try to achieve as much par-allelism as possible. Implementations equivalent to serial implementations will be awarded zero marks.







Submission guidelines




The assignment is to be done individually. You have to submit only three les (thread func.c (part-1), rwlock.c (part-2) and parallel hash.c (part-3)). Put these three les in a directory named with your roll number. Create a zip archive of the directory and upload in canvas.




Don’t modify any other les. We will not consider any le other than the above men-tioned les for evaluation.




You should remove all printf debug statements from submission les. We will taking di of your output and expected output for evaluation.







In-case of any issues you should reach out to us at the earliest. All the best!




















































2