Browsing by Author "Back, Godmar V."

Now showing 1 - 20 of 47
  • Thumbnail Image
    Analysis and Abstraction of Parallel Sequence Search
    Goddard, Christopher Joseph (Virginia Tech, 2007-09-05)
    The ability to compare two biological sequences is extremely valuable, as matches can suggest evolutionary origins of genes or the purposes of particular amino acids. Results of such comparisons can be used in the creation of drugs, can help combat newly discovered viruses, or can assist in treating diseases. Unfortunately, the rate of sequence acquisition is outpacing our ability to compute on these data. Further, traditional dynamic programming algorithms are too slow to meet the needs of biologists, who wish to compare millions of sequences daily. While heuristic algorithms improve upon the performance of these dated applications, they still cannot keep up with the steadily expanding search space. Parallel sequence search implementations were developed to address this issue. By partitioning databases into work units for distributed computation, applications like mpiBLAST are able to achieve super-linear speedup over their sequential counterparts. However, such implementations are limited to clusters and require significant effort to work in a grid environment. Further, their parallelization strategies are typically specific to the target sequence search, so future applications require a reimplementation if they wish to run in parallel. This thesis analyzes the performance of two versions of mpiBLAST, noting trends as well as differences between them. Results suggest that these embarrassingly parallel applications are dominated by the time required to search vast amounts of data, and not by the communication necessary to support such searches. Consequently, a framework named gridRuby is introduced which alleviates two main issues with current parallel sequence search applications; namely, the requirement of a tightly knit computing environment and the specific, hand-crafted nature of parallelization. Results show that gridRuby can parallelize an application across a set of machines through minimal implementation effort, and can still exhibit super-linear speedup.
  • Thumbnail Image
    Automated Adaptive Software Maintenance: A Methodology and Its Applications
    Tansey, Wesley (Virginia Tech, 2008-05-22)
    In modern software development, maintenance accounts for the majority of the total cost and effort in a software project. Especially burdensome are those tasks which require applying a new technology in order to adapt an application to changed requirements or a different environment. This research explores methodologies, techniques, and approaches for automating such adaptive maintenance tasks. By combining high-level specifications and generative techniques, a new methodology shapes the design of approaches to automating adaptive maintenance tasks in the application domains of high performance computing (HPC) and enterprise software. Despite the vast differences of these domains and their respective requirements, each approach is shown to be effective at alleviating their adaptive maintenance burden. This thesis proves that it is possible to effectively automate tedious and error-prone adaptive maintenance tasks in a diverse set of domains by exploiting high-level specifications to synthesize specialized low-level code. The specific contributions of this thesis are as follows: (1) a common methodology for designing automated approaches to adaptive maintenance, (2) a novel approach to automating the generation of efficient marshaling logic for HPC applications from a high-level visual model, and (3) a novel approach to automatically upgrading legacy enterprise applications to use annotation-based frameworks. The technical contributions of this thesis have been realized in two software tools for automated adaptive maintenance: MPI Serializer, a marshaling logic generator for MPI applications, and Rosemari, an inference and transformation engine for upgrading enterprise applications. This thesis is based on research papers accepted to IPDPS '08 and OOPSLA '08.
  • Thumbnail Image
    Bug Finding Methods for Multithreaded Student Programming Projects
    Naciri, William Malik (Virginia Tech, 2017-08-04)
    The fork-join framework project is one of the more challenging programming assignments in the computer science curriculum at Virginia Tech. Students in Computer Systems must manage a pool of threads to facilitate the shared execution of dynamically created tasks. This project is difficult because students must overcome the challenges of concurrent programming and conform to the project's specific semantic requirements. When working on the project, many students received inconsistent test results and were left confused when debugging. The suggested debugging tool, Helgrind, is a general-purpose thread error detector. It is limited in its ability to help fix bugs because it lacks knowledge of the specific semantic requirements of the fork-join framework. Thus, there is a need for a special-purpose tool tailored for this project. We implemented Willgrind, a debugging tool that checks the behavior of fork-join frameworks implemented by students through dynamic program analysis. Using the Valgrind framework for instrumentation, checking statements are inserted into the code to detect deadlock, ordering violations, and semantic violations at run-time. Additionally, we extended Willgrind with happens-before based checking in WillgrindPlus. This tool checks for ordering violations that do not manifest themselves in a given execution but could in others. In a user study, we provided the tools to 85 students in the Spring 2017 semester and collected over 2,000 submissions. The results indicate that the tools are effective at identifying bugs and useful for fixing bugs. This research makes multithreaded programming easier for students and demonstrates that special-purpose debugging tools can be beneficial in computer science education.
  • Thumbnail Image
    Capacity Characterization of Multi-Hop Wireless Networks- A Cross Layer Approach
    Chafekar, Deepti Ramesh (Virginia Tech, 2009-03-11)
    A fundamental problem in multi-hop wireless networks is to estimate their throughout capacity. The problem can be informally stated as follows: given a multi-hop wireless network and a set of source destination pairs, determine the maximum rate r at which data can be transmitted between each source destination pair. Estimating the capacity of a multi-hop wireless network is practically useful --- it yields insights into the fundamental performance limits of the wireless network and at the same time aids the development of protocols that can utilize the network close to this limit. A goal of this dissertation is to develop rigorous mathematical foundations to compute the capacity of any given multi-hop wireless network with known source-destination pairs. An important factor that affects the capacity of multi-hop wireless networks is radio interference. As a result, researchers have proposed increasingly realistic interference models that aim to capture the physical characteristics of radio signals. Some of the commonly used simple models that capture radio interference are based on geometric disk-graphs. The simplicity of these models facilitate the development of provable and often conceptually simple methods for estimating the capacity of wireless networks. A potential weakness of this class of models is that they oversimplify the physical process by assuming that the signal ends abruptly at the boundary of a geometric region (a disk for omni-directional antennas). A more sophisticated interference model is the physical interference model, also known as the Signal to Interference Plus Noise Ratio (SINR) model. This model is more realistic than disk-graph models as it captures the effects of signal fading and ambient noise. This work considers both disk-graph and SINR interference models. In addition to radio interference, the throughput capacity of a multi-hop wireless network also depends on other factors, including the specific paths selected to route the packets between the source destination pairs (routing), the time at which packets are transmitted (scheduling), the power with which nodes transmit (power control) and the rate at which packets are injected (rate control). In this dissertation, we consider three different problems related to estimating network capacity. We propose an algorithmic approach for solving these problems. We first consider the problem of maximizing throughput with the SINR interference model by jointly considering the effects of routing and scheduling constraints. Second, we consider the problem of maximizing throughput by performing adaptive power control, scheduling and routing for disk-graph interference models. Finally, we examine the problem of minimizing end-to-end latency by performing joint routing, scheduling and power control using the SINR interference model. Recent results have shown that traditional layered networking principles lead to inefficient utilization of resources in multi-hop wireless networks. Motivated by these observations, recent papers have begun investigating cross-layer design approaches. Although our work does not develop new cross-layered protocols, it yields new insights that could contribute to the development of such protocols in the future. Our approach for solving these multi-objective optimization problems is based on combining mathematical programming with randomized rounding to obtain polynomial time approximation algorithms with provable worst case performance ratios. For the problems considered in this work, our results provide the best analytical performance guarantees currently known in the literature. We complement our rigorous theoretical and algorithmic analysis with simulation-based experimental analysis. Our experimental results help us understand the limitations of our approach and assist in identifying certain parameters for improving the performance of our techniques.
  • Thumbnail Image
    The Client Insourcing Refactoring to Facilitate the Re-engineering of Web-Based Applications
    An, Kijin (Virginia Tech, 2021-05-19)
    Developers often need to re-engineer distributed applications to address changes in requirements, made only after deployment. Much of the complexity of inspecting and evolving distributed applications lies in their distributed nature, while the majority of mature program analysis and transformation tools works only with centralized software. Inspired by business process re-engineering, in which remote operations can be insourced back in house to restructure and outsource anew, this dissertation brings an analogous approach to the re-engineering of distributed applications. Our approach introduces a novel automatic refactoring---Client Insourcing---that creates a semantically equivalent centralized version of a distributed application. This centralized version is then inspected, modified, and redistributed to meet new requirements. This dissertation demonstrates the utility of Client Insourcing in helping meet the changed requirements in performance, reliability, and security. We implemented Client Insourcing in the important domain of full-stack JavaScript applications, in which both the client and server parts are written in JavaScript, and applied our implementation to re-engineer mobile web applications. Client Insourcing reduces the complexity of inspecting and evolving distributed applications, thereby facilitating their re-engineering. This dissertation is based on 4 conference papers and 2 doctoral symposium papers, presented at ICWE 2019, SANER 2020, WWW 2020, and ICWE 2021.
  • Thumbnail Image
    The CloudBrowser Web Application Framework
    McDaniel, Brian Newsom (Virginia Tech, 2012-05-02)
    While more and more applications are moving from the desktop to the web, users still expect their applications to behave like they did on the desktop. Specifically, users expect that user interface state is preserved across visits, and that the state of the interface truly reflects the state of the underlying data. Unfortunately, achieving this ideal is difficult for web application developers due to the distributed nature of the web. Modern AJAX applications rely on asynchronous network programming to synchronize the client-side user interface with server-side data. Furthermore, since the HTTP protocol is stateless, preserving interface state across visits requires a significant amount of manual work on behalf of the developer. CloudBrowser is a web application framework that supports the development of rich Internet applications whose entire user interface and application logic resides on the server, while all client/server communication is provided by the framework. CloudBrowser is ideal for single- page web applications, which is the current trend in web development. CloudBrowser thus hides the distributed nature of these applications from the developer, creating an environment similar to that provided by a desktop user interface library. CloudBrowser preserves the user interface state in a server-side virtual browser that is maintained across visits. Further- more, multiple clients can connect to a single server-side interface instance, providing built-in co-browsing support. Unlike other server-centric frameworks, CloudBrowser's exclusive use of the HTML document model and associated JavaScript execution environment allows it to exploit existing client-side user interface libraries and toolkits while transparently providing access to other application tiers. We have implemented a prototype of CloudBrowser as well as several example applications to demonstrate the benefits of its server-centric design.
  • Thumbnail Image
    CloudSpace: A Web Development Environment for CS1 Courses
    Woods, Michael John (Virginia Tech, 2011-05-03)
    Since a massive decline of computer science graduates in 2002, computer science departments have been unable to reach previous graduation rates. In wake of this dramatic loss of graduates, researchers have been searching for the reasons students are avoiding computer science and choosing other majors. To combat this decrease in computer science graduates, the CloudSpace environment pro- vides additional context to entry level computer science courses. This shift in context re- moves boring assignments from the early computer science curriculum and replaces them with more engaging web centric assignments. The CloudSpace environment presents a model that maintains student's focus on core computer science competencies while providing a highly simplified web development toolkit to develop feature rich AJAX web applications. This the- sis includes the rational and implementation of a cloud based hosting service and a highly abstracted web tool kit that enables students to replicate modern web applications.
  • Thumbnail Image
    Concept-Oriented Design in Chasm: Conversational Domain Language Inspired 3D User Interface Design and Development
    Wingrave, Chadwick A. (Virginia Tech, 2008-07-11)
    In my experience, novel ideas for 3D interaction techniques greatly outpace developers' ability to implement them, despite the potential benefit of these ideas. I believe this is due to the inherent implementation complexity of 3D interfaces, without sufficient support from methods and tools. Believing a developer-centric representation could overcome this problem, I investigated developer practices, artifacts and language. This resulted in the theory of Concept-Oriented Design and Chasm, a prototype realization of the theory. The key feature of Concept-Oriented Design is its use of developer-centric representations to create a multi-tiered implementation, ranging from an envisioned behavior expressed in conversational language to low-level code. Evaluation of Chasm by domain experts and its use in multiple case studies by volunteer developers has demonstrated that Concept-Oriented Design in Chasm addresses many of the problems of 3D design and development.
  • Thumbnail Image
    COPS: A Framework for Consumer Oriented Proportional-share Scheduling
    Deodhar, Abhijit Anant (Virginia Tech, 2007-05-14)
    Scheduling forms an important aspect of operating systems because it has a direct impact on system performance. Most existing general-purpose schedulers use a priority-based scheme to schedule processes. Such priority-based mechanisms cannot guarantee proportional fairness for every process. Proportional share schedulers maintain fairness among tasks based on given weight values. In both of these scheduler types, the scheduling decision is done per-process. However, system usage policies are typically set on a per-consumer basis, where a consumer represents a group of related processes that may belong to the same application or user. The COPS framework uses the idea of consumer sets to group processes. Its design guarantees system usage per consumer, based on relative weights. We have added a share management layer on top of a proportional share scheduler to ease the administrative job of share assignment for these consumer sets. We have evaluated our system in real world scenarios and show that the CPU usage for consumer sets with CPU-bound processes complies with the administrator-defined policy goals.
  • Thumbnail Image
    Design and Implementation of An Emulation Testbed for Video Communications in Ad Hoc Networks
    Wang, Xiaojun (Virginia Tech, 2006-01-11)
    Video communication is an important application in wireless ad hoc network environment. Although current off-the-shelf video communication software would work for ad hoc network operating under stable conditions (e.g., extremely low link and node failures), video communications for ad hoc network operating under extreme conditions remain a challenging problem. This is because traditional video codec, either single steam or layered video, requires at least one relatively stable path between source and destination nodes. Recent advances in multiple description (MD) video coding have opened up new possibilities to offer video communications over ad hoc networks. In this thesis, we perform a systematic study on MD video for ad hoc networks. The theoretical foundation of this research is based on an application-centric approach to formulate a cross-layer multipath routing problem that minimizes the application layer video distortion. The solution procedure to this complex optimization problem is based on the so-called Genetic Algorithm (GA). The theoretical results have been documented in [7] and will be reviewed in Chapter 2. Although the theoretical foundation for MD video over dynamic ad hoc networks has been laid, there remains a lot of skepticisms in the research community on whether such cross-layer optimal routing can be implemented in practice. To fill this gap, this thesis is devoted to the experimental research (or proof-of-concept) for the work in [7]. Our approach is to design and implement an emulation testbed where we can actually implement the ideas and algorithms proposed in [7] in a controlled laboratory setting. The highlights of our experimental research include: 1. A testbed that emulates three properties of a wireless ad hoc network: topology, link success probability, and link bandwidth; 2. A source routing implementation that can easily support comparative study between the proposed GA-based routing with other routing schemes under different network conditions; 3. A modified H.263+ video codec that employs Unequal Error Protection (UEP) approach to generate MD video; 4. Implementation of three experiments that • compared the GA-based routing with existing technologies (NetMeeting video conferencing plus AODV routing); • compared our GA-based routing with network-centric routing schemes (two-disjoint paths routing); • proved that our approach has great potential in supporting video communications in wireless ad hoc networks. 5. Experimental results that show the proposed cross-layer optimization significantly outperforms the current off-the-shelf technologies, and that the proposed cross-layer optimization provides much better performance than network-centric routing schemes in supporting routing of MD video. In summary, the experimental research in this thesis has demonstrated that a cross-layer multipath routing algorithm can be practically implemented in a dynamic ad hoc network to support video communications.
  • Thumbnail Image
    Design and Implementation of the FINS Framework: Flexible Internetwork Stack
    Reed, Jonathan Michael (Virginia Tech, 2014-06-29)
    This thesis describes the Flexible Internetwork Stack (FINS) Framework, an open-source tool to facilitate experimental research in wireless networks on multiple platforms. The FINS Framework uses a module-based architecture that allows cross-layer behavior and runtime reconfiguration of the protocol stack. Version 1.0 of the framework makes use of existing physical and data link layer functionality, while enabling modifications to the stack at the network layer and above, or even the implementation of a clean-slate, non-layered protocol architecture. Protocols, stubs for communicating with intact layers, and management and supervisory functions are implemented as FINS Framework modules, interconnected by a central switch. This thesis describes the FINS Framework architecture, presents an initial assessment along with experiments on Android and Ubuntu enabled by the tool, and documents an intuitive mechanism for transparently intercepting socket calls that maintains efficiency and flexibility.
  • Thumbnail Image
    Design and Implementation of the VirtuOS Operating System
    Nikolaev, Ruslan (Virginia Tech, 2014-01-21)
    Most operating systems provide protection and isolation to user processes, but not to critical system components such as device drivers or other systems code. Consequently, failures in these components often lead to system failures. VirtuOS is an operating system that exploits a new method of decomposition to protect against such failures. VirtuOS exploits virtualization to isolate and protect vertical slices of existing OS kernels in separate service domains. Each service domain represents a partition of an existing kernel, which implements a subset of that kernel's functionality. Service domains directly service system calls from user processes. VirtuOS exploits an exceptionless model, avoiding the cost of a system call trap in many cases. We illustrate how to apply exceptionless system calls across virtualized domains. To demonstrate the viability of VirtuOS's approach, we implemented a prototype based on the Linux kernel and Xen hypervisor. We created and evaluated a network and a storage service domain. Our prototype retains compatibility with existing applications, can survive the failure of individual service domains while outperforming alternative approaches such as isolated driver domains and even exceeding the performance of native Linux for some multithreaded workloads. The evaluation of VirtuOS revealed costs due to decomposition, memory management, and communication, which necessitated a fine-grained analysis to understand their impact on the system's performance. The interaction of virtual machines with multiple underlying software and hardware layers in virtualized environment makes this task difficult. Moreover, performance analysis tools commonly used in native environments were not available in virtualized environments. Our work addresses this problem to enable an in-depth performance analysis of VirtuOS. Our Perfctr-Xen framework provides capabilities for per-thread analysis with both accumulative event counts and interrupt-driven event sampling. Perfctr-Xen is a flexible and generic tool, supports different modes of virtualization, and can be used for many applications outside of VirtuOS.
  • Thumbnail Image
    Development and Analysis of a Spiral Theory-based Cybersecurity Curriculum
    Back, Godmar V.; Basu, Debarati; Naciri, William; Lohani, Vinod K.; Plassmann, Paul E.; Barnette, Dwight; Ribbens, Calvin J.; Gantt, Kira; McPherson, David (2017-01-09)
    Enhance cybersecurity learning experiences of students at Virginia Tech’s large engineering program
  • Thumbnail Image
    The Distributed Open Network Emulator: Applying Relativistic Time
    Bergstrom, Craig Casey (Virginia Tech, 2006-05-15)
    The increasing scale and complexity of network applications and protocols motivates the need for tools to aid in the understanding of network dynamics at similarly large scales. While current network simulation tools achieve large scale modeling, they do so by ignoring much of the intra-program state that plays an important role in the overall system's behavior. This work presents The Distributed Open Network Emulator, a scalable distributed network model that incorporates application program state to achieve high fidelity modeling. The Distributed Open Network Emulator, or DONE for short, is a parallel and distributed network simulation-emulation hybrid that achieves both scalability and the capability to run existing application code with minimal modification. These goals are accomplished through the use of a protocol stack extracted from the Linux kernel, a new programming model based on C, and a scaled real-time method for distributed synchronization. One of the primary challenges in the development of DONE was in reconciling the opposing requirements of emulation and simulation. Emulated code directly executes in real-time which progresses autonomously. In contrast, simulation models are forced ahead by the execution of events, an explicitly controlled mechanism. Relativistic time is used to integrate these two paradigms into a single model while providing efficient distributed synchronization. To demonstrate that the model provides the desired traits, a series of experiments are described. They show that DONE can provide super-linear speedup on small clusters, nearly linear speedup on moderate sized clusters, and accurate results when tuned appropriately.
  • Thumbnail Image
    Engineering News : Spring 2015
    Nystrom, Lynn; Haugh, Lindsey; Simpkins, David (Virginia Tech. College of Engineering, 2015)
    In fall 2011, ground was broken for the Signature Engineering Building, a dream project of current engineering Dean Richard C. Benson and Virginia Tech President Emeritus and former College of Engineering Dean Paul Torgersen. After three years of construction, the Hokie-stone-adorned, $95.2 million structure opened in August 2014 to welcome students to new classes (See Page 8) and weeks later was renamed to honor the philanthropy of longtime Virginia Tech supporters Alice and Bill Goodwin.
  • Thumbnail Image
    An Evaluation of the Linux Virtual Memory Manager to Determine Suitability for Runtime Variation of Memory
    Muthukumaraswamy Sivakumar, Vijay (Virginia Tech, 2007-02-02)
    Systems that support virtual memory virtualize the available physical memory such that the applications running on them operate under the assumption that these systems have a larger amount of memory available than is actually present. The memory managers of these systems manage the virtual and the physical address spaces and are responsible for converting the virtual addresses used by the applications to the physical addresses used by the hardware. The memory managers assume that the amount of physical memory is constant and does not change during their period of operation. Some operating scenarios however, such as the power conservation mechanisms and virtual machine monitors, require the ability to vary the physical memory available at runtime, thereby making invalid the assumptions made by these memory managers. In this work we evaluate the suitability of the Linux Memory Manager, which assumes that the available physical memory is constant, for the purposes of varying the memory at run time. We have implemented an infrastructure over the Linux 2.6.11 kernel that enables the user to vary the physical memory available to the system. The available physical memory is logically divided into banks and each bank can be turned on or off independent of the others, using the new system calls we have added to the kernel. Apart from adding support for the new system calls, other changes had to be made to the Linux memory manager to support the runtime variation of memory. To evaluate the suitability for varying memory we have performed experiments with varying memory sizes on both the modified and the unmodified kernels. We have observed that the design of the existing memory manager is not well suited to support the runtime variation of memory; we provide suggestions to make it better suited for such purposes. Even though applications running on systems that support virtual memory do not use the physical memory directly and are not aware of the physical addresses they use, the amount of physical memory available for use affects the performance of the applications. The results of our experiments have helped us study the influence the amount of physical memory available for use has on the performance of various types of applications. These results can be used in scenarios requiring the ability to vary the memory at runtime to do so with least degradation in the application performance.
  • Thumbnail Image
    Exploiting Malleable Parallelism on Multicore Systems
    McFarland, Daniel James (Virginia Tech, 2011-06-16)
    As shared memory platforms continue to grow in core counts, the need for context-aware scheduling continues to grow. Context-aware scheduling takes into account characteristics of the system and application performance when making decisions. Traditionally applications run on a static thread count that is set at compile-time or at job start time, without taking into account the dynamic context of the system, other running applications, and potentially the performance of the application itself. However, many shared memory applications can easily be converted to malleable applications, that is, applications that can run with an arbitrary number of threads and can change thread counts during execution. Many new and intelligent scheduling decisions can be made when applications become context-aware, including expanding to ll an empty system or shrinking to accommodate a more parallelizable job. This thesis describes a prototype system called Resizing for Shared Memory (RSM), which supports OpenMP applications on shared memory platforms. RSM includes a main daemon that records performance information and makes resizing decisions as well as a communication library to allow applications to contact the RSM daemon and enact resizing decisions. Experimental results show that RSM can improve turn-around time and system utilization even using very simple heuristics and resizing policies.
  • Thumbnail Image
    Exploring the Process and Challenges of Programming with Regular Expressions
    Michael, Louis Guy IV (Virginia Tech, 2019-06-27)
    Regular expressions (regexes) are a powerful mechanism for solving string-matching problems and are supported by all modern programming languages. While regular expressions are highly expressive, they are also often perceived to be highly complex and hard to read. While existing studies have focused on improving the readability of regular expressions, little is known about any other difficulties that developers face when programming with regular expressions. In this paper, we aim to provide a deeper understanding of the process of programming regular expressions by studying: (1) how developers make decisions through the process, (2) what difficulties they face, and (3) how aware they are about serious risks involved in programming regexes. We surveyed 158 professional developers from a diversity of backgrounds, and we conducted a series of interviews to learn more details about the difficulties and solutions that participants face in this process. This mixed methods approach revealed that some of the difficulties of regexes come in the shape of: inability to effectively search for them; fully validate them; and document them. Developers also reported cascading impacts of poor readability, lack of universal portability, and struggling with overall problem comprehension. The majority of our studied developers were unaware of critical security risks that can occur when using regexes, and those that were aware of potential problems felt that they lacked the ability to identify problematic regexes. Our findings provide multiple implications for future work, including development of semantic regex search engines for regex reuse, and improved input generators for regex validation.
  • Thumbnail Image
    An Extensible Framework for Annotation-based Parameter Passing in Distributed Object Systems
    Gopal, Sriram (Virginia Tech, 2008-06-06)
    Modern distributed object systems pass remote parameters based on their runtime type. This design choice limits the expressiveness, readability, and maintainability of distributed applications. While a rich body of research is concerned with middleware extensibility, modern distributed object systems do not offer programming facilities to extend their remote parameter passing semantics. Thus, extending these semantics requires understanding and modifying the underlying middleware implementation. This thesis addresses these design shortcomings by presenting (i) a declarative and extensible approach to remote parameter passing that decouples parameter passing from parameter types, and (ii) a plugin-based framework, DeXteR, that enables the programmer to extend the native set of remote parameter passing semantics, without having to understand or modify the underlying middleware implementation. DeXteR treats remote parameter passing as a distributed cross-cutting concern. It uses generative and aspect-oriented techniques, enabling the implementation of different parameter passing semantics as reusable application-level plugins that work with application, system, and third-party library classes. The flexibility and expressiveness of the framework is validated by implementing several non-trivial parameter passing semantics as DeXteR plugins. The material presented in this thesis has been accepted for publication at the ACM/USENIX Middleware 2008 conference.
  • Thumbnail Image
    Garbage Collection Scheduling for Utility Accrual Real-Time Systems
    Feizabadi, Shahrooz Shojania (Virginia Tech, 2006-12-07)
    Utility Accrual (UA) scheduling is a method of dynamic real-time scheduling that is designed to respond to overload conditions by producing a feasible schedule that heuristically maximizes a pre-defined metric of utility. Whereas utility accrual schedulers have traditionally focused on CPU overload, this dissertation explores memory overload conditions during which the aggregate memory demand exceeds a system's available memory bandwidth. Real-time systems are typically implemented in C or other languages that use explicit dynamic memory management. Taking advantage of modern type-safe languages, such as Java, necessitates the use of garbage collection (GC). The timeliness requirements of real-time systems, however, impose specific demands on the garbage collector. Garbage collection introduces a significant source of unpredictability in the execution timeline of a task because it unexpectedly interjects pauses of arbitrary length, at arbitrary points in time, with an arbitrary frequency. To construct a feasible schedule, a real-time scheduler must have the ability to predict the collector's activities and plan for them accordingly. We have devised CADUS (Collector-Aware Dynamic Utility Scheduler), a utility accrual algorithm that tightly links CPU scheduling with the memory requirements -and the corresponding garbage collection activities - of real-time tasks. By constructing and storing memory time allocation profiles, we address the problem of GC activation strategy. We estimate GC latency by using a real-time collector and modeling its behavior. We project GC frequency by planning, at schedule construction time, the memory bandwidth available to the collector. CADUS can point the collector's activities to any specific task in the system. The runtime system provides this ability by maintaining separate logical heaps for all tasks. We demonstrate the viability of CADUS through extensive simulation studies. We evaluated the behavior of CADUS under a wide range of CPU and memory load conditions and utility distributions. We compared its performance against an existing GC-unaware UA scheduler and found that CADUS consistently outperformed its GC-unaware counterpart. We investigated and identified the reasons for the superior performance of CADUS and quantified our results. Most significantly, we found that in an overloaded dynamic soft real-time system, a scheduler's preemption decisions have a highly significant impact on GC latency. A dynamic real-time scheduler therefore must predict the impact of its preemption decisions on GC latency in order to construct time-feasible schedules.