Test 1 Review A: Questions

R1a.1.

Both a thread and a process are abstractions provided by the operating system for executing program code. How are the two concepts different?

R1a.2.

Name and explain two reasons that threads are a useful in programming.

R1a.3.

Suppose we are writing a Web server. Explain how threads would be useful for our program, and describe why they are useful in this context.

R1a.4.

Complete the below Java program so that two threads are executing. One thread should execute the following code to continually update total.

for (int i = 1; true; i++) total += i;

The other thread should execute the following code to periodically display the current total.

while (true) {
    System.out.println(total);
    try { Thread.sleep(40); } catch (InterruptedException e) {}
}
public class Counter implements Runnable {
    static int total = 0;

    // your code here

    public static void main(String[] args) {

        // your code here

    }
}

Hint: The main method runs in its own thread. After it initiates a thread for one of the tasks, main can continue on to perform the the other task in its own thread.

R1a.5.

Modify the two program below so that it allows the user to type “begin” to initiate a background counter and “end” to stop the currently running count. (Don't worry about the possibility that the user might type “begin” while counting is in progress or “end” when no counting is ongoing.)

The below transcript illustrates how the program should work.

begin
1
2
3
4
5
end
begin
1
2
3
end

The following is code for displaying a counter as it increments each second.

while (true) {
    ++curCount;
    System.out.println(curCount);
    try { Thread.sleep(1000); } catch (InterruptedException e) {}
}

(Your program should not use any deprecated methods from the Thread class. If you stick to what we discussed in class, this won't be a problem for you.)

import java.util.Scanner;

public class Counter implements Runnable {


    public void run() {


    }

    public void doMain() {
        Scanner user = new Scanner(System.in);
        while (true) {
            String line = user.nextLine();
            if (line.equals("begin")) {


            } else {


            }
        }
    }

    public static void main(String[] args) {
        Counter c = new Counter();
        c.doMain();
    }
}
R1a.6.

Define the following terms as they relate to processes and threads.

  1. race
  2. deadlock
R1a.7.

One of the downsides to locking-based systems is priority inversion. Explain what this is.

R1a.8.

What is an advantage of using Java's ConcurrentHashMap class (from java.util.concurrent) rather than using a simple HashMap with a lock obtained for each access (such as would be constructed with Collections.synchronizedMap(new HashMap()))?

R1a.9.

For the below Java program, suppose we have two threads, a and b, where a executes the runA method and b executes the runB method. Give an example of code for runA and runB which could result in deadlock between the two threads.

public class Deadlock {
    private Object lockA;
    private Object lockB;

    public void runA() {

        // your code here

    }
    public void runB() {

        // your code here

    }
}
R1a.10.

Below is a class representing a figure on a screen. Suppose one thread often calls draw whenever the figure needs to be painted onto the screen, and another thread calls shift when it is time to shift the figure. Describe a specific situation where this code misbehaves, and modify the code to repair the problem.

public class Sprite {
    private int x = 100;
    private int y = 100;

    public void draw(Graphics g) {
        g.setColor(Color.black);
        g.fillOval(x - 10, y - 10, 20, 20);
        g.setColor(Color.white);
        g.fillOval(x -  9, y -  8, 16, 16);
    }

    public void shift(int dx, int dy) {
        x += dx;
        y += dy;
    }
}
R1a.11.

Suppose we have two threads using the below class. One frequently calls advance to advance the computation of primes, while another frequently calls output to output the current information.

  1. Describe a situation in which output may display erroneous information.

  2. Edit the code to fix this. Your fix must allow a thread to execute output even when another thread is inside the isPrime method.

public class PrimeCounter {
    private int lastChecked = 1;
    private int primesFound = 0;

    public void advance() {
        if (isPrime(lastChecked + 1)) {
            lastChecked++;
            primesFound++;
        } else {
            lastChecked++;
        }
    }

    public void output() {
        System.out.println(primesFound + " primes <= " + lastChecked);
    }

    private boolean isPrime(int n) {
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) return false;
        }
        return true;
    }
}
R1a.12.

Below is a class for representing a long-term computation. It attempts to implement two methods.

boolean process()

Performs the long-term computational process, returning true when it finishes successfully or false if it had to abort because of the following method.

void abort()

Initiates an abort of the computation if the computation is in progress.

class LongProcess {
    private boolean abortRequested = false;
    private boolean inProcess = false;
    private int value;

    public boolean process() {
        inProcess = true;
        value = 0;
        while (!abortRequested && value >= 0) {
            value++; // (just a placeholder for
                     // long-term computation)
        }
        inProcess = false;
        boolean ret = !abortRequested;
        abortRequested = false; // reset for future
        return ret;
    }

    public void abort() {
        if (inProgress) {
            abortRequested = true;
        }
    }
}

  1. Assuming that only one thread calls process at a time, and only one thread calls abort, describe a situation where the given attempt fails to work as specified.

  2. Repair the code so that it works correctly in all situations; you can simply indicate your modifications in the code above. Your repairs should not depend on the specific characteristics of the long-term computation (in this case, this computation continues incrementing i until it reaches a negative number).

R1a.13.

Explain what happens when a program calls the wait method inherited from the Object class in Java.

R1a.14.

Consider the following fairly useless Java program that spawns a thread and then displays the string held within that thread.

public class Useless implements Runnable {
    private String message = null;

    public void run() {
        message = "done.";

        // your code here
    }

    public void doMain() {
        // your code here

        System.out.println(message);
    }

    public static void main(String[] args) {
        Useless u = new Useless();
        new Thread(u).start();
        u.doMain();
    }
}

As it is, it could be that doMain displays message before run places a value there. Using wait and notifyAll, modify the program so it guaranteed to display the message placed by run, without resorting to busy-waiting. (The main thread should not alter message in any way, other than the null that already placed there.)

R1a.15.

The following is a skeleton of a Web server that creates a thread in response to each request, but it tries to ensure that no more than 5 threads are responding at any time.

public class WebServer {
    private class Responder implements Runnable {
        public void run() {
            // (omitted) receive request

            // (omitted) send response to client

            // tell "main" we are done
            numResponders--;
            synchronized (lock) {
                lock.notifyAll();
            }
        }
    }

    private int numResponders = 0;
    private Object lock = new Object();

    private void doMain() {
        // (omitted) start the server listening
        while (true) {
            // (omitted) accept connection from client

            // wait until # client threads is low
            synchronized (lock) {
                while (numResponders >= 5) {
                    lock.wait();
                }
            }
            numResponders++;

            // start thread to service client
            Responder responder = new Responder();
            // (omitted) initialize responder
            new Thread(responder).start()
        }
    }

    public static void main(String[] args) {
        new WebServer().doMain();
    }
}

This code is buggy: The thread executing “main” could end up waiting when fewer than 5 responding threads are active, or this thread could end up having more than 5 active responding threads. Explain how this could happen, and explain how to fix the bug.

R1a.16.

Below is an attempt to implement a Lock class so that threads can reserve an abstract lock (instead of using the built-in monitors). Unfortunately, it doesn't prevent two functions from getting the lock simultaneously.

Using the wait() and notifyAll() methods, add code so that only one thread can get the lock at a time; other threads wanting a lock will stall until the lock becomes available.

public class Lock {
    private boolean isLocked = false;

    public void getLock() {


        isLocked = true;


    }
    public void releaseLock() {


        isLocked = false;


    }
}
R1a.17.

The following skeleton describes a Java class with two methods, awaitRelease and release.

public class ThreadHolder {

    // your code here

    public void awaitRelease() {

        // your code here

    }

    public void release(int n) {

        // your code here

    }
}

Using wait and notifyAll, complete the outlined methods so they work as follows: When a thread calls the awaitRelease method, the thread should stall indefinitely within the method; when a thread calls release given some parameter n, that many threads stalled in the awaitRelease method should continue by returning from the awaitRelease method. (Do not worry about what happens if there are fewer than n threads in awaitRelease at that time.)

Test 1 Review A: Solutions

R1a.1.

Resources, like memory and file descriptors, are allocated independently to processes, whereas a thread shares resources with other threads. In fact, you can think of a thread as something that is part of a process — there are several processes that are currently alive, each of them will include one or more threads that are alive. (If you prefer an analogy, you can think of this relationship like being that between families and individuals: Each family has its own set of resources, which is shared among individuals, but the family has no identity without at least one person in it.)

R1a.2.

  • The programmer can conceptualize a procedure as doing one thing at a time, even though the process will actually be doing many things simultaneously.

  • Threads use less system resources than separate processes.

  • A process can continue perform computation during long I/O tasks (even when a system call is blocked).

  • A multi-threaded process can run on multiple CPUs/cores simultaneously, whereas a single-threaded process only runs on one CPU/core at any time.

R1a.3.

For good performance, a Web server must communicate with many browsers simultaneously, and it is natural to have a single thread handle for each browser connection to handle that one-on-one communication. Implementing the Web server as a single process without threads requires the programmer to write code that switches between discussions among browsers, which is difficult and conducive to programmer errors. Alternatively, one might implement the Web server to create a new process for each Web browser connection, but the high overhead of process creation would damage the program's efficiency, and multiple processes would interfere when the browsers' might share information. [This solution includes three different reasons why threads are useful, but one was sufficient.]

R1a.4.
public class Counter implements Runnable {
    private int total = 0;

    public void run() {
        for (int i = 1; true; i++) total += i;
    }

    public void doMain() {
        while (true) {
            System.out.println(total);
            try { Thread.sleep(40); } catch (InterruptedException e) {}
        }
    }

    public static void main(String[] args) {
        Counter c = new Counter();
        new Thread(c).start();
        c.doMain();
    }
}
R1a.5.
import java.util.Scanner;

public class Counter implements Runnable {
    private boolean stopped = false;

    public void run() {
        int curCount = 0;
        while (!stopped) {
            ++curCount;
            System.out.println(curCount);
            try { Thread.sleep(1000); } catch (InterruptedException e) {}
        }
    }

    public void doMain() {
        Scanner user = new Scanner(System.in);
        while (true) {
            String line = user.nextLine();
            if (line.equals("begin")) {
                stopped = false;
                new Thread(this).start();
            } else {
                stopped = true;
            }
        }
    }

    public static void main(String[] args) {
        Counter c = new Counter();
        c.doMain();
    }
}
R1a.6.

  1. A race occurs when the behavior of a program depends on the scheduling of concurrently running processes or threads.

  2. Deadlock occurs when there is a set of processes or threads waiting on locks held by each other. For example, if one thread holds a lock on a and wants a lock on b, and another thread holds a lock on b and wants a lock on a, there is deadlock.

R1a.7.

In systems where threads can be given different priorities, locking can undermine the priority system whenever a high-priority thread desires a lock held by a low-priority thread: Either the system must temporarily grant the low-priority thread a high priority so that it can finish its work with the lock, or else the high-priority thread will be stalled while the low-priority thread completes its work.

R1a.8.

Both prevent conflicts between threads attempting to simultaneously access to the HashMap. However, the single-lock HashMap will lead to worse performance, since it will permit only one thread at a time to access the HashMap, whereas a ConcurrentHashMap will allow simultaneous access when the requests don't conflict (such as when the requests map to different buckets of the hash table).

R1a.9.
public class Deadlock {
    Object a;
    Object b;

    public void runA() {
        synchronized (lockA) {
            synchronized (lockB) {
                System.out.println("I'm A");
            }
        }
    }
    public void runB() {
        synchronized (lockB) {
            synchronized (lockA) {
                System.out.println("I'm B");
            }
        }
    }
}

In this example, runA could get a lock on lockA, and then a context-switch could allow runB to get a lock on lockB. When runB then tries to get a lock on lockA, it will have to wait until runA releases its lock. And runA will not be able to continue until runB releases its lock. We have deadlock.

R1a.10.

A thread in draw could draw the first oval and — before it draws the second inscribed in it — could call and complete shift. As a result, the second oval drawn by draw would not be in a position consistent with the position of the first oval.

One possible solution would be to add a lock instance variable.

private Object lock = new Object();

Then we would modify draw and shift to access x and y only within a synchronized block on lock. This way, a thread must acquire a lock before accessing these variables.

    public void draw(Graphics g) {
        int myX;
        int myY;
        synchronized (lock) {
            myX = x;
            myY = y;
        }
        g.setColor(Color.black);
        g.fillOval(myX - 10, myY - 10, 20, 20);
        g.setColor(Color.white);
        g.fillOval(myX -  9, myY -  8, 16, 16);
    }

    public void shift(int dx, int dy) {
        synchronized (lock) {
            x += dx;
            y += dy;
        }
    }

(A shorter solution would simply modify draw so that its full body is in a synchronized block. However, this holds the lock longer than necessary, so the above implementation would be preferable.)

R1a.11.

  1. A thread could call output while the other thread is between the “lastChecked++;” and “primesFound++;” lines of advance, in which case it would display a count that is one less than it ought to be.

  2. Add a lock instance variable.

    private Object lock = new Object();

    Then modify advance to add a synchronized block around these two lines.

            synchronized (lock) {
                lastChecked++;
                primesFound++;
            }

    Also, put the contents of the output method into a synchronized block.

        public void output() {
            synchronized (lock) {
                System.out.println(primesFound + " primes <= " + lastChecked);
            }
        }
R1a.12.

  1. The aborting thread could determine that a thread is currently processing, and then a context switch could occur before that thread sets the abortRequested variable. The thread in process could then complete that method during its time slice, returning that it was not aborted. Then the aborting thread could pick up the CPU again and set abortRequested to true. Now a thread that later enters process will be aborted immediately.

    Another problem is that the process thread can complete the process normally, and just as it reaches the inProcess = false; line, the aborting thread executes the abort method, which sets abortRequested to true. In this circumstance, the processing thread would return false even though the thread actually did complete the computation successfully.

  2. To fix the first problem, we first add a lock instance variable.

    private Object lock = new Object();

    Then we place a synchronized block around the following in the process method.

            synchronized (lock) {
                inProcess = false;
                boolean ret = !abortRequested;
                abortRequested = true; // reset for future
                return ret;
            }

    Also, we use a synchronized block in the abort method.

        public void abort() {
            synchronized (lock) {
                if (inProcess) {
                    abortRequested = true;
                }
            }
        }

    Repairing the second problem is more challenging… To repair this problem, we'll change the process method to the following.         while (value >= 0) {
                synchronized (lock) {
                    if (abortRequested) { // see if abort is requested
                        inProcess = false;
                        abortRequested = false;
                        return false;
                    }
                }
                value++; // (just a placeholder for
                         // long-term computation)
            }
            synchronized (lock) {
                inProcess = false; // we completed successfully
                abortRequested = false; // cancel any abort request
            }
            return true;

    We would keep the synchronized block in the abort method. I'm not expecting that anybody would give this solution, however.

R1a.13.

The thread that calls the wait method releases the lock on which wait was called. The machine then puts it into a wait queue for this object, so that the thread is stalled within the method. It is not removed from this object's wait queue until somebody calls notify or notifyAll on the object, at which time the thread stalls until it can reacquire its lock on the object. Once the thread gets this lock, the thread returns from the wait method.

R1a.14.
public class Useless implements Runnable {
    private String message = null;
    private Object lock = new Object();

    public void run() {
        message = "done.";
        synchronized (lock) {
            lock.notifyAll();
        }
    }

    public void doMain() {
        synchronized (lock) {
            while (message == null) {
                try { lock.wait(); } catch (InterruptedException e) { }
            }
        }
        System.out.println(message);
    }

    public static void main(String[] args) {
        Useless u = new Useless();
        new Thread(u).start();
        u.doMain();
    }
}
R1a.15.

If two responders get to the numResponders-- line simultaneously, they could end up decrementing numResponders by a total of just one (if both load the current value of numResponders into a register, then store that value less one back into memory). Similarly, if doMain reaches numResponders++ at the same time that a responder gets to numResponders--, then either one of these statements may end up having no effect.

The solution is simply to move numResponders-- and numResponders++ into their respective synchronized blocks. For instance, these lines of run would change to:

            synchronized (lock) {
                numResponders--;
                lock.notifyAll();
            }

Alternatively, we could change numResponders to a AtomicInteger object, uing its decrementAndGet and incrementAndGet methods.

R1a.16.
public class Lock {
    private boolean isLocked = false;
    private Object lock = new Object();

    public void getLock() {
        synchronized (lock) {
            while (isLocked) {
                try { lock.wait(); } catch (InterruptedException e) { }
            }
            isLocked = true;
        }
    }
    public void releaseLock() {
        synchronized (lock) {
            isLocked = false;
            lock.notifyAll();
        }
    }
}
R1a.17.
public class ThreadHolder {
    private int released = 0;
    private Object lock = new Object();

    public void awaitRelease() {
        synchronized (lock) {
            while (released <= 0) {
                try { lock.wait(); } catch (InterruptedException e) {}
            }
            --released;
        }
    }

    public void release(int n) {
        synchronized (lock) {
            released += n;
            lock.notifyAll();
        }
    }
}