In a cooperative scheduler, a permanently runnable background operating-system process that never yields can monopolize the CPU. The timer service, smoothing operating-system process, and display may then fail to run even when their messages are ready. Correct message passing alone does not supply process scheduling.
Use timer-driven scheduling preemption, so an interrupt can force a context switch without cooperation. To give the measurement and display work bounded response despite background computation, use priority scheduling with the background operating-system process below the responsive services, or an explicit reservation policy. Round-robin scheduling gives CPU access among a fixed finite runnable set, but meeting a particular deadline additionally requires bounded service execution and sufficient CPU capacity.
With a synchronous reply,
send(client,&answer) blocks until the client receives. An indefinitely unready client therefore stalls the smoothing operating-system process, which may in turn stall the timer service and its other clients as in the preceding part. If the client is merely delayed, this is blocking and delayed service; a deadlock requires a circular wait or a client that will never receive.Requiring correctly used synchronous send-and-receive helps. A client calling
sendrec(SMOOTH,&m) is committed to waiting for the matching reply as soon as its request has been accepted. This closes the scheduling window between a separate send and receive and prevents unrelated client computation from postponing that receive. It does not by itself fix slow measurements, arbitrary failures, circular dependencies between other services, or lack of CPU scheduling. With buffered replies the initial effect may instead be queue growth, depending on the message passing contract.With synchronous message passing, the smoothing operating-system process can still be waiting for
TEMP when its next PING is due. If the timer service sends to subscribers serially, it blocks on this unready recipient and cannot deliver the other subscribers' ticks: one slow sensor can delay every timer client through head-of-line blocking. Once it resumes, implementations may deliver late ticks, drift from their schedule, or accumulate overdue work.The consequence depends on the delivery model. With buffered sends the timer need not block immediately, but its queue can grow or overflow; the smoothing operating-system process still cannot process readings at a sustained rate faster than the sensor. A nonblocking notification mechanism or separate timer-delivery workers can isolate other subscribers, while coalescing missed ticks prevents an unlimited backlog. These changes do not make an over-slow sensor meet the original sampling rate.
Maintain the latest five temperature readings in a circular buffer, together with their running sum. The following C programming language code spells out the message passing interface rather than assuming a particular library:
send(dst,&m) is a blocking synchronous message passing send; receive(src,&m) receives from the specified sender or ANY and returns the sender's identity; sendrec(dst,&m) atomically sends the request and waits for that sender's reply in the same message object. Successful, reliable operations are assumed. Message contents are copied by the interface.enum { ANY = -1, TIMER = 1, TEMP = 2 };
enum { PULSE, PING, REQUEST, REPLY };
typedef struct {
int type;
int period_ms;
double value;
} Message;
extern void send(int dst, const Message *m);
extern int receive(int src, Message *m);
extern void sendrec(int dst, Message *m);
void smooth(void) {
double history[5] = {0};
double sum = 0;
int count = 0, next = 0;
Message m = { .type = PULSE, .period_ms = 1000 };
send(TIMER, &m); /* subscribe once */
for (;;) {
int sender = receive(count < 5 ? TIMER : ANY, &m);
if (sender == TIMER && m.type == PING) {
Message t = { .type = REQUEST };
sendrec(TEMP, &t); /* matching REPLY contains t.value */
if (count == 5)
sum -= history[next];
else
++count;
history[next] = t.value;
sum += t.value;
next = (next + 1) % 5;
} else if (count == 5 && m.type == REQUEST) {
Message answer = { .type = REPLY, .value = sum / 5.0 };
send(sender, &answer);
}
}
}Before the fifth reading, selective reception from
TIMER prevents premature client requests from being accepted. Such clients wait at their synchronous sends; they are not given a partial arithmetic mean. Thereafter the operating-system process receives both timer messages and client requests. Each accepted PING initiates one measurement; each accepted client request returns the arithmetic mean of the five most recently completed measurements, without initiating another measurement or changing the circular buffer.The loop invariant is that
count is the number of valid readings, capped at five, sum is their sum, and next is the next unused slot during startup or the oldest slot afterwards. Removing the overwritten reading and adding the new one preserves this loop invariant. Each update and reply uses time complexity and storage, since the window length is fixed. Under timely sensor replies, timer delivery and process scheduling, measurements are initiated once per second. The next parts explain failures of these timing assumptions; the code does not promise one-second sampling when the sensor itself cannot sustain it.Keep
total in the callee-saved register r4, and the first returned sum in the callee-saved register r5. Suppose the surrounding function has made an aligned stack frame with the local seven-halfword array at the current sp, occupying fourteen bytes in a sixteen-byte slot. One possible frame setup is push {r4,r5,r6,lr} followed by sub sp,sp,#16; the earlier code initializes total, regular, and special before this fragment. ldr r0, =regular @ assembler literal load of the global array address
movs r1, #7
bl sum16
movs r5, r0 @ first sum must survive the next call
add r0, sp, #0 @ current frame's local special array
movs r1, #7
bl sum16
muls r0, r5, r0 @ second sum times first sum
adds r4, r4, r0 @ update totalThe AAPCS32 permits each call to overwrite
r0–r3, r12, and condition flags, but requires preservation of r4–r8, r10, r11, and sp. Thus both r4 and r5 remain valid even if sum16 is replaced by another conforming implementation. bl changes the link processor register lr, so the enclosing function saves its own return address in its prologue. Its epilogue can use add sp,sp,#16 and pop {r4,r5,r6,pc}. The frame uses thirty-two bytes in total, preserving the required eight-byte stack pointer alignment at both calls.[ref]The two calls may be evaluated in this order. Assume the product and final addition fit the signed 32-bit result expected by the source program; unlike each individual seven-element sum, their product need not fit. The assembly language operations retain their low 32 bits if this assumption fails, whereas signed integer overflow in the C programming language has different semantics.
Let the stored bits be and let . The sign extension performed by
ldrsh keeps output bit equal to for , and sets every output bit to . Thus a nonnegative halfword gets sixteen leading zero bits, while a negative halfword gets sixteen leading one bits.Its signed 32-bit two's complement value isThe last expression is exactly the original signed 16-bit value. The equality uses the finite geometric series . In particular, simply inserting zero bits would be wrong for a negative halfword: its unsigned interpretation differs from its signed value by .
Use the AAPCS32 convention:
r0 holds the input address, r1 the length, and r0 receives the result. The following Thumb instruction set assembly language uses only scratch processor registers, so no callee-saved registers need saving. Assume the array is valid, halfword-aligned, and has nonnegative length; for the mathematical sum assume it fits a signed 32-bit two's complement integer..syntax unified
.thumb
.thumb_func
sum16:
movs r2, #0 @ accumulated sum
cmp r1, #0
ble .Ldone @ empty array; also returns 0 if n < 0
.Lloop:
movs r3, #0 @ Thumb signed load needs a register offset
ldrsh r3, [r0, r3] @ signed halfword at a; offset read before r3 changes
adds r2, r2, r3 @ include this signed value
adds r0, r0, #2 @ advance by one short, not one byte
subs r1, r1, #1 @ one fewer element remains
bne .Lloop
.Ldone:
movs r0, r2 @ result register
bx lr @ leaf routine: lr was not overwrittenAfter iterations, the loop invariant is that
r2 contains the first elements' sum, r0 points to element , and r1 is . The sign extension in ldrsh supplies the correct signed addend. One iteration preserves this loop invariant, and the decreasing remaining length proves algorithm termination. For the seven-element calls, the sum lies between and , so it fits. For longer arrays that overflow, these instructions compute the sum modulo ; that is not a claim about defined signed C programming language overflow behavior. The operand forms are those of the paper's reference sheet.[ref]Thumb 16-bit instruction set quick reference by Arm. Load: signed halfword; Add/Subtract; Branch
Use a hierarchical leading-zero counter. A block of bits returns a zero flag and low count bits : its count leading zeros result is the concatenation . Thus means that the block is entirely zero and ; otherwise and is its leading-zero count. A one-bit block needs just and no low count bits.
For a block of bits, run two such Boolean circuits on the upper and lower halves in parallel. Write their flags as and their low count bits as . SetThe last expression is a two-input multiplexer. When the upper half is nonzero, its count is already the answer and . When only the upper half is zero, supplies the contribution while the multiplexers supply the lower half's count. When both halves are zero, the answer is , representing . This special encoding avoids an adder on the critical path.
Each node adds constant circuit depth, even though it uses logic gates for its parallel multiplexers. HenceIndeed the internal-node work is bounded by a constant times , and the leaves add . Delay is and size is , counting fixed-fan-in logic gates and the usual wire fan-out model.
Apply comparator composition recursively in a balanced binary tree, with one-bit digital comparators at its leaves. For a power of two , the circuit size and circuit depth satisfyThere are leaves and internal nodes, so the circuit size is and the combinational delay is . Here each fixed-fan-in logic gate has bounded delay. For arbitrary , pad both inputs with leading zero bits to the next power of two, which is less than ; this preserves their unsigned interpretation and both bounds.
Split each input into its more and less significant -bit halves: and . Let the two digital comparators produce and . The more significant halves are equal exactly when . The comparator composition is thereforeImplement with a logical disjunction followed by a negation, then use two AND gates and two more logical disjunction logic gates. If , the difference has magnitude at least , whereas ; hence the more significant comparison decides the result. If , the lower comparison decides it. This proves correctness in every case using a constant number of extra logic gates.
For bits , use two negation logic gates and two AND gates:The two unequal bit pairs activate their respective output; the equal pairs activate neither. In particular, a digital comparator never produces .
First negate the implication, then move the negation through the existential quantifier and the logical conjunction:This is negation normal form, because each negation is immediately in front of an atomic predicate. The occurrence of remains free. Keeping also avoids assuming any additional order axioms for the relation symbol ; if it has its usual linear-order interpretation, that atom can instead be expressed as .
The occurrence of in lies under the quantifier . Directly inserting the term would capture its free : the result would make the inserted bound and change the intended dependence on the original free value. Therefore the term is not free for the literal substitution requested.
Perform capture-avoiding first-order substitution by first renaming bound variables to fresh names. Renaming the first binder to is necessary; renaming the second to is optional but makes the result especially clear. These renamings give the equivalent formula . Substituting only the free occurrences of now givesBoth and in the inserted term remain free variables. The original has scope only over its own disjunct and would not capture the inserted in the first disjunct; its optional renaming is not a necessary capture repair. This distinction avoids confusing reuse of a letter elsewhere with binding within the relevant scope.
Describe a branching vertex by the first-order logic sentenceand the existence of a sink by . The directed path has sinks but no branching vertex; the directed cycle has neither sinks nor branching vertices; the directed arborescence has a branching vertex. Thus the following three sentences distinguish the named structures in order:Here are abbreviations for the displayed formulas; replacing them gives sentences in the single-relation first-order signature . Explicitly, says that some vertex has no successor and that no vertex has two distinct successors. The truth table across the three structures is:
| Sentence | |||
|---|---|---|---|
The conditions distinguish these three finite structures; they are not claimed to characterize all directed paths, cycles or trees among arbitrary directed graphs. Only local out-degrees and the presence of a sink are needed, without quantifying over paths of unbounded length.
On the universe , interpret the first-order signature byThis assigns both constants, a total binary function, a unary relation and a binary relation, so it specifies a complete first-order structure. If and both hold, then , and hence , proving the consequent. If either premise fails, the implication is true. Thus the universally quantified implication holds for every pair of integers, nonvacuously for every pair of nonnegative integers. Distinct constant symbols need not denote distinct objects unless a separate axiom requires it.
Using first-order logic with equality, one suitable sentence isThe distinct witnesses give at least two solutions, and the universal clause excludes every third solution. All variables are bound, and the same equation variable is used in every solution predicate. This is an instance of a first-order definition of exactly finitely many witnesses.
Assume the logical conjunction temporarily, then eliminate the premise's logical disjunction by cases. A natural deduction proof, with each indented assumption delimiting its own subproof, is:
1. not P or not Q premise
2. | P and Q temporary assumption
3. | P and-elim-L, 2
4. | Q and-elim-R, 2
5. | | not P first disjunction case
6. | | false not-elim, 3,5
7. | | not Q second disjunction case
8. | | false not-elim, 4,7
9. | false or-elim, 1, cases 5-6 and 7-8
10. not (P and Q) not-intro, discharge 2-9Lines 5–6 and 7–8 are separate sibling subproofs, not one nested inside the other. Both derive the same contradiction under the common assumption on line 2. Logical disjunction elimination discharges the two case assumptions, and negation introduction then discharges the logical conjunction assumption. The sole undischarged premise is the required one. This proof uses only the supplied logical conjunction, logical disjunction and negation rules; no converse form of De Morgan's laws is being assumed as an extra rule.
Simultaneous propositional substitution givesLet . The first disjunct equals . By De Morgan's laws, implies , so absorption reduces that first disjunct to . The second disjunct is and is also absorbed by . ThereforeThe resulting Boolean function is false only when both and are true, providing a four-row truth table check.
Repeated use of yieldsThis logical disjunction is false exactly when are all true and is false. There is precisely one such Boolean valuation out of the assignments to the independent propositional variables. Thus the number of satisfying assignments is . This is the satisfying-assignment count for nested implications; the implication brackets associate to the right here.
Eliminate the logical implication and apply De Morgan's laws:This is disjunctive normal form: a logical disjunction of conjunctions of literals. It has four literal occurrences, namely , meeting the stated bound.
There are unlisted articles, also show them or only show them.
