If a Java thread moves into the terminated state, it simply means that the thread is done running. If an operating system thread was associated with the Java thread object, it might get cleaned up. However, the Java object still exists, and methods can be called on it. Many will work fine; for example, no one is stopping you from sticking a method that prints "Hello, World" inside a thread object: you can call that anytime, regardless of the state of the thread. Some methods might throw an IllegalStateException or similar, as advertised, but the point is there is nothing magical about a thread terminating, because as long as the thread object is reachable, you can call methods on it.
There is no way to tell at compile time which thread will own an object's monitor.
Suppose the compiler had to compile
class C {
void f() {notify();}
}
What should it do? Because this class can be compiled and stuck in a library and used 100 years in the future the compiler has absolutely no idea how this class will be used. Someone could do this:
C c = new C();
synchronized (c) {
c.f();
}
(which would be fine) and someone else could do this
new C().f();
(which would cause an exception to be thrown). Monitor ownership is a runtime notion, not a compile time one.
Say there were three threads in the system, the current
maximum value of the counter is 10.
Thread A executes:
/* A1 */ c.add(8);
/* A2 */ c.add(4);
Thread B executes:
/* B1 */ c.subtract(9);
Thread C executes:
/* C1 */ c.add(2);
/* C2 */ c.add(5);
The order of execution could go something like this:
A1 (value = 0, A sets it to 8)
A2 (value = 8, A tries to make it 12 so gets blocked)
B1 (value = 8, B tries to make it -1 so gets blocked)
C1 (value = 8, C sets it to 10)
(*)
now at this point, since we just call notify(), the system can
choose to release EITHER A or B, we don't know which. Let's
say that it chose to release A.
A2 (value = 10, A tries to make it 14 so gets blocked)
C2 (value = 10, C tries to make it 15 so gets blocked)
Deadlock!
But if we had used notifyAll(), then at point (*) A and B both get
notified, then compete for the lock. If A gets it first, it immediately
reblocks trying to increment the counter to 14, but and releases
the lock. Now B can pick it up and decrement the counter to 1,
which notifies A. A and C can now both complete (in either order)
so there is no deadlock.
Number the philosophers clockwise from p0..p4 such that p0 is the one that tries for the right stick first. Number the chopsticks c0..c4 such that ci is to the left of pi.
Assume the system is deadlocked. Therefore ALL philosophers are blocked waiting for a chopstick. Therefore philosopher p1 is blocked. There are two cases to consider. Either p1 is waiting for her first (left) chopstick, c1, or her second chopstick (right) chopstick, c0.
Thus if we assume the system is deadlocked, then it is not deadlocked. Therefore deadlock is impossible.
Missing content
------------------------------------------------------------------------------
-- livelock.adb
--
-- Demonstrates a possible livelock condition. Two draftspeople, Alice
-- and Bob, each require a pen and a ruler to draw. They'll each try to
-- grab one and if successful, hold it for a few seconds, then try to
-- get the other; if a draftsperson can't get the second he or she gives
-- up the first one and tries again for both in the same manner. If the
-- person does successfully get the second instrument, that person can
-- draw and will then finish.
--
-- It's possible that this application will finish, but the stupid
-- obtaining and releasing of the drafting tools is most likely, and
-- could in theory run forever.
------------------------------------------------------------------------------
with Ada.Text_IO;
use Ada.Text_IO;
procedure Livelock is
type Employee_Name is (Alice, Bob);
protected type Tool is
entry Use_It;
procedure Done;
private
In_Use: Boolean := False;
end Tool;
task type Drafter(Name: Employee_Name);
protected body Tool is
entry Use_It when not In_Use is begin In_Use := True; end Use_It;
procedure Done is begin In_Use := False; end Done;
end Tool;
Pen: Tool;
Ruler: Tool;
task body Drafter is
procedure Log(Message: String) is
begin
Put_Line(Employee_Name'Image(Name) & " " & Message);
end Log;
begin
while (True) loop
select
Ruler.Use_It;
Log("got ruler, waiting for pen");
delay 5.0;
select
Pen.Use_It;
Log("got pen also, drafting!");
delay 5.0;
Pen.Done;
Ruler.Done;
exit;
else
Log("could not get pen, returning ruler, will try later");
Ruler.Done;
end select;
else
Log("could not get ruler, trying for pen");
select
Pen.Use_It;
Log("got pen, trying for ruler");
delay 5.0;
select
Ruler.Use_It;
Log("got ruler also, drafting!");
delay 5.0;
Ruler.Done;
Pen.Done;
exit;
else
Log("could not get ruler, returning pen, will try later");
Pen.Done;
end select;
else
Log("could not get pen either, will try later");
delay 5.0;
end select;
end select;
end loop;
Log("is finished");
end Drafter;
D1: Drafter(Alice);
D2: Drafter(Bob);
begin
null;
end Livelock;
Missing content
/*****************************************************************************
*
* sieve.cpp
*
* A simple concurrent solution to the problem of finding prime numbers. Here
* the user enters on the command line
*
* sieve <n>
*
* and the program writes out all the prime numbers up to and including n.
* The program works by sucessively sending each number in 2..n through a list
* of tasks; each task in the list corresponds to a prime number. Initially
* the list is empty. As a number goes through the list, each task checks to
* see if the prime number it represents evenly divides the candidate number.
* If it does, the number is composite and its journey through the list is
* over. If it does not, the number continues going through the list. If a
* number passes through the whole list, it is prime, and a new task
* corresponding to this number is allocated at the end of the list.
*
* ======== NOTE ========
*
* THERE IS NO ERROR HANDLING IN THIS YET. On some systems you can generate
* too many threads, and the application will just hang. When there are
* few enough threads, though, everything does get cleaned up nicely.
*
*****************************************************************************/
#include <iostream>
#include <pthread.h>
using namespace std;
/*
* Trivial logger object to serialize writes to cout.
*/
namespace Logger {
pthread_mutex_t stream_lock;
void init() {
pthread_mutex_init(&stream_lock, NULL);
}
void log(int p) {
pthread_mutex_lock(&stream_lock);
cout << p << ' ';
pthread_mutex_unlock(&stream_lock);
}
void destroy() {
pthread_mutex_destroy(&stream_lock);
}
};
/*
* The sieve itself is a linked list of filter threads.
*/
class Filter {
int prime;
int candidate;
Filter* next;
pthread_t thread;
pthread_mutex_t lock;
pthread_cond_t condition;
bool available;
public:
static const int STOP_TOKEN = -1;
Filter(int prime): prime(prime), available(false), next(NULL) {
Logger::log(prime);
pthread_mutex_init(&lock, NULL);
pthread_cond_init(&condition, NULL);
}
~Filter(){
if (next != NULL) delete next;
pthread_mutex_destroy(&lock);
pthread_cond_destroy(&condition);
}
/*
* Pthreads runs non-member functions.
*/
friend void* run(void* arg);
void start() {
pthread_create(&thread, NULL, &run, (void*)this);
}
void join() {
pthread_join(thread, NULL);
}
/*
* Determines what to do with the current candidate: if it's the
* stop token, pass it on to our successor, if any, and return the
* fact that we are ready to quit. If it divisible by our prime,
* forget it. If it's not divisible pass it on if possible. If
* it's not possible, create a new filter for it.
*/
bool testCandidate() {
bool returnValue = true;
pthread_mutex_lock(&lock);
while (!available) {
pthread_cond_wait(&condition, &lock);
}
if (candidate == STOP_TOKEN) {
returnValue = false;
if (next) next->setCandidate(STOP_TOKEN);
} else if (candidate % prime != 0) {
if (next) {
next->setCandidate(candidate);
} else {
next = new Filter(candidate);
next->start();
}
}
available = false;
pthread_cond_signal(&condition);
pthread_mutex_unlock(&lock);
return returnValue;
}
/*
* Accept the next candidate.
*/
void setCandidate(int candidate) {
pthread_mutex_lock(&lock);
while (available) {
pthread_cond_wait(&condition, &lock);
}
this->candidate = candidate;
available = true;
pthread_cond_signal(&condition);
pthread_mutex_unlock(&lock);
}
};
void* run(void* arg) {
Filter* self = static_cast<Filter*>(arg);
while (self->testCandidate()) {
;
}
if (self->next) {
self->next->join();
}
}
int main(int argc, char** argv) {
if (argc != 2) {
cout << "Exactly one commandline argument required\n";
return -1;
}
Logger::init();
Filter* first = new Filter(2);
first->start();
int limit = atoi(argv[1]);
for (int i = 3; i < limit; i++) {
first->setCandidate(i);
}
first->setCandidate(Filter::STOP_TOKEN);
first->join();
delete first;
Logger::destroy();
return 0;
}