Supporting Time-Sensitive Application on a Commodity OS

Ashvin Goel, Luca Abeni, Charles Krasic, Jim Snow, Jonathan Walpole

Presented by Seonah Lee

Presentation Slides

Here is the link for the Power Point file.

Discussion Recap

• Many students were confused about the usage of periodic timers. In fact, the paper does not use a periodic timer, just simulate a periodic timer with one-shot timer and queues.
• Some students wondered the bound of preemption latency, but the instructor answered it was difficult to measure.
• Some students asked the concept of HLP (Highest Locking Priority Protocol), solving priority inversion problems.
• A student asked why the author did not use "Real-Time" instead of "Time-Sensitive" in the title, and the instructor explained the distinction between two terms.

List of Submitted Questions

[Timer]

1 Since the ideal number of soft checks depends on the fraction of checks that result in a soft timer firing, would it be useful, and would it be possible, to dynamically alter the number of soft checks based on the number of soft timers that fire?

2 I am a bit unclear on how a one-shot timer works. In a periodic timer, sleep queues are implemented with a tick of the periodic timer decrementing the sleep value and a process being scheduled when the sleep value is 0. But in the case of a one-shot timer, the memory frequency is used to decrement the timer value. But how are multiple process timers implemented? Does each process have a one-shot timer if it needs one?

3 In Performance, the paper shows overhead of firm timers in TSL as compared to standard Linux with 20 and 50 timer processes. What about if using a large amount of timer processes and firm timers still has lower overhead?

4 The experiments shows that pure hard timers have lower overhead in some cases and firm timers have lower overhead in other cases such as in standard Linux. The paper hasnt talked about any shortcomings of firm timer. In what aspects do you think firm timer might encounter shortcoming comparing with other related work?

5 The overhead induced by one-shot timers seems quite high. Is there not a fine-grained periodic timer that could be used instead?

6 "In figure 6 and 7, soft timers seem to be quite competitive when compared to the original linux finishing time. Why bother with firm timers when soft timers seem to be working so well? (Answer: see firm 500 in figure 7, perhaps this line of results should be explored some more) "

7 The authors state that periodic timers operate in O(1) while one-shot timers operate in O(logn), and use this in part to justify employing both. Is there any measurable performance benefit to this approach? Correspondingly, how many active one-shot timers should we expect at any given time?

8 How do you compare the soft timers in the solution and the soft timers proposed in paper 22 (efficient microsecond software timer…)?.

9 It's good to have such accurate timing for the CPU but for network applications we also rely on good timing for the network card right? Do our network cards support sufficient timing to make these firm timers useful? What about hardware that's not integrated into our mainboard, is it still accurate enough? Maybe it's not an issue because the network generates interrupts asynchronously.

10 I like how this paper provides a throttle between two methods of interrupt timing. Both methods have advantages in different types of applications so it's nice to see a way to choose easily which one you need.

11 Can we change the parameters (to switch between hard and soft timers) online depending on the ratio or other heuristic?

12 The firm timers used in the paper relies on periodic timers as a contingency measure of sorts. Is there any way to go one step further and do away with periodic timers, just using pure one-shot/soft timers to handle any possible event?

13 Building on the above question, what sort of impact do you forsee if it is indeed possible to do away with periodic timers, beyond the cited compatibility issues. Do you think the gain will outweigh the growing pains?

14 Can increasing the resolution of basic timing facilities actually break some programs that depend on them?

15 In how long of an interval would you say the authors need to monitor the behaviuor of an application in order to establish the value of the timer overshoot parameter? What do you think could be monitored, and how often would the timer overshoot parameter get updated?

16 Can the overshoot values in firm timers be calculated/adjusted on the fly by using a feedback mechanism? Or has any work been done on this direction.

[Scheduler]

17 In a system with a lot of interdependent processes, does the HLP protocol degenerate to uniform priority, that is, does (almost) every process end up having maximum priority? Even without going to that extreme, doesn't HLP somewhat defeat the purpose of having priorities?

18 TSL add high-precision timing facilities so that scheduling allocations do not depend on coarse-grain periodic clocks.Why not use a real-time scheduling algorithm as the only task scheduler?

19 Priority inversion is usually dealt with as described in the paper by promoting a low-priority process with a lock on a resource needed by a high priority process to the level of the high priority process. The paper states that for providing guaranteed latency times, the low priority process (X-server) has to be trusted when implementing the HLP protocol. This is the standard implementation I guess. But doesn't this seem a little prone to trouble for time sensitive applications?

20 Won't probabilistic modeling that considers application's requirements provide a better real-time scheduling?

21 How would you assign proportions to a given set of tasks in the beginning ? Is the assigned proportion static or is it dynamically adjusted as the task progresses ?

22 The proportion-period scheduling algorithm, or more precisely the measurement data that is used (cf. Section 4.2.2) isn't entirely clear to me. Can you provide a clearer description of the measured values.

23 "TSL uses a priority ceiling protocol called ""Highest Locking Priority Protocol"" (HLP) to solve priority inversion problems when multiple interdependent tasks are running at different priorities. Using HLP, a task that acquires a resource gets the highest priority of any task that can access that resource. How can the kernel easily know that 2 different processes are accessing the same resources ? "

24 Can we implement proportion-period scheduler in commodity OS? It seems to have hard to meet requirements ( assumes task times are fixed, reserves a percentage of the CPU)? Is is part of being realtime or can we support realtime system with less requirement?

25 Wouldn't it be nice if there would be a scheduler that could switch its scheduling policy between simplistic (fast and efficient policy) and "enhanced-priority" policy (that would be used for time sensitive applications)? How do you think one could do this?

26 As far as I know there are some scheduling techniques that measure the amount of I/O between the user and the application to identify the interactive multimedia applications and then give them higher priorities to maintain their real-time performance. How do you compare this scheduling method and the one used in the paper?

27 The value Umax (admission for proportion-period tasks) is set to 0.9. Are there any formal justification for this number? Does it have to be determined emprically based on the actual load mix?

[Preemption]

28 In the TSL implementation is the preemption latency bounded ?

29 Have recent modifications (like the O(1) scheduler) in Linux kernel 2.6.* eliminated the need for some of the fine-grained pre-emptibility modifications, or are there still points where specific yielding has to be done? (cf. Section 3.2)

30 Do the actively running drivers make a difference in establishing kernel preemptability, or can drivers generally be written to allow interrupts or yield control often to bound the latency for handling an interrupt?

31 Why are kernel critical sections so long by default? The approach taken in this paper to reduce the size of critical sections seems to be obvious so why don't we do that in practice? Are we violating protection on some part of the kernel we're not seeing? Are we breaking the kernel abstraction?

32 Would a microkernel be more responsive just by virtue of it having less responsbilities? Or do threads spend correspondingly more frequent and more lengthy intervals in microkernel critical sections?

33 How and why does kernel preemptability affect timing accuracy?

34 When authors discuss how to achieve fine-grained kernel preemptibility (Section 3.2) they mention two ways of doing it: the insertion of preemption points, and using mutexes or spinlocks. Does this mean that the first approach, the insertion of preeemption points, assumes that there are no mutexes or spinlocks implemented in the kernel?

35 To obtain the fine granularity on kernel preemptibility, spinlocks are only allowed to be released and reacquired on the strategic points in the long code sections that access shared data. Is there an automated way to assign these strategic points?Otherwise you might have to deal with the code you haven`t written, or have little clue about, or am I making the situation sound like more dramatic than as it is?

[General]

36 Could you give some information on other projects in relative fields ?

37 Does the following paper in some way provide a better approach towards the real-time approach? "Real-Time for the Real World" by John Regehr et al. School of Computing, University of Utah

38 What kind of bounds could we establish (other than empirically) on the latency of TSL linux for handling an interrupt?

39 "Is it possible to implement firm timers for an operating system running on non-Intel processors? "

40 "What is it that makes TSL unsuitable for running regular applications (non time-sensitive tasks) ? "

41 "I found unclear the method by which TSL calculates proportions for user applications. The paper mentions that an application-specific progress rate metric is used. If that is true, doesn't that go against the goal of TSL to run on a *general* commodity operating system ? Shouldn't a more general heuristic be applied instead to determine which real-time tasks should be given higher priorities ? "

42 How does this three-element solution deal with the scalability?. In case there are a large number of time intensive applications running, what do you think about the efficiency of the solution?.

43 I found one negative point of this paper is they did not provide evaluation on effect for standard application and evaluation seems not completed. If you were the author, how would you improve the evaluation part in this paper?

44 In the end, did they integrate separate ideas relating to time-sensitivity of Linux kernel?

45 I think that it would be very useful to compare the overhead of this new method to a real-time OS (such as RTlinux) in addition to the comparison to the standard Linux. Why didn't they do that? Can you think of any specific reason?

46 What type of real-time applications do we need to support on commodity OSs other than multimedia and interactive applications?

47 How does the performance of TSL compare to RTLinux? (Provided that ABI is not a major problem)

48 While a worst case performance in the order of us is sufficient for most commercial-level real-time application (such as playing video), is this sufficient for industrial application, which the real-time process is used for equipment control or navigation?

49 What happens if a real-time application is allowed to take over the system? Is it possible that kernel becomes irresponsive when executing some misbehaving real-time applications?

50 So along the same line of thinking, is it the #2 (finer grain preempting) and #3 (scheduling) code changes that made the most difference in performance improvements?