Zachary Ryan Anderson and David Gay and Mayur Naik

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2009-44

March 29, 2009

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-44.pdf

SharC is a recently developed system for checking data-sharing in multithreaded programs. Programmers specify sharing rules (read-only, protected by a lock, etc.) for individual objects, and the SharC compiler enforces these rules using static and dynamic checks. Violations of these rules indicate unintended data sharing, which is the underlying cause of harmful data-races. Additionally, SharC allows programmers to change the sharing rules for a specific object using a sharing cast, to capture the fact that sharing rules for an object often change during the object's lifetime. SharC was successfully applied to a number of multi-threaded C programs.

However, many programs are not readily checkable using SharC because their sharing rules, and changes to sharing rules, effectively apply to whole data structures rather than to individual objects. We have developed a system called Shoal to address this shortcoming. In addition to the sharing rules and sharing cast of SharC, our system includes a new concept that we call groups. A group is a collection of objects all having the same sharing mode. Each group has a distinguished member called the group leader. When the sharing mode of the group leader changes by way of a sharing cast, the sharing mode of all members of the group also changes. This operation is made sound by maintaining the invariant that at the point of a sharing cast, the only external pointer into the group is the pointer to the group leader. The addition of groups allows checking safe concurrency at the level of data structures rather than at the level of individual objects.

We demonstrate the necessity and practicality of groups by applying Shoal to a wide range of concurrent C programs (the largest approaching a million lines of code). In all benchmarks groups entail low annotation burden and no significant additional performance overhead.

---

BibTeX citation:

@techreport{Anderson:EECS-2009-44,
    Author= {Anderson, Zachary Ryan and Gay, David and Naik, Mayur},
    Title= {Lightweight Annotations for Controlling Sharing in Concurrent Data Structures},
    Year= {2009},
    Month= {Mar},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-44.html},
    Number= {UCB/EECS-2009-44},
    Abstract= {SharC is a recently developed system for checking data-sharing in multithreaded programs. Programmers specify sharing rules (read-only, protected by a lock, etc.) for individual objects, and the SharC compiler enforces these rules using static and dynamic checks. Violations of these rules indicate unintended data sharing, which is the underlying cause of harmful data-races. Additionally, SharC allows programmers to change the sharing rules for a specific object using a sharing cast, to capture the fact that sharing rules for an object often change during the object's lifetime. SharC was successfully applied to a number of multi-threaded C programs.

However, many programs are not readily checkable using SharC because their sharing rules, and changes to sharing rules, effectively apply to whole data structures rather than to individual objects. We have developed a system called Shoal to address this shortcoming. In addition to the sharing rules and sharing cast of SharC, our system includes a new concept that we call groups. A group is a collection of objects all having the same sharing mode. Each group has a distinguished member called the group leader. When the sharing mode of the group leader changes by way of a sharing cast, the sharing mode of all members of the group also changes. This operation is made sound by maintaining the invariant that at the point of a sharing cast, the only external pointer into the group is the pointer to the group leader. The addition of groups allows checking safe concurrency at the level of data structures rather than at the level of individual objects.

We demonstrate the necessity and practicality of groups by applying Shoal to a wide range of concurrent C programs (the largest approaching a million lines of code). In all benchmarks groups entail low annotation burden and no significant additional performance overhead.},
}

EndNote citation:

%0 Report
%A Anderson, Zachary Ryan 
%A Gay, David 
%A Naik, Mayur 
%T Lightweight Annotations for Controlling Sharing in Concurrent Data Structures
%I EECS Department, University of California, Berkeley
%D 2009
%8 March 29
%@ UCB/EECS-2009-44
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-44.html
%F Anderson:EECS-2009-44