semaphore

---

1. Resource Limiter

class Semaphore {
  int count;

public:
  Semaphore(int initial_count) : count(initial_count) {}

  void acquire() {
    std::unique_lock<std::mutex> lock(mutex);
    while (count == 0) {
      cv.wait(lock);
    }
    --count;
  }

  void release() {
    std::unique_lock<std::mutex> lock(mutex);
    ++count;
    cv.notify_one();
  }

private:
  std::mutex mutex;
  std::condition_variable cv;
};

class ResourcePool {
public:
  ResourcePool(int max_resources) : semaphore(max_resources) {}

  Resource acquire_resource() {
    semaphore.acquire();
    return Resource();
  }

  void release_resource(Resource resource) {
    semaphore.release();
  }

private:
  Semaphore semaphore;
};

2. Mutual Exclusion

class Semaphore {
  std::atomic<int> count;
  std::mutex mutex;

public:
  Semaphore(int initial_count = 1) : count(initial_count) {}

  bool try_acquire() {
    if (count.fetch_sub(1) > 0) {
      return true;
    } else {
      count.fetch_add(1);
      return false;
    }
  }

  void acquire() {
    while (!try_acquire()) {
      std::this_thread::yield();
    }
  }

  void release() {
    count.fetch_add(1);
  }
};

class Mutex {
public:
  Mutex() : semaphore(1) {}

  void lock() {
    semaphore.acquire();
  }

  void unlock() {
    semaphore.release();
  }

private:
  Semaphore semaphore;
};

3. Producer-Consumer Problem

class BoundedBuffer {
public:
  BoundedBuffer(int capacity) : buffer(capacity), semaphore_empty(capacity), semaphore_full(0) {}

  void produce(int item) {
    semaphore_empty.acquire();
    buffer.push(item);
    semaphore_full.release();
  }

  int consume() {
    semaphore_full.acquire();
    int item = buffer.front();
    buffer.pop();
    semaphore_empty.release();
    return item;
  }

private:
  std::queue<int> buffer;
  Semaphore semaphore_empty;
  Semaphore semaphore_full;
};

4. Readers-Writers Problem

class ReadWriteLock {
public:
  ReadWriteLock() : readers(0), writers(0) {}

  void read_lock() {
    std::unique_lock<std::mutex> lock(mutex);
    while (writers > 0) {
      cv.wait(lock);
    }
    ++readers;
  }

  void read_unlock() {
    std::unique_lock<std::mutex> lock(mutex);
    --readers;
    if (readers == 0) {
      cv.notify_one();
    }
  }

  void write_lock() {
    std::unique_lock<std::mutex> lock(mutex);
    while (readers > 0 || writers > 0) {
      cv.wait(lock);
    }
    ++writers;
  }

  void write_unlock() {
    std::unique_lock<std::mutex> lock(mutex);
    --writers;
    cv.notify_all();
  }

private:
  std::mutex mutex;
  std::condition_variable cv;
  int readers;
  int writers;
};

5. Counting Semaphore

class CountingSemaphore {
public:
  CountingSemaphore(int max_count) : max_count(max_count) {}

  void acquire() {
    std::unique_lock<std::mutex> lock(mutex);
    while (count == max_count) {
      cv.wait(lock);
    }
    ++count;
  }

  void release() {
    std::unique_lock<std::mutex> lock(mutex);
    --count;
    cv.notify_one();
  }

  int get_count() {
    std::unique_lock<std::mutex> lock(mutex);
    return count;
  }

private:
  std::mutex mutex;
  std::condition_variable cv;
  int count = 0;
  int max_count;
};

6. Binary Semaphore

class BinarySemaphore {
public:
  BinarySemaphore() : state(false) {}

  void acquire() {
    std::unique_lock<std::mutex> lock(mutex);
    while (state) {
      cv.wait(lock);
    }
    state = true;
  }

  void release() {
    std::unique_lock<std::mutex> lock(mutex);
    state = false;
    cv.notify_one();
  }

private:
  std::mutex mutex;
  std::condition_variable cv;
  bool state;
};

7. Non-Blocking Semaphore

class NonBlockingSemaphore {
public:
  NonBlockingSemaphore(int max_count) : max_count(max_count) {}

  bool acquire() {
    if (count.fetch_sub(1) >= 0) {
      return true;
    } else {
      count.fetch_add(1);
      return false;
    }
  }

  void release() {
    count.fetch_add(1);
  }

private:
  std::atomic<int> count = 0;
  int max_count;
};

8. Timeout Semaphore

class TimeoutSemaphore {
public:
  TimeoutSemaphore(int initial_count, std::chrono::milliseconds timeout)
      : semaphore(initial_count), timeout(timeout) {}

  bool acquire() {
    return semaphore.try_acquire_for(timeout);
  }

  void release() {
    semaphore.release();
  }

private:
  Semaphore semaphore;
  std::chrono::milliseconds timeout;
};

9. Reentrant Semaphore

class ReentrantSemaphore {
public:
  ReentrantSemaphore(int initial_count) : count(initial_count) {}

  void acquire() {
    std::unique_lock<std::mutex> lock(mutex);
    ++acquired_threads;
    if (acquired_threads == 1) {
      while (count == 0) {
        cv.wait(lock);
      }
      --count;
    }
  }

  void release() {
    std::unique_lock<std::mutex> lock(mutex);
    --acquired_threads;
    if (acquired_threads == 0) {
      cv.notify_one();
    }
  }

private:
  std::mutex mutex;
  std::condition_variable cv;
  int count;
  int acquired_threads = 0;
};

10. Spinlock

class Spinlock {
public:
  Spinlock() : locked(false) {}

  void lock() {
    while (locked.exchange(true)) {
      // Busy wait
    }
  }

  void unlock() {
    locked.store(false);
  }

private:
  std::atomic<bool> locked;
};

11. Fair Mutex

class FairMutex {
public:
  FairMutex() : turn(0) {}

  void lock() {
    while (turn != id) {
      // Busy wait
    }
    turn = (turn + 1) % num_threads;
  }

  void unlock() {
    turn = (turn + 1) % num_threads;
  }

private:
  int id = 0;
  int num_threads = std::thread::hardware_concurrency();
  int turn = 0;
};

12. Ticket Lock

class TicketLock {
public:
  TicketLock() : next_ticket(0), serving_ticket(0) {}

  void lock() {
    int my_ticket = next_ticket.fetch_add(1);
    while (serving_ticket != my_ticket) {
      // Busy wait
    }
  }

  void unlock() {
    ++serving_ticket;
  }

private:
  std::atomic<int> next_ticket;
  int serving_ticket;
};

13. CLH Lock

class CLHLock {
public:
  CLHLock() : tail(nullptr) {}

  void lock() {
    Node* my_node = new Node;
    *tail = my_node;
    tail = &my_node->next;
    while (my_node->locked) {
      // Busy wait
    }
  }

  void unlock() {
    Node* my_node = tail;
    if (my_node == &my_node->next) {
      tail = nullptr;
      return;
    }
    my_node->locked = false;
    *tail = my_node->next;
  }

private:
  struct Node {
    std::atomic<bool> locked = true;
    Node* next = nullptr;
  };
  Node* tail;
};

14. MCS Lock

class MCSLock {
public:
  MCSLock() : tail(nullptr) {}

  void lock() {
    Node* my_node = new Node;
    my_node->next = nullptr;
    *tail = my_node;
    tail = &my_node->next;
    Node* prev_node = pred.exchange(my_node);
    if (prev_node != nullptr) {
      while (prev_node->next == nullptr) {
        // Busy wait
      }
    }
  }

  void unlock() {
    Node* my_node = pred.exchange(nullptr);
    if (my_node != nullptr) {
      *my_node = true;
    }
  }

private:
  struct Node {
    std::atomic<bool> locked = true;
    Node* next = nullptr;
  };
  Node* tail;
  std::atomic<Node*> pred;
};

15. TSL Lock

class TSLLock {
public:
  TSLLock() : tail(nullptr) {}

  void lock() {
    Node* my_node = new Node;
    my_node->next = nullptr;
    tail.compare_exchange_strong(nullptr, my_node);
    while (my_node->locked) {
      // Busy wait
    }
  }

  void unlock() {
    Node* my_node = tail.exchange(nullptr);
    if (my_node != nullptr) {
      my_node->locked = false;
    }
  }

private:
  struct Node {
    std::atomic<bool> locked = true;
    Node* next = nullptr;
  };
  std::atomic<Node*> tail;
};

16. Dekker's Algorithm

class DekkerLock {
public:
  DekkerLock() : turn(0), want_turn(2, false) {}

  void lock() {
    int my_id = id.fetch_add(1) % 2;
    want_turn[my_id] = true;
    while (want_turn[1 - my_id]) {
      if (turn == 1 - my_id) {
        want_turn[my_id] = false;
        while (turn == 1 - my_id) {
          // Busy wait
        }
        want_turn[my_id] = true;
      }
    }
  }

  void unlock() {
    int my_id = id.fetch_sub(1) % 2;
    turn = 1 - my_id;
    want_turn[my_id] = false;
  }

private:
  std::atomic<int> id = 0;
  std::atomic<bool> want_turn[2];
  int turn = 0;
};

17. Peterson's Algorithm

class PetersonLock {
public:
  PetersonLock() : flags(2, false), victim(0) {}

  void lock() {
    int my_id = id.fetch_add(1) % 2;
    flags[my_id] = true;
    victim = my_id;
    while (flags[1 - my_id] && victim == my_id) {
      // Busy wait
    }
  }

  void unlock() {
    int my_id = id.fetch_sub(1) % 2;
    flags[my_id] = false;
  }

private:
  std::atomic<int> id = 0;
  std::atomic<bool> flags[2];
  int victim;
};

18. Lamport's Bakery Algorithm

class LamportBakeryLock {
public:
  LamportBakeryLock() : number(std::vector<int>(num_threads, 0)) {}

  void lock() {
    int my_id = id.fetch_add(1) % num_threads;
    int max_number = 0;
    for (int i = 0; i < num_threads; ++i) {
      max_number = std::max(max_number, number[i]);
    }
    number[my_id] = max_number + 1;
    int turn = 0;
    while (true) {
      bool waiting = false;
      for (int i = 0; i < num_threads; ++i) {
        if (i != my_id && number[i] != 0) {
          if (number[i] < number[my_id] || (number[i] == number[my_id] && i < my_id)) {
            waiting = true;
          } else {
            turn = i;
          }
        }
      }
      if (!waiting) {
        break;
      } else {
        while (number[turn] != 0) {
          // Busy wait
        }
      }
    }
  }

  void unlock() {
    int my_id = id.fetch_sub(1) % num_threads;
    number[my_id] = 0;
  }

private:
  std::atomic<int> id = 0;
  std::vector<int> number;
  int num_threads = std::thread::hardware_concurrency();
};

19. Adaptive Mutex

class AdaptiveMutex {
public:
  AdaptiveMutex() : state(unlocked) {}

  void lock() {
    while (true) {
      std::unique_lock<std::mutex> lock(mutex);
      switch (state) {
        case unlocked:
          state = spinning;
          return;
        case spinning:
          if (lock.try_lock()) {
            state = locked;
            return;
          } else {
            state = blocking;
            cv.wait(lock);
          }
          break;
        case blocking:
          cv.wait(lock);
          break;
      }
    }
  }

  void unlock() {
    std::unique_lock<std::mutex> lock(mutex);
    switch (state) {
      case spinning:
        state = unlocked;
        break;
      case