xv6
操作系统接口操作系统管理和抽象硬件，使得程序共享硬件、共享数据 内核使用cpu提供的硬件保护机制实现保护模式 文件描述符接口将文件、管道和设备之间的差异抽象出来，使它们看起来都像字节流。我们将输入和输出称为 I/O fork和exec分开使得可以对子进程IO重定向 如果两个文件描述符是通过一系列fork和dup调用从同一个原始文件描述符派生出来的，那么它们共享一个偏移量； 父子进程各自的文件描述符表条目指向同一个文件表项 2>&1使得错误输出重定向到文件名描述符1，如果不加&表示文件1 lab1 utilsleep 1234567891011121314#include "kernel/types.h"#include "user/user.h"int main(int argc, char *argv[]){ if(argc != 2) { fprintf(2, "sleep: argc != 2\n"); exit(1); ...
go
gobyeaxmple 介绍并发编程 异步模型 1、seamless轻量级跨核心抢占式 2、csp and shared by communicating goroutines比线程切换快10倍，运行时增长栈，消除同步与异步代码之间区别 使用语言内建的通道消除锁需求 安装： rm -rf /usr/local && tar -xvf /usr/local xxx go mod ini：初始化你的代码模块，通常为保存源代码的存储库路径 1234567package mainimport "fmt"func main() { fmt.Println("Hello, World!")} 跟py挺像的，导入fmt包，也可以通过go mod tidy导入别人的包 如import "rsc.io/quote"，也可以通过go build生成二进制文件 123456package mainimport "fmt"import...
汇编基础
汇编程序由4种类型的组件组成：指令（instruction）、伪指令（directive）、标号（label）及注释（comment） AT&T和Intel语法AT&T语法会在每个寄存器前面加上%，每个常量前加上$，并且源操作数在目的地操作数前 mov $0x1, %eax mov eax, 0x1 x86指令的机器级结构x86指令由可选前缀（prefix）、操作码（opcode）及零个或多个操作数（operand）组成。注意除了操作码外，剩余部分都是可选的 寄存器通用寄存器 其他寄存器： rip：指令寄存器 rflag：标志寄存器，用于一些条件，判断等标志位 cs、ds、ss、es、fs及gs段寄存器：x86-64目前已废止内存分段 常见指令 指令 描述 数据传输 mov dst,src 将src赋给dst xchg dst1,dst2 互换dst1和dst2 push src 将src压栈，并递减rsp pop dst 出栈赋给dst，并递增rsp 算术 add dst, src dst...
huffman
...
红黑树
Rbtree学习 rbtree的几个原则 （颜色属性）节点非黑即红 （根属性）根节点一定是黑色 （叶子属性）叶子节点（NIL）一定是黑色 （红色属性）每个红色节点的两个子节点，都为黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点) （黑色属性）从任一节点到其每个叶子的所有路径，都包含相同数目的黑色节点。 rbtree平衡调整的两个手段： 旋转 和 变色 rbtree的平衡调整需要关注两个场景：当父亲节点为红色 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475叔叔节点为红： 即父亲叔叔都为红-》调整为黑，同时爷爷变红 爷爷向上递推调整叔叔节点为黑： 1、LL型失衡：变色、对爷爷左旋或右旋 privot，root颜色取反，旋转 2、LR型失衡：对父亲旋转-》LL型##...
cond6并行计算及两种并发模型
并行计算利用cpu多核计算子集，然后合并返回结果；例如在快排中，本身计算privot左边，交给子线程计算privot右边 倘若我们要实现一套通用的规则而不依赖于存储容器，那就可以使用函数式编程 程序由一系列函数组成，每一步计算就是函数求值，并且不改变状态和数据（那样拷贝数据返回新值挺费内存吧） 12345678910111213141516171819202122232425template<class T>std::list<T> parallel_quick_sort(std::list<T> input) { if(input.empty()) return input; std::list<T> result; // 转移，前插 result.splice(result.begin(), input, input.begin()); T const& pivot = *result.begin(); 基于privot拆分链表 auto divide_point =...
互斥和锁
互斥c++通过std::mutex实现锁机制，确保多线程下只有一个进入临界区 1234#include <mutex>std::mutex mtx;mtx.lock();mtx.unlock(); 层级锁自定义锁添加权重来保证每次加锁顺序和解锁顺序，数值越大权重越高 12345678910111213141516171819class hmutex {public: hmutex(unsigned value):cur(val),pre(0)void lock(){ if(cur <= val) std::logic_error("faild"); mtx.lock(); pre=cur,cur=val;}void unlock(){ if(cur != val) std::logic_error("faild"); mtx.unlock(); cur=pre;}private:std::mutex mtx;unsigned val;unsigned...
条件变量实现安全队列和信号量
条件变量实现安全队列一些源码的解释 12#include <condition_variable>std::codition_variable cv; // wake up one waiter 1void notify_one() noexcept // wake up all waiters 1void notify_all() noexcept Nothing to do to comply with LWG-2135 because std::mutex lock/unlock are nothrow 1void wait(unique_lock<mutex>& _Lck) // wait for signal and test predicate 123456template <class _Predicate>void wait(unique_lock<mutex>& _Lck, _Predicate _Pred)...
CAS实现无锁队列
悲观锁：阻塞线程，等待锁释放，发生上下文切换 乐观锁：修改时检查，失败则不断重试 汇编原子操作： 12345678910int inc(int* value, int add) { int old; __asm__ volatile ( "lock; xaddl %2, %1;" // 指令1：lock; 指令2: xaddl, 操作数占位符：%1, %2 : "=a" (old) // 输出：结果放入通用寄存器eax : "m" (*value), "a" (add) // 输入：操作数1（内存），操作数2（寄存器eax） : "cc", "memory" // 编译方式，内存 ); return...