From: <don...@is...> - 2009-02-21 20:08:48
|
It appears to me that after a thread finishes it remains un GC'd until it is killed. Is there some reason threads don't get killed automatically when they complete? Also it seems odd that (list-threads) returns threads that can be GC'd. What does thread-active-p mean? Just that it's not finished? I had expected that while waiting for a lock it would be false, but it seems to be true. For that matter it would be nice if the whostate were set to "waiting for <mutex-name>" while waiting for it. This would perhaps be easier if mutex-name were defined. Can you give me some idea how to use thread-wait? Also what it does? In old 1-cpu lisps there was a process-wait, which must be quite a bit different from thread-wait. I'm guessing thread-wait does something like (loop until (funcall wait-function)(thread-yield)) where thread-yield just allows other threads to run, and that this is just executed in the thread that calls thread-wait. Or maybe it includes a small sleep so as to not actually busy wait when there's nothing else to do. But there seems to be at least one more argument than I expect with process-wait. Note that process-wait ran the wait predicate "in the scheduler" where it was effectively run without-interrupts, and therefore when process-wait returned, nothing had changed from the state where the predicate had just returned true. I gather there's no notion of thread priority. Man pthreads seems to have something about scheduling policy and priority. What are exemptions about? I notice there's nothing about suspending/resuming threads. I guess it should be pretty easy to simulate with thread-interrupt. I tried (thread-interrupt t1 (lambda()(catch 'resume (break "waiting to resume")))) which was pretty close to what I wanted, other than the fact that the console is then shared by two threads and you can't tell which is going to get the input you type. I think there used to be a solution to this problem in which the debugger was connected to a separate input stream for each process and each such stream was connected to a separate emacs buffer. If you're going to support a whostate, then how about also (with-whostate state . forms) Although it seems a bit odd to support whostate when it seems nothing more than a special variable. Or did you have in mind something else? In any case, for now you could define it as (let ((*thread-whostate* state)) . forms) |
From: Vladimir T. <vtz...@gm...> - 2009-02-21 20:52:28
|
On Sat, 21 Feb 2009 22:08:52 +0200, Don Cohen <don...@is...> wrote: > > It appears to me that after a thread finishes it remains un GC'd until > it is killed. Is there some reason threads don't get killed > automatically when they complete? > Also it seems odd that (list-threads) returns threads that can be GC'd. After thread finishes it's lisp record will be colleted on next GC if there are no references to it. list-threads return all threads that are not GC-ed (obviously all active + finished with references to them + some (if any) finished without references to them that will be collected on next GC). > What does thread-active-p mean? Just that it's not finished? T means the thread is running, NIL - it has exitted. "running" means not exitted (it can be blocked in some system call). > I had expected that while waiting for a lock it would be false, but > it seems to be true. For that matter it would be nice if the whostate > were set to "waiting for <mutex-name>" while waiting for it. This > would perhaps be easier if mutex-name were defined. thread-whostate is left to the user. Depending on the problem you solve - you better know what is your state. > Can you give me some idea how to use thread-wait? Also what it does? It's not implemented and I am not sure that it will be. If somebody needs - he can be easily implemented it. Polling over some predicate is not good idea with preemptive threads. There was discussion about this here: http://thread.gmane.org/gmane.lisp.clisp.general/12781. both thread-state and thread-wait are not good if you do not have control over threads scheduler. > > I gather there's no notion of thread priority. > Man pthreads seems to have something about scheduling policy and > priority. Yes there is no way to set thread priority. Should be added. > > What are exemptions about? These are POSIX condition variables. Since in lisp "condition" means something different - Sam/Bruno in the past have chosen this name. > > I notice there's nothing about suspending/resuming threads. > I guess it should be pretty easy to simulate with thread-interrupt. > I tried > (thread-interrupt t1 (lambda()(catch 'resume (break "waiting to resume")))) > which was pretty close to what I wanted, other than the fact that the > console is then shared by two threads and you can't tell which is > going to get the input you type. I think there used to be a solution > to this problem in which the debugger was connected to a separate > input stream for each process and each such stream was connected to a > separate emacs buffer. suspend/resume of threads is not good and as you note - it can be easily implemented/simulated via thread-interrupt. even with some mutex it will be better: (thread-interrupt thr #'mutex-lock some-already-locked-by-me-mutex) Every thread can bind any special variable - including standard streams (from thread's function or via :initial-bindings). When the console streams are shared (default) - nothing good can be expected (as you noticed). > > If you're going to support a whostate, then how about also > (with-whostate state . forms) > Although it seems a bit odd to support whostate when it seems nothing > more than a special variable. Or did you have in mind something else? > In any case, for now you could define it as > (let ((*thread-whostate* state)) . forms) > I am not sure it is supposed to be part of the threads package at all - since everybody can easily implement it as he wants and it's problem specific. With many problems "state" means more than just where the control is at the moment. |
From: <don...@is...> - 2009-02-22 02:50:37
|
Vladimir Tzankov writes: > After thread finishes it's lisp record will be colleted on next GC > if there are no references to it. list-threads return all threads > that are not GC-ed (obviously all active + finished with references > to them + some (if any) finished without references to them that > will be collected on next GC). Is there anything that can be done with a finished thread? If not it seems useless for (list-threads) to return finished threads, and for that matter thread-active-p doesn't seem all that useful (though if you wanted it then you could test for membership in list-threads). > > Can you give me some idea how to use thread-wait? Also what it does? > It's not implemented and I am not sure that it will be. If somebody > needs - he can be easily implemented it. That depends what it's supposed to do. If my guess was right on that subject then I agree. > Polling over some predicate is not good idea with preemptive threads. What is a good way to wait for some condition? Suppose that when that condition arises the code that causes it will recognize it and can do something to cause the wait to end. This is what I'd like to use suspend and resume for. Is waiting for input a good (i.e., non-busy) implementation for suspend? Perhaps this is what exemptions are supposed to be used for. So far I don't have any idea how to use them. My immediate objective is to implement with-read/write-access, where - only one thread at a time can have write access - any number can have read access at a time - it is not permitted for one thread to have read access and another to have write access at the same time. Let me know if you have suggestions. I think I see how to do it with thread-wait (the definition I sent before) and maybe even with my input wait suspend. > both thread-state and thread-wait are not good if you do not have > control over threads scheduler. I don't see what control over the scheduler has to do with it. Thread-wait seems to make sense if you're willing to busy wait, which might be more reasonable if you include a sleep in the loop. At the moment I don't see what thread-state is, but if it's written only by the thread in question then it makes sense for that thread to read it. |
From: Vladimir T. <vtz...@gm...> - 2009-02-22 14:16:29
|
On Sun, 22 Feb 2009 04:50:35 +0200, Don Cohen <don...@is...> wrote: > Vladimir Tzankov writes: > > > After thread finishes it's lisp record will be colleted on next GC > > if there are no references to it. list-threads return all threads > > that are not GC-ed (obviously all active + finished with references > > to them + some (if any) finished without references to them that > > will be collected on next GC). > Is there anything that can be done with a finished thread? > If not it seems useless for (list-threads) to return finished threads, > and for that matter thread-active-p doesn't seem all that useful > (though if you wanted it then you could test for membership in > list-threads). The only thing that can be done with finished thread is to inspect the special variables bindings established by :inital-bindings (since at thread termination the stack is unwound). This may help sometimes with debugging (examining termination reasons). The runtime keeps list of all running threads - regardless whether there are references to them. For example somebody may create following thread: (make-thread #'some-background-task) and do not keep any reference to it. This thread is added to the global list and returned by list-thread (at least to be able to kill it). Also even that there are no references to it - the GC should not collect it until it runs. If the thread finishes - in order to remove it from the list of all threads - we will have to scan whether there are refernces to it. This is expensive operation and anyway is performed during GC. So on thread termination - I do not try to remove it from list of all threads. We leave this task to the GC. That's the reason to have thread-active-p as well - to be able to distinguish between alive and terminated threads. > > My immediate objective is to implement with-read/write-access, where > - only one thread at a time can have write access > - any number can have read access at a time > - it is not permitted for one thread to have read access and another > to have write access at the same time. > Let me know if you have suggestions. > I think I see how to do it with thread-wait (the definition > I sent before) and maybe even with my input wait suspend. > This is stadnadrd read/write lock. While they are part of recent POSIX standards - not all pthreads implementation have them. That's the reason they are absent. It can be implemented via the mutex and exemptions that are available. Something like (barely tested and not refined): (defstruct rwlock (lock (make-mutex :name "rwlock-mutex")) (r-exemption (make-exemption :name "reader-exemption")) (w-exemption (make-exemption :name "writer-exemption")) (active-readers 0) ;; active readers (active-writer nil) ;; is there write in progress (waiting-readers 0) ;; number of waiting readers (waiting-writers 0)) ;; number of waiting writers (defun rwlock-read-lock (rwlock) (with-lock ((rwlock-lock rwlock)) (when (rwlock-active-writer rwlock) ; write in progress (incf (rwlock-waiting-readers rwlock)) (exemption-wait (rwlock-r-exemption rwlock) (rwlock-lock rwlock)) (decf (rwlock-waiting-readers rwlock))) (incf (rwlock-active-readers rwlock)))) (defun rwlock-read-unlock (rwlock) (with-lock ((rwlock-lock rwlock)) (when (and (zerop (decf (rwlock-active-readers rwlock))) ;; no more readers (plusp (rwlock-waiting-writers rwlock))) ;; have waiting writers (exemption-signal (rwlock-w-exemption rwlock))))) (defun rwlock-write-lock (rwlock) (with-lock ((rwlock-lock rwlock)) (when (or (rwlock-active-writer rwlock) (plusp (rwlock-active-readers rwlock))) ; write or reads in progress (incf (rwlock-waiting-writers rwlock)) (exemption-wait (rwlock-w-exemption rwlock) (rwlock-lock rwlock)) (decf (rwlock-waiting-writers rwlock))) (setf (rwlock-active-writer rwlock) t))) (defun rwlock-write-unlock (rwlock) (with-lock ((rwlock-lock rwlock)) (setf (rwlock-active-writer rwlock) nil) ;; no more active writer (cond ((plusp (rwlock-waiting-readers rwlock)) (exemption-broadcast (rwlock-r-exemption rwlock))) ((plusp (rwlock-waiting-writers rwlock)) (exemption-signal (rwlock-w-exemption rwlock)))))) Of course with-rwlock-read and with-rwlock-write can be defined as well. > > both thread-state and thread-wait are not good if you do not have > > control over threads scheduler. > I don't see what control over the scheduler has to do with it. > Thread-wait seems to make sense if you're willing to busy wait, > which might be more reasonable if you include a sleep in the loop. See: http://gbbopen.org/hyperdoc/ref-portable-thread-entities.html - "What about Process Wait?" > At the moment I don't see what thread-state is, but if it's written > only by the thread in question then it makes sense for that thread to > read it. Whatever thread-state returns - until you process it in meaningful way - it may change. Will remove both of them (anyway they are not implemented). Any objections? Vladimir |
From: <don...@is...> - 2009-02-22 22:41:47
|
Vladimir Tzankov writes: > The reason finished threads are included in the list is that there > are references to them and/or you may be interested why some of I see no reason for the implementation related to list-threads to keep such references. If the programmer wants to keep other references that seems to present no problem. The argument that it could be useful for debugging applies just as well to all other objects that are subject to GC, but we don't generally expect to be able to find them. For that matter it could be useful for objects that have already been GC'd. > > My view is that it has nothing to do with the scheduler. > > I think process-wait was (is) a reasonable thing in single cpu > > machines. > Even with single CPU it is not good at all. thread-wait with some > predicate does not assure anything. I disagree. > The OS thread scheduler may preempt the predicate at the middle or > after it has returned T but before thread-wait returns. The next This is not true. The process-wait predicate was executed in the scheduler (meaning that no process other than the scheduler was running or was going to be able to until the scheduler resumed another process). When it returned true the scheduler would then resume the process that was ready. I think that process was even guaranteed a quantum of run time. If there were some critical operation that had to be done before any other process ran and you were worried about being interrupted before it was done, you could put it in the wait function. > scheduled thread may change the whole program state in such a way > that predicate is NIL. This will not lead to anything good. This is another matter. In general one expects that a program is designed to have parts that cooperate in order to achieve various ends and this involves maintaining certain relationships. An example is the fact that certain data is only to be written while holding a certain lock. You have to design your program so that these relationships will be maintained and such that they imply the other higher level goals of the program will be satisfied. The job of the programming language is just to make it possible (even better, convenient) to do so. > without-interrupts does not enforce no preemption with native OS > threads. It enforces the form to be executed entirely (what we > discuss about unwind-protect cleanup forms) but it can be preempted > meanwhile. You're now talking about the proposed version of without-interrupts in clisp that is not yet implemented. This, of course, has very different semantics from the function of the same name on lisp machine or other 1-cpu machines (I think even including mt clisp on a 1-cpu machine?). Perhaps we should use a different name. > Of course it is possible to provide something like > without-other-threads-running but this is the worst kind of > synchronization possible. It is expensive and will not scale. This is what I assumed as-atomic-operation did. You didn't answer my question of how expensive it is. (Or how it works.) > > I notice in particular that it contains something called > > as-atomic-operation, which I gather (let me know if I'm wrong about > > this) has the semantics described above -- nothing else can be going > > on at the same time. > > Please check also the comments in: > http://gbbopen.org/svn/GBBopen/trunk/source/tools/portable-threads.lisp > about ClozureCL and as-atomic-operation (CCL also uses native OS threads). I don't understand this. First, my understanding is that #+allegro without-scheduling and similar does not guarantee that no other lisp threads are running. And second, if I change my guess about what the meaning of as-atomic-operation is to be the same as (what I believe is meant by) without-scheduling, that seems completely different from the meaning of (with-lock-held ...) -- which also differs from what I expected as-atomic-operation to do. > > (BTW, another project I'd love to see is GC implemented as thread(s) > > running in parallel with non-gc threads.) > Me too. It seems the marking phase can be parallelised. However not > sure whether there will be significant increase in performance. I meant more than using multiple threads to gc. I meant that non-gc lisp threads would run at the same time. (I thought this was called something like "on line" GC ?) > > > Whatever thread-state returns - until you process it in meaningful > > > way - it may change. > > Is thread-state supposed to be related to who-state in some way? > No. I did not find good fit/implementation for both of > them. Whoever wants something like whostate - can easily implement > it. thread-state is not adequate when you can be preempted at any > time. I don't recall ever hearing about thread-state before, and without knowing more about what it's supposed to mean, I have no opinions on it. Whostate does seem to be implemented as a special variable, for whatever that's worth. In case you don't know, the wholine was a UI feature of the lisp machine. It told you what the machine was doing (along with a few other similar features to show when it was paging, and I think also GC). With-whostate changed this display. |
From: <don...@is...> - 2009-02-22 17:16:22
|
Vladimir Tzankov writes: > If the thread finishes - in order to remove it from the list of all > threads - we will have to scan whether there are refernces to > it. This is expensive operation and anyway is performed during GC. Clearly something internally does not work as I expect. To me the obvious solution was that - make-thread would add the new thread to the list read by list-threads - finishing a thread would remove it from that list > This is stadnadrd read/write lock. While they are part of recent > POSIX standards - not all pthreads implementation have them. That's > the reason they are absent. Sounds like it might be worth including in the mt package. > It can be implemented via the mutex and exemptions that are > available. Something like (barely tested and not refined): As I expected, exemption documentation would have been helpful. I look forward to seeing that. (It's interesting that I found (I think) an alternative implementation, which I suspect could actually be used as to implement exemptions within lisp.) Thanks. I'll try it out and see if I can deduce how exemptions work. > > > both thread-state and thread-wait are not good if you do not have > > > control over threads scheduler. > > I don't see what control over the scheduler has to do with it. > > Thread-wait seems to make sense if you're willing to busy wait, > > which might be more reasonable if you include a sleep in the loop. > See: http://gbbopen.org/hyperdoc/ref-portable-thread-entities.html - > "What about Process Wait?" I find the whole page to be very interesting - I was not aware it existed. However I don't see that it answers the question of what any of this has to do with control over the scheduler. My view is that it has nothing to do with the scheduler. I think process-wait was (is) a reasonable thing in single cpu machines. There you know that when you are in the scheduler deciding which process to run next, no other process could be running. In the lisp machine, which as far as I know was the first place this appeared, if the scheduler didn't find anything to do then the machine didn't have anything better to do than keep checking. Later when mp lisps started running as one process among many on non lisp machines it was still reasonable to go through one cycle to check whether any process was ready, and if none were ready then wait for some OS event that might make one of them ready. That would not account for cases like a process waiting for the time to be > 1PM, but the documentation explained this and showed how you could get the right effect in some other way (like sleep). When we have multiple lisp threads running and one may do something that causes another to be ready, without any explicit signal to that effect, there seems no alternative to something like thread-wait (the busy wait inside the thread), possibly mitigated by sleep. In some cases this may actually be the most efficient implementation, as well as the easiest to program. It occurs to me that, if you view gbbopen portable threads as a reasonable interface, you might implement it and make it part of clisp. I notice in particular that it contains something called as-atomic-operation, which I gather (let me know if I'm wrong about this) has the semantics described above -- nothing else can be going on at the same time. This is also what without-interrupts means on a 1-cpu machine, and in fact one correct (though perhaps not efficient) way for me to port to clisp-mt would be to define without-interrupts as as-atomic-operation. The good thing about as-atomic-operation is that it is an adequate basis for implementing all the other locking/scheduling/mutex stuff in lisp (which in effect is what I have done). The bad thing is that you have to stop all the other threads, which is a cost in efficiency in two different ways. One is loss of parallelism, the other is the cost of stopping all the other threads. You evidently already have a way to do that, since I gather GC does it. How expensive is this operation? (For that matter, I'd be interested in how it works.) (BTW, another project I'd love to see is GC implemented as thread(s) running in parallel with non-gc threads.) > Whatever thread-state returns - until you process it in meaningful > way - it may change. Is thread-state supposed to be related to who-state in some way? > Will remove both of them (anyway they are not implemented). Any > objections? At this point I can't tell what it is you plan to remove. |
From: Vladimir T. <vtz...@gm...> - 2009-02-22 18:22:10
|
On Sun, 22 Feb 2009 19:16:17 +0200, Don Cohen <don...@is...> wrote: > Vladimir Tzankov writes: > > > If the thread finishes - in order to remove it from the list of all > > threads - we will have to scan whether there are refernces to > > it. This is expensive operation and anyway is performed during GC. > Clearly something internally does not work as I expect. > To me the obvious solution was that > - make-thread would add the new thread to the list read by list-threads > - finishing a thread would remove it from that list list-threads returns all threads accessible in the system regardless whether they have finished or not. If you are interested only in running threads there is always (mapcar #'thread-active-p (list-threads)) However while you process the return of this - some of the threads may finish as well. The reason finished threads are included in the list is that there are references to them and/or you may be interested why some of them have terminated. This may be done by inspecting some of special variable bindings (symbol-value-thread sym thread). May be quite helpful sometimes and does not harm anything. > > > I don't see what control over the scheduler has to do with it. > > > Thread-wait seems to make sense if you're willing to busy wait, > > > which might be more reasonable if you include a sleep in the loop. > > See: http://gbbopen.org/hyperdoc/ref-portable-thread-entities.html - > > "What about Process Wait?" > I find the whole page to be very interesting - I was not aware it > existed. However I don't see that it answers the question of what > any of this has to do with control over the scheduler. > > My view is that it has nothing to do with the scheduler. > I think process-wait was (is) a reasonable thing in single cpu > machines. Even with single CPU it is not good at all. thread-wait with some predicate does not assure anything. The OS thread scheduler may preempt the predicate at the middle or after it has returned T but before thread-wait returns. The next scheduled thread may change the whole program state in such a way that predicate is NIL. This will not lead to anything good. without-interrupts does not enforce no preemption with native OS threads. It enforces the form to be executed entirely (what we discuss about unwind-protect cleanup forms) but it can be preempted meanwhile. Of course it is possible to provide something like without-other-threads-running but this is the worst kind of synchronization possible. It is expensive and will not scale. > It occurs to me that, if you view gbbopen portable threads as a > reasonable interface, you might implement it and make it part of > clisp. I plan to provide port for clisp. > I notice in particular that it contains something called > as-atomic-operation, which I gather (let me know if I'm wrong about > this) has the semantics described above -- nothing else can be going > on at the same time. Please check also the comments in: http://gbbopen.org/svn/GBBopen/trunk/source/tools/portable-threads.lisp about ClozureCL and as-atomic-operation (CCL also uses native OS threads). > (BTW, another project I'd love to see is GC implemented as thread(s) > running in parallel with non-gc threads.) Me too. It seems the marking phase can be parallelised. However not sure whether there will be significant increase in performance. > > Whatever thread-state returns - until you process it in meaningful > > way - it may change. > Is thread-state supposed to be related to who-state in some way? No. I did not find good fit/implementation for both of them. Whoever wants something like whostate - can easily implement it. thread-state is not adequate when you can be preempted at any time. |
From: Sam S. <sd...@gn...> - 2009-02-22 18:45:10
|
> * Don Cohen <qba...@vf...3-vap.pbz> [2009-02-22 09:16:17 -0800]: > > I think process-wait was (is) a reasonable thing in single cpu > machines. what would the process-wait's contract be? I have a feeling that any reasonable contract for process-wait can be implemented in the user space. -- Sam Steingold (http://sds.podval.org/) on Ubuntu 8.10 (intrepid) http://www.PetitionOnline.com/tap12009/ http://honestreporting.com http://thereligionofpeace.com http://www.memritv.org http://truepeace.org Three can keep a secret if two of them are dead. |
From: <don...@is...> - 2009-02-22 22:29:08
|
Sam Steingold writes: > what would the process-wait's contract be? I think this is now answered in the previous message. Among other things it gives you a place to put code that runs as at atomic operation -- which seems not to be what as-atomic-operation does. I don't think that can be implemented from user space. Actually, process wait now feels to me a lot like your exemptions. When you get control back you know that the condition was true just before. Even better than exemptions, though, you also know that nothing (at least nothing you're supposed to care about) has changed since then. Perhaps you can tell me why the term exemption is appropriate. I suggest thread-condition. |
From: Vladimir T. <vtz...@gm...> - 2009-02-22 23:00:19
|
On Mon, 23 Feb 2009 00:14:36 +0200, Don Cohen <don...@is...> wrote: > Vladimir Tzankov writes: > > > The reason finished threads are included in the list is that there > > are references to them and/or you may be interested why some of > > I see no reason for the implementation related to list-threads to keep > such references. If the programmer wants to keep other references > that seems to present no problem. Ok, what do you suggest list-threads should return (or should it be available at all)? Only running threads? What is the guarantee that when you get the results these threads will still be running? > > Even with single CPU it is not good at all. thread-wait with some > > predicate does not assure anything. > I disagree. > > > The OS thread scheduler may preempt the predicate at the middle or > > after it has returned T but before thread-wait returns. The next > This is not true. The process-wait predicate was executed in the > scheduler (meaning that no process other than the scheduler was > running or was going to be able to until the scheduler resumed another > process). When it returned true the scheduler would then resume the > process that was ready. No. The "scheduler" may not resume "the process that was ready". I think here we have confusion about what "scheduler" means. With native OS threads - we do not have control over "scheduler" - the OS does the scheduling and we cannot control it. We do not know which thread will run next, when we are going to be preempted, etc. That's the whole point to have sync primitives. > > Of course it is possible to provide something like > > without-other-threads-running but this is the worst kind of > > synchronization possible. It is expensive and will not scale. > > This is what I assumed as-atomic-operation did. You didn't answer > my question of how expensive it is. (Or how it works.) Basically all threads are asked to "suspend" themselves (by waiting on a mutex). Threads should acknowledge this suspend request. They check for suspend request at certain points - heap allocation, explicit points (and are considered to have ack-ed it while they are in possibly blocking system calls. upon return from these system calls - they may wait more for resume). > > > I notice in particular that it contains something called > > > as-atomic-operation, which I gather (let me know if I'm wrong about > > > this) has the semantics described above -- nothing else can be going > > > on at the same time. > > > > Please check also the comments in: > > http://gbbopen.org/svn/GBBopen/trunk/source/tools/portable-threads.lisp > > about ClozureCL and as-atomic-operation (CCL also uses native OS threads). > > I don't understand this. First, my understanding is that > #+allegro without-scheduling > and similar does not guarantee that no other lisp threads are running. > And second, if I change my guess about what the meaning of > as-atomic-operation is to be the same as (what I believe is meant by) > without-scheduling, that seems completely different from the meaning > of (with-lock-held ...) -- which also differs from what I expected > as-atomic-operation to do. My point is that as-atomic-operation in portable-threads for native OS threading implementation as ClozureCL is implemented via simple lock (mutex), since without-interrupts from CCL does not have anything to do with thread-scheduling. And there is confusion here about what atomic is. By atomic I understand quite low-level simple operation as described here: http://en.wikipedia.org/wiki/Atomic_operation Atomic operation are quite helpful in implementing some lock-free data structures. Can you explain what you mean by atomic operation? |
From: <don...@is...> - 2009-02-22 23:56:44
|
Vladimir Tzankov writes: > Ok, what do you suggest list-threads should return (or should it be > available at all)? It is too useful to be without. I'd expect it to return a copy of the list maintained by adding new threads when they are created and removing them when they are killed (inc. when they finish). > Only running threads? What is the guarantee that when you get the > results these threads will still be running? There is no such guarantee. > > > The OS thread scheduler may preempt the predicate at the middle or > > > after it has returned T but before thread-wait returns. The next > > This is not true. The process-wait predicate was executed in the > > scheduler (meaning that no process other than the scheduler was > > running or was going to be able to until the scheduler resumed another > > process). When it returned true the scheduler would then resume the > > process that was ready. > > No. The "scheduler" may not resume "the process that was ready". (The phrase "may not" is actually ambiguous in English. I assume you mean it is not required to, e.g., the test may return true and then the scheduler can do something other than resume it.) Although I don't recall seeing any such documentation (or code), my understanding was that whenever a process was resumed, it was the case that the only instructions that had been executed since its wait function returned true were the instructions used to resume it. This does not necessarly contradict your statement, but it does still provide a strong condition. > I think here we have confusion about what "scheduler" means. > With native OS threads - we do not have control over "scheduler" - > the OS does the scheduling and we cannot control it. We do not know > which thread will run next, when we are going to be preempted, > etc. That's the whole point to have sync primitives. I realize that the version of process-wait I described cannot be implemented in pthreads, at least not without stopping all threads, which is clearly undesirable. I was just trying to describe the semantics of old style processes and argue that they were reasonable. And remain reasonable in 1-cpu machines. I gather we can (and hope we will) have some more control over scheduling of threads. Locking already provides the most important control. > > This is what I assumed as-atomic-operation did. You didn't answer > > my question of how expensive it is. (Or how it works.) > Basically all threads are asked to "suspend" themselves (by waiting > on a mutex). Threads should acknowledge this suspend request. They I don't understand the acknowledgement part. (Maybe not necessary.) > check for suspend request at certain points ... So the point is that each thread is assumed to be running code that will, within some reasonable time, check whether it has been asked to suspend. I was hoping there was some better way. > My point is that as-atomic-operation in portable-threads for native > OS threading implementation as ClozureCL is implemented via simple > lock (mutex), since without-interrupts from CCL does not have > anything to do with thread-scheduling. But what does that guarantee? Only that two different atomic operations don't run simultaneously! The danger is that some thread NOT in an atomic might interfere with the atomic operation. > And there is confusion here about what atomic is. > By atomic I understand quite low-level simple operation as > described here: http://en.wikipedia.org/wiki/Atomic_operation > Atomic operation are quite helpful in implementing some lock-free > data structures. > Can you explain what you mean by atomic operation? I meant the first part - invisibility. That is, there should be no way to tell that anything outside the operation occurred other than before it started or after it finished. (Of course, compound operations could occur partly before and partly after.) As far as I know, the only way to implement this is to stop all other activity that could possibly interfere/interact with the atomic operation. The second part is about database transactions and seems not to apply here. |
From: Dan C. <corkill@GBBopen.org> - 2009-02-22 23:17:17
|
> I don't understand this. First, my understanding is that > #+allegro without-scheduling > and similar does not guarantee that no other lisp threads are running. >From Allegro CL's multiprocessing documentation: ... the without-scheduling macro protect[s] a segment of code from interleaving execution with other processes. |
From: <don...@is...> - 2009-02-22 23:28:00
|
Dan Corkill writes: > > > I don't understand this. First, my understanding is that > > #+allegro without-scheduling > > and similar does not guarantee that no other lisp threads are running. > > >From Allegro CL's multiprocessing documentation: > > ... the without-scheduling macro protect[s] a segment of code from > interleaving execution with other processes. This differs from the doc I see in http://www.franz.com/support/documentation/8.0/doc/multiprocessing.htm without-scheduling &body body This macro inhibits the OS (in :os-threads) or the scheduler (non :os-threads) from suspending a process involuntarily (asynchronously) during the execution of body. This always works in non :os-threads versions since the scheduler is a Lisp process. However, in :os-threads versions, the OS will run another process if the current process blocks, waits, or executes a process-allow-schedule. My interpretation is that if you can have two threads running sumultaneously then doing without-scheduling in one does not stop the other. without-interrupts &body body This macro executes body protecting against any handling of asynchronous interrupts. Execution of body is guaranteed to complete without any other process running, This seems to be what we want. But I'm still not convinced, without confirmation from Franz, that without-interrupts actually stops all other threads before continuing. If it does, then a better description is called for in the first sentence. or any asynchronous interrupt being dispatched, unless the process does something to block or otherwise explicitly yield to the scheduler (e.g., with process-allow-schedule). It is an error to call a heap-releasing foreign function within the scope of without-interrupts. |