彩虹云商城网站搭建,做社区网站用什么程序好,getoption wordpress,网站推广的方法有哪几种malloc是如何分配内存的#xff1f; 在 Linux 操作系统中#xff0c;虚拟地址空间的内部又被分为内核空间和用户空间两部分#xff0c;不同位数的系统#xff0c;地址空间的范围也不同。比如最常见的 32 位和 64 位系统#xff0c;如下所示#xff1a; 内核空间与用户空…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 字节的内存。 [rootxiaolin ~]# 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来分配内存 如果我们连续申请了 10k20k30k 这三片内存如果 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的入门题目因为是在树上进行状态转移我们在讲解二叉树的时候说过递归三部曲那么下面我以递归三部曲为框架其中融合动规五部曲的内容来进行讲解。 确定递归函数的参数和返回值。要求得到偷与不偷所得的金钱就要返回一个疮毒为2的数组。参数就是TreeNode。返回的数组就是dp数组下标为0记录不偷该节点所得到的的最大金钱下标为1记录偷该节点所得到的的最大金钱。 确定终止条件。如果遇到空节点就返回0。 确定遍历顺序。本题一定是要后序遍历因为通过递归函数的返回值来做下一步计算。 确定单层递归逻辑。 如果是偷当前节点那么左右孩子就不能偷val1 cur.val left[0] right[0]; 如果不偷当前节点那么左右孩子就可以偷至于到底偷不偷一定是选一个最大的所以val2 max(left[0], left[1]) max(right[0], right[1]); 最后当前节点的状态就是{val2, val1}; 即{不偷当前节点得到的最大金钱偷当前节点得到的最大金钱} 举例推导 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 。
使用五步法分析 确定dp数组以及下标含义dp[i][0]表示第i天持有股票所得最多现金。dp[i][1]表示第i天不持有股票所得最多现金。 递推公式 dp[i][0]可以由两个状态推导而来 第i - 1天就持有股票保持现状所得金额为dp[i - 1][0]。第i天才买入股票所得金额为-price[i]。 dp[i][1]也可以由两个状态推导而来 第i - 1天不持有股票保持现状所得金额为dp[i - 1][1]。第i天卖出股票所得金额为dp[i - 1][0] prices[i]。 dp数组初始化dp[0][0]为第0天持有股票dp[0][0] - prices[i]。dp[0][1]表示第0天不持有股票dp[0][1] 0。 遍历顺序从前往后。 举例推导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天持有股票的最多现金。
第i- 1天持有股票dp[i - 1][0]。2. 第i天买入股票可能包含之前的利润dp[i - 1][1] - prices[i]
dp[i][1]表示第i天不持有股票的最多现金。
第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那么在事务期间的多次读取同一条数据前后两次读的数据可能会出现不一致因为可能这期间另外一个事务修改了该记录并提交了事务。
