Semaphores

Keys: the bucket model

A semaphore is a built-in class modeling a bucket of keys . new(N) creates it with N keys. get(M) blocks until M keys are available, then atomically removes them; put(M) returns M keys; try_get(M) is non-blocking and returns 1 on success, 0 if insufficient keys. The blocking and atomicity are the whole point: when two processes call get(1) in the same timestep, the scheduler grants exactly one of them — there is no torn state, no test-and-set race to write yourself.

A crucial semantic difference from real locks: a semaphore has no concept of ownership . Any process may put keys, including a process that never called get, and putting more keys than the initial count is legal. The discipline of get-then-put around a critical section is purely a coding convention — the language will not stop a stray put from corrupting your mutual exclusion.

Arbitrating a shared bus between two drivers

The canonical testbench use: two BFMs share one physical bus. Each acquires the single key before driving and releases it after. Requests that arrive while the key is out simply block in get() — FIFO order by default in most simulators.

class bus_driver;
  string    name;
  semaphore bus_sem;              // shared handle — ONE object, many drivers

  function new(string n, semaphore s);
    name = n;  bus_sem = s;
  endfunction

  task drive_one(int unsigned addr);
    bus_sem.get(1);                       // acquire the bus (blocks)
    $display("[%0t] %s: GRANTED, driving addr=%0h", $time, name, addr);
    #20;                                  // bus is busy for 20ns
    $display("[%0t] %s: releasing bus", $time, name);
    bus_sem.put(1);                       // release — ALWAYS pair with get
  endtask
endclass

module top;
  initial begin
    semaphore  sem = new(1);              // 1 key = mutex
    bus_driver a   = new("drvA", sem);
    bus_driver b   = new("drvB", sem);
    fork
      a.drive_one('h10);                  // both request at time 0;
      b.drive_one('h20);                  // one is granted, one blocks 20ns
    join
  end
endmodule

Counting semaphores

With N greater than 1, a semaphore meters a pool rather than a mutex: 4 keys for 4 outstanding-transaction credits, 2 keys for 2 DMA channels. A process can also get(2) to claim multiple units atomically — but mixed multi-key requests are where deadlock begins.

Deadlock: how it happens and how to avoid it

DEADLOCK WITH TWO SEMAPHORES (classic AB-BA)

  sem_bus (1 key)        sem_mem (1 key)

  Process P                          Process Q
  ─────────                          ─────────
  sem_bus.get(1)   ✓ holds bus       sem_mem.get(1)   ✓ holds mem
       │                                  │
  sem_mem.get(1)   ✗ blocks ◄──────┐ sem_bus.get(1)   ✗ blocks
       │                          │      │
       └────────── waits on Q ────┴──── waits on P ──┘

  P holds bus, wants mem.  Q holds mem, wants bus.
  Neither can proceed → simulation hangs silently at the last #delay.

  FIXES
  1. Global lock ordering: everyone gets bus BEFORE mem, always.
  2. try_get with backoff: if second lock unavailable, release first, retry.
  3. One coarse semaphore guarding both resources (less parallelism, no deadlock).

// Fix 2: try_get with backoff — never hold-and-wait
task acquire_both(semaphore s_bus, semaphore s_mem);
  forever begin
    s_bus.get(1);
    if (s_mem.try_get(1)) return;   // got both — done
    s_bus.put(1);                   // could not get mem: release bus,
    #1;                             // back off, and retry — no deadlock
  end
endtask

Interview angle

• "Mutex vs semaphore?" — a 1-key semaphore acts as a mutex but has no ownership; any process may put.

• "Two agents share a bus — synchronize them." — shared semaphore handle, get/put around the drive task.

• "Your sim hangs at the same time every run." — suspect a get() with no matching put, or AB-BA deadlock.

Key takeaways

• get(M) blocks atomically for M keys; put(M) returns them; try_get is the non-blocking probe.

• Semaphores have no ownership — get/put pairing is a convention you must enforce in code review.

• One key gives mutual exclusion; N keys meter a resource pool or credit count.

• Avoid deadlock by global lock ordering or try_get-and-backoff; never hold one lock while blocking on another.

Common pitfalls

• Forgetting put() on an early return or error path — the bus is leaked and every later get hangs.

• Calling put() more times than get() — key count grows and mutual exclusion silently disappears.

• Two processes each holding one semaphore while blocking on the other — AB-BA deadlock.

• Using a semaphore to pass data — it only counts keys; use a mailbox for payloads.