Question: Given an integer array S of length N(N=100,000),there are M(M≥2) workers concurrently accessing and updating S.Each worker repeats the following operation 10,000 times: Generate random numbers i and j, 0≤i, j<100,000. Update S such that S(j)=S(i)+S(i+1)+S(i+2). If i+1 or i+2 is out of bounds, then use (i+1)%N or (i+2)%N. Hint: (a) Please consider concurrent protection,i.e.. reading S(i),S(i+1),S(i+2) and updating S(j) are atomic operations. *Refer to the two-phase locking algorithm. (b) Pay attention to the lock granularity. Each worker only reads 3 elements at a time and writes 1 element. There are a total of 100,000 elements. The probability that concurrent workers access the same element is very low. Using fine-grainted locks can reduce conflicts and improve concurrency. (c) Pay attention to the difference between read locks and write locks. (d) j may fall in the [i, i+2] range. (e) Addtional thinking: Will deadlock occur? How to avoid?
Regarding to this question, I tried using segmented locking technique. This method divides the shared array into multiple segments, each segment is protected by a mutex, and each thread only needs to lock the segment it accesses. Is this idea feasible or are there any better suggestions?