LINUX-based real-time system
content:
Part 1: Real-time scheduling algorithm 1. Real-time CPU scheduling algorithm classification 2. CPU scheduling in universal Linux system 3. Various live Linux systems 4. Summary of real-time Linux implementation schemes Reference information about the author
In the Linux area:
Tutorial Tools & Product Codes & Component Articles
Zhang Huanqiang (zhq@iscas.ac.cn) Institute of Multimedia Communication and Network Engineering Research Center, Institute of Sciences, China, October 2003
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.
The first part: Real-time scheduling algorithm introduces what is a real-time system, POSIX 1003.b made such definitions: refers to the system to provide the required level of service within 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 Classified Various Real Time Operating Systems The real-time scheduling algorithm can be divided into the following three categories [wang99] [Gopalan01]: Priority-Driven Scheduling-Pd, based on CPU usage ratio Share-Driven Scheduling-SD), and Time-Driven Scheduling Algorithm (Time-Driven Scheduling-TD), the following three scheduling algorithms are introduced one by one. 1.1. Scheduling algorithm based on priority is assigned a priority to each process based on priority scheduling algorithm. When each process schedules are scheduled, the scheduler always schedules tasks 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 staticly assigned a priority to all processes that are running in those systems. 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 have more 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. Although the proportional shared modification algorithm is simple and effective based on the priority scheduling algorithm, this scheduling algorithm provides a hard-real-time scheduling. In many cases, this scheduling algorithm is not suitable: such as real time multimedia Soft real-time applications such as the conference system. 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. Universal Linux system The CPU scheduling Universal Linux system supports 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 schedule method between the same real-time priority process is different: SCHED_FIFO: Different processes according to static The priority is queued, then in the same priority queue, who is ready to run first, and the running process will not terminate until the following occurs: 1. Have a higher priority process CPU; 2. It blocks yourself because of resource requests; 3. I actively give it to 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 film to each process, and the time slice is in progress The process will give up the execution; the length of the time film can be called by SCHED_RR_GET_INTERVAL; because the Linux system itself is a desktop system, there is some issues that exist when it is applied to real-time applications:
The scheduling unit in the Linux system is 10ms, so it is not able to provide accurate timing; when a process call system call enters the kernel, it is unable to be preempted; the Linux kernel implementation uses a large number of interrupt operations to cause Disrupting loss; due to the use of virtual memory technology, 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 causes the random read and write time, which will be in some cases Affected some deadlines for some real-time tasks; although Linux process scheduling also supports real-time priority, lacks a scheduling mechanism and scheduling algorithm for real-time tasks; its network subsystem protocol processing and other device interrupts have no corresponding correspondence The scheduling of the process is associated, and they do not have a clear scheduling mechanism; 3. Various real-time Linux systems 3.1. RT-Linux and RTAI RT-Linux are the research results of New Mexico Instute Of Technology [RTLinuxWeb [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 RT-Linux framework 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 blocked when the CPU is interrupted, the real-time subsystem in RT-Linux will intercept this request, record it, and actually unclear the hardware interrupt, so that the system due to the sealing interrupt is avoided. There is no response in a period of time, thereby improving real-time. When the hardware is interrupted, RT-Linux intercends the interrupt and determines whether or not 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 can provide more than a dozen micro-second scheduling granularity by setting the real-time clock of the system to a single trigger state. The task scheduling in the RT-Linux real-time subsystem can use the priority driving algorithm such as RM, EDF, or other scheduling algorithms can also be employed. RT-Linux is indeed 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, so 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, you need to do a lot of work in multimedia processing. Italy's RTAI (Real-Time Application Interface "is 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 abstraction. 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 precision [KurtWeb] [Srinivasan]. Different from RT-Linux separately implemented a real-time kernel, Kurt -Linux is implemented on a general Linux system, which 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, in normal state, it uses normal Linux scheduling strategies, only run 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 clock accuracy in the Linux system [UtimeWeb]: it sets the clock chip to a single trigger state (one shot mode), 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 relative to RT-Linux is that you can use the Linux system itself system call, 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 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, Kurt-Linux is available in: ARTS (ATM Reference Traffic System), multimedia play software, etc. In addition, Kurt-Linux uses this method that 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's interrupt simulation only simply puts the coming 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 preempted, Red-Linux inserts a preliminary term in a lot of functions of 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 the basis for process schedules: priority: Job priority; START-TIME: The start time of the job; FINISH-TIME: The end time of the job; BUDGET: How much is the resource you want to use during the operation; use these attributes and what kind of priority sequential sequential sequence Attribute values, almost all scheduling algorithms can be implemented. In this case, three different scheduling algorithms can be seamless, uniformly combined together. The framework structure of the Red-Linux scheduler is shown in Figure 2:
Figure 2 Red-Linux Scheduling Framework
The scheduling program of Red-Linux consists of two parts, where Schedule Allocator initializes attribute values in the JOB; SCHEDULE DISPATCHER selects a JOB according to the job value of JOB; 3.4. Linux / rk Linux / RK by Carnegiemelon University Real-Time and Multimedia System Laboratory [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 seal in the Linux kernel, the Linux / RK is also interrupted in the system, and the system clock frequency is improved, and the interrupt will be sent to the Linux kernel when it is required. . In addition, it uses the PROC file system to display resource reserved and use; 3.5. Qlinux Qlinux is a kind of soft and real-time, which is jointly developed by AT & T, Texas University Distributed Multimedia Calculation Lab and Massachusetts University Advanced System Software Laboratory (Soft Real-time) core [QlinuxWeb]. It provides QoS support for real-time multimedia applications. QLinux implemented some of the latest research results in the operating system in recent years, including: HIERARCHICAL START-TIME FAIR QUEUING [Goyal96]; - Lazy Receiver Processing: LRP) [DRUSCHEL96]; - Cello Disk Scheduling Algorithm [Shenoy98]; Figure 3 QLinux 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 University [SRTWEB] [ingram00], is basically an experimental thing, and since Ingram graduated from Cambridge in 2000, the project will no longer maintain . Like QLinux, Linux-SRT belongs to LINUX in soft real-time. In Linux-SRT, a task can be assigned 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; additional CPU is not only the only resources that affect multimedia applications. For those applications that make graphic display, the resource scheduling in the X server is also critical, so Linux-SRT is the most extension to XFree86, so that the X server can prioritize graphic display request from different X customers; in addition to convenient users Managing 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 policies to Linux on the three scheduling policies in the original Linux system, SCHED_PAUSE, SCHED_IDLE, SCHED_PAUS, SCHED_IDLE, SCHED_QOS, SCHED_VAR; Policies 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 extends the system scheduling of traditional several users to set up process schedule properties in accordance with POSIX, 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's facial orientation [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 structure operating system SCOUT in Linux in Linux (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 implementations summarize the implementation of the above real-time Linux, 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 in 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 also has achieved one by modifying the macro definition of Spinlock and the interrupt return processing code. Specusible kernel; method for the blocking interrupt in the Linux driver, the software simulation interrupt controller used by RT-Linux can effectively solve this problem; for the lack of real-time scheduling mechanism and scheduling algorithm 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; qlinux's 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: improving clock accuracy, solving blocking interrupts and kernel states cannot be preempted, On behalf of the system RT-Linux, Kurt-Linux, most real-time Linux used the idea of similar to RT-Linux improved clock accuracy and software interrupt manager; in general, the kernel supports hard real-time and use traditional Linux There is a contradiction between the rich system calls, so that the RT-Linux is separately realized a separate small hard real-time operating system; but due to software simulation terminal controllers, improve clock accuracy, and grabbing kernels. Introduced, 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: QLinux, Linux-SRT; introduce novel scheduling framework and resource management ideas to better support QoS requirements in the network system, such as the operating system scheduling of vertical structures in Silk, the thoughts of qlinux, and the resources used by Red-Linux and resources used in Linux / RKs Reserved ideas; convenient task QoS management interface functions and management procedures implementations, such as the concept of resources reserved in various resources in the operating system proposed by Linux / RK; Linux-SRT is conveniently used for users to easily use new real-time Scheduling support and increase the API, and the concept of proposed RESERVE, etc .; in the actual system, specifically use the real-time Linux technology, it is necessary to determine according to specific system requirements. If the target system is a hard real-time system such as machine tool 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 speed of the Linux response; if the target system is a soft real-time application like real-time multimedia systems, or a hopes can provide better in high load states The throughput server system, then QLinux and Red-Linux's thoughts provide a good reference; if it is to apply Linux to network nodes like routers, you can learn from Silk's implementation ideas. 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] CMKrishna, Kang G.Shin, Real-time Systems, Tsinghua Press, 2001 [Nieh01] Jason Nieh, Chris Vaill, Hua Zhong, Virtual-Time Round-Robin: An O (1) Proportional Share Scheduler, Proceedings of the 2001 USENIX Annual Technical Conference, 2001 [RTLinuxWeb] http://www.rtlinux.org/ or http://fsmlabs.com/[Barabanov97]Michael Barabanov, A Linux-based Real -Time Operating System, A Master Thesis, 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 Hesis, Department of Electrical Engineering and Computer Science, University of Kansas, Fe B, 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 [QlinuxWeb] http://lass.cs.umass.edu/software/qlinux/ [Goyal96] P. Goyal and X. Guo and HM Vin, a hierarchical cpu scheduler for multimedia Operating systems, procedings of 2nd Symposium On ON ON OPERATING SYSTEM Design and Implementation
