STM: Conflict Resolution Policy questions (and not only)

STM: Conflict Resolution Policy questions (and not only)

Hi -

First, thank you for releasing this prototype version.

I have some questions on the details behind your STM runtime. These might be covered in the McRT-STM (PPoPP 2006) but I don't know whether your protorype has the exact implementation as the McRT one.

  1. Is there any way to explicitly abort the transaction I am running in?
  2. Conflict Resolution Policy
  • Do you use read versioning/write locking?
  • Is it possible to give some description of the conflict resolution policy used in the prototype? If not could you please at least tell if it is the one described in the McRT-STM?
  • My guess is that a transaction may be aborted at any time due to a data conflict (according to McRT-STM). What does that mean for functions annotated with tm_waiver. Can a transaction get aborted while it is running in a tm_waiver function? Or, does the abort take place right after you return from a tm_waiver function?
  • How are POSIX user level threads mapped on the kernel level
    threads? My understanding from the McRT paper is that there is one
    kernel level thread per processor and user level threads are scheduled
    by the runtime to use the kernel level threads. If that is the case
    then what does happen if you execute a blocking system call outside a
    transaction?
  • Thanks

    6 posts / 0 new
    Last post
    For more complete information about compiler optimizations, see our Optimization Notice.

    HVolos (care to give a real name?),

    I'm not going to answer all of your questions, but I hope the following will help...

    Is there any way to explicitly abort the transaction I am running in?

    No. In the current What-If release we do notsupport explicit user abort or retry statements. Do you believe these are useful? If so please tell us, this is exatly the kind of feedback we're looking for.

    Note that they have the potential to add significant complexity to the TM model and implementation

    Conflict Resolution Policy

    • Do you use read versioning/write locking?
    • Is it possible to give some description of the conflict resolution policy used in the prototype? If not could you please at least tell if it is the one described in the McRT-STM?

    I'm going to skip these questions, since we're currently more interested in feedback on the usability and language features than on details of the implementation. Plus

    1. the implementation is extremely likely to change in future releases, so if I describe what's in the current release that will just end up being misleading.
    2. even in the current release there is more than one implementation, depending on the platform you're on...

    My guess is that a transaction may be aborted at any time due to a data conflict (according to McRT-STM). What does that mean for functions annotated with tm_waiver. Can a transaction get aborted while it is running in a tm_waiver function? Or, does the abort take place right after you return from a tm_waiver function?

    Remember that this is an STM, so conflict detection is performed by instrumentation on reads and writes. Since the point of a tm_waiver function is that it has no such instrumentation, the runtime can't detect conflicts caused by its execution (by making it tm_waiver you asserted that no such conflicts exist...).So your question is somewhat moot. While executing a tm_waiver function a transaction cannot detect (or cause) a conflict.

    The only remaining case is if another transaction detects a conflict and conflict resolution decides that thistransaction shouldretry. In that case the transaction which should retry is flagged, but the actual retry occurs when it next executes a suitable call into the TM runtime. That's the same whether or not it is executing in a tm_waiver function. (Though, as you are implicitly pointing out, it might take longer to notice that it should abort if it's off elsewhere...)

    How are POSIX user level threads mapped on the kernel level threads? My understanding from the McRT paper is that there is one kernel level thread per processor and user level threads are scheduled by the runtime to use the kernel level threads. If that is the case then what does happen if you execute a blocking system call outside a transaction?

    This is an issue for the designers of the threads package, not the STM runtime, which just uses threads. Don't confuse McRT and this runtime. They're not the same, and this runtime sits straight on top
    of the native threads for the platform...

    Is there any way to explicitly abort the transaction I am running in?

    No. In the current What-If release we do
    notsupport explicit user abort or retry statements. Do you believe
    these are useful? If so please tell us, this is exatly the kind of
    feedback we're looking for.

    Yes, at least for me the ability to abort my self would be useful. This would allow me to abort a transaction when in a higher level of abstraction the transaction is doomed and should therefore restart. However, please note, that I see the use of abort_self in non-trivial cases. For example this could be useful to wait on a conditional variable. In more general, what would be helpful is to have an interface to plun in a used defined conflict resolution policy. I understand that this requires a lot of effort.

    The only remaining case is if another transaction
    detects a conflict and conflict resolution decides that
    thistransaction shouldretry. In that case the transaction which
    should retry is flagged, but the actual retry occurs when it next
    executes a suitable call into the TM runtime. That's the same whether
    or not it is executing in a tm_waiver function. (Though, as you are
    implicitly pointing out, it might take longer to notice that it should
    abort if it's off elsewhere...)

    That's exactly what I had in mind. That a transaction only aborts when it notices the conflict which can be either on commit or at any other point where it validates its read set.

    Some more feedback: You might want to consider adding in a future release the ability to register commit and compensating actions.

    Yes, at least for me the ability to abort my self would be useful. This would allow me to abort a transaction when in a higher level of abstraction the transaction is doomed and should therefore restart. However, please note, that I see the use of abort_self in non-trivial cases. For example this could be useful to wait on a conditional variable.

    OK, so you want an abort (or fail) presumably something like this

    atomic {
    ...;
    if (...) fail;
    ...;
    } else {
    /* Executed only on failure of the atomic block */
    }

    However you said that you want to use it to achieve retry of the transaction. In that case do you also want an explicit "retry" statement which would cause the transaction nest to abort and then retry when something in the read-set had changed? That seems a simpler model for the user (if not for the implementer). (Not promising anything, just probing what you think makes sense...)

    In more general, what would be helpful is to have an interface to plun in a used defined conflict resolution policy. I understand that this requires a lot of effort.

    This is a noble aim for a research vehicle, but our hope is that we can create a TM system which makes life easier for the people who have trouble understanding locks. It seems clear that they would not be able to use such facilities. It's also not clear to me that this makes sense even for experts in an environment in which code is composed from multiple libraries potentially from different companies. If each library exploits the ability to use its own conflict resolution policy there's a serious conflict when they interact. (You're adding one more piece of shared state which has to be managed somehow).

    Some more feedback: You might want to consider adding in a future release the ability to register commit and compensating actions.
    Thanks, we're aware of that and the next What-If release will very likely support it.

    However you said that you want to use it to
    achieve retry of the transaction. In that case do you also want an
    explicit "retry" statement which would cause the transaction nest to
    abort and then retry when something in the read-set had changed? That
    seems a simpler model for the user (if not for the implementer). (Not
    promising anything, just probing what you think makes sense...)

    If you can provide these semantics for a retry then this would be great

    Also do you guys consider adding support for memory allocation inside transactions through a transactional allocator?

    This is a noble aim for a research vehicle, but
    our hope is that we can create a TM system which makes life easier for
    the people who have trouble understanding locks. It seems clear that
    they would not be able to use such facilities. It's also not clear to
    me that this makes sense even for experts in an environment in which
    code is composed from multiple libraries potentially from different
    companies. If each library exploits the ability to use its own conflict
    resolution policy there's a serious conflict when they interact.
    (You're adding one more piece of shared state which has to be managed
    somehow).

    I undestand your argument. However, I think that since conflict resolution is more of a policy then there should be a way to implement policies. Otherwise how can you predict that one policy fits all. I agree that there have been resolution polices that seem to work well but no one tried real workloads yet. And when I say real workloads I mean web servers, databases, etc. No one knows whether existing policies will work well with such workloads and therefore the flexibility of implementing the policy would be a benefit. Of course such workloads are currently intractable with TM for other reasons.

    Also do you guys consider adding support for memory allocation inside transactions through a transactional allocator?

    Yes. This isintended to be in the next What-If release (in a transparent form, so you can just use malloc, free, etc inside a transaction and "the right thing" will happen).

    Login to leave a comment.