进程并发编程概念与语言记号详解

3星 · 超过75%的资源需积分: 9 134 浏览量更新于2024-07-31 1 收藏 3.83MB PDF 举报

"《并发编程的概念与符号》是一份经典的教程，由格雷戈里·安德鲁斯和弗雷德·施奈德合著，他们分别来自亚利桑那大学和康奈尔大学计算机科学系。这份文献在过去的十年间积累了丰富的并发编程知识，对进程、进程间通信以及同步机制进行了深入探讨。文章首先定义了并发编程的核心概念，强调了进程在并发系统中的核心作用，它们是执行独立任务的实体，共享系统资源并可能在同一时间内协同工作。通信是进程间相互协作的关键，通过共享数据或消息传递来协调彼此的行为。此外，作者还讨论了同步的概念，即如何控制多个进程的执行顺序，防止数据竞争和死锁等问题。语言表达并发执行的方式和过程交互的规范性语法也被详尽地阐述。这包括了基于共享变量的同步原语，如互斥锁、条件变量等，以及基于消息传递的通信模型，如管道、队列和消息队列。这些语言构造允许程序员在设计并发程序时清晰地表达并管理不同进程间的依赖关系。此外，文章还识别并比较了三种主要类型的并发编程语言：基于进程的模型（如Unix/Linux的线程和进程）、基于事件驱动的模型（如异步I/O和回调函数）以及基于协程的模型（轻量级线程，具有更简洁的上下文切换）。每种模型都有其适用场景和性能特性，理解这些差异有助于开发者选择最合适的工具和技术。最后，作者将并发编程的主题分类，涉及到了编程技术的D.1.3部分（并发编程技术）、编程语言的D.3.3部分（支持并发的结构和特性）、操作系统管理的D.4.1（进程管理）以及组织结构的D.4.7（操作系统组织架构）。这表明并发编程不仅影响到程序设计，还涉及到系统设计和底层操作系统的复杂集成。《并发编程的概念与符号》是一本深入理解并发系统理论与实践的重要参考资料，无论是对初学者还是经验丰富的开发者，都是提升并发编程技能的宝贵资源。"

° G. R. Andrews and F. B. Schneider

tiple instances of each declared process to

be created. By contrast, in other languages

(e.g., PLITS[Feldman, !979] and Ada

[U. S. Department of Defense, 1981]) pro-

cesses can be created at any time during

execution, which makes possible computa-

tions having a variable number of pro-

cesses.

3. SYNCHRONIZATION PRIMITIVES BASED

ON SHARED VARIABLES

When shared variables are used for inter-

process communication, two types of syn-

chronization are useful: mutual exclusion

and condition synchronization.

Mutual ex-

clusion

ensures that a sequence of state-

ments is treated as an indivisible operation.

Consider, for example, a complex data

structure manipulated by means of opera-

tions implemented as sequences of state-

ments. If processes concurrently perform

operations on the same shared data object,

then unintended results might occur. (This

was illustrated earlier where the statement

x :ffi x + 1 had to be executed indivisibly

for a meaningful computation to result.) A

sequence of statements that must appear

to be executed as an indivisible operation is

called a

critical section.

The term "mutual

exclusion" refers to mutually exclusive ex-

ecution of critical sections. Notice that the

effects of execution interleavings are visible

only if two computations access shared var-

ibles. If such is the case, one computation

can see intermediate results produced by

incomplete execution of the other. If two

routines have no variables in common, then

their execution need not be mutually exclu-

sive.

Another situation in which it is necessary

to coordinate execution of concurrent proc-

esses occurs when a shared data object is in

a state inappropriate for executing a partic-

ular operation. Any process attempting

such an operation should be delayed until

the state of the data object (i.e., the values

of the variables that comprise the object)

changes as a result of other processes exe-

cuting operations. We shall call this type

of synchronization

condition synchroniza-

tion. 9

Examples of condition synchroniza-

tion appear in the simple batch operating

system discussed above. A process attempt-

9 Unfortunately, there is no 'commonly agreed upon

term for this.

ing to execute a "deposit" operation on a

buffer (the buffer being a shared data ob-

ject) should be delayed if the buffer has no

space. Similarly, a process attempting to

"fetch" from a buffer should be delayed if

there is nothing in the buffer to remove.

Below, we survey various mechanisms for

implementing these two types of synchro-

nization.

3.1 Busy-Waiting

One way to implement synchronization is

to have processes set and test shared vari-

ables. This approach works reasonably well

for implementing condition synchroniza-

tion, but not for implementing mutual ex-

clusion, as will be seen. To signal a condi-

tion, a process sets the value of a shared

variable; to wait for that condition, a proc-

ess repeatedly tests the variable until it is

found to have a desired value. Because a

process waiting for a condition must re-

peatedly test the shared variable, this tech-

nique to delay a process is called

busy-wait-

ing

and the process is said to be

spinning.

Variables that are used in this way are

sometimes called

spin locks.

To implement mutual exclusion using

busy-waiting, statements that signal and

wait for conditions are combined into care-

fully constructed protocols. Below, we pres-

ent Peterson's solution to the two-pro-

cess mutual exclusion problem [Peterson,

1981]. (This solution is simpler than the so-

lution proposed by Dekker [Shaw, 1974].)

The solution involves an

entry protocol,

which a process executes before entering its

critical section, and an

exit protocol,

which

a process executes after finishing its critical

section:

process P1;

loop

Entry Protocol;

Critical Section;

Exit Protocol;

Noncritical Section

end

process P2;

loop

Entry Protocol;

Critical Section;

Exit Protocol;

Noncritical Section

end

Computing Surveys, Vol. 15, No. 1, March 1983

Concepts and Notations for Concurrent Programming

• 11

Three shared variables are used as follows that the finite progress assuraption is not

to realize the desired synchronization. Boo- invalidated by delays due tO ~synchroniza.

lean variable

enteri

(i -- I or 2) is true when

process

is executing its entry protocol or

its critical section. Variable

turn

records

the name of the next process to be granted

entry into its own critical section;

turn

used when both processes execute their re-

spective entry protocols at about the same

time. The solution is

program

Mute.,:_ExanTph,;

var

enter l, enter2 : Boolean

initial

{false~false);

turn : integer

initial ("PI"); { or

"P2'" }

process

P1;

loop

Entry_Protocol:

enterl

true:

{ announce intent to enter }

turn

:="P2": { set priority to other process }

tion. In general, a synchronization mecha-

nism is

fair

if no process is delayed forever,

waiting for a condition that occurs infinitely

often; it is

bounded fair if

there exists an

upper bound on how longa process will be

delayed waiting for a condition that occurs

infinitely often. The above protocol is

bounded fair, since a process waiting to

enter its critical section is delayed for at

most one execution of the other process'

critical section; the variable

turn

ensures

this. Peterson [1981] gives operational

proofs of mutual exiZlusion, deadlock free-

dom, and fairness; Dijkstra [1981a] gives

axiomatic ones.

Synchronization protocols that use only

wh,e enter2

and

turn = "Re" busy-waiting are difficult to design, under-

do skip; { wait if other process is in and it is his turn !

Critical Section;

stand, and prove correct. First, although

Exit_Protocol:

enterl :=./ah'e;

{ renounce intent to enter }

Noncritical Section

end

end:

process

P2:

loop

Entry_Protocol:

enter2

true;

{ announce intent to enter }

turn

:= "PI'; { set priority to other process ]

while

enterl

and

turn ="PI'"

do skip; { wait if other process is in and it is his turn }

Critical Section:

Exit_Protocol:

enterl :=.false;

{ renounce intent to enter }

Noncritical Section

end

end.

In addition to implementing mutual ex-

clusion, this solution has two other desira-

ble properties. First, it is

deadlock free.

Deadlock

is a state of affairs in which two

or more processes are waiting for events

that will never occur. Above, deadlock

could occur if each process could spin for-

ever in its entry protocol; using

turn

pre-

cludes deadlock. The second desirable

property is

fairness: 1°

if a process is trying

to enter its critical section, it will eventually

be able to do so, provided that the other

process exits its critical section. Fairness is

a desirable property for a synchronization

mechanism because its presence ensures

~°A more complete discussion of fairness appears in

Lehmann et al. [1981].

instructions that make two memory refer-

ences part of a single indivisible operation

(e.g., the TS (test-and-set) instruction on

the IBM 360/370 processors) help, such

instructions do not significantly simplify

the task of designing synchronization pro-

tocols. Second, busy-waiting wastes pro-

cessor cycles. A processor executing a spin-

ning process could usually be ~employed

more productively by running other pro-

cesses until the awaited ~ condition occurs.

Last, the busy-waiting~approach to syn-

chronization burdens the programmer with

deciding both what synchronization is re-

quired and how to provide it. In reading a

program that uses busy-waiting, it may not

be clear to the reader which program vari-

ables are used for implementing synchro-

nization and which are used for, say, inter-

process communication.

3.2 Semaphores

Dijkstra was one of the first to appreciate

the difficulties of using low-level mecha-

nisms for process synchronization, and this

prompted his development of semaphores

[Dijkstra, 1968a, 19681)]. A

semaphore

is a

nonnegative integer-valued variable on

which two operations are defined: P and V.

Given a semaphore s, P(s) delays until

s > 0 and then executes s ~ s

the test

and decrement ar~ executed as an indivis-

ible operation. V(s) executes s :ffi s + 1 as

Compufliig Surveys, VoL 16, No. I, Match 1983

剩余40页未读，继续阅读

msd305

粉丝: 0
资源: 1

进程并发编程概念与语言记号详解

Parallel Programming Concepts and Practice

Concurrent Programming on Windows - Synchronization and Time

parallel programming: concepts and practice pdf

thread runnable

c primer plus

distributed systems: concepts and design 第五版知识点概括

printwriter

In China and western world, people have different time concepts. Which concept do you favor? And why?Please write at least 130 words.

transaction processing: concepts and techniques

最新资源