CS 345 slide 281 Spring 200512 April 2005Using n-ary semaphoresData invariant for the producer-consumer problem:0 #in – #out #bufferThis invariant can be maintained with two sema-phores, each of which enforces the invariant#enter – #leave s0 .Filling the buffer: #in – #out #buffers0 = #buffer; producer: enter, consumer: leave.Emptying the buffer: #out – #in 0s0 = 0; consumer: enter, producer: leave.In Ada:...filling, emptying : semaphore;critCons, critProd : binary_semaphore;...begin filling.init(size); -- provides notFull service emptying.init(0); -- provides notEmpty serviceendCS 345 slide 282 Spring 200512 April 2005The semaphores’ clientstask producer;task body producer is c : character;begin while not end_of_file loop get(c); filling.enter; critProd.enter; buf(rear) := c; rear := (rear+1) mod size; critProd.leave; emptying.leave; end loop;end producer;task consumer;task body consumer is c : character;begin loop emptying.enter; critCons.enter; c := buf(front); front := (front+1) mod size; critCons.leave; filling.leave; put(c); end loop;end consumer;Safety is assured, but the synchronization code isdistributed among the various clients, and an errorin any client can invalidate the entire system.CS 345 slide 283 Spring 200512 April 2005Synchronization by Rendezvous centralizes thesynchronizationA buffer server-task type:task type buffer is entry insert( c : in character ); entry remove( c : out character);end buffer;task B : buffer;The buffer task’s clients:task producer;task body producer is c : character;begin while not end_of_file loop get(c); B.insert(c); end loop;end producer;task consumer;task body consumer is c : character;begin loop B.remove(c); put(c); end loop;end consumer;CS 345 slide 284 Spring 200512 April 2005task body buffer is …declare variables…begin …initialize variables… loop select when notFull => accept insert(c: in character) do buf(rear) := c; rear := (rear+1) mod size; notFull := front /= succ(rear); notEmpty := true; end insert; or when notEmpty => accept remove(c: out character) do c := buf(front); front := (front+1) mod size; notFull := true; notEmpty := front /= rear; end remove; end select; end loop;end buffer;The buffer task’s clients are free of all responsibilityfor synchronization. An error in one of them cannotbring down the entire system.CS 345 slide 285 Spring 200512 April 2005Another example: a Print-server taskAssumptions:Each client callsprocedure printDoc( theDoc : in array (1..pMax) of Page )The print server callsprocedure printOnePage( aPage : in Page )which sends a single page to the printer.Implementations:procedure printDoc( theDoc : in array (1..pMax) of Page ) pn : integer; pages : integer;begin pn := 1; PrintServer.StartJob; loop PrintServer.PrintPage( theDoc( pn ) ); exit when pn = pMax; pn := pn + 1; end loop; PrintServer.EndJob( pages ); if pn /= pages then error( "a page was not printed" ); end if;end printDoc;CS 345 slide 286 Spring 200512 April 2005task PrintServer is entry StartJob; entry PrintPage( thePage : in Page ); entry EndJob( pages : out integer ); busy : boolean; pageCount : integer;begin busy := false; loop select when not busy => accept StartJob do busy := true; pageCount :=0; end StartJob; or when busy => accept PrintPage( thePage : in Page ) do pageCount := pageCount + 1; printOnePage( thePage ); end PrintPage; or when busy => accept EndJob( page : out integer ) do page := pageCount; busy := false; end EndJob; end select; end loop;end PrintServerCS 345 slide 287 Spring 200512 April 2005Example: a prime-number generatorMethod: “Sieve of Eratosthenes” (c. 200 B.C.)2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 …3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 …5 7 11 13 17 19 23 25 29 31 35 37 41 … counter ( 2) 2,3,4,5,6, …3,4,5,6,7, … filter (2) 3,5,7,9,…5,7,9,11,… filter (3) 5,7,11,13,…Evolution of the primes pipeline:counter (2)2,3,4,5,…counter (2) 2,3,4,5,…filter ( 2) 3,5,…counter (2) 2,3,4,5,…filter ( 2) 3,5,7,9,11,…filter (3) 5,7,11,…CS 345 slide 288 Spring 200512 April 2005The evolution’s agent: task sieve counter ( 2) 2sieve counter(2) 3filter ( 2) 3sieve counter(2) 4,5filter ( 2) 5filter ( 3) 5sieve What does sieve do?nsieve filter (n) sieve In Haskell:> primes = sieve [2..]> sieve (p:ns)> = p : sieve [ n | n<-ns, n `mod` p > 0 ]In Ada…with Ada.Integer_Text_IO, ada.text_io;use
View Full Document
Unlocking...