海岛一隅

sleep 注意👇这三个头文件的顺序不能修改，如果IDE有自动排序include的功能要关闭，否则通过不了编译 12345678910111213#include "kernel/types.h"#include "kernel/stat.h"#include "user.h"int main(int argc, char const *argv[]) { if (argc < 2) { printf("Usage: need sleep seconds\n"); exit(1); } int time = atoi(argv[1]); sleep(time); exit(0);} pingpong 代码看起来比较多，其实核心比较少的，我加了很多close，这个文件里面可以不加，应该用不了几个文件描述符，但是下面那一题一定要加，否则过不了 123456789101112131415161718192 ...

特别提醒，本文所涉及的源码是go1.21.0 darwin/amd64文件位置：container/list/list.go 1 数据结构12345678type Element struct { // 指向下一个节点和前一个节点 next, prev *Element // 标识当前element所属的List list *List // 存储的当前节点值 Value any} 1234type List struct { root Element // 哨兵节点 len int // 链表长度（不算哨兵节点）} 两者的关系如下图所示： 2 初始化123456func (l *List) Init() *List { l.root.next = &l.root l.root.prev = &l.root l.len = 0 return l} 将哨兵节点的next和prev都指向自己，表示当前链表为空 长度len设置为0 ...

1 定义Trie树，即字典树，又称前缀树，是一种树形结构，是一种哈希树的变种，像字典一样的树。 Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的，使用Trie相比哈希查询的好处是，路由算法中需要模糊匹配，哈希是做不到的，它只能精确查找。 2 实现2.1 字段123456class Trie{public: int tag; Trie *nxt[26]{}; Trie(): tag(0) {}}; 首先定义核心字段，tag用来表示当前节点是否是某个字符串的结尾，比如说如果在上面的树中，又来了一个go，那在第一个o中的tag应该标识为1 2.2 插入12345678910void insert(const string &s) { Trie *p = this; for (char i : s) { if (p->nxt[i - 'a'] == nullptr) { ...

特别提醒，本文所涉及的源码是go1.21.0 darwin/amd64文件位置：runtime/map.go 普通的map并不是并发安全的一个数据结构，因此想要使用并发安全的map，sync包下提供了一个sync.map数据结构 1 数据结构1234567type Map struct { // 保护并发读写、写写 mu Mutex read atomic.Pointer[readOnly] dirty map[any]*entry misses int} read：无锁化的map，实际类型为atomic.Pointer dirty：加锁的map，是一个普通的map misses：每次从read中读取失败，misses都会加1，达到一定阈值后，会将dirty提升为read 1234type readOnly struct { m map[any]*entry amended bool } m：read中的map，存放k-v对 amended：标识read和dirty中的元素是否一致 ...

特别提醒，本文所涉及的源码是go1.21.0 darwin/amd64文件位置：runtime/slice.go 1 数据结构12345678type RWMutex struct { w Mutex // 写锁 writerSem uint32 // 写操作等待读操作完成 readerSem uint32 // 读操作等待写操作完 readerCount atomic.Int32 readerWait atomic.Int32 }const rwmutexMaxReaders = 1 << 30 readerCount：在没有写锁介入的时候，表示的是当前正在读操作的数量。如果有写介入，则readerCount+rwmutexMaxReaders等于正在读操作的数量 readerWait：在能够获取写锁前，还需要等待多少个读协程释放读锁 2 写锁123456789101112func (rw *RWMutex) Lock() { ...

特别提醒，本文所涉及的源码是go1.21.0 darwin/amd64 文件位置：sync/mutex.go 文章所涉及的go汇编代码都是以_amd64结尾的文件 1 前期知识1.1 阻塞锁将当前协程阻塞挂起，直到锁被释放后，以回调的方式将阻塞协程重新唤醒，进行锁争夺 1.2 自旋锁结合CAS，重复校验锁的状态并尝试获取锁，始终占用cpu 1.3 对比 优势 劣势 阻塞/唤醒 不占用cpu时间片 需要上下文切换 自旋 不会阻塞当前协程 占用cpu时间片 2 数据结构1234type Mutex struct { state int32 sema uint32} state：状态表示，第1位表示是否上锁，第2位表示mutex是否被唤醒，第3位表示mutex是否处于饥饿模式 sema：控制锁状态的信号量 3 上锁1234567891011func (m *Mutex) Lock() { // 初次尝试，state为0则直接抢锁成功 if atomic.CompareAndSwapInt32(& ...

特别提醒，本文所涉及的源码是go1.21.0 darwin/amd64文件位置：runtime/slice.go 1 数据结构12345type slice struct { array unsafe.Pointer len int cap int} array：指向存储元素内存空间的起始地点 len：切片的长度 cap：切片的容量 2 初始化12345678910111213func makeslice(et *_type, len, cap int) unsafe.Pointer { // 判断分配的内存是否会溢出 mem, overflow := math.MulUintptr(et.Size_, uintptr(cap)) if overflow || mem > maxAlloc || len < 0 || len > cap { mem, overflow := math.MulUintptr(et.Size_, uintptr(len)) ...

特别提醒，本文所涉及的源码是go1.21.0 darwin/amd64 文件位置：runtime/map.go 哈希表作为一种非常常见的数据结构，在其它语言中也都会有出现，因此本文不对哈希表的概念、用法做解释，专注于go语言中的源码学习。 1 数据结构1234567891011type hmap struct { count int // 当前map中的元素数量 flags uint8 B uint8 noverflow uint16 hash0 uint32 // 哈希种子，在创建map时得到的一个随机数 buckets unsafe.Pointer // 桶数组 oldbuckets unsafe.Pointer // 扩容过程中旧的桶数组 nevacuate uintptr extra *mapextra // 额外记录的信息} flags：标志位 iterator = 1：可能有迭代器在遍历buckets ol ...

特别提醒，本文所涉及的源码是go1.21.0 darwin/amd64 文件位置：runtime/trace/chan.go 1 基本数据结构1.1hchanGo语言的channel在运行时使用runtime.hchan结构体来表示，如下所示： 1234567891011121314type hchan struct { qcount uint // 已经存放的元素个数 dataqsiz uint // 容量 buf unsafe.Pointer // 存放元素的环形缓冲区 elemsize uint16 // 元素类型的大小 closed uint32 // channel是否关闭 elemtype *_type // 元素类型 sendx uint // channel发送操作处理的位置 recvx uint // channel接收操作处理的位置 recvq waitq // 因接 ...

特别提醒，本文所涉及的源码是go1.21.0 darwin/amd64 1. 什么是Context在多个goroutine之间传递上下文的对象，传递的信息包括取消信号、截止时间以及其他一些跨api边界的值 2. 核心数据结构2.1 Context123456type Context interface { Deadline() (deadline time.Time, ok bool) Done() <-chan struct{} Err() error Value(key any) any} Context定义为Interface，定义了4个核心函数： Dealine：返回context的过期时间和一个bool值判断是否设置了deadline Done：返回context中的channel，该channel会在当前工作完成或者上下文被取消后关闭，多次调用返回的是同一个channel，如果该context是不能被取消的，则会返回nil Err：返回context结束的原因 Value：返回contxet中存储的 ...