The following is a ticket Dispenser Mechanism, it's from the article:

"Closing the Complexity Gap between FCFS Mutual Exclusion and Mutual Exclusion By Robert Danek and Wojciech Golab" http://www.cs.toronto.edu/~rdanek/fcfs_disc.pdf

shared variables:

Tickets: array[0..7N-1] of {INUSE, FREE } initially Tickets[0..(3N-1)] = FREE

and Tickets[3N..(7N-1)] = INUSE

lastTicket: 0..7N-1 initially 7N-1

private variables: ticket: 0..7N-1 uninitialized

Implementation of ObtainTicket():

45 first := lastTicket 46 i := 1 // Find upper bound on the smallest FREE ticket.

47 while i < 3N ( Tickets[(first + i) mod 7N] = INUSE do

48   i := min {3N, i x 2 } // Now do binary search to find the ticket.

49 last := first + i 50 while first < last do

51 midpoint := RoundDown[(first + last )/2]

52 if Tickets[midpoint mod 7N] = INUSE then

53 first := midpoint + 1

54 else

55 last := midpoint // At this point first = last holds.

56 ticket := first mod 7N

57 Tickets[ticket ] := INUSE

58 return ticket
Implementation of DoneWithTicket(): // Reset a ticket that was previously active.

59 Tickets[(ticket + 3N) mod 7N] := FREE

60 lastTicket := ticket

Why do we need 7N tickets and not 3N ?, it seems to suffice if every process can run this function and bypass us up to 3 times while process p is inside (It's Guaranteed according to the paper)

The 7N size is not explained in the paper whatsoever..


1 Answer 1


In the paper, it says:

Specification 1.

  • a) The domain of tickets is the set of integers modulo mN for some integer m ≥ 3.
  • b) At any time, the set of tickets that are active is confined to some interval of fewer than mN/2 consecutive integers modulo mN.

According to their specification, the active tickets should be less than half the domain size. So if there are 3N active tickets, the next available integer $m$ that will ensure $3N$ is less than half of $mN$ is $m=7$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.