HTML/procesy.htm

   1 <html>\r
   2 <HEAD><TITLE>Processes</TITLE></HEAD>\r
   3 \r
   4 \r
   5 <BODY>\r
   6 <H1>Chapter: PROCESSES</H1>\r
   7 \r
   8 <H2>by Andrzej Salwicki</H2>\r
   9 \r
  10 <H4>Plan</H4>\r
  11 \r
  12 \r
  13 <UL>\r
  14 <LI><A HREF = "#syntax">Syntax</A>\r
  15 <UL>\r
  16 <LI><A HREF = "#restric">Context Restrictions</A>\r
  17 <LI><A HREF = "#alicall">Alien Call</A>\r
  18 <LI><A HREF = "#maska">Mask</A>\r
  19 </UL>\r
  20 \r
  21 <LI><A HREF = "#semantyka">Semantics</A>\r
  22 <UL>\r
  23 <LI><A HREF = "#accept">Accept</A>\r
  24 <LI><A HREF = "#aliencall">Execution of Alien Call</A>\r
  25 </UL>\r
  26 \r
  27 <LI><A HREF = "#przyklady">Examples</A>\r
  28 <LI>Tips: how to\r
  29 </UL>\r
  30      \r
  31 <HR>\r
  32 <H4>Introduction</H4>\r
  33 <P>\r
  34 The word <em>process </em> has two meanings: it may denote a module of a programm or\r
  35 it may denote an object of a module. <BR>\r
  36 Once created a process-object may be activated. Its instructions are executed in parallel \r
  37 with the instructions of other processes-objects. The word <I>multithread </I>execution explains \r
  38 well the intuition of concurrent processes.\r
  39 While the objects of classes and of coroutines share a processor, \r
  40 the objects of processes do have a processor associated with each \r
  41 object of process. The processor can be either a physical processor \r
  42 e.g. a personal computer or workstation connected to other computers \r
  43 by means of LAN network, or it may be a virtual processor, in reality \r
  44 it can be an ability to acquire a time slice of a real computer. \r
  45 (More or less like a process in Unix system).\r
  46 \r
  47 \r
  48 <P>\r
  49 <H2><A NAME = "syntax">Syntax</A></H2>\r
  50 \r
  51 \r
  52 <P>The syntax of module process is similar to those of modules class or coroutine\r
  53 \r
  54 <PRE><B>unit</B> {<I>processTypeName</I>}: {<I>prefix</I>} <B>process</B> ({<I>formalParameters</I>}):\r
  55      {<I>declarations</I>}\r
  56 <B>begin</B>\r
  57      {<I>instructions</I>}\r
  58 <B>end</B> {<I>processTypeName</I>};</PRE>\r
  59 \r
  60 The present status of the processes in Loglan82 is experimental. There are several contextual restrictions imposed. Some of them are explained by the experimental and temporary status ... Some of them are not checked by the compiler. Sorry! Attention please!\r
  61 \r
  62 <H3><A NAME = "restric">Context restrictions.</A></H3>\r
  63 \r
  64 \r
  65 <OL>\r
  66 <LI> All process modules should be declared as global units. They can not be nested. They can inherit however. \r
  67 <BR>This is explained by the distributed model of memory of processes. \r
  68 <LI> There is no shared memory. Every process can access only its private resources, whether declared locally or transmitted as parameters, or procedures and functions declared in other object of process if it is accessible to the process.\r
  69 <LI> The parameters of a process can be\r
  70 <BR>        integer, real, char, Boolean, string  i.e. of primitive type\r
  71 <BR>or\r
  72 <BR>        process objects\r
  73 <BR>or\r
  74 <BR>        procedure declared in a process object\r
  75 <BR>or\r
  76  <BR>       procedure transmitted as a formal parameter.\r
  77 \r
  78 <LI> The procedure's instruction of the form\r
  79 <P>\r
  80          call X.proced1(params)\r
  81 \r
  82 <BR>placed in the body of a process module  has an effect of communicating the calling process with the callee X.\r
  83 <BR>Therefore such an instruction will be named an alien call of a procedure. We shall see later that the execution of an alien call needs a cooperation of both the calling and the callee processes.\r
  84 \r
  85 <LI> The operations in, is , qua, this\r
  86 are not defined on processes. The user should not put them in the body of a process module.\r
  87 <P>Sorry, the compiler will not check it as an error!!!\r
  88 \r
  89 <LI> There is no dynamic type checking concerning objects of processes.\r
  90 <BR>Again, the compiler does not warn you. Be careful!\r
  91 \r
  92 <LI> Each process has its own subsystem of coroutines. The instructions attach and detach can not transfer the control beyond the subsystem.\r
  93 \r
  94 \r
  95 <LI> No process object can access the global variables declared in the MAIN process. This does not apply to the principal program=MAIN. Remark that MAIN is a process object too.\r
  96 \r
  97 </OL>\r
  98 <P><H2><A NAME = "alicall">Allien call</A></H2>\r
  99 \r
 100 \r
 101 <DD><P>Let Y be a process object. Let X be another process object. If a command of the following form   \r
 102 \r
 103         <P>     <B>call</B> X.procedr1(actual_params)\r
 104 \r
 105 <BR>is to be executed in Y then we shall say of an allien call.\r
 106 <BR>The called procedure, in this example procedr1, can be either: \r
 107 <UL>\r
 108 <LI> - one of the procedures declared in the process X,  or\r
 109 <LI> - one of procedures being formal parameters of X,  or\r
 110 \r
 111 <LI> - a procedure which is a formal parameter of another procedure called      by alien call (this is a recursive definition).    \r
 112 </UL>\r
 113 <P>Y is said a calling process, X is  the callee process.\r
 114 \r
 115 \r
 116 <H3><A NAME = "maska">Mask</A>.</H3>\r
 117 \r
 118 \r
 119 <P>Each process has a predefined variable MASK associated with it. The value of the variable is a subset of the set of names of procedures and functions that are declared inside the process.\r
 120 \r
 121 The initial value of the MASK is the empty set .\r
 122 \r
 123 The instructions <B>ENABLE</B> and <B>DISABLE</B> can change the value of the MASK variable.\r
 124 \r
 125 <PRE>\r
 126 \r
 127                          MASK={q1, ... ,qn}\r
 128                                 \r
 129                                 \r
 130          <B>enable</B> p1,p2;          \r
 131                                         <B>disable</B> p1, p2;\r
 132                                 \r
 133                                 \r
 134                 MASK={q1, ... , qn, p1, p2}\r
 135 </PRE>\r
 136 As you see from the above diagram  an instruction 'enable' adds the names to the MASK. An instruction 'disable' deletes the names from the mask.\r
 137 \r
 138 There are two other instructions \r
 139         <B>RETURN ENABLE</B> p1, ... , pn <B>DISABLE</B> q1, ... , qk;\r
 140 and\r
 141         <B>ACCEPT</B> p1, ... , pl;\r
 142 \r
 143 which modify the value of the mask. Their meaning is described below.\r
 144 \r
 145 The instruction RETURN ENABLE p1, ... , pn DISABLE q1, ... , qk;  is legible in the body of a procedure or function only. The instruction ACCEPT can be put anywhere in a process module.\r
 146 \r
 147 \r
 148 \r
 149 <P>\r
 150 <H2><A NAME = "semantyka">SEMANTICS</A></H2>\r
 151 \r
 152 <P>Let us repeat: a process can be initialised, its initialisation phase terminates when the return statement is reached. It can be given a name, say p, and it remains passive. When another proces executes the command resume(p) then the process p is activated, its actions are executed in parallel with the actions of the other active processes.\r
 153 Once activated it continues the execution of its commands. It may execute a stop command and become a passive process. Other processescan call for an allien call of a procedure (or function) declared in the process p. The permission to interrupt the execution of its own commands and to do a service for an external process will be granted iffthe process p is active and if the name of the called procedure is in MASK.\r
 154 The process can change the value of  the MASK variable by means of commands enable and disable. One can use also the commands accept and return disable ... enable...\r
 155 <P>\r
 156 <H3><A NAME = "accept">ACCEPT</A></H3>\r
 157 \r
 158 <P>\r
 159 The execution of the command accept p1, ... , pn is as follows:\r
 160 1°  the names p1, ... ,pn are added to the MASK\r
 161 2° the process waits for an allien call of a procedure listed in the MASK.\r
 162 \r
 163 When an allien call is terminated the MASK is set to its previous value, i.e. to that before the ACCEPT was executed. This is a rule with an exception: see the return disable ... enable... command below. \r
 164 \r
 165 \r
 166 \r
 167 <H3><A NAME = "aliencall">Execution of an allien call</A></H3>\r
 168 \r
 169 \r
 170 <OL>\r
 171 <BR>\r
 172 <LI>1. The calling process Y calls the callee process X and waits,\r
 173 <LI>2. If the callee process X is active and if it is before execution of its Loglan command C and if the name of the called procedure is in the value of MASK variable, (let us recall it is a set of names of procedures) then the callee X is interrupted and\r
 174 <LI>3. The calling process Y transmits the actual parameters of the called procedure to the process X and waits.\r
 175 <LI>4. The calllee X saves the MASK, next, the MASK is set to empty (it means that all further alien calls are to wait) \r
 176 <BR>    REMARK that the called procedure can change the value of MASK.\r
 177 <LI>5.  The callee X executes the called procedure.\r
 178 <LI>6. When the execution of the procedure reaches its end then the output parameters of the procedure are transmitted to the calling process Y which receives them.\r
 179 <LI>7. The MASK is restored to its state before the call.\r
 180 <BR>REMARK. If the execution of the called procedure ends with the command\r
 181 <BR>        <B>return enable</B> ... <B>disable</B> ...;\r
 182 <LI>Then the restored MASK is subject to the modifications described by this command.\r
 183 <LI>8. Both processes resume their activities from before alien call\r
 184 <BR>   - the calling process passes to the instruction next to the alien call,\r
 185 <BR>   - the callee process executes the instruction C which was planned        already to be executed.\r
 186 <BR> \r
 187 </OL>\r
 188 \r
 189 \r
 190 The semantical phenomena\r
 191 of parallel programming are different than those of sequential programming. \r
 192 \r
 193 <A NAME = "przyklady">Example 1</A>\r
 194 Let us look what will happen if you execute the following program First.\r
 195 First of all, you will remark that the strings are mixed. This is because\r
 196  the commands write(a(i)) of the process w1 are executed in parallel with \r
 197 the commands write(a(i)) of the another process w2. The screen receives \r
 198 them interleaved and so the characters appear on the screen interleaved. \r
 199 \r
 200 Next, remark that the execution of a program is no longer determined \r
 201 by its text and its data. Execute the following program twice and compare \r
 202 the results. You will observe that the results displayed on the screen are \r
 203 different. However there is no visible reason for this difference.\r
 204 \r
 205 \r
 206 <PRE><B>program</B> First;\r
 207   <B>   unit </B>writer: <B>process</B>(node:integer, nr:integer,s: string);\r
 208     <B>     var </B>i: integer,\r
 209              A: <B>arrayof </B>char;\r
 210   <B>   begin</B>\r
 211      <B>      return;</B>\r
 212         a:=unpack(s);\r
 213      <B>      for </B>i := lower(a) <B>to </B>upper(a)\r
 214      <B>      do</B>\r
 215               write(a(i));\r
 216      <B>      od;</B>\r
 217            writeln;\r
 218   <B>   end </B>writer;\r
 219  \r
 220   <B>   var </B>w1, w2: writer, i: integer;\r
 221  \r
 222 <B>begin</B>\r
 223      w1:=<B>new</B> writer(0,1,"ici un texte tres long,\r
 224                         tres long, tres long tres long tres long tres long");\r
 225      w2:=<B>new</B> writer(0,2,"zdies otche'n dolgoj tiekst, otche'n dolgoj                                      tiekst, otche'n dolgoj tiekst");\r
 226      <B>   resume</B>(w1);\r
 227      <B>   resume</B>(w2);\r
 228      writeln("give me a character");\r
 229      readln;\r
 230 <B>end </B>First\r
 231  </PRE>\r
 232 We are going now to remede the interleaving the characters. \r
 233 For this purpose we are going to construct a semaphore. \r
 234 But what it is a semaphore? Well, it is a device that allows \r
 235 a train to pass iff it is in a state permitting to pass and in \r
 236 the same moment of the passage it changes its state to blocking one. \r
 237 Therefore only one train is authoised to pass. In the state blocking \r
 238 it accepts only the demand to liberate the semaphore i.e. the state of \r
 239 the semaphore changes from blocking to free. By default, it is assumed \r
 240 that it is only the train that passed who will execute the command: \r
 241 liberate (when it leaves the station).\r
 242 \r
 243 \r
 244 \r
 245 <PRE><B>program</B> Second;\r
 246 \r
 247   <B>unit </B>aSemaphore: <B>process</B>(node:integer);\r
 248      <B>unit </B>pass: <B>procedure;</B>\r
 249      <B>end </B>pass;\r
 250      <B>unit </B>free: <B>procedure;</B>\r
 251      <B>end </B>free;\r
 252   <B>begin</B>\r
 253      <B>return;</B>\r
 254      <B>do</B>\r
 255           <B>accept </B>pass;\r
 256           <B>accept </B>free;\r
 257      <B>od</B>\r
 258   <B>end </B>aSemaphore;\r
 259 \r
 260   <B>unit </B>writer: <B>process</B>(node:integer, nr:integer,s: string, sem: aSemaphore);\r
 261     <B>var </B>i: integer,\r
 262         A: <B>arrayof </B>char;\r
 263   <B>begin</B>\r
 264      <B>return;</B>\r
 265      <B>call </B>sem.pass;\r
 266      a:=unpack(s);\r
 267      <B>for </B>i := lower(a) <B>to </B>upper(a)\r
 268      <B>do</B>\r
 269        write(a(i));\r
 270      <B>od;</B>\r
 271      writeln;\r
 272      <B>call </B>sem.free;\r
 273   <B>end </B>writer;\r
 274  \r
 275   <B>var </B>s: aSemaphore, w1, w2: writer, i: integer;\r
 276  \r
 277 <B>begin</B>\r
 278   s := <B>new </B>aSemaphore(0);\r
 279   resume(s);\r
 280   w1:=<B>new</B> writer(0,1,"ici un texte tres long,\r
 281                         tres long, tres long tres long tres long tres long",s);\r
 282   w2:=<B>new</B> writer(0,2,"zdies otche'n dolgoj tiekst, otche'n dolgoj                                                        tiekst, otche'n dolgoj tiekst", s);\r
 283   resume(w1);\r
 284   resume(w2);\r
 285   writeln("give me a character");\r
 286   readln;\r
 287 <B>end </B>Second\r
 288 </PRE>\r
 289 \r
 290 <B><I>Theorem</I></B>\r
 291 The texts shown on the screen will never be mixed.\r
 292 \r
 293 We can prove even stronger theorem that for any number of objects-processes of type writer defined as in the program Second they critical sections (here it means printing on the screen) will be executed in mutual exclusivity.\r
 294 \r
 295 Therefore with the use of semaphores one is able to assure \r
 296 the mutual exclusivity of critical sections of given processes.\r
 297 \r
 298 A new question appears: is it true that semaphores garantee \r
 299 the mutual exclusion?\r
 300 The answer is no, as it can be seen from the Third program.\r
 301 \r
 302 \r
 303 \r
 304 <PRE>program Third;\r
 305 \r
 306   unit Semaphore: process(node:integer);\r
 307      unit pass: procedure;\r
 308      end pass;\r
 309      unit free: procedure;\r
 310      end free;\r
 311   begin\r
 312      return;\r
 313      do\r
 314           accept pass;\r
 315           accept free;\r
 316      od\r
 317   end Semaphore;\r
 318 \r
 319   unit writer1: process(node:integer, nr:integer,s: string, sem: semaphore);\r
 320     var i: integer,\r
 321         A: arrayof char;\r
 322   begin\r
 323      return;\r
 324      call sem.pass;\r
 325      a:=unpack(s);\r
 326      for i := lower(a) to upper(a)\r
 327      do\r
 328        write(a(i));\r
 329      od;\r
 330      writeln;\r
 331      call sem.free;\r
 332   end writer1;\r
 333   unit writer2: process(node:integer, nr:integer,s: string, sem: semaphore);\r
 334     var i: integer,\r
 335         A: arrayof char;\r
 336   begin\r
 337      return;\r
 338      call sem.free;\r
 339      a:=unpack(s);\r
 340      for i := lower(a) to upper(a)\r
 341      do\r
 342        write(a(i));\r
 343      od;\r
 344      writeln;\r
 345      call sem.pass;\r
 346   end writer2;\r
 347   var s: semaphore, w1: writer1, w2: writer2, i: integer;\r
 348 begin\r
 349   s := new semaphore(0);\r
 350   resume(s);\r
 351   w1:=new writer1(0,1,"ici un texte tres long,\r
 352                         tres long, tres long tres long tres long tres long",s);\r
 353   w2:=new writer2(0,2,"zdies otche'n dolgoj tiekst, otche'n dolgoj                                                      tiekst, otche'n dolgoj tiekst", s);\r
 354   resume(w1);\r
 355   resume(w2);\r
 356   writeln("give me a character");\r
 357   readln;\r
 358 end Third\r
 359 </PRE>\r
 360 The example above reveals that one should use semaphores with rigour. \r
 361 It may be the case that both processes use a semaphore but due \r
 362 to an error their critical sections are executed in parallel causing \r
 363 a chaos.\r
 364 \r
 365 In most cases it would be better to conceive the architecture of the \r
 366 system of parallel processes as clients and servers. In the example \r
 367 below we create one server: ecran for serving the resourc eof screen. \r
 368 The processes are calling the process server asking for a service. \r
 369 In this case it will be printing on the screen. \r
 370  \r
 371 <PRE>program Fourth;\r
 372   unit ecran: process(node: integer);    (* it is a server *)\r
 373     unit print: procedure(s: string);\r
 374        var i: integer,\r
 375            A: arrayof char;\r
 376     begin\r
 377      a:=unpack(s);\r
 378      for i := lower(a) to upper(a)\r
 379      do\r
 380        write(a(i));\r
 381      od;\r
 382      writeln;\r
 383     end print;\r
 384   begin\r
 385     return;\r
 386     do accept print od             (* it offers just the print service *)\r
 387   end ecran;\r
 388 \r
 389   unit writer: process(node:integer, nr:integer,s: string, ec:ecran); \r
 390     (* it is a client *)\r
 391   begin\r
 392      return;\r
 393      call ec.print(s)\r
 394   end writer;\r
 395  \r
 396   var e: ecran, w1, w2: writer, i: integer;\r
 397  \r
 398 begin\r
 399   e := new ecran(0);\r
 400   resume(e);\r
 401   w1:=new writer(0,1,"ici un texte tres long,\r
 402                         tres long, tres long tres long tres long tres long", e);\r
 403   w2:=new writer(0,2,"zdies otche'n dolgoj tiekst, otche'n dolgoj                                                               tiekst, otche'n dolgoj tiekst", e);\r
 404   resume(w1);\r
 405   resume(w2);\r
 406   writeln("give me a character");\r
 407   readln;\r
 408 end Fourth\r
 409 </PRE>\r
 410 Theorem\r
 411 The critical sections of printing the texts supplied by the processes w1 and w2 is done in mutual exclusion.\r
 412 \r
 413 ============================================================================\r
 414 Example 5\r
 415 \r
 416 In the example below we shall illustrate an asynchronous cooperation of processes.\r
 417 The case we are going to discuss now is as follows: there are several processes " writers ". Any of writers may print a file on a designated printer. In order to increase the throughput and in order to avoid an intermixed printing we have spoolers - one for each printer. A printer prints files taking them out of a queue.\r
 418 \r
 419 <PRE><B>program</B> Five;\r
 420  \r
 421   <B>unit </B>writer1: <B>process</B>(node: integer, printer1: spooler);\r
 422 \r
 423   <B>begin</B>\r
 424 \r
 425   <B>end </B>writer1;\r
 426 \r
 427   <B>unit </B>writer2: <B>process</B>(node: integer, printer1, printer2: spooler);\r
 428      (* this process may print on any of 2 printers *)\r
 429   <B>end </B>writer2\r
 430 \r
 431   <B>unit </B>spooler: <B>process</B>(node: integer);\r
 432 \r
 433     <B>var </B>Q: queue,\r
 434           f: file,\r
 435      tick: integer;\r
 436  \r
 437     <B>unit </B>print: <B>procedure</B>(f: file, ticket: integer);\r
 438     <B>begin</B>\r
 439        <B>call </B>Q.insert(f);\r
 440        <B>if </B>Q.full <B>then </B><B>return disable</B> print <B>fi;</B>\r
 441        tick := tick + 1;\r
 442        ticket := tick;\r
 443     <B>end </B>print;\r
 444 \r
 445   <B>begin </B>(*spooler*)\r
 446     Q := <B>new </B>queue;\r
 447     <B>return;</B>\r
 448 \r
 449      <B>do</B>\r
 450        <B>disable </B>print;\r
 451        <B>if </B>Q.empty <B>then </B><B>accept</B> print <B>fi;</B>\r
 452        f := Q.out;\r
 453        <B>enable</B> print;\r
 454        (* printing the file *)\r
 455         ...\r
 456      <B>od</B>\r
 457    <B>end </B>spooler;\r
 458 \r
 459  <B>var </B>s1, s2: spooler,\r
 460      w1, w2: writer1,\r
 461      w3    : writer2;\r
 462 <B>begin</B>\r
 463 \r
 464    ...\r
 465    s1 := <B>new </B>spooler(0);\r
 466    <B>resume</B>(s1);\r
 467 \r
 468    w1:= <B>new </B>writer1(0, s1);\r
 469    w2 := <B>new </B>writer1(0, s1);\r
 470    <B>resume</B>(s1);\r
 471    <B>resume</B>(s2);\r
 472 \r
 473    \r
 474 <B>end </B>Five\r
 475 </PRE>\r
 476 What are the properties of the program Five?\r
 477 Is it possible to obtain a mixture of texts coming from different files?\r
 478 <HR>\r
 479 <ADDRESS></ADDRESS>\r
 480 </body>\r
 481 </html>\r
 482 <DD>\r
 483 \r
 484 \r
 485 \r
 486 \r
 487 \r
 488 <H2></H2>\r
 489 &ograve;\r
 490 <HR>