Rate-monotonic Scheduling
   HOME
*





Rate-monotonic Scheduling
In computer science, rate-monotonic scheduling (RMS) is a priority assignment algorithm used in real-time operating systems (RTOS) with a static-priority scheduling class. The static priorities are assigned according to the cycle duration of the job, so a shorter cycle duration results in a higher job priority. These operating systems are generally preemptive and have deterministic guarantees with regard to response times. Rate monotonic analysis is used in conjunction with those systems to provide scheduling guarantees for a particular application. Introduction A simple version of rate-monotonic analysis assumes that threads have the following properties: *No resource sharing (processes do not share resources, ''e.g.'' a hardware resource, a queue, or any kind of semaphore blocking or non-blocking ( busy-waits)) *Deterministic deadlines are exactly equal to periods *Static priorities (the task with the highest static priority that is runnable immediately preempts all other tasks ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Computer Science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical disciplines (including the design and implementation of Computer architecture, hardware and Computer programming, software). Computer science is generally considered an area of research, academic research and distinct from computer programming. Algorithms and data structures are central to computer science. The theory of computation concerns abstract models of computation and general classes of computational problem, problems that can be solved using them. The fields of cryptography and computer security involve studying the means for secure communication and for preventing Vulnerability (computing), security vulnerabilities. Computer graphics (computer science), Computer graphics and computational geometry address the generation of images. Progr ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Lock-free And Wait-free Algorithms
In computer science, an algorithm is called non-blocking if failure or suspension of any thread cannot cause failure or suspension of another thread; for some operations, these algorithms provide a useful alternative to traditional blocking implementations. A non-blocking algorithm is lock-free if there is guaranteed system-wide progress, and wait-free if there is also guaranteed per-thread progress. "Non-blocking" was used as a synonym for "lock-free" in the literature until the introduction of obstruction-freedom in 2003. The word "non-blocking" was traditionally used to describe telecommunications networks that could route a connection through a set of relays "without having to re-arrange existing calls" (see Clos network). Also, if the telephone exchange "is not defective, it can always make the connection" (see nonblocking minimal spanning switch). Motivation The traditional approach to multi-threaded programming is to use locks to synchronize access to shared resourc ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Scheduling (computing)
In computing, scheduling is the action of assigning ''resources'' to perform ''tasks''. The ''resources'' may be processors, network links or expansion cards. The ''tasks'' may be threads, processes or data flows. The scheduling activity is carried out by a process called scheduler. Schedulers are often designed so as to keep all computer resources busy (as in load balancing), allow multiple users to share system resources effectively, or to achieve a target quality-of-service. Scheduling is fundamental to computation itself, and an intrinsic part of the execution model of a computer system; the concept of scheduling makes it possible to have computer multitasking with a single central processing unit (CPU). Goals A scheduler may aim at one or more goals, for example: * maximizing ''throughput'' (the total amount of work completed per time unit); * minimizing '' wait time'' (time from work becoming ready until the first point it begins execution); * minimizing '' latency ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


RTEMS
Real-Time Executive for Multiprocessor Systems (RTEMS), formerly Real-Time Executive for Missile Systems, and then Real-Time Executive for Military Systems, is a real-time operating system (RTOS) designed for embedded systems. It is free and open-source software. Development began in the late 1980s with early versions available via File Transfer Protocol (ftp) as early as 1993. OAR Corporation is currently managing the RTEMS project in cooperation with a steering committee which includes user representatives. Design RTEMS is designed for real-time, embedded systems and to support various open application programming interface (API) standards including Portable Operating System Interface (POSIX) and µITRON. The API now known as the Classic RTEMS API was originally based on the Real-Time Executive Interface Definition (RTEID) specification. RTEMS includes a port of the FreeBSD Internet protocol suite (TCP/IP stack) and support for various file systems including Network File System ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Earliest Deadline First Scheduling
Earliest deadline first (EDF) or least time to go is a dynamic priority scheduling algorithm used in real-time operating systems to place processes in a priority queue. Whenever a scheduling event occurs (task finishes, new task released, etc.) the queue will be searched for the process closest to its deadline. This process is the next to be scheduled for execution. EDF is an ''optimal'' scheduling algorithm on preemptive uniprocessors, in the following sense: if a collection of independent ''jobs,'' each characterized by an arrival time, an execution requirement and a deadline, can be scheduled (by any algorithm) in a way that ensures all the jobs complete by their deadline, the EDF will schedule this collection of jobs so they all complete by their deadline. With scheduling periodic processes that have deadlines equal to their periods, EDF has a utilization bound of 100%. Thus, the schedulability test for EDF is: :U = \sum_^ \frac \leq 1, where the \left\ are the worst-case com ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Dynamic Priority Scheduling
Dynamic priority scheduling is a type of scheduling algorithm in which the priorities are calculated during the execution of the system. The goal of dynamic priority scheduling is to adapt to dynamically changing progress and to form an optimal configuration in a self-sustained manner. It can be very hard to produce well-defined policies to achieve the goal depending on the difficulty of a given problem. Earliest deadline first scheduling and Least slack time scheduling are examples of Dynamic priority scheduling algorithms. Optimal Schedulable Utilization The idea of real-time scheduling is to confine processor utilization under schedulable utilization of a certain scheduling algorithm, which is scaled from 0 to 1. Higher schedulable utilization means higher utilization of resource and the better the algorithm. In preemptible scheduling, dynamic priority scheduling such as earliest deadline first (EDF) provides the optimal schedulable utilization of 1 in contrast to less than 0.6 ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  




Deos
DDC-I, Inc. is a privately held company providing software development of real-time operating systems, software development tools, and software services for safety-critical embedded applications, headquartered in Phoenix, Arizona. It was first created in 1985 as the Danish firm DDC International A/S (also known as DDC-I A/S), a commercial outgrowth of Dansk Datamatik Center, a Danish software research and development organization of the 1980s. The American subsidiary was created in 1986. For many years, the firm specialized in language compilers for the programming language Ada. In 2003, the Danish office was closed and all operations moved to the Phoenix location. Origins The origins of DDC International A/S lay in Dansk Datamatik Center, a Danish software research and development organization that was formed in 1979 to demonstrate the value of using modern techniques, especially those involving formal methods, in software design and development. Among its several projects wa ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Deadline-monotonic Scheduling
Deadline-monotonic priority assignment is a priority assignment policy used with fixed-priority pre-emptive scheduling. With deadline-monotonic priority assignment, tasks are assigned priorities according to their deadlines. The task with the shortest deadline is assigned the highest priority. This priority assignment policy is optimal for a set of periodic or sporadic tasks which comply with the following system model: # All tasks have deadlines less than or equal to their minimum inter-arrival times (or periods). # All tasks have worst-case execution times (WCET) that are less than or equal to their deadlines. # All tasks are independent, and so do not block each other's execution (e.g., by accessing mutually exclusive shared resources). # No task voluntarily suspends itself. # There is some point in time, referred to as a critical instant, where all of the tasks become ready to execute simultaneously. # Scheduling overheads (switching from one task to another) are zero. # All ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Interrupt Service Routine
In computer systems programming, an interrupt handler, also known as an interrupt service routine or ISR, is a special block of code associated with a specific interrupt condition. Interrupt handlers are initiated by hardware interrupts, software interrupt instructions, or software exceptions, and are used for implementing device drivers or transitions between protected modes of operation, such as system calls. The traditional form of interrupt handler is the hardware interrupt handler. Hardware interrupts arise from electrical conditions or low-level protocols implemented in digital logic, are usually dispatched via a hard-coded table of interrupt vectors, asynchronously to the normal execution stream (as interrupt masking levels permit), often using a separate stack, and automatically entering into a different execution context (privilege level) for the duration of the interrupt handler's execution. In general, hardware interrupts and their handlers are used to handle high-pri ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Mars Pathfinder
''Mars Pathfinder'' (''MESUR Pathfinder'') is an American robotic spacecraft that landed a base station with a roving probe on Mars in 1997. It consisted of a lander, renamed the Carl Sagan Memorial Station, and a lightweight, wheeled robotic Mars rover named ''Sojourner'', the first rover to operate outside the Earth–Moon system. Launched on December 4, 1996, by NASA aboard a Delta II booster a month after the ''Mars Global Surveyor'', it landed on July 4, 1997, on Mars's Ares Vallis, in a region called Chryse Planitia in the Oxia Palus quadrangle. The lander then opened, exposing the rover which conducted many experiments on the Martian surface. The mission carried a series of scientific instruments to analyze the Martian atmosphere, climate, and geology and the composition of its rocks and soil. It was the second project from NASA's Discovery Program, which promotes the use of low-cost spacecraft and frequent launches under the motto "cheaper, faster and better" promo ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

VxWorks
VxWorks is a real-time operating system (or RTOS) developed as proprietary software by Wind River Systems, a wholly-owned subsidiary of Aptiv. First released in 1987, VxWorks is designed for use in embedded systems requiring real-time, deterministic performance and, in many cases, safety and security certification for industries such as aerospace and defense, medical devices, industrial equipment, robotics, energy, transportation, network infrastructure, automotive, and consumer electronics.VxWorks
Goes 64-bit", Electronic Design, March 25, 2011
VxWorks supports AMD/Intel architecture, POWER architecture, ARM architectures and RISC-V. The RTOS can be used in multicore

Priority Ceiling Protocol
In real-time computing, the priority ceiling protocol is a synchronization protocol for shared resources to avoid unbounded priority inversion and mutual deadlock due to wrong nesting of critical sections. In this protocol each resource is assigned a priority ceiling, which is a priority equal to the highest priority of any task which may lock the resource. The protocol works by temporarily raising the priorities of tasks in certain situations, thus it requires a scheduler that supports dynamic priority scheduling. ICPP versus OCPP There are two variants of the protocol: Original Ceiling Priority Protocol (OCPP) and Immediate Ceiling Priority Protocol (ICPP). The worst-case behaviour of the two ceiling schemes is identical from a scheduling view point. Both variants work by temporarily raising the priorities of tasks. In OCPP, a task X's priority is raised when a higher-priority task Y tries to acquire a resource that X has locked. The task's priority is then raised to the prio ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]