{"topic":{"id":13232,"title":"计算机求职八股文","slug":"topic","categoryId":54,"createdAt":"2024-08-07 08:15:52.018327","bumpedAt":"2024-09-19 10:34:19.623121","views":1122,"postsCount":26,"highestPostNumber":26,"likeCount":29,"closed":false,"pinned":false,"pinnedGlobally":false,"pinnedAt":null,"pinnedUntil":null,"isBanner":false,"excerpt":"秋招了，写点计算机八股笔记，方便自己背诵和复习欢迎门友补充、提问，或者在楼中写下自己认为的重要八股知识","deletedAt":null,"isAnonymous":false,"category":{"id":54,"name":"学术专区","slug":"academic","color":"9EB83B"},"author":{"id":199,"username":"Lrefrain","name":null,"avatarUrl":"/uploads/image/97/69/9769ddd94c97978cf278e3b4b997ba4b7cfb26abaa7f18aa567820370b7a8a5b.avif"},"tags":[]},"posts":[{"id":38448,"postNumber":1,"raw":"秋招了，写点计算机八股笔记，方便自己背诵和复习\n欢迎门友补充、提问，或者在楼中写下自己认为的重要八股知识","cooked":"

秋招了，写点计算机八股笔记，方便自己背诵和复习
\n欢迎门友补充、提问，或者在楼中写下自己认为的重要八股知识

\n","createdAt":"2024-08-07 08:15:52.259163","updatedAt":"2024-08-07 10:03:54.289465","replyToPostNumber":null,"replyCount":0,"likeCount":9,"wordCount":51,"liked":false,"bookmarked":false,"polls":[],"reactions":[{"reaction":"❤️","count":8,"users":[{"id":166,"username":"Coryc1e","name":null},{"id":212,"username":"the42thnut","name":null},{"id":1381,"username":"greyishsong","name":"greyishsong"},{"id":1929,"username":"Quit","name":"Qwen"},{"id":2850,"username":"lyinx","name":"lyinx"},{"id":4263,"username":"Murphy","name":null},{"id":4668,"username":"IO","name":null},{"id":6205,"username":"uika_winwing","name":null}],"hasReacted":false}],"wiki":false,"version":2,"publicVersion":2,"deletedAt":null,"isAnonymous":false,"user":{"id":199,"username":"Lrefrain","name":null,"avatarUrl":"/uploads/image/97/69/9769ddd94c97978cf278e3b4b997ba4b7cfb26abaa7f18aa567820370b7a8a5b.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":38452,"postNumber":2,"raw":"**浅拷贝，深拷贝，std::move**\n1. 浅拷贝：按字节直接复制，可以解决很多场景的问题，但是当被拷贝的对象中含有指针或文件描述符时，会出现以下两方面的错误：\n- 使用的时候，被拷贝对象和拷贝对象的指针指向同一个地址，一方的改动会影响另一方的使用，这往往是不符合需要实现的逻辑的。\n- 析构的时候，被拷贝对象和拷贝对象的指针均被析构，则会对同一个地址析构两次，UB。\n2. 深拷贝：用来解决上述浅拷贝会出现的错误，深拷贝需要手动实现（赋值运算符/构造函数），假设被拷贝对象中有一个指针，则申请一段新的内存，复制被拷贝对象指针指向的内容到这段新的内存上。这样被拷贝对象和拷贝对象将会互不干扰。\n3. std::move：将左值转换为右值，其意义大概类似于\n```\ntemplate\nT && move(T lvalue) {\n return static_cast(lvalue);\n}\n```\n原始代码中略有更改，涉及到一些模板语法糖，不再赘述。使用 a = std::move(b);可以实现移动语义，也即对象所有权的转移，移动后 b 的值回到初始化状态（往往由移动构造/赋值函数来决定具体如何初始化，可见下例），不能再继续使用，但是可以被析构。\n使用如下代码来实现移动构造函数和移动赋值函数\n```\nclass A{\npublic:\n A() : data(nullptr) {\n }\n\n A(int value) : data(new int(value)) {\n }\n\n A(A&& other): data(other.data) {\n other.data = nullptr;\n }\n\n A& operator=(A&& other) {\n if (this != &other) {\n delete data;\n data = other.data;\n other.data = nullptr;\n }\n return *this;\n }\n\n ~A() {\n delete data;\n }\n\nprivate:\n int *data;\n};\n```","cooked":"

浅拷贝，深拷贝，std::move

浅拷贝：按字节直接复制，可以解决很多场景的问题，但是当被拷贝的对象中含有指针或文件描述符时，会出现以下两方面的错误：

使用的时候，被拷贝对象和拷贝对象的指针指向同一个地址，一方的改动会影响另一方的使用，这往往是不符合需要实现的逻辑的。
析构的时候，被拷贝对象和拷贝对象的指针均被析构，则会对同一个地址析构两次，UB。

深拷贝：用来解决上述浅拷贝会出现的错误，深拷贝需要手动实现（赋值运算符/构造函数），假设被拷贝对象中有一个指针，则申请一段新的内存，复制被拷贝对象指针指向的内容到这段新的内存上。这样被拷贝对象和拷贝对象将会互不干扰。
std::move：将左值转换为右值，其意义大概类似于

template<typename T>\nT && move(T lvalue) {\n    return static_cast<T &&>(lvalue);\n}\n

原始代码中略有更改，涉及到一些模板语法糖，不再赘述。使用 a = std::move(b);可以实现移动语义，也即对象所有权的转移，移动后 b 的值回到初始化状态（往往由移动构造/赋值函数来决定具体如何初始化，可见下例），不能再继续使用，但是可以被析构。
\n使用如下代码来实现移动构造函数和移动赋值函数

class A{\npublic:\n    A() : data(nullptr) {\n    }\n\n    A(int value) : data(new int(value)) {\n    }\n\n    A(A&& other): data(other.data) {\n        other.data = nullptr;\n    }\n\n    A& operator=(A&& other) {\n        if (this != &other) {\n            delete data;\n            data = other.data;\n            other.data = nullptr;\n        }\n        return *this;\n    }\n\n    ~A() {\n        delete data;\n    }\n\nprivate:\n    int *data;\n};\n

\n","createdAt":"2024-08-07 08:49:00.95905","updatedAt":"2024-08-07 08:49:00.95905","replyToPostNumber":null,"replyCount":0,"likeCount":2,"wordCount":491,"liked":false,"bookmarked":false,"polls":[],"reactions":[{"reaction":"❤️","count":2,"users":[{"id":151,"username":"Rin","name":"Tomotake Rin"},{"id":4668,"username":"IO","name":null}],"hasReacted":false}],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":199,"username":"Lrefrain","name":null,"avatarUrl":"/uploads/image/97/69/9769ddd94c97978cf278e3b4b997ba4b7cfb26abaa7f18aa567820370b7a8a5b.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":38455,"postNumber":3,"raw":"**lambda 表达式**\n使用方法：\n```\nint x= 10;\nauto f = [x](int c = 5) {return x + c;};\nstd::cout << f() << std::endl;\n```\n中括号内参数为捕获列表，可有如下几种填入方式：\n![image|690x265](/uploads/image/ae/85/ae85a0f1223eb521c20464d93b720e0728fd639abbbae69fa976690a85d4ccb8.avif)\n小括号内为形参列表，使用方式类似函数\n\n如需更改 x 的值，则需要加上 mutable 关键字，如下：\n```\nint x= 10;\nauto f = [&x](int c = 5) mutable {x=c;};\nf();\nstd::cout << x << std::endl;\n```","cooked":"

lambda 表达式
\n使用方法：

int x= 10;\nauto f = [x](int c = 5) {return x + c;};\nstd::cout << f() << std::endl;\n

中括号内参数为捕获列表，可有如下几种填入方式：
\n $\"image\"$
\n小括号内为形参列表，使用方式类似函数

如需更改 x 的值，则需要加上 mutable 关键字，如下：

int x= 10;\nauto f = [&x](int c = 5) mutable {x=c;};\nf();\nstd::cout << x << std::endl;\n

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

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

动态链接优缺点

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

加载

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

\n","createdAt":"2024-08-08 09:47:49.324662","updatedAt":"2024-08-13 08:28:40.457944","replyToPostNumber":null,"replyCount":0,"likeCount":2,"wordCount":1733,"liked":false,"bookmarked":false,"polls":[],"reactions":[{"reaction":"❤️","count":2,"users":[{"id":4263,"username":"Murphy","name":null},{"id":4668,"username":"IO","name":null}],"hasReacted":false}],"wiki":false,"version":3,"publicVersion":3,"deletedAt":null,"isAnonymous":false,"user":{"id":199,"username":"Lrefrain","name":null,"avatarUrl":"/uploads/image/97/69/9769ddd94c97978cf278e3b4b997ba4b7cfb26abaa7f18aa567820370b7a8a5b.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":38594,"postNumber":8,"raw":"

\n# 原子操作和 C++ 内存序\n\n## 原子操作和原子类型\n### std::atomic\n在 atomic 库中定义了原子类型 std::atomic<>，例如可以使用 std::atomic。\nstd::atomic<>可以通过函数实现各类原子操作，例如 std::atomic<>::load()，std::atomic<>::store()，std::atomic<>::fetch_and()，std:;atomic<>::fetch_add 等等。\n### CAS 操作\n通过 atomic<>::compare_exchange_weak/strong(x, y) 函数实现。表示如果原子量的值等于 x，则令原子量的值变为 y，且返回 true，否则将 x 的值变为原子量的值且返回 false。\nweak 性能更好，但是可能在可以返回 true 的时候返回 false。\nstrong 性能更差，但是在可以返回 true 的时候一定会返回 true。\n\n## C++ 内存序\n1. seq_cst 要求所有原子操作必须按照在程序中出现的顺序执行，最严格的内存序\n2. acquire 确保之前的所有使用 release 的写操作都对当前线程可见，该语句后的所有语句不能先于当前语句执行完成前执行。\n3. release 确保该语句前的所有写语句都已经执行完毕，并且对其他线程可见。\n4. acq_rel 确保该语句后的读语句执行前，该语句前的所有写语句执行完毕且对其他线程可见；确保该语句后的写语句执行前，该语句前的所有读语句执行完毕。\n5. relaxed 不对顺序做限制，最弱的内存序。\n6. consume","cooked":"

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

原子操作和原子类型

std::atomic

在 atomic 库中定义了原子类型 std::atomic<>，例如可以使用 std::atomic。
\nstd::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。
\nweak 性能更好，但是可能在可以返回 true 的时候返回 false。
\nstrong 性能更差，但是在可以返回 true 的时候一定会返回 true。

C++ 内存序

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

\n","createdAt":"2024-08-11 10:53:56.468703","updatedAt":"2024-09-19 13:16:54.748941","replyToPostNumber":null,"replyCount":0,"likeCount":1,"wordCount":374,"liked":false,"bookmarked":false,"polls":[],"reactions":[{"reaction":"❤️","count":1,"users":[{"id":4668,"username":"IO","name":null}],"hasReacted":false}],"wiki":false,"version":2,"publicVersion":2,"deletedAt":null,"isAnonymous":false,"user":{"id":199,"username":"Lrefrain","name":null,"avatarUrl":"/uploads/image/97/69/9769ddd94c97978cf278e3b4b997ba4b7cfb26abaa7f18aa567820370b7a8a5b.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":38595,"postNumber":9,"raw":"## 用户态和内核态\n引用一下之前的帖子：\n\n[quote=\"Lrefrain, post:39, topic:11497\"]\nDual Mode\n考虑为什么进程 A 的页表指针不能指向进程 B？\n因为这会破坏进程间的数据隔离。\n那我们该如何在必要时使用这种操作呢？这就要求硬件至少提供两种模式：内核模式和用户模式。\n下一个问题是该如何控制两种模式间的过渡和切换？\n\n[grid mode=\"tile\"]\n![image](/uploads/image/79/f6/79f6c9fbe7c8a2758e7ba054a89d45b8922d8ef231fa30ad0282dd0af6060f18.avif)\n\n![image](/uploads/image/90/11/9011bbfa1f1225fbfc737af6e56e7b08d3e4b8993c692569bc282d221f46d7f2.avif)\n[/grid]\n\n简单来说，如上图：调用系统调用 syscall，系统调用会支配硬件完成某些工作，然后结束 syscall 返回用户模式。\n注意到至少提供两种模式，后续在 Docker 中我们将了解到更多的权限介于二者之间的模式。\n[/quote]\n\n[quote=\"Lrefrain, post:40, topic:11497\"]\n一个例子\n\n![image](/uploads/image/73/97/7397d4d783f2c19a1a76cace15d8630c8b58cfc38ac45a0a7ed7a60eda7a51cb.avif)\n\n最开始处于内核模式，可以注意到其 Base 和 Bound 均失效（意味着可以访问 [0000…, FFFF…] 的所有地址空间），uPC 指向黄色进程的可执行代码，意味着目前想要加载进入黄色进程。\n\n![image](/uploads/image/62/b9/62b9fafc3259a403dcf2f1b4ac8b9dd355d5d09608c1fbf6a023fa8b16b8ee00.avif)\n\n我们将 PC 换为之前的 uPC，sysmode 改为 0 之后，Base 和 Bound 就激活了且等于黄色的地址区域边界，这意味着我们进入了黄色进程，同时进入了用户模式。\n\n![image](/uploads/image/8c/42/8c4278706a4ca86bb5f38a22688d98550e4e990b73a992d99bf08eb04f03282f.avif)\n\n假设一段时间后发生了计时器中断，下一条执行的指令将会是计时器中断处理程序（存在于内核代码区），中断发生后我们又一次进入了内核态。\n\n![image](/uploads/image/e3/a8/e3a840d3d0a09f77c667e22f9f20fa9b0703fa18f830cca6cfba9aff050d4169.avif)\n\n由于要发生进程切换，因此计时器中断处理程序将会保存黄色进程 PCB 并放入内核区（灰色）的 Static Data 中的黄色小方块。\n同时我们加载切换到绿色所需的寄存器信息。\n\n![image](/uploads/image/55/f2/55f2cf47b8acd9eed2b712565974d09e1e271d5c893defc1add7863a36b49279.avif)\n\n更改 sysmode 后成功以用户模式运行绿色进程。\n[/quote]","cooked":"

用户态和内核态

引用一下之前的帖子：

\n\t\t\t\t\t\t\t

\n\t\t\t\t\t\t\t\t

\n\t\t\t\t\t\t\t\t\t

\n\t\t\t\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\t\t

\n\t\t\t\t\t\t\t\t\tLrefrain:\n\t\t\t\t\t\t\t\t

\n\t\t\t\t\t\t\t\t

\n\t\t\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\t

\n\t\t\t\t\t\t\t

\n
Dual Mode
\n考虑为什么进程 A 的页表指针不能指向进程 B？
\n因为这会破坏进程间的数据隔离。
\n那我们该如何在必要时使用这种操作呢？这就要求硬件至少提供两种模式：内核模式和用户模式。
\n下一个问题是该如何控制两种模式间的过渡和切换？
\n
\n
$\"image\"$
\n
$\"image\"$
\n
\n
简单来说，如上图：调用系统调用 syscall，系统调用会支配硬件完成某些工作，然后结束 syscall 返回用户模式。
\n注意到至少提供两种模式，后续在 Docker 中我们将了解到更多的权限介于二者之间的模式。
\n

\n\t\t\t\t\t\t

\n\t\t\t\t\t\t\t

\n\t\t\t\t\t\t\t\t

\n\t\t\t\t\t\t\t\t\t

\n\t\t\t\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\t\t

\n\t\t\t\t\t\t\t\t\tLrefrain:\n\t\t\t\t\t\t\t\t

\n\t\t\t\t\t\t\t\t

\n\t\t\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\t

\n\t\t\t\t\t\t\t

\n
一个例子
\n
$\"image\"$
\n
最开始处于内核模式，可以注意到其 Base 和 Bound 均失效（意味着可以访问 [0000…, FFFF…] 的所有地址空间），uPC 指向黄色进程的可执行代码，意味着目前想要加载进入黄色进程。
\n
$\"image\"$
\n
我们将 PC 换为之前的 uPC，sysmode 改为 0 之后，Base 和 Bound 就激活了且等于黄色的地址区域边界，这意味着我们进入了黄色进程，同时进入了用户模式。
\n
$\"image\"$
\n
假设一段时间后发生了计时器中断，下一条执行的指令将会是计时器中断处理程序（存在于内核代码区），中断发生后我们又一次进入了内核态。
\n
$\"image\"$
\n
由于要发生进程切换，因此计时器中断处理程序将会保存黄色进程 PCB 并放入内核区（灰色）的 Static Data 中的黄色小方块。
\n同时我们加载切换到绿色所需的寄存器信息。
\n
$\"image\"$
\n
更改 sysmode 后成功以用户模式运行绿色进程。
\n

\n\t\t\t\t\t\t

\n","createdAt":"2024-08-11 11:00:26.692134","updatedAt":"2024-08-11 11:00:26.692134","replyToPostNumber":null,"replyCount":0,"likeCount":1,"wordCount":505,"liked":false,"bookmarked":false,"polls":[],"reactions":[{"reaction":"❤️","count":1,"users":[{"id":4668,"username":"IO","name":null}],"hasReacted":false}],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":199,"username":"Lrefrain","name":null,"avatarUrl":"/uploads/image/97/69/9769ddd94c97978cf278e3b4b997ba4b7cfb26abaa7f18aa567820370b7a8a5b.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":38598,"postNumber":10,"raw":"

\n# 并行编程及其应用\n\n## pthread(POXIS thread)\n\n[quote=\"Lrefrain, post:59, topic:11497\"]\npthread(POSIX Thread)\npthread_create，创建线程\npthread_exit，退出线程\npthread_join，等待某个线程结束\npthread_mutex_init，创建互斥锁\npthread_mutex_destroy，创建互斥锁\npthread_mutex_lock，阻塞式地获取互斥锁\npthread_mutex_unlock，释放互斥锁\npthread_spin_init，创建自旋锁\npthread_spin_destroy，创建自旋锁\npthread_spin_lock，阻塞式地获取自旋锁\npthread_spin_unlock，释放自旋锁\n[/quote]\n\n## 互斥锁和自旋锁\nMutex 想要使用 lock 去获得一个锁的时候，如果此时这个锁正被其他线程持有，那么使用 lock 的线程就会被阻塞，进行上下文切换，将线程放置到等待队列中。此时 CPU 可以被安排去做其他事情，等待锁的所有权空出来后再再次执行该线程。\nSpin 想要使用 lock 获得一个锁的时候，如果此时无法获取到锁，会一直忙等待，直到获取该锁为止。\n具体来说，一般获取锁的等待时间较长的时候使用 Mutex，获取锁的等待时间较短的时候使用 Spin。\n\n## 条件变量\nstd::condition_variable\n使用函数：\n1. pthread_cond_init/destroy 类似于互斥锁和自旋锁\n2. pthread_cond_wait\n函数定义：\nint pthread_cond_wait(pthread_cond_t *restrict cond, pthread_mutex_t *restrict mutex)\ncond：指向条件变量的指针。\nmutex：指向互斥锁的指针。\n调用该函数之前，必须先获得互斥锁 mutex，在等待期间，互斥锁会自动释放，并使当前线程处于阻塞状态，直到条件变量被唤醒并且重新获得互斥锁为止。\n\n3. pthread_cond_signal/broadcast\n用于唤醒等待条件变量的一个线程。signal 如果有多个线程在等待条件变量，则会唤醒其中一个线程；broadcast 则是唤醒所有等待的线程。\n如果没有线程在等待条件变量，则该函数不会产生任何效果。\n\n## 阻塞式循环队列\n上网抄个代码：\n```\n #include \n #include \n #include \n #include \n #include \n #include \n \n static const int kItemRepositorySize = 10; // Item buffer size.\n static const int kItemsToProduce = 1000; // How many items we plan to produce.\n \n struct ItemRepository {\n int item_buffer[kItemRepositorySize]; // 产品缓冲区，配合 read_position 和 write_position 模型环形队列.\n size_t read_position; // 消费者读取产品位置.\n size_t write_position; // 生产者写入产品位置.\n std::mutex mtx; // 互斥量，保护产品缓冲区\n std::condition_variable repo_not_full; // 条件变量，指示产品缓冲区不为满.\n std::condition_variable repo_not_empty; // 条件变量，指示产品缓冲区不为空.\n } gItemRepository; // 产品库全局变量，生产者和消费者操作该变量.\n \n typedef struct ItemRepository ItemRepository;\n \n \n void ProduceItem(ItemRepository *ir, int item)\n {\n std::unique_lock lock(ir->mtx);\n while(((ir->write_position + 1) % kItemRepositorySize)\n == ir->read_position) { // item buffer is full, just wait here.\n std::cout << \"Producer is waiting for an empty slot...\\n\";\n (ir->repo_not_full).wait(lock); // 生产者等待\"产品库缓冲区不为满\"这一条件发生.\n }\n \n (ir->item_buffer)[ir->write_position] = item; // 写入产品.\n (ir->write_position)++; // 写入位置后移.\n \n if (ir->write_position == kItemRepositorySize) // 写入位置若是在队列最后则重新设置为初始位置.\n ir->write_position = 0;\n \n (ir->repo_not_empty).notify_all(); // 通知消费者产品库不为空.\n lock.unlock(); // 解锁.\n }\n \n int ConsumeItem(ItemRepository *ir)\n {\n int data;\n std::unique_lock lock(ir->mtx);\n // item buffer is empty, just wait here.\n while(ir->write_position == ir->read_position) {\n std::cout << \"Consumer is waiting for items...\\n\";\n (ir->repo_not_empty).wait(lock); // 消费者等待\"产品库缓冲区不为空\"这一条件发生.\n }\n \n data = (ir->item_buffer)[ir->read_position]; // 读取某一产品\n (ir->read_position)++; // 读取位置后移\n \n if (ir->read_position >= kItemRepositorySize) // 读取位置若移到最后，则重新置位.\n ir->read_position = 0;\n \n (ir->repo_not_full).notify_all(); // 通知消费者产品库不为满.\n lock.unlock(); // 解锁.\n \n return data; // 返回产品.\n }\n \n \n void ProducerTask() // 生产者任务\n {\n for (int i = 1; i <= kItemsToProduce; ++i) {\n // sleep(1);\n std::cout << \"Produce the \" << i << \"^th item...\" << std::endl;\n ProduceItem(&gItemRepository, i); // 循环生产 kItemsToProduce 个产品.\n }\n }\n \n void ConsumerTask() // 消费者任务\n {\n static int cnt = 0;\n while(1) {\n sleep(1);\n int item = ConsumeItem(&gItemRepository); // 消费一个产品.\n std::cout << \"Consume the \" << item << \"^th item\" << std::endl;\n if (++cnt == kItemsToProduce) break; // 如果产品消费个数为 kItemsToProduce, 则退出.\n }\n }\n \n void InitItemRepository(ItemRepository *ir)\n {\n ir->write_position = 0; // 初始化产品写入位置.\n ir->read_position = 0; // 初始化产品读取位置.\n }\n \n int main()\n {\n InitItemRepository(&gItemRepository);\n std::thread producer(ProducerTask); // 创建生产者线程.\n std::thread consumer(ConsumerTask); // 创建消费之线程.\n producer.join();\n consumer.join();\n }\n```\n上述代码是单生产者和单消费者模型，多生产者多消费者模型只需要增加两个计数器用来计算当前已经生产/消费了多少个物品。\n\n## 无锁循环队列\n内核实现了一个无锁循环队列 kfifo\n粘贴一下代码：\n```\n/**\n * __kfifo_put - puts some data into the FIFO, no locking version\n * @fifo: the fifo to be used.\n * @buffer: the data to be added.\n * @len: the length of the data to be added.\n *\n * This function copies at most @len bytes from the @buffer into\n * the FIFO depending on the free space, and returns the number of\n * bytes copied.\n *\n * Note that with only one concurrent reader and one concurrent\n * writer, you don't need extra locking to use these functions.\n */\nunsigned int __kfifo_put(struct kfifo *fifo,\n\t\t\t unsigned char *buffer, unsigned int len)\n{\n\tunsigned int l;\n\n //计算写入空间：队列大小 - 写入位置 + 读取位置\n\tlen = min(len, fifo->size - fifo->in + fifo->out);\n\n\t/*\n\t * Ensure that we sample the fifo->out index -before- we\n\t * start putting bytes into the kfifo.\n\t *\n\t * 内存屏障（全屏障）\n\t */\n\n\tsmp_mb();\n\n\t/* first put the data starting from fifo->in to buffer end */\n /* 从队列写入位置 (mod 队列大小) 写入到队列结尾处 */\n\tl = min(len, fifo->size - (fifo->in & (fifo->size - 1)));\n\tmemcpy(fifo->buffer + (fifo->in & (fifo->size - 1)), buffer, l);\n\n\t/* then put the rest (if any) at the beginning of the buffer */\n /* 从队列起始位置向后写入剩余数据 */\n\tmemcpy(fifo->buffer, buffer + l, len - l);\n\n\t/*\n\t * Ensure that we add the bytes to the kfifo -before-\n\t * we update the fifo->in index.\n\t *\n\t * 内存屏障（写屏障）\n\t */\n\n\tsmp_wmb();\n\n //单调递增写入位置\n\tfifo->in += len;\n\n\treturn len;\n}\n\n/**\n * __kfifo_get - gets some data from the FIFO, no locking version\n * @fifo: the fifo to be used.\n * @buffer: where the data must be copied.\n * @len: the size of the destination buffer.\n *\n * This function copies at most @len bytes from the FIFO into the\n * @buffer and returns the number of copied bytes.\n *\n * Note that with only one concurrent reader and one concurrent\n * writer, you don't need extra locking to use these functions.\n */\nunsigned int __kfifo_get(struct kfifo *fifo,\n\t\t\t unsigned char *buffer, unsigned int len)\n{\n\tunsigned int l;\n\n //计算读取空间：写入位置 - 读取位置\n\tlen = min(len, fifo->in - fifo->out);\n\n\t/*\n\t * Ensure that we sample the fifo->in index -before- we\n\t * start removing bytes from the kfifo.\n\t *\n\t * 内存屏障（读屏障）\n\t */\n\n\tsmp_rmb();\n\n\t/* first get the data from fifo->out until the end of the buffer */\n /* 从缓存读取位置 (mod 队列大小) 读取到缓存结尾处 */\n\tl = min(len, fifo->size - (fifo->out & (fifo->size - 1)));\n\tmemcpy(buffer, fifo->buffer + (fifo->out & (fifo->size - 1)), l);\n\n\t/* then get the rest (if any) from the beginning of the buffer */\n /* 从缓存起始位置读取剩余数据 */\n\tmemcpy(buffer + l, fifo->buffer, len - l);\n\n\t/*\n\t * Ensure that we remove the bytes from the kfifo -before-\n\t * we update the fifo->out index.\n\t *\n\t * 内存屏障（全屏障）\n\t */\n\n\tsmp_mb();\n\n //单调递增读取位置\n\tfifo->out += len;\n\n\treturn len;\n}\n```\n\n## shared_ptr\n* `shared_ptr` 本身不是一个线程安全的 STL，因此并发读写对应内存区域是不安全的。\n* 由于赋值操作涉及原内存释放、修改指针指向等多个修改操作，其过程不是原子操作，因此对 `shared_ptr` 进行并发赋值不是线程安全的。\n* 对 `shared_ptr` 进行并发拷贝，对数据指针和控制块指针仅进行读取并复制，然后对引用计数进行递增，而引用计数增加是原子操作。因此是线程安全的。\n```\n#include\n#include\n \nusing namespace std;\n \nclass Counter\n{\npublic:\n\tCounter()\n\t{\n\t\tcount = 1;\t\n\t}\n\t\n\tvoid add()\n\t{\n\t\tcount++;\n\t}\n\t\n\tvoid sub()\n\t{\n\t\tcount--;\n\t}\n\t\n\tint get() const\n\t{\n\t\treturn count;\n\t}\n\t\nprivate:\n\tstd::atomic count;\n};\n \ntemplate \nclass Sp\n{\npublic:\n\tSp(); //默认构造函数\n\tSp(T *ptr); //参数构造函数\n\tSp(const Sp &obj); //复制构造函数\n\t~Sp(); //析构函数\n\tSp &operator=(const Sp &obj); //重载=\n\tT *get(); //得到共享指针指向的类\n\t \n\tint getcount(); //得到引用计数器\nprivate:\n\tT *my_ptr; //共享指针所指向的对象\n\tCounter* counter; //引用计数器\n\tvoid clear(); //清理函数\n};\n \n//默认构造函数，参数为空，构造一个引用计数器\ntemplate\nSp::Sp()\n{\n\tmy_ptr = nullptr;\n\tcounter = new Counter();\n\tcounter->add();\n}\n \n//复制构造函数，新的共享指针指向旧的共享指针所指对象\ntemplate\nSp::Sp(const Sp &obj)\n{\n //将所指对象也变为目标所指的对象\n\tmy_ptr = obj.my_ptr;\n //获取引用计数器，使得两个共享指针用一个引用计数器\n\tcounter = obj.counter;\n //使这个对象的引用计数器 +1\n\tcounter->add();\t\n};\n \n//重载=\ntemplate\nSp &Sp::operator=(const Sp&obj)\n{\n //清理当前所引用对象和引用计数器\n\tclear();\n //指向新的对象，并获取目标对象的引用计数器\n\tmy_ptr = obj.my_ptr;\n\tcounter = obj.counter;\n //引用计数器 +1\n\tcounter->add();\n //返回自己\n\treturn *this;\t\n}\n \n//创建一个共享指针指向目标类，构造一个新的引用计数器\ntemplate\nSp::Sp(T *ptr)\n{\n\tmy_ptr = ptr;\n\tcounter = new Counter();\n}\n \n//析构函数，出作用域的时候，调用清理函数\ntemplate\nSp:: ~Sp()\n{\n\tclear();\n}\n \n//清理函数，调用时将引用计数器的值减 1，若减为 0，清理指向的对象内存区域\ntemplate\nvoid Sp::clear()\n{\n //引用计数器 -1 \n\tcounter->sub();\n //如果引用计数器变为 0，清理对象\n\tif(0 == counter->get())\n\t{\n\t\tif(my_ptr)\n\t\t{\n\t\t\tdelete my_ptr;\n\t\t}\n\t\tdelete counter;\n\t}\n}\n \n//当前共享指针指向的对象，被几个共享指针所引用\ntemplate\nint Sp::getcount()\n{\n\treturn counter->get();\t\n}\n\ntemplate\nT * sp::get()\n{\n return my_ptr;\n}\n```","cooked":"

\n# 并行编程及其应用\n

pthread(POXIS thread)

\n\t\t\t\t\t\t\t

\n\t\t\t\t\t\t\t\t

\n\t\t\t\t\t\t\t\t\t

\n\t\t\t\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\t\t

\n\t\t\t\t\t\t\t\t\tLrefrain:\n\t\t\t\t\t\t\t\t

\n\t\t\t\t\t\t\t\t

\n\t\t\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\t

\n\t\t\t\t\t\t\t

\n
pthread(POSIX Thread)
\npthread_create，创建线程
\npthread_exit，退出线程
\npthread_join，等待某个线程结束
\npthread_mutex_init，创建互斥锁
\npthread_mutex_destroy，创建互斥锁
\npthread_mutex_lock，阻塞式地获取互斥锁
\npthread_mutex_unlock，释放互斥锁
\npthread_spin_init，创建自旋锁
\npthread_spin_destroy，创建自旋锁
\npthread_spin_lock，阻塞式地获取自旋锁
\npthread_spin_unlock，释放自旋锁
\n

\n\t\t\t\t\t\t

互斥锁和自旋锁

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

条件变量

std::condition_variable
\n使用函数：

\n
pthread_cond_init/destroy 类似于互斥锁和自旋锁
\n
\n
pthread_cond_wait
\n函数定义：
\nint pthread_cond_wait(pthread_cond_t *restrict cond, pthread_mutex_t *restrict mutex)
\ncond：指向条件变量的指针。
\nmutex：指向互斥锁的指针。
\n调用该函数之前，必须先获得互斥锁 mutex，在等待期间，互斥锁会自动释放，并使当前线程处于阻塞状态，直到条件变量被唤醒并且重新获得互斥锁为止。
\n
\n
pthread_cond_signal/broadcast
\n用于唤醒等待条件变量的一个线程。signal 如果有多个线程在等待条件变量，则会唤醒其中一个线程；broadcast 则是唤醒所有等待的线程。
\n如果没有线程在等待条件变量，则该函数不会产生任何效果。
\n

阻塞式循环队列

上网抄个代码：

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

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

无锁循环队列

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

/**\n * __kfifo_put - puts some data into the FIFO, no locking version\n * @fifo: the fifo to be used.\n * @buffer: the data to be added.\n * @len: the length of the data to be added.\n *\n * This function copies at most @len bytes from the @buffer into\n * the FIFO depending on the free space, and returns the number of\n * bytes copied.\n *\n * Note that with only one concurrent reader and one concurrent\n * writer, you don't need extra locking to use these functions.\n */\nunsigned int __kfifo_put(struct kfifo *fifo,\n\t\t\t unsigned char *buffer, unsigned int len)\n{\n\tunsigned int l;\n\n    //计算写入空间：队列大小 - 写入位置 + 读取位置\n\tlen = min(len, fifo->size - fifo->in + fifo->out);\n\n\t/*\n\t * Ensure that we sample the fifo->out index -before- we\n\t * start putting bytes into the kfifo.\n\t *\n\t * 内存屏障（全屏障）\n\t */\n\n\tsmp_mb();\n\n\t/* first put the data starting from fifo->in to buffer end */\n    /* 从队列写入位置 (mod 队列大小) 写入到队列结尾处 */\n\tl = min(len, fifo->size - (fifo->in & (fifo->size - 1)));\n\tmemcpy(fifo->buffer + (fifo->in & (fifo->size - 1)), buffer, l);\n\n\t/* then put the rest (if any) at the beginning of the buffer */\n    /* 从队列起始位置向后写入剩余数据 */\n\tmemcpy(fifo->buffer, buffer + l, len - l);\n\n\t/*\n\t * Ensure that we add the bytes to the kfifo -before-\n\t * we update the fifo->in index.\n\t *\n\t * 内存屏障（写屏障）\n\t */\n\n\tsmp_wmb();\n\n    //单调递增写入位置\n\tfifo->in += len;\n\n\treturn len;\n}\n\n/**\n * __kfifo_get - gets some data from the FIFO, no locking version\n * @fifo: the fifo to be used.\n * @buffer: where the data must be copied.\n * @len: the size of the destination buffer.\n *\n * This function copies at most @len bytes from the FIFO into the\n * @buffer and returns the number of copied bytes.\n *\n * Note that with only one concurrent reader and one concurrent\n * writer, you don't need extra locking to use these functions.\n */\nunsigned int __kfifo_get(struct kfifo *fifo,\n\t\t\t unsigned char *buffer, unsigned int len)\n{\n\tunsigned int l;\n\n    //计算读取空间：写入位置 - 读取位置\n\tlen = min(len, fifo->in - fifo->out);\n\n\t/*\n\t * Ensure that we sample the fifo->in index -before- we\n\t * start removing bytes from the kfifo.\n\t *\n\t * 内存屏障（读屏障）\n\t */\n\n\tsmp_rmb();\n\n\t/* first get the data from fifo->out until the end of the buffer */\n    /* 从缓存读取位置 (mod 队列大小) 读取到缓存结尾处 */\n\tl = min(len, fifo->size - (fifo->out & (fifo->size - 1)));\n\tmemcpy(buffer, fifo->buffer + (fifo->out & (fifo->size - 1)), l);\n\n\t/* then get the rest (if any) from the beginning of the buffer */\n    /* 从缓存起始位置读取剩余数据 */\n\tmemcpy(buffer + l, fifo->buffer, len - l);\n\n\t/*\n\t * Ensure that we remove the bytes from the kfifo -before-\n\t * we update the fifo->out index.\n\t *\n\t * 内存屏障（全屏障）\n\t */\n\n\tsmp_mb();\n\n    //单调递增读取位置\n\tfifo->out += len;\n\n\treturn len;\n}\n

shared_ptr

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

#include<iostream>\n#include<atomic>\n \nusing namespace std;\n \nclass Counter\n{\npublic:\n\tCounter()\n\t{\n\t\tcount = 1;\t\n\t}\n\t\n\tvoid add()\n\t{\n\t\tcount++;\n\t}\n\t\n\tvoid sub()\n\t{\n\t\tcount--;\n\t}\n\t\n\tint get() const\n\t{\n\t\treturn count;\n\t}\n\t\nprivate:\n\tstd::atomic<int> count;\n};\n \ntemplate <typename T>\nclass Sp\n{\npublic:\n\tSp();                           //默认构造函数\n\tSp(T *ptr);                     //参数构造函数\n\tSp(const Sp &obj);              //复制构造函数\n\t~Sp();                          //析构函数\n\tSp &operator=(const Sp &obj);   //重载=\n\tT *get();                       //得到共享指针指向的类\n\t   \n\tint getcount();                 //得到引用计数器\nprivate:\n\tT *my_ptr;                      //共享指针所指向的对象\n\tCounter* counter;                   //引用计数器\n\tvoid clear();                   //清理函数\n};\n \n//默认构造函数，参数为空，构造一个引用计数器\ntemplate<typename T>\nSp<T>::Sp()\n{\n\tmy_ptr = nullptr;\n\tcounter = new Counter();\n\tcounter->add();\n}\n \n//复制构造函数，新的共享指针指向旧的共享指针所指对象\ntemplate<typename T>\nSp<T>::Sp(const Sp &obj)\n{\n    //将所指对象也变为目标所指的对象\n\tmy_ptr = obj.my_ptr;\n    //获取引用计数器，使得两个共享指针用一个引用计数器\n\tcounter = obj.counter;\n    //使这个对象的引用计数器 +1\n\tcounter->add();\t\n};\n \n//重载=\ntemplate<typename T>\nSp<T> &Sp<T>::operator=(const Sp&obj)\n{\n    //清理当前所引用对象和引用计数器\n\tclear();\n    //指向新的对象，并获取目标对象的引用计数器\n\tmy_ptr = obj.my_ptr;\n\tcounter = obj.counter;\n    //引用计数器 +1\n\tcounter->add();\n    //返回自己\n\treturn *this;\t\n}\n \n//创建一个共享指针指向目标类，构造一个新的引用计数器\ntemplate<typename T>\nSp<T>::Sp(T *ptr)\n{\n\tmy_ptr = ptr;\n\tcounter = new Counter();\n}\n \n//析构函数，出作用域的时候，调用清理函数\ntemplate<typename T>\nSp<T>:: ~Sp()\n{\n\tclear();\n}\n \n//清理函数，调用时将引用计数器的值减 1，若减为 0，清理指向的对象内存区域\ntemplate<typename T>\nvoid Sp<T>::clear()\n{\n    //引用计数器 -1 \n\tcounter->sub();\n    //如果引用计数器变为 0，清理对象\n\tif(0 == counter->get())\n\t{\n\t\tif(my_ptr)\n\t\t{\n\t\t\tdelete my_ptr;\n\t\t}\n\t\tdelete counter;\n\t}\n}\n \n//当前共享指针指向的对象，被几个共享指针所引用\ntemplate<typename T>\nint Sp<T>::getcount()\n{\n\treturn counter->get();\t\n}\n\ntemplate<typename T>\nT * sp<T>::get()\n{\n    return my_ptr;\n}\n

\n","createdAt":"2024-08-11 14:26:42.707144","updatedAt":"2024-09-19 13:17:25.924052","replyToPostNumber":null,"replyCount":0,"likeCount":1,"wordCount":2453,"liked":false,"bookmarked":false,"polls":[],"reactions":[{"reaction":"❤️","count":1,"users":[{"id":4668,"username":"IO","name":null}],"hasReacted":false}],"wiki":false,"version":4,"publicVersion":4,"deletedAt":null,"isAnonymous":false,"user":{"id":199,"username":"Lrefrain","name":null,"avatarUrl":"/uploads/image/97/69/9769ddd94c97978cf278e3b4b997ba4b7cfb26abaa7f18aa567820370b7a8a5b.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":38603,"postNumber":11,"raw":"**LRU 替换算法实现**\n一个 leetcode 题，要求 O(1) 查找 O(1) 以 LRU 方式替换 cacheline。\n使用双向链表实现即可，用 STL list 比较方便。\n```\nclass LRUCache {\npublic:\n LRUCache(int capacity) {\n this->capacity=capacity;\n }\n \n int get(int key) {\n auto pos=_lruHash.find(key);\n if(pos!=_lruHash.end()){\n //Cache 命中，调整计数器更新 key 对应的节点的位置\n list>::iterator ptr=pos->second;\n //转移节点库函数 std::list::splice\n //void splice (iterator position, list& x, iterator i);\n //Transfers elements from x into the container, inserting them at position.\n //将 x 的第 i 个节点转移带 position 位置上\n _lruCacheList.splice(_lruCacheList.begin(), ptr);\n return pos->second->second;\n }\n return -1;\n }\n \n void put(int key, int value) {\n auto pos=_lruHash.find(key);\n if(pos!=_lruHash.end()){\n //更新 Cache，更新对应节点的位置\n list>::iterator ptr=pos->second;\n ptr->second=value;//更新数据\n _lruCacheList.splice(_lruCacheList.begin(),ptr);\n }\n else{\n //新增 Cache\n if(capacity==_lruHash.size()){\n //满了，替换删除尾上的数据\n pair&back=_lruCacheList.back();\n _lruHash.erase(back.first);\n _lruCacheList.pop_back();\n }\n _lruCacheList.push_front(make_pair(key,value));\n _lruHash[key]=_lruCacheList.begin();\n }\n }\nprivate:\n unordered_map>::iterator>_lruHash;//方便查找\n list>_lruCacheList;//保存数据\n size_t capacity;\n};\n\n/\\*\\*\n \\* Your LRUCache object will be instantiated and called as such:\n \\* LRUCache\\* obj = new LRUCache(capacity);\n \\* int param\\_1 = obj->get(key);\n \\* obj->put(key,value);\n \\*/\n\n```\n页表的 LRU 替换也类似。","cooked":"

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

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

页表的 LRU 替换也类似。

\n","createdAt":"2024-08-11 15:17:20.160729","updatedAt":"2024-08-11 15:17:20.160729","replyToPostNumber":null,"replyCount":1,"likeCount":1,"wordCount":245,"liked":false,"bookmarked":false,"polls":[],"reactions":[{"reaction":"❤️","count":1,"users":[{"id":4668,"username":"IO","name":null}],"hasReacted":false}],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":199,"username":"Lrefrain","name":null,"avatarUrl":"/uploads/image/97/69/9769ddd94c97978cf278e3b4b997ba4b7cfb26abaa7f18aa567820370b7a8a5b.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":38604,"postNumber":12,"raw":"

\n# 虚拟内存和内存分配？\n摘抄一下这篇文章 https://blog.csdn.net/weixin_60630451/article/details/130378350\n## 物理地址\n1. 内存空间利用率的问题\n各个进程对内存的使用会导致内存碎片化，当要用 malloc 分配一块很大的内存空间时，可能会出现虽然有足够多的空闲物理内存，却没有足够大的连续空闲内存这种情况，东一块西一块的内存碎片就被浪费掉了\n\n2. 读写内存的安全性问题\n物理内存本身是不限制访问的，任何地址都可以读写，而现代操作系统需要实现不同的页面具有不同的访问权限，例如只读的数据等等\n\n3. 进程间的安全问题\n各个进程之间没有独立的地址空间，一个进程由于执行错误指令或是恶意代码都可以直接修改其它进程的数据，甚至修改内核地址空间的数据，这是操作系统所不愿看到的\n\n4. 内存读写的效率问题\n当多个进程同时运行，需要分配给进程的内存总和大于实际可用的物理内存时，需要将其他程序暂时拷贝到硬盘当中，然后将新的程序装入内存运行。由于大量的数据频繁装入装出，内存的使用效率会非常低。\n\n## 虚拟内存\n\n### 内存分段\n1、内存分段\n 将虚拟内存分段，比如代码段、数据段、栈段、堆段等。\nA、分段机制下，物理内存与虚拟内存如何映射的\n 分段机制里，由段选择因子和段内偏移量\n段选择因子：保存在段寄存器中，里面包含有段号、标志位等。段号指向段表，段表保存段的基地址、段的界限和特权等级等。\n段内偏移：一般物理地址等于段基地址 + 段内偏移。\n\nB、存在问题：\n内存碎片\n 内存分段是按需分配，不会产生内部碎片，但是会产生外部碎片，可能会产生多个离散的空闲内存分区不太容易复用。解决外部碎片的方法是内存交换，把虚拟内存的各段先一个个交换到外存，存到硬盘，再一个个交换过去，内存交换效率低。\n如果内存交换的时候，交换的是一个占内存空间很大的程序，这样整个机器都会显得卡顿。\n\n### 内存分页\n分页是把整个虚拟和物理内存空间切成一段段固定尺寸的大小。这样一个连续并且尺寸固定的内存空间，我们叫页。在 Linux 下，每一页的大小为 4KB。\n\n内存分页产生页表和虚拟页号\n\n一般来说，物理地址是知道虚拟页号和页内偏移，然后根据虚拟页号（虚拟页号是页表的索引项），到相应的页表（页表是存储在内存中的）中查找到物理页号，物理页号 + 页内偏移等于物理地址 ——（其中主要是 MMU 内存管理单元发挥作用）\n\nA、存在问题：\n内存碎片\n分页机制不是按需分配，是分配适当的页表，页表每个是固定大小 4K，所以会产生内部碎片，因为大概率会有一个页表不是完全填充的。这就是内部碎片问题。\n\n分页机制解决内存交换效率低的问题：\n分页机制，在内存交换的时候只交换几个页，在此过程中，会有换入、换出操作，就是将内存页面从内存换入或换出到磁盘。相比于分段机制将整个段进行内存与磁盘间的交换，提高了内存交换的效率。\n\n存放页表会占用内存（空间上的缺陷）\n因为操作系统是可以同时运行非常多的进程的，那这不就意味着页表会非常的庞大。\n在 32 位的环境下，虚拟地址空间共有 4GB，假设一个页的大小是 4KB（2^12），那么就需要大约 100 万（2^20）个页，每个「页表项」需要 4 个字节大小来存储，那么整个 4GB 空间的映射就需要有 4MB 的内存来存储页表。但是要知道每个进程都是有自己的虚拟地址空间的，也就说都有自己的页表。多进程就需要耗费很多内存。\n如何解决分页机制的占用内存的问题：\n采用多级页表。由于局部性原理，对于大多数程序，其用到的空间远小于 4G，所以其对应的页表项有的是空的，所以如果某个一级页表的页表项没有被用到，也就不需要创建这个页表项对应的二级页表了，即可以在需要时才创建二级页表，这样占用的内存空间就是大大减少。\n\n### 虚拟内存好处\n第一，虚拟内存可以使得进程对运行内存超过物理内存大小，因为程序运行符合局部性原理，CPU 访问内存会有很明显的重复访问的倾向性，对于那些没有被经常使用到的内存，我们可以把它换出到物理内存之外，比如硬盘上的 swap 区域。\n第二，由于每个进程都有自己的页表，所以每个进程的虚拟内存空间就是相互独立的。进程也没有办法访问其他进程的页表，所以这些页表是私有的，这就解决了多进程之间地址冲突的问题。\n第三，页表里的页表项中除了物理地址之外，还有一些标记属性的比特，比如控制一个页的读写权限，标记该页是否存在等。在内存访问方面，操作系统提供了更好的安全性。\n第四，解决物理内存的离散式存储问题，虚拟内存中连续存储解决了物理内存碎片化资源利用率过低的问题。\n\n## 内存分配\n用户态调用 malloc 会分配堆的内存空间，实际上完成了一次内存映射。\n内存映射对应的系统调用主要有 brk() 和 mmap()，小块内存（<128K）使用 brk 来分配内存，大块内存（>128K），使用 mmap 来分配内存。\n\n### brk\n小块内存在释放的时候，不会立即释放，而是被缓存起来，可以通过 brk 来重复利用。这种方式减少了缺页中断发生的频率，提高了访存效率，但是这种方式容易造成内存碎片化。\n\n### mmap\n大块内存在释放的时候直接归还系统，每次 mmap 必发生缺页中断，频繁内存分配会造成大量缺页中断，降低性能。","cooked":"

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

\n
读写内存的安全性问题
\n物理内存本身是不限制访问的，任何地址都可以读写，而现代操作系统需要实现不同的页面具有不同的访问权限，例如只读的数据等等
\n
\n
进程间的安全问题
\n各个进程之间没有独立的地址空间，一个进程由于执行错误指令或是恶意代码都可以直接修改其它进程的数据，甚至修改内核地址空间的数据，这是操作系统所不愿看到的
\n
\n
内存读写的效率问题
\n当多个进程同时运行，需要分配给进程的内存总和大于实际可用的物理内存时，需要将其他程序暂时拷贝到硬盘当中，然后将新的程序装入内存运行。由于大量的数据频繁装入装出，内存的使用效率会非常低。
\n

虚拟内存

内存分段

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

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

内存分页

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

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

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

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

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

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

虚拟内存好处

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

内存分配

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

brk

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

mmap

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

\n","createdAt":"2024-08-11 15:56:54.340777","updatedAt":"2024-09-19 13:17:40.319637","replyToPostNumber":null,"replyCount":0,"likeCount":1,"wordCount":1918,"liked":false,"bookmarked":false,"polls":[],"reactions":[{"reaction":"❤️","count":1,"users":[{"id":4668,"username":"IO","name":null}],"hasReacted":false}],"wiki":false,"version":3,"publicVersion":3,"deletedAt":null,"isAnonymous":false,"user":{"id":199,"username":"Lrefrain","name":null,"avatarUrl":"/uploads/image/97/69/9769ddd94c97978cf278e3b4b997ba4b7cfb26abaa7f18aa567820370b7a8a5b.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":38611,"postNumber":13,"raw":"我让 gpt 给我做也是这个写法","cooked":"

我让 gpt 给我做也是这个写法

\n","createdAt":"2024-08-12 06:22:03.97394","updatedAt":"2024-08-12 06:22:03.97394","replyToPostNumber":11,"replyCount":1,"likeCount":0,"wordCount":12,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":178,"username":"Hypocrisy","name":"rotartsinimdA","avatarUrl":"/uploads/image/ce/f3/cef3773e378e161524cc7523c8a63dff0698d22802b0c1ab669894d395ee36a3.avif","admin":false,"moderator":true,"signatureRaw":null,"signatureCooked":null}},{"id":38613,"postNumber":14,"raw":"哪个啊？LRU 那个？我都上网随便看了几眼粘了一份","cooked":"

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

\n","createdAt":"2024-08-12 07:08:00.778574","updatedAt":"2024-08-12 07:08:00.778574","replyToPostNumber":13,"replyCount":0,"likeCount":0,"wordCount":21,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":199,"username":"Lrefrain","name":null,"avatarUrl":"/uploads/image/97/69/9769ddd94c97978cf278e3b4b997ba4b7cfb26abaa7f18aa567820370b7a8a5b.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":38631,"postNumber":15,"raw":"[quote=\"Lrefrain, post:4, topic:13232\"]\nCRTP\n[/quote]\n\n有没有可能，CRTP 和虚函数不是一个层面上的东西。虚函数对应的是动态派发。","cooked":"

\n\t\t\t\t\t\t\t

\n\t\t\t\t\t\t\t\t

\n\t\t\t\t\t\t\t\t\t

\n\t\t\t\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\t\t

\n\t\t\t\t\t\t\t\t\tLrefrain:\n\t\t\t\t\t\t\t\t

\n\t\t\t\t\t\t\t\t

\n\t\t\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\t

\n\t\t\t\t\t\t\t

\n
CRTP
\n

\n\t\t\t\t\t\t

有没有可能，CRTP 和虚函数不是一个层面上的东西。虚函数对应的是动态派发。

\n","createdAt":"2024-08-13 07:10:07.080926","updatedAt":"2024-08-13 07:10:07.080926","replyToPostNumber":4,"replyCount":1,"likeCount":0,"wordCount":38,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":3339,"username":"Ziqian_Chen","name":"Ziqian Chen","avatarUrl":"/uploads/image/83/a4/83a4ff188ae1e07941b5aeb4feb519adc01e1213fe205ed6375e00914355a9f7.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":38632,"postNumber":16,"raw":"我哪句话写的有问题吗？\n对比 CRTP 和虚函数的优劣是 Jump 面试时候问的原题","cooked":"

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

\n","createdAt":"2024-08-13 07:56:48.935673","updatedAt":"2024-08-13 08:11:47.056467","replyToPostNumber":15,"replyCount":1,"likeCount":0,"wordCount":31,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":2,"publicVersion":2,"deletedAt":null,"isAnonymous":false,"user":{"id":199,"username":"Lrefrain","name":null,"avatarUrl":"/uploads/image/97/69/9769ddd94c97978cf278e3b4b997ba4b7cfb26abaa7f18aa567820370b7a8a5b.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":38642,"postNumber":17,"raw":"你妹提优点","cooked":"

你妹提优点

\n","createdAt":"2024-08-14 03:53:41.045134","updatedAt":"2024-08-14 03:53:41.045134","replyToPostNumber":16,"replyCount":1,"likeCount":0,"wordCount":5,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":3339,"username":"Ziqian_Chen","name":"Ziqian Chen","avatarUrl":"/uploads/image/83/a4/83a4ff188ae1e07941b5aeb4feb519adc01e1213fe205ed6375e00914355a9f7.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":38643,"postNumber":18,"raw":"奥奥，比较的时候应该是限定了 crtp 和虚函数都可以实现的场景，不过确实可以补充一下，CRTP 不能动态派发。\n两方的优点都写在对方的缺点里了，反过来看就行","cooked":"

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

\n","createdAt":"2024-08-14 03:56:07.978861","updatedAt":"2024-08-14 03:56:07.978861","replyToPostNumber":17,"replyCount":0,"likeCount":0,"wordCount":68,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":199,"username":"Lrefrain","name":null,"avatarUrl":"/uploads/image/97/69/9769ddd94c97978cf278e3b4b997ba4b7cfb26abaa7f18aa567820370b7a8a5b.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":38689,"postNumber":19,"raw":"C++ 支持 RTTI 的三种主要形式是什么？\n\n（感觉这道笔试题出的太烂）\n\n常见：typeid + dynamic_cast\n\n似乎还有一个 std::bad_cast","cooked":"

C++ 支持 RTTI 的三种主要形式是什么？

（感觉这道笔试题出的太烂）

常见：typeid + dynamic_cast

似乎还有一个 std::bad_cast

\n","createdAt":"2024-08-15 06:35:28.558944","updatedAt":"2024-08-15 06:35:28.558944","replyToPostNumber":null,"replyCount":0,"likeCount":0,"wordCount":40,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":178,"username":"Hypocrisy","name":"rotartsinimdA","avatarUrl":"/uploads/image/ce/f3/cef3773e378e161524cc7523c8a63dff0698d22802b0c1ab669894d395ee36a3.avif","admin":false,"moderator":true,"signatureRaw":null,"signatureCooked":null}},{"id":39130,"postNumber":20,"raw":"

\n\n# 内存屏障与编译器屏障（C++）\n\n## 内存屏障与内存顺序\n\n**内存屏障**用来阻止处理器重排内存操作，是硬件或编译器层面上的工具。\n\n**内存顺序**指在多线程程序中多个线程如何观察彼此的读写操作，是 C++ 提供的高级抽象。它通过指定不同的内存顺序模型**隐式地插入内存屏障**。程序员不需要直接操作内存屏障，而是通过原子操作与内存顺序模型来实现对内存访问顺序的控制。\n\n二者都是为了控制内存操作，防止指令重排、缓存一致性问题带来的意料之外的错误\n\n## 内存顺序\n\n讨论的是**单线程内指令执行顺序对多线程影响**的问题。不论携带怎样的内存顺序，单独的操作只会影响单个线程，但几个线程可能会经由变量的同步建立间接的顺序关系，从而被各自的内存顺序影响。\n\n### 内存顺序标记\n\nc++ 标准库定义了 6 种内存顺序，按照从宽松到严格的顺序：\n\n1. **`memory_order_relaxed`**：宽松操作，仅保证原子操作自身的原子性\n2. **`memory_order_consume`**：读屏障，只影响当前 load 原子变量及依赖变量的写入，其他与 `memory_order_acquire` 一样。C++20 中弃用\n3. **`memory_order_acquire`**：读屏障，当前线程所有的读写操作不得重排至当前操作之前，使得其他线程中相同原子变量在 release 之前的写入对当前线程时可见的。即对于相关内存位置的 load 施加“acquire”占有，一定读到最新值。\n4. **`memory_order_release`**：写屏障，当前线程所有的读写操作不得重排至当前操作之后，使得当前操作的写入对于其他线程中相同原子变量在 acquire 之后是可见的。即对于相关内存位置的 store 施加“release”释放，一定写入最新值。\n5. **`memory_order_acq_rel`**：读写屏障，当前线程中的读写操作不能重排至当前操作之后也不能重排至当前操作之前\n6. **`memory_order_seq_cst`**：读写屏障，对于所有线程看见的读写操作顺序是一致的\n\n其中\n\n- 所有原子操作默认的内存顺序标记是 `std::memory_order_seq_cst`\n- 两种读屏障：`memory_order_consume` 只影响当前变量和依赖它的变量；`memory_order_acquire` 影响当前操作前的所有变量\n- 两种写屏障：`memory_order_acq_rel` 只对当前线程有效；`memory_order_seq_cst` 对全局有效\n\n### 协作组合\n\n常见的几种协作组合：\n\n- **宽松顺序：`memory_order_relaxed`**\n\n 仅保证原子性，允许所有指令重排\n\n- **释放 - 获得序：`memory_order_release`+`memory_order_acquire`**\n\n release 前的写操作一定到位，acquire 的读操作一定最新\n\n+ **释放 - 消费序：`memory_order_release`+` memory_order_consume`**\n\n 比释放获得序宽松一些，仅同步了原子操作本身的原子变量及与它产生依赖关系的变量\n\n+ **序列一致顺序 `memory_order_seq_cst`**\n\n 拒绝一切重排，对所有线程可见\n\n举个例子：\n\n首先定义两个变量\n\n```c++\nstd::atomic ptr;\nint data;\n```\n\n对于释放获得序：\n\n```c++\nvoid producer() {\n auto *p = new std::string(\"Hello\");\n data = 42;\n // 编译器不能将 data = 42 这条指令移动到 store 操作之后\n // memory_order_release 将修改后（写操作）的结果释放出来，其他线程使用 memory_order_acquire 可以观测到上述对内存写入的结果。此处保证 producer 的修改一定写入\n ptr.store(p, std::memory_order_release);\n}\n\nvoid consumer() {\n std::string *p2;\n // memory_order_acquire 读取到最新值，其他线程使用 memory_order_release 前的值一定可以读到。此处保证 consumer 一定读取到 producer 写入的值\n while (!(p2 = ptr.load(std::memory_order_acquire)))\n ;\n // 执行到此处说明 p2 是非空的，即 data = 42 的指令已经执行了（memory_order_release 保证）\n // 且此时 data 必定等于 42，p2 必定为“Hello”（memory_order_acquire 保证）\n assert(*p2 == \"Hello\");\n assert(data == 42); \n // 不会出错\n}\n```\n\n对于释放消费序：\n\n```c++\nvoid producer() {\n std::string* p = new std::string(\"Hello\");\n data = 42;\n ptr.store(p, std::memory_order_release);\n}\n \nvoid consumer() {\n std::string* p2;\n while (!(p2 = ptr.load(std::memory_order_consume)))\n ;\n assert(*p2 == \"Hello\"); // 不会出错：*p2 从 ptr 携带依赖\n assert(data == 42); // 有可能出错：data 不从 ptr 携带依赖\n}\n```\n\n## 内存屏障\n\nc++ 标准库中提供接口\n\n+ **`std::atomic_thread_fence`**：显式的**内存屏障**。与内存顺序标记配合使用，将线程分为若干个阶段，每个阶段需要等待其他线程完成特定操作之后才能进入下一阶段。对于所有数据有效，不仅仅是原子变量。\n\n使用时可以将原子变量都设置为 `memory_order_relaxed`，仅依靠内存屏障来实现对内存的控制\n\n例子：\n\n```c++\nstd::atomic x,y;\nvoid write_x_then_y() {\n x.store(true, std::memory_order_relaxed); // 1\n std::atomic_thread_fence(std::memory_order_release); // 2.a 写屏障\n y.store(true, std::memory_order_relaxed); // 2.b\n}\nvoid read_y_then_x() {\n while(!y.load(std::memory_order_relaxed)); // 3.a\n std::atomic_thread_fence(std::memory_order_acquire); // 3.b 读屏障\n assert(!x.load(std::memory_order_relaxed));// 4\n}\n```\n\n可以认为：\n\n+ 2.a 写屏障向下和 2.b 写操作相结合，将 2.b 提升为 release-store\n+ 3.b 读屏障向上和 3.a 读操作相结合，将 3.a 提升为 acquire-load\n+ 同步关系与前面举的内存顺序的例子相似，保证了 1 一定先于 4\n\n## 内存屏障与编译器屏障\n\n**编译器屏障**仅影响编译器。防止编译器重排指令，确保最终生成的汇编代码保留了源代码中指定的顺序，但不会生成实际的硬件指令，因此不会影响 CPU 或内存的访问顺序。不能处理线程并发带来的缓存一致性、内存可见性问题，常用于**单核**处理器。\n\n**内存屏障**同时影响编译器与 CPU。不仅防止编译器重排操作，还会生成硬件指令影响 CPU 的内存访问顺序。确保线程之间的数据同步，常用于**多核**处理器。\n\n## 编译器屏障\n\n\n\n+ **`std::atomic_signal_fence`** ：编译器屏障，对所有数据有效。用于防止编译器在信号处理程序或与硬件交互时重排指令。\n+ **`volatile` 关键字**：\n + 对于某个 volatile 变量，与该变量相关的操作必须对内存进行读写，而不能仅仅读写寄存器中的缓存值。\n + 对于多个 volatile 变量，它们之间的访问顺序不会被编译器改变\n\n编译器屏障相当于告诉编译器，这些变量的值可能会在程序的控制之外发生变化，不可以假设其不变。常用于信号处理、硬件交互、嵌入式系统中断程序。\n\n举个例子：\n\n```c++\n// thread1\nvolatile bool tag = true;\nvolatile int x = 0;\nwhile(tag);\nassert(!x);\n\n// thread2\nx = 10;\ntag = false;\n```\n\n在单核处理器上“伪并发”这两个线程，volatile 在此处有两个作用：\n\n+ 每次都从内存中读取 tag 最新值，避免 thread1 死循环\n+ x 和 tag 的读写顺序和源代码中一致，即 x=10 一定发生在 tag=false 之前\n\n但在多核处理器上“真并发”这两个线程时，即使 `volatile` 强制编译器生成了从主存读写的代码，具体执行顺序仍然由 CPU 决定。此时就需要使用内存屏障来实现需求的逻辑，保证内存操作按照指定顺序执行。","cooked":"

内存屏障与编译器屏障（C++）

内存屏障与内存顺序

内存屏障用来阻止处理器重排内存操作，是硬件或编译器层面上的工具。

内存顺序指在多线程程序中多个线程如何观察彼此的读写操作，是 C++ 提供的高级抽象。它通过指定不同的内存顺序模型隐式地插入内存屏障。程序员不需要直接操作内存屏障，而是通过原子操作与内存顺序模型来实现对内存访问顺序的控制。

二者都是为了控制内存操作，防止指令重排、缓存一致性问题带来的意料之外的错误

内存顺序

讨论的是单线程内指令执行顺序对多线程影响的问题。不论携带怎样的内存顺序，单独的操作只会影响单个线程，但几个线程可能会经由变量的同步建立间接的顺序关系，从而被各自的内存顺序影响。

内存顺序标记

c++ 标准库定义了 6 种内存顺序，按照从宽松到严格的顺序：

memory_order_relaxed：宽松操作，仅保证原子操作自身的原子性
memory_order_consume：读屏障，只影响当前 load 原子变量及依赖变量的写入，其他与 memory_order_acquire 一样。C++20 中弃用
memory_order_acquire：读屏障，当前线程所有的读写操作不得重排至当前操作之前，使得其他线程中相同原子变量在 release 之前的写入对当前线程时可见的。即对于相关内存位置的 load 施加“acquire”占有，一定读到最新值。
memory_order_release：写屏障，当前线程所有的读写操作不得重排至当前操作之后，使得当前操作的写入对于其他线程中相同原子变量在 acquire 之后是可见的。即对于相关内存位置的 store 施加“release”释放，一定写入最新值。
memory_order_acq_rel：读写屏障，当前线程中的读写操作不能重排至当前操作之后也不能重排至当前操作之前
memory_order_seq_cst：读写屏障，对于所有线程看见的读写操作顺序是一致的

其中

所有原子操作默认的内存顺序标记是 std::memory_order_seq_cst
两种读屏障：memory_order_consume 只影响当前变量和依赖它的变量；memory_order_acquire 影响当前操作前的所有变量
两种写屏障：memory_order_acq_rel 只对当前线程有效；memory_order_seq_cst 对全局有效

协作组合

常见的几种协作组合：

\n
宽松顺序：memory_order_relaxed
\n
仅保证原子性，允许所有指令重排
\n
\n
释放 - 获得序：memory_order_release+memory_order_acquire
\n
release 前的写操作一定到位，acquire 的读操作一定最新
\n

\n
释放 - 消费序：memory_order_release+ memory_order_consume
\n
比释放获得序宽松一些，仅同步了原子操作本身的原子变量及与它产生依赖关系的变量
\n
\n
序列一致顺序 memory_order_seq_cst
\n
拒绝一切重排，对所有线程可见
\n

举个例子：

首先定义两个变量

std::atomic<std::string *> ptr;\nint data;\n

对于释放获得序：

void producer() {\n  auto *p = new std::string(\"Hello\");\n  data = 42;\n  // 编译器不能将 data = 42 这条指令移动到 store 操作之后\n  // memory_order_release 将修改后（写操作）的结果释放出来，其他线程使用 memory_order_acquire 可以观测到上述对内存写入的结果。此处保证 producer 的修改一定写入\n  ptr.store(p, std::memory_order_release);\n}\n\nvoid consumer() {\n  std::string *p2;\n  // memory_order_acquire 读取到最新值，其他线程使用 memory_order_release 前的值一定可以读到。此处保证 consumer 一定读取到 producer 写入的值\n  while (!(p2 = ptr.load(std::memory_order_acquire)))\n    ;\n  // 执行到此处说明 p2 是非空的，即 data = 42 的指令已经执行了（memory_order_release 保证）\n  // 且此时 data 必定等于 42，p2 必定为“Hello”（memory_order_acquire 保证）\n  assert(*p2 == \"Hello\");\n  assert(data == 42); \n  // 不会出错\n}\n

对于释放消费序：

void producer() {\n    std::string* p  = new std::string(\"Hello\");\n    data = 42;\n    ptr.store(p, std::memory_order_release);\n}\n \nvoid consumer() {\n    std::string* p2;\n    while (!(p2 = ptr.load(std::memory_order_consume)))\n        ;\n    assert(*p2 == \"Hello\"); // 不会出错：*p2 从 ptr 携带依赖\n    assert(data == 42); // 有可能出错：data 不从 ptr 携带依赖\n}\n

内存屏障

c++ 标准库中提供接口

std::atomic_thread_fence：显式的内存屏障。与内存顺序标记配合使用，将线程分为若干个阶段，每个阶段需要等待其他线程完成特定操作之后才能进入下一阶段。对于所有数据有效，不仅仅是原子变量。

使用时可以将原子变量都设置为 memory_order_relaxed，仅依靠内存屏障来实现对内存的控制

例子：

std::atomic<bool> x,y;\nvoid write_x_then_y() {\n    x.store(true, std::memory_order_relaxed); // 1\n    std::atomic_thread_fence(std::memory_order_release); // 2.a 写屏障\n    y.store(true, std::memory_order_relaxed); // 2.b\n}\nvoid read_y_then_x() {\n    while(!y.load(std::memory_order_relaxed)); // 3.a\n    std::atomic_thread_fence(std::memory_order_acquire); // 3.b 读屏障\n    assert(!x.load(std::memory_order_relaxed));// 4\n}\n

可以认为：

2.a 写屏障向下和 2.b 写操作相结合，将 2.b 提升为 release-store
3.b 读屏障向上和 3.a 读操作相结合，将 3.a 提升为 acquire-load
同步关系与前面举的内存顺序的例子相似，保证了 1 一定先于 4

内存屏障与编译器屏障

编译器屏障仅影响编译器。防止编译器重排指令，确保最终生成的汇编代码保留了源代码中指定的顺序，但不会生成实际的硬件指令，因此不会影响 CPU 或内存的访问顺序。不能处理线程并发带来的缓存一致性、内存可见性问题，常用于单核处理器。

内存屏障同时影响编译器与 CPU。不仅防止编译器重排操作，还会生成硬件指令影响 CPU 的内存访问顺序。确保线程之间的数据同步，常用于多核处理器。

编译器屏障

std::atomic_signal_fence ：编译器屏障，对所有数据有效。用于防止编译器在信号处理程序或与硬件交互时重排指令。
volatile 关键字：\n
- 对于某个 volatile 变量，与该变量相关的操作必须对内存进行读写，而不能仅仅读写寄存器中的缓存值。
- 对于多个 volatile 变量，它们之间的访问顺序不会被编译器改变
\n

编译器屏障相当于告诉编译器，这些变量的值可能会在程序的控制之外发生变化，不可以假设其不变。常用于信号处理、硬件交互、嵌入式系统中断程序。

举个例子：

// thread1\nvolatile bool tag = true;\nvolatile int x = 0;\nwhile(tag);\nassert(!x);\n\n// thread2\nx = 10;\ntag = false;\n

在单核处理器上“伪并发”这两个线程，volatile 在此处有两个作用：

每次都从内存中读取 tag 最新值，避免 thread1 死循环
x 和 tag 的读写顺序和源代码中一致，即 x=10 一定发生在 tag=false 之前

但在多核处理器上“真并发”这两个线程时，即使 volatile 强制编译器生成了从主存读写的代码，具体执行顺序仍然由 CPU 决定。此时就需要使用内存屏障来实现需求的逻辑，保证内存操作按照指定顺序执行。

\n","createdAt":"2024-08-27 06:59:51.700799","updatedAt":"2025-09-13 07:59:05.079674","replyToPostNumber":6,"replyCount":1,"likeCount":4,"wordCount":1953,"liked":false,"bookmarked":false,"polls":[],"reactions":[{"reaction":"💯️","count":1,"users":[{"id":1288,"username":"LittleWangInShanghai","name":"小王在上海"}],"hasReacted":false},{"reaction":"❤️","count":4,"users":[{"id":199,"username":"Lrefrain","name":null},{"id":723,"username":"Luan_233","name":"ljj"},{"id":1288,"username":"LittleWangInShanghai","name":"小王在上海"},{"id":1381,"username":"greyishsong","name":"greyishsong"}],"hasReacted":false}],"wiki":false,"version":4,"publicVersion":4,"deletedAt":null,"isAnonymous":false,"user":{"id":4263,"username":"Murphy","name":null,"avatarUrl":"/uploads/image/73/16/7316507ede092b0d40102e861ffcee19a42447b50855285f66c9b0195b36b03f.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}}],"hasMore":true,"lastReadPostNumber":14,"hasUrlPostNumber":true}

预处理

编译

汇编

链接

可重定位目标文件

静态链接

静态链接优缺点

动态链接

动态链接的加载时重定位

动态链接优缺点

加载

原子操作和原子类型

std::atomic

CAS 操作

C++ 内存序

用户态和内核态

pthread(POXIS thread)

互斥锁和自旋锁

条件变量

阻塞式循环队列

无锁循环队列

shared_ptr

虚拟内存

内存分段

内存分页

虚拟内存好处

内存分配

brk

mmap

内存屏障与编译器屏障（C++）

内存屏障与内存顺序

内存顺序

内存顺序标记

协作组合

内存屏障

内存屏障与编译器屏障

编译器屏障