Computer science: Concurrent systems and applications

The Java language and Object Orientation

Object orientated design

UML

Unified Modelling Language class diagrams represent class hierarchies and systems.

A dashed line with an arrow represents instantiation of indicated class.
A solid line with an arrow represents a class referring to the indicated class.
A solid line with a solid arrow represents the indicated class being superclass of the other(s).

Design patterns

These are a number of common idioms that emerge in object-orientated programming. Studying them allows for shared terminology, better and more stable program organisation and extensibility and encourages reuse.

There are some common themes in design patterns:

It is better to separate code responsible for instantiating classes. (c.f. Abstract factory, Singleton)
Encourage loose coupling, to allow independent reuse. For example, Visitor separates structure traversal from the visitor-specific operation applied at each node.
We can delay commiting to particular functionality at compile-time with a particular organisation of extensions. (e.g. Adapter)

Observer

Also known as the model-view-controller pattern.

Keep a Data class clean.
Observers inherit from the abstract class DataObserver.

abstract class DataObserver 
{ 
    DataSubject subject;
    abstract void update();
}

DataSubject class handles all calls to update the other observers. This class maintains an array of observers, has methods to add an observer and set the value and keeps a reference to the Data class.
Observers can be implemented using interfaces. This means that we don't use up the opportunity to extend a class.
A many-to-many relationship which changes dynamically can exist between subjects and observers.

Flexibility limits compile-time type checking.
Cyclic updates could occur.
Computational overhead. (e.g. consider moving a slider left to right for a colour selector)

Singleton

Ensures that a class can be instantiated exactly once. A private constructor is used.
A static method creates an instance when first called, and saves a reference to this.
There is some flexibility in what is returned (i.e. an inherited class could be returned).
The constraint is in exactly one place.
The multi-threaded case is more tricky.

Abstract factory

How can an application get hold of separate implementations of various interfaces?
Define an abstract superclass called Factory. Code for its methods is in a variety of subclasses.
New families can be provided by giving the consumer a different subclassed instance.
This doesn't solve the problem entirely; which Factory should be used?

Adapter

The client wishes to invoke operations on a target interface which the adaptee does not implement. The adapter can be used with any desired sub-class of the adaptee. We adapt the implementation (which uses the wrong interface) into a different interface, providing a wrapper around the implementation which is compatible with the new class.

Visitor

Consider a data structure with a hierarchy of classes, such as a tree structure. To apply an operation to every node, we write various classes, which extend a subclass called Visitor; these have the property that they provide an implementation for an apply(). The data structure elements then accept(Visitor v) and apply the visitor to their stored data.
Example: Summing the sizes of files stored in a tree directory structure.
Example: BCEL library supports Visitor pattern for traversing a Java class file.

Java object orientation

Arrays and inheritance


class Customer {}
class BusinessCustomer extends Customer {}

Arrays can be inherited as shown:



Customer[] customers = ...
BusinessCustomer[] businessCustomers = ...

customers[0] = new BusinessCustomer(); // This is allowed.
customers[0] = new Customer(); // This is allowed.
businessCustomers[0] = new BusinessCustomer(); // This is allowed.
businessCustomers[0] = new Customer(); // This is not allowed. BusinessCustomer is a subtype of Customer!

Terminology

Composition - using a reference type for a field.
Java arrays (see above) are covariant arrays.
protected methods are always accessible within the package, as well as in subclasses.

Packages

These provide groupings of classes written by a particular user/group or with related functionality.

java.lang is imported automatically.

Nested classes

A nested class is defined within the definition of another.

Inner class - an ordinary class enclosed within a class definition.
Static nested class - an enclosed class which is static.
Nested interface - an interface declared within an enclosing class or interface.
Anonymous inner class - a class defined in-line.

Nested classes are used in the following situations:

to associated classes for readability;
as a shorthand for certain relationships; or
to provide a class with access to private members and local variables from its enclosing class.


class Bus
{
 Engine e;
 class Wheel
 {
  // Here the enclosing class is accessible using Bus.this
 }
}

There is no way for a Bus to get a list of Wheels. Static nested classes and nested interfaces (which are implicity static) are not associated with any instance of the enclosing class (like static fields and methods).

Using anonymous inner classes, an implementation for an interface can be provided inline. The syntax for an anonymous inner class is as follows:


class A
{
 void method1() {
  Object ref = new Object() {
   void method2() {}
  }
}

Java keywords

`abstract` modifier

A class is abstract if marked so, or any of its methods is abstract.
A field cannot be abstract.

`final` modifier

final is used due to providing faster calls and, possibly, security. The modified entity cannot be overridden or subclassed.
The value of a final field is fixed after initialisation, either directly or in every constructor.

`transient` modifier

The marked field will not be sent over the network or saved to an output stream.

`volatile` modifier

The marked field (which cannot be final) will be retrieved from the shared address space whenever it is accessed. For example a static boolean signal in a class with a run() method. It is important that this is not just kept in a processor register whenever it is tested. A change from another thread must propogate into the running thread.
This modifier is rarely seen in practice because the JVM will force a variable out of the cache when it is being locked by a mutex. (i.e. volatile is not necessary for a synchronized field or class)

`interface`

A class which implements an interface must, for each method, either provide an implementation or denote that method as abstract (thereby creating an abstract class).

Java library features

Native methods

The Java Native Interface (JNI) allows native methods to be called from Java. It is useful

to access special facilities only provided in native APIs;
to reuse an existing library (such as a numerical analysis library); or
to optimize a specific part of the application carefully.

However, there are some counterarguments to this last point: modern JVMs use JIT compiling, profile-direct optimization is useful and it is hard to recoup the cost of making a JNI call, including accessing Java objects within it.

The signature of a native method is included in a class defintion. A static initializer (class A {static {...}}) is used to call System.loadLibrary("hello") where a file exists called "hello.so" or "hello.dll". Run javah -jni HelloWorld to create a C header file. The implementation is then put in a separate file with JNIEXPORT void JNICALL Java_HelloWorld_displayHelloWorld(JNIEnv* env, jobject obj) {...}, with jni.h and the generated .h file included. Include files from the SDK installation should be used by the C compiler.

The JNIEnv parameter providers function pointers for various operations: FindClass to access the jclass for a specified name, GetSuperclass to map one jclass to its parent, NewObject to allocate an object and execute its constructor, CallObjectMethod, CallBooleanMethod, CallVoidMethod, ..., to call methods. Similarly named methods are provided to Get...Field. Objects passed to native methods and accessed from native methods cannot be garbage collected. Global references must be created and removed with NewGlobalRef and DeleteGlobalRef.

Class loaders

Class loaders provide a way to supply the JVM with a class definition from another source, such as the network or a dynamically generated class in memory. They take the form of an object derived from java.lang.ClassLoader

The default implementation for a given class loader is to:

Test whether a class is already loaded.
Delegate the loading to a parent class loader.
Call c.findClass(name).

A new implementation of ClassLoader should override the protected findClass(name) method so that the delegation model remains consistent. The new Class object can be created by calling the c.defineClass(name, b, off, len) method to create a new class definition from the specified range of the byte array provided.

Internally, classes are identified by their name and the class loader that created them. If a class A contains a field of type B or its superclass is of that type, the class loader which defined A is requested for B.

The JVM

Garbage collection

Managed memory

Advantages

Less work for programmer, rapid development
Fewer bugs
In some cases: increased runtime control - balanced, so idle time used
Unnecessary for short-lived programs
Increased stability for, e.g., server applications
Multi-threaded: no need to guarantee module responsibility, aids sharing
Lock-free data structure

Disadvantages

Runtime overhead (even for mutex operations)
Programer never thinks about allocation
Described as the antithesis of realtime execution
Less control over the memory foorprint
Difficult to optimise locations for page tables, etc.

GC techniques

Buddy system, mark and sweep, reapers, incremental

Newer implementations use:

Generational collection; objects are classified into short-term and long-term groups.
Parallel collection; multi-processor solution - fewer pauses.
Concurrent collection; GC occurs at the same time as application execution.
Incremental collection; small bursts of collection, e.g. when an object is allocated.

Reachable Objects

Referred to by static field in class
Referred to by local variables in running threads
Still need to be finalized
Referenced by another reachable class

Finalizers

When an object is unreachable, its finalizer can be run. java.lang.Object has

protected void finalize() throws Throwable {}

This allows the object to external resources, such as memory allocated natively, network connections, etc. It is also used in debugging.

If an object is made accessible in the finalizer, it will not be collected.

Finalizer rules:

A finalizer will not be run before an object becomes unreachable.
System.runFinalization() will cause the JVM to try to complete any outstanding finalizations.
There are no rules regarding the thread on which finalization will occur. It could be on a separate processor, a single thread per class or one of the threads performing GC.

It is vital that deadlock is prevented in a finalizer! Defensive programming is essential so that they do not enter endless loops.

Reference objects

These provide a general mechanism for:

scheduling clean-up actions when objects become unreachable via ordinary references;
managing caches in which the presence of an object in the cache should not prevent its garbage collection;
accessing temporary objects which can be removed when memory is low.

These operations are provided in the java.lang.ref.* package.

An extra level of indirection is added by referring to an object via a reference object. The referent is selected at the time of instantiation of the reference object. If a reference to an object is lost an only a reference wrapped in a weak reference remains, the object is eligible for collection: the value returned by get() is then null. The disadvantage of this system is that additional calls to get are required when traversing a data structure. However, this is still simpler than adding an additional type of reference to the language itself.

Reference queues

java.lang.ref.ReferenceQueues can be passed as a parameter to the constructor of a subclass of java.lang.ref.Reference. When an object which is softly, weakly or phantomly reachable is garbage collected, its associated instance of java.lang.ref.Reference is appended to the queue of references in the associated queue. This allows these objects to be recreated. The queue can either be poll()ed or the head of the queue can be removed by remove() which blocks.

Reference types

SoftReferences may be cleared when there is a shortage of memory and the object is no longer reachable by a strong reference.
WeakReferences may be cleared when the object is no longer reachable by soft reference or strong reference. This is useful for hashtables where data can be discarded when no longer in use.
PhantomReference s provide a flexible alternative to finalizers. The phantom reference is enqueued once the object is no longer reachable through strong, soft or weak references and once it has been finalized if necessary. The get() method always returns null. To use this in practice, PhantomReference is subclassed so that clean-up information can be stored. This would only be used with a ReferenceQueue.

Concurrency

Concurrency overview

When multiple threads are created in a Java application, they operate in the same address space.

Separate processes can communicate across their address space boundaries (or possibly across a network)?

The main problems are:

How should shared resources and data be named and referred to by the threads?
How should shared data be represented?
How should access be controlled?
What kinds of failure are possible?

Java supports lightweight concurrency within an application, so that multiple threads run simultaneously. This is useful to simplify code structure and aid interactive response (i.e. with a user interface thread and a backend thread). It is also useful for multiprocessor situations.

One consideration is Java's platform independence. Implementation schemes vary widely, so it is important to write portable code taking into account, for example, the potential absence of preemption.

Processes are the unit of protection and resource allocation. The PCB holds IDs, RAM information, accounting information and references to one or more TCBs.

Threads are the unit of scheduling. TCBs hold state, saved context information, references to a user and kernel stack and scheduling parameters.

Java threads

Subclassing `java.lang.Thread`

The run() method must be overridden. The thread terminates when run() returns. A common pattern is daemonic threads:


while (!this.done)
{
 // ...
}

Calling the start() method actually runs the thread. An application runs until all the threads created in this way have finished their methods. A daemon thread will not prevent the application from exiting: t1.setDaemon(true);

Implement `java.lang.Runnable`

Instantiate two Threads, each time passing an instance of a class which implements java.lang.Runnable. The start() method runs the threads, as before. The same instance can be passed to as many Thread constructors as necessary.

Note that in this case, the code can run on the same object, whereas for the subclassing method above two separate objects are required for two threads.

This way is more flexible because it doesn't use up the single opportunity to subclass. Fields can contain per-thread state.

The `java.lang.Thread` object

The yield() method yields execution to another thread. This is a hint to the system that it should try switching to another thread. Use of this method is vital in non-preemptive systems.

A thread may be interrupted immediately when it blocks. For example if the thread sleep()s. The InterruptedException is thrown in the thread. It is also possible to check for interruption using the isInterrupted() method.

The join(long waitTimeMilliseconds) method causes the current thread to wait until the target thread dies. A method which uses join() must deal with the InterruptedException, either in a throws clause or directly.

The setPriority(...) and getPriority() methods manage the thread's priority. A number of standard levels are available: MIN_PRIORITY, NORM_PRIORITY and MAX_PRIORITY.

It is never correct to control thread execution with shared data using priorities, due to differences in implementations.

Java thread execution

The choice of which thread to execute at a given time is OS and JVM dependent. Preemptive systems with PCBs and TCBs switch between threads during execution. Non-preemptive systems only switch when a thread yields: threads are implemented as part of the JVM.

Priority inversion

This is a liveness problem in priority-based systems.

$P_{low}$ starts and acquires a lock on an object A
The other two processes start.
$P_{high}$ runs since it has the highest priority. It blocks waiting for a lock on A
$P_{med}$ runs, preventing $P_{low}$ from releasing the lock on A and hence $P_{high}$ from running.

The solution is priority inheritance

Every lock has an associated priority $p$ of the highest priority process waiting for it.
The priority of the lock holder is temporarily boosted up to $p$ .
Handoff scheduling can implement this.

The Windows solution is to boost the priority of a thread in a ready-to-run state which has not been run for $\ge 300$ ticks. If so, boost the priority and double the time quantum.

Total blocking delay

The high priority thread can be blocked in two distinct ways:

Direct blocking - the thread waiting for a lock is blocked
Push-through blocking - a thread at a higher priority is blocked by a lower priority thread which has had its priority boosted (at an inherited priority).

The high priority thread can be blocked by each low priority thread for the length of a given critical section in the lower priority thread. A high priority thread can experience push-through blocking for any lock accessed by a lower-priority thread and by a job which has or can inherit a greater or equal priority.

Chains of blocking may limit the bounded and practical performance. This is a problem for real-time systems.

Priority inheritance does not prevent deadlock.

Safety and Liveness

Safety

A system will remain safe if 'nothing bad happens'. This cannot be usually checked by a compiler, unlike type safety.

Invariants are useful in verifying the safety of a system. Consistent object states are ones in which the invariants are satisfied. Ideally, operations should transition the system between consistent states.

It is important, therefore, to ensure that different threads are allowed to access objects in various ways which ensure that consistency is maintained.

Liveness

Per-thread and system-wide liveness are the requirements that something good eventually happens on a given thread and in the entire system.

Problems

Deadlock - a circular dependency between processes managing and using a particular resource. This resource is usually exclusive access to a lock.
Livelock - a thread keeps executing useless code, waiting for a particular lock to become available.
Missed wake-up (wake-up waiting) - a thread misses a notification and remains blocked.
Starvation - a thread waits for a particular resource but never receives it. (e.g. a low-priority thread)
Distribution failures - of nodes or network connections in a distributed system.

Shared objects - counters, hashtables, ..., and mutual exclusion locks.

Field accesses in Java

Field accesses are atomic in general. The exceptions are longs and doubles (one some platforms): these types require multiple reads.

A non-atomic operation may be subject to race conditions, that is, differences in result based on the particular interleaving of thread execution which occurs.

Thread accesses are controlled using the notion of critical regions. These are areas of code in which a particular thread should have exclusive access to a shared data structure.

Race conditions

Careful programming is insufficient to solve the problem of race conditions, because the value of a variable which determines whether the structure is in use may change between when it is tested and when the thread tries to take control by setting it to true itself: the system has then allowed in two threads which may be run in any order.

Mutual Exclusion Locks

Language support is therefore provided, using mutual exclusion locks which are attached to each object. The synchronized keyword is then used to delimit a critical region (which can be an entire method, or a specified scope within a method). synchronized blocks, so no spin is required, and the race condition between testing and setting a busy flag is avoided.

Calling a synchronized method where the lock is already held by another thread causes execution to block. However, multiple threads can call the same method on different objects. Locks are re-entrant: the thread may call one synchronized method from another.

static methods which are marked synchronized associated a mutex with the class rather than the object. The modifier cannot be applied to classes or fields.

Synchronized can be used within a method: synchronized (x) {...}. In this case, the thread takes out a lock on the variable x or blocks until it can do so.

The critical region should be made as small as possible, given performance constraints: mark two sections with an intermediate non-lock-requiring section with synchronized separately, rather than synchronizing the entire method or most of its body.

Mutual exclusion locks and exceptions

If an exception is not caught inside the region/method, the flow of execution leaves the synchronized region - this may entail releasing the lock automatically. The lock will always be removed before executing the catch block. Care must be taken not to make thread-unsafe accesses within the catch block.

Compound data structures: Hashtable

A lock can be applied to the entire hashtable. Advantages: easy to implement, works, good performance under light load (only one lock to deal with). Disadvantages: Poor performance with many threads, as only one operation can proceed at a time, even if it is theoretically possible to run both.

Small locks, for example on each bucket, provide improved performance. It's more difficult to implement the hashtable (resizing).

Dealing with many locks leads to poor performance as well. A balance is required between fine-grained locking and not wasting time juggling locks. There may be deadlock problems.

Deadlock

Thread P runs


synchronized (a)
 synchronized (b)
 {
  ...
 }

and thread Q runs the following:


synchronized (b)
 synchronized (a)
 {
  ...
 }

If either thread P or Q executes its first line, taking a lock out, and is preempted allowing the other thread to execute its first line, a situation of deadlock is reached.

This situation can be shown graphically, with the progress of each thread on each axis and shading to demonstrate that a region is unreachable. Obviously, the line cannot reverse its movement on any axis, so once blocked on each side deadlock is reached.

Conditions for deadlock

A resource request can be refused.
Resources are held while waiting for a resource to become available.
No preemption of resources is permitted.
A cycle of threads exists, such that each holds a lock required by the next process in the cycle.

Deadlock is possible in Java because the first three properties are part of the language and the fourth is a situation which can arise.

Object allocation graphs

Processes are represented by circles. Locks are represented by squares.

A solid arrow to a process from a lock indicates that the lock is currently held by the process. A dashed arrow from a process to a lock represents that the process is requesting that lock.

Using this scheme, cycles can be spotted.

Deadlock detection

Three matrices are required. In each matrix, the cell indicated by the row $i$ and the column $j$ contains a $1$ if the $i$ th thread holds a lock on the $j$ th object. An allocation matrix $A$ has $1$ s where the thread indicated by the row currently holds a lock on the object indicated by the column. The request matrix $R$ has $1$ s where the thread indicated by the row is requesting the lock on the object indicated by the column. The working matrix $W$ is a single row vector which contains $1$ s where an object is available. Wherever a cell does not contain a one, it contains a zero.

Select an unmarked row in the request matrix $R$ such that its request can be fulfilled according to the ones in the working matrix $W$ . If no such row exists, terminate.
Set the working matrix $W = W + A_i$ , so that the working matrix now indicates that those objects previously locked by $A_i$ are assumed to be available. Mark row $i$ in the request matrix.

Rows are marked if they are not part of a deadlocked set.

Using this algorithm, it is possible to detect when deadlock has occurred. Other useful properties are whether it is inevitable or possible.

Deadlock avoidance

Each process identifies the maximum set of resources it might lock ( $C_{ij}$ ).
When a thread $i$ requests a resource, construct a hypothetical allocation matrix in which the request is satisfied and another in which every other thread makes its maximum request.
If these two matrices do not indicate deadlock, the allocation is safe.

This technique may be preferable to deadlock recovery, but has a number of disadvantages: The maximum requests must be known, there is significant runtime overhead, there may be no safe states and object instantiation is dynamic.

Other design techniques can be used to avoid deadlock:

Locking schemes which encourage greater concurrency (MRSW better than mutex).
Do not hold resources while waiting - get all the locks at once.
Lock preemption and rollback (not a primitive in Java with built in locks). Hardware/software transactional memories provide this situation.

The most widely available practical schemes are:

Coalesce locks so that only one ever needs to be held - e.g. one lock for all bank accounts.
Enforce a lock acquisition order - this prevents circular waits.

There is a tradeoff between simplicity of implementation and concurrency.

Internal locking shared objects - queues, MRSW locks, ..., and condition variables.

Limitations of mutexes

No way to wait until a condition is satisfied without using up CPU time in a spin lock, creating race conditions and forcing variables out of the cache with volatile.
No way to enforce additional concurrency controls, e.g. identifying read operations safe for multiple threads, control which thread gets the next access to shared data (e.g. to prioritise updates, choose from FCFS or choose on the basis of scheduling priorities) and have anything more than simple protection from running the code simultaneously.

Waiting until a condition is satisfied


public synchronized removeValue() {
 wait_until(full);
 // If full is false, block the caller atomically with doing the test and release the lock held by this method.
 // Unblock and reacquire lock when full becomes true.
}

This cannot be implemented in Java due to call by value semantics and lack of ability to release a lock.

Condition variables must be used.

Condition variables

Two features not possible in standard Java: a wait() function waits until the condition variable associated with the object is true, releasing the lock and providing a kind of call by reference capability where it would not be possible originally (with a stored boolean field).
As well as wait() we have notify() which selects a thread blocked in wait() at random and releases it. We also have notifyAll() which releases all threads blocked in wait().
wait() always releases the mutual exclusion lock when it is called. wait() can only be called when the calling thread posesses a mutual exclusion lock.

In practice, condition variables are implemented in Java in the Object class. For an object o,

o.wait() - release lock on o (which must be held otherwise we get IllegalMonitorStateException) and block.
o.notify() - unblock exactly one waiting thread, or do nothing if there are none waiting.
o.notifyAll() - unblock all waiting threads, or do nothing if there are none waiting.

There are now two ways to gain a lock: entering a synchronized block and returning from wait().

notify() does not guarantee to wake the longest waiting thread.

Sometimes important to use notifyAll(): one cell buffer can have remover and putter - could wake either type after doing the wait. If notify() were used, could begin waiting indefinitely.

`suspend()` and `resume()`

These deprecated methods are unsafe, as they can lead to deadlock (possibly with locks used internally) and may cause missed wakeup.

Thread-safe design

There are a number of possible approaches to making a structure thread-safe.

Delegation and the adapter pattern: BasicImpl and MTImpl both implement a particular interface. The multi-threaded implementation wraps each operation of the interface in code for multi-threading. The client then accesses the data structure through on of the implementations of the interface.
The interface could be implemented by a basic implementation, which is then extended with a multi-threaded implementation. The client then accesses the interface. Only one instance is required, and delegation may be easier (i.e. use super.operation()). However, separate subclasses are required for each implementation and the composition of wrappers is fixed at compile time.

The actual operation must occur in stages:

Entry protocol - let the thread in once it is safe to do so.
Delegate to the underlying data structure. (This may be either of the schemes above - using the super keyword or accessing an instance of BasicImpl directly.)
Exit protocol - select the next threads to use the data structure.

Clearly, this structure will motivate further separation between concurrency and the data structure.

The separation can be made even more clear by moving all concurrency related code into a separate interface/implementation pair. The MTImpl class becomes even simpler, delegating to the concurrency class (enter() and exit()) and then to the basic implementation. This has clear advantages: the concurrency control is available for separate reuse and only a single MTImpl type class is needed to provide a variety of concurrency schemes (possibly through a factory class).

Multi-threaded hashtable: MRSW

The MRSW interface declares methods for entering and exiting readers and writers. The MTHashTable class implements Dictionary and delegates to some implementation of MRSW.

Consider the following implementation of MRSW:

Count readers and writers.
A reader must wait until there are no writers. A writer must wait until there are no readers or writers.

Using this scheme, it is possible to have multiple readers, but only one writer is allowed at a time.

The enter() method tests on the relevant condition (i.e. numWriters > 0 or (numWriters > 0) || (numReaders > 0)), wait()ing until it is false. At this point a reader or writer is allowed in and the relevant counter is updated.

The exit() method decrements the counters and calls notifyAll(). This wakes up some set of readers and writers.

When all the threads are woken, there may be a performance hit. Only one is going to be allowed to continue anyway, so notify() would be ideal.

Another possible implementation of MRSW is as follows:

Prioritize writers: count readers, writers and waiting writers.
Allow a reader in if there are no waiting writers and no writers. Allow a writer in if there are no readers or writers.
The number of waiting writers must be incremented before checking for writers and readers and decremented after checking for writers and readers.

There is a possible issue if InterruptedException is thrown within the wait() in the enterWriter method: the number of waiting writers is never decremented.

FCFS ordering on waiting threads can be implemented as follows:

Implement CCInterface storing the current turn and the next ticket which will be given (both integers). On entering, threads take a ticket (int myTicket = nextTicket++) and wait while currentTurn < myTicket; then allow that thread to enter.
The exit() method increases currentTurn and notifies all.

This is a very simple implementation. However, there are serious problems.

If a thread is interrupted during wait() then its ticket is lost.
notifyAll() wakes up everything, even though only one is needed.
The integer storing the next ticket may overflow.

If there are many objects in contention, it may be best to have an explicit queue of waiting threads, with the head of the queue being notified.

The queued objects may contain an abandoned entry, which stores whether that item should be ignored (for interrupted threads).

Work out whether longs might overflow.

Splitting locks

Consider a linked queue with possibly concurrent push-to-tail and pop-from-head operations.

Lock the head and last fields of the queue. Lock each entry in the list at its next field.

Lock instances of java.lang.Object to protect the head and tail of the queue.

Low-level synchronization

Implementation of mutual exclusion locks

Hardware support for compare-and-swap (CAS) is necessary. This is an atomic assembly language instruction.

Support in the scheduler for suspending and resuming of threads is required.

CAS can be implemented on the address of a particular field, checking it like a spin-lock - the loop is exited once the value returned by CAS is reset (by some other method). There are some cache issues, and multi-processor performance issues.

To avoid spinning each mutex has a queue of blocked threads waiting on it.

An entering thread tries to use CAS directly.
If it fails, it adds itself to the queue and invokes a suspend operation on the scheduler.
On releasing the lock, the scheduler selects an entry from the list (if it is non-empty) and resumes it. There is a potential issue if the resume() is lost on a thread that has just been selected (e.g. 1. add self to queue, 2. select just added thread, 2. select 1 to run, 1. suspend 1 - wakeup was lost). This means that resume()s must be remembered or thread switching must be disabled in the critical region.

Implementation of condition variables

The condition variable associated with each object stores in private fields a queue of threads that are waiting on it and a mutex to provide atomicity of wait().

wait(m) operates as follows:

Acquire the mutex on this condition variable.
Add this thread to the queue.
Release the mutex on m.
Release the mutex on this condition variable.
Suspend this thread. This is where the waiting actually occurs.
Reacquire the mutex on m.

notify() operates as follows:

Acquire the mutex on this condition variable.
Remove a thread from the queue.
Resume that thread.
Release the mutex on this condition variable.

As before, in general resumptions are remembered to avoid lost wake-up problems. (Also deal with exceptions in a real implementation.)

Alternative concurrency abstractions - monitors, active objects.

Semaphores

Semaphores provide basic operations on which mutexes and condition variables can be built.

A counting semaphore would take the form of a class definition would two native methods:

P() (wait) decrements the stored value and if the result is zero or less unblocks a thread.
V() (signal) increments the value and if the result is zero of less unblocks a thread.

They are not usually used directly.

Mutex implementation with semaphores

The value stored in a counting semaphore is typically used to represent the number of instances of some resource that are available. For example, a mutex implementation using semaphores would take the form of acquire() and release() methods which call P() and V() respectively. The mutex is unlocked when the stored value is 1 and locked when it is zero or less.

Condition variable implementation with semaphores

The condition variable class has a condition variable lock mutex, a number of waiters and a counting semaphore.