0
$\begingroup$

I am studying the bakery algorithm, and I am unsure of what the variable i represents in it. I understand that Entering represents a bool value to protect Nummber while it is updating, but I'm having a hard time finding clear explanations as to what variable is doing what.

Is Number an array of threads? Is i a particular thread? Or the value being updated?

  1. What do i and Number actually represent?
  2. What is passed in via Thread(integer i)? The value we are locking? Or a thread ID number?
  3. Is there a value that represents a value being locked?

For reference, here is the Bakery Algorithm I am referencing, from Wikipedia:

   // declaration and initial values of global variables
   Entering: array [1..NUM_THREADS] of bool = {false};
   Number: array [1..NUM_THREADS] of integer = {0};

   lock(integer i) {
       Entering[i] = true;
       Number[i] = 1 + max(Number[1], ..., Number[NUM_THREADS]);
       Entering[i] = false;
       for (integer j = 1; j <= NUM_THREADS; j++) {
           // Wait until thread j receives its number:
           while (Entering[j]) { /* nothing */ }
           // Wait until all threads with smaller numbers or with the same
           // number, but with higher priority, finish their work:
           while ((Number[j] != 0) && ((Number[j], j) < (Number[i], i))) { /* nothing */ }
       }
   }

   unlock(integer i) {
       Number[i] = 0;
   }

   Thread(integer i) {
       while (true) {
           lock(i);
           // The critical section goes here...
           unlock(i);
           // non-critical section...
       }
   }
$\endgroup$
  • $\begingroup$ Where did you get this presentation of the algorithm from? Doesn't the text around the algorithm in that source answer your question? $\endgroup$ – David Richerby Feb 25 '17 at 23:14
  • $\begingroup$ As I mentioned, I got the algorithm information from from Wikipedia which explains some stuff, but it's still unclear to me what is what. $\endgroup$ – The Fluffy Robot Feb 25 '17 at 23:23
  • $\begingroup$ Sorry -- I didn't notice the link. But, as I suspected, the text around the algorithm on the Wikipedia page explains what both number and i are. $\endgroup$ – David Richerby Feb 25 '17 at 23:29
1
$\begingroup$

As the Wikipedia page says, (emphasis mine),

Lamport envisioned a bakery with a numbering machine at its entrance so each customer is given a unique number. Numbers increase by one as customers enter the store. A global counter displays the number of the customer that is currently being served. All other customers must wait in a queue until the baker finishes serving the current customer and the next number is displayed. When the customer is done shopping and has disposed of his or her number, the clerk increments the number, allowing the next customer to be served. That customer must draw another number from the numbering machine in order to shop again.

According to the analogy, the "customers" are threads, identified by the letter i, obtained from a global variable.

$\endgroup$
  • $\begingroup$ Ah, I wasn't aware the variables were in reference to the analogy. That makes more sense. So the "numbers" is a list of threads listed by their thread ID? And the "i" is one of the particular threads in that list? $\endgroup$ – The Fluffy Robot Feb 25 '17 at 23:40

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.