Tcl Library Source Code

View Ticket
Login
Ticket UUID: 454718
Title: Semephore
Type: RFE Version: None
Submitter: erempel Created on: 2001-08-23 21:24:51
Subsystem: control Assigned To: dgp
Priority: 5 Medium Severity:
Status: Open Last Modified: 2003-04-25 01:15:14
Resolution: Closed By:
    Closed on:
Description:
With packages that provide a call back mechanism, it is
possible to have many essentially background processes.
Take the http:: package. It is possible to have many
http::geturl requests running simultaneously, but there
is really no default way to coordinate the call backs for
the various open requests.

A semephore package with the ability to wait on any
number of call backs is desirable. Using a generic
waitany routine would require that I be aware of the
internal variables of the http package to wait on
changes of these variables. Implimenting all of this in
a single semephore package allows the same
functionality without the need to have knowledge of the
internals of a package.

As a staring point I submit the following. There may
have to be changes due to multi-threaded tcl code, but
its a start none the less.

#  semephore.tcl
#  Impementation of semephores
#
#  Semephore::Signal token
#  Semephore::Wait   ?pattern?   - returns token
#  Semephore::Reset  token

package provide SemephorePkg 2.1

# 2.1 - October 22, 2000
#     - fixed a bug that would result in a very slow
memory leak

namespace eval Semephore {
  variable SemData
  array set SemData {}
  variable SemAny 0

  namespace export Signal Wait Reset
}


# -------------------------------------------------
Signal ----
# Signal a semephore
proc Semephore::Signal { SemToken } {
  variable SemData
  variable SemAny

  if {![info exist SemData($SemToken)]} then {
     set SemData($SemToken) 1
  } else {
     incr SemData($SemToken)
  }
  incr SemAny
}

# -------------------------------------------------
Wait ----
# Wait for a semephore
# Note: Resetting a semephore does not signal it.

proc Semephore::Wait { args } {
  variable SemData
  variable SemAny

  set Pattern [lindex $args 0]
  if {"$Pattern" == ""} then { set Pattern "*" }
  set FoundFlag 0
  set FoundName ""
  if {$SemAny != 0} then {
    foreach n [array names SemData $Pattern] {
      if {$SemData($n) > 0} then {
        set FoundName $n
        set FoundFlag 1
        break
      }
    }
  }
  while {!$FoundFlag} {
    vwait Semephore::SemAny
    foreach n [array names SemData $Pattern] {
      if {$SemData($n) > 0} then {
        set FoundName $n
        set FoundFlag 1
        break
      }
    }
  }
  if {[incr SemData($FoundName) -1] == 0} then {
    unset SemData($FoundName)
  }
  incr SemAny -1
  return $FoundName
}

# -------------------------------------------------
Reset ----
# Reset a semephore
# Note: Resetting a semephore does not signal it.

proc Semephore::Reset { SemToken } {
  variable SemData
  variable SemAny

  if {[info exist SemData($SemToken)]} then {
    incr SemAny -$SemData($SemToken)
  }
  set SemData($SemToken) 0
}
User Comments: dgp added on 2003-04-25 01:15:14:
Logged In: YES 
user_id=80530


did not review in time for tcllib 1.4

lvirden added on 2003-04-12 17:19:20:
Logged In: YES 
user_id=15949

Semaphore , as a package name, concerns me as
it can have more than one meaning.  On POSIX based
machines, there is a kernal based IPC data structure
called a semaphore,

Given that both uses of the term are common, what
would be the best way to disambiguate the issue?

andreas_kupries added on 2003-04-12 05:36:30:
Logged In: YES 
user_id=75003

Raising the priority of the item because its inclusion in the 
upcoming release was proposed in the Tcllib-devel mailing list.

Supporting or contrarian statements should be made on the 
referenced mailing list for public discussion.

erempel added on 2001-10-01 07:45:55:
Logged In: YES 
user_id=304001

Sorry for the long delay.

By "default way of coordinating callbacks", I mean that 
currently, if I am using two packages that have callback 
facilities, I must write my own code to wait on them at the 
same time. There is currently no mechanism in TCL to invoke 
asynchronous routines and wait for the one that completes 
firsts. I must wait for one routine specifically, and then 
wait for the other routine. If I wait for the wrong one, 
the following processing timeline is the result.

1. Start asynchronous routine A (completes in 5 seconds)
2. Start asynchronous routine B (completes in 2 seconds)
3. Wait for routine A to complete (5 second idle time)
4. Process the result of A (2 seconds)
5. Wait for routine B to complete (0 seconds idle time)
6. Process the result of B (2 seconds)

Total time = 5 sec idle + 4 sec processing = 9 seconds.

I would like to do

1. Start asynchronous routine A (completes in 5 seconds)
2. Start asynchronous routine B (completes in 2 seconds)
3. Wait for routine A or B to complete (2 second idle time)
4. Process the result of B (2 seconds)
5. Wait for routine A or B to complete (1 second idle time)
6. Process the result of A (2 seconds)

Total time = 2 idle + 2 process + 1 idle + 2 proc = 7 sec

If A and B are from the same package, this is usually easy, 
provided that the author build a "wait any" function.
If A and B are from different packages, I must invent some 
way to handle this -> semaphores.


The general concept is that I want to be able to wait for 
any of the callbacks, without knowing which one will 
respond first, or possibly waiting for any one of a 
particular type of callback, again without knowing which 
one will respond first.

An example is something like

 http::geturl $A ... -command Semaphore::signal
 http::geturl $b ... -command Semaphore::signal
 timer::set "120 seconds" -command Semaphore::signal

 for {set x 1} {$x <= 3} {incr x} {
   set completed [semaphore::wait *]
   switch -glob -- $completed {
     ::http* { ... }
     ::timer* { ... }
     default { error "Unknown completed semaphore 
$completed" }
   }
 }

This way, we don't get stuck on waiting for a response from 
a web server response, and we can determine timeouts. I 
realize that the http::geturl has a timeout option, 
however, the order in which you wait for them to complete 
becomes critical. With thus structure there is no need to 
build timeouts into all routines such as ftp, email, http, 
database, socket listening etc., and one does not have to 
wait for specific events to finish resulting in the ability 
to continue processing as soon as the first one completes.

The above code is very safe, but one could wait on 
semaphores of the format ::http::* or any other format.

dgp added on 2001-09-12 22:51:15:
Logged In: YES 
user_id=80530


I think there are many related ideas here.  Tcl's variable
and command traces, Tk's widget bindings, the Notifier
class in [incr Tcl] that Michael McLennan described at
the latest Tcl/Tk conference, as well as some internal
code we use on the OOMMF project.  I think this semaphore
idea is similar too.

They all have in common the notion of registering a callback
script to be evaluated later when something happens.  It
would be a worthwhile exercise for someone to make an
inventory of these techniques and what they share in common
and how they differ.  My impression is that the
implementations are very different, even when the purposes
are quite similar.

Perhaps there's a fundamental capability to be extracted
out and used by all?

andreas_kupries added on 2001-09-12 04:44:12:
Logged In: YES 
user_id=75003

I do not understand the part about the missing "default way 
of coordinating the callbacks".

What do you mean by 'coordinating' ?

Later you say 'ability to wait on any number of call backs 
is desirable'. 

If I undertand you correctly you want to start, say several 
http requests, and then perform an action after _all of 
them_ have reported back via the callback you gave them ?

Can you give me an example script how to use this ?

Note: It might have been better to attach the above 
implementation as a file instead of inlining it into the 
message itself. See the "check to upload and attach file" 
checkbox and entry items below, after the followups.