Programming Language - Java

Process and Thread

A process is a running instance of a program. A process includes code, data, stack, programming counter, files, and isolated memory including heap that is assigned by OS. Process is isolated from other process, i.e., process does not share anything explicitly with other processes.

A thread is a light weight process. Thread has its own program counter, and function stack, but share the same data, files, and code with other threads from the same process. Thread could be easily communicated with other threads through process’s memory (heap). Overhead to create a thread is much light than creating a process.

process-thread

Concurrency and Parallel

Concurrency normally refers to threads or process runing concurrently. It is different from parallel. Parallel means two threads/process running at the same time in different CPUs or computers. Cocurrency means two threads/process share the same CPU but runing inter-leaves.

Concurrency is to improve utilization of CPU, so that CPU doesn’t need to waste time to wait external data/file process, such as disk read/write, etc.

Because threads share the same data in process memory, read/write conflit is inevitable. Java has a few ways to handle data synchronization.

parallel-concurrency

Java Concurrency

Create Thread

Java has a class Thread that maintains the thread states. We can extends this class and overide the run method inside to create a new thread, e.g.,

public class HelloThread extends Thread {

    @Override
    public void run() {
        System.out.println("Hello from a thread!");
    }

}

Alternatively, Java has also an interface Runnable, we could implement it and initialize a thread by supply this interface.

public class HelloRunnable implements Runnable {

    public void run() {
        System.out.println("Hello from a thread!");
    }

    public static void main(String args[]) {
        (new Thread(new HelloRunnable())).start();
    }

}

Since Runnable is an interface, we could also use lamda expression or anounymous class to instantiate a implementation.

Synchronization

Lock

The concept of Lock is simple to understand: when a thread is reading/writting a data, assign a lock to this thread, if it finished access, the thread releases the lock. Other threads has to wait until the lock is released.

Condition

A lot of times, we have to wait for some condition to actually operate on a data, even if we already acquire a Lock on the data. Java has condition interface that could wait for the condition to be fullfilled, and release the lock.

Keyword synchronized

This keyword is applied on method/function that implies a intrisic lock on this method/function. It is basically adding a intrisic lock to the class and use it as the same of Lock and Condition.

Semaphore

Semaphore provides another way to restrict acess. It maintains a few permits, and only if available permits is more than required, the thread continues, else the thread will wait until permits enough.

Permits could be increased and decreased without limitation, i.e., not limited by the initialized permits.

Examples

Leetcode - 1188

Leetcode-1188

Lock/Condition

class BoundedBlockingQueue {

    private Queue<Integer> queue;
    private Lock lock;
    private Condition cond;
    private int capacity;
    public BoundedBlockingQueue(int capacity) {
        queue = new LinkedList<>();
        this.capacity = capacity;
        lock = new ReentrantLock();
        cond = lock.newCondition();
    }
    
    public void enqueue(int element) throws InterruptedException {
        lock.lock();
        try {
            // wait if the queue is already full
            // lock is released
            while (queue.size() == capacity) {
                cond.await();
            }
            queue.offer(element);
            cond.signalAll();
        } finally {
            lock.unlock();
        }
    }
    
    public int dequeue() throws InterruptedException {
        lock.lock();
        try {
            // wait if the queue is already empty
            // lock is released
            while (queue.size() == 0) {
                cond.await();
            }
            cond.signalAll();
            return queue.poll();
        } finally {
            lock.unlock();
        }
    }
    
    public int size() {
        return queue.size();
    }
}

Synchronized

class BoundedBlockingQueue {

    private Queue<Integer> queue;
    private int capacity;
    public BoundedBlockingQueue(int capacity) {
        queue = new LinkedList<>();
        this.capacity = capacity;

    }
    
    public synchronized void enqueue(int element) throws InterruptedException {

        while (queue.size() == capacity) {
            wait();
        }
        queue.offer(element);
        notifyAll();
    }
    
    public synchronized int dequeue() throws InterruptedException {

        while (queue.size() == 0) {
            wait();
        }

        notifyAll();
        return queue.poll();
    }
    
    public int size() {
        return queue.size();
    }
}

Semaphore

class BoundedBlockingQueue {

    private Queue<Integer> queue;
    private Semaphore full;
    private Semaphore empty;
    public BoundedBlockingQueue(int capacity) {
        queue = new LinkedList<>();
        full = new Semaphore(capacity);
        empty = new Semaphore(0);
    }
    
    public void enqueue(int element) throws InterruptedException {
        // acquire a permit for each element
        full.acquire();
        queue.offer(element);
        // increase the permit for empty semaphore
        // means the queues has a element coming in
        empty.release();
    }
    
    public int dequeue() throws InterruptedException {
        empty.acquire();
        full.release();
        return queue.poll();
        
    }
    
    public int size() {
        return queue.size();
    }
}

Written on August 23, 2021