/* [<][>][^][v][top][bottom][index][help] */
DEFINITIONS
This source file includes following definitions.
- initialize_bowls
- cleanup_bowls
- cat_eat
- cat_sleep
- mouse_eat
- mouse_sleep
- cat_simulation
- mouse_simulation
- catmouse
1 /*
2 * catmouse.c
3 *
4 * 30-1-2003 : GWA : Stub functions created for CS161 Asst1.
5 * 26-11-2007: KMS : Modified to use cat_eat and mouse_eat
6 * 21-04-2009: KMS : modified to use cat_sleep and mouse_sleep
7 * 21-04-2009: KMS : added sem_destroy of CatMouseWait
8 * 05-01-2012: TBB : added comments to try to clarify use/non use of volatile
9 * 22-08-2013: TBB: made cat and mouse eating and sleeping time optional parameters
10 * 27-04-2014: KMS: change this to simulation driver that invokes student-implemented synch functions
11 *
12 */
13
14
15 /*
16 * CS350 Students Note!
17 *
18 * You may not modify the code in this file in any way!
19 *
20 */
21
22
23 /*
24 *
25 * Includes
26 *
27 */
28
29 #include <types.h>
30 #include <lib.h>
31 #include <test.h>
32 #include <clock.h>
33 #include <thread.h>
34 #include <synch.h>
35 #include <synchprobs.h>
36
37 /* functions defined and used internally */
38 static void initialize_bowls(void);
39 static void cleanup_bowls(void);
40 static void cat_eat(unsigned int bowlnumber, int eat_time);
41 static void cat_sleep(int sleep_time);
42 static void mouse_eat(unsigned int bowlnumber, int eat_time);
43 static void mouse_sleep(int sleep_time);
44 static void cat_simulation(void *ptr, unsigned long catnumber);
45 static void mouse_simulation(void *ptr, unsigned long mousenumber);
46 /* static void print_state(void); */
47
48 /*
49 *
50 * Problem parameters
51 *
52 * Values for these parameters are set by the main driver
53 * function, catmouse(), based on the problem parameters
54 * that are passed in from the kernel menu command or
55 * kernel command line.
56 * changing them.
57 *
58 * These are only ever modified by one thread, at creation time,
59 * so they do not need to be volatile.
60 */
61 static int NumBowls; // number of food bowls
62 static int NumCats; // number of cats
63 static int NumMice; // number of mice
64 static int NumLoops; // number of times each cat and mouse should eat
65
66 static int CatEatTime = 1; // length of time a cat spends eating
67 static int CatSleepTime = 2; // length of time a cat spends sleeping
68 static int MouseEatTime = 1; // length of time a mouse spends eating
69 static int MouseSleepTime = 2; // length of time a mouse spends sleeping
70
71 /*
72 * Once the main driver function (catmouse()) has created the cat and mouse
73 * simulation threads, it uses this semaphore to block until all of the
74 * cat and mouse simulations are finished.
75 */
76 static struct semaphore *CatMouseWait;
77
78 /*
79 *
80 * shared simulation state
81 *
82 * note: this is state should be used only by the
83 * functions in this file, hence the static declarations
84 *
85 */
86
87 /* a character array with one entry for each bowl
88 * bowl[i-1] = 'c' if a cat is eating at the ith bowl
89 * bowl[i-1] = 'm' if a mouse is eating at the ith bowl
90 * bowl[i-1] = '-' otherwise */
91
92 /* The elements within the array can be changed by multiple
93 * threads so the contents are volatile.
94 */
95 static volatile char *bowls;
96
97 /* how many cats are currently eating?
98 * modified by multiple threads, so volatile
99 */
100 static volatile int eating_cats_count;
101
102 /* how many mice are currently eating?
103 * modified by different threads, so volatile
104 */
105 static volatile int eating_mice_count;
106
107 /* semaphore used to provide mutual exclusion
108 * for reading and writing the shared simulation state
109 * The actual mutex is created/initizliaed by one thread and not
110 * modified by others: not volatile
111 */
112 static struct semaphore *mutex;
113
114 /* performance statistics */
115 static volatile time_t cat_total_wait_secs;
116 static volatile uint32_t cat_total_wait_nsecs;
117 static volatile int cat_wait_count;
118 static volatile time_t mouse_total_wait_secs;
119 static volatile uint32_t mouse_total_wait_nsecs;
120 static volatile int mouse_wait_count;
121
122 /* mutex to provide mutual exclusion to performance stats */
123 static struct semaphore *perf_mutex;
124
125
126 /*
127 * initialize_bowls()
128 *
129 * Purpose:
130 * initializes simulation of cats and mice and bowls
131 *
132 * Arguments:
133 * unsigned int bowlcount: the number of food bowls to simulate
134 *
135 * Returns:
136 * 0 on success, 1 otherwise
137 */
138
139 static void
140 initialize_bowls()
141 {
142 int i;
143
144 KASSERT(NumBowls > 0);
145
146 bowls = kmalloc(NumBowls*sizeof(char));
147 if (bowls == NULL) {
148 panic("initialize_bowls: unable to allocate space for %d bowls\n",NumBowls);
149 }
150 /* initialize bowls */
151 for(i=0;i<NumBowls;i++) {
152 bowls[i] = '-';
153 }
154 eating_cats_count = eating_mice_count = 0;
155
156 /* intialize mutex semaphore */
157 mutex = sem_create("bowl mutex",1);
158 if (mutex == NULL) {
159 panic("initialize_bowls: could not create mutex\n");
160 }
161 /* intialize perf_mutex semaphore */
162 perf_mutex = sem_create("stats mutex",1);
163 if (perf_mutex == NULL) {
164 panic("initialize_bowls: could not create perf_mutex\n");
165 }
166
167 cat_total_wait_secs = 0;
168 cat_total_wait_nsecs = 0;
169 cat_wait_count = 0;
170 mouse_total_wait_secs = 0;
171 mouse_total_wait_nsecs = 0;
172 mouse_wait_count = 0;
173
174 return;
175 }
176
177
178 /*
179 * cleanup_bowls()
180 *
181 * Purpose:
182 * Releases resources created by initialize_bowls.
183 *
184 * Arguments:
185 * None
186 *
187 * Returns:
188 * Nothing
189 */
190
191 static void
192 cleanup_bowls()
193 {
194 if (mutex != NULL) {
195 sem_destroy( mutex );
196 mutex = NULL;
197 }
198 if (perf_mutex != NULL) {
199 sem_destroy( perf_mutex );
200 perf_mutex = NULL;
201 }
202 if (bowls != NULL) {
203 kfree( (void *) bowls );
204 bowls = NULL;
205 }
206 }
207
208 /*
209 * print_state()
210 *
211 * Purpose:
212 * displays the simulation state
213 *
214 * Arguments:
215 * none
216 *
217 * Returns:
218 * nothing
219 *
220 * Notes:
221 * this assumes that it is being called from within
222 * a critical section - it does not provide its own
223 * mutual exclusion
224 */
225
226 /* not currently used */
227 /*
228 static void
229 print_state()
230 {
231 int i;
232
233 kprintf(" Eating Cats: %3d Eating Mice: %3d ",eating_cats_count,
234 eating_mice_count);
235 for(i=0;i<NumBowls;i++) {
236 kprintf("%c",bowls[i]);
237 }
238 return;
239 }
240 */
241
242
243 /*
244 * cat_eat()
245 *
246 * Purpose:
247 * simulates a cat eating from a bowl, and checks to
248 * make sure that none of the simulation requirements
249 * have been violated.
250 *
251 * Arguments:
252 * unsigned int bowlnumber: which bowl the cat should eat from
253 *
254 * Returns:
255 * nothing
256 *
257 */
258
259 void
260 cat_eat(unsigned int bowlnumber, int eat_time)
261 {
262
263 /* check the bowl number */
264 KASSERT(bowlnumber > 0);
265 KASSERT((int)bowlnumber <= NumBowls);
266
267 /* check and update the simulation state to indicate that
268 * the cat is now eating at the specified bowl */
269 P(mutex);
270
271 /* first check whether allowing this cat to eat will
272 * violate any simulation requirements */
273 if (bowls[bowlnumber-1] == 'c') {
274 /* there is already a cat eating at the specified bowl */
275 panic("cat_eat: attempt to make two cats eat from bowl %d!\n",bowlnumber);
276 }
277 if (eating_mice_count > 0) {
278 /* there is already a mouse eating at some bowl */
279 panic("cat_eat: attempt to make a cat eat while mice are eating!\n");
280 }
281 KASSERT(bowls[bowlnumber-1]=='-');
282 KASSERT(eating_mice_count == 0);
283
284 /* now update the state to indicate that the cat is eating */
285 eating_cats_count += 1;
286 bowls[bowlnumber-1] = 'c';
287
288 DEBUG(DB_SYNCPROB,"cat starts to eat at bowl %d [%d:%d]\n",
289 bowlnumber,eating_cats_count,eating_mice_count);
290 V(mutex); // end critical section
291
292 /* simulate eating by introducing a delay
293 * note that eating is not part of the critical section */
294 clocksleep(eat_time);
295
296 /* update the simulation state to indicate that
297 * the cat is finished eating */
298 P(mutex); // start critical section
299 KASSERT(eating_cats_count > 0);
300 KASSERT(bowls[bowlnumber-1]=='c');
301 eating_cats_count -= 1;
302 bowls[bowlnumber-1]='-';
303
304 DEBUG(DB_SYNCPROB,"cat finished eating at bowl %d [%d:%d]\n",
305 bowlnumber,eating_cats_count,eating_mice_count);
306 V(mutex); // end critical section
307
308 return;
309 }
310
311 /*
312 * cat_sleep()
313 *
314 * Purpose:
315 * simulates a cat sleeping
316 *
317 * Arguments: none
318 *
319 * Returns: nothing
320 *
321 */
322 void
323 cat_sleep(int sleep_time)
324 {
325 /* simulate sleeping by introducing a delay */
326 clocksleep(sleep_time);
327 return;
328 }
329
330
331 /*
332 * mouse_eat()
333 *
334 * Purpose:
335 * simulates a mouse eating from a bowl, and checks to
336 * make sure that none of the simulation requirements
337 * have been violated.
338 *
339 * Arguments:
340 * unsigned int bowlnumber: which bowl the mouse should eat from
341 *
342 * Returns:
343 * nothing
344 *
345 */
346
347 void
348 mouse_eat(unsigned int bowlnumber, int eat_time)
349 {
350 /* check the bowl number */
351 KASSERT(bowlnumber > 0);
352 KASSERT((int)bowlnumber <= NumBowls);
353
354 /* check and updated the simulation state to indicate that
355 * the mouse is now eating at the specified bowl. */
356 P(mutex); // start critical section
357
358 /* first check whether allowing this mouse to eat will
359 * violate any simulation requirements */
360 if (bowls[bowlnumber-1] == 'm') {
361 /* there is already a mouse eating at the specified bowl */
362 panic("mouse_eat: attempt to make two mice eat from bowl %d!\n",bowlnumber);
363 }
364 if (eating_cats_count > 0) {
365 /* there is already a cat eating at some bowl */
366 panic("mouse_eat: attempt to make a mouse eat while cats are eating!\n");
367 }
368 KASSERT(bowls[bowlnumber-1]=='-');
369 KASSERT(eating_cats_count == 0);
370
371 /* now update the state to indicate that the mouse is eating */
372 eating_mice_count += 1;
373 bowls[bowlnumber-1] = 'm';
374
375 DEBUG(DB_SYNCPROB,"mouse starts to eat at bowl %d [%d:%d]\n",
376 bowlnumber,eating_cats_count,eating_mice_count);
377 V(mutex); // end critical section
378
379 /* simulate eating by introducing a delay
380 * note that eating is not part of the critical section */
381 clocksleep(eat_time);
382
383 /* update the simulation state to indicate that
384 * the mouse is finished eating */
385 P(mutex); // start critical section
386
387 KASSERT(eating_mice_count > 0);
388 eating_mice_count -= 1;
389 KASSERT(bowls[bowlnumber-1]=='m');
390 bowls[bowlnumber-1]='-';
391
392 DEBUG(DB_SYNCPROB,"mouse finishes eating at bowl %d [%d:%d]\n",
393 bowlnumber,eating_cats_count,eating_mice_count);
394 V(mutex); // end critical section
395 return;
396 }
397
398 /*
399 * mouse_sleep()
400 *
401 * Purpose:
402 * simulates a mouse sleeping
403 *
404 * Arguments: none
405 *
406 * Returns: nothing
407 *
408 */
409 void
410 mouse_sleep(int sleep_time)
411 {
412 /* simulate sleeping by introducing a delay */
413 clocksleep(sleep_time);
414 return;
415 }
416
417 /*
418 * cat_simulation()
419 *
420 * Arguments:
421 * void * unusedpointer: currently unused.
422 * unsigned long catnumber: holds cat identifier from 0 to NumCats-1.
423 *
424 * Returns:
425 * nothing.
426 *
427 * Notes:
428 * Each cat simulation thread runs this function.
429 *
430 */
431
432 static
433 void
434 cat_simulation(void * unusedpointer,
435 unsigned long catnumber)
436 {
437 int i;
438 unsigned int bowl;
439 time_t before_sec, after_sec, wait_sec;
440 uint32_t before_nsec, after_nsec, wait_nsec;
441
442 /* avoid unused variable warnings. */
443 (void) unusedpointer;
444 (void) catnumber;
445
446
447 for(i=0;i<NumLoops;i++) {
448
449 /* make the cat sleep */
450 cat_sleep(CatSleepTime);
451
452 /* choose bowl. legal bowl numbers range from 1 to NumBowls */
453 bowl = ((unsigned int)random() % NumBowls) + 1;
454
455 gettime(&before_sec,&before_nsec);
456 cat_before_eating(bowl); /* student-implemented function */
457 gettime(&after_sec,&after_nsec);
458
459 /* make the cat eat */
460 cat_eat(bowl, CatEatTime);
461
462 cat_after_eating(bowl); /* student-implemented function */
463
464 /* update wait time statistics */
465 getinterval(before_sec,before_nsec,after_sec,after_nsec,&wait_sec,&wait_nsec);
466 P(perf_mutex);
467 cat_total_wait_secs += wait_sec;
468 cat_total_wait_nsecs += wait_nsec;
469 if (cat_total_wait_nsecs > 1000000000) {
470 cat_total_wait_nsecs -= 1000000000;
471 cat_total_wait_secs ++;
472 }
473 cat_wait_count++;
474 V(perf_mutex);
475 }
476
477 /* indicate that this cat simulation is finished */
478 V(CatMouseWait);
479 }
480
481 /*
482 * mouse_simulation()
483 *
484 * Arguments:
485 * void * unusedpointer: currently unused.
486 * unsigned long mousenumber: holds mouse identifier from 0 to NumMice-1.
487 *
488 * Returns:
489 * nothing.
490 *
491 * Notes:
492 * each mouse simulation thread runs this function
493 *
494 */
495
496 static
497 void
498 mouse_simulation(void * unusedpointer,
499 unsigned long mousenumber)
500 {
501 int i;
502 unsigned int bowl;
503 time_t before_sec, after_sec, wait_sec;
504 uint32_t before_nsec, after_nsec, wait_nsec;
505
506 /* Avoid unused variable warnings. */
507 (void) unusedpointer;
508 (void) mousenumber;
509
510 for(i=0;i<NumLoops;i++) {
511
512 /* make the mouse sleep */
513 mouse_sleep(MouseSleepTime);
514
515 /* choose bowl. legal bowl numbers range from 1 to NumBowls */
516 bowl = ((unsigned int)random() % NumBowls) + 1;
517
518 gettime(&before_sec,&before_nsec);
519 mouse_before_eating(bowl); /* student-implemented function */
520 gettime(&after_sec,&after_nsec);
521
522 /* make the mouse eat */
523 mouse_eat(bowl, MouseEatTime);
524
525 mouse_after_eating(bowl); /* student-implemented function */
526
527 /* update wait time statistics */
528 getinterval(before_sec,before_nsec,after_sec,after_nsec,&wait_sec,&wait_nsec);
529 P(perf_mutex);
530 mouse_total_wait_secs += wait_sec;
531 mouse_total_wait_nsecs += wait_nsec;
532 if (mouse_total_wait_nsecs > 1000000000) {
533 mouse_total_wait_nsecs -= 1000000000;
534 mouse_total_wait_secs ++;
535 }
536 mouse_wait_count++;
537 V(perf_mutex);
538 }
539
540 /* indicate that this mouse is finished */
541 V(CatMouseWait);
542 }
543
544 /*
545 * catmouse()
546 *
547 * Arguments:
548 * int nargs: should be 5 or 9
549 * char ** args: args[1] = number of food bowls
550 * args[2] = number of cats
551 * args[3] = number of mice
552 * args[4] = number of loops
553 * Optional parameters
554 * args[5] = cat eating time
555 * args[6] = cat sleeping time
556 * args[7] = mouse eating time
557 * args[8] = mouse sleeping time
558 *
559 * Returns:
560 * 0 on success.
561 *
562 * Notes:
563 * Driver code to start up cat_simulation() and
564 * mouse_simulation() threads.
565 */
566
567 int
568 catmouse(int nargs,
569 char ** args)
570 {
571 int catindex, mouseindex, error;
572 int i;
573 int mean_cat_wait_usecs, mean_mouse_wait_usecs;
574 time_t before_sec, after_sec, wait_sec;
575 uint32_t before_nsec, after_nsec, wait_nsec;
576 int total_bowl_milliseconds, total_eating_milliseconds, utilization_percent;
577
578 /* check and process command line arguments */
579 if ((nargs != 9) && (nargs != 5)) {
580 kprintf("Usage: <command> NUM_BOWLS NUM_CATS NUM_MICE NUM_LOOPS\n");
581 kprintf("or\n");
582 kprintf("Usage: <command> NUM_BOWLS NUM_CATS NUM_MICE NUM_LOOPS ");
583 kprintf("CAT_EATING_TIME CAT_SLEEPING_TIME MOUSE_EATING_TIME MOUSE_SLEEPING_TIME\n");
584 return 1; // return failure indication
585 }
586
587 /* check the problem parameters, and set the global variables */
588 NumBowls = atoi(args[1]);
589 if (NumBowls <= 0) {
590 kprintf("catmouse: invalid number of bowls: %d\n",NumBowls);
591 return 1;
592 }
593 NumCats = atoi(args[2]);
594 if (NumCats < 0) {
595 kprintf("catmouse: invalid number of cats: %d\n",NumCats);
596 return 1;
597 }
598 NumMice = atoi(args[3]);
599 if (NumMice < 0) {
600 kprintf("catmouse: invalid number of mice: %d\n",NumMice);
601 return 1;
602 }
603 NumLoops = atoi(args[4]);
604 if (NumLoops <= 0) {
605 kprintf("catmouse: invalid number of loops: %d\n",NumLoops);
606 return 1;
607 }
608
609 if (nargs == 9) {
610 CatEatTime = atoi(args[5]);
611 if (CatEatTime < 0) {
612 kprintf("catmouse: invalid cat eating time: %d\n",CatEatTime);
613 return 1;
614 }
615
616 CatSleepTime = atoi(args[6]);
617 if (CatSleepTime < 0) {
618 kprintf("catmouse: invalid cat sleeping time: %d\n",CatSleepTime);
619 return 1;
620 }
621
622 MouseEatTime = atoi(args[7]);
623 if (MouseEatTime < 0) {
624 kprintf("catmouse: invalid mouse eating time: %d\n",MouseEatTime);
625 return 1;
626 }
627
628 MouseSleepTime = atoi(args[8]);
629 if (MouseSleepTime < 0) {
630 kprintf("catmouse: invalid mouse sleeping time: %d\n",MouseSleepTime);
631 return 1;
632 }
633 }
634
635 kprintf("Using %d bowls, %d cats, and %d mice. Looping %d times.\n",
636 NumBowls,NumCats,NumMice,NumLoops);
637 kprintf("Using cat eating time %d, cat sleeping time %d\n", CatEatTime, CatSleepTime);
638 kprintf("Using mouse eating time %d, mouse sleeping time %d\n", MouseEatTime, MouseSleepTime);
639
640 /* create the semaphore that is used to make the main thread
641 wait for all of the cats and mice to finish */
642 CatMouseWait = sem_create("CatMouseWait",0);
643 if (CatMouseWait == NULL) {
644 panic("catmouse: could not create semaphore\n");
645 }
646
647 /* initialize our simulation state */
648 initialize_bowls();
649
650 /* initialize the synchronization functions */
651 catmouse_sync_init(NumBowls);
652
653 /* get current time, for measuring total simulation time */
654 gettime(&before_sec,&before_nsec);
655
656 /*
657 * Start NumCats cat_simulation() threads and NumMice mouse_simulation() threads.
658 * Alternate cat and mouse creation.
659 */
660 for (catindex = 0; catindex < NumCats; catindex++) {
661 error = thread_fork("cat_simulation thread", NULL, cat_simulation, NULL, catindex);
662 if (error) {
663 panic("cat_simulation: thread_fork failed: %s\n", strerror(error));
664 }
665 if (catindex < NumMice) {
666 error = thread_fork("mouse_simulation thread", NULL, mouse_simulation, NULL, catindex);
667 if (error) {
668 panic("mouse_simulation: thread_fork failed: %s\n",strerror(error));
669 }
670 }
671 }
672 /* launch any remaining mice */
673 for(mouseindex = catindex; mouseindex < NumMice; mouseindex++) {
674 error = thread_fork("mouse_simulation thread", NULL, mouse_simulation, NULL, mouseindex);
675 if (error) {
676 panic("mouse_simulation: thread_fork failed: %s\n",strerror(error));
677 }
678 }
679
680 /* wait for all of the cats and mice to finish before
681 terminating */
682 for(i=0;i<(NumCats+NumMice);i++) {
683 P(CatMouseWait);
684 }
685
686 /* get current time, for measuring total simulation time */
687 gettime(&after_sec,&after_nsec);
688 /* compute total simulation time */
689 getinterval(before_sec,before_nsec,after_sec,after_nsec,&wait_sec,&wait_nsec);
690 /* compute and report bowl utilization */
691 total_bowl_milliseconds = (wait_sec*1000 + wait_nsec/1000000)*NumBowls;
692 total_eating_milliseconds = (NumCats*CatEatTime + NumMice*MouseEatTime)*NumLoops*1000;
693 if (total_bowl_milliseconds > 0) {
694 utilization_percent = total_eating_milliseconds*100/total_bowl_milliseconds;
695 kprintf("Bowl utilization: %d%%\n",utilization_percent);
696 }
697
698 /* clean up the semaphore that we created */
699 sem_destroy(CatMouseWait);
700
701 /* clean up the synchronization state */
702 catmouse_sync_cleanup(NumBowls);
703
704 /* clean up resources used for tracking bowl use */
705 cleanup_bowls();
706
707 if (cat_wait_count > 0) {
708 /* some rounding error here - not significant if cat_wait_count << 1000000 */
709 mean_cat_wait_usecs = (cat_total_wait_secs*1000000+cat_total_wait_nsecs/1000)/cat_wait_count;
710 kprintf("Mean cat waiting time: %d.%d seconds\n",mean_cat_wait_usecs/1000000,mean_cat_wait_usecs%1000000);
711 }
712 if (mouse_wait_count > 0) {
713 /* some rounding error here - not significant if mouse_wait_count << 1000000 */
714 mean_mouse_wait_usecs = (mouse_total_wait_secs*1000000+mouse_total_wait_nsecs/1000)/mouse_wait_count;
715 kprintf("Mean mouse waiting time: %d.%d seconds\n",mean_mouse_wait_usecs/1000000,mean_mouse_wait_usecs%1000000);
716 }
717
718 return 0;
719 }
720
721 /*
722 * End of catmouse.c
723 */