class SzymanskisMutex

Based on the Szymanski's Mutual Exclusion Algorithm

Constants

SZYMANSKIS_SLEEP: Larger seconds mean less cycles/second but may result in lower completion

Public Class Methods

mutual_exclusion(concern) { || ... } click to toggle source

Provide a MutEx lock Provide the critical section as a block to this method Different concerns will prevent unrelated code to wait on each other Returns the result of the critical code or nil if something fails

# File lib/szymanskis_mutex.rb, line 41
def mutual_exclusion(concern)
  @@counter[concern] ||= 0
  @@flags[concern] ||= {}

  # Suppose @@counter += 1 is an atomic function
  my_id = @@counter[concern] += 1

  entry_protocol(concern, my_id)
  begin
    result = yield
  ensure
    # If something fails in the critical section release the resource
    exit_protocol(concern, my_id)
    result
  end
end

Private Class Methods

entry_protocol(concern, id) click to toggle source

1: Standing outside waiting room 2: Waiting for other processes to enter 3: Standing in doorway 4: Closed entrance door id is the number of the process entering this section relative to concern

# File lib/szymanskis_mutex.rb, line 65
def entry_protocol(concern, id)
  # Standing outside waiting room
  @@flags[concern][id] = 1

  # Wait for open door
  sleep(SZYMANSKIS_SLEEP) while @@flags[concern].values.any? { |f| f > 2 }

  # Stand in doorway
  @@flags[concern][id] = 3

  # Is another process waiting to enter?
  if @@flags[concern].values.any? { |f| f == 1 }

    # Wait for other processes to enter
    @@flags[concern][id] = 2

    # Wait for a process to enter and close the door
    sleep(SZYMANSKIS_SLEEP) while @@flags[concern].values.all? { |f| f != 4 }
  end

  # Close the entrance door
  @@flags[concern][id] = 4

  # Wait for lower ids to finish exit protocol
  while @@flags[concern].select { |i| i < id }.values.any? { |f| f != 1 }
    sleep(SZYMANSKIS_SLEEP)
  end
end

exit_protocol(concern, id) click to toggle source

Exit the process and if it is the last one in that batch then reopens the door for the next batch id is the number of the process exiting this section relative to concern

# File lib/szymanskis_mutex.rb, line 97
def exit_protocol(concern, id)
  # Ensure everyone in the waiting room has realized that the door
  # is supposed to be closed
  while @@flags[concern].select { |i| i > id }.any? { |f| [2, 3].include?(f) }
    sleep(SZYMANSKIS_SLEEP)
  end

  # Leave. This will reopen door if nobody is still in the waiting room
  @@flags[concern].delete(id)

  # If there are processes still running this concern there is
  # nothing else to do
  return unless @@flags[concern].empty?

  # Prevent counter from increasing indefinitely
  @@counter.delete concern
  @@flags.delete concern
end