doc/gtut-tour-11-explicitwait.doc

   1 /**
   2 @page GRAS_tut_tour_explicitwait Lesson 11: Explicitely waiting for messages
   3
   4 \section GRAS_tut_tour_explicitwait_toc Table of Contents
   5  - \ref GRAS_tut_tour_explicitwait_intro
   6  - \ref GRAS_tut_tour_explicitwait_use
   7    - \ref GRAS_tut_tour_explicitwait_algo
   8    - \ref GRAS_tut_tour_explicitwait_code
   9      - \ref GRAS_tut_tour_explicitwait_code_msg
  10      - \ref GRAS_tut_tour_explicitwait_code_cb
  11      - \ref GRAS_tut_tour_explicitwait_code_api
  12      - \ref GRAS_tut_tour_explicitwait_code_smain
  13      - \ref GRAS_tut_tour_explicitwait_code_cmain
  14  - \ref GRAS_tut_tour_explicitwait_recap
  15
  16 <hr>
  17
  18 \section GRAS_tut_tour_explicitwait_intro Introduction
  19
  20 The messaging primitive we have seen so far are somehow limited on the
  21 receiver side. You have to attach a callback to a message type, and then go
  22 into an infinite loop. Sometimes, you want to block your execution until a
  23 message of a given type arrives. This often occures when you want to deal
  24 with synchronization problems.
  25
  26 As an example, we will study a simple centralized algorithm for mutual
  27 exclusion. In short, when the client wants to enter the critical section
  28 (CS), it sends a specific message to the server, and waits for the server to
  29 answer back with another message. While the client is "locked" waiting for
  30 the message, nothing else should occure for it (no callback or timer should
  31 be served).
  32
  33 The simplest interface to explicit message waiting allows you to specify the
  34 message type you are willing to accept (using gras_msg_wait()). But you can
  35 also specify a list of accepted message types (using gras_msg_wait_or()), or
  36 even provide your own message filters to decide precisly the kind of message
  37 you are waiting for (for example depending on message content -- this is
  38 done using gras_msg_wait_ext()).
  39
  40 Any message received not matching your expectation will be queued for
  41 further use. Ie, they will be stored in memory and are candidates for the
  42 next gras_msg_handle() or gras_msg_wait().
  43
  44 \section GRAS_tut_tour_explicitwait_use Example: mutual exclusion with centralized coordinator
  45
  46 \subsection GRAS_tut_tour_explicitwait_algo GRAS modelization of the algorithm
  47
  48 This section naturally provides an example of how to use gras_msg_wait(),
  49 but it can also be seen as an example of the guidelines provided in
  50 \ref GRAS_howto_design.
  51
  52 So, here are the caracteristics of our example:
  53
  54 There is two types of processes:
  55  - several <i>clients</i> which want to enter a critical section
  56  - a <i>server</i>, which grants clients to enter the CS when no other
  57    process is already in it.
  58
  59 There is three kind of messages in the system:
  60  - <i>request</i> (from clients to server) to ask for the permission to enter the CS
  61  - <i>release</i> (from clients to server) to express that they exited the CS
  62  - <i>grant</i> (from server to clients) to allow the given process to enter the CS
  63
  64 The server has 2 callbacks attached:
  65  - When it gets a <i>request</i>, it checks whether their is already a process in
  66    the CS. If yes, it adds the requester into a FIFO list. If not, it sends
  67    a <i>grant</i> message to the asking client.
  68  - When it gets a <i>release</i>, it checks whether there is some waiting
  69    processes in the waiting queue. If yes, it dequeues the first one and
  70    send a <i>grant</i> message to it. If no, it notes that the CS is free.
  71
  72 The server has two private data (for the callbacks to work):
  73  - a boolean indicating whether there is a process in the CS already
  74  - a waiting queue (#xbt_dynar_t is quite natural to code this).
  75
  76 The client interface is composed of two functions:
  77  - lock(), which tries to get the grant from the server to enter the CS.
  78    This is where explicit waiting comes into the game. This function sends a
  79    <i>request</i> to the server, and blocks until the server issues a
  80    <i>grant</i> back.
  81  - unlock(), which informs the server that we exited the CS (by sending a
  82    <i>release</i> message)
  83
  84 \subsection GRAS_tut_tour_explicitwait_code The code step-by-step
  85
  86 \subsubsection GRAS_tut_tour_explicitwait_code_msg a) Messages declaration
  87
  88 First of all, we should have a function declaring all used messages. As said
  89 before, this should be in a separate function so that it can be shared
  90 between all process kinds and avoid code dupplication which may result in
  91 definition discrepency.
  92
  93 Here, there is no payload attached to the messages.
  94
  95 \dontinclude 11-explicitwait.c
  96 \skip message_declaration
  97 \until }
  98
  99 \subsubsection GRAS_tut_tour_explicitwait_code_cb b) Defining private data and callbacks of the server
 100
 101 Then, we define the callbacks that should be invoqued on the server side
 102 when some messages are received, as previously. For this, we also have to
 103 declare a structure for the private data of the server.
 104
 105 \skip typedef
 106 \until end_of_release_callback
 107
 108 \subsubsection GRAS_tut_tour_explicitwait_code_api c) Client-side API
 109
 110 Now, we define the functions that the client must call to use the service.
 111 Note that this is where the explicit wait feature is used.
 112
 113 \skip lock
 114 \until end_of_unlock
 115
 116 \subsubsection GRAS_tut_tour_explicitwait_code_smain d) Server-side initialization
 117
 118 The core of our distributed service is implemented (protocol, actions on
 119 server side, and accessing function on client side). We should now
 120 initialize the server and let it wait for incomming messages.
 121
 122 Defining when to stop the server can become tricky. The simplest solution is
 123 to never let the server stop. It simply runs forever. But the simulator will
 124 raise an error at the end, so I won't do so here to keep the output clean.
 125 Another solution would be to deal with client membership properly: clients
 126 registers, use the service and quit afterward. When no client use the
 127 service, the server stops. This would be a bit difficult to implement
 128 (actually, there is an AMOK module to do so simply: \ref AMOK_pm).
 129 Here, we will just hardcode that the clients ask 5 times for the token, and
 130 that there is two clients. This clearly simplify the problem.
 131
 132 \dontinclude 11-explicitwait.c
 133 \skip gras_userdata_new
 134 \until gras_msg_handle
 135
 136 \subsubsection GRAS_tut_tour_explicitwait_code_cmain e) Client-side use
 137
 138 And now, the client is <b>really</b> simple to write:
 139
 140 \skip message_declaration
 141 \until }
 142
 143 \section GRAS_tut_tour_explicitwait_recap Recapping everything together
 144
 145 The program now reads:
 146 \include 11-explicitwait.c
 147
 148 Which produces the expected output:
 149 \include 11-explicitwait.output
 150
 151
 152 */