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