THINK FIRST·CODE LATER

← All labs

Interleaving explorer: watch updates get lost

Problem

Two threads A and B each increment a shared counter (initially 0) k times. Each increment is three steps: load (r = counter), add (r = r + 1), store (counter = r). Each thread has its own register r.

Input: first line k, second line a schedule: a string of A and B characters saying which thread executes its next step (it must contain exactly 3k A's and 3k B's; otherwise print Invalid schedule and stop).

  1. Execute the schedule and print one line per step: A load (rA=0), B add (rB=1), A store (counter=1).
  2. Print Final counter: X (expected 2k) and Lost updates: 2k - X.
  3. Enumerate all interleavings of the 6k steps (every schedule with 3k A's and 3k B's), and print All interleavings: N and Final values: v=count ... for every possible final value in increasing order.

Input:

1
ABABAB

Output:

A load (rA=0)
B load (rB=0)
A add (rA=1)
B add (rB=1)
A store (counter=1)
B store (counter=1)
Final counter: 1 (expected 2)
Lost updates: 1
All interleavings: 20
Final values: 1=18 2=2

Data for this lab

Your program reads its data from standard input. Download the file, then give it to your program as shown below. Start with data set 1: its expected output is given.

os7-1-data-1.txt

1
ABABAB
What your program must print for os7-1-data-1.txt
A load (rA=0)
B load (rB=0)
A add (rA=1)
B add (rB=1)
A store (counter=1)
B store (counter=1)
Final counter: 1 (expected 2)
Lost updates: 1
All interleavings: 20
Final values: 1=18 2=2

Run your program first, then open this and compare line by line: your output must contain these lines exactly.

How to give the file to my program

Terminal (macOS, Linux, or Windows Command Prompt), after compiling:

java Main < os7-1-data-1.txt

Windows PowerShell does not understand <:

Get-Content os7-1-data-1.txt | java Main

IntelliJ IDEA: Run → Edit Configurations → Redirect input from. Or simply paste the content of the file into the console when the program waits for input.

Write it here or in your IDE, then paste it. Compile and test it yourself before comparing. Your code stays in your browser — it is never sent to or stored on the server.