Quiz 6

Below is a fragment of code to determine the number of times each letter of the alphabet appears in a message.

01  // Shared variables
02  const int MAX = 26;
03  int current = 0;
04  struct entry { char letter; int count; } frequencies[MAX];
05
06  // Function to be called with different letters from different
07  // threads.
08  void count_and_update(char message[], int length, char letter)
09  {
10      // Determine number of occurrences (n) by looping through
11      // message.
12      int i, n = 0;
13      for(i = 0; i < length; i++)
14      {
15          if(message[i] == letter)
16          {
17              n++;
18          }
19      }
20
21      if(n > 0)
22      {
23          frequencies[current].letter = letter;
24          frequencies[current].count = n;
25          current++;
26      }
27  }

Given the message “ABSTRACT ALGEBRA”, the first part of the frequencies table might look like this:

                 letter  count
frequencies[0]    'A'     4
frequencies[1]    'B'     2
frequencies[2]    'C'     1
frequencies[3]    'E'     1
frequencies[4]    'G'     1
frequencies[5]    'L'     1
frequencies[6]    --      --
frequencies[7]    --      --
frequencies[8]    --      --
           ...    ...     ...

where current has the value 6 (the index of the next unused slot in frequencies). The entries mean that the letter 'A' appears four times in the message, 'B' appears twice, and the other letters shown appear once each.

Now suppose that two threads are concurrently working on the letters 'R' and 'S'. They should find that there are two occurrences of 'R' and one of 'S', but the results may depend on the way instructions from both processes are interleaved!

1. Mark each sequence below as valid or invalid, meaning: will it produce a coherent result in the frequencies table?

   1. R21 R23 R24 R25 S21 S23 S24 S25

   2. S21 R21 S23 S24 S25 R23 R24 R25

   3. S21 S23 R21 R23 S24 S25 R24 R25

   4. R21 R23 R24 S21 R25 S23 S24 S25

2. Which lines are part of the critical section within this function?

3. Fix the concurrency bug by adding a semaphore to the code. How will the semaphore be initialized? Where will you place the calls to wait and signal?

comments powered by Disqus