import argparse
from itertools import permutations
from collections import defaultdict
class Thread:
def __init__(self, name, instructions):
self.name = name
self.instructions = instructions
def is_valid_ordering(interleaving):
thread_order = defaultdict(list)
for thread, step, _ in interleaving:
if thread_order[thread] and step < thread_order[thread][-1]:
return False
thread_order[thread].append(step)
return True
def generate_interleavings(threads, allow_order_violation):
instruction_list = [(thread.name, i, instr) for thread in threads for i, instr in enumerate(thread.instructions)]
all_interleavings = list(permutations(instruction_list))
if allow_order_violation:
return all_interleavings
else:
return [i for i in all_interleavings if is_valid_ordering(i)]
def execute_interleaving(interleaving):
x, y = 0, 0
r1, r2 = None, None
local_vars = {'x': x, 'y': y, 'r1': r1, 'r2': r2}
for _, _, instruction in interleaving:
if '=' in instruction:
var, expr = instruction.split('=')
var = var.strip()
expr = expr.strip()
local_vars[var] = eval(expr, {}, local_vars)
return local_vars['r1'], local_vars['r2'], local_vars['x'], local_vars['y']
def interleaving_to_string(interleaving):
return '; '.join([f"[{thread}{step+1}] {instr}" for thread, step, instr in interleaving])
def simulate_dekker(threads, allow_order_violation):
interleavings = generate_interleavings(threads, allow_order_violation)
results = defaultdict(list)
for interleaving in interleavings:
outcome = execute_interleaving(interleaving)
results[outcome].append(interleaving_to_string(interleaving))
return results
def print_summary(results):
print("Possible outcomes:\n")
for outcome, interleavings in results.items():
print(f"r1 = {outcome[0]}, r2 = {outcome[1]}, x = {outcome[2]}, y = {outcome[3]}: {len(interleavings)} interleavings")
for interleaving in interleavings:
print(f" - {interleaving}")
print() # Add a blank line between outcomes for readability
print(f"Total interleavings: {sum(len(interleavings) for interleavings in results.values())}")
def main():
parser = argparse.ArgumentParser(description="Simulate Dekker's memory ordering example")
parser.add_argument('--allow-order-violation', '-a', action='store_true',
help='Allow violations of instruction order within threads')
args = parser.parse_args()
# Define the threads
thread_a = Thread("A", ["x = 1", "r1 = y"])
thread_b = Thread("B", ["y = 1", "r2 = x"])
# Run the simulation
results = simulate_dekker([thread_a, thread_b], args.allow_order_violation)
# Print the summary
print_summary(results)
if __name__ == "__main__":
main()
