cgroup 进程调度之 Borrowed-virtual-time (BVT) scheduling

规避 CFS 的非公平性问题(睡眠补偿等等),99年发表论文,15年heracles论文重新对 bvt 做了改进,从论文作者的名字,我扒到了对应的源码,这哥们把源码放到gist上了

1. cfs 睡眠补偿机制

在讲bvt之前,有必要先介绍一下 cfs 的睡眠补偿机制
cfs 调度器的目标是公平,cfs 希望每个进程得到调度的机会是一样的,这个“机会”是用 vruntime 来衡量的
但是如果一个进程一直在睡眠,那么它的 vruntime 是非常小的,当睡眠中的进程被唤醒时,基于 CFS 的调度逻辑,会一直持续运行当前进程,直到 vruntime 不是最小的时候,才会选择下一个进程来调度。
内核为了解决 sleep 进程获得过长时间的问题,增加了一个阈值限制,当进程被唤醒时,取当前运行队列的最小vruntime,并 + 上一个偏移量,这个偏移量默认是 1/2 个调度周期,12ms


overlayfs 差分文件系统原理

overlay文件系统的主要目的是要实现文件系统重叠,docker中的查分机制所依赖的文件系统分层就是依赖这种技术来实现的

1. upper and lower

overlay机制允许将两个文件系统重叠成一个文件系统,其中一个是upper,另一个是lower,对用户的可视顺序是:
upper -> lower
简单来说,如果upper和lower同时存在一个相同的文件,那么用户看到的是upper中的文件,lower中的同路径文件会被自动隐藏
overlay只关心文件,目录是会被穿透的,所以严格来说,overlay重叠的是目录树,而不是“文件系统”
所有的修改都会写入upper,lower是只读的。upper的文件系统必须支持trusted.*扩展属性,所以upper是不支持NFS的

2. 用法

mount -t overlay overlay -olowerdir=/lower,upperdir=/upper,workdir=/work /merged
如果不写upper和workdir,就是只读挂载
mount -t overlay overlay -olowerdir=/lower /merged


逻辑回归的代价函数

线性回归:2 – 2 – Cost Function (8 min).mkv

逻辑回归:6 – 4 – Cost Function (11 min).mkv

在看吴恩达的机器学习教程时,逻辑回归的代价函数怎么来的一开始没看懂,后来想了一下想明白了,记录一下

我们都知道,线性回归(不管是单变量还是多变量)


docker image 存储剖析

从docker pull开始,看 docker image 的存储过程
# docker pull ubuntu
Using default tag: latest
latest: Pulling from library/ubuntu
5ba4f30e5bea: Pull complete
6874f9870f5f: Pull complete
4c876570bd7d: Pull complete
10fb34ebccea: Pull complete
Digest: sha256:f1b592e2de671105255a0c0b7b2f71a92b829403e8fc845e3482667ecc301780
Status: Downloaded newer image for ubuntu:latest
# docker images
REPOSITORY          TAG                 IMAGE ID            CREATED             SIZE
ubuntu              latest              12543ced0f6f        2 weeks ago         122.4 MB
其中image名字是ubuntu,image的id是12543ced0f6f,在docker中,几乎所有的ID都是通过UUID或者sha256等方式计算出来的


深入理解L1、L2正则化

原文链接:https://zhuanlan.zhihu.com/p/29360425

正则化(Regularization)是机器学习中一种常用的技术,其主要目的是控制模型复杂度,减小过拟合。最基本的正则化方法是在原目标(代价)函数 中添加惩罚项,对复杂度高的模型进行“惩罚”。其数学表达形式为:

[公式]

式中 [公式][公式]为训练样本和相应标签, [公式] 为权重系数向量; [公式] 为目标函数, [公式] 即为惩罚项,可理解为模型“规模”的某种度量;参数[公式] 控制控制正则化强弱。不同的 [公式] 函数对权重 [公式] 的最优解有不同的偏好,因而会产生不同的正则化效果。最常用的 [公式] 函数有两种,即 [公式] 范数和 [公式] 范数,相应称之为 [公式] 正则化和 [公式] 正则化。此时有:

[公式]
[公式]

本文将从不同角度详细说明 [公式][公式] 正则化的推导、求解过程,并对 [公式] 范数产生稀疏性效果的本质予以解释。


文件系统隔离之 – 深入 prjquota,源码剖析

ext4 prjquota 实现原理,参考了 xfs prjquota,并且复用了linux 内核的磁盘配额管理机制的大部分实现,所以源码上分析起来还是非常简单的

linux内核本身就已经支持user、group级别的磁盘配额管理,用法可以参考:https://access.redhat.com/documentation/en-us/red_hat_enterprise_linux/7/html/storage_administration_guide/ch-disk-quotas

从文件系统实现层面来看,文件系统本身并不了解什么是uid,gid,因此disk quota的实现一定是在raw file system 之上的。正因为是如此,所以 prjquota 得以复用原有 disk quota 的大量实现,之需要在原有基础之上,扩展一个新的 quota 类型而已

具体内核提交的 patch:https://lore.kernel.org/patchwork/patch/541891/

4.14 内核时,已经进入主干,因此可以参考:https://lxr.missinglinkelectronics.com/linux+v4.14/fs/ext4/

简述一下其基本设计:

  1. 在 super block 中,有一块专门用来存储 project id 用量的元数据区
  2. 每个文件,属于哪个 project id,是记录在文件的 xattr 属性里面的(正是因为 ext4 文件系统支持 xattr 扩展,所以才很方便的移植这个特性)
  3. 文件写入的时候,先查找这个文件的 project id,然后判断当前 project 的 usage + 文件的增量的大小,是否超过 project 的 hardlimit,如果超过,返回 EDOUT,文件写入失败

实践 pytorch.nn.linear 线性回归

nn.Linear 定义:https://pytorch.org/docs/stable/generated/torch.nn.Linear.html#torch.nn.Linear

class torch.nn.Linear(in_features: int, out_features: int, bias: bool = True)

其中:

  • in_features – 每次输入的样本数,默认是1
  • out_features – 每次输出的样本数,默认也是1
  • bias – If set to False, the layer will not learn an additive bias. Default: True

pytorch 本身是没有神经网络层的概念的,所以如果我们要定义一个神经网络,需要通过 torch.nn.Module 来实现

假设我们有很多样本数据,符合模型 y = wx + c,我们也可以用 torch 来直接生成一些随即样本数据

x = torch.unsqueeze(torch.linspace(0, 1, 300),dim=1)
y = 2 * x + torch.rand(x.size())


CFS 调度算法的基本原理

调度单元有三种状态:

  1. 睡眠:不在 CPU 运行队列里
  2. PENDING:调度单元被唤醒,比如网络数据包到达,IO ready等,进程被唤醒,进入运行队列,但是还没得到 CPU 时间片
  3. 运行:调度单元得到 CPU 控制权,开始运行

调度延时其实就是指进程被唤醒,进入运行队列到得到 CPU 时间片之间的等待时间,也就是处于 PENDING 状态的时间

Linux 通过一个红黑树来维护所有进程的状态,每个 CPU 都会有一个运行队列,管理所有进程和进程组【注意,进程组也是内核的一个基本的调度单元】

每个调度单元都会有一个 vruntime 的属性,用来记录当前调度单元以运行的虚拟时间


CPI2: CPU performance isolation for shared compute clusters

这是google在13年发表的一片论文:https://dl.acm.org/doi/10.1145/2465351.2465388

这篇论文里,最有价值的地方在于建立了一个对业务透明,能够实时感知在线业务运行质量,并且能自动优化的机制

基本概念

  • CPI:uses cycles-per-instruction,平均每条指令消耗的时钟周期(时间),相当于指令执行的代价。

现代处理器均有多级缓存,类似下面这样的一条指令:“ mov 0x200160(%rip),%rax ”,其执行时间由缓存是否命中决定(L0/L1/L2)。


cpu iowait 到底算 busy 还是 idle?

我们在追查线上问题的时候,经常会碰到 cpu iowait 很高的 case,并且通常这种机器伴随着难登录、操作卡顿等现象,一看 cpu idle 还非常低,以为机器 cpu 被打爆了

其实不然,真正的罪魁祸首是 io,而不是 cpu。你看到的 cpu idle 很低,其实是因为部分 idle 时间被算到了 iowait 里面,导致看起来 cpu idle 很低而已。而纯粹的 iowait 很高,并不会引起系统卡顿,如果你发现系统卡顿,大概率是因为 io 异常的磁盘正好是根分区而已,不过今天我们不讨论 io,只讨论 cpu

那么问题来了,cpu iowait 到底是算 busy 还是 idle?

  1. 如果 cpu iowait 不算 busy,那衡量一个 cpu 的繁忙程度的指标到底是什么?
  2. 如果 cpu iowait 算 busy,这和直觉又不符合啊?既然是 io wait,cpu 都被切换出去执行其他进程了,又何来 busy 一说
  3. 初次之外,内核是如何统计 cpu iowait 的?