Semaphores

Analysis of Issues for Creating Semaphores in VHDL

• Who Updates: JimLewis, <Add YourName>, ...
• Date Proposed:
• Date Last Updated:
• Priority:
• Complexity:
• Focus: Testbench

Requirement Summary

• SAB 15: Semaphore data structure. Implement in a library.
  • Provides: New(#keys), Get(#keys), Put(#keys), TryGet(#keys)
  • Use Protected type is the key counter & implement the rest using regular functions and procedures.
  • TryGet is a function, the others are procedures.
  • New returns the handle to the object - could be an integer index value
  • What do we need it for? Multiple items trying to use one resource. Software - network access to a printer
  • Typically only one key. Default for put and get is 1 key.
  • Waiting queue is first in, first out.
  • Should be deterministic.

Related Issues:

Issue: ISAC Issue 2109

In ISAC Issue 2109, Paul Butler points out that if an implementation loops on TryGet, as shown below, the language is not required to suspend execution of the process while executing the while loop. As a result, the process that releases the semaphore may not start. As a result, the "wait for 0 ns" shown commented out is required to assure completion of the processes.

  P1: process is
  begin
    assert SemA.try_get;
    wait for 0 ns;
    SemA.put;
    while not SemB.try_get loop
      report "P1 waiting for SemB";
     --  wait for 0 ns;
    end loop;
    report "P1 finished";
    wait;
  end process P1;

  P2: process is
  begin
    assert SemB.try_get;
    wait for 0 ns;
    SemB.put;
    while not SemA.try_get loop
      report "P2 waiting for SemA";
      -- wait for 0 ns;
    end loop;
    report "P2 finished";
    wait;
  end process P2;

Issue: TryGet running transactions while locked

An extension to the issues illustrated by ISAC issue 2109, happens when a process locks the semaphore, starts a transaction, and then unlocks the semaphore. The problem becomes more interesting. Here, a simple "wait for 0 ns" in the while loop is insufficient.

Analysis of: ISAC Issue 2109

This same issue is shared by SystemVerilog semaphores. When calling the SystemVerilog try_get, time must pass between calls for it to execute correctly. Or said another way, a loop with try_get requires a time consuming method to be called between the calls to try_get. This is a methodology thing.

For cases where a process needs to suspend until the semaphore is unlocked, the method Get is used.

I suspect that the example in 2109 did not implement Get is that it is not currently implementable directly in a protected type. Instead, it requires a wait statement. Currently wait statements are not permitted within a protected type.

A First Trial Implementation:

There is an implementation of a semaphore in an open source project. This can be used to explore implementation of semaphores, to expose some of the limitiations of the current language, and make suggestions for language updates.

Suggested Language Changes

Based on the open source trial implementation, the following language updates would be helpful to create a Semaphore and other data structures in either greater utility or in a simplified manner.

Protected Types with Wait Statements

See proposal: Protected Types: Wait and Private Signals

In order to implement Get within a protected type, requires support for wait statements within a protected type procedure method. This is some what complicated by a protected type guaranteeing mutual exclusive access to the internals of the protected type. When a wait statement is encountered, the mutual exclusive access must be dropped, as otherwise, there would be no way to release the semaphore. This means when the method wakes up from a wait, either it is an error (detected by the compiler) or erroneous (meaning an error that is not detected by any compiler) for the method to access local variables (ones declared in the method) before they are updated with new values or local variables must be re-initialized to either the same value they had on entry to the method or the left-most value of the type. Another alternative is to disallow local variables in a procedure method that calls wait. Since this method can call other procedures which can have local variables, this may be an acceptible conservative simplification of the requirements.

In addition, to satisfy the nature of common structures such as Semaphores and Mailboxes, if there are multiple calls to a protected method (called from different processes/threads), then the wait statements must be checked in the order they were received (ie: semahpore and mailbox waiting queues is first in, first out). Furthermore, if there are waits statements currently suspended and a signal changes within these wait statements, these methods must be run before new methods of the protected type may run.

Private Signal/Event Class object in protected type body

See proposal: Protected Types: Wait and Private Signals

A semaphore Get needs some sort of a wake-up event. In an architecture, this would be a signal. The issue with a signal is one must trace drivers back to their source. Inside the protected type body, we do not want to create a persistent source of a signal. Instead we want to drive a signal and use register kind properties to retain its value after the method exits. Alterantely a new object with deposit type (no drivers) that has events like a signal and signal type update rules (meaning update on the next simulation cycle/delta cycle to ensure safe execution).

'transaction and declaration of signals in procedures (and processes)

See proposal: Protected Types: Wait and Private Signals

The attribute 'transaction creates and equivalent signal. Currently its usage in procedures is forbidden. However, in particular with respect to creation of semaphores, it would be useful if not necessary to be able to use "wait on signal_name'transaction" rather than "wait on signal_name". The issue being what happens with a multi-key semaphore when one processes does a put during the same delta cycle in which another does a get - both for the same amount. If a signal based algorithm were used, then there would not be an event on the signal.

Wait Statements on Private Variables

See proposal: Protected Types: Wait and Private Signals

There are potential interesting interactions between methods, waits, and delta cycles. Would it be reasonable to consider waking up wait statements within a method based on a protected type variable? In the above, how does one resolve the timing between the semaphore count signal and the semaphore count variable? Maybe a conjunction of the signal and variable need to be used?

Functions with Protected Type inputs

See Proposal: Allow access and protected type parameters on function interfaces

Currently VHDL functions do not allow either access types or Protected Type inputs. ADA removed the requirement for not allowing access type inputs in ADA-95. This would allow overloads like the non-protected type procedure TryGet[SemaphorePType, Boolean, Integer] to be re-expressed as a function TryGet[SemaphorePType, Integer return boolean] which is a more natural way to use it. The code is as follows

  function TryGet (Semaphore : SemaphorePType ; Count : Integer := 1 ) return boolean is
  begin
    return Semaphore.TryGet(Count) ; 
  end function TryGet ;

Make a shared variable name accessible internal to the protected type

See proposal: Paths to Protected Type Instances and Subprogram Calls

Many data and control structures require a name to produce a useful error message. Rather than requiring a user to set an internal name, it would be preferrable to set that name (at least by default) to be something that is based on the protected type itself.

Usage of instance_name and path_name within a protected type currently returns a name that is based on a name being in a package. Instead what I need is the name of the variable that creates the protected type object.

Allow Public Shared Variables in a Protected Type

See proposal: Composition with Protected Types

Many code structures reuse an item from another code structure. The is demonstrated in the open source semaphore prototype implementation with local the variable Name : NamePType defined in the protected type body with methods SetName, GetName, IsSetName, and ClearName. Rather than these, it would be much easier to accomplish this by doing:

  type SemaphorePType is protected
    . . . 
   shared variable Name : NamePType ; 
  end protected SemaphorePType ;

Then calling the methods of Name by the following:

architecture A of E is 
  shared variable Semaphore : SemaphorePType ; 
  . . . 
begin

  TestProc : process
  begin
    Semaphore.Name.Set("Test1_SemaphoreA") ;   -- not necessary to be in a process
    . . . 

If shorthand names are desirable, like provided in the package, It would be nicer to be able to create them with an alias instead:

  type SemaphorePType is protected
    . . . 
   shared variable Name : NamePType ; 
   -- For simple mapping.  Signature only required when it is otherwise ambiguous.
   alias GetName is Name.Get [return boolean] ;

   -- For more complicated mappings.  
   -- Intended to allow parameter reordering and mapping parameters to static values.
   alias SetName (NameIn : string) is Name.Set(NameIn); 

   . . . 
  end protected SemaphorePType ;

Public Signal/Event Class object in protected type declaration

See proposal: Protected Types with Public Signals

Allow public signals in a protected type declarative region. Access to these signals shall use a record like dot notation. Values driven from within the protected type are deposit only (similar to private Signal/Event class objects). Values driven from outside the protected type have normal drivers.

Gives a protected type similar capabilities to an interface in SystemVerilog.

Questions

General Comments

Supporters

Add your signature here to indicate your support for the proposal

-- Main.MartinThompson - 2013-02-22