Author: Zhang Huanqiang (
zhq@iscas.ac.cn)
Chinese Academy of Sciences Software Research Institute Multimedia Communication and Network Engineering Research Center
More and more developers construct embedded real-time applications based on Linux systems, they urgently need a guidebook based on Linux system constructing embedded real-time systems. Considering this requirement, this paper introduces several basic real-time process scheduling algorithms to study the process scheduling of ordinary Linux operating systems, and investigated a variety of real-time Linux systems to support real-time characteristics. Improvements made by Linux systems. The article analyzes some of the problems that occur when the Linux operating system is applied to real-time fields, summarizes how various real-time Linux solves these issues, and finally apply these existing research results and practical research and development. It has made good advice in the work.
Part 1: Real-time scheduling algorithm introduction
For what is a real-time system, POSIX 1003.b makes such definitions: refers to the service that provides the required level of service in a defined response time. The definition of a more acceptable by Donald Gillies is that a real-time system refers to the correctness of the calculation but also depends on the logical correctness of the program, but also depends on the time generated. If the system's time constraint is not available Meeting, the system error will occur.
Real-time systems can be divided into soft and hard-real-time depending on their real-time requirements. Hard real-time system refers to the system to ensure the worst case of ensuring, that is, the deadline for the response time of the event is to be satisfied. For example, the control of the spacecraft in the spacecraft is the system in reality. Other systems with real-time characteristics can be called soft real-time systems. If it is clear that the soft real-time system is those from the statistical perspective (in the discussion below, we will not distinguish between tasks and processes) can get the processing time of ensuring that the system can be reached. Before the deadline is exposed, it will be dealt with, but the deadline will not bring fatal errors, like real-time multimedia systems is a soft real-time system.
A computer system in order to provide support for real-time, its operating system must valid scheduling and management for CPUs and other resources. In multitasking real-time systems, the scheduling and management of resources is more complicated. This article will first discuss various real-time task scheduling algorithms from the perspective of the classification, and then study the process schedule of the normal Linux operating system and various real-time Linux systems to support real-time characteristics to improve the general Linux system. Finally, some issues that have been applied to the real-time field when analyzing the Linux operating system, and summarizes how various real-time Linux solves these problems.
1. Real-time CPU scheduling algorithm classification
Real-time scheduling algorithms of various real-time operating systems can be divided into three categories [WANG99] [Gopalan01]: Priority-Driven Scheduling-Pd, a shared scheduling algorithm based on CPU usage ratio (Share -Driven scheduling-sd), as well as time-driven schedule algorithm, the following three scheduling algorithms are introduced one by one.
1.1. Scheduling algorithm based on priority
The priority-based scheduling algorithm assigns a priority to each process. When each process schedules are scheduled, the scheduler always dispatches the task with the highest priority to execute. According to different priority allocation methods, priority-based scheduling algorithms can be divided into two types [Krishna01] [wang99]:
Static priority scheduling algorithm:
This scheduling algorithm is static to all processes that are running in the systematically allocate a priority. The allocation of the static priority can be performed according to the properties of the application, such as the period of task, user priority, or other predetermined strategy. The RM (RATE-MONOTONIC) scheduling algorithm is a typical static priority scheduling algorithm that determines the scheduling priority based on the length of the execution cycle of the task, and the tasks with small execution cycles have a high priority. Dynamic priority scheduling algorithm:
This scheduling algorithm dynamically allocates the priority of the task based on the resource requirements of the task, and its purpose is to make greater flexibility in resource allocation and scheduling. There are many such scheduling algorithms, such as short job priority. In the real-time scheduling algorithm, the EDF algorithm is the most dynamic priority scheduling algorithm that assigns priority based on each of the tasks in the ready queue, with a deadline, with the most recent deadline. The highest priority.
1.2. Based on proportional sharing modification algorithm
Although the priority scheduling algorithm is simple and effective, this scheduling algorithm provides a hard-real-time scheduling, and in many cases, this scheduling algorithm is not suitable: such as soft real-time applications like real time multimedia conference systems. . For such a soft real-time application, use a proportional share-shaped resource scheduling algorithm (SD algorithm) is more suitable.
The proportional shared scheduling algorithm refers to the shared scheduling algorithm based on the proportion of CPU usage. Its basic idea is to schedule a set of tasks that require scheduling in accordance with certain weights (ratios), allowing their execution time to completely corrected their weight.
We can achieve a proportional sharing scheduling algorithm in two ways [Nieh01]: The first method is to adjust the frequency of each ready process appear in the schedule queue, and the process execution of the team is the first way is to schedule The various processes in the queue are put into operation, but the runtime tablets allocated by all the processes are adjusted according to the allocated weights.
The proportional shared modification algorithm can be divided into the following categories: rotation, fair sharing, fair queue, lottery scheduling (Lottery).
One problem with the proportional shared modification algorithm is that it does not define any priority concepts; all tasks share the CPU resource based on their application, when the system is in an overloaded state, the execution of all tasks will slow down. Therefore, in order to ensure that the real-time process in the system can obtain a certain CPU processing time, a method of dynamically adjusting process weight is generally employed.
1.3. Time-based process scheduling algorithm
For those simple systems with stable, known input, it can use time-driven: TDs to provide a good predictability for data processing. This scheduling algorithm is essentially a designed an offline static scheduling method when designing. In the design phase of the system, in the case of all the processing in the system, make a clear arrangement and design for the beginning, switching, and end time, etc. for each task. This scheduling algorithm is suitable for applications such as small embedded systems, automatic control systems, sensors, and more.
The advantage of this scheduling algorithm is that the implementation of the task has a good predictability, but the maximum disadvantage is that there is a lack of flexibility and there is a task to be executed and the CPU remains free.
2. CPU scheduling in universal Linux system
The general Linux system supports both real-time and non-real-time processes, and the real-time process has an absolute priority relative to the normal process. Correspondingly, the real-time process uses the SCHED_FIFO or SCHED_RR scheduling policy, and the ordinary process uses the SCHED_OTHER scheduling policy.
In the implementation of the scheduling algorithm, each task in Linux has four parameters related to the schedule, which is RT_Priority, Policy, Priority (Nice), Counter. The scheduler is scheduled based on these four parameters.
In the SCHED_OTHER scheduling policy, the scheduler always selects the maximum process of the Priority Counter value to schedule execution. From logically analyzing, the SCHED_OTHER scheduling policy exists with a scheduling cycle (EPOCH), in each scheduling cycle, the size of a process of priority and counter affects which process should be scheduled to schedule, where priority is a fixed Value, it has been determined when the process is created, which represents the priority of the process, also represents how much the process can get in each dispatch cycle; Counter is a dynamic value, it reflects A process is still left in the current dispatch cycle. At the beginning of each scheduling cycle, the value of Priority is assigned to the counter, and then the Counter value is reduced each time the process is scheduled. When the Counter value is zero, the process uses the time slice yourself in this scheduled period and no longer participates in the process schedule of this scheduled cycle. When all processes are used, a scheduling cycle ends and then begins. It is also possible to see that the scheduling cycle in the Linux system is not static. It is an amount of dynamic variation, such as how much the process of running state and its priority value can affect the length of EPOCH. It is worth noting that in the 2.4 kernel, Priority is replaced by Nice, but the two functions. It can be seen that the SCHED_OTHER scheduling strategy is essentially a proportional scheduling policy. Its design method guarantees the fairness of the process schedule - a low priority process will receive it in every EPOCH. The CPU execution time, and it also provides the priority distinguishing between different processes, and the process with high priority values can obtain more execution time.
For real-time processes, they use the priority scheduling strategy based on real-time priority RT_Priority, but according to different scheduling policies, the scheduling methods between the same real-time priority process are different:
SCHED_FIFO: Different processes are queued according to static priority, then in the same priority queue, who is ready to run first, and the running process will not be terminated until the following occurs: 1. High priority process has a strong CPU; 2. It is blocked by resource requests; 3. I actively give up the CPU (call sched_yield);
SCHED_RR: This scheduling policy is exactly the same as the SCHED_FIFO above, except that it assigns a time slice to each process, and the time slice will give up the execution; the length of the time film can be called by sched_rr_get_interval;
Since the Linux system itself is a desktop system, there is some problems used in real-time applications:
The scheduling unit in the Linux system is 10ms, so it cannot provide accurate timing;
When a process call system call enters the kernel, it is not a preemption;
A large number of interrupt operations in Linux kernel implementation will cause interruption loss;
Since the virtual memory technology is used, when the page is wrong, you need to read the exchange data from the hard disk, but the hard disk read and write due to the randomness of the storage location, which causes the random read and write time, which will affect some real-time tasks in some cases. Deadline;
Although the Linux process schedule also supports real-time priority, lacks a scheduling mechanism and scheduling algorithm for real-time tasks; its network subsystem protocol handling and other devices are not associated with the scheduling of the process it corresponds, and They do not have a clear scheduling mechanism; 3. Various real-time Linux systems
3.1. RT- Linux and RTAI
RT-Linux is the research results of New Mexico Instute Of Technology [RT Linux Web] [Barabanov97]. Its basic idea is that in order to provide a hard real-time support in the Linux system, it implements a small real-time operating system of a microennote (we also called RT-Linux real-time subsystem), and will ordinary Linux system As a low priority task in the operating system. In addition, tasks in the normal Linux system can communicate via FIFO and real-time tasks. The framework of RT-Linux is shown in Figure 1:
Figure 1 RT-Linux structure
The key technology of RT-Linux is to simulate hardware interrupt controllers through software. When the Linux system is to block the interrupt of the CPU, the real-time subsystem in RT-Linux will take this request, record it, and actually unclear the hardware interrupt, so that the system caused by the blocking interrupt is avoided. There is no response in a period of time, thereby improving real-time. When there is a hardware interrupt, RT-Linux intercends the interrupt and determines whether there is an interrupt routine in a real-time subsystem to handle it to a normal Linux kernel. In addition, the minimum timing accuracy in the normal Linux system is determined by the frequency of the real-time clock in the system, and the general Linux system sets the clock to 100 clocks per second, so the general timing accuracy in the Linux system is 10ms, the clock cycle It is 10ms, and RT-Linux provides a dozen microsecond scheduling granularity by setting the real-time clock of the system to a single trigger state.
The task scheduling in the real-time subsystem in the RT-Linux can use the priority driver of RM, EDF, or other scheduling algorithms can also be employed.
RT-Linux is a good choice for those proprietary systems working under heavy load, but he only provides scheduling for CPU resources; and real-time systems and ordinary Linux system relationships are not very close, such, Developers cannot make full use of features that have been implemented in the Linux system, such as protocol stacks. Therefore, RT-Linux is suitable for real-time task functions such as industrial control, and there is a hard-real-time environment, but if you want to apply to multimedia processing, you need to do a lot of work.
Italy's RTAI (Real-Time Application Interface "originates from RT-Linux, which is identical to RT-Linux. It was originally designed to solve the problem that RT-Linux is difficult to transplant between different Linux versions. To this end, RTAI defines a real-time hardware abstraction layer on Linux, and the real-time task passes the interface and Linux system provided by this abstract layer. Interaction, this can modify the Linux kernel source code as much as possible when adding real-time support to the Linux kernel.
3.2. Kurt- Linux
Kurt - Linux is developed by Kansas University, which provides a microsecond level of real-time accuracy [KurtWeb] [Srinivasan]. Different from RT-Linux separately realize a real-time kernel, Kurt - Linux is implemented on the basis of a general Linux system, and it is also the first Linux-based real-time system that can be called using ordinary Linux system.
Kurt- Linux divides the system into three states: normal state, real-time and mixed state, it uses normal Linux scheduling strategies in normal state, running only real-time tasks in real-time, in real time and non-real time tasks Can be implemented; real-time motion can be used in cases in real time requirements.
In order to improve the real-time characteristics of the Linux system, the clock accuracy supported by the system must be improved. However, if only clock frequencies are simply increased, the increase in scheduling load is caused to severely reduce the performance of the system. In order to solve this contradiction, Kurt-Linux uses Utime to improve the clock accuracy in the Linux system [UtimeWeb]: it sets the clock chip to a single trigger state, that is, set one for the clock chip. Timeout, then set a timeout time to set a timeout in the clock interrupt handler when the timeout event occurs. Its basic idea is a precise timing means that we need clock interrupts in a relatively accurate time we need, but not necessarily requires that the system clock frequency reaches this precision. It uses the CPU's clock counter TSC (Time Stamp Counter) to provide accuracy of the CPU frequency.
For the scheduling of real-time tasks, KURT-Linux uses time (TD)-based static real-time CPU scheduling algorithms. Real-time tasks need to express their real-time events to occur during design phases. This scheduling algorithm can achieve better scheduling effects for the tasks of the loop execution.
Kurt - Linux is the advantage of RT-Linux is that you can use Linux system itself system calls, which is originally designed to provide hard-real-time support, but because it is simply simple to use a simple Linux scheduler with a simple LINUX scheduler The time-driven scheduler is replaced, so its real-time process scheduling is easily influenced by other non-real-time tasks, so that the deadline for real-time tasks can not satisfy in some cases, it is also known as strict real-time FIRM REAL-TIME. At present, the application based on KURT-Linux is: ARTS (ATM Reference Traffic System), multimedia play software, etc. In addition, the method used by Kurt-Linux needs to be programmed frequently with the clock chip.
3.3. Red- Linux
Red-linux is a real-time Linux system developed by the University of California Irvine [RedWeb] [wang99], which will be well implemented in the same operating system kernel for real-time scheduling support and Linux. It also supports three types of scheduling algorithms, namely: Time-Driven, Priority-Dirven, Share-Driven.
In order to improve the scheduling particle size of the system, Red-Linux draws on the mechanism of software simulation interrupt manager from RT-Linux, and increases the frequency of clock interrupt. When there is hardware interrupt, Red-Linux interrupt emulation simulation only simply puts the incoming interrupt in a queue and does not perform a real interrupt handler.
In addition, in order to solve the problem that the Linux process cannot be preemptive, Red-Linux inserts a sezimposition in a lot of functions in the Linux kernel, making the process in the internal nuclear state, can also be preemptive to some extent. In this way, the real-time characteristics of the kernel are improved.
Red-linux design goals are to provide a general scheduling framework that can support various scheduling algorithms, which adds the following properties to each task, and use them as the basis for process schedules:
Priority: The priority of the job;
Start-Time: The start time of the job;
FINISH-TIME: The end time of the job;
Budget: How much is the resources you want to use during operation during operation;
These attribute values can be used by adjusting the value of these attributes and what kind of priority in the priority of the scheduler, which can be used to achieve all scheduling algorithms. In this case, three different scheduling algorithms can be seamless, uniformly combined together.
The frame structure of the Red-Linux scheduler is shown in Figure 2:
Figure 2 Red-linux scheduling framework
Red-linux scheduling program consists of two parts, where Schedule Allocator initializes the attribute value in JOB; SCHEDULE DISPATCHER selects a JOB according to Job's attribute values;
3.4. Linux / RK
Linux / RK is developed by the University of Carnegiemelon University in real time and multimedia system laboratories [rkweb] [oikawa98]. It is the specific implementation of this laboratory resource kernel [Rajkumar98] in the Linux system. They first realized the idea of resource cores in RT-MACH, and later used the thoughts of the resource core to modify Linux. The concept of resource kernel is the extension of resource reservation ideas in the network. The application will request reserved resources to the operating system, and the operating system kernel reserves for the application, and can provide timely, Guarantee resource access.
There are two basic concepts in the resource core: resource reservation and resource sets. A resource reserves represents a computing resource, which can be CPU, memory, disk, network bandwidth, etc. In the kernel, a resource reserves a corresponding description of its data structure, and a set of resource sets refers to a set of resources reserved. Under normal circumstances, we make up all resource reserved portions requested by an application to form a resource set, which is convenient for management and assignment.
Linux / RK enhances the functionality of the ordinary Linux kernel, so that the Linux kernel can provide access control, resource reservation, and statistical management for various computing resources in the system. Linux / RK consists of two parts: a normal Linux kernel and a portable resource core; these two parts are interacting through the callback hook Hooks. Similar to RT-Linux, in order to prevent the operation in the Linux kernel and improve the scheduling accuracy, Linux / RK also interrupted the interrupt in the system, and improves the system clock frequency, and only the interrupt will be sent to the Linux core when needed. . In addition, it uses the PROC file system to display resource reservations and use;
3.5 Q Linux
Q Linux is a Soft Real-Time core [Q Linux Web], which is jointly developed by AT & T, Texas University Distributed Multimedia Calculation Lab and the Advanced System Software Laboratory of Massachusetts University. It provides QoS support for real-time multimedia applications.
Q Linux has implemented some of the latest research results in the field of operating system in recent years, including:
- H-SFQ resource scheduling algorithm (hieranchical start-time fair queuing) [Goyal96];
- Lazy receiver processing: LRP) [druschel96];
- Cello Disk Scheduling Algorithm [Shenoy98];
Figure 3 Q Linux system structure
The H-SFQ resource scheduling algorithm is proposed by Pawan Goyal et al, Texas, which uses a hierarchical scheduling idea, first proportionally distribute resources between different application categories, and is provided between application categories Separation of resources, while using different resource scheduling algorithms in each application category. The purpose of this is to provide QoS support in the multimedia system.
LRP technology is a novel idea of designing OS network subsystems, which is proposed by Peter Druschel et al. PETER Druschel et al., Its purpose is to solve the problem of network packets received in normal UNIX and class Unix systems. Traditional UNIX systems do not have explicit scheduling of protocol processes for the coming network package, which generally use interrupt driven mechanisms. When the NIC has an interruption, the CPU immediately performs a series of packet reception and protocol processing operations that are started by the NIC interrupt, and give the final data to the process waiting to receive and wakes up the process. However, this processing can affect the performance of application resource scheduling, and may cause hunger of some application layer tasks when the system is overloaded, reducing network throughput, and even makes the system no response. In order to solve these problems, the core idea of LRP is that every Socket has a queue of an IP package, only protocol processing only when the upper application requests data, and the protocol processing operation is explicitly explicitly revealed. Scheduling. By this way enhances the fairness of resource scheduling, it is possible to provide a certain degree of flow isolation, and can improve the throughput when the system is overloaded.
The Cello Disk Scheduling Algorithm was proposed by the University of Texas Prashant J. Shenoy et al. It supports multiple application categories, such as: interactiveness, and application, high throughput, and software, and soft real-time applications, and equipped to allocate disk access bandwidth to each category application.
In structure, Cello disk scheduling is a two-stage scheduling mode, which consists of a plurality of scheduler related to the application category and a scheduler unrelated to the application category (shown in Figure 4).
Figure 4 Cello disk scheduling
The scheduling of the scheduling of the screamer management time in the Cello scheduling algorithm is used in the Cello Scheduling Algorithm, and the application-related scheduler controls the disk scheduling on the small particle size. As with N application categories above above, Cello uses an application-independent scheduler C and N categories related scheduler, and there is N 1 adjustment queue in the system. The category unrelated scheduler c determines when and how much disk request is moved from the Waiting Queue to the Scheduled Queue; the category-related scheduler Si sorts the request in the waiting queue and according to the scheduling The status of the queue determines where the disk request is inserted into the scheduler.
3.6. Linux -SRT
Linux -SRT is a doctoral project of David Ingram, Cambridge [SRTWEB] [ingram00], is basically an experimental thing. Since INGRAM graduated from Cambridge in 2000, there was no more maintenance. Like Q Linux, Linux -SRT belongs to LINUX in soft real-time.
In Linux -SRT, you can assign a certain percentage of CPU time, which implements a rate-based scheduling mechanism to guarantee QoS requirements for all multimedia applications through the RM algorithm; For applications that make graphic display, resource scheduling in the X server is also critical, so Linux -SRT is the most extension of XFree86, allowing the X server to prioritize graphic display from different X customers; in addition to facilitating users Manage the CPU allocation of each process, Linux -SRT provides a program of a graphical interface. The following is a specific description for the modification of ordinary Linux for Linux -SRT.
Linux -SRT also improves the timing accuracy of the system. However, it did not use the usual practice of placing the clock chip in a single trigger mode, but simply modify the definition of Hz in the Linux kernel, and increases Linux clock frequencies from 1024 per second.
In addition, Linux -SRT adds some new scheduling strategies to Linux on the three scheduling strategies of Sched_other, SCHED_FIFO, SCHED_RR in the original Linux system: sched_pause, sched_idle, sched_qos, sched_var; policy is scheduled for sched_pause When it is ignored by the scheduler, not participating in the schedule execution; the process using the SCHED_QOS scheduling policy can get a guaranteed CPU execution time; the process priority using the SCHED_Idle policy is the lowest, it is assigned to those who can only be scheduled only when the system is idle The process, such as some batch programs; sched_var is a variable priority policy, which is used to solve the priority inversion problem due to critical resource access, that is, a high priority task waiting for low priority tasks A certain critical resources, but the low priority task does not receive the deadlock problem caused by the CPU processing time; at this time, the priority of the low priority task will be given to the high priority task of waiting for resources. Level (priority inheritance) to solve deadlock problems. For real-time tasks using the SCHED_QOS scheduling policy, the RM static priority scheduling algorithm is scheduted; in addition to scheduling, it also uses a dual-scheduled policy, that is, when a real-time task is used in the current scheduling cycle. After all the time slice, before the next dispatch cycle arrive, it is not simply not scheduled to execute it, but use the scheduling policy defined in the Fallback Policy in the process properties to schedule it, let it participate in this wheel with this policy. The dispatch of the remaining time.
Linux -SRT expands system scheduling of traditional several users setup process schedule properties in a POSIX recommendation, allowing users or programmers to use these newly added scheduling features in the backward-compatible case. In addition, in order to use, it also proposes the concept of reserve, a reserve has a node in the / proc file system, which contains the situation of resource allocation; Reserve independent and processes, one process can be related to newly added reserve System call request to join (use) or exit a RESERVE.
3.7. Hard-Hat Linux
Hardhat Linux is a Linux released by Montavista, which is mainly facing various embedded applications [HardHatWeb] [Morgan01]. Hard-Hat Linux's greatest contribution is: In order to solve the problem of Linux in the internal nuclear state, it has developed a pre-type core, and some people think that this method is in an amount, which is a grab ( The kernel of the preemptable.
Its basic idea is to let the scheduler get more execution opportunities, thereby reducing the time interval from one event to the scheduler being executed. The patch package that can be preempting the kernel modifies the SpinLock macro definition and the interrupt return processing code. When the current process can be preempted by "security", the system will call the scheduler for process schedule.
So what can I think a process can be preemptive by "security"? The earliest Linux kernel code believes that once the internal nuclear state is executed, whether it is caused (Trap) or interrupt processing, the current execution process will not be switched until the kernel is considered safely to reset safely. This idea can cause the kernel code to operate in some data structures, that is, it is necessary to securely access data without the use of modification protection of data using mutually exclusive words (such as rotary lock spinlock). However, with the development of the kernel source code, the kernel data access code without the protection mechanism is less and less, so in the top of the root core, if the kernel is not in an interrupt handler, and no Spinlock protected code, It is considered that the process switch can be performed "safe". The sewage kernel is some modifications to the ordinary Linux core:
The sewage kernel adds a data item to the Task Struct data structure: preempt_count. This data item is used by macro preempt_disable (), preempt_enable (), and preempt_enable_no_resched (). Preempt_Disable increments the preempt_count count, and preempt_enable is decrement to Preempt_Count. Preempt_enable macro looks at the content of the preempt_count and ned_resched domain of the current process. If preempt_count is 0 and NEED_RESCHED is 1, then call the preempt_schedule () function. This function will add a big value to the preempt_count item of the current process (such as letting preempt_counter = preempt_counter 0x4000000), then call the process scheduling function Schedule (), and then subtract this value from the process preempt_count after the schedule function returns. The scheduling function is also modified, it detects whether the process_counter is very large (this is to block some of the ordinary scheduling processes for the preemptive schedule), and then perform the preemptive scheduling.
The seizuated kernel patch also modified the spinlock code. In spin_lock () and spin_TRY_LOCK, the call to Preempt_Disable is added to spin_unlock () adds calls for preempt_enable.
Also the seizuated kernel patch also modified the code returned by the interrupt, increasing the call to preempt_enable.
So we can see according to the above three modifications, the prime schedule of the kernel occurs in the following case: When the SpinLock is released, or when the interrupt is returned, if the new_resched that the process is running is labeled, the preemptive scheduling is performed.
3.8. Silk
Silk represents Scout in Linux Kernel, which is a vertical structural operating system for Pathton's scheduling vertical structure operating system (SilkWeb] [Bavier01]. It implements a Scout operating system as a module of Linux.
The main purpose of the SILK system is to support some network QoS, which supports explicit scheduling for network pack processing, and this scheduling is done in Path. The novelty of the Path concept is that unlike traditional task-based schedule, it is scheduling from another perspective of the system, that is, the network data stream and its processing are scheduled. In detail, a PATH consists of a string of data processing or data conversion when a data stream is generated by a data stream, and the resources consumed by the corresponding data stream are also homed to the PATH. Studies have shown that this architecture is particularly suitable for distributed multimedia systems with QoS requirements and software routing equipment. The picture below is a picture for what is Path, which shows a TCP PATH: Figure 5 A TCP PATH
In implementations, the SILK system replaces the network subsystem in the Linux system with its own protocol stack. The Linux application creates and uses Paths through socket, almost no modification of the application itself.
Figure 6 illustrates the structure of the SILK system. In the left half of the figure, the SILK module, and network device driver, the Socket interface layer, and the package filter interface NetFilter exchange data. Silk also modified the scheduling parameters of the Linux task to affect the scheduling decision of the Linux process scheduler. The right part of the figure shows two two paths in Silk. The Silk module has its own CPU scheduler, which cooperates and coordinated with the CPU scheduler in the Linux system. This cooperation is represented by Linux Thread in the figure, and SILK will control the Linux scheduler by performing this thread.
Figure 6 Structure of SILK system structure
Silk provides a new Socket protocol in the operating system so that the upper application calls the underlying SCOUT PATH. In order to intercept the IP package before Linux, Silk Insert a Netfilter Hook through the Linux 2.4 kernel, all arrivals are redirected to the hook, if Silk finds a corresponding network package PATH, let Linux kernel discard the package, which is processed by Silk.
With regard to the CPU schedule, Silk has its own CPU scheduler and thread pack, and the scheduling program of the Linux system coexists, in the Linux system with Silk, we generally call the Silk thread by the Silk scheduling to a PATH ( Thread), and ordinary things called task (task); Silk implements its thread scheduling on a Linux kernel task, this kernel task is created when Silk is initialized, and the kernel The priority of the task is set to the highest priority real-time task, so Silk's kernel task is almost as long as it is ready to run, and only other common tasks in the Linux system when the kernel task is initiating the CPU. . SILK makes the CPU out of the normal Linux task are implemented by scheduling a thread called Linux Thread in Silk Thread, which is essentially a normal scheduler representing Linux in Silk's dispatch space. Silk After calling Linux Thread, Silk's kernel task representing Silk is set to non-unferrible state until it runs other processes, and the high priority SILK core task will receive the CPU. So this implementation mechanism allows SILK to schedule Linux Thread, the Linux scheduler can have a chance to schedule a further process. 4. Summary of real-time Linux implementation
Summarize the implementation of the various real-time Linux described above, which focuses on different design objectives, focusing on the common Linux operating system for real-time support from different side.
For Linux system timelines, the general solution is to program the real-time clock as a single trigger, and then use the CPU's clock count register to provide up to the Timer CPU clock frequency. This method is used like RT-Linux and Kurt-Linux.
For problems that the Linux process cannot be preempted when entering the kernel, the current solution has the method of plugging the seizure point in the kernel function, and the Hardhat is also modified by modifying the macro definition of SpinLock and the interrupt return processing code. Specusible kernel;
For methods in the Linux driver, the software simulation interrupt controller used by RT-Linux can effectively solve this problem;
For problems with lack of real-time scheduling mechanisms and scheduling algorithms in the Linux system, there are currently many new operating system scheduling frameworks and scheduling algorithms with Linux implementation, such as a universal real-time scheduling framework defined by Red-Linux; Q Linux The hierarchical CPU scheduling framework, and novel scheduling algorithms such as H-SFQ, and Cello disk scheduling algorithm, etc.; Silk uses the network processing of a packet into Path and then scheduling between PATH.
For the scheduling of the protocol processing and interrupt processing, the solution is basically a delayed technology, the arrival of the protocol package only copies it into a queue in the network card interrupt process, only when the upper layer application requests data The protocol is performed when the package is performed, and the processing time of the protocol is recorded in the corresponding process. In addition, Silk is for those network routing nodes. Due to the processing such as road, there is no corresponding upper application, so SILK is clearly scheduled between the network processing of the kernel.
Therefore, in general, from the development direction, the development of real-time Linux has the following four ideas:
Providing support for hard real-time, specific methods are: increase the clock accuracy, solve the problem of blocking interrupts and kernel states that cannot be preempted, represent system RT-Linux, Kurt-Linux, in fact, most of the real-time Linux has used similar to RT-Linux Increase the idea of clock accuracy and software interrupt manager; in general, there is a contradiction between the kernel supports hard real-time and using traditional Linux rich system calls, so that it is independent separately like RT-Linux. Small hard real-time operating system; but due to software simulation terminal controllers, improve clock accuracy, as well as the introduction of ideas such as the kernel, this contradiction is slowly resolved. Provide support for real-time multimedia applications, initiatives: introduction of novel scheduling algorithms (network package schedule, process scheduling, disk scheduling), representative system: Q Linux, Linux -SRT;
Introducing novel scheduling frameworks and resource management ideas to better support QoS requirements in the network system, such as the idea of operating system scheduling in the vertical structure in Silk, the thoughts of grading schedules in Q Linux, and RED-Linux A universal scheduling framework and the thoughts of resources used in Linux / RK;
The convenient task QoS management interface function and the implementation of the management program, such as the concept of resources reserved in various resources in the operating system proposed by Linux / RK; Linux -SRT is added to the user conveniently using the newly added real-time scheduling support. API, as well as the concept of Reserve, etc.
In the actual system, the real-time Linux technology is specifically used, and it is necessary to determine according to the specific system requirements. If the target system is a hard real-time system such as machine control or missile flight attitude, RT-Linux is a good solution; if a system is not so strict, it is not so strict, but it is not a soft real system, then Drawing from Kurt- Linux thinking and some ideas that can be presented in order to improve the LINUX response speed; if the target system is a soft real-time application like real-time multimedia systems, or a better way to provide better in high load states The gate of the throughput server system, then Q Linux and Red-Linux provide a good reference; if it is used to apply Linux to network nodes like routers, you can learn from Silk's implementation idea.
references
[Wang99]
YU-Chung Wang and Kwei-Jay Lin, Implementing a General Real-Time Scheduling Framework in The Red- Linux Real-Time Kernel, IEEE Real-Time Systems Symposium, 1999
[Gopalan01]
Kartik Gopalan, Real-Time Support in General Purpose Operating Systems, Tech Report, 2001
[Krishna01]
C. M.Krishna, Kang G.Shin, Real-Time Systems, Tsinghua Press, 2001
[Nieh01]
Jason Nieh, Chris Vaill, Hua Zhong, Virtual-Time Round-Robin: An O (1) Proce sectional Share Scheduler, Proceedings of the 2001 Usenix Annual Technical Conference, 2001
[RT Linux Web]
http://www.rt Linux .org / OR
http://fsmlabs.com/[barabanov97]
Michael Barabanov, A Linux -Based Real-Time Operating System, A Master Hesi, New Mexico Institute of Mining And Technology, Socorro, New Mexico, 1997
[Kurtweb]
http://www.ittc.ku.edu/kurt/
[SRINIVASAN]
Balaji Srinivasan, A Firm Real-Time System Implementation using Commercial Off-The-Shelf Hardware and Free Software, Master Thesis, Department of Electrical Engineering and Computer Science, University of Kansas, Feb, 1998
[Redweb]
http: // linux .ece.uci.edu / red- linux /
[Rkweb]
Http://www-2.cs.cmu.edu/~rajkumar/ linux -rk.html
[Rajkumar98]
Raj Rajkumar, Kanaka Juvva, Anastasio Molano and Shui Oikawa, Resource Kernels: A Resource-Centric Approach to Real-Time Systems, In Proceedings of the SPIE / ACM Conference on Multimedia Computing and Networking January 1998
[Oikawa98]
Shui Oikawa and Raj Rajkumar, Linux / RK: a Portable Resource Kernel in Linux, in IEee Real-Time Systems Symposium Work-In-Progress, Madrid, December 1998
[Q Linux Web]
http://lass.cs.umass.edu/software/qlinux/
[Goyal96]
P. Goyal and X. Guo and H.M. Vin, A Hierarchical CPU Scheduler for Multimedia Operating Systems, Proceedings of 2nd Symposium on Operating System Design and Implementation (OSDI'96), Seattle, WA, pages 107-122, October 1996.
[Druschel96]
Peter Druschel, Gaurav Banga, Lazy Receiver Processing (LRP): A Network Subsystem Architecture for Server Systems, Proceedings of the 2nd Symposium on Operating System Design and Implementation (OSDI'96), Seattle, WA, Pages 261-275, October 1996
[Genoy98]
Pshenoy and H M. Vin, Cello: a Disk Scheduling Framework for Next Generation Operating Systems, Proceedings of ACM SIGMETRICS Conference, Madison, Wi, Pages 44-55, June 1998.
[SRTWEB]
http://www.srcf.ucam.org/~dmi1000/ linux -SRT / [ingram00]
David Ingram, Integrated Quality of Service Management, Ph.d. Thesis, Jesus College, University of Cambridge, 2000
[HardhatWeb]
http://www.montavista.com/
[Morgan01]
Kevin Morgan, Preemptible Linux: a Reality CHECK, MONTAVISTA White Paper, 2001
[SilkWeb]
http://www.cs.princeton.edu/nsg/scout/
[Bavier01]
Andy Bavier, Thiemo Voigt, Mike Wawrzoniak, Larry Peterson, Silk: Scout Paths in The Linux Kernel, Technical Report, NOV 2001
[Utimeweb]
http://www.ittc.ku.edu/utime/
author information
Zhang Huanqiang, Male, Ph.D., Research Center, Multimedia Communication and Network Engineering Research Center, Chinese Academy of Sciences, Research Interests for home networks, real-time systems, video conferences, etc. by
EzHQ@cas.ac.cn can contact him.
Full article:
IBM DeveloperWorks China website
