singleton
1. 什么是单例模式？单例模式（Singleton Pattern）是一种创建型设计模式，它确保一个类只有一个实例，并提供一个全局访问点来访问该实例。 2. 为什么需要单例模式？在多线程环境下，我们需要多个线程使用同一份资源。 2.1 为什么不使用全局变量？在一些较为简单的环境中，直接使用一些全局变量供所有线程使用是很好的。 但是，如果这个对象是资源密集型的，使用全局变量会导致资源的浪费。而且，简单的全局变量没有提供访问控制（封装），线程可以任意地访问和修改。 而单例模式就可以实现按需创建实例，避免了资源的浪费。而且提供了类封装，确保不会有意外的修改。 3. 单例模式的实现（go）单例模式尤其要注意线程安全。 sync.Once 确保了实例只被创建一次，避免了多线程环境下的竞态条件。 以下是一个懒加载的版本。 中间件代码： 1234567891011121314151617var once sync.Oncetype singleton struct {}var singleInstance *singletonfunc GetInstance()...
buffer pool project study
本周主要跟着代码随想录学习了LRU, LFU, 以及ARC三种缓存替换算法的原理和C++实现。 1. LRULRU是Least Recently Used的缩写，即淘汰最近最少使用的元素。 缓存的实现使用了一个哈希表和一个双向链表。哈希表用于快速查找缓存中的元素，双向链表用于维护缓存中的元素顺序。 每当涉及一个元素的key时，将该元素移动到双向链表的头部。当缓存满时，将双向链表的尾部元素删除。同时将该元素从哈希表中删除。 1.1 改进以上的LRU存在着缓存污染、锁的粒度过大的问题。 缓存污染：当新加进来的一次性的数据很多，导致缓存满时，传统的LRU会直接删除尾部元素。但是，尾部元素可能是热门数据。锁的粒度大：一把大锁锁全局。多线程高并发的访问下，同步等待将是一笔极大的时间开销。 故考虑以下改进： 1.1.1...
2024 xv6 labs 2
本周完成了剩下的实验。上一篇见2024-xv6-labs-1 1. net lab1.1 NIC第一个实验是补全e1000_transmit() 和 e1000_recv() 重点在于先要理解e1000初始化的代码，以及e1000_dev.h里给出的各寄存器的定义。 然后理清一下工作流程：transmit所做的，其实就是将发送区和发送环的尾部更新为带发送的数据对应的元数据。注意此时status应为0而不是E1000_TXD_STAT_DD，因为这只是代表将数据填入发送区，并没有真正发送。然后更新E100_TDT的值。但为了防止竞态条件，所以还要注意用e1000_lock加锁。 而receive所做的就是以帧为单位，不断地将缓冲区里的数据交给net_rx()，并更新缓冲区和E1000_RDT，直到遇见E1000_RXD_STAT_DD。这里不用加锁，但值得注意的是E1000_RDT必须在最后更新？想不通。 1.2 UDP Receive说来惭愧，这个部分我实在没有思路，是让ai写的。。。 2. lock2.1 Memory...
binary search
1. 总结二分查找的原理非常简单，但是一些细节例如是 l<r还是 l<=r、更新 r时是 r=mid还是 r=mid-1（l同理）等地方却有些让人头疼，实际写来如果不注意就可能会造成死循环。 于是总结一种模板： 定义域为[lo, hi)的单增的f(x), 找出最小的ans, 使得f(ans)>0成立。 单减同理，甚至可以进行预处理先转化为单增的情况。 伪代码如下： 12345678910111213141516algorithm binary-search(lo,hi) while the search area has elments do: mid <- lo + (hi-lo)/2; if f(mid) satisfied: // the answer may occur here ans := mid; hi <- mid; // the search area could have no elments when in the next loop, so return ans; ...
monotonic stack
他向远方望去，无法看到高山背后的矮山，只看到一座座更高的山峰。————by 灵神 1. 总结单调栈就是保持栈内元素单调的栈。当新元素破坏单调性时，弹出栈顶元素，弹出的瞬间就找到栈顶元素对应的答案。 栈里存放着暂时还没有找到对应答案的元素。新元素入栈时，如果栈顶元素使得栈单调性被破环，那么栈顶元素的答案产生，栈顶元素找到答案，出栈。因此需要建立的栈的单调性与题目的答案需求往往是“反过来”。要下一个更大就要单减；要下一个更小就要单增。 12345678910algorithm generalized-monotonic-stack(A, cmp, process) stack S ← ∅ for i ← 0 to n-1 do: while S ≠ ∅ and condition(A[i], A[S.top()]) do: // 栈的单调性被破坏，while是为了让栈里满足条件的元素都可以出栈 j ← S.pop() // 栈顶出栈 recordAnswer(j, i) // 计算并记录栈顶对应的答案 ...
2024 xv6 labs 1
本周主要完成了2024-xv6-labs的util到cow的五个实验。 1. util lab1.1 sleep这个算是最简单的实验了。按照hints一步步写即可。没有任何额外需要注意的地方。 1.2 pingpong这个实验的主要难点是理解pipe函数的使用。先查看 sys_pipe函数： 1234567891011121314151617181920212223voidsys_pipe(void){ uint64 fdarray; // user pointer to array of two integers struct file *rf, *wf; int fd0, fd1; struct proc *p = myproc(); argaddr(0, &fdarray); if(pipealloc(&rf, &wf) < 0){ ... } ... if((fd0 = fdalloc(rf)) < 0 || (fd1 = fdalloc(wf))...