Thursday, July 21, 2011

How to Create a Pre-emptive Thread Shedular using Java.

First of all To understand this Post You must have some quite good knowledge about the Threads and their behaviors.

Now lets talk about the topic. What is a Preemptive thread scheduler? And why we need it?. The Preemptive scheduler means can suspend a current running thread and run another read and RESUME the previous suspended thread to continue.

So why we need a Preemptive task scheduler. In java JVM(java virtual machine ) has a thread scheduler but it is non preemptive scheduler. So if we need a some kind of Preemptive thread scheduler we have to build it. And we can't control massive complex systems with a non preemptive thread scheduler.

So lets see how can we build a preemptive task scheduler.

First of all we have to maintain a thread list that we are going to manage. It can be a vector , stack or array of threads or a queue. The characteristics of the scheduler will depend on the storing system of the thread list.We need to update a variable(type of thread ) to store the current thread which is at the running state for a given instance. And we must have a method to get the next thread to run.

In this scenario the preemptive thread scheduler it self is a thread which has the highest priority among the handling threads. So it can suspend or pause a any thread because it has the high priority than other threads.

Now Let see a sample code written in java to create a preemptive thread scheduler.


 import java.util.Scanner;  
 import java.util.Vector;  
 import java.util.*;  
 public class PreemtiveThreadShedular extends Thread{  
     private Vector taskList=new Vector(5,5);  
       private Philosopher currentThread;  
     private int index=0;  
     public static void main(String [] args){  
        PreemtiveThreadShedular shedular=new PreemtiveThreadShedular();  
        shedular.initializeThreads();  
         shedular.start();  
         shedular.run();  
     }  
     public PreemtiveThreadShedular(){  
       this.setPriority(MAX_PRIORITY);  
     }  
     public void initializeThreads(){  
         Philosopher [] phi=new Philosopher[num];  
         for(int i=0;i<phi.length;i++){  
           phi[i]=new Philosopher(""+i);  
           phi[i].setPriority(NORM_PRIORITY);     
           phi[i].start();  
           phi[i].suspend();          
           taskList.add(phi[i]);  
         }  
       }  
     public void nextThread(){  
       int size=taskList.size();  
       if(taskList.elementAt(index)!=null){  
         currentThread=(Philosopher) taskList.elementAt(index);  
         currentThread.suspend();  
       }  
       index++;  
       if(index==size){  
         index=0;  
       }  
             currentThread=(Philosopher) taskList.elementAt(index);  
       currentThread.resume();  
       try{   
       currentThread.run();  
       }  
       catch(InterruptedException e){  
         System.out.println("Interrupted Error Occured....");  
       }  
     }  
   public void run(){  
     while(isAlive()){  
      nextThread();  
      try{  
        sleep(100);  
      }  
      catch(InterruptedException e){  
        System.out.println("Error occured While Interrupting....");  
        stop();  
      }  
     }  
   }   
 }  
 class Philosopher extends Thread{  
  private String name;  
  public Philosopher(String name){  
    this.name=name;  
 }  
 public void run(){  
 System.out.println(name+" Thread is running");  
 }  
 }  



 
   

Wednesday, June 22, 2011

How to implement Merge Sort Using Java

By running the below program u can clearly understand how the merge sort works...
this program is to sort ten integers.


 // This program is to demonstrate how to implement mergesort in java..  
 // W.M.S Fernando.  
 //18/06/2011....  
 import java.util.Scanner;  
 public class MergeSort {  
    private final int num=10;  
     private int [] A=new int[num];  
   public static void main(String[] args) {  
     // TODO Auto-generated method stub  
   MergeSort m=new MergeSort();    
     m.Merge_S(m.getNum(), 0, 9);  
     m.show();  
   }  
 public MergeSort(){  
   Scanner input=new Scanner(System.in);  
   System.out.println("Enter the numbers to sort:");  
   for(int i=0;i<A.length;i++){  
     A[i]=input.nextInt();  
   }  
 }    
 public void Merge_S(int [] W,int p,int r){  
   int q=0;  
   System.out.println("P: "+p+" Q: "+q+" R: "+r+" out from if condition.... ");  
   if(p<r){  
     q=(p+r)/2;  
     System.out.println("P: "+p+" Q: "+q+" R: "+r+" In the if condition....");  
     System.out.println("Merge 1");  
     System.out.println("P: "+p+" Q: "+q+" R: "+r+" Befor merge_S 1");  
     ///////////////////////////  
     Merge_S(A,p,q);  
     ///////////////////////  
     System.out.println("P: "+p+" Q: "+q+" R: "+r+" After Merge_S 1");  
     System.out.println("Merge 2");  
     System.out.println("P: "+p+" Q: "+q+" R: "+r+" Befor Merge_S 2");  
     /////////////////////////  
     Merge_S(A,q+1,r);  
     /////////////////////////  
     System.out.println("P: "+p+" Q: "+q+" R: "+r+" After Merge_S 2");  
     System.out.println("P: "+p+" Q: "+q+" R: "+r+" Before the merge function..");  
     //////////////////////////////////////  
     MergeSort.Merge(A,p,q,r,100);  
     /////////////////////////////////////  
     System.out.println("P: "+p+" Q: "+q+" R: "+r+" After Merge");  
   }  
 }  
 public static void Merge(int [] W,int p,int q,int r,int Max){  
   System.out.println("Merge function executes.......");  
   int nL=q-p+1;  
   int nR=r-q;  
   System.out.println("nL: "+nL+" nR: "+nR);  
   int [] L=new int[nL+1];  
   int [] R=new int[nR+1];  
   L[nL]=Max+1;  
   R[nR]=Max+1;  
   for(int i=0;i<L.length-1;i++){  
     L[i]=W[p+i];  
     System.out.println("L["+i+"]: "+L[i]);  
   }  
   for(int j=0;j<R.length-1;j++){  
     R[j]=W[q+1+j];  
    System.out.println("R["+j+"]: "+R[j]);  
   }  
 int i=0;  
 int j=0;  
   for(int k=p;k<=r;k++){  
     if(L[i]<=R[j]){  
       W[k]=L[i];  
       System.out.println("W["+k+"]: "+W[k]);  
       i++;  
     }  
     else{  
       W[k]=R[j];  
       j ++;  
     System.out.println("W["+k+"]: "+W[k]);  
     }  
   }  
 }    
 public int Max(int [] W){  
   int max=0;  
   for(int i=0;i<W.length;i++){  
     if(W[i]>=W[i+1]){  
       max=W[i];  
     }  
     else{  
       max=W[i+1];  
     }  
   }  
   return max;  
 }  
 public int [] getNum(){  
   return A;  
 }  
 public void show(){  
   System.out.println("Here is the sorted Array....");  
   for(int i=0;i<A.length;i++){  
     System.out.print(" "+A[i]);  
   }  
 }  
 }  

Saturday, May 21, 2011

An Algorithm for path tracking robot with junction detecting and signal detecting


Algorithm

We use several important concepts for the robot’s motion.
·        Forward – two motos rotate in the forward direction
·        Right-  left motor rotates while right motor rests
·        Left- right motor rotates while left motor rests
·        Sharp right- left motor rotates forward while right motor rotates backward. Two motors rotate with the same speed in opposite directions. This movement is used when the robot needs to take a sharp right turn.
·        Sharp left- right motor rotates forward while left motor rotates backward. Two motors rotate with the same speed in opposite directions. This movement is used when the robot needs to take a sharp left turn.
·        Reverse- both motors rotate in the backward direction.


B3

B4

B6

B5

B7

B0

B2

B1
 




                             
                                          A top view of the sensor panel
This robot is continuosly repeats the source code until we power it off.so we use  instructions inside a infinite loop.

Path tracking

Basic path tracking is done using B3 and B4.



 If ( B3==0 and B4==0) , go forward  
 If(B3==0 and B4==1), turn left  
 If(B3==1 and B4==0), turn right  
 If (B3==1 and B4==1) {//  this situation occurs when the robot is out of the track, discontinuity,                    in a sharp bend,  
      If(B0==0 or B1==0 or B2==0) turn left while ( B3==1 and B4==1) // sharp left bends  
 and continue  
 If (B5==0 or B6==0 or B7==0) turn right while ( B3==1 and B4==1) // sharp right bend  
 and continue  
 If ( B0==1 and B1==1 and B2==1 and B3==1 and B4==1 and B5==1 and B6==1 and B7==1) go forward , a counter starts , after exeeding a specific limit, turn right and continue within this loop.// to find the path when roaming , in discontinuities the count doesn’t exeed the limit.  
 } // path tracking is done.  

Signal detecting

Signal posts are 4 x 4 cm2  black squares. To detect a signal we use six detectors and three variables , sig_right, sig_left and turn_val with all initial values 0.
Sig_left =1 if a signal is to the left, otherwise 0 ,
Sig_right=1 if a signal is to the right, otherwise 0,
Turn_val has 3 values, 0,1 and 2.
Turn_val becomes 0 after turning at a junction.
Turn_val becomes 1 when a signal is to left
Turn_val becomes 2 when a signal is to right



 If (B0==0 and B1==0 and B2==0 and B3==0 and B4==0 and B7==1 and( (sig_left==0 and sig_right ==0 ) or turn_val==2) ) // identifies a signal post to the left,  
      {  
      Sig_left=1,  
 sig_right=0 ,  
  turn_val=1,  
 continue to the main loop  
        }  
 If (B5==0 and B6==0 and B7==0 and B3==0 and B4==0 and B0==1 and( (sig_left==0 and sig_right ==0 ) or turn_val==1) ) // identifies a signal post to the right  
      {  
 Sig_left=0,  
 sig_right=1 ,  
 turn_val=2,  
      continue to the main loop  
 }  




Junction detecting

This algorithm is developed to detect 4-way junctions and turn according to the signals.We have already ddiscussed how the robot identifies a signal and here we explain how it turns at a junction according to the signals.
We employee six sensors out of the eight sensors to detect a junction.



 If ((B0==0 or B1==0 or B2==0) and (B5==0 or B6==0 or B7==0 ) and (sig_left==1 or sig_right==1))  
      {   
           If ( sig_left==1 and sig_right==0) {  
 Turn left, // to take the middle two sensors to the white background  
 Sharp left , // this takes a sharp left turn  
 Turn left while (B3==1 and B4==1)  
 Sig_left=0;  
 Sig_right=0;  
 Turn_val=0;  
 Continue to main loop;  
             }  
 If ( sig_left==1 and sig_right==0) {  
 Turn right,//to take the middle two sensors to the white background  
 Sharp right , // this takes a sharp right turn  
 Turn right while (B3==1 and B4==1)  
 Sig_left=0;  
 Sig_right=0;  
 Turn_val=0;  
 Continue to main loop;  
                   }  
 }  
 Else // if some signal comes except all combinations discussed above,        
      Go forward and continue to main loop;   
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////