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
|
// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:nil -*-
#include <array>
#include <mutex>
#include <numeric>
#include <future>
#include <gtest/gtest.h>
#include "common/fair_mutex.h"
TEST(FairMutex, simple)
{
ceph::fair_mutex mutex{"fair::simple"};
{
std::unique_lock lock{mutex};
ASSERT_TRUE(mutex.is_locked());
// fair_mutex does not recursive ownership semantics
ASSERT_FALSE(mutex.try_lock());
}
// re-acquire the lock
{
std::unique_lock lock{mutex};
ASSERT_TRUE(mutex.is_locked());
}
ASSERT_FALSE(mutex.is_locked());
}
TEST(FairMutex, fair)
{
// waiters are queued in FIFO order, and they are woken up in the same order
// we have a marathon participated by multiple teams:
// - each team is represented by a thread.
// - each team should have equal chance of being selected and scoring, assuming
// the runners in each team are distributed evenly in the waiting queue.
ceph::fair_mutex mutex{"fair::fair"};
const int NR_TEAMS = 2;
std::array<unsigned, NR_TEAMS> scoreboard{0, 0};
const int NR_ROUNDS = 512;
auto play = [&](int team) {
for (int i = 0; i < NR_ROUNDS; i++) {
std::unique_lock lock{mutex};
// pretent that i am running.. and it takes time
std::this_thread::sleep_for(std::chrono::microseconds(20));
// score!
scoreboard[team]++;
// fair?
unsigned total = std::accumulate(scoreboard.begin(),
scoreboard.end(),
0);
for (unsigned score : scoreboard) {
if (total < NR_ROUNDS) {
// not quite statistically significant. to reduce the false positive,
// just consider it fair
continue;
}
// check if any team is donimating the game.
unsigned avg = total / scoreboard.size();
// leave at least half of the average to other teams
ASSERT_LE(score, total - avg / 2);
// don't treat myself too bad
ASSERT_GT(score, avg / 2);
};
}
};
std::array<std::future<void>, NR_TEAMS> completed;
for (int team = 0; team < NR_TEAMS; team++) {
completed[team] = std::async(std::launch::async, play, team);
}
}
|
