XML CO538 Anonymous Questions and Answers Keyword Index

This page provides a keyword index to questions and answers. Clicking on a keyword will take you to a page containing all questions and answers for that keyword, grouped by year.

To submit a question, use the anonymous questions page. You may find the keyword index and/or top-level index useful for locating past questions and answers.

Keyword reference for barriers

Question 62 (2008):

Submission reference: IN1736

For question 4 of last year's exam (2008):

1. For part a, how would you receive the synchronisation signal from every sync channel in parallel before sending a signal to each ack channel to acknowledge the synchronisation without being able to read each sync signal into a dynamically sized array or read each value to a single variable in parallel?

2. Following on from part a, for part b how would you be able to tell when a certain number of channels have been synchronised?

Answer 62:

You don't have to read every sync channel in parallel ... but, if you do, you can read into local variables (i.e. you don't have to read into different elements of a dynamically declared and sized global array – nor, illegally, into a shared global variable). For instance:

  PROC barrier ([]CHAN BOOL sync?, ack?)
    WHILE TRUE
      SEQ
        PAR i = 0 FOR SIZE snyc?    -- gather in the bids to synchronise
	  BOOL b:
	  sync[i] ? b
        PAR i = 0 FOR SIZE ack?     -- all in, so let everyone go
	  BOOL b:
	  ack[i] ? b
  :

However, both those inner replicated PARs could be SEQs ... think about it, :).

For a partial barrier, where only m (< SIZE sync?) processes engage to trigger their release, we just have to listen out for m bids to synchronise and, then, let those m callers go:

  PROC p.barrier (VAL INT m, []CHAN BOOL sync?, ack?)
    WHILE TRUE
      SEQ
	SEQ i = 0 FOR m             -- gather in m bids to synchronise
	  ALT i = 0 FOR SIZE snyc?  -- gather one bid (from anyone)
	    BOOL b:
	    sync[i] ? b
	SEQ i = 0 FOR m             -- all in, so let m go
	  ALT i = 0 FOR SIZE snyc?  -- release someone (anyone)
	    BOOL b:
	    sync[i] ? b
  :

Note that we don't need to keep account of which processes are synchronising – we assume they all do this via the protocol given in the question – i.e.

  SEQ 
    sync[i] ! TRUE     -- let barrier know we are ready
    ack[i] ! TRUE      -- wait for everyone else

With this protocol, only those m processes whose opening syncs have been accepted will be attempting their acks.

Note also that the bid and release loops (m times) must be done in SEQ this time. They cannot be done in PAR, as in the barrier code above.

Keywords: barriers

Referrers: Question 69 (2010)