Obviously the canonical use of semaphores is to ration access to a
finite number of resources, say hard disks or memory buffers. It has
occurred to me that a semaphore could, in theory, also be used to
ration permission to send messages in a TCP-like protocol, where
messages must be acknowledged and sending is permitted only when the
number of unacknowledged messages is less than an arbitrary window
value. Would such a use be categorized as a legitemate use or an
unjustified abuse of a semaphore?

--
Christopher Benson-Manica | I *should* know what I'm talking about - if I
ataru(at)cyberspace.org | don't, I need to know. Flames welcome.

Christopher Benson-Manica wrote:

Say having 10 max sized buffers, when any becomes occupied semaphore is
decreased, freeing a buffer increases a semaphore. Of course the buffer was
freed when full message was acknowledged or timeout occurred.

Maciek

Christopher Benson-Manica wrote:
messages that timed out. All the semaphores would buy you is
keeping the number of unacknowledged messages below a certain
level so the resend thread could keep up. So it would be a
valid use in that case.

--
Joe Seigh

When you get lemons, you make lemonade.
When you get hardware, you make software.

Christopher Benson-Manica wrote:
This is your lucky day :-) I've only just completed a full protocol
over serial line for a 16-bit micro (datalink, network and transport).

My network layer does indeed have windows, and I can assure you
that relying on a semaphore never even occurred to me as the actual
protocol (whether over serial or ethernet or ...) is not multitasking
unless the protocol itself is to be used for that purpose; seeing
as how I cannot think of a single protocol that is used for more
than one task at one end[1].

Somehow, I think perhaps you don't mean what I thought you did,
although perhaps if you could come up with an example I'd be
interested as to how this could be used.

[1] Those that are create virtual circuits to avoid stepping on
other transmissions toes.

goose,
the cereal handler :-)

goose <ruse@webmail.co.za> wrote:

Well, it sounds to me like you implemented TCP itself
(congratulations!)...

Well, this protocol is both higher level and more rudimentary than TCP
- in Java the situation would look something like

class queue {
Queue<T> queue; // Made-up structure
Semaphore s = new Semaphore(3); // Window 3, arbitrary

public T get() {
s.acquire(); // Blocks until some ack()'s happen
return queue.get();
}

public void ack() {
s.release();
}
}

Basically the ack()'s come from a connected client, which may as well
be handled by a separate thread since the ack()'ed messages are just a
number. The thread doing the sending wouldn't be able to dequeue
another T to send until the client sent some ack()'s.

Does that make any sense?

--
Christopher Benson-Manica | I *should* know what I'm talking about - if I
ataru(at)cyberspace.org | don't, I need to know. Flames welcome.

Christopher Benson-Manica wrote:
I did, but this wasn't it :-) TCP is a little heavy when I've
got only 3K of stack space to play with and no heap.

Forgive (or even better, correct) me if I misunderstand this;
I'm not a java developer.

AIUI, the above code uses one window (window 3 in this case)
to send a message *only* if that window is not currently
engaged in a send and/or receive-ack with the connection?

Sure, for a connection which has multiple *channels*. I have to admit
being a little bit confused about the word "window" being used. I've
always used "window" (in the context of transmission protocols) to
mean "the number of frames that can be transmitted without waiting
for an acknowledgement". I'm beginning to suspect that you mean
something different, though; something perhaps similar to "A single
connection that can be used by multiple threads/processes independently
and/or invisibly to each other".

Like I said above, I've not found a need for a semaphore *unless*
the protocol itself is multitasking i.e. more than one virtual
connection runs across it.

Multiple windows (using my definition above for "window") are
only a little harder than if you have a single (nonchangeable)
window. IIRC, TCP allows window resizing during a connection.

I think that this is how a lot of the traffic shapers shape traffic?
(someone who knows for sure will *surely* post a correction :-)
<clueless conjecture>
They change the window size as the packets pass them, thereby
throttling the connection by making the window size smaller
and "opening up" the connection by making the window size larger.
No need to needlessly drop packets to throttle a connection.
</cc>

Post a simple state-machine for what you envision; I'm very curious
now.

goose

goose <ruse@webmail.co.za> wrote:

I think I've just done a lousy job of explaining myself, but hopefully
your curiousity will pay off in something interesting anyway... I
apologize in advance for being too lazy to implement the state machine
in pretty ASCII characters ;-)

Basically, this could be accomplished on one thread, without anything
complicated:

while(true) {
if(pending_acks > window) {
wait_for_ack();
pending_acks--;
}

send_message();
pending_acks++;

if(check_for_ack()) // Doesn't block
pending_acks--;
}

What I'm thinking of is something like

Thread 1:

while(true) {
get_window_semaphore_permit(); // Blocks if there aren't any
send_message();
}

Thread 2:

while(true) {
wait_for_ack();
release_window_semaphore_permit();
}

Of course, using a sempahore isn't *required* by any stretch - the
main thrust of my question is whether it makes sense from a conceptual
standpoint to view "ability to send a message" (in this case
predicated on how many have been ack'ed) as a resource that a
semaphore can regulate access to.

If that still didn't make sense, I'll have to fall back on the ASCII
art, but it isn't my first language :-)

--
Christopher Benson-Manica | I *should* know what I'm talking about - if I
ataru(at)cyberspace.org | don't, I need to know. Flames welcome.

Christopher Benson-Manica wrote:

Maybe this neat ASCII drawing tool will help you:
http://www.tech-chat.de/download.html


Martin

--
Quidquid latine scriptum sit, altum viditur.

Christopher Benson-Manica wrote:
I actually think that I'm not "getting it" because I'm not seeing
the big picture (but thanks for taking the time to bludgeon it
into me :-).

If I understand you, that "if" up there would be
better replaced with a "while"? If thats not the
case then I obviously don't understand.

Suprisingly enough, I understand now; I've always had the
"regulation" as a byproduct of a state-machine, even if the
state-machine ran in it's own thread. Using semaphores
(like above) would allow you to multiplex the communications
between different threads on the same connection, yes?

goose,
dense today (although I *still* consider those seperate
windows as channels).

Martin Eisenberg <martin.eisenberg@udo.edu> wrote:

It must be great for posting on those electrical hardware newsgroups
:-)

--
Christopher Benson-Manica | I *should* know what I'm talking about - if I
ataru(at)cyberspace.org | don't, I need to know. Flames welcome.

goose <ruse@webmail.co.za> wrote:

Oops, you're right. That's what I meant.

Yes, which is partly why the idea occurred to me. It seemed good to
me, but I know about 50% of my ideas turn out to be dumb, so I wanted
to ask the experts :-)

--
Christopher Benson-Manica | I *should* know what I'm talking about - if I
ataru(at)cyberspace.org | don't, I need to know. Flames welcome.

Christopher Benson-Manica wrote:
<snipped>

Only 50%? 99 out of a hundred of my ideas are real duds.

<grin>
However, the 100th one is generally a jaw-dropper, which is
how I get to make a living at this :-)

I wonder why they didn't answer ;-)

goose

goose wrote:
"If most of your ideas aren't stupid, you're probably being too
conservative. You're not bracketing the problem."
-- http://paulgraham.com/marginal.html

toby wrote:
Man, I feel a lot better now :-)

gooseb