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 autolearn=ham autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,9d303864ae4c70ad X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2004-04-16 11:40:29 PST Path: archiver1.google.com!news1.google.com!sn-xit-02!sn-xit-01!sn-post-02!sn-post-01!supernews.com!corp.supernews.com!not-for-mail From: "Randy Brukardt" Newsgroups: comp.lang.ada Subject: Re: Reprise: 'in out' parameters for functions Date: Fri, 16 Apr 2004 13:38:41 -0500 Organization: Posted via Supernews, http://www.supernews.com Message-ID: <1080a21p0nn482f@corp.supernews.com> References: <5ad0dd8a.0404090512.15af2908@posting.google.com> <5ad0dd8a.0404091828.6e79bb4e@posting.google.com> <8Oadneu6eY9pweDdRVn-hA@comcast.com> <5ad0dd8a.0404151752.4f598e1a@posting.google.com> <5ad0dd8a.0404160338.5a1c9116@posting.google.com> X-Priority: 3 X-MSMail-Priority: Normal X-Newsreader: Microsoft Outlook Express 5.50.4807.1700 X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4910.0300 X-Complaints-To: abuse@supernews.com Xref: archiver1.google.com comp.lang.ada:7221 Date: 2004-04-16T13:38:41-05:00 List-Id: "Wojtek Narczynski" wrote in message news:5ad0dd8a.0404160338.5a1c9116@posting.google.com... ... > I found no examples of data structures with lock granularity lower > than the whole data structure. That's because it would be hard to avoid deadlock in such data structures. (And, as Robert points out, the cost of grabbing a lot of locks would be very high.) The usual way of avoiding deadlock is the use the onion-skin model of locking. But that would serialize the data structure anyway, so there wouldn't be much point in separate locks. To see the problem, consider a tree struction. You'd have to lock many nodes if an insertion caused a rebalancing. If a second task tried to do a nearby insertion at the same time, it also could lock a number nodes. It would be quite likely for the second task to lock the nodes that it is going to insert into, then the first task try to lock the same nodes to do a rebalancing. So it would have to wait. Then the second task would discover that it, too needs to do a rebalancing - but it can't, because the first task already has locked some of the nodes that it needs to change for the rebalancing. Classic deadlock. To avoid this situation, you have to lock the whole data structure. The only place where you could get parallel operation is in modifying the elements once inserted. (And in a library like Ada.Containers, that's done updating a copy of the element, then calling the library to replace the previous element.) Randy.