Exclusive Access

One important problem in concurrent programming is to ensure exclusive access to shared resources by multiple threads. It is also known as the Mutual Exclusion protocol. A piece of code that needs to be protected from concurrent execution is called a critical section (CS). In order to coordinate access to the CS, application threads use a set of shared variables to send information to each other. These shared variables are distinct from all the variables used by the application code. In practice, the mutual exclusion protocol is implemented as two methods — enterCS and exitCS. When the application needs to execute some code in the CS, it calls enterCS, then executes the CS, then calls exitCS.

For a theoretical analysis of a mutual exclusion protocol one must consider the running application as a whole. Each thread of the application is represented as an infinite loop that repeatedly performs some work unrelated to the CS, which is called a non-critical section (NCS), then calls enterCS, then executes the CS, then calls exitCS, and then the loop repeats. The code inside the NCS and the CS is not relevant; it is considered to perform no operations related to the protocol and does not modify the shared variables used by the protocol.

We consider a system with two concurrently running threads. The threads use a set of shared one-bit variables to implement the mutual exclusion protocol. Each variable can store a value of zero or one that can be read or written by a single instruction. Shared variables are initialized to zero. Each thread has a local pointer to the instruction (IP) that it is going to execute next. Execution starts from the top of the code. During each step of execution one of the threads is arbitrarily chosen, it executes one instruction, and then changes its IP to the next instruction to execute. This infinite sequence of steps is called a history. A history is called legal if either both threads execute infinitely many steps, or just one thread does while the other thread, having taken a finite number of steps, stops with its IP at the NCS.

The table below contains several algorithms in pseudo-code that attempt to implement the mutual exclusion protocol. In this pseudo-code id is 0 for the first thread and 1 for the second. Variables want[0], want[1], and turn are shared between the threads to implement the mutual exclusion protocol. Lines marked with "+" implement enterCS, lines marked with "-" implement exitCS. The NCS() and CS() lines are placeholders for some code that works inside the non-critical and critical sections respectively and is not relevant for this problem.

• loop while
• (turn == 1 - id) CS()

• turn <- (1 - id) end loop | loop forever NCS()

• want[id] <- 1
• loop while
• (want[1 - id] == 1) CS()

• want[id] <- 0 end loop | loop forever NCS()

• want[id] <- 1
• turn <- (1 - id)
• loop while
• (want[1 - id] == 1 and

• turn == 1 - id)
  

  CS()

• want[id] <- 0 end loop

The task is to figure out whether the given algorithm satisfies three important properties:

- The algorithm satisfies *mutual exclusion* if in any legal history the CS is not executed concurrently by two threads (that is, there is no step where the IP of both threads is at the CS).
- The algorithm satisfies *deadlock freedom* if any legal history has infinitely many executions of the CS.
- The algorithm satisfies *starvation freedom* if in any legal history a thread that executes infinitely many steps has infinitely many executions of the CS.

The property of mutual exclusion is trivial. An algorithm that simply loops forever doing nothing will satisfy it. The sample algorithms above all satisfy mutual exclusion, but the first two fail to achieve deadlock freedom. Algorithm 3 (originally created by Gary Peterson) satisfies all three properties.

The input starts with a line containing two integers m1 and m2, where mi is the number of lines of code for the i-th thread (2 ≤ mi ≤ 9). It is followed by m1 lines with the code for the first thread and m2 lines with the code for the second thread.

The code for each thread contains one instruction per line. An instruction starts with an integer line number from 1 to mi (lines are numbered in ascending order and are included to aid readability), followed by an instruction mnemonic, followed by a list of instruction arguments, all separated by spaces. The last arguments of an instruction represent the line numbers of the next instructions to execute (NIP — from 1 to mi). There are three variables shared between the threads — A, B, and C. The instruction mnemonics are:

• NCS — non-critical section placeholder. Its single argument is NIP.
• CS — critical section placeholder. Its single argument is NIP.
• SET — write a value to a shared variable. It has three arguments v, x, and g, where v is the variable to write (A, B, or C), x is the value to write (0 or 1), and g is NIP.
• TEST — read and test the value of a shared variable. It has three arguments v, g0, and g1, where v is the variable to read (A, B, or C), g0 is NIP if the value of the variable is zero, and g1 is NIP if the value of the variable is one.

NCS and CS appear in the code of each thread exactly once. The code may or may not represent a simple loop, but is guaranteed to alternate executions of the CS and the NCS by one thread; that is, in every legal history two executions of the CS by one thread always have an NCS execution by the same thread in between and, vice versa, two executions of the NCS by one thread have a CS execution by the same thread in between.

Output a string of three letters. The letters represent the properties of mutual exclusion, deadlock freedom, and starvation freedom, in that order. Output the letter Y if the corresponding property is satisfied and N otherwise.