Bookstore

Recent

Author Topic: Multithreading with Semaphores  (Read 7398 times)

kapibara

  • Hero Member
  • *****
  • Posts: 520
Multithreading with Semaphores
« on: July 28, 2015, 08:14:36 pm »
I also posted this in the fpc mailinglist, but most people here don't use that so here goes...

A counting, or general, semaphore limits simultaneous access to a resource according to the number of permits you specify. On the other hand, a binary semaphore like a critical section limits the access to "one at a time".

FPC doesn't seem to have a general semaphore. I recently attempted to implement one, here is the code, plus a working Lazarus demo attached. It blocks on an event instead of the usual critical section. However, I didnt manage to have it block by just calling Wait, because then the code blocked without leaving the PermitLock and that meant deadlock for all threads. So thats why you see the "if Semaphore.Wait(aEvent) then RTLEventWaitFor(aEvent)" instead of just Semaphore.Wait(aEvent). It works just fine, but if anyone knows how to implement this by just calling Wait(aEvent), please tell. If you want to block on a critical section instead of an event, do that. Perhaps the result could be TFPSemaphore and go with FPC.

Code: [Select]
unit kbsemaphore;

{$mode objfpc}{$H+}

interface

uses
  Classes, SysUtils, syncobjs, contnrs;

type

  { TKBSemaphore }

  TKBSemaphore = class
  private
    FPermits: Cardinal;
    FPermitLock: TCriticalSection;
    FBlockQueue: TQueue;
    function GetWaitCount: Cardinal;
  public
    function Wait(var AEvent: PRTLEvent): Boolean;
    procedure Post;
    constructor Create(MaxPermits: Cardinal);
    destructor Destroy; override;
    property WaitCount: Cardinal read GetWaitCount;  //Approximate precision!
    property Permits: Cardinal read FPermits;
  end;


implementation

{ TKBSemaphore }

function TKBSemaphore.GetWaitCount: Cardinal;
begin
  FPermitLock.Enter;
  Result:= FBlockQueue.Count;
  FPermitLock.Leave;
end;

function TKBSemaphore.Wait(var AEvent: PRTLEvent): Boolean;
begin
  FPermitLock.Enter;
  if (FPermits > 0) then
  begin
    Dec(FPermits);
    Result:= False;
  end
  else
  begin
    AEvent:= RTLEventCreate;
    FBlockQueue.Push(AEvent);
    Result:= True;
  end;
  FPermitLock.Leave;
end;

procedure TKBSemaphore.Post;
begin
  FPermitLock.Enter;
  if FBlockQueue.Count > 0 then
  begin
    RTLeventSetEvent(PRTLEvent(FBlockQueue.Peek));
    RTLeventdestroy(PRTLEvent(FBlockQueue.Pop));
  end
  else
    Inc(FPermits);

  FPermitLock.Leave;
end;

constructor TKBSemaphore.Create(MaxPermits: Cardinal);
begin
  FPermits:= MaxPermits;
  FPermitLock:= TCriticalSection.Create;
  FBlockQueue:= TQueue.Create;
end;

destructor TKBSemaphore.Destroy;
begin
  FPermitLock.Free;
  FBlockQueue.Free;
  inherited Destroy;
end;

end.


EDIT: This was early attempt. The final semaphore is found further down in this thread.
« Last Edit: March 27, 2020, 12:03:25 am by kapibara »
Lazarus trunk / fpc 3.0.4 / Debian 10 - 64 bit

taazz

  • Hero Member
  • *****
  • Posts: 5365
Re: Multithreading with Semaphores
« Reply #1 on: July 28, 2015, 10:49:18 pm »
1) every lock/unlock pair must be protected at all time use a try..finally block for that.
2) what happens if one thread destroys the semaphore and an other calls the getwaitcount?
3) what happens when you call wait?
4) why post? as far as I know post is called to persist changes to a container also known as send or save.

I'll have to look at your demo to better understand your intentions but as far as I can see there is nothing here that could pause a thread until an access slot is open it is left to he thread to do the actual check and pause (I think, I'll have a better understanding when I see your demo).
please enclose the code in code tags it makes it easier to read.
Good judgement is the result of experience … Experience is the result of bad judgement.

OS : Windows 7 64 bit
Laz: Lazarus 1.4.4 FPC 2.6.4 i386-win32-win32/win64

kapibara

  • Hero Member
  • *****
  • Posts: 520
Re: Multithreading with Semaphores
« Reply #2 on: July 29, 2015, 01:16:58 am »
Quote
1) every lock/unlock pair must be protected at all time use a try..finally block for that.

I forgot to put it back in the last implementation. Thx for the reminder.

Quote
2) what happens if one thread destroys the semaphore and an other calls the getwaitcount?

The semaphore must not be destroyed before all threads are done.

Quote
3) what happens when you call wait?

Calling Wait is like entering a critical section, only that with a semaphore you dont block other threads until they outnumber the value of Semaphore.Permits. In that case Wait returns True and inside the code of your resource object you call RTLEventWaitfor(aEvent). When a thread finishes, it calls Semaphore.Post and that unblocks the next thread.

Quote
4) why post? as far as I know post is called to persist changes to a container also known as send or save.

Wait and Post are common names in semaphore implementations. Dijkstra, who invented the semaphore used V (verhoegen) for Post and P (probeeren) for Wait. But it can be called anything, instead of Post, Signal is also common. It might be even better, since post is used for other things in db programming.

https://en.wikipedia.org/wiki/Semaphore_%28programming%29

Quote
I'll have to look at your demo to better understand your intentions but as far as I can see there is nothing here that could pause a thread until an access slot is open it is left to he thread to do the actual check and pause (I think, I'll have a better understanding when I see your demo).
please enclose the code in code tags it makes it easier to read.

The blocking call is done outside the semaphore when Wait returns True. I had to do that because otherwise I got deadlock. If someone knows how to do it differently I'm all ears. Usually with semaphores you just call Wait(aSemaphore) and Post(aSemaphore). Some implement also timed waits, but I didn't get so far.

People have been asking for a freepascal semaphore for at least 7 years. The guys who came up with the idea of a semaphore in the 80's almost went nuts in the process. The past week I have come to understand them. ;)

Sample code from the demo, how to Wait and Post:

Code: [Select]
function TMyResource.Access: Boolean;
var
  aEvent: PRTLEvent = nil;
begin
  Result:= False;

  if FSemaphore.Wait(aEvent) then
    RTLeventWaitFor(aEvent);
  try
    if Available then  //Queued threads wont proceed if not available = faster shutdown.
    begin
      sleep(Random(3500)); //Here would the access code go
      Result:= True;
    end;
  finally
    FSemaphore.Post;  //Increments Permit Count or unblocks blocked thread
  end;
end;
« Last Edit: July 29, 2015, 01:20:27 am by kapibara »
Lazarus trunk / fpc 3.0.4 / Debian 10 - 64 bit

taazz

  • Hero Member
  • *****
  • Posts: 5365
Re: Multithreading with Semaphores
« Reply #3 on: July 29, 2015, 02:38:29 am »
Quote
2) what happens if one thread destroys the semaphore and an other calls the getwaitcount?

The semaphore must not be destroyed before all threads are done.

That is not an option you have. Don't try to enforce rules that are outside of your code's control and don't allow anyone to bypass your rules.
Specifically your code must be able to work in both (destroyed before and after all threads are done) cases and I must not be able to ignore the result of wait and access the data any way.

Quote
3) what happens when you call wait?

Calling Wait is like entering a critical section, only that with a semaphore you dont block other threads until they outnumber the value of Semaphore.Permits. In that case Wait returns True and inside the code of your resource object you call RTLEventWaitfor(aEvent). When a thread finishes, it calls Semaphore.Post and that unblocks the next thread.

Quote
4) why post? as far as I know post is called to persist changes to a container also known as send or save.

Wait and Post are common names in semaphore implementations. Dijkstra, who invented the semaphore used V (verhoegen) for Post and P (probeeren) for Wait. But it can be called anything, instead of Post, Signal is also common. It might be even better, since post is used for other things in db programming.

https://en.wikipedia.org/wiki/Semaphore_%28programming%29
have you read the wiki page you posted?
Quote
Dijkstra's earliest paper on the subject gives passering (passing) as the meaning for P, and vrijgave (release) as the meaning for V.

Anyway some interesting history on the subject there so thank you for the link.


Quote
I'll have to look at your demo to better understand your intentions but as far as I can see there is nothing here that could pause a thread until an access slot is open it is left to he thread to do the actual check and pause (I think, I'll have a better understanding when I see your demo).
please enclose the code in code tags it makes it easier to read.

The blocking call is done outside the semaphore when Wait returns True. I had to do that because otherwise I got deadlock.
Create a thread and type safe TQueue descendant and move the FPermitLock from the semaphore to the Queue. that removes the need to have any lock inside the semaphore it self and now your threads will not dead lock or to keep things a bit closer to your code add the call to the RTLeventWaitFor(aEvent) after the FPermitLock.Leave call in your wait method.
« Last Edit: July 29, 2015, 03:14:07 am by taazz »
Good judgement is the result of experience … Experience is the result of bad judgement.

OS : Windows 7 64 bit
Laz: Lazarus 1.4.4 FPC 2.6.4 i386-win32-win32/win64

taazz

  • Hero Member
  • *****
  • Posts: 5365
Re: Multithreading with Semaphores
« Reply #4 on: July 29, 2015, 03:27:23 am »
Just a quick FYI, here is a lecture on semaphores in English I haven't spend the time watch thoroughly yet but in a first look it seems to address a couple of the problems you have.
https://www.youtube.com/watch?v=RaEUw107dpg
Good judgement is the result of experience … Experience is the result of bad judgement.

OS : Windows 7 64 bit
Laz: Lazarus 1.4.4 FPC 2.6.4 i386-win32-win32/win64

Pascal

  • Hero Member
  • *****
  • Posts: 876
Re: Multithreading with Semaphores
« Reply #5 on: September 08, 2016, 01:03:37 am »
@kapibara: Did you manage to update your class to work with wait only?
laz trunk - fpc trunk 32bit - Windows 10 Pro x64 (1909)

kapibara

  • Hero Member
  • *****
  • Posts: 520
Re: Multithreading with Semaphores
« Reply #6 on: September 08, 2016, 06:59:46 am »
Yes, first Tazz created a Semaphore using Critical Sections. Later, by looking at MSE-IDE source code, I fixed the "wait problem" that my class had by using InterLockedDecrement / InterLockedIncrement. Source is on another computer. If you want, I can dig it up and post it.

@kapibara: Did you manage to update your class to work with wait only?
Lazarus trunk / fpc 3.0.4 / Debian 10 - 64 bit

JD

  • Hero Member
  • *****
  • Posts: 1772
Re: Multithreading with Semaphores
« Reply #7 on: September 08, 2016, 08:19:18 am »
I'm also interested in seeing it. Thanks.
Windows (10, 7) - Lazarus 2.1/FPC 3.2, Delphi

Indy 10.6 series; mORMot; Zeos 7.3; SQLite, Firebird, PostgreSQL & MariaDB; VirtualTreeView 5.5.3 R1

Pascal

  • Hero Member
  • *****
  • Posts: 876
Re: Multithreading with Semaphores
« Reply #8 on: September 08, 2016, 09:14:46 am »
Maybe it could work like this (but didn't test it):

Code: Pascal  [Select]
  1. function TKBSemaphore.Wait(var AEvent: PRTLEvent): Boolean;
  2. var
  3.   aWait: Boolean;
  4.   aEvent: PRTLEvent;
  5. begin
  6.   FPermitLock.Enter;
  7.   if (FPermits > 0) then
  8.   begin
  9.     Dec(FPermits);
  10.     aWait:= False;
  11.   end
  12.   else
  13.   begin
  14.     aEvent:= RTLEventCreate;
  15.     FBlockQueue.Push(aEvent);
  16.     aWait:= True;
  17.   end;
  18.   FPermitLock.Leave;
  19.   if aWait then
  20.     RTLeventWaitFor(aEvent);
  21. end;
laz trunk - fpc trunk 32bit - Windows 10 Pro x64 (1909)

kapibara

  • Hero Member
  • *****
  • Posts: 520
Re: Multithreading with Semaphores
« Reply #9 on: September 09, 2016, 05:40:28 am »
@Pascal Eventually the problem was solved in another way as you see in the attached file. But thanks for the interest, I'll check your idea anyway to compare with what I first tried.

@JD Updated the demo, with the semaphore. Tested under Linux. The demo has a common "resource" that is being accessed by an array of threads. The semaphore limits the simultaneous access to the resource to the number of threads chosen.

Modern CPU's has built in support for "Interlocked" routines which are threadsafe. Because of that, not much code is needed for the semaphore itself.
« Last Edit: September 09, 2016, 05:42:38 am by kapibara »
Lazarus trunk / fpc 3.0.4 / Debian 10 - 64 bit

JD

  • Hero Member
  • *****
  • Posts: 1772
Re: Multithreading with Semaphores
« Reply #10 on: September 09, 2016, 11:48:56 am »
@kapibara

Thanks!
Windows (10, 7) - Lazarus 2.1/FPC 3.2, Delphi

Indy 10.6 series; mORMot; Zeos 7.3; SQLite, Firebird, PostgreSQL & MariaDB; VirtualTreeView 5.5.3 R1

serbod

  • Full Member
  • ***
  • Posts: 130
Re: Multithreading with Semaphores
« Reply #11 on: September 09, 2016, 01:00:20 pm »
Why not using Interlocked Variable Access functions to check permits counter instead of locking whole counter?

Thaddy

  • Hero Member
  • *****
  • Posts: 9785
Re: Multithreading with Semaphores
« Reply #12 on: September 09, 2016, 02:48:39 pm »
Why not using Interlocked Variable Access functions to check permits counter instead of locking whole counter?
If the OS supported that that is possible but you did not pay enough attention: these OS functions are basically doing the same tthing and introduce indirection.
It is maybe the task of the compiler to translate it into safe code based on the algorythm. Interlocked * will fully lock the variable and is supposed to lock the variable for writing even if it is atomic, which is not necessarily the case with counted semaphores. That goes algorithm-wise even if the CPU supports it natively.
It may be easy to confuse these with binary semaphores. And that is not the subject: this is about counted semaphores, which is definitely a specialization of semaphores in general.
« Last Edit: September 09, 2016, 02:51:20 pm by Thaddy »
I am more like donkey than shrek

kapibara

  • Hero Member
  • *****
  • Posts: 520
Re: Multithreading with Semaphores
« Reply #13 on: September 09, 2016, 09:54:07 pm »
It could be useful to also have an overloaded Wait that times out if access takes to long time.

I came up with this algorithm: If no free slot is available, call RTLeventWaitFor while measuring time, let Wait return false if it takes too much time. But is this reliable?

Code: Pascal  [Select]
  1. function TSemaphore.Wait(ATimeOut: LongInt): Boolean;
  2. var
  3.   aStartTime, aStopTime: QWord;
  4. begin
  5.   Result := True;  //
  6.   if InterLockedDecrement(FCount) < 0 then
  7.   begin
  8.     aStartTime:= GetTickCount64;
  9.     RTLeventWaitFor(FEvent, ATimeOut);
  10.     aStopTime:= GetTickCount64;
  11.     if (aStopTime - aStartTime) > ATimeOut then
  12.       Result := False;
  13.   end;
  14. end;
« Last Edit: September 10, 2016, 12:34:24 am by kapibara »
Lazarus trunk / fpc 3.0.4 / Debian 10 - 64 bit

morningdragon

  • Newbie
  • Posts: 1
Re: Multithreading with Semaphores
« Reply #14 on: March 26, 2020, 09:24:07 pm »
@kapibara


your interlock-version semaphore unit works well ,i am so excited to find it here after a long period.
pithy,valuable, thanks!