Posts

auto 在概念上auto已经极简了，但是实际上仍然要微妙许多。它可以节约声明类型，也可以避免许多手动类型的正确性和声明问题。但是从结果的角度来说，尽管auto很努力在做事了，但是仍然可能是错误的。如果出现这种情况我们要知道如何去引导auto让他成为正确的类型，因为退回使用手动声明类型仍然是下下策。 接下来的内容会涵盖auto的所有细节 Item 5: Prefer auto to explicit type declarations. 不仅可以避免出现为初始化的变量，避免啰嗦又繁杂的类型声明，能直接持有闭包，还可以避免一些因为“类型捷径”出现的问题。 eg1. 有一些程序员会对类型发生误判，到时用范围较小的类型在32位机器上能够运行但是在64位机器上发生了改变，导致程序在移植的时候出现问题。 eg2. 上述代码看起来没什么问题，但是当实际运行之后并没有对哈希表m进行操作。原因在于哈希表中的kay值是const类型的，手动声明的类型不一样的话编译器会进行一个神奇的操作，它会讲m中的内容复制成为临时变量将key的类型改为和声明一致的，再将p绑定到临时变量上。 Summary auto说到底只是一个可选项罢了，不是必选项，如果你觉得你的项目使用显式的声明能够使得项目变得更加的可读和高效，当然可以继续使用。但是c++引入auto并不是一个多新鲜的东西，只是一个在其他语言中被称为“类型推导”的东西罢了。在其他的静态类型语言中类型推导都或多或少存在。而且动态语言还为类型推导积累了大量的经验。而且此类技术并不会于大型的工程项目产生冲突。 一些人觉得用完auto之后会让变量的类型变得不是一眼可以识别，但是这个问题随着ide的优化和适配已经被解决的相当完美了。 事实上手动声明变量经常是在画蛇添足，无论是正确率还是效率上。 Item 6: Use the explicitly typed initializer idiom when auto deduces undesired types. 纵使auto有万般好，但是auto也会出现推断的类型和你心目中期待的不一样的情况（当然也不完全是auto错了哦😀） 下面举一个auto推断不符合预期的例子。 上述声明了一个返回vector< bool >类型的函数，使用了auto之后虽然仍然能够直接进行编译和运行但是结果却不是所想要的。 而发生这样错误的原因是，在c++的设计当中回避了bit的引用所以返回的不是bool&，实际上c++中设计了一个代理类来完成向bool的转换操作，这就不展开细说了，但是代理类并不少见，我们经常使用的两个智能指针就是一种代理类。 代理类的设计在使用的时候尽量少的对程序员暴露内部细节，这些代理类的使用往往会在文档中标识出来，如果在文档中没有体现的话，也避免不了在头文件中漏出一些破绽，最不济在debug的时候可能也会发觉是使用了代理类。 但是这些都不重要了，现在重要的事怎么把auto引导到正确的道路上🙃。 就是使用一个强制的类型转换，让它去到该去的位置，虽然看起来有点滑稽，给人一种头痛医脚的感觉🤣。虽然在这些时候你也可以放弃使用auto，但是在这个踩坑的过程中不是也收获了新的知识么?😁 总之记住以下两点 隐形的代理类可能会让auto推断出错误的类型。 显式的类型转换可以让auto走向正确道路。 Moving to Modern C++ 接下来这一章会详细介绍现代c++的一些细节特性。我自己会记录几个我认为比较实用的。并不是全部。 Item 8: Prefer nullptr to 0 and NULL. 非常显然的是0的类型是int，不是一个指针，但是在一个本应该出现指针类型的地方出现了0，编译器也会勉强吧0解释为空指针，但这毕竟是不得已而为之的行为🙉， 总之0是int，不是指针。 nullptr’s advantage is that it doesn’t have an integral type. To be honest, it doesn’t have a pointer type, either, but you can think of it as a pointer of all types. nullptr’s actual type is std::nullptr_t, and, in a wonderfully circular definition, std::nullptr_t is defined to be the type of nullptr. The type std::nullptr_t implicitly converts to all raw pointer types, and that’s what makes nullptr act as if it were a pointer of all types. ...

环境搭建 按照P0的指导中进行环境的搭建，由于我本人现在时WIN平台，课程没有提供一键配置环境的脚本，所以我选择云服务器进行环境的构建，很稳。 但是我的云服务器配置只有2核2G在编译的时候会爆内存。这里还有个故事，在爆内存之后我已经意识到这个问题，我给阿里云客服提了个工单试图能白嫖一些配置，客服还是很有水平的，直接就分析出来我是内存爆了导致的，但是直接建议我加钱升级配置，不告诉我设置swap分区，有点不厚道了。 话说回来，设置完swap分区之后就没有再出现过爆内存的现象。用VScode的远程开发，体验还是很不错的。 Overview p1主要是内存管理部分的内容，这门课程的课本和录制视频还是很有必要看一下的。 主要的任务是以下三个部分： 可扩展的哈希表 LRU-K的淘汰策略的视线 Buffer Pool的一个实例 在开始梳理项目之前我想要先解释清楚一下三个任务之间的关系，以及各个部分的负责。 frame更像是一个载体，而page是其中的内容。打个比方来说，一个仓库（buffer pool）只有100辆货车（frame），而货物（page）成千上万种，每次都是仓库告诉货车需要什么货物然后由货车带着货物来到仓库，而可扩展的哈希表就是登记货车和货物的对应关系。因为只有100辆货车，当每辆车都是满的时候（没有闲置的车辆free_list不为空）就需要根据task2的LRU-K算法挑选出一个符合要求的货车清空后去装载指定的货物。 而task3就是负责整个的管理和交互。 大概解释了一下，可能比方不是很恰当，做的时候一定要多看文档和注释，因为漏看注释给我带来了极大的痛苦。 Task #1 -ExtendibleHashTable 相关函数 Find(K,V): 查询一个Key是否存在，如果存在则将其V指针指向相关的值，返回true，否则返回false Insert(K,V): 插入一个（K，V），如果插入失败需要进行一下步骤的重试： 插入失败肯定是桶满了，但是桶满了分为两种不同的情况。 一种是global深度和桶的local深度不相同的时候，需要对桶进行重新的分配。 当两个深度相同的时候说明桶是真的满了，需要对哈希表进行扩展 Remove(K): 在哈希表中移除对应的（K，V）对，但是需要进行哈希表缩小的操作。 IndexOf(K): 当前global深度下的映射规则。 项目架构 首先要清楚这个是自己动手实现一个可扩展哈希表用于保存frame和page的映射关系的。我觉得首先要明白frame和page之间的关系。不清楚的可以回看上文的解释。 Bucket 存储桶 在可可以扩展的哈希表种引入和Bucket的概念，用于解决哈希冲突的问题，每一个Bucket的大小都是固定的，当一个Bucket满了的时候就需要进行哈希表的扩展。 Bucket的组成 depth_：表示本地深度的一个标识，用于识别当前的深度是否和全局深度相同。要特别注意这个变量。 list_：发生哈希冲突时保存多个（K，V）映射的双向链表。 size：为了保证效率，list的长度不能无限延伸，所以达到一定长度的时候要进行哈希表的扩展。 可扩展的哈希表结构 Bucket_size:用于限制每个bucket的list的长度 dir_:用于哈西运算后保存映射关系。 global_depth_:全局深度，在插入的时候根据全局深度和局部深度来确定这个桶是否要进行重新的分配。 num_buckets:用于统计现在一共有多少bucket。 ReHash的过程详解 1.hash的规则是什么样的 template <typename K, typename V> auto ExtendibleHashTable<K, V>::IndexOf(const K &key) -> size_t { int mask = (1 << global_depth_) - 1; return std::hash<K>()(key) & mask; } 上述函数就是该哈希表的映射规则，总的来说就是取hash函数值的低global_depth位 假如现在global_depth_的值为3。 那么 1 << global_depth_的值就是8转换为二进制就是 1000 。mask=8-1=7，转换为二进制就是 111. mask 的作用就是取一个位数和global_depth_一样的全1的二进制数，为了取低global_depth_位做铺垫。 现在假如key的值进行完hash之后是 10110100011010 和 mask进行进行 & 的操作之后就变成了 010 （低3位） ...

TABLE INDEX A table index is a replica of a subset of a table’s attributes that are organized and/or sorted for efficient access using those attributes.The DBMS ensures that the contents of the table and the index are logically synchronized. 索引让数据在数据库中的查询更加的高效，DBMS负责使索引和实际内容同步。 DBMS的工作是选择最优的索引去执行查询，这就带来一个需要权衡的问题——索引越多查询越高效但是相对的维护成本（Maintenance Overhead）和存储成本（Storage Overhead） 就会相应的提高。 B-TREE FAMILY B-树家族。 重点了解B+树。 （B树虽然是一个平衡树（balance），但B树的B不是balance的缩写，到底代表什么还存疑） B+TREE B+树是一个自平衡树的数据结构，顺序的存储数据，并且将查询，顺序访问，插入和删除的时间复杂度基本控制在O(log n)。 是二叉搜索树的推广，因为它可以有超过两个的孩子节点。 它针对系统和存储之间的大块数据读写进行了特别的优化。 B+TREE PROPERTIES B+树是一个多叉搜索树，有以下特性： 他完美平衡 除了根节点都至少半满 k个值会把一个节点分为k+1部分。 B+TREE EXAMPLE 上图是一个小例子，能够发现B+树底层是能够双向访问的，这在多线程的时候有可能会造成死锁问题。这在后面讲解B+树多线程的章节也会对原因进行讲解。 ...

CMU15-445 作为 CMU 数据库的入门课，这门课由数据库领域的大牛 Andy Pavlo 讲授（“这个世界上我只在乎两件事，一是我的老婆，二就是数据库”）。 这是一门质量极高，资源极齐全的 Database 入门课，这门课的 Faculty 和背后的 CMU Database Group 将课程对应的基础设施 (Autograder, Discord) 和课程资料 (Lectures, Notes, Homework) 完全开源，让每一个愿意学习数据库的同学都可以享受到几乎等同于 CMU 本校学生的课程体验。 亮点在于这门课程实现了一个关系型数据库的Demo–bustub，并对组成部分进行修改，最后达到完成整个数据库的目的，非常的有意思。 近年来由于CMU15-445这门课的热度大增，无论是找工作还是保研的简历上都少不了这个课程。到了可以说是人手一个的地步（还有MIT6.824），但是最后的排行榜上真正完成4个项目并且有成绩的不过100余人。在这种背景下也催生出了很多卖课的机构和个人。还有种种乱象。暂且按下不表，进入主题。 前言 先附上 课程链接我原本是想要完成最新的课程即2023fall的，但是2023fall的P0直接就把我劝退了，相较于2022fall的P0我认为难度上升了不止一点。但是其他的Project的实现差别并不是太大，所以我选择了较为容易下手的2022fall的课程进行学习。 Project0-C++ Primer 还是先放上项目Project#0-C++primer链接 概述 这是一个相当于先导课程的项目，旨在培养和检验学生的现代C++编程能力 ，BusTub大量使用C++17，当你上手之后可能就会发现和你印象中的C++不一样。 在CMU如果你没能满分通过P0，那么你会被要求退课。 所需前置知识 我认为需要的前置知识主要包括C++11的新特性 这是在2023fall课程的一个可能是助教写的一个小demo包含了几个例子能够帮助你快速的上手c++11的新特性。 熟悉字典树能够理解字典树原理能够完成一个字典树的小demoLeetCode.208实现前缀字典树 可以先把这个做了，了解一下什么是字典树。 上图就是一个字典树的简单示意图 文件结构 在文件中作为字典树的架子文件中包含了三个类。 TrieNode TrieNodeWithValue Trie Task#1 字典树 先完成一个单线程版本的字典树，后期再考虑并发。 TrieNode TrieNode定义了一个Trie树的一个节点。 一个包含关键字的char类型`key_char_。 一个bool类型is_node的标志来标记这个节点是否是值节点 包含一个存储类型为 char to unique_ptr<TrieNode>映射的哈希表 需要注意的点： C++中智能指针std::unique_ptr的特性所带来的： The InsertChildNode and GetChildNode both return a pointer to unique_ptr 这个独享类型的智能指针也不支持被复制，所以要么使用std::move()把所有权交出去，要么就用get()函数把裸指针交出去。 the move constructor TrieNode(TrieNode &&other_trie_node) is used to transfer old TrieNode’s unique pointers to a new TrieNode。因为是unique_ptr所以在传递的时候不能对指针进行复制。（解决方法就是使用move()函数）。 ...

麻雀虽小五脏俱全的一个小而全的类unix教学用操作系统，由MIT开发 多核的操作系统，大约6000行还有大约300行的汇编，代码简洁易懂，有很多设计都值得借鉴。 一些特性 有进程管理功能 有虚拟地址和空间，pagetable 文件系统 时间片 21个syscall 用户程序 sh cat echo grep kill 能够被视为一个真正的操作系统 缺失的功能 用户ID 登录功能 文件保护 虚拟内存 无法联网 只有两个设备驱动 xv6特性 SMP 多线程共享内存 设备 UART 发送字节流，从一端到另一端 disk 磁盘驱动器 定时器 PLIC 平台级中断控制器，哪个核心应该被告诉中断 CLINT 本地中断控制器 内存管理 pagesize 4096B 一个freelist 没有可变的内存分配 没有“malloc” 三级页表 sv39，在pgtbl 巨页中有用到 调度器 基本的循环调度 时间片的大小是固定的 所有的核心共享一个就绪队列，循环的寻找可以执行的进程 不是完全的循环，如果在时间片内结束，会把这个进程放进队列然后换一个来 启动顺序 加载核心代码到固定的地址0x8000_0000,没有bios，bootloader bootblock 锁 自旋锁，sleep（），wakeup（） param.h 用户地址空间 函数的参数将会被放在栈中。 xv6的虚拟地址 sv39，三级页表之地 实际上xv6只使用了38位所以最大的是256GB xv6启动过程和组织 控制权逐步的转移 数据的类型 自旋锁 循环不断的检查，直到能够获取锁为止 test and set，原子的操作。 释放的时候直接修改值就行，可能看起来不是很原子，但是在内存里这被视为一个单独的操作。 ...