viernes, 30 de abril de 2010

Parallel algorithms. Java threads. Using multiple cores.

Today, computar machines has a multiples cores into his processors. The main problem is that the software engineers do not design the software accord this situation because they ignore this new technology or simply because they doesn´t want design parallel algorithms. This problem imply that the multiple core machines are underused.

I propose a simple problem: Adding an integer array of ten million positions with a due core machine.

  1. Only one process
  2. Four threads. A piece of vector by thread
  3. Two threads. A piece of vector by thread
The results:



Java Readers and Writer. Mutual exclusion.

Think about this situation, you have a buffer and into the bufer has one data. We have several elements in this situation: One Writer, that provide tha data into the buffer, and many Readers, thtat need the data into the buffer; and one restriction, only one persona can read or write into the buffer at the same time.

In order to resolve this problem we can use a Monitor. A monitor is a Class that provide a mutual exclusion in this methods. To write this in Java, we can introduce the keyword synchronized in the method. For ejample, in Buffer.java:




We can see complete execution over Main class



Output:

run:
Reader 0 is waiting to get data (total buffer=0)
Reader 9 is waiting to get data (total buffer=0)
Reader 8 is waiting to get data (total buffer=0)
Reader 7 is waiting to get data (total buffer=0)
Reader 3 is waiting to get data (total buffer=0)
Reader 6 is waiting to get data (total buffer=0)
Reader 2 is waiting to get data (total buffer=0)
Reader 1 is waiting to get data (total buffer=0)
The writer is writing data (buffer:1)
........reader 0 unlock
Reader 0 has read a data (buff=0)
........reader 9 unlock
Reader 9 is waiting to get data (total buffer=0)
Reader 4 is waiting to get data (total buffer=0)
Reader 5 is waiting to get data (total buffer=0)
The writer is writing data (buffer:1)
........reader 8 unlock
Reader 8 has read a data (buff=0)
........reader 7 unlock
Reader 7 is waiting to get data (total buffer=0)
The writer is writing data (buffer:1)
........reader 3 unlock
Reader 3 has read a data (buff=0)
........reader 6 unlock
Reader 6 is waiting to get data (total buffer=0)
The writer is writing data (buffer:1)
........reader 2 unlock
Reader 2 has read a data (buff=0)
........reader 1 unlock
Reader 1 is waiting to get data (total buffer=0)
Reader 28 is waiting to get data (total buffer=0)
Reader 29 is waiting to get data (total buffer=0)
Reader 20 is waiting to get data (total buffer=0)
Reader 11 is waiting to get data (total buffer=0)
Reader 13 is waiting to get data (total buffer=0)
Reader 16 is waiting to get data (total buffer=0)
Reader 27 is waiting to get data (total buffer=0)
Reader 10 is waiting to get data (total buffer=0)
Reader 18 is waiting to get data (total buffer=0)
Reader 24 is waiting to get data (total buffer=0)
Reader 23 is waiting to get data (total buffer=0)
Reader 17 is waiting to get data (total buffer=0)
The writer is writing data (buffer:1)
........reader 9 unlock
Reader 9 has read a data (buff=0)
........reader 4 unlock
Reader 4 is waiting to get data (total buffer=0)
Reader 21 is waiting to get data (total buffer=0)
Reader 22 is waiting to get data (total buffer=0)
Reader 19 is waiting to get data (total buffer=0)
Reader 12 is waiting to get data (total buffer=0)
Reader 25 is waiting to get data (total buffer=0)
Reader 26 is waiting to get data (total buffer=0)
Reader 14 is waiting to get data (total buffer=0)
The writer is writing data (buffer:1)
........reader 5 unlock
Reader 5 has read a data (buff=0)
........reader 7 unlock
Reader 7 is waiting to get data (total buffer=0)
The writer is writing data (buffer:1)
........reader 6 unlock
Reader 6 has read a data (buff=0)
........reader 1 unlock
Reader 1 is waiting to get data (total buffer=0)
Reader 15 is waiting to get data (total buffer=0)
The writer is writing data (buffer:1)
........reader 28 unlock
Reader 28 has read a data (buff=0)
........reader 29 unlock
Reader 29 is waiting to get data (total buffer=0)
The writer is writing data (buffer:1)
........reader 20 unlock
Reader 20 has read a data (buff=0)
........reader 11 unlock
Reader 11 is waiting to get data (total buffer=0)
The writer is writing data (buffer:1)
........reader 13 unlock
Reader 13 has read a data (buff=0)
........reader 16 unlock
Reader 16 is waiting to get data (total buffer=0)
The writer is writing data (buffer:1)
........reader 27 unlock
Reader 27 has read a data (buff=0)
........reader 10 unlock
Reader 10 is waiting to get data (total buffer=0)
The writer is writing data (buffer:1)
........reader 18 unlock
Reader 18 has read a data (buff=0)
........reader 24 unlock
Reader 24 is waiting to get data (total buffer=0)
The writer is writing data (buffer:1)
........reader 23 unlock
Reader 23 has read a data (buff=0)
........reader 17 unlock
Reader 17 is waiting to get data (total buffer=0)
The writer is writing data (buffer:1)
........reader 4 unlock
Reader 4 has read a data (buff=0)
........reader 21 unlock
Reader 21 is waiting to get data (total buffer=0)
The writer is writing data (buffer:1)
........reader 22 unlock
Reader 22 has read a data (buff=0)
........reader 19 unlock
Reader 19 is waiting to get data (total buffer=0)
The writer is writing data (buffer:1)
........reader 12 unlock
Reader 12 has read a data (buff=0)
........reader 25 unlock
Reader 25 is waiting to get data (total buffer=0)
The writer is writing data (buffer:1)
........reader 26 unlock
Reader 26 has read a data (buff=0)
........reader 14 unlock
Reader 14 is waiting to get data (total buffer=0)
The writer is writing data (buffer:1)
........reader 7 unlock
Reader 7 has read a data (buff=0)
........reader 1 unlock
Reader 1 is waiting to get data (total buffer=0)
The writer is writing data (buffer:1)
........reader 15 unlock
Reader 15 has read a data (buff=0)
........reader 29 unlock
Reader 29 is waiting to get data (total buffer=0)
The writer is writing data (buffer:1)
........reader 11 unlock
Reader 11 has read a data (buff=0)
........reader 16 unlock
Reader 16 is waiting to get data (total buffer=0)
The writer is writing data (buffer:1)
........reader 10 unlock
Reader 10 has read a data (buff=0)
........reader 24 unlock
Reader 24 is waiting to get data (total buffer=0)
The writer is writing data (buffer:1)
........reader 17 unlock
Reader 17 has read a data (buff=0)
........reader 21 unlock
Reader 21 is waiting to get data (total buffer=0)
The writer is writing data (buffer:1)
........reader 19 unlock
Reader 19 has read a data (buff=0)
........reader 25 unlock
Reader 25 is waiting to get data (total buffer=0)
The writer is writing data (buffer:1)
........reader 14 unlock
Reader 14 has read a data (buff=0)
........reader 1 unlock
Reader 1 is waiting to get data (total buffer=0)
The writer is writing data (buffer:1)
........reader 29 unlock
Reader 29 has read a data (buff=0)
........reader 16 unlock
Reader 16 is waiting to get data (total buffer=0)
The writer is writing data (buffer:1)
........reader 24 unlock
Reader 24 has read a data (buff=0)
........reader 21 unlock
Reader 21 is waiting to get data (total buffer=0)
The writer is writing data (buffer:1)
........reader 25 unlock
Reader 25 has read a data (buff=0)
........reader 1 unlock
Reader 1 is waiting to get data (total buffer=0)
The writer is writing data (buffer:1)
........reader 16 unlock
Reader 16 has read a data (buff=0)
........reader 21 unlock
Reader 21 is waiting to get data (total buffer=0)
The writer is writing data (buffer:1)
........reader 1 unlock
Reader 1 has read a data (buff=0)
........reader 21 unlock
Reader 21 is waiting to get data (total buffer=0)
The writer is writing data (buffer:1)
........reader 21 unlock
Reader 21 has read a data (buff=0)
The writer is writing data (buffer:1)
The writer is writing data (buffer:2)
The writer is writing data (buffer:3)
The writer is writing data (buffer:4)
The writer is waiting to write data. The buffer is full

jueves, 29 de abril de 2010

Java Process and Threads. TCP Java Server.

This post try it to explain how to manage Process, Threads and concurrence.

The main goal is explain how is a thread, and how is a process.
We can explain very well this topics with follow ilustration of Tanenbaum book :


The ilustration show in a) case three process with one thread into each one, in case b) we can see ONE process with three threads into the unique process.
The main diference between Process and Thread is that the thread is more ligth than a Process in order of the Threads works in the details of thw Process`s work and it can share the Thread stack with the others Threads.

A very good example of Process and Threads can be a Server and a Client.The server will be a Process wich accepts requests of a clients. Whe it accept one request, will create a Thread to give service to a client request.
We need three JavaClass: Server.java, Process.java and Cliente.java.

Server class create a s = new ServerSocket(9000); and wait to accept conecctions. When a conecction from a Cliente is coming, the server instance one Process with Procesador proc = new Procesador(cont,s.accept()); proc.start();

In this moment, Server is waiting for a new incoming conecction, and his Thread Process is working with the cliente conecction. The Processador read, operate and request the conecction cliente: b = new BufferedReader( new InputStreamReader ( sc.getInputStream() ) ); , p = new PrintStream ( sc.getOutputStream() );

Now, only need the Cliente operations: it´s simple, only create a socket s = new Socket(host,port); and write the request to a server.
We can see the result.




One iteration between Server and two clients:

One cliente close the conecction, but the oher cliente is coneccted and work in the server.



The client #3 executed two operations in the server and close conecction. Really close the Process Thread.