main.cpp

00001 #include "mbed.h"
00002 #include "rtos.h"
00003 #include <queue>
00004 
00005 
00006 //#define DELAY_INSIDE
00007 //#define DELAY_BTWN
00008 #define DELAY_DISPLAY
00009 
00010 #define DELAY_INSIDE_TIME  1000    
00011 #define DELAY_BTWN_TIME   311   
00012 #define DELAY_DISPLAY_TIME   100   
00013 
00014 
00015 #define ARRAY_SIZE   16
00016 #define THREAD_ARRAY_SIZE   10
00017  
00018 typedef struct{
00019    int tid;
00020    int pid;
00021    int cap;
00022    int weights[ARRAY_SIZE];
00023    int values[ARRAY_SIZE];
00024    int ts_begin;   
00025    int ts_end;
00026    int proc_time;
00027    int n;
00028 }problema;
00029 
00030 typedef struct{
00031    int tid;
00032    int pid;
00033    int cap;
00034    int weights[ARRAY_SIZE];
00035    int values[ARRAY_SIZE];
00036    int ts_begin;   
00037    int ts_end;
00038    int proc_time;
00039    int opt;  
00040 }solucion;
00041 
00042 
00043 Timer t;
00044 DigitalOut led1(LED1);  // Red
00045 DigitalOut led2(LED2);  // Green
00046 DigitalOut led3(LED3);  // Blue
00047 
00048 osMutexDef (mutex_leds);//mutex for LEDs
00049 osMutexDef (mutex_p);   //problem queue mutex
00050 osMutexDef (mutex_s);   //solution queue mutex 
00051 
00052 
00053 osMutexId  (mutex_leds_id); // LED mutex ID
00054 osMutexId  (mutex_p_id);    // problem queue mutex ID
00055 osMutexId  (mutex_s_id);    // solution queue mutex ID
00056 
00057 
00058 queue <problema> problem_q;
00059 queue <solucion> solution_q;
00060 
00061 Serial pc(USBTX, USBRX);
00062 
00063 #ifdef DEBUG 
00064 int printP(problema p){
00065     int i;
00066     printf("\n#P \t#T \tCap \t#items");
00067     printf("\n%i \t%i \t%i \t%i\n",p.pid,p.tid,p.cap,p.n);
00068     printf("  Weights \tValues\n");
00069     printf("  ------- \t------\n");
00070     i=0;
00071     while (p.weights[i]>-5 && p.values[i]>-5 && i<30){ 
00072         printf("%i.    %i \t%i\n", i+1, p.weights[i],p.values[i]);
00073         i++;
00074     }
00075     printf("\n");
00076     return 1;
00077 }
00078 
00079 int printS(solucion s){
00080     int i;
00081     printf("\n#S \t#T \tCap \tOpt Val \tBegin \t\tEnd \t\tProc");
00082     printf("\n%i \t%i \t%i \t%i \t\t%ius \t%ius \t%ius\n", s.pid, s.tid, s.cap, s.opt, s.ts_begin, s.ts_end, s.proc_time);
00083     printf("  Weights \tValues \t(included items)\n");
00084     printf("  ------- \t------\n");
00085     i=0;
00086     while (s.weights[i]>-5 && s.values[i]>-5 && i<30){ 
00087         printf("%i.    %i \t%i\n", i+1, s.weights[i],s.values[i]);
00088         i++;
00089     }
00090     printf("\n");
00091     return 1;
00092 }
00093 
00094 #else
00095 #endif
00096 
00097 int printF(solucion s){
00098     int i;
00099     printf("\n#");
00100     printf("%i,", s.tid);
00101     printf("%i,", s.pid);
00102     printf("%i", s.cap);
00103     i=0;
00104     while (s.weights[i]>=0 && s.values[i]>=0 && i<30){ 
00105         printf(",%i,%i", s.weights[i],s.values[i]);
00106         i++;
00107     }
00108     printf(",%i", s.ts_begin);
00109     printf(",%i", s.ts_end);
00110     printf(",%i", s.proc_time);
00111     printf("*");
00112     return 1;
00113 }
00114 
00115 int my_atoi(char *str) {
00116     int res = 0; // Initialize result
00117     // Iterate through all characters of input string and update result
00118     for (int i = 0; str[i] != '\0'; ++i)
00119         res = res*10 + str[i] - '0';
00120     return res;
00121 }
00122 
00123 // A utility function that returns maximum of two integers
00124 int max(int a, int b) { return (a > b)? a : b; }
00125 
00126 // Returns the maximum value that can be put in a knapsack of capacity W
00127 solucion knapSackP(problema p, int t){
00128    solucion s;
00129    s.ts_begin=t;//t.read_us();
00130    int i, w,index=0;
00131    int K[p.n+1][p.cap+1];
00132    // Build table K[][] in bottom up manner
00133    for (i = 0; i <= p.n; i++){
00134        for (w = 0; w <= p.cap; w++){
00135            if (i==0 || w==0)
00136                K[i][w] = 0;
00137            else if (p.weights[i-1] <= w)
00138                K[i][w] = max(p.values[i-1] + K[i-1][w-p.weights[i-1]],  K[i-1][w]);
00139            else
00140                  K[i][w] = K[i-1][w];
00141        }
00142    }
00143    s.opt = K[p.n][p.cap];
00144      
00145    w = p.cap;
00146    for (i=p.n; i>0; i--){
00147        if(K[i][w] != K[i-1][w]){
00148           //printf("(p.weights=%i,val=%i)-> ",p.weights[i-1],val[i-1]);
00149           s.weights[index]=p.weights[i-1];
00150           s.values[index++]=p.values[i-1];
00151           w=w-p.weights[i-1];
00152        }
00153    }
00154    s.weights[index]=-5;
00155    s.values[index]=-5;
00156    
00157    
00158    return s;
00159 }
00160  
00161 void led_func(uint32_t n){
00162     uint32_t temp = ~((n%7)+1);
00163     led3 = temp&(uint32_t)1;
00164     led2 = (temp&(uint32_t)2)>>1;
00165     led1 = (temp&(uint32_t)4)>>2;   
00166 }
00167 
00168 void led_thread(void const *argument)
00169 {
00170     uint32_t cont =0;
00171     while (true) {
00172         osMutexWait(mutex_leds_id, osWaitForever); //request lock
00173         led_func(cont);
00174         osMutexRelease(mutex_leds_id);              //unlock
00175         Thread::wait((uint32_t)argument );
00176         cont++;
00177     }
00178 }
00179 
00180 void worker_thread(void const *argument){
00181      problema p;
00182      solucion s;    
00183      
00184      while (true) {
00185         osMutexWait(mutex_p_id, 1000);
00186         if (!problem_q.empty()){
00187                 p = problem_q.front();
00188                 problem_q.pop();
00189                 osMutexRelease(mutex_p_id);
00190                 
00191                 #ifdef DEBUG 
00192                     p.tid = (uint32_t)argument;
00193                     printf("-------------------------------------------------------");
00194                     printP(p);
00195                 #endif
00196                 
00197                 //printf("\nT1:%i\n",t.read_us()); 
00198                 s = knapSackP(p,t.read_us());
00199                 s.ts_end=t.read_us();
00200                 //printf("\nT2:%i\n",t.read_us());
00201                 s.proc_time=s.ts_end-s.ts_begin;
00202                 s.tid = (uint32_t)argument;
00203                 s.pid = p.pid;
00204                 s.cap = p.cap;
00205                 
00206                 #ifdef DEBUG 
00207                     printS(s);
00208                 #endif
00209 
00210                 osMutexWait(mutex_s_id, 1000);
00211                     solution_q.push(s);
00212                 osMutexRelease(mutex_s_id);  
00213                 
00214                 osMutexWait(mutex_leds_id, 1000); //request lock
00215                     led_func((uint32_t)argument);
00216                 osMutexRelease(mutex_leds_id);    //unlock     
00217                 
00218             }else{
00219                 osMutexRelease(mutex_p_id);
00220             }
00221         
00222         osThreadYield();
00223         #ifdef DELAY_INSIDE
00224             Thread::wait(DELAY_INSIDE_TIME);
00225         #endif
00226     }
00227 }
00228 
00229 int main(){
00230     t.start();
00231     problema *problemas_array;          //array to store the parsed problems
00232     Thread *threads_array[THREAD_ARRAY_SIZE]; //array to instance the threads
00233     char buffer[4];                 //buffer to atoi convertion
00234     solucion s;             // var to pop the solutions from solution queue
00235     char input_char;    //received char form serial input
00236     char stage = 0;    //State of the parsing loop
00237     char parseFlag =1;  //flag to exit the input loop
00238     char displayFlag =1;   //flag to exit the display solution loop 
00239     int i;                  //used to indexing alog the differents arrays
00240     int number_threads;     //number of threads recived
00241     int number_threads_temp;  //used to verify if we have recived the number of threads
00242     char problema_counter;     //problem counter
00243     char item_counter;          //
00244     char buffer_counter;        //used to indexing the buffer used to atoi convertion
00245     pc.baud (115200);   //Baudrate
00246     
00247     
00248     while (true) {
00249         problemas_array =(problema *) malloc(10*sizeof(problema)) ;
00250         problema_counter=0;
00251         number_threads=0;
00252         item_counter=0;
00253         buffer_counter=0;
00254         buffer[0]='\0';
00255         buffer[3]='\0';
00256         i=0;
00257         parseFlag=1;
00258         displayFlag =1;
00259         stage = 0;
00260          
00261         while(parseFlag){               //input loop       
00262             input_char = getchar();     //receive char from Serial
00263             //Parsing the message
00264             if (input_char=='&'){   //start of message
00265                 buffer[0]='\0';
00266                 buffer_counter=0;
00267                 problema_counter=0;
00268                 item_counter=0;
00269                 number_threads=0;
00270                 stage = 1;
00271                 //printf("Stage %i\n", stage);
00272             }else if (input_char=='#'){    //end of threads number
00273                 buffer[0]='\0';
00274                 buffer_counter=0;
00275                 stage = 2;
00276                 //printf("Stage %i\n", stage);
00277             }else if (input_char >= '0' && input_char <= '9'){ //number received
00278                 buffer[buffer_counter++]=input_char;
00279                 buffer[buffer_counter]='\0';
00280             }else if (input_char=='*'){             //end of line
00281                 if (stage==1){
00282                      number_threads_temp = my_atoi(&buffer[0]);
00283                      number_threads = (number_threads_temp>0 && number_threads_temp<=10)? number_threads_temp: 5;
00284                     //printf("Number of threads = %i\n", number_threads);
00285                     //printf("Problema = %i\n", problema_counter);
00286                     buffer[0]='\0';
00287                     buffer_counter=0;
00288                 }else if (stage==4){
00289                     problemas_array[problema_counter].values[item_counter++]=my_atoi(&buffer[0]);
00290                     problema_counter++;
00291                     item_counter=0;
00292                     //printf("4Problema = %i\n", problema_counter);
00293                 }else if (stage==5){
00294                     problemas_array[problema_counter].values[item_counter++]=my_atoi(&buffer[0]);
00295                     problemas_array[problema_counter].values[item_counter]=-5;
00296                     problemas_array[problema_counter].weights[item_counter]=-5;
00297                     problemas_array[problema_counter].n=item_counter;
00298                     problema_counter++;
00299                     item_counter=0;
00300                     //printf("Problema = %i\n", problema_counter);
00301                 }  
00302                 
00303             }else if (input_char==','){         //delimiter do the message
00304                 if (stage==2){
00305                     problemas_array[problema_counter].pid = my_atoi(&buffer[0]);
00306                     stage=3;
00307                     //printf("Stage %i\n", stage);
00308                 }else if (stage==3){
00309                     problemas_array[problema_counter].cap = my_atoi(&buffer[0]);
00310                     stage=4;
00311                     //printf("Stage %i\n", stage);
00312                 } else if (stage==4){
00313                     problemas_array[problema_counter].weights[item_counter]=my_atoi(&buffer[0]);
00314                     stage=5;
00315                     //printf("Stage %i\n", stage);
00316                 }else if (stage==5){
00317                     problemas_array[problema_counter].values[item_counter++]=my_atoi(&buffer[0]);
00318                     stage=4;
00319                     //printf("Stage %i\n", stage);
00320                 }
00321                 buffer[0]='\0';
00322                 buffer_counter=0;
00323             }else if (input_char=='\n'){    //newline received
00324                 buffer[0]='\0';
00325                 buffer_counter=0;
00326             }else if (input_char=='X'){    //end of message
00327                 buffer[0]='\0';
00328                 buffer_counter=0;
00329                 stage=0;
00330                 //printf("\nNumber of threads = %i\n", number_threads);
00331                 fflush(stdout);
00332                 fflush(stdin);
00333                 parseFlag =0;               //exit form input loop
00334             }
00335         }
00336         //printf("\nNumber of threads = %i", number_threads);
00337         //printf("\nNumber of problems = %i", problema_counter);
00338         printf("\n Parse Finished \n");
00339         
00340         osMutexWait(mutex_p_id, osWaitForever);         //request lock
00341         for (i=0; i<problema_counter; i++){     
00342             problem_q.push(problemas_array[i]);
00343         }
00344         osMutexRelease(mutex_p_id);                    //unlock
00345         
00346         free(problemas_array);
00347         
00348         i=0;
00349         while (i<number_threads){
00350             threads_array[i]= new Thread(worker_thread,(void *)(i));
00351                 #ifdef DELAY_BTWN
00352             Thread::wait(DELAY_BTWN_TIME);
00353             #endif
00354             i++;
00355         }
00356         
00357         #ifdef DELAY_DISPLAY
00358             Thread::wait(DELAY_DISPLAY_TIME);
00359         #endif
00360         
00361                 
00362         while(displayFlag){
00363                 displayFlag=0;
00364                 printf("\n&%i*",number_threads);
00365                 
00366                 while(!solution_q.empty()){
00367                     osMutexWait(mutex_s_id, osWaitForever);
00368                         if (!solution_q.empty()){
00369                             s = solution_q.front();
00370                             solution_q.pop();
00371                             printF(s);
00372                         }    
00373                         osMutexRelease(mutex_s_id);
00374                 }
00375                   
00376                 
00377         }
00378         
00379       
00380         //i=0;
00381         //while (i<number_threads) threads_array[i];
00382         free(threads_array);
00383         
00384         //osMutexWait(mutex_leds_id, osWaitForever); //request lock
00385           //  led_func(6);
00386         //osMutexRelease(mutex_leds_id);              //unlock
00387     }
00388 }