C++ 实现基于时序公平的读写锁

读写锁的功能

读写锁与普通的互斥锁的区别在于有两种上锁方式：读锁和写锁。不用的用户对同一个读写锁获取读锁是非互斥的，其他情况（读锁和写锁、写锁和写锁）则是互斥的。在“读”操作较多的情况下使用读写锁可以提高并发。

---

读写锁实现

由读写锁的功能可知，我们需要维护当前有多少个读者（当前占有读锁的数目）和当前是否有写者（当前是否上有写锁）这两个信息，这样就可以判断是否需要阻塞上锁操作，以及何时唤醒等待锁的请求。具体实现可以通过互斥量+条件变量来封装一个读写锁：

class naive_rw_lock {
public:
    void lock_read() {//获取读锁
        unique_lock lk(mut);
        cv.wait(lk, [&] { return !have_writer; });//当没有写者时可以获得锁
        cnt_reader++;//读者数+1
    }

    void unlock_read() {//释放读锁
        unique_lock lk(mut);
        if (--cnt_reader == 0)//读者数-1
            cv.notify_all();//如果当前是唯一的一个读者，则唤醒等待锁的请求
    }

    void lock_write() {//获取写锁
        unique_lock lk(mut);
        cv.wait(lk, [&] { return !have_writer && cnt_reader == 0; });//当没有写者也没有读者时可以获得锁
        have_writer = true;//记录当前有写者
    }

    void unlock_write() {//释放写锁
        unique_lock lk(mut);
        have_writer = false;//记录当前无写者
        cv.notify_all();//唤醒等待锁的请求
    }

private:
    int cnt_reader = 0;//读者数目
    bool have_writer = false;//是否有写者
    mutex mut;//互斥量
    condition_variable cv;//条件变量
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

---

测试

为了方便测试读写锁的功能，下面简单封装一个基于时序的集合（元素在print中的输出顺序与insert插入顺序一致）：

class thread_safe_set {//线程安全的基于时序的集合
public:
    void insert(const string &ch) {//插入一个字符串ch
        lock_guard lk(mut);//上锁，保证对集合操作是线程安全的
        ind[ch] = ++id_li;//ind[ch]：ch的序号
        li[id_li] = ch;li
    }

    void erase(const string &ch) {//从集合中删除字符串ch
        lock_guard lk(mut);//上锁，保证对集合操作是线程安全的
        li.erase(ind[ch]);
    }

    void print() {//按插入顺序打印集合中的元素,同时检查读写者是否满足读写锁的工作模式
        lock_guard lk(mut);
        cout << ++id_line << ": ";//当前是输出的第id_line行
        int cnt_r = 0, cnt_w = 0;
        for (auto &[id, s]: li) {//id是插入字符串s时的时间戳
            cout << id << "(" << s << ") ";
            if (s[0] == 'r')
                cnt_r++;//读者数+1
            else
                cnt_w++;//写者数+1
        }
        assert(cnt_w == 0 || cnt_r == 0 && cnt_w == 1);//检查是否满足：要么没有写者，要么没有读者且只有一个写者
        cout << "\n" << flush;
    }

private:
    map<int, string> li;//按时间戳排序的集合 (时间戳,字符串) 
    unordered_map<string, int> ind;//无序集合 (字符串,时间戳)
    int id_li = 0, id_line = 0;
    mutex mut;//互斥量
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

接下来通过多线程模拟读写操作的流程：一些线程先上读锁，再往集合中添加首字母为 $r$ 的字符串以模拟读操作，一些线程先上写锁，再往集合中添加首字母为 $w$ 的字符串以模拟写操作。各线程插入字符串后调用集合的 $print$ 方法打印当前集合中的元素，判断是否满足读写锁的工作模式。

int rand_range(int l, int r) {//获得[l,r]内的随机数
    return rand() % (r - l + 1) + l;
}

int main() {
    srand(time(0));
    naive_rw_lock lock;//读写锁

    thread_safe_set safeSet;
    int read_tl = 10, read_tr = 50;
    int write_tl = 10, write_tr = 50;
    int n = 50;
    int cnt_reader = 4, cnt_writer = 2;//执行读操作、写操作的线程数
    vector<thread> reader(cnt_reader), writer(cnt_writer);
    for (int i = 0; i < cnt_reader; i++)
        reader[i] = thread([&, i] {//执行读操作的线程
            for (int j = 0; j < n; j++) {
                lock.lock_read();//获取读锁
                safeSet.insert("r" + to_string(i) + "_" + to_string(j));//插入字符串'r{线程id}_{字符串id}'        
                safeSet.print();//按插入顺序打印集合中的元素,同时检查读写者是否满足读写锁的工作模式
                this_thread::sleep_for(chrono::milliseconds(rand_range(read_tl, read_tr)));//当前线程随机暂停一段时间
                safeSet.erase("r" + to_string(i) + "_" + to_string(j));//删除字符串'r{线程id}_{字符串id}'
                lock.unlock_read();//释放读锁
            }
        });
    for (int i = 0; i < cnt_writer; i++)
        writer[i] = thread([&, i] {//执行写操作的线程
            for (int j = 0; j < n; j++) {
                lock.lock_write();//获取写锁
                safeSet.insert("w" + to_string(i) + "_" + to_string(j));//插入字符串'w{线程id}_{字符串id}' 
                safeSet.print();//按插入顺序打印集合中的元素,同时检查读写者是否满足读写锁的工作模式
                this_thread::sleep_for(chrono::milliseconds(rand_range(write_tl, write_tr)));//当前线程随机暂停一段时间
                safeSet.erase("w" + to_string(i) + "_" + to_string(j));//删除字符串'r{线程id}_{字符串id}'
                lock.unlock_write();//释放写锁
            }
        });
    for (int i = 0; i < cnt_reader; i++)//主线程等待所有执行读操作的线程结束
        if (reader[i].joinable())
            reader[i].join();
    for (int i = 0; i < cnt_writer; i++)//主线程等待所有执行写操作的线程结束
        if (writer[i].joinable())
            writer[i].join();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

由输出结果可知读写锁运行正常，任意时刻要么没有写者，要么没有读者且只有一个写者。但同时从输出中容易发现一个问题：如果有源源不断的读请求到来，写请求很可能出现长等待的问题，就比如运行结果很容易出现的情况：大量写请求需要等到所有读请求完成后才能进行。

//一个可能的运行结果
1: 1(r1_0) 
2: 1(r1_0) 2(r2_0) 
3: 1(r1_0) 2(r2_0) 3(r3_0) 
4: 1(r1_0) 2(r2_0) 3(r3_0) 4(r0_0) 
5: 1(r1_0) 3(r3_0) 5(r0_1) 
6: 1(r1_0) 3(r3_0) 5(r0_1) 6(r2_1) 
7: 1(r1_0) 5(r0_1) 6(r2_1) 7(r3_1) 
8: 5(r0_1) 6(r2_1) 7(r3_1) 8(r1_1) 
9: 7(r3_1) 8(r1_1) 9(r0_2) 
10: 7(r3_1) 8(r1_1) 9(r0_2) 10(r2_2) 
11: 7(r3_1) 9(r0_2) 10(r2_2) 11(r1_2) 
12: 9(r0_2) 10(r2_2) 11(r1_2) 12(r3_2) 
13: 9(r0_2) 11(r1_2) 13(r2_3) 
14: 11(r1_2) 13(r2_3) 14(r0_3) 
15: 11(r1_2) 13(r2_3) 14(r0_3) 15(r3_3) 
16: 13(r2_3) 14(r0_3) 15(r3_3) 16(r1_3) 
17: 13(r2_3) 15(r3_3) 16(r1_3) 17(r0_4) 
18: 13(r2_3) 16(r1_3) 17(r0_4) 18(r3_4) 
19: 16(r1_3) 17(r0_4) 18(r3_4) 19(r2_4) 
20: 17(r0_4) 18(r3_4) 19(r2_4) 20(r1_4) 
21: 17(r0_4) 18(r3_4) 20(r1_4) 21(r2_5) 
22: 17(r0_4) 18(r3_4) 21(r2_5) 22(r1_5) 
23: 21(r2_5) 22(r1_5) 23(r0_5) 
24: 21(r2_5) 22(r1_5) 23(r0_5) 24(r3_5) 
25: 21(r2_5) 24(r3_5) 25(r0_6) 
26: 24(r3_5) 25(r0_6) 26(r2_6) 
27: 25(r0_6) 26(r2_6) 27(r3_6) 
28: 25(r0_6) 26(r2_6) 27(r3_6) 28(r1_6) 
29: 26(r2_6) 27(r3_6) 28(r1_6) 29(r0_7) 
30: 27(r3_6) 29(r0_7) 30(r2_7) 31(r1_7) 
31: 27(r3_6) 29(r0_7) 30(r2_7) 31(r1_7) 
32: 29(r0_7) 30(r2_7) 31(r1_7) 32(r3_7) 
33: 31(r1_7) 32(r3_7) 33(r0_8) 
34: 31(r1_7) 32(r3_7) 33(r0_8) 34(r2_8) 
35: 31(r1_7) 33(r0_8) 34(r2_8) 35(r3_8) 
36: 33(r0_8) 34(r2_8) 35(r3_8) 36(r1_8) 
37: 33(r0_8) 34(r2_8) 35(r3_8) 37(r1_9) 
38: 33(r0_8) 35(r3_8) 37(r1_9) 38(r2_9) 
39: 33(r0_8) 37(r1_9) 38(r2_9) 39(r3_9) 
40: 37(r1_9) 38(r2_9) 39(r3_9) 40(r0_9) 
41: 37(r1_9) 38(r2_9) 41(r0_10) 
42: 37(r1_9) 38(r2_9) 41(r0_10) 42(r3_10) 
43: 37(r1_9) 41(r0_10) 42(r3_10) 43(r2_10) 
44: 41(r0_10) 42(r3_10) 43(r2_10) 44(r1_10) 
45: 42(r3_10) 43(r2_10) 44(r1_10) 45(r0_11) 
46: 42(r3_10) 43(r2_10) 45(r0_11) 46(r1_11) 
47: 42(r3_10) 45(r0_11) 46(r1_11) 47(r2_11) 
48: 45(r0_11) 46(r1_11) 47(r2_11) 48(r3_11) 
49: 47(r2_11) 48(r3_11) 49(r1_12) 
50: 48(r3_11) 49(r1_12) 50(r2_12) 
51: 48(r3_11) 49(r1_12) 50(r2_12) 51(r0_12) 
52: 49(r1_12) 50(r2_12) 51(r0_12) 52(r3_12) 
53: 51(r0_12) 53(r1_13) 
54: 51(r0_12) 53(r1_13) 54(r2_13) 
55: 51(r0_12) 53(r1_13) 54(r2_13) 55(r3_13) 
56: 53(r1_13) 54(r2_13) 55(r3_13) 56(r0_13) 
57: 55(r3_13) 56(r0_13) 57(r1_14) 
58: 56(r0_13) 57(r1_14) 58(r3_14) 
59: 57(r1_14) 58(r3_14) 59(r0_14) 
60: 57(r1_14) 58(r3_14) 59(r0_14) 60(r2_14) 
61: 58(r3_14) 61(r2_15) 62(r0_15) 
62: 58(r3_14) 61(r2_15) 62(r0_15) 
63: 61(r2_15) 62(r0_15) 63(r3_15) 
64: 61(r2_15) 62(r0_15) 63(r3_15) 64(r1_15) 
65: 61(r2_15) 63(r3_15) 64(r1_15) 65(r0_16) 
66: 61(r2_15) 64(r1_15) 65(r0_16) 66(r3_16) 
67: 61(r2_15) 65(r0_16) 66(r3_16) 67(r1_16) 
68: 65(r0_16) 66(r3_16) 67(r1_16) 68(r2_16) 
69: 66(r3_16) 67(r1_16) 68(r2_16) 69(r0_17) 
70: 66(r3_16) 67(r1_16) 69(r0_17) 70(r2_17) 
71: 67(r1_16) 69(r0_17) 70(r2_17) 71(r3_17) 
72: 69(r0_17) 70(r2_17) 71(r3_17) 72(r1_17) 
73: 70(r2_17) 73(r3_18) 
74: 73(r3_18) 74(r2_18) 
75: 73(r3_18) 74(r2_18) 75(r0_18) 
76: 73(r3_18) 74(r2_18) 75(r0_18) 76(r1_18) 
77: 73(r3_18) 74(r2_18) 76(r1_18) 77(r0_19) 
78: 76(r1_18) 77(r0_19) 78(r3_19) 
79: 77(r0_19) 78(r3_19) 79(r1_19) 
80: 77(r0_19) 78(r3_19) 79(r1_19) 80(r2_19) 
81: 78(r3_19) 79(r1_19) 80(r2_19) 81(r0_20) 
82: 78(r3_19) 79(r1_19) 81(r0_20) 82(r2_20) 
83: 78(r3_19) 81(r0_20) 82(r2_20) 83(r1_20) 
84: 81(r0_20) 82(r2_20) 83(r1_20) 84(r3_20) 
85: 85(r1_21) 
86: 85(r1_21) 86(r2_21) 
87: 85(r1_21) 86(r2_21) 87(r3_21) 
88: 85(r1_21) 86(r2_21) 87(r3_21) 88(r0_21) 
89: 87(r3_21) 88(r0_21) 89(r2_22) 
90: 87(r3_21) 89(r2_22) 90(r0_22) 
91: 89(r2_22) 90(r0_22) 91(r3_22) 
92: 89(r2_22) 90(r0_22) 91(r3_22) 92(r1_22) 
93: 89(r2_22) 93(r1_23) 
94: 89(r2_22) 93(r1_23) 94(r0_23) 
95: 93(r1_23) 94(r0_23) 95(r2_23) 96(r3_23) 
96: 93(r1_23) 94(r0_23) 95(r2_23) 96(r3_23) 
97: 93(r1_23) 95(r2_23) 96(r3_23) 97(r0_24) 
98: 93(r1_23) 95(r2_23) 97(r0_24) 98(r3_24) 
99: 95(r2_23) 97(r0_24) 98(r3_24) 99(r1_24) 
100: 97(r0_24) 98(r3_24) 99(r1_24) 100(r2_24) 
101: 98(r3_24) 99(r1_24) 101(r2_25) 
102: 98(r3_24) 99(r1_24) 101(r2_25) 102(r0_25) 
103: 99(r1_24) 101(r2_25) 102(r0_25) 103(r3_25) 
104: 101(r2_25) 102(r0_25) 103(r3_25) 104(r1_25) 
105: 101(r2_25) 104(r1_25) 105(r3_26) 
106: 101(r2_25) 105(r3_26) 106(r1_26) 
107: 101(r2_25) 105(r3_26) 106(r1_26) 107(r0_26) 
108: 105(r3_26) 106(r1_26) 107(r0_26) 108(r2_26) 
109: 105(r3_26) 106(r1_26) 108(r2_26) 109(r0_27) 
110: 105(r3_26) 109(r0_27) 110(r1_27) 
111: 105(r3_26) 109(r0_27) 110(r1_27) 111(r2_27) 
112: 109(r0_27) 110(r1_27) 111(r2_27) 112(r3_27) 
113: 109(r0_27) 110(r1_27) 112(r3_27) 113(r2_28) 
114: 109(r0_27) 112(r3_27) 113(r2_28) 114(r1_28) 
115: 112(r3_27) 113(r2_28) 114(r1_28) 115(r0_28) 
116: 113(r2_28) 114(r1_28) 115(r0_28) 116(r3_28) 
117: 113(r2_28) 114(r1_28) 116(r3_28) 117(r0_29) 
118: 114(r1_28) 116(r3_28) 117(r0_29) 118(r2_29) 
119: 116(r3_28) 117(r0_29) 118(r2_29) 119(r1_29) 
120: 117(r0_29) 118(r2_29) 119(r1_29) 120(r3_29) 
121: 118(r2_29) 119(r1_29) 120(r3_29) 121(r0_30) 
122: 119(r1_29) 120(r3_29) 121(r0_30) 122(r2_30) 
123: 120(r3_29) 121(r0_30) 122(r2_30) 123(r1_30) 
124: 121(r0_30) 122(r2_30) 123(r1_30) 124(r3_30) 
125: 125(r0_31) 
126: 125(r0_31) 126(r3_31) 
127: 125(r0_31) 126(r3_31) 127(r1_31) 
128: 125(r0_31) 126(r3_31) 127(r1_31) 128(r2_31) 
129: 126(r3_31) 127(r1_31) 128(r2_31) 129(r0_32) 
130: 126(r3_31) 128(r2_31) 129(r0_32) 130(r1_32) 
131: 126(r3_31) 129(r0_32) 130(r1_32) 131(r2_32) 
132: 129(r0_32) 130(r1_32) 131(r2_32) 132(r3_32) 
133: 130(r1_32) 132(r3_32) 133(r0_33) 
134: 130(r1_32) 133(r0_33) 134(r3_33) 
135: 133(r0_33) 134(r3_33) 135(r1_33) 
136: 133(r0_33) 134(r3_33) 135(r1_33) 136(r2_33) 
137: 135(r1_33) 136(r2_33) 137(r0_34) 
138: 135(r1_33) 136(r2_33) 137(r0_34) 138(r3_34) 
139: 135(r1_33) 137(r0_34) 138(r3_34) 139(r2_34) 
140: 137(r0_34) 138(r3_34) 139(r2_34) 140(r1_34) 
141: 137(r0_34) 138(r3_34) 139(r2_34) 141(r1_35) 
142: 137(r0_34) 139(r2_34) 141(r1_35) 142(r3_35) 
143: 139(r2_34) 141(r1_35) 142(r3_35) 143(r0_35) 
144: 141(r1_35) 142(r3_35) 143(r0_35) 144(r2_35) 
145: 141(r1_35) 142(r3_35) 144(r2_35) 145(r0_36) 
146: 141(r1_35) 144(r2_35) 145(r0_36) 146(r3_36) 
147: 144(r2_35) 145(r0_36) 146(r3_36) 147(r1_36) 
148: 145(r0_36) 146(r3_36) 147(r1_36) 148(r2_36) 
149: 149(r0_37) 150(r1_37) 151(r2_37) 
150: 149(r0_37) 150(r1_37) 151(r2_37) 152(r3_37) 
151: 149(r0_37) 150(r1_37) 151(r2_37) 152(r3_37) 
152: 149(r0_37) 150(r1_37) 151(r2_37) 152(r3_37) 
153: 150(r1_37) 152(r3_37) 153(r0_38) 
154: 152(r3_37) 153(r0_38) 154(r1_38) 
155: 153(r0_38) 154(r1_38) 155(r3_38) 
156: 153(r0_38) 154(r1_38) 155(r3_38) 156(r2_38) 
157: 155(r3_38) 157(r2_39) 
158: 155(r3_38) 157(r2_39) 158(r0_39) 
159: 157(r2_39) 158(r0_39) 159(r3_39) 
160: 157(r2_39) 158(r0_39) 159(r3_39) 160(r1_39) 
161: 157(r2_39) 158(r0_39) 161(r3_40) 162(r1_40) 
162: 157(r2_39) 161(r3_40) 162(r1_40) 163(r0_40) 
163: 157(r2_39) 161(r3_40) 162(r1_40) 163(r0_40) 
164: 161(r3_40) 162(r1_40) 163(r0_40) 164(r2_40) 
165: 161(r3_40) 165(r2_41) 
166: 161(r3_40) 165(r2_41) 166(r0_41) 
167: 165(r2_41) 166(r0_41) 167(r3_41) 
168: 165(r2_41) 166(r0_41) 167(r3_41) 168(r1_41) 
169: 169(r2_42) 
170: 169(r2_42) 170(r0_42) 
171: 169(r2_42) 170(r0_42) 171(r1_42) 
172: 169(r2_42) 170(r0_42) 171(r1_42) 172(r3_42) 
173: 172(r3_42) 173(r0_43) 174(r2_43) 
174: 172(r3_42) 173(r0_43) 174(r2_43) 175(r1_43) 
175: 172(r3_42) 173(r0_43) 174(r2_43) 175(r1_43) 
176: 173(r0_43) 174(r2_43) 175(r1_43) 176(r3_43) 
177: 173(r0_43) 174(r2_43) 175(r1_43) 177(r3_44) 
178: 173(r0_43) 174(r2_43) 177(r3_44) 178(r1_44) 
179: 177(r3_44) 178(r1_44) 179(r2_44) 180(r0_44) 
180: 177(r3_44) 178(r1_44) 179(r2_44) 180(r0_44) 
181: 177(r3_44) 178(r1_44) 179(r2_44) 181(r0_45) 
182: 178(r1_44) 179(r2_44) 181(r0_45) 182(r3_45) 
183: 179(r2_44) 181(r0_45) 182(r3_45) 183(r1_45) 
184: 181(r0_45) 182(r3_45) 183(r1_45) 184(r2_45) 
185: 181(r0_45) 183(r1_45) 184(r2_45) 185(r3_46) 
186: 183(r1_45) 184(r2_45) 185(r3_46) 186(r0_46) 
187: 184(r2_45) 185(r3_46) 186(r0_46) 187(r1_46) 
188: 185(r3_46) 186(r0_46) 187(r1_46) 188(r2_46) 
189: 185(r3_46) 186(r0_46) 187(r1_46) 189(r2_47) 
190: 185(r3_46) 186(r0_46) 189(r2_47) 190(r1_47) 
191: 186(r0_46) 189(r2_47) 190(r1_47) 191(r3_47) 
192: 189(r2_47) 190(r1_47) 191(r3_47) 192(r0_47) 
193: 189(r2_47) 190(r1_47) 192(r0_47) 193(r3_48) 
194: 190(r1_47) 192(r0_47) 193(r3_48) 194(r2_48) 
195: 192(r0_47) 193(r3_48) 194(r2_48) 195(r1_48) 
196: 193(r3_48) 194(r2_48) 195(r1_48) 196(r0_48) 
197: 194(r2_48) 196(r0_48) 197(r1_49) 
198: 194(r2_48) 197(r1_49) 198(r0_49) 
199: 197(r1_49) 198(r0_49) 199(r2_49) 
200: 197(r1_49) 198(r0_49) 199(r2_49) 200(r3_49) 
201: 201(w1_0) 
202: 202(w1_1) 
203: 203(w1_2) 
204: 204(w1_3) 
205: 205(w1_4) 
206: 206(w1_5) 
207: 207(w1_6) 
208: 208(w1_7) 
209: 209(w1_8) 
210: 210(w1_9) 
211: 211(w1_10) 
212: 212(w1_11) 
213: 213(w1_12) 
214: 214(w1_13) 
215: 215(w1_14) 
216: 216(w1_15) 
217: 217(w1_16) 
218: 218(w1_17) 
219: 219(w1_18) 
220: 220(w1_19) 
221: 221(w1_20) 
222: 222(w1_21) 
223: 223(w1_22) 
224: 224(w1_23) 
225: 225(w1_24) 
226: 226(w1_25) 
227: 227(w1_26) 
228: 228(w1_27) 
229: 229(w1_28) 
230: 230(w0_0) 
231: 231(w0_1) 
232: 232(w1_29) 
233: 233(w1_30) 
234: 234(w1_31) 
235: 235(w1_32) 
236: 236(w1_33) 
237: 237(w1_34) 
238: 238(w1_35) 
239: 239(w1_36) 
240: 240(w1_37) 
241: 241(w1_38) 
242: 242(w1_39) 
243: 243(w1_40) 
244: 244(w1_41) 
245: 245(w1_42) 
246: 246(w1_43) 
247: 247(w1_44) 
248: 248(w1_45) 
249: 249(w1_46) 
250: 250(w1_47) 
251: 251(w1_48) 
252: 252(w1_49) 
253: 253(w0_2) 
254: 254(w0_3) 
255: 255(w0_4) 
256: 256(w0_5) 
257: 257(w0_6) 
258: 258(w0_7) 
259: 259(w0_8) 
260: 260(w0_9) 
261: 261(w0_10) 
262: 262(w0_11) 
263: 263(w0_12) 
264: 264(w0_13) 
265: 265(w0_14) 
266: 266(w0_15) 
267: 267(w0_16) 
268: 268(w0_17) 
269: 269(w0_18) 
270: 270(w0_19) 
271: 271(w0_20) 
272: 272(w0_21) 
273: 273(w0_22) 
274: 274(w0_23) 
275: 275(w0_24) 
276: 276(w0_25) 
277: 277(w0_26) 
278: 278(w0_27) 
279: 279(w0_28) 
280: 280(w0_29) 
281: 281(w0_30) 
282: 282(w0_31) 
283: 283(w0_32) 
284: 284(w0_33) 
285: 285(w0_34) 
286: 286(w0_35) 
287: 287(w0_36) 
288: 288(w0_37) 
289: 289(w0_38) 
290: 290(w0_39) 
291: 291(w0_40) 
292: 292(w0_41) 
293: 293(w0_42) 
294: 294(w0_43) 
295: 295(w0_44) 
296: 296(w0_45) 
297: 297(w0_46) 
298: 298(w0_47) 
299: 299(w0_48) 
300: 300(w0_49) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301

---

基于时序公平的读写锁实现

由于上面实现的读写锁存在测试中提到的写请求容易被后来的读请求所阻塞造成写请求长等待的问题，可以考虑设计一种基于时序公平的读写锁：锁对读写请求按到来顺序依次进行处理，这样先到的写请求就不会被后到的读请求所阻塞，也就解决了上述问题。实现时在之前的共享锁的基础上添加队列来维护请求的到来顺序：

class rw_lock {
public:
    void lock_read() {
        unique_lock lk(mut);
        auto cur_id = std::this_thread::get_id();//当前线程id
        q_tid.push(cur_id);//将当前线程id加入队列
        cv.wait(lk, [&] { return q_tid.front() == cur_id && !have_writer; });//队头id等于当前线程id,且没有写者时可以获得锁
        cnt_reader++;
        q_tid.pop();//队首出队
    }

    void unlock_read() {
        unique_lock lk(mut);
        if (--cnt_reader == 0) {
            cv.notify_all();
        }
    }

    void lock_write() {
        unique_lock lk(mut);
        auto cur_id = std::this_thread::get_id();
        q_tid.push(cur_id);//将当前线程id加入队列
        cv.wait(lk, [&] { return q_tid.front() == cur_id && !have_writer && cnt_reader == 0; });//队头id等于当前线程id,且没有写者也没有读者时可以获得锁
        have_writer = true;
        q_tid.pop();//队首出队
    }

    void unlock_write() {
        unique_lock lk(mut);
        have_writer = false;
        cv.notify_all();
    }

private:
    int cnt_reader = 0;
    bool have_writer = false;
    mutex mut;
    condition_variable cv;
    queue<std::thread::id> q_tid;//存放放出请求的线程id的队列
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

再通过上述代码测试，从运行结果可以看出满足读写锁的工作模式，同时解决了写请求被后来的读请求所阻塞的问题。

//一个可能的运行结果
1: 1(r0_0) 
2: 1(r0_0) 2(r2_0) 
3: 1(r0_0) 2(r2_0) 3(r1_0) 
4: 1(r0_0) 2(r2_0) 3(r1_0) 4(r3_0) 
5: 5(w0_0) 
6: 6(w1_0) 
7: 7(r1_1) 
8: 7(r1_1) 8(r0_1) 
9: 9(r2_1) 
10: 9(r2_1) 10(r3_1) 
11: 11(w0_1) 
12: 12(w1_1) 
13: 13(r0_2) 
14: 13(r0_2) 14(r3_2) 
15: 13(r0_2) 14(r3_2) 15(r2_2) 
16: 13(r0_2) 14(r3_2) 15(r2_2) 16(r1_2) 
17: 17(w0_2) 
18: 18(w1_2) 
19: 19(r2_3) 
20: 20(r0_3) 
21: 21(r1_3) 
22: 22(r3_3) 
23: 23(w0_3) 
24: 24(w1_3) 
25: 25(r2_4) 
26: 26(r0_4) 
27: 27(r1_4) 
28: 27(r1_4) 28(r3_4) 
29: 29(w0_4) 
30: 30(w1_4) 
31: 31(r2_5) 
32: 32(r0_5) 
33: 32(r0_5) 33(r1_5) 
34: 32(r0_5) 33(r1_5) 34(r3_5) 
35: 35(w0_5) 
36: 36(w1_5) 
37: 37(r2_6) 
38: 38(r3_6) 
39: 39(r1_6) 
40: 39(r1_6) 40(r0_6) 
41: 41(w0_6) 
42: 42(w1_6) 
43: 43(r2_7) 
44: 44(r3_7) 
45: 45(r1_7) 
46: 45(r1_7) 46(r0_7) 
47: 47(w0_7) 
48: 48(w1_7) 
49: 49(r2_8) 
50: 50(r3_8) 
51: 51(r1_8) 
52: 52(r0_8) 
53: 53(w0_8) 
54: 54(w1_8) 
55: 55(r2_9) 
56: 56(r3_9) 
57: 57(r1_9) 
58: 57(r1_9) 58(r0_9) 
59: 59(w0_9) 
60: 60(w1_9) 
61: 61(r2_10) 
62: 62(r3_10) 
63: 63(r1_10) 
64: 64(r0_10) 
65: 65(w0_10) 
66: 66(w1_10) 
67: 67(r2_11) 
68: 68(r3_11) 
69: 68(r3_11) 69(r1_11) 
70: 70(r0_11) 
71: 71(w0_11) 
72: 72(w1_11) 
73: 73(r2_12) 
74: 74(r1_12) 
75: 75(r3_12) 
76: 75(r3_12) 76(r0_12) 
77: 77(w0_12) 
78: 78(w1_12) 
79: 79(r2_13) 
80: 79(r2_13) 80(r1_13) 
81: 79(r2_13) 80(r1_13) 81(r3_13) 
82: 82(r0_13) 
83: 83(w0_13) 
84: 84(w1_13) 
85: 85(r2_14) 
86: 85(r2_14) 86(r3_14) 
87: 87(r1_14) 
88: 87(r1_14) 88(r0_14) 
89: 89(w0_14) 
90: 90(w1_14) 
91: 91(r2_15) 
92: 91(r2_15) 92(r3_15) 
93: 93(r1_15) 
94: 94(r0_15) 
95: 95(w0_15) 
96: 96(w1_15) 
97: 97(r2_16) 
98: 98(r3_16) 
99: 99(r1_16) 
100: 100(r0_16) 
101: 101(w0_16) 
102: 102(w1_16) 
103: 103(r2_17) 
104: 104(r3_17) 
105: 105(r1_17) 
106: 105(r1_17) 106(r0_17) 
107: 107(w0_17) 
108: 108(w1_17) 
109: 109(r2_18) 
110: 110(r3_18) 
111: 110(r3_18) 111(r1_18) 
112: 112(r0_18) 
113: 113(w0_18) 
114: 114(w1_18) 
115: 115(r2_19) 
116: 115(r2_19) 116(r3_19) 
117: 115(r2_19) 116(r3_19) 117(r1_19) 
118: 118(r0_19) 
119: 119(w0_19) 
120: 120(w1_19) 
121: 121(r2_20) 
122: 122(r1_20) 
123: 123(r3_20) 
124: 123(r3_20) 124(r0_20) 
125: 125(w0_20) 
126: 126(w1_20) 
127: 127(r2_21) 
128: 127(r2_21) 128(r1_21) 
129: 127(r2_21) 128(r1_21) 129(r0_21) 
130: 130(r3_21) 
131: 131(w0_21) 
132: 132(w1_21) 
133: 133(r0_22) 
134: 133(r0_22) 134(r1_22) 
135: 135(r2_22) 136(r3_22) 
136: 135(r2_22) 136(r3_22) 
137: 137(w0_22) 
138: 138(w1_22) 
139: 139(r1_23) 
140: 139(r1_23) 140(r0_23) 
141: 139(r1_23) 140(r0_23) 141(r3_23) 
142: 142(r2_23) 
143: 143(w0_23) 
144: 144(w1_23) 
145: 145(r0_24) 
146: 145(r0_24) 146(r1_24) 
147: 145(r0_24) 146(r1_24) 147(r3_24) 
148: 148(r2_24) 
149: 149(w0_24) 
150: 150(w1_24) 
151: 151(r1_25) 
152: 151(r1_25) 152(r0_25) 
153: 153(r3_25) 
154: 153(r3_25) 154(r2_25) 
155: 155(w0_25) 
156: 156(w1_25) 
157: 157(r0_26) 
158: 158(r1_26) 
159: 159(r3_26) 
160: 160(r2_26) 
161: 161(w0_26) 
162: 162(w1_26) 
163: 163(r0_27) 
164: 164(r1_27) 165(r2_27) 
165: 164(r1_27) 165(r2_27) 166(r3_27) 
166: 164(r1_27) 165(r2_27) 166(r3_27) 
167: 167(w0_27) 
168: 168(w1_27) 
169: 169(r0_28) 
170: 169(r0_28) 170(r3_28) 
171: 171(r2_28) 
172: 172(r1_28) 
173: 173(w0_28) 
174: 174(w1_28) 
175: 175(r3_29) 
176: 176(r0_29) 
177: 176(r0_29) 177(r1_29) 
178: 176(r0_29) 177(r1_29) 178(r2_29) 
179: 179(w0_29) 
180: 180(w1_29) 
181: 181(r3_30) 
182: 181(r3_30) 182(r1_30) 
183: 183(r2_30) 
184: 183(r2_30) 184(r0_30) 
185: 185(w0_30) 
186: 186(w1_30) 
187: 187(r3_31) 
188: 187(r3_31) 188(r1_31) 
189: 189(r2_31) 
190: 190(r0_31) 
191: 191(w0_31) 
192: 192(w1_31) 
193: 193(r3_32) 
194: 193(r3_32) 194(r1_32) 
195: 193(r3_32) 194(r1_32) 195(r2_32) 
196: 196(r0_32) 
197: 197(w0_32) 
198: 198(w1_32) 
199: 199(r3_33) 
200: 200(r1_33) 
201: 201(r2_33) 
202: 202(r0_33) 
203: 203(w0_33) 
204: 204(w1_33) 
205: 205(r3_34) 
206: 205(r3_34) 206(r1_34) 207(r2_34) 
207: 205(r3_34) 206(r1_34) 207(r2_34) 
208: 208(r0_34) 
209: 209(w0_34) 
210: 210(w1_34) 
211: 211(r1_35) 
212: 211(r1_35) 212(r2_35) 
213: 213(r3_35) 
214: 214(r0_35) 
215: 215(w0_35) 
216: 216(w1_35) 
217: 217(r1_36) 
218: 218(r2_36) 
219: 219(r3_36) 
220: 219(r3_36) 220(r0_36) 
221: 221(w0_36) 
222: 222(w1_36) 
223: 223(r1_37) 
224: 224(r2_37) 
225: 224(r2_37) 225(r3_37) 
226: 226(r0_37) 
227: 227(w0_37) 
228: 228(w1_37) 
229: 229(r1_38) 
230: 229(r1_38) 230(r2_38) 
231: 231(r3_38) 
232: 231(r3_38) 232(r0_38) 
233: 233(w0_38) 
234: 234(w1_38) 
235: 235(r1_39) 
236: 236(r2_39) 
237: 237(r3_39) 
238: 237(r3_39) 238(r0_39) 
239: 239(w0_39) 
240: 240(w1_39) 
241: 241(r1_40) 
242: 242(r2_40) 
243: 243(r0_40) 
244: 244(r3_40) 
245: 245(w0_40) 
246: 246(w1_40) 
247: 247(r1_41) 
248: 248(r2_41) 
249: 249(r0_41) 
250: 249(r0_41) 250(r3_41) 
251: 251(w0_41) 
252: 252(w1_41) 
253: 253(r1_42) 
254: 253(r1_42) 254(r2_42) 
255: 255(r0_42) 
256: 255(r0_42) 256(r3_42) 
257: 257(w0_42) 
258: 258(w1_42) 
259: 259(r1_43) 
260: 259(r1_43) 260(r2_43) 
261: 261(r0_43) 
262: 262(r3_43) 
263: 263(w0_43) 
264: 264(w1_43) 
265: 265(r2_44) 
266: 266(r1_44) 
267: 266(r1_44) 267(r0_44) 
268: 268(r3_44) 
269: 269(w0_44) 
270: 270(w1_44) 
271: 271(r2_45) 
272: 271(r2_45) 272(r1_45) 
273: 271(r2_45) 272(r1_45) 273(r0_45) 
274: 274(r3_45) 
275: 275(w0_45) 
276: 276(w1_45) 
277: 277(r1_46) 
278: 278(r2_46) 
279: 278(r2_46) 279(r0_46) 
280: 280(r3_46) 
281: 281(w0_46) 
282: 282(w1_46) 
283: 283(r1_47) 
284: 284(r2_47) 
285: 284(r2_47) 285(r0_47) 
286: 286(r3_47) 
287: 287(w0_47) 
288: 288(w1_47) 
289: 289(r1_48) 
290: 289(r1_48) 290(r0_48) 
291: 291(r2_48) 
292: 291(r2_48) 292(r3_48) 
293: 293(w0_48) 
294: 294(w1_48) 
295: 295(r1_49) 
296: 295(r1_49) 296(r3_49) 
297: 295(r1_49) 296(r3_49) 297(r0_49) 
298: 298(r2_49) 
299: 299(w0_49) 
300: 300(w1_49)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301