Concurrent programming, Course examination 12.12.2008 Grading guidelines

[11 p] Critical section. 

1. (Teemu Kerola)
   1. [1 p] Def. Segment(s) of code that only one process at time may be executing.
   2. [2 p] Int disable. Good: one processor system, very short wait time. Not good: multiprocessors or not very short wait time.
   3. [2 p] Locks. Good: multiproc. system, shared mem, very short wait time. Not good: not very short wait time or uniproc. system
   4. [2 p] Semafor. Good: longer wait time, synchr. primitives part of OS support, baton passing needed. Not good: very short time wait, need solution at progr. lang. level, distr. system
   5. [2 p] Monitor. Good: longer wait times ok, mutex is part of a more complex problem solution, divide impl. with synchr. solut. and other work ,synchr solution at programming language level. Not good: very short wait time or distributed system.
   6. [2 p] R-A Token. Good: distributed system with no shared mem. Not good: centralized system, shared mem, or a system with very many nodes (token msg becomes too large)
       
2. (Päivi Kuuppelomäki)
   
   1. [2 p] See lecture 5, slide 12 and Stall 05 Chapter 6 Concurrency:Deadlock and starvation, 1p/question
   2. [2 p] See lecture 5, slide 15 and Stall 05 Chapter 6 subchapter The Conditions for Deadlock, At least first 3 conditons 2p less 1 p
   3. [2 p] There is a deadlock in the system.
   4. [3 p] See lecture slides 28-31. The question has same kind of matrixes as the example shown in slides 30-31.
   5. [2 p] See lecture 5 pages 20-24. In general(1 p): disallow one of the deadlock condiotions. Specifically in this case (1 p): one example was enough.
       
3. (Teemu Kerola)
   See lecture 11, slides 16-19.
   
   
• can also combine cond. variables pot_empty and fill_turn, and wait while portions==H or bee_filling.
• no difference between monitor and the code using it (no understanding of monitor). (total 0p)
• bear code (2p), bees code (2p), monitor code (4p), reasonable explanation (3p)
• many bees can fill the pot at the same time (-2p)
• bee or bear waits always (-1p)
• bees collect honey or fill pot inside monitor method, or it is not clear where bees collect honey or fill the pot (-2p)
• bear eats honey inside monitor method, or it is not clear where bear eats the honey (-2p)
   
4. (Päivi Kuuppelomäki)

1. [4 p] See lecture 10, slides 18-22 and BenA 06 chapter 10.6 Token passing algorithms. Distributed critical section algorithm using token-passing.(1 p) Meaning of Main and what it is needed for. (1p) Meaning of Receive and what it is needed for. (1p) Combining the prosesses into one process is not a good idea, because it would not be easy to receive request about token in any time. (1p)
2. [3 p] The elements of the set requested contains the last request messages from the other nodes. Each node updates it if it gets larger number from the node sending the request. The elements of the set granted are ticket numbers (myNum) held by each node the last time it was granted permission to enter its critical section. It is updated after critical section. Only the copy of granted maintained by the node with token is meaningful, and it is passed from one node to another as part of the token.
3. [4 p]

   We assume that also myNum is 550 for p1, 7700 for p2 and 33 for p3.
   Process p2 gets first into critical section, because it has already
   token.
   The granted of node where p2 is located contains (550, 7700, 33)
    
   Process p1 sends following messages:
   send(request, 2, 1, 551)
   send(request, 3, 1, 551)
   and waits in receive(token, granted)
   
   Process p3 sends following messages:
   send(request, 1, 3, 34)
   send(request, 2, 3, 34)
   and waits in receive(token, granted)
   
   Receive in the same node where p1
   send(request, 2, 3, 34) goes to receive(request, source=3 , reqNum=34)
   After the message has arrived requested=(0, 7700, 34)
   
   Receive in the same node where p3
   send(request, 3, 1, 551) goes to receive(request, source=1 , reqNum=551)
   After the message has arrived requested=(551, 7700, 0)
   
   Receive in the same node where p2
   send(request, 2, 1, 551) goes to receive(request, source=1, reqNum=551)
   send(request, 2, 3, 34) goes to receive(request, source=3 , reqNum=34)
   The order of these message is not fixed!
   After both messages have arrived requested=(551, 0, 34)
   
   If the process p2 is in the critical section when messages arrive then
   the token is sent after p2 has exited the critical section. In the algorithm
   it is not fixed to which process the token is sent next (it there is
   more choices). If only one of the messages asking token has only arrived
   then the message is ofcourse sent to that process.
   
   We assume that the token is sent to p1. (P3 would be also possible.)
   Either the Main process or Receive process will send the token by
   message: send(token, 1, granted=(550, 7700, 33))
   
   Waiting of process P1 ends and it gets token and granted=(550, 7700, 33).
   P1 goes to the critical section and after that it sends token to P3 (we
   assume that P2 has not asked for the token).
   granted[1]=551
   send (token, 3, (551, 7700, 33)) 
   
   Waiting of process P3 ends and it gets token and granted=(551, 7700, 33).
   P3 goes to the critical section
   granted[3]=34
   When p3 end the critical section granted=(551, 7700, 34) and it keeps
   the token if there is no new requests.
   
   The order of the processes get into the critical section is p2,p1,p3 or
   p2,p3,p1.