From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,FREEMAIL_FROM autolearn=ham autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: ffc1e,fb45e48e8dddeabd X-Google-Attributes: gidffc1e,public X-Google-Thread: 103376,fb45e48e8dddeabd X-Google-Attributes: gid103376,public From: "Vladimir Olensky" Subject: Re: Ada Protected Object Tutorial #1 Date: 1999/12/20 Message-ID: X-Deja-AN: 563020109 References: <839toq$pu$1@bgtnsc03.worldnet.att.net> <385AC716.7E65BD5C@averstar.com> Organization: Posted via Supernews, http://www.supernews.com X-MimeOLE: Produced By Microsoft MimeOLE V4.72.3110.3 Newsgroups: comp.programming.threads,comp.lang.ada X-Complaints-To: newsabuse@supernews.com Date: 1999-12-20T00:00:00+00:00 List-Id: Kaz Kylheku wrote in message ... >On Fri, 17 Dec 1999 23:28:22 GMT, Tucker Taft wrote: >>As one data point, a classic producer/consumer example with a >>bounded buffer, when coded using a protected type versus >>usingmutex/condition variables, results in typically half as many >>locks and unlocks, and one third as many context switches >>between the producer and the consumer. The mutex/condition >>variable approach involves so much more work because each >>thread ends up doing all the work "itself," rather than allowing the >>other threadto do a little bit of work on its behalf while it already >> holds the lock. > >Is there a paper about this which argues the case in more detail? Below is an example from Ada Rational: http://www.adahome.com/LRM/95/Rationale/rat95html/rat95-contents.html Regards, Vladimir Olensky ================================================== 9.1.3 Efficiency of Protected Types Protected types provide an extremely efficient mechanism; the ability to use the thread of control of one task to execute a protected operation on behalf of another task reduces the overhead of context switching compared with other paradigms. Protected types are thus not only much more efficient than the use of an agent task and associated rendezvous, they are also more efficient than traditional monitors or semaphores in many circumstances. As an example consider the following very simple protected object which implements a single buffer between a producer and a consumer task. protected Buffer is entry Put(X: in Item); entry Get(X: out Item); private Data: Item; Full: Boolean := False; end; protected body Buffer is entry Put(X: in Item) when not Full is begin Data := X; Full := True; end Put; entry Get(X: out Item) when Full is begin X := Data; Full := False; end Get; end Buffer; This object can contain just a single buffered value of the type Item in the variable Data; the boolean Full indicates whether or not the buffer contains a value. The barriers ensure that reading and writing of the variable is interleaved so that each value is only used once. The buffer is initially empty so that the first call that will be processed will be of Put. A producer and consumer task might be task body Producer is begin loop ... -- generate a value Buffer.Put(New_Item); end loop; end Producer; task body Consumer is begin loop Buffer.Get(An_Item); ... -- use a value end loop; end Consumer; In order to focus the discussion we will assume that both tasks have the same priority and that a run until blocked scheduling algorithm is used on a single processor. We will also start by giving the processor to the task Consumer. The task Consumer will issue a call of Get, acquire the lock and then find that the barrier is false thereby causing it to be queued and to release the lock. The Consumer is thus blocked and so a context switch occurs and control passes to the task Producer. This sequence of actions can be symbolically described by Get(An_Item); lock queue unlock switch context The task Producer issues a first call of Put, acquires the lock, successfully executes the body of Put thereby filling the buffer and setting Full to False. Before releasing the lock, it reevaluates the barriers and checks the queues to see whether a suspended operation can now be performed. It finds that it can and executes the body of the entry Get thereby emptying the buffer and causing the task Consumer to be marked as no longer blocked and thus eligible for processing. Note that the thread of control of the producer has effectively performed the call of Get on behalf of the consumer task; the overhead for doing this is essentially that of a subprogram call and a full context switch is not required. This completes the sequence of protected actions and the lock is released. However, the task Producer still has the processor and so it cycles around its loop and issues a second call of Put. It acquires the lock again, executes the body of Put thereby filling the buffer again. Before releasing the lock it checks the barriers but of course no task is queued and so nothing else can be done; it therefore releases the lock. The task Producer still has the processor and so it cycles around its loop and issues yet a third call of Put. It acquires the lock but this time it finds the barrier is false since the buffer is already full. It is therefore queued and releases the lock. The producer task is now blocked and so a context switch occurs and control at last passes to the consumer task. The full sequence of actions performed by the producer while it had the processor are Put(New_Item); lock Data := New_Item; Full := True; scan: and then on behalf of Consumer An_Item := Data; Full := False; set Consumer ready unlock Put(New_Item); lock Data := New_Item: Full := True; scan: nothing to do unlock Put(New_Item); lock queue unlock switch context The consumer task now performs a similar cycle of actions before control passes back to the producer and the whole pattern then repeats. The net result is that three calls of Put or Get are performed between each full context switch and that each call of Put or Get involves just one lock operation. This should be contrasted with the sequence required by the corresponding program using primitive operations such as binary semaphores (mutexes). This could be represented by package Buffer is procedure Put(X: in Item); procedure Get(X: out Item); private Data: Item; Full: Semaphore := busy; Empty: Semaphore := free; end; package body Buffer is procedure Put(X: in Item) is begin P(Empty); Data := X; V(Full); end Put; procedure Get(X: out Item) is begin P(Full); X := Data; V(Empty); end Get; end Buffer; In this case there are two lock operations for each call of Put and Get, one for each associated semaphore action. The behavior is now as follows (assuming once more that the consumer has the processor initially). The first call of Get by the consumer results in the consumer being suspended by P(Full) and a context switch to the producer occurs. The first call of Put by the producer is successful, the buffer is filled and the operation V(Full) clears the semaphore upon which the consumer is waiting. The second call of Put is however blocked by P(Empty) and so a context switch to the consumer occurs. The consumer is now free to proceed and empties the buffer and performs V(Empty) to clear the semaphore upon which the producer is waiting. The next call of Get by the consumer is blocked by P(Full) and so a context switch back to the producer occurs. The net result is that a context switch occurs for each call of Put or Get. This contrasts markedly with the behavior of the protected object where a context switch occurs for every three calls of Put or Get. In conclusion we see that the protected object is much more efficient than a semaphore approach. In this example it as a factor of three better regarding context switches and a factor of two better regarding locks. Observe that the saving in context switching overhead depends to some degree on the run-until-blocked scheduling and on the producer and consumer being of the same priority. However, the saving on lock and unlock overheads is largely independent of scheduling issues. The interested reader should also consult [Hilzer 92] which considers the more general bounded buffer and shows that monitors are even worse than semaphores with regard to potential context switches.