1 chapter 5 class entity entity objects model major simulation components. they may compete with one another for resources (res, bin), cooperate over stretches of time (wait/coopt), or even interrupt one another. entity object : new entity("e"); ---------------------- ! entity ! ---------------------- ! title "e 1" ! ! loop ! ! timein 0.0 ! ! evtime 0.0 ! ! priority 0 ! ! cycle 0 ! ! wants 0 ! ! interrupted 0 ! ! currentq none ! ! owner none ! ! terminated false ! ! ll none ! ! bl none ! ! rl none ! ! suc none ! ! pred none ! ! avail ! ! idle ! ! coopt ! ! interrupt(n) ! ! repeat ! ! into(q) ! ! out ! ! getserialno ! ! list ! ! insert ! ! insertaftercurrent ! ! insertdelay0 ! ! schedule(t) ! ! cancel ! entity level ---------------------- 1class entity page 5-2 outline class entity(title); value title; text title; virtual: label loop; begin real timein, evtime; integer priority, cycle, wants, interrupted; ref(queue)currentq; ref(entity)owner, ll, bl, rl, suc, pred; boolean terminated; boolean procedure idle; boolean procedure avail; procedure coopt; procedure interrupt(n); integer n; procedure repeat; procedure into(q); ref(queue)q; procedure out; procedure getserialno; procedure list; procedure insert; procedure insertaftercurrent; procedure insertdelay0; procedure schedule(t); real t; procedure cancel; actions: if title.length > 10 then title :- title.sub(1,10); getserialno; evtime := -1.0; detach; loop:; inner; terminated := true; if not idle then passivate; end***entity***; actions the actions of the class body first curtail the length of the title to 10 characters if longer, and then append a 2-digit class serial number (by the call getserialno) so that individual objects can be distinguished (e.g. see object depicted on the previous page). evtime is set to -1.0 (a signal that the object is out of the event list) and then the object is detached. this gives the user the chance to individually name the entity before scheduling it. for example, compare new entity("e").schedule(..); with e :- new entity("e"); e.schedule(..); 1class entity page 5-3 on return, the inner class body actions are executed (note the position of the virtual label loop). then terminated is set to true and the object is passivated (if in the event list). a demos error results if an attempt is made to schedule a terminated entity. attributes text title is a concatenation of the user given value (curtailed to 10 characters if longer) and a 2 digit class serial number. label loop is by default situated before the inner statement. it can be redefined at inner levels. loop is used in conjunction with repeat to permit a textually neat description of a cyclic class body with repeated actions preceded by an initialisation. the rather ugly initialisation; while true do begin repeated actions; end; can be replaced by initialisation; loop: repeated actions; repeat; real timein is set to time whenever an entity joins a queue. it is used to collect queue statistics on average wait times, etc. real evtime holds the time at which an entity's next phase will be entered when it is in the event list. it is set to -1.0 when an entity is removed from the event list. integer priority gives the entity's priority. this attribute is used by into whenever an entity joins a queue. an entity is ranked according its current value (larger values at the front end); tie breaks are resolved by placing later entries behind entities with the same priority but already in the queue. thus when an entity e enters a queue, e.pred == none or e.pred.priority >= e.priority and e.suc == none or e.priority > e.suc.priority integer cycle is incremented by 1 each time repeat is called. it thus gives a measure of how many times repeated entity actions have been executed. integer wants is set to the amount currently requested when an entity is waiting upon a res or a bin, otherwise its value is zero. this enables release and give to operate a little more efficiently as, if the first entity in a resource queue wants more than is currently 1class entity page 5-4 available, there is no point in trying to unblock it. integer interrupted is normally zero, but is set to n by a call interrupt(n). it is the user's responsibility to clear it after dealing with an interrupt, e.g. by such coding as if interrupted > 0 then begin if interrupted = 1 then deal with interrupt of type 1 else if interrupted = 2 then deal with interrupt of type 2 else ..................; interrupted := 0; end else no interrupt pending; ref(queue)currentq is set to reference the queue an entity is currently a member of when it enters (set to q on a call into(q)). it is set to none when removed from a queue by a call on out. by queue we mean any queue or sub-class of queue, i.e. queue, res, bin, waitq, or condq. ref(entity)owner references the entity if any which is currently coopting this entity, or none. it is set by a call on coopt and reset to none when the slave entity is next scheduled. boolean terminated is set to true when the class body actions are exhausted (including those at inner levels). a terminated object may not be scheduled again (this is checked for in schedule). ref(entity)ll, bl, rl reference neighbour entities in the event list, or none if the entity is not scheduled. the event list has been implemented as a leftist priority tree with special references root to the last entity in the tree, and current to the first entity in the tree (the one now operating). the following invariant holds for a leftist priority tree t: for all e belonging to t: e.ll == none => e.rl == none for all l belonging to e's left sub-tree l.evtime <= e.evtime for all r belonging to e's right sub-tree l.evtime < r.evtime < e.evtime (e, l, r are all entities). from which we may deduce that e.ll.evtime = e.evtime => e.rl == none, so that entities with equal event times form a linear sub-list connected by bl's and ll's, with the rl's of all but the first == none. this is handy to know when inserting delay 0 or after current. 1class entity page 5-5 ref(entity)suc, pred link together entities in queues. they are set to none when an entity leaves a queue. the suc of the last entity in a queue is none, as is the pred of the first. boolean procedure avail; a call e.avail returns true if e is not currently coopted, i.e. if e.owner == none. boolean procedure idle; a call e.idle returns true if e is currently out of the event list, i.e. e.evtime = -1.0. procedure coopt; a call e.coopt causes a demos error if e.owner =/= none. otherwise, e.owner is set to current, and e is removed from its current queue if any. procedure interrupt(n); integer n;. a call e.interrupt(n) removes an idle entity from its current queue, if any; and cancels a scheduled entity e. e.interrupted is set to n, and then e is scheduled delay 0 (at the current clock time, but as last entity scheduled for that time). procedure repeat increments cycle by 1 and then goes to loop. (it is of course meant to be called locally: do not call e.repeat.) procedure into(q); ref(queue)q; a call e.into(q) removes e from its current queue , if any. then it inserts e into q in priority order and sets e.currentq to q. into maintains the invariant e.pred.priority >= e.priority > e.suc.priority (e.suc, e.pred =/= none). into also maintains various statistics on q (average queue length, wait time, length now, etc.). procedure out. e.out removes e from its current queue, if any. it also maintains queue statistics and sets e.suc, e.pred, and e.currentq to none. procedure getserialno compares title with a list of names kept in zyqentnames. if a match is found in list member z, z.n is concatenated with title to give a text and a serial number. then z.n is incremented to reflect the next serial number. n is kept modulo 100. if no match is found, a new zyqenttitle object is entered at the head of zyqentnames with title as its text (and its n = 1). since getserialno is automatically called by the system, it should not be used explicitly again. procedure list. a call, e.list, sends one line of information about an entity in the event list to outf. (it is used in snapsqs.) e.evtime in columns 6-15 e.title in columns 17-28 e.ll.title in columns 30-41 e.bl.title in columns 43-54 e.rl.title in columns 56-67 1class entity page 5-6 procedure insert is an auxiliary routine used by hold and schedule. it assumes that the correct evtime has been set locally and that ll, bl, rl == none. the routine starts from root and inserts in o(log n). special care has to be taken if the fresh entry is inserted as the new root, or as the new current. (root and current must be maintained; a new current must be resumed). the insert algorithm is: 1. e.evtime >= root.evtime. insert as the new root and quit. 2. set w :- root. from now on, w references the current level in the event list and e is to be inserted below w. l is short for w.ll; r is short for w.rl. we maintain the invariant w.evtime > e.evtime. ----- ----- ! ! ! ! ! w ! ! e ! ! ! ! ! ----- ----- . . . . ----- ----- ! ! ! ! ! l ! ! r ! ! ! ! ! ----- ----- e.evtime < w.evtime l.evtime < r.evtime < w.evtime if r =/= none l.evtime <= w.evtime if r == none initial configuration 3. insert in the left sub-tree of w if we can (l.evtime <= w.evtime). let l :- w.ll;. 4. l == none? (implies r == none). insert e as new w.ll and quit. (a test is inserted for the new entry being current; and if so the new current e is resumed. however this case should not arise since it has been optimised out of calls on hold and schedule.) ----- ! ! ! w ! ! ! ----- . . ----- ! ! ! e ! ! ! ----- e.ll == none, e.bl == w, e.rl == none; w.ll == e 1class entity page 5-7 5. (l =/= none and) e.evtime < l.evtime? go down one level (w :- w.ll;) and continue from step 3. 6. (l =/= none and) e.evtime = l.evtime? insert between l and w and quit. ----- ! ! ! w ! ! ! ----- . . . . ----- ----- ! ! ! ! ! e ! ! r ! ! ! ! ! ----- ----- . . ----- ! ! ! l ! ! ! ----- e.ll == l, e.bl == w, e. rl == none; l.bl == e; w.ll == e l.evtime = e.evtime < r.evtime < w.evtime 7. (l =/= none and) e.evtime > l.evtime? insert in the right sub-tree of w. let r :- w.rl;. 8. (l =/= none and) r == none? insert as the new w.rl and quit. ----- ! ! ! w ! ! ! ----- . . . . ----- ----- ! ! ! ! ! l ! ! e ! ! ! ! ! ----- ----- e.ll == none, e.bl == w, e.rl == none; w.rl == e l.evtime < e.evtime < w.evtime 9. (l, r =/= none and) e.evtime < r.evtime? go down one level (w :- w.rl) and continue from step 3. 1class entity page 5-8 10. (l, r =/= none and) e.evtime >= r.evtime? insert between w and r and quit. ----- ! ! ! w ! ! ! ----- . . . . ----- ----- ! ! ! ! ! l ! ! e ! ! ! ! ! ----- ----- . . ----- ! ! ! r ! ! ! ----- e.ll == r, e.bl == w, e.rl == none; w.rl == e; r.bl == e l.evtime < r.evtime <= e.evtime < w.evtime procedure insertaftercurrent is a fast o(1) insert used in demos scheduling routines such as acquire, take, ... e.insertaftercurrent sets e.evtime to time and then inserts e as the new bl of current. if current was root, root is set to reference the new entry e. no effect if evtime >= 0.0, i.e. the entity is already in the event list. ----- ----- ----- ! ! ! ! ! ! ! e ! ! w ! ! w ! ! ! ! ! ! ! ----- ----- ----- . . . => . ----- ----- ! ! ! ! ! c ! ! e ! ! ! ! ! ----- ----- current . . ----- ! ! ! c ! ! ! ----- c.bl==w;w.ll==e e.ll==c,e.bl==w,e.rl==none c.evtime <= w.evtime c.evtime=e.evtime<=w.evtime 1class entity page 5-9 procedure insertdelay0; e.insertdelay0 inserts e at time, but as last entity scheduled for that time. the routine is a fast o(1) insert and starts from current following bl's until the insertion point is found. the exceptional case (where the new entry becomes root) is taken care of at the head of the routine. no effect if evtime >= 0.0, i.e. the entity is already in the event list. procedure schedule(t); real t; e.schedule (t) schedules a passive entity e into the event list delay t, i.e. at time + t, t >= 0.0. an error results if e is terminated (e.terminated = true). the call has no effect if e is already scheduled (e.evtime >= 0.0. to reactivate such an e, you must first cancel it). if t <= now, then e preempts current and the actions of e are taken up. if now < t <= 0.0, e is scheduled delay 0. if t >= 0.0, e.evtime is set and e is inserted from the top o(ln n) by a call on insert. procedure cancel; a call e.cancel deletes the entity e from the event list. it has no effect if e is already passive (e.evtime < 0.0). a run time error results if an attempt is made to cancel the only entry in the event list (e == current == root). n.b. only the cases e == e.bl.ll are depicted; the cases e == e.bl.rl are very similar. the routine sets evtime to -1.0 and then runs through the tests: e.ll == none? (=> e.rl == none). ----- ----- ! ! ! ! ! w ! ! w ! ! ! ! ! ----- ----- . . . . . . ----- ----- ----- ! ! ! ! ! ! ! e ! ! r ! => ! r ! ! ! ! ! ! ! ----- ----- ----- . . ----- ----- ! ! ! ! ! p ! ! p ! ! ! ! ! ----- ----- if e is the root then a fatal error is incurred - an attempt to delete 1class entity page 5-10 the last entity in the event list. otherwise there are two complications to overcome: 1) when we delete e we must remember to swing a non-empty right sub-tree of e.bl to the left. 2) if e == current, we must remember to locate and resume the new current. if e.bl.rl == none, this is e.bl; otherwise it is the leftmost entity in the right sub-tree of e.bl (shown as p). the code outline is: if this entity == root then error; if this entity == current then begin if bl.rl == none then current :- e.bl else begin locate the new current current :- e.bl.rl.ll.ll....ll; swing right sub-tree of e.bl in as e.bl.ll; e.bl.rl :- none; end; detach e from the event list; resume(current); end else begin swing right sub-tree of e.bl in as e.bl.ll; e.bl.rl :- none; detach e from the event list; end; e.rl == none? (and e.ll =/= none) ----- ----- ! ! ! ! ! w ! ! w ! ! ! ! ! ----- ----- . . . . ----- ----- ! ! => ! ! ! e ! ! l ! ! ! ! ! ----- ----- . . ----- ! ! ! ! ! l ! ! ! ----- 1class entity page 5-11 we merely have to set the links of e.ll and e.bl to bypass e and detach e from the event list. the only complication arises if e == root, when e.ll becomes the new root. e.rl =/= none? (=> e.ll =/= none) ----- ----- ! ! ! ! ! w ! ! w ! ! ! ! ! ----- ----- . . . . ----- ----- ! ! ! ! ! e ! => ! r ! ! ! ! ! ----- ----- . . . . . ----- ----- ----- ! ! ! ! ! ! ! l ! ! r ! ! p ! ! ! ! ! ! ! ----- ----- ----- . . . ----- ----- ! ! ! ! ! p ! ! l ! ! ! ! ! ----- ----- in this case, we swing the right sub-tree of e across in place of e, hanging the left sub-tree of e onto the leftmost entity, p,in the sub-tree r. if e == root then root is set to e.rl. example: changing the event list algorithm in operating systems simulations, it is sometimes necessary to interrupt current when a job of greater priority gets scheduled. how would we cope with this in demos? one way, used to illustrate the ease with which parts of the standard can be ripped out and replaced, would be to change the basic event list algorithms where necessary. we have to change the tie break rule for entities in the event list from first-come, first served (fcfs) to priority and then fcfs for entities with equal event times and equal priorities. also it is now possible for a freshly scheduled entity to interrupt current. whenever an entity is 1class entity page 5-12 scheduled at time, we have to check if it is the new current and resume it if it is. neither insertaftercurrent nor now are now needed. we replace all calls on insertaftercurrent by calls on insertelay0 and change the value of the constant now to 0.0. procedure insertdelay0 (page 5-9) may be coded as before with the while loop condition replaced by evtime > p.evtime or (evtime = p.evtime and priority >= p.priority) as the new entry may be current, we also include as the last statement in the procedure body if p == current then begin current :- this entity; resume(current); end; in procedure hold (page 6-1), the check on current's successor in the event list becomes evtime > p.evtime or (evtime = p.evtime and priority >= p.priority) procedure insert (pages 5-6:5-8) is also quite easy to program. all we need do is alter the two 'descend' tests labelled procedure insert1belowx and procedure insert2belowx to our old friend evtime > p.evtime or (evtime = p.evtime and priority >= p.priority) and remove the call error(15,....). procedure schedule (page 5-9) simplifies down a little. 'now' loses its significance - we can only interrupt current if we have greater priority. thus we replace the if-statement labelled preemptcurrent (yes, all if ... if ... else ... of it) by if t < 0.0 then t := 0.0; if t = 0.0 then insertdelay0 else begin evtime := evtime + t; insert; end; 1class entity page 5-13 5.2 class mainprogram demos uses the same trick as class simulation to return control to the main program block (see common base ]4, page 128[). demos creates an object of class mainprogram, referenced by ref(mainprogram)demos, to impersonate the main program block. its class body actions are detach; repeat; every time this object becomes current, the detach statement causes the actions of the main program block to be taken up again; and every time hold is called from inside the main program block, the mainprogram object is rescheduled and the new current is resumed. outline entity class mainprogram; begin detach; repeat; end***entity***; initialising actions current :- root :- demos :- new mainprogram("demos"); demos.evtime := 0.0; this code installs demos as the first entity object in the event list at time 0.0. since demos is an entity it can be cancelled by calls on either passivate from within the main program block, or demos.cancel; and later rescheduled by a call demos.schedule(....). it can also seize resources. this may be useful when a simulation has a run length which is not known at the outset. example of use in a simulation model of a single ferry system, writing the main block as: demos begin declarations; initialising statements; hold(480.0); end; 1class entity page 5-14 will end the simulation run after 8 hours regardless of the state of the system. this is not realistic enough. let the ferry stop working for the day when it returns to its home port, drops off its load and finds that it is not worthwhile starting another crossing, say time >= 465 minutes. an outline of the appropriate code is: demos begin entity class ferry; begin load; cross and return; unload; if time < 465.0 then repeat; demos.schedule(0.0); end***ferry***; other declarations; initialising statements; passivate; end; see also in the demos text book ]1, example 5, pp. 67-71[. for another example, consider the classic doctor's surgery which closes after 2 hours. any patients being consulted or waiting are seen, but not later arrivals. let the doctor be modelled by ref(res)dr. we can code the demos block as: demos begin ref(res)dr; other declarations; hold(540.0); comment start at 9.00 o'clock; initialising statements; hold(120.0); dr.acquire(1); end; 1 chapter 6 global event list procedures following the style of simula, there are two global scheduling procedures hold and passivate. (passivate is really redundant as cancel is local to entity in demos and serves the same purpose. but passivate is a little quicker; its base zyqpassivate is used in other demos routines.) there is also real procedure time which returns the value of current.evtime. real procedure time simply returns current.evtime. procedure zyqpassivate is equivalent to current.cancel, but is a little faster as it has a restricted environment. it is used in several demos routines to put current to sleep if it finds itself blocked. zyqpassivate does not give a trace. the algorithm is: 1. current == root? fatal error - an attempt to delete the only entry in the event list. 2. bl.rl == none? bl is the new current. goto 4). 3. (bl.rl =/= none). follow ll's of bl.rl to locate the new current. swing bl.rl over to bl.ll and set bl.rl => none. 4. delete the old current. resume the new current. 5. quit. procedure passivate sends a one line trace to outf if the trace switch is on, and then calls zyqpassivate. procedure hold(t); real t; delays current by t (>= 0.0). we first replace a negative t by 0.0. then we increment e.evtime by t. the following cases arise: 1. current == root? only one item in the event list. quit. 1global event list procedures page 6-2 2. locate next entity p. if evtime < p.evtime, e is still current. quit. 3. current.evtime >= p.evtime. delete current and set current => p. insert the old current from the top. resume p. quit. 1 chapter 7 classes queue, waitq, and condq 7.1 class queue tab class queue serves a dual purpose. primarily it is used in demos to prefix classes waitq, condq, res and bin. but queue is also usable in its own right as a convenient means of chaining several entities. queue ! ! --------------------- ! ! ! ! ! ! condq waitq resource ! ! --------- ! ! ! ! res bin n.b. the only objects allowed in queues are entities. an entity e is entered into a queue by a call e.into(q); and is removed from its (one) current queue by a call e.out. into and out maintain various queue statistics such as average queue time, queue length now, maximum queue length attained, etc. 1classes queue, waitq, and condq page 7-2 queue object : new queue("cargo") ------------------- ! queue ! ------------------- ! title "cargo" ! ! virtual:report ! ! virtual:reset ! ! obs 0 ! ! resetat 0.0 ! ! next none ! ! join(r) ! ! writetrn ! tab level ------------------- ! length 0 ! ! zeros 0 ! ! maxlength 0 ! ! qint 0.0 ! ! cum 0.0 ! ! lastqtime 0.0 ! ! first none ! ! last none ! ! list ! ! report ! ! reset ! queue level ------------------- outline tab class queue; begin integer length, zeros, maxlength; real qint, cum, lastqtime; ref(entity)first, last; procedure list; procedure report; procedure reset; actions: if this queue is queue then join(queueq); end***queue***; actions on generation, a queue object first executes the actions of its tab prefix (which curtail title to 12 characters, if longer, and then call reset). then the actions of the class body enter the object into queueq if it is a queue object (but not if it is in a sub-class; thus noqueue, waitq, condq, res, and bin objects are not entered into queueq). 1classes queue, waitq, and condq page 7-3 attributes (for title, obs, resetat, next, join, writetrn, see tab, page 2-4). integer length is maintained by into and out (see entity, page 5-5) to reflect the current length of the queue, that is the number of entities currently waiting in the queue. integer zeros is updated by 1 each time an entity leaves the queue after a 'zero' wait (zero is taken as < epsilon). it reflects the number of zero waits since clock time resetat. integer maxlength holds the maximum queue length attained since clock time resetat. real qint is used to record the time integral of the queue length since resetat. it is updated by calls on into and out, each of which increments qint by (e.timein-lastqtime)*length prior to entering or removing entity e into/from the queue. real cum is used to maintain a time integral of the entity wait times (including zero waits). when an entity e leaves its current queue q (by an explicit or implicit e.out), cum is incremented by time-e.timein (and obs by 1). real lastqtime records the last time at which an entity joined or left the queue; = resetat if obs = 0. ref(entity)first references the first entity in the queue (one with the highest priority), or none if length = 0. ref(entity)last references the last entity in the queue (one with the least priority), or none if length = 0. procedure list writes to outf. it prints a heading followed by one line of information on each entity waiting in the queue. this line contains the entities position in the queue (columns 17-20), its title (in columns 22-33), its priority (in columns 35-42), and its time of entry (in columns 44-53). it is called from snapqueues. entities waiting in l truck q ***************************** no object priority entry in q 1 l 8 4 9.805 2 l 9 3 9.707 3 l10 3 9.776 4 l11 3 9.787 5 l12 3 9.790 6 l13 0 9.737 7 l14 0 9.760 8 l15 0 9.807 1classes queue, waitq, and condq page 7-4 procedure report sends a report on the queue's status since resetat on one line to outf. it consists of: its title in columns 1-12 its reset time in columns 14-23 the number of completed waits (calls on out) in columns 24-30 the maximum queue length since resetat in columns 31-36 the current queue length in columns 37-42 the average queue length (qint plus an end correction) / (time-resetat) in columns 44-53 the number of zero waits in columns 54-59 the average waiting time (time spent in the queue by entities which have now left) in columns 61-70. it includes zero waits. n.b. columns 44-53 are skipped if time - resetat < epsilon; columns 61-70 are skipped if obs - 0. title / (re)set/ obs/ qmax/ qnow/ q average/zeros/ av. wait s truck q 0.000 97 4 3 0.796 25 8.082e-02 procedure reset sets zeros, obs, qint, cum to zero; lastqtime and resetat to time; maxlength to length. it does not affect length, first, or last. example of use cars arrive at a quay and are then carried across the water on a ferry. at the far side they are rescheduled and resume their actions again. a queue onboard is used to link cars together during the crossing. cars leave the ferry in reverse order. unloading and loading take 0.5; the ferry has a capacity of n cars and waits until it is full before sailing (summer season?). ref(waitq)quay; entity class car; begin queueforferry: quay.wait; unload: drive away; end***car***; 1classes queue, waitq, and condq page 7-5 entity class ferry(n); integer n; begin integer k; ref(entity)c; ref(queue)onboard; onboard :- new waitq("on board"); loop: for k := 1 step 1 until n do begin c :- quay.coopt; hold(load time); c.into(onboard); end; hold(crossing); for k := 1 step 1 until n do onboard.last.schedule(0.5*k); hold(0.5*n); return trip; repeat; end***ferry***; typical report (n = 2) q u e u e s *********** title / (re)set/ obs/ qmax/ qnow/ q average/zeros/ av. wait on board 5.000 90 2 2 0.947 0 10.259 w a i t q u e u e s ********************* title / (re)set/ obs/ qmax/ qnow/ q average/zeros/ av. wait quay 0.000 92 1 0 0.137 80 1.486 quay * 0.000 92 12 10 3.099 12 29.062 7.1.1 class noqueue class noqueue is a trick used in the implementation of waitq where we really need two queues together - one for the masters, one for the slaves (but none for the little boy who lives down the lane). we declare queue class noqueue;; a noqueue object is not entered into the queue queueq by the class body actions at the queue level as these read if this queue is queue then join(queueq); noqueue objects generated by waitqs are entered by the class body actions of waitq into waitqq. 1classes queue, waitq, and condq page 7-6 7.2 class waitq waitq's are used in the master/slave synchronisation in which several entities cooperate together over a period of time. instead of having several entities moving down the event list together, it is simplest to single out one entity as the master and let it coopt the others for the period in question. slave entities are released from their coopting owner when next scheduled. if the slaves are individually named, they may be coopted explicitly by using the routine coopt local to entity. however, this is not usually the case. a waitq contains two queues: one for the slaves (its own queue level mechanism), and ref(queue)masterq for the masters. waitq object : new waitq("quay"); ------------------------ ! queue ! ------------------------ ! title "quay" ! ! virtual:report ! ! virtual:reset ! ! obs 0 ! ! resetat 0.0 ! ! next none ! ! join(r) ! ! writetrn ! tab level ------------------------ ! length 0 ! ! zeros 0 ! ! maxlength 0 ! ! qint 0.0 ! ! cum 0.0 ! ! lastqtime 0.0 ! ! first none ! ! last none ! ! list ! ! report ! ! reset ! queue level ------------------------ ! masterq==new noqueue ! ! wait ! ! coopt ! ! avail ! ! find ! waitq level ------------------------ 1classes queue, waitq, and condq page 7-7 outline queue class waitq; begin ref(queue)masterq; procedure wait; ref(entity)procedure coopt; boolean procedure avail(e,c); name e,c; ref(entity)e; boolean c; procedure find(e,c); name e,c; ref(entity)e; boolean c; actions: masterq :- new noqueue(title); masterq.join(waitqq); join(waitqq); end***waitq***; actions on generation, a waitq object first executes the actions of its tab prefix (which curtail title to 12 characters, if longer, and then call reset); and then those of its queue prefix (nil). then the main class body actions create a noqueue object and enter it into waitqq; then this waitq object is entered into waitqq. the net effect is that reports on waitqs occupy two lines: the masterq is reported on line 1, and this waitq (which gives 'slave' statistics) is reported on line 2. similarly, reset will reset both objects separately. attributes (for title, obs, resetat, next, join, writetrn, see tab, page 2-4; for length, zeros, maxlength, qint, cum, lastqtime, first, last, list, report, reset, see queue, page 7-2.) procedure wait turns current into a (potential) slave resting in this queue. q.wait; current.into(this queue); if q.masterq.first =/= none then masterq.first.insertdelay0; passivate; the call places current in the slave queue in its priority order, activates the first master (if any) delay 0 (behind current), and then cancels current. ref(entity)procedure coopt removes the first slave from the slave queue and coopts it on behalf of current. if the slave queue is empty, the requester is blocked in the master queue (in priority order) until it is the first entity and the slave queue is not empty. 1classes queue, waitq, and condq page 7-8 e :- q.coopt; current.into(masterq); while length = 0 or current =/= masterq.first do passivate; current.out; if masterq.first =/= none and length = 0 then masterq.first.insertaftercurrent; p :- coopt :- first; p.coopt; current is entered into masterq in priority order. if the length of the slave queue is zero or current is not the first entity in masterq, current is passivated and remains dormant until the above conditions are fulfilled. then current leaves the masterq and coopts the first slave entity (which will remove it from the slave queue). should it be possible to unblock the master queue, the first entity in masterq is activated after current. boolean procedure avail(e, c); name e, c; ref(entity)e; boolean c; q.avail(e, condition) returns true if an entity e can be found in the slave queue of q satisfying the condition. if avail returns false, e is set to none. if avail returns true, e references the first entity in the slave queue satisfying the stated condition. notice that e and c are called by name; thus e may be assigned to and c is dynamically re-evaluated every time it is used. procedure find(e, c); name e, c; ref(entity)e; boolean c; a call q.find(e, c) made by current delays current until q.avail(e, c) is true and then coopts e on behalf of current. if blocked, current is delayed in q.masterq. q.find(e, c); current.into(masterq); while not q.avail(e, c) do begin p :- current.suc; if p =/= none then p.insertaftercurrent; passivate; end; p :- current.suc; current.out; e.coopt; if p =/= none then p.insertdelay0; 1classes queue, waitq, and condq page 7-9 example of use a cpu executes programs waiting in cpuq. each program has a cyclic life consisting of a burst on the cpu followed by an i/o transfer. ref(waitq)cpuq; entity class program; begin queueforcpuburst: cpuq.wait; doio: hold(i/o transfer time); repeat; end***program***; entity class cpu; begin ref(entity)e; e :- cpuq.coopt; hold(burst); e.schedule(0.0); repeat; end***cpu***; typical report w a i t q u e u e s ********************* title / (re)set/ obs/ qmax/ qnow/ q average/zeros/ av. wait cpu q 0.000 115 1 0 0.123 75 5.329 cpu q * 0.000 115 2 0 0.730 41 31.732 1classes queue, waitq, and condq page 7-10 7.3 class condq condq's are used to implement waits until in demos. a simple waituntil algorithm has been chosen which suffices in most cases. its advantage is that its application is always easy to understand. if the condition is complicated then it will appear in the program as complicated. this accords with the notion that it should be easy to write down simple conditions, and possible to write down even the most complicated. condq object : new condq("cond") ------------------- ! condq ! ------------------- ! title "cond" ! ! virtual:report ! ! virtual:reset ! ! obs 0 ! ! resetat 0.0 ! ! next none ! ! join(r) ! ! writetrn ! tab level ------------------- ! length 0 ! ! zeros 0 ! ! maxlength 0 ! ! qint 0.0 ! ! cum 0.0 ! ! lastqtime 0.0 ! ! first none ! ! last none ! ! list ! ! report ! ! reset ! queue level ------------------- ! all ! ! waituntil(c) ! ! signal ! condq level ------------------- outline queue class condq; begin boolean all; procedure waituntil(c); name c; boolean c; procedure signal; actions: join(condqq); end***condq***; 1classes queue, waitq, and condq page 7-11 actions on generation, a condq object first executes the actions of its tab prefix (which curtail title to 12 characters, if longer, and then call reset), and then those of its queue prefix (nil). the main class body actions enter the condq object into the reportq condqq. attributes (for title, obs, resetat, next, join, writetrn, see tab, page 2-4; for length, zeros, maxlength, qint, cum, lastqtime, first, last, list, report, reset, see queue, page 7-2.) boolean all is used as a flag in watuntil. if all is true, all entities waiting in the condq are activated to see if they can go when the condq is signalled. if all is false, only those at its head are tested and as soon as one condition evaluates to false, no more entities are tested. all can be used fruitfully when a condq contains entities waiting until on mixed conditions. procedure waituntil(c); name c; boolean c; a call q.waituntil(c) enters current into the condq q. then c is evaluated. if c is true, then current leaves q at once and continues on. if c is false, current is passivated and remains in the condq until tested and c evaluates to true. q.waituntil(c); current.into(this condq); while not c do begin if all then current.suc.insertaftercurrent; passivate; end; current.suc.insertaftercurrent; current.out; procedure signal; a call q.signal activates the first entity in the condq q delay 0. current continues on uninterruptedly; when e becomes current, it evaluates its condition c again and leaves the condq if c evaluates to true. as it does so it promotes the next condq member (if any) into the event list immediately behind itself. in this way, the condq entities are peeled off and tested one by one. if all is true, all entities are tested; if all is false, only those at the head of the condq. 1classes queue, waitq, and condq page 7-12 example of use having been emitted by a furnace in a steel mill, billets are transported to a soaking pit area on bogies. there they are unloaded by a crane. if the pits are full the billets are dumped by the pit side and await a crane and a free pit. if a pit is free, they are loaded straight in. ref(res)cranes, pits; ref(condq)pitq; entity class billet; begin hold(transport time); cranes.acquire(1); if pits.avail = 0 then begin hold(dump by pit area time); cranes.release(1); pitq.waituntil(cranes.avail > 0 and pits.avail > 0); pits.acquire(1); cranes.acquire(1); hold(load from pit side time); end else begin hold(unload into pit time); end; cranes.release(1); pitq.signal; hold(soak time); ................ end***billet***; typical report c o n d i t i o n q u e u e s ******************************* title / (re)set/ obs/ qmax/ qnow/ q average/zeros/ av. wait sq 0.000 114 1 0 5.038e-02 99 4.419e-03