科技在抱团，有点恶心，a股流动性都被吸光了

就是一般来说，你在市场上 take 别人的单会有一定的 impact，当你的资金量大的时候会尤其有这个问题。
举个例子比如你是一个 intraday 的 low/mid-freq statistic arbitrage 策略，每天或者每几分钟入场一次，假设入场时机不是 open/close auction 等没有 spread 的时机，那你每次入场的时候可能由于资金量不小，会导致你的资金对市场产生很大影响。比如原本你的 alpha 可能只能赚几个 bps，但是由于下单不够精细导致产生了很大的冲击成本，那你的 alpha 可能就被成本吃掉很多，甚至完全失效。
所以这时候为了解决一种“在规定时间内达成规定仓位”的问题，就产生了 execution 这个环节。目的是在于减少交易成本，这一步一般都偏高频，做的精细的话会有更高频的 signal 做辅助，做得好做到比市场成交的 vwap 低几个 bps。如果做的特别好的话甚至可以单飞成为一个高频策略。

笑死我了，早年黑历史了，从哪看到的啊

草，笑死我了，早年黑历史，从哪看到的啊。。

业界普遍做法是用 RL 做 execution

我在上海，深圳，北京各租过 3 个月，我感觉很容易啊，可能诀窍是比暑假提前一个月来租房，或者过年附近租房吧

现实中欧洲原子能机构叫 CERN，不是 SERN。
原作里还说 john titor 要找的是 IBN 5100，现实里则是 IBM 5100，都是改编的吧

sern，应该是根据这个改编的

和小登说：本科生就该好好上课，出去实习的都做不好科研，然后把上届的实习学长挂了

然而，zkw 混了大半辈子还只是个讲师，没见有啥成果，😅估计他本科时候也是好好上课的，读了个博士不写是哪个学校，估计野鸡，也是真无敌了

交门 offer 王现身了

无回放

成功门友
——————————
发自我的手机

不知道，我去问问能不能直播/录像

主讲人有一位在很短的时间内找到了工作，另外两位秋招分别收获了 5 个 offer 和 10+ 个 offer

😭

有人高中就能去 jump trading 了，评价还是菜就多练

中国人关键的一生

1. 日常实习可行，但很累，尤其如果你有十多门课，那就更累
2. 看就业具体的方向，ics，概率论，凸优化帮助过我，其他的没啥帮助
3. 能实现，不能实现的话，两段较好的暑期实习有很大的优势。实习经验是累积的，第一段实习会在帮助找第二段实习上发挥巨大作用，这个影响累计到秋招找全职工作时候会显示出很大的优势，前提是有价值且垂直的实习
4. 个人感觉中国大学生容错率不大，单纯为了钱多的话，个人建议选好方向，垂直做某一领域内的工作。

延长养老保险缴纳时间，减少养老保险享受时间

我妈算出来延迟了一年半

亲亲😘

盒盒了，所以他远超同龄人了吗？

确实，组成老师可能觉得他挂了对方，对方会很在意，所以暗爽，实际上人家根本不会在意那个保研名额

就是丢失保研资格，然后可以选择跟班走或者去计算机系，去计算机系要补课但是还能竞争保研资格，跟班走失去保研资格但是不用补课，不过感觉谁选去计算机系啊，肯定跟班走吧一般来说

确实，从 tyz 那里听过这位学长的英勇事迹
后面传的都是这位学长本科就业出路多么多么牛逼，没人再说挂科，计试分流的事，评价是这就是你交😅

教师节快乐组成老师

很赞同，学过的东西不会完全没用，一般确实能用上 10% 至少，学的时候不知道罢了，用上的时候能想起来的只有 10%，但是实际上其他 90% 的广泛涉猎也是必要的。
提高这个比例最好的方法是刚出生就选好以后的行业，找行业大牛一步一步带着上学，垂直入坑某个行业，这样学的知识可能 70% 以上有用。
先不提可行性，这样开局就定好了结局的人生又有啥意思呢

班长无权倒扣基础分倒是

刚才在小群里和群友激情讨论，得到的结论是你应该声称自己将会在 T 天内每天晚上审核一次，每个人的材料至多审核 x 次，如果审核完还是有错会直接上报给老师。
就完成了一次踢皮球，感觉很智慧

能不能网爆一下把头像搞出来，你这样一点威慑力都没有😆还得是你还能跟他讲上两句
换我直接 我操你妈逼了狗东西 喷就完了，讲什么理呢
——————————————————
感觉口嗨了，换我应该是不会提醒，给他扣完了直接交

感觉这转化成了经典问题，如果你是投资人，你会怎么投资 start ups
只不过把投资钱换成投资时间

感觉很对，不过我觉得前提得成为高水平 trader 吧😭同时这个某个比例的钱（某个比例怎么划分）比如一个策略从生产出来，有人挖因子，有人组合因子，有人搞具体的执行策略，我觉得很难去评定这几部分具体的贡献比例，除非一整个策略都是一个人搞出来的。我觉得这就要求一个人得从 junior 级干到至少 pm 级才行

那我恐怕得带资进组吧😭（而且感觉他们这种搞高频的一般不倾向于融资，有好的策略都自己偷着爽爽吃了，何必给别人分一杯羹

草，虽然来晚了但是怎么看起来像我前司 twx

HRT，感觉高频夏普高发钱多还稳，而且团队人少意味着更有机会 take the leadership

亲亲 🥰

我就是唐山人，你说的话我理解不了，完全没觉得本地方言像女人，东北更不像
我完全没觉得语调阴柔，而且说婉转，这边方言有的地方是没有三声的

牛蛙！

奥奥，比较的时候应该是限定了 crtp 和虚函数都可以实现的场景，不过确实可以补充一下，CRTP 不能动态派发。
两方的优点都写在对方的缺点里了，反过来看就行

我哪句话写的有问题吗？
对比 CRTP 和虚函数的优劣是 Jump 面试时候问的原题

看起来像，不过国内是不是都拉满两年的

哪个啊？LRU 那个？我都上网随便看了几眼粘了一份

# 虚拟内存和内存分配？ 摘抄一下这篇文章 虚拟内存：解决物理内存问题的策略-CSDN博客 ## 物理地址 1. 内存空间利用率的问题 各个进程对内存的使用会导致内存碎片化，当要用 malloc 分配一块很大的内存空间时，可能会出现虽然有足够多的空闲物理内存，却没有足够大的连续空闲内存这种情况，东一块西一块的内存碎片就被浪费掉了

1. 读写内存的安全性问题
   物理内存本身是不限制访问的，任何地址都可以读写，而现代操作系统需要实现不同的页面具有不同的访问权限，例如只读的数据等等

2. 进程间的安全问题
   各个进程之间没有独立的地址空间，一个进程由于执行错误指令或是恶意代码都可以直接修改其它进程的数据，甚至修改内核地址空间的数据，这是操作系统所不愿看到的

3. 内存读写的效率问题
   当多个进程同时运行，需要分配给进程的内存总和大于实际可用的物理内存时，需要将其他程序暂时拷贝到硬盘当中，然后将新的程序装入内存运行。由于大量的数据频繁装入装出，内存的使用效率会非常低。

虚拟内存

内存分段

1、内存分段
将虚拟内存分段，比如代码段、数据段、栈段、堆段等。
A、分段机制下，物理内存与虚拟内存如何映射的
分段机制里，由段选择因子和段内偏移量
段选择因子：保存在段寄存器中，里面包含有段号、标志位等。段号指向段表，段表保存段的基地址、段的界限和特权等级等。
段内偏移：一般物理地址等于段基地址 + 段内偏移。

B、存在问题：
内存碎片
内存分段是按需分配，不会产生内部碎片，但是会产生外部碎片，可能会产生多个离散的空闲内存分区不太容易复用。解决外部碎片的方法是内存交换，把虚拟内存的各段先一个个交换到外存，存到硬盘，再一个个交换过去，内存交换效率低。
如果内存交换的时候，交换的是一个占内存空间很大的程序，这样整个机器都会显得卡顿。

内存分页

分页是把整个虚拟和物理内存空间切成一段段固定尺寸的大小。这样一个连续并且尺寸固定的内存空间，我们叫页。在 Linux 下，每一页的大小为 4KB。

内存分页产生页表和虚拟页号

一般来说，物理地址是知道虚拟页号和页内偏移，然后根据虚拟页号（虚拟页号是页表的索引项），到相应的页表（页表是存储在内存中的）中查找到物理页号，物理页号 + 页内偏移等于物理地址 ——（其中主要是 MMU 内存管理单元发挥作用）

A、存在问题：
内存碎片
分页机制不是按需分配，是分配适当的页表，页表每个是固定大小 4K，所以会产生内部碎片，因为大概率会有一个页表不是完全填充的。这就是内部碎片问题。

分页机制解决内存交换效率低的问题：
分页机制，在内存交换的时候只交换几个页，在此过程中，会有换入、换出操作，就是将内存页面从内存换入或换出到磁盘。相比于分段机制将整个段进行内存与磁盘间的交换，提高了内存交换的效率。

存放页表会占用内存（空间上的缺陷）
因为操作系统是可以同时运行非常多的进程的，那这不就意味着页表会非常的庞大。
在 32 位的环境下，虚拟地址空间共有 4GB，假设一个页的大小是 4KB（2^12），那么就需要大约 100 万（2^20）个页，每个「页表项」需要 4 个字节大小来存储，那么整个 4GB 空间的映射就需要有 4MB 的内存来存储页表。但是要知道每个进程都是有自己的虚拟地址空间的，也就说都有自己的页表。多进程就需要耗费很多内存。
如何解决分页机制的占用内存的问题：
采用多级页表。由于局部性原理，对于大多数程序，其用到的空间远小于 4G，所以其对应的页表项有的是空的，所以如果某个一级页表的页表项没有被用到，也就不需要创建这个页表项对应的二级页表了，即可以在需要时才创建二级页表，这样占用的内存空间就是大大减少。

虚拟内存好处

第一，虚拟内存可以使得进程对运行内存超过物理内存大小，因为程序运行符合局部性原理，CPU 访问内存会有很明显的重复访问的倾向性，对于那些没有被经常使用到的内存，我们可以把它换出到物理内存之外，比如硬盘上的 swap 区域。
第二，由于每个进程都有自己的页表，所以每个进程的虚拟内存空间就是相互独立的。进程也没有办法访问其他进程的页表，所以这些页表是私有的，这就解决了多进程之间地址冲突的问题。
第三，页表里的页表项中除了物理地址之外，还有一些标记属性的比特，比如控制一个页的读写权限，标记该页是否存在等。在内存访问方面，操作系统提供了更好的安全性。
第四，解决物理内存的离散式存储问题，虚拟内存中连续存储解决了物理内存碎片化资源利用率过低的问题。

内存分配

用户态调用 malloc 会分配堆的内存空间，实际上完成了一次内存映射。
内存映射对应的系统调用主要有 brk() 和 mmap()，小块内存（<128K）使用 brk 来分配内存，大块内存（>128K），使用 mmap 来分配内存。

brk

小块内存在释放的时候，不会立即释放，而是被缓存起来，可以通过 brk 来重复利用。这种方式减少了缺页中断发生的频率，提高了访存效率，但是这种方式容易造成内存碎片化。

mmap

大块内存在释放的时候直接归还系统，每次 mmap 必发生缺页中断，频繁内存分配会造成大量缺页中断，降低性能。

LRU 替换算法实现
一个 leetcode 题，要求 O(1) 查找 O(1) 以 LRU 方式替换 cacheline。
使用双向链表实现即可，用 STL list 比较方便。

class LRUCache {
public:
    LRUCache(int capacity) {
        this->capacity=capacity;
    }
    
    int get(int key) {
        auto pos=_lruHash.find(key);
        if(pos!=_lruHash.end()){
            //Cache 命中，调整计数器 更新 key 对应的节点的位置
            list<pair<int,int>>::iterator ptr=pos->second;
            //转移节点库函数 std::list::splice
            //void splice (iterator position, list& x, iterator i);
            //Transfers elements from x into the container, inserting them at position.
            //将 x 的第 i 个节点转移带 position 位置上
            _lruCacheList.splice(_lruCacheList.begin(), ptr);
            return pos->second->second;
        }
        return -1;
    }
    
    void put(int key, int value) {
        auto pos=_lruHash.find(key);
        if(pos!=_lruHash.end()){
            //更新 Cache，更新对应节点的位置
            list<pair<int,int>>::iterator ptr=pos->second;
            ptr->second=value;//更新数据
            _lruCacheList.splice(_lruCacheList.begin(),ptr);
        }
        else{
            //新增 Cache
            if(capacity==_lruHash.size()){
                //满了，替换删除尾上的数据
                pair<int,int>&back=_lruCacheList.back();
                _lruHash.erase(back.first);
                _lruCacheList.pop_back();
            }
            _lruCacheList.push_front(make_pair(key,value));
            _lruHash[key]=_lruCacheList.begin();
        }
    }
private:
     unordered_map<int,list<pair<int,int>>::iterator>_lruHash;//方便查找
     list<pair<int,int>>_lruCacheList;//保存数据
     size_t capacity;
};

/\*\*
 \* Your LRUCache object will be instantiated and called as such:
 \* LRUCache\* obj = new LRUCache(capacity);
 \* int param\_1 = obj->get(key);
 \* obj->put(key,value);
 \*/

页表的 LRU 替换也类似。

# 并行编程及其应用

pthread(POXIS thread)

互斥锁和自旋锁

Mutex 想要使用 lock 去获得一个锁的时候，如果此时这个锁正被其他线程持有，那么使用 lock 的线程就会被阻塞，进行上下文切换，将线程放置到等待队列中。此时 CPU 可以被安排去做其他事情，等待锁的所有权空出来后再再次执行该线程。
Spin 想要使用 lock 获得一个锁的时候，如果此时无法获取到锁，会一直忙等待，直到获取该锁为止。
具体来说，一般获取锁的等待时间较长的时候使用 Mutex，获取锁的等待时间较短的时候使用 Spin。

条件变量

std::condition_variable
使用函数：

1. pthread_cond_init/destroy 类似于互斥锁和自旋锁

2. pthread_cond_wait
   函数定义：
   int pthread_cond_wait(pthread_cond_t *restrict cond, pthread_mutex_t *restrict mutex)
   cond：指向条件变量的指针。
   mutex：指向互斥锁的指针。
   调用该函数之前，必须先获得互斥锁 mutex，在等待期间，互斥锁会自动释放，并使当前线程处于阻塞状态，直到条件变量被唤醒并且重新获得互斥锁为止。

3. pthread_cond_signal/broadcast
   用于唤醒等待条件变量的一个线程。signal 如果有多个线程在等待条件变量，则会唤醒其中一个线程；broadcast 则是唤醒所有等待的线程。
   如果没有线程在等待条件变量，则该函数不会产生任何效果。

阻塞式循环队列

上网抄个代码：

    #include <unistd.h>
    #include <cstdlib>
    #include <condition_variable>
    #include <iostream>
    #include <mutex>
    #include <thread>
    
    static const int kItemRepositorySize  = 10; // Item buffer size.
    static const int kItemsToProduce  = 1000;   // How many items we plan to produce.
    
    struct ItemRepository {
        int item_buffer[kItemRepositorySize]; // 产品缓冲区，配合 read_position 和 write_position 模型环形队列.
        size_t read_position; // 消费者读取产品位置.
        size_t write_position; // 生产者写入产品位置.
        std::mutex mtx; // 互斥量，保护产品缓冲区
        std::condition_variable repo_not_full; // 条件变量，指示产品缓冲区不为满.
        std::condition_variable repo_not_empty; // 条件变量，指示产品缓冲区不为空.
    } gItemRepository; // 产品库全局变量，生产者和消费者操作该变量.
    
    typedef struct ItemRepository ItemRepository;
    
    
    void ProduceItem(ItemRepository *ir, int item)
    {
        std::unique_lock<std::mutex> lock(ir->mtx);
        while(((ir->write_position + 1) % kItemRepositorySize)
            == ir->read_position) { // item buffer is full, just wait here.
            std::cout << "Producer is waiting for an empty slot...\n";
            (ir->repo_not_full).wait(lock); // 生产者等待"产品库缓冲区不为满"这一条件发生.
        }
    
        (ir->item_buffer)[ir->write_position] = item; // 写入产品.
        (ir->write_position)++; // 写入位置后移.
    
        if (ir->write_position == kItemRepositorySize) // 写入位置若是在队列最后则重新设置为初始位置.
            ir->write_position = 0;
    
        (ir->repo_not_empty).notify_all(); // 通知消费者产品库不为空.
        lock.unlock(); // 解锁.
    }
    
    int ConsumeItem(ItemRepository *ir)
    {
        int data;
        std::unique_lock<std::mutex> lock(ir->mtx);
        // item buffer is empty, just wait here.
        while(ir->write_position == ir->read_position) {
            std::cout << "Consumer is waiting for items...\n";
            (ir->repo_not_empty).wait(lock); // 消费者等待"产品库缓冲区不为空"这一条件发生.
        }
    
        data = (ir->item_buffer)[ir->read_position]; // 读取某一产品
        (ir->read_position)++; // 读取位置后移
    
        if (ir->read_position >= kItemRepositorySize) // 读取位置若移到最后，则重新置位.
            ir->read_position = 0;
    
        (ir->repo_not_full).notify_all(); // 通知消费者产品库不为满.
        lock.unlock(); // 解锁.
    
        return data; // 返回产品.
    }
    
    
    void ProducerTask() // 生产者任务
    {
        for (int i = 1; i <= kItemsToProduce; ++i) {
            // sleep(1);
            std::cout << "Produce the " << i << "^th item..." << std::endl;
            ProduceItem(&gItemRepository, i); // 循环生产 kItemsToProduce 个产品.
        }
    }
    
    void ConsumerTask() // 消费者任务
    {
        static int cnt = 0;
        while(1) {
            sleep(1);
            int item = ConsumeItem(&gItemRepository); // 消费一个产品.
            std::cout << "Consume the " << item << "^th item" << std::endl;
            if (++cnt == kItemsToProduce) break; // 如果产品消费个数为 kItemsToProduce, 则退出.
        }
    }
    
    void InitItemRepository(ItemRepository *ir)
    {
        ir->write_position = 0; // 初始化产品写入位置.
        ir->read_position = 0; // 初始化产品读取位置.
    }
    
    int main()
    {
        InitItemRepository(&gItemRepository);
        std::thread producer(ProducerTask); // 创建生产者线程.
        std::thread consumer(ConsumerTask); // 创建消费之线程.
        producer.join();
        consumer.join();
    }

上述代码是单生产者和单消费者模型，多生产者多消费者模型只需要增加两个计数器用来计算当前已经生产/消费了多少个物品。

无锁循环队列

内核实现了一个无锁循环队列 kfifo
粘贴一下代码：

/**
 * __kfifo_put - puts some data into the FIFO, no locking version
 * @fifo: the fifo to be used.
 * @buffer: the data to be added.
 * @len: the length of the data to be added.
 *
 * This function copies at most @len bytes from the @buffer into
 * the FIFO depending on the free space, and returns the number of
 * bytes copied.
 *
 * Note that with only one concurrent reader and one concurrent
 * writer, you don't need extra locking to use these functions.
 */
unsigned int __kfifo_put(struct kfifo *fifo,
			 unsigned char *buffer, unsigned int len)
{
	unsigned int l;

    //计算写入空间：队列大小 - 写入位置 + 读取位置
	len = min(len, fifo->size - fifo->in + fifo->out);

	/*
	 * Ensure that we sample the fifo->out index -before- we
	 * start putting bytes into the kfifo.
	 *
	 * 内存屏障（全屏障）
	 */

	smp_mb();

	/* first put the data starting from fifo->in to buffer end */
    /* 从队列写入位置 (mod 队列大小) 写入到队列结尾处 */
	l = min(len, fifo->size - (fifo->in & (fifo->size - 1)));
	memcpy(fifo->buffer + (fifo->in & (fifo->size - 1)), buffer, l);

	/* then put the rest (if any) at the beginning of the buffer */
    /* 从队列起始位置向后写入剩余数据 */
	memcpy(fifo->buffer, buffer + l, len - l);

	/*
	 * Ensure that we add the bytes to the kfifo -before-
	 * we update the fifo->in index.
	 *
	 * 内存屏障（写屏障）
	 */

	smp_wmb();

    //单调递增写入位置
	fifo->in += len;

	return len;
}

/**
 * __kfifo_get - gets some data from the FIFO, no locking version
 * @fifo: the fifo to be used.
 * @buffer: where the data must be copied.
 * @len: the size of the destination buffer.
 *
 * This function copies at most @len bytes from the FIFO into the
 * @buffer and returns the number of copied bytes.
 *
 * Note that with only one concurrent reader and one concurrent
 * writer, you don't need extra locking to use these functions.
 */
unsigned int __kfifo_get(struct kfifo *fifo,
			 unsigned char *buffer, unsigned int len)
{
	unsigned int l;

    //计算读取空间：写入位置 - 读取位置
	len = min(len, fifo->in - fifo->out);

	/*
	 * Ensure that we sample the fifo->in index -before- we
	 * start removing bytes from the kfifo.
	 *
	 * 内存屏障（读屏障）
	 */

	smp_rmb();

	/* first get the data from fifo->out until the end of the buffer */
    /* 从缓存读取位置 (mod 队列大小) 读取到缓存结尾处 */
	l = min(len, fifo->size - (fifo->out & (fifo->size - 1)));
	memcpy(buffer, fifo->buffer + (fifo->out & (fifo->size - 1)), l);

	/* then get the rest (if any) from the beginning of the buffer */
    /* 从缓存起始位置读取剩余数据 */
	memcpy(buffer + l, fifo->buffer, len - l);

	/*
	 * Ensure that we remove the bytes from the kfifo -before-
	 * we update the fifo->out index.
	 *
	 * 内存屏障（全屏障）
	 */

	smp_mb();

    //单调递增读取位置
	fifo->out += len;

	return len;
}

shared_ptr

• shared_ptr 本身不是一个线程安全的 STL，因此并发读写对应内存区域是不安全的。
• 由于赋值操作涉及原内存释放、修改指针指向等多个修改操作，其过程不是原子操作，因此对 shared_ptr 进行并发赋值不是线程安全的。
• 对 shared_ptr 进行并发拷贝，对数据指针和控制块指针仅进行读取并复制，然后对引用计数进行递增，而引用计数增加是原子操作。因此是线程安全的。

#include<iostream>
#include<atomic>
 
using namespace std;
 
class Counter
{
public:
	Counter()
	{
		count = 1;	
	}
	
	void add()
	{
		count++;
	}
	
	void sub()
	{
		count--;
	}
	
	int get() const
	{
		return count;
	}
	
private:
	std::atomic<int> count;
};
 
template <typename T>
class Sp
{
public:
	Sp();                           //默认构造函数
	Sp(T *ptr);                     //参数构造函数
	Sp(const Sp &obj);              //复制构造函数
	~Sp();                          //析构函数
	Sp &operator=(const Sp &obj);   //重载=
	T *get();                       //得到共享指针指向的类
	   
	int getcount();                 //得到引用计数器
private:
	T *my_ptr;                      //共享指针所指向的对象
	Counter* counter;                   //引用计数器
	void clear();                   //清理函数
};
 
//默认构造函数，参数为空，构造一个引用计数器
template<typename T>
Sp<T>::Sp()
{
	my_ptr = nullptr;
	counter = new Counter();
	counter->add();
}
 
//复制构造函数，新的共享指针指向旧的共享指针所指对象
template<typename T>
Sp<T>::Sp(const Sp &obj)
{
    //将所指对象也变为目标所指的对象
	my_ptr = obj.my_ptr;
    //获取引用计数器，使得两个共享指针用一个引用计数器
	counter = obj.counter;
    //使这个对象的引用计数器 +1
	counter->add();	
};
 
//重载=
template<typename T>
Sp<T> &Sp<T>::operator=(const Sp&obj)
{
    //清理当前所引用对象和引用计数器
	clear();
    //指向新的对象，并获取目标对象的引用计数器
	my_ptr = obj.my_ptr;
	counter = obj.counter;
    //引用计数器 +1
	counter->add();
    //返回自己
	return *this;	
}
 
//创建一个共享指针指向目标类，构造一个新的引用计数器
template<typename T>
Sp<T>::Sp(T *ptr)
{
	my_ptr = ptr;
	counter = new Counter();
}
 
//析构函数，出作用域的时候，调用清理函数
template<typename T>
Sp<T>:: ~Sp()
{
	clear();
}
 
//清理函数，调用时将引用计数器的值减 1，若减为 0，清理指向的对象内存区域
template<typename T>
void Sp<T>::clear()
{
    //引用计数器 -1 
	counter->sub();
    //如果引用计数器变为 0，清理对象
	if(0 == counter->get())
	{
		if(my_ptr)
		{
			delete my_ptr;
		}
		delete counter;
	}
}
 
//当前共享指针指向的对象，被几个共享指针所引用
template<typename T>
int Sp<T>::getcount()
{
	return counter->get();	
}

template<typename T>
T * sp<T>::get()
{
    return my_ptr;
}

用户态和内核态

引用一下之前的帖子：

# 原子操作和 C++ 内存序

原子操作和原子类型

std::atomic

在 atomic 库中定义了原子类型 std::atomic<>，例如可以使用 std::atomic。
std::atomic<>可以通过函数实现各类原子操作，例如 std::atomic<>::load()，std::atomic<>::store()，std::atomic<>::fetch_and()，std:;atomic<>::fetch_add 等等。

CAS 操作

通过 atomic<>::compare_exchange_weak/strong(x, y) 函数实现。表示如果原子量的值等于 x，则令原子量的值变为 y，且返回 true，否则将 x 的值变为原子量的值且返回 false。
weak 性能更好，但是可能在可以返回 true 的时候返回 false。
strong 性能更差，但是在可以返回 true 的时候一定会返回 true。

C++ 内存序

1. seq_cst 要求所有原子操作必须按照在程序中出现的顺序执行，最严格的内存序
2. acquire 确保之前的所有使用 release 的写操作都对当前线程可见，该语句后的所有语句不能先于当前语句执行完成前执行。
3. release 确保该语句前的所有写语句都已经执行完毕，并且对其他线程可见。
4. acq_rel 确保该语句后的读语句执行前，该语句前的所有写语句执行完毕且对其他线程可见；确保该语句后的写语句执行前，该语句前的所有读语句执行完毕。
5. relaxed 不对顺序做限制，最弱的内存序。
6. consume

# 编译与链接 考虑用下面这条指令来构建 a.cpp 的可执行文件 ``` gcc a.c -o a ``` 这句话执行的时候做了四件事：预处理，编译，汇编，链接；这四个阶段分别对应了预处理器，编译器，汇编器，链接器四种工具。

预处理

1. 展开所有宏定义，条件宏定义
2. 将#include 包含的头文件插入到指定位置
3. 删除注释，添加文件名和行号（用于报错）

编译

编译过程可分为 6 步：词法分析，语法分析，语义分析，源代码优化，代码生成，目标代码优化
前 4 步属于编译器前端，后 2 步属于编译器后端，按照中间语言生成的前后来划分。
具体来说，词法分析将代码分割为 token，语法分析通过 token 产生抽象语法树，语义分析对抽象语法树进一步处理，检查程序是否符合语义规则，源代码优化将整个抽象语法树转换为中间代码。

汇编

汇编器将 a.s 翻译成机器语言指令，并将这些指令打包为可重定位目标文件（也就是.o 文件）。

链接

可重定位目标文件

其格式和内容如下：

----------------------
|     ELF Head       |    ELF 头，描述目标文件的基本信息
----------------------
|      .text         |    机器代码
----------------------
|      .rodata       |    只读数据
----------------------
|      .data         |    已初始化的全局变量和静态变量
----------------------
|       .bss         |    未初始化的全局变量和静态变量（实际上不占用空间，只需要运行时赋初值）
----------------------
|     .symtab        |    符号表，存储定义和引用的所有函数和全局变量
----------------------
|     .rel.text      |    代码重定位表，调用外部函数的指令需要重定位
----------------------
|     .rel.data      |    数据重定位表，引用外部全局变量和外部函数的全局变量需要重定位
----------------------
|      .debug        |
----------------------
|       .line        |
----------------------
|      .strtab       |
----------------------
|section header table|
----------------------

静态链接

• 链接器获取各个目标文件的符号表，并将之合并为一个全局符号表。
• 链接器获取各个目标文件的各个段的长度，计算出每个合并后段的长度与位置。
• 每个段的起始位置都默认是 0，加载时通过段起始地址 + 段内偏移量访问字段。

1. 符号解析
   每个可重定位目标文件中都有三类符号：
   a. 被当前模块定义且不能被其他模块引用的符号（static 函数和全局变量）
   b. 被当前模块定义且能被其他模块引用的符号（不带 static 的函数和全局变量）
   c. 被当前模块引用但在其他模块内定义的符号（其他模块定义的不带 static 的函数和全局变量）
   将每一个符号引用指向其对应的符号定义，就是符号解析，符号解析的规则如下：
   强符号是给定初值且定义的符号，弱符号是声明但未定义的符号。
   a. 只能有一个强符号。
   b. 一个强符号和多个弱符号，选择强符号为符号定义。
   c. 多个若符号，没有强符号，选择任意一个弱符号为符号定义。
2. 重定位
   上述生成的文件中，各个段的起始位置都默认是 0，链接器需要把符号定义和内存对应，这一对应的过程就是重定位。
   a. 链接器首先把各个段合并，生成聚合段作为可执行目标文件的段
   b. 计算出每个段的长度和起始位置
   c. 根据每个段的起始位置，给每个段内的代码/符号引用赋以运行时地址（也即段内偏移量）
   3.静态链接的优缺点

静态链接优缺点

缺点：浪费空间，因为每个可执行程序中对所有需要的目标文件都要有一份副本；更新困难，每次修改库函数代码，就需要重新编译链接。
优点：在可执行程序中具备了执行程序需要的任何东西，执行时运行速度快。

动态链接

动态链接的基本思想是把程序按照模块拆分成各个相对独立部分，在运行时完成链接。

假设现在有两个程序 program1.o 和 program2.o，这两者共用同一个库 lib.o，假设首先运行程序 program1，系统首先加载 program1.o，当系统发现 program1.o 中用到了 lib.o，即 program1.o 依赖于 lib.o，那么系统接着加载 lib.o，如果 program1.o 和 lib.o 还依赖于其他目标文件，则依次全部加载到内存中。当 program2 运行时，同样的加载 program2.o，然后发现 program2.o 依赖于 lib.o，但是此时 lib.o 已经存在于内存中，这个时候就不再进行重新加载，而是将内存中已经存在的 lib.o 映射到 program2 的虚拟地址空间中，从而进行链接（这个链接过程和静态链接类似）形成可执行程序。

动态链接的加载时重定位

1. 重定位.so 的文本和数据到某个内存段。
2. 重定位可执行文件中所有对.so 文件的引用。

这里涉及到一个有趣的细节，在 ics 课编码 linker 的时候，引用动态链接库中的符号会在第一次引用时多次跳转指针找到对应符号的内存段，并记录下来具体的位置，而在第二次引用时，则使用第一次记录下来的具体位置直接访问。

动态链接优缺点

优点：即使需要每个程序都依赖同一个库，也不会像静态链接那样在内存中存在多个副本，而是这多个程序在执行时共享同一份副本；更新方便，只需要替换原来的库文件，而无需将所有的程序重新链接。
缺点：链接推迟到了运行时，损失性能。

加载

通过加载器将可执行文件的代码和数据从磁盘中复制到内存中，然后 PC 跳转到程序的第一条指令或入口点。

缓存一致性与内存屏障
MESI 缓存一致性协议：

一个双核处理器如上图，memory 可以是主存，也可以是 L3 Cache（往往是 L3 Cache）
两个 Cache 指 L1/L2 Cache，简单起见假设只有一层 Cache。
考虑如下场景：
有一个变量 x=0，存在于 memory 和 CPU0 的 Cache 中

1. CPU1 read x，Cache miss，向 memory 请求得到 x 数据并存储进 Cache 中
2. CPU0 write x=1，Cache hit，直接在 CPU0 的 Cache 中修改，如果 Cache 不是写穿透策略则 memory 中 x 仍然为 0
3. CPU1 read x，Cache hit，读取 x=0，发生错误

为了防止上述情况发生，使用 MESI 协议来维护缓存一致性。
MESI 协议有四个状态，分别如下：
I: Invalidate，Cacheline 的数据是无效的。
S: Shared，Cacheline 是最新的，且至少一个其他核心的 Cache 中也存在该 Cacheline。
M: Modified，Cacheline 是最新的且和主存不一致，其他核心的 Cache 中不存在该 Cacheline 的最新副本。
E: Exclusive，Cacheline 是最新的且和主存一致，其他核心的 Cache 中不存在该 Cacheline 的最新副本。
考虑维护上述状态，根据 CPU 的各种行为形成了一个四状态自动机，进行 trans 的时候需要各个核心之间完成信息交互。

可能发生的交互消息类型：
Read: 读取 Cache miss 时，发送该消息，从其他核心的 Cache 或者主存中获取最新副本，消息内容为读取的数据地址。
Read Response: Read 的响应信号，消息内容为对应数据的最新副本。
Invalidate：收到消息的 Cache 要将对应数据的 Cacheline 无效化，消息内容为无效化的数据地址。
Invalidate Ack: Invalidate 的响应信号，在无效化相应 Cacheline 后返回 Ack。
Read Invalidate: 读取该 cacheline 的最新数据，并将核心 Cache 中的相应 cacheline 无效化。消息内容为读取和无效化的数据地址。一般在发生写 Cache miss 的时候发送此信号。需要收到 read response 和 invalidate acknowledge 信号作为响应。
Writeback: 发生在处于 M 状态的 Cacheline 被替换时，将脏数据块写回主存。消息内容为数据地址和 Cacheline 的副本。

MESI 协议很正确，但是效率并不高，不过可以增加一些简单优化，Store Buffer和Invalidate Queue

上图为 Arm 架构，x86 架构没有 Invalidate Queue
Store Buffer
当 CPU 发生写缺失时，需要发送 Read Invalidate 并等待响应，这一过程可能需要相当长的时间，而在这一时间段内，CPU 不能做其他事情，严重影响性能。使用 store buffer 解决这一问题。如下图所示，CPU 在发生写缺失时，可以发送 read invalidate 信号，同时将要写的数据存储到 store buffer 中，然后继续执行后面的指令。等到其他 CPU 或者主存返回了最新数据，同时接受到所有 CPU 的 invalidate ack 信号后，再将数据从 store buffer 中读出，写入 Cache 中。
Store Forwarding
考虑如下场景：
起初 x=0 且存在于 CPU 的 Cache 中

1. CPU 向 cache 中写入 x=1，则 CPU 会写操作存储到 store buffer 中，并发起 invalidate 操作。
2. CPU 读取 x，此时即 x=1 仍存储在 store buffer 中，没有修改成功。由于在 cacheline 中命中，得到 x=0。

Store Forwarding：当 CPU 读取数据时，首先检查 store buffer 中是否存在该数据，若存在，直接读取该数据，若不存在，再从 cache 中读取。

Store Buffer 与内存屏障

假设上述代码中删去第四行的 smp_mb()，考虑让 thread0 在 CPU0 上执行 foo 函数，thread1 在 CPU1 上执行 bar 函数。
初始时刻，a 的副本仅存储在 CPU1 的 Cache 中，b 的副本仅存储在 CPU0 的 Cache 中，则考虑如下执行顺序：

1. cpu0 执行 a=1，由于 a 不在 cpu0 的 cache 中，因此 cpu0 会发起 read invalidate 信号，同时将 a=1 存储在 store buffer 中。
2. cpu1 执行 while(b==0)，由于 b 不在 cpu1 的 cache 中，因此 cpu1 会发送 read 信号，请求 b 的最新副本。
3. cpu0 执行 b=1，由于 b 在 cpu0 的 cache 中，因此直接 hit，将 b 的值改写为 1 即可。
4. cpu0 收到来自 cpu1 的 read 信号，此时，cpu0 将 b 的新值 1 返回给 cpu1 即可。
5. cpu1 收到 b 的新值 1，cpu1 收到 b 的新值 1 后，将其更新到 cacheline 中，同时由于 b=1，因此 cpu1 跳出 while 循环。
6. cpu1 执行 assert(a==1)，发现此时 a 的值为 0，断言失败。
7. cpu1 收到 read invalidate 信号，将数据返回给 cpu0，同时无效 a 所在 cacheline。但此时已经太晚了！

smp_mb() 的作用是将 Store Buffer 中的内容被刷新到 Cache，也即阻塞至所有在该句话之前的 store 对所有 CPU 可见。

Invalidate Queues
Cache 的 Store Buffer 往往很小，当 Store Buffer 写满时，CPU 必须等待某一个 Store Buffer 中的内容被刷出，再 push 新的 store 指令进入，会导致性能大大降低。Store Buffer 内容的刷出速度取决于 Invalidate Ack 指令的回复速度。
CPU 收到 Invalidate 信号后，先不 Invalidate，而是将所有 Invalidate 信息存入 Invalidate Queue，然后提前返回 Invalidate Ack。Invalidate Queue 会异步地对 Cacheline 进行无效化。

Invalidate Queues 和内存屏障
考虑如下场景：
CPU1 和 CPU2 的 Cache 中同时持有 x=0 的最新副本，Cacheline 状态为 Shared。
考虑按照如下顺序执行指令：

1. CPU1 write x=1，发送 Invalidate 信号，将写信号放入 store buffer。
2. CPU2 收到 Invalidate 信号后返回 Invalidate Ack。
3. CPU1 的 store buffer 收到 Invalidate Ack，将 x=1 写入 Cache。
4. CPU2 read x，此时 CPU2 检测到 Cache 中对应 Cacheline 的状态为 Shared，直接读出 x=0（读取结果错误）
5. CPU2 的 Cache 将 x 所在 Cacheline 的状态改为 Invalidate，同时从 Invalidate Queue 中 pop 出该条指令，但为时已晚。

可以仍然考虑使用 smp_mb()，将 Invalidate Queue 中的内容清空，也即阻塞至所有在该句话之前的 load 对所有 CPU 可见。

关于内存屏障的思考
综上所述，其实我们可以发现，读写屏障 mb() 其实就是既清空 Store Buffer 和 Invalidate Queue，单独的写屏障 wmb() 可能是清空 Store Buffer，单独的读屏障 rmb() 还没有想清楚是怎么实现的。

指令乱序执行与内存屏障
指令乱序执行：
体系结构课上讲了很多（比如记分牌算法和 Tomasulo 算法），直接上网粘贴一段
乱序处理器（Out-of-order processors）处理指令通常有以下几步：

1. 指令获取
2. 指令被分发到指令队列
3. 指令在指令队列中等待，直到输入操作对象可用（一旦输入操作对象可用，指令就可以离开队列，即便更早的指令未被执行）
4. 指令被分配到适当的功能单元并执行
5. 执行结果被放入队列（而不立即写入寄存器堆）
6. 只有所有更早请求执行的指令的执行结果被写入寄存器堆后，指令执行的结果才被写入寄存器堆（执行结果重排序，让执行看起来是有序的）

从上面的执行过程可以看出，乱序执行相比有序执行能够避免等待不可用的操作对象（有序执行的第二步）从而提高了效率。现代的机器上，处理器运行的速度比内存快很多，有序处理器花在等待可用数据的时间里已经可以处理大量指令了。

内存屏障分为两类：

1. 编译器屏障
   用 volatile 关键字来定义变量，volatile 关键字有三重含义：

• volatile 变量之间的访问顺序不会被编译器改变
• volatile 变量每次读取时均访问内存
• volatile 变量不会被编译器进行激进优化
  举例：

//thread1
volatile bool tag = true;
volatile int x = 0;
while(tag);
work(x)

//thread2
x = 10;
tag = false;

这里 thread1 进入死循环，thread2 将 x 变为 10 写回内存，再 tag 变为 false 后写回内存，thread1 从内存中取到 tag，循环停止，调用 work(10)。
假设不使用 volatile 变量，编译优化可能出现内存乱序执行，例如 thread2 中 x=10 后于 tag=false 执行，就有可能导致 thread1 执行 work(0)。

1. CPU 屏障
   保证读写操作有序的，mb() 和 smp_mb()
   仅保证写操作有序的，wmb() 和 smp_wmb()
   仅保证读操作有序的，rmb() 和 smp_rmb()
   在多核处理机上实现使用的内存屏障，此时仅使用编译器屏障不够，具体涉及到缓存一致性，先按下不表。