【2.24】malloc()分配内存、MySQL事务、项目、动态规划

malloc是如何分配内存的？

• 在 Linux 操作系统中，虚拟地址空间的内部又被分为内核空间和用户空间两部分，不同位数的系统，地址空间的范围也不同。比如最常见的 32 位和 64 位系统，如下所示：

• 内核空间与用户空间的区别：

  • 进程在用户态时，只能访问用户空间内存；

  • 只有进入内核态后，才可以访问内核空间的内存；

• 虽然每个进程都各自有独立的虚拟内存，但是每个虚拟内存中的内核地址，其实关联的都是相同的物理内存。这样，进程切换到内核态后，就可以很方便地访问内核空间内存。

• 用户空间内存从低到高分别是 6 种不同的内存段：

  • 代码段，包括二进制可执行代码；

  • 数据段，包括已初始化的静态常量和全局变量；

  • BSS 段，包括未初始化的静态变量和全局变量；

  • 堆段，包括动态分配的内存，从低地址开始向上增长；

  • 文件映射段，包括动态库、共享内存等，从低地址开始向上增长（跟硬件和内核版本有关 (opens new window)）；

  • 栈段，包括局部变量和函数调用的上下文等。栈的大小是固定的，一般是 8 MB。当然系统也提供了参数，以便我们自定义大小；

• 在这 6 个内存段中，堆和文件映射段的内存是动态分配的。比如说，使用 C 标准库的 malloc() 或者 mmap() ，就可以分别在堆和文件映射段动态分配内存。

malloc是如何分配内存的？

• malloc 申请内存的时候，会有两种方式向操作系统申请堆内存。

  • 方式一：通过 brk() 系统调用从堆分配内存

    • 该方式实现方式简单，就是通过 brk() 函数将「堆顶」指针向高地址移动，获得新的内存空间。

  • 方式二：通过 mmap() 系统调用在文件映射区域分配内存；

• 什么场景下 malloc() 会通过 brk() 分配内存？又是什么场景下通过 mmap() 分配内存？

  • malloc() 源码里默认定义了一个阈值：如果用户分配的内存小于 128 KB，则通过 brk() 申请内存；如果用户分配的内存大于 128 KB，则通过 mmap() 申请内存；不同glibc版本不同阈值不同。

malloc()分配的是物理内存吗？

• malloc()分配的是虚拟内存。如果分配后的虚拟内存没有被访问，虚拟内存不会映射到物理内存（发生缺页），这样就不会占用物理内存了。

• 只有在访问已分配的虚拟地址空间的时候，操作系统通过查找页表，发现虚拟内存对应的页没有在物理内存中，就会触发缺页中断，然后操作系统会建立虚拟内存和物理内存之间的映射关系。

malloc(1)会分配多大的虚拟内存？

• malloc() 在分配内存的时候，并不是老老实实按用户预期申请的字节数来分配内存空间大小，而是会预分配更大的空间作为内存池。malloc 默认的内存管理器（Ptmalloc2）为例，malloc(1) 实际上预分配 132K 字节的内存。

  [root@xiaolin ~]# cat /proc/3191/maps | grep d730
  00d73000-00d94000 rw-p 00000000 00:00 0                                  [heap]
  

• 程序里打印的内存起始地址是 d73010，而 maps 文件显示堆内存空间的起始地址是 d73000，会多出来 0x10 （16字节）。

free释放内存，会归还给操作系统吗？

• 针对 malloc 通过 brk() 方式申请的内存的情况，通过 free 释放内存后，堆内存还是存在的，并没有归还给操作系统，而是缓存着放进 malloc 的内存池里。

• 如果 malloc 通过 mmap 方式申请的内存，free 释放内存后就会归归还给操作系统，内存得到真正释放。

为什么不全部使用mmap来分配内存？

• 申请内存是会经过系统调用的，而执行系统调用需要进入内核态，**每次进行运行态的切换会浪费时间。**每次 mmap 分配的虚拟地址都是缺页状态的，然后在第一次访问该虚拟地址的时候，就会触发缺页中断。

• 也就是说，频繁通过 mmap 分配内存，不仅每次都会发生运行态的切换，还会发生缺页中断（在第一次访问虚拟地址后），这样会导致 CPU 消耗较大。

• 为了改进这两个问题，malloc 通过 brk() 系统调用在堆空间申请内存的时候，由于堆空间是连续的，所以直接预分配更大的内存来作为内存池，当内存释放的时候，就缓存在内存池中。等下次在申请内存的时候，就直接从内存池取出对应的内存块就行了，而且可能这个内存块的虚拟地址与物理地址的映射关系还存在，这样不仅减少了系统调用的次数，也减少了缺页中断的次数，这将大大降低 CPU 的消耗。

为什么不全部使用brk来分配内存？

• 如果我们连续申请了 10k，20k，30k 这三片内存，如果 10k 和 20k 这两片释放了，变为了空闲内存空间，但是如果下次申请的内存大于 30k，没有可用的空闲内存空间，必须向 OS 申请，实际使用内存继续增大。随着系统频繁地 malloc 和 free ，尤其对于小块内存，堆内将产生越来越多不可用的碎片，导致“内存泄露”。而这种“泄露”现象使用 valgrind 是无法检测出来的。

• 所以，malloc 实现中，充分考虑了 brk 和 mmap 行为上的差异及优缺点，默认分配大块内存 (128KB) 才使用 mmap 分配内存空间。

free()函数只传入一个内存地址，为什么能知道要释放多大的内存？

• 当执行 free() 函数时，free 会对传入进来的内存地址向左偏移 16 字节（保存内存块的信息，比如大小），然后从这个 16 字节的分析出当前的内存块的大小，自然就知道要释放多大的内存了。

• leetcode213

  该题把环拆成两个队列即可。

  class Solution {int [] dp = new int [1000];public int rob(int[] nums) {int len = nums.length;if(len == 1) return nums[0];return Math.max(action(nums,0,len - 1) , action(nums , 1, len));}public int action(int [] nums , int start , int end){dp[start] = nums[start];if(start + 1 < nums.length){dp[start + 1] = Math.max(nums[start] , nums[start + 1]);}for(int i = start + 2 ; i < end ; i ++){dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);}return dp[end - 1];}
  }
  

• leetcode337

  动态规划就是要记录状态的变化，这里使用长度为2的数组，记录当前节点偷与不偷所得到的最大金钱。

  这道题目算是树形dp的入门题目，因为是在树上进行状态转移，我们在讲解二叉树的时候说过递归三部曲，那么下面我以递归三部曲为框架，其中融合动规五部曲的内容来进行讲解。

  1. 确定递归函数的参数和返回值。要求得到偷与不偷所得的金钱，就要返回一个疮毒为2的数组。参数就是TreeNode。返回的数组就是dp数组，下标为0记录不偷该节点所得到的的最大金钱，下标为1记录偷该节点所得到的的最大金钱。

  2. 确定终止条件。如果遇到空节点，就返回0。

  3. 确定遍历顺序。本题一定是要后序遍历，因为通过递归函数的返回值来做下一步计算。

  4. 确定单层递归逻辑。

     如果是偷当前节点，那么左右孩子就不能偷，val1 = cur.val + left[0] + right[0];

     如果不偷当前节点，那么左右孩子就可以偷，至于到底偷不偷一定是选一个最大的，所以：val2 = max(left[0], left[1]) + max(right[0], right[1]);

     最后当前节点的状态就是{val2, val1}; 即：{不偷当前节点得到的最大金钱，偷当前节点得到的最大金钱}

  5. 举例推导：

  class Solution {public int rob(TreeNode root) {int [] ret = action(root);return Math.max(ret[0] , ret[1]);}int[] action(TreeNode root){if(root == null){return new int [2];}int [] left = action(root.left);int [] right = action(root.right);//如果不偷父节点。就选择左右节点最大的金额。int nums0 = Math.max(left[0] , left[1]) + Math.max(right[0] , right[1]);//如果偷父节点，就加上不偷左右的值。int nums1 = root.val + left[0] + right[0];return new int []{nums0 , nums1};}
  }
  

买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

使用五步法分析：

1. 确定dp数组以及下标含义：dp[i][0]表示第i天持有股票所得最多现金。dp[i][1]表示第i天不持有股票所得最多现金。

2. 递推公式：

   dp[i][0]可以由两个状态推导而来：

   1. 第i - 1天就持有股票，保持现状，所得金额为：dp[i - 1][0]。
   2. 第i天才买入股票，所得金额为：-price[i]。

   dp[i][1]也可以由两个状态推导而来：

   1. 第i - 1天不持有股票，保持现状，所得金额为：dp[i - 1][1]。
   2. 第i天卖出股票，所得金额为：dp[i - 1][0] + prices[i]。

3. dp数组初始化：dp[0][0]为第0天持有股票，dp[0][0] -= prices[i]。dp[0][1]表示第0天不持有股票，dp[0][1] = 0。

4. 遍历顺序：从前往后。

5. 举例推导dp。

   class Solution {public int maxProfit(int[] prices) {int n = prices.length;int dp [][] = new int [n + 1][2];dp[0][0] = -prices[0];dp[0][1] = 0;for(int i = 1 ; i < n ; i ++){dp[i][0] = Math.max(dp[i - 1][0] , - prices[i]);dp[i][1] = Math.max(dp[i - 1][1] , dp[i - 1][0] + prices[i]);}return dp[n - 1][1];}
   }
   

---

本题和121. 买卖股票的最佳时机 (opens new window)的唯一区别是本题股票可以买卖多次了（注意只有一只股票，所以再次购买前要出售掉之前的股票）在动规五部曲中，这个区别主要是体现在递推公式上，其他都和121. 买卖股票的最佳时机 (opens new window)一样一样的。

本题的股票可以买卖多次，当第i天买入股票的时候，所得现金可能有之前买过的利润。

递推公式：

dp[i][0]表示第i天持有股票的最多现金。

1. 第i- 1天持有股票，dp[i - 1][0]。2. 第i天买入股票，（可能包含之前的利润）dp[i - 1][1] - prices[i]

dp[i][1]表示第i天不持有股票的最多现金。

1. 第i天不持有股票，dp[i - 1][1]。2. 第i天卖出股票prices[i] + dp[i - 1][0]

class Solution {public int maxProfit(int[] prices) {int n = prices.length;int dp [][] = new int [n + 1][2];//第0天不持有股票就是0dp[0][1] = 0;//第0天持有股票dp[0][0] = -prices[0];for(int i = 1 ; i < n ; i ++){//计算第i天持有股票的利润dp[i][0] = Math.max(dp[i - 1][0] , dp[i - 1][1] - prices[i]);  //计算第i天不持有股票的利润dp[i][1] = Math.max(dp[i - 1][1] , prices[i] + dp[i - 1][0]);}return dp[n - 1][1];}
}

事务隔离级别是怎么实现的？

• 事务的特性：并不是所有的引擎都能支持事务，比如 MySQL 原生的 MyISAM 引擎就不支持事务，也正是这样，所以大多数 MySQL 的引擎都是用 InnoDB。
  • 原子性（Atomicity）：同一个事务中的所有操作，要么全部完成，要么全部回滚，就像这个事务从来没有执行过一样，就好比买一件商品，购买成功时，则给商家付了钱，商品到手；购买失败时，则商品在商家手中，消费者的钱也没花出去。
  • 一致性（Consistency）：是指事务操作前后，数据满足完整性约束，数据保持合法状态。比如，用户 A 和用户 B 在银行分别有 800 元和 600 元，总共 1400 元，用户 A 给用户 B 转账 200 元，分为两个步骤，从 A 的账户扣除 200 元和对 B 的账户增加 200 元。一致性就是要求上述步骤操作后，最后的结果是用户 A 还有 600 元，用户 B 有 800 元，总共 1400 元，保持数据的合法状态。
  • 隔离性（Isolation）：多个事务同时使用相同的数据时，不会相互干扰，隔离性可以防止多个事务并发执行时由于交叉执行而导致数据的不一致，因为每个事务都有一个完整的数据空间，对其他并发事务是隔离的。也就是说，消费者购买商品这个事务，是不影响其他消费者购买的。
  • 持久性（Durability）：事务一旦提交，对数据的修改就是永久的。
• InnoDB 引擎通过什么技术来保证事务的这四个特性的呢？
  • 持久性是通过 redo log （重做日志）来保证的；
  • 原子性是通过 undo log（回滚日志） 来保证的；
  • 隔离性是通过 MVCC（多版本并发控制） 或锁机制来保证的；
  • 一致性则是通过持久性+原子性+隔离性来保证；

并行事务会引发什么问题？

MySQL 服务端是允许多个客户端连接的，在同时处理多个事务的时候，就可能出现**脏读（dirty read）、不可重复读（non-repeatable read）、幻读（phantom read）**的问题。

• 脏读：一个事务读取到了另一个事务修改过的但是还未提交的数据，就发生了脏读。此时事务发生回滚，那么另一个事务刚才得到的数据就是过期的数据。
• 不可重复读：一个事务内多次读取同一个数据，如果出现前后两次读到数据不一样的情况，就意为着发生了「不可重复」读现象。
• 幻读：一个事务内多次查询某个符合查询条件的「记录数量」，如果出现前后两次查询到的记录数量不一样的情况，就意味着发生了「幻读」现象。

事务的隔离级别有哪些？

SQL 标准提出了四种隔离级别来规避这些现象，隔离级别越高，性能效率就越低，这四个隔离级别如下：

• 读未提交（read uncommitted），指一个事务还没提交时，它做的变更就能被其他事务看到；
• 读提交（read committed），指一个事务提交之后，它做的变更才能被其他事务看到；
• 可重复读（repeatable read），指一个事务执行过程中看到的数据，一直跟这个事务启动时看到的数据是一致的，MySQL InnoDB 引擎的默认隔离级别；
• 串行化（serializable ）；会对记录加上读写锁，在多个事务对这条记录进行读写操作时，如果发生了读写冲突的时候，后访问的事务必须等前一个事务执行完成，才能继续执行；

---

针对不同的隔离级别，并发事务发生的现象有可能不同。

• 在「读未提交」隔离级别下，可能发生脏读、不可重复读和幻读现象；
• 在「读提交」隔离级别下，可能发生不可重复读和幻读现象，但是不可能发生脏读现象；
• 在「可重复读」隔离级别下，可能发生幻读现象，但是不可能脏读和不可重复读现象；
• 在「串行化」隔离级别下，脏读、不可重复读和幻读现象都不可能会发生。

---

MySQL InnoDB 引擎的默认隔离级别虽然是「可重复读」，但是它很大程度上避免幻读现象

• 快照读（普通 select 语句），是通过 **MVCC（多版本控制）方式解决了幻读。**因为可重复读隔离级别下，事务执行过程中看到的数据，一直跟这个事务启动时看到的数据是一致的，即使中途有其他事务插入了一条数据，是查询不出来这条数据的，所以就很好了避免幻读问题。
• 当前读（select … for update 等语句），是**通过 next-key lock（记录锁+间隙锁）方式解决了幻读。**因为当执行 select … for update 语句的时候，会加上 next-key lock，如果有其他事务在 next-key lock 锁范围内插入了一条记录，那么这个插入语句就会被阻塞，无法成功插入，所以就很好了避免幻读问题。
• 在可重复读隔离级别中，普通的 select 语句就是基于 MVCC 实现的快照读，也就是不会加锁的。而 select … for update 语句是当前读，也就是每次读都是拿到最新版本的数据，但是它会对读到的记录加上 next-key lock 锁。

---

四种隔离级别具体的实现方式

• 对于「读未提交」：直接读取最新的数据就好。
• 对于「串行化」：通过加读写锁的方式来避免并行访问。
• 对于「读提交」和「可重复读」：通过 **Read View **来实现，主要区别在于创建 Read View 的时机不同。
  • 可以把 Read View 理解成一个数据快照，「读提交」隔离级别是在「每个语句执行前」都会重新生成一个 Read View，而「可重复读」隔离级别是「启动事务时」生成一个 Read View，然后整个事务期间都在用这个 Read View。

---

MySQL 有两种开启事务的命令，分别是：

• 第一种：begin/start transaction 命令；执行了增删查改操作的 SQL 语句，才是事务真正启动的时机。
• 第二种：start transaction with consistent snapshot 命令；马上启动事务。

Read View在MVCC里如何工作？

Read View 有四个重要的字段：

• creator_trx_id ：指的是创建该 Read View 的事务的事务 id。

• m_ids ：指的是在创建 Read View 时，当前数据库中「活跃事务」的事务 id 列表，注意是一个列表，“活跃事务”指的就是，启动了但还没提交的事务。

• min_trx_id ：指的是在创建 Read View 时，当前数据库中「活跃事务」中事务 id 最小的事务，也就是 m_ids 的最小值。

• max_trx_id ：这个并不是 m_ids 的最大值，而是创建 Read View 时当前数据库中应该给下一个事务的 id 值，也就是全局事务中最大的事务 id 值 + 1；

---

聚簇索引记录中有两个隐藏列：

• trx_id，当一个事务对某条聚簇索引记录进行改动时，就会把该事务的事务 id 记录在 trx_id 隐藏列里；

• roll_pointer，每次对某条聚簇索引记录进行改动时，都会把旧版本的记录写入到 undo 日志中，然后这个隐藏列是个指针，指向每一个旧版本记录，于是就可以通过它找到修改前的记录。

• 在创建 Read View 后，我们可以将记录中的 trx_id 划分这三种情况：

• 一个事务去访问记录的时候，除了自己的更新记录总是可见之外，还有这几种情况：

  • 如果记录的 trx_id 值小于（当前事务的）Read View中的 min_trx_id 值，表示这个版本的记录是在创建 Read View 前已经提交的事务生成的，所以该版本的记录对当前事务可见。
  • 如果记录的 trx_id 值大于等于（当前事务的）Read View中的 max_trx_id 值，表示这个版本的记录是在创建 Read View 后才启动的事务生成的，所以该版本的记录对当前事务不可见。
  • 如果记录的 trx_id 值在 Read View 的min_trx_id和max_trx_id之间，需要判断 trx_id 是否在 m_ids 列表中：
    • 如果记录的 trx_id 在 m_ids 列表中，表示生成该版本记录的活跃事务依然活跃着（活跃事务还没提交），所以该版本的记录对当前事务不可见。
    • 如果记录的 trx_id 不在 m_ids列表中，表示生成该版本记录的活跃事务已经被提交，所以该版本的记录对当前事务可见。

  **这种通过「版本链」来控制并发事务访问同一个记录时的行为就叫 MVCC（多版本并发控制）**使用MVCC，解决了可重复读和幻读的问题。

可重复读是如何工作的？

• 可重复读隔离级别是启动事务时生成一个 Read View，然后整个事务期间都在用这个 Read View。

• 假设事务 A （事务 id 为51）启动后，紧接着事务 B （事务 id 为52）也启动了，那这两个事务创建的 Read View 如下：

  接着，在可重复读隔离级别下，事务 A 和事务 B 按顺序执行了以下操作：

  • 事务 B 读取小林的账户余额记录，读到余额是 100 万；

    • 解释：找到记录后，会先看这条记录的 trx_id，此时发现 trx_id 为 50，比事务 B 的 Read View 中的 min_trx_id 值（51）还小，这意味着修改这条记录的事务早就在事务 B 启动前提交过了，所以该版本的记录对事务 B 可见的，也就是事务 B 可以获取到这条记录。

  • 事务 A 将小林的账户余额记录修改成 200 万，并没有提交事务；

    • 事务 A 通过 update 语句将这条记录修改了（还未提交事务），将小林的余额改成 200 万，这时 MySQL 会记录相应的 undo log，并以链表的方式串联起来，形成版本链

  • 事务 B 读取小林的账户余额记录，读到余额还是 100 万；

    • 事务 B 第二次去读取该记录，发现这条记录的 trx_id 值为 51，在事务 B 的 Read View 的 min_trx_id 和 max_trx_id 之间，则需要判断 trx_id 值是否在 m_ids 范围内，判断的结果是在的，那么说明这条记录是被还未提交的事务修改的，这时事务 B 并不会读取这个版本的记录。而是沿着 undo log 链条往下找旧版本的记录，直到找到 trx_id 「小于」事务 B 的 Read View 中的 min_trx_id 值的第一条记录，所以事务 B 能读取到的是 trx_id 为 50 的记录，也就是小林余额是 100 万的这条记录。

  • 事务 A 提交事务；

  • 事务 B 读取小林的账户余额记录，读到余额依然还是 100 万；

    • 当事物 A 提交事务后，由于隔离级别时「可重复读」，所以事务 B 再次读取记录时，还是基于启动事务时创建的 Read View 来判断当前版本的记录是否可见。所以，即使事物 A 将小林余额修改为 200 万并提交了事务， 事务 B 第三次读取记录时，读到的记录都是小林余额是 100 万的这条记录。

读提交是如何工作的？

• 读提交隔离级别是在每次读取数据时，都会生成一个新的 Read View。

• 假设事务 A （事务 id 为51）启动后，紧接着事务 B （事务 id 为52）也启动了，接着按顺序执行了以下操作：

  • 事务 B 读取数据（创建 Read View），小林的账户余额为 100 万；

    • 找到记录后，会先看这条记录的 trx_id，此时发现 trx_id 为 50，比事务 B 的 Read View 中的 min_trx_id 值（51）还小，这意味着修改这条记录的事务早就在事务 B 启动前提交过了，所以该版本的记录对事务 B 可见的，也就是事务 B 可以获取到这条记录。

  • 事务 A 修改数据（还没提交事务），将小林的账户余额从 100 万修改成了 200 万；

  • 事务 B 读取数据（创建 Read View），小林的账户余额为 100 万；

    • 事务 B 在找到小林这条记录时，会看这条记录的 trx_id 是 51，在事务 B 的 Read View 的 min_trx_id 和 max_trx_id 之间，接下来需要判断 trx_id 值是否在 m_ids 范围内，判断的结果是在的，那么说明这条记录是被还未提交的事务修改的，这时事务 B 并不会读取这个版本的记录。而是，沿着 undo log 链条往下找旧版本的记录，直到找到 trx_id 「小于」事务 B 的 Read View 中的 min_trx_id 值的第一条记录，所以事务 B 能读取到的是 trx_id 为 50 的记录，也就是小林余额是 100 万的这条记录。

  • 事务 A 提交事务；

  • 事务 B 读取数据（创建 Read View），小林的账户余额为 200 万；

    • 第三次创建的Read View：事务 B 在找到小林这条记录时，会发现这条记录的 trx_id 是 51，比事务 B 的 Read View 中的 min_trx_id 值（52）还小，这意味着修改这条记录的事务早就在创建 Read View 前提交过了，所以该版本的记录对事务 B 是可见的。

• 正是因为在读提交隔离级别下，事务每次读数据时都重新创建 Read View，那么在事务期间的多次读取同一条数据，前后两次读的数据可能会出现不一致，因为可能这期间另外一个事务修改了该记录，并提交了事务。