2018年10月

相对于栈而言,堆这片内存面临着一个稍微复杂的行为模式:在任意时刻,程序可能发出请求,要么申请一段内存,要么释放一段已经申请过的内存,而且申请的大小从几个字节到几个GB都有可能,我们不能假设程序一次申请多少堆空间,因此,堆的管理显得较为复杂。

那么,使用 malloc() 在堆上分配内存到底是如何实现的呢?

一种做法是把 malloc() 的内存管理交给系统内核去做,既然内核管理着进程的地址空间,那么如果它提供一个系统调用,可以让 malloc() 使用这个系统调用去申请内存,不就可以了吗?当然这是一种理论上的做法,但实际上这样做的性能比较差,因为每次程序申请或者释放堆空间都要进行系统调用。我们知道系统调用的性能开销是比较大的,当程序对堆的操作比较频繁时,这样做的结果会严重影响程序的性能。

比较好的做法就是 malloc() 向操作系统申请一块适当大小的堆空间,然后由 malloc() 自己管理这块空间。

malloc() 相当于向操作系统“批发”了一块较大的内存空间,然后“零售”给程序用。当全部“售完”或程序有大量的内存需求时,再根据实际需求向操作系统“进货”。当然 malloc() 在向程序零售堆空间时,必须管理它批发来的堆空间,不能把同一块地址出售两次,导致地址的冲突。于是 malloc() 需要一个算法来管理堆空间,这个算法就是堆的分配算法。

malloc()和free()的分配算法

在程序运行过程中,堆内存从低地址向高地址连续分配,随着内存的释放,会出现不连续的空闲区域,如下图所示:


图1:已分配内存和空闲内存相间出现

带阴影的方框是已被分配的内存,白色方框是空闲内存或已被释放的内存。程序需要内存时,malloc() 首先遍历空闲区域,看是否有大小合适的内存块,如果有,就分配,如果没有,就向操作系统申请(发生系统调用)。为了保证分配给程序的内存的连续性,malloc() 只会在一个空闲区域中分配,而不能将多个空闲区域联合起来。

内存块(包括已分配和空闲的)的结构类似于链表,它们之间通过指针连接在一起。在实际应用中,一个内存块的结构如下图所示:


图2:内存块的结构

next 是指针,指向下一个内存块,used 用来表示当前内存块是否已被使用。这样,整个堆区就会形成如下图所示的链表:


图3:类似链表的内存管理方式

现在假设需要为程序分配100个字节的内存,当搜索到图中第一个空闲区域(大小为200个字节)时,发现满足条件,那么就在这里分配。这时候 malloc() 会把第一个空闲区域拆分成两部分,一部分交给程序使用,剩下的部分任然空闲,如下图所示:


图4:为程序分配100个字节的内存

仍然以图3为例,当程序释放掉第三个内存块时,就会形成新的空闲区域,free() 会将第二、三、四个连续的空闲区域合并为一个,如下图所示:


图5:释放第三个内存块

可以看到,malloc() 和 free() 所做的工作主要是对已有内存块的分拆和合并,并没有频繁地向操作系统申请内存,这大大提高了内存分配的效率。

另外,由于单向链表只能向一个方向搜索,在合并或拆分内存块时不方便,所以大部分 malloc() 实现都会在内存块中增加一个 pre 指针指向上一个内存块,构成双向链表,如下图所示:

链表是一种经典的堆内存管理方式,经常被用在教学中,很多C语言教程都会提到“栈内存的分配类似于数据结构中的栈,而堆内存的分配却类似于数据结构中的链表”就是源于此。

链表式内存管理虽然思路简单,容易理解,但存在很多问题,例如:

  • 一旦链表中的 pre 或 next 指针被破坏,整个堆就无法工作,而这些数据恰恰很容易被越界读写所接触到。
  • 小的空闲区域往往不容易再次分配,形成很多内存碎片。
  • 经常分配和释放内存会造成链表过长,增加遍历的时间。

针对链表的缺点,后来人们提出了位图和对象池的管理方式,而现在的 malloc() 往往采用多种方式复合而成,不同大小的内存块往往采用不同的措施,以保证内存分配的安全和效率。

内存池

不管具体的分配算法是怎样的,为了减少系统调用,减少物理内存碎片,malloc() 的整体思想是先向操作系统申请一块大小适当的内存,然后自己管理,这就是内存池(Memory Pool)。

内存池的研究重点不是向操作系统申请内存,而是对已申请到的内存的管理,这涉及到非常复杂的算法,是一个永远也研究不完的课题,除了C标准库自带的 malloc(),还有一些第三方的实现,比如 Goolge 的 tcmalloc 和 jemalloc。

我们知道,C/C++是编译型语言,没有内存回收机制,程序员需要自己释放不需要的内存,这在给程序带来了很大灵活性的同时,也带来了不少风险,例如C/C++程序经常会发生内存泄露,程序刚开始运行时占用内存很少,随着时间的推移,内存使用不断增加,导致整个计算机运行缓慢。

内存泄露的问题往往难于调试和发现,或者只有在特定条件下才会复现,这给代码修改带来了不少障碍。为了提高程序的稳定性和健壮性,后来的 Java、Python、C#、JavaScript、PHP 等使用了虚拟机机制的非编译型语言都加入了垃圾内存自动回收机制,这样程序员就不需要管理内存了,系统会自动识别不再使用的内存并把它们释放掉,避免内存泄露。可以说,这些高级语言在底层都实现了自己的内存池,也即有自己的内存管理机制。

池化技术

在计算机中,有很多使用“池”这种技术的地方,除了内存池,还有连接池、线程池、对象池等。以服务器上的线程池为例,它的主要思想是:先启动若干数量的线程,让它们处于睡眠状态,当接收到客户端的请求时,唤醒池中某个睡眠的线程,让它来处理客户端的请求,当处理完这个请求,线程又进入睡眠状态。

所谓“池化技术”,就是程序先向系统申请过量的资源,然后自己管理,以备不时之需。之所以要申请过量的资源,是因为每次申请该资源都有较大的开销,不如提前申请好了,这样使用时就会变得非常快捷,大大提高程序运行效率。

前言

本文来自于C语言中文网
在编写代码的过程中,相信大家肯定遇到过这样的情况:代码能够编译通过,没有语法错误,但是运行结果却不对,反复检查了很多遍,依然不知道哪里出了问题。这个时候,就需要调试程序了。

所谓调试(Debug),就是让代码一步一步慢慢执行,跟踪程序的运行过程。比如,可以让程序停在某个地方,查看当前所有变量的值,或者内存中的数据;也可以让程序一次只执行一条或者几条语句,看看程序到底执行了哪些代码。

在调试的过程中,我们可以监控程序的每一个细节,包括变量的值、函数的调用过程、内存中数据、线程的调度等,从而发现隐藏的错误或者低效的代码。

编译器可以发现程序的语法错误,调试可以发现程序的逻辑错误。所谓逻辑错误,是指代码思路或者设计上的缺陷。

对于初学者来说,学习调试也可以增加编程的功力,它能让我们更加了解自己自己的程序,比如变量是什么时候赋值的、内存是什么时候分配的,从而弥补学习的纰漏。

调试是每个程序员必须掌握的技能,没有选择的余地!

调试器(Debugger)

调试需要借助专业的辅助软件——调试器(Debugger)。现在主流C/C++调试器有下面几种:

1) Remote Debugger

Remote Debugger 是 VC/VS 自带的调试器,与整个IDE无缝衔接,使用非常方便,初学者建议使用该调试器,本教程也以 VS2010 为例讲解调试技巧。

2) WinDbg

大名鼎鼎的 Windows 下的调试器,它的功能甚至超越了 Remote Debugger,它还有一个命令行版本(cdb.exe),但是这个命令行版本的调试器指令比较复杂,不建议初学者使用。

3) LLDB

XCode 自带的调试器,Mac OS X 下开发必备调试器。

4) GDB

Linux 下使用最多的一款调试器,也有 Windows 的移植版,如果你不使用 VC/VS,GDB 将是一个不错的选择。

考虑到大部分读者使用Windows,本教程以 VS2010 为例讲解调试技巧,也即使用 Remote Debugger 调试器。当然你也可以使用 VS2012、VS2013、VS2015 等,它们之间的差别很小。

背景

公司的工资种类繁多,工种繁多,计算方法也经常改动,随着金税三期个人版的实施,开发一个实用的,扩展性高的工资系统非常有必要,系统灵活性比较大,综合考虑用PHP+MySQL来实现

核心需求

  • 与员工系统(employee system)相结合
  • 与考勤系统对接(请假、打卡、节假日)
  • 与人事通知、薪资通知相结合(薪资调整时间,到期时间,扣款,奖励)
  • 员工预支工资(提交预支审批书),推送到工资系统
  • 与福利发放、补发、多次发工资合并
  • 与社保、商业保险相挂钩
  • 关联个税算法,工资的每一个条目是否构成个税计算项目,需要勾选

    实现思路

  • 核心是员工系统
  • 通知系统关联员工系统
  • 工资系统关联员工系统
  • 工资系统中的 字段表 其他系统推送表
    百度脑图
    工资系统架构脑图

关于地图

地图走大道还是高德比较好用,让我感慨的是最近淄博这边修路好多路都没法走通,百度地图给的线路经常走不通,高德一直666

关于开车时看地图

以前开车时把地图打开,听地图报路线,这种做法有个很大的弊端,就是提前不知道该怎么走,尤其是到路口不知道向左还是向右,这次开车打开地图,开启UHD模式,放到方向盘中间(有个不好处就是挡住了仪表盘),提前知道红绿灯,提前知道路线和距离,开车时把控感爆棚。
下一步就是到某宝买个手机支架了