嵌入式系统导论-实验课-2-solution.pdfVIP

SMIE-141: Introduction to Embedded Systems Solution for Exercise 2 Dr.Kai Huang October 28, 2014 2.1 Model of Computation - Kahn Process Network 2.1.1 Similar to the Fair Merge mentioned in the lecture, here we consider again a merge process that merges data tokens from two input channels into one output channel, as shown in Figure 1. In this case, the merge process can peek but at most one data token at a time from inputs, which means the process can check the arrival and the status of the most recent incoming token. There are two different versions for this One Peek Merge process, the semantics of which are shown in Algorithm 1 and Algorithm 2, respectively. Algorithm 1 if L1[X], L2[Y] then del(X), del(Y), out[X,Y] else if L1[X], L2[φ] then del(X), out[X] else if L1[φ], L2[Y] then del(Y), out[Y] else if L1[φ], L2[φ] then no operation end if Algorithm 2 if L1[X] = L2[Y] then del(X), del(Y), out[X,Y] else if L1[X] L2[Y] then del(X), out[X] else if L1[X] L2[Y] then del(Y), out[Y] end if In Algorithm 2, we assume that the tokens X and Y have a built-in “serial number” and we 1 know that each channel produces increasing sequences of serial numbers (with unknown gaps though). ?Examine the determinacy of these two algorithms. Prove or disprove your conclusion. ?Examine the fairness of these two algorithms. Solution: Algorithm 1 is non-deterministic since the arrival order determines the output of the merge. But it is fair, since even if the sequences have different lengths, they are served on a first-come, first-serve basic. Formally: X = ([x1, x2], [φ]); X ′ = ([x1, x2], [y1]) F(X) = ([x1, x2]); F(X ′) = ([x1, y1, x2]) X?X ′ but F(X) 6?F(X ′) Algorithm 2 is deterministic since for any two input sequences (including knowledge of each token’s serial number), the output sequence is determined (increasing serial numbers). but it is unfair since we must request one token each for the comparison of the merge step, which unfairly starves the longer sequence (say L2), while w