View Related Documents

Abstract

We examine the ldquogranularityrdquo of statements of the form ldquoawait B rarr Srdquo, where B is a boolean expression over program variables and S is a multiple-assignment. We consider two classes of such statements to have the same granularity iff any statement of one class can be implemented without busy-waiting by using statements of the other class. Two key results are presented. First, we show that statements of the form ldquoawait B rarr Srdquo can be implemented without busywaiting by using simpler statements of the form ldquoawait Xrdquo, ldquoX:= yrdquo, and ldquoy:=Xrdquo, where y is a private boolean variable and X is a shared singler-reader, multi-writer boolean variable. Second, we show that if busy-waiting is not allowed, then there is no general mechanism for implementing statements of the form ldquoawait Brdquo, where B is an N-writer expression, using only assignment statements and statements of the form ldquoawait Crdquo, where C is an (N - 1)-writer expression. It follows from these results that the granularity of waiting depends primarily on the number of processes that may write each program variable.
Work supported, in part, by NSF Contract CCR 9109497, and by the Center of Excellence in Space Data and Information Sciences. The first author was also supported by an award from the General Research Board at the University of Maryland.

Fulltext Preview

Image of the first page of the fulltext document