Mitigating starvation of Linux CPU-bound processes in the presence of network I/O

In prior research work, it has been demonstrated that Linux can starve CPU-bound processes in the presence of network I/O. The starvation of Linux CPU-bound processes occurs under the two Linux schedulers, namely the 2.6 O(1) scheduler and the more recent 2.6 Completely Fair Scheduler (CFS). In this paper, we analyze the underlying root causes of this starvation problem and we propose effective solutions that can mitigate such starvation. We present detailed implementations of our proposed solutions for both O(1) and CFS Linux schedulers. We empirically evaluate the effectiveness of our proposed solutions in terms of execution time and incoming traffic load. For our experimental study and analysis, we consider two types of mainboard architectures: Uni-Processing (UP) and Symmetric Multi-Processing (SMP). Our empirical results show that the proposed solutions are highly effective in mitigating the starvation problem for CPU-bound processes with no negative impact on the performance of network I/O-bound processes.     

Interactivity vs. fairness in networked Linux systems

In general, the Linux 2.6 scheduler can ensure fairness and provide excellent interactive performance at the same time. However, our experiments and mathematical analysis have shown that the current Linux interactivity mechanism tends to incorrectly categorize non-interactive network applications as interactive, which can lead to serious fairness or starvation issues. In the extreme, a single process can unjustifiably obtain up to 95% of the CPU! The root cause is due to the facts that: (1) network packets arrive at the receiver independently and discretely, and the “relatively fast” non-interactive network process might frequently sleep to wait for packet arrival. Though each sleep lasts for a very short period of time, the wait-for-packet sleeps occur so frequently that they lead to interactive status for the process. (2) The current Linux interactivity mechanism provides the possibility that a non-interactive network process could receive a high CPU share, and at the same time be incorrectly categorized as interactive. In this paper, we propose and test a possible solution to address the interactivity vs. fairness problems. Experiment results have proved the effectiveness of the proposed solution.     

A comparison of interactivity in the Linux 2.6 scheduler and an MLFQ scheduler

We implemented a simple multilevel feedback queue scheduler in the Linux 2.6 kernel and compared its response to interactive tasks with that of the new Linux 2.6 scheduler. Our objectives were to evaluate whether Linux 2.6 accomplished its goal of improved interactivity, and to see whether a simpler model could do as well without all of the special cases and exceptions that the new Linux 2.6 scheduler acquired. We describe the two algorithms in detail, report their average interactive response times under different kinds of background workloads, and compare their methods of deciding whether a task is interactive. The MLFQ scheduler performs comparably to the Linux 2.6 scheduler in all response time tests and displays some inadvertent improvements in turnaround time, while avoiding the complex task of explicitly defining interactivity. We maintain an inverse relationship between priority and time slice length, and this seems to be the primary reason that the MLFQ remains simple, yet performs comparably to the Linux 2.6 scheduler. These results may provide some guidelines for designers of new scheduling systems. Copyright © 2006 John Wiley & Sons, Ltd.     

Linux2.6进程调度

分析了与Linux2.6进程调度密切相关的一些重要数据结构,详细描述了进程调度的时机、调度的策略和调度器的工作流程,并从算法分析和HackBench测试两个方面对Linux2.4和2.6进程调度器进行了对比.     

An efficient and comprehensive scheduler on Asymmetric Multicore Architecture systems

Several studies have shown that Asymmetric Multicore Processors (AMPs) systems, which are composed of processors with different hardware characteristics, present better performance and power when compared to homogeneous systems. With Moore’s law behavior still lasting, core-count growth creates typical non-uniform memory accesses (NUMA). Existing schedulers assume that the underlying architecture is homogeneous, and as consequence, they may not be well suited for AMP and NUMA systems, since they, respectively, do not properly explore hardware elements asymmetry, while improving memory utilization by avoid multi-processes data starvation. In this paper we propose a new scheduler, namely NUMA-aware Scheduler, to accommodate the next generation of AMP architectures in terms of architecture asymmetry and processes starvation. Experimental results show that the average speedup is 1.36 times faster than default Linux scheduler through evaluation using PARSEC benchmarks, demonstrating that the proposed technique is promising when compared to other prior studies.     

LGRR: A new packet scheduling algorithm for differentiated services packet-switched networks

Since Quality of Service (QoS) support is a mandatory requirement in the next-generation networking, each router in a packet-switched network must provide a better service to higher-priority packets under any situation such as congestion. We propose in this paper the loan-grant based Round Robin (LGRR) packet scheduler for use in each output port of a router in a DiffServ network. LGRR is a frame-based scheduler to pass traffic streams according to their class types and to their immediate upstream source routers. It uses a loan-grant scheme so that a higher priority traffic stream can be processed quickly by requesting a bandwidth loan from the scheduler. To control the amount of transmitted bits from each stream and to prevent malicious abuse, the bandwidth loan must be paid back from the quantum values acquired in future. LGRR gives a fair opportunity to different traffic streams to access to the network bandwidth. It performs better than MDRR+, MDRR++, and OCGRR in handling traffic under both normal and bursty traffic, but it also gives a better loss and delay performance to the higher-priority traffic when traffic load is very high.     

A QoS-enhanced intelligent stochastic real-time packet scheduler for multimedia IP traffic

A re-configurable, QoS-enhanced intelligent stochastic real-time optimal fair packet scheduler, QUEST, for IP routers is proposed and investigated. The objective is to maximize the system QoS subject to the constraint that the processor utilization is kept at 100%. All past work on router schedulers for multimedia traffic were of earlier generation, in that they focused on maximizing utilization whereas being QoS-aware but without explicitly maximizing the QoS. Keeping utilization fixed at nearly 100%, QoS is dynamically maximized, thus moving to the next generation. QUEST’s other unique advantages are three-fold. First, it solves the challenging problem of starvation for low priority processes; second, it solves the major bottleneck of Earliest Deadline First scheduler’s failure at heavy traffic loads. Finally, QUEST offers the benefit of arbitrarily pre-programming the process utilization ratio. Three classes of multimedia IP traffic, namely, VoIP, IPTV and HTTP have been considered. Two most important QoS metrics, namely, packet loss rate (PLR) and mean waiting time, are addressed. All claims are supported by discrete event and Monte Carlo simulations. The proposed scheduler outperforms benchmark schedulers and offers 37% improvement in packet loss rate and 23% improvement in mean waiting time over the best competing current scheduler Accuracy-aware EDF. The proposed scheduler was validated in a test-bed platform of a NetFPGA® router and results were observed with Paessler® PRTG network monitor.

     

Queueing systems with random service rate

We consider a queue with the arrival process, the service time process and the service rate process as regenerative processes. We provide conditions for its stability, rates of convergence, finiteness of moments and functional limit theorems. This queue can model a queue serving ABR and UBR traffic in an ATM switch; a multiple access channel with TDMA or CDMA protocol and fading; a queue holding best effort or controlled and guaranteed traffic in a router in the integrated service architecture (ISA) of IP-based Internet and a scheduler in the router of a differentiated service architecture. In the process we also provide results for a queue with a leaky bucket controlled bandwidth scheduler. This result is of independent interest. We extend these results to feed-forward networks of queues. We also obtain the results when the arrival rate to the queue can be feedback controlled based on the congestion information in the queue (as in ABR service in the ATM networks or in the real time applications controlled by RTCP protocol in the Internet).     

基于Netfilter的数据包捕获技术研究

在Linux下通常的数据包捕获系统,通过Libpcab函数框架实现,而在该体系下实现的包捕获存在着一些缺陷。在Linux2.4版本后,Linux使用了Netfilter框架,便于用户构建自己的防火墙。在该框架下,通过注册钩子函数,可以轻松实现数据包的捕获。本文通过研究Linux2.4后版本内核中的网络框架Netfilter,给出了在该框架下对数据包进行捕获的设计方案,并集中解决了数据信息提取和使用Netlink实现内核与用户态通信的关键问题。     

Implementation and experimental performance evaluation of a hybrid interrupt-handling scheme

The performance of network hosts can be severely degraded when subjected to heavy traffic of today’s Gigabit networks. This degradation occurs as a result of the interrupt overhead associated with the high rate of packet arrivals. NAPI, a packet reception mechanism integrated into the latest version of Linux networking subsystem, was designed to improve Linux performance to suit today’s Gigabit traffic. NAPI is definitely a major step up from earlier reception mechanisms; however, NAPI has shortcomings and its performance can be further enhanced. A hybrid interrupt-handling scheme, which was recently proposed in Salah et al. [K. Salah, K. El-Badawi, F. Haidari, Performance Analysis and Comparison of Interrupt-Handling Schemes in Gigabit Networks, International Journal of Computer Communications, Elsevier, Amsterdam 30 (17) (2007) 3425–3441], can better improve the performance of Gigabit network hosts. The hybrid scheme switches between interrupt disabling–enabling (DE) and polling (NAPI). In this paper, we present and discuss major changes required to implement such a hybrid scheme in the latest version of Linux kernel 2.6.15. We prove experimentally that the hybrid scheme can significantly improve the performance of general-purpose network desktops or servers running network I/O-bound applications, when subjecting such network hosts to both light and heavy traffic load conditions. The performance is measured and analyzed in terms of throughput, packet loss, latency, and CPU availability.     

Linux环境下路由器中的网络带宽管理

Linux是目前广泛用于路由设备中的操作系统,而流量管理是这种网络操作系统的一个重要功能.研究了Linux系统的流量管理机制,发现当前Linux系统所采用的在网络接口的出口实现的基于网络包调度的流量管理机制缺乏对于网络带宽在系统范围的全局性的管理,也缺乏对于输入流的网络处理的有效管理和调度,从而造成不必要的CPU资源的浪费.为解决这一问题,提出了一种新颖的网络带宽管理机制,它通过调度网络协议处理所占用的CPU时间来实现带宽管理.这种新的机制将网络带宽的管理和调度从网络接口的出口点转移到处理接收到的网络包的系统软件中断处理程序中,从而克服了原来的流量管理机制的缺点.通过系统实现和对比实验,发现该机制本身给系统带来的负载小于Linux原来的流量管理机制,同时可以提供更好的流量隔离,并且能够有效地节省用于网络处理的CPU资源.     

System supports for protocol and application adaptation in vertical handoffs

In overlay networks, the network characteristics before and after a vertical handoff would be drastically different. Consequently, in this paper, we propose an end‐to‐end based scheme to support protocol and application adaptation in vertical handoffs. First, we proposed a Vertical‐handoff Aware TCP, called VA‐TCP. VA‐TCP can identify the packet losses caused by vertical handoffs. If segments losses are due to vertical handoffs, VA‐TCP only retransmits the missing segments but does not invoke the congestion control procedure. Moreover, VA‐TCP dynamically estimates the bandwidth and round‐trip time in a new network. Based on the estimated bandwidth and round‐trip time, VA‐TCP adjusts its parameters to respond to the new network environment. Second, during a vertical handoff, applications also need to be adapted accordingly. Therefore, we design a programming interface that allows applications to be notified upon and adapt to changing network environments. To support our interface, we utilize the signal mechanism to achieve kernel‐to‐user notification. Nevertheless, signals cannot carry information. Thus, we implement the shared memory mechanism between applications and the kernel to facilitate parameters exchange. Finally, we also provide a handoff‐aware CPU scheduler so that tasks that are interested in the vertical‐handoff event are given preference over other processes to attain a prompt response for new network conditions. We have implemented a prototype system on the Linux kernel 2.6. From the experimental results, our proposed protocol and application adaptation mechanisms are shown to effectively improve the performance of TCP and applications during vertical handoffs. Copyright © 2008 John Wiley & Sons, Ltd.     

Linux 2.6内核进程调度分析

Linux操作系统是一种支持多任务、多用户和多处理器的现代通用操作系统。2.6内核的Linux支持O(1)级进程调度算法,支持可抢占内核,相比于2.4内核具有更好的实时性能。文中基于Linux 2.6.10内核源代码,分析了Linux 2.6内核的进程调度系统。并在详细介绍关键数据结构的基础上,阐述了进程调度算法的原理,并对实时进程的支持作了分析。     

基于Linux的流量控制机制研究

为实现QoS,网络节点必须具有流量控制的能力。Linux从内核2.2版起就增加了对网络QoS的支持,并提供了一套强大的流量控制功能。本文首先分析了Linux的协议体系结构、数据传递机制和数据转发过程,再介绍了流量分类、队列管理、流量整形和流量监测等技术,得到了Linux下流量控制机制的原理。     

Traffic-prediction-assisted dynamic bandwidth assignment for hybrid optical wireless networks

Hybrid optical-wireless networks provide the inexpensive broadband bandwidth, vital for modern applications, as well as mobility, and scalability required for an access network. However, in order to provide satisfactory Quality of Service (QoS) on such a non-homogeneous network, innovative designs are required.This paper proposes a novel scheduling mechanism to significantly improve the delay guarantee, while maintaining high-level throughput, by predicting the incoming traffic to optical network units (ONU). The proposed scheduler managed to exploit the available information in hybrid optical-wireless networks, to enhance the ONU scheduler. This results in accurate prediction of incoming traffic, which leads to intelligent and traffic-aware, scheduling and dynamic bandwidth assignment (DBA).Based on the proposed architecture, two DBA algorithms are proposed and their performance is evaluated by extensive simulations. Moreover, the maximum throughput of such network is analyzed. The results show that by using the proposed algorithms, the delay bound of delay-sensitive traffic classes can be decreased by a factor of two, without any adverse effect on the throughput.     

Verification of the legOS Scheduler using Uppaal

This article concentrates on the scheduler in the operating system legOS. LegOS is an open source embedded operating system for the Lego Mindstorms^® system. The scheduler in legOS practices starvation of lower priority threads. In this article the validity of starvation problems is proven through tests of the scheduler and through an Uppaal model of the scheduler wherein the starvation is verified. A new scheduler is designed and modeled in Uppaal. This Uppaal model is used to verify that starvation is no longer a problem in the new design. The new design is implemented in a new scheduler and tests are performed to show that the problem with starvation is no longer present.     

Performance evaluation comparison of Snort NIDS under Linux and Windows Server

In this paper, we present an experimental evaluation and comparison of the performance of Snort NIDS when running under the two popular platforms of Linux and Windows 2003 Server. Snort's performance is measured when subjecting a PC host running Snort to both normal and malicious traffic, and with different traffic load conditions. Snort's performance is evaluated and compared in terms of throughput and packet loss. In order to offer sound interpretations and get better insight into the behavior of Snort, we also measure the packet loss encountered at the kernel level. In addition, we identify key system parameters (for both Linux and Windows) that provide a fine-grained control over the percentage of the CPU bandwidth allocated to Snort application and can consequently impact its performance. We investigate such an impact, and determine the most appropriate values to improve and optimize Snort's performance. Specifically, for Windows we investigate the impact of customizing the Processor Scheduling configuration option; and for Linux, we investigate the impact of tuning the Budget configurable parameter used in the Linux kernel's packet reception mechanism.     

Comparative packet-forwarding measurement of three popular operating systems

This papers measures and compares the network performance (with respect to packet forwarding) of three popular operating systems when used in today's Gigabit Ethernet networks. Specifically, the paper compares the performance in terms of packet forwarding of Linux, Windows Server and Windows XP. We measure both kernel- and user-level packet forwarding when subjecting hosts to different traffic load conditions. The performance is compared and analyzed in terms of throughput, packet loss, delay, and CPU availability. Our evaluation methodology is based on packet-forwarding measurement which is a standard and popular benchmark and evaluation methodology to assess the performance of network elements such as servers, gateways, routers, and switches. Our evaluation methodology considers different configuration setups and utilizes open-source software tools to generate relatively high traffic rates. We consider today's typical network hosts of modern processors and Gigabit network cards. Our measurements show that in general Linux exhibits superior overall performance in the case of kernel (or IP) packet forwarding, whereas Windows Server exhibits superior performance in the case of user-level packet forwarding.     

Deadline scheduling in the Linux kernel

During the last decade, there has been a considerable interest in using Linux in real‐time systems, especially for industrial control. The simple and elegant design of Linux guarantees reliability and very good performance, while its open‐source license allows to modify and change the source code according to the user needs. However, Linux has been designed to be a general‐purpose operating system. Therefore, it presents some issues like unpredictable latencies and limited support for real‐time scheduling. In this paper, we present our experience in the design and implementation of the real‐time scheduler that has been recently included in the Linux kernel. The scheduler is based on the Resource Reservation paradigm, which allows to enforce temporal isolation between the running tasks. We describe the genesis of the project, the challenges we have encountered, the implementation details and the API offered to the programmers. Then, we show the experimental results measured on a real hardware. Copyright © 2015 John Wiley & Sons, Ltd.