The Orc language is a concurrency calculus pro- posed to study the orchestration patterns in service oriented computing. Its special features, such as high concurrency and asynchronism make it a brilliant subject for ...The Orc language is a concurrency calculus pro- posed to study the orchestration patterns in service oriented computing. Its special features, such as high concurrency and asynchronism make it a brilliant subject for studying web applications that rely on web services. The conventional se- mantics for Orc does not contain the execution status of ser- vices so that a program cannot determine whether a service has terminated normally or halted with a failure after it pub- lished some results. It means that this kind of failure cannot be captured by the fault handler. Furthermore, such a seman- tic model cannot establish an order saying that a program is better if it fails less often. This paper employs UTP methods to propose a denotational semantic model for Orc that con- rains execution status information. A failure handling seman- tics is defined to recover a failure execution back to normal. A refinement order is defined to compare two systems based on their execution failures. Based on this order, a system that introduces a failure recovery mechanism is considered bet- ter than one without. An extended operational semantics is also proposed and proven to be equivalent to the denotational semantics.展开更多
Modern multiprocessors deploy a variety of weak memory models(WMMs).Total Store Order(TSO)is a widely-used weak memory model in SPARC implementations and x86 architecture.It omits the store-load constraint by allowing...Modern multiprocessors deploy a variety of weak memory models(WMMs).Total Store Order(TSO)is a widely-used weak memory model in SPARC implementations and x86 architecture.It omits the store-load constraint by allowing each core to employ a write buffer.In this paper,we apply Unifying Theories of Programming(abbreviated as UTP)in investigating the trace semantics for TSO,acting in the denotational semantics style.A trace is expressed as a sequence of snapshots,which records the changes in registers,write buffers and the shared memory.All the valid execution results containing reorderings can be described after kicking out those that do not satisfy program order and modification order.This paper also presents a set of algebraic laws for TSO.We study the concept of head normal form,and every program can be expressed in the head normal form of the guarded choice which is able to model the execution of a program with reorderings.Then the linearizability of the TSO model is supported.Furthermore,we consider the linking between trace semantics and algebraic semantics.The linking is achieved through deriving trace semantics from algebraic semantics,and the derivation strategy under the TSO model is provided.展开更多
基金This work was supported by the National High Tech- nology Research and Development Program of China （2012AA011205）, the National Natural Science Foundation of China （Grant Nos. 61361136002, 61321064 and 91118007）, Shanghai Knowledge Service Platform Project （ZF1213） and Shanghai Minhang Talent Project.
文摘The Orc language is a concurrency calculus pro- posed to study the orchestration patterns in service oriented computing. Its special features, such as high concurrency and asynchronism make it a brilliant subject for studying web applications that rely on web services. The conventional se- mantics for Orc does not contain the execution status of ser- vices so that a program cannot determine whether a service has terminated normally or halted with a failure after it pub- lished some results. It means that this kind of failure cannot be captured by the fault handler. Furthermore, such a seman- tic model cannot establish an order saying that a program is better if it fails less often. This paper employs UTP methods to propose a denotational semantic model for Orc that con- rains execution status information. A failure handling seman- tics is defined to recover a failure execution back to normal. A refinement order is defined to compare two systems based on their execution failures. Based on this order, a system that introduces a failure recovery mechanism is considered bet- ter than one without. An extended operational semantics is also proposed and proven to be equivalent to the denotational semantics.
基金supported by the National Key Research and Development Program of China under Grant No.2018YFB2101300the National Natural Science Foundation of China under Grant Nos.61872145 and 62032024Shanghai Collaborative Innovation Center of Trustworthy Software for Internet of Things under Grant No.ZF1213.
文摘Modern multiprocessors deploy a variety of weak memory models(WMMs).Total Store Order(TSO)is a widely-used weak memory model in SPARC implementations and x86 architecture.It omits the store-load constraint by allowing each core to employ a write buffer.In this paper,we apply Unifying Theories of Programming(abbreviated as UTP)in investigating the trace semantics for TSO,acting in the denotational semantics style.A trace is expressed as a sequence of snapshots,which records the changes in registers,write buffers and the shared memory.All the valid execution results containing reorderings can be described after kicking out those that do not satisfy program order and modification order.This paper also presents a set of algebraic laws for TSO.We study the concept of head normal form,and every program can be expressed in the head normal form of the guarded choice which is able to model the execution of a program with reorderings.Then the linearizability of the TSO model is supported.Furthermore,we consider the linking between trace semantics and algebraic semantics.The linking is achieved through deriving trace semantics from algebraic semantics,and the derivation strategy under the TSO model is provided.
