Semaphores, ownership and deadlock

Keys in a bucket

A semaphore is a bucket of keys shared by processes. new(N) creates it with N keys. get(n) blocks until n keys are free and then takes them, and put(n) returns n keys. try_get(n) never blocks: it takes the keys and returns nonzero if they are free, or returns 0.

With one key, a semaphore is a lock. Only the process that holds the key may run the critical section, the code that uses the shared resource, and every other process waits in get(). When several processes wait, they are served in the order in which they asked.

A semaphore with more than one key models a pool. A memory model that accepts at most four outstanding reads can use new(4). Each read takes a key when it starts and returns it when its data comes back, so a fifth read waits until one of the four finishes.

Protect the whole operation

The lock must cover everything that has to happen without interruption. Here that is the whole three-beat burst, so get(1) goes before the first beat and put(1) after the last. A lock around each single beat would still let the beats of two bursts alternate.

Keep the critical section that size and no bigger. Every cycle you hold the key is a cycle in which no other sequence can use the bus. If a sequence holds the key while it waits for a slow read response, every other sequence stalls for that whole wait, and the test runs slower without failing.

Take and return the key in the same task that does the work, so the pair is easy to see. When get() and put() sit in different tasks or different classes, it becomes hard to prove that every path gives the key back.

The semaphore trusts you

A semaphore keeps a count of keys and nothing else. It does not record which process took a key, so any process may call put(), and nothing checks that a process returns exactly what it took.

Two mistakes follow from that. A leaked key is one that is never returned, for example because an error path returns early, and every later get() then blocks forever. An extra put() adds a key that was never taken, so two processes can be inside the critical section at once.

bus_key.get(1);
if (!item_ok) return;   // key never returned
drive(item);
bus_key.put(1);

if (!item_ok) return;   // no key held yet
bus_key.get(1);
drive(item);
bus_key.put(1);

A process killed with disable fork while it holds a key leaks that key too, because it never reaches its put(). Stop such processes only at points where they hold no keys, or return the key on their behalf.

A leak is cheap to catch at the end of the test. Once all sequences have finished, call try_get for the full number of keys, and report an error if it fails, because some path kept a key.

Deadlock: two processes, two semaphores

Some operations need two resources. Process P1 takes the bus key and then the mem key, while process P2 takes mem first and then bus.

This is a deadlock. If nothing else is scheduled, for example when no clock is running, the simulation simply ends at that point. A test that never checks how much work was finished can then report a pass.

// P1                 // P2
bus.get(1);            mem.get(1);
#1 mem.get(1);         #1 bus.get(1);

// P1                 // P2
bus.get(1);            bus.get(1);
#1 mem.get(1);         #1 mem.get(1);

The rule is to give the semaphores a fixed order and to have every process take them in that order. Write the order down next to the declarations, because one new sequence that breaks it brings the deadlock back.

One semaphore is enough for a deadlock, too. A task that holds the bus key and then calls a helper task that also takes the bus key waits for itself. The semaphore cannot tell that both requests come from the same process, so it makes the helper wait for a key that only its caller can return.

Try it

Without the key, the beats alternate exactly as in the opening story. With it, B blocks in get() at t=1 and starts only when A returns the key at t=6.

The stray put() raises the count to two keys, so both bursts get in and the beats alternate again, with no error from the semaphore. Now delete the put(1) at the end of burst and predict what the second run prints.

Check yourself

module tb;
  semaphore bus = new(1), mem = new(1);
  int done;
  initial begin
    fork
      begin bus.get(1); #1 mem.get(1); done++; mem.put(1); bus.put(1); end
      begin mem.get(1); #1 bus.get(1); done++; bus.put(1); mem.put(1); end
    join_none
    #50 $display("t=%0t done=%0d", $time, done);
  end
endmodule

task automatic send_burst(bit ok);
  if (!ok) return;
  bus_key.get(1);
  drive();
  bus_key.put(1);
endtask

task automatic send_burst(bit ok);
  bus_key.get(1);
  if (ok) drive();
  bus_key.put(1);
endtask

task automatic send_burst(bit ok);
  bus_key.get(1);
  if (!ok) begin
    bus_key.put(1);
    return;
  end
  drive();
  bus_key.put(1);
endtask

task automatic send_burst(bit ok);
  bus_key.get(1);
  if (!ok) return;
  drive();
  bus_key.put(1);
endtask

Practice

• Protected shared counter Fix · Easy