0%

os内存管理的目标是做到高效分配回收内存,支持多进程并发使用,又要做到进程之间的隔离。内存是一堆三极管,电容等器件组成的电路模块。每个内存单元有两个属性,对程序开发特别重要,一个是地址,一个是单元内保存的数据。

物理内存管理

分页机制

分页是CPU和操作系统共同实现的内存管理方式。目的是为了尽可能的减少内存碎片,同时可以让多个进程共享内存。把一个逻辑地址,通过页表转换为一个物理内存地址。转换过程是依靠CPU中的MMU单元。页表的数据是由操作系统来生成。x86架构是在80386推出时(1985年),实现的页机制。

物理内存管理上,只要启动分页机制,就是“虚拟”内存,这一层是CPU的机制(MMU单元的功能)。

OS在此基础上,对每个用户进程进行了隔离,在x86_32上,每个进程都可以访问4G的空间,但其实物理机器上有可能只有1G的内存,这个是通过swap机制实现的。

分页机制可以减少内存碎片。可以把不连续的逻辑地址,可以分配成连续物理内存空间。也可以把连续的逻辑地址,分配成不连续的物理空间。

分页机制可以把不同逻辑地址,映射到相同的物理地址上。

Read more »

系统启动

  1. CPU上电,加载BIOS
  2. BIOS从MBR上加载BootLoader
  3. BootLoader设置保护模式,加载内核
  4. 内核进行初始化,进入用户shell

中断机制

  1. 中断初始化 填中断门描述符
  2. 时钟中断
  3. int 0x80 系统调用 系统调用是操作系统给应用程序提供的接口API。通过中断,应用程序可以对外设、网络进行读写。
  4. trapframe
Read more »

最近在学习清华操作系统原理课程,他们的课程有实验环节,虽然参考了很多xv6,但是他们的有课程视频,还有实验指导书,学起来比mit6.828还是轻松不少。课程基本都已经听完了,实验也都跑通了,后面打算花一周时间把各章收获总结一下。

Read more »

Make 是自动构建工具。根据依赖关系,检查文件的更新时间,一旦有新的依赖文件,就把木匾文件重新构建一次。最早是贝尔实验室1976年开发的,后来GNU在标准make的基础上,增加了一些拓展,目前Linux下的make主要是GNU的make。

Read more »

GCC 内联汇编

GCC内联汇编就是可以在c代码里面加入汇编指令。有部分CPU指令是在C语言中没有提供对应功能的,比如lgdt, lidt等等。这些指令需要通过使用汇编直接操作CPU。在操作系统内核的代码中,这类汇编代码段非常常见,需要学习一下基本语法才能看懂OS内核代码的含义。

AT&T主要区别

  1. 操作数是源地址在前,目的地址在后的顺序in AT&T syntax the first operand is the source and the second operand is the destination
1
2
3
"Op-code dst src" in Intel syntax changes to

"Op-code src dst" in AT&T syntax.
  1. 寄存器名称前面需要加%

  2. 立即数用$开头

  3. 命令后缀’b’,‘w’,‘l’, 表示要操作的内存大小。byte(8-bit), word(16-bit), and long(32-bit)

  4. 内存寻址:

    section:disp(base, index, scale) in AT&T. section:[base + index*scale + disp]

    1
    2
    asm("movl %ecx %eax"); /* 把ecx的数据移动到eax */
    __asm__("movb %bh (%eax)"); /*把bh的一个字节放到eax所指的内存单元中,moves the byte from bh to the memory pointed by eax */
Read more »

矩阵 Broadcasting

Broadcasting就是可以让不同维度的矩阵,做算术运算的一种特殊规则。

规则就是,两个多维矩阵,如果某个维度上两个矩阵的维度不同,则把维度小的那个矩阵,在此维度上的数据"broadcasting"成维度大的那个矩阵,这样两个矩阵,就变成相同大小,就可以进行算术运算了。有个约束就是维度小的那一维必须是1,或者没有这一维,否则就会无法broadcasting。

比如

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
a = torch.randn(3,3)
b = torch.randn(1,3)
print(a)
print(b)
print(a+b)

output:

tensor([[-0.3362, 0.8403, 0.5095], # a [3*3]
[ 0.2355, 1.0402, -0.0055],
[-2.4016, 0.3533, 1.0728]])

tensor([[ 0.9663, -0.1208, 0.6794]]) # b [1*3]

tensor([[ 0.6300, 0.7195, 1.1889], # a+b [3*3]
[ 1.2018, 0.9194, 0.6739],
[-1.4353, 0.2326, 1.7522]])

这样相当于把b矩阵复制成三行,变成一个b’ [3*3] ,然后再和a进行相加

通过这样的方式可以让很多矩阵运算变简单,比如y=Wx+b ,这样b不用变成二维矩阵,他只要是个一维向量就可以依次加到不同列或者不同行上去了。

看到Broadcasting比较酷的一个应用就是在maskrcnn-benchmark代码中,求boxlist_iou时,找相交矩阵坐标点时的处理方式。

1
2
lt = torch.max(box1[:, None, :2], box2[:, :2])  # [N,M,2]
rb = torch.min(box1[:, None, 2:], box2[:, 2:]) # [N,M,2]

box1是N个box,box2是M个box,每个box都是4个数值,表示左上角坐标和右下角坐标。

现在要求box1的N个box分别和M个box之间的相交矩阵的左上角和右下角的坐标。

如果按我原来的思路就是二重循环,挨个遍历,这是简单粗暴的方式,更是最蠢的方法

1
2
3
for i<N  # 遍历N个box1
for j < M #遍历M个box2
res[i][j] = max(box1[i][:2], box2[j][:2])

而maskrcnn-benchmark的处理方式是,先把box1升一维,然后再利用broadcasting,把box1和box2维度都变成[N,M,2],然后再求对应元素的最大和最小值,就能得到需要的坐标点了。代码简单,只有一行,而且还可以利用CPU或GPU的并行计算,性能上也二重循环快两个数量级。

RPN整体逻辑

RPN网络是在faster-rcnn中提出来的,主要是为了替代Selective Search算法。在mask-rcnn中,RPN根据Backbone CNN计算得到的图像feature map,来负责找到2000个可能含有物体的bbox坐标(为了方便,主要以e2e_mask_rcnR_50_FPN_1x.yaml的训练过程为主进行记录和说明)

maskrcnn-benchmark代码中,用RPNModule模块,封装整个RPN的计算过程。RPNModule的几个重要对象为

  • head (RPNHead): rpn的cnn网络,对feature map每个点计算对应的bbox和cls_logits
  • anchor_generator(AnchorGenerator): 根据原图大小和feature map的大小,算出所有anchor在原图上的坐标。
  • box_selector_train(RPNPostProcessor): 根据head计算的分值,选取最高2000个box,送入后续的roi_head的网络中。这部分功能对RPN网络本身的训练没有帮助。如果只是训练RPN网络,这步可以省略。
  • loss_evaluator(RPNLossComputation): 用target的box,在anchor中按一定比例选择正负样本,然后根据前面head计算的结果,计算RPN网络的Loss
    Read more »

maskrcnn-benchmark 源码分析

代码中抽象出来一个model类GeneralizedRCNN。输入images,target到model中,然后返回loss,loss的计算都放在forward函数中了。外层的train函数,只是做iter循环、loss backward、optimizer.step、记录日志等这类比较固化的通用代码。

GeneralizedRCNN里面由三部分组成:backbone,RPN,Roi_head。网络的构建大量使用工厂方法,基本上可以根据配置来创建不同的检测网络,能够支持多种组合。

Read more »

目标检测

CNN在图像识别的任务上非常成功,人们就开始研究更难的任务,目标检测。最直观的想法就是用一个滑动窗口在图片上截取N多小图,然后送进CNN进行分类判断,就能检测出物体。这里的问题是框框太多,计算速度太慢。

因为滑动窗口截图的方式过于简单粗暴,人们又提出了Selective Search算法。根据像素区域的色彩、纹理找出一些可能感兴趣的区域(regions of interest ROI),这样可以节省很多计算量。

RCNN

有了SS算法,加上CNN,大牛Ross Girshick在2014年提出RCNN目标检测算法。思路也挺直观,就是SS算法选区域,然后把小图片缩放成相同尺寸进入CNN,得到特征向量,然后分别进行类别判断和bbox的调整。

rcnn

Fast-RCNN

RCNN在ROI选择上使用了SS算法,但需要进行多次的CNN计算,整体的检测速度还是很慢。所以还是Ross Girshick在2015年又整出来Fast-RCNN目标检测算法。所谓Fast就是减少CNN计算次数。先把图片送入CNN得到Feature Map,然后根据ROI的坐标,直接在Feature Map上截取特征值,然后在进行后续的分类和边框回归。

fast rcnn

RoI Pooling

Fast Rcnn新增了RoIPooling层。由于最后的分类和边框回归是全连接层,需要输入向量的大小是确定且统一的。RoI的框框是大小不一的,原始RCNN是截取原图,把小图进行缩放,可以得到相同大小的特征向量。但是使用RoI从FeatureMap上截取出来的特征向量,是没法缩放的。于是rgb就提出了RoI Pooling。

Pooling这个词翻译成池化。Max Pooling, Average Pooling,或者是RoI Pooling都翻译成池化,“池化”这是什么鬼,这绝对是狗屎翻译。Pooling这个词是有共用,合并的意思的。“池化”这样的翻译,会让人很难理解。

继续说RoI Pooling,RoIPooling的主要思想就是把大小不一的特征向量,变成统一的大小,他在原向量上,划分成固定的M*N份,然后每份做Max Pooling,得到最终统一的一个特征向量。下面这个动图,还是解释的很清楚的。

roi pooling

Faster-RCNN

Fast-RCNN算法提取的检测区域,还是使用SS算法,这个算法因为没法利用GPU,所以这个框架还是比较慢。于是这位大牛Ross Girshick在2015年又提出了Faster-RCNN目标检测算法

faster rcnn

Region proposal network

Faster-RCNN的主要改进是把Selective Search算法替换成一个NN模块,取名叫Region proposal network。我理解RPN就是GPU版本的滑动窗口算法。还记得最早目标检测的方法么,用各种尺寸的框框遍历整张图片,然后把截取出来的小图进行分类判断。RPN其实也差不多,只是这次用默认的大小的边框,截取图片的FeatureMap,然后判断在这个框框中是否有物体,他们管这个预先设定的边框叫anchor。

rpn

对FeatureMap上的每个点都进行一次小型CNN计算,可能是ZF或VGG16之类的网络,然后得出2k个数值,k表示有几个默认框(anchor),每个anchor得到两个值,对这两个值做softmax就能知道在这个位置上,对应的边框里是否有待检测的目标了。如果有目标,则用Roi的坐标值去截取FeatureMap,做最后的分类和回归。

至此,一个相对完整的目标检测网络框架就基本成型了。当然如果看代码,还是会有很多细节。比如在训练过程中的Target Building,Inference时的NMS(非极大值抑制),还有就是GPU上BBox的IoU计算,都是技巧性非常强的代码,值得仔细学习一下。但不管怎样,整体的框架就是这样了。总算是比之前更清楚一点了:)

有意思的地方是,Faster Rcnn论文的作者中有大神KaimingHe,而且那时他们都是在微软工作。同年年底KaimingHe发了ResNet的论文。随后在2016,2017也是这两位再发的ResNeXt,FPN,以及Mask RCNN就都是在Fackbook工作了。在2016年FAIR推出了PyTorch,2018年初又推出Detectron。在物体识别和目标检测上,估计Fackbook可以碾压任何对手了。不知道此刻,微软的心理阴影面积有多大。虽然不能近距离接触大神,看看他们的变化也挺有戏剧性的。

参考文档:

1,What do we learn from region based object detectors

2,Object Detection and Classification using R-CNNs

3,https://deepsense.ai/region-of-interest-pooling-explained/