20-CS-4003-001 Organization of Programming Languages Fall 2018
Lab Assignment 2

Lambda calculus, Type theory, Formal semantics, Program analysis

Threads and Deadlock

Due: 17 September, 2018 (submit instructions: here)

    To show that threads can be tricky - deadlock states are highly possible.
Lab Problem:
The code below attempts to implement an authentication protocol between two objects, called Boy and Girl. The protocol is asynchronous and works as follows: each "pings" the other; when the other is pinged, it responds with a "confirm".

When the code is executed the following is output:

Girl (ping): pinging Boy
Boy (ping): pinging Girl
due to a deadlock condition: both Boy and Girl are made to wait in ping and no one can invoke confirm. You may have to run the code several times before you see this.

Rework the code to get output that has both the girl and the boy getting confirmation - an example looks like this:

Girl (ping): pinging Boy
Boy (ping): pinging Girl
Girl (ping): asking Boy to confirm
Boy (confirm): confirm to Girl
Girl (ping): got confirmation
Boy (ping): asking Girl to confirm
Girl (confirm): confirm to Boy
Boy (ping): got confirmation
The girl and the boy must get confirmation on every run.

Try not to blow this off by serializing the code (for example, do not have the Girl autheticate the Boy then have the Boy authenticate the Girl). Leave the ping and the confirm methods in the Monitor (although one or both may be modified by you) and do not change the Runner class except, maybe, to add a print statement or two.

Important: the synchronized modifiers before void in ping and confirm in the code below prevent threads from executing inside both ping and confirm concurrently. Your solution must support this property.

The Code:
import java.applet.*;
import javax.swing.*;
import java.awt.*;
import java.awt.event.*;

// Attempt at a simple handshake.  Girl pings Boy, gets confirmation.
// Then Boy pings girl, get confirmation.
class Monitor {
   String name;
   public Monitor (String name) { this.name = name; }
   public String getName() {  return this.name; }
   // Girl thread invokes ping, asks Boy to confirm.  But Boy invokes ping,
   // and asks Girl to confirm.  Neither Boy nor Girl can give time to their
   // confirm call because they are stuck in ping.  Hence the handshake 
   // cannot be completed.
   public synchronized void ping (Monitor p) {
      System.out.println(this.name + " (ping): pinging " + p.getName());
      System.out.println(this.name + " (ping): got confirmation");
   public synchronized void confirm (Monitor p) {
      System.out.println(this.name+" (confirm): confirm to "+p.getName());

class Runner extends Thread {
   Monitor m1, m2;
   public Runner (Monitor m1, Monitor m2) { 
      this.m1 = m1; 
      this.m2 = m2; 
   public void run () {  m1.ping(m2);  }
public class DeadLock {
   public static void main (String args[]) {
      int i=1;
      Monitor a = new Monitor("Girl");
      Monitor b = new Monitor("Boy");
      (new Runner(a, b)).start();
      (new Runner(b, a)).start();