8.2.3 The Semaphore That Never Blocked

EasyFixVerilator · serverReview the topic

Fix a bus lock that grants the bus to two users at once, because its semaphore is not the built-in one.

Hardware context: UART line watcher, link checkers and a bus lock that share declarations through packages. Make a bus lock use the built-in semaphore that a package class was hiding.

This is a Fix problem: the code in the editor has one realistic defect. Find it and fix it.

A bus lock uses a semaphore with one key, so one user holds the bus at a time. In the regression two drivers wrote to the bus in the same cycle. The lock had granted both.

The code imports pool_pkg for log_grant and USERS. That package also declares a class named semaphore, a key counter for statistics whose try_get never refuses. The wildcard import offers it, and it is found before the built-in class.

Make the lock use the built-in semaphore of the std package. Keep the import: the lock still needs log_grant. Your code sits inside the test module, so the import is a module import.

Signals in the Timeline

SignalWidthRole
user8input of each check
Full specification
Compiled before your code (you cannot change it)
// pool_pkg.sv: shared helpers of the bus team.
package pool_pkg;
  parameter int USERS = 4;
  int grants [USERS];              // how often each user got the bus
  function automatic void log_grant(input int user);
    grants[user]++;
  endfunction
  // A key counter for statistics. It counts requests and never refuses one.
  class semaphore;
    int keys;
    function new(int n = 0);
      keys = n;
    endfunction
    function int try_get(int n = 1);
      keys -= n;
      return 1;
    endfunction
    function void put(int n = 1);
      keys += n;
    endfunction
  endclass
endpackage

CallCorrect lock
try_take(user)Returns 1 and records the user as holder when the bus is free. Returns 0 when someone holds it.
give_back(user)Frees the bus when user is the holder. Does nothing otherwise.

Each case makes one call. It reports whether the bus was granted, who holds it (-1 for nobody) and the number of grants logged in pool_pkg. It also tries bus_key itself: its one key must be taken exactly while someone holds the bus.

Examples

Example 1

The First User Gets the Bus
Input
try_take(0)
Output
key_taken = yes, granted = yes, holder = 0, grants_so_far = 1

The key is free, so user 0 takes it and becomes the holder. One grant is logged.

Example 2

A Second User Is Refused
Input
try_take(1)
Output
key_taken = yes, granted = no, holder = 0, grants_so_far = 1

The only key is taken. The built-in try_get returns 0, so the holder stays user 0.

Example 3

A User Without the Bus Cannot Give It Back
Input
give_back(1), then the state
Output
key_taken = yes, granted = no, holder = 0, grants_so_far = 1

User 1 is not the holder, so nothing changes.

Constraints and Contract

  • Keep try_take, give_back, holder and bus_key.
  • Keep the import of pool_pkg; grants must still be logged through log_grant.
  • One key: at most one user holds the bus.

Hints

Hint 1

Two classes are named semaphore here. Which scope does the search reach first: the import in your code, or the built-in package?

Hint 2

The built-in package has a name of its own. A name written with its package in front is never searched.

Hint 3

Keep one key. The number of users does not change how many may hold the bus.

What the grader checks: The lock is called in directed and seeded sequences of requests and returns from four users. Passing shows at most one user holds the bus on these sequences, and that grants are still logged. The tests also try bus_key itself, so its one key must really be taken. The runs use Verilator 5.052, because Icarus 12 has no std package.

35 checks on Verilator · server. Run the examples first, then check the full regression. Full checks use the server judge. Downloads contain public samples only. A passing result establishes the tested cases, not a proof for all possible inputs.

See all 3 steps and the final capstone

Report a problem with this page

Your code SystemVerilogSaved locally
Ln 1, Col 1Tab indents · Ctrl/⌘ + Enter runs samples
Not run yet

The First User Gets the Bus

Input
try_take(0)
Expected output
key_taken = yes, granted = yes, holder = 0, grants_so_far = 1

The key is free, so user 0 takes it and becomes the holder. One grant is logged.

Run samples executes all 3 public checks. Check all tests runs 35 checks on the server.

Verilator · server