in reply to Re: A faster?, safer, user transparent, shared variable "locking" mechanism.
in thread A faster?, safer, user transparent, shared variable "locking" mechanism.

Critical sections only affect a single process.

Threads not attempting enter the critical section are not blocked.

Only threads of the same process will ever be blocked, then only if they try to enter the same critical section as has already been acquired by another thread (from the same process), running concurrently on another cpu, as no other thread can run on this cpu until the critical section is exited.

Blocking preemption of a thread sounds like it could have a noticeable effect on other processes within the system, but, at worst--ie. if the thread entered the critical section just before it was about to be preempted--, it would only be extending that threads timeslice for a few 100 or so clock cycles.

On average, the critical section would be entered at the beginning, or in the middle of the timeslice, and possible several times, rather than at the end, and the minuscule extension to the timeslice when it did occur at the end would be negligible.

Swapping to use a PAGE_GUARD/STATUS_GUARD_PAGE exception, rather than PAGE_READONLY/ACCESS_VIOLATION would allow both reads and writes to the shared variables to trigger, and also remove one step from the 8 I listed, as the PAGE_GUARD Attribute is cleared automatically.

The structured exception mechanism is on a per thread basis. Naively, similar to throw/catch.

I see no reason why any privilege changes would occur?

It would work on multi-core/processor systems (if it worked at all!).

Now the $a = $a + 1; scenario (and all the other like it. The opcodes (perl5) representing that operation look like

BINOP (0x191da14) sassign BINOP (0x191da38) add [3] UNOP (0x191da7c) null [15] PADOP (0x191da9c) gvsv GV (0x1824348) *a SVOP (0x191da5c) const [4] IV (0x22509c) 1 UNOP (0x191dabc) null [15] PADOP (0x191dadc) gvsv GV (0x1824348) *a

If the critical section (they cost almost nothing (no transfer to kernel mode) to enter if they are unentered by other threads of the same process) are entered at the appropriate point in the opcode tree, in the above case, the sassign, then all the descendant opcodes are also completed within the auspices of the critical section, and so both gvsvs on *a are atomic.

The exception handling mechanism (~throw) would be wrapped around each (mutating) opcode, and the handler (catch) would be specific to that opcode. Normal operations on non-shared variables never throw the exception so cost nothing extra.

The critical section would be entered through the catch code, only when exceptions occurs.

This implies that effectively all accesses to all shared data are serialised across all threads within the process. However, since each critical section will aways be entered and exited within a single (possible marginally extended) timeslice, the longest any thread would have to wait to enter a critical section is 1 timeslice * the number of threads in the process. This longest delay(*) would only occur if all threads, all tried to do a mutating opcode on shared data, on a separate processor, concurrently. The average case would be much, much less.

Does it go anywhere?

(*) The longest wait calculation is not strictly correct. Threads are non-deterministic, therefore there is no guarentee that a thread blocked waiting for entry to a critical section, would receive that entry before another thread that had previously also be waiting, and having already received a timeslice, managed to reeneter the wait state and again be selected.

But this is true for all wait states and in practice does not cause a thread to be starved of cpu over the long term (1 or 2 seconds). Besides which, many if not all OSs have mechanism that temporarially, for one timeslice, boosts the priority of a thread that isn't getting cpu, causing it to get preferential selection on the next round robin.

Also, other processes threads are more likely to be selected than another thread from this process. This is the norm. The time spent in the trheads of other processes (on other cpus as this one is prevented from being preempted if its in a critical section), count to reduce the likelyhood that another thread from this process will be able to run concurrently on that other cpu, and so it serves to reduce the likelyhood that another thread will be blocked from running by this thread holding the critical section.

This stuff is all pretty well tuned, so ignoring the effects of the non-determinism in such calculations is the norm. Over time, the randomness cancels out and the average situation prevails.


Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal?
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.

Replies are listed 'Best First'.
Re^3: A faster?, safer, user transparent, shared variable "locking" mechanism.
by ikegami (Patriarch) on Oct 26, 2006 at 10:32 UTC

    Ah, you mean to hold the lock for all the child opcodes as well. In that case, the Anonymous Monk already answered

    • Sometimes the scope of the CS is too big.

      $shared .= <PIPE>;

      would need to be written as

      my $local = <PIPE>; $shared .= $local;
    • Sometimes the scope is too small.

      # XXX. The key and value are related. my $string = $shared_key . ' => ' . $shared_value;

      won't work without explicit locking.

    As you can see, the user still needs to be fully aware of the locking mechanism and must sometimes compensate for it. The only thing accomplished is the removal of the visual cues that something special is happening.

    And that's assuming you can figure out where to end the critical section. Consider the following:

    • $shared = $shared + 1;
    • $local = $shared + 1;
    • my $ref = \$shared;
      $$ref = $shared + 1;

      Sometimes the scope of the CS is too big.

      $shared .= <PIPE>;
      would need to be written as
      my $local = <PIPE>; $shared .= $local;

      It should be written that way, even with explicit locking. Else, you are blocking access to $shared for much longer than necessary.

      my $local = <PIPE>; { lock( $shared ); $shared = $local; }

      Is far better than

      { lock( $shared ); my $local = <PIPE>; $shared = $local; }

      That's a 'threading best practices' optimisation.

      Sometimes the scope is too small.
      # XXX. The key and value are related. my $string = $shared_key . ' => ' . $shared_value;

      won't work without explicit locking.

      Actually, I think it would.

      C:\test>perl -MO=Terse my $string = $shared_key . ' => ' . $shared_value; ^Z LISTOP (0x191d964) leave [1] OP (0x191d948) enter COP (0x191d988) nextstate ## exception handler installed here! BINOP (0x191d9c4) sassign ## exception handler entered here and the entire subtree retried < +<<------+ ## critical section entered here (on second attempt) + | BINOP (0x191d9e8) concat [5] + | BINOP (0x191da4c) concat [3] + | UNOP (0x191da90) null [15] + | PADOP (0x191dab0) gvsv GV (0x182435c) *shared_key + | ## Exception triggered here by the access to share +d data.-+ SVOP (0x191da70) const [6] PV (0x1824374) " => " UNOP (0x191da0c) null [15] PADOP (0x191da2c) gvsv GV (0x18243b0) *shared_value OP (0x191dad0) padsv [1] ## critical section exited here. - syntax OK
      Consider the following:

      Each of the following lines would be self contained branches of the opcode tree.

      • $shared = $shared + 1;

        This is the case I addressed above.

      • $local = $shared + 1;

        This is a readonly reference to the shared variable (in user land, though it may entail writes in perl land if $shared need promotion to an IV or NV).

        $local takes no further part in this snippet.

        I don't see how, on the basis of this snippet, this line has any affect upon the rest of them?

      • my $ref = \$shared;

        This doesn't touch the shared data at all.

      • $$ref = $shared + 1;

        After the dereference of $ref, this is the same as the first line.

      Maybe that's just a poor example of what you are getting at.

      I think the point you are trying to make is better illustrated by

      { lock( $shared ) $local = $shared; $shared = somefunction( $local ); }

      Without the lock(), by the time $shared is assigned to, its value may have changed. This is true. So don't do that. Do

      $shared = somefunction( $shared );

      gives

      C:\test>perl -MO=Terse sub somefunction{ $_[0] + 1 } $shared = somefunction( $shared ); ^Z LISTOP (0x191d7e0) leave [1] OP (0x191d7c4) enter COP (0x191d804) nextstate ## install exception handler here BINOP (0x191d840) sassign ## Exception handler catches here <<<<---------------------------^ ## Critical section entered here at second attempt UNOP (0x191d864) entersub [4] UNOP (0x191d8a0) null [141] OP (0x191d884) pushmark UNOP (0x191d8c4) null [15] PADOP (0x191d8e4) gvsv GV (0x22507c) *shared ## Exception raised here-------------------------- +-^ UNOP (0x191d904) null [17] PADOP (0x191d924) gv GV (0x225088) *somefunction UNOP (0x191d944) null [15] PADOP (0x191d964) gvsv GV (0x22507c) *shared ## ExitCriticalSection here. - syntax OK

      But, there's the rub. somefunction() may legitimately take a long time, and the requirements may legitimately state that $shared cannot be accesses by other threads until it returns. And spending more than a few milliseconds in a critical section is absolutely bad.

      It easy to see how to use declarative tagging of shared variables to caused multiple CSs to be used, thereby avoiding the "all access to all shared data is serialised" problem. But still, the problem of limiting the time spent within any given CS remains.

      Various possibilities come to mind, for switching the CS for a semaphore transparently when certain opcodes, like entersub, are encountered within a critical section, but suddenly the simplicity of the mechanism goes away.

      Oh well. Just a random thought.


      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal?
      "Science is about questioning the status quo. Questioning authority".
      In the absence of evidence, opinion is indistinguishable from prejudice.