Victor Ferman
/
frdm_rtos_knapsack
Soving knapsack problem
Diff: main.cpp
- Revision:
- 1:39e36a5c11e0
- Parent:
- 0:1ea8993f6b18
--- a/main.cpp Tue Oct 20 03:54:08 2015 +0000 +++ b/main.cpp Mon Mar 28 20:21:44 2022 +0000 @@ -1,53 +1,117 @@ #include "mbed.h" #include "rtos.h" +#include <queue> -DigitalOut led1(LED1); -DigitalOut led2(LED2); -DigitalOut led3(LED3); -uint32_t button_pressed; -Thread *thread2; -Thread *thread3; -Thread *thread4; -Thread *thread5; -Thread *thread6; + +//#define DELAY_INSIDE +//#define DELAY_BTWN +#define DELAY_DISPLAY + +#define DELAY_INSIDE_TIME 1000 +#define DELAY_BTWN_TIME 311 +#define DELAY_DISPLAY_TIME 100 + -osMutexDef (mutex_1); // Declare mutex -osMutexId (mutex_1_id); // Mutex ID - -osMutexDef (mutex_2); // Declare mutex -osMutexId (mutex_2_id); // Mutex ID +#define ARRAY_SIZE 16 +#define THREAD_ARRAY_SIZE 10 + +typedef struct{ + int tid; + int pid; + int cap; + int weights[ARRAY_SIZE]; + int values[ARRAY_SIZE]; + int ts_begin; + int ts_end; + int proc_time; + int n; +}problema; -osMessageQDef(message_q, 10, uint32_t); // Declare a message queue -osMessageQId (message_q_id); // Declare an ID for the message queue -Serial pc(USBTX, USBRX); - -struct Problema -{ +typedef struct{ int tid; int pid; int cap; - int weights[30]; - int values[30]; + int weights[ARRAY_SIZE]; + int values[ARRAY_SIZE]; int ts_begin; int ts_end; int proc_time; -}; + int opt; +}solucion; + + +Timer t; +DigitalOut led1(LED1); // Red +DigitalOut led2(LED2); // Green +DigitalOut led3(LED3); // Blue + +osMutexDef (mutex_leds);//mutex for LEDs +osMutexDef (mutex_p); //problem queue mutex +osMutexDef (mutex_s); //solution queue mutex -int printP(struct Problema p){ + +osMutexId (mutex_leds_id); // LED mutex ID +osMutexId (mutex_p_id); // problem queue mutex ID +osMutexId (mutex_s_id); // solution queue mutex ID + + +queue <problema> problem_q; +queue <solucion> solution_q; + +Serial pc(USBTX, USBRX); + +#ifdef DEBUG +int printP(problema p){ int i; - printf("\n--------------------\n"); - printf("pid: %i\n", p.pid); - printf("tid: %i\n", 0); - printf("cap: %i\n", p.cap); - printf("W \t V\n"); + printf("\n#P \t#T \tCap \t#items"); + printf("\n%i \t%i \t%i \t%i\n",p.pid,p.tid,p.cap,p.n); + printf(" Weights \tValues\n"); + printf(" ------- \t------\n"); i=0; - while (p.weights[i]>=0 && p.values[i]>=0){ - printf("%i \t %i\n", p.weights[i],p.values[i]); + while (p.weights[i]>-5 && p.values[i]>-5 && i<30){ + printf("%i. %i \t%i\n", i+1, p.weights[i],p.values[i]); i++; } - + printf("\n"); + return 1; +} + +int printS(solucion s){ + int i; + printf("\n#S \t#T \tCap \tOpt Val \tBegin \t\tEnd \t\tProc"); + 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); + printf(" Weights \tValues \t(included items)\n"); + printf(" ------- \t------\n"); + i=0; + while (s.weights[i]>-5 && s.values[i]>-5 && i<30){ + printf("%i. %i \t%i\n", i+1, s.weights[i],s.values[i]); + i++; + } + printf("\n"); return 1; } + +#else +#endif + +int printF(solucion s){ + int i; + printf("\n#"); + printf("%i,", s.tid); + printf("%i,", s.pid); + printf("%i", s.cap); + i=0; + while (s.weights[i]>=0 && s.values[i]>=0 && i<30){ + printf(",%i,%i", s.weights[i],s.values[i]); + i++; + } + printf(",%i", s.ts_begin); + printf(",%i", s.ts_end); + printf(",%i", s.proc_time); + printf("*"); + return 1; +} + int my_atoi(char *str) { int res = 0; // Initialize result // Iterate through all characters of input string and update result @@ -56,8 +120,45 @@ return res; } +// A utility function that returns maximum of two integers +int max(int a, int b) { return (a > b)? a : b; } + +// Returns the maximum value that can be put in a knapsack of capacity W +solucion knapSackP(problema p, int t){ + solucion s; + s.ts_begin=t;//t.read_us(); + int i, w,index=0; + int K[p.n+1][p.cap+1]; + // Build table K[][] in bottom up manner + for (i = 0; i <= p.n; i++){ + for (w = 0; w <= p.cap; w++){ + if (i==0 || w==0) + K[i][w] = 0; + else if (p.weights[i-1] <= w) + K[i][w] = max(p.values[i-1] + K[i-1][w-p.weights[i-1]], K[i-1][w]); + else + K[i][w] = K[i-1][w]; + } + } + s.opt = K[p.n][p.cap]; + + w = p.cap; + for (i=p.n; i>0; i--){ + if(K[i][w] != K[i-1][w]){ + //printf("(p.weights=%i,val=%i)-> ",p.weights[i-1],val[i-1]); + s.weights[index]=p.weights[i-1]; + s.values[index++]=p.values[i-1]; + w=w-p.weights[i-1]; + } + } + s.weights[index]=-5; + s.values[index]=-5; + + + return s; +} + void led_func(uint32_t n){ - //mutex uint32_t temp = ~((n%7)+1); led3 = temp&(uint32_t)1; led2 = (temp&(uint32_t)2)>>1; @@ -68,160 +169,220 @@ { uint32_t cont =0; while (true) { + osMutexWait(mutex_leds_id, osWaitForever); //request lock led_func(cont); + osMutexRelease(mutex_leds_id); //unlock Thread::wait((uint32_t)argument ); cont++; } } -void count_thread(void const *argument) -{ +void worker_thread(void const *argument){ + problema p; + solucion s; + while (true) { - osMutexWait(mutex_2_id, osWaitForever); - button_pressed++; - osMutexRelease(mutex_2_id); + osMutexWait(mutex_p_id, 1000); + if (!problem_q.empty()){ + p = problem_q.front(); + problem_q.pop(); + osMutexRelease(mutex_p_id); + + #ifdef DEBUG + p.tid = (uint32_t)argument; + printf("-------------------------------------------------------"); + printP(p); + #endif + + //printf("\nT1:%i\n",t.read_us()); + s = knapSackP(p,t.read_us()); + s.ts_end=t.read_us(); + //printf("\nT2:%i\n",t.read_us()); + s.proc_time=s.ts_end-s.ts_begin; + s.tid = (uint32_t)argument; + s.pid = p.pid; + s.cap = p.cap; + + #ifdef DEBUG + printS(s); + #endif + + osMutexWait(mutex_s_id, 1000); + solution_q.push(s); + osMutexRelease(mutex_s_id); + + osMutexWait(mutex_leds_id, 1000); //request lock + led_func((uint32_t)argument); + osMutexRelease(mutex_leds_id); //unlock + + }else{ + osMutexRelease(mutex_p_id); + } - osMutexWait(mutex_1_id, osWaitForever); - osMessagePut(message_q_id, button_pressed, osWaitForever); - osMutexRelease(mutex_1_id); - Thread::wait(2000); + osThreadYield(); + #ifdef DELAY_INSIDE + Thread::wait(DELAY_INSIDE_TIME); + #endif } } int main(){ - - char buffer_counter=0; - char buffer[4]; - char input_char; - buffer[0]='\0'; - buffer[3]='\0'; - char stage = 0; - int number_threads=0; - int i; - pc.baud (115200); - char parseFlag =1; - - struct Problema problemas[10]; - char problema_counter=0; - char item_counter=0; + t.start(); + problema *problemas_array; //array to store the parsed problems + Thread *threads_array[THREAD_ARRAY_SIZE]; //array to instance the threads + char buffer[4]; //buffer to atoi convertion + solucion s; // var to pop the solutions from solution queue + char input_char; //received char form serial input + char stage = 0; //State of the parsing loop + char parseFlag =1; //flag to exit the input loop + char displayFlag =1; //flag to exit the display solution loop + int i; //used to indexing alog the differents arrays + int number_threads; //number of threads recived + int number_threads_temp; //used to verify if we have recived the number of threads + char problema_counter; //problem counter + char item_counter; // + char buffer_counter; //used to indexing the buffer used to atoi convertion + pc.baud (115200); //Baudrate - /*thread2 = new Thread(count_thread); - thread3 = new Thread(count_thread); - thread4 = new Thread(count_thread); - thread5 = new Thread(count_thread); - thread6 = new Thread(count_thread); - osEvent event;*/ - - /*message_q_id = osMessageCreate(osMessageQ(message_q), NULL); - osEvent event = osMessageGet(message_q_id, osWaitForever); - - if (0== osMutexWait(mutex_1_id, 0)) { - printf(" %d \n\r", event.value.p); - }else{ - printf("Else \n\r"); - } - osMutexRelease(mutex_1_id); - */ while (true) { + problemas_array =(problema *) malloc(10*sizeof(problema)) ; + problema_counter=0; + number_threads=0; + item_counter=0; + buffer_counter=0; + buffer[0]='\0'; + buffer[3]='\0'; + i=0; parseFlag=1; - while(parseFlag){ - input_char = getchar(); - if (input_char=='&'){ + displayFlag =1; + stage = 0; + + while(parseFlag){ //input loop + input_char = getchar(); //receive char from Serial + //Parsing the message + if (input_char=='&'){ //start of message buffer[0]='\0'; buffer_counter=0; problema_counter=0; item_counter=0; number_threads=0; stage = 1; - printf("Stage %i\n", stage); - }else if (input_char=='#'){ + //printf("Stage %i\n", stage); + }else if (input_char=='#'){ //end of threads number buffer[0]='\0'; buffer_counter=0; stage = 2; - printf("Stage %i\n", stage); - }else if (input_char >= '0' && input_char <= '9'){ + //printf("Stage %i\n", stage); + }else if (input_char >= '0' && input_char <= '9'){ //number received buffer[buffer_counter++]=input_char; buffer[buffer_counter]='\0'; - }else if (input_char=='*'){ + }else if (input_char=='*'){ //end of line if (stage==1){ - number_threads = my_atoi(&buffer[0]); - printf("Number of threads = %i\n", number_threads); - printf("Problema = %i\n", problema_counter); + number_threads_temp = my_atoi(&buffer[0]); + number_threads = (number_threads_temp>0 && number_threads_temp<=10)? number_threads_temp: 5; + //printf("Number of threads = %i\n", number_threads); + //printf("Problema = %i\n", problema_counter); buffer[0]='\0'; buffer_counter=0; }else if (stage==4){ - problemas[problema_counter].values[item_counter++]=my_atoi(&buffer[0]); + problemas_array[problema_counter].values[item_counter++]=my_atoi(&buffer[0]); problema_counter++; item_counter=0; - printf("4Problema = %i\n", problema_counter); + //printf("4Problema = %i\n", problema_counter); }else if (stage==5){ - problemas[problema_counter].values[item_counter++]=my_atoi(&buffer[0]); - problemas[problema_counter].values[item_counter]=-5; - problemas[problema_counter].weights[item_counter]=-5; + problemas_array[problema_counter].values[item_counter++]=my_atoi(&buffer[0]); + problemas_array[problema_counter].values[item_counter]=-5; + problemas_array[problema_counter].weights[item_counter]=-5; + problemas_array[problema_counter].n=item_counter; problema_counter++; item_counter=0; - printf("Problema = %i\n", problema_counter); + //printf("Problema = %i\n", problema_counter); } - }else if (input_char==','){ + }else if (input_char==','){ //delimiter do the message if (stage==2){ - problemas[problema_counter].pid = my_atoi(&buffer[0]); + problemas_array[problema_counter].pid = my_atoi(&buffer[0]); stage=3; - printf("Stage %i\n", stage); + //printf("Stage %i\n", stage); }else if (stage==3){ - problemas[problema_counter].cap = my_atoi(&buffer[0]); + problemas_array[problema_counter].cap = my_atoi(&buffer[0]); stage=4; - printf("Stage %i\n", stage); + //printf("Stage %i\n", stage); } else if (stage==4){ - problemas[problema_counter].weights[item_counter]=my_atoi(&buffer[0]); + problemas_array[problema_counter].weights[item_counter]=my_atoi(&buffer[0]); stage=5; - printf("Stage %i\n", stage); + //printf("Stage %i\n", stage); }else if (stage==5){ - problemas[problema_counter].values[item_counter++]=my_atoi(&buffer[0]); + problemas_array[problema_counter].values[item_counter++]=my_atoi(&buffer[0]); stage=4; - printf("Stage %i\n", stage); + //printf("Stage %i\n", stage); } buffer[0]='\0'; buffer_counter=0; - - }else if (input_char=='\n'){ + }else if (input_char=='\n'){ //newline received buffer[0]='\0'; buffer_counter=0; - }else if (input_char=='X'){ + }else if (input_char=='X'){ //end of message buffer[0]='\0'; buffer_counter=0; stage=0; - printf("\nNumber of threads = %i\n", number_threads); - for (i=0; i<problema_counter; i++) printP(problemas[i]); - parseFlag =0; + //printf("\nNumber of threads = %i\n", number_threads); + fflush(stdout); + fflush(stdin); + parseFlag =0; //exit form input loop } } - printf("\nNumber of threads = %i\n", number_threads); - printf("\nNumber of problems = %i\n", problema_counter); - printf("\n Finished \n"); - Thread thread(led_thread, (void *)1000); - osDelay(6000); - thread.terminate(); + //printf("\nNumber of threads = %i", number_threads); + //printf("\nNumber of problems = %i", problema_counter); + printf("\n Parse Finished \n"); + + osMutexWait(mutex_p_id, osWaitForever); //request lock + for (i=0; i<problema_counter; i++){ + problem_q.push(problemas_array[i]); + } + osMutexRelease(mutex_p_id); //unlock + + free(problemas_array); + + i=0; + while (i<number_threads){ + threads_array[i]= new Thread(worker_thread,(void *)(i)); + #ifdef DELAY_BTWN + Thread::wait(DELAY_BTWN_TIME); + #endif + i++; + } + + #ifdef DELAY_DISPLAY + Thread::wait(DELAY_DISPLAY_TIME); + #endif + + + while(displayFlag){ + displayFlag=0; + printf("\n&%i*",number_threads); + + while(!solution_q.empty()){ + osMutexWait(mutex_s_id, osWaitForever); + if (!solution_q.empty()){ + s = solution_q.front(); + solution_q.pop(); + printF(s); + } + osMutexRelease(mutex_s_id); + } + + + } + + + //i=0; + //while (i<number_threads) threads_array[i]; + free(threads_array); + + //osMutexWait(mutex_leds_id, osWaitForever); //request lock + // led_func(6); + //osMutexRelease(mutex_leds_id); //unlock } } - -//osStatus status; -//mutex_1_id = osMutexCreate(osMutex(mutex_1)); -//osMutexWait(mutex_1_id, osWaitForever); -//if (0== osMutexWait(mutex_1_id, 0)) { -//}else{ -// printf("Else \n\r"); -//} -//osMutexRelease(mutex_1_id); -//message_q_id = osMessageCreate(osMessageQ(message_q), NULL); -//(mutex_1_id, osWaitForever); -//osEvent event = osMessageGet(message_q_id, osWaitForever); -//printf(" %d \n\r", event.value.p); -//fflush(stdout); -//osMutexRelease(mutex_1_id); -//Thread::wait(100); -//osMutexWait(mutex_2_id, 1000); -//osMutexRelease(mutex_2_id); -//printf("\n(%c)\n", input_char); -//fflush(stdout);