Julio Fajardo / Mbed 2 deprecated FRDM-K64_Threads_copy2

Threads copy 2

Dependencies:   SDFileSystem mbed-rtos mbed

Fork of FRDM-K64_Threads_copy by Julio Fajardo

main.cpp@3:8647bf7682b2, 2015-10-29 (annotated)

Committer:
julioefajardo
Date:
Thu Oct 29 22:29:08 2015 +0000
Revision:
3:8647bf7682b2
Parent:
0:e1c215fe231c
Child:
4:8a7e0bc98db0
Multithreading Knapsack Problem Solution

Who changed what in which revision?

UserRevisionLine numberNew contents of line
julioefajardo 3:8647bf7682b2 1 #include <stdio.h>
Kojto 0:e1c215fe231c 2 #include "mbed.h"
Kojto 0:e1c215fe231c 3 #include "SDFileSystem.h"
julioefajardo 3:8647bf7682b2 4 #include "rtos.h"
Kojto 0:e1c215fe231c 5
julioefajardo 3:8647bf7682b2 6 #define CTIME 50
julioefajardo 3:8647bf7682b2 7 #define WTIME 150
julioefajardo 3:8647bf7682b2 8
julioefajardo 3:8647bf7682b2 9 SDFileSystem sd(PTE3, PTE1, PTE2, PTE4, "sd");
Kojto 0:e1c215fe231c 10 Serial pc(USBTX, USBRX);
julioefajardo 3:8647bf7682b2 11 DigitalOut ledr(LED_RED);
julioefajardo 3:8647bf7682b2 12 DigitalOut ledg(LED_GREEN);
julioefajardo 3:8647bf7682b2 13 DigitalOut ledb(LED_BLUE);
julioefajardo 3:8647bf7682b2 14 Timer ProgramTimer;
julioefajardo 3:8647bf7682b2 15
julioefajardo 3:8647bf7682b2 16 int n_threads = 0;
julioefajardo 3:8647bf7682b2 17 int i = 0;
julioefajardo 3:8647bf7682b2 18 int j = 0;
julioefajardo 3:8647bf7682b2 19 int k = 0;
julioefajardo 3:8647bf7682b2 20 int l = 0;
julioefajardo 3:8647bf7682b2 21 int n = 0;
julioefajardo 3:8647bf7682b2 22
julioefajardo 3:8647bf7682b2 23 typedef struct {
julioefajardo 3:8647bf7682b2 24 int id;
julioefajardo 3:8647bf7682b2 25 int cap;
julioefajardo 3:8647bf7682b2 26 int n_objects;
julioefajardo 3:8647bf7682b2 27 int weight[32];
julioefajardo 3:8647bf7682b2 28 int value[32];
julioefajardo 3:8647bf7682b2 29 } knapsack;
julioefajardo 3:8647bf7682b2 30
julioefajardo 3:8647bf7682b2 31 typedef struct {
julioefajardo 3:8647bf7682b2 32 int tid;
julioefajardo 3:8647bf7682b2 33 int led;
julioefajardo 3:8647bf7682b2 34 int pid;
julioefajardo 3:8647bf7682b2 35 int cap;
julioefajardo 3:8647bf7682b2 36 int optimal;
julioefajardo 3:8647bf7682b2 37 int n_solutions;
julioefajardo 3:8647bf7682b2 38 int weight[32];
julioefajardo 3:8647bf7682b2 39 int value[32];
julioefajardo 3:8647bf7682b2 40 unsigned long ts_begin;
julioefajardo 3:8647bf7682b2 41 unsigned long ts_end;
julioefajardo 3:8647bf7682b2 42 } solution;
julioefajardo 3:8647bf7682b2 43
julioefajardo 3:8647bf7682b2 44 char *temp;
julioefajardo 3:8647bf7682b2 45 int *ttemp;
julioefajardo 3:8647bf7682b2 46 int *vsol;
julioefajardo 3:8647bf7682b2 47 int *wsol;
julioefajardo 3:8647bf7682b2 48 int sol = 0;
julioefajardo 3:8647bf7682b2 49
julioefajardo 3:8647bf7682b2 50 int phead, ptail;
julioefajardo 3:8647bf7682b2 51 int shead, stail;
julioefajardo 3:8647bf7682b2 52 knapsack *knapsacks;
julioefajardo 3:8647bf7682b2 53 knapsack *pQueue;
julioefajardo 3:8647bf7682b2 54 knapsack salida;
julioefajardo 3:8647bf7682b2 55 solution *solutions;
julioefajardo 3:8647bf7682b2 56 solution output;
julioefajardo 3:8647bf7682b2 57
julioefajardo 3:8647bf7682b2 58 Thread *threads[10];
julioefajardo 3:8647bf7682b2 59
julioefajardo 3:8647bf7682b2 60 Mutex mutex_p;
julioefajardo 3:8647bf7682b2 61 Mutex mutex_s;
Kojto 0:e1c215fe231c 62
julioefajardo 3:8647bf7682b2 63 int max(int a, int b);
julioefajardo 3:8647bf7682b2 64 solution KnapSack(int W, int wt[], int val[], int n);
julioefajardo 3:8647bf7682b2 65 void init_pQueue(void);
julioefajardo 3:8647bf7682b2 66 void init_sQueue(void);
julioefajardo 3:8647bf7682b2 67 int ispEmpty();
julioefajardo 3:8647bf7682b2 68 int issEmpty();
julioefajardo 3:8647bf7682b2 69 void pEnqueue(knapsack p);
julioefajardo 3:8647bf7682b2 70 void sEnqueue(solution s);
julioefajardo 3:8647bf7682b2 71 knapsack pDequeue();
julioefajardo 3:8647bf7682b2 72 solution sDequeue();
julioefajardo 3:8647bf7682b2 73
julioefajardo 3:8647bf7682b2 74 void worker(void const *args);
julioefajardo 3:8647bf7682b2 75
julioefajardo 3:8647bf7682b2 76 int main(){
julioefajardo 3:8647bf7682b2 77 ledr=1; ledg=1; ledb=1;
julioefajardo 3:8647bf7682b2 78 FILE *ptr_file;
julioefajardo 3:8647bf7682b2 79 char *plinea = (char *)malloc(128*sizeof(char));
julioefajardo 3:8647bf7682b2 80 char *linea = (char *)malloc(128*sizeof(char));
julioefajardo 3:8647bf7682b2 81 char *temp = (char *)malloc(4*sizeof(char));
julioefajardo 3:8647bf7682b2 82 int *ttemp = (int *)malloc(128*sizeof(int));
julioefajardo 3:8647bf7682b2 83 knapsacks = (knapsack *)malloc(32*sizeof(knapsack));
julioefajardo 3:8647bf7682b2 84 pQueue = (knapsack *)malloc(32*sizeof(knapsack));
julioefajardo 3:8647bf7682b2 85 solutions = (solution *)malloc(32*sizeof(solution));
julioefajardo 3:8647bf7682b2 86
julioefajardo 3:8647bf7682b2 87 pc.baud(115200);
julioefajardo 3:8647bf7682b2 88 pc.printf("\n\rInitializing\n\r");
julioefajardo 3:8647bf7682b2 89 pc.printf("============ \n\r");
julioefajardo 3:8647bf7682b2 90 wait(0.5f);
Kojto 0:e1c215fe231c 91
julioefajardo 3:8647bf7682b2 92 ProgramTimer.start();
julioefajardo 3:8647bf7682b2 93 ptr_file = fopen("/sd/test.txt","r");
julioefajardo 3:8647bf7682b2 94
julioefajardo 3:8647bf7682b2 95 fgets(plinea,512,ptr_file);
julioefajardo 3:8647bf7682b2 96 n_threads = plinea[1]-'0';
julioefajardo 3:8647bf7682b2 97 init_pQueue();
julioefajardo 3:8647bf7682b2 98 init_sQueue();
julioefajardo 3:8647bf7682b2 99
julioefajardo 3:8647bf7682b2 100 n=0;
julioefajardo 3:8647bf7682b2 101 while( !feof(ptr_file) ){
julioefajardo 3:8647bf7682b2 102 fgets(linea,512,ptr_file);
julioefajardo 3:8647bf7682b2 103 i=1; j=0; l=0;
julioefajardo 3:8647bf7682b2 104 while(linea[i]!='*'){
julioefajardo 3:8647bf7682b2 105 if (linea[i]!=','){
julioefajardo 3:8647bf7682b2 106 temp[j]=linea[i];
julioefajardo 3:8647bf7682b2 107 j++;
julioefajardo 3:8647bf7682b2 108 } else {
julioefajardo 3:8647bf7682b2 109 temp[j]='\0';
julioefajardo 3:8647bf7682b2 110 ttemp[l]=atoi(temp);
julioefajardo 3:8647bf7682b2 111 j=0; l++;
julioefajardo 3:8647bf7682b2 112 }
julioefajardo 3:8647bf7682b2 113 ttemp[l]=atoi(temp);
julioefajardo 3:8647bf7682b2 114 i++;
julioefajardo 3:8647bf7682b2 115 }
julioefajardo 3:8647bf7682b2 116 for(k=0;k<=l;k++){
julioefajardo 3:8647bf7682b2 117 if(k==0) knapsacks[n].id=ttemp[k];
julioefajardo 3:8647bf7682b2 118 if(k==1) knapsacks[n].cap=ttemp[k];
julioefajardo 3:8647bf7682b2 119 if((k>1)&&((k%2)==0)) knapsacks[n].weight[k/2-1]=ttemp[k];
julioefajardo 3:8647bf7682b2 120 if((k>2)&&((k%2)!=0)) knapsacks[n].value[k/2-1]=ttemp[k];
julioefajardo 3:8647bf7682b2 121 }
julioefajardo 3:8647bf7682b2 122 knapsacks[n].n_objects=l/2;
julioefajardo 3:8647bf7682b2 123 pEnqueue(knapsacks[n]);
julioefajardo 3:8647bf7682b2 124 n++;
Kojto 0:e1c215fe231c 125 }
julioefajardo 3:8647bf7682b2 126
julioefajardo 3:8647bf7682b2 127 pc.printf("id\tcap\tn\titems\n\r");
julioefajardo 3:8647bf7682b2 128 for(i=0;i<n;i++){
julioefajardo 3:8647bf7682b2 129 pc.printf("%d\t%d\t%d\t",knapsacks[i].id,knapsacks[i].cap,knapsacks[i].n_objects);
julioefajardo 3:8647bf7682b2 130 for(j=0;j<knapsacks[i].n_objects;j++) pc.printf("%d,%d ",knapsacks[i].weight[j],knapsacks[i].value[j]);
julioefajardo 3:8647bf7682b2 131 pc.printf("\n\r");
Kojto 0:e1c215fe231c 132 }
julioefajardo 3:8647bf7682b2 133 pc.printf("\n\r");
julioefajardo 3:8647bf7682b2 134
julioefajardo 3:8647bf7682b2 135 fclose(ptr_file);
julioefajardo 3:8647bf7682b2 136 free(plinea);
julioefajardo 3:8647bf7682b2 137 free(linea);
julioefajardo 3:8647bf7682b2 138 free(temp);
julioefajardo 3:8647bf7682b2 139 free(ttemp);
julioefajardo 3:8647bf7682b2 140
julioefajardo 3:8647bf7682b2 141 /*pc.printf("No Thread Solution\n\r");
julioefajardo 3:8647bf7682b2 142 pc.printf("==================\n\r");
julioefajardo 3:8647bf7682b2 143 pc.printf("#tid\t#pid\tcap\tsol\titems\n\r");
julioefajardo 3:8647bf7682b2 144 for(j=0;j<n;j++){
julioefajardo 3:8647bf7682b2 145 solutions[j] = KnapSack(knapsacks[j].cap,knapsacks[j].weight,knapsacks[j].value,knapsacks[j].n_objects);
julioefajardo 3:8647bf7682b2 146 pc.printf("main\t%d\t%d\t%d\t",j+1,knapsacks[j].cap,solutions[j].optimal);
julioefajardo 3:8647bf7682b2 147 for(i=0;i<solutions[j].n_solutions;i++) pc.printf("%d,%d,",solutions[j].weight[i],solutions[j].value[i]);
julioefajardo 3:8647bf7682b2 148 pc.printf("\n\r");
julioefajardo 3:8647bf7682b2 149 }*/
julioefajardo 3:8647bf7682b2 150 pc.printf("\n\r");
julioefajardo 3:8647bf7682b2 151 pc.printf("Thread Solution\n\r");
julioefajardo 3:8647bf7682b2 152 pc.printf("===============\n\r");
julioefajardo 3:8647bf7682b2 153
julioefajardo 3:8647bf7682b2 154 for(i=0;i<n_threads;i++){
julioefajardo 3:8647bf7682b2 155 threads[i] = new Thread(worker,(void *)(i+1));
julioefajardo 3:8647bf7682b2 156 Thread::wait(CTIME);
Kojto 0:e1c215fe231c 157 }
julioefajardo 3:8647bf7682b2 158 pc.printf("&%d*\n\r",n_threads);
julioefajardo 3:8647bf7682b2 159
julioefajardo 3:8647bf7682b2 160 while(1){
julioefajardo 3:8647bf7682b2 161 if(!issEmpty()){
julioefajardo 3:8647bf7682b2 162 mutex_s.lock();
julioefajardo 3:8647bf7682b2 163 output = sDequeue();
julioefajardo 3:8647bf7682b2 164 mutex_s.unlock();
julioefajardo 3:8647bf7682b2 165 pc.printf("#%d(%d),%d,%d,",output.led,output.tid,output.pid,output.cap);
julioefajardo 3:8647bf7682b2 166 for(i=0;i<output.n_solutions;i++) pc.printf("%d,%d,",output.weight[i],output.value[i]);
julioefajardo 3:8647bf7682b2 167 pc.printf("%.3f,%.3f,%.3f*\n\r",output.ts_begin/1000.0f,output.ts_end/1000.0f,(output.ts_end-output.ts_begin)/1000.0f);
julioefajardo 3:8647bf7682b2 168 ledr = !(output.led/2/2);
julioefajardo 3:8647bf7682b2 169 ledg = !(output.led/2%2);
julioefajardo 3:8647bf7682b2 170 ledb = !(output.led%2);
julioefajardo 3:8647bf7682b2 171 } else{
julioefajardo 3:8647bf7682b2 172 free(knapsacks);
julioefajardo 3:8647bf7682b2 173 free(pQueue);
julioefajardo 3:8647bf7682b2 174 free(solutions);
julioefajardo 3:8647bf7682b2 175 }
julioefajardo 3:8647bf7682b2 176 Thread::wait(1000);
julioefajardo 3:8647bf7682b2 177 }
Kojto 0:e1c215fe231c 178 }
Kojto 0:e1c215fe231c 179
Kojto 0:e1c215fe231c 180
julioefajardo 3:8647bf7682b2 181 solution KnapSack(int cap, int weight[], int value[], int n){
julioefajardo 3:8647bf7682b2 182 solution s;
julioefajardo 3:8647bf7682b2 183 int i, w;
julioefajardo 3:8647bf7682b2 184 int j = 0;
julioefajardo 3:8647bf7682b2 185 int sol = 0;
julioefajardo 3:8647bf7682b2 186 int K[n+1][cap+1];
julioefajardo 3:8647bf7682b2 187 s.ts_begin = ProgramTimer.read_us();
julioefajardo 3:8647bf7682b2 188 for(i=0;i<=n;i++){
julioefajardo 3:8647bf7682b2 189 for(w=0;w<=cap;w++){
julioefajardo 3:8647bf7682b2 190 if(i==0||w==0) K[i][w]=0;
julioefajardo 3:8647bf7682b2 191 else if(weight[i-1]<=w) K[i][w]=max(value[i-1]+K[i-1][w-weight[i-1]],K[i-1][w]);
julioefajardo 3:8647bf7682b2 192 else K[i][w]=K[i-1][w];
julioefajardo 3:8647bf7682b2 193 }
julioefajardo 3:8647bf7682b2 194 }
julioefajardo 3:8647bf7682b2 195 w=cap;
julioefajardo 3:8647bf7682b2 196 for(i=n;i>0;i--){
julioefajardo 3:8647bf7682b2 197 if(K[i][w]!=K[i-1][w]){
julioefajardo 3:8647bf7682b2 198 s.value[j] = value[i-1];
julioefajardo 3:8647bf7682b2 199 s.weight[j] = weight[i-1];
julioefajardo 3:8647bf7682b2 200 w=w-weight[i-1];
julioefajardo 3:8647bf7682b2 201 sol++;
julioefajardo 3:8647bf7682b2 202 j++;
julioefajardo 3:8647bf7682b2 203 }
julioefajardo 3:8647bf7682b2 204 }
julioefajardo 3:8647bf7682b2 205 s.ts_end = ProgramTimer.read_us();
julioefajardo 3:8647bf7682b2 206 s.optimal = K[n][cap];
julioefajardo 3:8647bf7682b2 207 s.n_solutions = sol;
julioefajardo 3:8647bf7682b2 208 return s;
julioefajardo 3:8647bf7682b2 209 }
Kojto 0:e1c215fe231c 210
julioefajardo 3:8647bf7682b2 211 int max(int a, int b){
julioefajardo 3:8647bf7682b2 212 return (a>b)?a:b;
julioefajardo 3:8647bf7682b2 213 }
julioefajardo 3:8647bf7682b2 214
julioefajardo 3:8647bf7682b2 215 void init_pQueue(void){
julioefajardo 3:8647bf7682b2 216 phead = ptail = -1;
julioefajardo 3:8647bf7682b2 217 }
julioefajardo 3:8647bf7682b2 218
julioefajardo 3:8647bf7682b2 219 int ispEmpty(){
julioefajardo 3:8647bf7682b2 220 return (phead == ptail);
julioefajardo 3:8647bf7682b2 221 }
julioefajardo 3:8647bf7682b2 222
julioefajardo 3:8647bf7682b2 223 void pEnqueue(knapsack p){
julioefajardo 3:8647bf7682b2 224 ptail++;
julioefajardo 3:8647bf7682b2 225 pQueue[ptail] = p;
Kojto 0:e1c215fe231c 226 }
Kojto 0:e1c215fe231c 227
julioefajardo 3:8647bf7682b2 228 knapsack pDequeue(){
julioefajardo 3:8647bf7682b2 229 knapsack p;
julioefajardo 3:8647bf7682b2 230 phead++;
julioefajardo 3:8647bf7682b2 231 p = pQueue[phead];
julioefajardo 3:8647bf7682b2 232 return p;
julioefajardo 3:8647bf7682b2 233 }
Kojto 0:e1c215fe231c 234
julioefajardo 3:8647bf7682b2 235 void init_sQueue(void){
julioefajardo 3:8647bf7682b2 236 shead = stail = -1;
julioefajardo 3:8647bf7682b2 237 }
Kojto 0:e1c215fe231c 238
julioefajardo 3:8647bf7682b2 239 int issEmpty(){
julioefajardo 3:8647bf7682b2 240 return (shead == stail);
julioefajardo 3:8647bf7682b2 241 }
Kojto 0:e1c215fe231c 242
Kojto 0:e1c215fe231c 243
julioefajardo 3:8647bf7682b2 244 void sEnqueue(solution s){
julioefajardo 3:8647bf7682b2 245 stail++;
julioefajardo 3:8647bf7682b2 246 solutions[stail] = s;
julioefajardo 3:8647bf7682b2 247 }
julioefajardo 3:8647bf7682b2 248
julioefajardo 3:8647bf7682b2 249 solution sDequeue(){
julioefajardo 3:8647bf7682b2 250 solution s;
julioefajardo 3:8647bf7682b2 251 shead++;
julioefajardo 3:8647bf7682b2 252 s = solutions[shead];
julioefajardo 3:8647bf7682b2 253 return s;
julioefajardo 3:8647bf7682b2 254 }
Kojto 0:e1c215fe231c 255
julioefajardo 3:8647bf7682b2 256 void worker(void const *args){
julioefajardo 3:8647bf7682b2 257 solution temp;
julioefajardo 3:8647bf7682b2 258 knapsack doc;
julioefajardo 3:8647bf7682b2 259 osThreadId id;
julioefajardo 3:8647bf7682b2 260 while (true) {
julioefajardo 3:8647bf7682b2 261 if(!ispEmpty()){
julioefajardo 3:8647bf7682b2 262 mutex_p.lock();
julioefajardo 3:8647bf7682b2 263 doc = pDequeue();
julioefajardo 3:8647bf7682b2 264 mutex_p.unlock();
julioefajardo 3:8647bf7682b2 265 temp = KnapSack(doc.cap,doc.weight,doc.value,doc.n_objects);
julioefajardo 3:8647bf7682b2 266 temp.pid = doc.id;
julioefajardo 3:8647bf7682b2 267 temp.cap = doc.cap;
julioefajardo 3:8647bf7682b2 268 temp.tid = (uint32_t)osThreadGetId();
julioefajardo 3:8647bf7682b2 269 temp.led = (uint32_t)args;
julioefajardo 3:8647bf7682b2 270 mutex_s.lock();
julioefajardo 3:8647bf7682b2 271 sEnqueue(temp);
julioefajardo 3:8647bf7682b2 272 mutex_s.unlock();
julioefajardo 3:8647bf7682b2 273 } else{
julioefajardo 3:8647bf7682b2 274 id = osThreadGetId();
julioefajardo 3:8647bf7682b2 275 osThreadTerminate(id);
julioefajardo 3:8647bf7682b2 276 }
julioefajardo 3:8647bf7682b2 277 Thread::wait(WTIME);
julioefajardo 3:8647bf7682b2 278 osThreadYield();
Kojto 0:e1c215fe231c 279 }
Kojto 0:e1c215fe231c 280 }