- 浏览: 216518 次
- 性别:
- 来自: 北京
文章分类
最新评论
-
dysking:
SWT 和 JFace -
wangyuhfut:
东西不少啊。学习中。。。
一个比较好、中文说明的emacs配置文件 1 -
pacocai:
呵呵!学习,学习~~~不过要说编辑器的话个人更喜欢用VIM,比 ...
一个比较好、中文说明的emacs配置文件 1 -
zhf1zhf2:
这两百多个记起来也不容易啊
英国人是这样背的! -
regex:
试了两次,都是乱码,版本是23.1.1,看来不适合
汉化 Emacs 菜单
June 15, 2009
In my last post I talked about the proposal for the ownership scheme for multithreaded programs that provides alias control and eliminates data races. The scheme requires the addition of new type qualifiers to the (hypothetical) language. The standard concern is that new type qualifiers introduce code duplication. The classic example is the duplication of getters required by the introduction of the const modifier:
class Foo {
private Bar _bar;
public:
Bar get() {
return _bar;
}
const Bar get() const {
return _bar;
}
}
Do ownership annotations lead to the same kind of duplication? Fortunately not. It’s true that, in most cases, two implementations of each public method are needed–with and without synchronization–but this is taken care by the compiler, not by the programmer. Unlike in Java, we don’t need a different class for shared Vector and thread-local ArrayList. In my scheme, when a vector is instantiated as a monitor (shared), the compiler automatically puts in the necessary synchronization code.
Need for generic code
The ownership scheme introduces an element of genericity by letting the programmer specify ownership during the instantiation of a class (just as a template parameter is specified during the instantiation of a template).
I already mentioned that most declarations can be expressed in two ways: one using type qualifiers, another using template notation–the latter exposing the generic nature of ownership annotations. For instance, these two forms are equivalent:
auto foo2 = new shared Foo;
auto foo2 = new Foo<owner::self>;
The template form emphasizes the generic nature of ownership annotations.
With the ownership system in place, regular templates parametrized by types also gain an additional degree of genericity since their parameters now include implicit ownership information. This is best seen in objects that don’t own the objects they hold. Most containers have this property (unless they are restricted to storing value types). For instance, a stack object might be thread-local while its elements are either thread-local or shared. Or the stack might be shared, with shared elements, etc. The source code to implement such stacks may be identical.
The polymorphic scheme and the examples are based on the GRFJ paper I discussed in a past post.
An example
- Stack
A parameterized stack might look like this :
class Stack<T> {
private Node<T> _top;
public:
void push(T value) {
auto newNode = new Node<owner::this, T>;
newNode.init(:=value, _top);
_top = newNode;
}
T pop() {
if (_top is null) return null;
auto value := _top.value();
_top = _top.next();
return value;
}
}
This stack is parametrized by the type T. This time, however, T includes ownership information. In particular T could be shared, unique, immutable or–the default–thread-local. The template picks up whatever qualifier is specified during instantiation, as in:
auto stack = new Stack<unique Foo>;
The _top (the head of the linked list) is of the type Node, which is parametrized by the type T. What is implicit in this declaration is that _top is owned by this–the default assignment of ownership for subobjects. If you want, you can make this more explicit:
private Node<owner::this, T> _top;
Notice that, when constructing a new Node, I had to specify the owner explicitly as this. The default would be thread-local and could leak thread-local aliases in the constructor. It is technically possible that the owner::this could, at least in this case, be inferred by the compiler through simple flow analysis.
Let’s have a closer look at the method push, where some interesting things are happening. First push creates a new node, which is later assigned to _top. The compiler cannot be sure that the Node constructor or the init method don’t leak aliases. That looks bad at first glance because, if an alias to newNode were leaked, that would lead to the leakage of _top as well (after a pop).
And here’s the clincher: Because newNode was declared with the correct owner–the stack itself–it can’t leak an alias that has a different owner. So anybody who tries to access the (correctly typed) leaked alias would have to hold the lock on the stack. Which means that, if the stack is shared, unsynchronized access to any of the nodes and their aliases is impossible. Which means no races on Nodes.
I also used the move operator := to move the values stored on the stack. That will make the stack usable with unique types. (For non-unique types, the move operator turns into regular assignment.)
I can now instantiate various stacks with different combinations of ownerships. The simplest one is:
auto localStack = new Stack<Foo>;
which is thread-local and stores thread-local objects of class Foo. There are no restrictions on Foo.
A more interesting combination is:
auto localStackOfMonitors = new Stack<shared Foo>;
This is a thread-local stack which stores monitor objects (the opposite is illegal though, as I’ll explain in a moment).
There is also a primitive multithreaded message queue:
auto msgQueue = new shared Stack<shared Foo>;
Notice that code that would try to push a thread-local object on the localStackOfMonitors or the msgQueue would not compile. We need the rich type system to be able to express such subtleties.
Other interesting combinations are:
auto stackOfImmutable = new shared Stack<immutable Foo>;
auto stackOfUnique = new shared Stack<unique Foo>;
The latter is possible because I used move operators in the body of Stack.
- Node
Now I’ll show you the fully parameterized definition of Node. I made all ownership annotations explicit for explanatory purposes. Later I’ll argue later that all of them could be elided.
class Node<T> {
private:
T _value;
Node<owner::of_this, T> _next;
public:
void init(T v, Node<owner::of_this, T> next)
{
_value := v;
_next = next;
}
T value() {
return :=_value;
}
Node<owner::of_this, T> next() {
return _next;
}
}
Notice the declaration of _next: I specified that it must be owned by the owner of the current object, owner::of_this. In our case, the current object is a node and its owner is an instance of the Stack (let’s assume it’s the self-owned msgQueue).
This is the most logical assignment of ownership: all nodes are owned by the same stack object. That means no ownership conversions need be done, for instance, in the implementation of pop. In this assignment:
_top = _top.next();
the owner of _top is msgQueue, and so is the owner of its _next object. The types match exactly. I drew the ownership tree below. The fat arrows point at owners.
But that’s not the only possibility. The default–that is _next being owned by the current node–would work too. The corresponding ownership tree is shown below.
The left-hand side of the assignment
_top = _top.next();
is still owned by msgQueue. But the _next object inside the _top is not. It is owned by the _top node itself. These are two different owners so, during the assignment, the compiler has to do an implicit ownership conversion. Such conversion is only safe if both owners belong to the same ownership tree (sometimes called a “region”). Indeed, ownership is only needed for correct locking, and the locks always reside at the top of the tree (msgQueue in this case). So, after all, we don’t need to annotate _next with the ownership qualifier.
The two other annotations can be inferred by the compiler (there are some elements of type inference even in C++0x and D). The argument next to the method init must be either owned by this or be convertible to owner::this because of the assignment
_next = next;
Similarly, the return from the method next is implicitly owned by this (the node). When it’s used in Stack.pop:
_top = _top.next();
the owner conversion is performed.
With ownership inference, the definition of Node simplifies to the following:
class Node<T> {
private:
T _value;
Node<T> _next; // by default owned by this
public:
void init(T v, Node<T> next)
{
_value := v;
_next = next; // inference: owner of next must be this
}
T value() {
return :=_value;
}
Node<T> next() {
return _next; // inference: returned node is owned by this
}
}
which has no ownership annotations.
Let me stress again a very important point: If init wanted to leak the alias to next, it would have to assign it to a variable of the type Node<owner::this, T>, where this is the current node. The compiler would make sure that such a variable is accessed only by code that locks the root of the ownership tree, msgQueue. This arrangement ensures the absence of races for the nodes of the list.
Another important point is that Node contains _value of type T as a subobject. The compiler will refuse instantiations where Node’s ownership tree is shared (its root is is self-owned), and T is thread-local. Indeed, such instantiation would lead to races if an alias to _value escaped from Node. Such an alias, being thread-local, would be accessible without locking.
Comment on notation
In general, a template parameter list might contain a mixture of types, type qualifiers, values, (and, in D, aliases). Because of this mixture, I’m using special syntax for ownership qualifiers, owner::x to distinguish them from other kinds of parameters.
As you have seen, a naked ownership qualifier may be specified during instantiation. If it’s the first template argument, it becomes the owner of the object. Class templates don’t specify this parameter, but they have access to it as owner::of_this.
Other uses of qualifier polymorphism
Once qualifier polymorphism is in the language, there is no reason not to allow other qualifiers to take part in polymorphism. For instance, the old problem of having to write separate const versions of accessors can be easily solved:
class Foo {
private Bar _bar;
public mut_q Bar get<mutability::mut_q>() mut_q
{
return _bar;
}
}
Here method get is parametrized by the mutability qualifier mut_q. The values it can take are: mutable (the default), const, or immutable. For instance, in
auto immFoo = new immutable Foo;
immutable Bar b = immFoo.get();
the immutable version of get is called. Similarly, in
void f(const Foo foo) {
const Bar b = foo.get();
}
the const version is called (notice that f may also be called with an immutable object–it will work just fine).
Class methods in Java or D are by default virtual. This is why, in general, non-final class methods cannot be templatized (an infinite number of possible versions of a method would have to be included in the vtable). Type qualifiers are an exception, because there is a finite number of them. It would be okay for the vtable to have three entries for the method get, one for each possible value of the mutability parameter. In this case, however, all three are identical, so the compiler will generate just one entry.
Conclusion
The hard part–explaining the theory and the details of the ownership scheme–is over. I will now switch to a tutorial-style presentation that is much more programmer friendly. You’ll see how simple the scheme really is in practice.
In my last post I talked about the proposal for the ownership scheme for multithreaded programs that provides alias control and eliminates data races. The scheme requires the addition of new type qualifiers to the (hypothetical) language. The standard concern is that new type qualifiers introduce code duplication. The classic example is the duplication of getters required by the introduction of the const modifier:
class Foo {
private Bar _bar;
public:
Bar get() {
return _bar;
}
const Bar get() const {
return _bar;
}
}
Do ownership annotations lead to the same kind of duplication? Fortunately not. It’s true that, in most cases, two implementations of each public method are needed–with and without synchronization–but this is taken care by the compiler, not by the programmer. Unlike in Java, we don’t need a different class for shared Vector and thread-local ArrayList. In my scheme, when a vector is instantiated as a monitor (shared), the compiler automatically puts in the necessary synchronization code.
Need for generic code
The ownership scheme introduces an element of genericity by letting the programmer specify ownership during the instantiation of a class (just as a template parameter is specified during the instantiation of a template).
I already mentioned that most declarations can be expressed in two ways: one using type qualifiers, another using template notation–the latter exposing the generic nature of ownership annotations. For instance, these two forms are equivalent:
auto foo2 = new shared Foo;
auto foo2 = new Foo<owner::self>;
The template form emphasizes the generic nature of ownership annotations.
With the ownership system in place, regular templates parametrized by types also gain an additional degree of genericity since their parameters now include implicit ownership information. This is best seen in objects that don’t own the objects they hold. Most containers have this property (unless they are restricted to storing value types). For instance, a stack object might be thread-local while its elements are either thread-local or shared. Or the stack might be shared, with shared elements, etc. The source code to implement such stacks may be identical.
The polymorphic scheme and the examples are based on the GRFJ paper I discussed in a past post.
An example
- Stack
A parameterized stack might look like this :
class Stack<T> {
private Node<T> _top;
public:
void push(T value) {
auto newNode = new Node<owner::this, T>;
newNode.init(:=value, _top);
_top = newNode;
}
T pop() {
if (_top is null) return null;
auto value := _top.value();
_top = _top.next();
return value;
}
}
This stack is parametrized by the type T. This time, however, T includes ownership information. In particular T could be shared, unique, immutable or–the default–thread-local. The template picks up whatever qualifier is specified during instantiation, as in:
auto stack = new Stack<unique Foo>;
The _top (the head of the linked list) is of the type Node, which is parametrized by the type T. What is implicit in this declaration is that _top is owned by this–the default assignment of ownership for subobjects. If you want, you can make this more explicit:
private Node<owner::this, T> _top;
Notice that, when constructing a new Node, I had to specify the owner explicitly as this. The default would be thread-local and could leak thread-local aliases in the constructor. It is technically possible that the owner::this could, at least in this case, be inferred by the compiler through simple flow analysis.
Let’s have a closer look at the method push, where some interesting things are happening. First push creates a new node, which is later assigned to _top. The compiler cannot be sure that the Node constructor or the init method don’t leak aliases. That looks bad at first glance because, if an alias to newNode were leaked, that would lead to the leakage of _top as well (after a pop).
And here’s the clincher: Because newNode was declared with the correct owner–the stack itself–it can’t leak an alias that has a different owner. So anybody who tries to access the (correctly typed) leaked alias would have to hold the lock on the stack. Which means that, if the stack is shared, unsynchronized access to any of the nodes and their aliases is impossible. Which means no races on Nodes.
I also used the move operator := to move the values stored on the stack. That will make the stack usable with unique types. (For non-unique types, the move operator turns into regular assignment.)
I can now instantiate various stacks with different combinations of ownerships. The simplest one is:
auto localStack = new Stack<Foo>;
which is thread-local and stores thread-local objects of class Foo. There are no restrictions on Foo.
A more interesting combination is:
auto localStackOfMonitors = new Stack<shared Foo>;
This is a thread-local stack which stores monitor objects (the opposite is illegal though, as I’ll explain in a moment).
There is also a primitive multithreaded message queue:
auto msgQueue = new shared Stack<shared Foo>;
Notice that code that would try to push a thread-local object on the localStackOfMonitors or the msgQueue would not compile. We need the rich type system to be able to express such subtleties.
Other interesting combinations are:
auto stackOfImmutable = new shared Stack<immutable Foo>;
auto stackOfUnique = new shared Stack<unique Foo>;
The latter is possible because I used move operators in the body of Stack.
- Node
Now I’ll show you the fully parameterized definition of Node. I made all ownership annotations explicit for explanatory purposes. Later I’ll argue later that all of them could be elided.
class Node<T> {
private:
T _value;
Node<owner::of_this, T> _next;
public:
void init(T v, Node<owner::of_this, T> next)
{
_value := v;
_next = next;
}
T value() {
return :=_value;
}
Node<owner::of_this, T> next() {
return _next;
}
}
Notice the declaration of _next: I specified that it must be owned by the owner of the current object, owner::of_this. In our case, the current object is a node and its owner is an instance of the Stack (let’s assume it’s the self-owned msgQueue).
This is the most logical assignment of ownership: all nodes are owned by the same stack object. That means no ownership conversions need be done, for instance, in the implementation of pop. In this assignment:
_top = _top.next();
the owner of _top is msgQueue, and so is the owner of its _next object. The types match exactly. I drew the ownership tree below. The fat arrows point at owners.
But that’s not the only possibility. The default–that is _next being owned by the current node–would work too. The corresponding ownership tree is shown below.
The left-hand side of the assignment
_top = _top.next();
is still owned by msgQueue. But the _next object inside the _top is not. It is owned by the _top node itself. These are two different owners so, during the assignment, the compiler has to do an implicit ownership conversion. Such conversion is only safe if both owners belong to the same ownership tree (sometimes called a “region”). Indeed, ownership is only needed for correct locking, and the locks always reside at the top of the tree (msgQueue in this case). So, after all, we don’t need to annotate _next with the ownership qualifier.
The two other annotations can be inferred by the compiler (there are some elements of type inference even in C++0x and D). The argument next to the method init must be either owned by this or be convertible to owner::this because of the assignment
_next = next;
Similarly, the return from the method next is implicitly owned by this (the node). When it’s used in Stack.pop:
_top = _top.next();
the owner conversion is performed.
With ownership inference, the definition of Node simplifies to the following:
class Node<T> {
private:
T _value;
Node<T> _next; // by default owned by this
public:
void init(T v, Node<T> next)
{
_value := v;
_next = next; // inference: owner of next must be this
}
T value() {
return :=_value;
}
Node<T> next() {
return _next; // inference: returned node is owned by this
}
}
which has no ownership annotations.
Let me stress again a very important point: If init wanted to leak the alias to next, it would have to assign it to a variable of the type Node<owner::this, T>, where this is the current node. The compiler would make sure that such a variable is accessed only by code that locks the root of the ownership tree, msgQueue. This arrangement ensures the absence of races for the nodes of the list.
Another important point is that Node contains _value of type T as a subobject. The compiler will refuse instantiations where Node’s ownership tree is shared (its root is is self-owned), and T is thread-local. Indeed, such instantiation would lead to races if an alias to _value escaped from Node. Such an alias, being thread-local, would be accessible without locking.
Comment on notation
In general, a template parameter list might contain a mixture of types, type qualifiers, values, (and, in D, aliases). Because of this mixture, I’m using special syntax for ownership qualifiers, owner::x to distinguish them from other kinds of parameters.
As you have seen, a naked ownership qualifier may be specified during instantiation. If it’s the first template argument, it becomes the owner of the object. Class templates don’t specify this parameter, but they have access to it as owner::of_this.
Other uses of qualifier polymorphism
Once qualifier polymorphism is in the language, there is no reason not to allow other qualifiers to take part in polymorphism. For instance, the old problem of having to write separate const versions of accessors can be easily solved:
class Foo {
private Bar _bar;
public mut_q Bar get<mutability::mut_q>() mut_q
{
return _bar;
}
}
Here method get is parametrized by the mutability qualifier mut_q. The values it can take are: mutable (the default), const, or immutable. For instance, in
auto immFoo = new immutable Foo;
immutable Bar b = immFoo.get();
the immutable version of get is called. Similarly, in
void f(const Foo foo) {
const Bar b = foo.get();
}
the const version is called (notice that f may also be called with an immutable object–it will work just fine).
Class methods in Java or D are by default virtual. This is why, in general, non-final class methods cannot be templatized (an infinite number of possible versions of a method would have to be included in the vtable). Type qualifiers are an exception, because there is a finite number of them. It would be okay for the vtable to have three entries for the method get, one for each possible value of the mutability parameter. In this case, however, all three are identical, so the compiler will generate just one entry.
Conclusion
The hard part–explaining the theory and the details of the ownership scheme–is over. I will now switch to a tutorial-style presentation that is much more programmer friendly. You’ll see how simple the scheme really is in practice.
发表评论
-
Ownership Systems against Data Races 10
2009-10-21 04:04 1221September 22, 2009 Posted by ... -
Spawning a Thread, the D way 8
2009-10-21 04:02 1675September 1, 2009 Posted by B ... -
The Anatomy of Reference Counting 7
2009-10-21 04:01 1101August 19, 2009 Posted by Bar ... -
On Actors and Casting 6
2009-10-21 03:59 1016July 16, 2009 Posted by Barto ... -
What’s Wrong with the Thread Object? 5
2009-10-21 03:58 1133July 7, 2009 Posted by Bartosz ... -
Multithreading Tutorial: Globals 4
2009-10-21 03:57 1215June 23, 2009 Posted by Barto ... -
Race-free Multithreading: Ownership 2
2009-10-21 03:53 942June 2, 2009 Since ownership ... -
Race-free Multithreading 1
2009-10-21 03:41 982Posted by Bartosz Milewski unde ... -
D语言并发编程特性前瞻
2008-08-19 19:49 1465http://wangyuanzju.blog.163.com ...
相关推荐
Java--多线程Java-多线程
Real-Time EmbeddedMultithreading:Using ThreadX and ARM
npm install react-native-multithreading npx pod-install 需要包括的react-native-reanimated版本。 您可以自己打补丁,也可以等到它发布后再发布。 :warning: 警告:这仍然只是概念证明-请勿在生产中使用该库...
`python CVE-2018-2628-MultiThreading.py` Usage: Place the 'ip:port' to be detected into the url.txt file in the same directory. Then run: `python CVE-2018-2628-MultiThreading.py` 运行环境: ...
要么跑 php composer.phar require --prefer-dist grandmasterx/yii2-multithreading "*"或添加 "grandmasterx/yii2-multithreading": "*"到composer.json文件的 require 部分。用法安装扩展后,只需通过以下方式在...
c#.net 多线程编程 <br>I share only those books I have read and considered classic.
实时操作系统 Treadx 详解,原始英文版,详细介绍了 Treadx 的各个接口以及使用;
多线程 leetcode hello-architect :pie::pie::pie:加餐加餐~ ...multithreading-topic : 多线程相关的练习 redis-jedis : redis 基本使用的练习 eshop-inventory : 构建基于 redis 的双写数据一致性问题的解决方案
1,Real-Time Embedded Multithreading Using ThreadX and MIPS 2,Real-Time_Embedded_Multithreading_Using_ThreadX 3,Real-Time Embedded ...5,(CMP) Real-Time Embedded Multithreading--Using ThreadX & ARM
视频压缩多线程适用于我的UROP的Android应用程序要以多线程方式压缩视频-通过牺牲拆分,合并和转换时间,可以大大节省压缩时间。 该版本是未完成的版本。
java7 hashmap源码 multithreading java多线程和多进程 以下内容包含:华东师范大学的多线程讲解 及 马士兵多线程讲解 ...-3.当系统有多个cpu时,可以为多个程序同时服务 ·cpu不再提高频率,而是提高核数: 由于受
mastering-c-multithreading-write-robust-concurrent-and-parallel-applications_compress
3 ■ Sharing data between threads 4 ■ Synchronizing concurrent operations 5 ■ The C++ memory model and operations on atomic types 6 ■ Designing lock-based concurrent data structures 7 ■ ...
java-多线程java-多线程用于多线程的 Java 并发 API。
Java-Multithreading-Tutorial:“正版编码器” YouTube频道Java多线程教程的源代码
ndt_omp 该软件包提供了从pcl派生的OpenMP增强的正态分布变换(和GICP)算法。 将NDT算法修改为对SSE友好并且是多线程的。 它的运行速度比pcl中的原始版本快10倍。 基准测试(在Core i7-6700K上) ...
2015-2016并发和多线程分配的自述文件档案结构bin / ndfs脚本启动应用程序。 图包的build.xml ant脚本doc javadoc。 输入输入文件。 应用程序所需的lib jar文件。 README.txt此文件。 src此项目的源代码。...
3 Modern Architectures 4C++11 Multithreading 5 Advanced C++11 Multithreading 6OpenMP 7 Compute Unified Device Architecture 8 Advanced CUDA Programming 9 Message Passing Interface 10 Unified Parallel ...
LRU多线程 LRU的Java实现
seconf 示例表明,我们可以通过在单独的线程上拆分逻辑任务来加速一批愚蠢的长 3 路数组副本。 这是我的第一个多线程应用程序,我想我会发布我发现的内容。 我通常喜欢通过直接弄乱代码来学习,但我找不到满足我...