printable version
Test 1 Review A
[1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17]
Problem 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?
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.)
Problem R1a.2.
Name and explain two reasons that threads are a useful in programming.
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.
Problem 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.
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.]
Problem 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.
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();
}
}
Problem 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();
}
}
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();
}
}
Problem R1a.6.
Define the following terms as they relate to processes and threads.
- race
- deadlock
A race occurs when the behavior of a program depends on the scheduling of concurrently running processes or threads.
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
aand wants a lock onb, and another thread holds a lock onband wants a lock ona, there is deadlock.
Problem R1a.7.
One of the downsides to locking-based systems is priority inversion. Explain what this is.
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.
Problem 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()))?
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).
Problem 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
}
}
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.
Problem 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;
}
}
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.)
Problem 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.
Describe a situation in which
outputmay display erroneous information.Edit the code to fix this. Your fix must allow a thread to execute
outputeven when another thread is inside theisPrimemethod.
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;
}
}
A thread could call
outputwhile the other thread is between the “lastChecked++;” and “primesFound++;” lines ofadvance, in which case it would display a count that is one less than it ought to be.Add a
lockinstance variable.private Object lock = new Object();Then modify
advanceto add a synchronized block around these two lines.synchronized (lock) {
lastChecked++;
primesFound++;
}Also, put the contents of the
outputmethod into asynchronizedblock.public void output() {
synchronized (lock) {
System.out.println(primesFound + " primes <= " + lastChecked);
}
}
Problem 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
truewhen it finishes successfully orfalseif 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;
}
}
}
Assuming that only one thread calls
processat a time, and only one thread callsabort, describe a situation where the given attempt fails to work as specified.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
iuntil it reaches a negative number).
The aborting thread could determine that a thread is currently processing, and then a context switch could occur before that thread sets the
abortRequestedvariable. The thread inprocesscould 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 setabortRequestedtotrue. Now a thread that later entersprocesswill be aborted immediately.Another problem is that the
processthread can complete the process normally, and just as it reaches theinProcess = false;line, the aborting thread executes theabortmethod, which setsabortRequestedtotrue. In this circumstance, the processing thread would returnfalseeven though the thread actually did complete the computation successfully.To fix the first problem, we first add a
lockinstance variable.private Object lock = new Object();Then we place a
synchronizedblock around the following in theprocessmethod.synchronized (lock) {
inProcess = false;
boolean ret = !abortRequested;
abortRequested = true; // reset for future
return ret;
}Also, we use a
synchronizedblock in theabortmethod.public void abort() {
synchronized (lock) {
if (inProcess) {
abortRequested = true;
}
}
}Repairing the second problem is more challenging… To repair this problem, we'll change the
processmethod 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
synchronizedblock in theabortmethod. I'm not expecting that anybody would give this solution, however.
Problem R1a.13.
Explain what happens when a program calls the
wait method inherited from the Object class in
Java.
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.
Problem 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.)
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();
}
}
Problem 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.
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.
Problem 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;
}
}
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();
}
}
}
Problem 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.)
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();
}
}
}