What is a process?

When you run a program (either by clicking or from the command line), a process is created on the operating system. A process is the state of program's execution, consisting of:

Monitoring processes

You can see a list of live processes by using top command on Linux terminal. The list will always contain the init command, which is the operating system itself, and the first ever process that was run when the computer was turned-on most recently. The init process has super privileges, and that is how it starts and pauses other processes one by one on the CPU, creating the illusion that they are running all at the same time. A multicore aware OS can make use of multiple CPUs and cores on the hardware.

ls /proc/ will show you numerous files whose names are numbers. These are records of live or finished processes in the system. /proc/ is actually a virtaul filesystem which provides information about the running system (e.g. /proc/cpu shows current state of CPUs, and /proc/memusage shows current memory usage, etc.)

For similar profiling of Java programs, you can use tools like VisualVM: http://visualvm.java.net/. Once started it will find running Java programs, and can show useful process statistics about them.

Concurrency: Processes vs Threads

Operating systems support concurrent execution in two different ways:

Every modern programming language provides commands and libraries to create and control threads. Programs who make use of threads result in concurrent processes. The fact that threads share the same heap is very useful, but also have a lot of risks. The rest of this course focuses on making use of threads, while at the same time understanding and controlling for those risks.

The Runtime environment

The following example demonstrates Java's conception of what a process, and its operating system is. Runtime and System are somewhat similar, and emerged during the language's evolution. System represents the JVM, whereas Runtime is its contact to the surrounding operating system environment. However the two sometimes overlap, such as in the case of System's in, out, and error streams, which are all connected to OS console, and OS environment variables returnsed by System.getenv().

Note that knowledge of runtime environment is useful, and necessary to control policies in your programs towards concurrecny, for example to decide how many concurrent threads to run depending on the number of CPUs and cores.

    import java.io.*;
    import java.util.Properties;

    class RuntimeEnvironment {
        public static void main(String[] args) {
            System.out.println("------------- RUNTIME --------------");
            Runtime runtime=Runtime.getRuntime();
            System.console().format("Number of processors:%d\n", runtime.availableProcessors());
            System.console().format("Free memory:%d\n", runtime.freeMemory());
            System.out.println("------------- SYSTEM PROPERTIES--------------");
            Properties props=System.getProperties();
            for(String s:props.stringPropertyNames())
                System.console().format("%s: %s\n",s,props.getProperty(s));
            System.out.println("------------- OPERATING SYSTEM ENVIRONMENT VARIABLES--------------");
            for(String s:System.getenv().keySet())
                System.console().format("%s: %s\n",s,System.getenv(s));
            System.out.println("------------- RUNNING A COMMAND--------------");
            try {
                String command=System.console().readLine("\n>>>>> Enter a command to execute:");
                if (command.length()==0)
                    return;
                Process p=runtime.exec(command);//run  command on the operating system
                p.waitFor(); //wait for the command to be completed
                InputStream s=p.getInputStream();
                while(s.available()>0)
                    System.err.write(s.read()); //THIS IS A SEPARATE STREAM
            } catch(Exception e){
                System.out.println(e);
            }
        }
    }

Thread mechanics 1: the main thread, and pausing execution

When a process is started from the command line, it runs in its own thread, i.e. a program in execution has at least one thread, which we will call the main thread. However, a process can also create additional threads of execution to exploit CPU power. Any process can learn about its main thread of execution by calling the static method Thread.currentThread().

    class Worker implements Runnable {
        long sleepTime;
        Worker(long sleepTime) { this.sleepTime=sleepTime;}
        public void run() {
            System.console().format("I'm thread no %d, starting with priority %d\n",Thread.currentThread().getId(), Thread.currentThread().getPriority());
            try {
                while(true) {
                    System.console().format("I'm thread no %d, doing nothing\n",Thread.currentThread().getId());
                    Thread.sleep(sleepTime);
                }
            } catch(InterruptedException e) {
                System.console().format("I'm thread no %d, goodby\n",Thread.currentThread().getId());
            }
        }
        public static void main(String[] args) {
            new Worker(1000).run();
        }
    }

The class in the above program implements Runnable. Its execution is no different than any other program, except that it never stops itself (has an infinite/unconditional loop).

The code demonstrates a few tricks about threads:

Thread mechanics 2: creating, starting, and stopping additional threads

Creating, accessing, and starting threads in Java requires one to use the Thread class and Runnable interface. A Runnable object is very simple, it provides a method called run() so that the thread will know where to start.

An additional thread is prepared by instantiating a Thread object and it starts running when that object's start() method is called. Run the program and pay attention to its output. Since the created threads run concurrently, but print to same terminal, their outputs are sometimes mixed up. The main thread uses a timer to stop the additional threads after 5 seconds, by calling interrupt() method of each additional thread object:

    class Worker implements Runnable {
        long sleepTime;
        Worker(long sleepTime) { this.sleepTime=sleepTime;}
        public void run() {
            System.console().format("I'm thread no %d, starting with priority %d\n",Thread.currentThread().getId(), Thread.currentThread().getPriority());
            try {
                while(true) {
                    System.console().format("I'm thread no %d, doing nothing\n",Thread.currentThread().getId());
                    Thread.sleep(sleepTime);
                }
            } catch(InterruptedException e) {
                System.console().format("I'm thread no %d, goodby\n",Thread.currentThread().getId());
            }
        }
        public static void main(String[] args) {
            new Worker(1000).run();
        }
    }
    class Threads {
        public static void main(String[] args) {
            int numThreads=10;
            Thread[] threads=new Thread[numThreads];
            for(int i=0;i<numThreads;i++)
                threads[i]=new Thread(new Worker(500+i*100));
            System.out.println("Thread info:");
            Thread.currentThread().getThreadGroup().list();
            System.console().readLine("Press ENTER to start:");
            for(int i=0;i<numThreads;i++)
                threads[i].start();
            try {
                Thread.currentThread().sleep(5000);
                System.out.println("INTERRUPTING");
                for(int i=0;i<numThreads;i++)
                    threads[i].interrupt();
            }catch(InterruptedException e) {
                System.out.println(e);
            }
        }
    }

Thread mechanics 3: waiting for threads to finish

In many applications you do not create threads with infinite loops. Instead you have a finite computational task and you expect for an additional thread to finish its job at some point. When a Runnable object running in its own thread has no more job to do (as if a program finishing and exitting) the thread becomes. You may ask a Thread object whether it isAlive(). However, polling thread status with this method is a bad practice. Instead the main thread can wait for a thread to finish by calling its join() method:

    /** Checks if the numebr given during construction is prime or not */
    class PrimeChecker implements Runnable {
        long n;
        boolean isPrime=false;
        PrimeChecker(long n) { this.n=n;}
        public void run() {
            boolean isPrime=true;
            for(long i=2;i<n;i++) 
                if (n % i ==0) {
                   isPrime=false;
                   break;
                }
        }
        public static void main(String[] args) {
            long n=Long.parseLong(System.console().readLine("Enter a number to check for primeness:"));
            PrimeChecker checker=new PrimeChecker(n);
            Thread thread=new Thread(checker);
            thread.start();
            try {
                while(thread.isAlive()){
                    thread.join(500);
                    System.out.println("Waiting for thread to finish");
                }
                System.console().format("%d is %b",n,checker.isPrime);
            } catch (InterruptedException e) {
                System.out.println(e);
            }
        }        
    }

Embarrassingly parallel processes

Modern computers provide us with the advantage that they may come with multiple CPUs and/or cores. Utilizing that computational power, however, is another story.

One class of problems which are relatively easier to program with threads is called "embarrassingly parallel". The name is due to the fact that the computation can be broken into parts which are totally independent from one another, thus not much coordination is necessary.

Some examples are: * Rendering of frames in a computer animation * Brute-force prime number finding * Search algorithms like genetic search * Serving files through a web server

Case study: Mandelbrot set

In this case study we tackle the problem of Computing and displaying portions of Mandelbrot sets. The Mandelbrot set consists of points \(c\) in complex plane for which when the function of the form \(f(z)=z^2+c\) is iteratively applied starting with \(z=0+i0\) it does not diverge. Single threaded version of the program follows, which when mouse clicked, enlarges the set visualization around mouse click position:

    import java.awt.*;
    import java.awt.event.*;
    import javax.swing.*;        

    class Complex {
        double real,imag;
        Complex(double real, double imag) {
            this.real=real;
            this.imag=imag;
        }
        Complex add(Complex with) {
            return new Complex(real+with.real,imag+with.imag);
        }
        Complex multiply(Complex with) {
            return new Complex(real*with.real-imag*with.imag,real*with.imag+imag*with.real);
        }
        double size() {
            return Math.sqrt(real*real+imag*imag);
        }
        public String toString() {
            return String.format("%.2f+i%.2f",real,imag);
        }
    }

    class MandelbrotSet {
        Complex rangeStart,rangeEnd;
        int resolution=400;
        int[][] results;
        double limit=100;
        double maxIter=1024;
        MandelbrotSet(int resolution) {
            this(resolution,new Complex(-1,-1),new Complex(1,1));
        }
        MandelbrotSet(int resolution, Complex rangeStart, Complex rangeEnd) {
            this.resolution=resolution;
            results=new int[resolution][resolution];
            this.rangeStart=rangeStart;
            this.rangeEnd=rangeEnd;
        }
        int f(Complex c){
            int i=0;
            Complex fz=new Complex(0,0);
            do {
                fz=fz.multiply(fz).add(c);
                i++;
            } while(i<maxIter && fz.size()<limit);
            return i;
        }

        public void run() {
            System.out.println("running");
            for(int i=0;i<resolution;i++)
                for(int j=0;j<resolution;j++)
                    results[i][j]=f(new Complex(((i+0.0)/resolution)*(rangeEnd.real-rangeStart.real)+rangeStart.real, ((j+0.0)/resolution)*(rangeEnd.imag-rangeStart.imag)+rangeStart.imag));
            System.out.println("finished");
        }
    }

    class MandelbrotDrawPanel extends JPanel {
        final MandelbrotSet set;
        double enlargementRatio=0.5;
        MandelbrotDrawPanel(MandelbrotSet setToUse) {
            super();
            this.set=setToUse;
            setPreferredSize(new Dimension(set.resolution,set.resolution));
            addMouseListener(new MouseListener() {
                public void mouseEntered(MouseEvent event) {}
                public void mouseExited(MouseEvent event) {}
                public void mousePressed(MouseEvent event) { }
                public void mouseReleased(MouseEvent event) {}
                public void mouseClicked(MouseEvent event) {
                    System.console().format("Click at: %d %d\n",event.getX(),event.getY());
                    Complex center=new Complex(
                                    set.rangeStart.real+(set.rangeEnd.real-set.rangeStart.real)*event.getX()/set.resolution,
                                    set.rangeStart.imag+(set.rangeEnd.imag-set.rangeStart.imag)*event.getY()/set.resolution);
                    double currentSize=(set.rangeEnd.real-set.rangeStart.real)/2;
                    double size=currentSize*enlargementRatio;
                    System.console().format("New center:%s, new size %.2f\n",center.toString(),size);
                    set.rangeStart=new Complex(center.real-size,center.imag-size);
                    set.rangeEnd=new Complex(center.real+size,center.imag+size);  
                    set.run();  
                    repaint();        
                }
            });
        }
        public void paintComponent(Graphics g) {
            super.paintComponent(g);
            for(int i=0;i<set.resolution;i++)
                for(int j=0;j<set.resolution;j++) {
                    g.setColor(new Color(Math.max(set.results[i][j]/4-1,0),set.results[i][j]/8,set.results[i][j]/16));
                    g.fillRect(i,j,i+1,j+1); //note that this is inverted due to coordinate system differences
                }
        }
    }

    class MandelbrotSetGUI extends JFrame {
        final MandelbrotSet set;
        MandelbrotDrawPanel panel;
        JTextField creal,cimag;
        MandelbrotSetGUI (MandelbrotSet setToUse) {
            super("Mandelbrot Set GUI");
            this.set=setToUse;
            setDefaultCloseOperation(EXIT_ON_CLOSE);
            setPreferredSize(new Dimension(set.resolution+50,set.resolution+150));
            setLayout(new FlowLayout());
            panel= new MandelbrotDrawPanel(set);
            add(panel);
            JButton close=new JButton("Close");
            close.addActionListener(new ActionListener(){
                public void actionPerformed(ActionEvent e){
                    System.exit(0);
                }
            });
            add(close);
            pack();
        }

        public static void main(String[] args) {
            MandelbrotSet set=new MandelbrotSet(600);
            //if (args.length==2) 
            //    set=new JuliaSet(600, Double.parseDouble(args[0]), Double.parseDouble(args[1]));
            MandelbrotSetGUI gui=new MandelbrotSetGUI(set);
            gui.setVisible(true);
            set.run();
            gui.repaint();
        }
    }

Parallelization of Mandelbrot

    import java.awt.*;
    import java.awt.event.*;
    import javax.swing.*;        

    class Complex {
        double real,imag;
        Complex(double real, double imag) {
            this.real=real;
            this.imag=imag;
        }
        Complex add(Complex with) {
            return new Complex(real+with.real,imag+with.imag);
        }
        Complex multiply(Complex with) {
            return new Complex(real*with.real-imag*with.imag,real*with.imag+imag*with.real);
        }
        double size() {
            return Math.sqrt(real*real+imag*imag);
        }
        public String toString() {
            return String.format("%.2f+i%.2f",real,imag);
        }
    }

    class MandelbrotSet {
        Complex rangeStart,rangeEnd;
        int resolution=400;
        int[][] results;
        double limit=100;
        double maxIter=1024;
        MandelbrotSet(int resolution) {
            this(resolution,new Complex(-1,-1),new Complex(1,1));
        }
        MandelbrotSet(int resolution, Complex rangeStart, Complex rangeEnd) {
            this.resolution=resolution;
            results=new int[resolution][resolution];
            this.rangeStart=rangeStart;
            this.rangeEnd=rangeEnd;
        }
        int f(Complex c){
            int i=0;
            Complex fz=new Complex(0,0);
            do {
                fz=fz.multiply(fz).add(c);
                i++;
            } while(i<maxIter && fz.size()<limit);
            return i;
        }

        public void run(int xstart, int xend) {
            System.out.println("running");
            for(int i=xstart;i<=xend&&i<resolution;i++)
                for(int j=0;j<resolution;j++)
                    results[i][j]=f(new Complex(((i+0.0)/resolution)*(rangeEnd.real-rangeStart.real)+rangeStart.real, ((j+0.0)/resolution)*(rangeEnd.imag-rangeStart.imag)+rangeStart.imag));
            System.out.println("finished");
        }
    }
    class MandelbrotRunner implements Runnable {
        MandelbrotSet set;
        int xstart, xend;
        MandelbrotRunner(MandelbrotSet set, int xstart, int xend) {
            this.set=set;
            this.xstart=xstart;
            this.xend=xend;
        }
        public void run() {
            set.run(xstart,xend);
        }
    }

    class MandelbrotDrawPanel extends JPanel {
        final MandelbrotSet set;
        double enlargementRatio=0.5;
        MandelbrotDrawPanel(MandelbrotSet setToUse) {
            super();
            this.set=setToUse;
            setPreferredSize(new Dimension(set.resolution,set.resolution));
            addMouseListener(new MouseListener() {
                public void mouseEntered(MouseEvent event) {}
                public void mouseExited(MouseEvent event) {}
                public void mousePressed(MouseEvent event) { }
                public void mouseReleased(MouseEvent event) {}
                public void mouseClicked(MouseEvent event) {
                    System.console().format("Click at: %d %d\n",event.getX(),event.getY());
                    Complex center=new Complex(
                                    set.rangeStart.real+(set.rangeEnd.real-set.rangeStart.real)*event.getX()/set.resolution,
                                    set.rangeStart.imag+(set.rangeEnd.imag-set.rangeStart.imag)*event.getY()/set.resolution);
                    double currentSize=(set.rangeEnd.real-set.rangeStart.real)/2;
                    double size=currentSize*enlargementRatio;
                    System.console().format("New center:%s, new size %.2f\n",center.toString(),size);
                    set.rangeStart=new Complex(center.real-size,center.imag-size);
                    set.rangeEnd=new Complex(center.real+size,center.imag+size);  
                    redo();
                }
            });
        }
        void redo() {MandelbrotSetGUI.doParallel(4,set,this);}
        public void paintComponent(Graphics g) {
            super.paintComponent(g);
            for(int i=0;i<set.resolution;i++)
                for(int j=0;j<set.resolution;j++) {
                    g.setColor(new Color(Math.max(set.results[i][j]/4-1,0),set.results[i][j]/8,set.results[i][j]/16));
                    g.fillRect(i,j,i+1,j+1); //note that this is inverted due to coordinate system differences
                }
        }
    }

    class MandelbrotSetGUI extends JFrame {
        final MandelbrotSet set;
        MandelbrotDrawPanel panel;
        JTextField creal,cimag;
        MandelbrotSetGUI (MandelbrotSet setToUse) {
            super("Mandelbrot Set GUI");
            this.set=setToUse;
            setDefaultCloseOperation(EXIT_ON_CLOSE);
            setPreferredSize(new Dimension(set.resolution+50,set.resolution+150));
            setLayout(new FlowLayout());
            panel= new MandelbrotDrawPanel(set);
            add(panel);
            JButton close=new JButton("Close");
            close.addActionListener(new ActionListener(){
                public void actionPerformed(ActionEvent e){
                    System.exit(0);
                }
            });
            add(close);
            pack();
        }

        static void doParallel(int howMany, MandelbrotSet set,MandelbrotDrawPanel panel) {
            MandelbrotRunner[] runners=new MandelbrotRunner[howMany];
            Thread[] threads=new Thread[howMany];
            for(int i=0;i<howMany;i++) {
                runners[i]=new MandelbrotRunner(set,i*set.resolution/howMany,(i+1)*set.resolution/howMany);
                threads[i]=new Thread(runners[i]);
                threads[i].start();
            }
            try {
                for(int i=0;i<howMany;i++) 
                    threads[i].join();
            } catch (InterruptedException e) {
                System.out.println();
            }
            panel.repaint();
        }

        public static void main(String[] args) {
            MandelbrotSet set=new MandelbrotSet(600);
            //if (args.length==2) 
            //    set=new JuliaSet(600, Double.parseDouble(args[0]), Double.parseDouble(args[1]));
            MandelbrotSetGUI gui=new MandelbrotSetGUI(set);
            gui.setVisible(true);
            MandelbrotSetGUI.doParallel(4,gui.set,gui.panel);
        }
    }