{"id":"fc77c582-c7a9-4107-b780-452f13fe3486","arxiv_id":"1908.06211","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"A progress-aware extension of mixed-criticality scheduling that extends high-criticality tasks' normal-mode budgets at runtime checkpoints, improving low-criticality task service while preserving AMC deadline guarantees.","lead":"The authors present PAStime, a scheduler that measures a critical task's runtime progress at code checkpoints and extends its CPU budget when it lags, keeping the system out of emergency mode longer. It matters as a practical attempt to recover otherwise wasted worst-case CPU reserve and give it to less critical workloads like a video decoder.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 1's online schedulability test may use stale budgets for higher-priority tasks when checking lower-priority tasks, potentially approving unschedulable LO-mode extensions.","rationale":"The reader's weakest assumption (C(HI) is a true worst-case execution time) is a legitimate concern, explicitly acknowledged in Section 5.1 ('we assume that our derivation of LO- and HI-mode budgets are safe and correct for our experiments'). It should be flagged, but it is an external assurance assumption common to measurement-based systems work. My stress-test identifies a more internal, potentially more damaging concern: the online schedulability test, which is the mechanism that guarantees the extended LO-mode schedule remains feasible, is under-specified in Algorithm 1. As written, it can approve an extension that causes a lower-priority task to miss its deadline, as shown by the concrete 2-task counterexample. If the implementation has the same behavior, the paper's core claim that AMC-PAStime 'guarantees service to high-criticality tasks' and keeps LO-mode schedulable would be false even with a certified C(HI). The paper deserves credit for a real LITMUSRT implementation, public source code, and for exploring alternative progress metrics, which shows the qualitative benefit is not an artifact of one prediction model. However, the soundness of the online test is foundational and must be verified. Since the reader's verdict was already CONDITIONAL, and the test I propose can settle whether this concern lands, I recommend keeping the verdict CONDITIONAL: accept only after the source code is checked against the counterexample and the algorithm is corrected or clarified.","tokens_in":21429,"tokens_out":20066,"duration_ms":195373,"concrete_test":"Inspect the PAStime source code (publicly available at the URL in Section 4) in the LITMUSRT task_change_params callback. Verify whether the response-time calculation for lower-priority tasks (Equation 4) reads the newly requested extended budget C'_k(LO) for the delayed higher-priority task, or uses the old max_extended_budget until after the test returns. Then run the synthetic taskset: τ1 (HC) with C(LO)=3, C(HI)=6, T=6, and τ2 (LC) with C(LO)=1, T=5, both released together, and have τ1 request a LO-mode extension to 5 at its checkpoint. If the online test approves the extension and τ2 misses its deadline, the concern is confirmed; if the implementation correctly propagates the new budget and rejects the extension, the concern is resolved.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central safety claim rests on the online schedulability test in Algorithm 1 (Section 3.3). In the loop over the delayed task and lower-priority tasks, the pseudocode sets C'_i(LO) to the task's max_extended_budget for each loop iteration, and only for the delayed task τ_k does it incorporate the newly requested budget C_k(LO)+e. The update to τ_k.max_extended_budget occurs only after the loop (line 19). Therefore, when Equation 4 is solved for a lower-priority task, the interference term from higher-priority task τ_k may still use the old C_k(LO), not the proposed extended budget. This is not just a presentation issue: the text (Section 3.3) says 'the system uses the maximum extended budget of every high-criticality task,' but the pseudocode does not show the new value being made visible to lower-priority response-time calculations. Counterexample: let τ1 (HC, highest priority) have C1(LO)=3, T1=6, and τ2 (LC) have C2(LO)=1, T2=5. Original AMC LO response times are RLO_1=3≤6 and RLO_2=1+3=4≤5, so the taskset is schedulable. If τ1 is delayed at its checkpoint and requests e=2 (C'_1(LO)=5), Algorithm 1 as written computes τ2's response time using C1=3; with initial value RLO_2+e=6, the recurrence R=1+ceil(R/6)*3 converges to 4, so the extension is approved. But with the actual extended budget of 5, τ2's response becomes 1+5=6, missing its deadline of 5. This shows the online test can be unsound unless the implementation supplies the new C'_k(LO) to every lower-priority recurrence, which the pseudocode does not specify.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces PAStime, a progress-aware extension of Adaptive Mixed-Criticality (AMC) scheduling. A high-criticality (HC) task is instrumented with a checkpoint; at runtime the system measures the delay to that checkpoint relative to a profiled reference and tentatively extends the task's LO-mode budget to a predicted execution time, subject to an online response-time schedulability test. If the extension is approved, the system remains in LO-mode and low-criticality (LC) tasks continue to execute; if the extended budget is exhausted, the system falls back to HI-mode as in AMC. The authors implement AMC and AMC-PAStime in LITMUS-RT, using Darknet object classification, dlib object tracking, and an MPEG decoder, reporting 1.5--9x improvements in LC utilization and reduced numbers of mode switches while all HC tasks meet deadlines in their experiments. The paper also contributes an LLVM pass to automatically instrument checkpoints and a C library for checkpoint profiling and runtime announcement.","tokens_in":21815,"tokens_out":5532,"duration_ms":50758,"significance":"If the schedulability argument were sound, PAStime would be a valuable practical contribution to mixed-criticality scheduling: it converts observed average-case slack into better LC service without, in the authors' experiments, violating HC deadlines. The implementation work is a strength: it is the first AMC implementation in LITMUS-RT, the source code is publicly available, and the evaluation uses realistic applications with a full system implementation rather than simulation only. The automatic checkpoint-instrumentation pass is also useful. However, the central online schedulability test has a logical gap that, as written, can approve budget extensions that make lower-priority tasks miss their deadlines, and the safety of the mode-switch fallback depends on an unverified measurement-based C(HI) assumption. These issues affect the core claim that AMC-PAStime preserves schedulability while improving QoS.","major_comments":[{"comment":"Algorithm 1's online schedulability test does not propagate the newly requested extension C_k(LO)+e into the interference terms of Equations (4) and (5) for lower-priority tasks. When the loop reaches a task τ_i below τ_k, the pseudocode sets C'_i(LO) = τ_i.max_extended_budget (line 8) and only for τ_i = τ_k does it use C_k(LO)+e (line 10); the recurrence for τ_i then sums over higher-priority tasks using the stored (stale) budgets of those tasks, including τ_k. Thus the test can approve an extension that actually makes a lower-priority task miss its deadline. Concretely, take τ1 (HC, highest priority) with C1(LO)=3, T1=6, and τ2 (LC) with C2(LO)=1, T2=5; both tasks are schedulable under AMC-rtb. If τ1 is delayed by e=2 at its checkpoint, Algorithm 1 as written computes RLO-ext_2 using C1(LO)=3, obtains R=4≤5, and approves the extension, whereas with the actual C'_1(LO)=5 the recurrence gives R=1+5=6>5. This contradicts the statement in Section 3.3 that 'the system uses the maximum extended budget of every high-criticality task' for the online test; the algorithm must make the proposed budget visible to every lower-priority response-time computation, or provide a proof that the initialization RLO_i+e' is a safe substitute (the counterexample shows it is not). This is load-bearing for the paper's main claim that AMC-PAStime keeps the system in LO-mode without weakening schedulability.","section":"Section 3.4, Algorithm 1, and Equations (4)--(5)"},{"comment":"The HI-mode budget C(HI) is derived as the maximum observed execution time during profiling, and the paper explicitly assumes (Section 5.1) that 'our derivation of LO- and HI-mode budgets are safe and correct for our experiments.' A measurement-based maximum is not a certified WCET; if a job exceeds C(HI) due to an unseen input, cache state, or I/O, the enforcement timer described in Section 4.6 will fire only at the extended budget, and the high-criticality task can miss its deadline. The paper should either use a measurement-based WCET tool with a documented safety margin or state clearly that the deadline guarantee holds only under the (unverified) assumption that C(HI) is a true WCET. Separately, setting C(LO) to the average profiling time makes the plain-AMC baseline switch to HI-mode whenever a job exceeds the average, which may exaggerate the reported 1.5--9x utilization improvements; the overestimation study in Section 5.5 only partially addresses this, since the headline result uses the average-case baseline.","section":"Section 5.1, Table 2, and Section 4.6"}],"minor_comments":[{"comment":"The phrase 'the the extended LO-mode response time' contains a duplicated article; please fix.","section":"Section 3.3"},{"comment":"The text 'depletion of itc_extended time' should read 'depletion of its c_extended time.'","section":"Section 4.6"},{"comment":"The comment 'Initialize R*-ext i for Equation 4' should refer to Equation 5, since line 17 solves Equation 5; the equation references should be consistent throughout the pseudocode and surrounding text.","section":"Algorithm 1, line 16"},{"comment":"The condition for resetting max_extended_budget ('when a task has not requested a LO-mode budget extension for any of its dispatched jobs within the maximum period of all tasks') should be accompanied by a safety argument; as stated, it is not obvious that a still-active job that previously received an extension could not be forgotten, which would cause the online test to underestimate interference.","section":"Section 3.3"},{"comment":"The abstract claims utilization improvement of '1.5 to 9 times for 2 to 20 tasks,' but Figure 4 and the text report improvement factors of 3, 5, and 9 for 8, 14, and 20 tasks; please clarify where the 1.5 factor appears or adjust the claim.","section":"Section 5.3 and abstract"},{"comment":"The checkpoint location and the 500 ms / 2000 ms annotations are not visually tied to specific basic blocks; please add explicit labels for readability.","section":"Figure 1"}],"recommendation":"major_revision","confidential_remarks":"The paper is a solid systems contribution with a real implementation and reproducible artifacts, but the formal schedulability argument has a real gap in Algorithm 1 that directly affects the main claim. If the authors can fix the online test, re-run the experiments, and more carefully scope the WCET assumption, the paper could become acceptable for publication. The C(HI) issue is worth emphasizing in revision, since the experiments observe no overruns but do not establish a guarantee."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a real systems contribution, not a theory breakthrough. The idea—extend a high-criticality task's LO-mode budget at runtime based on checkpoint progress, subject to an online schedulability test—is new relative to the cited AMC extensions, and they back it with a working LITMUS-RT implementation, a LLVM pass for checkpoint placement, and public source code. That alone makes it worth refereeing.\n\nWhat it does well: Equations 4 and 5 are a sensible extension of AMC-rtb, and using max_extended_budget is a conservative approximation. The overhead story is also solid: they bound the online test at 120 iterations, measure about 130 microseconds worst-case, and show that the actual iteration counts stay well below the bound. They also try several progress metrics in Section 5.8, and the memory-access variant still improves low-criticality utilization, so the core effect is not an artifact of one hand-picked extrapolation factor. The prediction-accuracy plot in Figure 11 shows the model tracking actual runtimes.\n\nSoft spots: the experimental evidence for the 1.5–9x utilization claim is reported as averages without error bars, with ten runs of ten tasksets. That is enough to show a direction, but not enough to pin down the magnitude. The LO-mode budget is set to the average profiling time, which is favorable to PAStime; the overestimation experiments in Section 5.5 only partly compensate. Most importantly, the safety guarantee rests on C(HI) being a true WCET, and the paper only says none of the observed jobs exceeded it. That is an explicit assumption, not a proof. If a job ever exceeds C(HI), the enforcement timer cannot save the deadline. This is a common limitation in empirical systems papers, but it should be stated as a limitation more prominently than it is.\n\nOn the stress-test concern: I do not think the stale-budget worry is a real soundness bug. The text and the Table 1 example make clear that the new extended budget is meant to be used in all lower-priority response-time calculations, and the pseudocode can be read that way if C' is a per-task array updated in priority order. However, Algorithm 1 is under-specified—it does not say C' is an array, nor that max_extended_budget is updated before lower-priority recurrences. An implementer following line-by-line could use stale values. This should be fixed in a revision, not because the idea is wrong, but because the formal statement should match the intended semantics.\n\nWho it is for: people working on mixed-criticality scheduling, especially anyone who wants an implementable alternative to static slack allocation. I would send it to a serious referee; it deserves engagement, but the revision should make the WCET assumption and the online-test semantics explicit.","headline":"A genuine systems contribution with a working LITMUS-RT implementation, but the safety guarantee and the utilization numbers are both more conditional than the paper lets on.","tokens_in":22344,"tokens_out":8386,"would_cite":true,"duration_ms":85119,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Checking a high-criticality task's progress at a code checkpoint lets a mixed-criticality system keep serving low-criticality work without missing hard deadlines.","keywords":["progress-aware scheduling","mixed-criticality systems","adaptive mixed-criticality","WCET overestimation","checkpoint instrumentation","response-time analysis","real-time Linux","quality of service"],"falsifier":"Run the Darknet object classifier on a held-out set of images with deliberately adversarial cache and DRAM interference, and count jobs that exceed the profiled $C(HI)$ or miss their deadlines; any such job would falsify the claim that high-criticality tasks are always guaranteed.","tokens_in":21198,"feed_emoji":"⏱️","tokens_out":6978,"duration_ms":57363,"temperature":0.7,"pith_summary":"PAStime argues that a high-criticality real-time task's progress, measured by how long it takes to reach a checkpoint in its control-flow graph, can be used to extend its low-criticality-mode budget by a predicted amount without relaxing worst-case guarantees. The paper integrates this idea with Adaptive Mixed-Criticality (AMC) scheduling: when a delayed task's extended budget is approved by an online schedulability test, the system stays in LO-mode and keeps serving low-criticality tasks; when the extended budget is exhausted, the deadline-enforcement timer switches the system to HI-mode exactly as AMC would. In experiments with real-time Linux applications (object classification, object tracking, video decoding), the combined scheduler raises low-criticality average utilization by 1.5–9 times across 2–20 tasks and cuts mode switches by 28–55%, while no high-criticality job misses its deadline.","feed_headline":"Progress checkpoints give low-criticality tasks up to 9x more CPU time","feed_subtitle":"A checkpoint-based progress detector extends LO-mode budgets so low-criticality apps keep running without missing any hard deadline.","key_machinery":"The load-bearing mechanism is the checkpoint progress metric: a single marked point in the high-criticality task's control-flow graph where the task compares its actual CPU-time consumption to a profiled reference. The online schedulability test uses extended AMC response-time recurrences—$R^{LO\\text{-}ext}$ for LO-mode and $R^{*\\text{-}ext}$ for the mode-switch case—to check that the extended budget $C'(LO)$ keeps every affected task schedulable; a per-task $max\\_extended\\_budget$ makes the test safe across multiple jobs without storing per-job histories. The enforcement timer, set to the extended budget, provides the safety net that returns the system to AMC behavior if the prediction is wrong.","core_discovery":"The central discovery is that average-case execution time, which is normally wasted when budgets are set to worst-case values, can be recovered at runtime through checkpoint-based progress monitoring. A high-criticality task is profiled to obtain its LO-mode budget $C(LO)$, its HI-mode budget $C(HI)$, and a reference time to reach a checkpoint; at runtime the delay at the checkpoint $X\\%$ is extrapolated linearly to predict a new total execution time $C'(LO) = C(LO) + C(LO)\\times X/100$. If extending the task's LO-mode budget to $C'(LO)$ passes an online response-time schedulability test (using extended versions of the AMC recurrence equations), the budget is extended and the system remains in LO-mode. The enforcement mechanism remains AMC's: if the extended budget is exhausted, the system switches to HI-mode and the task gets its $C(HI)$ budget, so the high-criticality deadline guarantee is preserved. The paper shows experimentally that this schedule keeps low-criticality utilization 1.5–9 times higher than AMC for 2–20 tasks, reduces mode switches by 28–55%, and bounds the additional scheduling overhead to roughly 130 microseconds.","pith_inferences":["The paper does not explore it, but the same progress signal could drive power management (e.g., DVFS) or cloud scheduling, since a checkpoint gives a cheap online estimate of residual work.","The reliance on a single checkpoint makes placement crucial; a systematic method that chooses checkpoints based on the variance of remaining execution time could reduce the observed sensitivity to placement (0.1× vs 0.8× positions).","The $max\\_extended\\_budget$ memory, which keeps the online test safe, also makes the test conservative: a task that once requested a large extension retains it for future releases, so the method trades some potential utilization for safety; a windowed or credit-based memory could reclaim some of that slack.","One could test the prediction model on a broader family of high-criticality applications (e.g., control loops with input-dependent loops) where the linear extrapolation assumption may be less accurate; the memory-access model shows the framework already anticipates such cases."],"forward_implications":["Low-criticality tasks receive 1.5 to 9 times higher average utilization for tasksets of 2 to 20 tasks compared with plain AMC scheduling.","The number of transitions to HI-mode drops by 28–55% (35% in the base case), directly improving the QoS of video-decoding and other low-criticality work.","The online schedulability test has a bounded worst-case overhead: at most 120 response-time iterations and roughly 130 µs per budget-extension decision in the tested configurations.","The method remains safe when the prediction is wrong: an exhausted extended budget triggers the normal AMC mode switch, and high-criticality jobs still complete within $C(HI)$ in all experiments.","Alternative progress metrics, such as a memory-access-based progress ratio, also improve low-criticality utilization, showing the framework supports prediction models beyond linear time extrapolation."],"supporting_citations":[{"why":"Supplies the AMC scheduling policy, the HI/LO-mode task model, and the base response-time recurrence equations that PAStime extends.","marker":"[7]"},{"why":"Introduces the multi-criticality execution-time model that motivates separate LO- and HI-mode budgets.","marker":"[52]"},{"why":"Provides the priority-assignment algorithm used to order tasks in the system.","marker":"[2]"},{"why":"Provides the real-time Linux testbed in which the AMC and AMC-PAStime schedulers are implemented.","marker":"[10,14]"},{"why":"The high-criticality object-classification application used in the experiments and for profiling-based budget derivation.","marker":"[44]"},{"why":"The high-criticality object-tracking application used in the memory-progress experiments.","marker":"[16]"},{"why":"The low-criticality video-decoder application whose QoS (frames decoded, utilization) measures the benefit.","marker":"[20]"}],"fun_headline_variants":["Checkpoint delays extend budgets, giving low-criticality tasks up to 9x CPU","Checkpoint-based progress slashes mode switches by up to 55%","PAStime recovers wasted WCET headroom for low-criticality tasks","First AMC implementation with progress checkpoints on LITMUS-RT","Checkpoint delays forecast budgets, up to 9x more CPU for low-criticality"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The HI-mode budget $C(HI)$, measured as the maximum observed execution time during profiling, is a true worst-case budget for every high-criticality job; if any job exceeds it, the enforcement timer cannot guarantee the deadline.","fun_headline_variants_meta":{"raw":{"variants":["Checkpoint delays extend budgets, giving low-criticality tasks up to 9x CPU","Checkpoint-based progress slashes mode switches by up to 55%","PAStime recovers wasted WCET headroom for low-criticality tasks","First AMC implementation with progress checkpoints on LITMUS-RT","Checkpoint delays forecast budgets, up to 9x more CPU for low-criticality"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001251,"raw_usage":{"total_tokens":5179,"prompt_tokens":1044,"completion_tokens":4135,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":660,"completion_tokens_details":{"reasoning_tokens":4031}},"tokens_in":660,"tokens_out":4135,"duration_ms":27355,"temperature":1.0,"reasoning_tokens":4031,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:53:28.539977+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the Darknet object classifier on a held-out set of images with deliberately adversarial cache and DRAM interference, and count jobs that exceed the profiled $C(HI)$ or miss their deadlines; any such job would falsify the claim that high-criticality tasks are always guaranteed.","supporting_citations":[{"cited_title":"Response-time Analysis for Mixed Criticality Systems","cited_arxiv_id":null,"evidence_quote":"Supplies the AMC scheduling policy, the HI/LO-mode task model, and the base response-time recurrence equations that PAStime extends."},{"cited_title":"Preemptive Scheduling of Multi-criticality Systems with Varying Degrees of Execution Time Assurance","cited_arxiv_id":null,"evidence_quote":"Introduces the multi-criticality execution-time model that motivates separate LO- and HI-mode budgets."},{"cited_title":"On Priority Assignment in Fixed Priority Scheduling","cited_arxiv_id":null,"evidence_quote":"Provides the priority-assignment algorithm used to order tasks in the system."},{"cited_title":"Darknet: Open Source Neural Networks in C","cited_arxiv_id":null,"evidence_quote":"The high-criticality object-classification application used in the experiments and for profiling-based budget derivation."},{"cited_title":"dlib: Video Tracking","cited_arxiv_id":null,"evidence_quote":"The high-criticality object-tracking application used in the memory-progress experiments."},{"cited_title":"https://www.ffmpeg.org/, 2019","cited_arxiv_id":null,"evidence_quote":"The low-criticality video-decoder application whose QoS (frames decoded, utilization) measures the benefit."}],"review_version":1}