- 博客(251)
- 资源 (18)
- 收藏
- 关注
RSS订阅原创 braft - lease机制
braft中和lease相关的定义：1234567891011121314151617181920212223// State of a lease. Following is a typical lease state change diagram:// // event: become leader become followe...
2023-05-29 12:53:03
343
原创 CPP - 清空vector
vector中一般是三个指针：beginendcapacitybegin ~ capacity为vector的容量，决定了vector在堆上所占的内存大小。begin ~ end为vector所拥有元素数量。end指针通过 resize 改变，capacity指针通过 reserve 改变。但是其中要注意的是，resize在缩小时，不会改变capacity指针。如果要减小v...
2023-04-17 02:03:44
371
原创 ./remake 算法 - 二叉树的最近公共祖先（LCA）
问题描述lca问题的描述：给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”对于如下二叉树：节点0和1的lca为1(一个节点也可以是它自己的祖先)节点7和6的lca为5(深度最深)思路与实...
2023-03-18 14:14:17
363
原创 mit6.s081 - xv6系统调用过程（用户态陷入内核）
核心问题：xv6是如何执行系统调用的？系统调用时用户进入内核的一种手段(一般是受限直接执行(Limited Direct Execution, LDE)机制)。如下图所示：有三种事件会导致CPU搁置普通指令的执行，强制将控制权转移给处理该事件的特殊代码。系统调用：当用户程序执行ecall指令要求内核为其做某事时。异常：一条指令(用户或内核)做了一些非法的事情，如除以零或使用无效的虚拟地...
2023-03-14 04:04:29
562
原创 mit6.s081 - xv6建立虚拟地址映射
核心问题：xv6虚拟地址空间到物理地址空间的映射是由页表实现的，那页表中的内容是怎么写入的？也即：xv6虚拟地址空间到物理地址空间的具体映射关系是如何建立的？内核地址空间在xv6的实现上，所有的进程的内核地址空间是共享的(也即，内核线程的页表都是一个)。每个CPU初始化后采用同一个页表：1234567891011121314151617181920212223// start() jum...
2023-03-12 14:16:12
85
原创 mit6.s081 - lab3 page tables
本文为本人完成6.s081 2021fall时的一些记录，仅作为备忘录使用。代码仓库地址：代码task 1: Speed up system calls (easy)题意描述When each process is created, map one read-only page at USYSCALL (a VA defined in memlayout.h). At the start...
2023-03-12 02:21:20
147
原创 mit6.s081 - xv6虚拟地址转换
核心问题：xv6如何实现虚拟地址转换的？即给定一个虚拟地址，xv6如何读写到真实的物理内存上。为什么需要虚拟内存？实现操作系统的隔离性，使各个进程之间互不干扰，自以为独占内存。地址空间一个进程的地址空间包含运行的程序的所有内存状态。虚拟内存系统负责为程序提供一个巨大的、稀疏的、私有的地址空间的假象，其中保存了程序的所有指令和数据。操作系统在专门硬件的帮助下，通过每一个虚拟内存的索引...
2023-03-11 06:16:12
171
原创 mit6.s081 - xv6物理内存分配器
核心问题：xv6是如何管理物理内存的？RISV-V中的物理地址、虚拟地址RISC-V 指令(用户和内核)操作的是虚拟地址。物理内存(RAM)是用物理地址来做索引的。RISC-V的页表硬件(MMU)通过将每个虚拟地址映射到一个物理地址将这两种地址联系起来(地址映射)。虚拟地址空间和物理地址空间的映射关系如下图：从右边的物理地址空间格局可以看出其主要分为以 0x80000000 为界限...
2023-03-10 01:44:12
133
原创 mit6.s081 - xv6启动过程
核心问题：xv6实验中，执行 make qemu CPUS=1 后 xv6是如何启动运行的？RISC-V的3种工作模式在了解启动流程之前，首先需要明确RISC-V的3种工作模式M-mode (Machine Mode)S-mode (Supervisor Mode)U-mode (User Mode)M-mode (Machine Mode)M-mode是最底层的模式，也是每一个...
2023-03-09 04:05:35
212
原创 mit6.s081 - lab2 system calls
本文为本人完成6.s081 2021fall时的一些记录，仅作为备忘录使用。代码仓库地址：代码task 1: System call tracing (moderate)题意描述In this assignment you will add a system call tracing feature that may help you when debugging later labs....
2023-03-07 14:39:06
81
原创 操作系统 - 受限直接执行（Limited Direct Execution, LDE）
概述虚拟化 CPU的概念：操作系统需要以某种方式让许多任务共享物理CPU,让它们看起来像是同时运行。在本节需要解决的关键问题是：如何高效、可控地虚拟化 CPU？解决方法：采用受限直接执行(Limited Direct Execution, LDE)机制直接执行的概念直接执行：直接在CPU上运行程序即可。使用正常的调用(call)跳转到用户程序的main()，用户程序结束后返回内核。直接...
2023-03-07 03:02:27
62
原创 操作系统 - PETERSON算法
Peterson算法概述Peterson算法是一种实现进程/线程间互斥访问临界区的算法。(线程间共享内存地址空间，进程需要采用共享内存实现)关键术语：临界区：一段代码，进程/线程在这段代码中进程将访问共享资源，当另外一个进程已在这段代码运行时，其他进程就不能在这段代码中运行。互斥：当一个进程/线程在临界区访问共享资源时，其他进程/线程不能进入临界区访问任何其他共享资源的情形。wiki定...
2023-03-07 02:45:55
371
原创 操作系统 - I/O设备
I/O设备综述I/O设备定义I/O设备是硬件中由人(或其他系统)使用与计算机进行通信的部件。例如，键盘或鼠标是计算机的输入设备，而监控器和打印机是输出设备。计算机之间的通信设备(如电信调制解调器和网卡)通常运行输入和输出操作。操作系统需要控制计算机的所有I/O设备。I/O设备划分根据信息交换的单位可讲I/O设备可分为块设备(block device)和字符设备(character devic...
2023-03-07 02:35:30
408
原创 操作系统 - 操作系统的整体结构
操作系统的大致内容的思维导图：操作系统在传统意义上都会有以下内容：进程与线程内存管理文件系统I/O死锁操作系统导论将操作系统视作三个简单的部分：虚拟化、并发、持久化。我认为是比较合理的，结合操作系统导论和现代操作系统的内容也能更好的学习操作系统。reference[1] 操作系统导论[2] 现代操作系统...
2023-03-07 02:32:31
45
原创 操作系统 - 进程
进程综述定义进程是正在执行程序的实例，包括程序计数器、寄存器和变量的当前值。进程不只是程序代码，程序代码称为文本段(代码段)，还包括当前活动，通过程序计数器的值和处理器寄存器的内容来表示。此外，进程还包括进程堆栈段(临时数据、函数参数、局部变量、地址)和数据段(包括全局变量。还可能包括堆(heap)，是在进程运行期间动态分配内存。程序和进程的关系：程序是被动实体，进程是活动实体(进程有...
2023-03-07 02:18:58
52
原创 操作系统 - 进程调度
进程调度概述定义进程存在的核心目的：虚拟化CPU，从而支持多个进程在少量的物理CPU上运行(每个进程以为它独享一个CPU)。进程调度就是选择一个可用的进程(可能从多个可用进程集合中选择)到CPU上执行。单处理器系统从来不会有超过一个进程在运行。如果有多个进程，那么余下的则需要等待CPU空闲并重新调度。调度队列进程进入系统时被加入到作业队列中，该队列包含系统中所有进程。驻留在内存中等待运行的...
2023-03-07 02:13:07
75
原创 操作系统 - 操作系统定义与历史
什么是操作系统操作系统是在硬件和应用之间的软件层“操作系统是管理硬件资源、控制程序运行、改善人机界面 和为应用软件提供支持的一种系统软件。” [计算机百科全书(第2版)]操作系统 = 管理 + 服务操作系统为应用提供的一些服务:为应用提供计算资源的抽象CPU：进程/线程，数量不受物理CPU的限制内存：虚拟内存，大小不受物理内存的限制I/O设备：将各种设备统一抽象为文件，提供...
2023-03-07 02:06:44
72
原创 操作系统 - 操作系统内核架构
操作系统设计原则操作系统的重要设计原则：策略与机制的分离策略(Policy)：要做什么 —— 相对动态机制(Mechanism)：怎么做 —— 相对静态 操作系统可仅通过调整策略来适应不同应用的需求例子策略机制登录什么用户、以什么权限登录输入处理、策略文件管理、桌面启动加载调度调度算法：Round-robin、 Earliest Deadline Firs...
2023-03-07 01:49:45
184
原创 操作系统 - 系统调用
系统调用概述系统调用：运行在用户空间的程序向操作系统内核请求需要更高权限运行的服务。系统调用提供用户程序与操作系统之间的接口。系统调用需要了解的点：系统调用将处理器从用户态切换到核心态，以便 CPU 访问受到保护的内核内存。每个系统调用都由一个唯一的数字来标识。系统调用可以有一套参数，用于用户空间与内核空间之间相互传递信息。(x86-64中最多使用寄存器传递6个参数，参考资料如...
2023-03-07 01:42:37
51
原创 操作系统 - 多级反馈队列
概述1962年，Corbato首次提出多级反馈队列，应用于兼容时分共享系统(CTSS)。Corbato因在CTSS中的贡献和后来在Multics中的贡献，获得了ACM颁发的图灵奖(Turing Award)。该调度程序经过多年的一系列优化，出现在许多现代操作系统中。多级反馈队列需要解决两方面的问题：优化周转时间(T 周转时间= T 完成时间−T 到达时间 )降低响应时间(T 响应时间= T...
2023-03-06 16:15:16
139
原创 操作系统 - 比例份额调度
概述比例份额(proportional-share)调度程序(又称公平份额(fair-share)调度程序)。比例份额算法基于一个简单的想法：调度程序的最终目标，是确保每个工作获得一定比例的CPU时间，而不是优化周转时间和响应时间。彩票调度(lottery scheduling)是比例份额调度程序的一个例子。基本思想很简单：每隔一段时间，都会举行一次彩票抽奖，以确定接下来应该运行哪个进程。越是应...
2023-03-06 16:11:28
48
原创 操作系统 - 线程
概述线程(thread)，又被称为轻量级进程(Lightweight Process, LWP)是程序执行流的最小单位，也是调度的基本单位。为什么需要线程？创建进程的开销较大：包括了数据、代码、堆、栈等进程的隔离性过强：进程间交互可以通过进程间通信(IPC)，但开销较大进程内部无法支持并行线程相较于进程，是一种更加轻量级的运行时抽象。线程只包含运行时的状态：线程执行状态(运行...
2023-03-06 15:53:03
28
原创 操作系统 - 进程API
概述进程的基本操作接口：进程创建：fork (spawn, vfork, clone)进程执行：exec进程间同步：wait进程退出：exit/abort进程创建：fork()fork()语义：为调用进程创建一个一模一样的新进程，fork后的两个进程均为独立进程(调用进程为父进程，新进程为子进程)。函数原型：1234#include <sys/types.h>...
2023-03-06 15:43:20
34
原创 mit6.s081 - xv6-debug
窗口1作为xv6的运行窗口。1make CPUS=1 qemu-gdb窗口2作为gdb调试窗口。1234567gdb-multiarch kernel/kernel# 进入gdb后执行set confirm offset architecture riscv:rv64set riscv use-compressed-breakpoints yestarget remote lo...
2023-03-06 07:09:47
56
原创 mit6.s081 - lab1 Xv6 and Unix utilities
本文为本人完成6.s081 2021fall时的一些记录，仅作为备忘录使用。代码仓库地址：代码task 1: sleepImplement the UNIX program sleep for xv6; your sleep should pause for a user-specified number of ticks. A tick is a notion of time define...
2023-03-06 07:06:47
63
原创 mit6.824 - MapReduce极简实现
概述MapReduce是一种广泛运用的分布式-大数据计算编程模型，最初由Google发表，其开源实现为Hadoop。MapReduce 的编程模型非常简单，正如名字一样，用户仅仅需要实现一个 Map 函数，一个 Reduce 函数。Map 函数，即映射函数：它会接受一个 key-value 对，然后把这个 key-value 对转换成 0 到多个新的 key-value 对并输出出去。1m...
2023-03-06 07:00:52
71
原创 STL - 番外0 vector resize reserve比较
vector resize reserve比较size：Returns the number of elements in the vector 目前存在的元素数。即： 元素个数capacity：Return size of allocated storage capacity 容器能存储数据的个数。 即：容器容量reserve原型：1void reserve (size_type n)...
2023-03-05 15:35:34
24
原创 STL - STL概述
STL概述容器 Containers：STL内部封装好的数据结构，一种class template，常用的包括vector、list、deque、set、map、multiset、multimap等分配器 Allocators：负责空间配置与管理。是一个实现了动态空间配置、空间管理、空间释放的class template。一般SGI STL为每一个容器都指定其缺省的空间配置器为alloc(SG...
2023-03-05 15:32:23
40
原创 STL - STL的编程范式
STL的编程范式OOP(Object-Oriented Programming)：面向对象 数据和操作在同一个类;OOP企图将datas和methods关联在一起12345template<class T, class Alloc = alloc>class list{ ... void sort();}GP(Generic Programming)：泛型编程 datas和...
2023-03-05 15:31:45
38
原创 STL - 分配器 allocators
C++ 内存配置操作和释放操作123class FOO{};FOO *pf = new FOO; delete pf;对于上述代码，其在底层执行内容为： line 2：new操作，首先调用::operator new分配内存 (2)调用Foo::Foo() 构造对象内容; ::operator new底层调用malloc分配内存。 line 3：delet...
2023-03-05 15:20:15
127
原创 STL - vector源码分析
vector概述向量(Vector)是一个封装了动态大小数组的顺序容器(Sequence Container)。跟任意其它类型容器一样，它能够存放各种类型的对象。可以简单的认为，向量是一个能够存放任意类型的动态数组。vector的实现技术，关键在于其对大小的控制以及重新配置时的数据移动效率，即“配置新空间/数据移动/释放旧空间”的这个过程。vector的主要定义如下：1234567891...
2023-03-05 15:15:09
172
原创 STL - list源码分析
list概述list底层为非连续区间，即链表(实质上是一个双向循环链表)list每次插入或者删除一个元素，就配置和释放一个元素空间，对于任何位置的原属插入或原属移除，list永远为常数时间。list的节点首先要知道，list本身和list的节点是不同的，如果我们声明一个list，里面放了100W个元素，然后执行sizeof，会发现sizeof的结果并不是100W。这就是因为容器所管理的内存...
2023-03-05 15:15:03
53
原创 STL - 番外1 什么？sizeof(list<int>)竟然是24
之前写了这样一段代码，1234printf("%d | %d \n", sizeof(std::list<int>), sizeof(std::list<long long>));/*24 | 24 */首先我们需要知道list是个什么东东：点进std::list，可以看到以下代码，可以看出list这玩意貌似没有成员？但他继承了一个 __list_imp<...
2023-03-05 15:08:12
53
原创 STL - array源码分析
array底层就是一个定长数组，给定长数组加上迭代器相关的东西，就可以让他像一个容器，符合容器的性质。12345678910111213141516171819202122232425262728293031323334#define _NOEXCEPT noexcepttemplate<class _Tp, size_t _Size>struct array { // t...
2023-03-05 15:04:52
35
原创 STL - deque源码分析
deque概述deque是一种双向开口的“连续”线性空间(即可以在头尾两端分别做元素的插入和删除操作)。deque与vector的差别：deque允许在常数时间内对头端进行元素的插入和删除操作，vector尾部插入和删除常数时间，头部操作O(n)时间deque没有容量概念，不需要和vector一样进行老三样：申请新空间->复制元素->释放旧空间deque的Ramdon A...
2023-03-05 15:02:41
28
原创 STL - 番外2 优先队列默认是大根堆？
stl中默认堆为大根堆，大根堆的定义为：1priority_queue<int> q;根据源码中的定义，有如下代码：123456789101112131415template <class _Tp, class _Container = vector<_Tp>, class _Compare = less<typename _Con...
2023-03-05 15:01:10
83
原创 CPP - 虚函数指针和虚函数表
虚函数指针和虚函数表虚函数表的定义多态是由虚函数实现的，而虚函数主要是通过虚函数表(V-Table)来实现的。如果一个类中包含虚函数(virtual修饰的函数)，那么这个类就会包含一张虚函数表(vftbl)，虚函数表存储的每一项是一个虚函数的地址。在一个对象的内存布局中，指向这张虚函数表的指针(vfptr)位于最前端。如下图：一般继承(无虚函数覆盖)对于如下UML的类：在普通继承情况，...
2023-02-13 15:22:42
18
原创 CPP - 处理类型
类型别名类型别名是一个名字，是某种类型的同义词。使用类型别名可以使复杂的类型名字变得简单明了。12typedef double wages;typedef wages base, *p; //base=double,p=double*C++11中支持新方法：1using wages = double;auto类型说明符C++11标准，编译器通过初始值推算变量的类型。(auto定义...
2023-02-12 15:22:42
26
原创 CPP - 栈展开(stack unwinding)
栈展开(stack unwinding)的定义抛出异常时，将暂停当前函数的执行，开始查找匹配的 catch 子句。首先检查 throw 本身是否在 try 块内部，如果是，检查与该 try 相关的 catch 子句，看是否可以处理该异常。如果不能处理，就退出当前函数，并且释放当前函数的内存并销毁局部对象，继续到上层的调用函数中查找，直到找到一个可以处理该异常的 catch 。这个过程称为栈展开(s...
2023-02-11 15:22:42
41
原创 CPP - 引用&指针
引用引用(reference)为对象起了另外一个名字，引用类型引用(refers to)另外一种类型。通过将声明符写成 &d 的形式来定义引用类型型,其中 d 是声明的变量名。在初始化变量时，会出现初始值拷贝现象，定义引用则将引用与初始值对象绑定在一起。引用必须初始化(类型必须严格匹配)引用并不是对象，而是给一个已经存在的对象起另一个名字(这个对象必须存在，不可为字面值[...
2023-02-10 15:22:42
84
基本设计模式的Java实现
2020-06-10
ooxml-lib.zip
2020-04-18
操作系统-国产操作系统介绍
2019-04-26
图的基本操作dfs，bfs，删除节点（邻接表实现）
2019-03-19
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人