多线程面试题

细颗粒度读写锁

题目：

给定一个长度为N(N=100,000)的整数数组S，有M(M>=2)个工人并发访问和更新S。每个工人重复以下操作10,000次:生成随机数i和j，0<=i,j<100,000。更新S使得S(j)=S(1)+S(i+1)+S(i+2)。如果i+1或i+2越界，则使用(i+1)%N或(i+2)%N。

提示:

(a)请考虑并发保护，即读取S(i)、S(i+1)、S(+2)和更新S(j)是原子操作。参考两阶段锁定算法
(b)注意锁的粒度。每个工人一次只读3个元素，写1个元素。总共有100,000个元素。并发工人访问相同元素的概率非常低。使用细粒度锁可以减少冲突并提高并发性。
(c)注意读锁和写锁之间的区别。
(d)j可能落在[i,i+2]范围内。
(e)额外思考:会发生死锁吗?如何避免?

代码

#include <iostream>
#include <vector>
#include <shared_mutex>
#include <thread>
#include <random>
#include <algorithm>

const int N = 100000; // 数组大小
const int M = 10;//线程数目
const int MAXNUM = 10000;//轮询次数
std::vector<int> S(N, 0);
std::vector<std::shared_mutex> locks(N); // 共享锁

std::pair<int, int> generateRandomNumbers() {//获取随机数
    static std::mt19937 gen(std::random_device{}());
    std::uniform_int_distribution<> dis(0, N - 1);
    int i = dis(gen);
    int j = dis(gen);
    return { i, j };
}

void workerOperation(int threadId) {
    
    for (int k = 0; k < MAXNUM; ++k) {
        auto tt = generateRandomNumbers();
        int i = tt.first;
        int j = tt.second;

        // 保证加锁顺序，从小到大，并且去重
        std::vector<int> lockIndexes = { i, (i + 1) % N, (i + 2) % N, j };
        std::sort(lockIndexes.begin(), lockIndexes.end());
        lockIndexes.erase(std::unique(lockIndexes.begin(), lockIndexes.end()), lockIndexes.end());

        // 加读锁和写锁
        std::vector<std::shared_lock<std::shared_mutex>> readLocks;
        std::unique_lock<std::shared_mutex> writeLock;

        //保证加锁顺序,并且加不同的锁
        for (const auto& index : lockIndexes) {
            if (index != j) {
                readLocks.emplace_back(locks[index]);
            }
            else {
                writeLock = std::unique_lock<std::shared_mutex>(locks[index]);
            }
        }

        S[j] = S[i] + S[(i + 1) % N] + S[(i + 2) % N];
    }
}

int main() {
    std::vector<std::thread> workers;

    for (int i = 0; i < M; ++i) {
        std::cout << i << std::endl;
        workers.emplace_back(workerOperation, i);
    }

    for (auto& worker : workers) {
        worker.join();
    }
    
    return 0;
}