2026-09-01
reserve.cpp
#include <atomic>
int reserve(std::atomic<int>& used, int n, int cap) {
}
used は、大きさ cap の領域のうち、先頭から使用済みになっている大きさです。used + n が cap 以下なら used を n 増やして、確保した部分の先頭の位置(増やす前の used)を返し、cap を超えるなら used を変えずに -1 を返す reserve を書いてください。複数のスレッドから同時に呼ばれても、確保した部分どうしが重なったり、used が cap を超えたりしてはいけません。n は1以上とします。
入力例 1
std::atomic<int> used{7}; reserve(used, 2, 10)
出力例 1
7
入力例 2
std::atomic<int> used{7}; reserve(used, 4, 10)
出力例 2
-1
入力例 3
std::atomic<int> used{6}; reserve(used, 4, 10)
出力例 3
6
Reference
int reserve(std::atomic<int>& used, int n, int cap) {
int old = used.load();
do {
if (old + n > cap) {
return -1;
}
} while (!used.compare_exchange_weak(old, old + n));
return old;
}
used.compare_exchange_weak(old, old + n) は、「used がまだ old なら old + n に書き換える」を、ほかのスレッドが割り込めない1つの操作として行います。読んでから書くまでの間に別のスレッドが used を変えていれば書き換えは失敗し、そのとき old には今の used が書き戻されます。ループの先頭で、その新しい old を使って容量の判定からやり直せるので、load を呼び直す必要はありません。weak の版は値が一致していても失敗することがありますが、ループで再試行するので結果は変わりません。
if (used + n > cap) return -1; と判定してから return used.fetch_add(n); で足す書き方は、1つずつの操作は不可分でも、判定と加算の間に別のスレッドが割り込めます。used が7、cap が10のとき、2つのスレッドがどちらも「7 + 2 は10以下」と確かめてから2ずつ足すと、used は11になり、2つ目の確保は容量からはみ出します。判定に使った値が書き換えの時点でも変わっていないことを確かめるのが、compare_exchange の役目です。
掲載したのは参考実装で、唯一の正解ではありません。std::mutex で判定と加算をまとめて囲んでも正しく動きます。