klarz klarz - 2 months ago 17
Java Question

Result of variables using Semaphore

Semaphore s = new Semaphore (0);
int x = 7;
int y = 1;

1.1 s.acquire(); 2.1 s.release();
2.2. s.release();
1.2 s.aquire(); 2.3 s.acquire();
1.3 int tmp = x; 2.4 int tmp = y;
1.4 s.release(); 2.5 s.release();

1.5. tmp = tmp * 2; 2.6 tmp = tmp * 3;

1.6. s.acquire(); 2.7 s.acquire();
1.7 y = tmp + 1; 2.8 x = tmp + 1;
1.8. s.release(); 2.9 s.release();


semaphore program

I have trouble getting the result of these variables x and y, if these two threads run parallel.


  1. The semaphore has 0 permits? So the only possible output here should be x=7, y=1, shouldn't it?

  2. I don't understand the nested acquires() and releases(). What would the result of x and y be ifsemaphore would have 2 permits?


Answer

Since there are no delays in your code, it can run in many ways, depending on which CPU is faster, or how the OS schedules the threads (e.g. in single-CPU system):

                        2.1 s.release();        1 permit
                        2.2 s.release();        2 permits
1.1 s.acquire();                                1 permit
1.2 s.acquire();                                0 permits
1.3 int tmp = x;
1.4 s.release();                                1 permit
1.5 tmp = tmp * 2;
1.6 s.acquire();                                0 permits
1.7 y = tmp + 1;
1.8 s.release();                                1 permit
                        2.3 s.acquire();        0 permits
                        2.4 int tmp = y;
                        2.5 s.release();        1 permit
                        2.6 tmp = tmp * 3;
                        2.7 s.acquire();        0 permits
                        2.8 x = tmp + 1;
                        2.9 s.release();        1 permit

Or:

                        2.1 s.release();         1 permit
                        2.2 s.release();         2 permits
                        2.3 s.acquire();         1 permit
                        2.4 int tmp = y;
                        2.5 s.release();         2 permits
                        2.6 tmp = tmp * 3;
                        2.7 s.acquire();         1 permit
                        2.8 x = tmp + 1;
                        2.9 s.release();         2 permits
1.1 s.acquire();                                 1 permit
1.2 s.acquire();                                 0 permits
1.3 int tmp = x;
1.4 s.release();                                 1 permit
1.5 tmp = tmp * 2;
1.6 s.acquire();                                 0 permits
1.7 y = tmp + 1;
1.8 s.release();                                 1 permit

What cannot happen, is for steps 1.3 and 2.4 to run in parallel. There are not enough permits for that.

                        2.1 s.release();         1 permit
1.1 s.acquire();                                 0 permits
                        2.2 s.release();         1 permit
1.2 s.acquire();                                 0 permits
1.3 int tmp = x;          <blocked>
1.4 s.release();          <blocked>              1 permit
                        2.3 s.acquire();         0 permits
                        2.4 int tmp = y;
                        2.5 s.release();         1 permit
1.5 tmp = tmp * 2;      2.6 tmp = tmp * 3;
                        2.7 s.acquire();         0 permits
  <blocked>             2.8 x = tmp + 1;
  <blocked>             2.9 s.release();         1 permit
1.6 s.acquire();                                 0 permits
1.7 y = tmp + 1;
1.8 s.release();                                 1 permit

There are many other ways these two threads can be interleaved.

Comments