Filter by type:

Sort by year

  1. MC-FLEX: Flexible Mixed-Criticality Real-Time Scheduling by Task-Level Mode Switch
  2. Jaewoo Lee and Jinkyu Lee
    IEEE Transactions on Computers (TC), Accepted
    SelectedJournal Paper

    Abstract

    Mixed-criticality (MC) scheduling becomes popular in real-time systems as it supports different criticality levels in a resource-efficient manner. Although it has been well established (i) how to guarantee MC schedulability offline, existing studies have paid less attention to achieve (ii) how to minimize deadline misses of low-criticality tasks at runtime; in addition, it has not matured yet how to address (ii) without compromising (i). In this paper, we propose MC-FLEX, which employs a task-level mode transition mechanism (as opposed to system-level one). MC-FLEX not only determines time instants at which each high-criticality task enters and exits the critical mode in a task level, but also selects time instants and target low-criticality task(s) to be dropped and resumed for each task-level mode switch of individual high-criticality tasks, yielding the achievement of both (i) and (ii). Via simulation results, we demonstrate that the proposed framework reduces the job deadline miss ratio of low-criticality tasks at runtime (by over 54.8% compared to the existing work), without compromising offline MC schedulability.


    Bibtex


    Journal Information

    ISSN: 0018-9340

  3. Necessary Feasibility Analysis for Mixed-Criticality Real-Time Embedded Systems
  4. Hoon Sung Chwa, Hyeongboo Baek, and Jinkyu Lee
    IEEE Transactions on Parallel and Distributed Systems (TPDS), Volume 33, Issue 7, pp. 1520-1537, July 2022 (Extended version of RTSS 2019)
    SelectedJournal Paper

    Abstract

    As multiple software components with different safety-criticality levels are integrated on a shared computing platform, a real-time embedded system becomes a mixed-criticality (MC) system, which should provide timing guarantees at all different levels of assurance to software components with different criticality levels. In the real-time systems community, the concept of an MC system is regarded as a promising, emerging solution to solve an inherent challenge of real-time systems: pessimistic reservation of computing resources, which yields a low resource-utilization for the sake of guaranteeing timing requirements. Since a timing guarantee should be provided before a real-time system starts to operate, its feasibility has been extensively studied for single-criticality systems; however, the same cannot be said for MC systems. In this paper, we develop necessary feasibility tests for MC real-time embedded systems, which is the first study that yields non-trivial results for MC necessary feasibility on both uniprocessor and multiprocessor platforms. To this end, we investigate characteristics of MC necessary feasibility conditions, and identify new challenges posed by the characteristics. By addressing those challenges, we develop two collective necessary feasibility tests and their simplified versions, which are able to exploit a tradeoff between capability in finding infeasible task sets and time-complexity. The simulation results demonstrate that the proposed tests find a number of additional infeasible task sets for both uniprocessor and multiprocessor platforms, which have been proven neither feasible nor infeasible by any existing studies.


    Bibtex


    Journal Information

    ISSN: 1045-9219

  5. LaLaRAND: Flexible Layer-by-Layer CPU/GPU Scheduling for Real-Time DNN Tasks
  6. Woosung Kang, Kilho Lee, Jinkyu Lee, Insik Shin, Hoon Sung Chwa
    The 42nd IEEE Real-Time Systems Symposium (RTSS), pp. -, Dortmund, Germany, December 2021 (Acceptance ratio: )
    SelectedConference Paper

    Abstract

    Deep neural networks (DNNs) have shown remarkable success in various machine-learning (ML) tasks useful for many safety-critical, real-time embedded systems. The foremost design goal for enabling DNN execution on real-time embedded systems is to provide worst-case timing guarantees with limited computing resources. Yet, the state-of-the-art ML frameworks hardly leverage heterogeneous computing resources (i.e., CPU, GPU) to improve the schedulability of real-time DNN tasks due to several factors, which include a coarse-grained resource allocation model (one-resource-per-task), the asymmetric nature of DNN execution on CPU and GPU, and lack of schedulabilityaware CPU/GPU allocation scheme. This paper presents, to the best of our knowledge, the first study of addressing the above three major barriers and examining their cooperative effect on schedulability improvement. In this paper, we propose LaLaRAND, a real-time layer-level DNN scheduling framework, that enables flexible CPU/GPU scheduling of individual DNN layers by tightly coupling CPU-friendly quantization with fine-grained CPU/GPU allocation schemes (one-resource-per-layer) while mitigating accuracy loss without compromising timing guarantees. We have implemented and evaluated LaLaRAND on top of the state-of-theart ML framework to demonstrate its effectiveness in making more DNN task sets schedulable by 56% and 80% over an existing approach and a baseline (vanilla PyTorch), respectively, with only up to -0.4% of performance (inference accuracy) difference.


    Bibtex


    Conference Information

  7. ML for RT: Priority Assignment Using Machine Learning
  8. Seunghoon Lee, Hyeongboo Baek, Honguk Woo, Kang G. Shin, and Jinkyu Lee
    The 27th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), pp. 118-130, Virtual, May 2021 (Acceptance ratio: 31/114=27.2%)
    SelectedConference Paper

    Abstract

    As machine learning (ML) has been proven effective in solving various problems, researchers in the real-time systems (RT) community have recently paid increasing attention to ML. While most of them focused on timing issues for ML applications (i.e., RT for ML), only a little has been done on the use ML for solving fundamental RT problems. In this paper, we aim at utilizing ML to solve a fundamental RT problem of priority assignment for global fixed-priority preemptive (gFP) scheduling on a multiprocessor platform. This problem is known to be challenging in the case of a large number (n) of tasks in a task set because exhaustive testing of all priority assignments (as many as n!) is intractable and existing heuristics cannot find a schedulable priority assignment, even if exists, for a number of task sets. We systematically incorporate RT domain knowledge into ML and develop an ML framework tailored to the problem, called PAL. First, raising and addressing technical issues including neural architecture selection and training sample regulation, we enable PAL to infer a schedulable priority assignment of a set of n tasks, by training PAL with same-size (i.e., with n tasks) samples each of whose schedulable priority assignment has already been identified. Second, considering the exhaustive testing of all priority assignments of each task set with large n makes it intractable to provide training samples to PAL, we derive inductive properties that can generate training samples with large n from those with small n, through empirical observation of PAL and mathematical analysis of the target gFP schedulability test. Finally, utilizing the inductive properties and additional techniques, we propose how to systematically implement PAL whose training sample generation process not only yields unbiased samples but also is tractable even for large n. Our experimental results demonstrate PAL covers a number of additional task sets, each of which has never been proven schedulable by any existing approaches for gFP.


    Bibtex


    Conference Information

  9. Non-Preemptive Real-Time Multiprocessor Scheduling Beyond Work-Conserving
  10. Hyeongboo Baek, Jaeheon Kwak, and Jinkyu Lee
    The 41st IEEE Real-Time Systems Symposium (RTSS), pp. 102-114, Virtual, December 2020 (Acceptance ratio: 28/140=20.0%)
    SelectedConference Paper

    Abstract

    Although essential for inherently non-preemptive tasks and favorable to tasks with large preemption/migration overheads, non-preemptive scheduling has not been thoroughly studied compared to preemptive scheduling. In particular, existing studies for non-preemptive scheduling could not effectively exploit being non-work-conserving (i.e., idling processor(s) intentionally), failing to achieve its full schedulability capability. In this paper, we propose the first non-preemptive scheduling framework that covers work-conserving-infeasible task sets (each of which is proven unschedulable by every work-conserving non-preemptive scheduling), without knowledge of future release patterns of tasks (i.e., called clairvoyance). To this end, we first discover the following principle: without clairvoyance, it is impossible to generate a feasible schedule for work-conserving-infeasible task sets on a uniprocessor platform. To make it possible on a multiprocessor platform, we design the NWC(N)-NP-* framework that systematicaly idles up to N processors so as to enable N designated tasks (that yield work-conserving-infeasibility) to be schedulable without clairvoyance, and derive important properties of the framework. We then target the framework associated with fixedpriority scheduling (as a prioritization policy), and develop its schedulability test by utilizing the framework's properties. Our simulation results demonstrate that the proposed framework successfully covers a number of work-conserving-infeasible task sets, none of which can be deemed schedulable by any previous approach.


    Bibtex


    Conference Information

  11. Power Guarantee for Electric Systems Using Real-Time Scheduling
  12. Eugene Kim, Youngmoon Lee, Liang He, Kang Shin, and Jinkyu Lee
    IEEE Transactions on Parallel and Distributed Systems (TPDS), Volume 31, Issue 8, pp. 1783-1798, August 2020 (Extended version of RTSS 2016)
    SelectedJournal Paper

    Abstract

    Modern electric systems, such as electric vehicles, mobile robots, nano satellites, and drones, require to support various power-demand operations for user applications and system maintenance. This, in turn, calls for advanced power management that jointly considers power demand by the operations and power supply from various sources, such as batteries, solar panels, and supercapacitors. In this article, we develop a power scheduling framework for a reliable energy storage system with multiple powersupply sources and multiple power-demand operations. Specifically, we develop offline power-supply guarantee analysis and online power management. The former provides an offline power-supply guarantee such that every power-demand operation completes its execution in time while the sum of power required by individual operations does not exceed the total power supplied by the entire energy storage system at any time; to this end, we develop a plain power-supply analysis as well as its improved version using real-time scheduling techniques. On the other hand, the latter efficiently utilizes the surplus power available at runtime for improving system performance; we propose two approaches, depending on whether future scheduling information of power-demanding tasks is available or not. For evaluation, we perform simulations to evaluate both the plain and improved analyses for offline power guarantee under various synthetic power-demand operations. In addition, we have built a simulation model and demonstrated that the proposed framework with the offline analysis and online management not only guarantees the required power-supply, but also enhances system performance by up to 56.49 percent.


    Bibtex


    Journal Information

    ISSN: 1045-9219

  13. Necessary Feasibility Analysis for Mixed-Criticality Task Systems on Uniprocessor
  14. Hoon Sung Chwa, Hyeongboo Baek and Jinkyu Lee
    The 40th IEEE Real-Time Systems Symposium (RTSS), pp. 446-457, Hong Kong, December 2019 (Acceptance ratio: 39/160=24.4%)
    (The conference has been cancelled, and the proceedings have been published in April 2020 via the IEEE Xplore Digital Library.)
    SelectedConference Paper

    Abstract

    While feasibility of timing guarantees has been extensively studied for single-criticality (SC) task systems, the same cannot be said true for mixed-criticality (MC) task systems. In particular, there exist only a few studies that address necessary feasibility conditions for MC task systems, and all of them have derived trivial results from existing SC studies that rely on simple demand-supply comparison. In this paper, we develop necessary feasibility tests for MC task systems on a uniprocessor platform, which is the first study that yields non-trivial results for MC necessary feasibility. To this end, we investigate characteristics of MC necessary feasibility conditions. Due to the existence of the mode change and consequences thereof, the characteristics pose new challenges that cannot be resolved by existing techniques for SC task systems, including how to calculate demand when the mode change occurs, how to determine the target sub-intervals for demand-supply comparison, how to derive an infeasibility condition from demand-supply comparisons with different possible mode change instants, how to select a scenario to specify the mode change instant without the target scheduling algorithm, and how to find infeasible task sets with reasonable time-complexity. By addressing those challenges, we develop a new necessary feasibility test and its simplified version. The simulation results demonstrate that the proposed tests find a number of additional infeasible task sets which have been proven neither feasible nor infeasible by any existing studies.


    Bibtex


    Conference Information

  15. Battery Aging Deceleration for Power-Consuming Real-Time Systems
  16. Jaeheon Kwak, Kilho Lee, Taehee Kim, Jinkyu Lee and Insik Shin
    The 40th IEEE Real-Time Systems Symposium (RTSS), pp. 353-365, Hong Kong, December 2019 (Acceptance ratio: 39/160=24.4%)
    (The conference has been cancelled, and the proceedings have been published in April 2020 via the IEEE Xplore Digital Library.)
    SelectedConference Paper

    Abstract

    Battery aging is one of the critical issues in battery-powered electric systems. However, this issue has not received much attention in the real-time systems community. In this paper, we present the first attempt to translate the problem of minimizing battery aging subject to timing requirements into a real-time scheduling problem, addressing the following issues. (i) Can scheduling make a systematic impact on battery aging? If so, which scheduling principles are favorable to minimizing battery aging? (ii) If there exists any, how can we build upon the scheduling principle to guarantee real-time requirements? For (i), we first illuminate the connection between task scheduling and battery aging minimization and then derive a principle for task scheduling from abstracting the complicated dynamics of battery aging, which is to minimize the variance of total power consumption over time. In addition, we implement a battery aging simulator and use it to verify the effectiveness of the proposed principle in minimizing battery aging and its impact on quantitative improvement. For (ii), we propose a scheduling framework that separates control for timing guarantees from that for battery aging minimization. Such a separation allows reducing the complexity significantly such that we can employ existing scheduling algorithm and schedulability analysis for real-time guarantee and tailor the proposed scheduling principle to decelerate battery aging without taking real-time guarantees into accounts. Our simulation results show that the proposed framework can extend the battery lifespan by up to 144.4%.


    Bibtex


    Conference Information

  17. MC-SDN: Supporting Mixed-Criticality Real-Time Communication Using Software-Defined Networking
  18. Kilho Lee, Minsu Kim, Taejune Park, Hoon Sung Chwa, Jinkyu Lee, Seungwon Shin, and Insik Shin
    IEEE Internet of Things Journal (IoT-J), Volume 6, Issue 4, pp. 6325-6344, August 2019 (Extended version of RTSS 2018)
    SelectedJournal Paper

    Abstract

    Despite recent advances, there still remain many problems to design reliable cyber-physical systems. One of the typical problems is to achieve a seemingly conflicting goal, which is to support timely delivery of real-time flows while improving resource efficiency. Recently, the concept of mixed-criticality (MC) has been widely accepted as useful in addressing the goal for real-time resource management. However, it has not been yet studied well for real-time communication. In this paper, we present the first approach to support MC flow scheduling on switched Ethernet networks leveraging an emerging network architecture, software-defined networking (SDN). Though SDN provides flexible and programmatic ways to control packet forwarding and scheduling, it yet raises several challenges to enable real-time MC flow scheduling on SDN, including: 1) how to handle (i.e., drop or re-prioritize) out-of-mode packets in the middle of the network when the criticality mode changes and 2) how the mode change affects end-to-end transmission delays. Addressing such challenges, we develop MC-SDN that supports real-time MC flow scheduling by extending SDN-enabled switches and OpenFlow protocols. It manages and schedules MC packets in different ways depending on the system criticality mode. To this end, we carefully design the mode change protocol that provides analytic mode change delay bound, and then resolve implementation issues for system architecture. For evaluation, we implement a prototype of MC-SDN on top of Open vSwitch, and integrate it into a real world network testbed as well as a 1/10 autonomous vehicle. Our extensive evaluations with the network testbed and vehicle deployment show that MC-SDN supports MC flow scheduling with minimal delays on forwarding rule updates and it brings a significant improvement in safety in a real-world application scenario.


    Bibtex


    Journal Information

    ISSN: 2327-4662

  19. JMC: Jitter-based Mixed-Criticality Scheduling for Distributed Real-Time Systems
  20. Kilho Lee, Minsu Kim, Hayeon Kim, Hoon Sung Chwa, Jaewoo Lee, Jinkyu Lee, and Insik Shin
    IEEE Internet of Things Journal (IoT-J), Volume 6, Issue 4, pp. 6310-6324, August 2019
    SelectedJournal Paper

    Abstract

    These days, the term of Internet of Things (IoT) becomes popular to interact and cooperate with individual smart objects, and one of the most critical challenges for IoT is to achieve efficient resource sharing as well as ensure safety-stringent timing constraints. To design such reliable real-time IoT, this paper focuses on the concept of mixed-criticality (MC) introduced to address the low processor utilization on traditional real-time systems. Although different worst-case execution time estimates depending on criticality are proven effective on processor scheduling, the MC concept is not yet mature on distributed systems (such as IoT), especially with end-to-end deadline guarantee. To the best of our knowledge, this paper presents the first attempt to apply the MC concept into interference (or jitter), which is a complicated source of pessimism when analyzing the schedulability of distributed systems. Our goal is to guarantee the end-to-end deadlines of high-criticality flows and minimize the deadline miss ratio of low-criticality flows in distributed systems. To achieve this goal, we introduce a jitter-based MC (JMC) scheduling framework, which supports node-level mode changes in distributed systems. We present an optimal feasibility condition (subject to given schedulability analysis) and two policies to determine jitter-threshold values to achieve the goal in different conditions. Via simulation results for randomly generated workloads, JMC outperforms an existing criticality-monotonic scheme in terms of achieving higher schedulability and fewer deadline misses.


    Bibtex


    Journal Information

    ISSN: 2327-4662

  21. Improved Schedulability Analysis of the Contention-Free Policy for Real-Time Systems
  22. Hyeongboo Baek and Jinkyu Lee
    Journal of Systems and Software (JSS), Volume 154, pp. 112-124, August 2019
    SelectedJournal Paper

    Abstract

    Real-time scheduling is the primary research for designing real-time systems whose correctness is determined by not only logical correctness but also timely execution. Real-time scheduling involves two fundamental issues: scheduling algorithm design and schedulability analysis development, which aim at developing a prioritization policy for real-time tasks and offering their timing guarantees at design time, respectively. Among the numerous scheduling algorithms and schedulability analysis for a multiprocessor platform, the contention-free (CF) policy and response-time analysis (RTA) have received considerable attention owing to their wide applicability and high analytical performance, respectively. Notwithstanding their effectiveness, it has been conjectured that it is not feasible to exploit the two techniques together. In this study, we propose a new schedulability analysis for the CF policy, referred to as pseudo-response time analysis (PRTA), which exploits a new notion of pseudo-response time effectively capturing the time instant at which the schedulability of a task is guaranteed under the CF policy. To demonstrate the effectiveness of PRTA, we apply PRTA to the existing earliest deadline first and rate monotonic scheduling algorithms employing the CF policy, and show that up to 46.4% and 18.3% schedulability performance improvement can be achieved, respectively, compared to those applying the existing schedulability analysis.


    Bibtex


    Journal Information

    ISSN: 0164-1212

  23. Adaptive Battery Diagnosis/Prognosis for Efficient Operation
  24. Eugene Kim, Bin Wu, Kang Shin, Jinkyu Lee, and Liang He
    The 10th ACM International Conference on Future Energy Systems (e-Energy), Phoenix, AZ, USA, June 2019
    SelectedConference Paper

    Abstract

    Since most modern mobile and electric vehicles are powered by Lithium-ion batteries, they need advanced power management that jointly considers battery performance and related electrochemical reactions. To meet these needs, we develop a charging diagnosis and prognosis system for effective battery control. We first examine the battery model that can capture electrochemical reactions and battery performance. Based on this model, we develop a charging diagnosis system that determines battery internal states and predicts their trend over operational cycles in various environments. Next, we propose a prognosis system to estimate battery's end-of-life (EOL) and determine optimal operating environments. Our in-depth experiments demonstrate that the proposed diagnosis and prognosis system estimates battery parameters and their degradation over operational cycles in various environments with high accuracy and without degrading user-perceived experience.


    Bibtex


    Conference Information

  25. Fault-Resilient Real-Time Communication Using Software-Defined Networking
  26. Kilho Lee, Minsu Kim, Hayeon Kim, Hoon Sung Chwa, Jinkyu Lee, and Insik Shin
    The 25th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), pp. 204-215, Montreal, Canada, April 2019 (Acceptance ratio: 30/116=25.9%)
    SelectedConference Paper

    Abstract

    The development of complex cyber-physical systems necessitates real-time networking with timing guarantees even in the presence of a link fault. Targeting firm real-time flows with the maximum allowable number of continuous deadline misses, this paper introduces FR-SDN, a fault-resilient SDN (Software-Defined Networking) framework that satisfies the timing requirements of firm real-time flows. To this end, we first investigate individual steps for path restoration: fault recognition, path recalculation, and path reassignment. We then design novel system architecture that reduces the delay of the fault recognition and path reassignment steps to potentially assign more time budget to the path recalculation step. Based on the calculation of tight upper-bounds on the delays in individual steps under the proposed system design, we derive a necessary feasibility condition that guarantees the timing requirements of firm real-time flows, and we calculate a time budget for the path recalculation step. Finally, we develop a multi-constrained path finding algorithm that can dynamically adjust the scope of flows to reroute according to the time budget. To the best of our knowledge, FR-SDN is the first study on adaptive path restoration for real-time flows, taking into account path restoration delay and fault tolerance constraints in case of link fault. We have implemented and evaluated FR-SDN on top of Open vSwitch to demonstrate its effectiveness, achieving an order of magnitude reduction in path restoration delay. In addition, we have deployed FR-SDN into a 1/10 scale autonomous vehicle and have shown, via an in-depth case study of adaptive cruise control, that FR-SDN is able to meet all fault tolerance requirements so that it can behave similarly as if there were no link failure.


    Bibtex


    Conference Information

  27. MC-SDN: Supporting Mixed-Criticality Scheduling on Switched-Ethernet Using Software-Defined Networking
  28. Kilho Lee, Taejune Park, Minsu Kim, Hoon Sung Chwa, Jinkyu Lee, Seungwon Shin, and Insik Shin
    The 39th IEEE Real-Time Systems Symposium (RTSS), pp. 288-299, Nashville, TN, USA, December 2018 (Acceptance ratio: 37/166=22.3%)
    SelectedConference Paper

    Abstract

    In this paper, we present the first approach to support mixed-criticality (MC) flow scheduling on switched Ethernet networks leveraging an emerging network architecture, Software-Defined Networking (SDN). Though SDN provides flexible and programmatic ways to control packet forwarding and scheduling, it yet raises several challenges to enable real-time MC flow scheduling on SDN, including i) how to handle (i.e., drop or reprioritize) out-of-mode packets in the middle of the network when the criticality mode changes, and ii) how the mode change affects end-to-end transmission delays. Addressing such challenges, we develop MC-SDN that supports real-time MC flow scheduling by extending SDN-enabled switches and OpenFlow protocols. It manages and schedules MC packets in different ways depending on the system criticality mode. To this end, we carefully design the mode change protocol that provides analytic mode change delay bound, and then resolve implementation issues for system architecture. For evaluation, we implement a prototype of MC-SDN on top of Open vSwitch, and integrate it into a real world network testbed as well as a 1/10 autonomous vehicle. Our extensive evaluations with the network testbed and vehicle deployment show that MC-SDN supports MC flow scheduling with minimal delays on forwarding rule updates and it brings a significant improvement in safety in a real-world application scenario.


    Bibtex


    Conference Information

  29. Non-Preemptive Scheduling for Mixed-Criticality Real-Time Multiprocessor Systems
  30. Hyeongboo Baek, Namyong Jung, Hoon Sung Chwa, Insik Shin, and Jinkyu Lee
    IEEE Transactions on Parallel and Distributed Systems (TPDS), Volume 29, Issue 8, pp. 1766-1779, August 2018
    SelectedJournal Paper

    Abstract

    Real-time scheduling for Mixed-Criticality (MC) systems has received a growing attention as real-time embedded systems accommodate various tasks with different levels of criticality. While many studies have addressed how to guarantee timing requirements for MC systems with uniprocessor and multiprocessors, most of them have focused on supporting preemptive tasks. On the other hand, there have been few studies to address non-preemptive scheduling especially for MC multiprocessor platforms, in which the jobs under execution cannot be preempted by other jobs. In this paper, we develop schedulability tests for non-preemptive scheduling, which is the first attempt for MC multiprocessor systems. To this end, we first generalize an existing NP-EDF (Non-Preemptive Earliest Deadline First) schedulability test developed for single-criticality multiprocessor systems, towards for MC multiprocessor systems. For the generalization, we introduce new timing guarantee techniques for the system transition between two different criticalities, which is one of the key features in MC systems. We next extend the proposed NP-EDF schedulability test towards NP-EDFVD (NP-EDF with Virtual Deadlines) that is specialized for MC systems, and pose a virtual deadline assignment problem. We develop an optimal virtual deadline assignment policy using a control knob of the system-level deadline-reduction parameter and then a suboptimal one for the task-level parameter. Our simulation results demonstrate that the NP-EDFVD schedulability test with the proposed virtual deadline assignment policies finds a number of additional schedulable task sets, which are not schedulable by the NP-EDF schedulability test.


    Bibtex


    Journal Information

    ISSN: 1045-9219

  31. Closing the Gap between Stability and Schedulability: A New Task Model for Cyber-Physical Systems
  32. Hoon Sung Chwa, Kang G. Shin and Jinkyu Lee
    The 24th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), pp. 327-337, Porto, Portugal, April 2018
    SelectedConference Paper

    Abstract

    A cyber-physical system (CPS) usually contains multiple control loops, each responsible for controlling different physical subprocesses, that run simultaneously upon a shared platform. The foremost design goal for CPSes is to guarantee system stability and control quality with limited cyber resources. We show, via an in-depth case study, that two inter-related design parameters - sampling period and consecutive control update misses - play a key role in determining stability and control performance. However, most CPS designs, such as control-schedule co-design and fault-tolerant scheduling, focus on either sampling period or control update misses alone, but not both. To remedy this problem, we propose a new CPS task model that captures both system stability and control performance in terms of sampling period and maximum allowable number of consecutive control update misses. To demonstrate the utility and power of this model, we develop two new scheduling mechanisms, offline parameter assignment and online state-aware scheduling. The former determines the sampling period and the maximum allowable number of consecutive job deadline misses for each task while preserving system stability. The latter then generates a schedule by exploiting the state of each physical subprocess to manage job deadline misses so as to improve the overall system performance without compromising system stability. Our in-depth evaluation results demonstrate that the proposed task model and the corresponding scheduling algorithm not only enable the efficient use of computing resource, but also significantly improve control performance without compromising system stability.


    Bibtex


    Conference Information

  33. Physical-State-Aware Dynamic Slack Management for Mixed-Criticality Systems
  34. Hoon Sung Chwa, Kang G. Shin, Hyeongboo Baek and Jinkyu Lee
    The 24th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), pp. 129-139, Porto, Portugal, April 2018
    SelectedConference Paper

    Abstract

    Safety-critical cyber-physical systems like autonomous cars require not only different levels of assurance, but also close interactions with dynamically-changing physical environments. While the former has been studied extensively by exploiting the notion of mixed-criticality (MC) systems, the latter has not, especially in conjunction with MC systems. To fill this important gap, we conduct an in-depth case study, demonstrating the importance of capturing current physical states, and introduce the problem of achieving efficient utilization of computing resources under varying physical states in MC systems. To solve this problem, we first develop a physical-state-aware MC task model, which is a generalization of the existing basic MC task model. We then propose new slack concepts tailored to the new task model, which enable efficient utilization of computing resources for MC systems. Finally, we develop a physical-state-aware dynamic slack management framework and demonstrate how to utilize the new MC task model and slack concepts towards efficient system utilization. We show, via a case study and in-depth evaluation, that the proposed framework makes 20x less low-criticality jobs dropped over a popular MC scheduling algorithm without compromising the MC-schedulability requirements.


    Bibtex


    Conference Information

  35. Multi-Level Contention-Free Policy for Real-Time Multiprocessor Scheduling
  36. Hyeongboo Baek, Jinkyu Lee, and Insik Shin
    Journal of Systems and Software (JSS), Volume 137, pp. 36-49, March 2018
    SelectedJournal Paper

    Abstract

    The contention-free policy has received attention in real-time multiprocessor scheduling owing to its wide applicability and significant improvement in offline schedulability guarantees. Utilizing the notion of contention-free slots in which the number of active jobs is smaller than or equal to the number of processors, the policy improves the schedulability by offloading executions in contending time slots to contention-free ones. In this paper, we propose the multi-level contention-free policy by exploiting a new, generalized notion of multi-level contention-free slots. In a case study, we present how the multi-level contention-free policy is applied to EDF (Earliest Deadline First) scheduling and develop a schedulability test for EDF that adopts the new policy. Our evaluation results demonstrate that the multi-level contention-free policy significantly improves the schedulability by up to 4188% and 127%, compared to vanilla EDF and EDF adopting the existing contention-free policy, respectively.


    Bibtex


    Journal Information

    ISSN: 0164-1212

  37. Beyond Implicit-Deadline Optimality: A Multiprocessor Scheduling Framework for Constrained-Deadline Tasks
  38. Hyeongboo Baek, Hoon Sung Chwa and Jinkyu Lee
    The 38th IEEE Real-Time Systems Symposium (RTSS), pp. 331-342, Paris, France, December 2017 (Acceptance ratio: 31/131=23.7%)
    SelectedConference Paper

    Abstract

    In the real-time systems community, many studies have addressed how to efficiently utilize a multiprocessor platform so as to accommodate as many periodic/sporadic real-time tasks as possible without violating any timing constraints. The scheduling theory has sufficiently matured for a set of implicit-deadline tasks (the relative deadline equal to the period), yielding a class of optimal scheduling algorithms. However, the same does not hold for a set of constrained-deadline tasks (the relative deadline no larger than the period) in that those task sets have been fully covered by neither existing implicit-deadline optimal scheduling algorithms nor heuristic scheduling algorithms., In this paper, we propose a scheduling framework that not only takes advantage of both existing implicit-deadline optimal and heuristic algorithms, but also surpasses both in finding schedulable constrained-deadline task sets. The proposed framework logically divides a given task set into the higher- and lower-priority classes and schedules the classes using an implicit-deadline optimal algorithm and a heuristic algorithm, respectively. Then, while the proposed framework guarantees schedulability of tasks in the higher-priority class by the target implicit-deadline optimal algorithm, we need to address the following technical issues for enabling tasks in the lower-priority class to efficiently reclaim remaining processor capacity while guaranteeing their schedulability: (i) division of a given task set into the two classes, (ii) selection/development of scheduling algorithms for the two classes, and (iii) development of a schedulability test for the framework with given (i) and (ii). We present a general case showing how to address (i)-(iii), and then a specific case addressing how to further improve schedulability by utilizing characteristics of the specific case. Our simulation results demonstrate that the proposed framework outperforms all existing scheduling algorithms in covering schedulable tasksets; in particular, if we focus on task sets with the system densitylarger than the number of processors, the framework finds up to446.3% additional schedulable task sets, compared to task setscovered by at least one of existing scheduling algorithms.


    Bibtex


    Conference Information

  39. Improved Schedulability Analysis Using Carry-in Limitation for Non-Preemptive Fixed-Priority Multiprocessor Scheduling
  40. Jinkyu Lee
    IEEE Transactions on Computers (TC), Volume 66, Issue 10, pp. 1816-1823, October 2017
    SelectedJournal Paper

    Abstract

    A time instant is said to be a critical instant for a task, if the task's arrival at the instant makes the duration between the task's arrival and completion the longest. Critical instants for a task, once revealed, make it possible to check the task's schedulability by investigating situations associated with the critical instants. This potentially results in efficient and tight schedulability tests, which is important in real-time systems. For example, existing studies have discovered critical instants under preemptive fixed-priority scheduling (P-FP), which limit interference from carry-in jobs, yielding the state-of-the-art schedulability tests on both uniprocessor and multiprocessor platforms. However, studies on schedulability tests associated with critical instants have not matured yet for non-preemptive scheduling, especially on a multiprocessor platform. In this paper, we find necessary conditions for critical instants for non-preemptive global fixed-priority scheduling (NP-FP) on a multiprocessor platform, and develop a new schedulability test that takes advantage of the finding for reducing carry-in jobs' interference. Evaluation results show that the proposed schedulability test finds up to 14.3 percent additional task sets schedulable by NP-FP, which are not deemed schedulable by the state-of-theart NP-FP schedulability test.


    Bibtex


    Journal Information

    ISSN: 0018-9340

  41. Global EDF Schedulability Analysis for Parallel Tasks on Multi-core Platforms
  42. Hoon Sung Chwa, Jinkyu Lee, Jiyeon Lee, Kiew-My Phan, Arvind Easwaran, and Insik Shin
    IEEE Transactions on Parallel and Distributed Systems (TPDS), Volume 28, Issue 5, pp. 1331-1345, May 2017 (Extended version of ECRTS 2013)
    SelectedJournal Paper

    Abstract

    With the widespread adoption of multi-core architectures, it is becoming more important to develop software in ways that takes advantage of such parallel architectures. This particularly entails a shift in programming paradigms towards fine-grained, thread-parallel computing. Many parallel programming models have been introduced for targeting such intra-task thread-level parallelism. However, most successful results on traditional multi-core real-time scheduling are focused on sequential programming models. For example, thread-level parallelism is not properly captured into the concept of interference, which is key to many schedulability analysis techniques. Thereby, most interference-based analysis techniques are not directly applicable to parallel programming models. Motivated by this, we extend the notion of interference to capture thread-level parallelism more accurately. We then leverage the proposed notion of parallelism-aware interference to derive efficient EDF schedulability tests that are directly applicable to parallel task models, including DAG models, on multi-core platforms, without knowing an optimal schedule. Our evaluation results indicate that the proposed analysis significantly advances the state-of-the-art in global EDF schedulability analysis for parallel tasks. In particular, we identify that our proposed schedulability tests are adaptive to different degrees of thread-level parallelism and scalable to the number of processors, resulting in substantial improvement of schedulability for parallel tasks on multi-core platforms.


    Bibtex


    Journal Information

    ISSN: 1045-9219

  43. Development and Use of a New Control Task Model for Cyber-Physical Systems: a Real-Time Scheduling Perspective
  44. Jinkyu Lee and Kang G. Shin
    Journal of Systems and Software (JSS), Volume 126, pp. 45-56, April 2017
    SelectedJournal Paper

    Abstract

    In a typical cyber-physical system (CPS), the cyber/computation subsystem controls the physical subsystem, and therefore the computer society has recently paid considerable attention to CPS research. To keep such a CPS stable, feedback control with periodic computation tasks has been widely used, and its theoretical guarantee of stability has been made with periodic real-time task models that enforce strict periodic control updates. However, some control update misses are usually allowed (e.g., via system over-design) in certain physical subsystem states (PSSes) without causing system instability, and the resources required for strict periodic control updates can thus be reduced or used for other purposes, achieving efficient controls for the entire CPS in terms of the operational cost, such as fuel consumption or tracking accuracy. In this paper, we propose a new periodic, fault-tolerant CPS task model, which not only expresses efficiency and stability of the underlying physical subsystem, but also generalizes existing periodic real-time task models, by capturing a tolerable number of control update misses in different PSSes. To demonstrate the utility of this model, we develop a new scheduling mechanism that prioritizes jobs (i.e., periodic invocations) of a set of tasks not only by the nature of each task, but also by the number of consecutive prior job deadline misses. Based on its analysis in terms of stability and efficiency, we also propose a priority-assignment policy that lowers the system operation cost without compromising stability. Our in-depth analysis and simulation results show that the scheduling mechanism and its analysis, as well as the priority-assignment policy under the proposed model not only generalize the existing periodic real-time task models, but also significantly lower the system operation cost without losing stability.


    Bibtex


    Journal Information

    ISSN: 0164-1212

  45. Time-Reversibility for Real-Time Scheduling on Multiprocessor Systems
  46. Jinkyu Lee
    IEEE Transactions on Parallel and Distributed Systems (TPDS), Volume 28, Issue 1, pp. 230-243, January 2017 (Extended version of RTSS 2014)
    SelectedJournal Paper

    Abstract

    In a typical cyber-physical system (CPS), the cyber/computation subsystem controls the physical subsystem, and therefore the computer society has recently paid considerable attention to CPS research. To keep such a CPS stable, feedback control with periodic computation tasks has been widely used, and its theoretical guarantee of stability has been made with periodic real-time task models that enforce strict periodic control updates. However, some control update misses are usually allowed (e.g., via system over-design) in certain physical subsystem states (PSSes) without causing system instability, and the resources required for strict periodic control updates can thus be reduced or used for other purposes, achieving efficient controls for the entire CPS in terms of the operational cost, such as fuel consumption or tracking accuracy. In this paper, we propose a new periodic, fault-tolerant CPS task model, which not only expresses efficiency and stability of the underlying physical subsystem, but also generalizes existing periodic real-time task models, by capturing a tolerable number of control update misses in different PSSes. To demonstrate the utility of this model, we develop a new scheduling mechanism that prioritizes jobs (i.e., periodic invocations) of a set of tasks not only by the nature of each task, but also by the number of consecutive prior job deadline misses. Based on its analysis in terms of stability and efficiency, we also propose a priority-assignment policy that lowers the system operation cost without compromising stability. Our in-depth analysis and simulation results show that the scheduling mechanism and its analysis, as well as the priority-assignment policy under the proposed model not only generalize the existing periodic real-time task models, but also significantly lower the system operation cost without losing stability.


    Bibtex


    Journal Information

    ISSN: 1045-9219

  47. Offline Guarantee and Online Management of Power Demand and Supply in Cyber-Physical Systems
  48. Eugene Kim, Liang He, Youngmoon Lee, Kang G. Shin and Jinkyu Lee
    The 37th IEEE Real-Time Systems Symposium (RTSS), pp. 89-98, Porto, Portugal, December 2016 (Cyber-Physical Systems Track) (Acceptance ratio: 32/137=23.4%)
    SelectedConference Paper

    Abstract

    In a typical cyber-physical system (CPS), the cyber/computation subsystem controls the physical subsystem, and therefore the computer society has recently paid considerable attention to CPS research. To keep such a CPS stable, feedback control with periodic computation tasks has been widely used, and its theoretical guarantee of stability has been made with periodic real-time task models that enforce strict periodic control updates. However, some control update misses are usually allowed (e.g., via system over-design) in certain physical subsystem states (PSSes) without causing system instability, and the resources required for strict periodic control updates can thus be reduced or used for other purposes, achieving efficient controls for the entire CPS in terms of the operational cost, such as fuel consumption or tracking accuracy. In this paper, we propose a new periodic, fault-tolerant CPS task model, which not only expresses efficiency and stability of the underlying physical subsystem, but also generalizes existing periodic real-time task models, by capturing a tolerable number of control update misses in different PSSes. To demonstrate the utility of this model, we develop a new scheduling mechanism that prioritizes jobs (i.e., periodic invocations) of a set of tasks not only by the nature of each task, but also by the number of consecutive prior job deadline misses. Based on its analysis in terms of stability and efficiency, we also propose a priority-assignment policy that lowers the system operation cost without compromising stability. Our in-depth analysis and simulation results show that the scheduling mechanism and its analysis, as well as the priority-assignment policy under the proposed model not only generalize the existing periodic real-time task models, but also significantly lower the system operation cost without losing stability.


    Bibtex


    Conference Information

  49. Thread-Level Priority Assignment in Global Multiprocessor Scheduling for DAG Tasks
  50. Jiyeon Lee, Hoon Sung Chwa, Jinkyu Lee, and Insik Shin
    Journal of Systems and Software (JSS), Volume 113, pp. 246-256, March 2016
    SelectedJournal Paper

    Abstract

    The advent of multi- and many-core processors offers enormous performance potential for parallel tasks that exhibit sufficient intra-task thread-level parallelism. With a growth of novel parallel programming models (e.g., OpenMP, MapReduce), scheduling parallel tasks in the real-time context has received an increasing attention in the recent past. While most studies focused on schedulability analysis under some well-known scheduling algorithms designed for sequential tasks, little work has been introduced to design new scheduling policies that accommodate the features of parallel tasks, such as their multi-threaded structure. Motivated by this, we refine real-time scheduling algorithm categories according to the basic unit of scheduling and propose a new priority assignment method for global task-wide thread-level fixed-priority scheduling of parallel task systems. Our evaluation results show that a finer-grained, thread-level fixed-priority assignment, when properly assigned, significantly improves schedulability, compared to a coarser-grained, task-level assignment.


    Bibtex


    Journal Information

    ISSN: 0164-1212

  51. Optimal Real-Time Scheduling on Two-Type Heterogeneous Multicore Platforms
  52. Hoon Sung Chwa, Jaebaek Seo, Jinkyu Lee, and Insik Shin
    The 36th IEEE Real-Time Systems Symposium (RTSS), pp. 119-129, San Antonio, TX, USA, December 2015 (Acceptance ratio: 34/151=22.5%)
    SelectedConference Paper

    Abstract

    Motivated by the cutting-edge two-type heterogeneous multicore chips, such as ARM's big.LITTLE, that offer a practical support for migration, this paper studies the global (or fully-migrative) approach to two-type heterogeneous multicore scheduling. Our goal is to design an optimal fully-migrative scheduling framework. To achieve this goal in an efficient and simple manner, we break the scheduling problem into two subproblems: workload assignment and schedule generation. We propose a per-cluster workload assignment algorithm, called Hetero-Split, that determines the fractions of workload of each task to be assigned to both clusters without losing feasibility with the complexity of O(n log n), where n is the number of tasks. Furthermore, it provides a couple of important properties (e.g., a dual property) that help to generate an optimal schedule efficiently. We also derive scheduling guidelines to design optimal schedulers for two-type heterogeneous multicore platforms, called Hetero-Fair. By tightly coupling the solutions of Hetero-Split and Hetero-Fair, we develop the first optimal two-type heterogeneous multicore scheduling algorithm, called Hetero-Wrap, that has the same complexity (O(n)) as in the identical multicore case. Finally, concerning a practical point of view, we derive the first bounds on the numbers of intra-and inter-cluster migrations under two-type heterogeneous multicore scheduling, respectively.


    Bibtex


    Conference Information

  53. Modeling and Real-Time Scheduling of Large-Scale Batteries for Maximizing Performance
  54. Eugene Kim, Kang G. Shin and Jinkyu Lee
    The 36th IEEE Real-Time Systems Symposium (RTSS), pp. 33-42, San Antonio, TX, USA, December 2015 (Cyber-Physical Systems Track) (Acceptance ratio: 34/151=22.5%)
    SelectedConference Pape

    Abstract

    Modern electric vehicles are equipped with an advanced battery management system, responsible for providing the necessary power efficiently from batteries to electric motors while maintaining the batteries within an operational condition. Because discharge-rate and temperature of batteries affect their health and efficiency significantly, batteries are managed to mitigate their discharge and thermal stresses. In this paper, we develop a real-time, efficient integrated management system for discharge-rate and temperature of batteries. To achieve this objective, we first construct a prognosis system predicting the likely states of batteries' capacity and capability. Based on prognostic estimates of the impact of temperature and discharge-rate on the performance, we solve an optimization problem to search for efficient discharging and cooling scheduling. Our experimentation and simulation demonstrate that the proposed management enhances system performance up to 85.3%.


    Bibtex


    Conference Information

  55. Composition of Schedulability Analyses for Real-Time Multiprocessor Systems
  56. Jinkyu Lee, Kang G. Shin, Insik Shin and Arvind Easwaran
    IEEE Transactions on Computers (TC), Volume 64, Issue 4, pp. 941-954, April 2015
    SelectedJournal Paper

    Abstract

    With increasing popularity and deployment of multi-core chips in embedded systems, a number of real-time multiprocessor scheduling algorithms have been proposed along with their schedulability analyses (or tests), which verify temporal correctness under a specific algorithm. Each of these algorithms often comes with several different schedulability tests, especially when it is difficult to find exact schedulability tests for the algorithm. Such tests usually find different task sets deemed schedulable even under the same scheduling algorithm. While these different tests have been compared with each other in terms of schedulability performance, little has been done on how to combine such different tests to improve the overall schedulability of a given scheduling algorithm beyond a simple union of their individual schedulability. Motivated by this, we propose a composition theory for schedulability tests with two new methods. The first method composes task-level timing guarantees derived from different schedulability tests, and the second one derives system-level schedulability results from a single schedulability test. The unified composition theory with these two methods then utilizes existing schedulability tests effectively so as to cover additional schedulable task sets. The proposed composition theory is shown to be applicable to most existing preemptive/non-preemptive scheduling algorithms. We also present three case-studies, demonstrating how and by how much the theory can improve schedulability by composing existing schedulability tests. Our evaluation results also show that the composition theory makes it possible to cover up to 181.7 percent additional schedulable task sets for preemptive fpEDF, preemptive EDF and non-preemptive EDF scheduling algorithms beyond their existing tests.


    Bibtex


    Journal Information

    ISSN: 0018-9340

  57. Capturing Urgency and Parallelism Using Quasi-Deadlines for Real-Time Multiprocessor Scheduling
  58. Hoon Sung Chwa, Hyoungbu Back, Jinkyu Lee, Kieu-My Phan and Insik Shin
    Journal of Systems and Software (JSS), Volume 101, pp. 15-29, March 2015
    SelectedJournal Paper

    Abstract

    Recent trends toward multi-core architectures in real-time embedded systems pose challenges in designing efficient real-time multiprocessor scheduling algorithms. We believe that it is important to take into consideration both timing constraints of tasks (urgency) and parallelism restrictions of multiprocessor platforms (parallelism) together when designing scheduling algorithms. Motivated by this, we define the quasi-deadline of a job as a weighted sum of its absolute deadline (capturing urgency) and its worst case execution time (capturing parallelism) with a system-level control knob to balance urgency and parallelism effectively. Using the quasi-deadline to prioritize jobs, we propose two new scheduling algorithms, called EQDF (earliest quasi-deadline first) and EQDZL (earliest quasi-deadline until zero laxity), that are categorized into job-level fixed-priority (JFP) scheduling and job-level dynamic-priority (JDP) scheduling, respectively. This paper provides a new schedulability analysis for EQDF/EQDZL scheduling and addresses the problem of priority assignment under EQDF/EQDZL by determining a right value of the system-level control knob. It presents optimal and heuristic solutions to the problem subject to our proposed EQDF and EQDZL analysis. Our simulation results show that EQDF and EQDZL can improve schedulability significantly compared to EDF and EDZL, respectively.


    Bibtex


    Journal Information

    ISSN: 0164-1212

  59. Time-Reversibility of Schedulability Tests
  60. Jinkyu Lee
    The 35th IEEE Real-Time Systems Symposium (RTSS), pp. 294-303, Rome, Italy, December 2014 (Acceptance ratio: 33/154=21.4%)
    SelectedConference Paper

    Abstract

    For timing guarantees of a set of real-time tasks under a target scheduling algorithm, a number of schedulability tests have been studied. However, there still exist many task sets that are potentially schedulable by a target scheduling algorithm, but proven schedulable by none of existing schedulability tests, especially on a multiprocessor platform. In this paper, we propose a new notion of time-reversibility of schedulability tests, which yields tighter schedulability guarantees by viewing real-time scheduling under a change in the sign of time. To this end, we first define the notion of a time-reversed scheduling algorithm against a target scheduling algorithm, for example, the time-reversed scheduling algorithm against EDF (Earliest Deadline First) is LCFS (Last-Come, First-Served), and the converse also holds. Then, a schedulability test for a scheduling algorithm is said to be time-reversible with respect to schedulability, if all task sets deemed schedulable by the test are also schedulable by its time-reversed scheduling algorithm. To exploit the notion of time-reversibility for tighter schedulability guarantees, we not only prove time-reversibility of an existing schedulability test, but also develop a new time-reversible schedulability test, both of which cover additional schedulable task sets. Next, we generalize the time-reversibility theory towards partial execution. Utilizing the notion, we can assure the schedulability of a task under a target scheduling algorithm in a divide-and-conquer manner: (i) the first some units of execution guaranteed by a schedulability test for the scheduling algorithm, and (ii) the remaining execution guaranteed by a time-reversible (with respect to partial execution) schedulability test for its time-reversed scheduling algorithm. Such a divide-and-conquer approach has not been directly applied to existing schedulability tests in that they cannot address (ii) effectively. As a case study,this paper develops RTA (Response-Time Analysis) for LCFS,proves its time-reversibility, and applies the divide-and-conquerapproach to the test along with an existing EDF schedulabilitytest. Our simulation results show that the time-reversibility theoryhelps to find up to 13.1% additional EDF-schedulable task setson a multiprocessor platform.


    Bibtex


    Conference Information

  61. Real-Time Charge/Discharge Rate Management for Hybrid Energy Storage in Electric Vehicles
  62. Eugene Kim, Kang G. Shin and Jinkyu Lee
    The 35th IEEE Real-Time Systems Symposium (RTSS), pp. 228-237, Rome, Italy, December 2014 (Cyber-Physical Systems Track) (Acceptance ratio: 33/154=21.4%)
    SelectedConference Paper

    Abstract

    Electric vehicles (EVs) are equipped with a large number of expensive battery cells, necessitating an effective battery management system (BMS) which protects the battery cells from harsh conditions while providing the required power efficiently. The discharge/charge rate affects battery health significantly, and existing BMSes employ simple discharge/charge rate scheduling so as to prevent weak cells from excessive discharge/charge. In this paper, we design and evaluate the real-time management of battery discharge/charge rate to extend battery life for EVs based on the physical dynamics and operation history of batteries. We first explore a modern energy storage system for EVs to capture physical dynamics and their impact on the battery discharge/charge rate, for example, a regenerative braking system for reusing the dissipated energy leads to current surges into the batteries, which shortens battery life. Based on understanding of the effects of discharge/charge rate in an energy storage system, we devise control knobs for manipulating the rate. Then, we design an adaptive discharge/charge rate management algorithm that determines the control knobs with a reconfigurable energy storage architecture. Our in-depth evaluation results demonstrate that the proposed discharge/charge rate management improves battery life up to 37.7% at little additional cost over the existing energy storage systems.


    Bibtex


    Conference Information

  63. Preempt a Job or Not in EDF Scheduling of Uniprocessor Systems
  64. Jinkyu Lee and Kang G. Shin
    IEEE Transactions on Computers (TC), Volume 63, Issue 5, pp. 1197-1206, May 2014
    SelectedJournal Paper

    Abstract

    The earliest-deadline-first (EDF) policy has been widely studied for the scheduling of real-time jobs for its effectiveness and simplicity. However, since each preemption incurs an additional delay to the execution of jobs, the effectiveness of EDF is affected greatly by the underlying preemption policy that determines if and when a higher-priority job is allowed to preempt a currently executing lower-priority job. To address this problem, we propose a new and better (in meeting job deadlines) preemption policy of EDF, given a non-zero preemption delay. Specifically, we propose a controlled preemption (CP) policy that controls the condition of preempting jobs, whereas existing approaches focus on that of preempted jobs. We define cp-EDF in which the CP policy is applied to EDF, and analyze its schedulability. This schedulability analysis is then utilized to develop an algorithm that assigns the optimal control parameters of cp-EDF. Our in-depth evaluation has demonstrated that cp-EDF with the optimal parameter assignment improves EDF schedulability over existing preemption policies by up to 7.4%.


    Bibtex


    Journal Information

    ISSN: 0018-9340

  65. Improvement of Real-Time Multi-Core Schedulability with Forced Non-Preemption
  66. Jinkyu Lee and Kang G. Shin
    IEEE Transactions on Parallel and Distributed Systems (TPDS), Volume 25, Issue 5, pp. 1233-1243, May 2014 (Extended version of RTSS 2012)
    SelectedJournal Paper

    Abstract

    While tasks may be preemptive or non-preemptive (due to their transactional operations), deadline guarantees in multi-core systems have been made only for those task sets in each of which all tasks are preemptive or non-preemptive, not a mixture thereof,i.e., fully preemptive or fully non-preemptive. In this paper, we first develop a schedulability analysis framework that guarantees the timing requirements of a given task set in which a task can be either preemptive or non-preemptive in multi-core systems. We then apply this framework to the prioritization polices of EDF (earliest deadline first) and FP (fixed priority), yielding schedulability tests of mpn-EDF (Mixed Preemptive/Non-preemptive EDF) and mpn-FP, which are generalizations of corresponding fully-preemptive and non-preemptive algorithms, i.e., fp-EDF and np-EDF, and fp-FP and np-FP. In addition to their timing guarantees for any task set that consists of a mixture of preemptive and non-preemptive tasks, the tests outperform the existing schedulability tests of np-EDF andnp-FP (i.e., special cases of mpn-EDF and mpn-FP). Using these tests, we also improve schedulability by developing an algorithm that optimally disallows preemption of a preemptive task under a certain assumption. We demonstrate via simulation that the algorithm finds up to 47.6 percent additional task sets that are schedulable with mpn-FP (likewise mpn-EDF), but not with fp-FP and np-FP (likewisefp-EDF and np-EDF).


    Bibtex


    Journal Information

    ISSN: 1045-9219

  67. Reducing Peak Power Consumption in Multi-Core Systems Without Violating Real-Time Constraints
  68. Jinkyu Lee, Buyoung Yun and Kang G. Shin
    IEEE Transactions on Parallel and Distributed Systems (TPDS), Volume 25, Issue 4, pp. 1024-1033, April 2014
    SelectedJournal Paper

    Abstract

    The potential of multi-core chips for high performance and reliability at low cost has made them ideal computing platforms for embedded real-time systems. As a result, power management of a multi-core chip has become an important issue in the design of embedded real-time systems. Most existing approaches have been designed to regulate the behavior of average power consumption, such as minimizing the total energy consumption or the chip temperature. However, little attention has been paid to the worst-case behavior of instantaneous power consumption on a chip, called chip-level peak power consumption, an important design parameter that determines the cost and/or size of chip design/packaging and the underlying power supply. We address this problem by reducing the chip-level peak power consumption at design time without violating any real-time constraints. We achieve this by carefully scheduling real-time tasks, without relying on any additional hardware implementation for power management, such as dynamic voltage and frequency scaling. Specifically, we propose a new scheduling algorithm FP Θ that restricts the concurrent execution of tasks assigned on different cores, and perform its schedulability analysis. Using this analysis, we develop a method that finds a set of concurrent executable tasks, such that the design-time chip-level peak power consumption is minimized and all timing requirements are met. We demonstrate via simulation that the proposed method not only keeps the design-time chip-level peak power consumption as low as the theoretical lower bound for trivial cases, but also reduces the peak power consumption for non-trivial cases by up to 12.9 percent compared to the case of no restriction on concurrent task execution.


    Bibtex


    Journal Information

    ISSN: 1045-9219

  69. Real-Time Battery Thermal Management for Electric Vehicles
  70. Eugene Kim, Kang G. Shin and Jinkyu Lee
    The 5th ACM/IEEE International Conference on Cyber-Physical Systems (ICCPS), pp. 72-83, Berlin, Germany, April 2014 (Acceptance ratio: 18/76=23.7%)
    SelectedConference Paper

    Abstract

    Electric vehicles (EVs) are powered by a large number of battery cells, requiring an effective battery management system (BMS) to maintain the battery cells in an operational condition while providing the necessary power efficiently. Temperature is one of the most important factors for battery operation, and existing BMSes have thus employed simple thermal management policies so as to prevent battery cells from very high and low temperatures which may likely cause their explosion and malfunction, respectively. In this paper, we study thermo-physical characteristics of battery cells, and design a battery thermal management system that achieves efficiency and reliability by active thermal controls. We first analyze the effect of a temperature change on the basic operation of a battery cell. We then show how it can cause thermal and general problems, e.g., a thermal runaway that results in explosion of battery cells, and unbalanced state of charge (SoC) that degrades battery cells' performance. Based on this understanding of thermal behavior, we finally develop temperature-control approaches which are then used to design a battery thermal management system. Our simulation results demonstrate that the proposed thermal management system improves battery performance by up to 58.4% without compromising reliability over the existing simple thermal management.


    Bibtex


    Conference Information

  71. Demand-Based Schedulability Analysis for Real-Time Multi-Core Scheduling
  72. Jinkyu Lee and Kang G. Shin
    Journal of Systems and Software (JSS), Volume 89, pp. 99-108, March 2014
    SelectedJournal Paper

    Abstract

    In real-time systems, schedulability analysis has been widely studied to provide offline guarantees on temporal correctness, producing many analysis methods. The demand-based schedulability analysis method has a great potential for high schedulability performance and broad applicability. However, such a potential is not yet fully realized for real-time multi-core scheduling mainly due to (i) the difficulty of calculating the resource demand under dynamic priority scheduling algorithms that are favorable to multi-cores, and (ii) the lack of understanding how to combine the analysis framework with deadline-miss conditions specialized for those scheduling algorithms. Addressing those two issues, to the best of our knowledge, this paper presents the first demand-based schedulability analysis for dynamic job-priority scheduling algorithms: EDZL (Earliest Deadline first until Zero-Laxity) and LLF (Least Laxity First), which are known to be effective for real-time multi-core scheduling. To this end, we first derive demand bound functions that compute the maximum possible amount of resource demand of jobs of each task while the priority of each job can change dynamically under EDZL and LLF. Then, we develop demand-based schedulability analyses for EDZL and LLF, by incorporating those new demand bound functions into the existing demand-based analysis framework. Finally, we combine the framework with additional deadline-miss conditions specialized for those two laxity-based dynamic job-priority scheduling algorithms, yielding tighter schedulability analyses. Via simulations, we demonstrate that the proposed schedulability analyses outperform the existing schedulability analyses for EDZL and LLF.


    Bibtex


    Journal Information

    ISSN: 0164-1212

  73. Contention-Free Executions for Real-Time Multiprocessor Scheduling
  74. Jinkyu Lee, Arvind Easwaran and Insik Shin
    ACM Transactions on Embedded Computing Systems (TECS), Volume 13, Issue 2s, Article 69, January 2014 (Extended version of RTAS 2011)
    SelectedJournal Paper

    Abstract

    A time slot is defined as contention-free if the number of jobs with remaining executions in the slot is no larger than the number of processors, or contending, otherwise. Then an important property holds that in any contention-free slot, all jobs with remaining executions are guaranteed to be scheduled as long as the scheduler is work-conserving. This article aims at improving schedulability by utilizing the contention-free slots. To achieve this, this article presents a policy (called CF policy) that moves some job executions from contending slots to contention-free ones. This policy can be employed by any work-conserving, preemptive scheduling algorithm, and we show that any algorithm extended with this policy dominates the original algorithm in terms of schedulability. We also present improved schedulability tests for algorithms that employ this policy, based on the observation that interference from jobs is reduced when their executions are postponed to contention-free slots. Simulation results demonstrate that the CF policy, incorporated into existing algorithms, significantly improves schedulability of those existing algorithms.


    Bibtex


    Journal Information

    ISSN: 1539-9087

  75. Design and Management of Satellite Power Systems
  76. Jinkyu Lee, Eugene Kim and Kang G. Shin
    The 34th IEEE Real-Time Systems Symposium (RTSS), pp. 97-106, Vancouver, Canada, December 2013 (Cyber-Physical Systems Track) (Acceptance ratio: 36/160=22.5%)
    SelectedConference Paper

    Abstract

    Satellites are indispensable for broadcast, weather forecast, navigation, and many other applications, but their design entails a number of stringent requirements, such as limited space and weight, impossible/costly online repairs, severe radiation, and a wide range of temperature they have to withstand. These requirements can only be met by an effective, robust co-design of physical and computing (control) parts of each satellite, making them prototypical cyber-physical systems (CPSes). Of the various CPS issues related to satellites, this paper focuses on offline design and online management of satellite power systems. Specifically, we analyze and model unique characteristics of power supply and demand of a satellite, which are dictated by the periodicity of power generation from solar panels and the nonlinear behavior of rechargeable battery cells. Based on the understanding of these characteristics, we first propose how to find the best configuration (e.g., the number, the arrangement, and the type) of solar panels and battery cells at design time, such that all tasks can be executed without power shortage throughout the satellite's mission lifetime. Second, we propose how to manage power online so as to execute the highest QoS versions of tasks (thus yielding the most power-effective performance) without compromising the power-sufficiency guarantee under a given configuration. As a case study, we study cubic-shaped nanosatellites, which have been launched multiple times since 2004. We borrow their architecture, configuration and parameters, and demonstrate the effectiveness of our design and management of satellite power systems.


    Bibtex


    Conference Information

  77. Schedulability Analysis for Continuous Task Execution During a Mode Transition in Real-Time Multi-Core Systems
  78. Jinkyu Lee and Kang G. Shin
    The 34th IEEE Real-Time Systems Symposium (RTSS), pp. 11-20, Vancouver, Canada, December 2013 (Acceptance ratio: 36/160=22.5%)
    SelectedConference Paper

    Abstract

    To enable real-time systems to adapt to dynamically changing environments, update functionalities and/or accommodate those tasks migrated from other failed sub-systems, there have been a number of studies on making timing guarantees while accounting for change of parameters and addition/deletion of tasks. While most of them have dealt with "transition" protocols that delay next task releases or discard the unfinished tasks released before the transition, such protocols are not suitable for many control systems in which missing/delaying control updates (by completing periodic tasks) even during a transition or mode-change may cause system instability or incur a significant incremental operational cost. In this paper, we focus on a transition protocol that does not miss/delay control updates during a system transition, and develop a new schedulability analysis for the transition in a real-time multi-core system, which provides sufficient timing guarantees without requiring any online information, such as the release and execution patterns of tasks and the start time of a transition. To achieve this, we extend an existing popular schedulability analysis framework for nontransitional tasks, and identify the scenarios that maximize the duration of a task's interference to another task in the case of a transition. Since the analysis works for any arbitrary transition order of tasks, we can improve the schedulability performance by enforcing a specific order. We formulate the problem of assigning an optimal transition order, and develop a solution by deriving some properties of optimality. Our evaluation results demonstrate that the proposed solution finds more schedulable task sets, which are not covered by naive approaches.


    Bibtex


    Conference Information

  79. Scheduling in Heterogeneous Computing Environments for Proximity Queries
  80. Duksu Kim, Jinkyu Lee, Junghwan Lee, Insik Shin, John Kim and Sung-Eui Yoon
    IEEE Transactions on Visualization and Computer Graphics (TVCG), Volume 19, Issue 9, pp. 1513-1525, September 2013 (Spotlight Paper for the September 2013 issue)
    SelectedJournal Paper

    Abstract

    We present a novel, linear programming (LP)-based scheduling algorithm that exploits heterogeneous multicore architectures such as CPUs and GPUs to accelerate a wide variety of proximity queries. To represent complicated performance relationships between heterogeneous architectures and different computations of proximity queries, we propose a simple, yet accurate model that measures the expected running time of these computations. Based on this model, we formulate an optimization problem that minimizes the largest time spent on computing resources, and propose a novel, iterative LP-based scheduling algorithm. Since our method is general, we are able to apply our method into various proximity queries used in five different applications that have different characteristics. Our method achieves an order of magnitude performance improvement by using four different GPUs and two hexa-core CPUs over using a hexa-core CPU only. Unlike prior scheduling methods, our method continually improves the performance, as we add more computing resources. Also, our method achieves much higher performance improvement compared with prior methods as heterogeneity of computing resources is increased. Moreover, for one of tested applications, our method achieves even higher performance than a prior parallel method optimized manually for the application. We also show that our method provides results that are close (e.g., 75 percent) to the performance provided by a conservative upper bound of the ideal throughput. These results demonstrate the efficiency and robustness of our algorithm that have not been achieved by prior methods. In addition, we integrate one of our contributions with a work stealing method. Our version of the work stealing method achieves 18 percent performance improvement on average over the original work stealing method. This result shows wide applicability of our approach.


    Bibtex


    Journal Information

    ISSN: 1077-2626

  81. EDZL Schedulability Analysis in Real-Time Multi-Core Scheduling
  82. Jinkyu Lee and Insik Shin
    IEEE Transactions on Software Engineering (TSE), Volume 39, Issue 7, pp. 910-916, July 2013
    SelectedJournal Paper

    Abstract

    In real-time systems, correctness depends not only on functionality but also on timeliness. A great number of scheduling theories have been developed for verification of the temporal correctness of jobs (software) in such systems. Among them, the Earliest Deadline first until Zero-Laxity (EDZL) scheduling algorithm has received growing attention thanks to its effectiveness in multicore real-time scheduling. However, the true potential of EDZL has not yet been fully exploited in its schedulability analysis as the state-of-the-art EDZL analysis techniques involve considerable pessimism. In this paper, we propose a new EDZL multicore schedulability test. We first introduce an interesting observation that suggests an insight toward pessimism reduction in the schedulability analysis of EDZL. We then incorporate it into a well-known existing Earliest Deadline First (EDF) schedulability test, resulting in a new EDZL schedulability test. We demonstrate that the proposed EDZL test not only has lower time complexity than existing EDZL schedulability tests, but also significantly improves the schedulability of EDZL by up to 36.6 percent compared to the best existing EDZL schedulability tests.


    Bibtex


    Journal Information

    ISSN: 0098-5589

  83. Global EDF Schedulability Analysis for Synchronous Parallel Tasks on Multicore Platforms
  84. Hoon Sung Chwa, Jinkyu Lee, Kieu-My Phan, Arvind Easwaran and Insik Shin
    The 25th Euromicro Conference on Real-Time Systems (ECRTS), pp. 25-34, Paris, France, July 2013 (Acceptance ratio: 27/99=27.3%)
    SelectedConference Paper

    Abstract

    The trend towards multi-core/many-core architectures is well underway. It is therefore becoming very important to develop software in ways that take advantage of such parallel architectures. This particularly entails a shift in programming paradigms towards fine-grained, thread-parallel computing. Many parallel programming models have been introduced targeting such intra-task thread-level parallelism. However, most successful results on traditional multi-core real-time scheduling are focused on sequential programming models. For example, thread-level parallelism is not properly captured into the concept of interference, which is key to many schedulability analysis techniques. Thereby, most interference-based analysis techniques are not directly applicable to parallel programming models. Motivated by this, we extend the notion of interference to capture thread-level parallelism more accurately. We then leverage the proposed notion of parallelism-aware interference to derive efficient EDF schedulability tests that are directly applicable to synchronous parallel task models on multi-core platforms. Our evaluation results indicate that the proposed analysis significantly advances the state-of-the-art in EDF schedulability analysis for synchronous parallel tasks.


    Bibtex


    Conference Information

  85. Real-Time Prediction of Battery Power Requirements for Electric Vehicles
  86. Eugene Kim, Jinkyu Lee, and Kang G. Shin
    The 4th ACM/IEEE International Conference on Cyber-Physical Systems (ICCPS), pp. 11-20, Philadalphia, PA, USA, April 2013 (Acceptance ratio: 24/103=23.3%)
    SelectedConference Paper

    Abstract

    A battery management system (BMS) is responsible for protecting the battery from damage, predicting battery life, and maintaining the battery in an operational condition. In this paper, we propose an efficient way of predicting the power requirements of electric vehicles (EVs) based on a history of their power consumption, speed, and acceleration, as well as the road information from a pre-downloaded map. The predicted power requirement is then used by the BMS to prevent the damage of battery cells that might result from high discharge rates. This prediction also helps BMS efficiently schedule and allocate battery cells in real time to meet an EV's power demands. For accurate prediction of power requirements, we need an accurate model for the power requirement of each given application. We generate this model in real time by collecting and using historical data of power consumption, speed, acceleration, and road information such as slope and speed limit. By using this information and the operator's driving pattern, the model extracts the vehicle's history of speed and acceleration, which, in turn, enables the prediction of the vehicle's (immediate) future power requirements. That is, the power requirement prediction is achieved by combining a real-time power requirement model and the estimation of the vehicle's acceleration and speed. The proposed approach predicts closer to the actual required power than a widely-used heuristic approach that uses measured power demand, by up to 69.2%.


    Bibtex


    Conference Information

  87. Extending Task-level to Job-level Fixed Priority Assignment and Schedulability Analysis Using Pseudo-deadlines
  88. Hoon Sung Chwa, Hyoungbu Back, Sanjian Chen, Jinkyu Lee, Arvind Easwaran, Insik Shin and Insup Lee
    The 33rd IEEE Real-Time Systems Symposium (RTSS), pp. 51-62, San Juan, Puerto Rico, December 2012 (Acceptance ratio: 35/157=22.3%)

    Best Paper Award: one best paper and one best student paper were selected out of 157 submissions

    SelectedConference Paper

    Abstract

    In global real-time multiprocessor scheduling, a recent analysis technique for Task-level Fixed-Priority (TFP) scheduling has been shown to outperform many of the analyses for Job-level Fixed-Priority (JFP) scheduling on average. Since JFP is a generalization of TFP scheduling, and the TFP analysis technique itself has been adapted from an earlier JFP analysis, this result is counter-intuitive and in our opinion highlights the lack of good JFP scheduling techniques. Towards generalizing the superior TFP analysis to JFP scheduling, we propose the Smallest Pseudo-Deadline First (SPDF) JFP scheduling algorithm. SPDF uses a simple task-level parameter called pseudo-deadline to prioritize jobs, and hence can behave as a TFP or JFP scheduler depending on the values of the pseudodeadlines. This natural transition from TFP to JFP scheduling has enabled us to incorporate the superior TFP analysis technique in an SPDF schedulability test. We also present a pseudo-deadline assignment algorithm for SPDF scheduling that extends the well-known Optimal Priority Assignment (OPA) algorithm for TFP scheduling. We show that our algorithm is optimal for the derived schedulability test, and also present a heuristic to overcome the computational complexity issue of the optimal algorithm. Our simulation results show that the SPDF algorithm with the new analysis significantly outperforms state-of-the-art TFP and JFP analysis.


    Bibtex


    Conference Information

  89. Controlling Preemption for Better Schedulability in Multi-Core Systems
  90. Jinkyu Lee and Kang G. Shin
    The 33rd IEEE Real-Time Systems Symposium (RTSS), pp. 29-38, San Juan, Puerto Rico, December 2012 (Acceptance ratio: 35/157=22.3%)
    SelectedConference Paper

    Abstract

    Interest in real-time multiprocessor scheduling has been rekindled as multi-core chips are increasingly used for embedded real-time systems. While tasks may be preemptive or non-preemptive (due to their transactional operations), deadline guarantees are usually made only for those task sets in each of which all tasks are preemptive or non-preemptive, not a mixture thereof, i.e., all or nothing. In this paper, we develop a schedulability analysis framework that guarantees the timing requirements of a given task set in which a task can be either preemptive or non-preemptive. As an example, we apply this framework to the prioritization policy of EDF (Earliest Deadline First), yielding schedulability tests of mpn-EDF (Mixed Preemptive/Non-preemptive EDF), which is a generalization of both fp-EDF (fully-preemptive EDF) and np-EDF (non-preemptive EDF). In addition to their deadline guarantees for any task set that is composed of a mixture of preemptive and non-preemptive tasks, the tests outperform the existing schedulability tests of np-EDF (a special case of mpn-EDF) by up to 109.1%. Using these tests, we also improve schedulability by disallowing preemptions of some preemptive tasks. For this, we develop an algorithm that optimally disallows preemption of a preemptive task under a certain assumption, and demonstrate via simulation that the algorithm discovers up to 30.9% additional task sets that are schedulable with the proposed scheduling scheme, but not with fp-EDF or np-EDF.


    Bibtex


    Conference Information

  91. Laxity Dynamics and LLF Schedulability Analysis on Multiprocessor Platforms
  92. Jinkyu Lee, Arvind Easwaran, and Insik Shin
    Real-Time Systems (RTSJ), Volume 48, Issue 6, pp. 716-749, November 2012 (Extended version of RTSS 2010) (Special Issue on Multiprocessor Real-Time Systems)
    SelectedJournal Paper

    Abstract

    LLF (Least Laxity First) scheduling, which assigns a higher priority to a task with a smaller laxity, has been known as an optimal preemptive scheduling algorithm on a single processor platform. However, little work has been made to illuminate its characteristics upon multiprocessor platforms. In this paper, we identify the dynamics of laxity from the system's viewpoint and translate the dynamics into LLF multiprocessor schedulability analysis. More specifically, we first characterize laxity properties under LLF scheduling, focusing on laxity dynamics associated with a deadline miss. These laxity dynamics describe a lower bound, which leads to the deadline miss, on the number of tasks of certain laxity values at certain time instants. This lower bound is significant because it represents invariants for highly dynamic system parameters (laxity values). Since the laxity of a task is dependent of the amount of interference of higher-priority tasks, we can then derive a set of conditions to check whether a given task system can go into the laxity dynamics towards a deadline miss. This way, to the author's best knowledge, we propose the first LLF multiprocessor schedulability test based on its own laxity properties. We also develop an improved schedulability test that exploits slack values. We mathematically prove that the proposed LLF tests dominate the state-of-the-art EDZL tests. We also present simulation results to evaluate schedulability performance of both the original and improved LLF tests in a quantitative manner.


    Bibtex


    Journal Information

    ISSN: 0922-6443

  93. Convex Optimization Framework for Intermediate Deadline Assignment in Soft and Hard Real-Time Distributed Systems
  94. Jinkyu Lee, Insik Shin, and Arvind Easwaran
    Journal of Systems and Software (JSS), Volume 85, Issue 10, pp. 2331-2339, October 2012 (Extended version of EMSOFT 2010)
    SelectedJournal Paper

    Abstract

    It is generally challenging to determine end-to-end delays of applications for maximizing the aggregate system utility subject to timing constraints. Many practical approaches suggest the use of intermediate deadline of tasks in order to control and upper-bound their end-to-end delays. This paper proposes a unified framework for different time-sensitive, global optimization problems, and solves them in a distributed manner using Lagrangian duality. The framework uses global viewpoints to assign intermediate deadlines, taking resource contention among tasks into consideration. For soft real-time tasks, the proposed framework effectively addresses the deadline assignment problem while maximizing the aggregate quality of service. For hard real-time tasks, we show that existing heuristic solutions to the deadline assignment problem can be incorporated into the proposed framework, enriching their mathematical interpretation.


    Bibtex


    Journal Information

    ISSN: 0164-1212

  95. Zero-Laxity based Real-Time Multiprocessor Scheduling
  96. Jinkyu Lee, Arvind Easwaran, Insik Shin, and Insup Lee
    Journal of Systems and Software (JSS), Volume 84, Issue 12, pp. 2324-2333, December 2011
    SelectedJournal Paper

    Abstract

    It has been widely studied how to schedule real-time tasks on multiprocessor platforms. Several studies have developed optimal scheduling policies for implicit deadline task systems. So far however, studies have failed to develop effective scheduling strategies for more general task systems such as constrained deadline tasks. We argue that a narrow focus on deadline satisfaction (urgency) is the primary reason for this lack of success. In particular, few studies have considered the impact on scheduling of the restriction that a job cannot simultaneously execute on more than one core (parallelism). In this paper we look at one such simple, but effective, characterization of urgency and parallelism ? the zero laxity first policy (ZL policy). We study in detail how beneficial the ZL policy is to schedulability. We then develop an improved schedulability test for any algorithm that employs the ZL policy, and prove that the test dominates previously known tests. Our simulation results show that the improved ZL schedulability test outperforms the existing ones.


    Bibtex


    Journal Information

    ISSN: 0164-1212

  97. Maximizing Contention-Free Executions in Multiprocessor Scheduling
  98. Jinkyu Lee, Arvind Easwaran and Insik Shin
    The 17th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), pp. 235-244, Chicago, IL, USA, April 2011 (Acceptance ratio: 29/139=20.9%)

    Best Student Paper Award: one best paper and one best student paper were selected out of 139 submissions

    SelectedConference Paper

    Abstract

    It is widely assumed that scheduling real-time tasks becomes more difficult as their deadlines get shorter. With deadlines shorter, however, tasks potentially compete less with each other for processors, and this could produce more contention-free slots at which the number of competing tasks is smaller than or equal to the number of available processors. This paper presents a policy (called CF policy) that utilizes such contention-free slots effectively. This policy can be employed by any work-conserving, preemptive scheduling algorithm, and we show that any algorithm extended with this policy dominates the original algorithm in terms of schedulability. We also present improved schedulability tests for algorithms that employ this policy, based on the observation that interference from tasks is reduced when their executions are postponed to contention-free slots. Finally, using the properties of the CF policy, we derive a counter-intuitive claim that shortening of task deadlines can help improve schedulability of task systems. We present heuristics that effectively reduce task deadlines for better scheduability without performing any exhaustive search.


    Bibtex


    Conference Information

  99. LLF Schedulability Analysis on Multiprocessor Platforms
  100. Jinkyu Lee, Arvind Easwaran and Insik Shin
    The 31st IEEE Real-Time Systems Symposium (RTSS), pp. 25-36, San Diego, CA, USA, December 2010 (Acceptance ratio: 36/142=25.4%)
    SelectedConference Paper

    Abstract

    LLF (Least Laxity First) scheduling, which assigns a higher priority to a task with smaller laxity, has been known as an optimal preemptive scheduling algorithm on a single processor platform. However, its characteristics upon multiprocessor platforms have been little studied until now. Orthogonally, it has remained open how to efficiently schedule general task systems, including constrained deadline task systems, upon multiprocessors. Recent studies have introduced zero laxity (ZL) policy, which assigns a higher priority to a task with zero laxity, as a promising scheduling approach for such systems (e.g., EDZL). Towards understanding the importance of laxity in multiprocessor scheduling, this paper investigates the characteristics of ZL policy and presents the first ZL schedulability test for any work-conserving scheduling algorithm that employs this policy. It then investigates the characteristics of LLF scheduling, which also employs the ZL policy, and derives the first LLF-specific schedulability test on multiprocessors. It is shown that the proposed LLF test dominates the ZL test as well as the state-of-art EDZL test.


    Bibtex


    Conference Information

  101. Online Robust Optimization Framework for QoS Guarantees in Distributed Soft Real-Time Systems
  102. Jinkyu Lee, Insik Shin and Arvind Easwaran
    The 10th ACM International Conference on Embedded Software (EMSOFT), pp. 89-98, Scottsdale, AZ, USA, October 2010 (Acceptance ratio: 29/89=32.6%)
    SelectedConference Paper

    Abstract

    In distributed soft real-time systems, maximizing the aggregate quality-of-service (QoS) is a typical system-wide goal, and addressing the problem through distributed optimization is challenging. Subtasks are subject to unpredictable failures in many practical environments, and this makes the problem much harder. In this paper, we present a robust optimization framework for maximizing the aggregate QoS in the presence of random failures. We introduce the notion of K-failure to bound the effect of random failures on schedulability. Using this notion we define the concept of K-robustness that quantifies the degree of robustness on QoS guarantee in a probabilistic sense. The parameter K helps to tradeoff achievable QoS versus robustness. The proposed robust framework produces optimal solutions through distributed computations on the basis of Lagrangian duality, and we present some implementation techniques. Our simulation results show that the proposed framework can probabilistically guarantee sub-optimal QoS which remains feasible even in the presence of random failures.


    Bibtex


    Conference Information

  103. Modeling and Performance Analysis of Address Allocation Schemes for Mobile Ad Hoc Networks
  104. Sehoon Kim, Jinkyu Lee, and Ikjun Yeom
    IEEE Transactions on Vehicular Technology (TVT), Volume 57, Issue 1, pp. 490-501, January 2008
    SelectedJournal Paper

    Abstract

    Address allocation is an essential part in maintaining a mobile ad hoc network (MANET) effectively, and several address allocation schemes have been proposed. In this paper, we present a set of analytical models to evaluate the efficiency of address allocation schemes. The derived models quantitatively characterize the efficiency of four popular address allocation schemes in terms of latency and communication overhead. Through the analysis, we achieve numerical results that show the impact of network parameters on the efficiency of these schemes. We also conduct simulations and compare with analytical results to validate our models. The analytical model developed in this paper is able to more accurately predict the performance of address allocation schemes over a various range of loss rates and would be useful in providing more insights for the study of an efficient address allocation scheme in MANETs. To our understanding, this is the first attempt in mathematically investigating the performance of addressing schemes in ad hoc networks.


    Bibtex


    Journal Information

    ISSN: 0018-9545

  105. Improved Low Time-Complexity Schedulability Test for Non-Preemptive EDF on a Multiprocessor
  106. Seongtae Lee, Sanghyeok Park and Jinkyu Lee
    IEEE Embedded Systems Letters, Accepted
    Journal Paper

    Abstract

    In real-time embedded systems, NP-EDF (Non-Preemptive Earliest Deadline First) is one of the most popular scheduling algorithms to offer timing guarantees of a set of nonpreemptive real-time jobs (tasks). While most existing schedulability tests for NP-EDF on a multiprocessor platform have paid attention to improving schedulability performance at the expense of increasing time-complexity, only a few studies can be used for the situation where low time-complexity is critical. In this paper, based on an existing low time-complexity schedulability test for NP-EDF, we develop schedulability tests that improve schedulability performance but maintain low time-complexity. Our experiments show that the proposed schedulability tests improve schedulability performance up to 592.4%, compared to the existing low time-complexity one, and they can find some additional task sets schedulable by NP-EDF, which cannot be covered by existing high time-complexity NP-EDF schedulability tests.


    Bibtex


    Journal Information

    ISSN: 1943-0663

  107. Infeasibility Test for Fixed-Priority Scheduling on Multiprocessor Platforms
  108. Hoon Sung Chwa and Jinkyu Lee
    IEEE Embedded Systems Letters, Accepted
    Journal Paper

    Abstract

    Fixed-Priority Scheduling (FPS), due to its simplicity to implement, has been one of the most popular scheduling algorithms for real-time embedded systems equipped with multiprocessor platforms. While there have been many studies that find sufficient conditions for a given task set to be feasible (schedulable) by FPS with a proper priority assignment, the other direction (i.e., finding infeasible task sets) has not been studied. In this letter, we address a necessary feasibility condition that judges a given task set to be infeasible under FPS with every priority assignment on multiprocessor platforms. To this end, we derive useful properties for the condition, and develop the first infeasibility test for FPS on multiprocessor platforms. Via simulations, we show that the proposed infeasibility test discovers a number of FPS-infeasible task sets which are not proven FPS-infeasible by any existing studies.


    Bibtex


    Journal Information

    ISSN: 1943-0663

  109. FT-PIP: Flush Task Incorporated Priority-Inheritance Protocol to Reduce Information Leakage on Multiprocessor Real-Time Systems
  110. Hyeongboo Baek and Jinkyu Lee
    IEEE Access, Volume 9, pp. 81882-81894, June 2021
    Journal Paper

    Abstract

    In a traditional real-time system, the major requirement is to finish every real-time task within its predefined time. However, as a modern real-time system is connected to external networks and its subsystems are developed by different vendors, it becomes an important requirement to address the problem of information leakage on resources shared by different real-time tasks. This triggers studies that incorporate security mechanisms into the real-time scheduling. While it is one of the most well-known approaches to add the flush task (FT) mechanism and analyze its effect on timing guarantees, the existing FT approaches have been limited to a real-time system that employs at most one resource shared by real-time tasks executed on a uniprocessor platform. In this paper, we propose a flush task incorporated priority-inheritance protocol (FT-PIP) for global fixed-priority multiprocessor scheduling and develop its schedulability analysis, which is the first attempt that not only (a) supports timing guarantees but also (b) satisfies security constraints for (c) a multiprocessor platform with multiple shared resources. Via simulations, we demonstrate that FT-PIP and its schedulability analysis are effective in achieving both (a) and (b) for (c).


    Bibtex


    Journal Information

    ISSN: 2169-3536

  111. Analysis of the K2 Scheduler for a Real-Time System with an SSD
  112. Sanghyeok Park and Jinkyu Lee
    Electronics, Volume 10, Issue 7, pp. 865:1-15, April 2021
    Journal Paper

    Abstract

    While an SSD (Solid State Drive) has been widely used for storage in many computing systems due to its small average latency, how to provide timing guarantees of a delay-sensitive (real-time) task on a real-time system equipped with an SSD has not been fully explored. A recent study has proposed a work-constraining I/O scheduler, called K2, which has succeeded in reducing the tail latency of a real-time task at the expense of compromising the total bandwidth for real-time and non-real-time tasks. Although the queue length bound parameter of the K2 scheduler is a key to regulate the tradeoff between a decrease in the tail latency of a real-time task and an increase in penalty of the total bandwidth, the parameter's impact on the tradeoff has not been thoroughly investigated. In particular, no studies have addressed how the case of a fully occupied SSD that incurs garbage collection changes the performance of the K2 scheduler in terms of the tail latency of the real-time task and the total bandwidth. In this paper, we systematically analyze the performance of the K2 scheduler for different I/O operation types, based on experiments on Linux. We investigate how the performance is changed on a fully occupied SSD due to garbage collection. Utilizing the investigation, we draw general guidelines on how to select a proper setting of the queue length bound for better performance. Finally, we propose how to apply the guidelines to achieve target objectives that optimize the tail latency of the real-time task and the total bandwidth at the same time, which has not been achieved by previous studies.


    Bibtex


    Journal Information

    ISSN: 2079-9292

  113. Improved Schedulability Test for Non-preemptive Fixed-Priority Scheduling on Multiprocessors
  114. Hyeongboo Baek and Jinkyu Lee
    IEEE Embedded Systems Letters, Volume 12, Issue 4, pp. 129-132, December 2020
    Journal Paper

    Abstract

    Non-preemptive scheduling is essential to tasks that inherently disallow any preemption and useful for tasks that exhibit extremely large preemption/migration overhead; however, studies of non-preemptive scheduling have not matured for real-time tasks subject to timing constraints. In this paper, we propose an improved schedulability test for non-preemptive fixed-priority scheduling (NP-FP), which offers timing guarantees for a set of real-time tasks executed on a multiprocessor platform. To this end, we first carefully investigate the NP-FP properties, and present an observation why the existing technique is pessimistic in calculating interference from higher-priority tasks. We then develop a new technique that tightly upper-bounds the amount of the interference, and show how to incorporate the technique into the existing schedulability test. Via simulations, we demonstrate that our proposed test improves schedulability performance of NP-FP up to 18%, compared to the state-of-the-art existing tests.


    Bibtex


    Journal Information

    ISSN: 1943-0663

  115. SmartGrip: Grip Sensing System for Commodity Mobile Devices Through Sound Signals
  116. Namhyun Kim, Junseong Lee, Joyce Jiyoung Whang, and Jinkyu Lee
    Personal and Ubiquitous Computing, Volume 24, Issue 5, pp. 643-654, October 2020
    Journal Paper

    Abstract

    Although many studies have attempted to detect the hand postures of a mobile device to utilize these postures as a user interface, they either require additional hardware or can differentiate a limited number of grips only if there is a touch event on the mobile device's screen. In this paper, we propose a novel grip sensing system, called SmartGrip, which allows a mobile device to detect different hand postures without any additional hardware and a screen touch event. SmartGrip emits carefully designed sound signals and differentiates the propagated signals distorted by different user grips. To achieve this, we analyze how a sound signal propagates from the speaker to the microphone of a mobile device and then address three key challenges: sound structure design, volume control, and feature extraction and classification. We implement and evaluate SmartGrip on three Android mobile devices. With six representative grips, SmartGrip exhibits 93.1% average accuracy for ten users in an office environment. We also demonstrate that SmartGrip operates with 83.5 to 98.3% accuracy in six different (noisy) locations. Further demonstrating the feasibility of SmartGrip as a user interface, we develop an Android application that exploits SmartGrip, validating its practical usage.


    Bibtex


    Journal Information

    ISSN: 1617-4909

  117. Panda: Reinforcement Learning-Based Priority Assignment for Multi-Processor Real-Time Scheduling
  118. Hyungsung Lee, Jinkyu Lee, Ikyun Yeom and Honguk Woo
    IEEE Access, Volume 8, pp. 185570-185583, October 2020
    Journal Paper

    Abstract

    Recently, deep reinforcement learning (RL) technologies have been considered as a feasible solution for tackling combinatorial problems in various research and engineering areas. Motivated by this recent success of RL-based approaches, in this paper, we focus on how to utilize RL technologies in the context of real-time system research. Specifically, we first formulate the problem of fixed-priority assignments for multi-processor real-time scheduling, which has long been considered challenging in the real-time system community, as a combinatorial problem. We then propose the RL-based priority assignment model Panda that employs (i) a taskset embedding mechanism driven by attention-based encoder-decoder deep neural networks, hence enabling to efficiently extract useful features from the dynamic relation of periodic tasks. We also present two optimization schemes tailored to adopt RL for real-time task scheduling problems: (ii) the response time analysis (RTA)-based policy gradient RL and guided learning schemes, which facilitate the training processes of the Panda model. To the best of our knowledge, our approach is the first to employ RL for real-time task scheduling. Through various experiments, we show that Panda is competitive with well-known heuristic algorithms for real-time task scheduling upon a multi-processor platform, and it often outperforms them in large-scale non-trivial settings, e.g., achieving an average 7.7% enhancement in schedulability ratio for a testing system configuration of 64-sized tasksets and an 8-processor platform.


    Bibtex


    Journal Information

    ISSN: 2169-3536

  119. Cooperative and Non-Cooperative Frameworks with Utility Function Design for Intermediate Deadline Assignment in Real-Time Distributed Systems
  120. Jinkyu Lee
    Mathematics, Volume 8, Issue 9, pp. 1579:1-13, September 2020
    Journal Paper

    Abstract

    In real-time distributed systems, it is important to provide offline guarantee for an upper-bound of each real-time task's end-to-end delay, which has been achieved by assigning proper intermediate deadlines of individual real-time tasks at each node. Although existing studies have succeeded to utilize mathematical theories of distributed computation/control for intermediate deadline assignment, they have assumed that every task operates in a cooperative manner, which does not always hold for real-worlds. In addition, existing studies have not addressed how to exploit a trade-off between end-to-end delay fairness among real-time tasks and performance for minimizing aggregate end-to-end delays. In this paper, we recapitulate an existing cooperative distributed framework, and propose a non-cooperate distributed framework that can operate even with selfish tasks, each of which is only interested in minimizing its own end-to-end delay regardless of achieving the system goal. We then propose how to design utility functions that allow the real-time distributed system to exploit the trade-off. Finally, we demonstrate the validity of the cooperative and non-cooperative frameworks along with the designed utility functions, via simulations.


    Bibtex


    Journal Information

    ISSN: 2227-7390

  121. Response-Time Analysis for Multi-Mode Tasks in Real-Time Multiprocessor Systems
  122. Hyeongboo Baek, Kang G. Shin and Jinkyu Lee
    IEEE Access, Volume 8, pp. 86111-86129, May 2020 (Extended version of RTSS 2013)
    Journal Paper

    Abstract

    Recently, traditional real-time systems that played a dedicated role in a limited environment have been evolving to interact with dynamically varying environments. In modern real-time systems, characteristics of real-time tasks such as computational demand and resource allocation can vary over time according to different circumstances, which is referred to as mode transition. In this paper, we focus on the problem of timing guarantees of a set of multi-mode tasks associated with mode transitions and develop an offline schedulability analysis, which does not require any online information; this is an important problem in the real-time systems area. The proposed schedulability analysis not only generalizes an existing framework designed for single-mode tasks, but also significantly improves the state-of-the-art framework designed for multi-mode tasks. Building on the proposed analysis, we also address the problem of enforcing the order of tasks within each mode transition and propose a task-level transition order assignment algorithm, yielding further improvement in schedulability performance. Through simulations, our proposed framework is shown to improve schedulability up to 777.3% over an existing schedulability analysis for multi-mode tasks, depending on the experiment setting under our evaluation environment.


    Bibtex


    Journal Information

    ISSN: 2169-3536

  123. Minimizing Capacity Degradation of Heterogeneous Batteries in a Mobile Embedded System
  124. Jaeheon Kwak and Jinkyu Lee
    IEEE Embedded Systems Letters, Volume 12, Issue 1, pp. 25-28, March 2020
    Journal Paper

    Abstract

    As different batteries exhibit their own advantages and disadvantages, a single-type battery system for a mobile embedded system (such as smartphones and tablet PC) cannot overcome the inherent limitations of its target battery. For example, although the lithium cobalt oxide (LCO) battery is the most popular battery for mobile embedded systems due to its high energy density, mobile embedded systems equipped with LCO batteries suffer from rapid capacity degradation. In this letter, we target heterogeneous batteries in a mobile embedded system and propose a method for minimizing the capacity degradation of the batteries. To this end, we first analyze factors that affect capacity degradation, and choose dominant factors that are controllable in a mobile embedded system. We then build a battery degradation model considering the factors, and finally develop a battery scheduling algorithm that minimizes capacity degradation using the degradation model. Our evaluation with real experiments and simulations demonstrates the effectiveness of the proposed algorithm in minimizing capacity degradation.


    Bibtex


    Journal Information

    ISSN: 1943-0663

  125. Limited Non-Preemptive EDF Scheduling for a Real-Time System with Symmetry Multiprocessors
  126. Hoyoun Lee and Jinkyu Lee
    Symmetry, Volume 12, Issue 1, pp. 172:1-19, January 2020
    Journal Paper

    Abstract

    In a real-time system, a series of jobs invoked by each task should finish its execution before its deadline, and EDF (Earliest Deadline First) is one of the most popular scheduling algorithms to meet such timing constraints of a set of given tasks. However, EDF is known to be ineffective in meeting timing constraints for non-preemptive tasks (which disallow any preemption) when the system does not know the future job release patterns of the tasks. In this paper, we develop a scheduling algorithm for a real-time system with a symmetry multiprocessor platform, which requires only limited information about the future job release patterns of a set of non-preemptive tasks, called LCEDF. We then derive its schedulability analysis that provides timing guarantees of the non-preemptive task set on a symmetry multiprocessor platform. Via simulations, we demonstrate the proposed schedulability analysis for LCEDF significantly improves the schedulability performance in meeting timing constraints of a set of non-preemptive tasks up to 20.16%, compared to vanilla non-preemptive EDF.


    Bibtex


    Journal Information

    ISSN: 2073-8994

  127. Design and Feasibility Study: Customized Virtual Buttons for Electronic Mobile Devices
  128. Seungtaek Song, Namhyun Kim, Sungkil Lee, Joyce Jiyoung Whang and Jinkyu Lee
    IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, Volume E102-A, Issue 4, pp. 668-671, April 2019
    Journal Paper

    Abstract

    Smartphone users often want to customize the positions and functions of physical buttons to accommodate their own usage patterns; however, this is unfeasible for electronic mobile devices based on COTS (Commercial Off-The-Shelf) due to high production costs and hardware design constraints. In this letter, we present the design and implementation of customized virtual buttons that are localized using only common built-in sensors of electronic mobile devices. We develop sophisticated strategies firstly to detect when a user taps one of the virtual buttons, and secondly to locate the position of the tapped virtual button. The virtual-button scheme is implemented and demonstrated in a COTS-based smartphone. The feasibility study shows that, with up to nine virtual buttons on five different sides of the smartphone, the proposed virtual buttons can operate with greater than 90% accuracy.


    Bibtex


    Journal Information

    ISSN: 0916-8508

  129. A Task Parameter Inference Framework for Real-Time Embedded Systems
  130. Namyong Jung, Hyeongboo Baek, and Jinkyu Lee
    Electronics, Volume 8, Issue 2, pp. 116:1-15, Feburary 2019
    Journal Paper

    Abstract

    While recent studies addressed security attacks in real-time embedded systems, most of them assumed prior knowledge of parameters of periodic tasks, which is not realistic under many environments. In this paper, we address how to infer task parameters, from restricted information obtained by simple system monitoring. To this end, we first develop static properties that are independent of inference results and therefore applied only once in the beginning. We further develop dynamic properties each of which can tighten inference results by feeding an update of the inference results obtained by other properties. Our simulation results demonstrate that the proposed inference framework infers task parameters for RM (Rate Monotonic) with reasonable tightness; the ratio of exactly inferred task periods is 95.3% and 65.6%, respectively with low and high task set use. The results also discover that the inference performance varies with the monitoring interval length and the task set use.


    Bibtex


    Journal Information

    ISSN: 2079-9292

  131. Incorporating Zero-Laxity Policy into Mixed-Criticality Multiprocessor Real-Time Systems
  132. Namyong Jung, Hyeongboo Baek, Donghyouk Lim and Jinkyu Lee
    IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, Volume E101-A, Issue 11, pp. 1888-1899, November 2018
    Journal Paper

    Abstract

    While conventional studies on real-time systems have mostly considered the real-time constraint of real-time systems only, recent research initiatives are trying to incorporate a security constraint into real-time scheduling due to the recognition that the violation of either of two constrains can cause catastrophic losses for humans, the system, and even environment. The focus of most studies, however, is the single-criticality systems, while the security of mixed-criticality systems has received scant attention, even though security is also a critical issue for the design of mixed-criticality systems. In this paper, we address the problem of the information leakage that arises from the shared resources that are used by tasks with different security-levels of mixed-criticality systems. We define a new concept of the security constraint employing a pre-flushing mechanism to cleanse the state of shared resources whenever there is a possibility of the information leakage regarding it. Then, we propose a new non-preemptive real-time scheduling algorithm and a schedulability analysis, which incorporate the security constraint for mixed-criticality systems. Our evaluation demonstrated that a large number of real-time tasks can be scheduled without a significant performance loss under a new security constraint.


    Bibtex


    Journal Information

    ISSN: 0916-8532

  133. Proof and Evaluation of Improved Slack Reclamation for Response Time Analysis of Real-Time Multiprocessor Systems
  134. Hyeongboo Baek, Donghyouk Lim and Jinkyu Lee
    IEICE Transactions on Information and Systems, Volume E101-D, Issue. 8, pp. 2136-2140, August 2018
    Journal Paper

    Abstract

    RTA (Response time analysis) is a popular technique to guarantee timing requirements for a real-time system, and therefore the RTA framework has been widely studied for popular scheduling algorithms such as EDF (Earliest Deadline First) and FP (Fixed Priority). While a number of extended techniques of RTA have been introduced, some of them cannot be used since they have not been proved and evaluated in terms of their correctness and empirical performance. In this letter, we address the state of the art technique of slack reclamation of the existing generic RTA framework for multiprocessors. We present its mathematical proof of correctness and empirical performance evaluation, which have not been revealed to this day.


    Bibtex


    Journal Information

    ISSN: 0916-8532

  135. Real-Time Uniprocessor Scheduling with Fewer Preemptions
  136. Jinkyu Lee
    Computing, Volume 99, Issue 12, pp. 1257-1270, December 2017
    Journal Paper

    Abstract

    In this paper, we propose a simple, but effective scheduling framework for EDF and RM, which reduces the number of preemptions by simply introducing a dummy task. We first observe useful preemption behavior under EDF and RM, leading to an interesting finding: an effective way to reduce the number of preemptions is to prevent jobs of a task with the smallest task period from preempting other jobs upon their release. To achieve this, we add a dummy task that invokes its job only when a newly-released job of the task with the smallest task period has a higher priority than the currently-executing job. Then, the currently-executing job can continue its execution without getting preempted by inheriting the priority of the dummy job. Since adding the dummy task can make a schedulable task set unschedulable, we propose how to set the dummy task's parameters without compromising schedulability. In addition to the negligible overhead of this framework due to its simplicity, it holds an important property that does not increase the number of preemptions of any task set, compared to the original scheduling algorithm, which has not been achieved by existing studies. We also demonstrate via simulation that the proposed framework effectively reduces the number of preemptions under EDF and RM.


    Bibtex


    Journal Information

    ISSN: 0010-485X

  137. Incorporating Security Constraints into Mixed-Criticality Real-Time Scheduling
  138. Hyeongboo Baek and Jinkyu Lee
    IEICE Transactions on Information and Systems, Volume E100-D, Issue. 9, pp. 2068-2080, September 2017
    Journal Paper

    Abstract

    While conventional studies on real-time systems have mostly considered the real-time constraint of real-time systems only, recent research initiatives are trying to incorporate a security constraint into real-time scheduling due to the recognition that the violation of either of two constrains can cause catastrophic losses for humans, the system, and even environment. The focus of most studies, however, is the single-criticality systems, while the security of mixed-criticality systems has received scant attention, even though security is also a critical issue for the design of mixed-criticality systems. In this paper, we address the problem of the information leakage that arises from the shared resources that are used by tasks with different security-levels of mixed-criticality systems. We define a new concept of the security constraint employing a pre-flushing mechanism to cleanse the state of shared resources whenever there is a possibility of the information leakage regarding it. Then, we propose a new non-preemptive real-time scheduling algorithm and a schedulability analysis, which incorporate the security constraint for mixed-criticality systems. Our evaluation demonstrated that a large number of real-time tasks can be scheduled without a significant performance loss under a new security constraint.


    Bibtex


    Journal Information

    ISSN: 0916-8532

  139. Real-Time Scheduling for Preventing Information Leakage with Preemption Overheads
  140. Hyeongboo Baek, Jinkyu Lee, Jaewoo Lee, Pyung Kim and Brent Byunghoon Kang
    Advances in Electrical and Computer Engineering, Volume 17, Issue 2, pp. 123-132, May 2017
    Journal Paper

    Abstract

    Real-time systems (RTS) are characterized by tasks executing in a timely manner to meet its deadlines as a real-time constraint. Most studies of RTS have focused on these criteria as primary design points. However, recent increases in security threats to various real-time systems have shown that enhanced security support must be included as an important design point, retro-fitting such support to existing systems as necessary. In this paper, we propose a new pre-flush technique referred to as flush task reservation for FP scheduling (FTRFP) to conditionally sanitize the state of resources shared by real-time tasks by invoking a flush task (FT) in order to mitigate information leakage/corruption of real-time systems. FTR-FP extends existing works exploiting FTs to be applicable more general scheduling algorithms and security model. We also propose modifications to existing real-time scheduling algorithms to implement a pre-flush technique as a security constraint, and analysis technique to verify schedulability of the real-time scheduling. For better analytic capability, our analysis technique provides a count of the precise number of preemptions that a task experiences offline. Our evaluation results demonstrate that our proposed schedulability analysis improves the performance of existing scheduling algorithms in terms of schedulability and preemption cost.


    Bibtex


    Journal Information

    ISSN: 1582-7445

  141. Channel and Timeslot Co-Scheduling with Minimal Channel Switching for Data Aggregation in MWSNs
  142. Sanggil Yeoum, Byungseok Kang, Jinkyu Lee, and Hyunseung Choo
    Sensors, Volume 17, Issue 5, pp. 1-16, May 2017
    Journal Paper

    Abstract

    Collision-free transmission and efficient data transfer between nodes can be achieved through a set of channels in multichannel wireless sensor networks (MWSNs). While using multiple channels, we have to carefully consider channel interference, channel and time slot (resources) optimization, channel switching delay, and energy consumption. Since sensor nodes operate on low battery power, the energy consumed in channel switching becomes an important challenge. In this paper, we propose channel and time slot scheduling for minimal channel switching in MWSNs, while achieving efficient and collision-free transmission between nodes. The proposed scheme constructs a duty-cycled tree while reducing the amount of channel switching. As a next step, collision-free time slots are assigned to every node based on the minimal data collection delay. The experimental results demonstrate that the validity of our scheme reduces the amount of channel switching by 17.5%, reduces energy consumption for channel switching by 28%, and reduces the schedule length by 46%, as compared to the existing schemes.


    Bibtex


    Journal Information

    ISSN: 1424-8220

  143. Discharge Scheduling for Voltage Balancing in Reconfigurable Battery Systems
  144. Dongwan Kim and Jinkyu Lee
    Electronics Letters, Volume 53, Issue 7, pp. 496-498, March 2017
    Journal Paper

    Abstract

    Collision-free transmission and efficient data transfer between nodes can be achieved through a set of channels in multichannel wireless sensor networks (MWSNs). While using multiple channels, we have to carefully consider channel interference, channel and time slot (resources) optimization, channel switching delay, and energy consumption. Since sensor nodes operate on low battery power, the energy consumed in channel switching becomes an important challenge. In this paper, we propose channel and time slot scheduling for minimal channel switching in MWSNs, while achieving efficient and collision-free transmission between nodes. The proposed scheme constructs a duty-cycled tree while reducing the amount of channel switching. As a next step, collision-free time slots are assigned to every node based on the minimal data collection delay. The experimental results demonstrate that the validity of our scheme reduces the amount of channel switching by 17.5%, reduces energy consumption for channel switching by 28%, and reduces the schedule length by 46%, as compared to the existing schemes.


    Bibtex


    Journal Information

    ISSN: 0013-5194

  145. New response time analysis for global EDF on a multiprocessor platform
  146. Jinkyu Lee
    Journal of Systems Architecture, Volume 65, pp. 59-63, April 2016
    Journal Paper

    Abstract

    Time-predictability is the most important requirement for a real-time system, and researchers have therefore paid attention to the duration between the arrival and completion of a real-time task, called response time. RTA (Response Time Analysis) studies, however, rely on the same technique, yielding room for further improvement, especially regarding multiprocessor platforms. For this paper, we investigated the properties of an existing utilization-based schedulability analysis for global EDF (Earliest Deadline First) on a multiprocessor platform, and developed a new RTA technique based on the corresponding properties, which calculates the response times of tasks in task sets deemed schedulable by the existing analysis. We demonstrated through simulations that our proposed RTA technique not only calculates response times that are less pessimistic than those of the existing approach, but also successfully derives response times that cannot be obtained by the existing approach.


    Bibtex


    Journal Information

    ISSN: 1383-7621

  147. Limited Carry-in Technique for Real-Time Multi-Core Scheduling
  148. Jinkyu Lee and Insik Shin
    Journal of Systems Architecture, Volume 59, Issue 7, pp. 372-375, August 2013
    Journal Paper

    Abstract

    Schedulability analysis has been widely studied to provide offline timing guarantees for a set of real-time tasks. The so-called limited carry-in technique, which can be orthogonally incorporated into many different multi-core schedulability analysis methods, was originally introduced for Earliest Deadline First (EDF) scheduling to derive a tighter bound on the amount of interference of carry-in jobs at the expense of investigating a pseudo-polynomial number of intervals. This technique has been later adapted for Fixed-Priority (FP) scheduling to obtain the carry-in bound efficiently by examining only one interval, leading to a significant improvement in multi-core schedulability analysis. However, such a successful result has not yet been transferred to any other non-FP scheduling algorithms. Motivated by this, this paper presents a generic limited carry-in technique that is applicable to any work-conserving algorithms. Specifically, this paper derives a carry-in bound in an algorithm-independent manner and demonstrates how to apply the bound to existing non-FP schedulability analysis methods for better schedulability.


    Bibtex


    Journal Information

    ISSN: 1383-7621

  149. Avoiding Collision with Hidden Nodes in IEEE 802.11 Wireless Networks
  150. Jinkyu Lee and Ikjun Yeom
    IEEE Communications Letters, Volume 13, Issue 10, pp. 743-745, October 2009
    Journal Paper

    Abstract

    In wireless networks, collision is a major factor of performance degradation. In this letter, we propose a scheme for reducing collision in IEEE 802.11 networks. Each node can avoid collision by maintaining a disjoint set of time slots for transmission. Through simulation, we show that the proposed scheme is effective to reduce collision even in the presence of hidden nodes.


    Bibtex


    Journal Information

    ISSN: 1089-7798

  151. Response Time Analysis of COTS-Based Multicores Considering the Contention on the Shared Memory Bus
  152. Dakshina Dasari, Bjorn Andersson, Vincent Nelis, Stefan M. Petters, Arvind Easwaran and Jinkyu Lee
    The 8th IEEE International Conference on Embedded Software and Systems (ICESS), pp. 1068-1075, Changsha, China, November 2011
    Conference Paper

    Abstract

    The current industry trend is towards using Commercially available Off-The-Shelf (COTS) based multicores for developing real-time embedded systems, as opposed to the usage of custom-made hardware. In typical implementation of such COTS-based multicores, multiple cores access the main memory via a shared bus. This often leads to contention on this shared channel, which results in an increase of the response time of the tasks. Analyzing this increased response time, considering the contention on the shared bus, is challenging on COTS-based systems mainly because bus arbitration protocols are often undocumented and the exact instants at which the shared bus is accessed by tasks are not explicitly controlled by the operating system scheduler; they are instead a result of cache misses. This paper makes three contributions towards analyzing tasks scheduled on COTS-based multicores. Firstly, we describe a method to model the memory access patterns of a task. Secondly, we apply this model to analyze the worstcase response time for a set of tasks. Although the required parameters to obtain the request profile can be obtained by static analysis, we provide an alternative method to experimentally obtain them by using performance monitoring counters (PMCs). We also compare our work against an existing approach and show that our approach outperforms it by providing tighter upper-bound on the number of bus requests generated by a task.


    Bibtex


    Conference Information

  153. Advanced Disjoint Address Allocation for Mobile Ad Hoc Networks
  154. Jinkyu Lee, Sehoon Kim and Ikjun Yeom
    The 66th IEEE Vehicular Technology Conference (VTC), pp. 304-308, Baltimore, MD, USA, October 2007
    Conference Paper

    Abstract

    Regarding to address allocation, a mobile ad hoc network (MANET) may suffer from the lack of address and network partition/merging due to mobility of nodes. In this paper, we propose a new address allocation protocol for dealing with those problems. The proposed protocol is developed based on disjoint address set distribution with binary splitting for scalability, and provides special treatments for resolving the lack of addresses. We also present an effective technique for handling network partition and merging. Through simulation, we show that the proposed protocol is effective to allocate addresses in a MANET with reasonable latency and communication overhead.


    Bibtex


    Conference Information

  155. Towards Measuring Body Temperature Using COTS Mobile Devices
  156. Sanghoon Jun and Jinkyu Lee
    The 12th International Conference on ICT Convergence (Poster), pp. 1847-1849, Jeju Island, Republich of Korea, October 2021
    WiP Conference Paper

    Abstract

    Body temperature measurement is one of the simple, yet effective ways to diagnose a variety of diseases, and its importance is growing in the era of COVID-19. In this paper, we show feasibility of measuring body temperature using a COTS (Commercial Off-The-Shelf) mobile device. To this end, we utilize the battery temperature sensor embedded in most COTS mobile devices, and analyze how the battery temperature varies according to different temperatures of an external object that makes contact with the target mobile device (e.g., a hand holding the device). Our approach makes it possible to estimate the external object’s temperature within 0.5C of accuracy, by (i) data collection of the battery temperature variation for some pairs of the initial battery temperature and the target object temperature, (ii) virtual data generation for the other pairs, and (iii) temperature estimation via classification of the collected data and generated ones.


    Bibtex


    Conference Information

  157. Towards Grip Sensing for Commodity Smartphones Through Acoustic Signature
  158. Namhyun Kim and Jinkyu Lee
    The 2017 ACM International Conference on Pervasive and Ubiquitous Computing (Ubicomp, Poster), Maui, HI, USA, September 2017
    WiP Conference Paper

    Abstract

    While hand grips are important to understand the intent of smartphone users, existing studies on hand grip detection either require additional hardware or exhibit limitations on the type/number of grips. In this paper, we propose a novel grip sensing system that enables a smartphone to detect various user-defined hand grips without any additional hardware. Our system emits a carefully-designed (inaudible) sound signal, and records the sound signal modified by an individual grip. The recorded sound signal is transformed into a unique sound signature through feature extraction process, and then SVM (Support Vector Machine) classifies the sound signature so as to identify the signature as one of pre-defined grips. With six representative grips, we demonstrate that our system exhibits 93.0% average accuracy for ten different users. Beyond this feasibility demonstration, our ongoing work is not only to improve the accuracy, but also to adapt our system to various real environments.


    Bibtex


    Conference Information

  159. WiP Abstract: Charge Scheduling for Large-Scale Battery Management Systems
  160. Jinkyu Lee
    The 6th ACM/IEEE International Conference on Cyber-Physical Systems (ICCPS, WiP), Seattle, WA, USA, April 2015
    WiP Conference Paper

    Abstract

    A large-scale Battery Management System (BMS) used in Electric Vehicles (EVs) and energy storage systems is a typical Cyber-Physical System (CPS) application in that scheduling of battery charge, discharge, and rest (i.e., cyber part) can significantly improve BMS performance under understanding and controlling battery characteristics (i.e., physical part). Therefore, the CPS community has paid attention to BMSes, e.g., ICCPS [4, 5, 3] and the CPS track in RTSS [7, 2, 6, 1].


    Bibtex


    Conference Information

  161. Finding an Upper Bound on the Increase in Execution Time Due to Contention on the Memory Bus in COTS-Based Multicore Systems
  162. Bjorn Andersson, Arvind Easwaran, and Jinkyu Lee
    The 30th IEEE Real-Time Systems Symposium (RTSS, WiP), Washington D.C., USA, December 2009 (Invited to the special issue of RTSS WiP 2009 in ACM SIGBED Review, Volume 7, Issue 1, January 2010; Selected among the top 5 out of 24)
    WiP Conference Paper

    Abstract

    Contention on the memory bus in COTS based multi-core systems is becoming a major determining factor of the execution time of a task. Analyzing this extra execution time is non-trivial because (i) bus arbitration protocols in such systems are often undocumented and (ii) the times when the memory bus is requested to be used are not explicitly controlled by the operating system scheduler; they are instead a result of cache misses. We present a method for finding an upper bound on the extra execution time of a task due to contention on the memory bus in COTS based multicore systems. This method makes no assumptions on the bus arbitration protocol (other than assuming that it is work-conserving).


    Bibtex


    Conference Information

  163. Multiprocessor Real-Time Scheduling Considering Concurrency and Urgency
  164. Jinkyu Lee, Arvind Easwaran, Insik Shin and Insup Lee
    The 30th IEEE Real-Time Systems Symposium (RTSS, WiP), Washington D.C., USA, December 2009 (Invited to the special issue of RTSS WiP 2009 in ACM SIGBED Review, Volume 7, Issue 1, January 2010; Selected among the top 5 out of 24)
    WiP Conference Paper

    Abstract

    It has been widely studied how to schedule real-time tasks on multiprocessor platforms. Several studies find optimal scheduling policies for implicit deadline task systems, but it is hard to understand how each policy utilizes the two important aspects of scheduling real-time tasks on multiprocessors: inter-job concurrency and job urgency. In this paper, we introduce a new scheduling policy that considers these two properties. We prove that the policy is optimal for the special case when the execution time of all tasks are equally one and deadlines are implicit, and observe that the policy is a new concept in that it is not an instance of Pfair or ERfair. It remains open to find a scheduliability condition for general task systems under our scheduling policy.


    Bibtex


    Conference Information

  165. ACM SIGBED Review, Volumn 12, Number 2, April 2015
  166. Jinkyu Lee and Reinder J. Bril
    Editorial

  167. Proceedings of the 7th Workshop on Compositional Theory and Technology for Real-Time Embedded Systems (CRTS 2014), Rome, Italy, December 2014
  168. Reinder J. Bril and Jinkyu Lee
    Editorial

Disclaimer:

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.