I am getting started with threads (linux/cthreads) and I'm very happy so far, but unsure of the best way to tackle my situation.

I have a program that needs to perform about 10,000 independent tasks, which usually involve waiting for I/O; thus it makes sense to use several threads so that some waiting can be done in parallel. I thought I'd try it with 10 threads.

When a thread completes its task, I'd like it to simply request a new task from the queue. The best way I could think to do this was to have a task assignment function (which accesses a global variable and returns a task id, marking it as pending.)

But how can I prevent race conditions? If threads X and Y happen to call the task assignment function at the same time, it seems to me that they could both be assigned to the same task. I know that this is a problem which has been addressed at great length in the computer science world ... so what's the easiest way for me to address it here and now?

While writing this message it dawned on me that I probably need an event loop (I'm writing a console app) which will, e.g., sleep for 1 second and then check on the status of each thread's work. Then the main loop can assign a new task by starting a new thread, whenever it finds one that is finished. That puts the assignment task back in the main loop where there is no race condition.

Do I even need to send this message? It would be nice to get a little input and see if I'm on the right track :)

Cheers,
David

Nice to see you posted this. Love, Dad

I apologize for accidentally posting a personal note to this list.

But how can I prevent race conditions? If threads X and Y happen to call the task assignment function at the same time, it seems to me that they could both be assigned to the same task.

Use for example the cross-platform implementations of Enter/LeaveCriticalSection. Like this:

EnterCriticalSection(MyCritVar);
try
  DoStuff
finally
  LeaveCriticalSection(MyCritVar);
end;

Then the main loop can assign a new task by starting a new thread, whenever it finds one > that is finished.

Also possible but not easier. Threads should not be started or stopped for each task, instead they should wait for an event telling them to continue with the next task. For example using SetEvent / ResetEvent as well as:

{$ifdef win32}
WaitForSingleObject(ContinueEvent,INFINITE);
{$else}
RTLEventWaitFor(ContinueEvent);
{$endif}

Cheers,
Tobias

En/na Tobias Giesen ha escrit:

There are some cross-platform synchronization classes in syncobjs

http://www.freepascal.org/docs-html/fcl/syncobjs/index.html

Bye

Maybe you can use MTProcs unit: http://wiki.lazarus.freepascal.org/Parallel_procedures

You don't need to worry about assigning tasks anymore.

Vincent

Luca Olivetti het geskryf:

There are some cross-platform synchronization classes in syncobjs http://www.freepascal.org/docs-html/fcl/syncobjs/index.html

And I'm working on cross-platform semaphore classes / methods because the current ones in FPC are totally useless.

Regards,
- Graeme -

Graeme Geldenhuys wrote

And I'm working on cross-platform semaphore classes / methods because the current ones in FPC are totally useless.

I guess you mean that there aren't any :)

Jonas

Jonas Maebe het geskryf:

I guess you mean that there aren't any :)

True and False. :) It was recommended to me that I use the methods directly from the thread manager, then later it was not recommended. Plus the methods available from the thread manager doesn't support initial max values for semaphores.

End result - totally useless. :)

Regards,
- Graeme -

Hope you find a good cross platform solution :)

It's because there is no cross-platform guarantee for any of the thread manager routines (i.c., the semaphore ones are only implemented for Unix platforms).

Jonas

just a question:

Should semaphores be on the thread manager?

because imho they are not realy thread related? They can be used by threads, but they have lot's of other uses. Even communication between processes of different applications. They are usually grouped together with other IPC like msg-queues and shared-mem.

my 2 cent

Martin

These are unrelated things. As mentioned before, the thread manager is not for public use, so whether or not it has hooks for semaphores is irrelevant w.r.t. what semaphores could theoretically be used for.

Jonas

Florian Klaempfl het geskryf:

Hope you find a good cross platform solution :)

So far I have single interface for create/destroy/lock/unlock of semaphores for Windows, Linux, *BSD. The latter two is actually for all unix with posix systems. So no more IFDEF's and specific uses clauses units in my higher level code.

I only have access to the platforms I mentioned above. Other developers with access to other platforms can implement the remaining implementations, or raise an exception if no implementation exists - to warn the end-user developer.

Regards,
- Graeme -

David Emerson pisze:

You need FIFO queue for multiple consumer. Each task can be assigned to them.
You can use ordinal tThreadList but it rather slow.

I use own lockfree FIFO http://www.emadar.com/fpc/lockfree.htm to distribute task between threads
its much faster and well scaling on multicore.

Dariusz Mazur wrote

I use own lockfree FIFO http://www.emadar.com/fpc/lockfree.htm to distribute task between threads its much faster and well scaling on multicore.

Note that it won't work as is on non-x86 machines, because it's missing memory barriers (and I think that you may actually need memory barriers on x86 too). Atomic operations are not memory barriers by themselves, and the fact that you perform an atomic operation does not mean that afterwards all cpu's will immediately see this new value.

Jonas

On x86 they are.

Jonas Maebe pisze:

I don't know other machines. On x86 used atomic operation, as Intel said, all needed cache are resolved.
I've made very stress test on several computers. it works good. Algorithm is very simple, need only 32bit CAS, thus implement it is possible on most platforms.
One thing is needed: multiplatform threadswich.

I use sleep(0) ,but its not best solution (I think).

At least on PowerPC it will fail (and I guess on SPARC as well).

At least on Mac OS X that will not do anything. There's a procedure called "ThreadSwitch" in the interface of the system unit though. At least for Unix platforms it will work if cthreads is used.

Jonas

Jonas Maebe pisze:

I don't say, that this will work on other than x86. I only test on Intel and AMD.

I sow it, but not test.
Seems enough to me.

But is this optimal solution:

procedure SysThreadSwitch;
begin
       Sleep(0);
end;
    WinThreadManager.ThreadSwitch           ;
procedure ThreadSwitch;
begin
  CurrentTM.ThreadSwitch;
end;

We have 2 unnecessary invoke function. Can compiler optimize this? Or maybe better do ThreadSwitch and SysThreadSwitch inlined.

SysThreadSwitch cannot be inlined, because it's called as a procvar. And since you are doing a context switch anyway, the additional overhead of a direct and an indirect call is negligible.

Jonas

-----Original message-----

Helmut Hartl pisze:

Its save about ABA problem, only it atomic operation are true atomic. I try to test both: theoretical and in real. But if You know sequence, that things may go wrong, pleas tell it.

64bit CAS is absent on many platforms, and is slower but I'd like too see Your implementation

thx for links

Graeme Geldenhuys wrote

So far I have single interface for create/destroy/lock/unlock of semaphores for Windows, Linux, *BSD. The latter two is actually for all

A semaphore is not "locked" and "unlocked", it is posted and waited for.

Micha

Jonas Maebe wrote

on x86 too). Atomic operations are not memory barriers by themselves, and the fact that you perform an atomic operation does not mean that afterwards all cpu's will immediately see this new value.

Explain? Isn't the point of an atomic update that it doesn't matter whether the other CPU has seen the value yet? Or are we talking about different values?

Micha

Yes, sorry for being unclear. One problem is that unless all of the data to which the queue elements point is also only loaded/stored using atomic operations, it is possible that the popping cpu will see different values than those intended the pushing cpu (because their caches may not yet have been syncronised). So at least for the pop you need a full memory barrier. There are probably more issues. Here's a page with several different atomic queue implementations for ppc, and all of them contain some form of barrier: http://www.cocoadev.com/index.pl?AtomicSQ

Jonas

2009/9/19 Micha Nelissen :

A semaphore is not "locked" and "unlocked", it is posted and waited for.

True, and to let it make even more sense (technically correct) one might have to use method names like deccount() / inccount() or grabitem() / releaseitem() etc etc...

Either way, internal implementation calls the correct post- and wait- API's of each platform.

Regards,
- Graeme -

_______________________________________________
fpGUI - a cross-platform Free Pascal GUI toolkit
http://opensoft.homeip.net/fpgui/

On Sat, 19 Sep 2009 10:25:20 +0200, Micha Nelissen wrote about Re: [fpc-pascal] Re: getting started with threads:

An event semaphore (or "condition" in POSIX-speak) is "waited for" and "posted".

A simple mutex semaphore is "locked" and "unlocked" -- or, more idiomatically, "acquired" and "released".

A read/write mutex semaphore (or "rwlock" in POSIX-speak) is "acquired for sharing" or "acquired for exclusion" and "released".

A Dijkstra semaphore is "upped" or "downed". This is the original usage of the term "semaphore" in computing. It is largely useless in comparison to the other types of semaphore.

In our previous episode, Jonas Maebe said:

Afaik memory barriers (s/lfence etc) are only needed for I/O mapped memory on x86.

But if you look at the MSDN help for interlocked* functions, you'll seean additional requirement that the arguments are 4-byte aligned. (which might be a requirement of the lock prefix).