管道通信 进程通信的概念 我们要明白进程是具有独立性的！那么如果我们需要通信——我们要明白一点通信的成本绝对不低 那么什么是通信呢？ 数据传输：一个进程需要将它的数据发送给另一个进程 资源共享：多个进程之间共享同样的资源。 通知事件：一个进程需要向另一个或一组进程发送消息，通知它（它们）发生了某种事件（如进程终止时要通知父进程）。 进程控制：有些进程希望完全控制另一个进程的执行（Debug进程，使用gdb去控制另我们的程序），此时控制进程希望能够拦截另一个进程的所有陷入和异常，并能够及时知道它的状态改变。 为什么要有通信？ 当我们需要进行多进程协同的时候——我们要让一个进程去专注处理一个...

文件系统 为什么要有文件系统 一个文件如果没有被打开，操作系统应该如何管理这些没有被打开的文件呢？ 没有被打开的文件只能放在磁盘文件上面！那么磁盘上面有如此大量的文件！这些大量的文件都应该被管理起来！方便我们随时的打开！——做这部分的工作的就是文件系统！ 无论是被打开的文件还是不被打开的文件其实都要被文件系统管理 磁盘的结构 要理解文件系统如何管理没有被打开的文件，我们首先就要去了解磁盘 我们要知道磁盘是我们计算机中唯一的机械结构——像是cpu，或者内存其实都是硬件电路构成的！（机械结构是很慢的！而且硬盘还是一个外设）所以这就注定了磁盘的访问是很慢的！（相比于内存或者cpu） 在我们日常...

基础IO 重谈文件 首先我们要知道 空文件也是占据磁盘空间的！ 文件=内容+属性！ 文件操作=对内容的操作+对属性的操作or是对内容和属性的操作 找到一个文件必须使用文件路径+文件名！——因为这样具有唯一性！ 如果没有指明对应的文件路径！默认是在当前路径进行文件访问——当前路径就是进程当前的工作路径！ 当我们把fopen，fclose，fread等接口写完后，形成二进制可执行程序，但是没有运行，文件对应的操作有没有被执行？——没有！对文件的操作本质是进程对文件的操作！ 一个文件要被访问首先要先被打开！——那么是要被谁打开的呢？——是被用户进程+OS打开的！用户进程去调用系统接口！操作系统帮...

进程控制 进程创建——fork函数 用于创建子进程的系统调用接口！ 这是一个函数函数执行前只有一个父进程，函数执行后有一个父进程一个子进程 进程调用fork，当控制转移到内核中的fork代码后，内核做 分配新的内存块和内核数据结构(PCB，地址空间，页表)给子进程 将父进程部分数据结构内容拷贝至子进程 添加子进程到系统进程列表当中 fork返回，开始调度器调度 fork后的子进程和父进程的数据使用写实拷贝的方式各自私有 但是进程的代码是各自私有的！可以使用ifelse的方式进行分流！ include<stdio.h> include<unistd.h> in...

进程状态概念详解 进程状态 进程状态分为：运行，新建，就绪，挂起，阻塞，等待，停止，挂起，死亡......... 上面的状态都是操作系统的说法！ 所以我们要从普遍的操作系统的层面去理解上面的概念！进而去理解linux下面的进程状态的概念！ 为什么会有这些状态 首先我们就要对操作系统有个宏观的概念！ 怎么多状态的本质就是为了满足不同的运行场景！ 上面的所有结构体和数据都是存放在内存里面的！因为操作系统要一开始就被加载在内存中运行！ 运行 因为cpu的核心个数是远少于进程个数的那么进程是如何在CPU里面运行的呢？ 就是通过CPU在内核中维护的运行队列来实现的！ 一般来说一个CPU对应...

程序地址空间 C/C地址空间！ 在先认识程序地址空间前我们要先认识一下C/C的地址空间！ 这就是C/C的地址空间的结构！ 不过这个地址空间究竟是什么？——是内存吗？ 答案是错误的！这个地址空间其实不是内存！ 我们可以看一下 intmain() { pid_tid=fork(); if(id<0) { printf("forkerror\n"); } elseif(id0) { intcnt=0; while(1) { printf("iamchild,pid=%d,ppid=%d,global_value=%d,&global_valueo=%p\n",getpid(),get...

布隆过滤器 位图 位图的概念 在介绍位图之前我们先看一个题目 给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。 对于这个问题有我们可以想到很多解决的方法 遍历，时间复杂度$O(N)$ 排序+二分法（排序我们可以使用快排）所以就是时间复杂度就是O(NlogN+logN) 使用红黑树或者哈希表 但是以上的方法都是要在内存中的！而且这是一个40亿个整数！光是数据量就是16g！一般的内存其实是放不下的！所以红黑树和哈希表就已经被否决了！ 既然放内存放不下我们是能不能用归并排序进行外排序！但是在磁盘里面就不能用二分法查找！磁盘里面是不支持随机访问...

哈希表与哈希桶的模拟实现 unordered系列关联式容器介绍 在C98中，STL提供了底层为红黑树结构的一系列关联式容器，在查询时效率可达到$log_2N$，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想。最好的查询是，进行很少的比较次数就能够将元素找到，因此在C11中，STL又提供了4个unordered系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同，例如，unordered_multimap和unordered_multiset 但是unordered系列的底层是哈希！——其实是应该叫做hash_map,hash_s...

C之线程库 前言 C的线程库，不是只有线程，有好几个库，包括了创建线程，锁，条件变量，原子操作等待 thread类 在C11之前，涉及到多线程问题，都是和平台相关的，比如windows和linux下各有自己的接口，这使得代码的可移植性比较差。C11中最重要的特性就是对线程进行支持了，使得C在并行编程时不需要依赖第三方库，而且在原子操作中还引入了原子类的概念。要使用标准库中的线程，必须包含<thread>头文件 构造函数 thread类是不支持拷贝构造的！ thread类是可以支持创建空线程(什么都不走)——像是linux下面的pthread就要求传入参数 thread类是...

STL之红黑树的模拟实现 红黑树的概念 红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。 意思就是最长路径不超过最短路径的二倍！ 相比AVL树，红黑树只是接近平衡！AVL树已经是二叉搜索树能解决的最严格的平衡！ 红黑树的性质 每个结点不是红色就是黑色 根节点是黑色的 如果一个节点是红色的，则它的两个孩子结点是黑色的 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点 每个叶子结点都是黑色的...

STL之AVL模拟的实现 AVL树的概念 为什么会有AVL树？在STL中对map/multimap/set/multiset其底层都是按照二叉搜索树来实现的，但是二叉搜索树有其自身的缺陷，假如往树中插入的元素有序或者接近有序，二叉搜索树就会退化成单支树，时间复杂度会退化成O(N)， 因此map、set等关联式容器的底层结构是对二叉树进行了平衡处理，即采用平衡树来实现 二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。 因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明...

set和map介绍 基础概念 关联式容器 像是vector，list，deque，forward_list这些都是属于序列式容器！因为其底层为线性序列的数据结构，里面存储的是元素本身。 而map和set是属于关联式容器！ 什么是关联式容器？关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是结构的<key,value>键值对，在数据检索时比序列式容器效率更高 关联式容器的数据与数据之间是紧密关联的！像是list，vector这样的序列式容器，数据之间的关联很小！如果要插入一个数据实际上插入那个位置是无所谓的！ 但是关联式容器不一样！关联式容器的每一个数据都是有固定的...

C11之类型转换 C语言中的类型转换 在C语言中，如果赋值运算符左右两侧类型不同，或者形参与实参类型不匹配，或者返回值类型与接收返回值类型不一致时，就需要发生类型转化，C语言中总共有两种形式的类型转换：隐式类型转换和显式类型转换。 隐式类型转化：编译器在编译阶段自动进行，能转就转，不能转就编译失败 显式类型转化：需要用户自己处理 voidTest() { inti=1; //隐式类型转换 doubled=i; printf("%d,%.2f\n",i,d); intp=&i; //显示的强制类型转换 intaddress=(int)p; printf("%x,%d\n",p,ad...

C11之IO流 什么是流？ ​“流”即是流动的意思，是物质从一处向另一处流动的过程，是对一种有序连续且具有方向性的数据（其单位可以是bit,byte,packet）的抽象描述。 C流是指信息从外部输入设备（如键盘）向计算机内部（如内存）输入和从内存向外部输出设备（显示器）输出的过程。这种输入输出的过程被形象的比喻为“流”。它的特性是：有序连续、具有方向性 为了实现这种流动，C定义了I/O标准类库，这些每个类都称为流/流类，用以完成某方面的功能 C的IO流 C系统实现了一个庞大的类库，其中ios为基类，其他类都是直接或间接派生自ios类 C的标准IO流 C标准库提供了4个全局流对象...