Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Path: utzoo!mnetor!uunet!husc6!bloom-beacon!oberon!sdcrdcf!ism780c!ico!cadnetix.UUCP!ted From: ted@cadnetix.UUCP (Ted Smith) Newsgroups: comp.arch Subject: Re: H/W Write Buffers, S/W Synchronization Message-ID: <1112@cadnetix.UUCP> Date: Fri, 13-Nov-87 12:32:57 EST Article-I.D.: cadnetix.1112 Posted: Fri Nov 13 12:32:57 1987 Date-Received: Sun, 15-Nov-87 15:52:00 EST References: Reply-To: ted@cadnetix.UUCP (Ted Smith) Organization: Cadnetix Corp., Boulder, CO Lines: 34 Summary: S/W Synchronization without test-and-set. In article zs01+@andrew.cmu.edu (Zalman Stern) writes: >I think it >is impossible to write correct multi-threaded (asynchronous) code without >some kind of indivisible read-modify-write memory operation. The book Algorithms for Mutual Exclusion Michel Raynal The MIT Press, Cambridge, MA 02142 ISBN 0-262-18119-3 contains many solutions to the mutual exclusion problem. Here is a simple protocol for two processes which is fair (from Peterson G. L. (1981): Myths about the mutual exclusion problem; Inf. Proc. Lett., 12(3), 115-116 The variables flag and turn are shared between the two processes; process i executes the following code (i = 0 or 1 and j = (i + 1) mod 2): var flag : array [0..1] of boolean turn : 0..1 flag[i] := true turn := i wait until (not flag[j]) or (turn = j) < critical section > flag[i] := false -- Ted Smith UUCP: cadnetix!ted Cadnetix Corp. hao!ico!cadnetix!ted 5757 Central Ave. Boulder, CO 80301