Research Interests

 

Current Research Projects


1)   Zygaria: storage performance as a managed resource

a) As a research intern with IBM, I focused on QoS support and performance management for storage
systems. 

b)  I also designed and implemented an improved I/O scheduling algorithm for IBM Kybos project.

 

2)   New: RBED scheduler for Linux 2.6

a) We have implemented a newer version of RBED in Linux 2.6 kernel. The patch to the 2.6.8.1 kernel is
available here. Before you download and apply the patch, please read the license here. After you have
patched the kernel, please read the Documentation/rbed.txt for help.

b)   Example workload is available here.


3)   BACKSLASH: Efficient resource allocation and reclamation for improving application performance in an
    integrated system

a)   Slack time management in  an integrated system

We schedule BE processes as SRT processes by assigning pseudo periods to them. With a pseudo deadline advancing mechanism, the BE processes could use up the slack time left by RT processes, while still maintain the feasibility of the processes. However, in RBED the SRT processes do not take advantage of the slack time left by other RT processes.

b)   SLASH = SLAD + CASH: Improving best-effort and soft real-time performance with better slack reclamation

i)                i) SLAD

•         Donates slack as soon as it is available

•         Donates slack to the process with the earliest deadline

•         Enabled by RBED rate enforcement

ii)             ii) CASH (extension to CBS) and RBED

•         Releases next job as soon as current job completes

•         Allows processes to ˇ°borrowˇ± from subsequent jobs

•         BUT, lowers EDF priority of needy tasks, reducing effectiveness

iii)            iIi) SLASH combines the best of both

•         Donates early, according to EDF

•         Allows ˇ°borrowingˇ± from future jobs


 

4)   RBED: Design, model and develop an integrated real-time system that simultaneously supports hard real-time, soft real-time and best-effort processes.

a)   RBED framework and scheduler

Resource-rate Based Earliest Deadline first scheduler (RBED) is a real-time scheduler, which consists of two independent components: a rate-based resource allocation policy and an EDF scheduling algorithm. RBED provides uniform scheduling for hard real-time (HRT), soft real-time (SRT), and non-real-time (Best-Effort) processes.

  • Basic Idea

•         EDF provides hard guarantees

•         Varying rates and periods provide flexibility

•         Programmable timer interrupts guarantee isolation between processes

  • RBED policy

•         Resource allocation: Target rate-of-progress for each process (S <= 100%)

•         Dispatching: Period based on process timeliness needs

  • RBED mechanism

•         Rate-Enforcing EDF: EDF + programmable timer interrupts (microseconds granularity)

 

 

b)   Soft real-time processing in RBED

i)    RBED supports multiple soft real-time classes, including missed-deadline soft real-time (MDSRT), resource allocation soft real-time (RASRT), rate-based real-time (RBRT), etc

ii) We are working on integrating firm real-time (FRT) into the RBED framework.

 

c)   Implementation of RBED

i)    We have implemented RBED in Linux 2.4 kernel. The patch to the 2.4.20 kernel is available here. In addition,
I have provided a README file for playing the scheduler.

ii) To test the functionality and performance of the RBED, we have implemented seven system calls for the RBED scheduler. The detailed description of these system calls is available here.

iii) Example workload is available here.

 

d)   Performance evaluation of RBED

There is no unique and optimal quality metric to measure the performance of a real-time scheduler. The basic metrics should demonstrate the overall performance of the scheduler, the performance of scheduling hard real-time and soft real-time processes, and the performance of scheduling BE processes under various workloads. We use two schedulers, Linux scheduler and edf/linux scheduler, as comparisons to RBED. The edf/linux scheduler schedules real-time processes with EDF algorithm, but schedules Best Effort (BE) processes with the Linux round-robin time sharing scheduling algorithm, i.e. BE processes run in background.

 

The performance results demonstrate RBED's feasibility (in underloaded situations) and flexibility (in overloaded situations) for fully integrated scheduling of HRT, SRT, and non-real-time processes. RBED achieved better performance in scheduling SRT processes than that of Linux scheduler, and better performance in scheduling BE processes than that of edf/linux scheduler.

 

 

5)   Adaptive Resource Allocation for Control System  (already integrated into and implemented in RBED scheduler)




Previous Research Projects

1)   RA/S model

a)    CPU Scheduling consists of two independent components: Resource Allocation and Scheduling (RA/S). RA/S model has the potential to provide true Application-Specific Real-Time processing.

b)    To verify the RA/S model, we have preliminarily implemented the RBED in Linux 2.4 kernel. The results show that the RA/S model is promising, while improving Linux support for real-time applications.

2)   OBFS

a)    Preliminary implementation of OBFS in Linux 2.4.9. OBFS (Object-Based File System) is a new File System designed for OBSD (Object-Based Storage Device) .