Transcribed Text
Question #1
Using as a guide, the code provided below, trace the lock states, variable values and order of buffer
values for the following sequence of thread events. For each thread that runs, list out the values in the
buffer array, the values for fill_ptr, use_ptr, count, the states of the locks, condition variables and
anything else that will explain why the buffer elements were processed in the order observed.
Assume all elements are at their initial values when the sequence of threads starts. The thread events
happen in the following sequential order:
prod(16), prod(21), cons(), cons(), cons(),prod(13),prod(5),prod(31),cons(),cons(),cons(
This code is a small variation of the code provided in figures 30.9 and 30.10. Assume these are "pseudo
code".
int buffer [MAX] ;
cond_t empty, fill;
int fill_ptr = 0;
mutex_t mutex;
int use_ptr = 0;
int count = 0;
void put (int value)
void *prod (int put_value)
I
{
buffer [fill ptr) = value;
Pthread mutex lock (&mutex) ;
fill_ptr = (fill_ptr + 1) % MAX;
while (count == MAX)
count++;
Pthread cond wait (&empty, &mutex) ;
-
)
put (put_value)
;
Pthread_cond_signal(&fill) ;
Pthread_mutex_unlock (&mutex) ;
}
int get ()
void *cons (void *arg)
I
(
int tmp = buffer (use_ptr) ;
Pthread_mutex_lock (&mutex) ;
use_ptr = (use_ptr + 1) % MAX;
while (count == 0)
-
count--;
Pthread_cond_wait (&fill, &mutex) ;
return tmp;
int tmp = get();
)
Pthread_cond_signal(&empty) ;
Pthread_mutex_unlock(&mutex) ;
printf("8d\n", tmp).
}
Hint: max = 10
An example of keeping track of state:
e.g.: prod(16)
void *prod (int put value)
(
Pthread_mutex_lock (&mutex) ;
while_(count == MAX)
Pthread cond wait (&empty, &mutex) ;
-
put (put value) ;
-
Pthread cond signal (&fill) ;
-
Pthread mutex unlock (&mutex) ;
)
I found it fairly easy to use Excel to keep track of columns of values. You can use whichever software you
want as long as it outputs into a standard format. Failing the standard office suite, PDF is a workable
alternative as long as the formatting is not lost.
5
6
Time
call
steps
buffer[0] buffer(1) buffer(:
fill ptr
use ptr
count
empty
fill
7
0 init
8
9
1 prod(16)
lock(mutex)
10
count!=MAX
11
put(16)
16
1
1
12
signal(fill) no one waiting
13
unlock(mutex)
14
Anything missing in the chart? mutex
Question #2
Assume that you have a linked list where the nodes look like:
typedef struct node_t
{
int key;
struct
node t *next;
} node t;
-
Part A:
What changes are required to this structure to allow protected use of this structure a multi-threaded
environment. The environment must allow for trheadsafe for inserts, deletes and reads ? Place any
additional variables, logic/locks or fields at the node level.
Part B:
For the following two questions, ensure your code is thread safe. Your solution should allow for
concurrent operations on nodes not affected by other threads.
By this I mean if you have a list comprising of : 1, 4, 9, 13, 16, 21, 77, 131, inserting an 11 must be
allowed to be "concurrent" with deleting 77.
1) For inserts, write some pseudo-code to force the elements of the list to be placed in ascending order.
(this should only be 8-10 lines long. Remember this is pseudo-code NOT C).
2) Write the pseudo-code for deleting an element of the list.
These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction
of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice.
Unethical use is strictly forbidden.