Approved for public release; distribution is unlimited / As demand for hard real-time and embedded computer systems increases, a new approach to software development is critical. Software engineers and users would benefit from an automated methodology allowing validation of design specifications or functional requirements early in the development life cycle. A fast, efficient, easy-to-use tool would increase productivity and would enhance user confidence that software would be delivered at less cost and on schedule. The Computer Aided Prototyping System (CAPS) is a conceptualized tool providing these capabilities. This thesis represents a pioneering effort to develop a Static Scheduler for the CAPS Execution Support System using the Ada programming language. The Static Scheduler initially extracts critical operators, timing constraints and precedence relationships from a high-level prototype source program. The Static Scheduler then creates a static schedule for run-time execution, using worst case scenarios, guaranteeing that timing constraints are met. The primary goal of this thesis is to provide the scheduling algorithms and implementation guidelines for the Static Scheduler. Secondary goals are to demonstrate the significance of continued research to telecommunications applications and to demonstrate the feasibility of Ada as the implementation language. / http://archive.org/details/staticschedulerf00jans / Lieutenant, United States Navy

Este trabalho apresenta uma avaliação do algoritmo EBS, uma política de escalonamento proposta para sistemas de tempo real flexíveis com qualidade de serviço baseado em limites superiores para tempos médios de resposta. Experimentos têm demonstrado propriedades vantajosas da política EBS em servidores Web com diferenciação de serviço. O objetivo do presente estudo é compreender o comportamento da EBS em relação à diferentes parâmetros que descrevem a carga de trabalho. Esse conhecimento é útil para obtenção de um melhor aproveitamento computacional. São apresentados experimentos e resultados que analisam a influência de cada um dos fatores considerados na qualidade do serviço oferecido. A partir desses resultados são tecidas conclusões acerca de abordagens para o dimensionamento de carga e de capacidade do servidor / This Master degree project has presented an evaluation of the EBS algorithm, a scheduling policy proposed for soft real-time systems with quality of service based on upper limits for average response times. Experiments have shown advantageous properties of the EBS policy on Web servers with service differentiation. The aim of this study is to understand the behavior of the EBS in relation to different parameters that describe the workload. This knowledge is useful for obtaining a better use of computing. Experiments and results are presented analyzing the influence of each factor considering the quality of service offered. From these results, conclusions are woven about approaches to the design load and server capacity

The High Performance Computing community is constantly facing new challenges due to the ever growing demand for processing power from scientific applications that represent diverse areas of human knowledge. Parallel and distributed systems are the key to speed up the execution of these applications as many jobs can be executed concurrently. These systems are shared by many users who submit their jobs over time and expect a fair treatment by the scheduler. The work done in this thesis lies in this context: to analyze and develop fair and efficient algorithms for managing computing resources shared among multiple users. We analyze scenarios with many submissions issued from multiple users over time. These submissions contain several jobs and the set of submissions are organized in successive campaigns. In what we define as the Campaign Scheduling model, the jobs of a campaign do not start until all the jobs from the previous campaign are completed. Each user is interested in minimizing the flow times of their own campaigns. This is motivated by the user submission behavior whereas the execution of a new campaign can be tuned by the results of the previous campaign. In the first part of this work, we define a theoretical model for Campaign Scheduling under restrictive assumptions and we show that, in the general case, it is NP-hard. For the single-user case, we show that an approximation scheduling algorithm for the (classic) parallel job scheduling problem also delivers the same approximation ratio for the Campaign Scheduling problem. For the general case with multiple users, we establish a fairness criteria inspired by time sharing. Then, we propose a scheduling algorithm called FairCamp which uses campaign deadlines to achieve fairness among users between consecutive campaigns. The second part of this work explores a more relaxed and realistic Campaign Scheduling model, provided with dynamic features. To handle this setting, we propose a new algorithm called OStrich whose principle is to maintain a virtual time-sharing schedule in which the same amount of processors is assigned to each user. The completion times in the virtual schedule determine the execution order on the physical processors. Then, the campaigns are interleaved in a fair way. For independent sequential jobs, we show that OStrich guarantees the stretch of a campaign to be proportional to campaigns size and to the total number of users. The stretch is used for measuring by what factor a workload is slowed down relatively to the time it takes to be executed on an unloaded system. Finally, the third part of this work extends the capabilities of OStrich to handle parallel jobs. This new version executes campaigns using a greedy approach and uses an event-based resizing mechanism to shape the virtual time-sharing schedule according to the system utilization ratio. / La communauté de Calcul Haute Performance est constamment confrontée à de nouveaux défis en raison de la demande toujours croissante de la puissance de traitement provenant dapplications scientifiques diverses. Les systèmes parallèles et distribués sont la clé pour accélérer lexécution de ces applications, et atteindre les défis associés car de nombreux processus peuvent être exécutés simultanément. Ces systèmes sont partagés par de nombreux utilisateurs qui soumettent des tâches sur de longues périodes au fil du temps et qui attendent un traitement équitable par lordonnanceur. Le travail effectué dans cette thèse se situe dans ce contexte: analyser et développer des algorithmes équitables et efficaces pour la gestion des ressources informatiques partagés entre plusieurs utilisateurs. Nous analysons les scénarios avec de nombreux soumissions issues de plusieurs utilisateurs. Ces soumissions contiennent un ou plusieurs processus et lensemble des soumissions sont organisées dans des campagnes successives. Dans ce que nous appelons le modèle dordonnancement des campagnes les processus dune campagne ne commencent pas avant que tous les processus de la campagne précédente soient terminés. Chaque utilisateur est intéressé à minimiser la somme des temps dexécution de ses campagnes. Cela est motivé par le comportement de lutilisateur tandis que lexécution dune campagne peut être réglé par les résultats de la campagne précédente. Dans la première partie de ce travail, nous définissons un modèle théorique pour lordonnancement des campagnes sous des hypothèses restrictives et nous montrons que, dans le cas général, il est NP-difficile. Pour le cas mono-utilisateur, nous montrons que lalgorithme dapproximation pour le problème (classique) dordonnancement de processus parallèles fournit également le même rapport dapproximation pour lordonnancement des campagnes. Pour le cas général avec plusieurs utilisateurs, nous établissons un critère déquité inspiré par une situation idéalisée de partage des ressources. Ensuite, nous proposons un algorithme dordonnancement appelé FairCamp qui impose des dates limite pour les campagnes pour assurer léquité entre les utilisateurs entre les campagnes successives. La deuxième partie de ce travail explore un modèle dordonnancement de campagnes plus relâché et réaliste, avec des caractéristiques dynamiques. Pour gérer ce cadre, nous proposons un nouveau algorithme appelé OStrich dont le principe est de maintenir un ordonnancement partagé virtuel dans lequel le même nombre de processeurs est assigné à chaque utilisateur. Les temps dachèvement dans lordonnancement virtuel déterminent lordre dexécution sur le processeurs physiques. Ensuite, les campagnes sont entrelacées de manière équitable. Pour des travaux indépendants séquentiels, nous montrons que OStrich garantit le stretch dune campagne en étant proportionnel à la taille de la campagne et le nombre total dutilisateurs. Le stretch est utilisé pour mesurer le ralentissement par rapport au temps quil prendrait dans un système dédié. Enfin, la troisième partie de ce travail étend les capacités dOStrich pour gérer des tâches parallèles rigides. Cette nouvelle version exécute les campagnes utilisant une approche gourmande et se sert aussi dun mécanisme de redimensionnement basé sur les événements pour mettre à jour lordonnancement virtuel selon le ratio dutilisation du système.

Este trabalho apresenta uma avaliação do algoritmo EBS, uma política de escalonamento proposta para sistemas de tempo real flexíveis com qualidade de serviço baseado em limites superiores para tempos médios de resposta. Experimentos têm demonstrado propriedades vantajosas da política EBS em servidores Web com diferenciação de serviço. O objetivo do presente estudo é compreender o comportamento da EBS em relação à diferentes parâmetros que descrevem a carga de trabalho. Esse conhecimento é útil para obtenção de um melhor aproveitamento computacional. São apresentados experimentos e resultados que analisam a influência de cada um dos fatores considerados na qualidade do serviço oferecido. A partir desses resultados são tecidas conclusões acerca de abordagens para o dimensionamento de carga e de capacidade do servidor / This Master degree project has presented an evaluation of the EBS algorithm, a scheduling policy proposed for soft real-time systems with quality of service based on upper limits for average response times. Experiments have shown advantageous properties of the EBS policy on Web servers with service differentiation. The aim of this study is to understand the behavior of the EBS in relation to different parameters that describe the workload. This knowledge is useful for obtaining a better use of computing. Experiments and results are presented analyzing the influence of each factor considering the quality of service offered. From these results, conclusions are woven about approaches to the design load and server capacity

CPU schedulers are an integral part of all operating systems used in modern systems, as they enable efficient task execution. In recent years the demand for interactive tasks such as video playback, streaming and gaming has increased rapidly. This combined with new ideas and design for CPU scheduling has led to the development of the BitMap Queue scheduler(BMQ) by Alfred Chen. Which aims to be efficient and scalable for interactive tasks, in hopes of becoming an alternative scheduler for Linux. This paper evaluates the performance of BMQ compared to the current default scheduler, the Completely Fair Scheduler(CFS). The methodology in the paper focuses on two key aspects latency and interactivity. The results display BMQ outperforming CFS in latency while maintaining similar performance in interactivity. However during heavier loads in the interactivity test BMQ outperformed CFS significantly. Thus the results suggest that BMQ provides reduced latency while providing at least similar and in some cases better interactive performance when compared to CFS.

No description available.

For a successful CubeSat mission, it is imperative to schedule events in a fashion that will generate maximum useful science data. Intuitive uplink commanding software is required for the Lower Atmosphere/Ionosphere Coupling Experiment (LAICE) CubeSat to ensure best results. The ground station up-link software is created with this aim in mind. This will make the operation center for the LAICE project efficient. This will also help in evaluating the effect of a particular schedule on LAICE instrument interface board (LIIB) before sending the commands to it. The interactive User Interface (UI) that makes the entire process intuitive guides the user to create an uplink schedule without any human error. The control software creates the command sequence taking in to account all the limitations and specification of the systems and instruments on LAICE. These data are backed up in an efficient format in Virginia Tech’s database for future processing. This web-based application ensures a smooth scheduling process without any errors. Assistive flight-ready software is provided on the flight computer on the LAICE CubeSat to upload the correct uplink sequence to the LIIB. / Master of Science

L'évolution technologique de RAN dans le contexte de la 5G n'est pas seulement guidée par l'amélioration de la qualité de service du réseau mais aussi par la nécessité de transformer toutes les technologies par des systèmes dynamiques intelligents. La nouvelle technologie de la 5G est plus que flexible et pourra satisfaire chaque utilisateur de façon équitable sans que son type (mobile ou statique) ou sa demande de service (service temps réel et non réel) n'affecte. Tous les cas d'utilisation seront intelligemment dimensionnés et gérés dans le réseau. L'objectif principal de cette thèse est d'analyser et d'améliorer les performances radio en tenant compte de la mobilité des véhicules en gérant dynamiquement et intelligemment les ressources disponibles. A cette fin, nous présentons différents modèles de mobilité des utilisateurs dans le cas discret et continu. Le modèle discret utilisant le modèle bien connu du car following est bien adapté pour les simulations. La méthode continue est utile pour obtenir des indicateurs analytiques de performance clés (KPI). La nouveauté de cette partie de la thèse est la formulation analytique de KPIs qui tiennent compte de la mobilité physique dans le trafic radio. A titre d'exemple, l'impact d'un feu rouge sur les indicateurs de performance dans une cellule est étudié. Il est montré qu'une congestion physique périodique du trafic due au feu de circulation détériore périodiquement la performance de la cellule. La première solution considérée consiste à améliorer l'allocation et le contrôle des ressources dans le contexte du réseau hétérogène LTE-Advanced. Une small cell est ensuite déployée à proximité du feu rouge pour diminuer la congestion périodique et la dégradation de la qualité de service. Trois systèmes d'allocation et de contrôle des ressources sont étudiés: une réutilisation de fréquence complète, un algorithme de division de fréquence statique et dynamique qui sont optimisés par rapport à une utilité alpha -fair basé sur les débits reçus. En outre, il est montré que le système de commande dynamique est particulièrement intéressant pour le trafic non stationnaire comme celui introduit par un feu de circulation périodique. Par souci de réduction des coûts financiers et énergétiques, et de suivi d'utilisateurs mobiles, une autre solution est fournie en utilisant un nouveau réseau d'antennes afin de gérer efficacement le trafic hétérogène, fixe et mobile. On considère trois technologies différentes de réseau d'antennes permettant de décharger les zones de congestion ainsi que la congestion mobile dynamique: Virtual Small Cell (VSC), petite cellule virtuelle avec réseau auto-organisateur (VSC-SON) et rayons focalisant avec un multiniveau global codebook qui gère le système d'antenne hétérogène à la station de base. Les deux premières technologies améliorent la performance de la cellule en raison de leur capacité de focaliser le signal à la concentration du trafic au niveau de la congestion physique. La nouvelle solution de faisceaux focalisants avec le global codebook améliore de manière significative les performances en raison de la capacité de focaliser le signal le long de la route et d'équilibrer implicitement le trafic entre les différentes antennes. Nous comparons toutes ces technologies et leur impact sur les performances du réseau. La question de la sélection d'un utilisateur pour lui allouer une partie (en temps ou en bande passante) de la ressource disponible est étudiée. Le contexte de la gestion des ressources et de la performance du réseau dans la mobilité est un des défis futurs pour la 5G. Grâce à la technologie MDT, les réseaux peuvent avoir une idée, ou plus précisément une moyenne du SINR grâce à la GLM. Nous introduisons le concept de Forecast Scheduling pour les utilisateurs en mobilité à vitesse élevée. On suppose que la REM peut fournir des valeurs interpolées du SINR le long des trajectoires des utilisateurs. / The technology evolution of Radio Access Network (RAN) in the context of 5th Generation (5G) is not only guided by improving the network performance but also by the need to transform all the technologies into intelligent dynamic ones. The new 5G is a flexible technology that will be able to satisfy at the same time each user of any type of mobility (static or mobile) or service request (real and non-real time service) without modifying any models or algorithms in networks. All physical use cases will be able to be considered by the network intelligently and resource managed automatically. The objective of this thesis is to analyse and enhance radio performance taking into account vehicular mobility by managing dynamically and intelligently the available resources. To this end, we describe different users mobility models for discrete and continuous modeling. The discrete model using the well-known car following model is well adapted for simulations. The continuous one is useful to derive analytical key performance indicators (KPI). The novelty of the thesis is the analytical formulation of KPIs that take into account the physical mobility in the radio traffic which is not necessary stationary. As an example, the impact of a traffic light on performance indicators in a cell is investigated. It is shown that a periodical physical traffic congestion due to the traffic light deteriorate periodically the cell performance. A first given solution is to improve resource allocation and control in the context of LTE-Advanced heterogeneous network. A small cell is deployed near the traffic light to relieve periodic congestion and QoS degradation. Three resource allocation and control schemes are investigated: a full frequency reuse, a static and a dynamic frequency splitting algorithm that are optimized with respect to a throughput based alpha-fair utility. For sake of financial and energy costs decreasing, another solution is provided using new antenna array technologies in order to manage efficiently heterogeneous, fixed and mobile traffic. A heterogeneous antenna system with different large antenna array technologies is considered to ooad static congestion areas and also the dynamical mobile congestion: Virtual Small Cell (VSC), virtual small cell with Self-Organizing Network (VSC-SON) and beamforming with multilevel global codebook that manages the heterogeneous antenna system at the Base Station (BS). The first two technologies improve the cell performance due to the capability to focus the signal at the traffic concentration. The novel beamforming solution with global codebook can further and significantly improve performance due to the capability to focus the signal along the road and to implicitly balance the traffic between the different antennas. We compare all these technologies and their impact on the network performance. The issue of user selection to allocate a portion (in time or in bandwidth) of the available resource is also analyzed. Moreover the context of resource management and network performance for 5G in high mobility is one of the future challenges. Thanks to the Minimization of Drive Testing (MDT) technology, networks can have Signal to Interference plus Noise Ratio (SINR) information with Geo-Localized Measurements (GLM).We introduce the concept of Forecast Scheduler for users in high mobility. It is assumed that a Radio Environment Map (REM) can provide interpolated SINR values along the user trajectories. Mobile users experience in their trajectories different mean SINR values. In mobile networks, schedulers exploit channel quality variation by giving the signal to the user experiencing best channel conditions while remaining fair. Nevertheless, we cannot record data rates of users with high mobility due to a very small time coherence. The Forecast Scheduling will exploit the SINR variation during users' trajectories.

Problem statement: Manufacturing and production plants operate machines and equipment that deteriorate with usage and time thus requiring maintenance actions to restore them back to their original operational conditions. Approach: This study investigates the current standard of maintenance planning at a steel manufacturing facility in South Africa. The study begins with a thorough literature study to find good characteristics of planning which should be present at any facility that is optimally engaged in performing excellent maintenance planning effectively and efficiently. A number of key observations from the literature are made indicating that planning is a key component of maintenance and affects excellence in maintenance significantly. The literature recommends that planning should be set and based on key principles to allow for standardisation and efficiency. An empirical study in the form of a survey is then completed to benchmark the current maintenance-planning environment of the steel facility against the good characteristics of maintenance planning found in literature. Results: The results from the empirical study show that the current maintenance environment at the steel manufacturer is not optimal. The following issues are uncovered from the study: no schedulers employed to relieve the planners’ work overload, no guiding principles for planning and standardisation of work planning, no efficient shutdown planning and also no existent measures for tracking some of the key performance areas. Conclusion: Key recommendations to be considered for implementation for improving the status of the maintenance environment at the works include: introducing the scheduler position, standardising planning methodologies according to specific principles and rigorously focusing on overall maintenance improvement using standardised methodologies. / MBA (Business Administration), North-West University, Potchefstroom Campus, 2015

Problem statement: Manufacturing and production plants operate machines and equipment that deteriorate with usage and time thus requiring maintenance actions to restore them back to their original operational conditions. Approach: This study investigates the current standard of maintenance planning at a steel manufacturing facility in South Africa. The study begins with a thorough literature study to find good characteristics of planning which should be present at any facility that is optimally engaged in performing excellent maintenance planning effectively and efficiently. A number of key observations from the literature are made indicating that planning is a key component of maintenance and affects excellence in maintenance significantly. The literature recommends that planning should be set and based on key principles to allow for standardisation and efficiency. An empirical study in the form of a survey is then completed to benchmark the current maintenance-planning environment of the steel facility against the good characteristics of maintenance planning found in literature. Results: The results from the empirical study show that the current maintenance environment at the steel manufacturer is not optimal. The following issues are uncovered from the study: no schedulers employed to relieve the planners’ work overload, no guiding principles for planning and standardisation of work planning, no efficient shutdown planning and also no existent measures for tracking some of the key performance areas. Conclusion: Key recommendations to be considered for implementation for improving the status of the maintenance environment at the works include: introducing the scheduler position, standardising planning methodologies according to specific principles and rigorously focusing on overall maintenance improvement using standardised methodologies. / MBA (Business Administration), North-West University, Potchefstroom Campus, 2015