5 我是土堆

尚未进行身份认证

公众号:土堆碎念; 一个不焦虑、有趣的公众号! 他有一个百宝袋,能帮你拥有更多的自由时间。

等级
TA的排名 7w+

内存访问全过程

这一篇,是重点!我们将去讲解操作系统根据代码(逻辑)地址去访问真实物理地址的全过程。将把全面几节的东西全部用上,并完全梳理,完善细节。前面讲了分段、分页机制,他们都可以实现,从虚拟地址(地址空间)向物理地址的转换。但是,实际使用过程中,使用的是分段+分页机制,段页结合。段页结合全过程分析(高能)我们现在采用边实验边讲解翻译全过程。写了一段 c 代码,编译,然后在 Linux 0.11 中,进行调试#include <stdio.h>int i = 0x12345678;in

2020-05-10 16:54:40

多级页表与快表

之前页表结构的不足之前的页表结构看起来挺好的呀,有什么问题呢?如果每个页的大小是4k,也就是2的12次方。如果是32位的地址话,也就是说,有2的20次方个页。那么对应到页表,也就说页表应该有2的20次方个项。因为每个项表示的是一个内存地址,也就说一个项的大小是32位,也就是4个字节。这样算下来,对应于一个32位的内存地址,一个页表应该4M大小。看起来还可以接受啊。但注意,每个进程都有一个页表。看下,我的电脑现在有280个进程,也就说如果采用之前的结构,光页表结构就得占用280*4M=1120M,

2020-05-09 16:27:54

分页

前面说到了采用分段技术来进行虚拟地址(地址空间)到物理内存的转换。分段有什么问题?肯定得有不足,才需要提出新的技术来改进。那么我们刚才的分段机制,不是挺好的嘛?有什么问题呢?比如说,我们现在存放一些内容,需要占用 160K 的空间,但是我们来看空间的地址空间,分别是150K和50K,每个段都不足以满足 160 K 的要求,但是两个加起来,的的确确可以满足要求。只使用 分段机制,会造成内存碎片,浪费空间。如何解决呢?针对上面的问题,我们可以想到有下面的一些方法:移动已经使用的内存,把空闲的内

2020-05-09 16:11:48

虚拟内存

背景我们一般把内存看成一块连续的字节数组。我们通过指定地址来访问其中的内容。我们看到图上,0KB-64KB 地址范围内,存放着操作系统。如果现在 A 同学想要写一个程序,它指定代码放在64KB-128KB的位置。现在B同学也写了一个程序,为了避免覆盖A同学程序,需要指定将代码放在128KB以后的位置。这样,就很麻烦了,你需要提前知道其他程序所在的位置,这样写代码就特别痛苦。为此,引入了虚拟内存的概念。地址空间的引入为此,引入了地址空间的概念,或者叫做虚拟地址。现在,对每一个程序,进程,都

2020-05-09 15:22:57

内存分段机制

我们可以写一段简单的c代码(code/memory/segment_1.c):#include <stdio.h>int main(){ int a = 1; printf("Hello, World!"); return 0;}然后将其转为汇编,运行:gcc -S segment_1.c之后会生成一个.s 文件(code/memory/segmen...

2020-05-07 17:37:49

Java vs c++ 字符串 vector ArrayList 迭代器数组比较

字符串Java 和 c++ 都支持字符串,但在使用方面有所区别。初始化,Java 的初始化方式比较简朴,= 后加上字符串即可。c++ 可以在变量后,使用括号进行多次重复或者进行赋值。除此之外,Java 可以两个字面量进行直接连接,而c++ 需要字面量另一边需要有一个字符串变量才可以。取值方式不同,如果想获取字符串中的每一个字符。那么Java 只能用charAt 函数,或者转为char[] ...

2020-03-27 13:33:19

Java vs C++ 基础异同比较

数据类型Java 中只有8种数据基本类型,C++的基本数据类型较多Java 中的8种基本数据类型为:boolean, byte, short, int, long, float, double, charc++ 中的数据类型较多,且部分写法有所区别:bool, short, int, long, float, double, char基本数据类型占用的字节数有所区别,因为 Java ...

2020-03-26 22:45:44

2. 数组

2.1 数组的结构数组,是一块连续的内存区域,且具有相同类型的数据结构。说回上一次的图。(图片修改自极客专栏:《数据结构与算法之美》)这就是数组的一块内存区域。我们提下上面说的两个特点:连续内存区域相同的数据类型这两个特点有什么好处呢?我们上次说到,如果我们想要查找一个房间1036(一块数据),我们站在上图中1000的位置,然后有下面两种方式:从1000走4步,到1004...

2020-03-26 00:33:19

1. 数据结构概述

1.1 什么是数据结构说到数据结构,我觉得可以拆分成两个词,数据和结构。先来打个比方。同样是水,有的被放进了游泳池,成为了游泳嬉戏的场所;有的被放进了杯子,供我们喝水;我们不可能喝水,不用杯子,用游泳池。说到底,就四个字:因地制宜???(好像比较恰当,欢迎大家集思广益)数据就好比这里的水,是我们想要使用的东西,对我们有价值的东西;结构就好比游泳池、杯子,是帮助我们更好的使用数据,...

2020-03-25 17:14:16

动态规划专题:LeetCode 完全平方数

原题链接279. 完全平方数思路这道题跟之前的动态规划有些区别。刷了不少动态规划的题目。大部分的结构,都是类似于这种形式dp[i] = Math.max(min)(dp[i-n]+k, dp[i-m]+k1) + M这种形式,涉及到最大小值,肯定涉及到题目求解的最值问题而且一般绝大多数情况下是,时间复杂度都是O(n)。这次的题目,主要涉及到一些关键点的处理。如果不考虑这些关键点,...

2020-03-24 23:14:34

动态规划专题:LeetCode 乘积最大子数组

原题链接乘积最大子数组思路刷题得按专题刷,发现这道题很有意思。因为负数的引入,导致推导状态就比较麻烦。看了题解,分别记录最大值和最小值。当遇到负数的时候,最大值将会变为最小,最小将会变为最大。真的很巧妙。算是开拓了一个新的思路。class Solution { public int maxProduct(int[] nums) { int max = Intege...

2020-03-24 19:54:15

动态规划专题:LeetCode连续数列

LeetCode题目链接面试题 16.17. 连续数列这个题目和最大子数列是一个题目思路用 dp[i] 表示,连续数列的和。当 dp[i-1] 小于0的时候,它如果加上nums[i]的话,肯定比单独的nums[i]小。此时,设置 dp[i] 为 nums[i]。如果它大于0,可以让其尝试继续相加。这里的dp[i]并不是说 i 位置前面连续数列的最大值。实现class Soluti...

2020-03-24 15:09:00

动态规划专题:LeetCode 按摩师

LeetCode题目面试题 17.16. 按摩师思路为什么要用动态规划在知道如何使用动态规划前,知道何时使用动态规划最重要吧。如果你要知道最后一天的值,取决于第三天做不做,这就是二叉树的结构,一般涉及到两个选择的,画下的话,可以看到有重叠部分,可以考虑动态规划。遇到最值问题的时候,后面的选择取决于前面选择的时候,考虑动态规划。遇到子序列的(可不连续)的时候,考虑动态规划。最重要...

2020-03-24 13:39:25

3. 无重复字符的最长子串

原题链接3. 无重复字符的最长子串解题思路在谈及重复问题,大概率会使用 hashmap 或者 hashset最长子串,因为是连续的,所以有点想使用滑动窗口的方法滑动窗口在 HashMap 中维护一个表,这个表的作用:记录每个字符最后一次出现的位置索引HashMap 天然是无重复的以abcba举例,在检索到abc的时候,在hashmap中存入,a-0,b-1,c-2。当检...

2020-03-23 11:21:04

字典树(前缀树/后缀树)

用途有人说是为了统计字频,可我觉得 HashMap 就可以完成。有人说比 HashMap 占用内存要小,但我感觉小也小不到哪里去。有人说为了查询字符,还是那句话,HashSet 表示我也可以。也许在 Hash 没有出来前,它也许在这些领域占有一席之地。目前,从数据结构来看,我认为它的作用也许在以下方面比较突出:也被称为 前缀树,就是剔除相同的前缀操作,这里看不懂很正常,后面慢慢说搜索提...

2020-03-22 17:23:11

10. 排序算法思想概述及总结(精华)

排序算法的常用种类初级排序选择排序插入排序希尔排序进阶排序快速排序归并排序(二叉堆排序)堆排序非比较排序计数排序基数排序桶排序逆序对逆序对,是分析排序算法的一个重要知识点。既然评估排序算法,就要知道如何去描述数组的排序程序。逆序对,数组中两个逆序元素的对数。比如【1, 5, 3】,其中(5, 3)就是逆序的,所以这个数组的逆序对为1。那么...

2020-03-20 15:53:23

9. 桶排序

思想桶排序,也是为了解决计数排序计数数组大小设置的问题。桶排序,就是把待排序数据分为不同的区间,然后区间内进行排序,最后即可完成排序。就有点像,成绩会有一个区间,比如100-90, 90-80这样,每个区间就是一个桶,然后对桶内元素进行排序。最后取出来,即完成排序。从上面分析可以看出,我们对区间排序的时候,最好每个区间(桶)中数据是均匀的。至于如何对桶内元素进行排序?这个是一个困惑,网上很...

2020-03-20 15:38:27

8. 基数排序

思想基数排序,是按照元素的更小元素组成来进行排序。拿常用的数字排序举例,会先对个位进行排序,然后对十位进行排序。其中,关键是如何对个位进行排序,如何对十位进行排序。我们知道对于数字的每一位,只有10个数字(0-9),这就是基数。所以故名,基数排序。基数排序所以可以理解为适用于基数是有限的情况下。所以基数排序中的基数,相当于把计数排序中的计数数组的大小确定下来了。那么如何对个位、十位进行排...

2020-03-20 15:12:26

7. 计数排序

思想计数排序,不再依赖元素的比较,而是通过计数的方式,来进行排序。比如,你知道成绩比你高的有5个人,那么你是多少名呢?计数排序就是采用这种思想。计数排序,为每一个元素设置一个计数,然后进行计数排序。从这个思想上来看,计数排序会使用到复制的空间,而且辅助空间的数量为 待排序数组的最大值-最小值+1。从这个分析上,可以知道计数排序适用于 小范围的排序,就是说待排序的数组,最大小值的差值不能太...

2020-03-20 14:52:02

6. 快速排序

思想快速排序,是选取一个元素,然后经过交换元素,保证选定元素的左边都小于它,右边元素都大于它。每次操作后,选定元素的位置就是排序后的位置。就像多个人进行高矮个排列一样,你看了下,前面的人都比你矮,后面的人都比你高,那么你就可以不动了,随他们怎么折腾,反正你站的位置对了,他们排序好了,你也还是站在这个位置。实现import java.util.Arrays;public class Qu...

2020-03-20 00:03:07

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。
  • 学习力
    学习力
    《原力计划【第二季】》第一期主题勋章 ,第一期活动已经结束啦,小伙伴们可以去参加第二期打卡挑战活动获取更多勋章哦。
  • 原力新人
    原力新人
    在《原力计划【第二季】》打卡挑战活动中,成功参与本活动并发布一篇原创文章的博主,即可获得此勋章。