自旋锁是一种会让尝试获取它的线程陷入循环 （“自旋”）并不断检查锁是否可用的锁 1。 和mutex 不同，mutex 可以睡眠，将cpu让渡给其他的程序，而自旋锁则是占据着cpu资源忙 等。忙等最主要的优点是，避免了调度所带来的上下文开销, 可以提升等锁进程获得锁的延 迟。另外，如果加锁的临界区很小，自旋锁忙等所带来的开销，可能会小于上下文切换的开 销，自旋锁的收益就会非常大。所以，自旋...

在计算机科学中，如果任何线程的故障或挂起不会导致其他线程的故障或挂起，则称该算法 为非阻塞算法1。根据非阻塞算法的达到效果，可以分为两类: wait-free: if there is also guaranteed per-thread progress lock-free: if there is guaranteed system-wide progress Obstr...

简介 负载计算公式 \[u = u_0 + u_1 * y + u_2 * y^2 + u_3 * y_3 + ... \tag{1} \\ y ^ {32} = 0.5\] 也就是说, 当前的负载会随着时间衰减, 经过 32 个时间单位会 衰减为之前的$\frac{1}{2}$ 该算法会对一段时间内的负载做估计，以更好的预测该se未来的负载以便实现per-se负 载均衡。 假如...

6 Fairness Analysis of the EEVDF Algorithm In this section we determine bounds for the service time lag. First we show that during any time interval in which there is at least one active client, t...

overflow 我们本篇文章主要看下, linux kernel 第一版引入 eevdf 时的patch 分析。 在介绍整个patchset之前，我们先来回忆下 eevdf 论文大致的算法。 eevdf 是结合了 将 EDF 实时算法以及比例份额算法进行结合, 可以让其 按照 类似于 EDF 算法处理批处理任务。 对此，需要做到: client 需要将自己的对时间片的需求，拆...

4. Fairness in Dynamic Systems 本节讨论了 dynamic system 的公平性问题。主要包括三种动作: client jion client leave client change weight 在理想环境下, 这都不是问题，因为 $lag_i = 0$(都是0)。但是在离散的时间片分配中, 任务总会带着$lag$离开加入竞争, 我们先...

前言 本文参考eevdf论文, 介绍eevdf 算法涉及到的概念，基本原理，以及公式推导, 关于eevdf不难理解的章节, 本文 将以概括的方式涵盖, 较难理解的章节，本文 将以中英翻译的方式将论文内容展现出来。 关于论文中的公式，本文尽量将其详细的展开推导。并添加一些直观上的理解。 1. introduce 论文中的第一章节主要讲解了调度器的职责以及面临的挑战: 职责: ...

weight 计算公式 Linux weight 和 nice 有一个对应关系, 具体的公式为: x为nice y为weight \[\begin{align} NICE_0\_weigth = 1024 , x \in [-20,19] \\ f(x) = NICE_0\_weight * \frac{1}{1.25^x} \end{align}\] 在kernel 代码中静态保...

Chapter 2 Resource Management Framework This chapter presents a general, flexible framework for specifying resource management policies in concurrent systems. Resource rights are encapsulated by a...

overflow 本篇文章