Issuu

for more solution manuals,visit Library Genesis: libgen.is, libgen.st, libgen.rs, and forum.mhut.org

Chapter 1

Introduction Exercises 1. Study one of the top 10 most powerful supercomputers in the world. Discover:

What kind of operating system does it run? How many CPUs/GPUs is it made of? What is its total memory capacity? What kind of software tools can be used to program it? Answer Students should research the answer by visiting the Top 500 site and -if available- the site of one of the reported systems. 2. How many cores are inside the top GPU offerings from NVidia and AMD? What is the GFlop rating of these chips? Answer N/A. 3. The performance of the most powerful supercomputers in the world is usually reported as two numbers Rpeak and Rmax, both in TFlops (tera floating point operations per second) units. Why is this done? What are the factors reducing performance from Rpeak to Rmax? Would it be possible to ever achieve Rpeak? Answer This is done because the peak performance is unattainable. Sustained, measured performance on specific benchmarks, is a better indicator of the true machine potential. The reason these are different is communication overhead. Rpeak and Rmax could never be equal. Extremely compute-heavy applications, that have no inter-node communications, could asymptotically approach Rpeak if they were to run for a very long time. A very long execution time is required to diminish the influence of the start-up costs. 5

CHAPTER 1. INTRODUCTION 4. A sequential application with a 20% part that must be executed sequentially, is required to be accelerated five-fold. How many CPUs are required for this task? Answer This requires the application of Amdahl’s law. The part that can be parallelized is α = 1 − 20% = 80%. The speedup predicted by Amdahl’s 1 law is speedup = 1−α+ α . N

Achieving a three-fold speedup requires that: 1 1 0.8 1 0.8 = − 0.2 ⇒ N = 1 =3⇒ =6 α =3⇒ 1−α+ N N 3 0.2 + 0.8 − 0.2 N 3 (1.1) Achieving a 5-fold speedup requires that: 1 0.8 0.8 =∞ = 0.8 = 5 ⇒ N = 1 0 0.2 + N 5 − 0.2

(1.2)

So, it is impossible to achieve a 5-fold speedup, according to Amdahl’s law. 5. A parallel application running on 5 identical machines, has a 10% sequential part. What is the speedup relative to a sequential execution on one of the machines? If we would like to double that speedup, how many CPU would be required? Answer This requires the application of Gustafson-Barsis’ law as the information relates to a parallel application. The parallel part is α = 1 − 10% = 90%. The speedup over a single machine is speedup = 1−α+N ·α = .1+5·0.9 = 4.6. 9.1 = 10.1 Doubling the speedup would require .1 + N · 0.9 = 9.2 ⇒ N = 0.9 machines. As N has to be an integer, we have to round-up to the closest integer, i.e. N = 11.

6. An application with a 5% non-parallelizable part, is to be modified for parallel execution. Currently on the market there are two parallel machines available: machine X with 4 CPUs, each CPU capable of executing the application in 1hr on its own, and, machine Y with 16 CPUs, with each CPU capable of executing the application in 2hr on its own. Which is the machine you should buy, if the minimum execution time is required? Answer As the information provided relates to a sequential application, we have to apply Amdahl’s law. The execution time for machine X is: tX = (1 − α)T +

0.95 · 1hr αT = 0.05 ∗ 1hr + = 0.2875hr N 4

(1.3)

The execution time for machine Y is: tY = (1 − α)T +

αT 0.95 · 2hr = 0.05 ∗ 2hr + = 0.21875hr N 16

(1.4)

7 So we should buy machine Y. 7. Create a simple sorting application that uses the mergesort algorithm to sort a large collection (e.g. 107 ) of 32-bit integers. The input data and output results should be stored in files, and the I/O operations should be considered a sequential part of the application. Mergesort is an algorithm that is considered appropriate for parallel execution, although it cannot be equally divided between an arbitrary number of processors, as Amdahl’s and Gustafson-Barsis’ laws require. Assuming that this equal division is possible, estimate α, i.e. the part of the program that can be parallelized, by using a profiler like gprof or valgrind to measure the duration of mergesort’s execution relative to the overall execution time. Use this number to estimate the predicted speedup for your program. Does α depend on the size of the input? If it does, how should you modify your predictions and their graphical illustration? Answer N/A 8. A parallel application running on 10 CPUs, spends 15% of its total time, in sequential execution. What kind of CPU (how much faster) would we need to run this application completely sequentially, while keeping the same total time? Answer This is an application of Gustafson-Barsis’ law. If T is the parallel execution time on the 10 CPUs, the sequential execution time on a single one would be Ts = (1 − α)T + N · α · T . The fast CPU should match the parallel time, i.e. Tf = T which means if should be TTfs = (1 − α) + N · α = 0.15 + 10 · 0.85 = 8.65 times faster.

Chapter 2

Multicore and Parallel Program Design 1. Perform a 2D agglomeration step for the image convolution problem of Section 2.2. What is the resulting number of communication operations? Answer Assuming that we target a grid of task groups forming K rows x M columns and that K and M divide the corresponding dimensions evenly, each group will hold IMMGX IMKGY tasks. The number of communication operations are:

Four for “internal” groups. There are (K −1)(M −1) internal groups. Each group sends IMMGX pixel values to its top and bottom neighbors, and IMKGY pixels to its left and right neighbors. Two for corner groups. There are four corner groups. Three for “boundary” groups. There are 2(K−2)+2(M −2) boundary groups. The total data volume communicated is : totalComm = (2

IM GY IM GX +2 )(K − 1)(M − 1) + M K IM GY IM GX + )2(M − 2) + (2 M K IM GX IM GY ( +2 )2(K − 2) + M K IM GX IM GY ( + )4 M K

(2.1) (2.2) (2.3) (2.4)

2. Perform the comparison between the 1D and 2D decompositions of the heat diffusion example in Section 2.3.3, by assuming that (a) half-duplex communication links are available and (b) n-port communications are possible, i.e. all communications can take place at the same time over all the links. Answer 9

CHAPTER 2. MULTICORE AND PARALLEL PROGRAM DESIGN (a) If half-duplex communication links where used, then the time spend on communication would be doubled: comp1D + comm1D =

comp2D + comm2D =

N2 · tcomp + 4 · (tstart + tcomm N ) P

N N2 tcomp + 8 tstart + tcomm · √ P P

(2.5)

which means that comm1D + comp1D < comm2D + comp2D ⇒ tstart > tcomm N

2 1− √ P

(2.6)

So there is no change in the condition that favors 1D over 2D. (b) In the n-port case, the communication time per time step will be: comm1D = tstart + tcomm N N comm2D = tstart + tcomm · √ P so the comparison between the two decompositions would be based on comm1D + comp1D < comm2D + comp2D ⇒

√ P <1

which is obviously false. So, 2D is always better than 1D. 3. How would communication costs affect the pipeline performance? Derive variations of Equations 2.16 to 2.18 that take into account a constant communication overhead between the pipeline stages. Answer Let’s assume that communication between the stages costs a fixed amount of time tc . Then we would have an additional overall time of tc (N + M ), assuming that the last stage also sends data back to whoever is controlling the execution. Thus: ttotal =

l−1 X j=0

tj + N · tl +

M −1 X

tj + tc (N + M )

j=l+1

The processing rate of the pipeline is: rate = Pl−1

j=0 tj + N · tl +

The latency of the pipeline is: latency =

N PM −1

M −2 X j=0

j=l+1 tj + tc (N + M )

tj + tc M

11 4. The total number of tasks calculated in Section 2.4.5 for the parallel quicksort of Listing 2.8, is based on the best-case assumption that the input is split in equal halves by every call to the PartitionData function. What would be the result if the worst-case (i.e. one part gets N − 1 elements and the other part 0) were considered? Answer If we assume that the PartitionData function produces a zero sized part and a part with N − 1 elements, then: T (N ) =

0 1 + T (N − 1)

if N ≤ T HRES if N > T HRES

as one of the calls to QuickSort would always have no input. Backward substitution can provide the answer: T (N ) = 1 + T (N − 1) = 1 + 1 + T (N − 2) = k + T (N − k) T (N − k) can be eliminated when N − k = T HRES ⇒ k = N − T HRES. Substituting this value of k in the previous equation yields: T (N ) = N − T HRES + T (T HRES) = N − T HRES as T (T HRES) = 0. This is obviously a poor result. What this formula does not convey is that parallelism is also eliminated as a result: there is effectively no overlap between the generated tasks. 5. Use a simple problem instance (e.g. a small array of integers) to trace the execution of the parallel quicksort of Listing 2.8. Create a Gantt graph for the tasks generated, assuming an infinite number of compute nodes is available for executing them. Can you calculate an upper bound for the speedup that can be achieved? Answer Given N input elements, PartitionData executes between N −1 and N +1 key comparisons. For simplicity we will assume that N comparisons are done and that the array is evenly split into parts equal in size to N 2−1 (taking out the pivot element). The first initial task that starts the sorting operation, will perform N comparisons, before spawning a task for N 2−1 elements and continuing with the remaining N 2−1 . The comparisons are done exclusively inside the PartitionData function, which means we have the following sequence of task executions and corresponding comparison steps:

1 task, N steps 2 tasks, N 2−1 steps each 2

+1 22 tasks, N −2 steps each 22 3

+1 23 tasks, N −2 steps each 23

And so on...

CHAPTER 2. MULTICORE AND PARALLEL PROGRAM DESIGN Size of data block to be sorted N −3 N −1 N 2 4

Threads

0 2 1 3 Time

Figure 2.1: The first three steps (assuming an ideal scenario of a perfect partition each time) in the parallel quicksort algorithm of Listing 2.8. Figure 2.1 illustrates this process. So, the overall duration in number of comparisons is : totalComp =

L−1 X

N − 2i + 1 + T HRES 2i i=0

where L is associated with when the size become smaller or equal to T HRES and no more tasks are spawned. The value of L is: N − 2L + 1 = T HRES ⇒ N − 2L + 1 = 2L T HRES ⇒ 2L N +1 N +1 2L = ⇒ L = lg( ) T HRES + 1 T HRES + 1 Thus: totalComp =

L−1 X

N − 2i + 1 + T HRES = 2i i=0 L−1 X

L−1 1 i X ( ) − (N + 1) 1 + T HRES = 2 i=0 i=0

( 1 )L − 1 − L + T HRES = (N + 1) 21 2 −1 T HRES + 1 2(N + 1)(1 − ) − L + T HRES = N +1 2(N + 1) − 2(T HRES + 1) − L + T HRES = 2N − T HRES − L ≈ 2N So the maximum speedup that could be ever achieved, given that the sequential quicksort performs N lgN comparisons, is: speedupmax =

N lgN lgN = 2N 2

Chapter 3

Threads and Concurrency in standard C++ Exercises 1. Enumerate and create the other timing diagrams that show the alternatives of Figure 3.4, when it comes to the final balance of the bank account. Answer All the possible permutations of the four events are allowed, as long as 1 proceeds 3 and 2 proceeds 4. So we have:

1, 2, 3, 4 : produces wrong result 1, 3, 2, 4 : produces correct result 1, 2, 4, 3 : produces wrong result 2, 1, 3, 4 : produces wrong result 2, 1, 4, 3 : produces wrong result 2, 4, 1, 3 : produces correct result 2. Research the term “fork bomb” and write a program that performs as such. Answer #i n c l u d e < s t d l i b . h> #i n c l u d e #i n c l u d e < l i m i t s . h> i n t m a i n ( i n t a r g c , c h a r ** a r g v ) { i n t N = atoi ( argv [ 1 ] ) ; f o r ( i n t i =0; i<N ; i++) pid_t cID = fork ( ) ; sleep ( INT_MAX ) ; return 0; }

14 CHAPTER 3. THREADS AND CONCURRENCY IN STANDARD C++ 3. Modify the producer-consumer example shown in Listing 3.11, so that the threads terminate after the number 100 is generated. Answer The only modification required affects the consume method, where the detection of the exit condition is done. It should become: bool consume ( int i ) { // t o be implemented c o u t << ”@” ; // j u s t t o show s o m e t h i n g i s h a p p e n i n g i f ( i == 1 0 0 ) r e t u r n t r u e ; e l s e return f a l s e ; }

4. Suggest a modification to the program of Listing 3.12 so that the IntegrCalc threads can use any function that return a double and takes a double as a parameter. Answer A pointer to such a function needs to be passed to the initClass method, so that it can be called by the threads. The modifications are highlighted in the following code: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

. . . //−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− // a c t s a s a consumer c l a s s IntegrCalc : public QThread { private : i n t ID ; s t a t i c QSemaphore * slotsAvail ; s t a t i c QSemaphore * resAvail ; s t a t i c QMutex l2 ; s t a t i c QMutex resLock ; s t a t i c Slice * buffer ; s t a t i c i n t out ; s t a t i c double * result ; s t a t i c double (* f ) ( double ) ; // <======= s t a t i c QSemaphore numProducts ; public : s t a t i c v o i d i n i t C l a s s ( Q S e m a p h o r e * s , Q S e m a p h o r e * a , S l i c e * b , ←֓ double *r , double (* f ) ( double ) ) ;

18 19 20 21 22 23 24 25

I n t e g r C a l c ( i n t i ) : ID ( i ) { }; void run ( ) ; }; //−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− . . . double (* IntegrCalc : : f ) ( double ) ; // <=======

26 27

//−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−

28 29

30 31 32 33 34 35 36 37

v o i d I n t e g r C a l c : : i n i t C l a s s ( Q S e m a p h o r e * s , Q S e m a p h o r e * a , S l i c e * b ←֓ , d o u b l e * res , d o u b l e ( * g ) ( d o u b l e ) ) { // <======= slotsAvail = s ; resAvail = a ; buffer = b ; result = res ; * result = 0; f = g ; // <======= } //−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−

38 39 40 41 42 43 44

void IntegrCalc : : run ( ) { while (1) { r e s A v a i l −>a c q u i r e ( ) ; // w a i t f o r an a v a i l a b l e i t e m l2 . lock ( ) ; i n t tmpOut = out ; o u t = ( o u t + 1 ) % B U F F S I Z E ; // update t h e o u t i n d e x

15 l2 . unlock ( ) ;

45 46

// t a k e t h e i t e m o u t double st = buffer [ tmpOut ] . start ; double en = buffer [ tmpOut ] . end ; double div = buffer [ tmpOut ] . divisions ;

47 48 49 50 51

s l o t s A v a i l −>r e l e a s e ( ) ; // s i g n a l

f o r a new empty s l o t

( d i v == 0 ) b r e a k ; // e x i t

// c a l c u l a t e a r e a double localRes = 0 ; double step = ( en − st ) / div ; double x ; x = st ; l o c a l R e s = f ( st ) + f ( en ) ; // <======= l o c a l R e s /= 2 ; f o r ( i n t i =1; i< d i v ; i++) { x += s t e p ; l o c a l R e s += f ( x ) ; // <======= } l o c a l R e s *= s t e p ;

56 57 58 59 60 61 62 63 64 65 66 67 68

// add i t t o r e s u l t resLock . lock () ; * r e s u l t += l o c a l R e s ; resLock . unlock () ;

69 70 71 72 73 74 75

} } //−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−

76 77 78 79 80 81 82 83 84 85 86 87

i n t main ( i n t argc , char * argv [ ] ) { i f ( a r g c == 1 ) { c e r r << ” Usage ” << a r g v [ 0 ] << ” #t h r e a d s #j o b s \n” ; exit (1) ; } i n t N = atoi ( argv [ 1 ] ) ; i n t J = atoi ( argv [ 2 ] ) ; S l i c e * b u f f e r = new S l i c e [ B U F F S I Z E ] ; QSemaphore avail , buffSlots ( BUFFSIZE ) ; i n t in = 0 ; double result ;

I n t e g r C a l c : : i n i t C l a s s (& b u f f S l o t s , &a v a i l , b u f f e r , &r e s u l t , ←֓ func ) ; // <=======

90 91

5. In a remote region of Siberia there are single tracks joining railroad stations. Obviously only one train can use a piece of track between two stations. The other trains can wait at the stations before they do their crossings. The following graph indicates the track and station layout: A

Write a Qt program that simulates the journey of 3 trains with the following schedules:

A→B→E→C

D→B→E→G

C→E→B→D→F

16 CHAPTER 3. THREADS AND CONCURRENCY IN STANDARD C++ As each trains arrives at a station display a relative message. You can assume that a station can hold any number of trains waiting. Answer The Train class constructor expects two vectors : one containing the names of the stations that will be traversed, and one containing references to the binary semaphores controlling access to the lines connecting the stations. 1 2 3 4 5

#i n c l u d e <QThread> #i n c l u d e <QMutex> #i n c l u d e #i n c l u d e <s t r i n g > #i n c l u d e <v e c t o r >

6 7

u s i n g namespace s t d ;

8 9 10 11 12 13 14 15 16

17 18

c l a s s Train : public QThread { private : i n t ID ; v e c t o r <s t r i n g > * s t a t i o n s ; v e c t o r <Q M u t e x *> * l i n e L o c k s ; public : T r a i n ( i n t i , v e c t o r <s t r i n g > * s , v e c t o r <Q M u t e x *> * l ) : I D ( i ) , ←֓ s t a t i o n s ( s ) , l i n e L o c k s ( l ) {} void run ( ) ; };

19 20 21 22 23 24 25

26 27

28 29 30

void Train : : run ( ) { int i ; f o r ( i =0; i<l i n e L o c k s −>s i z e ( ) ; i++) { c o u t << ” T r a i n ” <←֓ a t ( i ) << e n d l ; l i n e L o c k s −>a t ( i )−>l o c k ( ) ; c o u t << ” T r a i n ” <a t ( i +1) << e n d l ; l i n e L o c k s −>a t ( i )−>u n l o c k ( ) ; } c o u t << ” T r a i n ” <a t ( i ) << e n d l ; }

32 33 34 35 36 37 38 39

i n t main ( i n t argc , char * argv [ ] ) { Q M u t e x AB , BD , DF , BE , CE , E G ; // m u t i c e s f o r t h e l i n e s // one f o r e a c h t r a i n v e c t o r <Q M u t e x *> r o u t e s [ 3 ] ; v e c t o r <s t r i n g > s t [ 3 ] ;

40 41 42 43 44 45 46 47

48 49 50 51 52 53 54 55

56 57 58 59

r o u t e s [ 2 ] . p u s h _ b a c k (& C E ) ; r o u t e s [ 2 ] . p u s h _ b a c k (& B E ) ; r o u t e s [ 2 ] . p u s h _ b a c k (& B D ) ;

17 r o u t e s [ 2 ] . p u s h _ b a c k (& D F ) ; s t [ 2 ] . p u s h _ b a c k ( ”C” ) ; s t [ 2 ] . p u s h _ b a c k ( ”E” ) ; s t [ 2 ] . p u s h _ b a c k ( ”B” ) ; s t [ 2 ] . p u s h _ b a c k ( ”D” ) ; s t [ 2 ] . p u s h _ b a c k ( ”F” ) ;

60 61 62 63 64 65 66

// t h r e a d spawning Train *t [ 3 ] ; f o r ( i n t i =0; i <3; i++) { t [ i ] = new T r a i n ( i , &s t [ i ] , &r o u t e s [ i ] ) ; t [ i]−> s t a r t ( ) ; }

67 68 69 70 71 72 73 74

f o r ( i n t i =0; i <3; i++) t [ i]−> w a i t ( ) ; return 0;

75 76 77 78

}

6. Modify the program of the previous exercise so that each station can hold only 2 trains. Can this lead to deadlocks? If you have not done so already, make sure that your program uses only one thread class. Answer This cannot lead to deadlocks as long as we have three or less trains. For four or more we could have pairs of trains trying to cross opposite directions of the same line, leading to deadlock. The only required changes involves controlling access to the stations via a set of general semaphores. 1 2 3 4 5 6

#i n c l u d e <QThread> #i n c l u d e <QMutex> #i n c l u d e <QSemaphore> #i n c l u d e #i n c l u d e <s t r i n g > #i n c l u d e <v e c t o r >

7 8

u s i n g namespace s t d ;

9 10 11 12 13 14 15 16 17 18

19 20

c l a s s Train : public QThread { private : i n t ID ; v e c t o r <s t r i n g > * s t a t i o n s ; v e c t o r <Q S e m a p h o r e *> * s t a t i o n s C t r l ; v e c t o r <Q M u t e x *> * l i n e L o c k s ; public : T r a i n ( i n t i , v e c t o r <s t r i n g > * s , v e c t o r <Q M u t e x *> * l , v e c t o r <←֓ Q S e m a p h o r e *> * c ) : I D ( i ) , s t a t i o n s ( s ) , l i n e L o c k s ( l ) , ←֓ s t a t i o n s C t r l ( c ) {} void run ( ) ; };

21 22 23 24 25 26 27 28

void Train : : run ( ) { int i ; s t a t i o n s C t r l −>a t ( 0 )−>a c q u i r e ( ) ; f o r ( i =0; i<l i n e L o c k s −>s i z e ( ) ; i++) { c o u t << ” T r a i n ” <←֓ a t ( i ) << e n d l ; s t a t i o n s C t r l −>a t ( i +1)−>a c q u i r e ( ) ; // r e s e r v e s t a t i o n ←֓ b e f o r e l o c k i n g the l i n e

30 31

l i n e L o c k s −>a t ( i )−>l o c k ( ) ;

18 CHAPTER 3. THREADS AND CONCURRENCY IN STANDARD C++ c o u t << ” T r a i n ” <a t ( i +1) << e n d l ; l i n e L o c k s −>a t ( i )−>u n l o c k ( ) ;

33 34

s t a t i o n s C t r l −>a t ( i )−>r e l e a s e ( ) ; // r e l e a s e p r e v i o u s ←֓ station reservation c o u t<a t ( i )−>a v a i l a b l e ( ) << e n d l ←֓ ;

} c o u t << ” T r a i n ” <a t ( i ) << e n d l ;

37 38

}

40 41 42 43 44 45 46 47 48 49

i n t main ( i n t argc , char * argv [ ] ) { Q M u t e x AB , BD , DF , BE , CE , E G ; QSemaphore A (2) , B (2) , C (2) , D (2) , E (2) , F (2) , G (2) ; // one f o r e a c h t r a i n v e c t o r <Q M u t e x *> r o u t e s [ 3 ] ; v e c t o r <Q S e m a p h o r e *> s t C a p a c [ 3 ] ; v e c t o r <s t r i n g > s t [ 3 ] ;

r o u t e s [ 0 ] . p u s h _ b a c k (& A B ) ; r o u t e s [ 0 ] . p u s h _ b a c k (& B E ) ; r o u t e s [ 0 ] . p u s h _ b a c k (& C E ) ; s t [ 0 ] . p u s h _ b a c k ( ”A” ) ; s t [ 0 ] . p u s h _ b a c k ( ”B” ) ; s t [ 0 ] . p u s h _ b a c k ( ”E” ) ; s t [ 0 ] . p u s h _ b a c k ( ”C” ) ; s t C a p a c [ 0 ] . p u s h _ b a c k (&A ) ; s t C a p a c [ 0 ] . p u s h _ b a c k (&B ) ; s t C a p a c [ 0 ] . p u s h _ b a c k (&E ) ; s t C a p a c [ 0 ] . p u s h _ b a c k (&C ) ;

51 52 53 54 55 56 57 58 59 60 61 62

r o u t e s [ 1 ] . p u s h _ b a c k (& B D ) ; r o u t e s [ 1 ] . p u s h _ b a c k (& B E ) ; r o u t e s [ 1 ] . p u s h _ b a c k (& E G ) ; s t [ 1 ] . p u s h _ b a c k ( ”D” ) ; s t [ 1 ] . p u s h _ b a c k ( ”B” ) ; s t [ 1 ] . p u s h _ b a c k ( ”E” ) ; s t [ 1 ] . p u s h _ b a c k ( ”G” ) ; s t C a p a c [ 1 ] . p u s h _ b a c k (&D ) ; s t C a p a c [ 1 ] . p u s h _ b a c k (&B ) ; s t C a p a c [ 1 ] . p u s h _ b a c k (&E ) ; s t C a p a c [ 1 ] . p u s h _ b a c k (&G ) ;

63 64 65 66 67 68 69 70 71 72 73 74

r o u t e s [ 2 ] . p u s h _ b a c k (& C E ) ; r o u t e s [ 2 ] . p u s h _ b a c k (& B E ) ; r o u t e s [ 2 ] . p u s h _ b a c k (& B D ) ; r o u t e s [ 2 ] . p u s h _ b a c k (& D F ) ; s t [ 2 ] . p u s h _ b a c k ( ”C” ) ; s t [ 2 ] . p u s h _ b a c k ( ”E” ) ; s t [ 2 ] . p u s h _ b a c k ( ”B” ) ; s t [ 2 ] . p u s h _ b a c k ( ”D” ) ; s t [ 2 ] . p u s h _ b a c k ( ”F” ) ; s t C a p a c [ 2 ] . p u s h _ b a c k (&C ) ; s t C a p a c [ 2 ] . p u s h _ b a c k (&E ) ; s t C a p a c [ 2 ] . p u s h _ b a c k (&B ) ; s t C a p a c [ 2 ] . p u s h _ b a c k (&D ) ; s t C a p a c [ 2 ] . p u s h _ b a c k (&F ) ;

75 76 77 78 79 80 81 82 83 84 85 86 87 88 89

Train *t [ 3 ] ; f o r ( i n t i =0; i <3; i++) { t [ i ] = new T r a i n ( i , &s t [ i ] , &r o u t e s [ i ] , &s t C a p a c [ i ] ) ; t [ i]−> s t a r t ( ) ; }

90 91 92 93 94 95 96

f o r ( i n t i =0; i <3; i++) t [ i]−> w a i t ( ) ; return 0;

97 98 99 100

}

19 7. A desktop publishing (like PageMaker) application has two threads running: one for running the GUI and one for doing background work. Simulate this application in Qt. Your implementation should have the thread corresponding to the GUI, send requests to the other thread to run tasks on its behalf. The tasks should be (obviously just printing a message is enough for the simulation):

Printing Mail merging PDF generation After performing each requested task, the second thread should wait for a new request to be send to it. Make sure that the first thread does not have to wait for the second thread to finish before making new requests. Answer The following solution is a producer-consumer derivative, where just two counting semaphores are needed for each pair of interacting threads. There are two buffers, one for handling the interaction between GUI and mailmerge and one for the interaction between GUI and PDF generation. 1 2 3 4 5

#i n c l u d e <QSemaphore> #i n c l u d e <QThread> #i n c l u d e < s t d l i b . h> #i n c l u d e #i n c l u d e

6 7

u s i n g namespace s t d ;

8 9 10 11

c o n s t i n t T E R M I N F L A G = −1; const i n t RUNS = 20; const int BUFFSIZE = 5;

12 13 14 15 16 17

// t h e f o l l o w i n g s h o u l d n o t be g l o b a l v a r i a b l e s // but t h e y a r e s o t o r e d u c e t h e l e n g t h o f t h e c o d e QSemaphore mailReq (0) , mailSpace ( BUFFSIZE ) ; int mailJob [ BUFFSIZE ] ; // b u f f e r i n t m_in = 0 , mout = 0;

18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45

QSemaphore pdfReq (0) , pdfSpace ( BUFFSIZE ) ; int pdfJob [ BUFFSIZE ] ; // b u f f e r i n t pin = 0 , pout = 0 ; //============================================= c l a s s GUI : p u b l i c QThread { public : void run ( ) ; }; //−−−−−−−−−−−−−− void GUI : : run ( ) { f o r ( i n t i = 0 ; i < R U N S ; i++) { i n t choice = rand () % 2; i f ( choice ) // m a i l merge { mailSpace . acquire () ; mailJob [ m_in ] = i ; m_in = ( m_in + 1) % BUFFSIZE ; mailReq . release () ; } else // PDF g e n e r a t i o n { pdfSpace . acquire () ; pdfJob [ pin ] = i ; pin = ( pin + 1) % BUFFSIZE ;

20 CHAPTER 3. THREADS AND CONCURRENCY IN STANDARD C++ pdfReq . release () ;

}

} // t e r m i n a t i o n mailSpace . acquire () ; mailJob [ m_in ] = TERMINFLAG ; mailReq . release () ;

48 49 50 51 52 53

pdfSpace . acquire () ; pdfJob [ pin ] = TERMINFLAG ; pdfReq . release () ;

54 55 56 57

}

58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78

//============================================= c l a s s MailMerge : public QThread { public : void run ( ) ; }; //−−−−−−−−−−−−−− void MailMerge : : run ( ) { while (1) { mailReq . acquire () ; i n t job = mailJob [ mout ] ; mout = ( mout + 1) % BUFFSIZE ; i f ( j o b == T E R M I N F L A G ) break ; c o u t << ” Mail merge j o b #” << j o b << e n d l ; mailSpace . release () ; } }

79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99

//============================================= c l a s s PDFGen : public QThread { public : void run ( ) ; }; //−−−−−−−−−−−−−− void PDFGen : : run ( ) { while (1) { pdfReq . acquire () ; i n t job = pdfJob [ pout ] ; pout = ( pout + 1) % BUFFSIZE ; i f ( j o b == T E R M I N F L A G ) break ; c o u t << ”PDF g e n e r a t i o n j o b #” << j o b << e n d l ; pdfSpace . release () ; } }

100 101 102 103 104 105 106 107 108 109

//============================================= i n t main ( i n t argc , char * argv [ ] ) { GUI g ; PDFGen p ; MailMerge m ; g . start () ; p . start () ; m . run ( ) ; // m. s t a r t ( ) ; // can u s e run ←֓ i n s t e a d o f s t a r t t o a v o i d s t a r t i n g an e x t r a t h r e a d

110

g . wait () ; p . wait () ; // m. w a i t ( ) ; // s e e above return 0;

111 112 113 114 115

}

8. A popular bakery has a baker that cooks a loaf of bread at a time and

21 deposits it on a counter. Incoming customers pick up a loaf from the counter and exit the bakery. The counter can hold 20 loafs. If it is full the baker stops baking bread. If it is empty, a customer waits. Use semaphores to solve the coordination problem between the baker and the customers. Answer This is an instance of the producer-consumers problem. Because the baker thread is producing just simple integers in sequence, we can use a QAtomicInt variable for retrieving loaf IDs on the customers’ side. 1 2 3 4 5

#i n c l u d e <QThread> #i n c l u d e <QSemaphore> #i n c l u d e <QAtomicInt> #i n c l u d e #i n c l u d e < s t d l i b . h>

6 7

u s i n g namespace s t d ;

8 9

c o n s t i n t S P A C E =20;

10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

48 49 50 51 52 53 54 55 56 57 58 59 60

QSemaphore loafs (0) , counterSpace ( SPACE ) ; QAtomicInt loafID ; //============================ c l a s s Baker : public QThread { private : int totalBread ; public : B a k e r ( i n t t ) : t o t a l B r e a d ( t ) {} void run ( ) ; }; //−−−−−−−−−−−−−−−−−− void Baker : : run ( ) { f o r ( i n t i =0; i<t o t a l B r e a d ; i++) { counterSpace . acquire () ; c o u t << ” Baker baked # ” << i << e n d l ; loafs . release () ; } } //============================ c l a s s Customer : public QThread { private : i n t ID ; public : C u s t o m e r ( i n t i ) : I D ( i ) {} void run ( ) ; }; //−−−−−−−−−−−−−−−−−− void Customer : : run ( ) { loafs . acquire () ; int myBread = loafID . fetchAndAddOrdered (1) ; counterSpace . release () ; c o u t << ” Customer ” << I D << ” g o t b r e a d #” << m y B r e a d << e n d l ←֓ ; } //============================ i n t main ( i n t argc , char * argv [ ] ) { i n t totalCustomers = atoi ( argv [ 1 ] ) ; Customer *c [ totalCustomers ] ; f o r ( i n t i =0; i<t o t a l C u s t o m e r s ; i++) { c [ i ]=new C u s t o m e r ( i ) ; c [ i]−> s t a r t ( ) ; } Baker b ( totalCustomers ) ; b . run ( ) ;

22 CHAPTER 3. THREADS AND CONCURRENCY IN STANDARD C++ 61

// w a i t f o r t e r m i n a t i o n f o r ( i n t i =0; i<t o t a l C u s t o m e r s ; i++) c [ i]−> w a i t ( ) ;

62 63 64 65

return 0;

66 67

}

9. Because of customer demand, the bakery owner is considering the following enhancements to his shop: (a) Increase the capacity of the counter to 1000 (b) Hire 3 more bakers Modify the solution of the previous exercise to accommodate these changes. Which is the easiest to implement? Answer (a) In this case, the only change required is to modify line 9 in the previous listing to: c o n s t i n t S P A C E =1000;

(b) The complication in this case is the termination of the baker threads. For this purpose, the totalCustomers variable is used to initialize a general semaphore that is tested and decremented prior to the execution of each iteration of a baker thread (line 27): 1 2 3 4 5

#i n c l u d e <QThread> #i n c l u d e <QSemaphore> #i n c l u d e <QAtomicInt> #i n c l u d e #i n c l u d e < s t d l i b . h>

6 7

u s i n g namespace s t d ;

8 9

c o n s t i n t S P A C E =20;

10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

34 35 36 37 38

QSemaphore loafs (0) , counterSpace ( SPACE ) ; QSemaphore moreLoafs (0) ; QAtomicInt loafID ; //============================ c l a s s Baker : public QThread { private : i n t ID ; public : B a k e r ( i n t i ) : I D ( i ) {} void run ( ) ; }; //−−−−−−−−−−−−−−−−−− void Baker : : run ( ) { i n t m y P r o d =0; while ( moreLoafs . tryAcquire () ) { counterSpace . acquire () ; loafs . release () ; m y P r o d ++; } c o u t << ” Baker #” << I D << ” baked a t o t a l ” b r e a d s ” << e n d l ; } //============================ c l a s s Customer : public QThread { private :

o f ” << m y P r o d << ←֓

23 39 40 41 42 43 44 45 46 47 48 49 50

51 52 53 54 55 56 57 58 59 60 61 62

i n t ID ; public : C u s t o m e r ( i n t i ) : I D ( i ) {} void run ( ) ; }; //−−−−−−−−−−−−−−−−−− void Customer : : run ( ) { loafs . acquire () ; int myBread = loafID . fetchAndAddOrdered (1) ; counterSpace . release () ; c o u t << ” Customer ” << I D << ” g o t b r e a d #” << m y B r e a d << ←֓ endl ; } //============================ i n t main ( i n t argc , char * argv [ ] ) { i n t totalCustomers = atoi ( argv [ 1 ] ) ; Customer *c [ totalCustomers ] ; moreLoafs . release ( totalCustomers ) ; f o r ( i n t i =0; i<t o t a l C u s t o m e r s ; i++) { c [ i ]=new C u s t o m e r ( i ) ; c [ i]−> s t a r t ( ) ; }

Baker *b [ 4 ] ; f o r ( i n t i =0; i <4; i++) { b [ i ] = new B a k e r ( i ) ; b [ i ] −> s t a r t ( ) ; }

64 65 66 67 68 69 70 71

// w a i t f o r t e r m i n a t i o n f o r ( i n t i =0; i<t o t a l C u s t o m e r s ; i++) c [ i]−> w a i t ( ) ; f o r ( i n t i =0; i <4; i++) b [ i]−> w a i t ( ) ;

72 73 74 75 76 77

return 0;

78 79

}

10. A bank account class is defined as follows: c l a s s BankAccount { protected : double balance ; string holderName ; public : double getBalance ( ) ; void deposit ( double ) ; v o i d w i t h d r a w ( d o u b l e , i n t ) ; // t h e h i g h e s t t h e s e c o n d ←֓ argument , t h e h i g h e r t h e p r i o r i t y o f t h e r e q u e s t };

Write the implementation of the three methods given above, so that withdraw operations are prioritized: if there are not enough funds in the account for all, the withdrawals must be done in order of priority regardless if there are some that can be performed with the available funds. You can assume that the priority level in the withdraw method is by default equal to 0, and that it can is upper bounded by a fixed constant MAXPRIORITY. Answer

for more solution manuals,visit libgen.is, libgen.st, libgen.rs, and forum.mhut.org

Solution is monitor based, using a separate wait condition for each level of priority. 1 2

// Monitor−b a s e d s o l u t i o n #i n c l u d e <QThread>

24 CHAPTER 3. THREADS AND CONCURRENCY IN STANDARD C++ 3 4 5 6 7 8

#i n c l u d e <QMutexLocker> #i n c l u d e <QWaitCondition> #i n c l u d e <c s t r i n g > #i n c l u d e #i n c l u d e <s t r i n g > #i n c l u d e

9 10

u s i n g namespace s t d ;

11 12 13

const int MAXPRIORITY = 10; const int NUMAGENTS = 20;

14 15 16 17 18 19 20 21 22 23

//−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− c l a s s BankAccount { protected : double balance ; string holderName ; QMutex l ; QWaitCondition priCond [ MAXPRIORITY ] ; int waitingCount [ MAXPRIORITY ] ;

24 25 26 27 28 29

30 31 32 33 34 35 36 37

public : B a n k A c c o u n t ( string name , double init ) ; double getBalance ( ) ; void deposit ( double ) ; void w i t h d r a w ( double , i n t ) ; // t h e h i g h e s t t h e s e c o n d ←֓ argument , t h e h i g h e r t h e p r i o r i t y o f t h e r e q u e s t }; //−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− B a n k A c c o u n t : : B a n k A c c o u n t ( string name , double init ) { holderName = name ; balance = init ; memset ( waitingCount , 0 , MAXPRIORITY * s i z e o f ( int ) ) ; }

38 39 40 41 42 43

//−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− double BankAccount : : getBalance ( ) { return balance ; }

44 45 46 47 48 49 50

//−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− void BankAccount : : deposit ( double x ) { Q M u t e x L o c k e r m l (&l ) ; b a l a n c e += x ; c e r r << ” D e p o s i t e d ” << x << e n d l ;

// now d e t e r m i n e i f any t h r e a d i s w a i t i n g t o withdraw int priLvl = MAXPRIORITY − 1; w h i l e ( p r i L v l >= 0 ) { i f ( waitingCount [ priLvl ] > 0) { c e r r << ”Waking l e v e l ” << p r i L v l << e n d l ; priCond [ priLvl ] . wakeAll () ; // wake up a l l t h e t h r e a d s ←֓ at that p r i o r i t y l e v e l return ; } p r i L v l −−; }

52 53 54 55 56 57 58 59

60 61 62 63 64

}

65 66 67

68 69 70 71

//−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− // t h e h i g h e s t t h e s e c o n d argument , t h e h i g h e r t h e p r i o r i t y o f ←֓ the request void BankAccount : : withdraw ( double x , i n t lvl ) { Q M u t e x L o c k e r m l (&l ) ; l v l = ( l v l >= M A X P R I O R I T Y ) ? M A X P R I O R I T Y − 1 : l v l ; //make ←֓ s u r e p r i o r i t y i s not too high

25 // d e t e r m i n e i f o t h e r s a t t h e same o r h i g h e r waiting int othersWaiting = 0; int priLvl = MAXPRIORITY − 1; w h i l e ( p r i L v l >= l v l ) { o t h e r s W a i t i n g += w a i t i n g C o u n t [ p r i L v l ] ; p r i L v l −−; }

74 75 76 77 78 79 80

priority

a r e ←֓

// i f t h e y a r e o r t h e f u n d s a r e n o t enough w a i t a l s o i f ( othersWaiting > 0 | | balance < x ) { w a i t i n g C o u n t [ l v l ]++; while ( x > balance ) p r i C o n d [ l v l ] . w a i t (&l ) ;

82 83 84 85 86 87 88

b a l a n c e −= x ; w a i t i n g C o u n t [ l v l ]−−; i f ( w a i t i n g C o u n t [ l v l ] == 0 ) { priLvl = lvl ; w h i l e ( p r i L v l >= 0 && w a i t i n g C o u n t [ p r i L v l ] == 0 ) p r i L v l −−; i f ( p r i L v l >= 0 ) priCond [ priLvl ] . wakeAll () ; }

89 90 91 92 93 94 95 96 97 98

} else b a l a n c e −= x ;

99 100 101 102

c e r r << ” Withdrew ” << x << ” w i t h p r i ” << l v l << e n d l ;

103 104

}

105 106 107 108 109 110 111 112 113 114 115

116 117

//−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− // c l a s s f o r t e s t i n g p u r p o s e s c l a s s Agent : public QThread { private : B a n k A c c o u n t * ba ; double amount ; int priority ; public : Agent ( BankAccount * b , double x , p r i o r i t y ( p r i ) {} void run ( ) ; };

i n t p r i ) : b a ( b ) , a m o u n t ( x ) , ←֓

118 119 120 121 122 123 124 125 126

//−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− void Agent : : run ( ) { i f ( amount > 0) ba−>d e p o s i t ( a m o u n t ) ; else ba−>w i t h d r a w (− a m o u n t , p r i o r i t y ) ; }

127 128 129 130 131

//−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− i n t main ( i n t argc , char * argv [ ] ) { B a n k A c c o u n t b ( ” John Doe” , 0 ) ;

132 133 134 135 136 137 138 139 140

141 142 143

Agent * ag [ N U M A G E N T S ] ; f o r ( i n t i = 0 ; i < N U M A G E N T S ; i++) { a g [ i ] = new A g e n t (&b , −r a n d ( ) % 2 0 , i / 2 ) ; a g [ i]−> s t a r t ( ) ; } sleep (1) ; b . d e p o s i t ( N U M A G E N T S * 2 0 ) ; // make s u r e enough f u n d s a r e ←֓ available f o r ( i n t i = 0 ; i < N U M A G E N T S ; i++) a g [ i]−> w a i t ( ) ;