1This README consists of LWP related parts taken from, 2 3 RPC2 User Guide and Reference Manual 4 M. Satyanarayanan (Editor) Richard Draves, James Kistler, 5 Anders Klemets, Qi Lu, Lily Mummert, David Nichols, Larry 6 Raper, Gowthami Rajendran, Jonathan Rosenberg, Ellen Siegel 7 8So occasional references to RPC2 can be safely ignored. 9 10Jan 11 12 13LWP, a coroutine-based lightweight process package. 14=================================================== 15 16 RPC2 runs on LWP, a lightweight process package that allows multiple 17 non-preemptive threads of control to coexist within one Unix process. 18 RPC2 and LWP run entirely at user-level on the Unix 4.3BSD interface; 19 no kernel changes are necessary. 20 21 The first versions of LWP and RPC2 were operational in early 1984 and 22 mid-1985 respectively. The design of LWP predates that of the 23 Cthreads package in Mach. LWP and Cthreads are conceptually similar, 24 but differ substantially in the details. We have successfully emulated 25 all of LWP on top of the preemptive and nonpre- emptive versions of 26 Cthreads, and a subset of the non-preemptive version of Cthreads on 27 top of LWP. 28 29 Both LWP and RPC2 have evolved over time, resulting in increased 30 functionality and robustness. They have also been ported to a wide 31 variety of machine architectures, such as IBM-RTs, MIPS, Sun2, Sun3, 32 Sparc, and i386, as well as variants of the Unix operating systems 33 such as Mach, SunOS and AIX. Whenever there has been choice between 34 portability and machine-specific performance, we have always favored 35 portability. 36 37 38Credits 39------- 40 41 The original design and implementation of LWP was done by Larry Raper. 42 Its documentation descends from a manual by Jonathan Rosenberg and 43 Larry Raper, later extended by David Nichols and M. Satyanarayanan. 44 Richard Draves, Qi Lu, Anders Klemets and Gowthami Rajendran helped in 45 revising and improving this document. 46 47 48The Basic LWP Package 49===================== 50 51 The LWP package implements primitive functions providing basic 52 facilities that enable procedures written in C, to proceed in an 53 unsynchronized fashion. These separate threads of control may 54 effectively progress in parallel, and more or less independently of 55 each other. This facility is meant to be general purpose with a heavy 56 emphasis on simplicity. Interprocess communication facilities can be 57 built on top of this basic mechanism, and, in fact, many different IPC 58 mechanisms could be implemented. The RPC2 remote procedure call 59 package (also described in this manual) is one such IPC mechanism. 60 61 The LWP package makes the following key design choices: 62 63 o The package should be small and fast; 64 o All processes are assumed to be trustworthy -- processes are not 65 protected from each others actions; 66 o There is no time slicing or preemption -- the processor must be 67 yielded explicitly. 68 69 In order to set up the environment needed by the lightweight process 70 support, a one-time invocation of the LWP_Init function must precede 71 the use of the facilities described here. The initialization function 72 carves an initial process out of the currently executing C procedure. 73 The process id of this initial process is returned as the result of 74 the LWP_Init function. For symmetry a LWP_TerminateProcessSupport 75 function may be used explicitly to release any storage allocated by 76 its initial counterpart. If used, it must be issued from the process 77 created by the LWP_Init function. 78 79 Upon completion of any of the lightweight process functions, an 80 integer value is returned to indicate whether any error conditions 81 were encountered. 82 83 Macros, typedefs, and manifest constants for error codes needed by the 84 lightweight process mechanism reside in the file <lwp.h>. A process 85 is identified by an object of type PROCESS, which is defined in the 86 include file. 87 88 The process model supported by the operations described here is based 89 on a non-preemptive priority dispatching scheme. (A priority is an 90 integer in the range [0..LWP_MAX_PRIORITY], where 0 is the lowest 91 priority.) Once a given lightweight process is selected and 92 dispatched, it remains in control until it voluntarily relinquishes 93 its claim on the CPU. Relinquishment may be either explicit 94 (LWP_DispatchProcess) or implicit (through the use of certain other 95 LWP operations). In general, all LWP operations that may cause a 96 higher priority process to become ready for dispatching, preempt the 97 process requesting the service. When this occurs, the priority 98 dispatching mechanism takes over and dispatches the highest priority 99 process automatically. Services in this category (where the scheduler 100 is guaranteed to be invoked in the absence of errors) are 101 102 o LWP_CreateProcess 103 o LWP_WaitProcess 104 o LWP_MwaitProcess 105 o LWP_SignalProcess 106 o LWP_DispatchProcess 107 o LWP_DestroyProcess 108 109 The following services are guaranteed not to cause preemption (and so 110 may be issued with no fear of losing control to another lightweight 111 process): 112 113 o LWP_Init 114 o LWP_NoYieldSignal 115 o LWP_CurrentProcess 116 o LWP_StackUsed 117 o LWP_NewRock 118 o LWP_GetRock 119 120 The symbol LWP_NORMAL_PRIORITY provides a good default value to use 121 for process priorities. 122 123 124A Simple Example 125--------------- 126 127 #include <lwp.h> 128 129 static void read_process (int *id) 130 { 131 LWP_DispatchProcess (); /* Just relinquish control for now */ 132 133 for (;;) { 134 /* Wait until there is something in the queue */ 135 while (empty(q)) LWP_WaitProcess (q); 136 /* Process queue entry */ 137 LWP_DispatchProcess (); 138 } 139 } 140 141 static void write_process (void) 142 { 143 ... 144 145 /* Loop & write data to queue */ 146 for (mesg=messages; *mesg!=0; mesg++) { 147 insert (q, *mesg); 148 LWP_SignalProcess (q); 149 } 150 } 151 152 int main (int argc, char **argv) 153 { 154 PROCESS *id; 155 156 LWP_Init (LWP_VERSION, 0, &id); 157 /* Now create readers */ 158 for (i=0; i < nreaders; i++) 159 LWP_CreateProcess (read_process, STACK_SIZE, 0, i, "Reader", 160 &readers[i]); 161 LWP_CreateProcess (write_process, STACK_SIZE, 1, 0, "Writer", &writer); 162 /* Wait for processes to terminate */ 163 LWP_WaitProcess (&done); 164 for (i=nreaders-1; i>=0; i--) LWP_DestroyProcess (readers[i]); 165 } 166 167 168The Lock Package 169================ 170 171 The lock package contains a number of routines and macros that allow C 172 programs that utilize the LWP abstraction to place read and write 173 locks on data structures shared by several light-weight processes. 174 Like the LWP package, the lock package was written with simplicity in 175 mind -- there is no protection inherent in the model. 176 177 In order to use the locking mechanism for an object, an object of type 178 struct Lock must be associated with the object. After being 179 initialized, with a call to Lock_Init, the lock is used in 180 invocations of the macros ObtainReadLock, ObtainWriteLock, 181 ReleaseReadLock and ReleaseWriteLock. 182 183 The semantics of a lock is such that any number of readers may hold a 184 lock. But only a single writer (and no readers) may hold the clock at 185 any time. The lock package guarantees fairness: each reader and 186 writer will eventually have a chance to obtain a given lock. However, 187 this fairness is only guaranteed if the priorities of the competing 188 processes are identical. Note that no ordering is guaranteed by the 189 package. 190 191 In addition, it is illegal for a process to request a particular lock 192 more than once, without first releasing it. Failure to obey this 193 restriction may cause deadlock. 194 195Key Design Choices 196------------------ 197 198 o The package must be simple and fast: in the case that a lock can be 199 obtained immediately, it should require a minimum of instructions; 200 o All the processes using a lock are trustworthy; 201 o The lock routines ignore priorities; 202 203 204A Simple Example 205---------------- 206 207 #include "lock.h" 208 209 struct Vnode { ... struct Lock lock; /* Used to lock this vnode */ ... }; 210 211 #define READ 0 212 #define WRITE 1 213 214 struct Vnode *get_vnode (char *name, int how) 215 { 216 struct Vnode *v; 217 218 v = lookup (name); 219 if (how == READ) 220 ObtainReadLock (&v->lock); 221 else 222 ObtainWriteLock (&v->lock); 223 } 224 225 226The IOMGR Package 227================= 228 229 The IOMGR package allows light-weight processes to wait on various 230 Unix events. IOMGR_Select allows a light-weight process to wait on 231 the same set of events that the Unix select call waits on. The 232 parameters to these routines are the same. IOMGR_Select puts the 233 caller to sleep until no user processes are active. At this time the 234 IOMGR process, which runs at the lowest priority, wakes up and 235 coaleses all of the select request together. It then performs a 236 single select and wakes up all processes affected by the result. 237 238 The IOMGR_Signal call allows a light-weight process to wait on 239 delivery of a Unix signal. The IOMGR installs a signal handler to 240 catch all deliveries of the Unix signal. This signal handler posts 241 information about the signal delivery to a global data structure. The 242 next time that the IOMGR process runs, it delivers the signal to any 243 waiting light-weight processes. 244 245Key Design Choices 246------------------ 247 248 o The meanings of the parameters to IOMGR_Select, both before and 249 after the call, should be identical to those of the Unix select; 250 o A blocking select should only be done if no other processes are 251 runnable. 252 253 254A Simple Example 255---------------- 256 257 void rpc2_SocketListener () 258 { 259 int ReadfdMask, WritefdMask, ExceptfdMask, rc; 260 struct timeval *tvp; 261 262 while (TRUE) { 263 . . . 264 ExceptfdMask = ReadfdMask = (1 << rpc2_RequestSocket); 265 WritefdMask = 0; 266 rc = IOMGR_Select (8*sizeof(int), &ReadfdMask, 267 &WritefdMask, &ExceptfdMask, tvp); 268 269 switch (rc) { 270 case 0: /* timeout */ 271 continue; /* main while loop */ 272 273 case -1: /* error */ 274 SystemError ("IOMGR_Select"); 275 exit (-1); 276 277 case 1: /* packet on rpc2_RequestSocket */ 278 . . . process packet . . . 279 break; 280 281 default: /* should never occur */ 282 } 283 } 284 } 285 286 287The Timer Package 288================= 289 290 The timer package contains a number of routines that assist in 291 manipulating lists of objects of type struct TM_Elem. TM_Elems 292 (timers) are assigned a timeout value by the user and inserted in a 293 package-maintained list. The time remaining to timeout for each timer 294 is kept up to date by the package under user control. There are 295 routines to remove a timer from its list, to return an expired timer 296 from a list and to return the next timer to expire. This specialized 297 package is currently used by the IOMGR package and by the 298 implementation of RPC2. A timer is used commonly by inserting a field 299 of type struct TM_Elem into a structure. After inserting the desired 300 timeout value the structure is inserted into a list, by means of its 301 timer field. 302 303 304A Simple Example 305---------------- 306 307 static struct TM_Elem *requests; 308 309 ... 310 311 TM_Init (&requests); /* Initialize timer list */ 312 ... 313 for (;;) { 314 TM_Rescan (requests); /* Update the timers */ 315 expired = TM_GetExpired (requests); 316 if (expired == 0) break; 317 ... process expired element ... 318 } 319 320 321The Preemption Package 322====================== 323 324 The preemption package provides a mechanism by which control can pass 325 between light-weight processes without the need for explicit calls to 326 LWP_DispatchProcess. This effect is achieved by periodically 327 interrupting the normal flow of control to check if other (higher 328 priority) procesess are ready to run. 329 330 The package makes use of the interval timer facilities provided by 331 4.2BSD, and so will cause programs that make their own use of these 332 facilities to malfunction. In particular, use of alarm (3) or 333 explicit handling of SIGALRM is disallowed. Also, calls to sleep (3) 334 may return prematurely. 335 336 Care should be taken that routines are re-entrant where necessary. In 337 particular, note that stdio (3) is not re-entrant in general, and 338 hence light-weight processes performing I/O on the same FILE structure 339 may function incorrectly. 340 341 342Key Design Choices 343------------------ 344 345 o The package should not affect the nonpreemptive scheduling 346 behaviour of processes which do not use it; 347 o It must be simple and fast, with a minimum of extra system 348 overhead; 349 o It must support nested critical regions; 350 o Processes using the package are assumed to be co-operating. 351 352 353A Simple Example 354---------------- 355 356 #include <sys/time.h> 357 #include "preempt.h" 358 359 ... 360 361 struct timeval tv; 362 363 LWP_Init (LWP_VERSION, ... ); 364 tv.tv_sec = 10; 365 tv.tv_usec = 0; 366 PRE_InitPreempt (&tv); 367 PRE_PreemptMe (); 368 369 ... 370 371 PRE_BeginCritical (); 372 373 ... 374 375 PRE_EndCritical (); 376 377 ... 378 379 PRE_EndPreempt (); 380 381 382The Fast Time Package 383===================== 384 385 The Fast Time package allows the caller to find out the current time 386 of day without incurring the expense of a kernel call. It works by 387 mapping the page of the kernel that has the kernels time-of-day 388 variable and examining it directly. Currently, this package only 389 works on Suns. You may call the routines on other machines, but they 390 will run more slowly. 391 392 The initialization routine for this package is fairly expensive since 393 it does a lookup of a kernel symbol via nlist (). If you have a 394 program which runs for only a short time, you may wish to call 395 FT_Init with the notReally parameter true to prevent the lookup from 396 taking place. This is useful if you are using another package that 397 uses Fast Time (such as RPC2). 398 399 400Some design considerations for LWP programming 401============================================== 402 403 Clients and servers are each assumed to be Unix processes using the 404 LWP package. RPC2 will not work independently of the LWP package. The 405 LWP package makes it possible for a single Unix process to contain 406 multiple threads of control (LWPs). An RPC call is synchronous with 407 respect to an individual LWP, but it does not block the encapsulating 408 Unix process. Although LWPs are non-preemptive, RPC2 internally 409 yields control when an LWP is blocked awaiting a request or reply. 410 Thus more than one LWP can be concurrently making RPC requests. There 411 is no a priori binding of RPC connections to LWPs, or LWPs to 412 subsystems within a client or server. Thus RPC connections, LWPs and 413 subsystems are completely orthogonal concepts. 414 415 Since LWPs are non-preemptive, a long-running computation by an LWP 416 will prevent the RPC2 code from getting a chance to run. This will 417 typically manifest itself as a timeout by the client on the RPC in 418 progress. To avoid this, the long running computation should 419 periodically invoke IOMGR_Poll followed by LWP_DispatchProcess. 420 421 For similar reasons, Unix system calls such as read (2), sleep (3), 422 and select (2) that may block for a long time should be avoided. 423 Instead, use IOMGR_Select. 424 425