Re: Lock Free -- where to start


"chris noonan" <usenet@xxxxxxxxxxxxxx> wrote in message
news:1128628483.149398.195550@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

> David Schwartz wrote:

>> > If locks are efficient, why does the technique called I/O Completion
>> > Port exist?

>> I don't understand what one has to do with the other. IOCP is about
>> optimizing the number of concurrent threads without the risk of thread
>> starvation.

> But you are assuming that the optimum number of concurrent threads
> is one per processor! (OK, I know IOCP sometimes schedules more).
> That is only true if the performance of a large number of threads
> would be destroyed by locks.
> (I will have more to say on the IOCP fraud in a separate topic.)

The optimum number of concurrent threads is one per processor if the
threads are CPU bound. I still don't understand what you think the
connection between IOCP and lock efficiency is. Maybe it's obvious to you,
but I don't see it. I'm genuinely curious.

>> > Now introduce a lock, contended for by the threads,
>> > such that the lock is held for 1% of a thread's
>> > running time. Every hundredth timeslice, a thread
>> > is switched out when it is holding the lock. During
>> > the subsequent 20ms timeslice, all the other threads
>> > run up against the lock, leading to 999 context
>> > switches before the original thread gets the processor
>> > again. Accordingly, every hundred timeslices there are
>> > 1099 switches instead of 100, an eleven-fold increase.
>> > That *is* going to sap performance.

>> Umm, no. Some thread will get the lock and unless the thread library
>> is
>> poorly designed, it will be allowed to do useful work at full speed
>> without
>> context switches. If other threads want the lock, they'll have to wait.

> I am sure you are missing the point. Read the analysis again.
> It is bound to happen that occasionally a thread switch (caused
> asynchronously by a timer interrupt) will deschedule a thread
> in the middle of some critical section thingy. No other thread
> (in a homogeneous collection of threads running the same code path)
> can thereafter get significant work done UNTIL the original thread
> leaves the critical section. The scheduling algorithm in Windows NT
> (for example) ensures that is not before 999 further switches have
> been incurred. What operating system is it that allows a thread
> to run indefinitely?

Again, you need the assumption that the system can get *no* useful work
done at all without this lock. You also need a very improbable interruption
inside a very small piece of code. You also need the thread to use up its
entire timeslice (which means it just did a *lot* of useful work at absolute
top speed).

In any event, if you don't have 1000 CPUs, it's pretty dumb for you to
have 1000 ready-to-run threads. If you do have 1000 CPUs, it's really just
the time it takes to do *one* context switch.

DS


.

Relevant Pages

  • Re: Lock Free -- where to start
    ... I know IOCP sometimes schedules more). ... >> Now introduce a lock, contended for by the threads, ... Every hundredth timeslice, a thread ... >> switches before the original thread gets the processor ...
    (comp.programming.threads)
  • Re: Tech: Whirlwind target bug-like oddity
    ... the game only spots a compass target if you do ... must be completed to light Lock... ... shows what I'd expect - 3 trough switches and ramp down. ...
    (rec.games.pinball)
  • Lock convoys
    ... context switches the system suffers eleven-fold. ... "Every time a thread is caught holding the lock at the expiry of ... its scheduling quantum, the following bad things happen ..." ... (before taking into account the cost of the switches ...
    (comp.programming.threads)
  • Re: Lock convoys
    ... context switches the system suffers eleven-fold. ... "Every time a thread is caught holding the lock at the expiry of ... its scheduling quantum, the following bad things happen ..." ... thread/process that accepts messages from clients. ...
    (comp.programming.threads)
  • Re: Lock convoys
    ... context switches the system suffers eleven-fold. ... "Every time a thread is caught holding the lock at the expiry of ... its scheduling quantum, the following bad things happen ..." ... suspend/resume overhead as long as the contention is not constant. ...
    (comp.programming.threads)