* Multitasking and containers @ 2006-11-24 8:51 Maciej Sobczak 2006-11-24 10:11 ` Georg Bauhaus ` (2 more replies) 0 siblings, 3 replies; 27+ messages in thread From: Maciej Sobczak @ 2006-11-24 8:51 UTC (permalink / raw) Hi, Paragraph 3 in Annex A says that it's OK to call any standard subprogram from concurrent tasks as long as the parameters do not overlap. John Barnes ("Progamming in Ada 2005") suggests that in order to (for example) read from the same container, the operations need to be protected "by using the normal techniques such as protected objects". But reading from the protected object is not mutually exclusive (many readers are allowed) - so where's the gain? What's the difference between concurrent reads of, say, a Vector via protected object vs. direct access? -- Maciej Sobczak : http://www.msobczak.com/ Programming : http://www.msobczak.com/prog/ ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Multitasking and containers 2006-11-24 8:51 Multitasking and containers Maciej Sobczak @ 2006-11-24 10:11 ` Georg Bauhaus 2006-11-24 10:19 ` Dmitry A. Kazakov 2006-11-24 12:02 ` Matthew Heaney 2 siblings, 0 replies; 27+ messages in thread From: Georg Bauhaus @ 2006-11-24 10:11 UTC (permalink / raw) Maciej Sobczak wrote: > But reading from the protected object is not mutually exclusive (many > readers are allowed) - so where's the gain? What's the difference > between concurrent reads of, say, a Vector via protected object vs. > direct access? Supposing that some operations perform a write on the container, for example while filling or updating, then if there is any potential overlap of a read and a write, the gain of protection is that none of the writes can ever interfere with one of the read operations. If there is no write after some point, I would say that "normal means of protection" includes "no protection is necessary after this point". -- Georg ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Multitasking and containers 2006-11-24 8:51 Multitasking and containers Maciej Sobczak 2006-11-24 10:11 ` Georg Bauhaus @ 2006-11-24 10:19 ` Dmitry A. Kazakov 2006-11-24 10:35 ` Maciej Sobczak 2006-11-24 12:05 ` Matthew Heaney 2006-11-24 12:02 ` Matthew Heaney 2 siblings, 2 replies; 27+ messages in thread From: Dmitry A. Kazakov @ 2006-11-24 10:19 UTC (permalink / raw) On Fri, 24 Nov 2006 09:51:24 +0100, Maciej Sobczak wrote: > Paragraph 3 in Annex A says that it's OK to call any standard subprogram > from concurrent tasks as long as the parameters do not overlap. John > Barnes ("Progamming in Ada 2005") suggests that in order to (for > example) read from the same container, the operations need to be > protected "by using the normal techniques such as protected objects". > > But reading from the protected object is not mutually exclusive (many > readers are allowed) - so where's the gain? What's the difference > between concurrent reads of, say, a Vector via protected object vs. > direct access? I think he didn't mean container being a protected object. It would be difficult to do, because protected types alas aren't tagged. So I read it as "by using a locking/serialization technique, such as mutex, which can be implemented as a protected object." [ I don't know if ARM 2005 permits mutable implementations of read operations on the containers. I suppose it does, so the need to lock upon read. ] -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Multitasking and containers 2006-11-24 10:19 ` Dmitry A. Kazakov @ 2006-11-24 10:35 ` Maciej Sobczak 2006-11-24 11:14 ` Dmitry A. Kazakov 2006-11-24 12:12 ` Matthew Heaney 2006-11-24 12:05 ` Matthew Heaney 1 sibling, 2 replies; 27+ messages in thread From: Maciej Sobczak @ 2006-11-24 10:35 UTC (permalink / raw) Dmitry A. Kazakov wrote: >> Paragraph 3 in Annex A says that it's OK to call any standard subprogram >> from concurrent tasks as long as the parameters do not overlap. John >> Barnes ("Progamming in Ada 2005") suggests that in order to (for >> example) read from the same container, the operations need to be >> protected "by using the normal techniques such as protected objects". >> >> But reading from the protected object is not mutually exclusive (many >> readers are allowed) - so where's the gain? What's the difference >> between concurrent reads of, say, a Vector via protected object vs. >> direct access? > > I think he didn't mean container being a protected object. No, but you might want to encapsulate a container within a protected object and have some protected procedures and functions forwarding to relevant ones in the container. > [ I don't know if ARM 2005 permits mutable implementations of read > operations on the containers. I suppose it does, so the need to lock upon > read. ] That would be interesting, but would break apart when encapsulated within a protected object, because there multiple readers would be allowed. Having a mutex for readers sounds like a concurrency killer and relying on protected wrappers seems to be fragile because of this possible mutability. So - what is The Solution (tm) for multiple tasks reading from the same container? Let's say you want to have N worker tasks consulting a shared dictionary (map) that was initialized before the tasks started their work. How would you solve this? -- Maciej Sobczak : http://www.msobczak.com/ Programming : http://www.msobczak.com/prog/ ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Multitasking and containers 2006-11-24 10:35 ` Maciej Sobczak @ 2006-11-24 11:14 ` Dmitry A. Kazakov 2006-11-24 12:13 ` Matthew Heaney 2006-11-24 12:12 ` Matthew Heaney 1 sibling, 1 reply; 27+ messages in thread From: Dmitry A. Kazakov @ 2006-11-24 11:14 UTC (permalink / raw) On Fri, 24 Nov 2006 11:35:11 +0100, Maciej Sobczak wrote: > Dmitry A. Kazakov wrote: > >>> Paragraph 3 in Annex A says that it's OK to call any standard subprogram >>> from concurrent tasks as long as the parameters do not overlap. John >>> Barnes ("Progamming in Ada 2005") suggests that in order to (for >>> example) read from the same container, the operations need to be >>> protected "by using the normal techniques such as protected objects". >>> >>> But reading from the protected object is not mutually exclusive (many >>> readers are allowed) - so where's the gain? What's the difference >>> between concurrent reads of, say, a Vector via protected object vs. >>> direct access? >> >> I think he didn't mean container being a protected object. > > No, but you might want to encapsulate a container within a protected > object and have some protected procedures and functions forwarding to > relevant ones in the container. OK, but that's same to me. Aggregation + delegation = inheritance for poor... >> [ I don't know if ARM 2005 permits mutable implementations of read >> operations on the containers. I suppose it does, so the need to lock upon >> read. ] > > That would be interesting, but would break apart when encapsulated > within a protected object, because there multiple readers would be allowed. > > Having a mutex for readers sounds like a concurrency killer and relying > on protected wrappers seems to be fragile because of this possible > mutability. So - what is The Solution (tm) for multiple tasks reading > from the same container? > > Let's say you want to have N worker tasks consulting a shared dictionary > (map) that was initialized before the tasks started their work. How > would you solve this? I would try to decouple the mutable part. [ It is a quite common problem, not necessarily in the context of concurrent programming. ] The cache that does not belong to the container should be associated with the caller's task. That would eliminate any need of locking. The cache shared between the callers should be locked when changed. So a protected object should be associated with that cache, not with the container as a whole. Write your own container. Parallel systems require delicate handmade work. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Multitasking and containers 2006-11-24 11:14 ` Dmitry A. Kazakov @ 2006-11-24 12:13 ` Matthew Heaney 2006-11-27 4:17 ` Jeffrey R. Carter 0 siblings, 1 reply; 27+ messages in thread From: Matthew Heaney @ 2006-11-24 12:13 UTC (permalink / raw) "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes: > Write your own container. Parallel systems require delicate handmade work. Horrible advice. Just declare the container inside a protect object, and manipulate the container by calling protected procedures. Works great... ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Multitasking and containers 2006-11-24 12:13 ` Matthew Heaney @ 2006-11-27 4:17 ` Jeffrey R. Carter 2006-11-27 10:30 ` Georg Bauhaus 0 siblings, 1 reply; 27+ messages in thread From: Jeffrey R. Carter @ 2006-11-27 4:17 UTC (permalink / raw) Matthew Heaney wrote: > "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes: > >> Write your own container. Parallel systems require delicate handmade work. > > Horrible advice. Just declare the container inside a protect object, and > manipulate the container by calling protected procedures. Works great... Not at all, even for sequential systems. Standard libraries are necessarily compromises among various concerns such as safety, performance, ease of use, and so on. Specific projects may, and sometimes will, have requirements that are not met by such libraries. In such cases, custom versions are needed. In this case, we may have an instance of premature optimization; the OP seems to be worrying about the overhead of wrapping a container in a protected object without any evidence that this approach won't meet the project's requirements (indeed, it seems there is no project and no specific requirements are involved). In that case, it probably will "work great". But in specific cases a custom version that does allow unprotected multiple readers may be required. -- Jeff Carter "There's no messiah here. There's a mess all right, but no messiah." Monty Python's Life of Brian 84 ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Multitasking and containers 2006-11-27 4:17 ` Jeffrey R. Carter @ 2006-11-27 10:30 ` Georg Bauhaus 2006-11-27 18:41 ` Jeffrey R. Carter 0 siblings, 1 reply; 27+ messages in thread From: Georg Bauhaus @ 2006-11-27 10:30 UTC (permalink / raw) On Mon, 2006-11-27 at 04:17 +0000, Jeffrey R. Carter wrote: > Matthew Heaney wrote: > > "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes: > > > >> Write your own container. Parallel systems require delicate handmade work. > > > > Horrible advice. Just declare the container inside a protect object, and > > manipulate the container by calling protected procedures. Works great... > > Not at all, [...]. Specific projects may, and > sometimes will, have requirements that are not met by such libraries. But "parallel systems require delicate handmade work" is probably not good advice at all, because (a) parallel systems operate in parallel and there isn't a sharing issue in the first place, no protection is needed. (b) When systems start communicating, and if it were true that concurrency requires delicate handmade work, why then use a language like Ada? The delicacies of the mechanisms behind tasks and shared protected objects are hidden in Ada RTSs. Therefore, if parallel systems do require delicate handmade work, the language designers should abandon Ada tasks and protected objects, because obviously they cannot meet the requirements of parallel systems. ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Multitasking and containers 2006-11-27 10:30 ` Georg Bauhaus @ 2006-11-27 18:41 ` Jeffrey R. Carter 2006-11-27 18:57 ` Dmitry A. Kazakov 2006-11-27 19:45 ` Matthew Heaney 0 siblings, 2 replies; 27+ messages in thread From: Jeffrey R. Carter @ 2006-11-27 18:41 UTC (permalink / raw) Georg Bauhaus wrote: > > But "parallel systems require delicate handmade work" is probably > not good advice at all, because (a) parallel systems operate in parallel > and there isn't a sharing issue in the first place, no protection is > needed. (b) When systems start communicating, and if it were true > that concurrency requires delicate handmade work, why then use a > language like Ada? The delicacies of the mechanisms behind tasks > and shared protected objects are hidden in Ada RTSs. Therefore, if > parallel systems do require delicate handmade work, the language > designers should abandon Ada tasks and protected objects, because > obviously they cannot meet the requirements of parallel systems. I guess we have different interpretations of "delicate handmade work". I took it simply to mean custom implementations tailored to the specific project (such as a container that does not need protection for reads). I guess only Kazakov can tell us for sure. -- Jeff Carter "My brain hurts!" Monty Python's Flying Circus 21 ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Multitasking and containers 2006-11-27 18:41 ` Jeffrey R. Carter @ 2006-11-27 18:57 ` Dmitry A. Kazakov 2006-11-27 19:45 ` Matthew Heaney 1 sibling, 0 replies; 27+ messages in thread From: Dmitry A. Kazakov @ 2006-11-27 18:57 UTC (permalink / raw) On Mon, 27 Nov 2006 18:41:00 GMT, Jeffrey R. Carter wrote: > Georg Bauhaus wrote: >> >> But "parallel systems require delicate handmade work" is probably >> not good advice at all, because (a) parallel systems operate in parallel >> and there isn't a sharing issue in the first place, no protection is >> needed. (b) When systems start communicating, and if it were true >> that concurrency requires delicate handmade work, why then use a >> language like Ada? The delicacies of the mechanisms behind tasks >> and shared protected objects are hidden in Ada RTSs. Therefore, if >> parallel systems do require delicate handmade work, the language >> designers should abandon Ada tasks and protected objects, because >> obviously they cannot meet the requirements of parallel systems. > > I guess we have different interpretations of "delicate handmade work". I > took it simply to mean custom implementations tailored to the specific > project (such as a container that does not need protection for reads). I > guess only Kazakov can tell us for sure. Actually, you did it better than me. Thanks. I also agree with your point about premature optimization. It is a common disease, which costs much work and many bad designs, which in the end turn neither efficient nor clean. I suffer it as well, this in a human nature of many programmers. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Multitasking and containers 2006-11-27 18:41 ` Jeffrey R. Carter 2006-11-27 18:57 ` Dmitry A. Kazakov @ 2006-11-27 19:45 ` Matthew Heaney 2006-11-27 21:15 ` Simon Wright 2006-11-28 1:43 ` Dr. Adrian Wrigley 1 sibling, 2 replies; 27+ messages in thread From: Matthew Heaney @ 2006-11-27 19:45 UTC (permalink / raw) Jeffrey R. Carter wrote: > > I guess we have different interpretations of "delicate handmade work". I > took it simply to mean custom implementations tailored to the specific > project (such as a container that does not need protection for reads). But that's the same as saying you can not use anything in the predefined library. If so then the container library is the least of your problems! ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Multitasking and containers 2006-11-27 19:45 ` Matthew Heaney @ 2006-11-27 21:15 ` Simon Wright 2006-11-28 1:43 ` Dr. Adrian Wrigley 1 sibling, 0 replies; 27+ messages in thread From: Simon Wright @ 2006-11-27 21:15 UTC (permalink / raw) "Matthew Heaney" <mheaney@on2.com> writes: > Jeffrey R. Carter wrote: >> >> I guess we have different interpretations of "delicate handmade work". I >> took it simply to mean custom implementations tailored to the specific >> project (such as a container that does not need protection for reads). > > But that's the same as saying you can not use anything in the > predefined library. If so then the container library is the least of > your problems! If the predefined library doesn't meet your needs you do indeed have a lot of work ahead of you; often small beer in the overall scope (eg, safety-related systems with SIL4 software => no runtime at all [GNAT high integrity edition for example] highly desirable if not absolutely necessary precondition for certification). But if it does meet your needs you're crazy not to use it! ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Multitasking and containers 2006-11-27 19:45 ` Matthew Heaney 2006-11-27 21:15 ` Simon Wright @ 2006-11-28 1:43 ` Dr. Adrian Wrigley 2006-11-28 2:19 ` Matthew Heaney 1 sibling, 1 reply; 27+ messages in thread From: Dr. Adrian Wrigley @ 2006-11-28 1:43 UTC (permalink / raw) On Mon, 27 Nov 2006 11:45:08 -0800, Matthew Heaney wrote: > Jeffrey R. Carter wrote: >> >> I guess we have different interpretations of "delicate handmade work". I >> took it simply to mean custom implementations tailored to the specific >> project (such as a container that does not need protection for reads). > > But that's the same as saying you can not use anything in the > predefined library. If so then the container library is the least of > your problems! Dmitry wrote: >> Write your own container. Parallel systems require delicate handmade work. (noting a breakdown in logic in this argument... Dmitry said handmade work is required. This does not mean that *only* handmade work is allowed, as Matthew seems to infer.) Actually, I think Dmitry's view is largely valid in practice, if somewhat extreme. -- Adrian ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Multitasking and containers 2006-11-28 1:43 ` Dr. Adrian Wrigley @ 2006-11-28 2:19 ` Matthew Heaney 2006-11-28 8:50 ` Dmitry A. Kazakov 0 siblings, 1 reply; 27+ messages in thread From: Matthew Heaney @ 2006-11-28 2:19 UTC (permalink / raw) "Dr. Adrian Wrigley" <amtw@linuxchip.demon.co.uk.uk.uk> writes: > Actually, I think Dmitry's view is largely valid in practice, if > somewhat extreme. But we were talking specifically about using a protected object to implement a multiple readers schema vs. using a protected object to implement a Hoare-style monitor. Because reads must by synchronized, the standard container library requires a monitor-style synchronization scheme. The OP made the argument that this isn't very efficient, and Dmitry responded by saying, "well of course systems require custom hand-made solutions." But the premise is all wrong, so what Dmitry said is irrelevant. The OP (not Dmitry) seems to be confused (he was asking the question, after all) about the difference between a mutex and a monitor. He (the OP) probably doesn't understand that monitor-type synchronization executes on the current thread, so there's no context switch, and so there's no efficiency loss. The only time when monitor-style synchronization would be inappropriate is if the protected operation needed to make a "potentially-blocking call," but that's not the case here so there's no reason (certainly there's no efficiency reason) not to use a monitor. ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Multitasking and containers 2006-11-28 2:19 ` Matthew Heaney @ 2006-11-28 8:50 ` Dmitry A. Kazakov 2006-11-28 10:31 ` Georg Bauhaus ` (2 more replies) 0 siblings, 3 replies; 27+ messages in thread From: Dmitry A. Kazakov @ 2006-11-28 8:50 UTC (permalink / raw) On Tue, 28 Nov 2006 02:19:55 GMT, Matthew Heaney wrote: > "Dr. Adrian Wrigley" <amtw@linuxchip.demon.co.uk.uk.uk> writes: > >> Actually, I think Dmitry's view is largely valid in practice, if >> somewhat extreme. > > But we were talking specifically about using a protected object to implement a > multiple readers schema vs. using a protected object to implement a Hoare-style > monitor. Because reads must by synchronized, the standard container library > requires a monitor-style synchronization scheme. > > The OP made the argument that this isn't very efficient, and Dmitry responded > by saying, "well of course systems require custom hand-made solutions." But the > premise is all wrong, so what Dmitry said is irrelevant. The OP (not Dmitry) > seems to be confused (he was asking the question, after all) about the > difference between a mutex and a monitor. He (the OP) probably doesn't > understand that monitor-type synchronization executes on the current thread, so > there's no context switch, and so there's no efficiency loss. I read OP question very differently. He said (let Maciej correct me): 1. That accessing a mutable operation disguised as a protected object's function were wrong. 2. Using a protected object's procedure/entry would kill concurrency by serialization of the action to undertake. Both statements are evidently true. My comments considered possible solutions *provided* that 2 were really a problem, because as Jeffrey rightly pointed out, the loss of performance could be actually minor. But that depends. It is easy to imagine a situation (massively parallel computing with shared memory) where the loss could be huge. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Multitasking and containers 2006-11-28 8:50 ` Dmitry A. Kazakov @ 2006-11-28 10:31 ` Georg Bauhaus 2006-11-28 11:24 ` Dmitry A. Kazakov 2006-11-28 17:12 ` Matthew Heaney 2006-11-29 10:14 ` Maciej Sobczak 2 siblings, 1 reply; 27+ messages in thread From: Georg Bauhaus @ 2006-11-28 10:31 UTC (permalink / raw) On Tue, 2006-11-28 at 09:50 +0100, Dmitry A. Kazakov wrote: > On Tue, 28 Nov 2006 02:19:55 GMT, Matthew Heaney wrote: > It is easy to imagine a > situation (massively parallel computing with shared memory) where the loss > could be huge. I have learned that Ada tasking is defined at a relatively high level. Suppose you are writing highly specialized low level software, such as when taking advantage of a specific computer's architecture at the system or hardware level. It is easy for me to imagine that you are working way below Ada's tasking level. Are you suggesting that this is the normal mode of using a high level programming language that supports tasking? ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Multitasking and containers 2006-11-28 10:31 ` Georg Bauhaus @ 2006-11-28 11:24 ` Dmitry A. Kazakov 2006-11-29 8:51 ` Georg Bauhaus 0 siblings, 1 reply; 27+ messages in thread From: Dmitry A. Kazakov @ 2006-11-28 11:24 UTC (permalink / raw) On Tue, 28 Nov 2006 11:31:13 +0100, Georg Bauhaus wrote: > On Tue, 2006-11-28 at 09:50 +0100, Dmitry A. Kazakov wrote: >> On Tue, 28 Nov 2006 02:19:55 GMT, Matthew Heaney wrote: >> It is easy to imagine a >> situation (massively parallel computing with shared memory) where the loss >> could be huge. > > I have learned that Ada tasking is defined at a relatively > high level. Suppose you are writing highly specialized low > level software, such as when taking advantage of a specific > computer's architecture at the system or hardware level. > It is easy for me to imagine that you are working way below > Ada's tasking level. Are you suggesting that this is the > normal mode of using a high level programming language > that supports tasking? I didn't mean Ada tasking at all [*]. I meant explicitly one concrete design solution: a container with mutable reads wrapped into a protected object's procedure. What makes you think that my proposal to decouple the mutable context from the container data type is any lower level than fighting with side-effects by rough locking? It is merely a design question. You replace: function Find ( Container : access Dictionary; Token : Key ) return Topic; with function Find ( Container : Dictionary; Token : Key; Context : access Environment ) return Topic; where Context provides protected interface to shared mutable data, which hopefully need not to changed upon each call. or else you use mix-in on the container type: type Dictionary (Context : access Environment) is ...; ------------------------------------------- * If your question concerns whether Ada's tasking primitives are composable with other language features. Then the answer is clear and unambiguous. They are *not*. There are many *objective* reasons for this unhappy situation. Objective in the sense that it would be unfair and just wrong to address them to the language design faults. If you disagree with that, then you should have dismissed the design of Ada.Containers for being task-unsafe. Because the following two statements are mutually incompatible: 1. Ada.Containers may be task-unsafe 2. Ada tasking primitives are composable -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Multitasking and containers 2006-11-28 11:24 ` Dmitry A. Kazakov @ 2006-11-29 8:51 ` Georg Bauhaus 0 siblings, 0 replies; 27+ messages in thread From: Georg Bauhaus @ 2006-11-29 8:51 UTC (permalink / raw) On Tue, 2006-11-28 at 12:24 +0100, Dmitry A. Kazakov wrote: > On Tue, 28 Nov 2006 11:31:13 +0100, Georg Bauhaus wrote: > > > On Tue, 2006-11-28 at 09:50 +0100, Dmitry A. Kazakov wrote: > >> On Tue, 28 Nov 2006 02:19:55 GMT, Matthew Heaney wrote: > >> It is easy to imagine a > >> situation (massively parallel computing with shared memory) where the loss > >> could be huge. > > > > I have learned that Ada tasking is defined at a relatively > > high level. Suppose you are writing highly specialized low > > level software, such as when taking advantage of a specific > > computer's architecture at the system or hardware level. > > It is easy for me to imagine that you are working way below > > Ada's tasking level. Are you suggesting that this is the > > normal mode of using a high level programming language > > that supports tasking? > > I didn't mean Ada tasking at all [*]. I meant explicitly one concrete > design solution: a container with mutable reads wrapped into a protected > object's procedure. Well, your design solution ("have the user take care of any concurrency issues by providing access to some Environment context" IIUC) seemed to me to refer to a multi-CPU system with shared memory. Then there was massively parallel computing. To me, this sounds like it could be image/video processing, sound production, pattern recognition and the like. Smells like matrices and specially designed algorithms, not like standard containers and Maps of Maps. If your algorithm can guarantee that no read operation tampers with anything in your shared data, fine. If some out of the box algorithms and standard containers are to be used in a less specialized concurrent program, imagining off the street programmers, will you profit from using Ada if programmers will have to trigger semaphores hoisting flags and the like? This is what made me think that your proposal is low level. Incidentally, the design solution blends well with your other design decisions that I can remember. E.g. have the compiler at most help the user to flesh out an Array interface, instead of providing a stinking array construct defined by the language. :-) As Matt has said, "The reason is a conflict between safety and flexibility, a conflict that was resolved in favor of safety." Isn't this true of Ada in general? -- Georg ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Multitasking and containers 2006-11-28 8:50 ` Dmitry A. Kazakov 2006-11-28 10:31 ` Georg Bauhaus @ 2006-11-28 17:12 ` Matthew Heaney 2006-11-28 18:21 ` Dmitry A. Kazakov 2006-11-29 10:14 ` Maciej Sobczak 2 siblings, 1 reply; 27+ messages in thread From: Matthew Heaney @ 2006-11-28 17:12 UTC (permalink / raw) Dmitry A. Kazakov wrote: > 2. Using a protected object's procedure/entry would kill concurrency by > serialization of the action to undertake. There is a difference between "synchronizing access to a shared resource" and "waiting for a resource to become available". Calling a protected function or procedure is an example of the former. Calling a protected procedure would hardly "kill concurrency". In a monitor there is only synchronization. (I think it's the case that the task stays in a running state.) Calling a protected entry whose barrier condition is false is an example of the latter. If the barrier condition were false this would mean the task waits (it transitions to a blocked state). I would be loathe to say that that would "kill" concurrency since in typical designs that's exactly what the task is supposed to do. ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Multitasking and containers 2006-11-28 17:12 ` Matthew Heaney @ 2006-11-28 18:21 ` Dmitry A. Kazakov 2006-11-28 19:17 ` Matthew Heaney 0 siblings, 1 reply; 27+ messages in thread From: Dmitry A. Kazakov @ 2006-11-28 18:21 UTC (permalink / raw) On 28 Nov 2006 09:12:27 -0800, Matthew Heaney wrote: > Dmitry A. Kazakov wrote: >> 2. Using a protected object's procedure/entry would kill concurrency by >> serialization of the action to undertake. > > There is a difference between "synchronizing access to a shared > resource" and "waiting for a resource to become available". > > Calling a protected function or procedure is an example of the former. > Calling a protected procedure would hardly "kill concurrency". In a > monitor there is only synchronization. (I think it's the case that the > task stays in a running state.) Ah, you mean: in absence of preemptive scheduling. > Calling a protected entry whose barrier condition is false is an > example of the latter. If the barrier condition were false this would > mean the task waits (it transitions to a blocked state). I would be > loathe to say that that would "kill" concurrency since in typical > designs that's exactly what the task is supposed to do. No difference if the above premise holds, i.e. no task switches as long as the barrier is closed. But, the above is true *only* for a single-CPU system. So for a truly parallel system it could become a problem. Dual-cores aren't that expensive in these days. Further, even on a single CPU, where protected functions and procedures are equivalent, the requirement "no task switches while lock held" might be unacceptable if you hold it for too long. Searching a container within a protected action ... well, one should be a quite strong believer for this. I wouldn't dismiss it completely, but I definitely don't like it. For hashes I would at least take one with an external hash function computed outside the protected action. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Multitasking and containers 2006-11-28 18:21 ` Dmitry A. Kazakov @ 2006-11-28 19:17 ` Matthew Heaney 2006-11-29 18:43 ` Dmitry A. Kazakov 0 siblings, 1 reply; 27+ messages in thread From: Matthew Heaney @ 2006-11-28 19:17 UTC (permalink / raw) Dmitry A. Kazakov wrote: > > Further, even on a single CPU, where protected functions and procedures are > equivalent, the requirement "no task switches while lock held" might be > unacceptable if you hold it for too long. But this is already a precondition for using a protected object as a monitor. The RM makes it clear that you shouldn't be doing anything that takes "too long" inside a protected operation. > Searching a container within a > protected action ... well, one should be a quite strong believer for this. If this is an associative container then no problem. If this is a sequence container with many elements, well that's another story. > I wouldn't dismiss it completely, but I definitely don't like it. For > hashes I would at least take one with an external hash function computed > outside the protected action. The issue with hash tables is not the computation of the hash value, but rather if the hash function is poor and there are many collisions. If that's the case then the time to compare the key to items already in that bucket will be large compared to the cost of computing the hash value itself. ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Multitasking and containers 2006-11-28 19:17 ` Matthew Heaney @ 2006-11-29 18:43 ` Dmitry A. Kazakov 0 siblings, 0 replies; 27+ messages in thread From: Dmitry A. Kazakov @ 2006-11-29 18:43 UTC (permalink / raw) On 28 Nov 2006 11:17:33 -0800, Matthew Heaney wrote: > The issue with hash tables is not the computation of the hash value, > but rather if the hash function is poor and there are many collisions. > If that's the case then the time to compare the key to items already in > that bucket will be large compared to the cost of computing the hash > value itself. Yes. This is why one should look into the container, as I said before. You lock not the container as a whole, but the bucket. The advantage is that in this case you can lock buckets in a preemptive way, lifting the problem of too long waits, while loosing little: doubled overhead of a protected action. This is how our middleware works. Actually it is just a specialized hash table of process variables. Because it were too expensive to maintain a lock per bucket, I grouped them into a lesser number of "access channels." -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Multitasking and containers 2006-11-28 8:50 ` Dmitry A. Kazakov 2006-11-28 10:31 ` Georg Bauhaus 2006-11-28 17:12 ` Matthew Heaney @ 2006-11-29 10:14 ` Maciej Sobczak 2006-11-29 15:50 ` Matthew Heaney 2 siblings, 1 reply; 27+ messages in thread From: Maciej Sobczak @ 2006-11-29 10:14 UTC (permalink / raw) Dmitry A. Kazakov wrote: >> The OP (not Dmitry) >> seems to be confused (he was asking the question, after all) about the >> difference between a mutex and a monitor. I was asking a question about strategy to use a standard container in a multitasking environment, not what's the difference between a mutex and a monitor. I don't see any implication for confusion in the latter. >> He (the OP) probably doesn't >> understand that monitor-type synchronization executes on the current thread, so >> there's no context switch, and so there's no efficiency loss. The efficiency loss might be possible due to contention on the shared resource. It is clear that with single CPU there is nothing to fuss over, but the concept of "single CPU" became somewhat fuzzy nowadays. > I read OP question very differently. He said (let Maciej correct me): > > 1. That accessing a mutable operation disguised as a protected object's > function were wrong. > > 2. Using a protected object's procedure/entry would kill concurrency by > serialization of the action to undertake. > > Both statements are evidently true. And that's exactly what I meant. > My comments considered possible solutions *provided* that 2 were really a > problem And that's absolutely a non-issue. I'm interested in principles and rationale - a clear understanding of the tools is crucial at the very early stages of project development, because it's when the decisions have the biggest impact on later phases. What I've learned in this thread is that: 1. Ada standard containers should be protected against concurrent accesses (in the general meaning of "access") and it's the obligation of the user to do it. 2. This serializes all users of the container with obvious consequences. Whether any of these two is a problem in any particular project is a non-issue. The point is that these two facts are to be understood, so that they can be taken into account when there's a time to do so. -- Maciej Sobczak : http://www.msobczak.com/ Programming : http://www.msobczak.com/prog/ ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Multitasking and containers 2006-11-29 10:14 ` Maciej Sobczak @ 2006-11-29 15:50 ` Matthew Heaney 0 siblings, 0 replies; 27+ messages in thread From: Matthew Heaney @ 2006-11-29 15:50 UTC (permalink / raw) Maciej Sobczak wrote: > And that's absolutely a non-issue. I'm interested in principles and > rationale - a clear understanding of the tools is crucial at the very > early stages of project development, because it's when the decisions > have the biggest impact on later phases. The rule about synchronizing access to operations declared in the predefined library is an old rule. It was true in Ada83 when using Text_IO. There are no new issues here. > What I've learned in this thread is that: > 1. Ada standard containers should be protected against concurrent > accesses (in the general meaning of "access") and it's the obligation of > the user to do it. Yes, the same as for any other unit in the predefined library. (Do note that monitor-style synchronization of container calls is allowed, since the operations in the container library are not "potentially blocking" calls.) > 2. This serializes all users of the container with obvious consequences. Well the consequences aren't so obvious to me! I have no idea what you're talking about, especially since you claimed above that synchronization was a "non-issue" for you. > Whether any of these two is a problem in any particular project is a > non-issue. The point is that these two facts are to be understood, so > that they can be taken into account when there's a time to do so. Yes, you have to synchronize access to a units in the predefined library. That fact certainly needs to be understood. ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Multitasking and containers 2006-11-24 10:35 ` Maciej Sobczak 2006-11-24 11:14 ` Dmitry A. Kazakov @ 2006-11-24 12:12 ` Matthew Heaney 1 sibling, 0 replies; 27+ messages in thread From: Matthew Heaney @ 2006-11-24 12:12 UTC (permalink / raw) Maciej Sobczak <no.spam@no.spam.com> writes: > That would be interesting, but would break apart when encapsulated within a > protected object, because there multiple readers would be allowed. But I think that's true only when multiple readers are calling protected functions. (There is a subtle difference in semantics between protected functions and protected procedures.) It does seem you'd need to use a protected procedure when manipulating a container nested inside a protected object, since a protected function wouldn't provide the level of synchronization required. > Having a mutex for readers sounds like a concurrency killer and relying on > protected wrappers seems to be fragile because of this possible > mutability. So - what is The Solution (tm) for multiple tasks reading from > the same container? Declare the container object inside a protected object, and use protected procedures to manipulate the container. Protected wrappers should be fine, as long as you use protected procedures, not protected functions. > Let's say you want to have N worker tasks consulting a shared dictionary > (map) that was initialized before the tasks started their work. How would you > solve this? As above: declare the container object inside a protected object, and use protected procedures to manipulate the container. ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Multitasking and containers 2006-11-24 10:19 ` Dmitry A. Kazakov 2006-11-24 10:35 ` Maciej Sobczak @ 2006-11-24 12:05 ` Matthew Heaney 1 sibling, 0 replies; 27+ messages in thread From: Matthew Heaney @ 2006-11-24 12:05 UTC (permalink / raw) "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes: > [ I don't know if ARM 2005 permits mutable implementations of read > operations on the containers. I suppose it does, so the need to lock upon > read. ] Yes, some read operations mutate the container temporarily. That's why the user needs to always synchronize access to the container (even for read operations) if the container can be accessed by several tasks. ^ permalink raw reply [flat|nested] 27+ messages in thread
* Re: Multitasking and containers 2006-11-24 8:51 Multitasking and containers Maciej Sobczak 2006-11-24 10:11 ` Georg Bauhaus 2006-11-24 10:19 ` Dmitry A. Kazakov @ 2006-11-24 12:02 ` Matthew Heaney 2 siblings, 0 replies; 27+ messages in thread From: Matthew Heaney @ 2006-11-24 12:02 UTC (permalink / raw) Maciej Sobczak <no.spam@no.spam.com> writes: > Paragraph 3 in Annex A says that it's OK to call any standard subprogram from > concurrent tasks as long as the parameters do not overlap. John Barnes > ("Progamming in Ada 2005") suggests that in order to (for example) read from > the same container, the operations need to be protected "by using the normal > techniques such as protected objects". Right. > But reading from the protected object is not mutually exclusive (many readers > are allowed) - so where's the gain? What's the difference between concurrent > reads of, say, a Vector via protected object vs. direct access? The reason is a conflict between safety and flexibility, a conflict that was resolved in favor of safety. The container must set some internal state to indicate that Query_Element is executing, in order to prevent you from doing things inside Query_Element that would potentially destroy the element (such as Delete'ing it). Even though Query_Element is technically a read-only operation, that's true only in the logical sense, not the physical sense. It doesn't look like Query_Element modifies the container, but it really does modify the container, to set some state that indicates a Query_Element is in progress. Yes, it would seem as if it should be possible for multiple tasks to all be reading from the container simultaneously. But it's impossible to do that and also satisfy the requirement that the container detect potentially harmful manipulation of the container while Query_Element is executing. So multiple tasks -- even tasks only calling (logically) read-only operations -- cannot simultaneously call container operations without also synchronizing the tasks, by wrapping the container inside a protected object, using a critical section, etc. -Matt ^ permalink raw reply [flat|nested] 27+ messages in thread
end of thread, other threads:[~2006-11-29 18:43 UTC | newest] Thread overview: 27+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2006-11-24 8:51 Multitasking and containers Maciej Sobczak 2006-11-24 10:11 ` Georg Bauhaus 2006-11-24 10:19 ` Dmitry A. Kazakov 2006-11-24 10:35 ` Maciej Sobczak 2006-11-24 11:14 ` Dmitry A. Kazakov 2006-11-24 12:13 ` Matthew Heaney 2006-11-27 4:17 ` Jeffrey R. Carter 2006-11-27 10:30 ` Georg Bauhaus 2006-11-27 18:41 ` Jeffrey R. Carter 2006-11-27 18:57 ` Dmitry A. Kazakov 2006-11-27 19:45 ` Matthew Heaney 2006-11-27 21:15 ` Simon Wright 2006-11-28 1:43 ` Dr. Adrian Wrigley 2006-11-28 2:19 ` Matthew Heaney 2006-11-28 8:50 ` Dmitry A. Kazakov 2006-11-28 10:31 ` Georg Bauhaus 2006-11-28 11:24 ` Dmitry A. Kazakov 2006-11-29 8:51 ` Georg Bauhaus 2006-11-28 17:12 ` Matthew Heaney 2006-11-28 18:21 ` Dmitry A. Kazakov 2006-11-28 19:17 ` Matthew Heaney 2006-11-29 18:43 ` Dmitry A. Kazakov 2006-11-29 10:14 ` Maciej Sobczak 2006-11-29 15:50 ` Matthew Heaney 2006-11-24 12:12 ` Matthew Heaney 2006-11-24 12:05 ` Matthew Heaney 2006-11-24 12:02 ` Matthew Heaney
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox