6
\$\begingroup\$

My homework was to organize semaphores into a pyramid. The task was accomplished, but I ended up with this long ugly conditional and was wondering if anyone can see a better way/algorithm to accomplish the same thing.

if (me==0) {
    wait_sem(semaphore[1]);
    wait_sem(semaphore[2]);
    signal_sem(semaphore[0]);

}

if (me==1) {
    wait_sem(semaphore[3]);
    wait_sem(semaphore[4]);

}
if (me==2) {
    wait_sem(semaphore[4]);
    wait_sem(semaphore[5]);

}

if (me==3) {
    wait_sem(semaphore[6]);
    wait_sem(semaphore[7]);

}
if (me==4) {
    wait_sem(semaphore[7]);
    wait_sem(semaphore[8]);

}
if (me==5) {
    wait_sem(semaphore[8]);
    wait_sem(semaphore[9]);

}
if (me==6) {
    wait_sem(semaphore[10]);
    wait_sem(semaphore[11]);

}
if (me==7) {
    wait_sem(semaphore[11]);
    wait_sem(semaphore[12]);

}
if (me==8) {
    wait_sem(semaphore[12]);
    wait_sem(semaphore[13]);

}

if (me==9) {
    wait_sem(semaphore[13]);
    wait_sem(semaphore[14]);

}
\$\endgroup\$

migrated from stackoverflow.com Nov 1 '13 at 1:19

This question came from our site for professional and enthusiast programmers.

  • 2
    \$\begingroup\$ You could use a switch \$\endgroup\$ – Mike W Nov 1 '13 at 0:26
  • \$\begingroup\$ Yeah. A switch is a good choice. \$\endgroup\$ – joshua-anderson Nov 1 '13 at 0:31
4
\$\begingroup\$

I wouldn't even use a switch here:

wait_sem(semaphore[me*2+1]);
wait_sem(semaphore[me*2+2]);
if (me==0) {
    signal_sem(semaphore[0]);    
}

Edit: I see the sequence is not quite linear. If you can come up with an easy mapping between me and the indices, this will work (but with a different formula). Otherwise, a switch statement may be the easiest way.

You can also bury the switch inside a map by mapping the input ints to the two indices (std::map<int, std::pair<int, int> >). It essentially does the same thing, but you can hide the ugly in a header file.

\$\endgroup\$
  • \$\begingroup\$ Potential maintenance issues here... \$\endgroup\$ – edtheprogrammerguy Nov 1 '13 at 1:21
  • \$\begingroup\$ For me==9 you should wait for 13 and 14, not 19 and 20 \$\endgroup\$ – Adrian Panasiuk Nov 1 '13 at 1:23
  • \$\begingroup\$ Sorry this migrated right as I was editing, then I had to create an account. Avoiding extraneous code is a good thing, but it probably will not work here. \$\endgroup\$ – user31517 Nov 1 '13 at 1:27
3
\$\begingroup\$

I think using if is ok, but please note that using else if clauses are also important for your code's performance.

Here is another way to do the job. Someone told me that data structures are easier to comprehend than control flows, so let's turn your if statements into data tables

typedef struct
{
   int a;
   int b;
}MY_TYPE;

MY_TYPE me[10] =
{
   {1, 2},
   {3, 4},
   {4, 5},
   {6, 7},
   {7, 8},
   {8, 9},
   {10, 11},
   {11, 12},
   {12, 13},
   {13, 14},
};

Then you can use it like this:

   int i = 0;
   for (i = 0; i < 10; i++)
   {
      wait_sem(semaphore[me[i].a]);
      wait_sem(semaphore[me[i].b]);
      if (i == 0)
      {
         signal_sem(semaphore[i]);
      }
   }

I believe the if/else clause in for could be encapsulated by other utility functions, so maybe you can try it yourself :)

\$\endgroup\$
  • \$\begingroup\$ Nice solution. As the structure is used nowhere else and is not modified, I would make it const and simplify it a bit by removing the typedef and MY_TYPE so that me[10] is just an anonymous struct \$\endgroup\$ – William Morris Nov 7 '13 at 12:44
  • \$\begingroup\$ I like this: similar to my answer, but better given the non-regular nature of the number boundaries. +1. \$\endgroup\$ – user31517 Nov 27 '13 at 5:58
1
\$\begingroup\$

Switch statements are quite helpful in such cases. They are also more efficient than your series of if statements which has to check all of them even after it finds the one it is looking for. The switch will immediately branch to the correct one and skip all the others. Is that helpful?

switch(me)
{
  case 0:
  wait_sem(semaphore[1]);
  wait_sem(semaphore[2]);
  signal_sem(semaphore[0]);
  break;

  case 1:
  wait_sem(semaphore[3]);
  wait_sem(semaphore[4]);
  break;

  //etc.

}
\$\endgroup\$
0
\$\begingroup\$

You always wait on two semaphores and sometimes signal one semaphore. By calculating the index of the semaphores to wait on, you can shorten the code:

assert(me >= 0);

if (me < 10) {
    // Find the unique n s.t. T_n <= me < T_{n+1} where {T_n}_n are the triangular numbers
    int n = (int)(0.5 * (sqrt(1+8*me)-0.99));
    // then calculate nextPos := me + (T_{n+1} - T_n)
    int nextPos = me + n + 1;
    wait_sem(semaphore[nextPos]);
    wait_sem(semaphore[nextPos + 1]);
}

if (me == 0) {
    signal_sem(semaphore[0]);    
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.